Area-based, loop-free internet routing

Abstract

The diffusing update algorithms (DUAL) constitute a family of distributed routing algorithms that has been shown to be loop-free at every instant, to converge after an arbitrary sequence of link-cost or topological changes, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities. Two hierarchical routing schemes based on DUAL are presented to make it more applicable to very large internets. A scheme based on McQuillan's (1974, 1980) hierarchical routing scheme and a backbone-oriented scheme, similar to the one used in OSPF, are introduced to reduce the amount of routing information maintained at each router. The performance of these schemes is compared by simulation to the performance of the basic DUAL, an ideal routing algorithm based on topology broadcast, and OSPF. The simulation results suggest that DUAL with areas outperforms OSPF, and provide additional insight on the performance of OSPF, EIGRP, and area-based routing algorithms in general.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>