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

Stability and control
of packet-switching
broadcast channels

Guy Erol Jacques
G.Fayolle, E.Gelenbe, J.Labetoulle

Rapport de Recherche n°116.

Avril 1975.
STABILITY AND CONTROL OF PACKET-SWITCHING
BROADCAST CHANNELS

G. Fayolle*, E. Gelenbe**, J. Labetoulle*

RESUME

Le but de cet article est d'étudier le comportement d'un canal Radio de transmission de paquets de données, du type "ALOHA", utilisé par un ensemble de terminaux pour accéder à un ou à plusieurs ordinateurs partagés. Un modèle mathématique nous permet de mettre en évidence les propriétés principales de ce type de liaison.

Nous commençons par rappeler le caractère fondamentalement instable de ce canal, qu'il soit à source infinie (une infinité de terminaux considérés comme une source unique poissonienne) ou à source finie (nombre fini de terminaux). Nous donnons ensuite un ensemble de théorèmes généraux qui permettent d'établir des relations entre débit instantanné, flux d'entrée, politiques d'admission et de retransmission guarantissant la stabilité du canal. Nous étudions enfin plusieurs politiques de contrôle, ce qui nous permet de démontrer que le débit théorique maximum du canal trouvé par Roberts et Abramson (e<sup>-1</sup>) peut effectivement être atteint.

<footnote>* IRIA-LABORIA</footnote>

<footnote>** Chaire d'Informatique de l'Université de Liège et IRIA-LABORIA.</footnote>
ABSTRACT

In this paper we consider the behaviour of the slotted broadcast channel used by an ensemble of terminals for the transmission of packets of data. A mathematical model is used to prove that the channel is unstable, leading to zero effective throughput, if no control is imposed on the channel behaviour. Two classes of control policies, acting on the input and on retransmissions from blocked terminals, are then analyzed and stability and optimality conditions for the channel with these policies are derived. The theorem on instability of the uncontrolled channel can in fact be considered as being a corollary of the stability theorem for the retransmission control policy. We show that $e^{-1}$ is a lower bound to the maximum achievable throughput with an input control policy. On the other hand, an optimal retransmission control policy must regulate re-transmissions so that the probability of retransmission of an individual blocked terminal is of the form $(1-\lambda)n^{-1}$ in each slot, where n is the total number of blocked terminals. Some simulation results are provided in order to illustrate the effect of this policy.
# 1. INTRODUCTION.

Computer networks using packet-switching techniques have been implemented [1,2,3,4,5,10] in order to allow a large community of communicating users to share and transmit data and to utilize excess computing power which may be available at remote locations in an efficient manner. In this paper, we shall be concerned with packet switching networks using radio channels similar to the ALOHA system [1].

We consider a large set of terminals communicating over a single radio channel in such a way that a packet is successfully transmitted only if its transmission does not overlap in time with the transmission of another packet; otherwise all packets being simultaneously transmitted are lost. A terminal whose transmission is unsuccessful is said to be *blocked*; it has to repeat the transmission until it achieves success. A terminal which is not blocked is either *active* or it is transmitting a packet. The operation of the system is shown schematically in Figure 1 where the different state transitions of a terminal are shown. Since the only means of communication between terminals is the channel itself, it is not easy to schedule transmissions so as to avoid collisions between packets. It is also obvious that a terminal would in no case transmit more than one packet simultaneously.

Various methods for controlling the transmission of packets have been suggested. The simplest is to allow terminals to transmit packets at any instant of time. The second method, known as the *slotted ALOHA* scheme has been shown to increase channel throughput over the first method [6]. Here time is divided into "slots" of equal duration; each slot can accommodate the transmission time of one packet and packets are all of the same length. Packet transmission is synchronized so as to be initiated at the beginning of a slot for any termi-
nal and it terminates at the end of the same slot. Other schemes have been suggested elsewhere [9].

KLEINROCK and LAM [8] have discussed the stability problem of the slotted ALOHA channel. They give qualitative arguments and results based on simulations indicating that the channel becomes saturated if the set of terminals is very large, independently of the arrival rate of packets to the channel, saturation being the phenomenon whereby the number of blocked terminals becomes very (or arbitrarily) large. They also compute the expected time to attain a given level of saturation. In [11] policies designed to optimize the throughput of the channel, defined as the expected number of successful transmissions per slot, are presented.

The purpose of this paper is to give a theoretical treatment of some control policies which can be applied to the broadcast channel in order to stabilize it and to maximize its performance. We first recall the proof of instability in [12] extending it to the finite source model taken in the limit as the total number of terminals becomes very large, and showing that channel instability implies that the equilibrium value of the throughput is zero. Two simple control policies are then presented and necessary and sufficient conditions for stability of the controlled channel are derived. Bounds for the equilibrium value of the channel throughput with these policies are obtained. Finally we give a simple algorithm for the approximate implementation of this policy and exhibit some simulation results showing its performance.
## 2. A MATHEMATICAL MODEL.

A precise definition of stability can only be considered in the context of a model of the behaviour of the broadcast channel. In this section we present a model identical to the one we have considered in an earlier paper [12] except that we shall take into account here both finite and infinite source systems.

Assuming that the slot, and the time necessary to transmit a packet, are of unit length, consider $N(k)$ the number of blocked terminals at the instants $k = 0,1,2,...$ when a slot begins. Let $X_k$ be the number of packets transmitted by the set of active terminals during the k-th slot and denote by $Y_k$ the number of blocked terminals transmitting during the k-th slot. In the infinite source model ($X_k$) is the sequence of independent and identically distributed random variables with common distribution given by

$$ (1) \qquad \mathrm{Pr}(X_k = i) = c_i, \quad i \ge 0 $$

In the *finite source model* assuming that the total number of terminals in the system is $M$, we let the event $(X_k=i/N(k)=j)$ be independent of values of $X_t$ for $t < k$; its probability is given by

$$ (2) \qquad q_j(n) = \mathrm{Pr}(X_k=j/N(k)=n) = \binom{M-n}{j} b^j (1-b)^{M-n-j} $$

for $0 \le j \le M-n$, where $b$ is the probability that any one active terminal transmits a packet during a slot.

For both models we shall denote by $f$ the probability that any one blocked terminal transmits a packet during a slot. We then define

$$ (3) \qquad g_i(n) = \mathrm{Pr}(Y_k = i/N(k)=n) $$
where we assume that the event $(Y_k/N(k))$ is independent of $Y_t$ for $t < k$. Therefore

$$ (4) \qquad g_i(n) = \binom{n}{i} f^i (1-f)^{n-i} $$

and more particularly

$$ (5) \qquad g_0(n) = (1-f)^n, \quad g_1(n) = nf(1-f)^{n-1} $$

**Definition 1.**

The infinite source broadcast channel is *unstable* if for $k \to \infty$ the probability $Pr(N(k) < j) \to 0$ for all finite values of j; otherwise it is *stable*. For the finite source model, the system is unstable if the above condition is verified as we let $M \to \infty$, $b \to 0$, $M.b \to d$, where d is a constant.

The definition given here simply states that instability is verified if (with probability one) the number of blocked terminals becomes infinite as time tends to infinity.

**Theorem 1.**

The broadcast channel is unstable both for the finite and infinite source model.

**Proof.**

Let us first consider the infinite source model. The proof given here is identical to the one we presented in [12]. Let $p_n(k)$ denote the probability that $N(k) = n$. The following transition equation may be written for the infinite source model (1):

<footnote>(1) Equation (6) is valid for all $n \ge 0$ if we adopt the rule that $p_i(k)=0, i<0$.</footnote>
$$ (6) \qquad \begin{aligned} p_n(k+1) = & \sum_{j=2}^{n} p_{n-j}(k) c_j + p_{n+1}(k) g_1(n+1) c_0 \\ & + p_n(k) (1-g_1(n)) c_0 + p_n(k) g_0(n) c_1 \\ & + p_{n-1}(k) (1-g_0(n-1)) c_1 \end{aligned} $$

On the right-hand side of (6), the first term covers the cases where two or more packets have been transmitted by the active terminals during the k-th slot; the second term covers the case in which exactly one blocked terminal has transmitted while no active terminal has done so. Notice that {$N(k); k=0, 1, ...$} is a Markov chain and that it is aperiodic and irreducible. It is ergodic if an invariant probability measure {$p_n; n=0, 1, ...$} exists satisfying (6) such that $p_n \ge 0$ for all n and where $p_n = \lim_{k \to \infty} p_n(k)$. To show that $\lim_{k \to \infty} \text{Pr}(N(k) < j) = 0$ for all finite values of j it suffices that the Markov chain re-presenting the number of blocked terminals be not ergodic. Substituting $p_n$ for $p_n(k)$ and $p_n(k+1)$ in (6) we obtain

$$ (7) \quad p_n = \sum_{j=0}^{n} p_{n-j} c_j + p_{n+1} g_1(n+1) c_0 + p_n(g_0(n) c_1 - g_1(n) c_0) - p_{n-1} g_0(n-1) c_1 $$

Let

$$ (8) \quad S_N = \sum_{n=0}^{N} p_n $$

we then have for any $N \ge 0$,

$$ (9) \quad S_N = p_{N+1} g_1(N+1) c_0 + p_N g_0(N) c_1 + \sum_{n=0}^{N} S_{N-n} c_n $$

or

$$ (10) \quad S_N(1-c_0) = \sum_{n=1}^{N} S_{N-n} c_n + p_{N+1} g_1(N+1) c_0 + p_N g_0(N) c_1 $$
or equivalently

$$ (11) \qquad p_N(1-c_0) \le p_{N+1}g_1(N+1)c_0 + p_N g_0(N)c_1 $$

But then, from (5) and (11) we have

$$ (12) \qquad \frac{p_{N+1}}{p_N} \ge \frac{1 - c_0 - (1-f)^N c_1}{(N+1)f(1-f)^N c_0} $$

for any non-negative integer N. This implies that the ratio $(p_{N+1}/p_N) \to \infty$ as $N \to \infty$, so that the sum $S_\infty$ can only exist if $p_N=0$ for all finite values of N; otherwise $S_\infty$ is divergent and this cannot be the case since the $p_N$, $N \ge 0$, define a probability distribution. Thus the Markov chain representing the number of blocked terminals is not ergodic, and the broadcast channel under the infinite source assumption is unstable.

Now consider the finite source model. Using the rule that $p_i(k)=0$ for $i < 0$, the transition equation for $0 \le n < M$ is

$$ (13) \qquad \begin{aligned} p_n(k+1) = & \sum_{j=2}^{n} p_{n-j}(k)q_j(n-j) + p_{n+1}(k)g_1(n+1)q_0(n+1) \\ & + p_n(k)(1-g_1(n))q_0(n) + p_n(k)g_0(n)q_1(n) \\ & + p_{n-1}(k)(1-g_0(n-1))q_1(n-1) \end{aligned} $$

Defining, for $0 \le N < M$, the sum $S_N$ as in (8) for the finite source model we obtain from (13) and substituting the stationary probability $p_n$:

$$ (14) \quad S_N = p_{N+1}g_1(N+1)q_0(N+1) + p_N g_0(N)q_1(N) + \sum_{n=0}^{N} \sum_{j=0}^{n} p_{n-j}q_j(n-j) $$
Now take limit as in Definition 1 : $M→∞$, $b→0$, $M.b→d$; we obtain $q_j(n) = \frac{d^j}{j!} e^{-d}$ for any j and n. Therefore, in the limit

$$ (15) \quad S_N = p_{N+1} g_1^{(N+1)} q_0^{(N+1)} + p_N g_0^{(N)} q_1^{(N)} + \sum_{j=0}^{N} \frac{d^j e^{-d}}{j!} S_{N-j} $$

and an argument identical to the one for the infinite source model can be now used to complete the proof of instability.

We note in passing that the finite source model in the limit as we let the total number of terminals tend to infinity, and the infinite source model are not identical; in the infinite model there is a non-zero probability of a transmission from active terminals in each slot even when we let $k→∞$, while for the finite source model in the limit as $M→∞$ no active terminal will transmit as $k→∞$.

In the context of this study, another measure of interest is the throughput of the broadcast channel. Indeed this may well be the primary performance measure for the system under consideration.

## Definition 2.

The conditional throughput $D_n(k)$ of the broadcast channel is the conditional probability that one packet is successfully transmitted during the k-th slot given that $N(k)=n$.

Clearly, the conditional throughput cannot exceed one; it can also be defined as the expected value of the number of successful transmissions during the k-th slot conditional on there being n blocked terminals at the beginning of that slot.
## Definition 3.

The throughput of the broadcast channel is defined as

$$D = \lim_{k \to \infty} \sum_{n=0}^{\infty} D_n(k) p_n(k)$$

The conditional throughput is

$$(17) \qquad D_n(k) = c_0 g_1(n) + c_1 g_0(n)$$

for the infinite source model; for the finite source model we replace $c_0$ and $c_1$ by $q_0(n)$ and $q_1(n)$, respectively. This quantity is obviously independent of $k$, therefore in the following we shall simply write $D_n$ instead of $D_n(k)$.

## Theorem 2.

For $f > 0$, the throughput of the broadcast channel is zero for the infinite source model, and for the finite source model as we let $M \to \infty$, $b \to 0$, $M \cdot b \to d$.

The proof is straightforward and not presented here.

## 3. CERTAIN CHANNEL CONTROL POLICIES.

Various control policies for the broadcast channel have been discussed in [11] where these have been classified, roughly speaking, into three groups : policies which regulate access to the channel from the active terminals, those which regulate access from the blocked terminals, and mixed policies. In this section we discuss two policies in some detail and give a definition of stability in each case. We see that this definition will be a variant of (or identical to) the definition
given above. The first control policy which we shall describe typifies the first group of policies and it may well be impossible to implement; the second policy is of the second group and has a better chance of being realizable.

### 3.1. *A threshold control policy.*

An input control policy as defined by LAM [11] is one which limits access to the channel from the active terminals depending on the present state and past history of the channel. Borrowing the terminology of Markov decision theory [13], a policy is said to be *stationary* if it only depends on the present state of the system.

The first policy we present is described in Figure 2. If the number of blocked terminals exceeds $\Theta$, the threshold, an active terminal which wishes to initiate the transmission of a packet is not allowed to transmit and joins the *impeded set*; if not the transmission takes place as in the uncontrolled channel. As soon as the number of blocked terminals decreases below $\Theta$ (this can only take place in steps of one) an impeded terminal joins the blocked set; thus the number of blocked terminals can be less than $\Theta$ only if there are no impeded terminals. The retransmission rate of blocked terminals is constant. We shall refer of this scheme as the *threshold control policy*.

In this context, stability must be defined in terms of the number of impeded plus blocked terminals.

### Definition 4.

Let $U(k)$ be the number of blocked plus impeded terminals at the beginning of the $k$-th slot for the threshold control policy. The channel, with this control scheme, is unstable if the limit as $k \to \infty$ of $Pr\{U(k) < j\}$ is zero for all
finite values of j for the infinite source model; for the
finite source model the same definition is used as $M \to \infty$,
$b \to 0$, $M.b \to d$. Otherwise the channel is stable.

The following equations, which must be satisfied
by the equilibrium probabilities p_n for the number n of
blocked plus impeded terminals at the beginning of a slot,
may be derived.

$n \le \theta$

$$
(19) p_n = \sum_{j=0}^{n} p_{n-j} c_j + p_{n+1} A_1 (n+1) c_0 + p_n [c_1 g_0 (n) - c_0 g_1 (n)] - p_{n-1} g_0 (n-1) c_1
$$

$n \ge \theta + 1$

$$
(20) \quad p_n = \sum_{i=n-\theta}^{n} p_{n-i} c_i + \sum_{i=1}^{n-\theta-1} p_{n-i} c_i [1-A_1(n-i)] \\
\phantom{(20) \quad p_n =} + \sum_{i=1}^{n-\theta} p_{n-i+1} c_i A_1(n-i+1) + p_{n+1} c_0 A_1(n+1) + p_n [1-A_1(n)] c_0
$$

where

$$
A_1(n) = \begin{cases}
g_1(\theta) & \text{if } n > \theta \\
g_1(n) & \text{if } 0 \le n \le \theta
\end{cases}
$$

Equation (20) may be rewritten as :

$$
(21) \quad p_n = \sum_{i=0}^{n} p_{n-i} c_i + \sum_{i=0}^{n-\theta-1} p_{n-i} A_1 (n-i) [c_{i+1} - c_i] + p_{n+1} c_0 A_1 (n+1)
$$

We obtain the following result concerning the sta-
bility of the threshold control policy. For simplicity let
$A = g_1(\theta)$.
**Theorem 3.**

$\lambda = \sum_{i=1}^{\infty} ic_i$ for the infinite source model is less than A, then the broadcast channel with a stationary threshold control policy is stable; otherwise it is unstable.

The proof is given in Appendix 1.

The threshold control policy may be quite difficult to implement in practice. It has a major advantage, however, with respect to the retransmission control policies we shall study in Section 3.2: the maximum achievable channel throughput is not limited to $e^{-1}$. In fact the throughput may be arbitrarily close to one if $\theta = 1$ since it suffices to set $f = 1$ in this case. In general, for $\theta \ge 1$, A is maximized by setting $f$ equal to $f^* = \theta^{-1}$. We then have $A(f^*) = (1-\theta^{-1})^{\theta-1}$ which, for $\theta \gg 1$, is $A(f^*) \approx \exp(-1+\theta^{-1}) > e^{-1}$. We see here that $e^{-1}$ is a lower bound to the maximum achievable throughput. This does not depend on the Poisson assumption of packet arrivals to the channel.

## 3.2. *A retransmission control policy.*

A retransmission control policy is one which regulates access to the channel from the set of blocked terminals as a function of the past and present state of the system. We consider such a policy which only uses information concerning the present state (it is stationary) to regulate the retransmission rate of the ensemble of blocked terminals. The appropriate definition of stability (for this case) is then that given in Definition 1 and the equations for the controlled system are (6) for the infinite source model and (7) for the finite source model with the following modification. The parameter $f$ which determines $g_i(n)$ (see (3) and (4)) giving the probability that a blocked terminal retransmits a packet
during a slot will be a function of n which we denote $f(n)$
so that

$$
(22) \quad g_i(n) = \binom{n}{i} [f(n)]^i [1-f(n)]^{n-i}
$$

The following result can then be established :

Theorem 4.

A stationary retransmission control policy yields a
stable broadcast channel if

$$
\lambda = \sum_{i=1}^{\infty} i c_i < d
$$

and an unstable one if $\lambda>d$ where $d = \lim_{n\to\infty}[c_1g_0(n) + c_0g_1(n)]$.

The proof of this result is given in Appendix 2.
We do not have a proof of instability for $\lambda=d$ except for a
special case; the question is only of mathematical interest,
however.

Remark.

In fact Theorem 1 is a corollary of Theorem 4 since
if (as is the case for the uncontrolled broadcast channel) f
is independent of n we have d = 0.

Another consequence of Theorem 4 concerns the form
which the function f(n) must take to ensure stability.

Theorem 5.

For the broadcast channel under stationary retrans-
mission control to be stable it is necessary that
$$ \lim_{n \to \infty} f(n) = 0 \quad \text{and} \quad \lim_{n \to \infty} nf(n) > 0 $$

### Proof.

Clearly if the first condition is not satisfied we shall have $d = 0$ leading to the instability of the channel. Now suppose that the second condition is not satisfied, that is $\lim_{n \to \infty} nf(n) = 0$, but that the first condition is satisfied. Then $d = c_1$ and we cannot have $\lambda < d$; therefore by Theorem 4 the system will be unstable, which completes the proof.

We see therefore by this last result that a stationary retransmission control policy (with expected time between attempts of a blocked terminal to retransmit given by $[f(n)]^{-1}$) may stabilize the channel only if $f(n)$ decreases with $n$ but no faster than the function $n^{-1}$.

### 3.3. *An optimal retransmission control policy.*

It is natural to seek retransmission control policies which will maximize the output rate of the channel; for a stabilizing policy the maximum value will be $d$ of theorem 4 since the input rate will be identical to the output rate. Consider

$$ D_n(f) = c_1(1-f)^n + c_0nf(1-f)^{n-1} $$

By deriving this expression with respect to $f$ and setting the result equal to zero we see that $D_n(f)$ is maximized by setting $f$ equal to $f^* = (c_0-c_1)(nc_0-c_1)^{-1}$ for $n \ge 1$, or $f^* = (1-\alpha)(n-\alpha)^{-1}$ if $\alpha = c_1/c_0$, where we are restricted to $\alpha < 1$ (for instance, with a Poisson arrival process $\alpha = \lambda$). The maximum value of $D_n(f)$ is then $D_n(f^*) = c_0[(n-1)(n-\alpha)^{-1}]^{n-1}$. In the limit as $n \to \infty$ we will obtain the throughput $d = \exp(\log c_0 + \alpha - 1)$.
If the arrival process is Poisson we obtain $d = e^{-1}$ as predicted by Abramson (1) and Kleinrock and Lam (8) for the maximum throughput of the channel.

On figure 3 we present time series characterizing channel behaviour obtained by Monte-Carlo simulation with a Poisson arrival process of packets from active terminals. On Figure 3a we show the behaviour of the uncontrolled broadcast channel; we see that if the number of blocked terminals is sufficiently high, the channel is unable to recover (i.e. it is unstable) and the total number of blocked terminals increases indefinitely while the channel throughput tends to zero. On Figure 3b we see the channel behaviour under identical conditions, except for the retransmission probability which is chosen to be $f^*$. The channel is now able to recover from an initial state with a large number of blocked terminals and the throughput matches the input rate. The exact form of $f$ chosen in the simulation results of Figure 3b is $f^+ = (1-\lambda)n^{-1}$, where denominator term of $f^*$ has been simplified. There is a simple intuitive (but non-rigorous) explanation for the choice of $f^+$: when there are $n$ blocked terminals and $n$ is very large the set of blocked terminals will behave as a Poisson source of parameter $f^+ \cdot n = 1-\lambda$; thus the total input rate of packets to the channel will be $\lambda+f^+n=1$ which is the maximum rate it can admit.

The control policy $f^*$ could be approximately implemented by simple statistical estimation of the number of blocked terminals. The estimate could be obtained by a specialized terminal (or by the data concentrator which receives packets and sends back the acknowledgement packets) which would deduce an instantaneous estimate of the number of blocked terminals by measuring the throughput. It would then send once in a while an updated value of $f^*$ on the frequency used for acknowledgement packets.
## 4. CONCLUSIONS.

In this paper we have given a theoretical treatment of some basic problems related to the packet switching broadcast channel. Its inherent instability has motivated us to look into stabilizing control policies. The first policy examined has been one in which access to the channel is controlled by admitting active terminals which wish to transmit a packet into an impeded set. Necessary and sufficient conditions under which the number of impeded plus blocked terminals remains bounded are derived, and it is shown that with this policy it is theoretically possible to achieve a throughput which is arbitrarily close to one.

We have then examined control schemes based only on choosing the transmission probability of any blocked terminal as a function of the total number of blocked terminals. Sufficient conditions for stability and instability of the channel and necessary conditions which must be satisfied by the retransmission probability are derived for this scheme. We then obtain the optimal control policy for the channel which maximizes the throughput. This policy appears promising as a practical means of optimizing channel performance.

## Acknowledgements.

The authors are grateful to Prof. L. Kleinrock for discussions which motivated this research.
The theorem is easily established for $\theta = 1$. It suffices to notice
that in this case the system is equivalent to a single server queue with
binomial service (with parameter $A = f$) and mean service time $1/f$; the
arrival process is independent in each service interval. It is easily
shown that the model has an equilibrium distribution of queue length
 corresp (corresponding to the numbers of impeded terminals) if and only if $\lambda \ll A$.
Now consider the case $\theta > 1$. Let $\pi_n$ denote the equilibrium probability
that the number of impeded terminals is $n$ for $n \ge 1$; $q_j$ will denote the
equilibrium probability that there are zero impeded terminals and $j$ blocked
ones. The equilibrium probabilities satisfy for $n \ge 1$,

$$
\begin{equation}
\begin{split}
(23) \quad \pi_n ={}& \pi_{n+1} C_0 A + \sum_{i=0}^{n-1} \pi_{n-i} [C_i (1-A) + C_{i+1} A] \\
& \phantom{=} + \sum_{j=0}^{\theta} q_j C_{n-j+\theta} - q_{\theta} C_{n+1} A
\end{split}
\end{equation}
$$

Define the generating function $G(x) = \sum_{n=1}^{\infty} \pi_n x^n$. Then

$$
\begin{equation}
\begin{split}
(24) \quad G(x) = \frac{C_0 A}{x} \biggl( &G(x) - \pi_1 \biggr) + G(x) \biggl[ G(x)(1-A) + \frac{A}{x} (C(x) - C_0) \biggr] \\
& + \Phi(x) - q_{\theta} A' \cdot \frac{C(x) - C_0}{x}
\end{split}
\end{equation}
$$

where

$$
\Phi(x) = \sum_{n=1}^{\infty} \sum_{j=0}^{\theta} q_j C_{n-j+\theta} x^n
$$

yielding

$$
(25) \quad G(x) = \frac{x \Phi(x) - q_{\theta} A (C(x) - C_0) - C_0 A \pi_1}{x - x C'(x) (1 - A) - A C(x)}
$$
Notice that $\pi_n = p_{\theta+n}$, $n \ge 1$, $q_j = p_j$, $0 \le j \le \theta$, of equations (20), (21).
By FOSTER'S theorem [14] the Markov chain representing the number of blocked
plus impeded terminals will be ergodic (and the channel will be stable) if
there exists a positive solution to (23), of finite sum since the Markov
chain is irreducible and aperiodic.

Suppose $q_0 > 0$ ; it can be easily shown that $q_j > 0$, $1 \le j \le \theta$, and
$\pi_n > 0$, $n \ge 1$. Denote by $F(x)$ the numerator of (25) ; we first show that
if $q_0 > 0$, then $F'(1) > 0$. We have

$$
\begin{align*}
F'(1) &= \Phi(1) + \Phi'(1) - q_{\theta} A \sum_{n=1}^{\infty} n C_n \\
&= \sum_{n=1}^{\infty} \left( \sum_{j=0}^{\theta} q_j C_{n-j+\theta} (n+1) - A q_{\theta} C_n \right) > 0
\end{align*}
$$

since we have $A \le 1$.

Now take $\lim_{x \to 1} G(x)$. After applying l'Hôpital's rule we remain with

$$
\lim_{x \to 1} G(x) = \frac{F'(1)}{A - C'(1)} = \frac{F'(1)}{A - \lambda}
$$

Clearly if $A = \lambda$ and $q_0 > 0$ then $G(1)$ does not exist and the channel is
unstable. Similarly if $A > \lambda$ and $q_0 > 0$, then $G(1) < 0$ which is a contra-
diction so that again the channel is unstable. The case $\lambda < A$ however
remains to be considered ; taking any finite $q_0 > 0$ we see that since
$G(1) < \infty$ due to the fact that $F'(1)$ is bounded, the sum

$$
G(1) + \sum_{j=0}^{\theta} q_j < \infty
$$

and FOSTER's theorem is satisfied. Therefore if $\lambda < A$ the broadcast channel
with the threshold control policy is stable.
Appendix 2 : Proof of Theorem 4

Let us first determine that the channel is
unstable if $\lambda > d$. If the limit defining $d$ exists, then
for each $\epsilon>0$ there exists an integer $n_o$ such that for
all $n \ge n_o$,

$$
|g_1(n) - a| \le \epsilon \text{ and } |g_o(n) - b| \le \epsilon
$$

where a, b are constants such that

$$
d = c_o a + c_l b
$$

$$
\text{Let } P(z) = \sum_{n=n_o}^{\infty} p_n z^n \, , \quad Q(z) = \sum_{n=n_o}^{\infty} S_n z^n \, . \text{ Then, from}
$$

(9) and the discussion above we have

$$
(26) \quad S_n - \sum_{j=0}^{n} S_{n-j} c_j \le (a+\epsilon)p_{n+1} c_o + (b+\epsilon)p_n c_l
$$

and

$$
(27) \quad S_n - \sum_{j=0}^{n} S_{n-j} c_j \ge (a-\epsilon) p_{n+1} c_o + (b-\epsilon) p_n c_l
$$

for all $n \ge n_o$. Thus, from (26), we derive

$$
Q(z) - \sum_{n=n_o}^{\infty} \sum_{j=0}^{n} S_{n-j} c_j z^n \le \frac{(a+\epsilon)c_o}{z} (P(z)-z^{n_o}p_{n_o}) + (b+\epsilon)c_l P(z)
$$

Notice that

$$
\sum_{n=n_o}^{\infty} \sum_{j=0}^{n} S_{n-j} c_j z^n = \sum_{n=n_o}^{\infty} \sum_{j=0}^{n-n_o} S_{n-j} c_j z^n + \sum_{n=n_o}^{\infty} \sum_{j=n-n_o+1}^{n} S_{n-j} c_j z^n
$$
Therefore, if we denote $C(z) = \sum_{j=0}^{\infty} c_j z^j$,

$$ (28) \quad Q(z)(1-C(z)) \le \frac{(a+\epsilon)c_0}{z} (P(z) - z^{n_0}p_{n_0} + (b+\epsilon)c_1 P(z)) + \sum_{n=n_0}^{\infty} \sum_{j=n-n_0+1}^{n} S_{n-j} c_j z^n $$

The following relationship may be verified :

$$ Q(z)(1-z) = z^{n_0} S_{n_0} + P(z) - z^{n_0} p_{n_0} = P(z) + z^{n_0} S_{n_0-1} $$

yielding after substitution in (28) and combining terms :

$$ (29) \quad P(z) \left[ \frac{1-C(z)}{1-z} - \frac{(a+\epsilon)c_0}{z} - (b+\epsilon)c_1 \right] \le -z^{n_0} \frac{1-C(z)}{1-z} S_{n_0-1} - z^{n_0-1} (a+\epsilon)c_0 p_{n_0} + \sum_{n=n_0}^{\infty} \sum_{j=n-n_0+1}^{n} S_{n-j} c_j z^n $$

However

$$ \sum_{n=n_0}^{\infty} \sum_{j=n-n_0+1}^{n} S_{n-j} c_j z^n \le S_{n_0-1} \sum_{n=n_0}^{\infty} \sum_{j=n-n_0+1}^{n} c_j z^n $$
and

$$ \sum_{n=n_o}^{\infty} \sum_{j=n_o+1}^{n} c_j z^n \le \sum_{n=1}^{\infty} \sum_{j=n}^{\infty} c_j z^n = F(z) $$

where $\lim z \to 1 F(z) = \lambda$.

Returning to (29) we obtain:

$$ (30) \quad P(z) \left[ \frac{1-C(z)}{1-z} - \frac{(a+\epsilon)c_o}{z} - (b+\epsilon)c_1 \right] \\ \le S_{n_o-1} \left[ -z^o \left( \frac{1-C(z)}{1-z} \right)^{\sum_{n=1}^{\infty} \sum_{j=n}^{\infty} c_j z^n} + \sum_{n=1}^{\infty} \sum_{j=n}^{\infty} c_j z^n \right] \\ - z^{n_o-1} (a+\epsilon)c_o p_{n_o} $$

Now take the limit as $z \to 1$ of both sides in (30). We obtain:

$$ (31) \quad P(1) \left[ \lambda - (a+\epsilon)c_o - (b+\epsilon)c_1 \right] \le - c_o p_{n_o} (a+\epsilon) $$

Therefore if $\lambda > d$, choosing $n_o$ sufficiently large so that $\lambda - d > \epsilon(c_o+c_1)$, we have that either $p_{n_o} = 0$ and $P(1) \le 0$ or $p_{n_o} > 0$ and $P(1) < 0$; in both cases it implies that the balance equations satisfied by the equilibrium probability distribution ${p_n}$ do not possess a positive solution. Thus the Markov chain representing the number of blocked terminals at the beginning of each slot is not ergodic and the channel is unstable if $\lambda > d$.
Starting with (27) and proceeding by arguments similar to the ones used above we can obtain

$$ (32) \quad P(1)[\lambda - (a-\epsilon)c_o - (b-\epsilon)c_1] \ge -\lambda S_{n_o-1} - (a-\epsilon)c_o p_{n_o} \\ + \sum_{n=n_o}^{\infty} \sum_{j=n-n_o+1}^{n} S_{n-j} c_j $$

The last term on the right-hand side of (32) cannot exceed $\lambda S_{n_o-1}$, therefore assuming $p_{n_o}$ is positive we may write

$$ P(1)[\lambda - (a-\epsilon)c_o - (b-\epsilon)c_1] \ge -\alpha(n_o) $$

where

$$ o < \alpha(n_o) = \lambda S_{n_o-1} + (a-\epsilon)c_o p_{n_o} - \sum_{n=n_o}^{\infty} \sum_{j=n-n_o+1}^{n} S_{n-j} c_j $$

since by choosing $n_o$ sufficiently large we know that $a > \epsilon$. Therefore if $\lambda < d$, then

$$ P(1) \le \frac{\alpha(n_o)}{d - \lambda - \epsilon(c_o + c_1)} $$

assuming that $n_o$ is large enough so that $d-\lambda > \epsilon(c_o+c_1)$. From (7) we notice that we may write for any $n \ge o$

$$ (33) \qquad p_n = k(n)p_o $$

where $k(n) > 0$; thus

$$ (34) \quad P(1) \le \frac{\sum_{j=0}^{n_o-1} k(j) + (a-\epsilon)c_o k(n_o)}{d - \lambda - \epsilon(c_o + c_1)} $$
Notice that $p_{n_o}$ is positive if and only if $p_o$ is positive. We can now invoke FOSTER's theorem [14] which implies that the Markov chain is ergodic if there exists a positive solution to the equilibrium equation (7) such that $P(1) < \infty$. Setting $p_o=1$ (or any positive constant), (33) represents a positive solution of (7); by (34) we will have $P(1)<\infty$ therefore we have satisfied FOSTER's condition completing the proof that the channel is stable if $\lambda < d$. We now have to consider the case $\lambda=d$.

For $n \ge n_o$ we may write

$$g_l(n) = a + u_n, \quad g_o(n) = b + v_n$$

so that from (9) we obtain

$$Q(z) [1-C(z)] = \frac{ac_o}{z} [P(z) - z^{n_o}p_{n_o}] + bc_l P(z) \\ + \frac{c_o}{z} [U(z) - z^{n_o}u_{n_o}p_{n_o}] \\ + c_l V(z) + \sum_{n=n_o}^{\infty} \sum_{j=n-n_o+1}^{n} S_{n-j} c_j z^n$$

where

$$U(z) = \sum_{n=n_o}^{\infty} u_n p_n z^n, \quad V(z) = \sum_{n=n_o}^{\infty} v_n p_n z^n$$

yielding
(35) $P(z) =$

$$ -z^{n} {}_{o}S_{n-1}^{o} \frac{1-C(z)}{1-z} - c_{o} (a+u_{n}) p_{n} z^{n-1} \frac{c_{o}}{z} U(z)+c_{1}V(z) + \sum_{n=n_{o}}^{\infty} \sum_{j=n-n_{o}+1}^{n} s_{n-j} c_{j} z^{n} $$

$$ \frac{1-C(z)}{1-z} - \frac{aC_{o}}{z} - bc_{1} $$

For $\lambda=d$, the denominator of $P(1)$ vanishes. Instability for $\lambda=d$ will be verified if we can show that the numerator of $P(1)$ does not, or that the numerator of $P(z)$ tends to zero more slowly than the denominator for $\lambda=d$ as $z \to 1$. If $c_0 g_1(n) + c_1 g_0(n) < d$ for all $n \ge n_o$ (i.e. if $D_n$ tends to $d$ from below), then $c_0 U(1) + c_1 V(1) < 0$ and clearly the numerator of $P(1)$ is negative for $p_n > 0$ and $P(1)$ does not exist. Under this condition the channel is unstable for $\lambda=d$. In general however, even though we conjecture that the channel is unstable when $\lambda=d$, we have no proof of this.
<figure><img src="image_1.png" /><figcaption>Figure 1</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Figure 2</figcaption></figure>
<figure><img src="image_3.png" /><figcaption>Figure 3a</figcaption></figure>

<figure><img src="image_4.png" /></figure>
REFERENCES

( 1) Abramson, N., "The ALOHA system-Another alternative for computer communications", Fall Joint Computer Conference, AFIPS Conf. Proc., Vol. 37, 1970, pp. 281 - 285.

( 2) Kleinrock, L., "Resource allocation in computer systems and computer-communication networks", Proc. IFIP Congress, Stockholm, 1974, to appear.

( 3) Baran, P., Boehm, S., and Smith, P., "On distributed communications", series of eleven reports available from Rand Corp., Santa Monica, Calif., 1964.

( 4) Davies, D. W., "The principles of a data communication network for computers and remote peripherals", Proc. IFIP Congress (Hardware), Edinburgh, 1968.

( 5) Roberts, L. G., "Multiple computer networks and inter-computer communications", ACM Symposium on Operating Systems, Gatlinburg, Tenn., 1967.

( 6) Abramson, N., "Packet switching with satellites", National Computer Conference, AFIPS Conf. Proc., 1973, PP. 695-702.

( 7) Roberts, L. G., "Dynamic allocation of satellite capacity through packet reservation", National Computer Conference, AFIPS Conf. Proc., 1973, pp. 711-716.

( 8) Kleinrock, L., and Lam, S., "Packet switching in a slotted satellite channel", National Computer Conference, AFIPS Conf. Proc., pp. 703-710.

( 9) Kleinrock, L., and Lam, S., "On stability of packet switching in a random multi-access broadcast channel",

(10) Pouzin, L., "Presentation and major design aspects of the Cyclades computer network", submitted for presentation at the Third Data Communications Symposium, April 1973.

(11) Lam, S., Ph. D. Thesis, Computer Science Dept., UCLA, 1974.

(12) Fayolle, G., Gelenbe, E., Labetoulle, J., and Bastin, D., "The stability problem of broadcast packet switching computer networks", to appear in Acta Informatica.

(13) Howard. R.A., "Dynamic Probabilistic Systems," Vol.II, John Wiley, New York, 1971.

(14) Cohen, J., "The Single Server Queue," North-Holland, Amsterdam, 1969.