Open AccessResilient overlay design in DWDM systems
Author(s) -
Pablo Romero,
Cecilia Parodi,
Franco Robledo,
Carlos E. Testuri
Publication year - 2016
Publication title -
yugoslav journal of operations research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.221
H-Index - 21
eISSN - 1820-743X
pISSN - 0354-0243
DOI - 10.2298/yjor150730001p
Subject(s) - tabu search , overlay , mathematical optimization , computer science , network planning and design , integer programming , variable neighborhood search , reduction (mathematics) , overlay network , metaheuristic , class (philosophy) , flow network , variable (mathematics) , heuristics , mathematics , computer network , the internet , artificial intelligence , mathematical analysis , geometry , world wide web , programming language
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