Abstract
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 & 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 linls. The genetic operators attempt to generate a more cost-eftective or reliable layout. Simulation shows that the proposed algorithm can efficiently find a sub-optimal solution for most cases.
| Original language | English |
|---|---|
| Pages (from-to) | 225-233 |
| Number of pages | 9 |
| Journal | IEEE Transactions on Reliability |
| Volume | 47 |
| Issue number | 3 PART 1 |
| DOIs | |
| Publication status | Published - 1998 Dec 1 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Safety, Risk, Reliability and Quality
- Electrical and Electronic Engineering
Cite this
}
Topological optimization of a reliable communication network. / Cheng, Sheng Tzong.
In: IEEE Transactions on Reliability, Vol. 47, No. 3 PART 1, 01.12.1998, p. 225-233.Research output: Contribution to journal › Article
TY - JOUR
T1 - Topological optimization of a reliable communication network
AU - Cheng, Sheng Tzong
PY - 1998/12/1
Y1 - 1998/12/1
N2 - 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 & 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 linls. The genetic operators attempt to generate a more cost-eftective or reliable layout. Simulation shows that the proposed algorithm can efficiently find a sub-optimal solution for most cases.
AB - 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 & 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 linls. The genetic operators attempt to generate a more cost-eftective or reliable layout. Simulation shows that the proposed algorithm can efficiently find a sub-optimal solution for most cases.
UR - http://www.scopus.com/inward/record.url?scp=0032156812&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032156812&partnerID=8YFLogxK
U2 - 10.1109/24.740489
DO - 10.1109/24.740489
M3 - Article
AN - SCOPUS:0032156812
VL - 47
SP - 225
EP - 233
JO - IEEE Transactions on Reliability
JF - IEEE Transactions on Reliability
SN - 0018-9529
IS - 3 PART 1
ER -