Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007...

Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1


Andrea Bobbio, Roberta TerruggiaDipartimento di Informatica

Università del Piemonte Orientale, “A. Avogadro”15100 Alessandria (Italy)

[email protected] - http://www.mfn.unipmn.it/~bobbio

NETWORK RELIABILITY ANALYSIS VIA BDD

mailto:[email protected]


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.


Are these connections reliable ?


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;


Network reliabilityArcs and nodes are binary entities

We study: ConnectivityReliability

Qualitative analysis:Minimal pathsMinimal cuts

Quantitative analysis:Reliability and Unreliability functions


Topology versus reliability

Regular networks

Random networks

Scale free networks


Regular Networks

9

Random graph with 54 nodes Scale Free net with 54 nodes

Network Topology


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


Binary Decision Diagrams

BDD are binary trees for manipulating Boolean functions

Shannon decomposition function:

F = x1 ∧ Fx1=1 ∨ ¬ x1 ∧ Fx1=0

Probability function:


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



Minpath analysis




Contraction: edge perfectly reliable

Deletion: edge fails

G = ei T ∨ ¬ ei E



Bridge network:Pivotal decomposition (1)



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


e2

e5

e3e3

e5

e3

e1

e4 e4 e4

e1 e1 e1 e1 e1

e4 e4 e4 e4

1 0




Minpath analysis




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.


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 }


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


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


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


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



Minpath analysis





This algorithm generates the BDD directly via a recursive visit on the graph without explicitly deriving the boolean connectivity function orthe minpath.


Example: Bridge network

Arcs order:e4 ⇐ e3 ⇐ e5 ⇐ e2 ⇐ e1

1 0

e4

e3

e5 e5

e2 e2

e1


Tool implementation (1)

Type of algorithm:Pivotal decompositionMinpath analysisGraph visiting algorithm

Input graph:incidence matrix, adjacency list, formats provided by other tools


Tool implementation(2)

Elements fail:only arcs, only nodes both arcs and nodes.

Failure probabilities

Output:ReliabilityMinpathsMincuts


Example: Symmetric Network

Number of Nodes N=5

Degree of Nodes k=2


Example: Symmetric Network


Example: Directed Lattice Graph

Number of nodes =N X N


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.


Example: Random vs Scale Free


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

Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007...

Documents

Transcript of Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007 1Bobbio-Terruggia ENEA-Cresco; Roma - July 6, 2007...