Accession Number:

ADA073487

Title:

Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1979-08-01

Pagination or Media Count:

52.0

Abstract:

Several proposed routing algorithms for store and forward communication networks, including one currently under implementation in the ARPANET, route messages along shortest paths computed by using some set of link lengths. When these lengths depend on current traffic conditions as they must in an adaptive algorithm, dynamic behavior questions such as stability, convergence, and speed of convergence are of interest. This paper is the first attempt to analyze systematically these issues. It is shown that minimum queuing delay path algorithms tend to exhibit violent oscillatory behavior in the absence of a damping mechanism. Several easily implementable damping schemes are proposed and analyzed by using nonlinear stability theory techniques.

Subject Categories:

  • Statistics and Probability
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE