A practical framework for minimum‐delay routing in computer networks

Article type: Research Article

Authors: Vutukury, Srinivas | Garcia‐Luna‐Aceves, J.J.

Affiliations: Cumputer Sciences Department, University of California, Santa Cruz, CA 95064, USA E‐mail: vutukury@cse.ucsc.edu | Computer Engineering Department, University of California, Santa Cruz, CA 95064, USA; Networking and Security Center, Sun Microsystems Laboratories, Palo Alto, CA 94303, USA E‐mail: jj@cse.ucsc.edu

Abstract: 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 describe 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 for minimum‐delay routing are comparable to those obtained using Gallager’s algorithm for minimum‐delay routing. Also, we show that our framework renders far smaller delays and makes better use of resources than traditional single‐path routing.

Journal: Journal of High Speed Networks, vol. 8, no. 4, pp. 241-263, 1999