Oblivious routing on node-capacitated and directed graphs

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

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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).

Original languageEnglish
Article number1290688
JournalACM Transactions on Algorithms
Volume3
Issue number4
DOIs
StatePublished - 1 Nov 2007
Externally publishedYes

Keywords

  • Communication networks
  • Directed graphs
  • Node-capacitated graphs
  • Oblivious routing

Fingerprint

Dive into the research topics of 'Oblivious routing on node-capacitated and directed graphs'. Together they form a unique fingerprint.

Cite this