Approximation of the Node-Pair Reliability of Data Communication Networks

Data communication networks are often analyzed for the estimation of their dependability and one of the most requirements is to calculate the reliability of the nodes. Since the time complexity of the reliability calculation algorithms is O(n²), this paper proposes a linear-time approximation technique to identify lower reliable node-pairs without calculation of the actual reliability of nodes. Since the reliability of a node-pair is directly and indirectly proportional to the total number of paths and the number of hops/path respectively, the proposed technique considers these two parameters for the approximation of the reliability. As an illustration and verification, the proposed technique has been applied to a network of 11 nodes and 19 links, and satisfactory results have been obtained.