Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Oblivious routing on node-capacitated and directed graphs

Oblivious routing on node-capacitated and directed graphs 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 (&sqrt; k log( n )) for undirected node-capacitated graphs and O (&sqrt; 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 (&sqrt; n 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 Ω(&sqrt; 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 ). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Oblivious routing on node-capacitated and directed graphs

Download PDF
13 pages

Loading next page...
 
/lp/association-for-computing-machinery/oblivious-routing-on-node-capacitated-and-directed-graphs-HBsnPMebw8

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2007 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1290672.1290688
Publisher site
See Article on Publisher Site

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 (&sqrt; k log( n )) for undirected node-capacitated graphs and O (&sqrt; 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 (&sqrt; n 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 Ω(&sqrt; 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 ).

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2007

There are no references for this article.