SODA

Robust load-balancing under statistical uncertainty: models and polynomial-time algorithms

Gunnar, Anders and Johansson, Mikael (2009) Robust load-balancing under statistical uncertainty: models and polynomial-time algorithms. In: NGI 2009, 1-3 July 2009, Aveiro, Portugal.

Full text not available from this repository.

Abstract

We study the problem of guaranteed-performance routing under statistical traffic uncertainty. Relevant traffic models are presented and a polynomial-time algorithm for solving the associated robust routing problem is given. We demonstrate how our techniques, in combination with fundamental limitations on the accuracy of estimated traffic matrices, enable us to compute bounds on the achievable performance of OSPF-routing optimized using only topology information and link count data. We discuss extensions to other types of traffic uncertainties and describe an alternative, more memory efficient, algorithm based on combined constraint and column generation. The proposed techniques are evaluated in several numerical examples to highlight the features of our approach.

Item Type:Conference or Workshop Item (Paper)
ID Code:3595
Deposited By:Kivanc Doganay
Deposited On:18 May 2009
Last Modified:18 Nov 2009 16:24

Repository Staff Only: item control page