Patent ID: 7881229

Claim:
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.