JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2015, Vol. 45 ›› Issue (2): 43-48.doi: 10.6040/j.issn.1672-3961.1.2014.011

Previous Articles     Next Articles

Performance comparison between breadth-first ordering and priority ordering in network reliability analysis

WU Huan, ZHONG Farong, MO Yuchang, PAN Zhusheng, ZENG Lingguo   

  1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Received:2014-03-26 Revised:2015-03-17 Online:2015-04-20 Published:2014-03-26

PDF (PC)

693

Abstract: In order to explore the correlation between edge ordering heuristics and characteristics of network structure, and to build the method of selecting heuristic relied on network structure, the performances of breadth-first search and priority ordering search were studied based on four kinds of regular network models. Some performance data, such as binary decision diagram size and runtime under two heuristics, were compared emphatically through the experiments. The experimental results showed that different ordering heuristics fitted different network structures: BFS was generally better than POS in the networks of Torus and Square, and POS was generally better than BFS in the De Bruijn and Nearest-neighbor networks. These results could provide reference for choosing the optimal or suboptimal edge ordering heuristic for the particular regular network.

Key words: breadth-first search, edge ordering heuristic, priority ordering search, regular networks, binary decision diagram

CLC Number: 

  • TB114
[1] SHELDON B AKERS. Binary decision diagrams[J]. IEEE Transactions on Computers, 1978, C-27(6):509-516.
[2] RANDAL E BRYANT. Symbolic boolean manipulation with ordered binary-decision diagrams[J]. ACM Computing Surveys, 1992, 24(3):293-318.
[3] RANDAL E BRYANT. Graph-based algorithms for boolean function manipulation[J]. IEEE Transactions on Computers, 1986, C-35(8):677-691.
[4] SIELING D, WEGEBER I. Reduction of OBDDs in linear time[J]. Information Processing Letters, 1993, 48(3):139-144.
[5] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco, USA: WH Freeman & Company, 1979:45-65.
[6] BOLLIG B, WEGENER I. Improving the variable ordering of OBDDs is NP-complete[J]. IEEE Transactions on Computers, 1996, 45(9):993-1002.
[7] STEVEN J FRIEDMAN, KENNETH J SUPOWIT. Finding the optimal variable ordering for binary decision diagrams[J]. IEEE Transactions on Computers, 1990, 39(5):710-713.
[8] BUTLER K M, ROSS D E, KAPUR R, et al. Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams[C]//Proceedings of the 28th ACM/IEEE Design Automation Conference. San Francisco, USA: ACM, 1991: 417-420.
[9] FUJITA M, FUJISAWA H, KAWATO N. Evaluation and improvements of boolean comparison method based on binary decision diagrams[C]//IEEE International Conference on Computer-Aided Design. Santa Clara, USA: IEEE, 1988:2-5.
[10] FUJITA M, MATSUNAGA Y, KAKUDA T. On variable ordering of binary decision diagrams for the application of multi-level logic synthesis[C]//Proceedings of the Conference on European Design Automation. Amsterdam, Holland: IEEE, 1991:50-54.
[11] MERCER M R, KAPUR R, ROSS D E. Functional approaches to generating orderings for efficient symbolic representation[C]//Proceedings of the 29th ACM/IEEE Design Automation Conference. Anaheim, USA: IEEE, 1992:624-627.
[12] BOUISSOU M. An ordering heuristic for building binary decision diagrams from fault-trees[C]//Reliability and Maintainability Symposium, Proceedings of the International Symposium on Product Quality and Integrity. Las Vegas, USA: IEEE, 1996:208-214.
[13] BOUISSOU M, BRUYERE F, RAUZY A. BDD based fault-tree processing: a comparison of variable ordering heuristics[C]//Proceedings of European Safety and Reliability Association Conference. Lisboa, Portuguesa: Elsevier, 1997.
[14] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. Computing all-terminal reliability of stochastic networks with binary decision diagrams[C]//Proceedings of the 11th International Symposium on Applied Stochastic Models and Data Analysis. Brest, France: ASMDA, 2005:1468-1474.
[15] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. K-terminal network reliability measures with binary decision diagrams[J]. IEEE Transactions on Reliability, 2007, 56(3):506-515.
[16] FU MIN YEH, SY YEN KUO. OBDD-based network reliability calculation[J]. Electronics Letters, 1997, 33(9):759-760.
[17] SY YEN KUO, SHYUE KUNG LU, FU MIN YEH. Determining terminal-pair network reliability based on edge expansion diagrams using OBDD[J]. IEEE Transactions on Reliability, 1999, 48(3):234-246.
[18] FU MIN YEH, SHYUE KUNG LU, SY YEN KUO. OBDD-based evaluation of k-terminal network reliability[J]. IEEE Transactions on Reliability, 2002, 51(4):443-451.
[19] 潘竹生, 莫毓昌, 赵建民. 优先级边排序策略及其性能分析[J]. 计算机科学, 2014, 41(8):81-84. PAN Zhusheng, MO Yuchang, ZHAO Jianmin. Priority edge ordering strategy and performance analysis[J]. Computer Science, 2014, 41(8):81-84.
[20] ADIGA N R, BLUMRICH M A, CHEN D, et al. Blue Gene/L torus interconnection network[J]. IBM Journal of Research and Development, 2005, 49(2/3):265-276.
[21] BARRENRTXEA G, BEFERULL LOZANO B, VETTERLI M. Lattice networks: capacity limits, optimal routing, and queueing behavior[J]. IEEE/ACM Transactions on Networking, 2006, 14(3):492-505.
[22] SRIDHAR M A, RAGHAVENDRA C S. Fault-tolerant networks based on the de bruijn graph[J]. IEEE Transactions on Computers, 1991, 40(10):1167-1174.
[1] LIU Xuan, PAN Zhusheng, ZHONG Farong, MO Yuchang, CHEN Zhongyu. Network simplification method for reliability analysis of infrastructure networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 27-32.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd