Evaluating Communication-Network Reliability with Heterogeneous Link-Capacities Using Subset Enumeration
Volume 2, Number 1, January 2006 - Paper 1 - pp. 3 - 17
SIETENG SOH1, KOK YONG LIM and SURESH RAI21Department of Computing, Curtin University of Technology, Perth, Western Australia
2Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, LA, USA
(Received on March 1, 2005)
This paper proposes an improved algorithm to compute the reliability of a communication-network having heterogeneous link capacities. The reliability measure, capacity related reliability (CRR), is a generalization of a two-terminal reliability. A subset-cut-technique (SCT ) obtains CRR in two steps. First, SCT generates non-redundant subset-cut (SC) of the evaluated network. Second, the technique uses a sum-of-disjoint product algorithm to compute CRR from the generated SC. The computational complexity of SCT depends on the total number of subsets generated, the total number of internal (external) redundant SC generated and removed, and the total number of cuts in the network that are used to generate SC. The SCT generates too many subsets and internal (external)-redundant SC. In this paper, we propose a new subset cut enumeration (SCE) technique, which significantly reduces the total number of enumerated subsets and the total number of internal-redundant SC. Hence, the non-redundant SC are generated more efficiently. Examples are given to illustrate the technique, and the time complexity of our SCE is also described. Our method has been implemented in C and results show that SCE performs better than SCT.
Click here to download the paper.
Please note : You will need Adobe Acrobat viewer to view the full articles.