Oblivious routing in directed graphs with random demands

ABSTRACT

Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. Comparatively little positive results are known about oblivious routing in general directed networks. Using a novel approach, we present the first oblivious routing algorithm which is O(log² n) competitive with high probability in directed graphs given that the demands are chosen randomly from a known demand-distribution. On the other hand, we show that no oblivious routing algorithm can be o(logn/log log n) competitive even with constant probability in general directed graphs.Our routing algorithms are not oblivious in the traditional definition, but we add the concept of demand-dependence, i.e., the path chosen for an s-t pair may depend on the demand between s and t. This concept that still preserves that routing decisions are only based on local information proves very powerful in our randomized demand model.Finally, we show that our approach for designing competitive oblivious routing algorithms is quite general and has applications in other contexts like stochastic scheduling.

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: 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
• 3: 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]
• 4: 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]
• 5: Stéphane Boucheron , Gábor Lugosi , Pascal Massart, A sharp concentration inequality with application, Random Structures & Algorithms, v.16 n.3, p.277-292, May 2000 [doi>10.1002/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO;2-1 ]
• 6: 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]
• 7: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 8: Brian C. Dean , Michel X. Goemans , Jan Vondrák, Adaptivity and approximation for stochastic packing problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: 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
• 10: 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]
• 11: B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo, Solving symmetric diagonally-dominant systems by preconditioning. manuscript, 2003.
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: 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
• 14: Harald Räcke , Adi Rosén, Distributed online call control on general networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: 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:
demand distributions, directed graphs, oblivious routing