Broadband Communications, Networks, and Systems. 7th International ICST Conference, BROADNETS 2010, Athens, Greece, October 25–27, 2010, Revised Selected Papers

Research Article

Hybrid Demand Oblivious Routing: Hyper-cubic Partitions and Theoretical Upper Bounds

Download20 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-30376-0_7,
        author={G\^{a}bor N\^{e}meth and G\^{a}bor R\^{e}tv\^{a}ri},
        title={Hybrid Demand Oblivious Routing: Hyper-cubic Partitions and Theoretical Upper Bounds},
        proceedings={Broadband Communications, Networks, and Systems. 7th International ICST Conference, BROADNETS 2010, Athens, Greece, October 25--27, 2010, Revised Selected Papers},
        proceedings_a={BROADNETS},
        year={2012},
        month={10},
        keywords={oblivious ratio demand-oblivious routing hyper-cubic region},
        doi={10.1007/978-3-642-30376-0_7}
    }
    
  • Gábor Németh
    Gábor Rétvári
    Year: 2012
    Hybrid Demand Oblivious Routing: Hyper-cubic Partitions and Theoretical Upper Bounds
    BROADNETS
    Springer
    DOI: 10.1007/978-3-642-30376-0_7
Gábor Németh1,*, Gábor Rétvári1,*
  • 1: Budapest University of Technology and Economics
*Contact email: namethgap@tmit.bme.hu, retvari@tmit.bme.hu

Abstract

Traditionally, network routing was optimized with respect to an expected traffic matrix, which left the network in a suboptimal state if user traffic did not match expectations. A demand-oblivious routing is, contrarily, optimized with respect to all possible traffic matrices, obviating the need for traffic matrix estimation. Oblivious routing is a fundamentally distributed scheme, so it can be implemented easily. Unfortunately, in certain cases it may cause unwanted link over-utilization. Recently, we have introduced a hybrid centralized-distributed method to mitigate this shortcoming. However, our scheme did not provide a theoretical upper bound for the link over-utilization. In this paper, we tackle the problem again from a different perspective. Based on a novel hyper-cubic partition of the demand space, we construct a new algorithm that readily delivers the theoretical bounds. Simulation results show the theoretical and practical significance of our algorithm.