Premium
Optimal dynamic routing in communication networks with continuous traffic
Author(s) -
Hajek Bruce,
Ogier Richard G.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140308
Subject(s) - mathematical optimization , computation , routing (electronic design automation) , multi commodity flow problem , computer science , weighting , node (physics) , minimum cost flow problem , flow network , relaxation (psychology) , maximum flow problem , flow (mathematics) , algorithm , mathematics , computer network , social psychology , geometry , structural engineering , engineering , radiology , medicine , psychology
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.