Methods and apparatus for maintaining a map of node relationships for a network
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification