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

• US 7,984,137 B2
• Filed: 05/10/2006
• Issued: 07/19/2011
• Est. Priority Date: 01/25/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jannotti, John J., O'Toole, James W. Jr.
• Primary Examiner(s): Moore; Ian N
• Assistant Examiner(s): Huynh; Dung B
• Application Number:
  US11/431,600
• Publication Number:
  US 20060218301A1
• Time in Patent Office: 1,896 Days
• Field of Search: None
• US Class Current: 709/224
• 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 of operating a computer forming a node in a hierarchical, tree-connected network of nodes extending from a root node to a plurality of end nodes, each node formed by a respective computer, the network characterized by dynamic movement of child nodes among successive different parent nodes and a need to track changing locations of child nodes to effect multicast communication of data from the root node to the end nodes, comprising:

maintaining a map of parent-child relationships of the nodes of the network;

monitoring for receipt of check-in messages from child nodes of the node at a preset interval, each check-in message including parent-child information about a reporting child node originating the check-in message and about child nodes of the reporting child node, the parent-child information including one or more change relationship signals each regarding a respective parent-child relationship at or below the reporting child node in the hierarchical network, a first type of change relationship signal reflecting creation of the respective parent-child relationship and a second type of change relationship signal reflecting termination of the respective parent-child relationship;

for each check-in message received from a child node within the preset interval, updating the map of parent-child relationships using the parent-child information in the check-in message;

if a check-in message is not received from a non-reporting child node within the preset interval, then updating the map of parent-child relationships to indicate that the non-reporting child node and its child nodes are no longer child nodes of the node; and

upon updating the map of parent-child relationships, creating one or more new change relationship signals and sending them to a parent node of the node, a first new change relationship signal reflecting creation of a new parent-child relationship between the node and a newly reporting child node, and a second new change relationship signal reflecting termination of a previous parent-child relationship between the node and a non-reporting child node,

wherein;

the map includes, for each child node identified in the map, a respective highest known sequence number reflecting a number of parents that the respective child node has had;

each change relationship signal includes a respective sequence number indicating how many parents the child node identified in the change relationship signal has had; and

updating the map of parent-child relationships includes (a) comparing a sequence number of a change relationship signal in a received check-in message to the highest known sequence number for a child node identified in the change relationship signal, and (b) modifying the map of node relationships in accordance with the change relationship signal of the received check-in message only if the sequence number of the change relationship signal is greater than the highest known sequence number.

2. A method according to claim 1, wherein the highest known sequence number is maintained in an entry of the map, and wherein modifying the map includes replacing the highest known sequence number in the entry with the sequence number from the change relationship signal.

3. A method according to claim 1, further comprising, for each check-in message received from a child node within the preset interval, extracting the change relationship signals contained in the parent-child information and propagating the extracted change relationship signals to the parent node of the node.

4. A method according to claim 1, wherein updating the map includes modifying an entry of the map in a selected one of first and second ways, the first way being performed when the change relationship signal is a first type and including modifying the entry to remove an existing child relationship from the map, the second way being performed when the change relationship signal is a second type and including modifying the entry to add a new child relationship to the map.

5. A method according to claim 1, wherein the check-in message is one of a series of expected check-in messages expected to be received at the preset interval, and further comprising (a) monitoring for receipt of each of the expected check-in messages within the preset interval, (b) in the case that an expected check-in message is received within the preset interval, then performing a respective update of the map which maintains an indication a reporting child node is a child of the node, and (c) in the case that an expected check-in message is not received within the preset interval, then performing a respective update of the map which deletes an indication that a non-reporting child node is a child of the node.

6. A method according to claim 1, further comprising:

setting up a relationship to an alternate network node capable of receiving a change relationship signal; and

activating the alternate network node so that the alternate network node receives the change relationship signal and performs the updating of the map.

7. A non-transitory computer readable medium having computer instructions stored thereon, the computer instructions being executable by a computer forming a node in a hierarchical, tree-connected network of nodes extending from a root node to a plurality of end nodes, each node formed by a respective computer, the network characterized by dynamic movement of child nodes among successive different parent nodes and a need to track changing locations of child nodes to effect multicast communication of data from the root node to the end nodes, the execution of the instructions causing the computer to perform a method including:

maintaining a map of parent-child relationships of the nodes of the network;

monitoring for receipt of check-in messages from child nodes of the node at a preset interval, each check-in message including parent-child information about a reporting child node originating the check-in message and about child nodes of the reporting child node, the parent-child information including one or more change relationship signals each regarding a respective parent-child relationship at or below the reporting child node in the hierarchical network, a first type of change relationship signal reflecting creation of the respective parent-child relationship and a second type of change relationship signal reflecting termination of the respective parent-child relationship;

for each check-in message received from a child node within the preset interval, updating the map of parent-child relationships using the parent-child information in the check-in message;

if a check-in message is not received from a non-reporting child node within the preset interval, then updating the map of parent-child relationships to indicate that the non-reporting child node and its child nodes are no longer child nodes of the node; and

upon updating the map of parent-child relationships, creating one or more new change relationship signals and sending them to a parent node of the node, a first new change relationship signal reflecting creation of a new parent-child relationship between the node and a newly reporting child node, and a second new change relationship signal reflecting termination of a previous parent-child relationship between the node and a non-reporting child node,

wherein;

the map includes, for each child node identified in the map, a respective highest known sequence number reflecting a number of parents that the respective child node has had;

each change relationship signal includes a respective sequence number indicating how many parents the child node identified in the change relationship signal has had; and

updating the map of parent-child relationships includes (a) comparing a sequence number of a change relationship signal in a received check-in message to the highest known sequence number for a child node identified in the change relationship signal, and (b) modifying the map of node relationships in accordance with the change relationship signal of the received check-in message only if the sequence number of the change relationship signal is greater than the highest known sequence number.

8. A computer readable medium according to claim 7, wherein the highest known sequence number is maintained in an entry of the map, and wherein modifying the map includes replacing the highest known sequence number in the entry with the sequence number from the change relationship signal.

9. A computer readable medium according to claim 7, wherein the method further includes, for each check-in message received from a child node within the preset interval, extracting the change relationship signals contained in the parent-child information and propagating the extracted change relationship signals to the parent node of the node.

10. A computer readable medium according to claim 7, wherein updating the map includes modifying an entry of the map in a selected one of first and second ways, the first way being performed when the change relationship signal is a first type and including modifying the entry to remove an existing child relationship from the map, the second way being performed when the change relationship signal is a second type and including modifying the entry to add a new child relationship to the map.

11. A computer readable medium according to claim 7, wherein the check-in message is one of a series of expected check-in messages expected to be received at the preset interval, and wherein the method further includes (a) monitoring for receipt of each of the expected check-in messages within the preset interval, (b) in the case that an expected check-in message is received within the preset interval, then performing a respective update of the map which maintains an indication a reporting child node is a child of the node, and (c) in the case that an expected check-in message is not received within the preset interval, then performing a respective update of the map which deletes an indication that a non-reportingchild node is a child of the node.

12. A computer readable medium according to claim 7, wherein the method further includes:

setting up a relationship to an alternate network node capable of receiving a change relationship signal; and

activating the alternate network node so that the alternate network node receives the change relationship signal and performs the updating of the map.

13. A computer system operative to form a node in a hierarchical, tree-connected network of nodes extending from a root node to a plurality of end nodes, each node formed by a respective computer, the network characterized by dynamic movement of child nodes among successive different parent nodes and a need to track changing locations of child nodes to effect multicast communication of data from the root node to the end nodes, the computer system comprising:

means for maintaining a map of parent-child relationships of the nodes of the network, the map including, for each child node identified in the map;

means for monitoring for receipt of check-in messages from child nodes of the node at a preset interval, each check-in message including parent-child information about a reporting child node originating the check-in message and about child nodes of the reporting child node, the parent-child information including one or more change relationship signals each regarding a respective parent-child relationship at or below the reporting child node in the hierarchical network, a first type of change relationship signal reflecting creation of the respective parent-child relationship and a second type of change relationship signal reflecting termination of the respective parent-child relationship;

means operative, for each check-in message received from a child node within the preset interval, to update the map of parent-child relationships using the parent-child information in the check-in message;

means operative, if a check-in message is not received from a non-reporting child node within the preset interval, to update the map of parent-child relationships to indicate that the non-reporting child node and its child nodes are no longer child nodes of the node; and

means operative, upon updating the map of parent-child relationships, to create one or more new change relationship signals and sending them to a parent node of the node, a first new change relationship signal reflecting creation of a new parent-child relationship between the node and a newly reporting child node, and a second new change relationship signal reflecting termination of a previous parent-child relationship between the node and a non-reporting child node,

wherein;

the map includes, for each child node identified in the map, a respective highest known sequence number reflecting a number of parents that the respective child node has had;

each change relationship signal includes a respective sequence number indicating how many parents the child node identified in the change relationship signal has had; and

updating the map of parent-child relationships includes (a) comparing a sequence number of a change relationship signal in a received check-in message to the highest known sequence number for a child node identified in the change relationship signal, and (b) modifying the map of node relationships in accordance with the change relationship signal of the received check-in message only if the sequence number of the change relationship signal is greater than the highest known sequence number.

14. A computer system according to claim 13, wherein the highest known sequence number is maintained in an entry of the map, and wherein modifying the map includes replacing the highest known sequence number in the entry with the sequence number from the change relationship signal.

15. A computer system according to claim 13, further comprising means, operative for each check-in message received from a child node within the preset interval, for extracting the change relationship signals contained in the parent-child information and propagating the extracted change relationship signals to the parent node of the node.

16. A computer system according to claim 13, wherein updating the map includes modifying an entry of the map in a selected one of first and second ways, the first way being performed when the change relationship signal is a first type and including modifying the entry to remove an existing child relationship from the map, the second way being performed when the change relationship signal is a second type and including modifying the entry to add a new child relationship to the map.

17. A computer system according to claim 13, wherein the check-in message is one of a series of expected check-in messages expected to be received at the preset interval, and further comprising means for (a) monitoring for receipt of each of the expected check-in messages within the preset interval, (b) in the case that an expected check-in message is received within the preset interval, then performing a respective update of the map which maintains an indication a reporting child node is a child of the node, and (c) in the case that an expected check-in message is not received within the preset interval, then performing a respective update of the map which deletes an indication that a non-reporting child node is a child of the node.

18. A computer system according to claim 13, further comprising:

means for setting up a relationship to an alternate network node capable of receiving a change relationship signal; and

means for activating the alternate network node so that the alternate network node receives the change relationship signal and performs the updating of the map.