Method and apparatus for storing and updating information in a multi-cast system

• US 7,007,040 B1
• Filed: 12/04/2001
• Issued: 02/28/2006
• Est. Priority Date: 12/04/2001
• Status: Active Grant

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Inventors: Stephens, George, Duke, Andrew
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): EHICHIOYA, IRETE FRED
• Application Number:
  US10/004,126
• Time in Patent Office: 1,547 Days
• Field of Search: 707/1, 707/2, 707/3, 707/100, 707/101.R, 707/102, 707/103.R, 707/203, 707/4, 707/5, 707/6, 707/7, 707/200, 709/203, 709/231, 341/50
• US Class Current: 1/1
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and apparatus for storing and updating information in a multicast system is represented by a tree data structure. The method and apparatus defines and populates a set of keys for each node in the tree. The number and content of the set of keys may vary depending on whether a node is an internal node or a leaf node. The method and apparatus can use these keys to update information in some leaves while excluding the information from other leaves. The method and apparatus can analyze the system to determine a minimum number of messages that need to be sent in order to update the information stored in leaves. The method and apparatus then sends the minimum number of messages throughout the system where each message can only be read by a particular subset set of the leaves that have the correct key to read that particular message.

Claims

1. A computer implemented method for storing and updating information in a network having n hierarchical levels, said method comprising the steps of:

defining a root node positioned in a first of said levels, said root node having no parent node and at least one child node;

defining at least two leaf nodes positioned within an nth of said hierarchical levels, each of said leaf nodes having a parent node and no child node;

defining a corresponding path between each of said at least two leaf nodes and said root node;

associating each non-leaf node with a corresponding set of keys wherein each key in said corresponding set of keys further corresponds to at least one child node of said non-leaf node; and

providing each leaf node with a related set of keys, wherein said related set of keys includes each key associated with each non-leaf node on said corresponding path from said leaf node to said root node wherein said corresponding set of keys associated with each non-leaf node includes 2^m−

1 keys where m is the maximum number of child nodes that may be associated with each non-leaf node.

2. The method of claim 1 wherein each non-leaf node is associated with more than two child nodes.

3. The method of claim 1 wherein each non-leaf node is associated with the same number of child nodes.

4. The method of claim 1 further comprising the step of defining an internal node positioned on said corresponding path between said root node and a first of said leaf nodes, said internal node being associated with a hierarchal level between said first level and said nth level.

5. The method of claim 1 further comprising the step of identifying a specific one of said leaf nodes as a compromised leaf node.

6. The method of claim 5 further comprising the step of removing at least a portion of said corresponding path associated with said compromised leaf node.

7. The method of claim 5 comprising the step of marking a key in said set of keys related to said compromised leaf node as a compromised key.

8. The method of claim 7 further comprising the step of sending a message from said root node to a non-compromised leaf node using a key that has not been marked as a compromised key.

9. The method of claim 1 further compromising the step of identifying each of one or more specific leaf nodes as a compromised leaf node.

10. The method of claim 9 further compromising the step of removing at least a portion of said path between each of said one or more compromised leaf nodes and said root node.

11. The method of claim 9 further comprising the step of marking a key in said set of keys related to each of said one or more compromised leaf nodes as a compromised key.

12. The method of claim 11 further comprising the step of sending a message from said root node to a non-compromised leaf node using a key that has not been marked as a compromised key.

13. A computer implemented method for storing and updating information in a network having n hierarchical levels, said method comprising the steps of:

defining a root node positioned in a first of said levels, said root node having no parent node and at least one child node;

defining at least two leaf nodes positioned within an nth of said hierarchical levels, each of said leaf nodes having a parent node and no child node;

defining a corresponding path between each of said at least two leaf nodes and said root node;

associating each non-leaf node with a corresponding set of keys wherein each key in said corresponding set of keys further corresponds to at least one child node of said non-leaf node; and

providing each leaf node with a related set of keys, wherein said corresponding set of keys associated with each non-leaf node includes 2^m−

2 keys where m is the maximum number of child nodes that may be associated with each non-leaf node.

14. A computer implemented method for storing and updating information in a network having n hierarchical levels, said method comprising the steps of:

defining a root node positioned in a first of said levels, said root node having no parent node and at least one child node;

defining at least two leaf nodes positioned within an nth of said hierarchical levels, each of said leaf nodes having a parent node and no child node;

defining a corresponding path between each of said at least two leaf nodes and said root node;

associating each non-leaf node with a corresponding set of keys wherein each key in said corresponding set of keys further corresponds to at least one child node of said non-leaf node; and

providing each leaf node with a related set of keys, wherein said related set of keys provided to each leaf node includes (n−

1)*(2^m−

1) keys where m is the maximum number of child nodes that may be associated with each non-leaf node.