Topological optimization of a reliable communication network

作者：Sheng-Tzong Cheng · 发表于：IEEE Transactions on Reliability · 年份：1998 · DOI：10.1109/24.740489 · 被引用次数：91 · 研究领域：VLSI and FPGA Design Techniques、Interconnection Networks and Systems

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.