Optimal Oblivious Path Selection on the Mesh
|
In the oblivious path selection problem, each packet in the network independently chooses a path, which is an important property if the routing algorithm is to be independent of the traffic distribution. The quality of the paths is determined by the congestion $C$, the maximum number of paths crossing an edge, and the dilation $D$, the maximum path length. So far, the oblivious algorithms studied in the literature have focused on minimizing the congestion while ignoring the dilation. An open question is whether $C$ and $D$ can be controlled simultaneously. Here, we answer this question for the $d$-dimensional mesh. We present an oblivious algorithm for which $C$ and $D$ are both within $O(d^2)$ of optimal. The algorithm uses randomization, and we show that the number of random bits required per packet is within $O(d)$ of the minimum number of random bits required by any algorithm that obtains the same congestion. For fixed $d$, our algorithm is asymptotically optimal.
[1] 660 J. Aspens, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts, “Online Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing,” Proc. 25th Symp. Theory of Computing, pp.623-631, 1993.
[2] B. Awerbuch and Y. Azar, “Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation,” Proc. 35th Symp. Foundations of Computer Science, pp. 240-249, 1994.
[3] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke, “Optimal Oblivious Routing in Polynomial Time,” Proc. 35th Symp. Theory of Computing, pp. 383-388, 2003.
[4] M. Bienkowski, M. Korzeniowski, and H. Räcke, “A Practical Algorithm for Constructing Oblivious Routing Schemes,” Proc. 15th Symp. Parallelism in Algorithms and Architectures, pp. 24-33, 2003.
[5] A. Borodin and J.E. Hopcroft, “Routing, Merging, and Sorting on Parallel Models of Computation,” J. Computer and System Science, vol. 30, pp. 130-145, 1985.
[6] C. Busch, M. Magdon-Ismail, and J. Xi, “Oblivious Routing on Geometric Networks,” Proc. 17th Symp. Parallelism in Algorithms and Architectures, pp. 316-324, 2005.
[7] C. Busch, M. Magdon-Ismail, and J. Xi, “Optimal Oblivious Path Selection on the Mesh,” Proc. 19th Int'l Parallel and Distributed Processing Symp., pp. 82-91, 2005.
[8] J. Gao and L. Zhang, “Tradeoffs between Stretch Factor and Load Balancing Ratio in Wireless Network Routing,” Proc. 23rd Symp. Principles of Distributed Computing, pp. 189-196, 2004.
[9] C. Harrelson, K. Hildrum, and S. Rao, “A Polynomial-Time Tree Decomposition to Minimize Congestion,” Proc. 15th Symp. Parallelism in Algorithms and Architectures, pp. 34-43, 2003.
[10] C. Kaklamanis, D. Krizanc, and T. Tsantilas, “Tight Bounds for Oblivious Routing in the Hypercube,” Proc. Second Symp. Parallelism in Algorithms and Architectures, pp. 31-36, 1990.
[11] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Elsevier, 1992.
[12] F.T. Leighton, B.M. Maggs, and S.B. Rao, “Packet Routing and Job-Scheduling in $O(congestion + dilation)$ Steps,” Combinatorica, vol. 14, pp. 167-186, 1994.
[13] B.M. Maggs, F. Meyer auf der Heide, B. Vöcking, and M. Westermann, “Exploiting Locality in Data Management in Systems of Limited Bandwidth,” Proc. 38th Symp. Foundations of Computer Science, pp. 284-293, 1997.
[14] F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, and M. Grünewald, “Congestion, Dilation, and Energy in Radio Networks,” Theory of Computing Systems, vol. 37, no. 3, pp. 343-370, 2004.
[15] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge Univ. Press, 2000.
[16] H. Räcke, “Minimizing Congestion in General Networks,” Proc. 43rd Symp. Foundations of Computer Science, pp. 43-52, 2002.
[17] H. Räcke, “Data Management and Routing in General Networks,” PhD dissertation, Univ. of Paderborn, 2003.
[18] P. Raghavan and C.D. Thompson, “Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs,” Combinatorica, vol. 7, pp. 365-374, 1987.
[19] C. Scheideler, unpublished course notes, http://www14.in. tum.de/lehre/2005WS/naindex.html.en , 2008.
[20] A. Srinivasan and C.-P. Teo, “A Constant Factor Approximation Algorithm for Packet Routing and Balancing Local versus Global Criteria,” Proc. 29th Symp. Theory of Computing, pp. 636-643, 1997.
[21] L.G. Valiant and G.J. Brebner, “Universal Schemes for Parallel Communication,” Proc. 13th Symp. Theory of Computing, pp. 263-277, 1981.
Index Terms:
Routing protocols
Citation:
Costas Busch, Malik Magdon-Ismail, Jing Xi, "Optimal Oblivious Path Selection on the Mesh," IEEE Transactions on Computers, vol. 57, no. 5, pp. 660-671, Jan. 2008, doi:10.1109/TC.2008.23
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb