Semi-oblivious routing: lower bounds

ABSTRACT

We initiate the study of semi-oblivious routing, a relaxation of oblivious routing which is first introduced by Räcke and led to many subsequent improvements and applications. In semi-oblivious routing like oblivious routing, the algorithm should select only a polynomial number of paths between the source and the sink of each commodity, but unlike oblivious routing, the flow from each source to its sink is not just a scalar multiple of the single-commodity flow; any amount of flow can be sent along each selected path. Semi-oblivious routing has several applications in traffic engineering and VLSI routing.

Trivially, any competitive ratio ρ for oblivious routing (includling the polylogarthimic ratio in undirected graphs obtained by Räcke) also implies competitive ratio ρ for semi-oblivious routing. In this paper, we focus on lower bounds. We rule out the possibility of O(1) competitive ratio for semi-oblivious routing in undirected graphs by providing a lower bound of Ω(log n/log log n) in grids or even series-parallel graphs. More strongly in directed graphs, we rule out the possibility of sub-polynomial competitive ratio when the number of paths between each source and its sink is in O(n^1/5). The proof of our lower bound on the grid uses a non-Markovian random walk on the integers with a mixing property which may be of independent interest. Last but not least, our lower bounds on the grid can be significantly strengthened to show that with paths of at most b bends, the competitive ratio is in Ω(n^1/2b+1). This answers negatively a long-standing open problem on b-bend routing schemes in grids posed e.g. in [10, 6].

REFERENCES

• 1: M. Andrews, D. Bhatia, T. Leighton, F. Makedon, C. H. Norton, and Y. L. Zhang, Improved algorithms for routing on two-dimensional grids. Unpublished manuscript available at citeseer.ist.psu.edu/249177.html.
• 2: D. O. Awduche, MPLS and traffic engineering in ip networks, IEEE Communications Magazine, (1999), pp. 42--47.
• 3: Baruch Awerbuch , Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton, Online client-server load balancing without global information, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: 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]
• 5: 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]
• 6: C. Haibt-Norton, Promlems in Discrete Optimization, PhD thesis, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, 1993.
• 7: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: 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]
• 9: R. Karp, T. Leighton, R. Rivest, C. Thompson, U. Vazirani, and V. Vazirani, Global wire routing in two-dimensional arrays, Algorithmica, 2 (1987), pp. 113--129.
• 10: T. Leighton, Research Topics in Theory of Parallel Computation and VLSI. Course Notes from Fall 1985.
• 11: 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