Topological Design Using Genetic Algorithms

Introduction

We are currently living in an information era, where most people use devices with advanced multimedia applications to obtain and exchange information. These trends are creating a demand for flexible, scalable, and reliable transport networks with minimum Capital Expenditures (CAPEX) and Operational Expenditures (OPEX). Optical networks that employ Wavelength Division Multiplexing (WDM) are currently the first choice for transport networks. Wavelength division multiplexing is a technology that aggregates multiple wavelengths into a single optical fiber offering a transmission bandwidth of terabits per second. With such huge amount of traffic traversing a single optical fiber a link failure may lead to catastrophic consequences affecting critical applications from governmental agencies, banks or health services. Therefore, a network providing enough capacity to recover connections in case of failure is essential.

The node location is one of the first pieces of information that the network designer has, corresponding to the location of the central offices where the traffic is added and dropped. The first stage of the overall network design process is the topological design; at this stage the connections between the nodes are established. The network topological design should guarantee a reliable network, and this depends on which links are going to be implemented (Kerivin & Mahjoub, 2005). The traffic to be transported by the network is hard to forecast and is continuously changing (Klopfenstein, 2009). In practice, several traffic scenarios are defined and evaluated, then the lowest cost network that will remain feasible for the majority of the scenarios is implemented (Klopfenstein, 2009). Therefore, the utilization of methods to quickly design physical topologies ensuring the routing of the required traffic and guaranteeing the network survivability at minimum cost is crucial. In optical networks, the failure of multiple fibers at the same time is extremely rare (Ramamurthy et al., 2003). The majority of failures regard single-link failures. Thus, we consider that the network should be survivable against any single link failure. Hence, the underlying topology is a 2-connected graph (Jungnickel, 2008). The topological design of minimum cost 2-connected graphs, not allowing the use of parallel edges, is strongly NP-hard (Kerivin & Mahjoub, 2005; Garey & Johnson, 1979); thus Integer Linear Programming (ILP) models only lead to optimal solutions, within reasonable time and computational effort, for small networks. Consequently, heuristics are commonly used to search for near-optimal solutions.

A 2-connected graph is required to ensure survivability in optical networks, however it is not sufficient. In order to guarantee survivability, protection schemes have to be implemented. We focus on path dedicated protection, where a link disjoint backup path is used to protect each optical channel (Ramamurthy et al., 2003). In this scheme the backup path has dedicated resources that cannot be shared with others working and backup paths. When a working path link fails all the affected demands are switched to the respective dedicated backup path.

In this chapter, we address the problem of jointly designing the physical topology, ensuring survivability, and minimizing the network CAPEX of an opaque optical transport network (Bouillet et al., 2007). In order to deal with this problem we propose a genetic algorithm. As the convergence of the genetic algorithm depends on the used genetic operators, we analyze their impact on the quality of the obtained solutions. Two initial population generators, two selection methods, two crossover operators, and two population sizes are compared within the genetic algorithm. The performance of the proposed heuristic is evaluated using an ILP model. We use a simplified cost model to calculate the CAPEX of an optical network to obtain exact results that can be compared with the heuristic solutions. The computational results are obtained using the node location of nine real telecommunications networks.