RESILIENT OVERLAY DESIGN IN DWDM SYSTEMS

  • Cecilia Parodi Facultad de Ingenier´ıa, Universidad de la Rep ´ublica–Uruguay
  • Franco Robledo Facultad de Ingenier´ıa, Universidad de la Rep ´ublica–Uruguay
  • Pablo Romero Facultad de Ingenier´ıa, Universidad de la Rep ´ublica–Uruguay
  • Carlos E. Testuri Facultad de Ingenier´ıa, Universidad de la Rep ´ublica–Uruguay

Abstract

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 that 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.

Published
Oct 1, 2016
How to Cite
PARODI, Cecilia et al. RESILIENT OVERLAY DESIGN IN DWDM SYSTEMS. Yugoslav Journal of Operations Research, [S.l.], v. 26, n. 3, oct. 2016. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/5>. Date accessed: 29 mar. 2024.
Section
Articles