Accession Number:

ADA461336

Title:

Design and Analysis of Distributed Routing Algorithms

Descriptive Note:

Master's thesis

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Personal Author(s):

Report Date:

1994-06-01

Pagination or Media Count:

70.0

Abstract:

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 Dijkstras 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.

Subject Categories:

  • Numerical Mathematics
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE