Design and Analysis of Distributed Routing Algorithms.

摘要

Route assignment is one of the operational problems of communication network, and adaptive routing schemes are required to achieve real time performance. This thesis introduces, verifies and analyses two new distributed, shortest-path routing algorithms, which are called, Path-Finding Algorithm (PFA) and Loop-Free Path-Finding Algorithm (LPA). Both algorithms require each routing node to know only the distance and the second-to-last-hop (or predecessor) node to each destination. In addition to the above information, LPA uses an efficient inter-neighbor coordination mechanism spanning over a single hop. PFA reduces the formation of temporary loops significantly, while LPA achieves loop-freedom at every instant by eliminating temporary loops. The average performance of these two algorithms is compared with the Diffusing Update Algorithm (DUAL) and an ideal link state (ILS) using Dijkstra's shortest- path algorithm by simulation; this performance comparison is made in terms of time taken for convergence, number of packets exchanged and the total number of operations required for convergence by each of the algorithms. The simulations were performed using a C-based simulation tool called Drama, along with a network simulation library. The results indicated that the performance of PFA is comparable to that of DUAL and ILS and that a significant improvement in performance can be achieved with LPA over DUAL and ILS.