Methods and apparatus for managing the arrangement of nodes in a network

• US 7,185,077 B1
• Filed: 05/24/2001
• Issued: 02/27/2007
• 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: O'Toole, James, Jannotti, John H.
• Primary Examiner(s): Caldwell; Andrew
• Assistant Examiner(s): AILES, BENJAMIN A
• Application Number:
  US09/864,487
• Time in Patent Office: 2,105 Days
• Field of Search: 709201-203, 709231-235, 709238-239, 709223-224, 709217-219, 707/2, 707 4- 5, 707/102, 707/104, 370254-256, 370/217, 370/220
• US Class Current: 709/223
• 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 managing a network of nodes by automatically configuring the arrangement of nodes in the network. A network manager in a node selects a group of nodes and compares network metrics for each node in the group, such as a bottleneck bandwidth measurement from each node to a root node of the network. The network manager selects a target node using the network metrics. Optionally, the network manager can select a new group of nodes using the target node, compare network metrics for the new group, and optionally select a new target node. If the node is a newly connecting node to the network, the network manager can repeat this process of selecting new groups until establishing a relationship with a target node that is not a root node (e.g., with performance that is the same, or about the same, as the root node), because the goal is not to overload the root node with too many relationships. If the node is a node with an established relationship to the network that is trying to reconnect to a new target node, the network manager can repeat the process of selecting new groups until establishing a relationship with a new target node that provides improved performance than the previous target node, but is, preferably, not the root node.

Claims

1. A method for managing a network of nodes, the steps comprising:

requesting an initial set of network metrics for an initial subset of nodes in the network of nodes based on a connecting node attempting to establish a relationship with a target node of the initial subset, each network metric of the initial set associated with a respective node from the initial subset and measuring a performance aspect of the respective node relative to the network;

receiving the initial set of the network metrics for the initial subset of nodes;

establishing the relationship between the connecting node and the target node of the initial subset based on a comparison of the network metrics in the initial set; and

prior to the step of requesting the initial set of network metrics, selecting a network metric from at least one of a bottleneck bandwidth metric, a latency metric, and a hop count metric; and

further comprising the steps of;

(i) choosing a revised subset of nodes based on the target node;

(ii) requesting a revised set of the network metrics based on the revised subset;

(iii) receiving the revised set of the network metrics based on the revised subset;

(iv) establishing a selected relationship between the connecting node and a selected target node of the revised subset based on a comparison of the network metrics in the revised set of network metrics and setting the selected target node to be the target node;

(v) repeating steps (i) through (iv) until determining that the selected relationship to the target node is a preferred relationship for the connecting node to the network.

2. The method of claim 1, wherein the step of receiving the initial set of network metrics comprises measuring a set of interactions over the network between the connecting node and the target node and between the connecting node and each node from the initial subset of the nodes.

3. The method of claim 1, wherein the step of receiving the initial set of network metrics comprises measuring a set of bottleneck bandwidth metrics between each node of the initial subset and a root node of the network of nodes.

4. The method of claim 1, wherein the connecting node does not have a previous relationship to the network prior to the step of requesting the initial set of network metrics, and the initial subset of nodes comprises a root node of the network of nodes.

5. A method for managing a network of nodes, the steps comprising:

requesting an initial set of network metrics for an initial subset of nodes in the network of nodes based on a connecting node attempting to establish a relationship with a target node of the initial subset, each network metric of the initial set associated with a respective node from the initial subset and measuring a performance aspect of the respective node relative to the network;

receiving the initial set of the network metrics for the initial subset of nodes;

establishing the relationship between the connecting node and the target node of the initial subset based on a comparison of the network metrics in the initial set; and

prior to the step of requesting the initial set of network metrics, selecting a network metric from at least one of a bottleneck bandwidth metric, a latency metric, and a hop count metric, wherein;

the connecting node is a reconnecting node having an existing association with the network and attempting to replace the existing association with a modified association with the network represented by the relationship with the target node; and

further comprising the steps of;

selecting a plurality of initial subsets of nodes at periodic intervals; and

performing the steps of requesting, receiving, and establishing at each periodic interval based on each initial subset of nodes of the plurality of initial subsets of nodes.

6. The method of claim 5, wherein the step of selecting the plurality of initial subsets of nodes is based on a lineage selection procedure that selects nodes for each initial subset based on a lineage group of nodes associated with the connecting node in the network.

7. The method of claim 5, wherein the step of selecting the plurality of initial subsets of nodes is based on a remote selection procedure that selects nodes for each initial subset based on selecting at least one node for each initial subset exclusive of a lineage group of nodes associated with the connecting node.

8. A computer system for managing a network of nodes, the computer system comprising:

a memory;

a network interface in communication with the memory; and

a processor in communication with the memory and the network interface, wherein the memory is encoded with logic instructions for a network manager application that, when performed on the processor, cause the processor to form a network manager that manages the nodes in the network by performing the operations of;

requesting an initial set of network metrics for an initial subset of nodes in the network of nodes based on a connecting node attempting to establish a relationship with a target node of the initial subset, each network metric of the initial set associated with a respective node from the initial subset and measuring a performance aspect of the respective node relative to the network;

receiving the initial set of the network metrics for the initial subset of nodes; and

establishing the relationship between the connecting node and the target node of the initial subset based on a comparison of the network metrics in the initial set; and

wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operation, prior to requesting the initial set of network metrics, of selecting the network metric from one of a bottleneck bandwidth metric, a latency metric, and a hop count metric; and

wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operations of;

(i) choosing a revised subset of nodes based on the target node;

(ii) requesting a revised set of the network metrics based on the revised subset;

(iii) receiving the revised set of the network metrics based on the revised subset;

(iv) establishing a selected relationship between the connecting node and a selected target node of the revised subset based on a comparison of the network metrics in the revised set of network metrics and setting the selected target node to be the target node;

(v) repeating steps (i) through (iv) until determining that the selected relationship to the target node is a preferred relationship for the connecting node to the network.

9. The computer system of claim 8, wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operation of measuring a set of interactions over the network between the connecting node and the target node and between the connecting node and each node from the initial subset of the nodes.

10. The computer system of claim 8, wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operation of measuring a set of bottleneck bandwidth metrics between each node of the initial subset and a root node of the network of nodes.

11. The computer system of claim 8, wherein the connecting node does not have a previous relationship to the network prior to the step of requesting the initial set of network metrics, and the initial subset of nodes comprises a root node of the network of nodes.

12. The computer system of claim 8, wherein the computer system is the connecting node.

13. A computer system for managing a network of nodes, the computer system comprising:

a memory;

a network interface in communication with the memory; and

a processor in communication with the memory and the network interface, wherein the memory is encoded with logic instructions for a network manager application that, when performed on the processor, cause the processor to form a network manager that manages the nodes in the network by performing the operations of;

requesting an initial set of network metrics for an initial subset of nodes in the network of nodes based on a connecting node attempting to establish a relationship with a target node of the initial subset, each network metric of the initial set associated with a respective node from the initial subset and measuring a performance aspect of the respective node relative to the network;

receiving the initial set of the network metrics for the initial subset of nodes; and

establishing the relationship between the connecting node and the target node of the initial subset based on a comparison of the network metrics in the initial set; and

wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operation, prior to requesting the initial set of network metrics, of selecting the network metric from one of a bottleneck bandwidth metric, a latency metric, and a hop count metric, wherein;

the connecting node is a reconnecting node having an existing association with the network and attempting to replace the existing association with a modified association with the network represented by the relationship with the target node; and

the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operations of;

selecting a plurality of initial subsets of nodes at periodic intervals; and

performing the operations of requesting, receiving, and establishing at each periodic interval based on each initial subset of nodes of the plurality of initial subsets of nodes.

14. The computer system of claim 13, wherein the logic instructions for the network manager application comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operation of selecting the plurality of initial subsets of nodes based on a lineage selection procedure that selects nodes for each initial subset based on a lineage group of nodes associated with the connecting node in the network.

15. The computer system of claim 13, wherein the logic instructions for the network manager applicatior, comprise further logic instructions, that, when performed on the processor, cause the network manager to perform the operations of selecting the plurality of initial subsets of nodes based on a remote selection procedure that selects nodes for each initial subset based on selecting at least one node for each initial subset exclusive of a lineage group of nodes associated with the connecting node.

16. A method for managing an overlay network of nodes, the method comprising:

requesting an initial set of network metrics for an initial subset of nodes in the overlay network of nodes based on a new node attempting to establish a virtual link with a target node of the initial subset, each network metric of the initial set associated with a respective node from the initial subset and measuring bandwidth to a root node from each respective node;

receiving the initial set of the network metrics for the initial subset of nodes;

establishing the virtual link between the new node and the target node of the initial subset based on a comparison of the network metrics in the initial set;

choosing a revised subset of nodes based on the target node;

requesting a revised set of the network metrics based on the revised subset;

receiving the revised set of the network metrics based on the revised subset; and

establishing a selected relationship between the connecting node and a selected target node of the revised subset based on a comparison of the network metrics in the revised set of network metrics and setting the selected target node to be the target node;

wherein choosing the revised subset, requesting the revised set, receiving the revised set and establishing the selected relationship are adapted to be performed until determining that the selected relationship to the target node is a preferred relationship for the connecting node to the network.