Oblivious routing on node-capacitated and directed graphs

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

REFERENCES

• 1: Noga Alon , Baruch Awerbuch , Yossi Azar , Niv Buchbinder , Joseph (Seffi) Naor, A general approach to online network optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
• 3: Awerbuch, B., and Azar, Y. 1994. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), 240--249.
• 4: Awerbuch, B., and Leighton, F. T. 1993. A simple local-control approximation algorithm for multicommodity flow. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 459--468.
• 5: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 6: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 7: Yair Bartal , Stefano Leonardi, On-Line Routing in All-Optical Networks, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.516-526, July 07-11, 1997
• 8: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 9: Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007383]
• 10: Even, G., Naor, J. S., Schieber, B., and Sudan, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151--174.
• 11: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 12: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Multiway cuts in node weighted graphs, Journal of Algorithms, v.50 n.1, p.49-61, January 2004 [doi>10.1016/S0196-6774(03)00111-1]
• 13: Hajiaghayi, M. T., and Räcke, H. An O(&sqrt;n)-approximation algorithm for directed sparsest cut. Inf. Proc. Lett. to appear.
• 14: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 15: Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997 [doi>10.1006/jagm.1996.0833]
• 16: B. Maggs , F. Meyer auf der Heide , B. Voecking , M. Westermann, Exploiting Locality for Data Management in Systems of Limited Bandwidth, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.284, October 19-22, 1997
• 17: Bruce M. Maggs , Gary L. Miller , Ojas Parekh , R. Ravi , Shan Leung Maverick Woo, Finding effective support-tree preconditioners, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073996]
• 18: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 19: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
Oblivious routing, communication networks, directed graphs, node-capacitated graphs