New lower bounds for oblivious routing in undirected graphs
Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton, Harald Räcke · 2006
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many sub-sequent 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(log2 n)-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 Ω ( lognlog logn) 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 evalu-ating the throughput of an oblivious routing scheme which subsumes all suggested models for the throughput of oblivi-ous routing considered so far. In this general model, we first prove a lower bound Ω ( lognlog logn) 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 Ω ( lognlog logn) on the competitive ratio of congestion based oblivious routing with adversarial demands.