loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers
Optimal Oblivious Path Selection on the Mesh
Denver, Colorado
April 04-April 08
ISBN: 0-7695-2312-9
Costas Busch, Rensselaer Polytechnic Institute, Troy, NY
Malik Magdon-Ismail, Rensselaer Polytechnic Institute, Troy, NY
Jing Xi, Rensselaer Polytechnic Institute, Troy, NY
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 controled simultaneously. Here, we answer this question for the d-dimensional mesh. We present an online 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 near-optimal congestion. For fixed d, our algorithm is asymptotically optimal.
Citation:
Costas Busch, Malik Magdon-Ismail, Jing Xi, "Optimal Oblivious Path Selection on the Mesh," ipdps, vol. 1, pp.82, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, 2005
Usage of this product signifies your acceptance of the Terms of Use.