# A study of flows in queueing networks and an approximate method for solution

Guy Pujolle, Christine Soula

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

## To cite this version:

Guy Pujolle, Christine Soula. A study of flows in queueing networks and an approximate method for solution. [Research Report] IRIA-RR-340, IRIA. 1979, pp.15. hal-04716620

HAL Id: hal-04716620

https://inria.hal.science/hal-04716620v1

Submitted on 1 Oct 2024

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inv. 05893 RR 340

RIA

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

A STUDY OF FLOWS
IN QUEUEING NETWORKS
AND AN APPROXIMATE
METHOD FOR SOLUTION

Guy PUJOLLE
Christine SOULA

Rapport de Recherche N° 340

Janvier 1979

15P.
A STUDY OF FLOWS IN QUEUEING NETWORKS AND AN APPROXIMATE
METHOD FOR SOLUTION

Guy Pujolle, Christine Soula

IRIA/LABORIA

Résumé :

Nous introduisons une nouvelle méthode approchée pour étudier un réseau de files d'attente à un
ou plusieurs serveurs. Cette méthode est basée sur une étude théorique de la nature des flots dans
un réseau de Jackson.

Abstract :

A new approximate approach to study open single or many servers queuing network is introduced
here. The method is based on a theoretical study of the nature of flows to be Poisson or not, in a
Jackson network.
# INTRODUCTION

The performance of computer systems and data networks are often studied using queueing networks. Unfortunately as soon as the network in somewhat complex, the exact methods no longer exist and we need for accurate approximate methods. Presently, we have three types of such methods: iterative techniques [1] [2], diffusion techniques [3] [4] [5], isolation techniques [6] [7]. Our purpose here is to propose a new approach to study open complex queueing networks with single or many servers queues of the type G/G/s.

As we shall show it in the first section, queueing networks are very complicated to study when a customer can go through a station more than one time. This fact implies that even as in a so simple network as Jackson queueing systems, only some flows possess the Poisson property.

In particular we derive the characteristics of the input, output, feedback and departure processes of exponential queues in series, with a Poisson external arrival process and a global feedback. We show that input process and output process are identically distributed and different of a Poisson process. If n queues are in tandem a recursive formula is given to obtain these distributions.

By a decomposition technique we can predict the property to be Poisson or not of flows in a Jackson network.

As the main approximation in studying queueing networks comes from customers which can go through a station more than one time, we propose a new approach, in avoiding feedback customers. For this, we decompose the network in sub systems characterized by the fact that queues i and j belong to the same sub system if it is possible to go to i from j and to j from i. The only streams which do not possess feedback customers are inter sub network flows.

Then, each station of a sub network is studied in isolation considering that a customer entering the sub network goes through each station at most one time. We obtain mean number in station and response time for each queue, using an appropriate formula obtained by comparisons of available GI/G/1 expressions. The method is extended to take into account stations with many servers. The accuracy of the new method is shown using comparisons with results of simulations on some queueing systems.
M/M/1 QUEUE WITH BERNOULLI FEEDBACK

The model and notations

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>

The problem to be studied is illustrated in figure 1.

The arrival process is Poisson with parameter $\lambda$. The queueing discipline is FCFS (first come, first served) and the service process is also Poisson 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 instantaneous. We denote the traffic intensity by $o = \frac{\lambda}{\mu q}$.

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 and enter from outside respectively.

In this paper, we adopt the following notations :

- $A(t)$ : distribution function of the interinput times. Let us introduce the L.S.T (Laplace Stieltjes Transform)

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

- $S(t)$ : distribution function of the inter departure times

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

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

- $B(t) = 1 - e^{-\mu t}$ and $\hat{b}(s) = \frac{1}{\mu + s}$

The input process

This problem has been studied by P.J. Burke [8].

The distribution function of interarrival times is $1 - e^{-\lambda t}$. Let $t_0$ be the time of any input, and let $G(t)$ be the probability for the only customer to arrive between times $t_0$ and $t_0+t$ to be a feedback customer.

Then we can write

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

and if we use the L.S.T; (1) can be transformed to :

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

if we denote : $\hat{g}(\lambda+s) = \int_{0}^{\infty} e^{-(\lambda+s)t} dG(t)$
Now, we have to compute $\hat{g}(s)$.

Let $\pi(i)$ the equilibrium probability of state i, just before to

It can be showed (see Burke [7], Disney [9]), that $\pi(i) = e^{i}(1-e)$.

Let us denote $\pi(\ge i) = \sum_{j \ge i} \pi(j) = \pi^i$.

Using the fact that there is no arrival before the next feedback and using the value of $\pi(\ge i)$, we get :

$$ \hat{g}(s) = \sum_{i=0}^{\infty} \pi(\ge i) \rho q^i [\hat{B}(s)]^{i+1} $$

Therefore

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

and we find :

$$ g(t) = pue^{-(u-\lambda)t} $$

from (3) we obtain :

$$ \hat{g}(\lambda+s) = \frac{p\lambda}{\lambda+s} $$

Substituting the expression of $\hat{g}(\lambda+s)$ into (2) yields :

$$ \hat{a}(s) = \frac{\lambda u+s(du-\lambda)}{(\lambda+s)(u+s)} $$

or

$$ (4) \qquad \hat{a}(s) = \frac{p\lambda}{u-\lambda} \frac{u}{u+s} + \frac{uq-\lambda}{u-\lambda} \frac{\lambda}{\lambda+s} $$

then, if we take the inverse transformation

$$ (5) \qquad A(t) = 1 - \frac{p\lambda}{u-\lambda} e^{-\lambda(t-u)} - \frac{uq-\lambda}{u-\lambda} e^{-\lambda(t-s)} $$

We have to note that the input process is not Poisson.

Disney and McNickle [9] show this process is not even a renewal process

## The departure process

We analyse the departure process by the following substitution : a customer service time is replaced by the addition of the service times of all his successive returns.

Let $B^*(t)$ the p.d.f (probability distribution function) of the equivalent service time. L. Takacs [10] shows the result :

$$ B^*(t) = 1 - e^{-uq} $$

therefore, the p.d.f of the interdeparture times is :

$$ S(t) = \pi^*(o) \int_0^t (1 - e^{-\lambda(t-x)}) dB^*(x) + (1 - \pi^*(o)) B^*(t) $$
when $\pi^*(i)$ is the stationary probability of state i. in the equivalent system, but we know (see [8], [9]) that the distribution of the queue size is the same for both systems, then: $\pi(i) = \pi^*(i)$. Finally we get:

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

As the departure process is renewal [25], it is a Poisson process.

## The output process

Let us now, examine the distribution $F(t)$ of the times between two completeness of service. Such an interval is equal to a service time except when the queue becomes empty.

We denote by $\hat{f}(s)$ the L.S.T of the interoutput times. Therefore, the function $f(s)$ is:

$$\hat{f}(s) = \pi'(0) \frac{\lambda}{\lambda+s} (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 [11] proves the result $\pi'(0) = \pi(0)q = q[1 - \frac{\lambda}{\mu q}]$ then we get:

$$\hat{f}(s) = \frac{\mu q}{\mu - \lambda} \frac{\lambda}{\lambda + 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 (an hyperexponential distribution). This result was pointed out by R.L. Disney and D.G. McNickle [11]. Moreover, it is shown by Foley [28] this process also fails to be a renewal process.

## The feedback process

A complementary result is the L.S.T of the interfeedback times. We know that just after a feedback time the queue is in state i with the stationary probability $\pi(i-1)$ ([8]). Then, conditioning upon the number of customers in queue we can write:

$$\hat{r}(s) = \sum_{i=1}^{\infty} \pi(i-1)\alpha(i)$$

where $\alpha(i)$ is the L.S.T of interfeedback times knowing that the queue is in state i. We use an iterative technique to compute the function $\alpha(i)$. The time of the first event after the feedback is the lower of the first arrival and the first output. So the L.S.T of this time is $\frac{\lambda+\mu}{\lambda+\mu+s}$. With a probability $\frac{\lambda}{\lambda+\mu}$ (resp. $\frac{\mu q}{\lambda+\mu}$) this event is an arrival (resp : a departure) and now the queue is in state i+1 (resp : i-1), and with a probability $\frac{\mu q}{\lambda+\mu}$ this is a feedback. Then we have:

$$\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 q}{\lambda+\mu} \right] \quad i > 0$$

$$\alpha(0) = \frac{\lambda}{\lambda + s} \alpha(1)$$

This can be seen as an application of the strong Markov property. We write these equations as follows:

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

$$(7) \qquad (\lambda+\mu+s)\alpha(0) = \lambda\alpha(1)$$

Using $\pi(i) = \rho\pi(i-1)$ and (7), the summation of (6) for $i=1$ to $\infty$ after multiplica-
tion by $\pi(i-1)$ yields :

$$ (8) \qquad (up+s)\hat{r}(s) = up - \frac{up}{\lambda} s \pi(0)\alpha(0) $$

Now, we have to compute $\alpha(0)$ :

Setting $\alpha(i) = \beta(i) + \frac{up}{up+s}$ in (6), we get the following equation

$$ (\lambda+u+s)\beta(i) = \lambda\beta(i+1) + uq\beta(i-1) \quad i \ge 1 $$

and a solution of this last equation is

$$ (9) \qquad \beta(i) = a_1^i $$

where $a_1^i$ is the lower root of the equation

$$ \lambda x^2 - (\lambda+u+s)x + uq = 0 $$

(for more details see [27]).

Now, using (7) and (9), we deduce the system

$$ \left\{ \begin{array}{l} \alpha(0) = a + \frac{up}{up+s} \\[1em] \frac{\lambda+s}{\lambda} \alpha(0) = a \alpha_1 + \frac{up}{up+s} \end{array} \right. $$

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

$$ (10) \qquad (up+s)\hat{r}(s) = up-uqs\pi(0) \frac{up(1-a_1)}{(up+s)[\lambda(1-a_1)+s]} $$

Thus 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.

## RESULTS FOR TWO QUEUES IN SERIES

The two tandem queues system with feedback is illustrated on figure 2

<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>

The service times of the first server are distributed exponentially with parameter $u_1$ and L.S.T is $b_1(s)$; those of the second server are exponential with parameter $u_2$ and L.S.T is $b_2(s)$. A(t) is again the interinput distribution (mark I, on figure 2) and F(t) is the interoutput distribution (mark II, on figure 2), the equality (1) :

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

$$ 1 - F(t) = e^{-\lambda t}[1 - H(t)] $$
Using the L.S.T we obtain

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

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

And from (11) we get :

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

Now, we shall see (in part III) that the L.S.T $\hat{f}(s)$ can be easily found for n
tandem queues. For n=2, we have :

$$
\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)\hat{b}_1(s)\hat{b}_2(s)(p+q\rho_1) + \rho_2\hat{b}_2(s)
$$

$$
setting \ \rho_i = \frac{\lambda}{\mu_i q}, \quad (i=1,2).
$$

After some algebra, we find

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

Let us now compute the function $\hat{g}(s)$. Conditioning upon the states i and j of the
queue 1 and 2 we can write :

$$
(13) \quad \hat{g}(s) = \sum_{j=0}^{\infty} \pi_2(j) \sum_{i=1}^{\infty} \pi_1^{(i-1)} \alpha(i,j)
$$

where $\alpha(i,j)$ is the L.S.T of interval of time before the next arrival knowing that
the queue 1 is in state i with the stationary probability $\pi_1(i-1)$ and queue 2 is
in state j with the stationary probability $\pi_2(j)$. Let $t_0$ be the time of any input
in queue 1. The first event after $t_0$ is first of both possible service completion,
which L.S.T is $\frac{\mu_1+\mu_2}{\mu_1+\mu_2+s}$. Such as for $\alpha(i)$ in I.5 we get the following recurrent equa-
tions :

$$
(14) \quad (\mu_1+\mu_2+s)\alpha(i,j) = \mu_1\alpha(i-1,j+1) + \mu_2q\alpha(i,j-1) + \mu_2p \quad i>0, j>0
$$

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

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

And of course we have

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

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

Then the summation of (14) and (15) after multiplication by $\pi_1^{(i-1)}$ yields

$$
(18) \quad \begin{cases} (\mu_1+\mu_2+s)\gamma(j) = \mu_1[\pi_1^{(0)}\alpha(0,j+1) + \alpha_1\gamma(j+1)] + \mu_2q\gamma(j-1) - \mu_2p \quad j>0 \\ (\mu_1+s)\gamma(0) = \mu_1[\pi_1^{(0)}\alpha(0,1) + \alpha_1\gamma(1)] \end{cases}
$$
then, summing (18) upon $j$, to obtain
$$ \sum_{j=0}^{\infty} \pi_2(j) \gamma(s) = \hat{g}(s) $$
we get after reduction :

$$ (u_1+s-\lambda)\hat{g}(s) = u_1 \pi_1(0) \sum_{j=0}^{\infty} \pi_2(j)\alpha(o,j+1) + u_2 p [1-\pi_2(0)] $$

Now, we need to compute the time $\sum_{j=1}^{\infty} \pi_2(j)\alpha(o,j+1)$. From the equation (16) valid for $j \ge 2$ we get by summation and after reduction and using (17)

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

So, after simplification we finally get

$$ \hat{g}(s) = \frac{p[u_1 u_2 q + \lambda(s-\lambda)]}{q[u_1 + s - \lambda][u_2 + s - \lambda]} $$

this last expression is strictly equivalent to the one we obtained for the function $h(s)$. From this equality we come to the conclusion that the L.S.T a(s) and $f(s)$ are equal : the interinput times and interoutput times are identically distributed and different of the exponential distribution.

It is interesting (in view of generalization) to note that the last expression that we obtained for $\hat{g}(s)$ can be written as :

$$ \hat{g}(s) = p(1-\pi_2(0)) \frac{\hat{b}_2(s)}{1-q\rho_2\hat{b}_2(s)} + p\pi_2(0) \frac{\hat{b}_1(s)\hat{b}_2(s)}{[1-q\rho_1\hat{b}_1(s)][1-q\rho_2\hat{b}_2(s)]} $$

The main conclusion is that the feedback process is not Poisson.

GENERALIZATION TO n TANDEM QUEUES

Such a system is illustrated on figure 3

<figure><img src="image_5.png" /><figcaption>Figure 3</figcaption></figure>

$$ \text{Let } \hat{b}_i(s) = \int_0^\infty e^{-st} u_i e^{-u_i t} dt \quad i=1,2,\dots,n. $$

It is convenient to note $\hat{f}(s) = \hat{f}_n(s)$, where n indicate the number of tandem queues.

So we have :

$$ (19) \qquad \hat{f}_n(s) = q \sum_{i=1}^{n} (1-\alpha_i) \hat{b}_i(s) + (p+q\alpha_1) \hat{b}_1(s) \sum_{i=2}^{n} (1-\alpha_i) \hat{b}_i(s) \\ \qquad \qquad + \sum_{k=2}^{n-1} \alpha_k \hat{b}_k(s) \sum_{i=k+1}^{n} (1-\alpha_i) \hat{b}_i(s) + \alpha_n \hat{b}_n(s) $$

From (19), we deduce the recurrent equation
$$
(20) \qquad \hat{f}_n(s) = \hat{f}_{n-1}(s)(1-\rho_n)\hat{b}_n(s) + \rho_n\hat{b}_n(s) \quad n=2,3,\dots
$$

Since $\hat{h}_n(s) = \frac{s\hat{f}_n(s-\lambda)-\lambda}{s-\lambda}$, for all $n=1,2,\dots$. We show that the functions $\hat{h}_n(s)$ also verify

$$
(21) \qquad \hat{h}_n(s) = \hat{h}_{n-1}(s)(1-\rho_n)\hat{b}_n(s-\lambda) + \rho_n\hat{b}_n(s-\lambda)
$$

By setting $\hat{B}_n(s) = \frac{\hat{b}_n(s)}{1-q\rho_n\hat{b}_n(s)} = \frac{\lambda_n}{\lambda_n+s-\lambda}$, we have $\hat{B}_n(s) = \hat{b}_n(s-\lambda)$.

Therefore (21) is equivalent to

$$
(22) \qquad \boxed{\hat{h}_n(s) = \hat{h}_{n-1}(s)(1-\rho_n)\hat{B}_n(s) + \rho_n\hat{B}_n(s)}
$$

Moreover, from the two queues case, we deduce

$$
\hat{g}_n(s) = \rho_n \hat{B}_n(s) + \hat{g}_{n-1}(s) \frac{\hat{b}_n(s)(1-\rho_n)}{1-\rho_n \hat{b}_n(s)}
$$

$$
(23) \qquad \hat{g}_n(s) = \rho_n \hat{B}_n(s) + \hat{g}_{n-1}(s)(1-\rho_n) \hat{B}_n(s)
$$

In parts I, II, we showed that $\hat{g}_n(s) = \hat{h}_n(s)$ for $n=1,2$. The equations (22), (23)
prove that $g_n(s) = h_n(s)$ for any $n$. That is to say, whatever the number of
tandem queues, the input distribution and the output distribution are identically
distributed.

Moreover, we show in a second paper [27] that these distributions fails to be Pois-
son. Indeed we prove in this second paper that the distribution of interinput and
interoutput intervals are identically distributed. Therefore, it is obvious from
this result that the flow between two any queues is not a Poisson process.

We easily verify that, when n tends to infinity, the interinput (or interoutput)
times are exponentially distributed with parameter $\lambda q^{-1}$.

ON A PROPERTY OF JACKSON NETWORKS AND A DECOMPOSITION OF A GENERAL NETWORK

We have shown that the only streams which possesses the property to be a Poisson
process in a feedback tandem queueing system, are the external arrival process and
the departure process. Now let R be a general network and on this network, let i←j
be the following relation of equivalence : from i it is possible to go to j and
from j it is possible to go to i. The classes of equivalence of this relation are
subnetworks such that when a customer leaves a subnetwork he never returns it. We
name them irreducible subnetwork. The global network can now be decomposed in these
irreducible subnetworks as shown in figure 4.
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>

represents an irreducible sub network

When a customer goes out of an irreducible network he never returns.

For a given irreducible network we are going to examine the distribution of departure processes. From Kelly [25] we know that the customers leaving the system form a Poisson stream. Now from feedback property we have shown in the previous sections, that all the other flows are not Poisson processes. (Due to the irreducibility of the network, for each station we can build at least one tandem queueing system including this station, among the paths of the network).

This proves that all the flows except external arrival and departure streams are not Poisson.

If we come back to our global Jackson network, we can conclude that the streams between two any stations of a same irreducible subnetwork are not Poisson but that external arrival and departure processes of each individual subnetwork are Poisson. The only Poisson processes in a Jackson network, are inter irreducible subnetwork streams. Indeed they are even the only renewal process as we show it in a further paper.

## GENERAL OUEUEING NETWORK : A NEW APPROACH

We have shown that in a Jackson network only few streams have the property to be Poisson processes. Moreover, we have shown that input and output processes fail to be renewal, as soon as feedback customers are allowed. Now if we are interested by general queueing networks even streams without feedback customers are no longer renewal processes, but the dependances come only from the service time distributions (dependence by feedback customers are abolished). So, we propose the following new technique to study a general queueing networks :

1. the network is decomposed into its irreducible sub systems;

2. for each separate subnetwork, we compute the mean number of passage at each station;
3 - each station of each sub system is studied in isolation considering that the customers go through it one time and only one time.

We deal now with the last point in a more detailed manner; the decomposition has been studied in the previous section and the computation of the mean number of passage at each station for each sub system is obvious.

Study of each station. After to have decomposed our global network, we study each subsystem independently. For a given irreducible subnetwork, let $\lambda$ be the arrival rate entering this subsystem and $e = (e_1,e_2,...,e_n)$ be the solution of $e=q+e_0$ where $q=(q_{01},q_{02},...,q_{0n})$ is the probability to enter this sub-system by station $i: Q = \{q_i: 1 \le i \le n; 1 \le j \le n\}$ is the matrix of transition probabilities where $n$ is the number of stations in the irreducible subnetwork. The quantity $e_k, k=1,...,n$ gives the mean number of passages in the station $k$. (*)

Our new approach consists to assume that the customers go through the station only one time (there is no longer feedback customers), see figure 5. So we are going to define an equivalent service time and a new input process. The new service time of a station is the total time spent by a customer in its server. For station $k$, $k=1,...,n$, the new service time distribution (see figure 5) is defined by its rate $\tilde{\lambda}_k=\mu_k/e_k$ and its squared coefficient of variation (SCV) $\hat{K}_k=p_k+Ks_k(1-p_k)$ with $p_k = \max(\frac{e_k-1}{e_k},0)$ (if $e_k$ is less than 1, namely the mean number of passage is less than 1, then $p_k=0$ and $\hat{K}_k=Ks_k$).

<figure><img src="image_8.png" /><figcaption>Figure 5</figcaption></figure>

<footnote>(*) Let $\lambda'$ and $e'_k$ be the total arrival rate in the general network and the mean number of passage computed on the general network. Generally $e_k$ is different of $e'_k$ but $\lambda' e'_k = \lambda e_k$. $e_k$ is the mean number of passage through station $k$ knowing the customer enters the subnetwork we consider.</footnote>
The equivalent arrival process is then defined assuming that all the customers entering the subnetwork go through each station one time and only one time. The equivalent arrival rate is $\lambda_k=\lambda$, k=1,...,n. Before to compute the SCV of the new arrival process we need to know the SCV of the initial arrival process. This one can be computed from several manners : Kobayashi [3], Gelenbe and Pujolle [5] or Sevcik et al [2]. We shall adopt a simplification of the second one (see Gelenbe and Mitrani [12]) :

$$Ka_k = \frac{1}{\lambda_k} \sum_{j=0}^{n} [(c_j - 1)q_{jk} + 1] \lambda_j q_{jk} \quad \text{with } \lambda_k = \lambda e_k$$

where $c_j$ is the SCV of the inter departure times at station j and whose an approximated value is :

$$c_j = \frac{\rho_j^2 (Ks_j - 1)}{1 - (1 - \rho_j) q_{jj}^2} + 1, \quad j=1,...,n.$$

$c_o$ is the SCV of the inter arrival times of external customers.

Now, the SCV of the arrival process at station k, k=1,...,n is $\tilde{K}a_k=p_k+Ka_k(1-p_k)$.

Now, we have characterized each station by their two first moments of service and input processes, we have only to choose an adequate formula giving the response time and the mean number in station.

Firstly we have examined the case of a single server queue GI/G/1. A certain number of approximated formulae can be used. We have compared them one another using the mean number in station. They are the following ones :

1 - Kingman [13] $\bar{n} = \rho[1 + \frac{(Ka+Ks)}{2(1-\rho)}]$

2 - formula obtained by diffusion approximations

$$2a - [3] \qquad \bar{n} = \frac{\rho}{1-\rho} \quad \text{with} \quad \bar{\rho} = \exp\left[\frac{2(1-\rho)}{\rho Ka + Ks}\right]$$

$$2b - [14] \qquad \bar{n} = \rho[1 + \frac{\rho Ka + Ks}{2(1-\rho)}]$$

3 - Page [15] $\bar{n} = \rho+KaKs\bar{n}_{M/M/1}+Ka(1-Ks)\bar{n}_{M/D/1}+Ks(1-Ka)\bar{n}_{D/M/1}$ where $\bar{n}_{G/G/1}$ is the mean number in the station G/G/1 (for $\bar{n}_{D/M/1}$ we have used Kingman's formula);

4 - Kramer and Langenback - Belz [16] :

$$\bar{n} = \rho[1 + \frac{\rho(Ka+Ks)}{2(1-\rho)} \times g]$$

$$\text{with } g = \begin{cases} \exp\left[-\frac{2(1-\rho)(1-Ka)^2}{3\rho(Ka+Ks)}\right] & \text{if } Ka < 1 \\ \exp\left[-\frac{(1-\rho)(Ka-1)}{Ka+4Ks}\right] & \text{if } Ka \ge 1. \end{cases}$$

Other formulae have been examined as Marchal [17] and Kingman [18] ones, but they are bounds and not very accurate approximations.

Among the previous expressions 1, 3 and 4 have the advantage to give the exact Khintchine-Pollaczek formula for M/G/1 queueing system.
We shall say that a formula is correct if the result has an accuracy of the same order as a simulation (10% at the maximum). Diffusion formulae are correct only on small intervals, Page is almost always correct when Ka and Ks are less than 1; Kingman when Ka and Ks are close to 1. Finally formula 4 is very satisfying: for practically all the cases examined ($0 \le Ka \le 3$ and $0 \le Ks \le 3$) the accuracy is very good. So we have adopted this expression for the computation of the mean number in station in our approach of queueing systems.

Now, if many server queues exist, our approach is the following: for the aim to determine only the departure process, the servers are replaced by just one server whose distribution function $G(t)$ is chosen to satisfy $G(t) = F(st)$ where $s$ is the number of servers and $F(t)$ the distribution function for the service time of any server of the many server queue. The accuracy of this approximation about the departure process is evaluated by Arjas [19]. With this intermediate approximation we can now calculate the equivalent arrival and service processes.

About the mean number in station some formulae can be used. We have compared their results:

$$1 - \text{Kingman [20]} : \quad \bar{n} = s_c + \frac{Ka+c^2Ks}{2(1-\bar{o})}$$

$$2 - \text{Sakasegawa [21]} : \quad \bar{n} = s_c + \frac{(Ka+Ks)c\sqrt{2(s+1)}}{2(1-\bar{o})}$$

$$3 - \text{Pujolle [22] (obtained by diffusion)} \\ \qquad \bar{n} = \sum_{n=1}^{\infty} n p(n)$$

$$\text{if } n \le s \quad p(n) = [1-p(\bar{o})] c \hat{o}(1)\hat{o}(2) \dots \hat{o}(n)$$

$$\text{if } n \ge s \quad p(n) = [1-p(\bar{o})] c \hat{o}(1)\hat{o}(2) \dots \hat{o}(s-1)\hat{o}(s)^{n-s+1} \\ \qquad p(\bar{o}) = [1+\hat{o}(1)+\hat{o}(2)+\dots+\hat{o}(s-1)]^{-1}$$

$$\text{and} \quad c = \left[ \sum_{i=1}^{\infty} p(i) \right]^{-1} = [\hat{o}(1)+\hat{o}(2)+\dots+\frac{\hat{o}(1)\dots\hat{o}(s-1)}{1-\hat{o}(s)}]^{-1}$$

$$\text{with} \quad \hat{o}(n) = \exp\left[\frac{2(\lambda-nu)}{\lambda Ka+nuKs}\right], \quad \hat{o}(n) = \frac{\lambda}{nu}.$$

We have also compared the results obtained by Stoyan [23] and Brumelle [24] which worked on bounds.

Results of these comparisons show the good accuracy of Sakasagawa's formula when $Ka \le 1.2$ and $Ks \le 1.2$, that we shall adopt in these limits. Finally formula 3 is taken in the other cases. It remains correct when Ka and Ks are not too large: $Ka$ and $Ks$ less than 2.

**Accuracy of the method and conclusion.** Firstly we have to note that for a Jackson network the exact result is found again by our new approach. Then, we have compared the solution of our new approach with simulation results on different queueing systems. Mainly, we have used the central server model (with the main queue representing the CPU and the feedback queues, the swapping devices) and tandem queueing systems. These two types of systems can be considered as extreme cases: the former is an irreducible subnetwork by itself.

On table 2 we have compared the results obtained by our new approach to previous
methods : Kühn [6], and diffusion approximations : Reiser and Kobayashi [26]. Gelenbe and Pujolle [4]. The model we have adopted is shown in figure 6 and the values of the parameters in table 1. The results of a simulation conducted by Kühn are given in table 2, and also the relative differences referred to simulation results of Kühn.

<figure><img src="image_9.png" /><figcaption>Figure 6</figcaption></figure>

<table><caption>Table 1</caption><thead><tr><th>case</th><th>λ</th><th>μ<sub>1</sub><sup>-1</sup></th><th>Ks<sub>1</sub></th><th>μ<sub>2</sub><sup>-1</sup></th><th>Ks<sub>2</sub></th></tr></thead><tbody><tr><td>1</td><td>0.5</td><td>0.9</td><td>0.5</td><td>0.84</td><td>0</td></tr><tr><td>2</td><td>0.5</td><td>0.95</td><td>0.5</td><td>0.89</td><td>0</td></tr><tr><td>3</td><td>0.5</td><td>0.9</td><td>1</td><td>0.84</td><td>1</td></tr><tr><td>4</td><td>0.5</td><td>0.95</td><td>1</td><td>0.89</td><td>1</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Case</th><th colspan="2">Simulation Kühn<br>10<sup>6</sup> events</th><th colspan="2">Theory<br>Kühn</th><th colspan="2">Theory<br>Reiser<br>Kobayashi</th><th colspan="2">Theory<br>Gelenbe<br>Pujolle</th><th colspan="2">Theory<br>Pujolle<br>Soula</th></tr><tr><th>n&#773;<sub>1</sub></th><th>n&#773;<sub>2</sub></th><th>n&#773;<sub>1</sub></th><th>n&#773;<sub>2</sub></th><th>n&#773;<sub>1</sub></th><th>n&#773;<sub>2</sub></th><th>n&#773;<sub>1</sub></th><th>n&#773;<sub>2</sub></th><th>n&#773;<sub>1</sub></th><th>n&#773;<sub>2</sub></th></tr></thead><tbody><tr><td>1</td><td>7.36</td><td>0.45</td><td>6.12<br>16.8%</td><td>3.64<br>12.5%</td><td>5.70<br>8.1%</td><td>2.70<br>35%</td><td>5.65<br>9.6%</td><td>2.95<br>29%</td><td>7.53<br>2.3%</td><td>4.04<br>2.8%</td></tr><tr><td>2</td><td>13.69</td><td>1.32</td><td>12.47<br>8.9%</td><td>5.42<br>7.2%</td><td>14.30<br>4.4%</td><td>4.52<br>22.6%</td><td>12.62<br>7.8%</td><td>4.39<br>24.8%</td><td>14.61<br>7.1%</td><td>5.72<br>2%</td></tr><tr><td>3</td><td></td><td></td><td>9<br>exact</td><td>5.25</td><td>9.007</td><td>5.26</td><td>9.46</td><td>5.30</td><td>9<br>exact</td><td>5.25<br>exact</td></tr><tr><td>4</td><td></td><td></td><td>19<br>exact</td><td>8.09</td><td>19.004</td><td>8.10</td><td>19.53</td><td>8.65</td><td>19<br>exact</td><td>8.09<br>exact</td></tr></tbody></table>
With single server queues and SCV of service times less than 3, the results of all the tests we have made are in the confidence interval given by the simulation. With many server queues the results we obtained are of the same accuracy when the SCV of service times are between 1.5 and 0.5 and is not very far of the confidence interval when SCV of service times are less than 0.5 or between 1.5 and 2.

Finally, with our new approach we can predict with a good accuracy (better than with diffusion or iterative techniques) the behavior of a general single queueing system.

Another advantage is the possibility to study also many server queueing systems. In this last domain improvements are possible, especially by an accurate formula giving the mean number in the stations GI/G/s when SCV are either close to 0 or greater than 2.

## ACKNOWLEDGEMENTS

We would like to thank Dr. D. Foley and Professor I. Mitrani for their comments and suggestions on the manuscript.

## REFERENCES

[ 1 ] Chandy K.M., Herzog U., Woo L., "Parametric analysis of queueing networks" IBM J. Res. Develop. 19, 36-42, 1975.

[ 2 ] Sevcik K.C., Levy A.I., Tripathi S.K., Zahoyan J.L., "Improving approximations of aggregated queueing network subsystems", proc. of IFIP WG 7.3, Yorktown Heights, 1977.

[ 3 ] Kobayashi H., "Application of the diffusion approximation to queueing networks I", JACM 21, 2, 316-328, 1974.

[ 4 ] Gelenbe E., Pujolle G., "The behaviour of a single queue in a general queueing network", Acta Informatica 7, 123-136, 1976.

[ 5 ] Gelenbe E., Pujolle G., "A diffusion model for multiple class queueing networks", proc. of the 3rd International Symposium on Modelling and Performance Evaluation of Computer System, Bonn, 1977.

[ 6 ] Kühn P., "Analysis of complex queueing networks by decomposition", proc. of 8th International Teletraffic Congress, Melbourne, 1976.

[ 7 ] Labetoulle J., Pujolle G., "Modeling of packet switching communication network with finite buffer size at each node", proc. of IFIP WG 7.3, Yortown Heights, 1977.

[ 8 ] Burke P.J., "Proof of a conjective on the interarrival time distribution in a M/M/1 queue with feedback", IEEE Transaction on Communication 24, 175-178, 1976.

[ 9 ] Disney R., McNickle D.C., "The M/G/1 queue with instantaneous Bernoulli feedback", Technical report 77 - 4, University of Michigan, Ann Arbor, 1977.

[10] Takacs L., "A single server queue with feedback", Bell system Journal 42, 505-519, 1963.

[11] Melamed B., Zeigler B.P., Beutler F., "Simplifications of Jackson queueing network", technical report 163, University of Michigan, 1975.

[12] Gelenbe E., Mitrani I., "Analysis and synthesis of computer system models, to appear.

[13] Kingman J.F.C., "Some inequalities for the GI/G/1 queue", Biometrika 49, 315-324, 1962.

[14] Gelenbe E., "On approximate computer system models", J.ACM, 22, 2, 261-299, 1975.
[15] Page E., "Queueing theory in Operations research", Butterworths, 1972.

[16] Kramer W., Langenback-Belz M., "Approximate formulae for the delay in the queueing system GI/G/1", Proc. of 8th International Teletraffic Congress, Melbourne, 1976.

[17] Marchal W.G., "Some simple bounds and approximations in queueing", Research Report T. 294, George Washington University, 1974.

[18] Kingman J.F.C., "Inequalities in theory of queues", J.R. Statist. Soc. B. 32, 102-110, 1970.

[19] Arjas E., "Approximating many server queues by mean of single server queues", to appear in Mathematics of Operations Research (also Research Report D-21, University of Oulu, Helsinki, 1977).

[20] Kingman J.F.C., "The heavy traffic approximation in the theory of queues", Proc. Symposium on Congestion Theory, University of North Carolina, 137-169, 1964.

[21] Sakasegawa H., "An approximation formula $Lq \approx \alpha_0 B^{(1-\rho)}$, Annals of the Institute of Statistical Mathematics 29, 1, 67-75, 1977.

[22] Pujolle G., "Files d'attente avec dépendance de l'éata" Proc. of SMF/AFCET Congrès, Palaiseau, 1978.

[23] Stoyan D., "Some bounds for many server systems GI/G/s", Math. Operations forsch. Statit. 5, 117-129, 1974.

[24] Brumelle S.L., "Some inequalities for parallel server queues", Oper. Res. 19, 402-413, 1971.

[25] Kelly F.P., "Networks of queues", Adv. Appl. Prob. 8, 416-432, 1976.

[26] Reiser M., Kobayashi H., "Accuracy of the diffusion approximation for some queueing systems", IBM J. Res. Devel. 18, 2, 110-124, 1974.

[27] Labétoulle J., Pujolle G., Soula C., "Distribution of the flows in a general Jackson network", to appear.

[28] Foley R.D., "On the output process of an M/M/1 queue with feedback", Research Report of the University of Michigan, 1977.