research-article

Asymptotic optimality of shortest path routing algorithms

Authors:

Eli M. Gafni,

Dimitri P. BertsekasAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 33, Issue 1

Pages 83 - 90

https://doi.org/10.1109/TIT.1987.1057274

Published: 02 January 1987 Publication History

Abstract

Many communication networks use adaptive shortest path routing. By this we 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. We show 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.

Cited By

View all

Charron-Bost BFgger MNowak T(2017)New transience bounds for max-plus linear systemsDiscrete Applied Mathematics10.1016/j.dam.2016.11.003219:C(83-99)Online publication date: 11-Mar-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.11.003
Charron-Bost BFügger MNowak T(2013)Transience bounds for distributed algorithmsProceedings of the 11th international conference on Formal Modeling and Analysis of Timed Systems10.1007/978-3-642-40229-6_6(77-90)Online publication date: 29-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40229-6_6
Jacob RRitscher SScheideler CSchmid S(2009)A Self-stabilizing and Local Delaunay Graph ConstructionProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_78(771-780)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_78

Index Terms

Asymptotic optimality of shortest path routing algorithms

Recommendations

Complexity of inverse shortest path routing
INOC'11: Proceedings of the 5th international conference on Network optimization

The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest ...
An Appraisal of Some Shortest-Path Algorithms

This paper treats five discrete shortest-path problems: 1 determining the shortest path between two specified nodes of a network; 2 determining the shortest paths between all pairs of nodes of a network; 3 determining the second, third, etc., shortest ...
A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IEEE Transactions on Information Theory Volume 33, Issue 1

January 2, 1987

179 pages

ISSN:0018-9448

Editor:
A. D. Wyner

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 02 January 1987

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Charron-Bost BFgger MNowak T(2017)New transience bounds for max-plus linear systemsDiscrete Applied Mathematics10.1016/j.dam.2016.11.003219:C(83-99)Online publication date: 11-Mar-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.11.003
Charron-Bost BFügger MNowak T(2013)Transience bounds for distributed algorithmsProceedings of the 11th international conference on Formal Modeling and Analysis of Timed Systems10.1007/978-3-642-40229-6_6(77-90)Online publication date: 29-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40229-6_6
Jacob RRitscher SScheideler CSchmid S(2009)A Self-stabilizing and Local Delaunay Graph ConstructionProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_78(771-780)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_78

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Complexity of inverse shortest path routing

An Appraisal of Some Shortest-Path Algorithms

A Multiple Pairs Shortest Path Algorithm

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations