Design and performance of a loop free routing algorithm
Arvind Tripathi, Pallapa Venkataram · 2002
We propose a distributed asynchronous routing algorithm that guarantees that the routing tables are free of loops at any point of time. It is a distance vector algorithm, basically derived from the traditional distributed bellman ford algorithm, which it supplements to avoid routing loops. When a node sees the possibility of a loop, it initiates a computation (which spreads to other nodes), and waits to detect the termination of this computation. The properties of loop freedom and convergence of the algorithm to the correct solution are proved, and the complexity of the algorithm analyzed. Further, the algorithm is tested by running it over a test topology. The Distributed Bellman Ford algorithm (DBF) and the Ideal Link State protocol (ILS) are also simulated over the same topology, and their performance is compared. The proposed algorithm is seen to outperform both DBF and ILS.