%0 Tesis doctoral %0 Tesis doctoral %0 publishedVersion %A Pecorari, Agustín %E Loiseau, Irene %I Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales %D 2016 %G Español %T Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos %U https://hdl.handle.net/20.500.12110/tesis_n6094_Pecorari %X Las redes de telecomunicaciones se han convertido en infraestructura fundamental paralas 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, esimperativo 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 pesarde la ocurrencia de fallas. Y esto se logra redirigiendo el tráfico afectado hacia otros sectoresde 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 laprotección del tráfico frente a ciertos tipos de fallas con el menor costo posible. Los especialistasdesarrollaron inicialmente dos métodos: la protección basada en la restauraciónde la malla y las topologías basadas en anillos. La tecnología de p-ciclos fue propuesta afinales de la década de 1990 y se convirtió rápidamente en una técnica prometedora debidoa que brinda los beneficios combinados de la velocidad de recuperación de la arquitecturade anillo y la eficiencia económica de la arquitectura de malla. Inicialmente se propusieronredes basadas en p-ciclos donde cada ciclo protege la red ante la falla de un vínculo queforma parte del ciclo o de uno que tiene sus dos extremos en éste (cuerda). Años mas tardese 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 problemasson 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 linealentera (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 seobtuvieron 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 nodosobtuvimos resultados de menos de 4,5% del óptimo. Para el segundo problema (FIPP) propusimos un nuevo modelo PLEM que implementamossobre CPLEX (Branch-and-Cut), un modelo de CP, una metaheurística GRASPcon 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 lasolución óptima dentro de los 5 minutos para todas nuestras instancias.