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

HAL
open science

# On approximate computer system models

Erol Gelenbe

► To cite this version:

Erol Gelenbe. On approximate computer system models. [Research Report] IRIA-RR-068, IRIA. 1974, pp.19. hal-04715962

HAL Id: hal-04715962

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

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
RIA
laboria

laboratoire de recherche
en informatique
et automatique

On approximate
computer system models

E. Gelenbe

19p

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 68

avril 1974
# ON APPROXIMATE COMPUTER SYSTEM MODELS*

E. GELENBE

## ABSTRACT

We investigate the appropriate choice of boundary conditions for diffusion approximations to multiple resource computer system models. The instantaneous return process is investigated and analytical results for approximations to the M/G/1 system and to a non-Markovian two-server system are given. Numerical results which are presented suggest that the approach yields a good degree of accuracy. The method suggested has the advantage of not requiring the introduction of results from queueing theory to obtain the boundary conditions. Certain classical queueing theory results are deduced from our approximate model.

## RÉSUMÉ

Nous présentons un modèle approché qui permet d'obtenir la solution stationnaire de certains systèmes d'attente non-Markoviens. Le modèle est appliqué à un système informatique comportant une unité centrale et une mémoire secondaire.

<footnote>* A paraître dans Journal of the ACM.</footnote>
# I - INTRODUCTION

Recently considerable interest has been shown for obtaining approximate solutions to queueing models using diffusion processes [1][2]. The interest of these approximations lies essentially in the fact that analytical though approximate, results are obtainable for relatively complex situations where the only possible alternative lies in numerical methods or simulation experiments. It is not surprising that this approach has been applied to the mathematical modelling of multiple resource computer systems [3], [4], [5] for which analytical results are otherwise difficult to obtain.

The basic argument used in these approximations (see for instance [3], p. 570) is that the number of users $N(t)$ in queue at time $t$ will tend to become normally distributed for large $t$, with mean $b(t) \cdot t$ and variance $\alpha(t) \cdot t$ if "boundary conditions" (such as the case where the queue is empty) are neglected; thus one argues that the process $N(t)$ can be approximated by a diffusion process. Reflecting boundaries (for instance at the origin, for a single server queue) are imposed in order to keep the process in the desired region (for instance on the positive real line) but also to insure that no probability mass collects at the boundaries. These models are then only useful in heavy traffic conditions (for a single-server queue when the traffic intensity is close to or greater than one).

In this paper we improve on the existing diffusion approximation techniques by suggesting the use of the instantaneous return process [6], [7], [8] as the basic model, and by showing that its use to model an M/G/1 queue yields the probability of an empty queue exactly and the formula of
POLLATZEK and KHINTCHINE approximately. We then apply the model to the approximation of a closed two-server system and compare the results obtained with those of GAVER and SHEDLER [3] and of SHEDLER [11]. Our approach seems to yield quite accurate results in this case too, and familiar queueing theory results are obtained naturally from the model.
## II - THE INSTANTANEOUS RETURN PROCESS.

Let us briefly and informally recall the basic equations for the instantaneous return process for which an informal presentation can be found in [8] and a rigorous treatment in [6], [7].

Consider the stochastic process $\{X(t), t \ge 0\}$ on the closed interval $[0, M]$ of the positive real line. On the open interval $]0, M[$ the process behaves as a diffusion (Wiener) process. However when the process reaches on of the boundaries (0 or M) it remains there for an exponentially distributed time, after which it jumps instantaneously back into $]0, M[$, distributing itself with some probability density function over the interval, re-initiating the diffusion process. Since the holding times on the boundaries are exponentially distributed, the elementary return process $\{X(t), t \ge 0\}$ retains the Markov property. Though it is easy to imagine a semi-Markov version of this process with arbitrarily distributed holding times at the boundaries we do not know of mathematical results covering this case.

Let $m_1(t), m_2(t)$ be the probability masses concentrated at the lower and upper boundary and $1/\lambda_1, 1/\lambda_2$ the expected holding times at 0 and M, respectively.

The probability density function of the point from which the diffusion process starts once again immediately after a jump is $f_1(x)$ if
the jump originated at 0 and $f_2(x)$ if it originated at M. Denote also
by $A_{x,t}$ the forward operator

$$
(1) \quad A_{x,t} f = - \frac{\partial}{\partial t} f(x,t) - \frac{\partial}{\partial x} [b(x,t)f(x,t)] + \frac{1}{2} \frac{\partial^2}{\partial x^2} [\alpha(x,t)f(x,t)] \\
\text{and by } B_{x,t} \text{ the operator}
$$

$$
(2) \quad B_{x,t} f = - b(x,t)f(x,t) + \frac{1}{2} \frac{\partial}{\partial x} [\alpha(x,t)f(x,t)]
$$

where $f=f(x,t)$ is the probability density function of the process at time $t$

$$
(3) \quad b(x,t) = \lim_{\Delta t \to 0} \frac{E\{X(t+\Delta t) - X(t) | X(t)=x\}}{\Delta t}
$$

and

$$
(4) \quad \alpha(x,t) = \lim_{\Delta t \to 0} \left[ \frac{E\{[X(t+\Delta t) - X(t)]^2 | X(t)=x\}}{\Delta t} - \frac{E\{X(t+\Delta t) - X(t) | X(t)=x\}}{\Delta t} \right]^2
$$

The equations for the instantaneous return process are then [6], [7], [8]:

$$
(5) \quad A_{x,t} f + \lambda_1 m_1(t) f_1(x) + \lambda_2 m_2(t) f_2(x) = 0
$$

$$
(6) \quad \frac{d}{dt} m_1(t) = B_{0,t} f - \lambda_1 m_1(t)
$$

$$
(7) \quad \frac{d}{dt} m_2(t) = - B_{M,t} f - \lambda_2 m_2(t)
$$

These equations have a simple interpretation. The term :

$$
B_{0,t} f = \lim_{x \to 0} \left[ -b(x,t)f(x,t) + \frac{1}{2} \frac{\partial}{\partial x} \left( \alpha(x,t)f(x,t) \right) \right]
$$

represents the rate of flow of the probability mass from the region ]0,M[
to the lower boundary, while $-B_{M,t}f$ is the flow to the upper boundary.
$\lambda_1 m_1(t)$ is the rate of flow of mass from the lower boundary into ]0,M[
and $\lambda_2 m_2(t)$ is the corresponding quantity from the upper boundary. The
conservation of mass should be satisfied ; that is we must have
$$
(8) \quad \frac{\partial}{\partial t} \left[ \int_0^1 f(x,t) dx + m_1(t) + m_2(t) \right] = 0
$$

From (5) and (1) and since $\displaystyle\int_0^\infty f_1(x)dx = 1$, $\displaystyle\int_0^\infty f_2(x)dx = 1$,

$$
(9) \quad \frac{\partial}{\partial t} \int_0^1 f(x,t) dx = \left[ -b(x,t)f(x,t) + \frac{1}{2} \frac{\partial}{\partial x} [\alpha(x,t)f(x,t)] \right]_0^M + \lambda_1 m_1(t) + \lambda_2 m_2(t) \\
= B_M t f - B_0 t f + \lambda_1 m_1(t) + \lambda_2 m_2(t)
$$

Using (6), (7) and (9) we then have

$$
\begin{align*}
\frac{\partial}{\partial t} \int_0^1 f(x,t) dx + \frac{dm_1(t)}{dt} + \frac{dm_2(t)}{dt} &= B_M t f - B_0 t f + \lambda_1 m_1(t) + \lambda_2 m_2(t) + \\
&\quad + B_0 t f - \lambda_1 m_1(t) - B_M t f - \lambda_2 m_2(t) = 0
\end{align*}
$$

which verifies (8). Thus we can now set

$$
(10) \quad \int_0^1 f(x,t) \, dx + m_1(t) + m_2(t) = 1
$$

Equation (5) can also be interpreted in terms of the flow of probability
masses. Let $\Omega$ be a subinterval of $]0, M[$. Then from (5) we have

$$
\int_{\Omega} A_{x,t} f + \lambda_1 m_1(t) \int_{\Omega} f_1(x) + \lambda_2 m_2(t) \int_{\Omega} f_2(x) = 0
$$

or from (1),

$$
(11) \quad \frac{\partial}{\partial t} \int_{\Omega} f(x,t) = \int_{\Omega} \left[ - \frac{\partial}{\partial x} (b(x,t) f(x,t)) + \frac{1}{2} \frac{\partial^2}{\partial x^2} (\alpha(x,t) f(x,t)) \right] + \\
\qquad + \lambda_1 m_1(t) \int_{\Omega} f_1(x) + \lambda_2 m_2(t) \int_{\Omega} m_2(t)
$$

which states that the rate of change of the probability mass in Ω is equal
to the flow of mass from the boundaries O and M (the last two terms on
the right-hand side of (11)) plus the flow out of the region Ω.
Although a more general case may be considered, we shall assume that the boundaries act as absorbing boundaries for the diffusion process until the jump occurs. Thus we take for all $t \ge 0$

$$ (12) \qquad \lim_{x \to 0} f(x,t) = \lim_{x \to M} f(x,t) = 0 $$

as with absorbing boundaries. Of course, initial conditions for $m_1(t)$, $m_2(t)$ and $f(x,t)$ will also have to be given.

Let us note that $\lambda_1, \lambda_2$ may be functions of time, and that $f_1(x)$, $f_2(x)$ could be taken to be functions of the instant of time at which the jump occurs.

### III - APPROXIMATION TO THE M/G/1 QUEUE.

We shall apply the instantaneous return model to the M/G/1 queue system. The process $\{X(t), t \ge 0\}$, taken on the interval $[0, \infty]$ (the non-negative real line), approximates the number of requests in queue including the one in service.

Since we will seek the stationary solution, if it exists, we will not be concerned with the probability mass accumulated at $+\infty$, nor with jumps originating at that point. The origin will represent the empty queue and, after an exponentially distributed holding time at 0, a jump will take place to the point +1 representing one arrival. The equations (5), (6), (7), become at stationary state defined by $\frac{\partial f}{\partial t}=0$, $\frac{df}{dt}=0$

$$ (13) \qquad -b \frac{\partial f}{\partial x} + \frac{1}{2} \alpha \frac{\partial^2 f}{\partial x^2} = -\lambda m \delta(x-1) $$

$$ (14) \qquad \lim_{x \to 0} \left[ -bf + \frac{1}{2} \alpha \frac{\partial f}{\partial x} \right] = \lambda m $$

where $\delta(x-1)$ is a Dirac density function concentrated at $x=1$, $m$ is the stationary probability mass at $x=0$, and $\alpha, b$ are independent of $x, t$
and obtained (see [1] or [3]) using asymptotic renewal theory

$$b = \lambda - \mu$$

$$\alpha = \lambda^3 v_a + \mu^3 v_s$$

where $\lambda, \mu$ are the mean arrival and service rate, respectively. $v_a, v_s$ are the variance of the interarrival and service time, respectively. Since the arrival process is Poisson, we have

$$\alpha = \lambda + \mu^2 v_s$$

Let us note

$$\gamma = \frac{2b}{\alpha} = - \frac{2(1-\rho)}{\rho + K_s}$$

where $\rho = \lambda/\mu$ and $K_s = \mu^2 v_s$. The solution to (13) with boundary conditions

(14), and $\lim_{x \to 0} f(x) = 0$ from (12), is

$$f = \begin{cases} \frac{m\lambda}{b} [e^{\gamma x} - 1], & 0 \le x \le 1 \\ \frac{m\lambda}{b} [1 - e^{-\gamma}e^{\gamma x}], & x \ge 1 \end{cases}$$

To compute $m$ we use

$$(17) \qquad m + \int_{0}^{\infty} fdx = 1$$

which yields after some computation, and on condition that $\gamma < 0$ (i.e. $\rho < 1$)

$$(18) \qquad m = 1 - \rho$$

for the probability of an empty queue, which one would expect to obtain.

Note that

$$f + m \delta(x)$$
to be a density function we must have $m > 0$ or $\rho < 1$. Finally let us compute $n$ the average number of customers in the system at steady-state. Let us discretize the density by setting

$$ \pi_0 = m; \quad \pi_i = \int_{i-1}^{i} fdx, \quad i > 0 $$

where $\pi_i$, $i \ge 0$, denote the stationary probabilities for the number of customers in queue. We can then compute

$$ (19) \qquad \begin{aligned} n &= \sum_{i=1}^{\infty} i \pi_i = \rho \left[ 1 - \frac{1}{\gamma} \right] \\ &= \rho \left[ 1 + \frac{(\rho + K_s)}{2(1-\rho)} \right] \end{aligned} $$

This differs from the POLLATZEK-KHINTCHINE formula which yields

$$ (20) \qquad \hat{n} = \rho \left[ 1 + \frac{\rho(1+K_s)}{2(1-\rho)} \right] $$

Other approaches to diffusion approximations [1], [2] do not yield (18) or (20). Though we are able to obtain the probability of an empty queue correctly with our approach, we have been unable to obtain (20) exactly. Notice that the exact result would have been obtained if $\gamma$ were

$$ \gamma = \frac{-2(1-\rho)}{\rho(K_a + K_s)} $$

instead of (15). The error is given by

$$ n - \hat{n} = \frac{1}{2} \rho K_s $$
IV - APPROXIMATION OF A CLOSED TWO-SERVER SYSTEM.

Consider the closed two-server system shown in Figure 1. The system contains a fixed number M of customers, which we shall call "programs", and we shall call the two servers the CPU (central processing unit) and the SM (secondary memory), respectively. This model has been analyzed by GAVER and SHEDLER [3] using a diffusion approximation with reflecting boundaries. In order to choose appropriate boundary conditions to the diffusion equation they suggest one of three approaches : the use of renewal theory to obtain an exact fit for (i) the case M=1, or (ii) the case M=2, or (iii) the use of the basic queueing theory result $\pi_0=1-\rho$ to obtain an exact fit for M=∞. The results obtained in [3] yield very good fits to an exact solution ; conceptually however one is not fully satisfied since the boundary conditions have to be introduced from queueing or renewal theory.

In this section we analyze the same model as in [3] (shown in Figure 1) making use of the instantaneous return process. Except for the specification of the constants $\alpha, \beta$ of the diffusion equation, no results from queueing or renewal theory need be used to solve for the probability distribution function F(x) of the number of programs in the CPU queue at steady-state. We shall also obtain the probability of an empty CPU queue which will satisfy the queueing theory result for M=∞ mentioned above. It will also be shown that our result satisfies another familiar queueing theory result : that for each server the stationary arrival rate is equal to the stationary departure rate for any value of M.

As previously, let $f(x)$ be the stationary probability density function for the diffusion process in $[0,M[$, where x is the value approximating the number of programs in the CPU queue; $M-x$ will correspond
The boundary conditions on f are (12):

$$ \lim_{x \to 0} f = \lim_{x \to M} f = 0 $$

we integrate (21) once to obtain:

$$ (25) \qquad \frac{1}{2} \alpha f' - b f = - \lambda m_1 \phi(x-1) - \mu m_2 \phi(x-M+1) + a $$

where a is a constant, and

$$ \phi(x) = \begin{cases} 0 & \text{for } x \le 0 \\ 1 & \text{for } x > 0 \end{cases} $$

Using (22) we see that:

$$ (26) \qquad a = \mu m_1 $$

and we also see that (26) satisfies (23). We then solve (25) in the three regions $0 \le x < 1$, $1 < x < M-1$ and $M-1 < x \le M$. It can be shown that the solution to (25) must be continuous so that we may use the continuity of $f$ at $x=1$ and $x=M-1$. Solving for $f$ and using (12) we obtain:

$$ (27) \qquad f = \begin{cases} -\frac{\lambda m_1}{b} [1 - e^{\gamma x}], & 0 \le x \le 1 \\ -\frac{\lambda m_1}{b} [e^{-\gamma} - 1]e^{\gamma x}, & 1 \le x \le M-1 \\ -\frac{\mu m_2}{b} [e^{\gamma(x-M)} - 1], & M-1 \le x \le M \end{cases} $$

$$ (28) \qquad m_2 = \frac{\lambda m_1}{\mu} e^{\gamma(M-1)} $$

where, as previously $\gamma = \frac{2b}{\alpha}$. Also, using

$$ (29) \qquad \int_0^M f \, dx + m_1 + m_2 = 1 $$
we obtain

$$ - \int_{0}^{M} f dx = - \frac{\lambda m_{1}}{b} [1 - e^{\gamma(M-1)}] $$

so that

$$ m_1 + \frac{\lambda m_1}{\mu} e^{\gamma(M-1)} - \frac{\lambda m_1}{b} [1 - e^{\gamma(M-1)}] = 1 $$

Then, setting $\rho = \lambda/\mu$,

$$ m_1 = \frac{1}{1 + \rho e^{\gamma(M-1)} + \frac{\rho}{1-\rho} [1 - e^{\gamma(M-1)}]} $$

yielding

**Proposition 1**

The approximation by the instantaneous return process for the closed two-server system yields the stationary probability of an empty CPU queue as

$$ (30) \qquad m_1 = \frac{1-\rho}{1-\rho^2 e^{\gamma(M-1)}} $$

If $\rho < 1$ and is independent of $M$ we have the familiar queueing theory result for $M \to \infty$:

$$ (31) \qquad m_1 = 1 - \rho $$

Furthermore when $\rho = 1$,

$$ (32) \qquad m_1 = \frac{1}{2\left[1 + \frac{(M-1)}{K_a + K_s}\right]} $$

where (32) is valid if the squared coefficients of variation

$$ K_a = \lambda^2 V_a^2, \quad K_s = \mu^2 V_s^2 $$

do not vary with $\rho$. Note also that if $M=1$ we obtain
$$ (33) \qquad m_1 = \frac{\mu}{\lambda+\mu} = \frac{\frac{1}{\lambda}}{\frac{1}{\lambda}+\frac{1}{\mu}} $$

which is the result we would expect from renewal or queueing theory.

Another result is that (28) and (30) imply

$$ (34) \qquad (1-m_2)\lambda = (1-m_1)\mu $$

which states that the arrival rate to the CPU queue is equal to the departure rate, at steady-state.

In figure 2 we compare numerical results for stationary CPU utilization $\eta = 1-m_1$ with the diffusion approximation of GAVER and SHEDLER [3] and the exact semi-Markov analysis of SHEDLER [11]. The SM service time is constant of value $1/\lambda = 1$ and the CPU service time is Erlang (1,2, 3,4,5,∞). $\mu$ is varied; S-M refers to the exact analysis [11], Diff. refers to the diffusion approximation in [3] and I-R refers to our results which seem to be generally closer to the S-M results.
V - CONCLUSIONS.

Diffusion approximations appear to be attractive alternatives to
queueing networks as models of systems of interconnected resources since they
allow a more detailed characterization of service and inter-arrival time
statistics with a greater economy of representation.

The basic problems raised by these approximations are (i) the choice
of the diffusion parameters β(x,t) and α(x,t), (ii) the choice of the
proper boundary conditions, (iii) the selection of the discretization of
the probability density function f(x,t) in the neighbourhood of integer
valued points x=i in order to approximate the probability of finding i
customers in queue at time t. In this paper we have suggested a solution
to the issue raised in (ii) using the instantaneous return process. This is
distinct from previous approaches and seems to yield good approximations in
the cases which have been discussed. Problem (i) can be treated either using
asymptotic renewal theory [1], [3] or as in [12] using WALD's identity
and the results of HAJI and NEWELL [13]. Problem (iii) does not seem to
have been adequately treated as yet.

Our approach to (ii) has the advantage that we do not have to call
upon queueing theory results in order to obtain the integration constants
of the diffusion equation; in fact some familiar queueing theory results
are directly obtained from the instantaneous return model.
ACKNOWLEDGEMENTS

I thank Messrs. QUADRAT and VIOT of IRIA-LABORIA for discussions on the elementary return process.
<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>
REFERENCES

1. G.F. NEWELL
*Applications of Queueing Theory*,
Chapman and Hall, Ltd., London, 1971.

2. D.P. GAVER
Diffusion Approximations and Models for Certain Congestion Problems,
*J. Appl. Prob.* 5, 607-623 (1968).

3. D.P. GAVER and G.S. SHEDLER
Processor utilization in Multiprogramming Systems via
Diffusion Approximations,
*Opns. Res.* 21, 569-576 (1973).

4. H. KOBAYASHI
Application of the Diffusion Approximation to Queueing Network
Part I - Equilibrium Queue Distributions,
ACM-SIGME First Symposium on Measurement and Evaluation, 54-62
Palo Alto, Calif. (1973).

5. E. GELENBE
Modèles de Systèmes Informatiques,
Thèse de Doctorat d'Etat ès Sciences Mathématiques, Université
Paris VI (1973).

6. W. FELLER
The Parabolic Differential Equations and the Associated Semi-
groups of Transformations,
*Ann. Math.* 55, 468-519 (1952).

7. W. FELLER
Diffusion Processes in One Dimension,
*Trans. Am. Math. Soc.* 77, 1-31 (1954).

8. A.T. BHARUCHA-REID
Elements of the Theory of Markov Processes and Their Applica-
tions,
McGraw-Hill, New York, 1960.

10. J.R. JACKSON
Jobshop-Like Queueing Systems,
*Management Sci.* 10, 131-142 (1963).

11. G.S. SHEDLER
A Cyclic Queue Model of a Paging Machine,
IBM Research Report RC-2814, IBM Watson Research Center,
Yorktown Heights, New York, March 1970.

12. D.P. GAVER and G.S. SHEDLER
Approximate Models for Processor Utilization in Multi-
programmed Computer Systems,
Research Report, Naval Postgraduate School, Monterey, California
September 1972.
13. HAJI,R. and NEWELL,G.F., A Relation Between Stationary Queue and Waiting Time Distributions, J. Appl. Prob. 8, 3, 617-620, 1971.