A practical algorithm for constructing oblivious routing schemes

Marcin Bienkowski, Miroslaw Korzeniowski, Harald Räcke

Publikation: KonferenzbeitragPapierBegutachtung

51 Zitate (Scopus)

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 [11] 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. [4] 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 Script O sign (log4 n) for undirected networks. Furthermore, our approach yields a proof for the existence of an oblivious routing scheme with competitive ratio Script O sign (log3n), which is much simpler than the original proof from [11].

OriginalspracheEnglisch
Seiten24-33
Seitenumfang10
DOIs
PublikationsstatusVeröffentlicht - 2003
Extern publiziertJa
VeranstaltungFifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - San Diego, SA, USA/Vereinigte Staaten
Dauer: 7 Juni 20039 Juni 2003

Konferenz

KonferenzFifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
Land/GebietUSA/Vereinigte Staaten
OrtSan Diego, SA
Zeitraum7/06/039/06/03

Fingerprint

Untersuchen Sie die Forschungsthemen von „A practical algorithm for constructing oblivious routing schemes“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren