A Class of Optimal Routing Algorithms for Communication Networks

Abstract

This report describes an algorithm for minimum delay routing in a communication network. During the algorithm each node maintains a list of paths along which it sends traffic to each destination together with a list of the fractions of total traffic that are sent along these paths. At each iteration a minimum marginal delay path to each destination is computed and added to the current list if not already there. Simultaneously the corresponding fractions are updated in a way that reduces average delay per message. The algorithm is capable of employing second derivatives of link delay functions thereby providing automatic scaling with respect to traffic input level. It can be implemented in both a distributed and a centralized manner, and it can be shown to converge to an optimal routing at a linear rate.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1980
Accession Number
ADA089840

Entities

People

  • Dimitri P. Bertsekas

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computations
  • Computer Programming
  • Contrast
  • Convergence
  • Electronics Laboratories
  • Equations
  • Evolutionary Algorithms
  • Information Processing
  • Information Systems
  • Iterations
  • Mathematical Analysis
  • Mathematics
  • Military Research
  • Nonlinear Programming
  • Optimization

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking