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
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||