Open access peer-reviewed chapter

Obtaining and Using Cumulative Bounds of Network Reliability

By Alexey S. Rodionov and Denis A. Migov

Submitted: December 8th 2016Reviewed: November 3rd 2017Published: December 20th 2017

DOI: 10.5772/intechopen.72182

Downloaded: 233

Abstract

In this chapter, we study the task of obtaining and using the exact cumulative bounds of various network reliability indices. A network is modeled by a non-directed random graph with reliable nodes and unreliable edges that fail independently. The approach based on cumulative updating of the network reliability bounds was introduced by Won and Karray in 2010. Using this method, we can find out whether the network is reliable enough with respect to a given threshold. The cumulative updating continues until either the lower reliability bound becomes greater than the threshold or the threshold becomes greater than the upper reliability bound. In the first case, we decide that a network is reliable enough; in the second case, we decide that a network is unreliable. We show how to speed up cumulative bounds obtaining by using partial sums and how to update bounds when applying different methods of reduction and decomposition. Various reliability indices are considered: k-terminal probabilistic connectivity, diameter constrained reliability, average pairwise connectivity, and the expected size of a subnetwork that contains a special node. Expected values can be used for unambiguous decision-making about network reliability, development of evolutionary algorithms for network topology optimization, and obtaining approximate reliability values.

Keywords

  • network reliability
  • factoring method
  • network connectivity
  • random graph
  • diameter constraint
  • probabilistic connectivity
  • pairwise connectivity
  • network topology optimization
  • estimation
  • cumulative updating

1. Introduction

The network reliability analysis is one of the primary tasks in the course of the network topology design and optimization. Usually, random graphs are used when modeling networks with unreliable elements [17]; therefore, the network reliability is defined as a connectivity measure in a random graph. There are many reliability indices of networks, for example, probabilistic connectivity [4], average pairwise reliability [5, 6], and diameter constrained reliability [7].

The most widespread network reliability index is the probabilistic connectivity of the corresponding random graph. Depending on the number of terminals (selected nodes that must be connected), there are three types of this measure such as two-terminal, all-terminal (ATR) and k-terminal reliabilities. The average pairwise reliability (APR) describes the network reliability from the point of connection between every two nodes, while a network may be still disconnected. The reliability of a network with a diameter constraint (DCR) is defined as the probability of each pair of nodes connectivity by paths that travel through a limited number of communication channels. This index is more useful, especially for P2P networks [8], wavelength division multiplexing networks, wireless sensor networks, and so on.

Another reliability index we consider in this chapter is the mathematical expectation of the size of a connected subgraph that contains a special node (MENC) [2], which describes the quality of monitoring area coverage.

Despite the fact that problems of exact reliability computations are NP-hard [9, 10], it is possible to conduct the exact calculation for networks of practical interest dimension, taking into account some special features of network topologies. For large-scale networks, various methods of reliability evaluation are widely used [11, 12]. Won and Karray suggested the cumulative updating of reliability bounds for uniqueness of decision on network feasibility [13]. Originally, this approach was presented for ATR. In this chapter, we present our results on cumulative updating of other reliability indices, and some improvements for ATR bounds cumulative updating. In addition, the main ideas of constructing the cumulative bounds for random graph characteristics are discussed along with examples of their usage in obtaining better evaluation of reliability indices and improving bionic optimization algorithms.

2. The basic notations

We simulate a network with perfectly reliable nodes and unreliable links by an undirected random graph G = (V,E) with given presence probabilities 0 ≤ ei ≤ 1 of the edges. The notations which are used in this chapter are given below. Most of them coincide with the notations from [14].

  1. G—Undirected probabilistic network;

  2. V—Set of n nodes;

  3. E—Set of m edges;

  4. ei; eij – i-th edge or edge that connects i-th and j-th nodes, depending on context;

  5. pj – Operating probability of j-th edge;

  6. wi – Weight of node i, WT = (w1,…,wn);

  7. W(G) Total weight of nodes of G;

  8. R(G) All-terminal reliability of G, that is, probability that every two nodes are connected;

  9. K—Set of terminal nodes;

  10. RKdG—Diameter constrained reliability of G, that is, the probability that every two nodes from K are connected by a path that travel through not more than d edges;

  11. LB, UB—Lower and upper bounds of G reliability. In case of ATR, we use the original notation form [13]: RL, RU;

  12. R0—Predefined threshold for the network reliability value;

  13. N(G) (M(G))Mathematical expectation of the number of disconnected (or connected) pairs of nodes in G;

  14. CS(G; s)Mathematical expectation of a number of nodes in a connected subgraph that contains a node s; if s = 1, then CS(G);

  15. R¯Average pairwise reliability of G;

  16. C—Edge chain composed of edges e1,…,ek;

  17. G/C (G/e)Network G with a contracted chain C (edge e);

  18. G\C (G\e)Network G without chain C (edge e); and

  19. Ge—Network G with an absolutely reliable edge e;

3. Factoring method and cumulative updating of network reliability bounds

The most common exact method for calculating various network reliability measures is the factoring method. According to this method, we divide the probability space, which consists of all particular network realizations, into two sets based on the presence or absence of a network element. Further on we refer to such a network element as a factored element, or a pivot element. As a result, for a given network G and a factored element e, we will obtain the two networks: Ge, where e is absolutely reliable, and G\e, where e is absolutely unreliable, so we could remove it. The probability of Geis equal to the pivot element reliability, and the probability of G\e is equal to the pivot element failure probability. For a reliability index Rel of the initial network, the following expression holds (the total probability law):

RelG=peRelGe+1peRelG\eE1

Then the obtained networks are subject to the same factoring procedure. Recursions continue until either an unreliable network is obtained (0 is returned) or an absolutely reliable network is obtained (1 is returned). For ATR (Figure 1), expression (1) turns to:

RG=peRG/e+1peRG\e.E2

Figure 1.

The factoring method.

We can speed up the factoring process by calculating the intermediate networks reliabilities directly, that is, without further factorization. For ATR calculation, the five-vertex graph reliability formula can be used [13]. Another way to accelerate the reliability computing by using various reduction [4] and decomposition [17] methods, such as serial-parallel transformation on each recursive call of the factoring procedure, biconnected decomposition, and other methods.

The idea of the cumulative updating method is an incremental updating of exact lower (LB) and upper (UB) reliability bounds and comparing them with a given reliability threshold R0. If LB>R0, then the network is reliable. If UB<R0, then the network is unreliable. The LB must necessarily be non-decreasing, and the UB must necessarily be non-increasing. Another obligatory condition is the equality of LB, UB at the last step and exact reliability value R. One possible way of bounds updating is the usage of the factoring method. When a final graph or a disconnected graph is obtained, we can update bounds [13].

As a rule, any algorithm of calculation of mathematical expectation for a non-negative function μ of a random graph G practically comes to summarizing non-negative values. According to the definition of mathematical expectation in the discrete case [14]:

EμG=HΓPHμH,E3

where Γ is a set of all possible final realizations of G that are obtained during factorization.

If some realizations Γ0are obtained along with their probabilities, and a function μ is obtained for all these realizations, then the LB is greater or equal to the corresponding partial sum.

Now let us assume that for μ, its possible minimal μmand maximal μMvalues are known. In this case, we easily obtain the following bounds:

LB=HΓ0PHμH+μm1HΓ0PH;UB=HΓ0PHμH+μM1HΓ0PH.E4

Finally, both bounds will obviously come to an exact value.

From (4), we easily obtain the equations for improving bounds when the new (i-th) realization Hiis obtained and μHiis calculated:

LBi=LBi1+PHiμHiμm;UBi=UBi1PHiμMμH.E5

For ATR, μm=0and μM=1, so we arrive to the equations presented by Won and Karray in [13], while for MENC μm=1and μM=n, where n is a total number of nodes in a graph. Initial values of bounds are equal to these values.

4. Improvements for ATR bounds cumulative updating

4.1. The chain branching

Our methods named chain branching (CB) and chain reduction (CR) [15] could be used [16] .as a basis for two kinds of the ATR bound updating (UAB) algorithms named UAB based on CB (UAB_CB), and UAB based on CR (UAB_CR). These methods can be used if a network contains a chain, that is, a sequence of adjacent two-degree nodes. The CB reduces the calculation of ATR for calculating the ATRs of networks obtained from G by removing a pivot chain, or removing it and contracting its terminal nodes, while CR reduces it for calculating the ATR of the network GR, in which, this chain is substituted by a single edge. Let a chain C consist of k edges, its terminal nodes are s and t, and let an edge esthas a reliability pst, then [16]

RG=i=1kpi+psti=1k1pijipjRG/C+1psti=1k1pijipjRG\C.E6

The best choice is the usage of the longest chain as a pivot. However, it requires finding of all the chains. We may accelerate the calculation by choosing a chain (or an edge) incidental to a node with a minimal degree for obtaining a new chain.

4.2. The usage of Cutnodes

Let a network G have a cutnode u that divides G into two subnetworks G1and G2, therefore, RG=RG1RG2. RL1and RU1are lower and upper bounds for RG1, respectively. Like wise, RL2and RU2are the lower and upper bounds for RG2, respectively. Then RL1RL2RGRU1RU2.

Let us estimate the ATR of subnetworks G1and G2in turn starting from G1. While estimating the ATR of G1, we have no information about the ATR of G2, thus RL2=0and RU2=1, and RL for R(G) is 0, while RU for R(G) is RUG1. After some steps of estimating RG1, we switch to estimating RL2and RU2, thus improving RL and RU for G, and so on. Therefore, we calculate the bounds for RG1and RG2separately (possibly in parallel). Now let us continue with applying this scheme to calculating the bounds for RG1and RG2by the factoring method.

Similar to [15], we suppose that some networks H1, H1, …, HIare obtained from G1, and networks K1, K2,,KJfrom G2by factorization (1). Let us denote xi=PHi, yi=RHi, 1 ≤ i ≤ I, and si=PKi, ti=RKi, 1 ≤ i ≤ J. Then [16]:

RG1=i=1Ixiyi=1i=1Ixi1yi;RG2=i=1Jsiti=1i=1Jsi1ti.E7

Statement 1 For all a,b such that 1 ≤ a ≤ I, 1 ≤ b ≤ J, the following inequalities hold:

i=1axiyii=1bsitiRG1i=1axi1yi1i=1bsi1ti.E8

Proof of the statement can be found in [16], as well as the algorithm with the use of cutnodes (UAB_C).

4.3. The usage of two-node cuts

Now let us describe the UAB modification that uses two-node cuts. Let the network G has a node cut u,v that divides it into two subnetworks G1and G2(Figure 2). For any network H that contains the nodes u and v we will denote a network that is obtained by contracting these nodes as H′.

Figure 2.

The network G with two-node cut and auxiliary networks.

For the first time, the approach based on two-node cut was presented by Kevin Wood [17] in 1989. It describes how to perform the reliability-preserving triconnected decomposition of a network for calculating its k-terminal reliability. Later in 2006, we have introduced a general method which allows using an arbitrary node cut for calculating all-terminal reliability [18, 19]. This method makes possible to reduce the reliability calculation to the calculation of reliabilities of a group of networks each one with a smaller dimension. The total number of these networks is 2*BW, where BW is the Bell number and W is the number of nodes in the cut. A particular case of two-node cut along with numerical experiments to demonstrate the efficiency for the ATR calculation was presented in [16, 20], and in [21]—for the k-terminal reliability calculation. Despite the fact that the method from [17] presents a graph transformation for further factoring, and the method from [20] presents an expression for the network reliability, both of them practically lead to similar calculations of the same complexity. Another result was with the ATR calculation using special kind of node cuts [22]: the so-called longitudinal and cycle cuts. All the listed results, which we have obtained, are described in detail in [19]. Following is the corresponding Eq. [20] for the ATR without proof:

The following equation holds:

RG=RG1RG2uvRG2+RG2RG1uvRG1+RG1RG2.E9

The equation for three-node cut is sufficiently more complicated [18, 19]:

RG=12[RG1123RG2123+RG2132RG2123+RG1123RG2123+RG2132RG2123+RG1132RG2123+RG2123RG2132RG1RG2123+RG2132+RG2123RG2RG1123+RG1132+RG1123+RG1RG2]+RG1RG2123+RG1123RG2,E10

where nodes 1, 2, and 3 composes the threee-node cut, Gixyzis a graph that is obtained by merging y and z nodes in Gi, and Gixyzis obtained by merging x, y, and z nodes. The expression for four-node cut has also been obtained [19], but we do not present it due to its huge size.

However, our results on using an arbitrary node cut for all-terminal reliability calculation were published only in Russian [18, 19], and only the two-node cut case was presented in English [16, 20]. Maybe, this is the reason that these results are not so widely known, and therefore, the same ideas were proposed again by Juan Manuel Burgos and Franco Robledo Amoza [23, 24] in 2016. As we have done it in [1620], in [23, 24], the authors show how to calculate the all-terminal reliability of a network with a node cut via reliabilities of a group of smaller networks, but in a somewhat different way. As a result, Eqs. (910) were presented.

Let us describe how we can use expression (9) and update the ATR bounds separately for both subgraphs G1and G2(Figure 2) for obtaining the ATR bounds of the whole graph G.

Suppose that some networks H1,,HIare obtained from G1during the factoring process. If this factoring does not involve edges incidental to u or v, then parallel factoring in G1uvleads to obtain H1uv,,HIuv. Let us introduce the following denotations: xi=PHi, yi=RHi, xi=PHiuv, and yi=RHiuv, for 1 ≤ i ≤ I. As in both G1and G1uv, the factoring is executed by the same pivot edges, we have xi=xi. Obviously yiyibecause H1uvdiffers from Hiby the edge (u,v) that has reliability 1 in H1uv. Similarly, by the factoring in G2by edges that are not incidental to x or y, we obtain the networks K1,,Kj, and by the factoring in G2uv, we obtain K1,,KJ. Let us denote siPKi, ti=RKi, si=PKiuv, and ti=RKiuvfor 1 ≤ i ≤ J. Similar to the above case, we have si=si, titi. Let L=maxIJ, and let xi=yi=yi=0for I+1iL, si=ti=ti=0for J+1iL.

Let us obtain RL1,i,RU1,i,RL1,i,RU1,i,RL2,i,RU2,i,RL2,i,RU2,ifor1iL:

RLi1=j=1ixjyj,RUi1=1j=1ixj1yj,RLi1=j=1ixjyj,RUi1=1j=1ixj1yj,RLi2=j=1isjtj,RUi2=1j=1isj1tj,RLi2=j=1isjtj,RUi2=1j=1isj1tj.

As is shown in [13], these values are the upper and lower bounds for reliabilities of the corresponding networks; these bounds are exact for i = L. In the case i = 0, the lower bounds are 0 and the upper bounds are 1.

Note that RL1,iRL1,i,RU1,iRU1,i, as yiyi;RL2,iRL2,i, RU2,iRU2,i, as titi.

Now we obtain RLj, and RUjfor odd and even j separately. For j = 2i, 0 ≤ i ≤ L:

RU2i=RUi1RUi2+RUi1RUi2RUi1RUi2,RL2i=RLi1RLi2RLi2+RLi2RLi1RLi1+RLi1RLi2.E11

For j = 2i + 1,0 ≤ i ≤ L − 1:

RU2i+1=RUi+11RUi2+RUi+11RUi2RUi+11RUi2,RL2i+1=Li+11RLi2RLi2+RLi2RLi+11RLi+11+RLi+11RLi2.E12

Statement 2 For any 1 ≤ j ≤ 2 L, we have

RUj1RUjRGRLjRLj1.E13

If j = 2 L, then the second and the third inequalities become equalities. The proof of the statement can be found in [16], as well as the algorithm (UAB_2NC) with two-node cuts.

Note that both CB and CR can be used for speeding up the 2NC algorithm under the condition that the nodes u and v do not belong to a pivot chain. In the case of CR RUj1RUj1xj1p, RUj1RUj1xj1p, where p is a multiplier by which the reliability of a reduced network must be multiplied in CR [4].

4.4. Case studies

We have compared the algorithms presented with node cuts UAB_C and UAB_2NC to the algorithm CR from [13] that does not take possible cutnodes or two-node cuts into account. The results [16] of the comparison are presented in Tables 13. The CR was used while factoring for better performance, and the five-node networks were considered as simple ones. The PC with Intel Core Duo 2.93 GHz was used for testing.

NetworkR0AlgorithmTimeRecursions
G10.9UAB_CR39 s5,245,491
G10.9UAB_C<1 ms2504
G10.94UAB_CR34 s639,562
G10.94UAB_C<1 ms2643
G20.5UAB_CR2 s259,879
G20.5UAB_C60 ms4322
G20.901UAB_CR3 min 22 s24,765,569
G20.901UAB_C45 ms3233

Table 1.

Comparison of UAB_CR and UAB_C.

We have chosen the two networks G1and G2for testing UAB_C, and the two networks G3and G4for testing UAB_2NC.

The network G1consists of two 9-vertex complete graphs which are connected by a cutnode. Thus, it contains 17 nodes and 72 edges.

The network G2consists of two 5 × 5 lattices which are connected by a cutnode. As a cutnode, we choose the corner. The resulting network contains 49 nodes and 80 edges. Table 1 shows the results of numerical experiments.

The network G3(48 nodes and 79 edges) is composed of two 5 × 5 lattices which are connected by two nodes (Figure 3).

Figure 3.

The union of two 5 × 5 lattices by two nodes.

The network G4(22 nodes and 108 edges) is composed of two 11-vertex complete graphs which are connected by two nodes without edge connecting them. A similar network that is composed of two 5-vertex complete graphs is presented in Figure 4.

Figure 4.

The union of two complete five-node networks by two nodes without connecting edge.

The edges G1and G4are equally reliable with p = 0.5, while the edges G2and G3are equally reliable with p = 0.9. RG1=0.9307194, RG2=0.883248, RG3=0.903168801959, and RG4=0.982472649148.

Tables 2 and 3 present the results for G3and G4, respectively. The third row contains the results when the threshold value coincides with the exact reliability value. The results for the factoring algorithm with chain reduction are shown in the second column. The results for the UAB_2NC are shown in the third column.

R0UAB_CRUAB_2NC
Time (s)RecursionsTime (s)Recursions
0.52.2257,0840.088696
0.643.25,055,5530.1819,399
RG30.2827,180
0.92131,532,2930.088725
0.9222.5281,5650.088696

Table 2.

Results of the numerical experiments for the network G3.

R0UAB_CRUAB_2NC
Time (s)RecursionsTime (s)Recursions
0.20.1216,8140.110,963
0.3273,630,4940.8780,756
RG48,8805,358
0.99611314,878,0880.021747
0.9980.3645,374< 1 ms35

Table 3.

Results of the numerical experiments for the network G4.

As can be seen, the approach proposed has a great advantage. The efficiency of UAB as it is depends on the closeness of the threshold value R0to the reliability value R(G).

5. Cumulative updating of diameter constrained network reliability

For the DCR, expression (1) takes the following form:

RKdG=peRKdGe+1peRKdG\e.E14

We denote this method as a simple factoring method (SFM). Cancela and Petingi have proposed a modified factoring method for calculating DCR [7], which is much faster than the already described classical factoring method in the diameter constrained case (14). The Cancela and Petingi factoring method (CPFM) operates with a list of paths instead of graphs. For any terminals s, t, the list Pstdof all the paths with a limited length between s, t is generated. By Pdthe union of Pstdfor all the pairs of terminals is denoted. P(e) is composed of the paths of Pdwhich include the edge e. The list of CPFM arguments are given below [7]:

  • npst: the number of paths of length at most d between s and t in G;

  • linksp: the number of non-perfect edges (edges e such that p(e) < 1) in the path p, for every pPd.

  • feasiblep: this is a flag, which has the value False when the path is no longer feasible, that is, it includes an edge which failed; and True otherwise;

  • connectedst: this is a flag, which has the value True when s and t are connected by a perfect path of length at most d and False otherwise;

  • connectedPairs: the number of pairs of terminals which are connected by a perfect path of length at most d.

Pseudocode of the method proposed for the DCR bounds cumulative updating [27], which is based on CPFM, is presented below:

Input: G = (V;E), d, Pd, P(e), np(s; t), links(p), feasible(p), connected(s,t), connectedPairs, RL = 0, RU = 1, Pl = 1.

Function FACTO (np(s,t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)if RL > R0 or RU < R0 then

    e is an arbitrary edge: 0 < pe < 1    

    contractEdge (np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)    

    deleteEdge (np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)

end FACTO

Function contractEdge(np(s; t), links(p), feasible(p), connected(s,t),connectedPairs, Pr)Pr = Pr * pe

for each p = (s,..,t) in P(e) such that feasible(p) = true do

    links(p) = links(p) - 1    

    if connected(s,t) = false and links(p) = 0 then

                 connected(s,t) true

                 connectedPairs = connectedPairs + 1                 

                 if connectedPairs = |K|*(|K|-1)/2 then RL = RL + Pr

FACTO (np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)end contractEdge

Function deleteEdge(np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)Pr = Pr *(1-pe)

For each p = (s,…,t) in P(e) such that feasible(p) = true do

       feasible(p) = false

       np(s,t) = np(s,t) - 1

       if np(s,t) = 0 then RU = RU - Pr

FACTO (np(s,t), links(p), feasible(p), connected(s,t), connectedPairs, Pr)

end deleteEdge

For the speeding up of DCR calculation, it is possible to apply methods of reduction and decomposition. In our previous studies [2527], we have obtained such methods which can calculate the DCR faster. These methods are the analogue of the well-known series-parallel transformation for CPFM, and the pivot edge selection strategy. Also, we have obtained decomposition methods for calculating DCR in the case with two terminals. The methods obtained allow us to significantly reduce the number of recursive calls in CPFM and the complexity of DCR computation. In the above algorithm, we assume that the series-parallel reduction has been already performed and the pivot edge selection strategy is used.

Figure 5.

The Intellinet network.

Below we show how RL and RU are changing during the procedure proposed for the Intellinet network topology (Figure 5). The edge reliability is equal to 0.7 for each edge and the diameter value is equal to 12. The threshold value was equal to the exact DCR value, which was previously calculated. The calculation time was about 12 min. Experiments were performed on Intel Xeon E31240 3.3 GHz, 8 cores (Figure 6).

Figure 6.

The behavior of DCR bounds for the Intellinet network.

6. Special problems of updating reliability bounds

When special methods of graph reduction or decomposition are applied for the speeding up of calculations, the corresponding equations for updating the bounds must be used. Derivation of such equations for different functions μ(G) is based on taking into account all ”inner” changes of bounds that are concealed inside intermediate steps thus leading to final results of such a reduction or a decomposition. For example, when “branching by chain” [15] is applied, consequent factoring by edges of a chain is used for derivation, and each factoring may require a change of bounds.

Now let us turn to an example of a simple reduction, which is removing a dangling node. Let the graph G have some attached trees in its structure is shown in Figure 7.

Figure 7.

The graph with attached trees.

In the case of the ATR, we have the trivial equality RG=peRG\e, where e is the edge that connects the dangling node to the graph. As removing e with probability 1peleads to graph disconnection, the upper bound must be decreased by 1pe. The lower bound rests unchanged, but probabilities of all further realizations of G\e must be multiplied by pe. If there are some attached trees as shown in Figure 7, then the ATR of the graph G is equal to the ATR of this graph without all attached trees G0multiplied by the product of reliabilities of all the edges in these trees (let us denote it as Pr): RG=PrRG0. Thus, we continue with the graph G0, LB does not change, Pr must be included as a multiplier in probabilities of further realizations, and UB is reduced by probability of at least one edge of attached trees, that is, 1-Pr. If the reduction takes place at the initial step, then the upper bound starts from Pr.

The case of APR is not so simple. It is known that the task of obtaining this reliability index is equivalent to the one of obtaining mathematical expectation of the number of disconnected pairs of nodes in a random graph (EDP, see [28, 29]). Indeed, the following equations are valid:

R¯G=Cn2NGCn2;NG=Cn21R¯G.E15

From these equations, bounds are easily obtained:

LBAPR=Cn2UBEDPCn2,UBAPR=Cn2LBEDPCn2.E16

In [14], the following equation was derived with deleting the dangling node t that is incidental to the node s:

NG=NG0+1pstwtWG\est.E17

Here wtis the weight of the node t, initially 1. This weight shows an expected number of nodes that are merged in this node during the graph transformations: when using the factoring method, for example, one should remember the number of nodes that are merged if we assume that an edge between them is reliable. This weight is used for calculating the number of disconnected pairs of nodes when the graph is divided. Let W(G) be the total weight of the all nodes (initially, it is equal to the number of nodes) in G. G0 equals G with the only difference: the weight of the node s becomes equal to ws+pstwt.

From this, we obtain the following changes in the bounds: LBEDPis increased by 1pstwtWGwtand the UBEDPis decreased by pstwtWGwt. Contrary to case of the ATR, the result of removing attached trees highly depends on their structures, so dangling nodes must be removed one at a time. The only known exception with the derived equation is the case of the attached chain [6].

7. Using cumulative bounds for network reliability approximation

A simple approximation of the function μ(G) through its bounds is their average: μ(G) = (LB + UB)/2. However, the bounds tend to the exact solution with different rates. It seems to be reasonable assuming that cross of lines, obtained by the linear approximation of curves for LB and UB, may be a better approximation of μ(G). Let us have the bounds LBiand uBiat a step i > 0 and let μiGbe the corresponding approximation. The following proportion takes place:

μMUBi:LBiμm=UBiμ̂iG:μ̂iGLBi.E18

Hence, we have

μ̂iG=μMLBiμmUBiμMUBiμm+LBi.E19

Let us name this approximation as the approximation based on trends (ABT).

In the case of ATR, μm=0and LB=UB=μG, so

R̂iG=LBi1UBi+LBi,E20

while in the case of MENC, μm=1and μM=Cn2, so

CŜiG=Cn2LBiUBiCn2UBi1+LBi.E21

At the last step, LB=UB=μG, and from (19) we have that the proposed approximation also equals this value.

In Figures 810, the behavior of bounds for the EDP of 4x4 lattice (p = 0.7), for the MENC of the same lattice with c-node 1, and for the probability of the flow transmission (PFT) between two diagonal corners of this lattice with throughput of all edges 1 and the edges reliability uniformly distributed between 0.5 and 1, are presented, respectively.

Figure 8.

The behavior of bounds and approximations of EDP, the exact value is 20.915633.

Figure 9.

The behavior of bounds and approximations of MENC, the exact value is 12.562672.

Figure 10.

The behavior of bounds and approximations of PFT, the exact value is 0.196600.

As we can see the ABT has become better than the average of LB and UB from the first step or very fast.

We consider the practical usage of cumulative bounds and ABT in the following section.

8. Using cumulative bounds in network topology optimization

When optimizing the network topology by a certain criteria, a fitness function (FF) must be calculated for each alternative. In our case (k-terminal reliability, MENC, and APR) this means using NP-hard algorithms for its obtaining. Note that using approximate algorithms may lead to wrong decisions when structures with close values of FF are compared.

We propose using the cumulative bounds for decision-making about whether a new solution obtained by crossover or mutation deserves including into population.

The ideas are simple (without the loss of generality, we assume that a task is maximizing some function of an unreliable network):

  1. A wittingly inappropriate solution may be rejected before carrying out the exhaustive calculation of the corresponding FF. If the upper bound of the FF becomes smaller than the FF value of the worst solution in the current population, then this potential solution is rejected.

  2. At initial stages, a new solution may be included into the population based on the LB value. If it exceeds the FF value of the worst solution in the current population, then this new solution substitutes the worst one with assigning ABT as an approximate value of the FF.

Note that inevitable narrowing of bounds of FF in population leads to seldom updating of the population and to a better approximation of FF.

The experiments [30, 31] with network topology optimization by the criteria of the ATR and the DCR show that using the cumulative bounds allow the speeding up of calculations up to two times without loss of precision or with negligible loss (about 10−7).

9. Conclusion

The general approach of obtaining the cumulative bounds of random graph functions is presented. We have shown the possibility of computing the cumulative bounds by partial sums and updating the cumulative bounds in case of applying different methods of reduction and decomposition. For example, various indices of the network reliability were considered: the all-terminal reliability, the diameter constrained reliability, the average pairwise connectivity, and the expected size of a subnetwork that contains a special node. Also, we have described how the cumulative bounds approach can be used for network reliability evaluation and development of evolutionary algorithms for the network topology optimization. Future works can include methods of computing the cumulative bounds for other reliability indices along with methods of reduction and decomposition, further improvement of evolutionary algorithms for the network topology optimization, and parallel algorithms for the network reliability analysis.

Acknowledgments

This research was supported by the Russian Foundation for Basic Research under grants 17-07-00775, 17-47-540977.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Alexey S. Rodionov and Denis A. Migov (December 20th 2017). Obtaining and Using Cumulative Bounds of Network Reliability, System Reliability, Constantin Volosencu, IntechOpen, DOI: 10.5772/intechopen.72182. Available from:

Embed this chapter on your site Copy to clipboard

<iframe src="http://www.intechopen.com/embed/system-reliability/obtaining-and-using-cumulative-bounds-of-network-reliability" />

Embed this code snippet in the HTML of your website to show this chapter

chapter statistics

233total chapter downloads

1Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Spare Parts Forecasting Based on Reliability

By Nataša Kontrec and Stefan Panić

Related Book

First chapter

Microassembly Using Water Drop

By Taksehi Mizuno

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us