# Exact and approximate solution to probabilistic models of computer system behaviour part 1

Erol Gelenbe

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

## To cite this version:

Erol Gelenbe. Exact and approximate solution to probabilistic models of computer system behaviour part 1. [Research Report] IRIA-RR-124, IRIA. 1975, pp.39. hal-04716112

HAL Id: hal-04716112

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

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
02142 AR124

RIA
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

Exact and approximate solution
to probabilistic models
of computer system
behaviour
Part 1.

Evol
E. Gelenbe

Rapport de Recherche n° 124

Mai 1975
# EXACT AND APPROXIMATE SOLUTION TO PROBABILISTIC MODELS OF COMPUTER SYSTEM BEHAVIOUR-PART I +)

E. Gelenbe

Université de Liège, et IRIA-LABORIA

These notes served as a basis for lectures delivered at the International School on Computer System Modelling held at the University of Bologna in February 1975, and sponsored by the Centro Nazionale delle Ricerche (C.N.R.).

## Résumé

Nous présentons dans cet article une synthèse de certains résultats mathématiques concernant les réseaux de files d'attente et qui s'appliquent à l'étude des performances des systèmes informatiques. Il s'agit, en particulier, du théorème de Baskett-Chandy-Muntz-Palacios concernant les solutions en forme de produit des équations de Chapman-Kolmogorov à l'état d'équilibre pour des réseaux de files d'attente Markoviens, des théorèmes de Chang-Lavenberg-Traiger sur les taux d'activité des serveurs, des méthodes d'équivalence et de décomposition de Avi-Itzhak, Heyman et Courtois. Nous rappelons aussi les résultats plus anciens de Jackson et de Gordon-Newell.

## ABSTRACT

This paper is a survey of certain known results concerning networks of queues. The choice of the topics presented has been made with special emphasis on mathematical results which can be applied to the analysis and synthesis of mathematical or simulation models of complex computer systems in which an ensemble of resources is shared among a set of user programs. The subjects covered include the Jackson, and Gordon and Newell theorems; the work-rate theorems of Chang, Lavenberg and Traiger; the Baskett, Chandy, Muntz, Palacios result, and the equivalence and decomposition technique of Courtois, and Avi-Itzhak and Heyman. A companion paper (Part II) will present some new results of the author concerning diffusion approximations as well as a brief review of previous work on the subject.

+) Article en cours de publication.
# I - INTRODUCTION

The theory of networks of queues is developing rapidly under the impact of problems which have been raised by the mathematical modelling of multiprogrammed computer systems and related topics. The thrust of recent work has been towards establishing explicit expressions for the equilibrium probabilities of queueing networks of increasing complexity [1, 2, 3] ; these results serve largely as a guideline to the search for approximate solutions of queueing models for which exact solutions have not yet been found and which may well be unobtainable. Interesting and useful results have been obtained by approximating queueing systems with continuous processes [4, 5, 6, 7] which appear to yield very accurate predictions for wide ranges of parameter values [8, 9]. Iterative techniques based on heuristic considerations [10] have also been considered and appear quite promising. Approximate solutions to some models in which intricate structural dependencies exist have been given in [11, 12]. The analysis of systems in which blocking phenomena occur [13, 14] has also been examined.

The purpose of this lecture is to present in a unified manner some of these results which are directly applicable to the performance analysis of multiprogramming systems.

We shall begin with Jackson's theorem [1] concerning a queueing network (QN) with exponentially distributed service time, Poisson arrivals, and routing in the network described by a first-order Markov chain. Both the "closed" and "open" version of the result will be given and the relationship to a representation of computer system behaviour will be presented. The shortcomings of Jackson's theorem for the accurate representation of such systems will motivate the remaining discussion.
In section III the model considered by Jackson is generalized to include arbitrary service time distributions. In this case little can be said concerning equilibrium probability distributions. There is, however, an interesting theorem due to Chang and Lavenberg [15] yielding a relationship between the work-rates of the different processors for a closed QN which we generalize to the case where the routing of customers is described by an h-order Markov chain ($h \ge 1$). Another work-rate theorem [16] is given stating that work-rates are unchanged if in Jackson's QN some or all of the servers at which queues cannot build up are replaced by servers with service times of general distribution but identical mean.

Section IV is devoted to the presentation of the BCMP (Baskett, Chandy, Muntz, Palacios) [2] theorem.

The result in [2] is a substantial contribution to the area. Jackson's model is extended to one in which several classes of customers share the QN. Let a service station operate under a BCMP discipline if the latter is either a round-robin processor sharing (RR) or a pre-emptive-resume priority last-come-first-served discipline (LCFS). The product form equilibrium solution to the network equations is given [2] for a QN in which almost general distribution functions are allowed at stations containing an infinite number of servers or those utilizing the BCMP discipline.

The fifth section is devoted to a brief presentation of a decomposition technique due to Courtois [11] and Avi-Itzhak and Heyman [12]. This method is useful in obtaining approximate solutions to queueing networks in which service time distributions depend on the total number of customers in a part of the system. Applications of this approach to virtual memory systems have been given in [11]; other interesting examples are provided in [12]. A final section is devoted to conclusions and some open problems.
Solution methods for first-come-first-served discipline and general service time distributions are not treated in this paper. Such QN can be approached using diffusion approximations [5-8] ; a companion paper will present some new results and applications in this direction.

A survey article by R. Muntz [28] discusses some of the applications which have been made of the methods presented here to the performance evaluation and prediction of existing systems.

## II. JACKSON'S THEOREM

Consider the QN of Figure 1. A set of service stations are interconnected to each other via an arbitrary topology. Customers enter the network via a source and are directed to a service station. These stations allocate service to the customers awaiting service in the respective queues in FCFS order. The analogy with a complex computer system is immediate : the customers are tasks or processes (in the sense attributed to this word in computer science) and the service stations are processors (central processing units, input-output channels, etc...), although a large number of application areas outside computer systems may be imagined. Another analogy with a computer system may also be considered : the service stations could be processes utilizing a set of resources (the customers in Jackson's model) ; these resources are created by an external agent (the arrival process) or are destroyed (the departure of customers), or again a resource is obtained by process j (service station j) after having been utilized by process i.

Let us now turn to a precise definition of the model which consists of n service stations. Let $k = (k_1, ..., k_n)$ be vector of non-negative integers, $k_i$ being the number of customers present at service station i, and denote by $K = \sum_{i=1}^{n} k_i$ the total number of customers in the
network. The service time at station i is a random variable $\chi_i$ which is
independent and identically distributed for each customer ; it is assumed
that $\text{Pr}\{\chi_i \le t\} = 1 - \exp(-\mu_i(k_i)t)$ where $\mu_i(k_i)$ is some function of $k_i$.
Let $\mathcal{Y}_m$ be the m.th service station visited by a customer which has entered
the system ; then $\{\mathcal{Y}_m ; m = 1, 2, ...\}$ is a Markov chain whose transition
matrix $P = (p_{ij})$ is defined as $p_{ij} = \text{Pr}[\mathcal{Y}_{m+1} = j | \mathcal{Y}_m = i]$ for any
$m = 1, 2, ...$, where i and j correspond to service stations. In the "open"
model $p_{oj}$ will be the probability that an extremal arrival first enters
station j if $1 \le j \le n$. We take $p_{o, n+1} = 0$. For $1 \le i \le n$, $p_i, n+1$ is
the probability that a customer leaves the system after completing service
at station i. The arrival process of customers is assumed to be Poisson
(interarrival times are exponentially distributed) with rate $\lambda(K)$ function
of the total number of customers in the system. With these assumptions
it is immediatly seen that the stochastic process representing the number
of customers in each queue is a continuous time Markov chain [17]. Let
$a(k, i)$ and $b(k, i)$ be vectors identical to k except for the element $k_i$
which is replaced by $k_i+1, k_i-1$ respectively. Let also $C(k, i, j)$ be
identical to k except for $k_i$ an $k_j$ which are replaced by $k_i+1, k_j-1$ respec-
tively. Define the probability $p(k, t)$ that the system is in state k at
time t. The Chapman-Kolmogorov equations for the open model are then

$$
\begin{align*}
(1) \quad \frac{d}{dt} p(k, t) = & - (\lambda(K) + \sum_{i=1}^{n} \mu_i(k_i) (1-p_{ii})) p(k, t) \\
& + \sum_{i=1}^{n} \lambda(K-1) p_{oi} p(b(k, i), t) \\
& + \sum_{i=1}^{n} \mu_i(k_i+1) p_{i, n+1} p(a(k, i), t) \\
& + \sum_{i \neq j} \sum_{k_j}^{n} \mu_i(k_i-1) p_{ij} p(C(k, i, j), t)
\end{align*}
$$

where it has been assumed that $p(k, t) = 0$ for any $k$ containing a negative
element. We shall assume that $0 < \mu_i(k_i) < 0$ for all $i$, except for $k_i = 0$
where $\mu_i(0) = 0$ and that the Markov chain $\{\mathcal{Y}_m\}$ has a single transient
state (0) and a single absorbing state (n+1). Under these assumptions it
can be shown that (1) represents the state transitions of an irreducible
continuous time Markov chain. Foster's theorems [18]*) guarantee the
existence of a joint equilibrium probability distribution for the number
of customers in each queue if there exists any positive solution {$p(k)$}
to (1) with $(dp(k, t)/dt) = 0$ such that $\Sigma p(k) < \infty$.

Let $\hat{P}$ be obtained from $P$ by deleting its first row and last column, and $e = (e_1, \dots, e_n)$ be a row vector such that

$$
(2) \qquad e = (p_{01}, \dots, p_{0n}) + e \hat{P}
$$

Denote

$$
N(k) = \sum_{i=1}^{n} \sum_{m=1}^{k_i} \pi^{i} \mu_{i} (e_{i} / \mu_{i}(m))
$$

and

$$
\omega(K) = \begin{cases} K-1 & \lambda(m) \\ \pi & m=0 \end{cases}
$$

$$
T(K) = \begin{array}{ll} \sum & N(k) \\ \text{all } k \\ \text{s.t. } \sum_{1}^{n} k_i = K & \end{array}
$$

For the open model we have described, Jackson's theorem becomes

**Theorem 1** : The equilibrium joint probability distribution {$p(k)$} for the number of customers exists if e of (2) has a unique non-negative solution and $\sum_{K'=0}^{\infty} \omega(K')$ $T(K') < \infty$. It is given by

$$
p(k) = \left[ \sum_{K'=0}^{\infty} \omega(K') T(K') \right]^{-1} N(k) \omega(K)
$$

<footnote>*) Although Cohen's book [18] is not the primary reference for Foster's theorems, the account given of them is very good.</footnote>
The elements of e have a simple physical interpretation ; $e_i$ is the average number of times a customer transits through station i before leaving the system.

Now consider the "closed" model in which a constant number K of customers circulates within the QN indefinitely. The routing behaviour is given by a first-order irreducible Markov chain with transition matrix $P = (p_{ij})_{nxn}$. The Chapman-Kolmogorov equations are now

$$ (3) \quad \frac{d}{dt} p(k, t) = - \left( \sum_{i=1}^{n} \mu_i(k_i) (1-p_{ii}) \right) p(k, t) \\ \qquad + \sum_{i \neq j}^{n} \sum_{k_i=k}^{n} \mu_i(k_i+1) p_{ij} p(c(k, i, j), t) $$

where we have used the same notations as previously, including the rule that $p(k, t) = 0$ if $k$ contains a negative element and that $0 < \mu_i(k_i) < \infty$ except $\mu_i(0) = 0$.

In this case Jackson's theorem becomes identical to a result discovered much later by Gordon and Newell [19]. We shall refer to Theorems 1 and 2 as the JGN theorems.

**Theorem 2** : Let $\pi$ be the unique probability row vector satisfying $\pi P = \pi$ and $\pi_i, 1 \le i \le n$, its i-th element. Then $p(k)$, the equilibrium probability distribution satisfying (3) with $\sum_{i=1}^{n} k_i = K$, $k_i \ge 0$, exists and is given by

$$ p(k) = v(k) [G(K)]^{-1} $$

where

$$ v(k) = \sum_{i=1}^{n} \pi_i \frac{k_i}{\pi_i - \pi} \sum_{j=1}^{n} \frac{1}{\mu_j(k_j)} $$

and $G(K)$ in a normalizing constant so that $\sum p(k) = 1$.
Proofs of Theorems 1 and 2 are quite simple since they can be carried out by direct substitution in the equilibrium equations obtained by setting the time derivatives of $p(k; t)$ to zero in (1) and (3).

The JGN models present several shortcomings in their applicability to computer system modelling. The main ones are :

- (i) inability to distinguish among classes of customers with distinct stochastic behaviour

- (ii) restriction on service time and interarrival time distributions which must be exponential

- (iii) restriction on probabilistic routing behaviour given by a first order Markov chain

- (iv) inability to handle certain service disciplines of interest such as round-robin (RR)

- (v) exclusion of QN in which service time parameters depend on the number, and properties, of customers in a subnetwork rather than in each queue.

The remaining parts of this lecture are devoted to results which allow us to remove most of these restrictions. There is at this time, however, no one single model for which equilibrium probability distributions are known and which can represent systems where (i) - (v) cannot be assumed.

The theorems of Jackson and Gordon and Newell have played and still play a central role in research on the theory of queueing networks. We shall see that more general network solutions can be often obtained as equivalent JNG networks. These transformations also serve as a proof technique in establishing properties of more general QN. Also, the diffusion approximation results presented in [5, 8] are partly based on postulating a structure for the equilibrium probabilities similar to that presented in this section.
### III.- WORK RATE THEOREMS

Exact solutions for the equilibrium probabilities of queueing networks with first-come-first-served (FCFS) service discipline and general service times are unavailable at present. The diffusion models presented in Section V yield only approximate solutions. Some interesting general results can, however, be given for the equilibrium work-rates of the service stations. These are mainly due to Chang and Lavenberg [15] and Lavenberg, Traiger and Chang [16].

Unless stated otherwise, the QN examined in this section are closed with K customers and n service stations. A customer proceeds to queue j after terminating service at queue i with probability $p_{ij}$. The matrix $P = (p_{ij})_{nxn}$ is irreducible. Service times at station i are independent and identically distributed with mean $0 < \mu_i^{-1} < \infty$ and general distribution function $F_i = F_i(t)$; station i contains $m_i$ service centers with $m_i \ge 1$, $1 \le i \le n$; the case $m_i \ge K$ is possible and corresponds to a station with no queueing delay. If $F_i(t)$ is an exponential distribution, this assumption will correspond to taking $\mu_i(k_i)$ of the form

$$ \mu_i(k_i) = \begin{cases} k_i \mu_i & \text{if } 0 \le k_i \le m_i \\ m_i \mu_i & \text{if } k_i > m_i \end{cases} $$

Service times are independent from one station to another and are mutually independent at any given station; the service discipline is FCFS.

The state of the model is characterised by the number of customers and by the service time which has been obtained by those in service at each station. We define the service rendered by station i in $[0, t]$ as $W_i(t)$. The following theorem, due to Chang and Lavenberg [16], is stated without proof.
**Theorem 3** : $u_i = \lim_{t \to \infty} \frac{W_i(t)}{t}$ exists with probability one and is independent of the state at $t = 0$. It is the expected number of active servers station i at equilibrium.

The next result is a direct consequence of Theorem 2.

**Theorem 4** : If the model of this section is restricted to $F_i(t) = 1-\exp(-\mu_i t)$, then

$$u_i = \pi_i \mu_i^{-1} \frac{G(K-1)}{G(K)}$$

for $1 \le i \le n$.

**Proof** : We have

$$u_i = \sum_{k_i=1}^{m_i} k_i \frac{\Sigma_k}{k} p(k) + \sum_{k_i=m_i+1}^{K} k_i \frac{\Sigma_k}{k} p(k)$$

yielding the result after some algebra.

**Theorem 5** : If $K = 1$ then for $1 \le i \le n$,

$$u_i = \frac{\pi_i \mu_i^{-1}}{\Sigma_j \mu_j^{-1}}$$

This result is simply a direct consequence of semi-Markov process theory (see, for instance, Howard [20]). For $K=1$ the "position" of the customer is a stochastic process described by a first order Markov chain for state transitions and holding times in each state defined by general distribution functions. The work-rate of station i is then the equilibrium probability of finding the customer in that station.
$u_i$, which is the equilibrium value of the expected number of servers active at station i, can be interpreted as the equilibrium probability that station i is active when $m_i = 1$.

A result analogous to Theorem 4 has been established [15] for QN in which the only non-exponential service distribution are associated with stations at which no queueing can occur. This result can now be considered as a special case of the BCMP theorem [2] given in the next section.

**Theorem 6** : Maintaining the other assumptions stated at the beginning of this section suppose that $F_i(t) = 1-\exp(-\mu_i t)$, $1 \le i \le b$, and $m_i \ge K$ for $b+1 \le i \le n$. Then for all $1 < i \le n$

$$u_i = \pi_i \mu_i^{-1} \frac{G(K-1)}{G(K)}$$

**Proof** : The idea of the proof is simple. We first show that Theorem 6 is true if each $F_j$, $b+1 \le j \le n$, is a mixture of Erlang distributions. Then we establish a well-known result : any distribution function of finite mean for a non-negative random variable can be approximated arbitrarily closely by a mixture of Erlang distributions. Under the assumptions of the theorem we are then able to invoke continuity of the work-rates to complete the proof. We shall proceed as in [15].

**Lemma 1** : If the servers at which no queueing can occur have a service time distribution which is a mixture of Erlang laws then Theorem 6 is true.

An Erlang-q distribution with mean $q/\alpha$ corresponds to the distribution function of a random variable which is the sum of q exponential random variables, each of parameter $\alpha$; it is therefore given by

$$E(t) = 1 - \sum_{j=0}^{q-1} \left( \frac{\alpha t}{j!} \right)^j e^{-\alpha t}$$
$$ \text{Now let } F_i(t) = \sum_{r=1}^{s_i} C_{ir} E_{ir}(t) $$

where $E_{ir}(t)$ is the law $E(t)$ with parameters $q_{ir}$ and $\alpha_{ir}$, and $C_{ir} > 0$,

$$ \sum_{r=1}^{s_i} C_{ir} = 1 $$

We now construct a new QN by adding to each server of station i, $s_i$ new stations $i1, ..., i_s$, succeeding the previous i-th station; a customer entering any server in station i in the old network will enter an exponential station $i1$ in the new network whose average service time is $\alpha_{ir}^{-1}$ with probability $C_{ir}$, $1 \le r \le s_i$. It will then proceed through $q_{ir}^{-1}$ other identical stations before going to station j with probability $p_{ij}$. Notice that the new QN has exponential service at all stations and no queueing at stations derived from no-queueing stations of the old network. Each "new" station sequence $i1, ..., i_s$ must contain only one customer : this is not really a restriction since there are $m_i \ge K$ such sequences. Therefore Theorem 2 is applicable. Call $k' = (k_1, ..., k_b, k_{b+1}, 1, ..., k_{b+1}, s_1, ..., k_n, s_n)$ and $P'$ the new transition matrix for routing behaviour. Let $\pi'P' = \pi'$ be the new vector of equilibrium probabilities corresponding to $P'$ : $\pi_i$ in $\pi$ has been replaced by $\pi_{i1}, ..., \pi_{is_i}$ in $\pi'$ for $b+1 \le i \le n$. It is easily seen that $P'$ will also be irreducible, furthermore $\pi'_i = a\pi_i$, $1 \le i \le b$, and $\pi'_{ir} = a C_{ir} \pi_i$ for $b+1 \le i \le n$ and $1 \le r \le s_i$. We then have,

$$ p(k') = [g(K)]^{-1} \sum_{i=1}^{b} \pi^{k_i} (a\pi_i \mu_i^{-1})^{k_i} \sum_{i=b+1}^{s_i} \pi^{k_{ir}} (q_{ir} a C_{ir} \pi_i \alpha_{ir}^{-1})^{k_{ir}/k_{ir}!} $$

However

$$ \sum_{k_{i1}, \dots, k_{is_i}} s_i \frac{(z_{ir})^{k_{ir}}}{\pi^{k_i} k_{ir}!} $$ 
 s.t. $\sum k_{ir} = k_i$

$$ = \frac{1}{k_i!} \left( \sum_{r=1}^{s_i} z_{ir} \right)^{k_i} $$
and $\sum_{r=1}^{s_i} q_{ir} C_{ir} \alpha_{ir}^{-1} = \mu_i^{-1}$. Therefore

$$p(k) = a^K [f(K)]^{-1} v(k)$$

We normalize setting $[g(K)]^{-1} = a^{-K}[G(K)]^{-1}$ completing the proof since Theorem 6 is true if all service times are exponential.

The next lemma is classical (see Cox[22] for further details).

**Lemma 2** : Let $F(t)$ be an arbitrary distribution function for a non-negative random variable of finite average. There exists for each $\varepsilon > 0$ a distri- bution function $\Phi(t)$ which is a convex combination of Erlang laws such that

$$\int_{0}^{\infty} |F(t) - \Phi(t)| dt < \varepsilon, \quad \left| \int_{0}^{\infty} t(F(t) - \Phi(t)) dt \right| < \varepsilon$$

**Proof** : We follow closely the proof in [15]. The idea is to construct a staircase approximation

$$\bar{F}(t) = \sum_{r=1}^{s} C_r u(t - rh)$$

to $F(t)$, where $h$ is the discretisation step, $u(t)$ is the unit step function and $s$ has been chosen so that

$$\int_{\tau}^{\infty} (1 - F(t)) dt < h$$

where $s$ is the integer part of $\tau/h$ plus 2. Also

$$C_r = F(h(r+1)) - F(h_r), \quad 2 \le r \le s-1$$

$$C_1 = F(2h), \quad C_s = 1 - F(sh)$$
Notice that $C_r \ge 0$, $\Sigma C_r = 1$. Each element step function is then shown to approximate an Erlang function establishing the correspondence between $F(t)$ and a convex combination of Erlangs. Clearly

$$ \int_{0}^{\infty} |F(t) - \bar{F}(t)| dt \le 2hC_{1} + \sum_{r=2}^{s-1} hC_{r} + hC_{s} = 2h $$

Also

$$ \begin{aligned} & \int_{0}^{\infty} \left| 1 - \sum_{r=0}^{s-1} \left( \frac{\alpha t}{r!} \right)^r e^{-\alpha t} - u(t - s/\alpha) \right| dt \\ &= 2 \int_{0}^{s/\alpha} dt \left( 1 - \sum_{r=0}^{s} \left( \frac{\alpha t}{r!} \right)^r \right) = \frac{2se^{-r}r^r}{\alpha r!} \end{aligned} $$

which tends to zero for $r \to \infty$. Then

$$ \begin{aligned} & \int_{0}^{\infty} |F(t) - \Phi(t)| dt \le \int_{0}^{\infty} |F(t) - \bar{F}(t)| + \int_{0}^{\infty} |\bar{F}(t) - \Phi(t)| \\ & < \varepsilon \end{aligned} $$

The proof that the absolute value of the difference of the expected values is less than $\varepsilon$ is analogous.

To complete the proof of Theorem 6 an additional result is used from [16].

**Lemma 3** : $F = (F_1, \dots, F_n)$ be a set of probability distribution functions for a QN satisfying the assumptions of this section and let $\{F^m\}$ be a sequence of sets of such functions with

$$ \lim_{m \to \infty} \sum_{i=1}^{n} \int_{0}^{\infty} |F_{i}^{m}(t) - F_{i}(t)| dt = 0 $$
Then if $u_i(F)$ is the work-rate of station i with distribution functions $F_1, \dots, F_n$ we have

$$ \lim_{m \to \infty} u_i(F^m) = u_i(F) $$

From this result the theorem is now immediate. Notice that in the proof of theorem 6, and in particular in the proof of Lemma 1, our equations imply that stations 1 to b contain one server only; clearly, the generalisation to $m_i > 1$ servers at these stations is immediate by modifying the expression for $p(k')$.

For the QN model this section Chang and Lavenberg have established the following :

**Theorem 7 [15]** : For the QN networks of this section

$$ \frac{u_i}{u_j} = \frac{\pi_i \mu_i^{-1}}{\pi_j \mu_j^{-1}} $$

This result can be of use in simulation studies of queueing networks, since it implies that work-rates for all queues can be deduced if the work-rate at only one station is known (or has been measured).

On the other hand, Lemma 3 can be helpful in computing work-rates approximately; if one replaces general service time distributions by appropriately chosen distributions which can be expressed as linear combinations of Erlang distributions, the resulting model is a continuous-time Markov chain which can (in principle) be solved numerically. Lemma 3 guarantees that in this manner one can compute work-rates with any desired degree of accuracy.

Another useful result has been established in [15].
**Theorem 8** : Let $u_i^{(K)}$ be the work-rate at station i, $1 \le i \le n$, of the closed QN with general service time distributions and K customers. Then

$$u_i^{(K)} \le u_i^{(K+1)}$$

for all $K = 0,1, ...$

This result has the simple consequence that Theorem 5 provides a lower bound to the values of the work-rates for each station.
## IV. THE BCMP THEOREM

The major extension of the work of Jackson came a decade after his paper [1]. Although Jackson's work was in the line of traditional operations research, the BCMP theorem was motivated by problems of computer system modeling although it has far wider implications than just in computer science.

In this section we shall first consider the general model analyzed by Baskett, Chandy, Huntz and Palacios [2]. We then state their theorem.

Consider a network of queues with n service stations. Customers belong to one of $\xi$ classes at any instant of time during their existence in the network. Routing in the network is described by a Markov chain with transition matrix $P = (p_{i,c;j,c'})$ where $0 \le i, j \le n+1, 1 \le c, c' \le \xi$; $p_{i,c;j,c'}$ is the probability that a customer of class c leaving station i will enter station j as a customer to class C' if $1 \le i, j \le n$. $p_{o,c;j,c'}$ is the probability that an external arrival first enter station j ($j \ne n+1$) in class c', and $p_{i,c;n+1,c'}$ is the probability that a customer of class c leaves the network after receiving service at station i.

The most general service time distribution considered is one which has rational Laplace transform; we shall call such service time distributions Coxian [22]. Notice that convex mixtures of Erlang distributions are Coxian so that, by Lemma 2 an arbitrary distribution may be approximated as closely as one may wish by a Coxian distribution having approximately the same mean. The service stations of the network are of one of the four following types.

**Type 1** : The station i has a single server with exponential service time of parameter $\mu_i(k_i)$ identical for all classes, $k_i$ being the total number

<footnote>+) A brief introduction to these distributions is given in the Appendix.</footnote>
of customers at the station, and the service discipline being FCFS.

**Type 2** : The service time distributions are Coxian and may be distinct for each class. There is a single server and the discipline is processor sharing (PS) so that each customer receives $k_i^{-1}$ seconds of service per second.

**Type 3** : The service time distributions are Coxian and may be distinct for each class. The number of servers at this station is larger than the maximum number of customers which may be queued here at any instant of time.

**Type 4** : The station contains a single server which allocates service according to a pre-emptive resume last-come-first-served discipline. That is, a new arrival interrupts the current service and takes over the server ; the interrupted customer resumes service when the customer which has interrupted it has finished . The interrupted customer's remaining service time is its total service time minus the amount it has already obtained. The service time distributions are Coxian and may be distinct for each class.

The arrival process to the QN is Poisson of parameter $\lambda(K)$ where K is the total number of customers in the network *) .

In order to state the BCMP theorem we shall have to develop some notations. Let {$e_{jc}$} be a solution to the system of equations

$$e_{jc} = \sum_{c'=1}^{\xi} \sum_{i=1}^{n} e_{ic'} p_{i,c';j,c'} + p_{0,c';j,c}$$

for $1 \le j \le n$, $1 \le c \le \xi$. $e_{jc}$ is the relative frequency (or the normalized average number) of visits of a class c customer to service center j.

<footnote>*) A somewhat different arrival pattern is also allowed in [2].</footnote>
The state of the QN is the vector

$$ \hat{k} = (\hat{k}_1, \dots, \hat{k}_n) $$

where if station i is of

Type 1 :

$$ \hat{k}_i = (k_{i1}, \dots, k_{ik_i}) $$

$k_{ij}$ is the class of the j-th customer at station i in FCFS order.

Type 4 :

$$ \hat{k}_i = ( (k_{i1}, s_{i1}), \dots, (k_{ik_i}, s_{ik_i}) ) $$

$k_{ij}$ is the class of the j-th customer in LCFS order and $s_{ij}$ is its stage.

Type 2 or 3 :

$$ \hat{k}_i = ( (k_{i1}, s_{i1}), \dots, (k_{ik_i}, s_{ik_i}) ) $$

where $k_{ij}$, $s_{ij}$ are as in Type 4 except that the order is arbitrary. We denote by $k_{icm}$ the number of customers of class c in the m-th stage of service at station i.

We denote by $\mu_i(j)$ the parameter of the negative exponential service time distribution at a Type 1 station when $k_i=j$.

The Coxian densities will be represented as (see Figure 2) a sequence of exponential stages : $S_{ic}$ is the number of stages of the service time distribution of class c customers at station i and $\mu_{icm}$ is the parameter of the exponential distribution at its m-th stage. A customer's service time is then the sum of independent exponential random variables ; after the m-th stage the customer either heads for the (m+1)-th stage or ends its service with fixed branching probabilities. $A_{icm}$ is the probability that a class c customer at station i will reach its m-th stage of service.
For further details, it is suggested that the reader refer to the discussion in the Appendix.

The BCMP Theorem is

**Theorem 9** : $p(\hat{k})$ the equilibrium probability distribution of $\hat{k}$ exists if $\gamma < \infty$. It is given by

$$p(\hat{k}) = \gamma^{-1} h(K) \prod_{i=1}^{n} f_i(\hat{k}_i)$$

where K is the total number of customers in state $\hat{k}$ and

$$f_i(\hat{k}) = \begin{cases} \sum_{j=1}^{k_i} (e_{ik_i} / \mu_i(j)), & \text{if } i \text{ is Type 1} \\ \sum_{c=1}^{\xi} \frac{S_{ic} (e_{ic} A_{icm} \mu_{icm}^{-1})^{k_{icm}}}{\pi \pi m=1} / k_{icm}!, & \text{if } i \text{ is of Type 2} \\ \sum_{c=1}^{\xi} \frac{S_{ic} (e_{ic} A_{icm} \mu_{icm}^{-1})^{k_{icm}}}{\pi \pi m=1} / k_{icm}!, & \text{if } i \text{ is of Type 3} \\ \sum_{j=1}^{k_i} (e_{ik_j} A_{ik_j} s_{ij} \mu_{ik_j}^{-1} s_{ij}), & \text{if } i \text{ is of Type 4} \end{cases}$$

where

$$h(K) = \begin{cases} K-1 & \pi \quad \lambda(m) \quad \text{if the QN is open} \\ \pi & m=0 \\ 1 & \text{if it is closed} \end{cases}$$

$$\gamma = \sum_{\hat{k}} h(K) \prod_{i=1}^{n} f_i(\hat{k}_i)$$

**Theorem 10 (Marginal distributions)** : Let $k = (k_1, ..., k_n)$. The equilibrium probability of $k$, $p(k)$, exists under the same condition as $p(\hat{k})$. It is given by

$$p(k) = \gamma^{-1} \lambda(m) \prod_{i=1}^{n} g_i(k_i)$$
where if station i is of

Type 1 :

$$g_i(k_i) = e_i^{\frac{k_i}{\pi}} \mu_i^{j-1}$$

Type 2, 4 :

$$g_i(k_i) = \left( \sum_{c=1}^{\xi} e_{ic} \mu_{ic}^{-1} \right)^{k_i}$$

Type 3 :

$$g_i(k_i) = \frac{1}{k_i!} \left( \sum_{c=1}^{\xi} e_{ic} \mu_{ic}^{-1} \right)^{k_i}$$

In fact, the BCMP theorem contains as special cases stationary solutions to several models of interest. Consider, for instance, Jackson's QN in which routing is modified so as to be represented by a semi-Markov process [20].

We shall consider a QN identical to that of Section II except that, after completing its service at station i, a customer takes $\tau_{ij}$ seconds to arrive at queue j, where $\tau_{ij}$ is a random variable whose distribution function $F_{ij}(t)$ is Coxian. Of course, this customer will choose station j with fixed probability $p_{ij}$. This model is covered by the BCMP theorem if we add to the original QN $n^2$ new stations $(i,j)$ of Type 3. The new routing probabilities will be

$$p'_{i,(i,j)} = p_{ij}$$

$$p'_{(i,j),j} = 1$$

and $p'_{o,i} = p'_{o,i}$, $p'_{i,n+1} = p'_{i,n+1}$ for all $1 \le i,j \le n$, considering an open QN. If $e'_{i}$ or $e'_{(i,j)}$ are the expected number of visits of a customer to a
station in the new QN and $e_i$ are the corresponding parameters in the original QN, we shall have $e'_i(i,j) = e_i p_{ij}$, $e'_i = e_i$ for all $1 \le i,j \le n$. The equilibrium probability distribution of $k = (k_1, ..., k_n)$ is then

$$p(k) = G \exp \left( \sum_{i=1}^{n} e_i \sum_{j=1}^{n} p_{ij} T_{ij} \prod_{m=0}^{K-1} \lambda(m) \prod_{i=1}^{n} e_i \prod_{j=1}^{k_i} \mu_i(j)^{-1} \right)$$

where $T_{ij} = \int_{0}^{\infty} t F_{ij}(t) dt$, and $k_i, 1 \le i \le n$, refers to the number in queue i. $G$ is the normalizing constant.

Models of this type, in which transitions of customers from one station (after completing their service) to another do not take place instantaneously can be of interest in representing certain aspects of multiprogramming systems. For instance, suppose a job terminates a period of service at the CPU because of an input-output request. Before this request can be placed in the queue of some input-output device it may be necessary to await the availability of input-output buffer space in primary memory. Similarly, before a certain job which has just terminated input-output can join the queue of "ready" jobs at the CPU it may have to wait until it can regain primary memory space (e.g. to load its "working-set" of pages). These can be considered as being random delays of the type discussed above.

Another apparent generalization of the BCMP theorem which is already contained in this important result concerns the generalization to routing probabilities defined by an h-order (rather than first order) Markov chain. Consider, for instance, a job representing a user editing a text at a time-sharing terminal. The behaviour of the job could be characterized by a time spent at the terminal (thinking and typing) followed by a short execution at the CPU (interpreting a file request command), followed by
an input-output (loading a file into primary memory), followed by a CPU execution (modifying the contents of the file), and finally a return to the terminal. Clearly, the probability of transition of the job from one station to the other in this example can depend on, at least, the last two stations it has visited and not just the last one.

To see that this generalization can be reduced to the cases covered by the BCMP theorem, suppose that the routing probabilities of customers are given by the matrix ($p_{I,c; j, c'}$) where $I = (i_1, i_2, ..., i_h)$ represents the last h stations visited by the customer ($i_h$ is the most recent one) and j is the next station it will visit ; c and c' are, as usual, the present and next class to which it will belong. We now obtain a new QN, equivalent to this one, but of the form covered by the BCMP theorem. For each class c and (h-1)-tuple of service stations ($i_1, ..., i_{h-1}$) of the original QN we form a class in the new QN of the form ($i_1, ..., i_{h-1}, c$). The new transition probabilities are now :

$$p'_{i_h, K; j, K'} = p_{I, c; j, c'}$$

where

$$K = (i_1, ..., i_{h-1}, c), K' = (i_2, ..., i_{h-1}, i_h, c')$$

so that routing probabilities are now defined by a first-order Markov chain. The service time distributions for a customer of some class K in the new network are identical to those of a customer of the corresponding class C in the original QN. Otherwise the two networks are identical. Equilibrium probabilities, and other statistics, for the original network can be found by applying the BCMP theorem to the new network and summing over all values of $i_1, ..., i_{h-1}$ for a class K to obtain the corresponding quantity for class c. This remark is reportedly due to R. Muntz.
The four types of service centers included in the BCMP theorem are not all motivated by practical considerations. However Type 2 service centers are, in many cases, a reasonable representation of central processing units allocated in quanta; the processor sharing discipline is an idealization with a quantum of "very small" (in fact, zero) duration and no overhead associated with switching from one job to the other. A Type 3 station represents well terminals in a time sharing system. Type 1 service centers are useful in many instances (secondary memory units, input-output devices, etc.). There are no concrete examples for the use of Type 4 stations in computer systems.
Of the five important restrictions outlined in Section II which must be satisfied by QN which can be handled by the JGN theorems, the fifth is particularly restrictive in situations where we deal with systems in which only a limited number of tasks can access a certain subset of system resources or where service time characteristics at some station are a function of the total number of customers in some part of the computer system. A simple example comes to mind. The uninterrupted service time at the CPU will be a function of the page fault rate in a virtual memory computer [11], [25], [26], [27] (that is, on the rate of references to units of information of the address space which reside outside of primary memory), and this rate will depend on the amount of primary memory allocated to a given program and thus, for fixed total primary memory space, on the number of programs sharing this space. Therefore the CPU service time will depend on the number of programs in the CPU queue and also on the number in the secondary memory and input-output device queues.

Some problems of this type can be treated via a simple technique devised by Avi-Itzhak and Heyman [12] which yields approximate results. A more general framework for such approaches is available in the work of Courtois [11], which we shall not discuss here and which also contains an interesting application to virtual memory multi-programming computer systems. In the sequel we shall follow the presentation given in [12].

Consider the closed QN of Figure 2 corresponding to the central server model discussed by Buzen [25]. It
contains K customers circulating among the service stations numbered 1 to n; station 1 represents the CPU (the "central server") and the remaining n-1 stations are input-output or secondary memory devices. The routing of jobs in the model is described by the usual first-order markov chain ($p_{ij} \neq 0$, $p_{ij} = 0$, $p_{jl} = 1$ for $i \neq j$, $1 \le i \le n$. Let $\mu_i^{-1}$ be the expected value of the service time at station i, and let us call $p_{li} = \pi_i$, $1 \le i \le n$. By the work-rate theorem we have

$$ \frac{\mu_l}{\mu_i} = \frac{\mu_l^{-1}}{\pi_i \mu_i^{-1}} $$

Let a cycle time be the epoch between two consecutive arrivals of a given customer to the CPU queue. Denote by $T(K)$ the expected value of the cycle time when the total number of jobs in the model is K. By Little's Theorem

$$ K = \mu_l \mu_l T(K) $$

Of course, $\mu_l$ can be a function of K; $\mu_l$ will in any case depend on K. No assumptions regarding service time distributions have been made so far. Now consider the system shown on Figure 3; jobs arrive to be executed on a computer and are placed in an external queue before being admitted into the computer. Each job may cycle again in the computer or leave the system via the output after execution. The computer itself may be considered to be identical to the central server model of Figure 2 during consecutive periods of time when the number of customers in the computer remains constant.

Let Y be the random variable representing the number of times a job cycles in the computer (through the
CPU queue) before it completes service. The expected time between job completions, $\gamma_K^{-1}$ (when there are K customers in the central server model), satisfies (by Little's theorem) :

$$ \gamma_K E\{Y\}T(K) = K $$

or the average rate of job completions is

$$ \gamma_K = q_1 \mu_1 (E\{Y\})^{-1} $$

Now suppose that the average interarrival time $\lambda^{-1}$ of customers from the input is much larger than the expected time taken by the computer to reach equilibrium; this means that in a cycle time of a customer, K will remain (roughly) unchanged. If we abolish the external queue, the Avi-Itzhak and Heyman approximation consists in replacing the system of Figure 6 by a single-server queue with average inter-arrival time $\lambda^{-1}$ and average service time $\gamma_K^{-1}$ where K is the number in queue - of course, K is now variable. In [12] the server is replaced by an exponential server. If the arrival process is Poisson then the approximate stationary probability distribution for the number in queue is, of course,

$$ p_K = p_0 \lambda^K (\gamma_1 \dots \gamma_K)^{-1} $$

where $p_0$ is chosen so that $\sum p_K = 1$, and will exist if a positive solution of finite sum of the stationary equations

$$ \lambda p_0 = \gamma_1 p_1 \\ (\lambda + \gamma_K) p_K = \lambda_{K-1} p_{K-1} + \gamma_{K+1} p_{K+1} $$

exists. We may take also the arrival rate to be a function of K. If the computer can admit at most N jobs (for ins-
tance, because of limitations of primary memory space) then the excess jobs will be kept in the external queue of Figure 6 and, since $K \le N$, we write

$$ \gamma_m = \begin{cases} q_1(m) \mu_1(m) (E\{Y\})^{-1} & \text{if } m \le N \\ q_1(N) \mu_1(N) (E\{Y\})^{-1} & \text{if } m \ge N \end{cases} $$

and replace K by m in the equations above, where m is now the total number of jobs (K plus those in the external queue) in the system, and we have explicitly indicated that $q_1$ is a function of K and that $\mu_1$ may also depend on K.

Even if the central server model of Figure 5 has exponential service times at each station, the birth-death model suggested by the equilibrium equations is only approximate since the time between two consecutive job completions (as defined above) is not exponentially distributed. The quantity $q_1(K)$ to be used in obtaining the approximate solution may be obtained via simulation of the central server model (using the assumption that K changes slowly with respect to the time it takes the central server model to attain statistical equilibrium). $q_1(K)$ may also be computed using the assumption that each service time distribution in the system of Figure 2 is exponential.

In [12] this approach is applied to several examples with a comparison to exact solutions; the accuracy appears to be very good.

The presentation in [11] provides a broader and more rigorous basis for such approximations in the framework of discrete and continuous time Markov chain models.
# VI - CONCLUSIONS

In this paper we have presented a survey of exact results concerning networks of queues which are applicable to the evaluation of the performance of complex computer systems. A companion paper (Part II) will treat some new results we have obtained concerning approximate solutions based on applying diffusion processes.

The results summarized here include expressions for equilibrium probability distributions for queues with exponential service time distributions or with service time distributions having rational Laplace transforms and specific service disciplines. The routing behaviour of the customers in these networks can be described by arbitrary (but finite) order Markov chains or by semi-Markov processes, and classes of customers possessing distinct statistical behaviour.

For networks of queues for which equilibrium probability distributions are unavailable, we have presented work-rate theorems relating the utilisation factors of the different service stations. The networks for which these results are given (general service time distributions at the different service stations and routing described by a first order Markov chain) have every chance of not being solved exactly in the future, because special instances have been examined with very limited success since the inception of queueing theory. Therefore in any application, such models will have to be analyzed via a Monte-Carlo simulation; the work-rate theorems are important in this respect since they allow the deduction of all work-rates from measurements of only one of them. They can be also useful in choosing best estimators for a given quantity. Several interesting problems of mathematical nature remain to be solved in this area.

Generalizations of the work-rate theorems to several classes of customers and to arbitrary order Markov chain representations of transition probabilities would be useful.
Also one might ask whether analogous theorems for eqilibrium proba-
bilities might be established.

The most interesting direction for further research lies probably
in the study of approximate (diffusion or iterative) methods for solving gene-
ral classes of models. Finally studies related to the optimal and adaptative
control of models of multiprogramming systems [29] will provide both stimulating
theoretical work and practical applications to the design of self-regulating
operating systems.
# APPENDIX

The purpose of this section is to provide a brief introduction to Coxian or almost general probability distributions, that is those having rational Laplace transform. The presentation given here stresses the intuitive aspects.

Consider the network presented on Figure 4, and resume that between points A and B a single customer is present at a time; the time spent by the customer in this network will correspond to the realization of a random variable whose distribution is Coxian. The customer entering at point A either immediately leaves the system from B with probability (1 - b₀) or enters into a first stage with probability b₀, where it will remain for a time which is a realization of a random variable τ₁ exponentially distributed with parameter λ₁; In general, after residing in the i-th stage (1 ≤ i ≤ n - 1) the customer will either proceed to the (i + 1) - th stage with probability bᵢ or leave through B with probability (1 - bᵢ); the time spent in stage i by the customer is exponentially distributed with parameter λᵢ.

Let f(t) be the probability density function for the time τ spent by a customer in traversing the network of Figure 4 from A to B and let f*(s) be its Laplace-Stieltjes transform :

$$f^*(s) = \int_0^\infty e^{-st} f(t) dt$$

Nothing that with probability (1 - b₀), the random variable τ has value zero, and that with probability b₀ it is the sum of a random number of exponential random variables, we have

$$f^*(s) = (1 - b_0) + \sum_{i=1}^{n} (1 - b_i) a_i \prod_{j=1}^{i} \frac{\lambda_j}{s + \lambda_j}$$

where

$$a_i = b_0 b_1 \cdots b_{i-1}, \quad 1 \le i \le n$$
Also

$$E \{\tau\} = \sum_{i=1}^{n} \frac{a_i}{\lambda_i}$$

and the variance of τ is

$$\mathrm{Var}(\tau) = \sum_{i=1}^{n} \frac{a_i}{\lambda_i^2}$$

The class of density functions whose Laplace-Stetjes transform is of this form contains both hypoexponential and hyperexponential densities; in fact it contains all densities whose transform is a rational function of s and is closed under addition. Therefore it contains, in particular, the linear combinations of Erlang densities which have been used in the approximation results concerning work-rates presented in Section III.
<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>

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

REFERENCES

1. J.R. JACKSON, "Jobshop-Like Queueing Systems", Management Science 10, 131-142 (1963).

2. F. BASKETT, M. CHANDY, R. MUNTZ, J. PALACIOS, "Open, Closed and Mixed Networks of Queues with Different Classes of Customers", to appear in JACM.

3. D.P. GAVER, "Probability Models for Multiprogramming Computer Systems", JACM 14, 423-438 (1967).

4. D.P. GAVER, G.S. SHEDLER, "Processor Utilization in Multiprogramming Systems Via Diffusion Approximations", Operations Research 21, 569-576 (1973).

5. H. KOBAYASHI, "Application of the Diffusion Approximation to Queueing Networks: Part I - Equilibrium Queue Distributions", JACM 21, 2, 316-328 (April 1974).

6. E. GELENBE, "On approximate Computer System Models", to appear in JACM.

7. E. GELENBE, "A non-Markovian Diffusion Model and its Application to the Approximation of Queueing and Computer System Behaviour", Research Report 74-1, Chaire de Systèmes Informatiques, Université de Liège, Belgium (1974).

8. M. REISER, H. KOBAYASHI, "Accuracy of the Diffusion Approximation for Some Queueing Systems", IBM J.Res. Develop. 18, 2, 110-124 (March 1974).

9. M. BADEL, A.V.Y. SHUM, "Accuracy of a Diffusion Approximation Method for Computing Work-Rates in Multiprogramming Systems", IRIA Research Report (1975).

10. M. CHANDY, U. HERZOG, L. WOO, "Approximate Analysis of General Queueing Networks", IBM Research Report RC 4931 (July 1974).

11. P.J. COURTOIS, "On the Near Complete Decomposability of Networks of Queues and of Stochastic Models of Multi-programming Systems", Carnegie-Mellon University, Computer Science Department, Research Report (Nov. 1971).

12. B. AVI-ITZHAK, P. HEYMAN, "Approximate Models of Multi-programming Computer Systems", Operations Research, 21, 1212-1230 (1973).
13. M. REISER, H. KOBAYASHI, "Blocking in a Queueing Network with Two Exponential Servers", IBM Research Report RJ 1360 (March 1974).

14. D. POTIER, G. PUJOLLE, "Limited Capacity Queueing Networks with Applications to Computer Systems", IRIA Research Report (Jan. 1975).

15. A. CHANG, S.S. LAVENBERG, "Work-rates in Closed Queueing Networks with General Independent Servers", IBM Research Report RJ 989 (1972).

16. S.S. LAVENBERG, I.L. TRAIGER, A. CHANG, "Bounds on Work-Rates for Closed Queueing Networks with Non-Exponential Stages", IBM Research Report RJ 1182 (March 1973).

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

18. J. COHEN, "The Single Server Queue", North-Holland, Amsterdam (1969).

19. W.J. GORDON, G.F. NEWELL, "Closed Queueing Systems with Exponential Servers", Opns. Res. 15, 254-265 (1967).

20. R.A. HOWARD, "Dynamic Probabilistic Systems, Vol. I and II" John Wiley, New York, 1973.

21. J.P. BUZEN, "Computational Algorithms for Closed Queueing Networks with Exponential Servers", Comm. ACM 16, 527-531 (1973).

22. D.R. COX, "A Use of Complex Probabilities in the Theory of Stochastic Processes", Proc. Cambridge Philosophical Society 51, 2, 313-319. (April 1955)

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

24. G.F. NEWELL, "Applications of Queueing Theory", Chapman and Hall, Ltd., London, 1971.

25. J.P. BUZEN, "Queueing Network Models of Multiprogramming", Ph. D. Thesis, Harvard University (1971).

26. E. GELENBE, "Modèles de Systèmes Informatiques; Thèse de Doctorat d'Etat, Université Paris VI (1973).

27. A. BRANDWAJN, J. BUZEN, E. GELENBE, D. POTIER, "A Model of Performance for Virtual Memory Systems", Proc. ACM-SIGMETRICS Symposium, Montreal, September 1974.
28. R.R. MUNTZ, "Analytical Modelling of Interactive Systems," to appear in *Proceedings of the IEEE*, Special Issue on Interactive Systems, June 1975.

29. M. BADEL, E. GELENBE, J. LEROUDIER, D. POTIER, "Adaptive Optimization of a Virtual Memory System," to appear in *Proceedings of the IEEE*, Special Issue on Interactive Systems, June 1975.