Methods and apparatus for maintaining a map of node relationships for a network

• US 7,117,273 B1
• Filed: 12/29/2000
• Issued: 10/03/2006
• Est. Priority Date: 01/25/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: O'Toole, James, Jannotti, John H.
• Primary Examiner(s): CALDWELL, ANDREW T
• Assistant Examiner(s): Le, Hieu
• Application Number:
  US09/752,842
• Time in Patent Office: 2,104 Days
• Field of Search: 709220-224, 709238-239, 709/242, 709/252, 707/10, 707/104, 370/254, 370/408, 714/786
• US Class Current: 709/252
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

The invention is directed to techniques for maintaining a map of node relationships for a network of nodes (e.g., network of computers). In one example, the map of node relationships represents relationships overlaying and typically different from the network of physical connections among the nodes. Each child node periodically checks in with its parent nodes, and the parent nodes can thus determine when a child node has terminated a relationship with the parent or created a new relationship with a new parent. Changes in relationships propagate upward through the network of nodes so that each node maintains a map of the relationships among the descendants of that node. A root node receives the propagated change relationship information and maintains a map of the entire network and valid pathways through the network. The root node can use the map when responding to a request from a client to receive services from a node in the network and redirects the client to attach to a node in the network that has a valid path to the root node. The root node can then broadcast data (e.g. a stream of video data) throughout the network, which is received by all the clients attached to nodes in the network.

Claims

1. A method for maintaining a map of node relationships for a network of related nodes, the method comprising the steps of:

detecting a change of a relationship between a first network node and a second network node having a child relationship to the first network node, the first network node being a parent to the second network node;

generating a change relationship signal indicating the change of the relationship between the first network node and the second network node; and

transmitting the change relationship signal, having a change sequence number, to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.

2. The method of claim 1, further comprising the step of:

selectively updating a map of node relationships based on the change relationship signal having the sequence number operable for comparison with previously received sequence numbers such that the map of node relationships indicates the state of the relationship between the first network node and the second network node.

3. The method of claim 1, further comprising the steps of:

receiving a propagated change relationship signal indicating a change in a relationship between two network nodes other than the first network node; and

transmitting the propagated change relationship signal to the parent node, so that the parent node receives an update of a state of the relationship between the two network nodes.

4. The method of claim 3, further comprising the step of:

updating the map of node relationships based on the propagated change relationship signal such that the map of node relationships indicates the state of the relationship between the two network nodes other than the first network node.

5. The method of claim 1, further comprising the steps of:

receiving a plurality of propagated change relationship signals indicating a change of relationship between two network nodes, each propagated change relationship signal having a sequence number;

comparing the sequence numbers for the propagated change relationship signals;

selecting one of the propagated change relationship signals with which to update the map of node relationships based on the step of comparing the sequence numbers; and

transmitting the selected one of the propagated change relationships signals to the parent node, so that the parent node receives an update of a state of relationship between the two network nodes.

6. The method of claim 1, wherein the change relationship signal is a termination signal indicating the termination of the relationship between the first network node and the second network node.

7. The method of claim 1, wherein the change relationship signal is a creation signal indicating the creation of the relationship between the first network node and the second network node.

8. The method of claim 1, wherein the step of detecting the change of the relationship comprises initiating a check-in communication from the second network node to the first network node.

9. A method for maintaining a map of node relationships for a network of related nodes, the method comprising the steps of:

detecting a change of a relationship between a first network node and a second network node having a child relationship to the first network node, the first network node being a parent to the second network node;

generating a change relationship signal indicating the change of the relationship between the first network node and the second network node, generating the change relationship signal further comprising generating the change relationship signal having a sequence number indicating a number of relationship changes of the second network node, the sequence number representing a count of parents of the second network node; and

transmitting the change relationship signal to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.

10. A computer system comprising:

a processor;

a memory; and

an interconnection mechanism coupling the processor and the memory;

wherein the memory is encoded with logic instructions for a map maintainer application that, when performed on the processor, cause the processor to form a map maintainer that maintains a map of node relationships for the network by performing the operations of;

detecting by the processor a change of a relationship between a first network node and a second network node having a child relationship to the parent first network node;

generating a change relationship signal, the change relationship signal having a change sequence number, in the memory indicating the change of the relationship between the first network node and the second network node; and

transmitting the change relationship signal to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.

11. The computer system of claim 10, wherein the logic instructions for the map maintainer application comprise further logic instructions that, when performed on the processor, cause the map maintainer to perform the operation of selectively updating the map of node relationships based on the change relationship signal, the change relationship signal having the sequence number operable for comparison with previously received sequence numbers such that the map of node relationships indicates the state of the relationship between the first network node and the second network node.

12. The computer system of claim 10, wherein the logic instructions for the map maintainer application comprise further logic instructions that, when performed on the processor, cause the map maintainer to perform the operations of:

receiving a propagated change relationship signal indicating a change in a relationship between two network nodes other than the first network node; and

transmitting the propagated change relationship signal to the parent node, so that the parent node receives an update of a state of the relationship between the two network nodes.

13. The computer system of claim 12, wherein the logic instructions for the map maintainer application comprise further logic instructions that, when performed on the processor, cause the map maintainer to perform the operation of updating the map of node relationships based on the propagated change relationship signal such that the map of node relationships indicates the state of the relationship between the two network nodes other than the first network node.

14. The computer system of claim 10, wherein the logic instructions for the map maintainer application comprise further logic instructions that, when performed on the processor, cause the map maintainer to perform the operations of:

receiving a plurality of propagated change relationship signals indicating a change of relationship between two network nodes, each propagated change relationship signal having a sequence number;

comparing the sequence numbers for the propagated change relationship signals;

selecting one of the propagated change relationship signals with which to update the map of node relationships based on the step of comparing the sequence numbers; and

transmitting the selected one of the propagated change relationships signals to the parent node, so that the parent node receives an update of a state of relationship between the two network nodes.

15. The computer system of claim 10, wherein the change relationship signal is a termination signal indicating the termination of the relationship between the first network node and the second network node.

16. The computer system of claim 10, wherein the change relationship signal is a creation signal indicating the creation of the relationship between the first network node and the second network node.

17. The computer system of claim 10, wherein the second network node initiates a check-in communication from the second network node to the first network node.

18. A computer system comprising:

a processor;

a memory; and

an interconnection mechanism coupling the processor and the memory;

wherein the memory is encoded with logic instructions for a map maintainer application that, when performed on the processor, cause the processor to form a map maintainer that maintains a map of node relationships for the network by performing the operations of;

detecting by the processor a change of a relationship between a first network node and a second network node having a child relationship to the parent first network node;

generating a change relationship signal in the memory indicating the change of the relationship between the first network node and the second network node, the change relationship signal having a sequence number indicating a number of relationship changes of the second network node, the sequence number representing a count of parents of the second network node; and

transmitting the change relationship signal to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.

19. A computer program product having computer program instructions stored in a tangible storage medium for maintaining a map of node relationships for a network, such that the instructions, when carried out by a computer, cause the computer to perform the steps of:

detecting a change of a relationship between a first network node and a second network node having a child relationship to the parent first network node;

generating a change relationship signal having a change sequence number indicating the change of the relationship between the first network node and the second network node; and

transmitting the change relationship signal to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.

20. A computer system for maintaining a map of node relationships for a network of related nodes, the computer system comprising:

means for detecting a change of a relationship between a first network node and a second network node having a child relationship to the parent first network node;

means for generating a change relationship signal having a change sequence number indicating the change of the relationship between the first network node and the second network node; and

means for transmitting the change relationship signal to a parent node of the first network node so that the parent node receives an update of a state of the relationship between the first network node and the second network node.