An area-based link-vector algorithm (ALVA) is introduced for the distributed maintenance of routing information in very large internetworks. According to ALVA, destinations in an internetwork are aggregated in areas in multiple levels of hierarchy. Routers maintain a database that contains a subset of the topology at each level of the hierarchy. This subset corresponds to those links used in preferred paths to reach destinations (nodes inside the same immediate area or remote areas). The ALVA is the first hierarchical routing algorithm based on link-state information that does not require complete topology information at each level in the hierarchy. The correctness of the ALVA is verified. Simulation results are presented showing that the ALVA outperforms the OSPF in terms of communication and storage overhead.

Routing protocols based on the distribution of link-state information rely on sequence numbers to validate information that a router receives. A fundamental problem is to bound the sequence-number space. We propose a new sequence-number reset algorithm that needs neither periodic retransmissions nor age fields. It is based on a recursive query-response procedure and is designed to handle resource failures during operation. This new algorithm is applicable to routing protocols based on both flooding and selective distribution of link-state information. The correctness of the algorithm is verified in the context of selective dissemination of topology information, and its complexity analyzed. Because the reset algorithm does not use any aging, the distribution of new link-state information or the purging of old information is always done in a time proportional to the time it takes to traverse the network.

We have present a new method for distributed routing in computer networks and internets using link-state information. Link vector algorithms (LVA) are introduced for the distributed maintenance of routing information in large networks and internets.

A new family of routing algorithms for the distributed maintenance of routing information in large networks and internets is introduced. This family is called link vector algorithms (LVA), and is based on the selective diffusion of link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information to all routers. According to LVA, each router maintains a subset of the topology that corresponds to the links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates; each such update specifies a link and its parameters. LVAs can be used for different types of routing. The correctness of LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router. LVA is shown to have smaller complexity than link-state and distance-vector algorithms, and to have better average performance than the ideal topology-broadcast algorithm and the distributed Bellman-Ford algorithm.