Systems and methods for forming an adjacency graph for exchanging network routing data

• US 7,881,229 B2
• Filed: 08/06/2004
• Issued: 02/01/2011
• Est. Priority Date: 08/08/2003
• Status: Expired due to Fees

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Inventors: Rosenzweig, Vladimir, Keller, Joseph, Weinstein, Joseph J.
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): HAN, CLEMENCE S
• Application Number:
  US10/913,151
• Publication Number:
  US 20050041676A1
• Time in Patent Office: 2,370 Days
• Field of Search: 370/254, 370/255, 370/256
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A system for exchanging routing information over a communications network constructs a connectivity graph that indicates connectivity between a first node and a first set of nodes in the network. The system constructs an adjacency graph that indicates a second set of nodes with which the first node will exchange routing data, where the adjacency graph is distinct from the connectivity graph. The system exchanges routing data between the first node and each node of the second set of nodes based on the adjacency graph.

Claims

1. A method of exchanging first routing data that is generated and employed by a link-state routing algorithm that is implemented internal and external to a first network, the method comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in the first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing an adjacency graph, based at least in part upon information contained in the connectivity graph, that indicates a second set of nodes with which the first node will exchange the first routing data that is generated and employed by the link-state routing algorithm that is implemented internal and external to the first network, where the adjacency graph is distinct from the connectivity graph and where constructing the adjacency graph comprises;

electing one or more nodes from the connectivity graph as a head of a cluster of a third set of nodes,

forming, for every node of the connectivity graph that is not a cluster head, an adjacency with a next hop node along a shortest path to a closest cluster head, and

selecting one or more nodes as adjacency connectors between each of the clusters of nodes; and

exchanging the first routing data between the first node and each node of the second set of nodes based on the adjacency graph, where the first routing data is generated and employed by the link-state routing algorithm that is implemented internal and external to the first network and is distinct from the second routing data internal to the first network.

2. The method of claim 1, where the second set of nodes is a subset of the first set of nodes.

3. A method of exchanging first routing data that is generated and employed by a link-state routing algorithm that is implemented internal and external to a first network, the method comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in the first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing an adjacency graph, based at least in part upon information contained in the connectivity graph, that indicates a second set of nodes with which the first node will exchange the first routing data that is generated and employed by the link-state routing algorithm that is implemented internal and external to the first network, where the adjacency graph is distinct from the connectivity graph and where constructing the adjacency graph comprises;

determining an area-specific connectivity graph from the connectivity graph, from which all nodes not belonging to a configured subset of the first set of nodes have been eliminated, and

determining a shortest-path spanning tree of the area-specific connectivity graph, where the shortest-path spanning tree comprises the adjacency graph; and

exchanging the first routing data between the first node and each node of the second set of nodes based on the adjacency graph, where the first routing data is generated and employed by a link-state routing algorithm that is implemented internal and external to the first network and is distinct from the second routing data that is internal to the first network.

4. A method of exchanging routing data, comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing an adjacency graph, based at least in part upon information contained in the connectivity graph, that indicates a second set of nodes with which the first node will exchange the first routing data, where the adjacency graph is distinct from the connectivity graph and where constructing the adjacency graph comprises;

searching the connectivity graph to locate a second node within a distance of C₁ from the first node that belongs to a configured subset of the first set of nodes and that has a lowest ordinal number within that search distance, and

including the located second node within the adjacency graph; and

exchanging the first routing data between the first node and each node of the second set of nodes based on the adjacency graph, where the first routing data is distinct from the second routing data internal to the first network.

5. The method of claim 4, where constructing the adjacency graph further comprises:

searching the connectivity graph to locate the second node within a distance of C₂ from the first node, if the second node is not located within the distance C₁ from the first node, where the second node belongs to the configured subset of the first set of nodes and has a lowest ordinal number within that search distance; and

including the located second node within the adjacency graph.

6. A method of exchanging routing data, comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing an adjacency graph, based at least in part upon information contained in the connectivity graph, that indicates a second set of nodes with which the first node will exchange the first routing data, where the adjacency graph is distinct from the connectivity graph and where constructing the adjacency graph comprises;

searching the connectivity graph to locate a second node within a distance of C₁ from the first node that belongs to a configured subset of the first set of nodes and that has a highest ordinal number within that search distance, and

including the located second node within the adjacency graph; and

exchanging the first routing data between the first node and each node of the second set of nodes based on the adjacency graph, where the first routing data is distinct from the second routing data internal to the first network.

7. The method of claim 6, where constructing an adjacency graph further comprises:

searching the connectivity graph to locate the second node within a distance of C₂ from the first node, if the second node is not located within the distance C₁ from the first node, where the second node belongs to the configured subset of the first set of nodes and has a highest ordinal number within that search distance; and

including the located second node within the adjacency graph.

8. A method of exchanging routing data, comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing an adjacency graph, based at least in part upon information contained in the connectivity graph, that indicates a second set of nodes with which the first node will exchange the first routing data, where the adjacency graph is distinct from the connectivity graph and where constructing the adjacency graph comprises;

identifying a second node, from the first set of nodes, that neighbors the first node and that has a lower ordinal number, and

including the identified second node within the adjacency graph; and

exchanging the first routing data between the first node and each node of the second set of nodes based on the adjacency graph, where the first routing data is distinct from the second routing data internal to the first network.

9. The method of claim 8, where the second node is within a configured subset of the first set of nodes.

10. A method of selecting nodes from a plurality of nodes in a first network for exchanging first routing data that is generated and employed by a link-state routing algorithm that is implemented internal and external to the first network, the method comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a first set of nodes in the first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing, based at least in part upon information contained in the connectivity graph, an adjacency graph that is distinct from the connectivity graph, by selecting a second set of nodes from the first set of nodes, where the second set of nodes is a subset of the first set of nodes and where selecting the second set of nodes comprises;

determining an area-specific connectivity graph from the connectivity graph, from which all nodes not belonging to a configured subset of the first set of nodes have been eliminated, and

determining a shortest-path spanning tree of the area-specific connectivity graph, where the second set of nodes comprises at least a portion of nodes comprising the shortest-path spanning tree; and

exchanging the first routing data, between the first node and each node of the selected second set of nodes, where the first routing data is generated and employed by the link-state routing algorithm that is implemented internal and external to the first network and is distinct from the second routing data internal to the first network.

11. A method of selecting nodes from a plurality of nodes for exchanging routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing, based at least in part upon information contained in the connectivity graph, an adjacency graph that is distinct from the connectivity graph, by selecting a second set of nodes from the first set of nodes, where the second set of nodes is a subset of the first set of nodes and where selecting the second set of nodes comprises;

searching the connectivity graph to locate a second node within a distance of C₁ from the first node that belongs to a configured subset of the first set of nodes and that has a lowest ordinal number within that search distance, and

including the located second node within the second set of nodes; and

exchanging the first routing data between the first node and each node of the selected second set of nodes, where the first routing data is distinct from the second routing data internal to the first network.

12. The method of claim 11, where selecting the second set of nodes comprises:

searching the connectivity graph to locate the second node within a distance of C₂ from the first node, if the second node is not located within the distance C₁ from the first node, where the second node belongs to the configured subset of the first set of nodes and has a lowest ordinal number within that search distance; and

including the located second node within the second set of nodes.

13. A method of selecting nodes from a plurality of nodes for exchanging routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing, based at least in part upon information contained in the connectivity graph, an adjacency graph that is distinct from the connectivity graph, by selecting a second set of nodes from the first set of nodes, where the second set of nodes is a subset of the first set of nodes and where selecting the second set of nodes comprises;

searching the connectivity graph to locate a second node within a distance of C₁ from the first node that belongs to a configured subset of the first set of nodes and that has a highest ordinal number within that search distance, and

including the located second node within the second set of nodes; and

exchanging the first routing data between the first node and each node of the selected second set of nodes, where the first routing data is distinct from the second routing data internal to the first network.

14. The method of claim 13, where electing the second set of nodes comprises:

searching the connectivity graph to locate the second node within a distance of C₂ from the first node, if the second node is not located within the distance C₁ from the first node, where the second node belongs to the configured subset of the first set of nodes and has a highest ordinal number within that search distance; and

including the located second node within the second set of nodes.

15. A method of selecting nodes from a plurality of nodes for exchanging routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a first set of nodes in a first network, where connectivity between the first node and at least one node of the first set is provided by forwarding data within the first network based upon second routing data internal to the first network;

constructing, based at least in part upon information contained in the connectivity graph, an adjacency graph that is distinct from the connectivity graph, by selecting a second set of nodes from the first set of nodes, where the second set of nodes is a subset of the first set of nodes and where selecting the second set of nodes comprises;

identifying a second node, from the first set of nodes, that neighbors the first node and that has a lower ordinal number, and

including the identified second node within the second set of nodes; and

exchanging the first routing data between the first node and each node of the selected second set of nodes, where the first routing data is distinct from the second routing data internal to the first network.

16. The method of claim 15, where the second node is within a configured subset of the first set of nodes.

17. A method of selecting adjacent nodes for the exchange of first routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a plurality of other nodes, where node identifying ordinal numbers are associated with each of the first node and the plurality of other nodes, and where connectivity between the first node and at least one node of the plurality of other nodes is provided by forwarding data among the plurality of nodes based upon second routing data internal to the plurality of nodes;

searching the connectivity graph to locate a second node within a distance of C₁ from the first node that belongs to a configured subset of the first set of nodes and that has at least one of a highest or lowest ordinal number within that search distance; and

exchanging the first routing data with the second node if the second node exists and is located within the distance of C₁ from the first node, where the routing data is distinct from the second routing data internal to the plurality of nodes.

18. The method of claim 17, where the distance C₁ comprises a first number of hops from the first node.

19. The method of claim 18, further comprising:

searching the connectivity graph to locate the second node within a distance of C₂ from the first node, if the second node is not located within the distance C₁ from the first node, where the second node belongs to a configured subset of the first set of nodes and has a lowest ordinal number within that search distance; and

exchanging routing data with the second node if the second node is located within the distance of C₂.

20. The method of claim 19, where the distance of C₂ comprises a second number of hops from the first node, where the second number of hops is greater than the first number of hops.

21. A method of selecting adjacent nodes for an exchange, in a first network, of first routing data that is generated and employed by a link-state routing algorithm that is implemented internal and external to the first network, the method comprising:

acquiring a connectivity graph that indicates connectivity between a plurality of nodes, where connectivity between at least two nodes among the plurality of nodes is provided by forwarding data among the plurality of nodes based upon second routing data internal to the plurality of nodes;

determining an area-specific connectivity graph by eliminating from the connectivity graph all nodes of the plurality of nodes that are inactive, external, or do not belong to a configured subset of a first set of nodes;

electing one or more nodes from the connectivity graph as a head of a cluster of a set of nodes of the plurality of nodes, where each node of the plurality of nodes has a priority for election as a cluster head;

forming, for every node of the connectivity graph that is not a cluster head, an adjacency with a next hop node along a shortest path to a closest cluster head;

selecting one or more nodes of the connectivity graph, as adjacency connectors between each of the clusters of nodes; and

exchanging, between at least two nodes of the plurality of nodes, the first routing data that is generated and employed by a link-state routing algorithm that is implemented internal and external to the first network, where the first routing data is distinct from the second routing data that is internal to the plurality of nodes.

22. A method of selecting adjacent nodes for the exchange of first routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a plurality of nodes, each of the plurality of nodes having an associated identification number, where connectivity between at least two nodes among the plurality of nodes is provided by forwarding data among the plurality of nodes based upon second routing data internal to the plurality of nodes;

determining an area-specific connectivity graph by eliminating from the connectivity graph all nodes that are inactive, external, or do not belong to a configured subset of the plurality of nodes;

determining a shortest-path spanning tree of the connectivity graph, where the shortest-path spanning tree comprises a set of nodes of the plurality of nodes, where the shortest-path spanning tree is rooted at a selected node of the plurality of nodes, and where the selected node comprises at least one of a lowest node identification number or a highest node identification number in the spanning tree; and

exchanging the first routing data between each of the nodes of the set of nodes of the shortest-path spanning tree, where the first routing data is distinct from the second routing data internal to the plurality of nodes.

23. The method of claim 22, where each node of the plurality of nodes establishes an adjacency with a next node on a path to the selected node.

24. A method of selecting adjacent nodes for the exchange of first routing data, comprising:

acquiring a connectivity graph that indicates connectivity between a first node and a plurality of other nodes, where node identifying ordinal numbers are associated with each of the first node and the plurality of other nodes, and where connectivity between at least two nodes among a plurality of nodes is provided by forwarding data among the plurality of nodes based upon second routing data internal to the plurality of nodes;

selecting a second node of the plurality of other nodes that neighbors the first node and that has a lower ordinal number; and

exchanging the first routing data with the selected second node, where the first routing data is distinct from the second routing data internal to the plurality of nodes.

25. The method of claim 24, where selecting the second node further comprises:

selecting the second node that is closest to the first node and that has the lower ordinal number.

26. The method of claim 25, where selecting the second node further comprises:

selecting the second node that is in a configured subset of the first set of nodes.

27. The method of claim 24, further comprising:

determining if a third node of the plurality of other nodes neighbors the first node and has a lower ordinal number than the second node; and

exchanging routing data with the third node based on the determination.