TY - JOUR

T1 - Oblivious routing on node-capacitated and directed graphs

AU - Hajiaghayi, Mohammad Taghi

AU - Kleinberg, Robert D.

AU - Räcke, Harald

AU - Leighton, Tom

PY - 2007/11/1

Y1 - 2007/11/1

N2 - Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities. We present the first nontrivial upper bounds for both these cases, providing algorithms for k-commodity oblivious routing problems with competitive ratio O(√k log(n)) for undirected nodecapacitated graphs and O(√ k n 1/4 log(n)) for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes O(√k log(n)) in both cases, matching the lower bound up to a factor of log(n). The lower bound (which first appeared in Azar et al. [2003]) is obtained on a graph with very high degree.We show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an O(Δ polylog(n))- competitive oblivious routing scheme for graphs of degree Δ. For the directed case, however, we show that the lower bound of Ω(√n) still holds in low-degree graphs. Finally, we settle an open question about routing problems in which all commodities share a common source or sink.We show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than Ω(log n).

AB - Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities. We present the first nontrivial upper bounds for both these cases, providing algorithms for k-commodity oblivious routing problems with competitive ratio O(√k log(n)) for undirected nodecapacitated graphs and O(√ k n 1/4 log(n)) for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes O(√k log(n)) in both cases, matching the lower bound up to a factor of log(n). The lower bound (which first appeared in Azar et al. [2003]) is obtained on a graph with very high degree.We show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an O(Δ polylog(n))- competitive oblivious routing scheme for graphs of degree Δ. For the directed case, however, we show that the lower bound of Ω(√n) still holds in low-degree graphs. Finally, we settle an open question about routing problems in which all commodities share a common source or sink.We show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than Ω(log n).

KW - Communication networks

KW - Directed graphs

KW - Node-capacitated graphs

KW - Oblivious routing

UR - http://www.scopus.com/inward/record.url?scp=36448959813&partnerID=8YFLogxK

U2 - 10.1145/1290672.1290688

DO - 10.1145/1290672.1290688

M3 - Article

AN - SCOPUS:36448959813

SN - 1549-6325

VL - 3

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 4

M1 - 1290688

ER -