A second order cone model for robust network design in telecommunication

Abstract:
In planning telecommunication networks, operators usually highly overestimate capacity modules needed for routing the arising network traffic, but safety factors of 300% or more are very expensive. To reduce installation costs we consider a backbone network for telecommunication with uncertain demand between each pair of nodes. The task is to find capacities for the links in the network so that all demand can be routed through the network with high probability. Our model is based on a multicommodity flow formulation for routing the demand between each pair of nodes with chance constraints coupling flow and capacity values on each edge. If the demand can be approximated reasonably by a multivariate normal distribution, a standard approach following Lobo et. al. [9] is to reformulate the chance constraints as second order cone constraints. In practice, demand is given via past traffic matrices that typically exhibit rather strong fluctuations. The purpose of this case study is to investigate whether this second order cone approach is helpful in spite of the rather bad match between data and required distribution properties. Underlying testinstances are based on data from the US research and education network Abilene. To evaluate the quality of such a solution of this network design problem, i.e., the capacities and routings for each given demand pair, we study some so called robustness measures for comparing this modelling approach with other approaches.