Systems and methods for forming an adjacency graph for exchanging network routing data
First Claim
Patent Images
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 20)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
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 C1. - View Dependent Claims (22, 23, 24)
-
-
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. - View Dependent Claims (27, 28, 29)
-
-
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. - View Dependent Claims (31, 32, 33)
-
-
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. - View Dependent Claims (36)
-
Specification