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

• US 20050041676A1
• Filed: 08/06/2004
• Published: 02/24/2005
• Est. Priority Date: 08/08/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation)
• Inventors: Rosenzweig, Vladimir, Keller, Joseph, Weinstein, Joseph J.
• Granted Patent: US 7,881,229 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• 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 routing data, comprising:

constructing a connectivity graph that indicates connectivity between a first node and a first set of nodes in a network;

constructing an adjacency graph that indicates a second set of nodes with which the first node will exchange routing data, wherein the adjacency graph is distinct from the connectivity graph; and

exchanging routing data between the first node and each node of the second set of nodes based on the adjacency graph.

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

3. The method of claim 1, wherein constructing an 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.

4. The method of claim 1, wherein constructing an adjacency graph comprises:

determining an area-specific connectivity graph from the connectivity graph, from which all nodes not belonging to a current OSPF area have been eliminated;

determining a shortest-path spanning tree of the area-specific connectivity graph, wherein the shortest-path spanning tree comprises the adjacency graph.

5. The method of claim 1, wherein each of the first node and the first set of nodes is assigned an ordinal number as a node identification number, and wherein constructing an 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 same Open Shortest Path First (OSPF) area and that has a lowest ordinal number within that search distance; and

including the located second node within the adjacency graph.

6. The method of claim 1, wherein each of the first node and the first set of nodes is assigned an ordinal number as a node identification number, and wherein constructing an 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 same Open Shortest Path First (OSPF) area and that has a highest ordinal number within that search distance; and

including the located second node within the adjacency graph.

7. The method of claim 5, wherein constructing an adjacency graph further comprises:

if a second node is not located within the distance C, from the first node, increasing the distance to C₂;

searching the connectivity graph to locate the second node within the distance of C₂ from the first node that belongs to the same OSPF area and that has a lowest ordinal number within that search distance; and

including the located second node within the adjacency graph.

8. The method of claim 7, wherein constructing an adjacency graph further comprises:

if a second node is not located within the distance C, from the first node, increasing the distance to C₂;

searching the connectivity graph to locate the second node within the distance of C₂ from the first node that belongs to the same OSPF area and that has a highest ordinal number within that search distance; and

including the located second node within the adjacency graph.

9. The method of claim 1, wherein each of the first node and the first set of nodes is assigned an ordinal number as a node identification number, and wherein constructing an adjacency graph comprises:

identifying a second node, from the 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.

10. The method of claim 9, wherein the second node is within a same OSPF area as the first node.

19. The method of claim 1, wherein each of the first node and the first set of nodes is assigned an ordinal number as an identification number, and wherein selecting the second set of nodes comprises:

identifying a second node, from the 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.

20. The method of claim 19, wherein the second node is within a same OSPF area as the first node.

11. A network device, comprising:

a plurality of input interfaces configured to receive messages from neighboring nodes in a network; and

first logic configured to;

construct, based on the received messages, a connectivity graph that indicates connectivity between the network device and a first set of nodes in the network, construct an adjacency graph that indicates a second set of nodes with which the network device will exchange routing data, wherein the adjacency graph is distinct from the connectivity graph, and exchange routing data with each node of the second set of nodes based on the adjacency graph.

12. A computer-readable medium containing instructions for controlling at least one processor to perform a method of exchanging routing data, the method comprising:

constructing a connectivity graph that indicates connectivity between the first node and a first set of nodes in the network;

constructing an adjacency graph that indicates a second set of nodes with which the first node will exchange routing data, wherein the adjacency graph is distinct from the connectivity graph; and

initiating the exchange of routing data between the first node and each node of the second set of nodes based on the adjacency graph.

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 network;

selecting a second set of nodes from the first set of nodes, wherein the second set of nodes is a subset of the first set of nodes; and

exchanging routing data between the first node and each node of the selected second set of nodes.

14. The method of claim 13, wherein 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 current Open Shortest Path First (OSPF) area have been eliminated;

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

15. The method of claim 13, wherein each of the first node and the first set of nodes has an associated ordinal number as an identification number, and wherein 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 same Open Shortest Path First (OSPF) area and that has a lowest ordinal number within that search distance; and

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

16. The method of claim 13, wherein each of the first node and the first set of nodes has an associated ordinal number as an identification number, and wherein 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 same Open Shortest Path First (OSPF) area and that has a highest ordinal number within that search distance; and

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

17. The method of claim 15, wherein selecting the second set of nodes comprises:

if a second node is not located within the distance C, from the first node, increasing the distance to C₂;

searching the connectivity graph to locate the second node within the distance of C₂ from the first node that belongs to the same OSPF area and that has a lowest ordinal number; and

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

18. The method of claim 15, wherein selecting the second set of nodes comprises:

if a second node is not located within the distance C, from the first node, increasing the distance to C₂;

searching the connectivity graph to locate the second node within the distance of C₂ from the first node that belongs to the same OSPF area and that has a highest ordinal number; and

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

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

acquiring a connectivity graph that indicates connectivity between a first node and a plurality of other nodes, wherein node identifying ordinal numbers are associated with each of the first node and the plurality of other nodes;

searching the connectivity graph to locate a second node within a distance of C, from the first node that belongs to the same Open Shortest Path First (OSPF) area and that has at least one of a highest or lowest ordinal number within that search distance; and

exchanging routing data with the second node if the second node exists and is located within the distance of C₁.

22. The method of claim 21, wherein the distance C, comprises a first number of hops from the first node.

23. The method of claim 22, further comprising:

if the second node is not located within the distance of C₁, increasing the distance to C₂;

searching the connectivity graph to locate the second node within the distance of C₂ that belongs to the same OSPF area and that has the at least one of the highest or lowest ordinal number; and

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

24. The method of claim 23, wherein the distance C₂ comprises a second number of hops from the first node, wherein the second number of hops is greater than the first number of hops.

25. A method of selecting adjacent nodes for the exchange of routing data in a network, comprising:

acquiring a connectivity graph that indicates connectivity between a plurality of routers;

electing one or more nodes from the connectivity graph as a head of a cluster of a set of router of the plurality of routers;

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

selecting one or more routers as adjacency connectors between each of the clusters of routers.

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

acquiring a connectivity graph that indicates connectivity between a plurality of nodes;

determining an area-specific connectivity graph by eliminating from the connectivity graph all routers that are inactive, external, or do not belong to the current Open Shortest Path First (OSPF) area; and

determining a shortest-path spanning tree of the connectivity graph, wherein the shortest-path spanning tree comprises a set of nodes of the plurality of nodes; and

exchanging routing data between each of the nodes of the set of nodes of the shortest-path spanning tree.

27. The method of claim 26, wherein the shortest-path spanning tree is rooted at a selected node of the plurality of nodes.

28. The method of claim 27, wherein each of the plurality of nodes has a router identification number associated with it, and wherein the selected node comprises at least one of a lowest router identification number or a highest router identification number in the spanning tree.

29. The method of claim 27, wherein each node of the plurality of nodes establishes an adjacency with a next node on a path to the selected node.

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

acquiring a connectivity graph that indicates connectivity between a first node and a plurality of other nodes, wherein node identifying ordinal numbers are associated with each of the first node and the plurality of other 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 routing data with the selected second node.

31. The method of claim 30, wherein selecting the second node further comprises:

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

32. The method of claim 31, wherein selecting the second node further comprises:

selecting the second node that is in the same Open Shortest Path First (OSPF) area as the first node.

33. The method of claim 30, 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.

34. A system for exchanging routing data, comprising:

means for constructing a connectivity graph that indicates connectivity between the first node and a first set of nodes in the network;

means for constructing an adjacency graph that indicates a second set of nodes with which the first node will exchange routing data, wherein the adjacency graph is distinct from the connectivity graph; and

means for exchanging routing data between the first node and each node of the second set of nodes based on the adjacency graph.

35. A data structure encoded on a computer-readable medium, comprising:

first data comprising a connectivity graph that indicates connectivity between a first node and a first set of nodes in a network; and

second data comprising an adjacency graph that indicates a second set of nodes with which the first node will exchange routing data, wherein the adjacency graph is distinct from the connectivity graph.

36. The data structure of claim 35, further comprising:

routing data that can be exchanged between the first node and each node of the second set of nodes.