Italiano (Italian) English (Inglese)
Friday, 29 March 2024

Technical Reports

Technical Report Details
Authors:Marco Beccuti
Susanna Donatelli
Giuliana Franceschinis
Roberta Terruggia
Scientific Area:Dependability and Reliability
Performance Evaluation
Title:A new symbolic approach for network reliability analysis
Published on:TR-INF-2011-06-02-UNIPMN
Publisher:Computer Science Department, UPO
Year:2011
URL:http://www.di.unipmn.it...R-INF-2011-06-02-UNIPMN.pdf
Abstract:In this paper we propose a new approach for network reliability analysis based on Binary Decision Diagrams (BDDs). This approach can be summarized in three steps: first, we encode on a BDD the rules generating the minpaths of a specific graph and we use it to efficiently derive a BDD encoding the minpaths. Then, the minpath BDD is translated in the BDD encoding the connectivity function using an approach based on saturation strategy. Finally, we use the classical algorithm to compute the network reliability from BDD encoding the connectivity function and the probability of the edges to be connected. In this way, we are able to reduce the computation memory peak with respect to already developed approaches which build directly the BDD encoding the connectivity function. Finally, a set of experiments comparing, in terms of memory utilization and computation time, the proposed approach with respect to others approaches building directly a BDD encoding the connectivity function.