Optimal dynamic routing in communication networks with continuous traffic

Bruce Hajek, Richard G. Ogier

Research output: Contribution to journalArticle

Abstract

New characterizations of optimal state‐dependent routing strategies are obtained for the continuous traffic network model proposed by Segall for linear cost with unity weighting at each node and for constant inputs. The concept of flow relaxation is introduced and is used t o transform the optimal routing problem into an initial flow optimization problem with convex cost and linear constraints. Three algorithms are given for open‐loop computation of the optimal initial flow. The first is a simple iterative algorithm based on gradient descent with bending and it is well suited for decentralized computation. The second algorithm reduces the problem t o a series of max‐flow problems and it computes the exact optimal initial flow in O(lN14) compu‐ tations, where IN1 is the number of nodes in the network. The third algorithm is based on a search for successive bottlenecks in the network.

Original languageEnglish (US)
Pages (from-to)457-487
Number of pages31
JournalNetworks
Volume14
Issue number3
DOIs
StatePublished - Jan 1 1984

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this