Optimal Oblivious Path Selection on the Mesh Costas Busch Malik Magdon-Ismail Jing Xi 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 independent. 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(d2) 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. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-04-07
Optimal Oblivious Path Selection on the Mesh
Costas Busch
Malik Magdon-Ismail
Jing Xi
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 independent. 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(d2) 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.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-04-07