Loop-free routing using diffusing computations
J.J. Garcia-Lunes-Aceves · IEEE/ACM Transactions on Networking · 1993
A family of distributed algorithms for the dynamic computation of the shortest paths in a computer network or internet is presented, validated, and analyzed. According to these algorithms, each node maintains a vector with its distance to every other node. Update messages from a node are sent only to its neighbors; each such message contains a distance vector of one or more entries, and each entry specifies the length of the selected path to a network destination, as well as an indication of whether the entry constitutes an update, a query, or a reply to a previous query. The new algorithms treat the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten (1980). They improve on a number of algorithms introduced previously. The new algorithms are shown to converge in finite time after an arbitrary sequence of link cost or topological changes, to be loop-free at every instant, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities.>
Cited by 302 works. doi:10.1109/90.222913
Authors
References
- Flows in networks
- Transmission Control Protocol
- The New Routing Algorithm for the ARPANET
- Transmission Control Protocol
- A Failsafe Distributed Routing Protocol
- Routing Information Protocol
- Border Gateway Protocol 3 (BGP-3)
- A Responsive Distributed Routing Algorithm for Computer Networks
- A correctness proof of a topology information maintenance protocol for a distributed computer network
- A unified approach to loop-free routing using distance vectors or link states