RIA

laboria

laboratoire de recherche
en informatique
et automatique

APPLICATIONS OF SOME
MARKOV CHAINS RESULTS
TO COMPUTER
SYSTEMS MODELLING

Guy PUJOLLE

Rapport de Recherche N° 289

Avril 1978

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
APPLICATIONS OF SOME MARKOV CHAINS RESULTS TO COMPUTER
SYSTEMS MODELLING

Guy Pujolle

IRIA/LABORIA

Résumé :

La connaissance des conditions de stabilité est indispensable dans l'étude de tout système. C'est
dans ce but que nous développons ici, les conditions de stabilité de différents systèmes de files
d'attente par l'intermédiaire de résultats obtenus sur les chaînes de Markov.

Le résultat principal de la première partie est l'obtention de la condition de stabilité d'une file GI/
G/M la plus générale possible : les distributions des temps de service peuvent être différentes à cha-
que serveur, et dépendre de l'état du système.

Ensuite, les conditions de stabilité sont formulées pour :

- des réseaux généraux,

- des files d'attente avec un temps de séjour maximal,

- des files d'attente avec blocage,

- des files d'attente avec arrivées ou départs en groupe.

Des applications à des systèmes informatiques sont données en parallèle.

Dans la dernière partie, enfin, nous présentons une application plus spécifique : les conditions de stabilité d'un canal radio (ALOHA) lorsqu'il y a plusieurs fréquences disponibles.

Abstract :

In the first section we give and develop results on the ergodicity condition of a queue with state-dependent service times. The main result is the condition of stability of a GI/G/M queue with M different servers with state-dependent service times. Then we apply results of the first section to
- the stability condition of general queueing networks (BCMP networks are included),

- time-out problems,

- queues with blocking,

- queues with batch arrivals or services.

Applications to computer system modelling are given. In the last section we present a more speci-
fic application, namely the stability of a packet switching broadcast channel (slotted ALOHA)
when there are several available frequencies.
# 1 - INTRODUCTION

The departure of our study comes from the question : under what conditions a computer system such as an operating system, a packet switching network a disk..... is stable ? A practical approach is to have a mathematical model often expressed by queueing theory or Markov chain theory. By stability we mean that there exists a probability distribution of the state, independent of time which has elapsed from the beginning of the process. In a queueing network which can be represented by an aperiodic and irreducible Markov chain, this notion of stability is equivalent to the notion of ergodicity given by Feller [1]. As powerfull results exists on ergodicity condition of aperiodic and irreducible Markov chain, the purpose of the first section is to improve these results to obtain simple conditions adapted to computer system modelling ( for example queues with state dependent service rates).

Next, we present some applications. Particularly, the stability of a packet switching broadcast channel when there are several available frequencies, is studied.

# 2 - ERGODICITY CONDITIONS OF A QUEUE WITH STATE-DEPENDENT SERVICE TIMES

We denote the set of all non-negative integers by $N$. Unless otherwise specified, $n$ ranges over $N$.

We denote the set of all reals by $R$, and the positive reals by $R_+$. Let $(E, \mathfrak{F})$ be a measurable space and let $(\Omega, \mathcal{A}) = (E, \mathfrak{F})^N$ be the trajectories space. Let $\{X_n\}$ be a Markov chain on $(\Omega, \mathcal{A})$. If $E$ is countable, then sufficient conditions exist for the chain to be ergodic : Foster's theorems [2], extended by Pakes [3]. Here, we are interested in the case where $E$ is a continuous state space. Ergodicity conditions of such Markov chains easily find applications in queueing theory.

The formulation of stability conditions of a queue with state dependent service time is simple and very comprehensible : under heavy load, the rate of service is greater than the rate of arrivals. However the proof of this assertion is very complicated and we need the theory of Markov chain on a continuous state space (Revuz [19]).
Let $P = \{P(x,A) = \text{Prob.}(X_{n+1} \in A | X_n = x)\}$ be a function on $(E, \mathfrak{F})$ such that:
- $P(x, \cdot, \cdot)$ is a probability measure on $\mathfrak{F}$ for each $x \in E$
- $P(\cdot, A)$ is $\mathfrak{F}$ measurable for each $A \in \mathfrak{F}$

$P(x, A)$ is called a transition probability function. The iterates $P^n(x, A) = P(X_n \in A | X_0 = x)$ of $P(x, A)$, which are also transition probability functions are defined inductively by setting $P^0(x, A) = I_A(x)$, where $I_A(x)$ denotes the indicator function of the set $A$, and

$$P^{n+1}(x, A) = \int P^n(x, dy)P(y, A)$$

for each $x \in E$, $A \in \mathfrak{F}$.

Throughout this paper, we shall assume that $E$ is $R_+^K$, $K \in \mathbb{N}$, (results will be also true if $E$ is a Banach space) and $\{X_n\}$ is an *aperiodic* and *irreducible* Markov chain with transition function $P$. We assume $P$ compatible with the structure of $E$.

When $E=N$ we have the following theorem due to Pakes [3].

**Theorem 1** : Let $\gamma_i = E[X_{n+1} - X_n/X_n = i] \quad i \in N$; if $|\gamma_i| < +\infty$ for all $i$ and if $\limsup_{i \to \infty} \gamma_i < 0$ in an irreducible and aperiodic Markov chain, then it is ergodic.

For a finite-dimensional Banach space (complete normed vector space), in particular for $E = R_+^K$ we have :

**Theorem 2** (Tweedie)[4] : If $P(x, \cdot)$ is strongly continuous then a sufficient condition for ergodicity is the existence of constants $\alpha, C$ such that for all $x$ with $||x|| > \alpha$, $\gamma_x \le -C$ and for all $x$ with $||x|| \le \alpha$, $\gamma_x$ is bounded above with $\gamma_x = E\{||X_{n+1}|| - ||X_n||/X_n = x\}$.
As the condition "$P(x, .)$ is strongly continuous", is automatically satisfied for a Banach space and an irreducible $X_n$ we may rewrite this last theorem as follows:

**Corollary 3** : If E is a finite-dimensional Banach space, the Markov chain $X_n$ is ergodic if $\gamma_X$ is bounded above and $\limsup \gamma_X < 0$. $$ \|x\| \to \infty \gamma_X $$

Let B be the set of the transition probability functions:

$$ P(x, A) = \int_A f(x, x_1, \dots, x_K) \prod_{i=1}^K \alpha_i(dx_i) $$

where $\alpha_i$ are distribution functions and f is a bounded non negative function.

For these transition probability functions the necessary condition given by Tweedie [4] is verified : there exists a compact K such that $R(x, K) = \sum_{n=1}^{\infty} n K P^n(x, K)$ is bounded for all $x \in K$, and

$A^n(x, K) = P(X_n \in K, X_s \notin A, s = 1, \dots, n-1/X_0 = x)$. This follows from Theorem 7 of Tweedie [5] and the form of the functions of the set B. We then have :

**Theorem 4** : For the set B of transition probability functions on a finite dimensional Banach space, the Markov chain $X_n$ is ergodic, if and only if, $\gamma_X$ is bounded above and $\limsup \gamma_X < 0$. $$ \|x\| \to \infty \gamma_X $$

Now we prove a general theorem on the ergodicity of a GI/G/M queue with M different servers with state-dependent service times. The special case of one server in discrete time has been already proved by Callahan [6] using Theorem 1.

Consider a FIFO queue with M different servers. Denote $S^{(i)}(x)$ the service time of server i when the unfinished work equals x. For each

i=1,...,M and for each $x \in R_+$, $S^{(i)}(x)$ is a non negative random variable with distribution function $\beta_i(x)$. Moreover, we assume that for each i=1,...,M, $S^{(i)}(x)$ are independent random variables. In the sequel, to simplify the notation, the argument of $S^{(i)}$ can be a vector, but only the i-th component affects the value of $S^{(i)}$.
We also assume that interarrival times are independent and identically distributed. Let $T$ be the random variable describing the time between two arrivals of distribution function $\alpha$. Let $S_n^{(i)}(x)$ and $T_n$ be a representation of random variable $S_n^{(i)}(x)$ and $T$. $S_n^{(i)}(x)$ is the service time of the $n$-th customer, if he enters server $i$ and he has found an unfinished work equal to $x$, and $T_n$ is the interarrival time after customer $n$. We assume that :

$$ (3) \quad 0 < E[S_n^{(i)}(x)] < +\infty \quad \text{for each } x \text{ and each } i. $$

When there are more than $M$ customers in the system or when the unfinished work becomes large then all servers are busy. When this is true, we shall use $R(x)$ to denote the following quantity :

$$ R(x) = \frac{1}{\sum_{i=1}^{M} \left[ S_n^{(i)}(x) \right]^{-1}}. $$

Always under the assumption that $x$ is large, $R(x)$ can be interpreted as the time between service initiations, when the unfinished work is $x$. The argument $x$ is a vector belonging to $R_+^M$.

Let $\| \|_+$ define any norm on $R_+^M$ (all the norms are equivalent on a finite dimensional Banach space).

**Theorem 5** : The following two propositions are equivalent :

(4) 
$$ \begin{cases} 1 - \limsup_{\|x\| \to \infty} E[R(x)] < E(T) \\ \|x\| \to \infty \end{cases} $$

2. The queue considered is ergodic (stable).

This theorem translated in plain terms states that when the unfinished work goes to the infinity, the expected time between service initiations must be less than the expected time between two arrivals. We give the proof in the appendix.
**REMARK** : If all the servers are identical, $R(x)=S(x)/M$ when $x$ is large and the following condition of ergodicity holds:

$$ (5) \quad \limsup_{\|x\| \to \infty} \frac{1}{M} E[S(x)] < E(T) $$

and when the service time does not depend on the total unfinished work we find again the condition obtained by Kiefer and Wolfowitz [14] :

$$ E[S] < M E(T) $$

When M equals 1 we obtain :

**Corollary 6** : A single server queue with a state-dependent service time is ergodic if and only if

$$ (6) \quad \limsup_{x \to \infty} E[S(x)] < E(T) $$

Theorem 5 may be extended as follows. (The proof is not given but it is on the same order of complexity that theorem 5, but with complex notations).

1. We can assume that interarrival times in the system depend on virtual unfinished work of customers $T(x)$, and $O \subset E[T(x)] \subset +\infty$ for each $x$.

2. We can have several classes of customers: J classes with various priorities. Denote $S_i^j(x)$ the service time at the i-th service of a class-j customer. We shall assume that an arriving customer has the probability $p_j$ to be of class j, and $\sum_{j=1}^{J} p_j = 1$.

With these extensions the ergodicity condition of the queue becomes:

$$ (7) \quad \limsup_{\|x\| \to \infty} E \left\{ \frac{1}{\sum_{i=1}^{M} \sum_{j=1}^{J} \frac{p_j}{S_i^j(x)}} \right\} < \limsup_{\|x\| \to \infty} E[T(x)], $$

if $E[S_i^j(x)] < +\infty$ for all $i, j$ and $x$.
In Theorem 5 we have a limit on the unfinished work x. Now, we consider a queue with a state dependent service rate $\mu_i(n)$, $n \in N$ for the server i, $i=1,...,M$. The argument of $\mu_i$ represents the total number of customers in the queue. When $n$ goes to the infinity, the unfinished work of each server becomes infinite.

$$ \text{Therefore we have } \limsup_{x \to \infty} E[R(x)] = \limsup_{n \to \infty} \frac{1}{\sum \mu_i(n)}. $$

From Theorem 5 it follows:

**Theorem 7** : A queue with a state dependent service rate is ergodic if and only if

$$ (8) \quad \limsup_{n \to \infty} \left\{ \frac{1}{\sum_{i=1}^{M} \mu_i(n)} \right\} < E[T]. $$

For a single server queue we have : $\limsup_{n \to \infty} [1/\mu(n)] < E[T]$.

From the relation $\limsup_{n \to \infty} (1/\mu) \le 1/\liminf_{n \to \infty} \mu$, we obtain the following

sufficient condition: a single server queue is stable if $\lambda < \liminf_{n \to \infty} \mu(n)$.

We now apply Theorem 7 to queueing systems (extensions with several services and several classes of customers are easy).
# 3 - APPLICATIONS

## 3.1 - Stability conditions in a general queueing network

Theorem 7 provides a convenient way of examining the stability conditions of a general queueing system with state dependent service rates; Baskett, Chandy, Muntz and Palacios (BCMP) networks [15], are included in the general case.

Let $\mu_i(n)$ be the service rate when there are $n$ customers at the service center $i$, $1 < i < K$.

**Corollary 8:** The queueing system is stable if and only if for all $i$, $1 < i < K$

$$ (9) \quad \limsup_{n \to \infty} \frac{1}{\mu_i(n)} < \frac{1}{\lambda} = E[T]. $$

**Remark:** -It is sufficient that there exists an $i$ such that the series $\mu_i(n)$ possesses an adherence value equal to 0 for the system is always unstable.

-BCMP networks stability can be now treated when there are state dependent service rates.

**Example:** Consider the model described in [18] of a virtual memory operating system. This model is a central server system and it can be studied taking an equivalent queue with state dependent service rates.

We know [7] that there is an optimum for the multiprogramming degree and if there are too many customers a thrashing phenomenon happens and the service rate goes to zero. Thus, from corollary 8 the system is unstable. It is necessary to control the system for the multiprogramming degree does not overtake a certain value.

## 3.2 - Problem with time-outs (or maximum sojourn times)

We recall the usual notations: $\lambda$ and $\mu$ interarrival and service rates. Let $a_n$ denote the arrival time in the queue of customer $n$. Assume that a time $T_n$ is assigned to customer $n$, in such a way that if the customer is not out of the system at time $a_n + T_n$, then he is rejected out of the queue.

Assume the sequence $(T_n, n \in N)$ of independent and identically distributed random variables. Denote $Q$ the following probability:

$$ Q = \text{Prob.}\{T_n = +\infty\} \quad . \quad Q \text{ is the proportion of customers without a finite time-out.} $$

We have:

**Corollary 9:** The queue is ergodic if and only if $Q\lambda < \mu$.
**Proof :** When the unfinished work tends towards infinity, the customers which have a finite time-out, have a service time equal to zero. It follows from the law of large number that the mean service time is $Q/\mu$. The proof then follows from Theorem 5.

Q.E.D.

A similar result has been proved in Charlot and Pujolle [8]. A necessary condition and a sufficient condition are given in the general case (even if $W_n$ is not an aperiodic and irreducible Markov chain).

**Consequence :**

- If all the customers have finite time-outs, then $Q = 0$ and the queue is always stable.

- If all the customers have infinite time-outs, then $Q = 1$ and we find again the classical conditions $\lambda < \mu$ for stability.

**Example:** In a packet switching communication network, time-out mechanisms are used to avoid either congestion of nodes, or deadlocks. Packets which stay for too long in the network are rejected and this allows the other packets to proceed more rapidly. Let us assume that a packet entering the station has a probability $P$ to be rejected by the time-out mechanism. Rejected packets feed-back into the system, with external arrivals. The new input rate is $\lambda/(1-P)$. Let $Q = 1-P$. We can associate an infinite time-out at customers which are not rejected without changed the state of the system. Let us assume that the new sequence $(T_n, n \in N)$ are independent and identically distributed random variables. From Corollary 9 the queue is stable if $Q\lambda/(1-P) < \mu$ or $\lambda < \mu$. This is the result obtained with an infinite time-out.

Simulations show that the condition on the sequence $T_n$ is accurate only if the rejection probability is weak (less than 0.1). This proves that the introduction of a large time-out in a packet switching network does not change the throughput but avoid deadlock and can cure the congestion.

### 3.3 - Queue with blocking

Consider an open queueing network consisting of an input queue of unlimited capacity in series with a subnetwork of queue having finite capacity constraints. The subnetwork can be quite complex in structure. When a customer finishes his service and cannot continue because of finite capacity constraints, he blocks the service of the queue till a place becomes free in the following queue. Let $S$ and $B$ be random variables representing a service time and a blocking time of the input queue when there is always at least one customer in this queue. Let the time
between successive arrivals at the queue be a random variable T, and let $W_n$ be the waiting time in the input queue of the n-th customer to enter service. $W_n$ is given by the recursive relation : $W_n = \max(0, W_{n-1} + S + B - T)$

The sequence {$W_n$} is a Markov chain defined on the Banach space $R_+$.
Assume {$W_n$} irreducible and aperiodic (this is realized except for deterministic service times).

Applying the same method as in Theorem 5 we obtain :

**Theorem 10** : The system described above is ergodic if and only if

$$E[S + B] < E(T)$$

This is an extension of Hildebrand' results [20].

Let $\hat{\lambda}$ be the output rate of the system when there is at most one customer in the input queue ; we have $\hat{\lambda} = \frac{1}{E[S + B]}$.

Therefore we have :

**Corollary 11** : The system is ergodic if and only if $\lambda < \hat{\lambda}$.

If all the service time distributions of the queueing network have a rational Laplace-Stieljes transform, {$W_n$} is an irreducible and aperiodic Markov chain.

We find again a result of Lavenberg [9].

**Example :**

Consider the system of two tandem queues, with service times exponentially distributed with coefficient $\mu_1$ and $\mu_2(j)$ where j is the number of customers in station 2. The second station is limited to N customers.

This network can represent a path in a computer network : two hosts with an intermediate node as the second station.

Corollary 11 allows to compute the maximal traffic rate on this path : $\hat{\lambda} = \mu_1(1 - p_N)$, where $p_N$ is the probability to have N customers in the second queue. We can compute $p_N$ by the following method. The behaviour of the second queue is exactly the same if 1-the capacity is N+1, 2-when a customer cannot enter the second station, it comes back in the first service and repeats it again*(this happens because of the non memory of exponential service). So the second station is an M/M/1/N queue with interarrival rate $\mu_1$ and service rate $\mu_2(j)$.

<footnote>*This last policy is again identical to the following one: 1- the capacity of the second queue is N+1, 2- when the capacity of N+1 is reached the first server is stopped. The Chapman Kolmogorov equations of this system are exactly identical to this of the firstblocking case (considering in this last case that the customer blocked at the end of his service is counted in the second queue.</footnote>
$$ \text{Therefore} \quad \rho_N = \frac{\sum_{j=1}^{N} \rho_2(j)}{1 + \rho_2(1) + \rho_2(1) \rho_2(2) + \dots + \rho_2(1) \rho_2(2) + \dots + \sum_{j=1}^{N} \rho_2(j)} \quad \text{with } \rho_2(j) = \frac{\mu_1}{\mu_2(j)} $$

and

$$ \hat{\lambda} = \mu_1 \frac{1 + \frac{\mu_1}{\mu_2(1)} + \dots + \frac{(\mu_1)^{N-1}}{\mu_2(1) \dots \mu_2(N)}}{1 + \frac{\mu_1}{\mu_2(1)} + \dots + \frac{(\mu_1)^N}{\mu_2(1) \dots \mu_2(N)}} $$

If $\mu_1 = 1$ and $\mu_2(j) = j$, we obtain $\hat{\lambda} = \frac{1}{2}, \frac{4}{5}, \frac{15}{16}, \frac{64}{65}$ for $M = 1, 2, 3, 4$.

For $\mu_2(j) = \mu_2$ this result has been obtained by other methods [10], [11].

## 3.4 - Application to batch service and batch arrival

### 3.4.1 - Batch service

Assume a GI/G/1 queue with batch service. Now, let $w_n$ be the waiting time of the first customer to be served in the n-th batch. Let $x_n$ denote this customer, $T_n$ the interarrival time after n., $v_n$ the number of customers served in this batch and $S_n$ the service time of n-th group. Set

$A_n = T_n + \dots + T_{n-1} + v_{n-1}$ and let $S$ and $A$ be the random variables representing $S_n$ and $A_n$. We have :

$$ w_{n+1} = \max(0, w_n - A_n + S_n) $$

if we assume that for the n-th batch there are effectively at least $\bar{v}_n$ customers in the queue. If this assumption is not true, then in place of $w_n - A_n$ we must substitute the first negative value in the sequence

$$ w_n - (T_{n-1} + \dots + T_{n-k}) \quad k = 0, 1, \dots, v_n-1 $$
The waiting time of the first customer of each batch is a Markov chain.
We can also assume that the service time of a batch is dependent of the unfinished
work x encountered by this first customer. We assume in this case that S(x) is a
random variable for each x.

**Theorem 12** : The state-dependent batch service time system is ergodic if and only if

$$
E[S(x)] < + \infty \quad \text{for each } x
$$

$$
\limsup_{x \to \infty} E[S(x)] < E(A) = E(v_n) E(T).
$$

The proof is identical to that of theorem 5.

3.4.2.- Batch arrival

In this section we denote by $w_n$ the waiting time of the first customer of
the n-th arriving group and T the random variable of interarrival times. $v_n$ is
now the number of arrivals in the group n. Let $S_n$, n $\in$ N, be the time spent
servicing the n-th successive group of customers, and S the random variable
representing these times. Then

$$
w_{n+1} = \max(0, w_n + S_n - T_n)
$$

is a Markov chain.

**Theorem 13** : The batch arrival system is stable if and only if :

$$
E[S] < + \infty
$$

$$
E[S] < E(T)
$$
# 4 - APPLICATION TO THE STABILITY OF A PACKET SWITCHING BROADCAST CHANNEL

We follow the notation of Fayolle-Gelenbe-Labetoulle [12]. We consider a large set of terminals communicating over a single radio channel. We assume the time divided into "slots". Packet transmission is synchronized and the transmission time equals a slot. A terminal which transmission is unsuccessful is said to be blocked; it has to repeat the transmission until it succeeds. We assume that the set of terminals is infinite and we say that the broadcast channel is unstable if the number of blocked terminals becomes infinite with probability one as time goes to infinity. Let $N_\ell$, $X_\ell$, $Y_\ell$ be the following random variables :

$N_\ell$ the number of blocked terminals at the beginning of the $\ell$-th slot,

$X_\ell$ the number of packets transmitted from the set of active terminals,

$Y_\ell$ the number of blocked terminals transmitting during the $\ell$-th slot.

Denote by $f$ the probability that a blocked terminal transmits during a slot.

$$ \text{Let } C_i = \text{Prob}\{X_\ell = i\} $$

$$ g_i(n) = \text{Prob}\{Y_\ell = i | N_\ell = n\} = \binom{n}{i} f^i (1-f)^{n-i} $$

## 4.1 - k Aloha

We consider that a packet is successfully transmitted only if its transmission does not overlap in time with the transmission of more that k-1 another packets, otherwise, all packets being simultaneously transmitted are lost. The case usually treated is k=1 [16].

### 4.1.1 - k-Aloha with or without retransmission control policy

If $f$ is a function of the number of blocked terminals, we have a retransmission control policy, otherwise we have not.

The process $N_\ell$ is a Markov chain on the positive integers $N$. We can apply Theorem 1 to study the ergodicity of this system.
**Theorem 14** : If the expected arrival rate $\lambda = \sum_{j=1}^{\infty} j C_j$ of active packets is less than $\limsup_{i \to \infty} d_k(i)$, where :

$$d_k(i) = C_0 \sum_{j=0}^{k} j g_j(i) + C_1 \sum_{j=0}^{k-1} (j+1) g_j(i) + \dots + C_{k-1} [(k-1) g_0(i) + k g_1(i)] + k C_k g_0(i), \text{ then the broadcast channel is stable.}$$

$$\textbf{Proof :} \quad \gamma_i = E\{N_{n+1} - N_n / N_n = i\} = \sum_{j=k+1}^{\infty} (i+j) C_j + (i+k) C_k(1-g_0(i)) \\ + i C_k g_0(i) + (i+k-1) C_{k-1}[1-g_0(i)-g_1(i)] + i C_{k-1} g_0(i) + (i-1) C_{k-1} g_1(i) \\ + \dots + i C_0(1-g_0(i)-g_1(i)-\dots-g_k(i)) + i C_0 g_0(i) + (i-1) C_0 g_1(i) + \dots \\ + (i-k) C_0 g_k(i) - i$$

$$\text{We obtain } \gamma_i = \lambda - d_k(i).$$

It is easy to verify that $|\gamma_i| < +\infty$. So from Theorem 1, the chain is ergodic if

$$\lambda < \limsup_{i \to \infty} d_k(i).$$

**Remark :**

If $f$ is independent of $n$ and $k < +\infty$, then $\limsup_{i \to \infty} d_k(i) = 0$. Therefore, when there is no retransmission control policy, the broadcast channel is unstable. This extends the result obtained for $k=1$.

Let $k \binom{D}{n}(\ell)$ be the conditional throughput as defined in [12]. It is the expected value of the number of successful transmissions during the $\ell$-th slot, conditional on there being $n$ blocked terminals at the beginning of that slot. Here we have :

$$k \binom{D}{n}(\ell) = \sum_{m=0}^{k} \sum_{j=0}^{r} (j+m) C_m^{(n)} [f(n)]^j [1-f(n)]^{n-j}, \quad \text{where } r = \min(k-m, n).$$

The right member is obviously independent of $\ell$. The quantity $k \binom{D}{n}$ may be maximized with respect to $f$. If the arrival process is poisson, then we shall set the maximum value of $k \binom{D}{n}$ equals to $d$.

Here if $k=1$, then $d=1/e$ and if $k=2$, then $d=0.83$.
k Aloha with a threshold policy or with a mixed policy

If the number of blocked terminals exceeds $O$, the threshold, then an active terminal that wishes to initiate the transmission of a packet is not allowed to transmit and joins a set of impeded terminals. As soon as the number of blocked terminals decreases below $O$ an impeded terminal joins the blocked set. With this threshold control policy we denote by $N_\ell$ the number of blocked plus impeded terminals at the beginning of the $\ell$-th slot. We assume that $k \le O$.

**Theorem 15** : If the expected arrival rate $\lambda = \sum_{i=1}^{\infty} i C_i$ of active packets is less than $\sum_{j=1}^{k} j g_j(O)$ then the broadcast channel is stable.

**Proof** : Consider $i \ge O$. We have :

$$ 
\begin{aligned}
\gamma_i &= E\{N_{n+1} - N_n / N_n = i\} = \sum_{j=0}^{\infty} (i+j) C_j (1-g_1(O) - g_2(O) - \dots - g_k(O)) \\
&\quad + \sum_{j=0}^{\infty} (i+j-1) C_j g_1(O) + \dots + \sum_{j=0}^{\infty} (i+j-\ell) C_j g_\ell(O) + \dots \\
&\quad + \sum_{j=0}^{\infty} (i+j-k) C_j g_k(O) - i \\
&= \lambda - g_1(O) - 2g_2(O) - \dots - kg_k(O)
\end{aligned}
$$

It is easy to see that $|\gamma_i| < +\infty$. The proof then follows from Theorem 1.

For $k=1$, we find again the condition of [12].

## 4.2 - Aloha with several frequencies

It is possible to elaborate more sophisticated systems than the preceding ones with the possibility to have several frequencies. See for example Spaniol [13]. Here we are going to assume that we can use 2 frequencies. In a first case we assume that the second frequency is only reserved to retransmissions.
### 4.2.1 - Aloha with two specialized frequencies

**Theorem 16** : The broadcast channel with a frequency reserved for blocked terminals is stable if the expected arrival rate $\lambda = \sum_{j=1}^{\infty} j C_j$ of active packet satisfies the following condition:

$$ \lambda - C_1 < \limsup_{i \to \infty} [g_1(i)] $$

**Proof** : It is an easy application of Theorem 1.

**Remark** :

If there is no control policy the channel is unstable as $\limsup_{i \to \infty} g_1(i) = 0$ and $\lambda - C_1 > 0$.

The value of the maximum throughput is easily obtained: $d = C_1 + e^{-1}$.

If the arrival process is Poisson $d = \lambda e^{-\lambda} + e^{-1}$ and the maximum is $d* = 0.71$.
We obtain almost the double of the case k=1 with just one frequency.

If we adopt the threshold control policy we obtain the following theorem:

**Theorem 17** : The broadcast channel is stable if

$$ \lambda - C_1 \le g_1(0) $$

### 4.2.2 - Aloha with 2 frequencies

We assume in this case that a terminal transmits with one or the other frequency with probability 0.5. A packet is successfully transmitted only if its transmission does not overlap in time with another transmission on the same frequency. We obtain the following theorem:

**Theorem 18** : The broadcast channel with two frequencies is stable if :

$$ \lambda < \limsup_{i \to \infty} \sum_{j=1}^{\infty} \frac{2j}{2^j} \sum_{\ell=0}^{j} C_{\ell} g_{j-\ell}(i). $$

**Proof** : The proof follows from Theorem 1.
**Remark:** If there is no retransmission control policy the channel is unstable.

It is possible to compute the maximum throughput of the channel with a digital computer. We have done so assuming Poisson arrival stream. The maximum throughput was $d = 0.53$. It was already found by Metzner [17].

We have found that the maximum value of the throughput is 0.83 for k-Aloha with $k=2$, 0.71 for Aloha with two specialized frequencies and 0.53 for Aloha with two frequencies. Therefore, as k-Aloha is certainly difficult to realize for technical reason, it is preferable to use two specialized frequencies.

With a threshold control policy we obtain the theorem :

**Theorem 19 :** The broadcast channel is stable if

$$ \lambda < \sum_{j=1}^{\infty} \frac{2j}{2^j} g_j(\alpha) $$

## 5 - CONCLUSION

It is surely possible to extend the basic theorem on Markov chains to have new results. For example it should be interesting to have a sort of a converse of Theorem 1*, i.e. something of the form: the Markov chain is unstable if $\liminf \gamma_i > 0$.

Also, we can obtain other results from theorem 1 to 5. For example, using Pakes theorem, it is possible to study queues with batch arrival and batch service. In order to do so either the batch arrival or the batch service must be exponential.

Applications to computer systems modelling are numerous : disk, queue with service interruptions in a data-base system, protocol in a store and forward packet switching, etc...

<footnote>* When $E = N$ (N is not a Banach space).</footnote>
# Appendix

## Proof of theorem 5

Let $G_M$ be the permutation group of $[1,...,M]$ and $\sigma_k \in G_M$, $k = 1,...,M!$.

For $n \ge 0$, let $W_n$ denote the following process:

$$ (A1) \qquad W_n = (W_n^{\sigma_{kn}(1)}, W_n^{\sigma_{kn}(2)}, \dots, W_n^{\sigma_{kn}(M)}) $$

where $W_n$ is the total unfinished work of the M servers put in ascending order at the time the n-th customer arrives: $W_n \le W_n^{\sigma_{kn}(1)} \le W_n^{\sigma_{kn}(2)} \le \dots \le W_n^{\sigma_{kn}(M)} \in G_M$ gives the number of the corresponding server.

$W_n^{\sigma_{kn}(1)}$ is exactly the unfinished work to do before the customer n enters service.

$$ \text{Let } \bar{1} = (1, 1, \dots, 1) \in \mathbb{R}^M $$

$$ \text{and } \bar{e} = (1, 0, \dots, 0) \in \mathbb{R}^M. $$

Let $x_+ = \max(x, 0)$ and let $f: \mathbb{R}^M \to \mathbb{R}^M$ be the function which arranges the components in ascending order. We have :

$$ (A2) \qquad W_{n+1} = f(W_n + S_n(W_n - T_n)\bar{1}) $$

Effectively the n-th customer will go into the first empty server, namely the one whose unfinished work is $W_n^{\sigma_{kn}(1)}$. The unfinished works to do are then :

$W_n^{\sigma_{kn}(1)} + S_n(W_n^{\sigma_{kn}(2)} - W_n^{\sigma_{kn}(1)})$, $W_n^{\sigma_{kn}(2)}$, $\dots$. When the $(n+1)$-th customer arrives

the unfinished works are :

$$ (A3) \qquad (W_n^{\sigma_{kn}(1)} + S_n(W_n^{\sigma_{kn}(2)} - T_n) + \dots, W_n^{\sigma_{kn}(1)} - T_n) + \dots $$

and the ordered series gives $W_{n+1}^{\sigma_{kn}(2)}$ (A2).
Consider the following norm on $R_+^M$:

$$ \|v\| = \left[ \frac{1}{M} \sum_{i=1}^{M} v_i \right] . \quad \text{where } v_i \text{'s are the components of vector } v.$$

$R_+^M$ together with this norm becomes a Banach space.

$\|W_n\|$ gives the mean of the unfinished work for each server at the time the n-th customer arrives.

From (A2) or (A3) we see that when $\|x\|$ is large (obviously verified if $\|x\| \to \infty$) i.e. $R(x)$ is well defined, then

$$ (A4) \quad E\left( \left\| W_{n+1} \right\| - \left\| W_n \right\| / W_n = x \right) = E\left[ R(x) - T \right] $$

From (A2), $W_{n+1}$ is a Markov chain with a transition function

$$ (A5) \quad P(t; A) = \int_{R_+}^{M} \prod_{i=1}^{M} \beta_i(dx) I_A \left[ f(t + y\bar{e}_i - x\bar{t}) \right] $$

where $I_A$ is the characteristic function of A.

This transition function belongs to the set B on which Theorem 4 gives a necessary and sufficient condition for ergodicity.

Now we prove 1 $\Rightarrow$ 2.

By the definition of the norms $\|W_n\|$ and $\|W_{n-1}\|$ we have

$$ (A6) \quad E\left[ \left\| W_n \right\| - \left\| W_{n-1} \right\| / W_{n-1} = x \right] \le E \sup_{i=1, \dots, M} \left[ S_{n-1}^{(i)}(x) \right] < +\infty $$

From (4) we obtain: $\limsup E[R(x) - T] < 0$, therefore there exists $\|x\| \to \infty$ such that $\forall \|x\| > N_1$, $E[R(x) - T] < -\epsilon$ for an $\epsilon > 0$.
From A2, A3, A4, $\exists N_2$ and $\forall x$ such that $||x|| > N_2$

$$ (A7) \quad E[R(x) - T] + \frac{\epsilon}{2} > E[\|W_n\| - \|W_{n-1}\|/\|W_{n-1}\| = x] $$

For $||x|| > N_3 = \sup (N_1, N_2)$

$$ E[ \|W_n\| - \|W_{n-1}\|/\|W_{n-1}\| = x ] < -\epsilon $$

$$ \text{and} \quad \limsup_{||x|| \to \infty} E[ \|W_n\| - \|W_{n-1}\|/\|W_{n-1}\| = x ] < 0. $$

So, {$W_n$} satisfies the conditions of Theorem 4 and the chain {$W_n$} is ergodic.

2 $\Rightarrow 1$ Now, assume {$W_n$} is ergodic.

It follows from Theorem 4, that $\gamma_x = E[\|W_{n+1}\| - \|W_n\|/\|W_n\| = x]$ satisfies the condition

$$ \limsup_{||x|| \to \infty} \gamma_x < 0. $$

(A8) When $||x|| \to \infty$, then from (A4), $\gamma_x = E[R(x)-T]$. Therefore

$$ \limsup_{||x|| \to \infty} E[R(x)] < E(T) \text{ and the condition 1 is satisfied.} $$
REFERENCES

[1] Feller W. - "Probability theory and its applications" - John Wiley and Sons - New York - 1957.

[2] Foster F.G. - "On stochastic matrices associated with certain processes" - Ann. Math. Statist. 24 - 335-360 - 1953.

[3] Pakes A.G. - "Some conditions for ergodicity and recurrence of Markov chains" - Operations Research 17 - 1058-1061 - 1969.

[4] Tweedie R.L. - "Sufficient conditions for ergodicity and recurrence of Markov chains on a general state space" - Stoch. Proc. and their Appl. 3 - 385-403 - 1975.

[5] Tweedie R.L. - "R - theory for Markov chains on a general state space" - Ann. Prob. 2 - 840-864 - 1974.

[6] Callahan J.R. - "A queue with waiting time dependent service times" - Naval. Res. Logist. Quart. 20 - 321-324 - 1973.

[7] Gelenbe E. - "Modèles de comportement de systèmes informatiques" - Thèse d'Etat - Université de Paris VI - 1973.

[8] Charlot F., Pujolle G. - "Recurrence in single server queues with impatient customers" to appear in Les Annales de l'Institut Henri-Poincaré.

[9] Lavenberg S.S. - "Stability and maximum departure rate of certain open queueing networks having finite capacity constraints" - *IBIl Research Report* RJ 1625 - San Jose - California - 1975.

[10] Neuts M.F. - "Two queues in series with a finite intermediate waiting room" - J. Appl. Prob. 5 - 123 - 1968.

[11] Konheim A.G., Reiser H. - "A queueing model with finite waiting room and blocking" - J.ACM 23 - 2 - 1976.

[12] Fayolle G., Gelenbe E., Labetoulle J. - "Stability and optimal control of the packet switching broadcast channel" - J.ACM 24,3 - 375-386 - 1977.

[13] Spaniol O. - "Analyse von Aloha-netzwerken mit mehreren benutzerkanälen" - Research Report Institut für Informatik der Universität Bonn - 1976.
[14] Kiefer J. and Wolfowitz J.-"On the theory of queues with many servers"
Transactions of the American Mathematics Society-78, 1-18, 1955.

[15] Baskett F., Chandy K.M., Muntz R.R., and Palacios F.G. "Open, closed, and mixed networks of queues with different classes of customers"-J.ACM 22, 248-260, 1975.

[16] Kleinrock L. and Lam S.S. "Packet switching in a slotted satellite channel"
AFIPS Conference Proceedings 42, 703-710, 1973.

[17] Metzner J.J. "On improving utilization in ALOHA networks"-IEEE Trans. on Com. 24, 447-448, 1976.

[18] Brandwajn A., Buzen J., Gelenbe E., Potier D.- A model of performance for virtual memory systems" Proc. ACM-SIGMETRICS Symposium- Montreal- September 1974.

[19] Revuz D., "Markov chains", North-Holland, 1975.

[20] Hildebrand D.K. "On the capacity of tandem server, finite queue, service system" - Operations Research 16, 1, 73-82, 1968.