Computer Science ›› 2015, Vol. 42 ›› Issue (7): 122-124.doi: 10.11896/j.issn.1002-137X.2015.07.026

Previous Articles     Next Articles

Computing Approximate Network Reliability Based on Truncated Edge Expansion Diagram

SUN Yun ZHONG Fa-rong MO Yu-chang PAN Zhu-sheng   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Exact reliability of small-scale network can be calculated quickly,but for large-scale networks,reliability calculation is difficult.We proposed an approximate analysis algorithm for network reliability based on truncated edge expansion diagrams.The experiment results show that our algorithm can obtain the approximate network reliability based on generating smaller edge expansion diagrams and equivalent binary decision diagrams.

Key words: Edge expansion diagrams(EED),Network reliability,Truncation approximation

[1] Xing L D.An efficient binary-decision-diagram-based approach for network reliability and sensitivity analysis [J].IEEE Transactions on Systems,Man.and Cybernetics,Part A:Systems and Humans,2008,8(6):105-115
[2] Rai S,Aggarwal K K.An efficient method for reliability evaluation of a general network [J].IEEE Transactions on Reliability,1978,27(3):206-211
[3] Medhi D.A unified approach to network suevivability for teletraffic networks:models,algorithms and analysis[J].IEEE Transactions on Communications,1994,2(2/3/4):534-548
[4] Doverspike R.Trends in layered network management of ATM,SONET,and WDM technologies for network survivability and fault management[J].Journal of Network and Systems Management,1997,5(2):215-220
[5] Hui K P.Monte carlo networks reliability ranking estimation[J].IEEE Transactions on Reliability,2007,6(1):50-57
[6] Shier D R.Network reliability and algebraic structures[M].Oxford New York:Clarendon Press,1991
[7] Lin Y K.Spare routing reliability for a stochastic flow network through two minimal paths under budget constraint[J].IEEE Transactions on Reliability,2010,9(1):2-10
[8] Yeh W C.A simple minimal path method for estimating theweighted multi-commodity multistate unreliable networks reliability [J].Reliability Engineering and System Safety,2008,3(1):125-136
[9] Jane C C,Laih Y W.A dynamic bounding algorithm for approximating multi-state two-terminal reliability [J].European Journal of Operational Research,2010,5(3):625-637
[10] Shooman A M.Algorithms for network reliability and connection availability analysis [C]∥Electro/95 International Professional Program Proceedings.Boston,USA,1995:309-333
[11] Resnde L I P.Implementation of a factoring algorithm for reliability evaluation of undirected networks [J].IEEE Transactions on Reliability,1988,37(5):462-468
[12] Kuo S Y,Lu S K,Yeh F M.Determining terminal-pair network reliability based on edge expansion diagrams using OBDD [J].IEEE Transaction on Reliability,1999,48(3):234-246
[13] Bryant R E.Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams [J].ACM Computing Surveys,1992,4(3):293-318
[14] Friedman S J,Supowit K J.Finding the Optimal Variable Ordering for Binary Decision Diagrams [J].IEEE Transactions on Computers,1990,39(5):710-713
[15] Yeh W C,Lin Y C,Chung Y Y.Performance analysis of cellular automata Monte Carlo simulation for estimating network reliability [J].Expert Systems with Applications,2010,37(5):3537-3544
[16] Doguc O,Ramirez-Marquez J E.A generic method for estimating system reliability using Bayesian networks [J].Reliability Engineering and System Safety,2009,94(2):542-550

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!