Integer optimization applied to the design of robust minimum cost multi-layer networks.

Abstract

In this work we solve the problem of designing an MPLS data network, to be deployed over an existing SDH/DWDM transport infrastructure, which is itself a combination of technologies. The data and different work hypothesis are from a particular operator: the National Telecommunications Administration (ANTEL) of Uruguay where the problem was originated. The target Data Network is an IP/MPLS Multi-Layer network over which different kinds of services are delivered and therefore with different quality requirements. During the process we will seek to minimize the economical resources incurred by the deployment over the Transport Infrastructure (Transport Network) of ANTEL. The solution found should be of optimal (minimum) cost and must be able to send a known traffic meeting certain quality parameters, even considering simple failures in some section of the Transport Network. The proposed problem is NP-Hard class in terms of computational complexity. Special cases of it are NP-complete problems. We model the problem algebraically as an Integer Mathematical Programming Problem and solve it approximately.

En este trabajo se resuelve el problema de diseñar una red de datos MPLS, a ser desplegada sobre una infraestructura de transporte SDH/DWDM ya existente, que es a su vez una combinación de tecnologías. Los datos y las distintas hipótesis de trabajo son de un operador particular: la Agencia Nacional de Telecomunicaciones (ANTEL) de Uruguay, donde este problema fue originado. La Red de Datos objetivo es una red multi-capa IP/MPLS sobre la cual se distribuyen diferentes tipos de servicios que tiene distintos requerimientos de calidad. Durante el proceso se buscará minimizar los recursos económicos que surgen del despliegue sobre la infraestructura de transporte (Red de Transporte) de ANTEL. La solución encontrada debe ser de mínimo costo y debe poder enviar determinado tráfico cumpliendo con ciertos parámetros de calidad, incluso frente a fallas simples en la Red de Transporte. El problema propuesto es de la clase NP-Hard en términos de complejidad computacional. Casos particulares del mismo son problemas NP-Completos. Modelamos el problema de forma algebraica como un problema de Programación Entera y lo resolvemos de forma aproximada.