Accession Number:

ADA459441

Title:

Routing in Packet-Switched Networks Using Path-Finding Algorithms

Descriptive Note:

Doctoral thesis

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Personal Author(s):

Report Date:

1996-09-01

Pagination or Media Count:

166.0

Abstract:

Route assignment is one of the operational problems of a communication network. The function of a routing algorithm is to guide packets through the communication network to their correct destinations. This dissertation is on the design and analysis of distributed, adaptive routing algorithms and protocols for packet switching networks. We introduce the general framework on which these algorithms are based. Using this general model, we propose several routing techniques to suit heterogeneous environments. In this dissertation, we concentrate on distance-vector algorithms. One important drawback of previous distance-vector algorithms based on the distributed Bellman-Ford algorithm for shortest-path computation is that they suffer from counting-to-infinity problem and the bouncing effect. Recently, distributed shortest-path algorithms which utilize information about distance and second-to-last hop along the shortest-path to each destination have been proposed. This class of algorithms are called path-finding algorithms. Our proposals are based on path-finding algorithms.

Subject Categories:

  • Numerical Mathematics
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE