Oblivious routing on node-capacitated and directed graphs

ABSTRACT

Oblivious routing algorithms for general undirected networks were introduced by Räcke [17], 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 non-trivial upper bounds for both these cases, providing algorithms for k-commodity oblivious routing problems with competitive ratio O(√klog(n)) for undirected node-capacitated graphs and O(√kn^1/4log(n)) for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes O(√nlog(n)) in both cases, matching the lower bound up to a factor of log(n). The lower bound (which first appeared in [6]) 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).

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 routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 3: B. Awerbuch and Y. Azar, Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1994, pp. 240--249.
• 4: B. Awerbuch and T. Leighton, A simple local control approximation algorithm for multicommodity flow, in Proceedings of the 34th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1993, pp. 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, Theoretical Computer Science, v.221 n.1-2, p.19-39, June 28, 1999 [doi>10.1016/S0304-3975(99)00025-0]
• 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: G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20 (1998), pp. 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: 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]
• 14: 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]
• 15: 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
• 16: B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo, Solving symmetric diagonally dominant systems by preconditioning. manuscript, 2003.
• 17: 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
• 18: 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]