Oblivious Routing on Geometric Networks Costas Busch Malik Magdon-Ismail Jing Xi We study oblivious routing algorithms in which packet paths are constructed independently. We give a very simple oblivious routing algorithm for geometric networks (networks which are embedded in the Euclidean plane): choose a random intermediate node in the space between the source and destination, and then send the packet to its destination through the intermediate node. We analyze this simple algorithm in terms of stretch and congestion. We show that the stretch is constant, and the congestion is near optimal when the network paths can be chosen to be close to the geodesics. We give applications of our general result to the mesh topology and uniform disc graphs. Previous oblivious routing algorithms with near optimal congestion use many intermediate nodes and do not control the stretch. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-05-04
Oblivious Routing on Geometric Networks
Costas Busch
Malik Magdon-Ismail
Jing Xi
We study oblivious routing algorithms in which packet paths are constructed independently. We give a very simple oblivious routing algorithm for geometric networks (networks which are embedded in the Euclidean plane): choose a random intermediate node in the space between the source and destination, and then send the packet to its destination through the intermediate node. We analyze this simple algorithm in terms of stretch and congestion. We show that the stretch is constant, and the congestion is near optimal when the network paths can be chosen to be close to the geodesics. We give applications of our general result to the mesh topology and uniform disc graphs. Previous oblivious routing algorithms with near optimal congestion use many intermediate nodes and do not control the stretch.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-05-04