# G-NETWORKS OF UNRELIABLE NODES

Jean-Michel Fourneau

► To cite this version:

Jean-Michel Fourneau. G-NETWORKS OF UNRELIABLE NODES. Probability in the Engineering and Informational Sciences, 2016, 30 (03), pp.361 - 378. 10.1017/S026996481600005X . hal-01832153

HAL Id: hal-01832153

https://uvsq.hal.science/hal-01832153v1

Submitted on 24 Jan 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# G-NETWORKS OF UNRELIABLE NODES

JEAN-MICHEL FOURNEAU

DAVID, Université de Versailles-St Quentin, 45, Av. des États-Unis, 78035 Versailles, France
E-mail: jmf@prism.uvsq.fr, Jean-Michel.Fourneau@uvsq.fr

We study G-networks with positive and negative customers and signals. We consider two types of signals: they can make a subnetwork of queues operational or down. As signals are sent by queues after a customer service completion, one can model the availability of a sub-network of queues controlled by another network of queues. We prove that under classical assumptions for G-networks and assumptions on the rerouting probabilities when a subnetwork is not operational, the steady-state distribution, if it exists, has a product form steady state distribution. Some examples are given.

## 1. INTRODUCTION

G-networks of queues have been introduced by Gelenbe in [9]. They consist of queues which contains positive (or usual) customers and signals. The first signal studied in the literature is the “negative customer signal” defined in [9]. All the signals studied so far always have some common characteristics: they are created at the end of a customer service in a queue, they route to a queue (not necessarily distinct) and they interact with the queue at their arrival. This interaction is instantaneous. After the interaction takes place, the signal disappears. The interaction may succeed or fail depending on the state or a Bernoulli trial. Signals differ by their effect on the queue they reached. Since Gelenbe’s seminal paper, many signals have been studied in the literature: negative customers which delete one usual customer if there exists at least one in the queue, triggers which move a customer from one queue to another one [10] catastrophes which flushes all the customers out of the queue [7], resets which change the state according to a distribution closely related to the steady state [13]. Extensions with multiple classes of customers have been studied [14]. They allow more complex interactions between signals and queues based on the classes of customers and service disciplines: for instance in [3] a signal can change the class of a customer in a network with symmetric queues as defined by Kelly [20]. Despite these synchronized transitions on several queues (end of service and action of signal), the models previously mentioned all have a product form distribution at steady state when it exists. Such a result is proved under usual assumptions about the arrivals of customers of the outside (independent Poisson processes), service time distributions (exponential), open topology and Markov routing. Note that as the effect of a signal can be a local effect followed by the emission of another signal sent to another queue, one may obtain a complex instantaneous transition on several queues with a product form steady-state distribution [8]. Another possible extension of the theory of G-network is to
enrich the types of customers which may react to signal but do not interact anymore with servers (the so-called inert customers introduced in [4]).

G-networks had also motivated many new important results in the theory of queues. As negative customers lead to customer deletions, the original description of quasi-reversibility by arrivals and departures does not hold anymore and extensions of the quasi-reversibility definition had been proposed. At the time being, the description proposed by Chao, Miyazawa, and Pinedo in [2] looks sufficient to study queues with customers and signals. A completely different approach, based on Stochastic Process Algebra, was proposed by Harrison [17,18]. The main results (CAT and RCAT theorems and their extensions [1,17,18]) give some sufficient conditions for product form stationary distributions. This technique clearly has a different range of applications as it allows us to represent component based models which are much more general and more detailed than networks of queues.

Here we use the detailed global balance technique because it looks easier in the context of a network of queues with failed components which change the routing mechanisms. We investigate G-networks of queues with signals which change the availability of a sub-network. Thus a service completion in one queue may lead to the fault of another part of the network. We generalize some of the results obtained by Sauer and Daduna [22] for ordinary queues to G-queues with signals. We also allow more general failure based on the state of the queues: that is, the so-called the structure function to be consistent with Fault Trees terminology. To the best of our knowledge it is the first application of G-networks to model systems with failure of components and we hope that this new result allows us to develop more applications.

Network of positive and negative customers were introduced to model neural networks where neurones exchange inhibitory and exciting signals [11,12]. G-networks and Random Neural Networks were also used in the design of the learning process for Cognitive Packet Networks [15] or application of the Random Neural Networks to quality of service [21]. Currently there are several hundred references devoted to the subject and two books [2,16] provide insight into some of the research issues, developments and applications in the area of networks of queues with customers and signals.

The technical part of the paper is organized as follows. In Section 2, we present the model and the assumptions about the signals and the failures of the subnetworks. Section 3 is devoted to the proof. For the sake of readability, the last steps of the proof are postponed in an appendix. We present some examples in Section 4 before the conclusions.

## 2. G-NETWORKS WITH UNRELIABLE NODES

We consider an open network of queues. The set of queues is partitioned into two subsets $S1$ and $S2$. Queues in $S1$ are reliable while queues in $S2$ are subjected to failures. All the queues have one server and the services are exponentially distributed with rate $\mu_i$ for queue $i$. The fresh arrival of customers in the queues follow independent Poisson processes with rate $\lambda_i$ for queue $i$ except when the system is down (see in the following the definition for a down system). Let $N2$ be the cardinal of $S2$.

The state of a queue in $S1$ (say queue $i$) is the number of customers in the queue and is denoted as $n_i$. The state is a queue in $S2$ (say $j$) has two components ($y_j$ and $n_j$):

* $y_j$ is a 0,1 value which is 0 when component $j$ is faulty, and 1 otherwise,

* $n_j$ is the number of customers in the queues.

We consider a structure function as for a Fault Tree [23], which is a mapping of $(0, 1)^{N2}$ to (TRUE, FALSE). The system is down when the structure function is TRUE, again like in a
<figure><img src="image_2.png" /><figcaption>FIGURE 1. Network of unreliable G-queues, the customer movements are represented with thin straight lines, the negative customers by thin dotted lines, the signals by thick dotted lines.</figcaption></figure>

Fault Tree. However, unlike in a Fault Tree, we do not assume that the structure function is coherent. Let $F(Y)$ be the structure function. The behavior of an arbitrary queue in $S2$ only depends on the value of the structure function. Such a structure function generalizes the conjunction function proposed in [22].

The network contains usual and negative customers, and two types of signal (see Fig. 1 for an exemple). The first type of signal change the value of $y_j$ to 1 when it arrived to queue $j$ in $S2$. It is denoted as a $T$ signal. The other type of signal, denoted as an $F$ signal changes the value of $y_j$ to 0. After changing the value of $y_j$, the signals disappear from the network immediately. If the value of $y_j$ was already the targeted value of the signal, it has no effect and it vanishes. Signals appear after a service completion of a customer in a queue of $S1$ and are routed to queues of $S2$.

Negative customers were introduced by Gelenbe in [9]. At their arrival, they delete a customer already in the queue and disappear immediately. If the queue is already empty, a negative customers disappears at its arrival. Without loss of generality we assume that there is no arrivals of negative customers or signals from the outside.

Positive customers are queued, they receive service or are deleted by negative customers. At the completion of a service, they move to another queue. More precisely, at the completion of its service in queue $i$ in $S1$, a customer may:

* route as a customer to a queue (say $k$) in $S1$ or $S2$ with probability $P_{i,k}$;

* route as a negative customer to a queue (say $k$) in $S1$ or $S2$ with probability $Q_{i,k}$;

* route as a $T$ signal to a queue (say $j$) in $S2$ with probability $T_{i,j}$;

* route as a $F$ signal to a queue (say $j$) in $S2$ with probability $F_{i,j}$;

* leave the system with probability $d_i$.
Of course the have the normalization: for all $i$ in $S1$

$$d_i + \sum_{k \in S1 \cup S2} P_{i,k} + \sum_{j \in S1 \cup S2} Q_{i,k} + \sum_{j \in S2} T_{i,j} + \sum_{j \in S2} F_{i,j} = 1. \quad (1)$$

The behavior of customers in queues of $S2$ is much simpler: at the completion of its service in queue $i$ in $S2$, a customer may:

* route as a customer to a queue (say $k$) in $S2$ with probability $P_{i,k}$;

* route as a negative customer to a queue (say $k$) in $S2$ with probability $Q_{i,k}$;

* leave the system with probability $d_i$.

We also have a normalization equation: for all $i$ in $S2$

$$d_i + \sum_{k \in S2} P_{i,k} + \sum_{k \in S2} Q_{i,k} = 1. \quad (2)$$

When the structure function is TRUE, the system is down and all the queues in $S2$ are blocked until the structure function becomes FALSE. No services are allowed and no arrivals of customers are possible (either from the outside or from the queue in $S1$, see below for the consequence of an arrival in that case). Thus is it not possible for a customer to leave a queue in $S2$ when this subnetwork is down. The only possible events are the reception of a $T$ signal or a $F$ signal which may change the structure function.

The movement of customers between queues depend on the nature of the customers (positive or negative) and the set of queues involved. The negative customers arriving in a down system are rejected with probability one. We also assume that the customers arriving from $S1$ or from the outside to subnetwork $S2$ when it is down, are rerouted to $S1$ or to the outside according to a distribution of probability. This distribution is the same for all customers and does not depend of the source of the customer. Let $r(i)$ be the probability that a customer arriving a to queue in $S2$ while the structure function is TRUE is rerouted to queue $i$ in $S1$. Similarly, let $r0$ be the probability that such a customer is routed to the outside and leaves the network. We clearly have

$$r0 + \sum_{i \in S1} r(i) = 1.$$

For the sake of readability and without loss of generality, we assume that there exist nor arrivals of signals neither arrivals of negative customers from the outside of the network.

### 3. MAIN RESULTS

Let $X_t$ be the processes defined by $(n_i(t))_{i \in S1}$, $(n_j(t))_{j \in S2}$. Let us denote by $Y_t$, the process $(y_j(t))_{j \in S2}$. Clearly, $(X_t, Y_t)$ is a Markov chain.

We also assume that if all queue in $S2$ receives both $F$ signals and $T$ signals: for all $j \in S2$,

$$\sum_{i \in S1} T(i, j) \neq 0 \quad \text{and} \quad \sum_{i \in S1} F(i, j) \neq 0.$$

This is a necessary condition for the irreducibility of the chain.

Notation: $e_i$ is an integer vector of the appropriate size the entries of which are all zero except entry $i$ which is equal to 1. $Y \odot (j, Lo)$ denotes the vector $Y$ with entry $j$ equals to value $Lo$.
THEOREM 3.1: Assume that $(X_t, Y_y)$ is ergodic, If the following relations hold

$$r(i) = \frac{\sum_{k \in S_2} \mu_k \rho_k P_{k,i}}{\sum_{j \in S_2} \lambda_j + \sum_{k \in S_1} \mu_k \rho_k \sum_{j \in S_2} P_{k,j}}, \quad (3)$$

and

$$r0 = \frac{\sum_{k \in S_2} \mu_k \rho_k d_k + \sum_{k \in S_2} \sum_{j \in S_2} \mu_j \rho_j Q_{j,k} + \sum_{k \in S_2} \sum_{j \in S_2} \mu_j \rho_j \rho_k Q_{j,k} + \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i \rho_j Q_{i,j}}{\sum_{j \in S_2} \lambda_j + \sum_{k \in S_1} \mu_k \rho_k \sum_{j \in S_2} P_{k,j}}, \quad (4)$$

then the Markov chain has a product form steady-state distribution. More precisely

$$\pi(X, Y) = C \prod_{i \in S_1} (1 - \rho_i)(\rho_i)^{x_i} \prod_{j \in S_2} (1 - \rho_j)(\rho_j)^{x_j} (\beta_j)^{y_j} (1 - \beta_j)^{1-y_j}, \quad (5)$$

where, C is a normalization constant and for all $i \in S_1$,

$$\rho_i = \frac{\lambda_i + \sum_{k \in S_1 \cup S_2} \mu_k \rho_k P_{k,i}}{\mu_i + \sum_{k \in S_1} \mu_k \rho_k Q_{k,i}}, \quad (6)$$

and for all $j \in S_2$,

$$\rho_j = \frac{\lambda_j + \sum_{k \in S_1 \cup S_2} \mu_k \rho_k P_{k,j}}{\mu_j + \sum_{k \in S_1 \cup S_2} \mu_k \rho_k Q_{k,j}}, \quad (7)$$

and for all $j \in S_2$,

$$\beta_j = \frac{\sum_{i \in S_1} \mu_i \rho_i T_{i,j}}{\sum_{i \in S_1} \mu_i \rho_i T_{i,j} + \sum_{i \in S_1} \mu_i \rho_i F_{i,j}}. \quad (8)$$

PROOF: it is based on the Chapman-Kolmogorov equation for the steady state. First, let us write the equation and then we will check the guessed solution given by Eqs. (6)-(8). Note that in the following equation all the terms implying a queue in subnetwork S2 must take into account if the subnetwork is operational or not. As the global balance equation is rather complex, we label all the terms. They receive a label with a L prefix for the left-hand side and with a R prefix with the right-hand side. The labels are then used to describe how we perform algebraic manipulations to avoid to write the loyal balance equation.

The first three terms of the left-hand side describe the arrivals of customers form the outside while the last two models the services. The arrivals occur without constraint in sub-network S1, but it is only possible to enter a queue in S2 when subnetwork S2 is operating. Finally, we have to take into account the fresh arrivals coming to subnetwork S2 which are rerouted to S1 (Term [L3]).

Let us now describe the right-hand side. The first three terms describe the arrivals in subnetwork S1 [R1], subnetwork S2 [R2], or subnetwork S1 after being rejected in S2 because it is not operational [R3]. The terms [R4] and [R5] represent the departure of
customers from respectively subnetwork S1 and S2.

$$
\begin{align*}
\pi(X, Y) & \left( \sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j \mathbf{1}_{\text{not F}(Y)} + \sum_{j \in S2} \lambda_j (1-r0) \mathbf{1}_{F(Y)} \right. & \left[ \text{L1,L2,L3} \right] \\
& \left. + \sum_{i \in S1} \mu_i \mathbf{1}_{\mathbf{x}_i > 0} + \sum_{j \in S2} \mu_j \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F}(Y)} \right) & \left[ \text{L4,L5} \right] \\
& = \sum_{i \in S1} \lambda_i \mathbf{1}_{\mathbf{x}_i > 0} \pi(X - e_i, Y) & \left[ \text{R1} \right] \\
& + \sum_{j \in S2} \lambda_j \mathbf{1}_{\mathbf{x}_j > 0} \pi(X - e_j, Y) \mathbf{1}_{\text{not F}(Y)} & \left[ \text{R2} \right] \\
& + \sum_{j \in S2} \lambda_j \sum_{i \in S1} \mathbf{1}_{\mathbf{x}_i > 0} \pi(X - e_i, Y) \mathbf{1}_{F(Y)} r(i) & \left[ \text{R3} \right] \\
& + \sum_{i \in S1} \mu_i d_i \pi(X + e_i, Y) & \left[ \text{R4} \right] \\
& + \sum_{j \in S2} \mu_j d_j \pi(X + e_j, Y) \mathbf{1}_{\text{not F}(Y)} & \left[ \text{R5} \right] \\
& + \sum_{i \in S1} \sum_{k \in S1} \mu_i P_{i,k} \pi(X + e_i - e_k, Y) \mathbf{1}_{\mathbf{x}_k > 0} & \left[ \text{R6} \right] \\
& + \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \pi(X + e_i + e_k, Y) & \left[ \text{R7} \right] \\
& + \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \pi(X + e_i, Y) \mathbf{1}_{\mathbf{x}_k = 0} & \left[ \text{R8} \right] \\
& + \sum_{j \in S2} \sum_{k \in S2} \mu_j P_{j,k} \pi(X + e_j - e_k, Y) \mathbf{1}_{\text{not F}(Y)} \mathbf{1}_{\mathbf{x}_k > 0} & \left[ \text{R9} \right] \\
& + \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \pi(X + e_j + e_k, Y) \mathbf{1}_{\text{not F}(Y)} & \left[ \text{R10} \right] \\
& + \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \pi(X + e_j, Y) \mathbf{1}_{\text{not F}(Y)} \mathbf{1}_{\mathbf{x}_k = 0} & \left[ \text{R11} \right] \\
& + \sum_{i \in S1} \sum_{j \in S2} \mu_i P_{i,j} \pi(X + e_i - e_j, Y) \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F}(Y)} & \left[ \text{R12} \right] \\
& + \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \pi(X + e_i + e_j, Y) \mathbf{1}_{\text{not F}(Y)} & \left[ \text{R13} \right] \\
& + \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \pi(X + e_i, Y) \mathbf{1}_{\text{not F}(Y)} \mathbf{1}_{\mathbf{x}_j = 0} & \left[ \text{R14} \right] \\
& + \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \pi(X + e_i, Y) \mathbf{1}_{F(Y)} & \left[ \text{R15} \right] \\
& + \sum_{i \in S1} \sum_{j \in S2} \sum_{k \in S1} \mu_i \pi(X + e_i - e_k, Y) P_{i,j} r(k) \mathbf{1}_{F(Y)} \mathbf{1}_{\mathbf{x}_k > 0} & \left[ \text{R16} \right]
\end{align*}
$$
$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i \pi(X + e_i, Y) P_{i,j} r 0 \mathbf{1}_{F(Y)} \quad [R17]$$

$$+ \sum_{j \in S2} \sum_{i \in S1} \mu_j P_{j,i} \pi(X + e_j - e_i, Y) \mathbf{1}_{\text{not F(Y)}} \mathbf{1}_{\mathbf{x}_i > 0} \quad [R18]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i T_{i,j} \mathbf{1}_{y_j=1} (\pi(X + e_i, Y \odot (j, 0)) + \pi(X + e_i, Y \odot (j, 1))) \quad [R19]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i F_{i,j} \mathbf{1}_{y_j=0} (\pi(X + e_i, Y \odot (j, 0)) + \pi(X + e_i, Y \odot (j, 1))). \quad [R20]$$

Terms [R6] to [R14] are associated to the same set of events, but differ by the subnetworks involved in the migration of customers. More precisely, Term [R6] models the end of service for a customer in S1 followed by a migration in S1. Terms [R7] and [R8] represent the end of service followed by a migration in S1 as a negative customer which succeeds [R7] or which fails because the queue is empty [R8]. Terms [R9] to [R11] models the same events for both queues in S2, while Terms [R12] to [R14] describe the same set of events when it is originated in S1 and the destination is in S2 and B is operational. Term [R15] models an end of service in S1 followed by a migration of a negative customer to S2 when subnetwork B is not operational. Remember that the negative customer is dropped. Similarly, Terms [R16] and [R17] model an end of service in S1 followed by a tentative of migration to a queue in S2 when subnetwork S2 is not operational. Thus, the customers are sent in another queue of S1 [R16] or sent to the outside [R17].

Term [R18] represents the migration of a customer from a queue in S2 to a queue in S1. Remember that there is no negative customer migration from S2 to S1. Finally, Terms [R19] and [R20] describe the generation of signals at the completion of a customer service in a queue of S1 moving to a queue of S2. The first one represents the T signal while the last one models the F signal.

We divide both terms by $\pi(X, Y)$ and use the multiplicative form for the steady-state solution (i.e., Eq. (5)) and perform the following simplifications:

$$\frac{\pi(X + e_i, Y)}{\pi(X, Y)} = \rho_i, \quad \frac{\pi(X, Y \odot (j, 1))}{\pi(X, Y)} = \mathbf{1}_{y_j=1} + \frac{\beta_j}{1 - \beta_j} \mathbf{1}_{y_j=0}, \\ \frac{\pi(X, Y \odot (j, 0))}{\pi(X, Y)} = \mathbf{1}_{y_j=0} + \frac{1 - \beta_j}{\beta_j} \mathbf{1}_{y_j=1}, \quad \frac{\pi(X + e_i, 1)}{\pi(X, Y)} = \rho_i \left( \mathbf{1}_{y_j=1} + \frac{\beta_j}{1 - \beta_j} \mathbf{1}_{y_j=0} \right).$$

$$\sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j \mathbf{1}_{\text{not F(Y)}} + \sum_{j \in S2} \lambda_j (1 - r0) \mathbf{1}_{F(Y)} \quad [L1,L2,L3]$$

$$+ \sum_{i \in S1} \mu_i \mathbf{1}_{\mathbf{x}_i > 0} + \sum_{j \in S2} \mu_j \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F(Y)}} \quad [L4,L5]$$

$$= \sum_{i \in S1} \lambda_i \frac{1}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \quad [R1]$$

$$+ \sum_{j \in S2} \lambda_j \frac{1}{\rho_j} \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F(Y)}} \quad [R2]$$

$$+ \sum_{j \in S2} \lambda_j \sum_{i \in S1} \frac{1}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \mathbf{1}_{F(Y)} r(i) \quad [R3]$$
$$+ \sum_{i \in S_1} \mu_i d_i \rho_i \qquad [R4]$$

$$+ \sum_{j \in S_2} \mu_j d_j \rho_j \mathbf{1}_{\text{not F(Y)}} \qquad [R5]$$

$$+ \sum_{i \in S_1} \sum_{k \in S_1} \mu_i P_{i,k} \frac{\rho_i}{\rho_k} \mathbf{1}_{\mathbf{x}_k > 0} \qquad [R6]$$

$$+ \sum_{i \in S_1} \sum_{k \in S_1} \mu_i Q_{i,k} \rho_i \rho_k \qquad [R7]$$

$$+ \sum_{i \in S_1} \sum_{k \in S_1} \mu_i Q_{i,k} \rho_i \mathbf{1}_{\mathbf{x}_k = 0} \qquad [R8]$$

$$+ \sum_{j \in S_2} \sum_{k \in S_2} \mu_j P_{j,k} \frac{\rho_j}{\rho_k} \mathbf{1}_{\text{not F(Y)}} \mathbf{1}_{\mathbf{x}_k > 0} \qquad [R9]$$

$$+ \sum_{j \in S_2} \sum_{k \in S_2} \mu_j Q_{j,k} \rho_j \rho_k \mathbf{1}_{\text{not F(Y)}} \qquad [R10]$$

$$+ \sum_{j \in S_2} \sum_{k \in S_2} \mu_j Q_{j,k} \rho_j \mathbf{1}_{\mathbf{x}_k = 0} \mathbf{1}_{\text{not F(Y)}} \qquad [R11]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i P_{i,j} \frac{\rho_i}{\rho_j} \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F(Y)}} \qquad [R12]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i Q_{i,j} \rho_j \rho_i \mathbf{1}_{\text{not F(Y)}} \qquad [R13]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i Q_{i,j} \rho_i \mathbf{1}_{\text{not F(Y)}} \mathbf{1}_{\mathbf{x}_j = 0} \qquad [R14]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i Q_{i,j} \rho_i \mathbf{1}_{\mathbf{F(Y)}} \qquad [R15]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \sum_{k \in S_1} \mu_i \frac{\rho_i}{\rho_k} P_{i,j} r(k) \mathbf{1}_{\mathbf{F(Y)}} \mathbf{1}_{\mathbf{x}_k > 0} \qquad [R16]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i P_{i,j} r(0) \mathbf{1}_{\mathbf{F(Y)}} \qquad [R17]$$

$$+ \sum_{j \in S_2} \sum_{i \in S_1} \mu_j P_{j,i} \frac{\rho_j}{\rho_i} \mathbf{1}_{\text{not F(Y)}} \mathbf{1}_{\mathbf{x}_i > 0} \qquad [R18]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i T_{i,j} \mathbf{1}_{\mathbf{y}_j = 1} \left(1 + \frac{1 - \beta_j}{\beta_j}\right) \qquad [R19]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i F_{i,j} \mathbf{1}_{\mathbf{y}_j = 0} \left(1 + \frac{\beta_j}{1 - \beta_j}\right). \qquad [R20]$$

Some results are proved in the following Lemmas. The complete proof is postponed in an appendix. ■
LEMMA 3.1: We have:

$$[\text{R19}] + [\text{R20}] = \sum_{j \in S2} \sum_{i \in S1} \mu_i \rho_i (T_{i,j} + F_{i,j}).$$

Let us now consider Eq. (8) which defines $\beta_j$. After substitution in [R19] we get:

$$\sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i T_{i,j} \mathbf{1}_{\mathbf{y}_j=1} \left(\frac{1}{\beta_j}\right) = \sum_{j \in S2} \mathbf{1}_{\mathbf{y}_j=1} \left(\frac{1}{\beta_j}\right) \sum_{i \in S1} \mu_i \rho_i T_{i,j} \\ = \sum_{j \in S2} \mathbf{1}_{\mathbf{y}_j=1} \left(\sum_{i \in S1} \mu_i \rho_i T_{i,j} + \sum_{i \in S1} \mu_i \rho_i F_{i,j}\right).$$

Similarly, with [R20], we get:

$$\sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i F_{i,j} \mathbf{1}_{\mathbf{y}_j=0} \left( \frac{1}{1 - \beta_j} \right) = \sum_{j \in S2} \mathbf{1}_{\mathbf{y}_j=0} \left( \sum_{i \in S1} \mu_i \rho_i T_{i,j} + \sum_{i \in S1} \mu_i \rho_i F_{i,j} \right).$$

As $\mathbf{1}_{\mathbf{y}_j=0} + \mathbf{1}_{\mathbf{y}_j=1} = 1$ for all states, the proof is complete.

PROPERTY 3.1: Clearly, $\mathbf{1}_{\mathbf{x}_k=0} = 1 - \mathbf{1}_{\mathbf{x}_k>0}$. Thus we substitute this trivial relation in all the terms containing $\mathbf{1}_{\mathbf{x}_k=0}$. The negative terms are moved to the left-hand side. The property is applied to [R14], R[11] and [R8].

Application to [R14]:

$$[\text{R14}] = \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \rho_i \mathbf{1}_{\text{not } \mathbf{F}(Y)} \mathbf{1}_{\mathbf{x}_j=0} \\ = \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \rho_i \mathbf{1}_{\text{not } \mathbf{F}(Y)} - \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \rho_i \mathbf{1}_{\text{not } \mathbf{F}(Y)} \mathbf{1}_{\mathbf{x}_j>0}.$$

The first term is gathered with [R15] to get

$$[\text{R15}] = \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \rho_i,$$

and [R14] is canceled. The second term is moved to the left-hand side and added with [L5].

$$[\text{L5}] = \sum_{j \in S2} \mathbf{1}_{\mathbf{x}_j>0} \mathbf{1}_{\text{not } \mathbf{F}(Y)} (\mu_j + \sum_{i \in S1} \mu_i Q_{i,j} \rho_i).$$

Application to [R11]:

We perform the same operation and we get a new value for [L5] and [R11].

$$[\text{R11}] = \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \rho_j \mathbf{1}_{\text{not } \mathbf{F}(Y)}.$$

The second term is moved to the left-hand side and added with [L5] after a permutation of indices.

$$[\text{L5}] = \sum_{j \in S2} \mathbf{1}_{\mathbf{x}_j>0} \mathbf{1}_{\text{not } \mathbf{F}(Y)} \left( \mu_j + \sum_{i \in S1} \mu_i \rho_i Q_{i,j} + \sum_{k \in S2} \mu_k \rho_k Q_{k,j} \right).$$

Application to [R8]:
With a similar manipulation, we obtain:

$$[\text{R8}] = \sum_{i \in S1} \sum_{k \in S1} \mu_i \rho_i Q_{i,k}$$

The second term is moved to the left-hand side and added with [L5] after a permutation of indices.

$$[\text{L4}] = \sum_{i \in S1} \mathbf{1}_{\mathbf{x}_i > 0} \left( \mu_j + \sum_{i \in S1} \mu_k \rho_k Q_{k,i} \right).$$

We now show how the rerouting probabilities when the subnetwork is down can be taken into account. Let us begin with $r(i)$.

**PROPERTY 3.2:** Let us add [R3] and [R16] and factorize after a permutation of indices.

$$[\text{R3}] + [\text{R16}] = \mathbf{1}_{\mathbf{F}(\mathbf{Y})} \sum_{i \in S1} \frac{r(i)}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \left( \sum_{j \in S2} \lambda_j + \sum_{k \in S1} \sum_{j \in S2} \mu_k \rho_k P_{k,j} \right).$$

After substitution of the value of $r(i)$ from Eq. (3), we get:

$$[\text{R3}] + [\text{R16}] = \mathbf{1}_{\mathbf{F}(\mathbf{Y})} \sum_{i \in S1} \frac{1}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \sum_{j \in S2} \mu_j \rho_j P_{j,i}.$$

After addition with [R18], the step function $\mathbf{1}_{\mathbf{F}(\mathbf{Y})}$ vanishes:

$$[\text{R3}] + [\text{R16}] + [\text{R18}] = \sum_{i \in S1} \frac{1}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \sum_{j \in S2} \mu_j \rho_j P_{j,i}.$$

Consider now $r0$

**PROPERTY 3.3:** In a first step, we rewrite [L3] as follows:

$$[\text{L3}] = \sum_{j \in S2} \lambda_j (1 - r0) \mathbf{1}_{\mathbf{F}(\mathbf{Y})} = \sum_{j \in S2} \lambda_j \mathbf{1}_{\mathbf{F}(\mathbf{Y})} - \sum_{j \in S2} \lambda_j r0 \mathbf{1}_{\mathbf{F}(\mathbf{Y})}.$$

The first term is added to [L2] which becomes $\sum_{j \in S2} \lambda_j$. The second term is moved to the right-hand side and added to [R17] which becomes:

$$[\text{R17}] = \sum_{j \in S2} \mathbf{1}_{\mathbf{F}(\mathbf{Y})} r(0) \left( \lambda_j + \sum_{i \in S1} \mu_i \rho_i P_{i,j} \right).$$

Taking into account the definition of $r0$ in Eq. (4) we get:

$$[\text{R17}] = \mathbf{1}_{\mathbf{F}(\mathbf{Y})} \left( \sum_{k \in S2} \mu_k \rho_k d_k + \sum_{k \in S2} \sum_{j \in S2} \mu_j \rho_j Q_{jk} + \sum_{k \in S2} \sum_{j \in S2} \mu_j \rho_j \rho_k Q_{jk} + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j Q_{ij} \right).$$
The first term is added to [R5] to obtain:

$$[\text{R5}] = \sum_{j \in S2} \mu_j d_j \rho_j.$$

The second term is added to [R11] and we get (do not forget that [R11] has already been changed using Property 3.1):

$$[\text{R11}] = \sum_{j \in S2} \sum_{k \in S2} \mu_j \rho_j Q_{j,k}.$$

The third term is added to [R10] which becomes:

$$[\text{R10}] = \sum_{j \in S2} \sum_{k \in S2} \mu_j \rho_j \rho_k Q_{j,k}.$$

Finally, the fourth term is added to [R13] and we get:

$$[\text{R13}] = \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j Q_{i,j}.$$

It is important to remark that after this step, all the step function $1_{\text{F(Y)}}$ or $1_{\text{not F(Y)}}$ have disappeared from the balance equation.

LEMMA 3.2: The following relation (i.e., Eq. (9)) is the flow equation of the model.

$$\sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j = \sum_{i \in S1} \mu_i \rho_i d_i + \sum_{j \in S2} \mu_j \rho_j d_j + \sum_{i \in S1} \sum_{k \in S1} \mu_i \rho_i \rho_k Q_{i,k} + \sum_{i \in S1} \sum_{k \in S1} \mu_i \rho_i Q_{i,k} \\ + \sum_{j \in S2} \sum_{k \in S2} \mu_j \rho_j \rho_k Q_{j,k} + \sum_{j \in S2} \sum_{k \in S2} \mu_j \rho_j Q_{j,k} + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j Q_{i,j} \\ + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i Q_{i,j} + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j (T_{i,j} + F_{i,j}). \quad (9)$$

Note that this equation has a simple physical interpretation. Assume that the structure function is always FALSE. The left-hand side describes the arrivals of customer from the outside in both subnetworks while the right-hand side describe the various ways a customer can leave the network and go back to the outside: usual departure, deletion by a negative customers, transformation into a negative customer and transformation into a signal.

PROOF: Consider Eq. (6). After multiplication of both sides of the equation by the denominator and summation for all $i \in S1$ we get:

$$\sum_{i \in S1} \mu_i \rho_i + \sum_{i \in S1} \sum_{k \in S1} \mu_k \rho_k \rho_i Q_{k,i} = \sum_{i \in S1} \lambda_i + \sum_{i \in S1} \sum_{k \in S1} \mu_k \rho_k P_{k,i} + \sum_{i \in S1} \sum_{k \in S2} \mu_k \rho_k P_{k,i}$$

Similarly, using Eq. (7) for all $j \in S2$,

$$\sum_{j \in S2} \mu_j \rho_j + \sum_{j \in S2} \sum_{k \in S1} \mu_k \rho_k Q_{k,j} \rho_j + \sum_{j \in S2} \sum_{k \in S2} \mu_k \rho_k Q_{k,j} \rho_j \\ = \sum_{j \in S2} \lambda_j + \sum_{j \in S2} \sum_{k \in S1} \mu_k \rho_k P_{k,j} + \sum_{j \in S2} \sum_{k \in S2} \mu_k \rho_k P_{k,j}$$
Thus, after reordering, and some permutation of indices,

$$ \sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j = \sum_{i \in S1} \mu_i \rho_i \left( 1 - \sum_{k \in S1} P_{i,k} - \sum_{k \in S2} P_{i,k} \right) \\ + \sum_{j \in S2} \mu_j \rho_j \left( 1 - \sum_{k \in S1} P_{j,k} - \sum_{k \in S2} P_{j,k} \right) + \sum_{i \in S1} \sum_{k \in S1} \mu_i \rho_i \rho_k Q_{i,k} \\ + \sum_{j \in S2} \sum_{k \in S2} \mu_j \rho_j \rho_k Q_{j,k} + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j Q_{i,j} \quad (10) $$

After substitution using the normalization equations (i.e., Eqs. (1) and (2)) we get Eq. (9). ■

And to complete the characterization of the steady-state distribution, one can easily obtain the two following properties.

**PROPERTY 3.4:** *The normalization constant C is equal to 1.*

**PROOF:** By summation for the probability for all the states of the Markov chain. ■

**PROPERTY 3.5:** *The parameters $\rho_i$, $i \in S1$ and $\rho_j$ for $j \in S2$ can be computed with the envelope algorithm presented in [5].*

**PROOF:** Indeed, even if the model is quite different, the flow equation on parameters $\rho_i$, $i \in S1$ and $\rho_j$ for $j \in S2$ are the same that the ones studied by Gelenbe for networks of queues with negative customers [9]. The algorithm developed in [5] is proved to solve these flow equations and it can be used here. The fact that several models of queues with signals may exhibit the same flow equations had already been mentioned in [6] and it was suggested that it can give some highlights on the models which have a steady-state distribution with a multiplicative form. ■

It is worthy to remark that the way that the parameters $r0$ and $r(i)$ are related to the loads of the queues has a physical interpretation. Indeed, combining the normalization of probabilities with Eqs. (3) and (4), we obtain:

$$ \sum_{j \in S2} \lambda_j + \sum_{k \in S1} \mu_k \rho_k \sum_{j \in S2} P_{k,j} = \sum_{i \in S1} \sum_{k \in S2} \mu_k \rho_k P_{k,i} + \sum_{k \in S2} \mu_k \rho_k d_k + \sum_{k \in S2} \sum_{j \in S2} \mu_j \rho_j Q_{j,k} \\ + \sum_{k \in S2} \sum_{j \in S2} \mu_j \rho_j \rho_k Q_{j,k} + \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i \rho_j Q_{i,j}, $$

and this relation is a flow equation for subnetwork $S2$ when it is operational. The left-hand side describes the incoming customers (either fresh customers or migration from $S1$), while the right-hand side represents all the possibilities for a customer to leave $S2$ either by a deletion due to the arrival of a negative customer coming from $S1$ or $S2$, or after a service followed by a migration, a departure, or a transformation into a negative customer. Clearly, these assumptions on $r0$ and $r(i)$ make the flows during periods of failures consistent with the lows during availability periods.
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Topology for Example 1: the customer movements are represented with thin straight lines, the negative customers by thin dotted lines, the signals by thick dotted lines.</figcaption></figure>

# 4. EXAMPLES

We present two examples to describe in a more detailed manner the various possibilities for the structure function and the rerouting mechanisms.

## 4.1. Rejecting Positive Customers in a Blocked Sub-Network

In this first example, we present a model where the structure function is more complex than a simple conjunction and a routing matrix which implies that the positive customers are rejected when the sub-network is not operational. More precisely, we assume that subnets $S1$ and $S2$ contain respectively 2 and 3 queues (see Fig. 2), labeled 1 to 2 for $S1$ and 3 to 5 for $S2$. We also assume that the structure function is $y_4 OR (y_5 AND y_3)$. This is typically a structure function associated with a Fault Tree and it is much more general than a conjunction of the boolean values.

We assume that there is no positive customer migration from $S2$ to $S1$: $P_{j,i} = 0$ for all $j$ in $S2$ and $i$ in $S1$. Therefore, according to Eqs. (4) and (3), we have $r(i) = 0$ for all $i$ in $S1$ and $r0 = 1$ because of the normalization. All the customers sent to $S2$ are rejected when $S2$ is not operational.

For that model, the fixed point equation on $\rho_k$ becomes: for all $i \in S1$,

$$ \rho_i = \frac{\lambda_i + \sum_{k=1}^{2} \mu_k \rho_k P_{k,i}}{\mu_i + \sum_{k=1}^{2} \mu_k \rho_k Q_{k,i}}, \quad (11) $$

and for all $j \in S2$,

$$ \rho_j = \frac{\lambda_j + \sum_{k=1}^{2} \mu_k \rho_k P_{k,j}}{\mu_j + \sum_{k=1}^{5} \mu_k \rho_k Q_{k,j}}, \quad (12) $$

This is a generalization of the stalling model on G-queues with signals. Note however that the signals are not interrupted when $S2$ is not available, unlike positive and negative customers.
<figure><img src="image_4.png" /><figcaption>FIGURE 3. Network of unreliable G-queues, the customer movements are represented with thin straight lines, the negative customers by thin dotted lines, the signals by thick dotted lines.</figcaption></figure>

## 4.2. A System with Signal Feedback

We consider a network with 4 queues partitioned into two subsets (queues 1 and 2 in S1, queues 3 and 4 in S2) as depicted in Fig. 3. We assume that there is no arrival of fresh customers in S1 (i.e., for all i in S1, $λ_i = 0$). To obtain an irreducible Markov chain, we add that $λ_j > 0$ for all $j ∈ S2$ and that for all i in S1 there exists a directed path from a queue in S2 to queue i for a positive customer (i.e., in matrix P).

Negative customers are restricted to migrate inside the subnetworks where they have been created. Thus, the only interaction between the subnetworks are:

* a flow of T and F signals from S1 to S2,

* a flow of positive customers from S2 to S1.

Inside subnetworks, there exist migrations of positive and negative customers. Of course according to the rerouting mechanism, when subnetwork S2 is not operational, the arrivals of fresh customers are rerouted to S1. The probabilities $r0$ and $r(i)$ are simplified to take into account the assumptions on the routing matrices:

$$r(i) = \frac{\mu_3 \rho_3 P_{3,i} + \mu_4 \rho_4 P_{4,i}}{\lambda_3 + \lambda_4}, \qquad (13)$$

and

$$r0 = \frac{\sum_{k=3}^{4} \mu_k \rho_k d_k + \sum_{k=3}^{4} \sum_{j=3}^{4} \mu_j \rho_j Q_{j,k} + \sum_{k=3}^{4} \sum_{j=3}^{4} \mu_j \rho_j \rho_k Q_{j,k}}{\lambda_3 + \lambda_4}, \qquad (14)$$

Such a network exhibits an unusual behavior. Assume that subnetwork S2 is backlogged and subnetwork S1 is empty. Some customers may be routed to S1 at the end of a service in S2. Thus after a delay (i.e., service time) they return to S2 as a F signal which makes subnetwork S2 fails. This sequence of events describes how a service in S2 provokes, in a probabilistic manner and after some delays, a failure of subnetwork S2.

Not the that the chain is still irreducible because it is still possible to receive a T signal sent after a service in S1. The customer which becomes a T signal may have joined
a queue in $S1$ from the outside, even if the arrival rate of fresh customers is 0. Indeed, as subnetwork $S2$ is not available, fresh customers trying to reach $S2$ are rerouted with a positive probability to $S1$.

## 5. CONCLUSION

Negative customers have previously been used to describe failed customers [19], but it is the first time, to the best of our knowledge that signals are used to model the failure of a queue or a subset of a network provoked by another part of the network. The failure of a subnetwork can be generalized easily in several directions. First, it is possible to consider several subnetworks associated with several structure function and the network still have a product form solution when it is ergodic. It is also possible to consider closed topology for $S2$ if we assume that there are no negative customers in $S2$ (it is sufficient to consider that $Q_{k,j} = 0$ for all $j$ in $S2$ and $k$ in $S1 \cup S2$).

Another possible generalization consists in allowing a more complex routing mechanism (i.e., for instance, which can be state dependent). Remember that is this paper, $r(i)$ does not depend of the queue which is targeted by the customer. We are investigating how we can make this probability dependent of all the queues involved in the re-routing process and how we can make some re-routing for the negative customers. To the best of our knowledge such a result does not exist in the literature on G-networks.

## References

1. Balsamo, S., Harrison, P.G. & Marin, A. (2010). A unifying approach to product-forms in networks with finite capacity constraints. In Vishal Misra, Paul Barford, & Mark S. Squillante, (eds.), *SIGMETRICS 2010, Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems*, New York: ACM, pp. 25–36.

2. Chao, X., Miyazawa, M. & Pinedo, M. (1999). *Queueing networks customers, signals and product form solutions*. Chichester: John Wiley & Sons.

3. Dao-Thi, T.-H., Fourneau, J.-M. & Tran, M.-A. (2010). Networks of symmetric multi-class queues with signals changing classes. In Khalid Al-Begain, Dieter Fiems, & Knottenbelt, W.J. (eds.), *Analytical and Stochastic Modeling Techniques and Applications, 17th International Conference, ASMTA 2010*, , vol. 6148 of *Lecture Notes in Computer Science*, Cardiff, UK: Springer, pp. 72–86.

4. Dao-Thi, T.-H., Fourneau, J.-M. & Tran, M.-A. (2013). Network of queues with inert customers and signals. In *7th International Conference on Performance Evaluation Methodologies and Tools, ValueTools '13*, Italy: ICST/ACM, pp. 155–164.

5. Fourneau, J.-M. (1991). Computing the steady-state distribution of networks with positive and negative customers. In *13th IMACS World Congress on Computation and Applied Mathematics*, Dublin.

6. Fourneau, J.-M. & Gelenbe, E. (2004). Flow equivalence and stochastic equivalence in g-networks. *Computational Management Science* 1(2): 179–192.

7. Fourneau, J.-M., Kloul, L. & Quessette, F. (1995). Multiple class G-Networks with jumps back to zero. In *MASCOTS '95: Proceedings of the 3rd International Workshop on Modeling, Analysis, & Simulation of Computer and Telecommunication Systems*, Washington, DC, USA: IEEE Computer Society, pp. 28–32.

8. Fourneau, J.-M., Kloul, L. & Quessette, F. (2000). Multiple class G-networks with iterated deletions. *Performance Evaluation* 42(1): 1–20.

9. Gelenbe, E. (1991). Product-form queuing networks with negative and positive customers. *Journal of Applied Probability* 28: 656–663.

10. Gelenbe, E. (1993). G-networks with instantaneous customer movement. *Journal of Applied Probability* 30(3): 742–748.

11. Gelenbe, E. (1994). G-networks: An unifying model for queuing networks and neural networks. *Annals of Operations Research* 48(1–4): 433–461.

12. Gelenbe, E. & Fourneau, J.-M. (1999). Random neural networks with multiple classes of signals. *Neural Computation* 11(4): 953–963.
13. Gelenbe, E. & Fourneau, J.-M. (2002). G-networks with resets. Performance Evaluation 49(1-4): 179-191.

14. Gelenbe, E. & Labed, A. (1998). G-networks with multiple classes of signals and positive customers. European Journal of Operations Research 108: 293-305.

15. Gelenbe, E., Lent, R. & Xu, Z. (2001). Design and performance of cognitive packet networks. Performance Evaluation 46(2-3): 155-176.

16. Gelenbe, E. & Mitrani, I. (2010). Analysis and synthesis of computer systems. London: Imperial College Press.

17. Harrison, P.G. (2004). Compositional reversed Markov processes, with applications to G-networks. Performance Evaluation 57(3): 379-408.

18. Harrison, P.G. (2003). Turning back time in Markovian process algebra. Theoretical Computer Science 290(3): 1947-1986.

19. Hernandez, M. & Fourneau, J-M. (1993). Modelling defective parts in a fow system using G-Networks. In International Conference on performability, Mont Saint-Michel.

20. Kelly, F.P. (1987). Reversibility and stochastic networks. Chichester: Wiley.

21. Mohamed, S., Rubino, G. & Varela, M. (2004). Performance evaluation of real-time speech through a packet network: a random neural networks-based approach. Performance Evaluation 57(2): 141-161.

22. Sauer, C. & Daduna, H. (2003). Availability formulas and performance measures for separable degradable networks. Economic Quality Control 18(2): 165-194.

23. Trivedi, K.S. (2002). Probability and Statistic with Reliability, Queueing and Computer Science Applications, 2nd ed. New York: Wiley.

APPENDIX

After taking into account Lemmas 3.1, and 3.2 and Properties 3.1 and 3.2 the global balance equation becomes:

$$ \sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j + \sum_{i \in S1} \mathbf{1}_{\mathbf{x}_i > 0} \left( \mu_i + \sum_{k \in S1} \mu_k \rho_k Q_{k,i} \right) \quad [L1,L2,L4] $$

$$ + \sum_{j \in S2} \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not } \mathbf{F}(\mathbf{Y})} \left( \mu_j + \sum_{i \in S1} \mu_i \rho_i Q_{i,j} + \sum_{k \in S2} \mu_k \rho_k Q_{k,i} \right) \quad [L5] $$

$$ = \sum_{i \in S1} \lambda_i \frac{1}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \quad [R1] $$

$$ + \sum_{j \in S2} \lambda_j \frac{1}{\rho_j} \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not } \mathbf{F}(\mathbf{Y})} \quad [R2] $$

$$ + \sum_{i \in S1} \mu_i d_i \rho_i \quad [R4] $$

$$ + \sum_{j \in S2} \mu_j d_j \rho_j \quad [R5] $$

$$ + \sum_{i \in S1} \sum_{k \in S1} \mu_i P_{i,k} \frac{\rho_i}{\rho_k} \mathbf{1}_{\mathbf{x}_k > 0} \quad [R6] $$

$$ + \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \rho_i \rho_k \quad [R7] $$

$$ + \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \rho_i \quad [R8] $$
$$+ \sum_{j \in S2} \sum_{k \in S2} \mu_j P_{j,k} \frac{\rho_j}{\rho_k} \mathbf{1}_{\text{not F(Y)}} \mathbf{1}_{\mathbf{x}_k > 0} \quad [R9]$$

$$+ \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \rho_j \rho_k \quad [R10]$$

$$+ \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \rho_j \quad [R11]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i P_{i,j} \frac{\rho_i}{\rho_j} \mathbf{1}_{\mathbf{x}_j > 0} \mathbf{1}_{\text{not F(Y)}} \quad [R12]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i Q_{i,j} \rho_j \rho_i \quad [R13]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i Q_{i,j} \quad [R15]$$

$$+ \sum_{j \in S2} \sum_{i \in S1} \mu_j P_{j,i} \frac{\rho_j}{\rho_i} \mathbf{1}_{\mathbf{x}_i > 0} \quad [R18]$$

$$+ \sum_{i \in S1} \sum_{j \in S2} \mu_i \rho_i (T_{i,j} + F_{i,j}) \quad [R19]$$

We now substitute the solution for $\rho_i$ for all $i$ in $S1$. Remember that:

$$\rho_i = \frac{\lambda_i + \sum_{k \in S1 \cup S2} \mu_k \rho_k P_{k,i}}{\mu_i + \sum_{k \in S1} \mu_k \rho_k Q_{k,i}},$$

After substitution, Term [L4] cancels with Terms [R1], [R6] and [R18]. Similarly, the definition of $\rho_j$ for $j$ in $S2$ implies that Term [L5] cancels with Terms [R2], [R9] and [R12]. Finally we get:

$$\sum_{i \in S1} \lambda_i + \sum_{j \in S2} \lambda_j \quad [L1,L2, ]$$

$$= \sum_{i \in S1} \mu_i d_i \rho_i \quad [R4]$$

$$+ \sum_{j \in S2} \mu_j d_j \rho_j \quad [R5]$$

$$+ \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \rho_i \rho_k \quad [R7]$$

$$+ \sum_{i \in S1} \sum_{k \in S1} \mu_i Q_{i,k} \rho_i \quad [R8]$$

$$+ \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \rho_j \rho_k \quad [R10]$$

$$+ \sum_{j \in S2} \sum_{k \in S2} \mu_j Q_{j,k} \rho_j \quad [R11]$$
$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i Q_{i,j} \rho_j \rho_i \qquad [R13]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i Q_{i,j} \qquad [R15]$$

$$+ \sum_{i \in S_1} \sum_{j \in S_2} \mu_i \rho_i (T_{i,j} + F_{i,j}) \qquad [R19]$$

And this is the flow equation stated in Lemma 3.2. This completes the proof.