Post on 23-May-2020
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 2
Andrea Bobbio, Roberta TerruggiaDipartimento di Informatica
Università del Piemonte Orientale, “A. Avogadro”15100 Alessandria (Italy)
bobbio@unipmn.it - http://www.mfn.unipmn.it/~bobbio
NETWORK RELIABILITY ANALYSIS VIA BDD
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 3
Networks in human society
Many technological, economical and social systems can be viewed in form of networks.
Networks are characterized by a set of nodes, the entities of the system, connected by arcs, the relations among them.
The connection between any two nodes can be achieved through a number of redundant paths.
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 4
Are these connections reliable ?
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 5
Assumptions
Arcs can be:• undirected• directed
Failures can be located in:• Arcs only;• Nodes only;• Both arcs and nodes.
Two special nodes are defined:• One source node s;• One sink node t;
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 6
Network reliabilityArcs and nodes are binary entities
We study: ConnectivityReliability
Qualitative analysis:Minimal pathsMinimal cuts
Quantitative analysis:Reliability and Unreliability functions
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 7
Topology versus reliability
Regular networks
Random networks
Scale free networks
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 8
Regular Networks
9
Random graph with 54 nodes Scale Free net with 54 nodes
Network Topology
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 10
We explore three network reliability algorithms:
Pivotal decomposition
Minpath analysis
Graph visiting algorithm
All the algorithms are based on the BDD representation of the connectivity function
Network reliability algorithms
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1111
Binary Decision Diagrams
BDD are binary trees for manipulating Boolean functions
Shannon decomposition function:
F = x1 ∧ Fx1=1 ∨ ¬ x1 ∧ Fx1=0
Probability function:
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 12
In the construction of the BDD the variables must be Ordered
Occasionally, the binary tree contains identical subtrees.
Reduction – Identical portions of BDD are folded
The result is the Reduced Ordered BDD
ROBDD
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 13
Pivotal decomposition
Minpath analysis
Graph visiting algorithm
Network reliability algorithms
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 14
Contraction: edge perfectly reliable
Deletion: edge fails
G = ei T ∨ ¬ ei E
Pivotal decomposition
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1515
Bridge network:Pivotal decomposition (1)
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1616
Bridge network:Pivotal decomposition (2)
1
1 0 0 1 0
0
1 0
0
1 0
0
1 0 01
0
1
e2
e1
e5
e4e3
0
e2 ⇐ e5 ⇐ e3 ⇐ e1 ⇐ e4
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1717
e2
e5
e3e3
e5
e3
e1
e4 e4 e4
e1 e1 e1 e1 e1
e4 e4 e4 e4
1 0
Bridge network:Pivotal decomposition (3)
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 18
Pivotal decomposition
Minpath analysis
Graph visiting algorithm
Network reliability algorithms
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 19
For a given graph G=(V,E) a path H is a subset of components, arcs and/or nodes, that guarantees the source O and sink Z to beconnected if all the components of this subset are functioning.
A path is minimal (minpath) if does not exist a subset of nodes in H that is also a path.
Path and minpath, Cut and mincut
For a given graph G=(V,E) a cut K is a subset of components, arcs and/or nodes, that disconnect the source O and sink Z if all thecomponents of this subset are failed.
A cut is minimal (mincut) if does not exist a subset of nodes in K that is also a cut.
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 20
Reliability Computation
TTheThe Reliability function of a network, can bedeterminated from the minpaths :
If (H1, H2,…, Hn) are the minpaths, then:
S = H1 ∪ H2 ∪ … ∪Hn
RS = Pr{S} = Pr{H1 ∪ H2 ∪ … ∪Hn }
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 21
Example: Bridge network
The point-to-point connectivity function can be expressed as:S1-4 = e1 e4 ∪ e2 e3 e4 ∪ e2 e5
List of mincut: H1 = { e1, e4} ; H2 = { e2, e3, e4 } ; H3 = { e2, e5}
List of minpath: K1 = { e1, e2} ; K2 = { e2, e4 } ; K3 = { e4, e5} ; K4 = { e1, e3, e5 }
The point-to-point reliability can be expressed as:R1-4 = Pr {S1-4 } = p1 p4 + p2 p3 p4 + p2 p5 – p1 p2 p3 p4
– p2 p3 p4 p5 – p1 p2 p4 p5 + p1 p2 p3 p4 p5
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 22
BDD are binary trees formanipulatingBoolean functions[Bryant et al. 1990]
Connectivity Function:S1-4 = e1 e4 ∪ e2 e3 e4 ∪ e2 e5
Example: Bridge BDD
Variables must be ordered.
Orderinge2 ⇐ e5 ⇐ e3 ⇐ e1 ⇐ e4
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 23
Reduction – Identical portions of BDD are folded
Occasionally, the binary tree contains identical subtrees.
The subtrees at the node e1 e4appear twice and can be folded.
The result is the Reduced Ordered BDD
Example: Bridge ROBDD
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 24
The computation of the probability of the BDD proceeds recursively by resorting to the Shannon decomposition.
Pr{F} = p1 Pr {F{x1=1} } + (1 - p1) Pr{ F{x1=0} }
= Pr{ F{x1=0} } + p1 ( Pr {F{x1=1} } - Pr{ F{x1=0} } )
Example: Bridge ROBDDProbability
computation
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 25
Pivotal decomposition
Minpath analysis
Graph visiting algorithm
Network reliability algorithms
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 2626
Graph visiting algorithm
This algorithm generates the BDD directly via a recursive visit on the graph without explicitly deriving the boolean connectivity function orthe minpath.
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 27
Example: Bridge network
Arcs order:e4 ⇐ e3 ⇐ e5 ⇐ e2 ⇐ e1
1 0
e4
e3
e5 e5
e2 e2
e1
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 28
Tool implementation (1)
Type of algorithm:Pivotal decompositionMinpath analysisGraph visiting algorithm
Input graph:incidence matrix, adjacency list, formats provided by other tools
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 29
Tool implementation(2)
Elements fail:only arcs, only nodes both arcs and nodes.
Failure probabilities
Output:ReliabilityMinpathsMincuts
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 30
Example: Symmetric Network
Number of Nodes N=5
Degree of Nodes k=2
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 31
Example: Symmetric Network
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 32
Example: Directed Lattice Graph
Number of nodes =N X N
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 33
Results
TABLE I – Benchmark on Directed Lattice Graph
Lattice# Lattice
nodes# Lattice
arcs# BDDnodes
#minpath
2 X 2 4 4 6 24 X 4 16 24 94 206 X 6 36 60 1034 2528 X 8 64 112 8384 3432
10 X 10 100 180 56338 48620
12 X 12 144 264 342038 N.A.
14 X 14 196 364 1933338 N.A.
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 34
Example: Random vs Scale Free
Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 35
Conclusion
The tool is under experimentation.Different network topologies:
RegularRandomScale free
Network reliability problem is NP-complete
For very large networks new algorithms are needed