Chapter 6
Unified Framework and Capacitated Network Reliability
In the design of communication networks, reliability has emerged as an important parameter due to the fact that failure of these networks affects its user adversely. The interest in the area of reliability evaluation is quite evident from numerous formulations of network reliability problems and articles appearing in the literature for the past couple of decades. This has resulted in the evaluation of various methodologies, techniques and algorithms to tackle these problems in an efficient and effective manner.
Briefly speaking, the two-terminal, k-terminal, and g-terminal reliability analysis techniques for general reliability structures include serial-reduction/parallel-combination, event-space enumeration, cutset/pathset unionizations, and pivotal decomposition using keystone components etcetera. Event-space enumeration is a sure-fire method but the enumerative efforts are excessive even for a small structure. An extensive work has been done for determining the network reliability measures, viz., two-, g-, and k-terminal reliability. This chapter provides a minimal cutset based unified framework to evaluate 2-,g-, and k-terminal reliability using MVI-SDP approach (Mishra & Chaturvedi, 2009).
6.1 The Unified Framework
In earlier Chapters, the methodology and usefulness of the MVI-SDP approach have been demonstrated to obtain reliability expression and its numerical value in a straight forward manner. However, the expression and inference rendered by the technique depends on the type of input provided to any SDP algorithm. Basically, the SDP technique is used to provide disjoint form of the terms (success or failure) appearing on its input. This is one of the biggest advantages that have been exploited to propose a common framework by using a suitable SDP algorithm with a single algorithm of enumerating different types of terms (already described in Chapter 4 and 5) suitable for a desired reliability measure. Summarily, Figure 5.1 depicts the majority of the methodologies adopted for applying the SDP techniques.
Clearly, the key issues in applying the approach are network representation (simple the better), enumeration of all possibilities of connectivity among a specified sets of nodes (depending on the reliability measures, viz., 2-, k-, or g- terminal) and making these possibilities disjoint with each other to form the reliability expression. Although, from spanning trees, one can generate pathsets or k-trees (Rath & Soman, 1993), but for a given network, processing of a large number of spanning trees to obtain pathsets and k-trees is so time consuming that researchers resorted to several specific algorithms rather than a single one.
The idea of the unified approach is depicted in Figure 6.2, where a single algorithm provides all types of minimal cutsets, which are used to evaluate respective reliability measures using MVI-SDP techniques. Note that from the same framework 2-terminal capacitated reliability can also be obtained, which is discussed in next section of this Chapter.
Figure 6.1 A scheme for evaluating reliability measures using SDP approach.
Figure 6.2 An alternative scheme for evaluating network reliability measures using SDP approach.
6.2 Capacitated Reliability Measure: An Introduction
In earlier Chapters, it has been stated that a system can be modelled as a probabilistic graph G (V, E), which consists of a set of V nodes and a set E of links, directed or undirected depending upon the corresponding links being one-way (or two-way). Various measures for the reliability index for such networks have been proposed by (Colbourn, 1987). The most common quantitative index in reliability analysis of such system is ‘s-f reliability’. However, the assumption that the network can always carry the desired amount of information between (s, f) pairs of nodes whenever a connectivity exist (or the links capacities are large enough to sustain the transmission of any size) is unrealistic and economically unjustifiable in the design and analysis of such networks as the link capacity is a function of cost and definitely limited. Each link of the network can have different capacity and is required to transmit a specified amount of flow from source to the terminal node.
The reliability of such capacity constrained network can be defined as the probability that the network has capable of carrying at least, a minimum specified capacity, (Wmin), between (s, f) pair of nodes. This definition can also be extended to other flow networks such as power distribution network, transportation network or a water supply network. Such performance index is also referred as capacity related reliability (CRR) (Soh & Rai, 1991).
The efficient methodologies in vogue use a priori information of either minimal path sets or cutsets of the network. The CRR computation is accomplished in two steps, viz.,
Efficient approaches do exist for the second step to obtain the mutually disjoint terms; however, the first step is still in open area of research and has attracted much attention in the recent past. The main thrusts in these methods have been on the efficient enumeration of success (or failure) sub networks in terms of the nodes and branches of the network for a desired capacity of flow. From this information, these methods obtain disjoint sets of these terms by employing well-established Sum-of-Disjoint-Product (SDP) techniques thereafter. The greatest advantage of this approach is that the disjoint terms so obtained would have a one-to-one correspondence with the reliability (unreliability) expression.
As noted in earlier Chapters that in most practical system, the number of minimal cutsets is much smaller than the number of minimal pathsets. It would be beneficial to address the CRR evaluation based on minimal cutsets rather than minimal pathsets with regards to computational efforts and memory requirements. Additionally, it is easier to handle a single minimal cutset at a time rather than handle two or more pathsets at a time to form a composite path (CP). Therefore, this Chapter focuses to enumerate irredundant subsets of minimal cutsets (SCG) of a communication network having heterogeneous link capacities, each of which is capable of blocking a flow of specified value, Wmn, and is first step in CRR evaluation by using SDP techniques (Chaturvedi, 2007). The algorithm described in this Chapter generates the irredundant SCG that can be fed as input to any SDP based reliability evaluation algorithm discussed in earlier Chapters to obtain the CRR. The generation of such terms requires a priori knowledge of minimal cutsets arranged in order of increasing order of their flow blocking capacity and within the same value of blocking-capacity, a lexicographic ordering. The ordering scheme not only helps in reducing effort in enumerations but also help eliminates the internal/external redundancies through simple validity checks by proposing two equations. Besides, we describe a subset-generating scheme, starting from a certain order onwards to aid the generation of SCG process. This scheme is being used to generate next higher order subsets of a cut from the unqualified SCG, if any, to reduce the number of subsets enumerations.
The technique (Chaturvedi, 2007) explained in this Chapter is applied to several complex networks and a comparison with respect to the number of subsets generation, number of external/internal redundant subsets removal in obtaining irredundant SCG with recent algorithms are provided to show computational efforts and thus a better performance of the approach than the existing ones. Some of the definitions useful to understand the approach for flow networks for a specified Wmin are provided here under:
6.2.1 Some Related Definitions
6.2.1.1 Minimal Cutset and Subset Cut Group
Minimal cutset for a flow network is a set of links of the network, which would obstruct the (s, f) connectivity and would not allow any amount of flow from source to destination whereas the minimal subset cut group (SCG) is a set of links of the network that would allow (s, f) connectivity of the network on the removal of links contained in it but the sub-network will not be able to transmit a specified amount of flow, i.e., it would block the desired flow through the network despite the network being (s, f) connected.
6.2.1.2 External Redundant Subset Cut Group
A subset of a minimal cut is said to be external redundant SCG if has already been formed by some earlier minimal cutset (s) or its subset cut group.
6.2.1.3 Internal Redundant Subset Cut Group
A higher order subset of a minimal cutset is said to be internal redundant SCG if its lower order subsets would also capable of blocking a required amount of flow through the network.
6.2.1.4 Invalid Cut Set Cut Group
The SCG would be called as invalid one, if there exist some or no SCG of a minimal cutset that would be capable of obstructing the desired amount of flow through the network, those SCG would be called as invalid SCG.
6.2.1.5 Description of the Algorithm
The approach first constructs a cut-matrix from the minimal cut information from the minimal cutsets arranged in increasing order of their cut capacity. The number of rows of this matrix will be equal to the number of minimal cutsets and number of columns would be the total number of links present in the network under study. It then detects single-link SCG, if any, from this cut matrix. This single-link SCG is removed from further consideration as any supersets of single-link SCG will be a redundant SCG. Then, for remaining links contained in each cutset, it is determined that whether generation of subsets of the cut (SCG) is required? If so, then what order onwards to block the specified amount of flow, Wmin?
To answer the above questions, an enumeration scheme that enumerates a particular order of subsets from a given set is provided. And two simple equations, which operate on the cut-matrix to check the validity of a cutset (as SCG (as a whole) or it needs subsets enumerations and of what order onwards?) are devised. These two equations are further applied to validate the irredundant SCG, redundant SCG or invalid SCG. The end product of algorithm is irredundant SCG devoid of any redundancy check overheads by which most of the existing algorithm suffer. In the next section, entire approach has been presented with an example.
6.3 Algorithm Description
In the following section, we present some of the preliminaries forming the building blocks of the approach by utilizing the following information on the network system, viz., ‘s-f’ minimal cutsets, link-capacities, minimum specified carrying capacity of the network; and cut capacities and maximum carrying capacity of the network from the cut information. Let the cutset-matrix, be A and its cut-capacity vector (as a sum of each link capacity contained in a particular cut) for each cutset be, CA.
6.3.1 Equations: The idea
For a specified flow, Wmin, a minimal cut of the network may itself be a SCG or its subsets would form SCG. There could be three possibilities for a SCG i.e., (i) it can block the desired flow, Wmin or (ii) it can be a redundant one (external/internal) or (iii) it cannot block the flow at all (invalid). The equation to compute the capacity of the network on removal of some links contained in a SCG (or cutset as whole) with a capability of removing external redundancy is based on the following idea:
For any ith minimal cut set, ordered in their respective flow-capacity and lexicography, a SCG of this cutset would either keep the maximum carrying capacity of the network intact or it would decrease the capacity to a certain lower level less than the maximum carrying capacity of the network, i.e., to the current flow-capacity of the network, Ns, on removal of such links in SCG from the network can be computed by,
Where,
CX = CAj -fk ∀j ≤i
CAj = Capacity of jth element of CA
fk = Sum of capacities of links contained in kth SCG (or cut) of certain order.
Equation (6.1) not only provides the exact network flow capacity on removing a set of links from the network whose capacity-sum is in fk but also helps in identifying external or both external/internal redundant SCG. However, working on several examples, it does fail to locate the existence of SCG that would be only internally redundant.
The following equation solves the problem:
A SCG is said to be internally redundant, if any link contained in it has its,
The value of Δ provides the margin by which the network capacity can be improved through the reinsertions of link(s) from a SCG (mote that the SCG is nothing but link(s) taken out from the network under consideration). And if any reinsertion of link(s) of this set cannot improve the capacity of the network up to, Wmin, implying that this link(s) in this set is redundant and the SCG under consideration is an internally redundant SCG.
6.3.2 Is Cut itself a SCG or does it need its Subsets Enumeration?
Equations (6.1) and (6.2) are utilized to ascertain whether a cut itself is a SCG or its subsets would form SCG. Obviously, any ith minimal cut would produce a current network flow capacity, Ns, equal to zero occurring only at ith position in Equation (6.1). Thus, Δ = Wmin. Now, if no link in the cut has a capacity < Δ would imply that the cut itself is a SCG. However, if the cut has some link(s) capacities ≤ Δ, then there could be a certain sets of links of this cut, which are capable of blocking a flow of Wmin. Thus, subsets of this cut will have to be formed to determine those SCG.
Other possibilities, which will force to enumerate subsets of a cut, could be:
6.3.3 What Initial Order?
Once it is established that the subsets of a minimal cutset are to be formed, the next task is to determine from what order of subsets to be enumerated initially to reduce the number of enumerations and validity checks? The situation arises when a minimal cutset has some link(s) capacity ≤ Δ or situation (ii) as stated above. This is dealt with, in the following manner:
For an ith cut:
The number of links so determined would be the initial order of SCG to be enumerated, which would be checked for valid/invalid/redundant SCG. The remaining SCG, if any, are then carried over for next higher order SCG enumerations.
The following examples are used to explain the above points. Consider a network shown in Figure 6.3 with its minimal cutsets and cut capacities as given in Table 6.1. The link capacities are shown in brackets along with their respective link number. Note that the minimal cutsets are arranged in order of their capacity and lexicography.
Figure 6.3 Network of 6 Nodes and 11 Links with Cmax = 15 units.
Table 6.1 Minimal cutsets for the network of Figure 6.3.
| Minimal cutset | Cut capacity (Σ) |
| C1 = {4, 5, 6} C2 = {4, 8, 11} C3 = {1, 2} C4 = {9, 10, 11} C5 = {4, 7, 10, 11} C6 = {1, 3, 6} C7 = {2, 3, 4, 5} C8 = {5, 6, 7, 9} C9 = {7, 8, 9, 11} C10 = {5, 6, 8, 9, 10} C11 = {2, 3, 5, 7, 9} C12 = {1, 3, 5, 8, 11} C13 = {1, 3, 5, 7, 10, 11} Cl4 = {2, 3, 5, 8, 9, 10} |
15 18 19 20 20 23 25 25 28 33 35 36 38 43 |
Example 6.1: Consider the 3rd cut with its link capacities shown in brackets, {1 (10), 2(9)}, CA3 = 19. Let Wmin = 6. Applying Equation (6.1), Ns = min [15, 18, 0] = 0, occurs at position, i = 3. From Equation (6.2), Δ = 6. Since there is no link with capacity ≤ Δ, {1, 2} is itself an irredundant SCG.
Consider 4th cut, {9(9), 10(5), 11(6)}, CA4 = 20. Applying Equation (6.1) and (6.2); it is seen that provide, Ns = min [15, 12, 19, 0] = 0 occurs at position i = 4 and Δ = 6. Since there are links with capacity ≤ Δ, SCG will have to be formed.
Example 6.2 case (i): Consider the 8th cut {5 (5), 6 (6), 7 (5), 9(9)}, CA8 = 25. Let Wmin = 10. This cut had a first order SCG {6}. The remaining links in the cut are {5, 7, 9}. Applying Equation (5.1), i.e., Ns = min {10, 18, 19, 11, 15, 23, 20, 6} = 6 at position i = 8. From Equation (5.2), Δ = 4. Since there is no link ≤ Δ, {5, 7, 9} is itself a SCG.
Example 6.3 case (ii): Consider 12th cut, which had a first order SCG {1}, i.e., {3(7), 5(5), 8(8), 11(6)}, CA12 = 36 and Wmin = 10. Applying Equation (6.1) yields, Ns = 4 occurs at i = 2 (≠ 12). So, M = 26 and link capacity are arranged in decreasing order as {8, 7, 6, 5}. All four links are failed to provide capacity > 26 and so no SCG generation is performed.
Consider 5th cut, {4(4), 7 (5), 10(5), 11(6)}. For Wmin = 10, Ns = min {11, 8, 19, 9, 0} = 0 and Ns < Wmin occurs at three positions, viz., at {2, 4, 5}. Therefore, after calculating M = 10 and arranging the capacities in decreasing order {6, 5, 5, 4}, we find that the SCG of minimum order two are to be generated and if required, then higher order.
For Wmin = 6, there is a single position at which Ns < Wmin and M = 14. Thus, SCG of third order only are to be generated.
Clearly, this method greatly reduces the number of subsets generation. The following example illustrates and proves points.
Example 6.4: Consider i = 11th minimal cutset {2 (9), 3 (7), 5 (5), 7 (5), 9 (9)} of the network. For, Wmin = 10 units, Equation (5.1) and (5.2) yields Ns < Wmin at three positions, viz., at {7, 8, 11} with M = 25. By arranging the capacities of links in decreasing order as {9, 9, 7, 5, 5}, the minimum number of links needed to get capacity > M is four. It entails the SCGs to be generated of order four from this 5th order cutset, viz., {2, 3, 5, 7}, {2, 3, 5, 9}, {2, 3, 7, 9}, (2, 5, 7, 9 and {3, 5, 7, 9}, respectively. Consider first SCG, {2, 3, 5, 7} for which, Ns = 4 occurs at 7th position (< i). This clearly implies that the SCG is redundant. Validating other SCG in this manner, it is found that all SCG are redundant.
In the above examples, the number of SCG of order two and higher would be 26, i.e., (25-6), had we started generating SCG of second order onwards. However, only five SCG are generated. Obviously, the number of SCG and their order would further reduce if the valid SCG were obtained at the initial stages. In fact, this happens as the desired capacity, Wmin, increases from some minimum value to the maximum carrying capacity of the network.
6.3.4 Efficient Enumeration of Particular Order SCG of a Minimal Cut
Once we establish the order of enumeration, we can generate SCG of a particular order in the following manner. Let us represent a 6th order cut with a set of ordered numbers, S6 = {1, 2, 3, 4, 5, 6} to represent the position of a link in the cut. Let order of subsets generation required turns out to be the third order. Taking the last three terms of S6 (equal to the order of enumeration needed) provides a term = {4, 5, 6}. From this term, all other terms are generated by decreasing each term in a logical manner by noting that the first term in this set could decrease up to 1, second up to 2 and third up to 3. In other words, the last term of third order in the list would be {1, 2, 3}. Table 6.2 explains the enumeration scheme with remarks (a) and (b) at relevant points to write a computer program.
Table 6.2 Enumerating SCGs of a particular order from a set of numbers.
| S. No. | SCGs | Remark |
| 1. | {4, 5, 6} | (a) Decrease first digit up to 1 |
| 2. | {3, 5, 6} | |
| 3. | {2, 5, 6} | |
| 4. | {1, 5, 6} | (b) First digit cannot be decreased further. Decrease the next digit by one and replace all previous digit one less than this value keeping all other digits as they were. |
| 5. | {3, 4, 6} | Repeat (a) |
| 6. | {2, 4, 6} | |
| 7. | {1, 4, 6} | Repeat (b) |
| 8. | {2, 3, 6} | Repeat (a) |
| 9. | {1, 3, 6} | Repeat (b) |
| 10. | {1, 2, 6} | Repeat (b). Only third digit can be reduced. |
| 11. | {3, 4, 5} | Repeat (a) |
| 12. | {2, 4, 5} | |
| 13. | {1, 4, 5} | Repeat (b) |
| 14. | {2, 3, 5} | Repeat (a) |
| 15. | {1, 3, 5} | Repeat (b) |
| 16. | {1, 2, 5} | Repeat (b). Only third digit can be reduced. |
| 17. | {2, 3, 4} | Repeat (a) |
| 18. | {1, 3, 4} | Repeat (b) |
| 19. | {1, 2, 4} | Repeat (b). Only third digit can be reduced. |
| 20. | {1, 2, 3} | No digit can be reduced. Stop. |
It may be noted that by following steps (a) and (b), SCG of any order can be generated. In implementation, a mapping is done, i.e., a minimal cutsets say {1, 5, 7, 8, 13, 14} is mapped with a set {1, 2, 3, 4, 5, 6} Note that a term {2, 3, 4}, for example for a cut {1, 5, 7, 8, 13, 14}, should be interpreted a SCG {5, 7, 8}.
6.3.5 External or Both External/ Internal Redundancy Removal
In Equation (6.1) for the ith cutset, Ns < Wmin, may occur at position(s) lesser than ith. It implies that some SCG have already been encountered in the SCG of some other and already processed (such as SCG generation and external or internal redundant check etc …) cut (< i). Thus, the SCG of a particular order of this ith cut is generated. On these each SCG, we reapply Equation (6.1) and check, if Ns < Wmin, occurs at a position(s) lesser than ith, if it happens then the SCG would be externally redundant.
Example 6.5: Reconsidering i = 11th minimal cutset {2, 3, 5, 7, 9} of the network shown in Figure 6.3 and consider the following cases:
Case (i): Let us consider one of its SCG {2, 3, 5, 7} for Wmin = 10. Equation (6.1) for this combination would be: Ns = min {10, 18, 10, 20, 15, 16, 4, 15, 23, 28, 9} = 4 units and Ns< Wmin occurs at 7th and 11th positions rather than only at 11th position, (< i, i.e., 7 < 11). This implies that although {2, 3, 5 7} is a SCG but it is a superset of SCG {2, 3} generated by 7th minimal cutset, {2, 3, 4, 5}, processed earlier and is therefore externally redundant. In fact, for the 7th minimal cutset, Equation (6.1) for the subset {2, 3} is min [15, 18, 10, 20, 20, 16, 9] = 9, and minimum occurs at 7th position, which provides {2, 3} as a valid SCG and this SCG is not used further to generate its third order SCG. Likewise, {2, 5, 7, 9} would be detected as a superset of a valid SCG {5, 7, 9} produced by 8th cut set earlier.
Case (ii): Consider 5th minimal cutset, {4, 7, 10, 11}, of the same network wherein after the test on this cut, it is found that SCG of order two onwards are required to be generated.
Let us consider the subset (SCG), {4, 7}, for which Equation (6.1) yields, min [11, 14, 19, 20, 11] = 11 > Wmin (Not a valid SCG but possibly adding one or more link of the cut to this SCG might give a valid SCG. Thus it is be taken to generate next higher order combination). However, for its next order combination, {4, 7, 10} and {4, 7, 11}, Equation (6.1) yields:
min [11, 15, 19, 15, 6] = 6 (a valid SCG), and
min [11, 8, 19, 14, 5] = 5 (A redundant SCG).
In this case the current network flow capacity on removing links {4, 7, 11} would be 5 units (can be verified visually). However, Ns < Wmin has occurred at two positions. Therefore, this SCG is redundant. Basically, {4, 7, 11}⊇ {4, 11} or {7, 11}, which are valid and non-redundant SCG. In fact, it is a case of both external for {4, 11} and internal redundant for {7, 11} SCG detected by Equation (6.1) but can also be removed using Equation (6.2).
Similar, situation can occur on a tie between the minimums, i.e., for a SCG, {10, 11}, min [15, 12, 19, 9, 9] = 9. Here again, the current network flow capacity would be 9 units. However, the set is not a valid SCG as Ns < Wmin has occurred at 4th position as well.
6.3.6 Internal Redundancy Removal
Let us again illustrate it through a suitable example by extending the cases.
Case (iii): Consider the example in Figure 6.4 of (Example and Figure 2 in (Soh & Rai, 2005). Only, the network is reproduced for the sake of brevity. The maximum network flow capacity is 10 units and let the desired network capacity (Wmin) be 4 units.
Figure 6.4 Network of 7 Nodes and 15 Links.
Consider SCG, {1, 2, 7, 11} of the third minimal cutset, {1, 2, 7, 11, 15} in the order of its blocking capacity with respective capacities of links as {3, 1, 4, 3, 1}. Applying Equation (6.1) yields, Ns = min {10, 8, 1} = 1 < 4 units, which appears to be a non-redundant SCG.
However, capacity of link ‘2’ < Δ (= 3) and even if link ‘2’ is reinserted in the network could only raise the network capacity to 2 units, still less than Wmin. So link 2’s presence or absence does not matter for a specified Wmin = 4. In fact, {1, 2, 7, 11}⊇ {1, 7, 11}, and {1, 7, 11} has already been detected as an irredundant SCG in an earlier iteration implying {1, 2, 7, 11} is an internally redundant SCG.
The foregoing paragraphs have explained the building blocks of the approach. Using the above observations and cases, one can easily write the various algorithmic steps to follow. The program available at www.scrivenerpublishing.com contains the implementation of the algorithm in Matlab(R).
6.4 The CRR Evaluation Algorithm
Steps:
Cij ∀j = 1, 2 … L, in each column and compute, Ns = min [CAi - Cij].
If Ns < Wmin then link lij is a valid SCG. Make all column entries zero corresponding to link, lij.
The next step generates higher order SCG and removes external/internal redundancies, if any, through validity check using Equations (6.1) & (6.2).
If yes then go to (iii).
Ns = min [CX], nPos = [CX] < Wmin
Δ = Wmin - Ns
Where,
CX = CAj - Ck∀j ≤ i
CAj = Capacity of jth element of CA
Ck = Sum of capacities of links contained in kth SCG of certain order.
External
If Ns > Wmin and occurred at position i, check for internal redundancy.
If Ns has occurred at position (s) < i, then remove it from the list of combinations from further consideration.
Internal
If any link capacity in SCG < Δ, then it is an internal redundant SCG; remove it from further consideration.
Store and remove the qualified and redundant SCG.
For remaining SCG, if any, check
If order of SCG < order of the cut, then generate next higher order SCG and repeat the step from 3 b (iv). Else, repeat from step 3(b) for next cut.
6.5 A Complete Example
Consider the network shown in Figure 6.3. Obviously, the capacity of the network, Cmax, is 15 units. Let Wmin = 10 units, we apply each step of the algorithm on this network. The Cut-matrix, A, Cut-capacity vector and steps involved are shown side-by-side in Table 6.3.
Table 6.3 Algorithmic steps to solve illustrative example.
Therefore, for specified minimum flow requirement, Wmin = 10 units, the 14 non-redundant valid SCG are: {{1}, {6}, {4, 5}, {4, 8}, {4,11}, {8, 11}, {9, 10}, {9, 11}, {10, 11}, {7, 11}, {2, 3}, {4, 7, 10}, {5, 7, 9}, {7, 8, 9} out of 39 SCG generated by the algorithm. The resultant SCG of the network of Figure 6.3 have been shown in Figure 6.5 to show that removal of links contained in any SCG would render the network that cannot carry a load of 10 units, despite being (s, t) connected.
Figure 6.5 Sub-graphs of Figure 6.3 after Removal of Respective SCG for Wmin = 10 units
The valid SCG so obtained are used to evaluate the CRR expression and its value for the network using any of SDP approaches (Single or Multi variable), as mentioned earlier. The program available at www.scrivenerpublishing.com contains the Matlab® code from SCG enumeration to reliability.
The program can be executed as:
The SCG generated and stored in the file fig6.3SCG10Units.m can be fed to MVI/SVI programs to evaluate the capacitated reliability of the flow constrained network graph.
6.6 Experimental Results, Comparison and Discussion
Since, the key issue in CRR problem lying in generation of valid SCG from subsets of cuts, author makes the performance comparison with reference to this with the recent approaches of (Soh & Rai, 2005) (Soh et al., 2006) based on-how the valid SCG are generated and from how many subsets. To make a comparison among the approaches, the following comparative statements can be made:
To compare the performance of the algorithm, we provide a comparison of some networks, which are treated as complex in (Soh & Rai, 2005) (Soh et al., 2006). The complex networks are shown in Figure 6.6 and Figure 6.7, respectively. The cutsets of these networks are 214 and 7376, respectively. The results for various Wmin are also tabulated in Table 6.4 and Table 6.5 respectively Column#4 of the Tables shows whether T3 provides the benefits or not. A graphical representation of experimental results of the number of subsets enumerated by various algorithms (Columns#2,3 and 5 of Table 6.4 and Table 6.5) with varying Wmin is also shown in Figure 6.8 and Figure 6.9 respectively, for visualizing the efficiency of the algorithm.
Figure 6.6 Network of 13 Nodes and 22 Links.
Figure 6.7 Network of 20 Nodes and 30 Links.
Table 6.4 Results and comparison for the network in Figure 6.6.
Table 6.5 Results and comparison for the network in Figure 6.7.
Figure 6.8 Comparison of subsets generated for Figure 6.4.
Figure 6.9 Comparison of subsets generated for Figure 6.5.
From the results provided (in bold) in Table 6.4 and Table 6.5, it can be well-observed that:
Summarily, the method definitely efficient as it substantially reduces the number of subsets generations, removes the internal/external redundancies simultaneously rather than its removal after generating all cut groups. Equation (6.1) can also be used to provide the network capacity on removal of certain links from a cut set. Further, as the desired capacity approaches closer to the maximum capacity of the network, the number of subsets generation drastically decreases in comparison to A1 and SCE wherein there are polynomial rise in number of generated subsets.
The exercises of this chapter is deliberately left blank to the ingenuity of the readers to formulate by taking the several network graphs discussed in earlier Chapters of this text.
References
Chaturvedi, S.K., 2007. Irredundant Subset Cut Genaeration to Compute Capacity Related Reliability. International Journal of Performability Engineering, Vol. 3(2), pp. 243–256.
Colbourn, C.J., 1987. The combinatorics of Network Reliability. New York: Oxford University Press.
Mishra, R. & Chaturvedi, S.K., 2009. A Cutsets based Unified Framework to Evaluate Network Reliability Measures. IEEE Transaction on Reliability, Vol. 56(4), pp. 658–666.
Rath, D. & Soman, K.P., 1993. A simple Method for Generating k - Trees of a Network. Microelectronics and Reliability, Vol 33(9), pp. 1241–1244.
Soh, S., Lim, K.Y. & Rai, S., 2006. Evaluating Communication Network Reliability with Heterogenous Link Capacities using Subset Enumeration. International Journal of Performability Engineering, Vol. 2(1), pp. 3–17.
Soh, S. & Rai, S., 1991. CAREL: Computer Aided Reliability Evaluator for Distributed Computing Networks. IEEE Transaction on parallel and Distributed Systems, Vol.2(2), pp. 199–213.
Soh, S. & Rai, S., 2005. An Efficient Cutset Approach for Evaluating Communication-Network Reliability with Heterogenous Link-Capacities. IEEE Transactions on Reliability, Vol. 54(1), pp. 133–144.