Combination of Graph Reduction and Tie-set Techniques for Network Reliability Assessment

摘要

The reliability of the communication network is used as one of the quality of service factors defining the availability and the resilience of the operating networks. Many classical algorithms exist but most of them fail to be applied for real-time reliability assessment in complex networks where the calculation load is increased in function of the complexity. In the present work, a new algorithm is proposed to resolve the problem of the reliability evaluation for all kinds of networks (simple and complex). The algorithm is based on the combination of two classical reliability methods giving an efficient hybrid algorithm. Graph transformation method and tie sets methods are fused into multi stages algorithm. The network passes through many simplification layers based on series, parallel, and edge factoring graph transformation to transform a complex network into a simpler network. The simplified topology is then used as input for a classical algorithm; here the tie sets for the two-terminal reliability evaluation. A simulation is performed on a 11-node random complex network to compare the performances of the new algorithm to the existing algorithms. The results of the proposed algorithm are compared to those resulting from the use of tie sets algorithm in term of computing time. The implementation of the algorithms by MATLAB shows a noticeable improvement in the time for reliability calculation. The improvement depends on the selected commodity as source-destination pair. For example, the network under simulation shows an improvement in time computing compared to classical tie-set algorithm of 550% for the commodity (2)-(3). Also, there is no limitation on the size and complexity of the network.