A Genetic Algorithm Based Heuristic for the Design of pCycle Networks

A telecommunication network is said survivable if it is still able to provide service after one of its components fails. Survivability is achieved by redirecting the data through other spans of the network where spare capacity was previously introduced. There are two important aspects to take into...

Descripción completa

Detalles Bibliográficos
Autores principales: Delgadillo, Remberto Emanuel, Loiseau, Irene
Formato: Objeto de conferencia Resumen
Lenguaje:Inglés
Publicado: 2015
Materias:
Ciencias Informáticas
survivable network design
Heuristic methods
Algorithms
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/59242
http://44jaiio.sadio.org.ar/sites/default/files/sio10-10.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-59242
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
survivable network design
Heuristic methods
Algorithms
spellingShingle Ciencias Informáticas
survivable network design
Heuristic methods
Algorithms
Delgadillo, Remberto Emanuel
Loiseau, Irene
A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
topic_facet Ciencias Informáticas
survivable network design
Heuristic methods
Algorithms
description A telecommunication network is said survivable if it is still able to provide service after one of its components fails. Survivability is achieved by redirecting the data through other spans of the network where spare capacity was previously introduced. There are two important aspects to take into account while providing survivability to the network: fast recovery and low cost. pCycles are structures that were introduced to design the spare capacity of optical networks providing quick restoration. Representing the network as a 2connected graph, a pCycle is a cycle composed of one preconfigured spare channel on each span (edge) it crosses. Each pCycle provides one protection channel (unit of demand) to each span it crosses and two protection channels to each span that is not in the cycle but its ending nodes are (straddling span). We deal here with the Spare Capacity Allocation (SCA) problem which requires protecting all working demands against any span failure with pCycles at minimum cost. We propose a greedy heuristic that builds a solution for this problem iteratively. At each step, a Genetic Algorithm builds a cycle trying to maximize the Actual Efficiency, which was defined in the literature for developing other heuristics for this problem. To achieve this, we propose to decode cycles from genes representing fundamental cycles of a basis of cycle space. We give two alternatives for fitness evaluation to treat disjoint cycles or closed walks with repeated nodes. Several computational experiments were performed and promising results were obtained.
format Objeto de conferencia
Resumen
author Delgadillo, Remberto Emanuel
Loiseau, Irene
author_facet Delgadillo, Remberto Emanuel
Loiseau, Irene
author_sort Delgadillo, Remberto Emanuel
title A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
title_short A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
title_full A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
title_fullStr A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
title_full_unstemmed A Genetic Algorithm Based Heuristic for the Design of pCycle Networks
title_sort genetic algorithm based heuristic for the design of pcycle networks
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/59242
http://44jaiio.sadio.org.ar/sites/default/files/sio10-10.pdf
work_keys_str_mv AT delgadillorembertoemanuel ageneticalgorithmbasedheuristicforthedesignofpcyclenetworks
AT loiseauirene ageneticalgorithmbasedheuristicforthedesignofpcyclenetworks
AT delgadillorembertoemanuel geneticalgorithmbasedheuristicforthedesignofpcyclenetworks
AT loiseauirene geneticalgorithmbasedheuristicforthedesignofpcyclenetworks
bdutipo_str Repositorios
_version_ 1764820478269063170

Ejemplares similares