Publication

Abstract : This paper considers the design of reliable backbone networks under certain real-life constraints of cost and fault tolerance. The constraints are: keeping the cost of the links with in a predefined budget; and keeping the topology 1-FT (fault-tolerant) to 1-link failure. A network topology is said to be 1-FT iff every pair of nodes is reachable from all other nodes for 1 link failure. i.e., the graph remains connected. Formally, a graph G is 1-FT iff all the graphs, which have one less link than graph G, are connected. That is, 1-FT network can survive 1-link failure in the network. Therefore, the problem is to find a reliable network topology for a set of nodes whose total link cost is minimized subject to constraints that the backbone network can accommodate a 1-link failure under a given budget. The problem is NP-hard i.e. there exists no polynomial time algorithm to solve this problem. In this paper we have proposed an efficient method based on genetic algorithm to solve the problem. In our method we have represented a backbone layout by means of an upper triangular matrix by concatenating a row with its previous rows. The genetic operators iteratively attempt to find a more cost-effective and reliable network layout. Through the extensive simulation we show that our proposed genetic algorithmic approach can efficiently find a sub-optimal solution for most of the cases.