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

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

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

DISTRIBUTION OF THE FLOWS
IN A GENERAL
JACKSON NETWORK

Jacques LABETOULLE
Guy PUJOLLE
Christine SOULA

Rapport de Recherche N° 341

Janvier 1979

<figure><img src="image_3.png" /></figure>
DISTRIBUTION OF THE FLOWS IN A GENERAL JACKSON NETWORK

Jacques Labetoulle, Guy Pujolle, Christine Soula

Résumé :

Des systèmes de files d'attente du type «Jackson» sont considérés dans cet article. Les distributions des intervalles de temps entre deux entrées et entre deux sorties sont calculées pour une file M/M/1 avec rebouclage, un système de deux files d'attente en série avec rebouclage et un réseau de deux stations entièrement interconnecté. Finalement nous montrons l'égalité des deux précédentes distributions pour chaque file d'un réseau de Jackson général. Nous analysons également la distribution des intervalles de temps entre deux rebouclages dans deux modèles particuliers.

Abstract :

Several queueing systems with feedback are analyzed in this paper. We obtain the distribution of the interinput times and interoutput times for a M/M/1 queue with feedback, a two tandem queues system with feedback and a particular open network with two stations interconnected. And finally we show the equality of the distributions of the interinput times and interoutput times for any queue in a general Jackson Network. We also analyze the distribution of the interfeedback times in two particular models.
## INTRODUCTION

It has been shown since a long time [1] that the output of a M/M/1 queue in equilibrium is a Poisson process. Consequently, analysis of a general queueing network with exponential servers and with Poisson input streams has often been considered as easy, inasmuch as the queue length probabilities in steady state are in a product form. This product form asserts that the queue lengths are mutually independent, and have the same equilibrium probabilities as those of M/M/1 queues. This form can let one believe that the traffic between two stations is a Poisson process. This conjecture is true for a flow when there are no feedback customers but false in the other cases [2] [3]. However a property is preserved : the distributions of interinput times and interoutput times are identical. This is the main result we prove for the so-called Jackson Networks (JN).

This result can be considered as a generalization of the studies of Burke [4] and Disney and McNickle [5]; their works are mainly based upon a M/M/1 queue with Bernoulli feedback. They show that for this unique station the distributions of the interinput times and interoutput times are identical. Our method allows to obtain also the distribution of the flows in a general network.

In a first part we study again the M/M/1 queue with feedback by our new approach and we obtain the exact distribution of interfeedback times.

In a second part we show that the equality of the distribution of the interinput and interoutput times in a two tandem queues with feedback is still true.

In the part III, we consider a particular Jackson Network with two input sources and two departures points and we prove our assertion is still true. We also calculate the distribution of the interfeedback times for some particular values of the parameters.

Finally, in part IV we consider a general JN with a set of n
service stations interconnected. All this part is devoted to prove the
equality between the distributions of the interinput times and interoutput
times for any queue of the network.

# I. M/M/1 queue with Bernoulli feedback

## I.1. Model and notations

<figure><img src="image_4.png" /><figcaption>Figure 1 : the M/M/1 queue with feedback</figcaption></figure>

The problem to be studied is illustrated on Figure 1. The
arrival process is a Poisson process with parameter $\lambda$. The queueing
discipline is "first come, first served", and the service is
exponential with parameter $\mu$. Upon completion of a service, the customer
engages a Bernoulli switch : with fixed probability $q$, he leaves
definitively the system and with probability $p = 1-q$, he rejoins the queue.
The feedback is assumed to be instantaneous. We denote the traffic
intensity by $\rho = \frac{\lambda}{\mu q}$.

The times of service completions will be called "outputs". Exits
from the system will be called "departures". Similarly, "inputs" and
"arrivals" will be the moments when customers join the queue (from outside
or due to a feedback), and enter from outside respectively.

We adopt the following notations :

$A(t)$ : distribution function of the interinput times

$$ \hat{a}(s) = \int_{0}^{\infty} e^{-st} dA(t) $$

$F(t)$ : distribution function of the interoutput times

$$ \hat{f}(s) = \int_{0}^{\infty} e^{-st} dF(t) $$
$S(t)$ : distribution function of the interdeparture times

$R(t)$ : distribution function of the interfeedback times

$$ \hat{r}(s) = \int_{0}^{\infty} e^{-st} dR(t) $$

$$ \hat{b}(s) = \mu/\mu+s $$

## 1.2. Recall of previous results

### 1.2.1. The input process

The following results have been obtained by P. BURKE [4], and R. DISNEY, D. MCNICKLE [5].

Let $G(t)$ be the probability for the only customer arriving between times $t_0$ and $(t_0+t)$ to be a feedback customer if $t_0$ is the time of any input. We have : (see [4])

$$ (1) \qquad 1-A(t) = e^{-\lambda t}[1-G(t)] $$

and if we use the L.S.T. (Laplace-Stieltjes Transformed), (1) can be transformed to :

$$ (2) \qquad \hat{a}(s) = \frac{\lambda}{\lambda+s} [1-\hat{g}(\lambda+s)] + \hat{g}(\lambda+s) $$

$$ \text{where } \hat{g}(s) = \int_{0}^{\infty} e^{-st} dG(t) $$

It can be showed (see [1]) that :

$$ (3) \qquad \hat{g}(s) = \frac{p\hat{b}(s)}{1-q\hat{b}(s)} $$

Therefore

$$ (4) \qquad \hat{a}(s) = \frac{p\mu}{\mu-\lambda} \frac{\mu}{\mu+s} + \frac{\mu q - \lambda}{\mu - \lambda} \frac{\lambda}{\lambda+s} $$
### I.2.2. The output process

Let us now examine the distribution of the times between two completions of service. Such an interval is equal to the service time unless the queue becomes empty. Therefore, the function $\hat{f}(s)$ is given by

$$ (5) \qquad \hat{f}(s) = \pi(0) \frac{\lambda}{\lambda+s} \hat{b}(s) + (1-\pi(0)) \hat{b}(s) $$

where $\pi(0)$ is the probability for the queue to be empty just after an output. And DISNEY, McNICKLE proved that:

$$ \pi(0) = q[1 - \frac{\lambda}{\mu q}] $$

Then they get

$$ (6) \qquad \hat{f}(s) = \frac{p\mu}{\mu-\lambda} \frac{\mu}{\mu+s} + \frac{\mu q-\lambda}{\mu-\lambda} \frac{\lambda}{\lambda+s} $$

So we see that the interinput times and the interoutput times have exactly the same distribution, which is a hyperexponential distribution.

### I.2.3. The departure process

It is easy to show ([5]; [6]) that the departure process is a Poisson process with parameter $\lambda$.

So we have:

$$ (7) \qquad S(t) = 1 - e^{-\lambda t} $$

### I.3. The feedback process

A complementary result is the distribution of the interfeedback times. Let $P(i)$ be the stationary probability of state i. We have
$$P(i) = \rho^i (1-\rho) = \left(\frac{\lambda}{\mu q}\right)^i \left(1-\frac{\lambda}{\mu q}\right) \quad i=0,1,\dots,n,\dots$$

If $t_0$ is the time of a feedback, we know that just after $t_0$ the queue is in state i with the probability $P(i-1)$ ([4]). Let us introduce the following function $\alpha(i)$: $\alpha(i)$ is the L.S.T. of the interfeedback times knowing that the queue is in state i.

Then, conditioning upon the number of customers in queue, we can write:

$$(8) \qquad \hat{f}(s) = \sum_{i=1}^{\infty} P(i-1) \alpha(i)$$

and we use an iterative technique to compute the functions $\alpha(i)$.

The time of the first event after $t_0$ is the lower of the times of the first arrival and the first output (feedback or departure). So, the L.S.T. of this time is $\frac{\lambda+\mu}{\lambda+\mu+s}$.

With a probability $\frac{\lambda}{\lambda+\mu}$, this event is an arrival and now the queue is in state $(i+1)$; with a probability $\frac{\mu q}{\lambda+\mu}$ this is a departure and the queue is in state $(i-1)$; with a probability $\frac{\mu p}{\lambda+\mu}$, this is a feedback. Therefore, we can write:

$$(9) \qquad \alpha(i) = \frac{\lambda+\mu}{\lambda+\mu+s} \left[ \frac{\lambda}{\lambda+\mu} \alpha(i+1) + \frac{\mu q}{\lambda+\mu} \alpha(i-1) + \frac{\mu p}{\lambda+\mu} \right] \quad i > 0 \\ (10) \qquad \alpha(0) = \frac{\lambda}{\lambda+s} \quad \alpha(1)$$

Or:

$$(11) \qquad (\lambda+\mu+s) \alpha(i) = \lambda\alpha(i+1) + \mu q \alpha(i-1) + \mu p \quad i > 0 \\ (12) \qquad (\lambda+s) \alpha(0) = \lambda\alpha(1)$$

Summing (11) for $i=1$ to $\infty$, and using $P(i) = \rho P(i-1)$ we get:

$$(\lambda+\mu+s) \sum_{i=1}^{\infty} P(i-1)\alpha(i) = \frac{\lambda}{\rho} \left[ \sum_{i=0}^{\infty} P(i-1)\alpha(i) - P(0)\alpha(1) \right] \\ + \mu q \left[ P(0)\alpha(0) + \rho \sum_{i=0}^{\infty} P(i-1)\alpha(i) \right] + \mu p$$
that is :

$$ (\lambda+\mu+s)\hat{r}(s) = \frac{\lambda}{\rho} [\hat{r}(s)-P(0)\alpha(1)] + \mu q[P(0)\alpha(0)+\rho\hat{r}(s)] + \mu p $$

Using (12) and after simplifications, we obtain

$$ (13) \qquad (\mu p+s) \hat{r}(s) = \mu p - \frac{\mu q}{\lambda} s P(0) \alpha(0) $$

Now, we have to determine $\alpha(0)$.

Setting $\alpha(i) = \sigma(i) + \frac{\mu p}{\mu p+s}$ in (11), we get the following equations

$$ (14) \qquad (\lambda+\mu+s)\sigma(i) = \lambda\sigma(i+1) + \mu q \sigma(i-1) \quad i \ge 1. $$

A general solution of equation (14) is

$$ \sigma(i) = ax_1^i + bx_2^i $$

where $x_1, x_2$ are the solutions of :

$$ \lambda x^2 - (\lambda + \mu + s) x + \mu q = 0 $$

We have $x_1+x_2 = 1 + \frac{\mu+s}{\lambda}$; $x_1x_2 = \frac{\lambda}{\mu q}$. So, one root, say $x_2$, is such that $|x_2| > 1$. As $i$ tends to infinity $\alpha(i)$ obviously tends to $\frac{\mu p}{\mu p+s}$, so $b=0$.

Therefore :

$$ (15) \qquad \sigma(i) = a x_1^i $$

where $x_1$ is the lower root of the equation :

$$ \lambda x^2 - (\lambda + \mu + s)x + \mu q = 0 $$

Then, we have

$$ (16) \qquad x_1 = \frac{\lambda+\mu+s - \sqrt{(\lambda+\mu+s)^2 - 4\lambda\mu q}}{2\lambda} $$

Now, using (12) and (15), we deduce the system

$$ \left\{ \begin{array}{l} \alpha(0) = a + \frac{\mu p}{\mu p+s} \\ \\ \frac{\lambda+s}{\lambda} \alpha(0) = ax_1 + \frac{\mu p}{\mu p+s} \end{array} \right. $$

Then we get

$$ (17) \qquad \alpha(0) = \left[ \frac{1-x_1}{1-x_1 + \frac{s}{\lambda}} \right] \frac{\mu p}{\mu p+s} $$

Now, the L.S.T. $\hat{r}(s)$ is entirely determined. We have

$$ (18) \qquad (\mu p+s) \hat{r}(s) = \mu p - \mu q s P(0) \frac{\mu p}{\mu p+s} \left[ \frac{1-x_1}{\lambda(1-x_1)+s} \right] $$
From (18) we easily verify

$$M_1(r) = \int_0^\infty t \, dR(t) = - \left. \frac{\partial \hat{r}(s)}{\partial s} \right|_{s=0} = \frac{q}{\lambda p}$$

## Conclusion

We have studied the most elementary kind of network : an M/M/1 queue with instantaneous feedback. After a recall of previous results, we showed we could calculate the distribution of the interfeedback times. We show that the feedback process is not a Poisson process. This is a new result. However, it is not known, if the feedback process is a renewal process.

In the second part, we extend the distribution equality to the case of two tandem queues with feedback, by using the same notations and the same techniques. Then we shall study a particular Jackson Network.

## II. Results for two tandem queues

The two tandem queues system with feedback is illustrated on Figure 2.

<figure><img src="image_5.png" /><figcaption>Figure 2 : a two tandem queues system with feedback</figcaption></figure>

The service times of the first server are exponentially distributed with parameter $\mu_1$ and the L.S.T. is $\hat{b}_1(s)$. Second server's are exponentially distributed with parameter $\mu_2$ and the L.S.T. is $\hat{b}_2(s)$. Identically to the first part we are interested by the distribution of the interinput times $A(t)$ of queue 1 and the distribution of interoutput times $F(t)$ of queue 2. We show the following result.
**Theorem 1:**

In a two tandem queues system with feedback, the interinput times and interoutput times have exactly the same distribution. This distribution is an hyperexponential distribution.

In this system, the equality (1) : $1-A(t) = e^{-\lambda}t[1-G(t)]$ is still true whatever the number of tandem queues is. In the same way, since the departure process is still a Poisson process with parameter $\lambda$, we have symmetrically ($H(t)$ is the symmetrical of $G(t)$ for the feedback process).

$$ (19) \qquad 1-F(t) = e^{-\lambda}t[1-H(t)] $$

Using the L.S.T., we obtain

$$ (20) \qquad \hat{f}(s) = \frac{\lambda}{\lambda+s} [1-\hat{h}(\lambda+s)] + \hat{h}(\lambda+s) $$

where $\hat{h}(\lambda+s) = \int_{0}^{\infty} e^{-(\lambda+s)t} dH(t)$.

From (20), we get:

$$ (21) \qquad \hat{h}(s) = \frac{s\hat{f}(s-\lambda)-\lambda}{s-\lambda} $$

Now, the L.S.T. $\hat{f}(s)$ can be easily found. We have

$$ (22) \qquad \hat{f}(s) = (1-\rho_1)(1-\rho_2)q \frac{\lambda}{\lambda+s} \hat{b}_1(s)\hat{b}_2(s) + (1-\rho_2)(p+q\rho_1)\hat{b}_1(s)\hat{b}_2(s) + \rho_2 \hat{b}_2(s) $$

This is the L.S.T. of an hyperexponential distribution (of order 3).

Effectively (22) can be transformed to:

$$ \hat{f}(s) = k_1 \frac{\lambda}{\lambda+s} + k_2 \frac{\mu_1}{\mu_1+s} + k_3 \frac{\mu_2}{\mu_2+s} $$

with $k_1+k_2+k_3=1$.

$$ k_1 = \frac{(\mu_1 - \lambda)(\mu_2 q - \lambda)}{q(\mu_1 - \lambda)(\mu_2 - \lambda)} $$

$$ k_2 = \frac{p\mu_1(\mu_2 q - \lambda)}{q(\mu_2 - \mu_1)(\mu_1 - \lambda)} $$

$$ k_3 = \frac{p\mu_2(\mu_1 q - \lambda)}{q(\mu_2 - \lambda)(\mu_1 - \mu_2)} $$
Setting $\rho_i = \frac{\lambda}{\mu_i q}$ ($i=1,2$) in (22) and after some algebra, we find :

$$ (23) \qquad \hat{h}(s) = \frac{p[\mu_1 \mu_2 q + \lambda(s-\lambda)]}{q[\mu_1 + s - \lambda][\mu_2 + s - \lambda]} $$

Let us now compute the function $\hat{g}(s)$. We recall that the definition of $\hat{g}(s)$ implies that if $t_0$ is the time of an input, the only customer to arrive before $(t_0+t)$ is a feedback customer (there is no arrival before the feedback).

Conditioning upon the states i and j of the queue 1 and 2, we can write

$$ (24) \qquad \hat{g}(s) = \sum_{j=0}^{\infty} P_2(j) \sum_{i=1}^{\infty} P_1(i-1)\alpha(i,j) $$

where $\alpha(i,j)$ is the L.S.T. of the interval of time before the next arrival knowing that the queue 1 is in state i and queue 2 in state j. And just after $t_0$, the queue 1 is in state i with the stationary probability $P_1[i-1]$, and queue 2 is in state j with the stationary probability $P_2[j]$.

We have $P_k(n) = \rho_k^n(1-\rho_k)$, $k=1,2$. The first event after the time $t_0$ is first of both possible service completions, which L.S.T. is $\frac{\mu_1+\mu_2}{\mu_1+\mu_2+s}$. Such as for $\alpha(i)$ in I.3., we get the following recurrent equations :

$$ (25) \qquad (\mu_1+\mu_2+s)\alpha(i,j) = \mu_1\alpha(i-1,j+1) + \mu_2q\alpha(i,j-1) + \mu_2p \quad \begin{cases} i > 0 \\ j > 0 \end{cases} $$

$$ (26) \qquad (\mu_1+s)\alpha(i,0) = \mu_1\alpha(i-1,1) \qquad i > 0 $$

$$ (27) \qquad (\mu_2+s)\alpha(0,j) = \mu_2 q \alpha(0,j-1) + \mu_2 p \qquad j > 1 $$

Of course we have :

$$ (28) \qquad \alpha(0,1) = \frac{\mu_2 p}{\mu_2 + s} $$

Let $\gamma(j)$ be defined as :
$$ \gamma(j) = \sum_{i=1}^{\infty} P_{1}(i-1)\alpha(i,j) $$

then, by summation on (25) we get :

$$ (29) \qquad (\mu_1+\mu_2+s)\gamma(j) = \mu_1[P_1(0)\alpha(0,j+1) + \rho_1\gamma(j+1)] \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \mu_2 q\gamma(j-1) + \mu_2 p \qquad \qquad \qquad \qquad j > 0 $$

To compute $\gamma(0)$, we use (26) :

$$ (30) \qquad (\mu_1+s)\gamma(0) = \mu_1[P_1(0)\alpha(0,1) + \rho_1\gamma(1)] $$

$$ \text{And } \hat{g}(s) = \sum_{j=0}^{\infty} P_2(j)\gamma(j) $$

So, using (29) and (30) :

$$ \begin{align*} (\mu_1+\mu_2+s)\hat{g}(s) - \mu_2 P_2(0)\gamma(0) &= \mu_1 P_1(0) \sum_{j=0}^{\infty} P_2(j)\alpha(0,j+1) \\ &\quad + \mu_1 \frac{\lambda}{\mu_1 q} \sum_{j=0}^{\infty} P_2(j)\gamma(j+1) \\ &\quad + \mu_2 q \frac{\lambda}{\mu_2 q} \hat{g}(s) + \mu_2 p \sum_{j=1}^{\infty} P_2(j) \\ &= \mu_1 P_1(0) \sum_{j=0}^{\infty} P_2(j)\alpha(0,j+1) + \frac{\lambda}{q} \left[ \frac{\mu_2 q}{\lambda} (\hat{g}(s)-P_2(0)\gamma(0)) \right] \\ &\quad + \lambda \hat{g}(s) + \mu_2 p [1-P_2(0)] \end{align*} $$

And after simplifications :

$$ \begin{align*} (\mu_1+s-\lambda)\hat{g}(s) &= \mu_1 P_1(0) \sum_{j=0}^{\infty} P_2(j)\alpha(0,j+1) + \mu_2 p [1-P_2(0)] \\ &= \mu_1 P_1(0) [P_2(0)\alpha(0,1) + \sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1)] \\ &\quad + \mu_2 p [1-P_2(0)] \end{align*} $$
Now, we need to compute $\sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1)$. From the equation (27) valid for $j \ge 2$, we get by summation :

$$ (\mu_2+s) \sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1) = \mu_2 q \bar{p}_2[P_2(0)\alpha(0,1) + \sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1)] + \mu_2 p[1-P_2(0)] $$

Then :

$$ (\mu_2+s-\lambda) \sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1) = \lambda P_2(0)\alpha(0,1) + \mu_2 p[1-P_2(0)] $$

and using (28) we get

$$ (\mu_2+s-\lambda) \sum_{j=1}^{\infty} P_2(j)\alpha(0,j+1) = \lambda P_2(0) \frac{\mu_2 p}{\mu_2+s} + \frac{\lambda p}{q} $$

So

$$ (\mu_1+s-\lambda)\hat{g}(s) = \mu_1 P_1(0) \left[ \frac{P_2(0)\mu_2 p}{\mu_2+s} + \frac{\lambda P_2(0) \frac{\mu_2 p}{\mu_2+s} + \frac{\lambda p}{q}}{\mu_2+s-\lambda} \right] + \mu_2 p[1-P_2(0)] $$

And after reduction we finally get :

$$ (31) \qquad \hat{g}(s) = \frac{p[\mu_1 \mu_2 q + \lambda(s-\lambda)]}{q[\mu_1 + s - \lambda][\mu_2 + s - \lambda]} $$

This last expression is strictly equivalent to the one we obtained for the function $\hat{h}(s)$.

From this equality, we come to the conclusion that the L.S.T. $\hat{a}(s)$ and $\hat{f}(s)$ are equal. So theorem 1 is proved.

**Remark** : it is interesting to note that $\hat{g}(s)$ in (31) can be written as :
$$ (32) \qquad \hat{g}(s) = \frac{p_{\hat{B}_2}(s)[1-p_2(0)]}{[1-q\rho_2\hat{B}_2(s)]} + \frac{p_{\hat{B}_1}(s)\hat{B}_2(s)p_2(0)}{[1-q\rho_1\hat{B}_1(s)][1-q\rho_2\hat{B}_2(s)]} $$

### III. A particular case of a Jackson Network (J.N.)

Consider the queueing network of Figure 3 with Poisson arrivals of parameters $\lambda_1$ and $\lambda_2$.

<figure><img src="image_6.png" /><figcaption>Figure 3: a particular case of Jackson Network</figcaption></figure>

Customers enter the network through two sources and are directed to service stations. The customer's service times at station i ($i=1,2$) are exponentially distributed with parameter $\mu_i$ of L.S.T. $\hat{B}_i(s)$ ($i=1,2$). After completion of a service at queue i, the customer leaves the network with a fixed probability $q_i = 1-p_i$. With the probability $p_i$ he joins the queue j ($j \neq i$).

We always note $\hat{a}(s)$ and $\hat{f}(s)$ the L.S.T. of the interinput times and interoutput times at the queue 1.

If $\rho_1$ and $\rho_2$ are the traffic intensities for each queue we have

$$ \rho_1 = \frac{\lambda_1 + \rho_2 \lambda_2}{\mu_1 (1 - \rho_1 \rho_2)} $$

$$ \rho_2 = \frac{\lambda_2 + \rho_1 \lambda_1}{\mu_2 (1 - \rho_1 \rho_2)} $$
**Theorem 2 :**

The interinput times and interoutput times at each queue have exactly the same distribution.

The demonstration of this theorem uses the same techniques as for Theorem 1; and it is sufficient to show : $\hat{a}(s) = \hat{f}(s)$ to obtain the theorem 2.

First we introduce the following function noted $\alpha(i,j)$ : $\alpha(i,j)$ is the L.S.T. of the first input time in the queue 1 when the queue 1 is in state i and queue 2 in state j. Just after an input in queue k, we know that the queue is in state i with a stationary probability $P_k(i-1)$ ($k=1,2$). Now we examine the functions $\hat{a}(s)$ and $\hat{f}(s)$ using $\alpha(i,j)$ and conditioning upon the states of queues. We have :

$$ (33) \qquad \hat{a}(s) = \sum_{j=0}^{\infty} P_2(j) \sum_{i=1}^{\infty} P_1(i-1)\alpha(i,j) $$

$$ (34) \qquad \hat{f}(s) = \rho_1 \hat{b}_1(s) + (1-\rho_1) \hat{b}_1(s) \sum_{j=0}^{\infty} (p_1 \alpha(0,j+1) + q_1 \alpha(0,j)) P_2(j) $$

And we note

$$ \gamma(j) = \sum_{i=1}^{\infty} P_1(i-1)\alpha(i,j) . $$

If $t_0$ is the time of any input in the queue 1, the L.S.T. of the first event after $t_0$ is $\frac{\lambda_1+\lambda_2+\mu_1+\mu_2}{\lambda_1+\lambda_2+\mu_1+\mu_2+s}$. With a probability $\frac{\lambda_1+\mu_2p_2}{\lambda_1+\lambda_2+\mu_1+\mu_2}$ we have an input in queue 1. But with the probabilities

$\frac{\lambda_2}{\lambda_1+\lambda_2+\mu_1+\mu_2}$ , $\frac{\mu_1 q_1}{\lambda_1+\lambda_2+\mu_1+\mu_2}$ , $\frac{\mu_1 p_1}{\lambda_1+\lambda_2+\mu_1+\mu_2}$ , $\frac{\mu_2 q_2}{\lambda_1+\lambda_2+\mu_1+\mu_2}$ the system becomes respectively in state (i,j+1), (i-1,j), (i-1,j+1), (i,j-1).

So we have the iterative formulas :

$$ (35) \qquad (\lambda_1+\lambda_2+\mu_1+\mu_2+s)\alpha(i,j) = (\lambda_1+\mu_2p_2) + \lambda_2\alpha(i,j+1) + \mu_1q_1\alpha(i-1,j) \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \mu_1p_1\alpha(i-1,j+1) + \mu_2q_2\alpha(i,j-1) \quad i,j > 0 $$
$$
(36) \quad (\lambda_1 + \lambda_2 + \mu_1 + s)\alpha(i, 0) = \lambda_1 + \lambda_2\alpha(i, 1) + \mu_1 q_1\alpha(i-1, 0) + \mu_1 p_1\alpha(i-1, 1) \quad i > 0
$$

$$
(37) \quad (\lambda_1 + \lambda_2 + \mu_2 + s)\alpha(0, j) = (\lambda_1 + \mu_2 p_2) + \lambda_2 \alpha(0, j+1) + \mu_2 q_2 \alpha(0, j-1) \quad j > 0
$$

$$
(38) \quad (\lambda_1 + \lambda_2 + s)\alpha(0, 0) = \lambda_1 + \lambda_2\alpha(0, 1)
$$

Now, using (35) we easily compute $\gamma(j)$. By summation on $i$ we get

$$
\begin{align*}
(39) \quad (\lambda_1 + \lambda_2 + \mu_1 + \mu_2 + s)\gamma(j) &= (\lambda_1 + \mu_2 p_2) + \lambda_2 \gamma(j+1) \\
&\quad + \mu_1 q_1 [P_1(0)\alpha(0,j) + \rho_1 \gamma(j)] \\
&\quad + \mu_1 p_1 [P_1(0)\alpha(0,j+1) + \rho_1 \gamma(j+1)] \\
&\quad + \mu_2 q_2 \gamma(j-1)
\end{align*}
$$

for $j = 1, 2, \dots$

Using (36) we have the equation valid for $j = 0$:

$$
\begin{equation}
\begin{split}
(40) \quad (\lambda_1 + \lambda_2 + \mu_1 + s)\gamma(0) ={}& \lambda_1 + \lambda_2\gamma(1) + \mu_1 q_1 [P_1(0)\alpha(0,0) + \rho_1\gamma(0)] \\
& + \mu_1 p_1 [P_1(0)\alpha(0,1) + \rho_1\gamma(1)]
\end{split}
\end{equation}
$$

Then, by summation on $j$ and setting $\sum_{j=0}^{\infty} P_2(j)\gamma(j) = \hat{a}(s)$, the equations
(39) and (40) yield

$$
\begin{align*}
& (\lambda_1 + \lambda_2 + \mu_1 + \mu_2 + s) \hat{a}(s) - \mu_2 \gamma(0) P_2(0) = \lambda_1 + \mu_2 P_2(1 - P_2(0)) \\
& \qquad + \frac{\lambda_2}{\rho_2} [\hat{a}(s) - P_2(0)\gamma(0)] \\
& \qquad + \mu_1 P_1(0) \sum_{j=0}^{\infty} P_2(j) [q_1\alpha(0,j) + p_1\alpha(0,j+1)] \\
& \qquad + \mu_1 q_1 \rho_1 \hat{a}(s) + \frac{\mu_1 P_1 \rho_1}{\rho_2} [\hat{a}(s) - P_2(0)\gamma(0)] \\
& \qquad + \mu_2 q_2 \rho_2 \hat{a}(s).
\end{align*}
$$
Or, after simplifications :

$$
(41) \quad \left[ \lambda_1 + \lambda_2 - \mu_1 q_1 \rho_1 - \mu_2 q_2 \rho_2 + \mu_2 - \left( \frac{\lambda_2}{\rho_2} + \frac{\mu_1 p_1 \rho_1}{\rho_2} \right) + \mu_1 + s \right] \hat{a}(s) =
$$
$$
\lambda_1 + \mu_2 p_2 \rho_2 + p_2(0)\gamma(0) \left[ \mu_2 - \frac{1}{\rho_2} \left( \lambda_2 + \mu_1 p_1 \rho_1 \right) \right] + \mu_1 p_1(0) \sum_{j=0}^{\infty} p_2(j) \left[ q_1 \alpha(0,j) + p_1 \alpha(0,j+1) \right]
$$

But, we know that the input rate is equal to the output rate for each
queue. That is, to say that we have the following identities :

$$
(43) \qquad \lambda_1 + p_2 \mu_2 \rho_2 = \mu_1 \rho_1
$$

$$
(43) \qquad \lambda_2 + p_1 \mu_1 \rho_1 = \mu_2 \rho_2
$$

Then, using (42) and (43) in (41), we see that the coefficient of $\gamma(0)$ is equal to zero, and the coefficient of $\hat{a}(s)$ is simply $(\mu_1+s)$. So, (41) becomes

$$
(44) \quad (\mu_1+s)\hat{a}(s) = \mu_1\rho_1 + \mu_1(1-\rho_1) \sum_{j=0}^{\infty} p_2(j)[q_1\alpha(0,j) + p_1\alpha(0,j+1)]
$$

This last expression shows the identity between $\hat{a}(s)$ and $\hat{f}(s)$. Then, the theorem 2 is proved without computations of the functions $\alpha(i,j)$. And we remark that the functions $\hat{a}(s)$ and $\hat{f}(s)$ are equal terms to terms.

Now, taking some particular values for $\lambda_2$ and $p_2$, we exactly
compute the function $\hat{f}(s)$ (or $\hat{a}(s)$).

$$
\lambda_2 = 0, p_2 = 1
$$

In this case, we have

$$
(45) \quad (\mu_1+s)\hat{f}(s) = \rho_1\mu_1 + \mu_1(1-\rho_1)(p_1+q_1\rho_2) \sum_{j=1}^{\infty} p_2(j-1)\alpha(0,j) \\
\phantom{(45) \quad (\mu_1+s)\hat{f}(s) =} + \mu_1q_1(1-\rho_1)(1-\rho_2)\alpha(0,0)
$$

and the system of equations (35), (36), (37) and (38) becomes :
$$
(46) \quad (\lambda_1 + \mu_1 + \mu_2 + s)\alpha(i,j) = \lambda_1 + \mu_2 + \mu_1 q_1 \alpha(i-1,j) + \mu_1 p_1 \alpha(i-1,j+1) \quad i,j > 0
$$

$$
(47) \quad (\lambda_1 + \mu_1 + s)\alpha(i,0) = \lambda_1 + \mu_1 q_1 \alpha(i-1,0) + \mu_1 p_1 \alpha(i-1,1) \quad i > 0
$$

$$
(48) \quad (\lambda_1 + \mu_2 + s)\alpha(0,j) = \lambda_1 + \mu_2 \qquad j > 0
$$

$$
(49) \quad (\lambda_1 + s)\alpha(0,0) = \lambda_1
$$

Then, using (48) we obviously have

$$
(50) \quad \sum_{j=1}^{\infty} P_2(j-1)\alpha(0,j) = \frac{\lambda_1 + \mu_2}{\lambda_1 + \mu_2 + s}
$$

By substitution of (50) and setting $\alpha(0,0) = \frac{\lambda_1}{\lambda_1+s}$ (equation 49) in (45),
$\hat{f}(s)$ becomes :

$$
(51) \quad \hat{f}(s) = \rho_1 \frac{\mu_1}{\mu_1+s} + (1-\rho_1)(p_1+q_1\rho_2) \frac{\mu_1}{\mu_1+s} \frac{\lambda_1+\mu_2}{\lambda_1+\mu_2+s} + q_1(1-\rho_1)(1-\rho_2)
$$

$$
\frac{\mu_1}{\mu_1+s} \quad \frac{\lambda_1}{\lambda_1+s}
$$

with $\rho_1 = \frac{\lambda_1}{\mu_1 q_1}$ and $\rho_2 = \frac{\lambda_1 p_1}{\mu_2 q_1}$.

And (51) can be transformed to :

$$
(52) \quad \hat{f}(s) = k_1 \frac{\mu_1}{\mu_1+s} + k_2 \frac{\lambda_1 + \mu_2}{\lambda_1 + \mu_2 + s} + k_3 \frac{\lambda_1}{\lambda_1+s}
$$

$$
\text{with}
\begin{cases}
k_1+k_2+k_3=1 \\
k_1 = \rho_1 - (1-\rho_1)(p_1+q_1\rho_2) \frac{\lambda_1+\mu_2}{\mu_1-(\lambda_1+\mu_2)} - q_1(1-\rho_1)(1-\rho_2) \frac{\lambda_1}{\mu_1-\lambda_1} \\
k_2 = (1-\rho_1)(p_1+q_1\rho_2) \frac{\mu_1}{\mu_1-(\lambda_1+\mu_2)} \\
k_3 = q_1(1-\rho_1)(1-\rho_2) \frac{\mu_1}{\mu_1-\lambda_1}
\end{cases}
$$

So $\hat{f}(s)$ is the L.S.T. of an hyperexponential distribution.
From the equation (34) we deduce the L.S.T. of the interoutput in the queue 2 : we note $f_*(s)$ this function. We have

$$
(53) \quad \begin{aligned}
\hat{f}_*(s) = \rho_2 \hat{b}_2(s) &+ (1-\rho_2) \hat{b}_2(s) \left[ (p_2+q_2\rho_1) \sum_{i=1}^{\infty} P_1(i-1)\beta(i,0) \right. \\
& \left. \qquad + q_2 P_1(0)\beta(0,0) \right]
\end{aligned}
$$

where $\beta(i,j)$ is the L.S.T. of the first input in queue 2 when the system is in state $(i,j)$.

For the particular case $\lambda_2 = 0$, $p_2 = 1$ (53) becomes :

$$
(54) \quad \left[ \mu_2 + s \right] \hat{f}_*(s) = \rho_2 \mu_2 + (1 - \rho_2) \mu_2 \sum_{i=1}^{\infty} P_1(i-1) \beta(i, 0)
$$

But we have already computed $\sum_{i=1}^{\infty} P_1(i-1)\beta(i,0)$. Effectively, this term is strictly equivalent to $\hat{f}(s)$, the L.S.T. of interfeedback times in a M/M/1 queue since the queue 2 is empty. The function $\hat{f}(s)$ and $x_1$ are given by (18) and (16). Then :

$$
\sum_{i=1}^{\infty} P_2(i-1)\beta(i,0) = \frac{\mu_1 p_1}{\mu_1 p_1 + s} \left[ 1 - s \left( \frac{\mu_1 q_1 - \lambda_1}{\mu_1 p_1 + s} \right) \left( \frac{1 - x_1}{\lambda_1 (1-x_1) + s} \right) \right]
$$

and

$$
(55) \quad f_*(s) = \rho_2 \frac{\mu_2}{\mu_2+s} + (1-\rho_2) \frac{\mu_2}{\mu_2+s} \frac{\mu_1}{\mu_1 p_1+s} \left[ 1 - \frac{s(\mu_1 q_1 - \lambda_1)(1-x_1)}{(\mu_1 p_1+s)(\lambda_1(1-x_1)+s)} \right]
$$

From the conclusion of theorem 2, the function $\hat{f}_*(s)$ is equivalent to the L.S.T. of the interfeedback times.

Conclusion

We proved on a particular case of J.N. that the input and output distributions at each queue are always the same and obviously not equal to a Poisson process. Some useful remarks : the equality of these distributions has been obtained terms to terms and without needing to compute exactly the functions $\hat{a}(s)$ and $\hat{f}(s)$. Then we reduce the system to compute the L.S.T. of the interfeedback times. We will extend the results of theorems 1 and 2 to any J.N.
IV. General Jackson network

We consider a J.N. with a set of n service stations interconnected
[4] (see Figure 4). Stations 0 and n+1 are a source and a sink respectively

<figure><img src="image_7.png" /><figcaption>Figure 4 : a Jackson Network</figcaption></figure>

The service times at station i are exponential with parameter µ_i
of L.S.T. b̂_i(s). The arrival process is assumed to be Poisson of rate λ.
Let Q be the transition matrix : Q = (q_i,j) 0 ≤ i,j ≤ n+1 ; q_0j is
the probability for an external arrival to enter station j (for j = 0
and j = n+1, we take q_0j = 0), q_{j,n+1} is the probability that a customer
leaves the system after completing service at station j, and q_jj is the
probability of a feedback at station j.

If we note e_i the average number of times a customer passes through
station i before leaving the system, we have

$$
(56) \quad e_i = q_{0i} + \sum_{j=1}^{n} e_j q_{ji}
$$

And the intensity traffic in queue i is defined by

$$
(57) \quad \rho_i = \frac{\lambda e_i}{\mu_i}
$$
We note $\hat{a}_i(s)$ the L.S.T. of the interinput times at the queue i and
$\hat{f}_i(s)$ the L.S.T. of the interoutput times at the queue i. We have the
following result.

**Theorem 3 :**

For i = 1,n the functions $\hat{a}_i(s)$ and $\hat{f}_i(s)$ are equal; that means that
the interinput times and interoutput times at each queue have exatly the
same distributions.

To show this result, we need some notations. The state of the
model is characterized by the number of customers in each station.
We define the state by the vector : $\vec{E} = (j,k_2,k_3,...,k_n)$ where j is the
number of customers at the first station and $k_i$ (i=2,n) the number of
customers at station i. For simplification we only note $\vec{E} = (j,\vec{k})$.

Let $(j, \vec{k}_{i+1})$ and $(j, \vec{k}_{i-1})$ be the vectors identical to $\vec{E}$, except for
the element $k_i$ which is respectively replaced by $(k_{i+1})$ and $(k_{i-1})$. Let
also $(j, \vec{k}_{i+}, \vec{l}-)$ be identical to $\vec{E}$ except for the elements $k_i$ and $k_l$ which
are respectively replaced by $(k_{i+1})$ and $(k_{l-1})$.

We shall prove the theorem for the first queue. Now let us examine
the functions $\hat{a}_1(s) = \hat{a}(s)$ and $\hat{f}_1(s) = \hat{f}(s)$. We have :

$$
(58) \quad \hat{a}(s) = \sum_{\vec{k}} \sum_{j=1}^{\infty} P(\vec{k}) P_1(j-1) \alpha(j, \vec{k})
$$

$$
(59) \quad \hat{f}(s) = \hat{b}_1(s) \left[ (1-P_1(0))+P_1(0) \left\{ q_{11} + \sum_{\vec{k}} P(\vec{k}) (q_{1,n+1}\alpha(0,\vec{k}) + \sum_{i=2}^{n} q_{1i}\alpha(0,\vec{k}_{i+})) \right\} \right]
$$

where $P(\vec{k})$ is the stationary probability for the queue 2,3,...,n to be in
state $\vec{k} = (k_2,k_3,...,k_n)$, and we know that $P(\vec{k}) = P_2(k_2)P_3(k_3)...P_n(k_n)$
if $P_i(j)$ is the stationary probability for the queue i to be in state j
for i = 1,2,...,n.

If $t_0$ is the time of any input at station 1 just after $t_0$, the queue is
in stationary state and we have j customers with a probability $P_1(j-1)$.
The function $\alpha(j, \vec{k})$ is the L.S.T. of the first input after $t_0$ at the queue 1, knowing that the queue 1 is in state j and the others in states $(k_2, k_3, \dots, k_n)$.

Then conditioning upon the states of the network we get (58).

Now, the distribution of the times between two completions of service at queue 1 is equal to service time except when the queue becomes empty with probability $P_1(0)$. Then we have to wait for the convolution of the first input time with a service time. If t is the time of an output at station 1, and just after t the queue is empty, the system is in state $\begin{cases} (0, \vec{k}) & \text{with a probability } q_{1,n+1} \text{ (the customer leaves the network after t)} \\ (0, \vec{k}_{i+}) & \text{with a probability } q_{1,i} \text{ (the customer enters at station i) and} \\ & \text{with a probability } q_{11} \text{ (the customer feedback), we only have to wait for} \\ & \text{a service time.} \end{cases}$

Then conditioning upon the states of the system we get (59).

To study the function $\hat{a}(s)$, we first compute the summation upon the states j of the queue 1, and we note :

$$ (60) \qquad \gamma(\vec{k}) = \sum_{j=1}^{\infty} P_1(j-1)\alpha(j, \vec{k}) $$

Let us write the iterative equations that $\alpha(j, \vec{k})$ verifies. The time of the first event after $t_0$ (time of any input) is

$$ \frac{\lambda + \sum_{i=1}^{n} \mu_i}{n} \quad \text{with a probability} \quad \frac{\lambda q_{01} + \sum_{i=1}^{n} \mu_i q_{i1}}{\lambda + \sum_{i=1}^{n} \mu_i} $$

station 1

$$ \text{with probability } \frac{\mu_i q_{i,n+1}}{n} \text{, this is a departure from} \\ \lambda + \sum_{i=1}^{n} \mu_i $$

station i and the system is now in state $(j, \vec{k}_{i-})$,

... this being done for each event. After an obviously reduction by $(\lambda + \sum_{i=1}^{n} \mu_i)$ we get :
$$
\begin{equation}
\begin{aligned}
(61) \quad & \left(\lambda + \sum_{i=1}^{n} \mu_i^{+s} \right) \alpha(j, \vec{k}) = \lambda q_{01} + \mu_1 q_{11} + \sum_{i=2}^{n} \lambda q_{0i} \alpha(j, \vec{k}_{i+}) \\
& + \sum_{i=2}^{n} \mu_i \left[ q_{i,1} + \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{i,l} \alpha(j, \vec{k}_{i-}, l+) + q_{i,n+1} \alpha(j, \vec{k}_{i-}) \right] \\
& + \sum_{i=2}^{n} \mu_i q_{ii} \alpha(j, \vec{k}) + \mu_1 \left[ q_{1,n+1} \alpha(j-1, \vec{k}) + \sum_{i=2}^{n} q_{li} \alpha(j-1, \vec{k}_{i+}) \right]
\end{aligned}
\end{equation}
$$

Then, by summation upon j, we get :

$$
\begin{align*}
(62) \quad & \left(\lambda + \sum_{i=1}^{n} \mu_i^{+s} \right) \gamma(\vec{k}) = \lambda q_{01} + \mu_1 q_{11} + \sum_{i=2}^{n} \lambda q_{0i} \gamma(\vec{k}_{i+}) \\
& + \sum_{i=2}^{n} \mu_i \left[ q_{i1} + \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{i,l} \gamma(\vec{k}_{i-}, l+) + q_{i,n+1} \gamma(\vec{k}_{i-}) \right] \\
& + \sum_{i=2}^{n} \mu_i q_{ii} \gamma(\vec{k}) \\
& + \mu_1 [1 - P_1(0)] [q_{1,n+1} \gamma(\vec{k}) + \sum_{i=2}^{n} q_{1,i} \gamma(\vec{k}_{i+})] \\
& + \mu_1 P_1(0) [q_{1,n+1} \alpha(0, \vec{k}) + \sum_{i=2}^{n} q_{1,i} \alpha(0, \vec{k}_{i+})]
\end{align*}
$$

But this equation is only valid for a vector $\vec{k}$ with all its components strictly positive.

With a probability $P_i(0)$, the station i is empty and in the left-hanside of (62) there are no term with $\mu_i$. And also in the right-handside we don't have the terms with $\mu_i$.

So we introduce the following notations :

$$
\sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) = \sum_{k_2=0}^{\infty} \dots \sum_{k_{i-1}=0}^{\infty} \sum_{k_{i+1}=0}^{\infty} \sum_{k_n=0}^{\infty} P[k_2, \dots, k_{i-1}, k_{i+1}, \dots, k_n]
$$
$$ \gamma(\vec{k}^i=0) = \gamma(k_2, \dots, k_{i-1}, 0, k_{i+1}, \dots, k_n). $$

Then, using $\hat{a}(s) = \sum_{\vec{k}} \gamma(\vec{k}) P(\vec{k})$ and the previous remarks, we get by summation upon $\vec{k}$ in (62):

$$ (63) \quad \left( \lambda + \sum_{i=1}^{n} \mu_i s \right) \hat{a}(s) - \sum_{i=2}^{n} \mu_i \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) P_i(0) \gamma(\vec{k}^i=0) = $$

$$ \lambda q_{01} + \mu_1 q_{11} + \sum_{i=2}^{n} \mu_i q_{i1} \rho_i $$

$$ + \mu_1 P_1(0) \sum_{\vec{k}} P(\vec{k}) [ q_{1,n+1}(0) \alpha(0,\vec{k}) + \sum_{i=2}^{n} q_{li}(0) \alpha(0,\vec{k}_{i+}) ] $$

$$ + \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} \hat{a}(s) - \sum_{i=2}^{n} \frac{\lambda q_{0i} P_i(0)}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^i=0) $$

$$ + \sum_{i=2}^{n} \mu_i q_{ii} \hat{a}(s) - \sum_{i=2}^{n} \mu_i q_{ii} P_i(0) \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^i=0) $$

$$ + \sum_{i=2}^{n} \mu_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il} \rho_i}{\rho_l} \hat{a}(s) - \sum_{i=2}^{n} \mu_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il} \rho_i}{\rho_l} P_l(0) \sum_{\vec{k}-\{l\}} P(\vec{k}-\{l\}) \gamma(\vec{k}^l=0) $$

$$ + \sum_{i=2}^{n} \mu_i \rho_i q_{i,n+1} \hat{a}(s) + \mu_1 \rho_1 q_{1,n+1} \hat{a}(s) $$

$$ + \mu_1 \rho_1 \hat{a}(s) \sum_{i=2}^{n} \frac{q_{li}}{\rho_i} - \mu_1 \rho_1 \sum_{i=2}^{n} \frac{q_{li} P_i(0)}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^i=0) $$

See appendix I for more details.

So we have :
$$
\begin{align*}
(64) \quad & \hat{a}(s)[\lambda + \mu_1 + \sum_{i=2}^{n} \mu_i s + \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} - \sum_{i=2}^{n} \mu_i q_{ii} - \sum_{i=2}^{n} \mu_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il} \rho_i}{\rho_l} - \\
& \qquad - \sum_{i=2}^{n} \mu_i \rho_i q_{i,n+1} - \mu_1 \rho_1 q_{1,n+1} - \mu_1 \rho_1 \sum_{i=2}^{n} \frac{q_{li}}{\rho_i}] - \\
& \qquad - \sum_{i=2}^{n} \mu_i \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) P_i(0) \gamma(\vec{k}^{i=0}) \\
&= \lambda q_{01} + \mu_1 q_{11} + \sum_{i=2}^{n} \mu_i q_{il} \rho_i \\
& \qquad + \mu_1 P_1(0) \sum_{\vec{k}} P(\vec{k}) [q_{1,n+1} \alpha(0,\vec{k}) + \sum_{i=2}^{n} q_{li} \alpha(0,\vec{k}_{i+})] \\
& \qquad - \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} P_i(0) \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) \\
& \qquad - \sum_{i=2}^{n} \mu_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il} \rho_i}{\rho_l} P_l(0) \sum_{\vec{k}-\{l\}} P(\vec{k}-\{l\}) \gamma(\vec{k}^{l=0}) - \\
& \qquad - \mu_1 \rho_1 \sum_{i=2}^{n} \frac{q_{li} P_i(0)}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0})
\end{align*}
$$

But in the right handside of (64), after an inversion of the double summation,
and using (56) and (57), the three negative terms can be written as :

$$
\begin{align*}
& \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} P_i(0) \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) \\
& + \sum_{i=2}^{n} \frac{P_i(0)}{\rho_i} \sum_{\substack{l=2 \\ l \neq i}}^{n} \lambda e_l q_{li} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) \\
& + \lambda e_l \sum_{i=2}^{n} \frac{q_{li} P_i(0)}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) =
\end{align*}
$$
$$ = \sum_{i=2}^{n} \frac{P_i(0)}{\rho_i} \lambda [q_{0i} + \sum_{\ell=1}^{n} e_{\ell} q_{0i}^{\ell}] \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) $$

$$ = \sum_{i=2}^{n} P_i(0) \frac{\lambda e_i}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0}) $$

and we have $\frac{\lambda e_i}{\rho_i} = \mu_i$ (57).

So we find that the negative terms of the right-hand side of (64) are equal to the negative term of the left hand side.

Now, let us see the coefficient of $\hat{a}(s)$.

Using the relation (57), we get:

$$ \lambda + \mu_1 + s + \sum_{i=2}^{n} \frac{\lambda e_i}{\rho_i} - \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} - \sum_{i=2}^{n} \frac{\lambda e_i q_{ii}}{\rho_i} - \sum_{i=2}^{n} \lambda e_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il}}{\rho_l} $$

$$ - \sum_{i=1}^{n} \lambda e_i q_{i,n+1} - \lambda e_1 \sum_{i=2}^{n} \frac{q_{li}}{\rho_i} $$

$$ = \lambda - \lambda \sum_{i=1}^{n} e_i q_{i,n+1} + \sum_{i=2}^{n} \frac{\lambda e_i}{\rho_i} - \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} - \sum_{i=1}^{n} \lambda e_i \sum_{\ell=2}^{n} \frac{q_{il}}{\rho_\ell} + \mu_1 + s $$

But the term $\sum_{i=1}^{n} e_i q_{i,n+1}$ is, for each queue, the average number of customer who leaves the system through that queue, then $\sum_{i=1}^{n} e_i q_{i,n+1} = 1$ and the coefficient of $\hat{a}(s)$ becomes after inversion of the double summation

$\mu_1 + s + \lambda \sum_{i=2}^{n} \frac{1}{\rho_i} [e_i - (q_{0i} + \sum_{\ell=1}^{n} e_\ell q_{\ell i})]$ and from (56) we see that the summation is equal to zero. So the coefficient of $\hat{a}(s)$ is simply $(\mu_1+s)!$.
Let us now return to equation (64) which becomes

$$
(65) \quad (\mu_l+s)\hat{a}(s) = \lambda q_{0l} + \mu_l q_{1l} + \sum_{i=2}^{n} \mu_i q_{il} \rho_i \\
\phantom{(65) \quad (\mu_l+s)\hat{a}(s) = } + \mu_l P_l(0) \sum_{\vec{k}} P(\vec{k}) \Gamma_{q_{l,n+1}} \alpha(0,\vec{k}) + \sum_{i=2}^{n} q_{li} \alpha(0,\vec{k}_{i+})
$$

Using again (56) and (57), we see that (65) is equivalent to

$$
(66) \quad (\mu_l+s)\hat{a}(s) = \mu_l \rho_l + \mu_l (1-\rho_l) q_{1l} \\
\phantom{(66) \quad (\mu_l+s)\hat{a}(s) = } + \mu_l (1-\rho_l) \sum_{\vec{k}} P(\vec{k}) \Gamma_{q_{l,n+1}} \alpha(0,\vec{k}) + \sum_{i=2}^{n} q_{li} \alpha(0,\vec{k}_{i+})
$$

Setting $\hat{b}_l(s) = \frac{\mu_l}{\mu_l+s}$ in (59), we see that we obtain excatly the same expression that for $\hat{f}(s)$. This result is true for any queue of the network. So, the theorem 3 is proved. In a general Jackson Network, the distributions of the interinput times and interoutput times are equivalent for any queue. It is also possible to show this result for a network of queues with state dependent service times (see the proof in Appendix II).

Conclusion

We have shown that the distributions of interinput times and inter-
output times are equal for any station (with state-dependent service
times or not) in a global Jackson Network. These distributions are
generally different from an exponential distribution (we have hyperexponential
distributions). The only streams which possess the property to be a Poisson
process are the external arrival process, the departure process and the streams
without feedback customers.

We believe that the result for the distribution of flows to be
identical is still true for network satisfying the BCMP conditions (see [8]).
We have not yet been able to prove this result.

We conjecture that the following results are true but proofs are necessary :

1 - The equality of flows is true for the distributions but also for the processes. Brémaud [9] shows this results for the M/M/1 queue with feedback

2 - The equality of processes is still true for BCMP networks

3 - The class of networks provided with the process equality property is broader than BCMP network in the sense of product form solution. As an example of such a network with product form solution and which does not belong to the BCMP networks class we can give the following one. Let a new queue obtained by an equivalence of two M/M/1 queues in tandem as shown in figure 5

<figure><img src="image_8.png" /><figcaption>Figure 5 : the equivalent queue</figcaption></figure>

The service process of the equivalent queue can be obtained from the bivariate point process (input and output times) and filtering with respect to the output. It is a general service process.

Two such equivalent queues in series posses the product form property and do not belong to the BCMP class.

4 - The only networks with general *independent* service processes and product form solutions must satisfy the condition of Chandy, Howard, Towsley [10] : either all the service distributions are negative exponential or the discipline of service satisfies station balance (In particular any queueing discipline which satisfies station balance must begin to serve new customers immediately).
Future research can also be directed towards the comparison of
the diverse necessary or sufficient conditions to have a product form
solution : local balance property, Markov → Markov property, probability
for an unit at the end of its service to see the network at steady state,
equality of the distribution of flows.
APPENDIX I

From the equation (62) to obtain (63)

$$
\begin{align*}
(\lambda + \sum_{i=1}^{n} \mu_i + s)\gamma(\vec{k}) &= \lambda q_{01} + \mu_1 q_{11} + \sum_{i=2}^{n} \lambda q_{0i} \gamma(\vec{k}_{i+}) \\
&\quad + \sum_{i=2}^{n} \mu_i [q_{i1} + \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{il} \gamma(\vec{k}_{i-}, l^+) + q_{i,n+1} \gamma(\vec{k}_{i-})] \\
&\quad + \sum_{i=2}^{n} \mu_i q_{ii} \gamma(\vec{k}) \\
&\quad + \mu_1 \rho_1 [q_{1,n+1} \gamma(\vec{k}) + \sum_{i=2}^{n} q_{li} \gamma(\vec{k}_{i+})] \\
&\quad + \mu_1 P_1(0) [q_{1,n+1} \alpha(0, \vec{k}) + \sum_{i=2}^{n} q_{li} \alpha(0, \vec{k}_{i+})]
\end{align*}
$$

$$
\begin{align*}
\text{Calculus of } \sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} \lambda q_{0i} \gamma(\vec{k}_{i+})
\end{align*}
\begin{align*}
&= \sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} \sum_{j=1}^{\infty} \lambda q_{0i} P_1(j-1) \alpha(j, \vec{k}_{i+}) \\
&= \sum_{i=2}^{n} \lambda q_{0i} \sum_{j=1}^{\infty} P_1(j-1) \frac{1}{\rho_i} \sum_{\vec{k}} P(\vec{k}_{i+}) \alpha(j, \vec{k}_{i+}) \\
&= \sum_{i=2}^{n} \lambda q_{0i} \sum_{j=1}^{\infty} P_1(j-1) \frac{1}{\rho_i} \left[ \sum_{\vec{k}} P(\vec{k}) \alpha(j, \vec{k}) - P_1(0) \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \alpha(j, \vec{k}^{i=0}) \right] \\
&= \sum_{i=2}^{n} \frac{\lambda q_{0i}}{\rho_i} \sum_{\vec{k}} P(\vec{k}) \gamma(\vec{k}) - \sum_{i=2}^{n} \frac{\lambda q_{0i} P_1(0)}{\rho_i} \sum_{\vec{k}-\{i\}} P(\vec{k}-\{i\}) \gamma(\vec{k}^{i=0})
\end{align*}
$$
The calculus of $\sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} q_{il} \gamma(\vec{k}_{i+})$ is identical.

Calculus of $\sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} \mu_i q_{i,n+1} \gamma(\vec{k}_{i-})$

$$= \sum_{i=2}^{n} \mu_i q_{i,n+1} \sum_{j=1}^{\infty} P_1(j-1) \sum_{\vec{k}} P(\vec{k}) \alpha(j, \vec{k}_{i-})$$

$$= \sum_{i=2}^{n} \mu_i q_{i,n+1} \rho_i \sum_{j=1}^{\infty} P_1(j-1) \sum_{\vec{k}} P(\vec{k}_{i-}) \alpha(j, \vec{k}_{i-})$$

But when the queue i is empty, this term does not exist, then

$$\sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} \mu_i q_{i,n+1} \gamma(\vec{k}_{i-}) = \sum_{i=2}^{n} \mu_i q_{i,n+1} \rho_i \sum_{j=1}^{\infty} P_1(j-1) \sum_{\vec{k}} P(\vec{k}) \alpha(j, \vec{k})$$

$$= \sum_{\vec{k}} P(\vec{k}) \gamma(\vec{k}) \sum_{i=2}^{n} \mu_i \rho_i q_{i,n+1}$$

Calculus of $\sum_{\vec{k}} P(\vec{k}) \sum_{i=2}^{n} \mu_i \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{il} \gamma(\vec{k}_{i-,l+})$

$$= \sum_{i=2}^{n} \mu_i \sum_{\substack{\vec{k} \\ l=2}} P(\vec{k}) \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{il} \sum_{j=1}^{\infty} P_1(j-1) \alpha(j, \vec{k}_{i-,l+})$$

$$= \sum_{i=2}^{n} \mu_i \rho_i \sum_{\substack{l=2 \\ l \neq i}}^{n} q_{il} \sum_{j=1}^{\infty} P_1(j-1) \sum_{\vec{k}} P(\vec{k}) \alpha(j, \vec{k}_{l+})$$

$$= \sum_{i=2}^{n} \mu_i \rho_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il}}{\rho_{il}} \sum_{j=1}^{\infty} P_1(j-1) \sum_{\vec{k}} P(\vec{k}_{l+}) \alpha(j, \vec{k}_{l+})$$

$$= \sum_{i=2}^{n} \mu_i \rho_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il}}{\rho_{il}} \sum_{j=1}^{\infty} P_1(j-1) \left[ \sum_{\vec{k}} P(\vec{k}) \alpha(j, \vec{k}) - P_\ell(0) \sum_{\vec{k}-\{l\}} P(\vec{k}-\{l\}) \alpha(j, \vec{k}^{\ell=0}) \right]$$

$$= \sum_{\vec{k}} P(\vec{k}) \gamma(\vec{k}) \sum_{i=2}^{n} \mu_i \rho_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il}}{\rho_{il}}$$

$$- \sum_{i=2}^{n} \mu_i \rho_i \sum_{\substack{l=2 \\ l \neq i}}^{n} \frac{q_{il}}{\rho_{il}} P_\ell(0) \sum_{\vec{k}-\{l\}} P(\vec{k}-\{l\}) \gamma(\vec{k}^{\ell=0})$$
APPENDIX II

We consider the system illustrated on Figure 4 but the departure rate is denoted by $\mu_i(k_i)$ at station i if $k_i$ is the number of customers in this queue. The state of the system is defined by the vector $\vec{E} = (k_1, \dots, k_n)$. The interinput times and interoutput times distributions for the queue 1 can be written as :

$$ (1) \quad \hat{a}(s) = \sum_{\vec{E}} P(\vec{E}) \alpha(\vec{E}_{1+}) $$

$$ (2) \quad \hat{f}(s) = \sum_{\vec{E}} P(\vec{E}) [ q_{1,n+1}(\vec{E}) + \sum_{j=1}^{n} q_{1j}(\vec{E}) \beta(\vec{E}_{j+}) ] $$

where $\alpha(\vec{E})$ (respectively $\beta(\vec{E})$) is the L.S.T. of the interinput (resp. interoutput) times, knowing that the system is in state $\vec{E}$, and $P(\vec{E})$ is the stationary probability for the system to be in state $\vec{E}$, we have the recursive formula

$$ \begin{aligned} (3) \quad (\lambda + \sum_{1}^{n} \mu_i(k_i) + s) \alpha(\vec{E}) = & \lambda q_{01} + \sum_{j=1}^{n} \mu_j(k_j) q_{j1} \\ & + \sum_{j=2}^{n} \lambda q_{0j} \alpha(\vec{E}_{j+}) + \sum_{i=2}^{n} \sum_{j=1}^{n} \mu_j(k_j) q_{ji} \alpha(\vec{E}_{j-,i+}) \\ & + \sum_{j=1}^{n} \mu_j(k_j) q_{j,n+1} \alpha(\vec{E}_{j-}) \end{aligned} $$

$$ \begin{aligned} (4) \quad (\lambda + \sum_{1}^{n} \mu_i(k_i) + s) \beta(\vec{E}) = & \sum_{i=1}^{n} \lambda q_{0i} \beta(\vec{E}_{i+}) \\ & + \sum_{j=2}^{n} \mu_j(k_j) q_{j,n+1} \beta(\vec{E}_{j-}) + \sum_{i=1}^{n} \sum_{j=2}^{n} \mu_j(k_j) q_{ji} \beta(\vec{E}_{j-,i+}) + \mu_1(k_1) \end{aligned} $$

Now, summing relation 3 (resp. 4) after multiplication by $\beta(\vec{E}) P(\vec{E})$ (resp. $\alpha(\vec{E}) P(\vec{E})$), we obtain two another relations with an identical lefthand-
side term. Using the same kind of simplifications than in part IV (in particular we use the equations of local balance), we obtain the wanted result.

Now, as an example, we develop this calculus when the system is reduced to a M/M/1 queue with feedback. We set $q_{1,n+1} = q$, $q_{11} = p$, $\mu_1(k_1) = \mu(n)$; then the equations (1), (2), (3) and (4) become :

$$
(5) \quad \hat{a}(s) = \sum_{n=0}^{\infty} P(n)\alpha(n+1)
$$

$$
(6) \quad \hat{f}(s) = \sum_{n=0}^{\infty} P(n) [q \beta(n) + p \beta(n+1)]
$$

$$
(7) \quad (\lambda + \mu(n) + s) \alpha(n) = \lambda + p\mu(n) + q\mu(n)\alpha(n-1)
$$

$$
(8) \quad (\lambda + \mu(n) + s) \beta(n) = \lambda\beta(n+1) + \mu(n)
$$

By using the relation

$$
(9) \quad \lambda P(n-1) = \mu(n) qP(n)
$$

the summation of (7) after multiplication by $\beta(n)P(n)$ yields :

$$
\begin{equation}
\begin{split}
\sum_{n=1}^{\infty} (\lambda+\mu(n)+s)P(n)\alpha(n)\beta(n) ={}& \lambda \sum_{n=1}^{\infty} P(n)\beta(n) + \\
& + \sum_{n=1}^{\infty} p\mu(n) P(n) \beta(n) + \lambda \sum_{n=1}^{\infty} P(n-1)\alpha(n-1)\beta(n).
\end{split}
\tag{10}
\end{equation}
$$

and the summation of (8) after multiplication by $\alpha(n)P(n)$ yields :

$$
\begin{equation}
\begin{split}
\sum_{n=1}^{\infty} (\lambda + \mu(n) + s) P(n) \alpha(n) \beta(n) ={}& \lambda \sum_{n=1}^{\infty} P(n) \alpha(n) \beta(n+1) \\
& + \sum_{n=1}^{\infty} P(n) \mu(n) \alpha(n)
\end{split}
\tag{11}
\end{equation}
$$

Then we get :

$$
\begin{align*}
& (12) \quad \lambda \sum_{n=1}^{\infty} P(n)\beta(n) + \sum_{n=1}^{\infty} p\mu(n)P(n)\beta(n) + \lambda P(0)\alpha(0)\beta(1) \\
& \qquad = \sum_{n=1}^{\infty} P(n)\mu(n)\alpha(n).
\end{align*}
$$
But we obviously have $\beta(0) = \alpha(0)\beta(1)$. Then, using (9) we obtain

$$ (13) \quad \lambda \sum_{n=0}^{\infty} P(n)\beta(n) + p \sum_{n=0}^{\infty} \frac{\lambda}{q} P(n)\beta(n+1) = \frac{\lambda}{q} \sum_{n=0}^{\infty} P(n)\alpha(n+1) $$

By simplification of $\frac{\lambda}{q}$ we get :

$$ (14) \quad \sum_{n=0}^{\infty} P(n) [q\beta(n) + p\beta(n+1)] = \sum_{n=0}^{\infty} P(n)\alpha(n+1) $$
REFERENCES

[1] P.J. BURKE, "The output of a queueing system", Operat. Res., 4, 699-704, 1956.

[2] F.J. BEUTLER, B. MELAMED, "Decomposition and customer streams of feedback queueing networks in equilibrium", Research Report 77-1, University of Ann Arbor, 1977.

[3] G. PUJOLLE, C. SOULA, "A study of flows in queueing networks and an approximate method for solution", Research Report IRIA/LABORIA, 1978.

[4] P.J. BURKE, "Proof of a conjecture in the interarrival time distribution in a M/M/1 queue with feedback", I.E.E.E. Transactions on Communications (May 1976), p. 175-176.

[5] R. DISNEY, P. MCNICKLE, "The M.G.I queue with instantaneous Bernoulli feedback", Technical Report 77-4 (April 1977) of the University of Michigan, Ann Arbor.

[6] B. MELAMED, B.P. ZEIGLER, F. BEUTLER, "Simplifications of Jackson queueing network", Report n° 163 of the University of Michigan (August 1975).

[7] J.R. JACKSON, "Jobshop-like queue systems", Management Science, 10, 1963, p. 131-142.

[8] F. BASKETT, M. CHANDY, R. MUNTZ, J. PALACIOS, "Open, closed and mixed networks of queues with different classes of customers", JACM, 22, April 1975.

[9] P. BREMAUD, "Dynamical point process and Ito systems in communications and queueing" to appear.

[10] K.M. CHANDY, J.H. HOWARD, D.F. TOWSLEY, "Product form and local balance in queueing networks".