A practical approach to minimizing delays in Internet routing
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 479-483
- https://doi.org/10.1109/icc.1999.767986
Abstract
We present a practical approach to Internet routing that provides near-minimum delays over multiple loop-free paths to destinations. The new protocol, which we call NEAR-OPT, obtains multiple loop-free paths to destinations using long-term delay measures, and allocates destination-oriented flows over such paths using short-term delay measures to minimize delay. We compare the performance of NEAR-OPT with traditional single-path routing and the only known adaptation for dynamic networks of Gallager's (1977) minimum-delay routing algorithm. Using actual Internet traffic traces and other traffic source models, we show that NEAR-OPT provides delays comparable to the lower bounds achievable with Gallager's algorithm for static networks, provides lower delays than implementations of Gallager's algorithm in networks subject to fractal traffic, and renders far smaller delays and better use of resources than traditional single-path routing. NEAR-OPT does not depend on any global constant and is completely distributed, making it easy to implement as a loop-free "distance-vector" protocol similar to Cisco's EIGRP.Keywords
This publication has 10 references indexed in Scilit:
- Loop-free multipath routing using generalized diffusing computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Loop-free routing using diffusing computationsIEEE/ACM Transactions on Networking, 1993
- Distributed routing with on-line marginal delay estimationIEEE Transactions on Communications, 1990
- Second Derivative Algorithms for Minimum Delay Distributed Routing in NetworksIEEE Transactions on Communications, 1984
- Dynamic behavior of shortest path routing algorithms for communication networksIEEE Transactions on Automatic Control, 1982
- A Failsafe Distributed Protocol for Minimum Delay RoutingIEEE Transactions on Communications, 1981
- Termination detection for diffusing computationsInformation Processing Letters, 1980
- A Failsafe Distributed Routing ProtocolIEEE Transactions on Communications, 1979
- A Minimum Delay Routing Algorithm Using Distributed ComputationIEEE Transactions on Communications, 1977
- The Modeling of Adaptive Routing in Data-Communication NetworksIEEE Transactions on Communications, 1977