Research Article
Hybrid Demand Oblivious Routing: Hyper-cubic Partitions and Theoretical Upper Bounds
@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
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.