Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia
Una red de comunicaciones se dice superviviente si puede continuar brindando servicio pese a la falla de alguno de sus componentes. Hacia fines de los noventa surgió el concepto de p-ciclos como alternativa prometedora a las tecnologías existentes (malla y anillos) para el diseño de redes supervivie...
Guardado en:
Autor principal: | |
---|---|
Otros Autores: | |
Formato: | Tesis de grado publishedVersion |
Lenguaje: | Español |
Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2013
|
Materias: | |
Acceso en línea: | https://hdl.handle.net/20.500.12110/seminario_nCOM000462_DelgadilloCardenas |
Aporte de: |
id |
seminario:seminario_nCOM000462_DelgadilloCardenas |
---|---|
record_format |
dspace |
spelling |
seminario:seminario_nCOM000462_DelgadilloCardenas2023-09-12T13:13:23Z Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia Models and algorithms for communication network design survivability requirements Delgadillo Cárdenas, Remberto Emanuel Loiseau, Irene REDES SUPERVIVIENTES P-CICLOS OPTIMIZACION COMBINATORIA MODELOS DE PROPAGACION LINEAL ENTERA HEURISTICAS SURVIVABLE NETWORKS P-CYCLES COMBINATORIAL OPTIMIZATION INTEGER LINEAR- PROGRAMMING MODELS HEURISTICS Una red de comunicaciones se dice superviviente si puede continuar brindando servicio pese a la falla de alguno de sus componentes. Hacia fines de los noventa surgió el concepto de p-ciclos como alternativa prometedora a las tecnologías existentes (malla y anillos) para el diseño de redes supervivientes. Las topologías basadas en p-ciclos combinan las mejores características de las mismas para asegurar la supervivencia: velocidad en la recuperación y poca capacidad redundante o sea menor costo. A partir de la necesidad de diseñar redes basadas en p-ciclos de costo mínimo, surgieron varios problemas de optimización combinatoria. Uno de ellos es el Spare Capacity Allocation problem (SCA). En este problema se tiene una red con demandas asociadas a cada enlace. Se debe determinar la disposición de la capacidad redundante mediante la ubicación de p-ciclos de forma que quede garantizada la recuperación de las comunicaciones ante la falla de alguno de sus enlaces. Un modelo simple de PLE para resolver este problema, requiere la enumeración de todos los ciclos del grafo para construir una solución óptima, lo cual puede hacer el problema intratable. Entonces a partir de este modelo se diseñaron heurísticas basadas en elegir a priori algunos ciclos prometedores. Por otro lado algunos autores propusieron modelos de PLE que no requieren la enumeración de los ciclos del grafo. Nosotros introducimos un nuevo modelo de programación entera para SCA que tampoco requiere la enumeración a priori de ciclos candidatos. Los resultados obtenidos luego de la experimentación muestran un mejor desempeño respecto a los modelos previos. También presentamos una heurística para SCA sin enumeración de ciclos basada en este modelo y en una heurística golosa propuesta por otros autores. Problem (SCA) is one of these. In this problem, there is a network with a discrete demand for each link. Spare capacity location has to be determined by means of placing p-cycles over the network, so that full restoration is possible in case of any link fails. A simple ILP model to solve this problem requires explicit enumeration of all simple cycles of the graph, turning this problem intractable. Based on this model, several heuristics were designed to select a priori candidate cycles. On the other hand, some authors have proposed ILP models that do not require enumeration of graph cycles. Here we propose a new integer linear programming model that does not require a priori candidate cycle enumeration to solve SCA. We achieved better results than previous models. We also present an heuristic without cycle enumeration for SCA, based on both this model and a greedy heuristic proposed by other authors. Fil: Delgadillo Cárdenas, Remberto Emanuel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2013-03-20 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado 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/seminario_nCOM000462_DelgadilloCardenas |
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 SUPERVIVIENTES P-CICLOS OPTIMIZACION COMBINATORIA MODELOS DE PROPAGACION LINEAL ENTERA HEURISTICAS SURVIVABLE NETWORKS P-CYCLES COMBINATORIAL OPTIMIZATION INTEGER LINEAR- PROGRAMMING MODELS HEURISTICS |
spellingShingle |
REDES SUPERVIVIENTES P-CICLOS OPTIMIZACION COMBINATORIA MODELOS DE PROPAGACION LINEAL ENTERA HEURISTICAS SURVIVABLE NETWORKS P-CYCLES COMBINATORIAL OPTIMIZATION INTEGER LINEAR- PROGRAMMING MODELS HEURISTICS Delgadillo Cárdenas, Remberto Emanuel Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
topic_facet |
REDES SUPERVIVIENTES P-CICLOS OPTIMIZACION COMBINATORIA MODELOS DE PROPAGACION LINEAL ENTERA HEURISTICAS SURVIVABLE NETWORKS P-CYCLES COMBINATORIAL OPTIMIZATION INTEGER LINEAR- PROGRAMMING MODELS HEURISTICS |
description |
Una red de comunicaciones se dice superviviente si puede continuar brindando servicio pese a la falla de alguno de sus componentes. Hacia fines de los noventa surgió el concepto de p-ciclos como alternativa prometedora a las tecnologías existentes (malla y anillos) para el diseño de redes supervivientes. Las topologías basadas en p-ciclos combinan las mejores características de las mismas para asegurar la supervivencia: velocidad en la recuperación y poca capacidad redundante o sea menor costo. A partir de la necesidad de diseñar redes basadas en p-ciclos de costo mínimo, surgieron varios problemas de optimización combinatoria. Uno de ellos es el Spare Capacity Allocation problem (SCA). En este problema se tiene una red con demandas asociadas a cada enlace. Se debe determinar la disposición de la capacidad redundante mediante la ubicación de p-ciclos de forma que quede garantizada la recuperación de las comunicaciones ante la falla de alguno de sus enlaces. Un modelo simple de PLE para resolver este problema, requiere la enumeración de todos los ciclos del grafo para construir una solución óptima, lo cual puede hacer el problema intratable. Entonces a partir de este modelo se diseñaron heurísticas basadas en elegir a priori algunos ciclos prometedores. Por otro lado algunos autores propusieron modelos de PLE que no requieren la enumeración de los ciclos del grafo. Nosotros introducimos un nuevo modelo de programación entera para SCA que tampoco requiere la enumeración a priori de ciclos candidatos. Los resultados obtenidos luego de la experimentación muestran un mejor desempeño respecto a los modelos previos. También presentamos una heurística para SCA sin enumeración de ciclos basada en este modelo y en una heurística golosa propuesta por otros autores. |
author2 |
Loiseau, Irene |
author_facet |
Loiseau, Irene Delgadillo Cárdenas, Remberto Emanuel |
format |
Tesis de grado Tesis de grado publishedVersion |
author |
Delgadillo Cárdenas, Remberto Emanuel |
author_sort |
Delgadillo Cárdenas, Remberto Emanuel |
title |
Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
title_short |
Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
title_full |
Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
title_fullStr |
Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
title_full_unstemmed |
Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
title_sort |
modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia |
publisher |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
publishDate |
2013 |
url |
https://hdl.handle.net/20.500.12110/seminario_nCOM000462_DelgadilloCardenas |
work_keys_str_mv |
AT delgadillocardenasrembertoemanuel modelosyalgoritmosparadisenoderedesdecomunicacionesconrequisitosdesupervivencia AT delgadillocardenasrembertoemanuel modelsandalgorithmsforcommunicationnetworkdesignsurvivabilityrequirements |
_version_ |
1782031588129767424 |