Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Pecorari, Agustín
Otros Autores: Loiseau, Irene
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2016
Materias:
REDES DE TELECOMUNICACIONES SUPERVIVIENTES
P-CICLOS
FIPP P-CICLOS
BRANCH-AND-PRICE
SURVIVABLE NETWORKS
P-CYCLES
FIPP P-CYCLES
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6094_Pecorari
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n6094_Pecorari
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic REDES DE TELECOMUNICACIONES SUPERVIVIENTES
P-CICLOS
FIPP P-CICLOS
BRANCH-AND-PRICE
SURVIVABLE NETWORKS
P-CYCLES
FIPP P-CYCLES
BRANCH-AND-PRICE
spellingShingle REDES DE TELECOMUNICACIONES SUPERVIVIENTES
P-CICLOS
FIPP P-CICLOS
BRANCH-AND-PRICE
SURVIVABLE NETWORKS
P-CYCLES
FIPP P-CYCLES
BRANCH-AND-PRICE
Pecorari, Agustín
Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
topic_facet REDES DE TELECOMUNICACIONES SUPERVIVIENTES
P-CICLOS
FIPP P-CICLOS
BRANCH-AND-PRICE
SURVIVABLE NETWORKS
P-CYCLES
FIPP P-CYCLES
BRANCH-AND-PRICE
description 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.
author2 Loiseau, Irene
author_facet Loiseau, Irene
Pecorari, Agustín
format Tesis doctoral
Tesis doctoral
publishedVersion
author Pecorari, Agustín
author_sort Pecorari, Agustín
title Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
title_short Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
title_full Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
title_fullStr Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
title_full_unstemmed Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos
title_sort diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y fipp p-ciclos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2016
url https://hdl.handle.net/20.500.12110/tesis_n6094_Pecorari
work_keys_str_mv AT pecorariagustin disenoderedesdecomunicacionesmediantearquitecturasdepciclosyfipppciclos
AT pecorariagustin pcycleandfipppcycletelecommunicationsnetworkdesign
_version_ 1782022271133548544
spelling tesis:tesis_n6094_Pecorari2023-10-02T20:15:04Z Diseño de redes de comunicaciones mediante arquitecturas de p-ciclos y FIPP p-ciclos P-cycle and FIPP p-cycle telecommunications network design Pecorari, Agustín Loiseau, Irene REDES DE TELECOMUNICACIONES SUPERVIVIENTES P-CICLOS FIPP P-CICLOS BRANCH-AND-PRICE SURVIVABLE NETWORKS P-CYCLES FIPP P-CYCLES BRANCH-AND-PRICE 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. Telecommunications networks have become fundamental infrastructure for the economyand 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 communicationbetween sites it connects after certain component fails. Survivability is achived redirectingtraffic 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 trafficon some failure scenarios at minimum cost. Mesh restoration schemes were widely used inthe 1970s and early 1980s. Ring based topologies were introduced in the late 80s basedon self-healing rings (SHR) networks technology. In the late 1990s the p-cycle networkingconcept was proposed. This new technology is reported to simultaneously provide theswitching speed and simplicity of rings with the much greater efficiency and exibility forreconfiguration of a mesh network. A single unit capacity p-cycle is a cycle composed ofone spare channel on each span it crosses. So a p-cycle provides one protection path for afailed span and it also protects spans that have both end nodes on the cycle but are notthemselves on the cycle. In 2005, the FIPP (failure independent path protecting) p-cyclewas 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 realnetworks (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 algorithmwith exact local search and one exact Branch-and-Price algorithm. With the last algorithmwe obtained excelents results (less than 1.5% optimality gap) on artificial networkswith more than 59 millions cycles. For the real networks instances with up to 27 nodes weobtained 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 exactlocal 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 solutionswithin 5 minutes for all our instancies. Fil: Pecorari, Agustín. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2016-10-19 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n6094_Pecorari

Ejemplares similares