Tesis > Documento


Ver el documento (formato PDF)   Pecorari, Agustín.  "Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos"  (2016-10-19)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Las redes de telecomunicaciones se han convertido en infraestructura fundamental para las economías y las sociedades. Debido a las altísimas velocidades de transferencia de datos, la supervivencia de la red es de primordial importancia. En caso de una falla accidental, es imperativo que la red logre una rápida recuperación para minimizar la pérdida de datos. Las redes de telecomunicaciones supervivientes son aquellas que siguen funcionando a pesar de la ocurrencia de fallas. Y esto se logra redirigiendo el tráfico afectado hacia otros sectores de la red en los cuales se instaló capacidad extra con ese fin. Al diseñar las redes de telecomunicaciones, el objetivo es que se pueda garantizar la protección del tráfico frente a ciertos tipos de fallas con el menor costo posible. Los especialistas desarrollaron inicialmente dos métodos: la protección basada en la restauración de la malla y las topologías basadas en anillos. La tecnología de p-ciclos fue propuesta a finales de la década de 1990 y se convirtió rápidamente en una técnica prometedora debido a que brinda los beneficios combinados de la velocidad de recuperación de la arquitectura de anillo y la eficiencia económica de la arquitectura de malla. Inicialmente se propusieron redes basadas en p-ciclos donde cada ciclo protege la red ante la falla de un vínculo que forma parte del ciclo o de uno que tiene sus dos extremos en éste (cuerda). Años mas tarde se desarrolló el concepto de FIPP p-ciclos (failure independent path protecting p-cycles), en el cual los p-ciclos protegen caminos entre dos de sus nodos. Nuestro trabajo se centra en los problemas de alocación de capacidades de repuesto (Spare Capacity Allocation Problem, SCA) para p-ciclos y FIPP p-ciclos. Estos problemas son NP-difíciles. Evaluamos nuestros resultados utilizando topologías de redes reales (de EEUU y Europa) y artificiales (grafos completos de hasta 12 nodos, K12). Para el primer poblema (SCA) propusimos tres nuevos modelos de programación lineal entera (PLE) y entera mixta (PLEM) que implementamos sobre CPLEX (Branchand- Cut), dos modelos de programación por restricciones (CP) sobre el motor CP de CPLEX, una metaheurística Greedy Randomized Adaptive Search Procedures (GRASP) con búsqueda local exacta y un algoritmo Branch-and-Price exacto. Con este último se obtuvieron excelentes resultados (menos de 1,5% del óptimo) para las instancias artificiales (K12 tiene mas de 59 millones de ciclos posibles). Para las redes reales de hasta 27 nodos obtuvimos resultados de menos de 4,5% del óptimo. Para el segundo problema (FIPP) propusimos un nuevo modelo PLEM que implementamos sobre CPLEX (Branch-and-Cut), un modelo de CP, una metaheurística GRASP con búsqueda local exacta y un algoritmo Branch-and-Price exacto. En este caso, el algoritmo Branch-and-Cut del modelo PLEM resultó ser el más eficiente, obteniendo la solución óptima dentro de los 5 minutos para todas nuestras instancias.

Abstract:
Telecommunications networks have become fundamental infrastructure for the economy and societies. Due to high speeds of data transfers, network survivability is of major importance. In case of an accidental failure, a fast recovery is imperative to minimize data loss. A telecommunication network is said survivable if it is still able to provide communication between sites it connects after certain component fails. Survivability is achived redirecting traffic to parts of the network where spare capacity have been installed for that porpouse. The objective of survivable network design is to guarantee the protection of the traffic on some failure scenarios at minimum cost. Mesh restoration schemes were widely used in the 1970s and early 1980s. Ring based topologies were introduced in the late 80s based on self-healing rings (SHR) networks technology. In the late 1990s the p-cycle networking concept was proposed. This new technology is reported to simultaneously provide the switching speed and simplicity of rings with the much greater efficiency and exibility for reconfiguration of a mesh network. A single unit capacity p-cycle is a cycle composed of one spare channel on each span it crosses. So a p-cycle provides one protection path for a failed span and it also protects spans that have both end nodes on the cycle but are not themselves on the cycle. In 2005, the FIPP (failure independent path protecting) p-cycle was proposed to protect paths. Our work centers on the Spare Capacity Allocation Problems (SCA) for p-cycles and FIPP p-cycles. These problems are NP-hard. We evaluated our work on topologies of real networks (USA and Europe) and artificial ones (complete graphs up to 12 nodes, K12). For the first problem (SCA) we present three new mixed integer programming (MIP) models implemented on CPLEX (Branch-and-Cut), two constraint programming (CP) models implemented on the CPLEX CP engine, one GRASP metaheuristics algorithm with exact local search and one exact Branch-and-Price algorithm. With the last algorithm we obtained excelents results (less than 1.5% optimality gap) on artificial networks with more than 59 millions cycles. For the real networks instances with up to 27 nodes we obtained less than 4.5% optimality gap. For the second problem (FIPP) we present one new mixed integer programming (MIP) model implemented on CPLEX (Branch-and-Cut), one constraint programming (CP) implemented on the CPLEX CP engine, one GRASP metaheuristics algorithm with exact local search and one exact Branch-and-Price algorithm. In this case the Branch-and- Cut algorithm based on the MIP model is the most efficient, obtaining the optimal solutions within 5 minutes for all our instancies.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos     =    P-cycle and FIPP p-cycle telecommunications network design
Autor : Pecorari, Agustín
Director : Loiseau, Irene
Consejero : Loiseau, Irene
Jurados : Cancela Bosi, Héctor  ; Méndez Díaz, Isabel  ; Vulcano, Gustavo
Año : 2016-10-19
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_6094_Pecorari
Idioma : Español
Area Temática : 
Palabras claves : REDES DE TELECOMUNICACIONES SUPERVIVIENTES; P-CICLOS; FIPP P-CICLOS; BRANCH-AND-PRICE; SURVIVABLE NETWORKS; P-CYCLES; FIPP P-CYCLES; BRANCH-AND-PRICE
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34