Network Design Under Demand Uncertainties: A Case Study on the Abilene and GÉANT network data

Inhalt:
Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. Often, expensive safety factors of 300% or more are applied to the link capacity. In this paper, we consider telecommunication network design under demand uncertainty, adopting the robust optimization approach of Bertsimas and Sim. This deterministic approach provides an adjustable uncertainty and preserves the computational complexity of the original non-robust problem. Recently, Koster et al. have applied this approach to network design problems. Using detailed real-life traffic measurements of the US Internet 2 (Abilene) and the pan-European research and education network (GEANT) backbone networks, we present an extensive computational case study for this so-called Γ-robust network design problem. For each network, we determine optimal robust network designs for 198 different parameter settings. Afterwards, we evaluate the realized robustness of these designs with respect to (i) the traffic measurements used as planning data, and (ii) a larger set of traffic measurements including the planning data to simulate uncertain future traffic. We give different robust measurements (e. g., the percentage of supported traffic matrices, or the percentage of congested links) and compare the corresponding realized robustnesses. We report on the importance of statistical input data analysis to determine reasonable parameter settings for robust network planning. Further, by determining pareto-optimal parameter settings based on the price of robustness and the evaluated realized robustness, our analysis provides practical decision support criteria for network planners.