Dynamics of distributed shortest-path routing algorithms
Published 1 August 1991Open access
W.T. Zaumen, J. J. Garcia-Luna Aceves
Citations58
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Comparisons of the distributed Belhnen-Ford algorithm used in several routing protocols in the paa~ and an ideal link-state ttlgonthm, and a loop-free distance-vector algorithm, made for the network topologies of the 1988 ARPANET, LOSNE’ITOS, DOE-ESNET, and the NSFNET T1 Backbone.
Abstract
The dynamics of shortest-path routing algorithms bss.ed on distance vectors and link states are investigated.
Keywords
Computer Science
Flows in networks
4,080 Citations1962D. R. Ford, D. R. Fulkerson
Addison-Wesley Longman Publishing Co., Inc. eBooksTelecommunication networks: protocols, modeling and analysis
902 Citations1986Mischa Schwartz
1. Introduction to Queuing Theory, Layered Architectures in Data Networks, and The Evolution toward Integrated Networks.
Routing Information Protocol
765 Citations1988C.L. Hedrick
This document specifies a routing protocol, based on the Routing Information Protocol, for the Simple Internet Protocol (SIP), as defined in [3], and a companion document will define the SNMP MIB objects for SIP-RIP (TBD).
Information Processing LettersTermination detection for diffusing computations
683 Citations1980Edsger W. Dijkstra, Carel S. Schölten
IRE Transactions on Communications SystemsThe New Routing Algorithm for the ARPANET
680 Citations1980John M. McQuillan, I. Richer +1 more
The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations.
IRE Transactions on Communications SystemsA Failsafe Distributed Routing Protocol
210 Citations1979Philip M. Merlin, A. Segall
The algorithm can be employed in message as well as circuit switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows, and is completely failsafe.
A loop-free extended Bellman-Ford routing protocol without bouncing effect
192 Citations1989C. Cheng, Richard D Riley +2 more
A protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and recover at arbitrary times, and avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm.
Exterior Gateway Protocol formal specification
84 Citations1984David L. Mills
This memo updates portions of RFC-888 and RFC-827 to specify an official protocol of the DARPA community for use between gateways of different autonomous systems in the ARPA-Internet.
A unified approach to loop-free routing using distance vectors or link states
84 Citations1989J.J. Garcia‐Luna‐Aceves
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 is described.
ACM SIGCOMM Computer Communication ReviewA loop-free extended Bellman-Ford routing protocol without bouncing effect
80 Citations1989C. Cheng, Richard D Riley +2 more
IEEE Transactions on ComputersPerformance Analysis of Distributed Routing Strategies Free of Ping-Pong-Type Looping
58 Citations1987Shin, Ming-Syan Chen⋆
Using the number of time intervals required for a node to recover from a network failure as the measure of network's adaptability, performance of this strategy and the ARPANET's previous routing strategy is comparatively analyzed without resorting to simulation.
Computer Networks and ISDN SystemsA minimum-hop routing algorithm based on distributed information
38 Citations1989J.J. Garcia‐Luna‐Aceves
There is a need for algorithms with a stronger internodal coordination, such as those reported previously in the literature by Jaffe and Moss and the author, to help solve the counting-to-infinity problem.
IRE Transactions on Communications SystemsA Routing Procedure for the TIDAS Message-Switching Network
38 Citations1975T. Cegrell
It has turned out that due to the requirements for TIDAS the best routing procedure is a one-parametric adaptive method, which has built-in instruments to adapt to the different situations that can arise in the net, for instance, when line and/or node errors occur.
DARPA Internet gateway
36 Citations1982R. Hinden, Alan B. Sheltzer
This memo presents detailed descriptions of message formats and gateway procedures, however, this is not an implementation specification, and such details are subject to change.
DCN Local-Network Protocols
35 Citations1983David L. Mills
This RFC provides a description of the DCN protocols for maintaining connectivity, routing, and clock information in a local network and may be of interest to the designers and implementers of other local networks.
ACM SIGCOMM Computer Communication ReviewA unified approach to loop-free routing using distance vectors or link states
33 Citations1989J.J. Garcia‐Luna‐Aceves
Computer Networks and ISDN SystemsSubtle design issues in the implementation of distributed, dynamic routing algorithms
23 Citations1986Jeffrey M. Jaffe, Alan E. Baratz +1 more
The conclusion is that one must be careful both in the overall design of a distributed algorithm, and in its detailed implementation, and the importance of careful formal validation of such protocols, rather than informal, intuitive arguments.