New insights into breadth-first search edge ordering of regular networks for terminal-pair reliability analysis

Abstract

In the binary decision diagram–based terminal-pair network reliability analysis, the size of binary decision diagram heavily depends on the chosen edge ordering. From a theoretical point of view, finding the best ordering is an intractable task. Therefore, heuristics have been used to obtain reasonably good orderings. Among them, the breadth-first search heuristic typically outperforms other heuristics by generating smaller binary decision diagram and thus has been widely used for terminal-pair network reliability analysis. However, the performance of breadth-first search is still only vaguely understood; not much formal work has been done. In this work, we investigate the selection of high-performance root node of breadth-first search ordering for both lattice networks and de Bruijn networks. Empirical study shows that using the two terminal nodes in the terminal-pair network reliability analysis as the root node of the breadth-first search heuristic can have poor performance, and the high-performance root nodes are not randomly distributed. The relationship between the distribution pattern of high-performance root nodes and the rearrangement of successors is also studied. Given that there is often a variation of several orders of magnitude between the sizes of binary decision diagram built using different root nodes for the same network, the application of our results can dramatically reduce the running time and memory usage and make the binary decision diagram–based reliability analysis of large-scale regular networks possible.

Keywords

Network reliability binary decision diagram edge ordering heuristic breadth-first search lattice network de Bruijn network

Get full access to this article

View all access options for this article.

References

Selcuk

Yucemen

. Reliability of lifeline networks under seismic hazard. Reliab Eng Syst Safe 1999; 65(3): 213–227.

Ching

Hsu

. An efficient method for evaluating origin-destination connectivity reliability of real-world lifeline networks. Comput-Aided Civ Inf 2007; 22: 584–596.

Ahmad

. Simple enumeration of minimal cutsets of acyclic directed graph. IEEE T Reliab 1988; 37(5): 484–487.

Hariri

Raghavendra

. SYREL: a symbolic reliability algorithm based on path and cutset methods. IEEE T Comput 1987; C-36(10): 1224–1232.

Gadani

. System effectiveness evaluation using star and delta transformations. IEEE T Reliab 1981; R-30(1): 43–47.

Satyanarayana

Chang

. Network reliability and the factoring theorem. Networks 1983; 13: 107–120.

Wood

. A factoring algorithm using polygon-to-chain reductions for computing k-terminal network reliability. Networks 1985; 15: 173–190.

Akers

. Binary decision diagrams. IEEE T Comput 1978; C-27(6): 509–516.

Bryant

. Graph based algorithms for Boolean function manipulation. IEEE T Comput 1986; C-35(8): 677–691.

10.

Rauzy

. New algorithms for fault tree analysis. Reliab Eng Syst Safe 1993; 40: 203–211.

11.

Xing

Amari

. Reliability of phased-mission systems. In: Misra

(ed.) Handbook of performability engineering. London: Springer, 2008, ch 23, pp.349–368.

12.

. New insights into the BDD-based reliability analysis of phased-mission systems. IEEE T Reliab 2009; 58(4): 667–678.

13.

Xing

. An efficient binary decision diagrams based approach for network reliability and sensitivity analysis. IEEE T Syst Man Cy A 2008; 38(1): 105–115.

14.

Kuo

Yeh

. Determining terminal-pair network reliability based on edge expansion diagrams using OBDD. IEEE T Reliab 1999; 48(3): 234–246.

15.

Yeh

F-M

S-K

Kuo

S-Y

. OBDD-based evaluation of k-terminal network reliability. IEEE T Reliab 2002; R-51(4): 443–451.

16.

Sekine

Imai

. Computation of the network reliability (extended abstract). Technical report, Department of Information Science, University of Tokyo, Japan, Sept., 1998.

17.

Imai

Sekine

Imai

. Computational investigations of all terminal network reliability via BDDs. IEICE T Fund Electr 1999; E82-A(5): 714–721.

18.

Hardy

Lucet

Limnios

. K-terminal network reliability measures with binary decision diagrams. IEEE T Reliab 2007; 56(3): 506–515.

19.

Barrenetxea

Beferull-Lozano

Vetterli

. Lattice networks: capacity limits, optimal routing, and queueing behavior. IEEE/ACM T Netw 2006; 14(3): 492–505.

20.

D’Andrea

Dullerud

. Distributed control design for spatially interconnected systems. IEEE T Automat Contr 2003; 48(9): 1478–1495.

21.

Barrenetxea

Beferull-Lozano

Vetterli

. Lattice sensor networks: capacity limits, optimal routing and robustness to failures. In: IPSN2004, Berkeley, California, USA, 26–27 April 2004, pp.186–195. New York: IEEE Signal Processing Society.

22.

Pottie

Kaiser

. Wireless integrated network sensors. Commun ACM 2000; 43(5): 51–58.

23.

Sridhar

Raghavendra

. Fault-tolerant networks based on the de Bruijn graph. IEEE T Comput 1991; 40(10): 1167–1174.

24.

Bermond

J-C

Fraigniaud

. Broadcasting and gossiping in de Bruijn networks. SIAM J Comput 1994; 23(1): 212–225.

25.

Fraigniaud

Gauron

. D2B: a De Bruijn based content-addressable network. Theor Comput Sci 2006; 355(1): 65–79.

26.

Dutuit

Rauzy

Signoret

J-P

. Computing network reliability with Réséda and Aralia. In: ESREL96, 24–28 June 1996, pp.1947–1952. Crete, Greece: ESRA.

27.

Rauzy

. Some disturbing facts about depth first left most variable ordering heuristics for binary decision diagrams. Proc IMechE, Part O: J Risk and Reliability 2008; 222: 463–720.

28.

Watts

Strogatz

. Collective dynamics of “small-world” networks. Nature 1998; 393(6684): 440–442.

29.

Barabási

Bonabeau

. Scale-free networks. Sci Am 2003; 288(5): 60–69.

30.

Javanbarg

Scawthorn

Kiyono

. Reliability analysis of infrastructure networks using OBDD. In: ICOSSAR2009, Osaka, Japan, 13–17 Sept 2009, pp.100–107, New York: IASSAR.