Catálogo de publicaciones - tesis
Título de Acceso Abierto
Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
Agustín Pecorari Irene Loiseau
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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.Palabras clave – provistas por el repositorio digital
REDES DE TELECOMUNICACIONES SUPERVIVIENTES; P-CICLOS; FIPP P-CICLOS; BRANCH-AND-PRICE; SURVIVABLE NETWORKS; P-CYCLES; FIPP P-CYCLES
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2016 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2016-10-19
Información sobre licencias CC
