# Throughput analysis of a two-computer system

Guy Pujolle, Adam Wolisz

► To cite this version:

Guy Pujolle, Adam Wolisz. Throughput analysis of a two-computer system. [Research Report] IRIA-RR-357, IRIA. 1979, pp.24. hal-04716606

HAL Id: hal-04716606

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

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

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.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_3.png" /></figure>

THROUGHPUT ANALYSIS
OF A TWO-COMPUTER SYSTEM

Guy PUJOLLE
Adam WOLISZ

Rapport de Recherche N° 357

Juin 1979
THROUGHPUT ANALYSIS OF A TWO-COMPUTER SYSTEM

Guy Pujolle*, Adam Wolisz**

Résumé :

L'utilisation de liaisons entre des mini-ordinateurs et un gros calculateur (qui peut exécuter des programmes plus volumineux) est de plus en plus attrayante. Tous les programmes sont pré-exécutés sur le mini et quelques uns d'entre eux sont exécutés sur la grosse machine. Celle-ci est utilisée par d'autres usagers et ne peut accepter qu'un nombre fini de programmes. Lorsqu'un travail ne peut être accepté sur le gros ordinateur par manqué de place, le mini commence son exécution qui peut être continuée sur le gros calculateur si une place se libère.

Pour évaluer les performances de ce système informatique un modèle de deux files d'attente en série est développée. Suivant les priorités d'accès au gros calculateur, les hypothèses de fonctionnement diffèrent. Plusieurs paramètres caractérisant le débit d'une telle installation sont calculés et comparés aux cas limites : soit il n'y a pas de gros calculateur, soit les travaux dirigés sur la grosse machine sont toujours acceptés. Nous donnons enfin des exemples numériques.

Abstract :

Users of small computers (minis) frequently find it useful to establish a link between their in
house mini and a large machine, which can more rapidly execute big programs occuring occasional-
ly. In this case all programs are pre-processed on the mini. Some of them are afterwards moved
for further processing on the large machine which is used by other customers as well. This large
machine accepts only a finite number of jobs in every time period.

If an attempt to place a job in the large machine fails because of its overloading, the mini will start the execution of this job.

Two stage tandem queueing networks are used to model such a system under different assump-
tions depending on the priority access to the large computer. Several parameters characterizing
the throughput of such an installation are calculated. They are compared with the parameters of
two limiting cases :

1) no access to the large machine is established,

2) every job sent to the large machine is always accepted.

Illustrative numerical examples are provided.

*Institut de Recherche d'Informatique et d'Automatique, LABORIA, Rocquencourt-78150 Le Chesnay (France)

**Polish Academy Of Sciences, Department of Complex Automation Systems, 44-100 Gliwice, Zwyciestwa 21
(Poland)
# 1. INTRODUCTION

Recently, because of the various implementations which mini-computers find in different areas, and due to decreasing prices of the digital equipment their utilization became fairly popular. Many users such as for example research centres, laboratories, design offices etc. have often to perform experiments and computations perfectly suitable for the "mini". But they can also have some complex computations which would be done much faster on a bigger machine than on a "mini".

In that case, if actual computational needs do not justify installing a large computer, it is frequently reasonable to connect the "mini" to a large computer used also by other customers. When more sophisticated jobs are to be executed, they are initially prepared on the mini and perhaps undergo there also some test and validation runs. Only afterwards are they sent for further execution on the larger computer.

However in the large computer, (serving also other customers), the situation may occur when despite its speed and memory facilities, the number of jobs presented for processing increases temporarily or in the long-run. This situation makes the use of the big machine less attractive, or even almost impossible. Therefore it is reasonable to assume that when the number of jobs presented to the large computer exceeds some predetermined value, all further jobs are refused. In this case the decision of the customer utilizing the mini would probably be to run the refused job at his "mini" at least until the bigger machine becomes available again.
In this paper some queueing models pertaining to such a situa-
tion will be developed. We shall not investigate however the fate of
individual job in the system, neglecting such parameters as waiting
time distribution, response time distribution etc. On the other hand,
we shall rather be interested in the throughput of such systems i.e. in
the number of jobs which can be successfully completed in a time period.
Therefore our analysis remains valid for a large class of scheduling
disciplines. For example it seems to be natural to assume that the
effective speed offered by the large computer to its users will depend
on the number of jobs actually present in the system, but no provision
was made for various modes of processing like batch, time-sharing etc.

2. MODEL DESCRIPTION

We shall be mainly concerned with the analysis of the system
presented in figure 1, referred hereafter as Model I. The system con-
sists of two servers A₁ and A₂, dealing with jobs arriving in two
input streams. Jobs from one of the streams, having intensity λ₀, form
a queue Q₁ and are served with rate µ₁ by server A₁. Completed jobs
leave the system with probability (1-a). With probability a, they
are presented for further service in system A₂, queueing up in a queue
Q₂.

<figure><img src="image_4.png" /><figcaption>The queueing model</figcaption></figure>

Figure 1
However this queue is joined also by jobs coming directly from a
second input stream representing other users of the system as a source
S, and having intensity λ. Jobs delivered by the source B or
coming from server A₁ are served with an equal intensity µ<sub>B</sub>(n) depend-
ing on the number of jobs present actually in system A₂ and queue Q₂.
The capacity of queue Q₂ is limited to N jobs. When queue Q₂ becomes
full, blocking phenomenon occurs, as far as the external source S is
concerned. This leads server A₁ to continue the treatment of the job
initiated. However because of its lower speed, the service intensity is
equal to µ<sub>A</sub> = (µ<sub>B</sub>(1))/v. This situation will be further referred to as block-
ing of server A₁.

We shall now discuss briefly the problem of service disciplines.
As far as the queue Q₁ and server A₁ are concerned, we assume only that
jobs are processed one by one, neglecting their sequencing.

We do not make any assumptions about service discipline applied
in queue Q₂. In any application of this model, the scheduling rules
imposed for the queue Q₂ should be reflected by the proper shape of
µ<sub>B</sub>(n). For example a following discipline can be imposed : let first L
jobs in the queue L < N be served in a multiprogramming mode, while
other (if any !) wait for a departure. In this case, a proper analysis
of multiprogramming system, having a specified configuration, would pro-
vide us with values µ<sub>B</sub>(n) for different levels of multiprogramming n.

We must also specify the rules of joining the queue $Q_2$.

If the number of jobs in $Q_2$ is less than N, then no assumptions are
necessary. However, if both the server $A_1$ and source S are blocked, a
priority rule for joining the queue $Q_2$ after its length decreases to
(N-1) jobs (after a departure) is needed.
We shall investigate two possibilities :

**Case a** - Jobs from source S have priority over jobs from $A_1$ in joining queue $Q_2$ after blocking.

**Case b** - Jobs from server $A_1$ have priority over jobs from source S in joining queue $Q_2$ after blocking.

For the purpose of further analysis the following assumptions are introduced :

**Ass. 1.** All service times are independent random variables exponentially distributed with proper, earlier introduced, parameters.

**Ass. 2.** Jobs generated by source S (if unblocked) form a Poisson stream.

**Ass. 3.** The Queue $Q_1$ is never empty, thus no assumptions on the input stream have to be made.

Assumptions 1 and 2 constrain the investigation to a purely Markovian model. Assumption 3 is motivated by our interest in throughput rather than in other operational parameters and allows directly to obtain the maximal throughput of the system, as proved by Lavenberg [Lave 75].

This model, corresponding with a two computer installation discussed in section 1, will be compared (from the point of view of its throughput) with two other possible models, being in some sense boundary situations for the model I.

Model II is given in figure 2, and corresponds to a situation where all jobs coming to system $A_1$ are entirely served, while system $A_2$ is devoted to the service of jobs from source S exclusively. It means that no link between the two computers was established. By the way, the service time of server $A_1$ is described by a stochastic variable having a probability density function $f_1(x) = \mu_I e^{-\mu_I x}$ with
probability 1-a or $f_2(x) = (\mu_I e^{-\mu I x}) * (\mu_A e^{-\mu A x})$ (where * denotes convolution) with probability a.

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

Model III is shown in figure 3. This case, corresponds to an infinite capacity of the queue $Q_2$ in model I. All jobs which are expected to use system $A_2$ for the second phase of their calculations, join queue $Q_2$.

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

In the following sections the models introduced above will be investigated in detail.

### 3. ANALYSIS OF MODEL I

Let us introduce system state as a triple $\langle n, k, \ell \rangle$ denoting the following situation.
- there are exactly n demands in the subsystem II consisting
  of the queue $Q_2$ and server $A_2$.

- the source S is blocked if $k=1$ and operating if $k=0$.

- the server $A_1$ is blocked if $\ell=1$ or operates. It is executing only the first initial part of every service if $\ell=0$.

We shall derive equations describing transitions between feasible states, separately for case a and b. Proper subscripts a and b will be added to indicate which case is being considered.

### Case a

The feasible states of the system are :

$$ \begin{gathered} <n,0,0>, \ <N+1,0,1>, \ <N+1,1,0>, \ <N+1,1,1> \\ n=0,1,...,N+1. \end{gathered} $$

We shall denote by $P_t(n,k,l)$ the probability that at time t the considered system is in state $<n,k,l>$. Thus the above enumerated states obey the following system of equations (1) to (7). It can be easily shown that these states form a continuous time Markov chain which is irreducible and homogeneous. As the number of state is finite the Markov chain is also ergodic.

Let $\delta$ be a small positive real variable; we have :

$$ (1) \quad \sum_{n=0}^{N+1} P_t(n,0,\theta) + P_t(N+1,0,0) + P_t(N+1,0,1) + P_t(N+1,1,1) = 1 $$

$$ (2) \quad P_{t+\delta}(0,0,0) = P_t(1,0,0)\mu_B(1)\delta + P_t(0,0,0)[1-\alpha\mu_I\delta-\lambda\delta] $$

$$ (3) \quad P_{t+\delta}(n,0,0) = P_t(n+1,0,0)\mu_B(n+1)\delta + P_t(n,0,0)[1-\alpha\mu_I\delta-\lambda\delta-\mu_B(n)\delta] + P_t(n-1,0,0)[\lambda\delta+\alpha\mu_I\delta] $$

for $n=1,2,...,N$.
$$ (4) \quad P_{t+\delta}(N+1,0,0) = P_t(N+1,0,0)[1-\mu_I\delta-\lambda\delta-\mu_B(N+1)\delta] + \\ \qquad + P_t(N,0,0)[\lambda\delta+\mu_I\delta] + P_t(N+1,1,0)\mu_B(N+1)\delta + \\ \qquad + P_t(N+1,0,1)[\mu_B(N+1)\delta + \mu_A\delta]. $$

$$ (5) \quad P_{t+\delta}(N+1,1,1) = P_t(N+1,1,0)\mu_I\delta + P_t(N+1,0,1)\lambda\delta + \\ \qquad + P_t(N+1,1,1)[1-\mu_A\delta-\mu_B(N+1)] $$

$$ (6) \quad P_{t+\delta}(N+1,1,0) = P_t(N+1,0,0)\lambda\delta + P_t(N+1,1,0)[1-\mu_I\delta-\mu_B(N+1)\delta] + \\ \qquad + P_t(N+1,1,1)\mu_A\delta. $$

$$ (7) \quad P_{t+\delta}(N+1,0,1) = P_t(N+1,0,0)\mu_I\delta + P_t(N+1,0,1)[1-\lambda\delta-\mu_A\delta-\mu_B(N+1)\delta] + \\ \qquad + P_t(N+1,1,1)\mu_B\delta. $$

Tending with $\delta \to \infty$, neglecting the small values of second order we obtain after simple algebra the difference differential equations for $P_t(n,k,l)$. Setting the derivatives equal to zero we obtain the following steady state equations.

$$ (8) \quad \sum_{n=0}^{N+1} p(n,0,0) + p(N+1,1,0) + p(N+1,0,1) + p(N+1,1,1) = 1 $$

$$ (9) \quad [\mu_I+\lambda]p(0,0,0) = \mu_B(1)p(1,0,0) $$

$$ (10) \quad [\mu_I+\lambda+\mu_B(n)]\mu(n,0,0) = \mu_B(n+1)p(n+1,0,0) + (\lambda+\mu_I)p(n-1,0,0) \\ n=1,2,...,N. $$

$$ (11) \quad [\mu_I+\lambda+\mu_B(N+1)]p(N+1,0,0) = \mu_B(N+1)[p(N+1,1,0) + p(N+1,0,1)] + \\ \qquad + \mu_A p(N+1,0,1) + p(N,0,0)[\lambda+\mu_I\delta] $$

$$ (12) \quad [\mu_A+\mu_B(N+1)]p(N+1,1,1) = \mu_I p(N+1,1,0) + \lambda p(N+1,0,1) $$
$$
(13) \quad [a_{\mu_I} + a_{\mu_B}^{(N+1)}] p(N+1,1,0) = a_{\mu_A} p(N+1,1,1) + \lambda p(N+1,0,0)
$$

$$
(14) \quad [\lambda + \mu_A + \mu_B (N+1)] p(N+1,0,1) = \mu_B (N+1) p(N+1,1,1) + a \mu_I p(N+1,0,0)
$$

where $p(n,k,l) = \lim_{t \to \infty} p_t(n,k,l)$.

Let us denote by

$$
(15) \quad \rho_i \equiv \frac{a \mu_I + \lambda}{\mu_B (i)}
$$

It is easy to show, from (9) and (10) using an inductive reasoning that

$$
(16) \quad p(i;0,0) = p(i-1,0,0)\rho_i
$$

for i=1,2,...,N+1,

thus we obtain

$$
(17) \quad p(i,0,0) = \sigma_i p(0,0,0)
$$

$$
\text{where } \sigma_i = \sum_{j=1}^{i} \rho_i.
$$

Utilizing (16) in equations (11) to (14) we obtain

$$
(18) \quad p_{N+1} \sigma_{N+1} p(0,0,0) = p(N+1,1,0) + p(N+1,0,1) + \frac{\mu_A}{\mu_B (N+1)} p(N+1,0,1)
$$

$$
(19) \quad [\mu_A + \mu_B (N+1)] p(N+1, 1, 1) = a \mu_I p(N+1, 1, 0) + \lambda p(N+1, 0, 1)
$$

$$
(20) \quad [a \mu_I + \mu_B (N+1)] p(N+1, 1, 0) = \mu_A p(N+1, 1, 1) + \lambda \sigma_{N+1} p(0, 0, 0)
$$

$$
(21) \quad [1 + \rho_{N+1}] p(N+1, 0, 1) = p(N+1, 1, 1) + \frac{a \mu_I}{\mu_B (N+1)} \sigma_{N+1} p(0, 0, 0)
$$

Expressing $p(N+1,1,0)$ and $p(N+1,1,1)$ as a function of $p(N+1,0,1)$
and $p(0,0,0)$ from equations (18) and (21), we obtain after substitutions
into (20)
$$
\begin{align*}
(22) \quad [a\mu_I + b\mu_B(N+1)]\{\rho_{N+1}\sigma_{N+1}p(0,0,0) - [1 + \frac{\mu_A}{\mu_B(N+1)}]p(N+1,0,1)\} &= \\
&= \mu_A\{[1+\rho_{N+1}]p(N+1, 0,1) - \frac{a\mu_I}{\mu_B(N+1)}\sigma_{N+1}p(0,0,0)\} + \lambda\sigma_{N+1}p(0,0,0)
\end{align*}
$$

After simple reordering we obtain

$$
(23) \quad p(N+1,0,1) = \alpha^a \sigma_{N+1} p(0,0,0)
$$

where

$$
\alpha^a = \frac{\{\rho_{N+1}[a\mu_I + b\mu_B(N+1)] + \frac{\mu_A}{\mu_B(N+1)}a\mu_I - \lambda\}}{\mu_A[1+\rho_{N+1}]+[a\mu_I+b\mu_B(N+1)][1+\frac{\mu_A}{\mu_B(N+1)}]}
$$

Using (18) and (23) we obtain

$$
(24) \quad p(N+1,1,0) = \beta^a \sigma_{N+1} p(0,0,0)
$$

where

$$
\beta^a = \rho_{N+1} - \left[1 + \frac{\mu_A}{\mu_B(N+1)}\right] \alpha^a
$$

Similarly using (20) we obtain

$$
(25) \quad p(N+1,1,1) = \gamma^a \sigma_{N+1} p(0,0,0)
$$

where

$$
\gamma^a = [1 + \rho_{N+1}] \alpha^a - \frac{a \mu_I}{\mu_B (N+1)}
$$

Using equation (8) with substitution of right sides of equations (16), (23),
(24), (25) instead of p(n,k,l) we obtain

$$
p(0,0,0) \left[ 1 + \sum_{j=1}^{N+1} \sigma_j + \sigma_{N+1} (\alpha^a + \beta^a + \gamma^a) \right] = 1
$$

thus,

$$
(26) \quad p(0,0,0) = \frac{1}{1 + \sum_{j=1}^{N+1} \sigma_j + \sigma_{N+1}(\alpha^a + \beta^a + \gamma^a)}
$$

which completes the analysis of case a.
Case b

We can present a similar reasoning for case b. In fact, equations (1) to (5) are still valid also in this case, and the only difference occurs in equations (6) and (7) which have to be changed to (27) and (28) given below :

$$
(27) \quad \begin{aligned}
p_{t+\delta}(N+1,1,0) ={}& p_t(N+1,0,0)\lambda\delta + p_t(N+1,1,0)[1-\alpha\mu_I\delta - \mu_B(N+1)\delta] + \\
& \qquad + p_t(N+1,1,1)\mu_A\delta + p_t(N+1,1,1)\mu_B(N+1)\delta
\end{aligned}
$$

$$
(28) \quad p_{t+\delta}(N+1,0,1) = p_t(N+1,0,0)\alpha\mu_I\delta + p_t(N+1,0,1)[1-\lambda\delta - \mu_A\delta - \mu_B(N+1)\delta]
$$

Thus for the steady state we obtain, respectively,

$$
(29) \quad [\alpha\mu_I + \mu_B(N+1)]p(N+1,1,0) = \mu_B(N+1)p(N+1,1,1) + \mu_A p(N+1,1,1) + \lambda p(N+1,0,0)
$$

$$
(30) \quad [\lambda + \mu_A + \mu_B(N+1)]p(N+1,0,1) = \alpha \mu_I p(N+1,0,0).
$$
The system of equations (8) to (12), (29), (30) gives a complete description of case b for the model 1.

Also for this case equations (16) and (17) hold as a direct result from (9) and (10). Substituting (16) into (11), (29) and (30), we obtain the following system of equations (31), (32), (33).

$$ (31) \quad \rho_{N+1}\sigma_{N+1}p(0,0,0) = p(N+1,1,0) + p(N+1,0,1)[1 + \frac{\mu_A}{\mu_B(N+1)}] $$

$$ (32) \quad [a\mu_I + \mu_B(N+1)]p(N+1,1,0) = [\mu_B(N+1) + \mu_A]p(N+1,1,1) + \lambda\sigma_{N+1}p(0,0,0) $$

$$ (33) \quad [\lambda + \mu_A + \mu_B(N+1)]p(N+1,0,1) = a\mu_I\sigma_{N+1}p(0,0,0) $$

Equation (33) yields directly

$$ (34) \quad p(N+1,0,1) = \alpha^b \sigma_{N+1} p(0,0,0) $$

where

$$ \alpha^b = \frac{a\mu_I}{\lambda + \mu_A + \mu_B(N+1)} $$

Using (34) and (31) we obtain

$$ (35) \quad p(N+1,1,0) = \beta^b \sigma_{N+1} p(0,0,0) $$

where

$$ \beta^b = \{ \rho_{N+1} - \alpha^b [1 + \frac{\mu_A}{\mu_B(N+1)}] \} $$

Finally (35) and (32) yield

$$ (36) \quad p(N+1,1,1) = \gamma^b \sigma_{N+1} p(0,0,0) $$

where

$$ \gamma^b = \frac{[a\mu_I + \mu_B(N+1)]\beta^b - \lambda}{\mu_A + \mu_B(N+1)} $$
Using equation (8) with substitution of right sides of equations (16), (34), (35), (36) instead of p(n,k,l) we obtain

$$p(0,0,0)[1 + \sum_{j=1}^{N+1} \sigma_j + \sigma_{N+1}(\alpha^b + \beta^b + \gamma^b)] = 1$$

thus

$$(37) \quad p(0,0,0) = [1 + \sum_{j=1}^{N+1} \sigma_j + \sigma_{N+1}(\alpha^b + \beta^b + \gamma^b)]^{-1}$$

which completes the analysis of case b.

Results obtained for both cases of model 1 are presented jointly in table 1 below.

$$ \begin{align*} p(0,0,0) &= \left[1 + \sum_{j=1}^{N+1} \sigma_j + \sigma_{N+1}(\alpha+\beta+\gamma)\right]^{-1} \\ p(i,0,0) &= \sigma_i p(0,0,0) \quad \text{ i=1,2,...,N+1} \\ p(N+1,0,1) &= \alpha p(0,0,0) \sigma_{N+1} \\ p(N+1,1,0) &= \beta p(0,0,0) \sigma_{N+1} \\ p(N+1,1,1) &= \gamma p(0,0,0) \sigma_{N+1} \\ \sigma_i &= \prod_{j=1}^{i} \rho_j \quad \rho_j = \frac{a \mu_i + \lambda}{\mu_B(j)} \end{align*} $$

$$ \begin{align*} \underset{\text{Case a}}{\alpha^a} &= \frac{\rho_{N+1}[a\mu_I + \mu_B(N+1)] + \frac{\mu_A a \mu_I}{\mu_B(N+1)} - \lambda}{\mu_A[1+\rho_{N+1}]+[a\mu_I+\mu_B(N+1)][1+\frac{\mu_A}{\mu_B(N+1)}]} \\ \beta^a &= \rho_{N+1} - \left[1 + \frac{\mu_A}{\mu_B(N+1)}\right]^a \\ \gamma^a &= \left[1 + \rho_{N+1}\right]^a \frac{a \mu_I}{\mu_B(N+1)} \end{align*} $$

$$ \begin{align*} \underset{\text{Case b}}{\alpha^b} &= \frac{a \mu_I}{\lambda + \mu_A + \mu_B(N+1)} \\ \beta^b &= \rho_{N+1} - \alpha^b \left[1 + \frac{\mu_A}{\mu_B(N+1)}\right] \\ \gamma^b &= \frac{[a\mu_I + \mu_B(N+1)]\beta^b - \lambda}{\mu_A + \mu_B(N+1)} \end{align*} $$

<caption>Table 1 - Results for model 1</caption>
4. PERFORMANCE PARAMETERS

We shall now define and calculate some performance parameters
for model 1.

V = Output rate from the server A₂, defined as mean number of jobs leaving server A₂ in a time unit (throughput of A₂)

$$
(38) \quad V = \frac{1}{E(X)}
$$

where E(X) stands for the mean interdeparture time from server A₂.

The distribution φ(x) of the interdeparture X from A₂ can
however be easily found based on classical arguments used for the
M/G/1 queue as presented, for example, by Cohen [COHE 69]

$$
(39) \quad \varphi(x) = [1 - p(0,0,0)] \mu_B e^{-\mu_B x} + p(0,0,0) [\mu_B e^{-\mu_B x} * \mu e^{-\mu x}]
$$

where $\mu = \lambda + a\mu_I$.

Thus using the Laplace transform we obtain :

$$
(40) \quad \bar{\varphi}_X(s) = [1 - p(0,0,0)] \frac{\mu_B}{s+\mu_B} + p(0,0,0) \frac{\mu_B}{s+\mu_B} \frac{s}{s+\mu}
$$

where

$$
\varphi_X(s) = \int_0^\infty e^{-st} \varphi(t) \, dt .
$$

Clearly

$$
(41) \quad E(X) = \mu_B + p(0,0,0) \frac{1}{\lambda + a\mu_I}
$$
so finally

$$ (42) \quad V = \left[ \mu_B + \frac{p(0,0,0)}{\lambda + a\mu_I} \right]^{-1} $$

K = Mean number of jobs served by the server $A_1$ in a time unit.

Following assumption 3 (section 2), stating that the queue in front of $A_1$ is never empty, K stands for the maximal throughput of server $A_1$.

We have :

$$ K = [1 - P(N+1,0,1) - P(N+1,1,1)] \mu_I, $$

as $[1 - P(N+1,0,1) - P(N+1,1,1)]$ represents the fraction of time which server A1 spends executing the initial part of jobs, which has anyway to be executed for every job.

L = Mean number of jobs which need the second phase of computation to be performed, and have both of these phases fully completed on served $A_1$.

$$ (44) \quad L = \mu_A[p(N+1,0,1) + p(N+1,1,1)] $$

Formula (44) is derived as follows : (for case a). Let us rewrite equation (44) :

$$ L = \mu_A p(N+1,0,1) + \mu_A p(N+1,1,1) = L_1 + L_2 $$

From equation (29) it is obvious, that state $<N+1,0,1>$ can be left if one of the following events occurs

- another job arrives from source S, causing a transition $<N+1,0,1> \rightarrow <N+1,1,1>$, with intensity $\lambda$

- service on $A_2$ is completed, causing a transition $<N+1,0,1> \rightarrow <N+1,0,0>$ with intensity $\mu_B(N+1)$
- service on $A_1$ is completed (end of blocking) causing a transition $\langle N+1,0,1 \rangle \rightarrow \langle N+1,0,0 \rangle$ with intensity $\mu_A$.

Exactly this transition corresponds to the investigated situation, when also the second phase of computations is completed on server A1.

But from the Chapman - Kolmogorov equations it is clear that the rate of this transition is equal to

$$L_1 = \mu_1 p(N+1,0,1)$$

Identical reasoning can be followed for the state $\langle N+1,1,1 \rangle$ leading to

$$L_2 = \mu_A p(N+1,1,1)$$

Similarly, after enumeration of the possible transitions for the case b of model 1 the correctness of (44) can be justified also for this case.

R = the mean number of jobs coming from server $A_1$ which are completed on $A_2$ during a time unit

$$(45) \quad R = aK-L.$$

## 5. MODELS II AND III

The analysis of systems II and III can be done easily using the classical results of queueing theory. Therefore we shall only resume here briefly formulas for performance parameters describing the throughput of those systems for various types of demands, similarly as it was done for the model I in section 4. We shall however assume in this section $\mu_B(n)=\mu_B$.

For model II we can apply directly results obtained for the M/G/1 queue, with service time distribution b(x) being given by :
$$ (46) \quad b(x) = \mu_I e^{-\mu_I x} * a \mu_B e^{-\mu_B x} $$

Thus the maximal throughput $K_{II}$ of the server $A_1$ is equal to

$$ (47) \quad K_{II} = [\mu_I + \mu_A]a, $$

while the maximal throughput $V_{II}$ of the server $A_2$ is naturally

$$ (48) \quad V_{II} = \mu_B. $$

For the model III the mean number of jobs served by the server $A_1$ can be defined in the following way, taking into account the conditions for stationary state :

$$ (49) \quad K_{III}^* = \mu_I \quad \text{if} \quad a\mu_I + \lambda < \mu_B, \quad V_{III} = a\mu_I + \lambda. $$

However if $a\mu_I + \lambda \ge \mu_B$ then priority rules between jobs coming from server $A_1$ and jobs coming from source S have to be included.

### Case III<sub>A</sub>

Output from source S has nonpreemptive priority in access to $A_2$.

In this case

$$ (50) \quad K_{III_A}^* = \inf(\mu_I, [\frac{\mu_B - \lambda}{a}]_+) $$

where

$$ [\alpha]_+ = \begin{cases} \alpha & \text{if } \alpha \ge 0 \\ 0 & \text{if } \alpha < 0 \end{cases} $$

### Case III<sub>B</sub>

Output from server $A_1$ has nonpreemptive priority in access to $A_2$.

In this case :

$$ (51) \quad K_{III_B}^* = \inf(\mu_I, \mu_B/a). $$
For the server $A_2$ the maximal throughput is equal again to

$V_{III}^* = \mu_B$, for both cases $III_A$ and $III_B$.

## 6. NUMERICAL EXAMPLES AND CONCLUSION

In Figures 4 to 7 numerical results obtained by our analytical method are presented, concerning the models shown in Figures 1 to 3. In the sequel, we have considered the following characteristics of the model : $\mu_I = 1$, $\mu_A = 0.1$, $\mu_B = 1$. The quantity plotted in Figures 4 to 7 is the maximal throughput allowed by the system to the customers entering the system by the queue $Q_1$, when the probability a equals 0.2 and 0.8 (a is the probability that jobs are presented for further service in system $A_2$).

Results shown in Figures 4 and 5 depend on the intermediate waiting room size. Results shown in Figures 6 and 7 depend on the arrival rate from the source S.

We can see that the greatest maximal throughput is obtained when the intermediate waiting room size tends to the infinity. However, it is important to note that the infinity point presents a discontinuity. Indeed as long as the second queue is finite, the system is stable, but when the second queue is infinite the system can be unstable.

It is also important to notice in the two first Figures (4 and 5) that the greatest maximal throughput is approached rapidly with only a small number of buffers.

Figures 6 and 7 show the instability of model III. They show that when the probability a is small the maximal throughput is not very sensitive to the value of the arrival rate from the source S for a sufficient number of intermediate buffers (N greater than 4).
We can conclude from the previous numerical results that a small number of buffers is sufficient to obtain almost the greatest maximal throughput.

Now if we look at the total response time of a customer asking for further service in system A₂, we have:

$$ \bar{t} = \{\mu_I + (1-\alpha)\mu_B[\text{Prob}(N+1,0,1) + \text{Prob}(N+1,1,1)]\}^{-1} + \bar{t}_2 $$

$$ \text{where } \bar{t}_2 = \frac{1}{\lambda} \left\{ \begin{aligned} & \sum_i P(i,0,0) + (N+1)[\text{Prob}(N+1,1,1) + \text{Prob}(N+1,0,1)] \\ & + \text{Prob}(N+1,1,0)] \end{aligned} \right\} $$

$$ \text{where } \lambda' = \lambda + (1-\alpha)\mu_I \left(1 - \frac{L}{K - a\mu_I}\right) $$

We show in Figure 8 the total response time versus the intermediate waiting room size when a equals 0.2.

As would be expected, the response time increases with the number of buffers and it is clear that the greater the arrival rate from S, the greater the increase of the response time.

As a conclusion, it turns out that a small amount of waiting room before the server A₂ is sufficient to obtain a near optimal throughput and a reasonable response time.

## REFERENCES

[COHE 69] J.W. Cohen, "The Single Server Queue" North Holland, Amsterdam, 1969.

[LAVE 77] S.S. Lavenberg, "Stability and maximum departure rates of certain open queueing networks having finite capacity constraints". IBM Research Report, RJ 1625, San Jose, California.
<figure><img src="image_7.png" /></figure>

Maximal throughput for the customers coming from $Q_1$ versus the intermediate waiting room size when $\mu_I=1$, $\mu_A=0.1$, $\mu_B=1$, $a=0.2$.

<caption>Figure 4</caption>
<figure><img src="image_8.png" /></figure>

Maximal throughput for the customers coming from $Q_1$ versus the intermediate waiting room size when $\mu_I=1$, $\mu_A=0.1$, $\mu_B=1$, $a=0.8$.

<caption>Figure 5</caption>
<figure><img src="image_9.png" /></figure>

Maximal throughput for the customers coming from $Q_1$ versus the arrival rate from the source S when $\mu_I=1$, $\mu_A=0.1$, $\mu_B=1$, $a=0.2$. Both model I and model III are investigated in the case a.

<caption>Figure 6</caption>
<figure><img src="image_10.png" /><figcaption>Maximal
throughput</figcaption></figure>

Maximal throughput for the customers coming from $Q_1$ versus the arrival rate from the source S, when $\mu_I=1.0$, $\mu_A=0.1$, $\mu_B=1.0$, $a=0.8$.
Both model I and model III are investigated in the case a.

<caption>Figure 7</caption>