Asymptotic Optimality of Shortest Path Routing

Abstract

Many communication networks use adaptive shortest path routing. By this the authors mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length updates is routed along a shortest path corresponding to the latest link lengths. It is shown that in certain situations, typical of networks involving a large number of small users and utilizing virtual circuits, this routing method performs optimally in an asymptotic sense. In other cases shortest path routing can be far from optimal.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1983
Accession Number
ADA132280

Entities

People

  • Dimitri P. Bertsekas
  • Eli M. Gafni

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computer Science
  • Convergence
  • Differential Equations
  • Equations
  • Inequalities
  • Linear Differential Equations
  • Mathematics
  • Networks
  • Probability
  • Statistics
  • Stochastic Processes

Fields of Study

  • Computer science

Readers

  • Operations Research
  • Radio communications and signal processing.