Topological optimization of a reliable communication network

Research output: Contribution to journalArticle

82 Citations (Scopus)

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 languageEnglish
Pages (from-to)225-233
Number of pages9
JournalIEEE Transactions on Reliability
Volume47
Issue number3 PART 1
DOIs
Publication statusPublished - 1998 Dec 1

Fingerprint

Telecommunication networks
Costs
Network performance
Computational complexity
Genetic algorithms
Topology

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering

Cite this

@article{7e1b7b080b6a4b73aa796ca978dbe1be,
title = "Topological optimization of a reliable communication network",
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.",
author = "Cheng, {Sheng Tzong}",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/24.740489",
language = "English",
volume = "47",
pages = "225--233",
journal = "IEEE Transactions on Reliability",
issn = "0018-9529",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3 PART 1",

}

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 journalArticle

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 -