New lower bounds for oblivious routing in undirected graphs

Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations

Abstract

Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (with respect to edge congestion) for any undirected graph. However, there are directed networks for which the competitive ratio is in Ω(√n). To cope with this inherent hardness in general directed networks, the concept of oblivious routing with demands chosen randomly from a known demand distribution was introduced recently. Under this new model, O(log 2n)-competitiveness with high probability is possible in general directed graphs. However, it remained an open problem whether or not the competitive ratio, under this new model, could also be significantly improved in undirected graphs. In this paper, we rule out this possibility by providing a lower bound of Ω(log n/log log n) for the multicommodity case and Ω(√log n) for the single-sink case for oblivious routing in a random demand model. We also introduce a natural candidate model for evaluating the throughput of an oblivious routing scheme which subsumes all suggested models for the throughput of oblivious routing considered so far. In this general model, we first prove a lower bound Ω(log n/log log n) for the competitive ratio of any oblivious routing scheme. Interestingly, the graphs that we consider for the lower bound in this case are expanders, for which we also obtain a lower bound Ω(log n/log log n) on the competitive ratio of congestion based oblivious routing with adversarial demands.

Original languageEnglish
Pages918-927
Number of pages10
DOIs
StatePublished - 2006
Externally publishedYes
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: 22 Jan 200624 Jan 2006

Conference

ConferenceSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period22/01/0624/01/06

Fingerprint

Dive into the research topics of 'New lower bounds for oblivious routing in undirected graphs'. Together they form a unique fingerprint.

Cite this