# The stability problem of broadcast packet switching computer network

Guy Fayolle, Erol Gelenbe, Jacques Labetoulle, Didier Bastin

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

## To cite this version:

Guy Fayolle, Erol Gelenbe, Jacques Labetoulle, Didier Bastin. The stability problem of broadcast packet switching computer network. [Research Report] IRIA-RR-075, IRIA. 1974, pp.8. hal-04715965

HAL Id: hal-04715965

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

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

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

The stability problem
of broadcast packet
switching
computer network

G.Fayolle, E.Gelenbe,
J.Labetoulle, D.Bastin

Rapport de Recherche n°75

juin 1974
# THE STABILITY PROBLEM OF BROADCAST PACKET SWITCHING COMPUTER NETWORK

G. Fayolle, E. Gelenbe, J. Labetoulle, D. Bastin

IRIA-LABORIA

## ABSTRACT

Certain computer networks have been implemented using a radio broadcast frequency over which a large set of terminals are allowed to transmit packets of bits; one such example is the ALOHA computer network [1]. In such systems, a basic problem is that of the blocking of terminals whose transmission of a packet has overlapped in time with transmission by some other terminal. In this paper we consider a "slotted ALOHA" packet transmission scheme with an infinite set of terminals each transmitting at an infinitesimally small rate. We present a probabilistic model of such a system to show that the slotted ALOHA system with an infinite population is inherently unstable. This paper confirms the simulations and results of Kleinrock and Lam [8].

## RESUME

On étudie le comportement d'un canal de transmissions de données réalisé par la réflexion sur un satellite géostationnaire de messages envoyés par des terminaux communicant entre eux. Un théorème est présenté, qui montre l'instabilité de ce système. Les résultats s'appliquent au réseau d'ordinateurs "ALOHA".
# I - INTRODUCTION

Due to the inefficiency of allocating a large number of low capacity channels to a large set of user pairs transmitting data to each other, compared to the sharing of a high speed channel between the ensemble of users [2], various forms of packet switching schemes have been suggested [3],[4] and implemented in the ARPA [5], CYCLADES [10] and ALOHA computer networks [1].

We are concerned with networks using radio channels for packet switching similar to the ALOHA network in which *each* packet whose transmission overlaps in time the use of the channel by some other packet is lost. We can think of the shared radio channel being implemented using a geostationary satellite which acts as a transponder reflecting packets it receives back to earth. The information being transmitted can be heard by every user when it is reflected back; thus a terminal having transmitted a packet will know (by listening to the "echo") whether its packet has "collided" with another one and therefore is lost or whether the transmission has been successful. A terminal whose transmission is lost is blocked; it repeats the transmission of the same packet until a successful transmission occurs. A terminal which is not blocked is active. No collisions would occur if the transmission could be scheduled; the difficulty with this solution is that the only means of communication between the terminals is the channel itself. The three following methods for controlling transmissions over the channel have been suggested.
The first allows the terminal to transmit a packet at any instant of time.
The second method is known as the "slotted ALOHA" system which is the subject of
this paper. Here time is divided into equal slots whose duration is the transmis-
sion time of a packet (packet length is constant). Packet transmission is synch-
ronized so as to be initiated at the beginning of a slot and this approach has
been shown to increase the channel throughput over the first method [6]. Other
control schemes are mentioned elsewhere [9].

Kleinrock and Lam [8] have discussed the stability problem of the
slotted ALOHA channel. They give a qualitative argument indicating that this
channel will become saturated if the population of users is infinite independently
of the value of the arrival rate of packets to the channel. Here saturation is
construed as the phenomenon whereby the number of blocked terminals becomes arbi-
trarily large after a long period of operation. They also indicate that saturation
has been observed during simulation runs and they compute average first exit times
into the set of channel states which lead to saturation from an initially empty
channel for an infinite population model.

In this paper we concern ourselves with the infinite population system
which is a worst case representation of reality. We present a simple mathematical
model of the broadcast channel allowing us to give a characterization which is dif-
ferent from [9] of the channel throughput. We then give a proof of the instability
of the infinite population slotted broadcast channel. Our result confirms the dis-
cussion based on "fluid approximation" and the simulations of Kleinrock and Lam [8].

## II - THE MODEL

Consider the broadcast channel at the sequence of instants 0,1,2,...
when a slot begins. It is assumed that the slot, and packet data transmission,
is of unit length. Denote by $N(k)$ the number of blocked terminals at instant k.

Packets arrive from the non-blocked terminals according to a Poisson
process of rate $\lambda$; the instants of "arrival" of packets (which are Poisson) are
distinct from the instants of transmission of packets which are regular (as indi-
cated above). We assume that the time between the completion of transmission of
a packet and the time of retransmission of the same packet (if in the meanwhile
the terminal becomes blocked) is exponentially distributed with expected value
$1/\gamma$. This would probably not be so in a realistic situation where a fixed time
elapses (during which the terminal is silent) before the terminal knows that it
is blocked. The exponential assumption is equivalent to an assumption of Klein-
rock and Lam (equation (1) of [9]) for which they report that, based on simula-
tion runs, it is seen that a good degree of accuracy is obtained with this representation. In addition to these assumptions, each blocked terminal behaves as an independent source retransmitting the packet untill the transmission is successful.

In this framework N(k) is a random variable.

Let

$$ (1) \qquad p_n(k) = \text{Prob} \{ N(k) = n \} $$
We may then write the equation (1):

$$ (2) \qquad p_n(k+1) = \sum_{j=2}^{n} p_{n-j}(k) \frac{\lambda^j}{j!} e^{-\lambda} + p_{n+1}(k) \pi_1(n+1) e^{-\lambda} \\ \qquad \qquad + p_n(k)[1-\pi_1(n)]e^{-\lambda} + p_n(k)\pi_0(n)\lambda e^{-\lambda} \\ \qquad \qquad + p_{n-1}(k)[1-\pi_0(n-1)]\lambda e^{-\lambda} $$

where $\pi_i(n)$, i=0,1,2,..., is the probability that during one slot i blocked terminals transmit a packet conditional on there being n blocked terminals at the beginning of a slot.

We have

$$ (3) \qquad \pi_0(n) = e^{-\gamma n} $$

and

$$ (4) \qquad \pi_1(n) = n e^{-\gamma(n-1)} (1-e^{-\gamma}) $$

On the right-hand side of (2), the first term represents the fact that if in a slot two or more "external arrivals" occur (i.e. those which do not originate from blocked terminals) then these go to increase the number of blocked terminals independently of the number of packets generated by the blocked terminals.

The second term covers the case where no external arrival occurs and exactly one blocked terminal emits a packet thus becoming unblocked. The fourth term covers the case where no blocked terminal retransmits a packet and one external arrival occurs. In the fifth term one external arrival and at least one transmission from a blocked terminal take place. Equation (2) is the transition equation of a discrete time Markov chain which is aperiodic and irreducible. It remains valid for n=0,1 if by definition $p_i(k) = 0$ for $i < 0$.

1) Equation (2) remains valid for all non-negative integer values of n if we use the rule that $p_i(k)=0$ for $i<0$. This rule is necessary for n= 0,1.
Consider the invariant probability measure {$p_n$} satisfying (2); that is

$$ (6) \quad p_n = \sum_{j=2}^{n} p_{n-j} \frac{\lambda^j}{j!} e^{-\lambda} + p_{n+1} \pi_1(n+1)e^{-\lambda} + p_n[1-\pi_1(n)]e^{-\lambda} \\ \qquad + p_n \pi_0(n) \lambda e^{-\lambda} + p_{n-1}[1-\pi_0(n-1)]\lambda e^{-\lambda} $$

$$ \text{and} \quad (7) \quad \sum_{n=0}^{\infty} p_n = 1 $$

**Definition** We shall say that the slotted broadcast channel is **unstable** if an invariant probability measure, solution to (6) and (7), such that $p_n > 0$ for all non-negative integer $n$ does not exist.

In other terms, if the Markov chain given by (2) is not ergodic then we shall say that the channel is **unstable**. In physical terms this implies that after a sufficiently long time the number of blocked terminals becomes arbitrarily large.

**Theorem** The slotted broadcast channel is unstable.

To prove the theorem let us write (6) in slightly different form:

$$ (8) \quad p_n = \sum_{j=0}^{n} p_{n-j} \frac{\lambda^j}{j!} e^{-\lambda} + p_{n+1} \pi_1(n+1)e^{-\lambda} + p_n e^{-\lambda} [\lambda \pi_0(n) - \pi_1(n)] \\ \qquad - p_{n-1} \pi_0(n-1) \lambda e^{-\lambda} $$

and define

$$ (9) \quad S_N = \sum_{j=0}^{N} p_j $$

Then (8) yields

$$ S_N = p_{N+1} \pi_1 (N+1) e^{-\lambda} + p_N \pi_0 (N) \lambda e^{-\lambda} + \sum_{n=0}^{N} S_{N-n} \frac{\lambda^n}{n!} e^{-\lambda} $$

or

$$ S_N[1-e^{-\lambda}] = \sum_{n=1}^{N} S_{N-n} \frac{\lambda^n}{n!} e^{-\lambda} + p_{N+1} \pi_1(N+1)e^{-\lambda} + p_N \pi_0(N) \lambda e^{-\lambda} $$

leading to the inequality

$$ (10) \quad S_N[1-e^{-\lambda}] \le S_{N-1}[1-e^{-\lambda}] + p_{N+1}\pi_1(N+1)e^{-\lambda} + p_N\pi_0(N)\lambda e^{-\lambda} $$

equivalently

$$ p_N[1-e^{-\lambda}] \le p_{N+1}\pi_1(N+1)e^{-\lambda} + p_N\pi_0(N)\lambda e^{-\lambda} $$

or
$$ (11) \qquad \frac{p_{N+1}}{p_N} \ge \frac{1-e^{-\lambda} - \pi_0(N)\lambda e^{-\lambda}}{\pi_1(N+1)e^{-\lambda}} $$

But the right-hand side of (11) tends to infinity as $N \to \infty$. Therefore the series $\sum_{n=0}^{\infty} p_N$ diverges unless $p_N = 0$ for all $N$. Since (7) must be satisfied we conclude that $p_n = 0$ for all $n$ (finite) and the channel is unstable, as was to be shown.

### III - MODEL ASSUMPTIONS UNDER WHICH INSTABILITY IS VERIFIED

In fact, the theorem we have proved remains valid under broader assumptions which we state as follows.

A1- Let $X_k$ be the number of external arrivals during the k-th slot;

$\{X_k\}_{0 \le k < \infty}$ is a sequence of independent identically distributed random variables whose sample space is the set of non-negative integers and

$$ \begin{gathered} \lim_{n \to \infty} \mathrm{Prob}\{X_k = i\} = c_i, \quad i \ge 0 \\ \sum_{i=0}^{n} c_i = 1 \end{gathered} $$

A2- Let

$Y_{ki} = \begin{cases} 1 & \text{if the i-th blocked terminal transmits during the} \\ k \text{-th slot} \\ 0 & \text{otherwise} \end{cases}$

$Y_{ki}$ is a random variable; it is independent of $Y_{kj}$ for $i \ne j$, of $Y_{li}$ for $l \ne k$, and of $Y_{lj}$ for $l \ne k, i \ne j$. Furthermore $\mathrm{Prob}\{Y_{ki} = 1\} = a > 0$.

Equation (2) is now replaced by

$$ (12) \qquad p_n(k+1) = \sum_{j=2}^{n} p_{n-j}(k) c_j + p_{n+1}(k) \pi_1(n+1) c_0 + p_n(k) [1-\pi_1(n)] c_0 \\ \qquad \qquad + p_n(k) \pi_0(n) c_1 + p_{n-1}(k) [1-\pi_0(n-1)] c_1 $$

where, instead of (3) and (4), we have

$$ (13) \qquad \pi_0(n) = (1-a)^n $$

$$ (14) \qquad \pi_1(n) = n(1-a)^{n-1}a $$

and (10) is replaced by

$$ (15) \qquad S_N[1-c_0] \le S_{N-1}[1-c_0] + p_{N+1}\pi_1(N+1)c_0 + p_N\pi_0(N)c_1 $$

so that

$$ (16) \qquad \frac{p_{N+1}}{p_N} \ge \frac{1-c_0-(1-a)^N}{Na(1-a)^{N-1}} $$

The arguments used in the preceding section are then used to prove the theorem.
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] Baren, 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.S., "Packet switching in a slotted satellite channel", National Computer Conference, AFIPS Conf. Proc., 1973, pp. 703-710.

[9] Kleinrock, L., and Lam, S.S., "On stability of packet switching in a random multi-access broadcast channel", to appear.

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