Genetic algorithm for solving Survivable Network Design Problem with Extending-Cycle-Based Protected Working Capacity Envelope

摘要

The study of protection and prevention against failures is an important problem in communication networks due to the growth of capacity demands for data transmission, especially in the Internet traffic. In this paper, we consider the Survivable Network Design Problem (SNDP) with Protected Working Capacity Envelope (PWCE) called capacity SNDP (ca-SNDP) in which a network topology is modeled by a weighted and undirected graph. The weight of each edge is maximum capacity bandwidth of this edge. A working network (Wn) and a backup network (Bn) will be constructed from this topology. Design survivable network with maximum total bandwith in Wn is objective of ca-SNDP. This paper proposes Extending Cycle (EC) model and genetic algorithm for solving ca-SNDP. We experimented and evaluated the effectiveness of proposed aprroach for solving survivable network design problem.