Resumen:
El despliegue de enlaces de alta capacidad en redes de telecomunicaciones trajo como consecuencia la necesidad de que grandes redes deban operar sin ninguna falla. Debido al uso de esta clase de enlaces muy pocos transportan la información de gran cantidad de canales, que tradicionalmente dependían de muchos enlaces de menor capacidad. La posibilidad de que un número pequeño de fallas pudiera causar la caída de una red hizo que la creación de enlaces tolerantes a fallos se volviera un tema de mucha importancia. Una técnica para proveer este tipo de robustez a la red es formarla usando Self Healing Rings (SHR). En este trabajo proponemos una heurística para resolver el Bounded Cycle Cover Problem (BCCP), el cual consiste en encontrar un cubrimiento de un grafo 2-conexo con ciclos de costo mínimo y una cantidad acotada de ejes, que puede aplicarse a la creación de SHR tolerantes a fallos. La solución que proponemos es una variante de GRASP, cuya principal diferencia está en el mecanismo de selección de los ciclos candidatos. Mientras que GRASP lista los vecinos más ventajosos según la función greedy, y luego elige uno al azar, nuestra heurística selecciona vecinos al azar y se queda con el más ventajoso de ellos. Nuestro algoritmo, comparado con otras heurísticas que aproximan soluciones para el mismo problema consigue soluciones de mejor calidad, en algunos casos a costa de un mayor tiempo de cómputo.
Abstract:
An important consequence of the development of modern communications is a need for highly reliable networks that can operate for extended periods of time without any faults. Due to the deployment of high speed links most traffic that would have traditionally been sent through multiple low capacity links is now being sent on a few high capacity fiber optic channels, creating few single points of failure. Due to the possibility of massive disruption due to the failure of one of those links, research into fault tolerant networks and failover techniques became a priority. One of these techniques is to provide resilence to a network is using Self Healing Rings (SHR). In this document we propose a heuristic approach to solve the Bounded Cycle Cover Problem (BCCP), finding a minimum cost cycle cover for a 2-connected graph, with a limited number of hops per cycle, which can be used in the construction of fault tolerant networks composed of SHRs. Our proposed solution is a variant of GRASP, the main difference being the cycle selection mechanism: while GRASP obtains a list of possible neighbors based on a greedy funtions and chooses one at random, our heuristic selects a few neighbours at random and selects the best one according to the greedy function. Our algorithm, when compared with other heuristics used for obtaining solutions for the same problem, yields better quality solutions, at a higher computational cost.
Citación:
---------- APA ----------
Alvarez Capandeguy, Ernesto Adrián; Managó, María Fernanda. (2009). Nueva heurística para el problema de recubrimiento de grafos por ciclos acotados. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000389_AlvarezCapandeguyManago
---------- CHICAGO ----------
Alvarez Capandeguy, Ernesto Adrián; Managó, María Fernanda. "Nueva heurística para el problema de recubrimiento de grafos por ciclos acotados". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2009.https://hdl.handle.net/20.500.12110/seminario_nCOM000389_AlvarezCapandeguyManago
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000389_AlvarezCapandeguyManago.pdf
Distrubución geográfica
