Binary Decision Diagram based Reliability Evaluation
Manoj Singhal
Dr. Manoj Singhal, Associate Professor, Department of Information Technology, Greater Noida (U.P.), India.
Manuscript received on November 23, 2012. | Revised Manuscript received on December 05, 2012. | Manuscript published on December 30, 2012. | PP: 88-92 | Volume-2, Issue-2, December 2012. | Retrieval Number: B0847112212 /2012©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In this paper, I have considered a computer communication network which has perfect vertices and imperfect links. It means communication links may fail with known probability. I have found the reliability of the given network by using an exact method (inclusion-exclusion formula) and with binary decision diagram. I have found that the reliability obtained by both the method is same. Binary decision diagram based reliability evaluation involves three main steps. First ordering the given communication link by applying a heuristic approach. I have proposed a heuristic approach to generate the minimum size binary decision diagram. Second generate the reliability function with the help of min-paths from source to sink. At last apply Shannon’s decomposition to compute the reliability of the given network.
Keywords: Binary Decision Diagrams (BDD), Directed Acyclic Graph (DAG), Computer communication Network (CNN), Modified Binary Decision Diagram (MBDD), Ordered Binary Decision Diagram (OBDD), Dual Binary Decision Diagram (DBDD).