IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

F

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

Probabilistic models
of computer systems
part II

Erol GUY
E. Gelenbe, G. Pujolle

Rapport de Recherche n°147
Décembre 1975
PROBABILISTIC MODELS OF COMPUTER SYSTEMS - PART II
(APPROXIMATION TO A SINGLE QUEUE IN A NETWORK)

E. Gelenbe, G. Pujolle

RÉSUMÉ :

A l'aide d'une approximation par les processus de diffusion, nous développons une méthode pour calculer, sous des conditions très générales, la distribution du temps d'attente d'une station quelconque d'un réseau. Des applications aux réseaux d'ordinateurs et à des systèmes informatiques travaillant en temps partagé, sont présentées.

ABSTRACT :

We develop a method based on diffusion approximations in order to compute, under some general conditions, the queue length probability distribution of a single queue in a network of queues. Several applications of this approach to computer network performance analysis and to time-sharing systems are presented. The accuracy of model predictions are evaluated by comparison with known exact results in particular cases, with simulation experiments and with the approximation method of Reiser-Kobayashi.

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

# 1. Introduction

Though considerable progress has been made in obtaining exact solutions for large classes of queueing network models [1, 2], one particularly simple type of network, an arbitrary network with first-come-first-served (FCFS) service discipline and general distribution function of service time at the servers, has proved to be resilient to all approaches except for approximate solution techniques. Here our attention is limited to this type of queueing network.

Several approximation methods have been suggested for its treatment. On the one hand there are diffusion approximations [3, 4, 5] applicable to two-station networks or to general queueing networks [6, 7], and on the other hand we have iterative techniques [8]. The convergence of the latter to the exact solution is not an established fact and we know that the former tend, in certain simple cases, to the exact solution under heavy traffic assumptions.

Although most of the work published in the literature has concentrated on evaluating the joint probability distribution of queue lengths for all the queues in a network, it is seldom possible to make use of this complete information. In measurements on computer systems it is difficult enough to collect data on the performance of a single resource, and the measurement of joint data for several resources could become very time and space consuming.

The same can be said of simulation experiments where the task of
estimating confidence intervals for estimated joint statistics
becomes impractical. Furthermore when it comes to computing average
response times it suffices to know the average response time
encountered in each individual queue. Therefore it would suffice in
most cases to be able to compute within satisfactory accuracy the
probability distribution for the queue length in each individual queue
in the network.

In this note we present an approximation method using a
diffusion model to obtain the stationary probability of queue length
for any given queue in an open or closed queueing network composed
of FCFS service stations, each composed of a single server with
general service time distribution. The method is applied to a
simple example of interest and the model predictions are compared
with simulation results.

The approximation technique we propose is based on assuming
that the output from any queue in the network forms a renewal process.
First consider the general network of Figure 1 in which:

(i) external arrivals constitute a renewal process of rate $\lambda_o$; the variance of the interarrival time is $V_o$.

(ii) the transition of customers from one station to another is
defined by a first order Markov chain with transition matrix
$P = (p_{ij})$, $p_{ij} \le 1$, $i \le n+1$, $j \le n+1$, being the probability that a
customer having terminated its service at station i then enters
station j, or leaves the system when $j = n+1$; P is assumed to have
a single absorbing state $n+1$.

(iii) the service times for successive customers at station i are
independent and identically distributed with common distribution function $F_1(t)$; service times are also independent from one station to the other.

(iv) customers first entering the network are directed to station i with fixed probability $p_{oi}$.

Let $e_i$, $1 \le i \le n$, be the solution to the system of equations

$$e_i = p_{oi} + \sum_{j=1}^{n} e_j p_{ji}$$

which is unique under the assumptions we have made. Then $e_i$ is the expected number of visits which a customer of the network will make to station i. The arrival rate of customers to station i is then $\lambda e_i$ at steady-state; also the steady-state probability $u_i$ that station i contains at least one customer is given by

$$u_i = \frac{\lambda e_i}{\mu_i} \quad \text{if } \lambda e_i < \mu_i \quad \text{where}$$

$$\mu_i^{-1} = \int_0^\infty t dF_1(t)$$

is the average service time for a customer at station i. These facts can be easily established rigorously; one way is to treat an open network of this kind as a limiting case of a closed network when one station is saturated and to apply the work-rate theorem [9].
## 2. Diffusion approximation for a single queue

In this section we briefly review some material on diffusion approximations which will be used in this paper [3, 4, 5].

Consider a queue with FCFS service and suppose that at time $t = 0$ a busy period of the queue begins. Interarrival times are independent and identically distributed, of mean and variance $\lambda^{-1}$ and $V_a$, respectively. Service times are independent of inter-arrival times and of each other, and are identically distributed with mean and variance $\mu^{-1}$ and $V_s$ respectively. Let $A(t)$, $D(t)$ be the total number of arrivals and departures up to time $t$, where $t$ is some instant during the busy period beginning at $t = 0$. Then for $t$ large enough, $A(t)$, $D(t)$ will be approximately normally distributed with mean $\lambda t$, $\mu t$ respectively, and variance $\lambda^3 V_a t$, $\mu^3 V_s t$, respectively. Thus $N(t)$, the number in queue at time $t$, will be approximately normal with mean $(\lambda - \mu)t$ and variance $(\lambda^3 V_a + \mu^3 V_s)t$, since $N(t) = A(t) - D(t)$. Thus $N(t)$ may be approximated by a continuous random variable $X(t)$ whose probability density function

$$f(x, t) \, dx = \text{Pr}[x \le X(t) < x+dx]$$

satisfies, for $X(t) > 1$ the diffusion equation

$$-\frac{\partial f}{\partial t} - b \frac{\partial f}{\partial x} + \frac{1}{2} \alpha \frac{\partial^2 f}{\partial x^2} = 0$$

where $b = \lambda - \mu$, $\alpha = \lambda^3 V_a + \mu^3 V_s$. For values of $X(t)$ in $[0, \infty]$ we follow the approach in [5]. Let $P(t)$ be the probability that $X(t) = 0$. Then for $X(t)$ on the non-negative real line we have
$$ (1) \quad \left\{ \begin{array}{l} -\frac{\partial f}{\partial t} - b \frac{\partial f}{\partial x} + \frac{1}{2} \alpha \frac{\partial^2 f}{\partial x^2} + \Lambda P(t) \delta(x-1) = 0 \\[1em] \frac{dP(t)}{dt} = -\Lambda P(t) + \lim_{x \to 0} + \frac{1}{2} \alpha \frac{\partial f}{\partial x} \\[1em] f(0) = 0 \end{array} \right. $$

where the term containing the Dirac delta function $δ(x-1)$ in the first equation represents an arrival to the queue after an idle period of average duration $Λ^{-1}$. These equations are fully interpreted in [5]. Let us mention that they assume that the idle time is exponentially distributed with mean $Λ^{-1}$; this is not a restriction for our purposes for the following reason.

It is shown in [10-b] that the steady-state solution to (1) is identical to the steady-state probability distribution obtained for a more elaborate version of (1) where the idle time has the same mean $Λ^{-1}$ but obeys a general (differentiable) distribution function. The equilibrium (steady state) solution to (1) is

$$ \left\{ \begin{array}{l} f(x) = \begin{cases} \Lambda(e^{-\gamma}-1)e^{\gamma x}, & x \ge 1 \\ R(1-e^{\gamma x}), & 0 \le x \le 1 \end{cases} \\[1em] P(0) = 1 - \frac{\Lambda}{\Lambda + \mu - \lambda} \approx 1-R \end{array} \right. $$

where $γ = \frac{2b}{α}$; the solution exists if $γ < 0$ as would be expected, since it implies the $λ < μ$. We set $Λ = λ$ since it is known that the steady-state probability that the queue being modelled is empty is $(1-λμ)^{-1}$. Thus the solution we adopt is:
$$ (2) \quad \left\{ \begin{aligned} f(x) &= \begin{cases} u(e^{-\gamma}-1)e^{\gamma x}, & x \ge 1 \\ u(1-e^{\gamma x}), & 0 \le x \le 1 \end{cases} \\ P(0) &= 1-u, \quad u = \lambda\mu^{-1} \end{aligned} \right. $$

In section 4 we shall choose the parameters $\alpha, \beta, \lambda, \mu$, in (2) so as to approximate the behavior of a single queue in an open queueing network.
### 3. The approach of Reiser and Kobayashi for queueing networks

In [6], Kobayashi proposed a generalization to an open or closed queueing network of arbitrary topology of the results of Gaver and Shedler [4]. Kobayashi imposes reflecting boundaries to the n-dimensional diffusion process and arrives at an equilibrium joint distribution of queue lengths which is in product form. He introduces from queueing theory the probability of an empty queue for each queue to modify the solution of the diffusion equation so as to obtain a more accurate representation of queue length distribution. Reiser and Kobayashi [7] have presented a simplified diffusion model which necessitates considerably less numerical computation for obtaining the model parameters but which leads to a comparable degree of accuracy. We briefly review here their approach.

The squared coefficient of variation of the interarrival time to queue i is taken to be

$$ (3) \qquad K^{(1)} = (\lambda_i)^{-1} \sum_{j=0}^{n} [(K_j-1)p_{ji} + 1]\lambda_j p_{ji} $$

where $\lambda_j = \lambda_0 e_j$, $1 \le j \le n$, and $K_j$ is the squared coefficient of variation of the service time at queue j if $j \ne 0$; $K_0 = \lambda_0^2 v_0$. An equilibrium queue size distribution

$$ (4) \qquad p_i(m_i) = \begin{cases} 1-u_i & \text{if } m_i = 0 \\ u_i(1-\delta_i)\delta_i^{m_i-1} & \text{if } m_i \ge 1 \end{cases} $$

is proposed for queue i where $m_i$ is the i-th queue's length, and

$$ \delta_i = e^{\gamma_i} $$
where

$$ (5) \qquad \gamma_i = \frac{2(\lambda_i - \mu_i)}{\lambda_i K^{(i)} + \mu_i K_i} $$

The approximation proposed for the joint probability distribution is

$$ (6) \qquad p(m_1, \dots, m_n) = \prod_{i=1}^{n} p_i(m_i) $$

for the n queues in an open network. Obviously the result is valid only when $\lambda_i < \mu_i$, $1 \le i \le n$.

For a closed network, the following treatment has been suggested in [7]. Suppose $\hat{u}_i$ is the utilization of server i; the joint probability distribution is taken to be (for M customers in the network):

$$ (7) \qquad \hat{p}(m_1, \dots, m_n) = G' \prod_{i=1}^{n} p_i(m_i) $$

where

$$ (8) \qquad \hat{p}_i(m_i) = \begin{cases} 1 - \hat{u}_i, & m_i = 0 \\ \hat{u}_i (1 - \hat{p}_i) \beta_i^{m_i - 1}, & m_i = 1, 2, \dots, M \end{cases} $$

and $G'$ is a normalizing constant. Several methods are suggested for choosing $u_i$. The simplest seems to be to assume that M is sufficiently large so that there exists a "bottle-neck" queue (say k) whose utilization is 1. Then

$$ (9) \qquad \hat{u}_i = \frac{\Pi_i \mu_k}{\Pi_k \mu_i} $$

where $\Pi_i, \Pi_k$ are the equilibrium probabilities that a customer will be at station i, k, respectively. This is, of course, an application of the work-rate theorem [9].
This approach has some obvious shortcomings in certain cases. Consider for instance the sequence of two FCFS service stations shown on Figure 2. Suppose station 1 has constant service time and that arrivals to the system are Poisson of rate $\lambda$. Assume also that we wanted to compute the queue length distribution at station 2 using (4). We would then have from (2)

$$K^{(2)} = 1$$

using $u_1 = \frac{\lambda}{\mu_1}$. This would mean that we would be using a diffusion model for station 2 in which it is assumed that arrivals to station 2 are Poisson, which is only true when $u_1 = 0$. When $u_1$ is close to 1, which is when the diffusion approximation for station 1 works well, we have nearly constant interarrival times to station 2 ($K^{(2)} \approx 0$) which is very different from what the model predicts.
4. Diffusion approximation to the behavior of a single queue in an open network

The approach we develop in this section is based on the following assumption which in general is unjustified: the departure process from any station in the open network is a renewal process, i.e. times between successive departures are independent and identically distributed. 1) This assumption is valid in the open network with Poisson arrivals and exponentially distributed service times. It is also valid for the output of station i when $\frac{\lambda_o e_i}{\mu_i} \ge 1$, or when all $u_j \approx 0$. Let $C_i$, $1 \ge i \ge n$, be the squared coefficient of variation of the interdeparture times at station i, and denote by $A_i$ the interarrival time, by $S_i$ the service time, by $A'_i$ the idle time, and by $\tau_i$ the interdeparture time. We shall define $C_o = K_o$ in order to maintain a uniform presentation.

Then for t large enough, and assuming that the output processes from each individual queue are independent, the total number of arrivals to station i in the interval $[0, t]$ will be normally distributed with mean $\lambda_i t$ and variance

$$ (10) \qquad \sum_{j=0}^{n} \left[ (C_j - 1)p_{ji} + 1 \right] \lambda_j p_{ji} t $$

Here we have used the fact that the sum of independent normal random variables is normal with variance being the sum of individual variances.

In the usual diffusion equations for approximating the length of queue i (equations (1)) the following parameters will be chosen:

1) We shall make use of this assumption in order to compute the first two moments of the interdeparture time distribution, though it is in general not satisfied. We shall see in Sections 5,6,7 that it does lead to accurate predictions.
$$ (11) \quad \left\{ \begin{array}{l} b_i = \lambda_i - \mu_i, \quad \Lambda_i = \lambda_i \\ \\ \alpha_i = \mu_i K_i + \sum_{j=0}^{n} [(C_j - 1)p_{ji} + 1]\lambda_j p_{ji} \end{array} \right. $$

where the subscript i refers to the parameters of the equation for the i-th queue. The value of $\alpha_i$ used by Reiser and Kobayashi (see (4) and (5)) is

$$ \alpha_i' = \mu_i K_i + \sum_{j=0}^{n} [(C_j - 1)p_{ji} + 1]\lambda_j p_{ji} $$

In order to complete the development we must obtain $C_i$, $1 \le i \le n$. We shall assume that $\tau_i$ is a service time $S_i$ with probability $u_i$ or an interarrival time plus a service time $A_i + S_i$ with probability $(1-u_i)$. We then have

$$ E\{\tau_i\} = u_i \mu_i^{-1} + (1-u_i)(\lambda_i^{-1} + \mu_i^{-1}) = \lambda_i^{-1} $$

as would be expected, and

$$ E\{\tau_i^2\} = (\lambda_i^{-1})^2 (1 + C_i) = E\{S_i^2\} + (1-u_i)(E\{A_i^2\} + 2E\{A_i\}E\{S_i\}) $$

so that

$$ (12) \quad C_i + 1 = u_i^2 (K_i + 1) + (1-u_i) (\lambda_i^2 E\{A_i^2\} + 2u_i) $$

Finally we use (10) in the following manner; we assume it is the variance of the number of arrivals in $[0, t]$, for large $t$, of a renewal process. Therefore

$$ \sum_{j=0}^{n} [(C_j - 1)p_{ji} + 1]\lambda_j p_{ji} = \lambda_i^3 (E\{A_i^2\} - (\lambda_i^{-1})^2) $$

and for $1 \le i \le n$, taking
$$ (13) \qquad C_i = u_i^2 (K_i + 1) + (1-u_i) \left[ 2u_i + 1 + \lambda_i^{-1} \sum_{j=0}^{n} \left[ (C_j-1)p_{ji} + 1 \right] \lambda_j p_{ji} \right]^{-1} $$

The values of the $C_i$, $1 \le i \le n$, to be used in (11) are the solutions to the system of equations (13).

In the case of a queueing network with exponentially distributed service times and Poisson arrivals, setting $K_i = 1$ we see that (13) has the unique solution $C_i = 1$, $1 \le i \le n$. In the case of the example of Figure 2 we would have

$$ C_1 = u_1^2 + (1-u_1)[2u_1 + 1 + \lambda^{-1}\lambda]^{-1} = 1 - u_1^2 $$

as the squared coefficient of variation of interarrival times to station 2, rather than the value $K^{(2)} = 1$ which would have been obtained by the method of Reiser and Kobayashi.

## 5. Validation : comparison with theoretical results

Since there is no exact method of solution for the type of network considered in this paper, most of the material on validation of our approximation will be based on simulation results; these will be presented in the next section. In this section we shall concentrate on comparing the few available results on departure processes from queues in order to determine the conditions under which our choice for the squared coefficient of variation of interarrival times, given in the previous section, is of sufficient accuracy.

As mentioned above, in the case of Poisson external arrivals and exponential service times at all stations our predictions for the $C_i$, $1 \le i \le n$, from (13) are exact. It has been shown in [11, 12] that for FCFS service interdeparture times are exponentially distributed only if interarrival times and service times are exponential.
5.1 - The output of an M/D/1 queue has been examined in considerable detail [13] so that all moments of the interdeparture time distribution are available. We may apply this information to the system of Figure 2 when arrivals to the first queue are Poisson and its service times are constant. For that case equation (13) predicts $C_1 = 1-\mu_1^2$ for the departures from the first queue ; the value obtained from Pack [13] is exactly the same. Thus the squared coefficient of variation or interarrival times to the second queue is $1-\mu_2^2$. The Reiser-Kobayashi [7] model predicts $\kappa^{(2)} = 1$ for the same quantity.

5.2 - The output process of an M/G/1 queue has been studied [14] by means of a Wiener-Hopf factorisation to obtain the Laplace-Stieltjes transform of the interdeparture time distribution. In [15] the variance of interdeparture times has been computed explicitly for the system M/G/1/N, i.e. with finite population N ; the results of interest to us are obtained by setting $N \to \infty$. In this case too we are see that our predictions are exact. The variance of interdeparture times from the first queue of the system in Figure 2 if service time is general and external arrivals are Poisson is computed from [15] as being $\left[ (1-\mu_1^2)/\lambda^2 + \kappa_1/\mu_1^2 \right]$ ; the value of $C_1/\lambda^2$ obtained from equation (13) is exactly this value.

6. Application to the analysis of a packet-switching network

In this section we shall apply the new diffusion approximation method introduced in section 4 to the analysis of the packet switching sub-network CIGALE of the computer network CYCLADES [16].

The CIGALE topology is shown on Figure 3 ; nodes A through G are minicomputers used for packet buffering and switching. The numbers on the arcs connecting the nodes refer to output queues ; thus 3 refers to the queue which contains packets being transfered from node B to node G, while 5 is the queue
of packets proceeding in the opposite direction. Traffic moving in the two opposite directions along an arc is non-interfering. Each node receives external traffic at a rate of $\lambda_i$ (i = A, B, ..., G) packets per second. We assume that a packet arriving from the outside of the network to any node i has equal probability of having any of the other six nodes as a final destination. A packet arriving at its final destination is instantaneously destroyed there. Packet routing is fixed and summarized in Table 1.

<table><caption>Table 1</caption><thead><tr><td>Source</td><td>Destination</td><td>Via Node</td></tr></thead><tbody><tr><td>A</td><td>F</td><td>C</td></tr><tr><td>B</td><td>F</td><td>C</td></tr><tr><td>C</td><td>G</td><td>F</td></tr><tr><td>D</td><td>G</td><td>F</td></tr><tr><td>G</td><td>C,D</td><td>B</td></tr><tr><td>F</td><td>A,B</td><td>C</td></tr></tbody></table>

The routes which are not indicated on Table 1 are chosen by shortest line transit time; this time is 0.4 seconds for a packet on all lines but 1, 2, 3, 5 which are faster (0.3 seconds for one packet). This assumes in fact that all packets are of the same length (1000 bits). The assumption concerning fixed packet length is not necessarily realistic but was chosen because more realistic information was unavailable; the same can be said about the assumption concerning the choice of destinations. The fixed routes are fairly realistic and so are the line transit times, and the order of magnitude of packet length.
All queues are assumed to be of infinite capacity; this is not the case in practice.

The network can be represented as the queueing network of Figure 4 which is a special case of the one of Figure 1. Service times at each queue are constant of value indicated on Figure 4. Routing probabilities have been computed from the routing data given in Table 1 and in the text. We have assumed, both in the simulations and the model that external arrivals of packets to each node are Poisson for lack of more realistic information; the arrival rates (identical to those used in [17]) are chosen from practical considerations. The model has been simulated in order to obtain the average length of each queue at equilibrium; the simulation results are compared with the diffusion approximation method introduced in Section 4, with the method of Reiser and Kobayashi [7] for the case where external arrivals to each node are Poisson (for want of real data on traffic). The accuracy with which our method predicts average queue lengths is varying. Somewhat less accurate results are obtained by the approach of Reiser and Kobayashi, while the assumption of exponentially distributed transit times and the application of Jackson's [1] formula is the least accurate approach.
<table><caption>Figure 1(b)</caption><thead><tr><th>Queue</th><th>Using diffusion<br>expected queue length<br>(G-P method)</th><th>Average queue length<br>by simulation</th></tr></thead><tbody><tr><td>1</td><td>0,515</td><td>0,530</td></tr><tr><td>2</td><td>1,040</td><td>0,945</td></tr><tr><td>3</td><td>1,388</td><td>1,317</td></tr><tr><td>4</td><td>0,346</td><td>0,340</td></tr><tr><td>5</td><td>1,495</td><td>1,397</td></tr><tr><td>6</td><td>1,862</td><td>1,903</td></tr><tr><td>7</td><td>0,547</td><td>0,560</td></tr><tr><td>8</td><td>1,155</td><td>1,273</td></tr><tr><td>9</td><td>6,234</td><td>6,568</td></tr><tr><td>10</td><td>1,913</td><td>2,008</td></tr><tr><td>11</td><td>0,491</td><td>0,497</td></tr><tr><td>12</td><td>0,287</td><td>0,331</td></tr><tr><td>13</td><td>0,647</td><td>0,658</td></tr><tr><td>14</td><td>0,312</td><td>0,342</td></tr><tr><td>15</td><td>0,491</td><td>0,506</td></tr><tr><td>16</td><td>1,913</td><td>1,923</td></tr></tbody></table>
## 7. Application to a model of an interactive system

The model shown on Figure 5 represents an interactive computer system examined by Anderson and Sargent [18]. It was used by Reiser and Kobayashi [7] as an example to illustrate their approach; we shall use their parameters in order to compare our approach to theirs. Jobs arrive to the system according to a Poisson process of parameter $\mu_0$. After passing through server 1 they leave the system with probability $1-\theta_1$ or enter the queue of server 2 with probability $\theta_1$. Server 1 and 2 can be used to represent a CPU and an I/O device, respectively.

Assuming $\mu_0 = 0.5$, $\theta_1 = \theta_2 = 0.5$ we obtain using the method introduced in Section 4 the average queue lengths tabulated on Table 2(a-d) which we compare with the simulation and diffusion approximation results in [7]. The results marked R-K correspond to the results of Reiser and Kobayashi, while G-P indicates our approach. On Table 2(a) and (b) we see that the R-K or G-P results can be more accurate, depending on the parameters and the queue considered. The error in the G-P results never exceeds 8%, however, while that in the R-K model predictions can be as high as 15%. The G-P approach is applied to the network in which all servers are exponential on Table 2(c) and (d); the error here never exceeds 5%.

Finally on Table 3 we apply our approach to the case where $\theta_2 = 0$ for constant service time at Server 2 and hyper-exponential service time at Server 1; $\mu_0, \mu_1$ are varied while $\mu_2$ is kept fixed at $\mu_2 = 1$. The squared coefficient of variation of service time at server 1 is kept at $K_1 = 2$, and our results are compared with the simulations carried out at IRIA by M. Badel. The accuracy of our results is such that the error in average queue length never exceeds 8%, and is mostly in the range of 2 to 3%.
We give a comparison with the interactive computer system that
may be modeled by the queueing system of Anderson and Sargent [18] represented
on figure 5.

Let be the input exponential, with rate $\mu_0 = 0.5$ and $\theta_1 = 0.5$ and $\theta_2 = 0.5$.
So

$$ \lambda_1 = \mu_0 e_1 = 1/(1-\theta_1) = 1 $$

$$ \lambda_2 = \mu_0 e_2 = \frac{\theta_1}{(1-\theta_1)(1-\theta_2)} = 1 $$

The following set of parameters was chosen :

**Case I** : Server 1 : 2 stage Erlang $K_1 = 0.5$
Server 2 : Constant Service $K_2 = 0$

**Case II** : Server 1 : Exponential $K_1 = 1$
Server 2 : Exponential $K_2 = 1$
And for the two cases we take 2 values for service time

$$A : \mu_1 = 0.9 \qquad \mu_2 = 0.84$$

$$B : \mu_1 = 0.95 \qquad \mu_2 = 0.89$$

We obtain the following tables of results for the average queue size.

$$\text{Case I-A: } \mu_1 = 0.9 \quad \mu_2 = 0.84 \quad \mu_3 = 0.5 \quad \mu_4 = 0.9 \quad \mu_5 = 0.1$$

<table><caption>Table 2(a)</caption><thead><tr><th></th><th>queue 1</th><th>queue 2</th></tr></thead><tbody><tr><td>simulation</td><td>6,84</td><td>3,22</td></tr><tr><td>diffusion<br>Reiser and<br>Kobayashi</td><td>6,76</td><td>2,70</td></tr><tr><td>error of R-K</td><td>1,5 %</td><td>15 %</td></tr><tr><td>diffusion G-P</td><td>6,65</td><td>2,95</td></tr><tr><td>error of G-P</td><td>2,5 %</td><td>8 %</td></tr></tbody></table>
$$ \mu_1 = 0.95 \quad K_1' = 0.5 \quad \mu_2 = 0.89 \quad K_2 = 0 $$

<table><caption>Table 2(b)</caption><thead><tr><th></th><th>queue 1</th><th>queue 2</th></tr></thead><tbody><tr><td>simulation</td><td>13,3</td><td>4,5</td></tr><tr><td>diffusion R-K</td><td>14,3</td><td>4,52</td></tr><tr><td>error R-K</td><td>7,5 %</td><td>1 %</td></tr><tr><td>diffusion G-P</td><td>12,62</td><td>4,39</td></tr><tr><td>error G-P</td><td>5 %</td><td>2,5 %</td></tr></tbody></table>

$$ \text{Case II-A : } \mu_1 = 0.9 \quad K_1 = 1 \quad \mu_2 = 0.84 \quad K_2 = 1 $$

<table><caption>Table 2(c)</caption><thead><tr><th></th><th>queue 1</th><th>queue 2</th></tr></thead><tbody><tr><td>using Jackson's results</td><td>9</td><td>5,25</td></tr><tr><td>diffusion G-P</td><td>9,46</td><td>5,3</td></tr><tr><td>error G-P</td><td>5 %</td><td>1 %</td></tr></tbody></table>
$$ \text{Case II-B : } \mu_1 = 0.95 \quad K_1 = 1 \quad \mu_2 = 0.89 \quad K_2 = 1 $$

<table><caption>Table 2(d)</caption><thead><tr><th></th><th>queue 1</th><th>queue 2</th></tr></thead><tbody><tr><td>Results Jackson</td><td>19</td><td>9</td></tr><tr><td>diffusion G-P</td><td>19,53</td><td>8,65</td></tr><tr><td>error G-P</td><td>2,5 %</td><td>3,5 %</td></tr></tbody></table>

We see that the error with the new method is always under 8 %.

We compare now always with the same system but with $\theta_2 = 0$. We take an hyperexponential service for server 1 and constant service for server 2. The simulations were done at IRIA by M. Badel; the results obtained are given in Table 3.

<table><caption>Table 3</caption><thead><tr><th rowspan="2">μ<sub>0</sub></th><th rowspan="2">μ<sub>1</sub></th><th colspan="2">simulation</th><th colspan="2">diffusion</th></tr><tr><th>queue 1</th><th>queue 2</th><th>queue 1</th><th>queue 2</th></tr></thead><tbody><tr><td>0.25</td><td>0.8</td><td>1.40</td><td>0.32</td><td>1.41</td><td>0.30</td></tr><tr><td>0.25</td><td>0.75</td><td>1.33</td><td>0.32</td><td>1.35</td><td>0.30</td></tr><tr><td>0.25</td><td>0.5</td><td>1.05</td><td>0.31</td><td>1.09</td><td>0.30</td></tr><tr><td>0.25</td><td>0.25</td><td>0.88</td><td>0.31</td><td>0.90</td><td>0.30</td></tr><tr><td>0.20</td><td>0.8</td><td>1.21</td><td>0.24</td><td>1.25</td><td>0.23</td></tr><tr><td>0.20</td><td>0.75</td><td>1.18</td><td>0.24</td><td>1.20</td><td>0.23</td></tr><tr><td>0.20</td><td>0.5</td><td>1.00</td><td>0.24</td><td>1.01</td><td>0.23</td></tr><tr><td>0.20</td><td>0.25</td><td>0.89</td><td>0.24</td><td>0.90</td><td>0.23</td></tr><tr><td>0.15</td><td>0.8</td><td>1.10</td><td>0.18</td><td>1.12</td><td>0.17</td></tr><tr><td>0.15</td><td>0.75</td><td>1.09</td><td>0.18</td><td>1.10</td><td>0.17</td></tr><tr><td>0.15</td><td>0.5</td><td>0.98</td><td>0.17</td><td>0.94</td><td>0.17</td></tr><tr><td>0.15</td><td>0.25</td><td>0.91</td><td>0.17</td><td>0.84</td><td>0.17</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 3</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 5</figcaption></figure>
1. J. R. Jackson, "Jobshop-Like Queueing Systems," Management Science 10, p. 131-142, (1963).

2. F. Baskett, K. M. Chandy, R. R. Muntz, F. G. Palacios, "Open, Closed and Mixed Networks of Queues with Different Classes of Customers," Journal ACM 22, p. 248-260, 2(1975).

3. G. F. Newell, *Applications of Queueing Theory*, Chapman and Hall, Ltd.
London, 1971, Chapter 6.

4. D. P. Gaver and G. S. Shedler, "Multiprogramming System Performance via Diffusion Approximations," IBM Research Report RJ-938, 1971,
Yorktown Heights, N.Y.

5. E. Gelenbe, "On Approximate Computer System Models," Journal ACM 22, p. 261-263, 2(1975).

6. H. Kobayashi, "Applications of the Diffusion Approximation to Queueing Networks: Parts I and II," IBM Research Reports RC 3943, 1972, and
RC 4054, 1972, Yorktown Heights, N.Y.

7. M. Reiser and H. Kobayashi, "Accuracy of the Diffusion Approximation for Some Queueing Systems," IBM J. Res. Devel. 18, p. 110-124, 2(1974).

8. M. Chandy, U. Herzog, L. Woo, "Parametric Analysis of Queueing Networks," IBM J. Res. Devel. 19, p. 36-42, 1(1975).

9. A. Chang, S. S. Lavenberg, "Work-Rates in Closed Queueing Networks with General Independent Sewers," Opns. Res. 22, p. 838-847, 4(1974).

10-a. E. Gelenbe and R. R. Muntz, "Probabilistic Models of Computer Systems-Part I (Exact Results)", to appear in Acta Informatica.

10-b. E. Gelenbe, "Probabilistic Models of Computer Systems, Part III (Diffusion Approximations, Waiting Times and Batch Arrivals)" to appear.
11. P.J. Burke, "The Output of a Queueing System", Opns. Res., 4, 699-704 (1956).

12. E. Reich, "Waiting Times when Queues are in Tandem", Annals Math. Stat., 28, 768-773, (1957)

13. C.D. Pack, "The Output of an M/D/1 Queue", Opns. Res., 23, 750-760, (1975)

14. K.T. Marshall, "Some Relationships between the Distributions of Waiting Time, Idle Time, and Inter-output Time in GI/G/1 Queue"; SIAM J. Appl. Math., 16, 324-327, (1968).

15. R.L. Disney and W.P. Cherry, "Some Topics in Queueing Network Theory", In Mathematical Methods in Queueing Theory A.B. Clarke (ed.), Springer-Verlag, Berlin, (1974).

16. L. Pouzin, "CIGALE, the Packet-Switching Machine of the Cyclades Computer Network", Proc. IFIP Congress 74, Stockholm, North-Holland, 155-159 (Aug. 1974).

17. M. Irland, "Simulation of Cigale, report on assumptions and results", CCNG Report E-32, University of Waterloo, (January 1975).

18. H.A. Anderson and R. Sargent, "The statistical Evaluation of the performance of an Experimental APL/360 system". Statistical Computer Performance Evaluation, W. Freiberger (ed), p. 73-98, Academic press, 1972.