Reliability Estimation of 4 $\times$ 4 SENs Using UGF Method

Vaibhav Bisht^* and S. B. Singh

Department of Mathematics, Statistics and Computer Science, G.B. Pant University of Agriculture and Technology, Pantnagar, India

E-mail: bishtvickybng@gmail.com; drsurajbsingh@yahoo.com

$^{*}$ Corresponding Author

Received 02 November 2020; Accepted 18 February 2021; Publication 10 June 2021

Abstract

Shuffle Exchange Networks (SENs) are considered as an appropriate interconnection network because they consist of switching elements of small size and possess a straight forward and simple configuration. In this paper, we have proposed a method for analyzing reliability of $4 \times 4$ SEN, $4 \times 4$ SEN $+$ 1 and $4 \times 4$ SEN $+$ 2. The reliability has been obtained on the basis of three indices, namely, terminal reliability, broadcast reliability and network reliability by using universal generating function (UGF) method. This study also examines effect of adding the additional stages in $4 \times 4$ shuffle exchange networks (SENs).

Keywords: Universal generating function (UGF), shuffle exchange network, terminal reliability (TR), broadcast reliability (BR) and network reliability (NR).

1 Introduction

In today’s era, nearly everyone depends upon the proper functioning of large number of machines and equipment for our day to day requirements and safety. We expect our communication system, electrical appliances, computer networks, nuclear power plants, and aerospace applications etc. to perform as expected. When they fail the results can be disastrous, injury or even loss of life. Thus it becomes very vibrant to assure their working, by carrying out the study of reliability.

A computer network system plays a vital role in transmitting information or messages. It is a process in which the signals are transmitted from source node to the destination node through circuits. Computer networks mainly have three main components, namely, local area network (LAN), wide area network (WAN), and metropolitan area network (MAN). LAN is a network that interconnects the computers within the limited distance. WAN is a telecommunication computer network which is used to connect over a large geographic range. The largest WAN, till date in the earth is the internet. In MAN, the interconnected area lie in the range between WAN and LAN, i.e. less than WAN but more than LAN (Gunawan 2014).

At the present time, there is high demand of reliable parallel computing systems. The computer system which consists of control units, memory modules and interconnection networks, is called parallel processing system. It is widely used for the construction of high-performance computing systems (Wu and Feng 1980). In the multiprocessor method, the interconnection network provides the means of communication through which a range of processors and memory. Interconnection networks are further divided into direct and indirect network. In the direct network, there is the point-to-point connection with the processing nodes via different edges, and also known as the static network or router-based network. Star graph, trees, Mesh, torus and hypercube are few examples of direct networks. In the indirect network, the messages between any two different nodes are passed through the switches contained in the network. The indirect interconnection networks are widely used in parallel computing to switch and route the dynamic nodes. The transmission of networks in an indirect network is carried out with the help of switches and the communication edges and these networks are designated as switch-based networks, dynamic networks, shared-medium network and the hybrid network (Bistouni and Jahanshahi 2014b; Rajkumar and Goyal 2016).

The multistage interconnection networks (MINs) are the important components of the dynamic network because there are certain links in dynamic topology and they are rearranged by setting with the mobile switching elements. MINs contain multiple sheets of interconnected switching elements which are arranged in a pre-defined topology. These types of networks have numerous applications in the areas such as integrated circuits, computer communications, multiprocessor systems and telecommunication switches. Since they are of large size and have complex structure, so it is essential to improve their performance and the reliability. It is worth mentioning here that these switching elements (SEs) are usually connected to each other in stages. MINs are further classified into three classes, namely blocking, non-blocking and rearrangeable non-blocking. In blocking networks, the possibility of relation between a free input/output pair is very low, since it clashes with the connections already present in the network. In non-blocking networks, there is a connection from any input node to any output node without affecting the pre-defined connections present in the network and there are many paths to each output between every input, which leads to extra stages. However, rearranging its actual connections by Gunawan (2014), Rajkumar and Goyal (2016), Trivedi (2008), a rearrangeable non-blocking network can create all possible connections between the source and the destination.

Generally, a Multistage interconnection network consists of N inputs and N outputs and n ( $= \log_{2} N$ ) stages and N/2 switching elements per stage, where N is the size of network. Some of widely used multistage interconnection networks are Shuffle exchange network (SEN), SEN with additional stages, Gamma interconnection network (GIN), Extra-stage GIN, Omega network, Benes network, Clos network, Multistage cube network and many more. It is to mention here that the reliability of network not only depends on the components in it but also depends on topology of the network. Poor choice of network structure and weak routing strategies are the main reasons of the failure of the MINs (Rajkumar and Goyal 2016).

In the past, many researchers have designed different types of methods to improve the performance and reliability of MINs. Trivedi (2008) calculated the reliability of MINs by using continuous Markov chains method. Rajkumar and Goyal (2016) estimated the reliability characteristics of two MINs, viz. gamma network and shuffle exchange network by the path set-based analytical method with the help of multiple variable inversion algorithms. Blake and Trivedi (1989) studied the reliability of the unique-path MIN and focussed on fault-tolerant scheme for increasing the reliability of the network. Both obtained derivations for the reliability of $8 \times 8$ SEN and $16 \times 16$ SEN. Bistouni and Jahanshahi (2014) suggested a new way to augment the reliability and fault-tolerance of one of the most often used MIN, $8 \times 8$ Shuffle-exchange network (SEN) by increasing the number of switching stages. They observed that the reliability of SEN with one additional stage (SEN $+$ 1) is better than that of SEN or SEN having two additional stages (SEN $+$ 2). Further, SEN $+$ 1 was found more reliable than SEN $+$ 2. Fard and Gunawan (2005) calculated a modified SEN consisting of $1 \times 2$ switching elements (SEs) at the source, $2 \times 2$ at the intermediate stages and $2 \times 1$ at the terminal stage, and calculated the terminal reliability of modified SEN and usual shuffle exchange network (SEN).

To analyse the various systems, many works have been carried out by using universal generating function (UGF). Negi and Singh (2015) calculated the reliability of non-repairable complex systems along with its subsystems which were connected in series with the help of UGF method. Bisht and Singh (2019) suggested an efficient process to evaluate reliability indices like reliability, MTTF and signature reliability of the complex bridge networks having independent and identically distributed lifetime components using UGF. Yeh (2008, 2009) estimated the reliability indices of MNN and also generated the algorithm to find the minimal paths of the network taken in the consideration, by UGF method. Levitin (2005) extended the UGF method to the situation when the performance distribution of certain elements of the MSS taken is dependent on the state of another element. Meenakshi and Singh (2017) calculated the reliability and MTTF of a non-repairable MSS by using IUGF. Sharma et al. (2009) examined the reliability and path lengths of certain irregular MINs, in which there are different number of switching elements in each stage. The reliability of the system is estimated by comprising the uncertainties in the probabilities and the failure rates of the components of the considered system.

2 Universal Generating Function (UGF)

Various methods are used for calculating the reliability of complex networks and engineering systems. Out of these methods, UGF is one of the widely used method due to its less complexity and time reducing nature. The basic notion behind this method was given by Ushakov (1986). Levitin and Lisnianski (1999) gave a method based on UGF procedure to calculate the importance of element reliability in various Multi-State System (MSS). Chacko (2018) applied named UGF method for the fast reliability assessment for a set of continuous MSSs. The proposed new UGF method may evaluate the reliability factors quickly for many different structures. Kumar and Singh (2018) studied the A-within-B-from-D/G SWCS incorporating multiple failures. An algorithm for evaluating signature estimation on the basis of Owen’s method and UGF technique was used for the considered system.

The UGF is based on the generalization of ordinary generating function. It is a form of the moment generating function in polynomial form representing the probability mass function of variables. If there are m possible values of k independent variables and $r_{m}$ is the probability of k which is equal to $k_{m}$ , then UGF of k is given by the polynomial as:

U (z) = \sum_{m = 1}^{M} r_{m} z^{k_{m}}

(1)

Consider p independent discrete random variables $X_{1}, X_{2} \dots X_{p}$ . Let $U_{1} (z), U_{2} (z), \dots, U_{p} (z)$ be the UGF of random variable $X_{1}, X_{2} \dots X_{p}$ and $f (X_{1}, X_{2} \dots X_{p})$ be an arbitrary function. Moreover, combination of r UGF is represented by composition operator, where the properties of the composition operator depend on properties of $f (X_{1}, X_{2} \dots X_{p})$ . So $U_{r} (z)$ is given in the following manner:

U_{r} (z) = \underset{f}{\otimes} (U_{1} (z), U_{2} (z) \dots, U_{p} (z))

If in a network, two components are given then, their UGFs is given by-

UGF of a series system is given as:

$(u_{1} (z) \underset{s e r}{\otimes} u_{2} (z))$	$= \sum_{k_{1} = 1}^{K_{1}} p_{1 k_{1}} z^{g_{1 k_{1}}} \underset{s e r}{\otimes} \sum_{k_{2} = 1}^{K_{2}} p_{2 k_{2}} z^{g_{2 k_{2}}}$
	$= \sum_{= 1}^{K_{1}} p_{1 k_{1}} \sum_{k_{2} = 1}^{K_{2}} p_{2 k_{2}} z^{s e r (g_{1 k 1}, g_{2 k 2})}$	(2)

UGF of a parallel system is given as:

$(u_{1} (z) \underset{p a r}{\otimes} u_{2} (z))$	$= \sum_{k_{1} = 1}^{K_{1}} p_{1 k_{1}} z^{g_{1 k_{1}}} \underset{p a r}{\otimes} \sum_{k_{2} = 1}^{K_{2}} p_{2 k_{2}} z^{g_{2 k_{2}}}$
	$\sum_{= 1}^{K_{1}} p_{1 k_{1}} \sum_{k_{2} = 1}^{K_{2}} p_{2 k_{2}} z^{p a r (g_{1 k 1}, g_{2 k 2})}$	(3)

where, $\otimes_{s e r}$ and $\otimes_{p a r}$ denote the composition operators for series and parallel components respectively.

The structure function for the series ( $φ$ ser) and parallel ( $φ$ par) systems can be computed by the Equations (4) and (5), respectively, as

$φ_{s e r} (p_{1}, \dots p_{n})$	$= m i n {p_{1}, \dots p_{n}},$	(4)
$φ_{p a r} (p_{1}, \dots p_{n})$	$= m a x {p_{1}, \dots p_{n}},$	(5)

where, $p_{1}, \dots p_{n}$ are the components present in the system.

3 Structure of 4 $\times$ 4 SEN, SEN $+$ 1 and SEN $+$ 2

The $4 \times 4$ SEN, SEN $+$ 1 and SEN $+$ 2 are shown in Figures 1–3 respectively.

Figure 1 $4 \times 4$ SEN.

Figure 2 $4 \times 4$ SEN $+$ 1.

Figure 3 $4 \times 4$ SEN $+$ 2.

4 Reliability of 4 $\times$ 4 SEN, SEN $+$ 1 and SEN $+$ 2

Reliability analysis of $4 \times 4$ SEN, SEN $+$ 1 and SEN $+$ 2 is calculated on the basis of following three reliabilities, viz. terminal reliability, broadcast reliability and network reliability. Here, we propose to study the same with the application of UGF.

4.1 Terminal Reliability (TR)

The terminal reliability (TR) of a network is defined as the probability of existence of at least one fault-free path between source and destination of the network.

4.1.1 Terminal reliability of 4 $\times$ 4 SEN

Terminal reliability block diagram of $4 \times 4$ SEN is shown in Figure 4.

Figure 4 TR of SEN.

The terminal reliability of $4 \times 4$ SEN with the help of UGF can be calculated as:

R_{T R} (S E N) = \min (p_{1}, p_{2})

where, $p_{1}, p_{2}$ are the probabilities of the components present in the network.

(a) When the components of $4 \times 4$ SEN are not same and the probabilities of the components in the network are distinct, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2 .$

Let us consider that the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2$ respectively, are given by:

u_{s_{1}} (z) = 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}

Since both the SEs are connected in series, hence the UGF of both the switching elements can be calculated as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{s_{2}} (z)$
$U (z)$	$= 0.9702 z^{1} + 0.0298 z^{0}$

Finally, the terminal reliability (TR) of $4 \times 4$ SEN network is given by

TR (SEN) = 0.9702

(b) When all the components of the $4 \times 4$ SEN are same then all the switching elements has the same probabilities, then the structure function is expressed as:

R_{T R} (SEN) = p^{2}

Terminal reliability of $4 \times 4$ SEN is evaluated with respect to different switching reliability by UGF method and compared with $8 \times 8$ SEN as given in Table 1.

Table 1 Terminal reliability of $4 \times 4$ SEN

Switching	TR Evaluation	TR of $8 \times 8$ SEN	TR of $8 \times 8$ SEN
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.81	0.72900	0.72900
0.95	0.9025	0.85737	0.85737
0.96	0.9216	0.88473	0.88473
0.98	0.9604	0.94119	0.94119
0.99	0.9801	0.97029	0.97029

4.1.2 Terminal Reliability of 4 $\times$ 4 SEN $+$ 1

SEN $+$ 1 is a double path MIN. Terminal reliability block diagram of SEN $+$ 1 of size $4 \times 4$ is shown in Figure 5.

Figure 5 TR of SEN $+$ 1.

The UGF of terminal reliability of SEN $+$ 1 is given as:

R_{T R} (SEN + 1) = \min (\max (p_{2}, p_{3}), p_{1}, p_{4})

where, $p_{1}, p_{2}, p_{3}, p_{4}$ are the probabilities of the switching elements present in the network.

(a) If the components of $4 \times 4$ SEN $+$ 1 are not similar, i.e. the probabilities of the components in the network are different, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2, 3$ and 4.

Let, the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, 3$ and 4 respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{2}} (z) \underset{\max}{\otimes} u_{s_{3}} (z)$
	$= 0.9994 z^{1} + 0.006 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 1 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} U_{A} (z) \underset{\min}{\otimes} u_{s_{4}} (z)$
$U (z)$	$= 0.94982976 z^{1} + 0.05017024 z^{0}$

Hence, the terminal reliability of $4 \times 4$ SEN $+$ 1 network is given by

TR (SEN + 1) = 0.94982976

(b) If the components of the $4 \times 4$ SEN $+$ 1 are identical and all switching elements has the same probabilities, then the structure function is expressed as:

R_{T R} (SEN +) = 2 p^{3} - p^{4}

Terminal reliability of $4 \times 4$ SEN $+$ 1 is evaluated with respect to different switching reliability by using UGF method and compared with $8 \times 8$ SEN $+$ , which is presented in Table 2.

Table 2 Terminal reliability of $4 \times 4$ SEN $+$ 1

Switching	TR Evaluation	TR of $8 \times 8$ SEN $+$	TR of $8 \times 8$ SEN $+$
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.8019	0.780759	0.780759
0.95	0.90024	0.893920	0.893920
0.96	0.920125	0.915935	0.915935
0.98	0.960016	0.95889	0.95889
0.99	0.98000	0.979712	0.979712

4.1.3 Terminal Reliability of 4 $\times$ 4 SEN $+$ 2

SEN $+$ 2 can transmit the signal through four different paths from input source to output sink. The terminal reliability block diagram of SEN $+$ 2 for the size $4 \times 4$ is shown in Figure 6.

Figure 6 TR of $4 \times 4$ SEN $+$ 2.

The structure function for terminal reliability of $4 \times 4$ SEN $+$ 2 by UGF is given as:

R_{T R} (SEN + 2) = \min (\max (\min (p_{2}, p_{4}), \min (p_{3}, p_{5})), p_{1}, p_{6})

where, $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}$ are the probabilities of the switching elements present in the network.

(a) If the components of $4 \times 4$ SEN $+$ 2 are not identical and the probabilities of the components in the network are distinct, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2, 3, 4, 5$ and 6.

Let us consider that the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1$ , 2, 3, 4, 5 and 6 respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$
$u_{s_{5}} (z)$	$= 0.95 z^{1} + 0.05 z^{0} u_{s_{6}} (z) = 0.94 z^{1} + 0.06 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{2}} (z) \underset{\min}{\otimes} u_{s_{4}} (z)$
	$= 0.9408 z^{1} + 0.0592 z^{0}$
$U_{B} (z)$	$= u_{s_{3}} (z) \underset{\min}{\otimes} u_{s_{5}} (z)$
	$= 0.9215 z^{1} + 0.0785 z^{0}$
$U_{C} (z)$	$= U_{A} (z) \underset{\max}{\otimes} U_{B} (z)$
	$= 0.9953528 z^{1} + 0.00464 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 2 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{C} (z) \underset{\min}{\otimes} u_{s_{6}} (z)$
$U (z)$	$= 0.926275315 z^{1} + 0.073724685 z^{0}$

Hence, the terminal reliability of $4 \times 4$ SEN $+$ 2 network is given by

TR (SEN + 2) = 0.926275315

(b) If all the components of the $4 \times 4$ SEN $+$ 2 are identical ( $p_{i} = p)$ then the structure function of reliability is expressed as:

R_{T R} (SEN + 2) = 2 p^{4} - p^{6}

Terminal reliability of $4 \times 4$ SEN $+$ 2 is evaluated with respect to different switching reliability by UGF method and compared with $8 \times 8$ SEN $+$ 2 as presented in Table 3.

Table 3 Terminal reliability of $4 \times 4$ SEN $+$ 2

Switching	TR Evaluation	TR of $8 \times 8$ SEN $+$ 2	TR of $8 \times 8$ SEN $+$ 2
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.780759	0.7888415	0.591145
0.95	0.893921	0.8971944	0.755517
0.96	0.915935	0.9182251	0.7966417
0.98	0.958894	0.9595733	0.889761
0.99	0.979712	0.9798963	0.942558

4.2 Broadcast Reliability

It is the probability of transmitting network from single source to all destination nodes. In this segment, Broadcast reliability of $4 \times 4$ SEN, SEN $+$ 1, SEN $+$ 2 are being calculated using UGF method and is compared with $8 \times 8$ SEN, SEN $+$ 1 and SEN $+$ 2.

4.2.1 Broadcast reliability of 4 $\times$ 4 SEN

Broadcast reliability block diagram of $4 \times 4$ SEN is shown in Figure 7.

Figure 7 BR of $4 \times 4$ SEN.

The broadcast reliability of $4 \times 4$ SEN is calculated by UGF as:

R_{B R} (SEN) = \min (p_{1}, p_{2}, p_{3})

where, $p_{1}, p_{2}$ and $p_{3}$ are the probabilities of the components present in the network.

(a) If all the components of $4 \times 4$ SEN are not identical and the probabilities of the components in the network are distinct, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2, 3$ .

Let us suppose that the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2$ and 3 respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0}$

Since all three SEs are connected in series, here the UGF of the switching elements can be calculated as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{s_{2}} (z) \underset{\min}{\otimes} u_{s_{3}} (z)$
$U (z)$	$= 0.941094 z^{1} + 0.058906 z^{0}$

Finally, the broadcast reliability of $4 \times 4$ SEN network is calculated as

BR (SEN) = 0.941094

(b) If the components of the $4 \times 4$ SEN are same, then all switching elements has the same probabilities, then it’s structure function is expressed as:

R_{T R} (SEN) = p^{3}

Broadcast reliability of $4 \times 4$ SEN is evaluated with respect to different switching reliability by the proposed UGF method and compared with $8 \times 8$ SEN as given in Table 4.

Table 4 Broadcast reliability of $4 \times 4$ SEN

Switching	BR Evaluation	BR of $8 \times 8$ SEN	BR of $8 \times 8$ SEN
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.95	0.857375	0.698337	0.77184
0.96	0.884736	0.751447	0.81406
0.98	0.941192	0.868126	0.90359
0.99	0.970299	0.932065	0.95089

4.2.2 Broadcast reliability of 4 $\times$ 4 SEN $+$ 1

SEN $+$ 1 is a double path MIN. Broadcast reliability block diagram of SEN $+$ 1 of size $4 \times 4$ as shown in Figure 8.

Figure 8 BR of $4 \times 4$ SEN $+$ 1.

The UGF of broadcast reliability of $4 \times 4$ SEN $+$ 1 is given as:

R_{B R} (S E N + 1) = \min (\max (p_{2}, p_{3}), p_{1}, p_{4}, p_{5})

where, $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}$ are the probabilities of the components present in the network.

(a) If all the components of $4 \times 4$ SEN $+$ 1 are not same and the probabilities of the components in the network are distinct, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2, 3, 4$ and 5.

Let, the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, \dots, 5$ respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$
$u_{s_{5}} (z)$	$= 0.95 z^{1} + 0.05 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{2}} (z) \underset{\max}{\otimes} u_{s_{3}} (z)$
	$= 0.9994 z^{1} + 0.006 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 1 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} U_{A} (z) \underset{\min}{\otimes} u_{s_{4}} (z) \underset{\min}{\otimes} u_{s_{5}} (z)$
$U (z)$	$= 0.902338272 z^{1} + 0.097661728 z^{0}$

Hence, the broadcast reliability of $4 \times 4$ SEN $+$ 1 network is calculated as

BR (SEN + 1) = 0.902338272

(b) If all the components of the $4 \times 4$ SEN $+$ 1 are same, i.e. ( $p_{i} = p)$ then the structure function is expressed as:

R_{T R} (S E N + 2) = 2 p^{4} - p^{5}

For different switching reliability, broadcast reliability of $4 \times 4$ SEN $+$ 1 is calculated and compared with $8 \times 8$ SEN $+$ 1 as shown in Table 5.

Table 5 Broadcast reliability of $4 \times 4$ SEN $+$ 1

Switching	BR Evaluation	BR of $8 \times 8$ SEN $+$	BR of $8 \times 8$ SEN $+$ 1
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.72171	0.5548722	0.56917
0.95	0.85523	0.7611920	0.76642
0.96	0.88332	0.8067559	0.81036
0.98	0.94081	0.9014617	0.90250
0.99	0.97020	0.9503338	0.95061

4.2.3 Broadcast reliability of 4 $\times$ 4 SEN $+$ 2

SEN $+$ 2 can transmit the signal through four different paths from input source to output sink. The broadcast reliability block diagram of SEN $+$ 2 for the size $4 \times 4$ is shown in Figure 9.

Figure 9 BR of $4 \times 4$ SEN $+$ 2.

The broadcast reliability of $4 \times 4$ SEN $+$ 2 is calculated using UGF as:

R_{B R} (S E N + 2) = \min (\max (\min (p_{2}, p_{4}), \min (p_{3}, p_{5})), p_{1}, p_{6}, p_{7})

where, $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}$ and $p_{7}$ are the probabilities of the network components.

(a) If all the components of $4 \times 4$ SEN $+$ 2 are not similar, then the probabilities of the components in the network will be different, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2$ , 3, 4, 5, 6 and 7.

Let, the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, \dots, 7$ . respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$
$u_{s_{5}} (z)$	$= 0.95 z^{1} + 0.05 z^{0} u_{s_{6}} (z) = 0.94 z^{1} + 0.06 z^{0}$
$u_{s_{7}} (z)$	$= 0.93 z^{1} + 0.07 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{2}} (z) \underset{\min}{\otimes} u_{s_{4}} (z)$
	$= 0.9408 z^{1} + 0.0592 z^{0}$
$U_{B} (z)$	$= u_{s_{3}} (z) \underset{\min}{\otimes} u_{s_{5}} (z)$
	$= 0.9215 z^{1} + 0.0785 z^{0}$
$U_{c} (z)$	$= U_{A} (z) \underset{\max}{\otimes} U_{B} (z)$
	$= 0.9953528 z^{1} + 0.0046472 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 1 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} U_{C} (z) \underset{\min}{\otimes} u_{s_{6}} (z) \underset{\min}{\otimes} u_{s_{7}} (z)$
$U (z)$	$= 0.861436043 z^{1} + 0.138563957 z^{0}$

Hence, the broadcast reliability of $4 \times 4$ SEN $+$ 2 network is calculated as

BR (SEN + 2) = 0.861436043

(b) If the components of the $4 \times 4$ SEN $+$ 2 are identical and all switching elements has the same probabilities, i.e. ( $p_{i} = p$ ), then the structure function is expressed as:

R_{T R} (S E N + 2) = 2 p^{5} - p^{7}

Using UGF, broadcast reliability of $4 \times 4$ SEN $+$ 2 is evaluated for different switching reliability and compared with $8 \times 8$ SEN $+$ 2, which is presented in Table 6.

Table 6 Broadcast reliability of $4 \times 4$ SEN $+$ 2

Switching	BR Evaluation	BR of $8 \times 8$ SEN $+$ 2	BR of $8 \times 8$ SEN $+$ 2
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.702683	0.5669980	0.5776400
0.95	0.849225	0.7668366	0.7697292
0.96	0.879298	0.8108211	0.8126635
0.98	0.939716	0.9027414	0.9042140
0.99	0.969915	0.9506918	0.9508393

Figure 10 NR of $4 \times 4$ SEN.

4.3 Network Reliability

It is the probability of successful transmission of signals from all source nodes to all sink nodes. In this segment, network reliability of $4 \times 4$ SEN, SEN $+$ 1, SEN $+$ 2 are being calculated with the help of the UGF.

4.3.1 Network reliability of 4 $\times$ 4 SEN

Network reliability block diagram of $4 \times 4$ SEN is shown in Figure 10.

Using UGF, the structure function for the network reliability of $4 \times 4$ SEN is given as:

R_{T R} (SEN) = \min (p_{1}, p_{2}, p_{3}, p_{4})

where, $p_{1}, p_{2}, p_{3}, p_{4}$ are the probabilities of the components present in the network.

(a) When the components of $4 \times 4$ SEN are not same and the probabilities of the components in the network are distinct, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2, 3$ and 4.

Let us consider that UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, 3$ and 4 respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$

Since all the SEs are connected in series, then the UGF of the switching elements can be calculated as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{s_{2}} (z) \underset{\min}{\otimes} u_{s_{3}} (z) \underset{\min}{\otimes} u_{s_{4}} (z)$
$U (z)$	$= 0.90345024 z^{1} + 0.09654976 z^{0}$

Finally, the network reliability of $4 \times 4$ SEN network is calculated as

NR (SEN) = 0.90345024

(a) When the components of the $4 \times 4$ SEN are identical and all switching elements has the same probabilities, then the structure function is expressed as:

R_{N R} (SEN) = p^{4}

Using UGF, network reliability of $4 \times 4$ is evaluated for different switching reliability and compared with that of $8 \times 8$ SEN, which is presented in Table 7.

Table 7 Network reliability of $4 \times 4$ SEN

Switching	NR Evaluation	NR of $8 \times 8$ SEN	NR of $8 \times 8$ SEN
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht, and Singh (2018)]
0.90	0.6561	0.2824295	0.4219009
0.95	0.814506	0.540360	0.6601074
0.96	0.849347	0.612709	0.7190827
0.98	0.922368	0.7847147	0.8500825
0.99	0.960596	0.8863849	0.9225601

4.3.2 Network reliability of 4 $\times$ 4 SEN $+$ 1

SEN $+$ 1 is a double path MIN. Network reliability block diagram of SEN $+$ 1 of size $4 \times 4$ is shown in Figure 11.

Figure 11 NR of $4 \times 4$ SEN $+$ 1.

The network reliability of $4 \times 4$ SEN $+$ 1 is calculated using UGF as:

R_{N R} (S E N + 1) = \min (\max (p_{3}, p_{4}), p_{1}, p_{2}, p_{5}, p_{6})

where, $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}$ are the probabilities of the components present in the network.

(a) If the components of $4 \times 4$ SEN $+$ 1 are not same, i.e. probabilities of all the components in the network are different, then UGFs of the various switching elements are given by:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2$ , 3, 4, 5 and 6.

Let, the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, \dots 5$ respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$
$u_{s_{5}} (z)$	$= 0.95 z^{1} + 0.05 z^{0} u_{s_{6}} (z) = 0.94 z^{1} + 0.06 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{3}} (z) \underset{\max}{\otimes} u_{s_{5}} (z)$
	$= 0.9988 z^{1} + 0.0012 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 1 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{s_{2}} (z) \underset{\min}{\otimes} U_{A} (z) \underset{\min}{\otimes} u_{s_{5}} (z) \underset{\min}{\otimes} u_{s_{6}} (z)$
$U (z)$	$= 0.865348933 z^{1} + 0.134651066 z^{0}$

Hence, the network reliability of $4 \times 4$ SEN $+$ 1 network is given as

NR (SEN + 1) = 0.865348933 .

(b) If all the SEs of the $4 \times 4$ SEN $+$ 1 has the same probabilities, then the structure function is expressed as:

R_{T R} (SEN + 2) = 2 p^{5} - p^{6}

Network reliability of $4 \times 4$ SEN $+$ 1 is calculated with respect to different switching reliability by the proposed UGF method and compared with $8 \times 8$ SEN $+$ 1 as given in Table 8.

Table 8 Network reliability of $4 \times 4$ SEN $+$ 1

Switching	NR Evaluation	NR of $8 \times 8$ SEN $+$	NR of $8 \times 8$ SEN $+$ 1
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.649539	0.388707	0.406669
0.95	0.812470	0.645470	0.653831
0.96	0.847988	0.708630	0.714663
0.98	0.921999	0.8468415	0.848744
0.99	0.960499	0.9216594	0.922203

4.3.3 Network reliability of 4 $\times$ 4 SEN $+$ 2

SEN $+$ 2 can transmit the signal through four different paths from input source to output sink. The network reliability block diagram of SEN $+$ 2 for the size $4 \times 4$ is depicted in Figure 12.

Figure 12 NR $4 \times 4$ SEN $+$ 2.

The UGF of network reliability of $4 \times 4$ SEN $+$ 2 is given as:

R_{N R} (SEN + 2) = \min (\max (\min (p_{3}, p_{4}), \min (p_{5}, p_{6})), p_{1}, p_{2}, p_{7}, p_{8})

where, $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}, p_{7}$ and $p_{8}$ are the probabilities of the components present in the network.

(a) If the components of $4 \times 4$ SEN $+$ 2 are not similar, i.e. the probabilities of all the SEs are different, then UGFs of the various switching elements is expressed as:

u_{s_{j}} (z) = p_{s_{j}} z^{1} + (1 - p_{s_{j}}) z^{0}

where, $p_{s_{j}}$ is the probability of the switch $s_{j}, j = 1, 2$ , 3, 4, 5, 6, 7 and 8.

Let, the UGFs $u_{s_{j}} (z)$ of the network for the switches $s_{j}, j = 1, 2, \dots, 8$ respectively, are given as:

$u_{s_{1}} (z)$	$= 0.99 z^{1} + 0.01 z^{0} u_{s_{2}} (z) = 0.98 z^{1} + 0.02 z^{0}$
$u_{s_{3}} (z)$	$= 0.97 z^{1} + 0.03 z^{0} u_{s_{4}} (z) = 0.96 z^{1} + 0.04 z^{0}$
$u_{s_{5}} (z)$	$= 0.95 z^{1} + 0.05 z^{0} u_{s_{6}} (z) = 0.94 z^{1} + 0.06 z^{0}$
$u_{s_{7}} (z)$	$= 0.93 z^{1} + 0.07 z^{0} u_{s_{8}} (z) = 0.92 z^{1} + 0.08 z^{0}$

Applying composition operators for different SEs as per their combination, we have UGFs as follows:

$U_{A} (z)$	$= u_{s_{3}} (z) \underset{\max}{\otimes} u_{s_{4}} (z)$
	$= 0.9988 z^{1} + 0.0012 z^{0}$
$U_{B} (z)$	$= u_{s_{5}} (z) \underset{\max}{\otimes} u_{s_{6}} (z)$
	$= 0.997 z^{1} + 0.003 z^{0}$

Finally, the reliability of the source-to-multiple terminal structure of $4 \times 4$ SEN $+$ 2 is obtained as:

$U (z)$	$= u_{s_{1}} (z) \underset{\min}{\otimes} u_{s_{2}} (z) \underset{\min}{\otimes} U_{A} (z) \underset{\min}{\otimes} u_{B} (z) \underset{\min}{\otimes} u_{s_{7}} (z) \underset{\min}{\otimes} u_{s_{8}} (z)$
$U (z)$	$= 0.826619675 z^{1} + 0.173380325 z^{0}$

Finally, the network reliability of $4 \times 4$ SEN $+$ 2 network is calculated as

NR (SEN + 2) = 0.826619675 .

(b) If all the components of the $4 \times 4$ SEN $+$ 2 are same then all the switching elements has the same probabilities, i.e. ( $p_{i} = p$ ), then the structure function is expressed as:

R_{T R} (S E N + 2) = 4 p^{6} + p^{8} - 4 p^{7}

With the help of UGF, network reliability of $4 \times 4$ is evaluated for different switching reliability and compared with that of $8 \times 8$ SEN $+$ 2, which is presented in Table 9.

Table 9 Network reliability of $4 \times 4$ SEN $+$ 2

Switching	NR Evaluation	NR of $8 \times 8$ SEN $+$ 2	NR of $8 \times 8$ SEN $+$ 2
Reliability	by UGF	[Rajkumar and Goyal (2016)]	[Bisht and Singh (2018)]
0.90	0.643044	0.406633	0.406628
0.95	0.810438	0.655175	0.653830
0.96	0.846631	0.715835	0.714668
0.98	0.921630	0.849251	0.848751
0.99	0.9604039	0.922354	0.922294

5 Conclusion

In the present work, we have considered the $4 \times 4$ Shuffle exchange network (SEN), $4 \times 4$ shuffle exchange network with one additional stage (SEN $+$ 1) and $4 \times 4$ shuffle exchange network with two additional stages (SEN $+$ 2). The reliability block diagram for the terminal, broadcast and network reliability of the $4 \times 4$ SENs has been presented. By using UGF, the reliability of $4 \times 4$ SENs have been evaluated with respect to the same and different switching element probabilities and it was observed that the reliability of $4 \times 4$ SEN is the highest and that of $4 \times 4$ SEN $+$ 2 is the lowest. It is also observed that the reliability of $4 \times 4$ Shuffle exchange networks decreases with adding additional stages in it. The order of reliability was obtained as $4 \times 4$ SEN $>$ $4 \times 4$ SEN $+$ 1 $>$ $4 \times 4$ SEN $+$ 2.

References

[1] Bisht, S. [2018]. Reliability indices and signature analysis of complex networks. Thesis Ph.D. GBPUA&T Pantnagar.

[2] Bisht, S., & Singh, S. B. [2019]. Signature reliability of binary state node in complex bridge networks using universal generating function. International Journal of Quality & Reliability Management, Vol. 36(2), pp. 186–201.

[3] Bistouni, F., & Jahanshahi, M. [2014a]. Analyzing the reliability of shuffle-exchange networks using reliability block diagrams. Reliability Engineering & System Safety, Vol. 132, pp. 97–106.

[4] Bistouni, F., & Jahanshahi, M. [2014b]. Improved extra group network: a new fault- tolerant multistage interconnection network. The Journal of Supercomputing, Vol. 69(1), pp. 161–199.

[5] Blake, J. T., & Trivedi, K. S. [1989]. Multistage interconnection network reliability. IEEE Transactions on Computers, Vol. 38(11), pp. 1600–1604.

[6] Chacko, V. M. [2018]. Continuous Multistate System Universal Generating Function. Reliability: Theory & Applications, 13(4 (51)).

[7] Fard, N. S., & Gunawan, I. [2005]. Terminal reliability improvement of shuffle-exchange network systems. International Journal of Reliability, Quality and Safety Engineering, Vol. 12(01), pp. 51–60.

[8] Gunawan, I. [2014]. Fundamentals of Reliability Engineering: Applications in Multistage Interconnection Networks. John Wiley & Sons.

[9] Kumar, A., & Singh, S. B [2019]. Signature A-within-B-from-D/G sliding window system. International Journal of Mathematical, Engineering and Management Sciences, Vol. 4(1), pp. 95–107

[10] Levitin, G. [2004]. A universal generating function approach for the analysis of multi-state systems with dependent elements. Reliability Engineering & System Safety, Vol. 84(3), pp. 285–292.

[11] Levitin, G., & Lisnianski, A. [1999]. Importance and sensitivity analysis of multi-state systems using the universal generating function method. Reliability Engineering & System Safety, Vol. 65(3), pp. 271–282.

[12] Meenakshi, & Singh, S. B. [2017]. Reliability analysis of multi-state complex system having two multi-state subsystems under uncertainty. Journal of Reliability and Statistical Studies, Vol. 10(1), pp. 161–177.

[13] Negi, S., & Singh, S. B. [2015]. Reliability analysis of non-repairable complex system with weighted subsystems connected in series. Applied Mathematics and Computation, Vol. 262, pp. 79–89.

[14] Rajkumar, S., & Goyal, N. K. [2016]. Review of multistage interconnection networks reliability and fault-tolerance. IETE Technical Review, Vol. 33(3), pp. 223–230.

[15] Sharma, S., Kahlon, K. S., & Bansal, P. K. [2009]. Reliability and path length analysis of irregular fault tolerant multistage interconnection network. ACM SIGARCH Computer Architecture News, Vol. 37(5), pp. 16–23.

[16] Trivedi, K. S. [2008]. Probability and statistics with reliability, queuing and computer science applications. Wiley, Hoboken.

[17] Ushakov, I. A. [1986]. A universal generating function. Soviet Journal of Computer and Systems Sciences, Vol. 24(5), pp. 118–129.

[18] Wu, C. L., and Feng, T. Y. [1980]. On a class of multistage interconnection networks. IEEE Transactions on Computers, Vol. 100(8), pp. 694–702.

[19] Yeh, W. C. [2008]. A simple universal generating function method for estimating the reliability of general multi-state node networks. IIE Transactions, Vol. 41(1), pp. 3–11.

[20] Yeh, W. C. [2009]. A simple universal generating function method to search for all minimal paths in networks. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol. 39(6), pp. 1247–1254.

Biographies

Vaibhav Bisht is a Research Scholar in Department of Mathematics, Statistics and Computer Science at G. B. Pant University of Agriculture and Technology, Pantnagar, India. He received the B.Sc. degree from Kumaun University, Nainital, India, in 2018 and M.Sc. degree, with major in Mathematics and minor in Computer science from G. B. Pant University of Agriculture and Technology, India, Pantnagar, in 2020. His area of research is Reliability Theory.

S. B. Singh is a Professor in the Department of Mathematics, Statistics and Computer Science, G. B. Pant University of Agriculture and Technology, Pantnagar, India. He has around 25 years of teaching and research experience to undergraduate and post graduate students at different engineering colleges and universities. Prof. Singh is a member of Indian Mathematical Society, Operations Research Society of India, ISST and National Society for Prevention of Blindness in India and Indian Science Congress Association. He is a regular reviewer of many books and international/national journals. He has been a member of organizing committee of many international and national conferences and workshops. He is editor in Chief of the journal “Journal of Reliability and Statistical Studies”. He has authored and co-authored eight books on different courses of Applied/Engineering Mathematics. He has been conferred with four national awards and two times best teacher award. He has published his research works at national and international journals of repute. His area of research is Reliability Theory.

Journal of Reliability and Statistical Studies, Vol. 14, Issue 1 (2021), 173–198.
doi: 10.13052/jrss0974-8024.1418
© 2021 River Publishers