Topological optimization of a reliable communication network

This paper considers backbone network design under the constraints: minimal total link cost, and 1-FT (fault-tolerant to 1 link-failure). As networks become huge, the backbone layout design is essential to network performance and reliability. A 1-FT backbone can survive any 1-link failure. On the other hand, the total cost of the links in backbone layout is a practical concern. Therefore, the problem is to find a network topology for a set of nodes whose total link cost is minimized, subject to the condition that the backbone network can accommodate 1 link failure. The problem is NP-hard, and methods based on heuristic search are desired to obtain optimal or sub-optimal solutions. This paper proposes an efficient method based on genetic algorithms to solve the problem. The representation of a backbone layout is based on a list of ordered links. The genetic operators attempt to generate a more cost-effective or reliable layout. Simulation shows that the proposed algorithm can efficiently find a sub-optimal solution for most cases.