Modelos y algoritmos para diseño de redes de comunicaciones con requisitos de supervivencia

Mostrar todas las versiones(2)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Delgadillo Cárdenas, Remberto Emanuel
Otros Autores: Loiseau, Irene
Formato: Tesis de grado publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2013
Materias:
REDES SUPERVIVIENTES
P-CICLOS
OPTIMIZACION COMBINATORIA
MODELOS DE PROPAGACION LINEAL ENTERA
HEURISTICAS
SURVIVABLE NETWORKS
P-CYCLES
COMBINATORIAL OPTIMIZATION
INTEGER LINEAR- PROGRAMMING MODELS
HEURISTICS
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000462_DelgadilloCardenas
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
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

Ejemplares similares