The planning of a communication network inevitably depends on the quality of both the planning tool and the demand forecast used. In this article, we show by example how the emerging area of robust optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.

Next generation 5G networks will rely on virtualized Data Centers (vDC) to host virtualized network functions on commodity servers. Such Network Function Virtualization (NFV) will lead to significant savings in terms of infrastructure cost and reduced management complexity. However, green strategies for networking and computing inside data centers, such as server consolidation or energy aware routing, should not negatively impact the quality and service level agreements expected from network operators. In this paper, we study how robust strategies that place virtual network func- tions (VNF) inside vDC impact the energy savings and the protection level against resource demand uncertainty. We propose novel optimization mod- els that allow the minimization of the energy of the computing and network infrastructure which is hosting a set of service chains that implement the VNFs. The model explicitly provides for robustness to unknown or impre- cisely formulated resource demand variations, powers down unused routers, switch ports and servers, and calculates the energy optimal VNF placement and network embedding also considering latency constraints on the service chains. We propose both exact and heuristic methods. Our experiments were carried out using the virtualized Evolved Packet Core (vEPC), which allows us to quantitatively assess the trade-off between energy cost, robust- ness and the protection level of the solutions against demand uncertainty. Our heuristic is able to converge to a good solution in a very short time, in comparison to the exact solver, which is not able to output better results in a longer run as demonstrated by our numerical evaluation. We also study the degree of robustness of a solution for a given protection level and the cost of additional energy needed because of the usage of more computing and network elements.Peer ReviewedPostprint (author's final draft

We propose a pure 0-1 formulation for the wireless network design problem, i.e., the problem of configuring a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixed-integer formulations, where power emissions are represented by continuous variables, we consider only a finite set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective basic formulation for the single knapsack problem representing the coverage condition of a receiver. This formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L (1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl. Math. 29(2–3):251–261]; and its core is an extension of the exact formulation of the GUB knapsack polytope with two GUB constraints. This special case corresponds to the very common practical situation where only one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational results over realistic instances of two typical technologies, namely, WiMAX and DVB-T. This paper was accepted by Dimitris Bertsimas, optimization.