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

• US 20060218301A1
• Filed: 05/10/2006
• Published: 09/28/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 J.
• Granted Patent: US 7,984,137 B2
• Time in Patent Office: Days
• US Class Current: 709/244
• 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-22. -22. (canceled)

23. In a computer system, a method for maintaining a map of node relationships for a network of related nodes, comprising the steps of:

receiving a change relationship signal indicating a change in a relationship between a first network node and a second network node having a child relationship to the first network node;

locating, in the map of node relationships, an entry corresponding to the second network node; and

modifying the entry based on the change relationship signal so that the map of node relationships reflects the change in the relationship between the first network node and the second network node.

24. The method of claim 23, further comprising the steps of:

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

activating the alternate first network node so that the alternate first network node receives the change relationship signal and performs the steps of locating the entry and modifying the entry.

25. The method of claim 23, further comprising the steps of:

receiving a request for data;

selecting a network node capable of responding to the request based on the map of node relationships and the request; and

directing the request to the network node to provide a response to the request.

26. A computer system comprising:

a processor;

a memory comprising a map of node relationships for the network; 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 the map of node relationships by performing the operations of;

receiving a change relationship signal indicating a change in a relationship between a first network node and a second network node having a child relationship to the first network node;

locating, in the map of node relationships in the memory, an entry corresponding to the second network node; and

modifying the entry based on the change relationship signal so that the map of node relationships in the memory reflects the change in the relationship between the first network node and the second network node.

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

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

activating the alternate first network node so that the alternate first network node receives the change relationship signal and performs the steps of locating the entry and modifying the entry.

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

receiving a request for data;

selecting a network node capable of responding to the request based on the map of node relationships and the request; and

directing the request to the network node to provide a response to the request.

29. A computer program product that includes a computer readable medium having instructions stored thereon 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:

receiving a change relationship signal indicating a change in a relationship between a first network node and a second network node having a child relationship to the first node;

locating, in the map of node relationships, an entry corresponding to the second network node; and

modifying the entry based on the change relationship signal so that the map of node relationships reflects the change in the relationship between the first network node and the second network node.

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

means for receiving a change relationship signal indicating a change in a relationship between a first network node and a second network node having a child relationship to the first node;

means for locating, in the map of node relationships, an entry corresponding to the second network node; and

means for modifying the entry based on the change relationship signal so that the map of node relationships reflects the change in the relationship between the first network node and the second network node.