Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks,

Abstract

Several proposed routing algorithms for store and forward communication networks, including one currently in operation 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. The oscillations can be damped by means of several types of schemes two of which are analyzed in this paper. In the first scheme a constant bias is added to the queuing delay thereby providing a preference towards paths with small number of links. In the second scheme the effects of several past routings are averaged as for example when the link lengths are computed and communicated asynchronously throughout the network. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA087706

Entities

People

  • Dimitri P. Bertsekas

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computations
  • Computer Science
  • Congestion
  • Convergence
  • Eigenvalues
  • Electrical Engineering
  • Equations
  • Intervals
  • Markov Chains
  • Network Topology
  • Point Theorem
  • Ring Networks
  • Stochastic Processes
  • Topology
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Atmospheric Science / Meteorology, specifically Wind Wave Turbulence.
  • Computer Networking