Network reliability is defined as the probability that all nodes, or a subset of the nodes, of the graph communicate through at least one path of working edges. The computational techniques proposed in the literature to solve the network reliability problem always assume that the network elements are statistically independent and can be classified into two main categories;
- approaches in which the desired network reliability measure is calculated directly (series-parallel reduction, pivotal decomposition using keystone components) and
- approaches in which all possibilities two specified nodes can communicate (or not communicate) with each other are first enumerated (path/cut set search) and then the reliability expression is evaluated, resorting to different techniques, like inclusion-exclusion method or sum of disjoint products
The Network Reliability Analyser (NRA) is based on Binary Decision Diagrams (BDD) which provides an efficient method to represent and manipulate Boolean functions and have been also exploited to model the connectivity of Boolean networks.
NRA computes the qualitative and quantitative reliability of a network according to two approaches:
the quantitative reliability is directly computed on BDD, then the list of the minpaths and of the mincuts is determined and
- the quantitative reliability is computed passing through a preliminary search of the minpath/mincuts, and then resorting to BDD. The efficiency and the limits of the tool have been investigated by means of a scalable benchmark which includes different network structures, namely Lattice, Scale Free and Random Graph networks. The tool is able to deal with networks composed of up to several hundreds of elements and is under evaluation on a network of a power distribution grid at regional level.The tool has been jointly developed by ENEA and Università del Piemonte Orientale.
For more information
A. Bobbio, R. Terruggia, E. Ciancamerla, M. Minichino
Evaluating network reliability versus topology by means of BDD algorithms
Università del Piemonte Orientale, Alessandria, Italy
Università di Torino, Torino, Italy
ENEA, Roma, Italy