On the Robustness of Optimal Network Designs

Robust optimization is an emerging field in telecommunication network design which takes future traffic uncertainty into account. This yields optimal robust network designs which are optimal for all traffic realizations within a pre-defined set of uncertainty. In 2003, Bertsimas and Sim have introduced an adjustable uncertainty set for general optimization problems which preserves the computational complexity of the original non-robust problem. Recently, Koster et al. have applied this approach to network design problems. In this paper, we consider this so-called Γ-robust network design problem. We investigate the importance of statistical input data analysis to determine reasonable parameter settings for robust network planning. Using detailed real-life traffic measurements of two backbone networks (Abilene and GEANT), we determine optimal robust network designs for 495 different parameter settings per network. Afterwards, we evaluate the realized robustness (i.e., the percentage of supported traffic matrices) w.r.t. the planning data and a larger set of historical data to simulate uncertain future traffic.