Dynamics of distributed shortest-path routing algorithms
William T. Zaumen, J. J. Garcia-Luna Aceves · 1991
The dynamics of shortest-path routing algorithms bss.ed on distance vectors and link states are investigated.Detailed quantitative comparisons of the distributed Belhnen-Ford algorithm used in several routing protocols in the paa~an ideal link-state ttlgonthm similar to the one used in OSPF and in the 0S1 intradomain routing protocol, and a loop-free distance-vector algorithm, are made for the network topologies of the 1988 ARPANET, LOS-NE'ITOS, DOE-ESNET, and the NSFNET T1 Backbone.Comparisons include the response of the algorithms to link-cost changes and to link end node failures and recoveries.A variety of quantities, including the length of messages and the average nutnber of paths affected by routing lceps, are computed as a function of time after a link or node change.Probabilities of various conditions are also obtained as a function of time, including the existence of loops.As expected, the dwtributed Belhnen-Ford algorithm behaves poorly compared with the other two.However, deciding between a routing protocol based on a link-state algorithm and one based on a loop-free d~tance-vector algorithm depends on the particular network in which it will perform.