Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1979
Accession Number
ADA073487

Entities

People

  • Dimitri P. Bertsekas

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Electronics Laboratories
  • Equations
  • Information Processing
  • Information Systems
  • Markov Chains
  • Military Research
  • Network Topology
  • New York
  • Numbers
  • Ring Networks
  • Sequences
  • Stochastic Processes
  • Topology
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computer Networking
  • Theoretical Analysis.