Resilient overlay design in DWDM systems
DOI:
https://doi.org/10.2298/YJOR150730001PKeywords:
Network survivability, Network Optimization, OverlayAbstract
The goal of this work is to design a minimum cost resilient overlay network, where a data network is on top of a transport network. Two major challenges are addressed. On one hand, a single failure in the transport network causes multiple simultaneous failures; on the other, the multicommodity flow must respect integrality. An integer programming formulation is presented to design an overlay, meeting the previous constraints. We prove the problem belongs to the class NP-Hard. Then, a decomposition approach is introduced, where the problem is solved in two steps by means of relaxations of the original formulation. Experiments carried out with real-life instances, coming from the Uruguayan telecommunication operator, show that the approach is competitive with respect to previous metaheuristics, to know, Tabu-Search (TS) and Variable Neighborhood Search (VNS). A modest percentage of cost-reduction is achieved in some instances, which means millionaire savings in practice.References
Colbourn, C.J., Reliability Issues In Telecommunications Network Planning, Springer, US, 1999.
Orlowski, S., Koster, A., Raack, C., and Wessly, R., ”Two-layer network design by branch-and-cut featuring MIP-based heuristics”, in: Proceedings of the Third International Network Optimization Conference (INOC 2007) Spa, Belgium, 2007.
Ruiz, M., Pedrola, O., Velasco, L., Careglio, D., Fernández-Palacios, J., and Junyent, G., ”Survivable IP/MPLS-Over-WSON multilayer network optimization”, Optical Communications and Networking, 3 (8) 2011, 629–640.
Zhang, X., Li, K., and Bian, L., ”Towards the maximum resource sharing degree for survivable IP/MPLS over WDM mesh networks”, Optical Switching and Networking, 11 (2014) 177–188.
Fouilhoux, P., Karasan, O.E., Mahjoub, A.R., Zkk, O., and Yaman, H., ”Survivability in hierarchical telecommunications networks”, Networks, 59 (1) (2012) 37–58.
Okamura, H., and Seymour, P., ”Multicommodity flows in planar graphs”, Combinatorial Theory, Series B, 31 (1) (1981) 75–81.
Alevras, D., Grötschel, M., and Wessly, R., ”A network dimensioning tool”, in: Preprint SC 96–49, Konrad-Zuse-Zentrum für Informationstechnik, 1996.
Raack, C., Koster, A., Orlowski, S., and Wessly, R., ”On cuinequalities for capacitated net design polyhedra”, Networks, 2010.
Oellrich, M., ”Minimum cost disjoint paths under arc dependence”, University of Technology Berlin, (4) 2008.
Parodi, C., ”Integer optimization applied to the design of robust minimum cost multi-layer networks”, Master’s thesis, Facultad de Ingeniería, Universidad de la República Uruguay, 2011.
Baiou, M., ”Le problème du sous graphe Steiner 2-arête connexe: Approche polyédrale”, Ph.D. dissertation, Université de Rennes I, France, 1996.
Risso, C., ”Using GRASP and GA to design resilient and cost-effective IP/MPLS networks”, Theses, University of the Republic, Uruguay, 2014.
IBM, IBM ILOG CPLEX V12.1: User’s Manual for CPLEX, International Business Machines Corporation, Armonk, New York, US, 2009.
Corez, A., ”Multi-Overlay network planning by applying a variable neighbourhood search approach”, Master’s thesis, Facultad de Ingeniería, Universidad de la República Uruguay, 2010.
Despaux, F., ”Optimización de una Red de Datos IP/MPLS sobre SDH/DWDM usando Tabú Search”, 2011.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
