Distributed, scalable routing based on vectors of link states
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 13 (8) , 1383-1395
- https://doi.org/10.1109/49.464710
Abstract
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. According to an LVA, each router maintains a subset of the topology that corresponds to adjacent links and those 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. The LVA can be used for different types of routing. The correctness of the LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router and each router is able to differentiate old updates from new. The LVA are shown to have better performance than the ideal link-state algorithm based on flooding and the distributed Bellman-Ford algorithmKeywords
This publication has 17 references indexed in Scilit:
- Area-based, loop-free internet routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A loop-free path-finding algorithm: specification, verification and complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Loop-free routing using diffusing computationsIEEE/ACM Transactions on Networking, 1993
- A protocol for route establishment and packet forwarding across multidomain internetsIEEE/ACM Transactions on Networking, 1993
- Another adaptive distributed shortest path algorithmIEEE Transactions on Communications, 1991
- Topology broadcast algorithmsComputer Networks and ISDN Systems, 1989
- An adaptive hierarchical routing protocolIEEE Transactions on Computers, 1989
- Routing Information ProtocolPublished by RFC Editor ,1988
- Algorithms for finding paths with multiple constraintsNetworks, 1984
- Hierarchical routing for large networks Performance evaluation and optimizationComputer Networks (1976), 1977