Evaluating communication-network reliability with heterogeneous link-capacities using subset enumeration

Abstract

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 [7]) 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.