Analyzing network reliability with imperfect nodes using OBDD

Fu Min Yeh; Hung Yau Lin; Sy Yen Kuo

doi:10.1109/PRDC.2002.1185623

Analyzing network reliability with imperfect nodes using OBDD

Fu Min Yeh
, Hung Yau Lin
, Sy Yen Kuo

Chung-shan Institute of Science and Technology Taiwan
National Taiwan University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Scopus citations

Abstract

The nodes as well as the links may fail in a real network. Almost all the existing tree-based partitioning algorithms are inefficient in finding the disjoint paths in a large network even if all the nodes are perfect. The number of disjoint paths will increase dramatically if a network has imperfect nodes. In this paper, strategies based on edge expansion diagram using OBDD are proposed to efficiently evaluate the reliability of a network with imperfect nodes. The fixed sink algorithm is proposed to further speed up the process for k-terminal networks. The essential variable is also defined to help us identify the most critical part of the network. Our methods are better than previous numeric algorithms and have two significant results. First, it takes only about 65 seconds to identify the essential variable for a 2⁹⁹-path network on a SPARC 20 with 128 MB of memory. Second, the overhead due to considering imperfect nodes is as low as 0.2% in average for seven st3×n networks, where n = 13, 14,..., 19.

Original language	English
Title of host publication	Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002
Publisher	IEEE Computer Society
Pages	89-96
Number of pages	8
ISBN (Electronic)	0769518524
DOIs	https://doi.org/10.1109/PRDC.2002.1185623
State	Published - 2002
Externally published	Yes
Event	Pacific Rim International Symposium on Dependable Computing, PRDC 2002 - Tsukuba City, Ibaraki, Japan Duration: 16 12 2002 → 18 12 2002

Publication series

Name	Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC
Volume	2002-January
ISSN (Print)	1541-0110

Conference

Conference	Pacific Rim International Symposium on Dependable Computing, PRDC 2002
Country/Territory	Japan
City	Tsukuba City, Ibaraki
Period	16/12/02 → 18/12/02

Bibliographical note

Publisher Copyright:
© 2002 IEEE.

Keywords

Boolean functions
Computer networks
Councils
Data structures
Equations
Failure analysis
Merging
NP-hard problem
Partitioning algorithms
Production

Access to Document

10.1109/PRDC.2002.1185623

Cite this

Yeh, F. M., Lin, H. Y., & Kuo, S. Y. (2002). Analyzing network reliability with imperfect nodes using OBDD. In Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002 (pp. 89-96). Article 1185623 (Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC; Vol. 2002-January). IEEE Computer Society. https://doi.org/10.1109/PRDC.2002.1185623

@inproceedings{a7c413a088754d0eba4891d8f96fd725,

title = "Analyzing network reliability with imperfect nodes using OBDD",

abstract = "The nodes as well as the links may fail in a real network. Almost all the existing tree-based partitioning algorithms are inefficient in finding the disjoint paths in a large network even if all the nodes are perfect. The number of disjoint paths will increase dramatically if a network has imperfect nodes. In this paper, strategies based on edge expansion diagram using OBDD are proposed to efficiently evaluate the reliability of a network with imperfect nodes. The fixed sink algorithm is proposed to further speed up the process for k-terminal networks. The essential variable is also defined to help us identify the most critical part of the network. Our methods are better than previous numeric algorithms and have two significant results. First, it takes only about 65 seconds to identify the essential variable for a 299-path network on a SPARC 20 with 128 MB of memory. Second, the overhead due to considering imperfect nodes is as low as 0.2\% in average for seven st3{\texttimes}n networks, where n = 13, 14,..., 19.",

keywords = "Boolean functions, Computer networks, Councils, Data structures, Equations, Failure analysis, Merging, NP-hard problem, Partitioning algorithms, Production",

author = "Yeh, \{Fu Min\} and Lin, \{Hung Yau\} and Kuo, \{Sy Yen\}",

note = "Publisher Copyright: {\textcopyright} 2002 IEEE.; Pacific Rim International Symposium on Dependable Computing, PRDC 2002 ; Conference date: 16-12-2002 Through 18-12-2002",

year = "2002",

doi = "10.1109/PRDC.2002.1185623",

language = "英语",

series = "Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC",

publisher = "IEEE Computer Society",

pages = "89--96",

booktitle = "Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002",

address = "美国",

}

Yeh, FM, Lin, HY & Kuo, SY 2002, Analyzing network reliability with imperfect nodes using OBDD. in Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002., 1185623, Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC, vol. 2002-January, IEEE Computer Society, pp. 89-96, Pacific Rim International Symposium on Dependable Computing, PRDC 2002, Tsukuba City, Ibaraki, Japan, 16/12/02. https://doi.org/10.1109/PRDC.2002.1185623

Analyzing network reliability with imperfect nodes using OBDD. / Yeh, Fu Min; Lin, Hung Yau; Kuo, Sy Yen.
Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002. IEEE Computer Society, 2002. p. 89-96 1185623 (Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC; Vol. 2002-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Analyzing network reliability with imperfect nodes using OBDD

AU - Yeh, Fu Min

AU - Lin, Hung Yau

AU - Kuo, Sy Yen

PY - 2002

Y1 - 2002

N2 - The nodes as well as the links may fail in a real network. Almost all the existing tree-based partitioning algorithms are inefficient in finding the disjoint paths in a large network even if all the nodes are perfect. The number of disjoint paths will increase dramatically if a network has imperfect nodes. In this paper, strategies based on edge expansion diagram using OBDD are proposed to efficiently evaluate the reliability of a network with imperfect nodes. The fixed sink algorithm is proposed to further speed up the process for k-terminal networks. The essential variable is also defined to help us identify the most critical part of the network. Our methods are better than previous numeric algorithms and have two significant results. First, it takes only about 65 seconds to identify the essential variable for a 299-path network on a SPARC 20 with 128 MB of memory. Second, the overhead due to considering imperfect nodes is as low as 0.2% in average for seven st3×n networks, where n = 13, 14,..., 19.

AB - The nodes as well as the links may fail in a real network. Almost all the existing tree-based partitioning algorithms are inefficient in finding the disjoint paths in a large network even if all the nodes are perfect. The number of disjoint paths will increase dramatically if a network has imperfect nodes. In this paper, strategies based on edge expansion diagram using OBDD are proposed to efficiently evaluate the reliability of a network with imperfect nodes. The fixed sink algorithm is proposed to further speed up the process for k-terminal networks. The essential variable is also defined to help us identify the most critical part of the network. Our methods are better than previous numeric algorithms and have two significant results. First, it takes only about 65 seconds to identify the essential variable for a 299-path network on a SPARC 20 with 128 MB of memory. Second, the overhead due to considering imperfect nodes is as low as 0.2% in average for seven st3×n networks, where n = 13, 14,..., 19.

KW - Boolean functions

KW - Computer networks

KW - Councils

KW - Data structures

KW - Equations

KW - Failure analysis

KW - Merging

KW - NP-hard problem

KW - Partitioning algorithms

KW - Production

UR - https://www.scopus.com/pages/publications/34250374584

U2 - 10.1109/PRDC.2002.1185623

DO - 10.1109/PRDC.2002.1185623

M3 - 会议稿件

AN - SCOPUS:34250374584

T3 - Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing, PRDC

SP - 89

EP - 96

BT - Proceedings - 2002 Pacific Rim International Symposium on Dependable Computing, PRDC 2002

PB - IEEE Computer Society

T2 - Pacific Rim International Symposium on Dependable Computing, PRDC 2002

Y2 - 16 December 2002 through 18 December 2002

ER -

Analyzing network reliability with imperfect nodes using OBDD

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this