Startseite > Publikationen > Publikationen

Publikationen

Bienkowski, Marcin;Korzeniowski, Miroslaw;Räcke, Harald:

A Practical Algorithm for Constructing Oblivious Routing Schemes.

In: Proc. 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'2003), S. 24-33, 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 citeR02 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. citeACF+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^4n)$
for undirected networks. Furthermore, our approach yields a proof
for the existence of an oblivious routing scheme with competitive ratio
$O(log^3n)$, which is much simpler than the original proof from citeR02.

Dateien

paper.pdf
paper.ps



Bibtex

@inproceedings{hniid=1502,
author = {Bienkowski, Marcin and Korzeniowski, Miroslaw and R{\"a}cke, Harald},
title = {A Practical Algorithm for Constructing Oblivious Routing Schemes},
booktitle = {Proc. 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'2003)},
pages = {24-33},
year = {2003},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1502