graphicHomeAdvance ProgramAward Anniversary EventCall for PapersConference CommitteeLocal InformationPaper SubmissionProgram committeeRegistrationStudent Travel AwardsTutorialgraphic Sigcomm logoSigcomm'99

A Simple Approximation to Minimum-Delay Routing

Srinivas Vutukury
Computer Science Department, Baskin School of Engineering, University of California, Santa Cruz

J.J. Garcia-Luna-Aceves
Computer Engineering Department, Baskin School of Engineering University of California, Santa Cruz

The conventional approach to routing in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Single-path routing is very responsive to topological and link-cost changes; however, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase. On the other hand, minimum-delay routing approaches can minimize delays only when traffic is stationary or very slowly changing.

We present a "near-optimal" routing framework that offers delays comparable to those of optimal routing and that is as flexible and responsive as single-path routing protocols proposed to date. First, an approximation to the Gallager's minimum-delay routing problem is derived, and then algorithms that implement the approximation scheme are presented and verified. We introduce the first routing algorithm based on link-state information that provides multiple paths of unequal cost to each destination that are loop-free at every instant. We show through simulations that the delays obtained in our framework are comparable to those obtained using the Gallager's minimum-delay routing. Also, we show that our framework renders far smaller delays and makes better use of resources than traditional single-path routing.

Papers are provided as a service to all by the members of ACM SIGCOMM. Please check this box if you are a SIGCOMM member so we can get an idea of how the service is used.

This paper is available in and .

For information about joining SIGCOMM, follow this link


The referenced paper appears in Computer Communication Review, a publication of ACM SIGCOMM, volume 29, number 4, October 1999.

ACM Copyright Notice: Copyright (c) 1999 by Association for Computing Machinery, Inc. (ACM) Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage and that the copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permission to publish from: Publications Dept. ACM, Inc. Fax +1 212 869 0481 or email at