Garcia-Luna-Aceves. A Simple Approximation to Minimum-Delay Routing

The conventional approach to routing in computer networks con-sists 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 de-lays, 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 de-lays 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 ap-proximation 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 ob-tained in our framework are comparable to those obtained using the Gallager’s minimum-delay routing. Also, we show that our frame-work renders far smaller delays and makes better use of resources than traditional single-path routing.