Abstract
We present a unified approach for the dynamic computation of shortest paths in a computer network using either distance vectors or link states. We describe a distributed algorithm that provides loop-free paths at every instant and extends or improves algorithms introduced previously by Chandy and Misra, Jaffe and Moss, Merlin and Segall, and the author. Our approach treats the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten. We verify the loop-freedom of the new algorithm, and also demonstrate that it converges to the correct routing entries a finite time after an arbitrary sequence of topological changes. We analyze the complexity of the new algorithm when distance vectors and link states are used, and show that using distance vectors is better insofar as routing overhead is concerned.
Keywords
Computer scienceDistance-vector routing protocolDijkstra's algorithmTheoretical computer scienceAlgorithmK shortest path routingEqual-cost multi-path routingShortest path problemRouting (electronic design automation)Link (geometry)Link-state routing protocolTopology (electrical circuits)MathematicsRouting protocolComputer networkCombinatorics
Affiliated Institutions
Related Publications
A routing protocol for packet radio networks
Abstract : The authors present a new distance-vector routing protocol for a packet radio network. The new distributed routing protocol, Wireless Routing Protocol (WRP), works on...
A loop-free extended Bellman-Ford routing protocol without bouncing effect
Distributed algorithms for shortest-path problems are important in the context of routing in computer communication networks. We present a protocol that maintains the shortest-p...
Routing Techniques Used in Computer Communication Networks
An overview is provided in this paper of the routing procedures used in a number of operating networks, as well as in two commercial network architectures. The networks include ...
Geographic routing for wireless networks
Distributed shortest-path routing protocols for wired networks either describe the entire topology of a network or provide a digest of the topology to every router. They continu...
Resilient overlay networks
A Resilient Overlay Network (RON) is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance wi...
Publication Info
- Year
- 1989
- Type
- article
- Pages
- 212-223
- Citations
- 84
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
84
OpenAlex
Cite This
J.J. Garcia‐Luna‐Aceves
(1989).
A unified approach to loop-free routing using distance vectors or link states.
, 212-223.
https://doi.org/10.1145/75246.75268
Identifiers
- DOI
- 10.1145/75246.75268