A practical approach to minimizing delays in Internet routing

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