Research Article
Optimal Oblivious Routing in Hole-Free Networks
@INPROCEEDINGS{10.1007/978-3-642-29222-4_30, author={Costas Busch and Malik Magdon-Ismail}, title={Optimal Oblivious Routing in Hole-Free Networks}, proceedings={Quality, Reliability, Security and Robustness in Heterogeneous Networks. 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range Communications Workshop, DSRC 2010, Houston, TX, USA, November 17-19, 2010, Revised Selected Papers}, proceedings_a={QSHINE}, year={2012}, month={10}, keywords={oblivious routing congestion path stretch wireless networks sensor networks}, doi={10.1007/978-3-642-29222-4_30} }- Costas Busch
Malik Magdon-Ismail
Year: 2012
Optimal Oblivious Routing in Hole-Free Networks
QSHINE
Springer
DOI: 10.1007/978-3-642-29222-4_30
Abstract
We study oblivious routing algorithms in which the packet paths are constructed independently of each other. Oblivious algorithms are inherently distributed and they can be designed to efficiently balance the network utilization. We give an oblivious routing algorithm for the class of hole-free networks, in which the nodes are topologically embedded in simple areas of the plane. Such networks appear frequently in wireless and sensor network topologies. The algorithm achieves optimal congestion and stretch. The stretch of the resulting paths is constant. The congestion is ( log), where is the optimal non-oblivious congestion and is the number of nodes. This congestion bound is asymptotically worst-case optimal for oblivious routing algorithms.