ALCOMFT-TR-03-116

Marcin Bienkowski, Miroslaw Korzeniowski and Harald Räcke
A Practical Algorithm for Constructing Oblivious Routing Schemes
Paderborn. Work package 2. December 2003.

Abstract: In a (randomized) oblivious routing scheme the path chosen for a request between a source s and a target t is independent from the current traffic in the network. Hence, such a scheme consists of probability distributions over s-t paths for every source-target pair s,t in the network.

In a recent result [R02] it was shown that for any undirected network there is an oblivious routing scheme that achieves a polylogarithmic competitive ratio with respect to congestion. Subsequently, Azar et al. [ACF+03] gave a polynomial time algorithm that for a given network constructs the best oblivious routing scheme, i.e. the scheme that guarantees the best possible competitive ratio. Unfortunately, the latter result is based on the Ellipsoid algorithm; hence it is unpractical for large networks.

In this paper we present a combinatorial algorithm for constructing an oblivious routing scheme that guarantees a competitive ratio of \O(log⁴n) for undirected networks. Furthermore, our approach yields a proof for the existence of an oblivious routing scheme with competitive ratio \O(log³n), which is much simpler than the original proof from [R02].

Postscript file: ALCOMFT-TR-03-116.ps.gz (208 kb).