Minimizing average latency in oblivious routing

Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Jaikumar Radhakrishnan, Harald Rácke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

19 Zitate (Scopus)

Abstract

We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function Σe(load(e)) 2 where for a network link e, load(e) denotes the amount of traffic that has to be forwarded by the link. We show that for the case when all routing requests are directed to a single target, there is a routing scheme with competitive ratio O(log n), where n denotes the number of nodes in the network. As a lower bound we show that no oblivious scheme can obtain a competitive ratio of better than Ω(√log n). This latter result gives a qualitative difference in the performance that can be achieved by oblivious algorithms and by adaptive online algorithms, respectively, since there exist a constant competitive online routing algorithm for the cost-measure of average latency[2]. Such a qualitative difference (in general undirected networks) between the performance of online algorithms and oblivious algorithms was not known for other cost measures (e.g. edge-congestion).

OriginalspracheEnglisch
TitelProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Seiten200-207
Seitenumfang8
PublikationsstatusVeröffentlicht - 2008
Extern publiziertJa
Veranstaltung19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA/Vereinigte Staaten
Dauer: 20 Jan. 200822 Jan. 2008

Publikationsreihe

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Konferenz

Konferenz19th Annual ACM-SIAM Symposium on Discrete Algorithms
Land/GebietUSA/Vereinigte Staaten
OrtSan Francisco, CA
Zeitraum20/01/0822/01/08

Fingerprint

Untersuchen Sie die Forschungsthemen von „Minimizing average latency in oblivious routing“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren