A Genetic Algorithm Based Heuristic for the Design of pCycle Networks

Abstract

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.