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

Research Article

Optimal Oblivious Routing in Hole-Free Networks

Download
468 downloads
  • @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
Costas Busch1,*, Malik Magdon-Ismail2,*
  • 1: Louisiana State University
  • 2: Rensselaer Polytechnic Institute
*Contact email: busch@csc.lsu.edu, magdon@cs.rpi.edu

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.