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

HAL
open science

# Simulation d'un canal de transmission de données partage.

Banh Tri-An, H Demarbaix, Erol Gelenbe

► To cite this version:

Banh Tri-An, H Demarbaix, Erol Gelenbe. Simulation d'un canal de transmission de données partage.. [Rapport de recherche] IRIA-RR-119, IRIA. 1975, pp.10. hal-04716087

HAL Id: hal-04716087

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

Simulation d'un canal
de transmission de données
partage.

Banh Tri An, H. Demarbaix

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 119

Mai 1975
SIMULATION D'UN CANAL DE TRANSMISSION DE DONNÉES PARTAGE

Banh Tri An, et H. Demarbaix

présenté par E. Gelenbe

Résumé

Fayolle, Gelenbe, et Labetoulle [9] ont démontré l'instabilité d'un
canal de transmission de données partagé à commutation de paquets de
type "ALOHA" et ont également prouvé que certaines politiques de
contrôle agissant sur l'entrée de paquets dans le canal le stabilisent
et optimisent ses performances.

Le but de cet étude est de mettre en évidence ces propriétés du
canal par des expériences de simulation et d'étudier son temps de
recouvrement à la suite de phénomènes de surcharge de trafic de
durée limitée.

Abstract

The purpose of this note is to present a number of simulation results concerning a packet switching broadcast channel. In particular, we verify the theoretical predictions of Fayolle, Gelenbe, Labetoulle [9]. The instability of the uncontrolled channel and the effect of certain stabilizing control policies is apparent from the experimental results. We also experiment with the ability of the channel to recover from transient surges of input traffic.
# I. Introduction.

Face au développement à grande échelle des réseaux de transmission de données [4] la commutation de paquets utilisant un canal radio partagé [6],[10] par un ensemble de terminaux semble être une parmi les solutions ayant un intérêt pratique. En effet, on peut énumérer plusieurs avantages par rapport à un réseau conventionnel à lignes :

- élimination des problèmes de topologie et de routage;

- indépendance du coût vis-à-vis de l'étendue géographique;

- mobilité des utilisateurs;

- possibilité d'élimination de terminaux sans faire aucune modification à l'ensemble du réseau;

- possibilité de diffusion simultanée de l'information vers un nombre variable de noeuds;

- flexibilité dans la modification du réseau.

Le but de cette étude est de présenter quelques résultats de simulation caractérisant le comportement d'un canal de transmission de paquets partagé pour complémenter et étendre les résultats théoriques qui ont été présentés dans [1],[9].

Le système étudié est représenté sur la Figure 1(a) et (b). Un ensemble de terminaux transmettent des paquets aux instants $k = 0,1,2,...$ sur une seule fréquence radio (le canal) ou sur une même ligne de transmission. On suppose que l'unité de temps correspond à la durée de transmission d'un paquet (que nous appellerons l'intervalle), la longueur en bits des paquets étant constante. Si plusieurs terminaux émettent un paquet simultanément, ceux-ci entrent dans l'état bloqué; c'est-à-dire que les transmissions ne peuvent pas être reçues correctement. Un
terminal bloqué devra retransmettre le même paquet jusqu'au moment où la transmission a lieu avec succès et le terminal rejoint l'état *actif*. Le schéma que nous avons décrit correspond au fonctionnement du système ALOHA discrétisé ("slotted ALOHA") décrit dans [5].

<figure><img src="image_3.png" /><figcaption>Fig 1 (a)</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig 1 (b)</figcaption></figure>
## II. Quelques définitions et rappels des résultats obtenus dans [1],[9].

Dans ce paragraphe, nous présenterons brièvement la formalisation des notions relatives au canal ALOHA décritisé qui ont été développées dans [1],[9].

Nous dirons que le canal est instable si au bout d'un temps suffisamment long, le nombre de terminaux bloqués dépasse toute borne finie fixée à l'avance. Plus formellement

$$ \lim_{k \to \infty} \text{Pr} [N(k) < j] = 0 \quad , \forall j \quad j < \infty. $$

Pour la distribution de probabilité suivant laquelle les paquets sont réémis, il existe deux alternatives analytiquement simples :

- **Retransmission aléatoire uniforme** caractérisée par un entier K et dans laquelle un paquet est réémis dans l'un des K slots consécutifs, avec chaque fois la probabilité $1/K$.

- **Retransmission aléatoire géométrique** caractérisée par une probabilité f avec laquelle un terminal bloqué réémet dans un intervalle quelconque.

Ces deux possibilités correspondent aussi à des cas de réalisation pratique. Dans les deux cas, chaque terminal bloqué est supposé agir indépendamment (du point de vue probabilité) des autres terminaux (actifs et bloqués). Cette indépendance est aussi une nécessité sur le plan pratique car une des hypothèses de fonctionnement de ce système est qu'il n'est pas possible de synchroniser entre eux le comportement des terminaux. Dans le cas de la retransmission aléatoire uniforme étudié par LAM [4], il n'existe pas
de démonstration rigoureuse de l'instabilité qui est cependant apparente dans des résultats de simulation.

Les théorèmes suivants ont été obtenus par FAYOLLE, GELENBE, LABETOULLE [1,9] pour le cas de la retransmission géométrique aléatoire.

**Théorème 1** [9].

Le canal est instable si les terminaux actifs constituent une source de paquets telle que (i) la transmission de paquets est indépendante d'un intervalle à l'aujourd'hui (ii) la probabilité de transmission de n paquets par les terminaux actifs dans un interval est donnée par

$$c_{n}, n \geq 0, \sum_{\substack{0 \\ n}}^{\infty} c_{n} = 1,$$

(iii) $0 < f \le 1$ est constant.

Ce théorème a été généralisé aussi dans [9] au cas d'un modèle à source finie. Le problème d'instabilité a pour conséquence que le débit du canal à l'équilibre est nul; c'est-à-dire :

$$D = \lim_{k \to \infty} \sum_{n=0}^{\infty} p_n(k) [c_0 g_1(n) + c_1 g_0(n)] = 0$$

où $p_n(k)$ est la probabilité qu'il y ait n terminaux bloqués au début du kème intervalle. Soient $N(k)$ le nombre total de terminaux bloqués et $X(k)$ le nombre de terminaux bloqués ayant transmis un paquet dans le kème intervalle; alors :

$$g_0(n) = \Pr[X(k) = 0 | N(k) = n]$$

$$g_1(n) = \Pr[X(k) = 1 | N(k) = n]$$

On remarque que $[c_0 g_1(n) + c_1 g_0(n)]$ est la probabilité d'une
transmission avec succès dans un intervalle au début duquel il y a n terminaux bloqués. Ce phénomène d'instabilité est la motivation des études de politiques de contrôle du canal.

LAM [4] a classifié les politiques de contrôle en trois groupes :

- Politiques de contrôle sur les entrées (PCE), limitant les accès des terminaux actifs,

- Politiques de contrôle sur les retransmissions (PCR), jouant sur les terminaux bloqués,

- Politiques mixtes (PCER).

Nous allons discuter, résultats de simulation à l'appui, de celles appartenant au second groupe (PCR). Certains résultats nous conduiront ensuite à parler de celles du troisième groupe (PCER).

Au sujet des politiques PCR, FAYOLLE, GELENBE et LABETOULLE [9] ont démontré les résultats suivants. Soit $\lambda = \sum_{i=1}^{\infty} \alpha_{i}$, le taux moyen d'arrivée des paquets à partir des terminaux actifs.

### Théorème 2 [9].

Soit une politique de contrôle PCR de type $f=f(n)$ où n est le nombre de terminaux bloqués. Notons :

$$ (1) \qquad d = \lim_{n \to \infty} [c_0 g_1(n) + c_1 g_0(n)] $$

alors le canal est stable si $\lambda < d$, et instable si $\lambda > d$.

### Théorème 3 [9].

Pour une politique PCR de type $f=f(n)$ les conditions suivantes sont nécessaires à la stabilité du canal :
$$ \lim_{n \to \infty} f(n) \to 0 \quad , \quad \lim_{n \to \infty} nf(n) > 0 $$

Une politique PCR du type $f=f(n)$ est conceptuellement très simple ; on verra par la suite qu'elle permet d'optimiser le débit effectif du canal. En effet, il est démontré [9] également que

$$ (2) \quad f^*(n) = \frac{c_0 - c_1}{nc_0 - c_1} $$

maximise $D_n = c_0 g_1(n) + c_1 g_0(n)$ pour tout $n$ et, en particulier quand le processus d'arrivée de paquets à partir des terminaux actifs est de Poisson de paramètre $\lambda$, $c_0=e^{-\lambda}$, $c_1=\lambda e^{-\lambda}$, nous avons

$$ (3) \quad f(n) = \frac{1 - \lambda}{n - \lambda} $$

Si le canal est stable le débit effectif de transmission de paquets est égal au taux d'arrivée à partir de terminaux actifs. Donc le théorème 2 implique que le débit effectif maximum est $d-\epsilon$, $\epsilon>0$, où $\epsilon$ peut être arbitrairement petit. En introduisant (3) dans (1) nous obtenons :

$$ d = e^{-1} $$

qui serait le débit effectif maximum atteint par le canal. Ceci confirme d'ailleurs les résultats d'ABRAMSON [5].

Les simulations du paragraphe suivant confirment ces résultats théoriques.

### III. Résultats de simulations.

Dans les simulations faites avec un processus de Poisson d'arrivée de paquets des terminaux actifs, nous avons commencé par vérifier le théorème 3 :
CAPACITANCE CIRCUIT 1.22/FARADENCE

CAPACITANCE CIRCUIT 2.00/FARADENCE

CIRCUIT 1.22/FARADENCE

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

CAPACITANCE CIRCUIT 1.22/FARADENCE

CAPACITANCE CIRCUIT 2.00/FARADENCE

<figure><img src="image_6.png" /></figure>
Fig. 1

<figure><img src="image_7.png" /></figure>
CONCENTRATION OF PARTICLES IN THE DOWNFALL OF STORMS

UPPER LIMIT = 2,000 MILES = 0

LOW LIMIT = 0,000 MILES = 1,500

MEDIUM LIMIT = 1,500 MILES = 3,000

LOW LIMIT = 3,000 MILES = 6,000

MEDIUM LIMIT = 6,000 MILES = 12,000

HIGH LIMIT = 12,000 MILES = 24,000

LOW LIMIT = 24,000 MILES = 48,000

MEDIUM LIMIT = 48,000 MILES = 96,000

HIGH LIMIT = 96,000 MILES = 192,000

CONCENTRATION OF PARTICLES IN THE DOWNFALL OF STORMS

UPPER LIMIT = 1,500 MILES = 3,000

MEDIUM LIMIT = 3,000 MILES = 6,000

LOW LIMIT = 6,000 MILES = 12,000

MEDIUM LIMIT = 12,000 MILES = 24,000

HIGH LIMIT = 24,000 MILES = 48,000

LOW LIMIT = 48,000 MILES = 96,000

MEDIUM LIMIT = 96,000 MILES = 192,000

HIGH LIMIT = 192,000 MILES = 384,000

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

<figure><img src="image_9.png" /></figure>
CENORHOPAL DIAPESE 1.02/1.04/1.05/1.06/1.07/1.08/1.09

LAMINA • 0.325

STB • 0.350

NBTACI • 6

6

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

CENORHOPAL DIAPESE 1.02/1.04/1.05/1.06/1.07/1.08/1.09

LAMINA • 0.325

STB • 0.400

NBTACI • 130

130

<figure><img src="image_11.png" /></figure>
1) Avec une valeur de f constante et en introduisant un nombre N suffisamment élevé de bloqués dès le début, avec Nf suffisamment supérieur à un, l'instabilité s'est manifestée d'une façon évidente, due à un trafic trop élevé dans le canal (Fig. 1).

2) Avec une fonction $f(n)$ décroissant plus vite que $\frac{1}{n}$, c'est-à-dire

$$ \frac{p}{n^{3/2}} \text{ et } \frac{p}{n^2}, $$

nous avons constaté le phénomène inverse : les bloqués qui redeviennent actifs sont trop largement compensés par les nouveaux bloqués. Le trafic à l'entrée du canal G reste inférieur à un et le débit effectif S reste inférieur au taux d'entrée $\lambda$ tout en étant supérieur à zéro (Fig. 2).

Nous avons ensuite examiné les cas $n^{-1/2}$ et $n^{-1}$ qui vérifient les deux conditions précitées (Théorème 3).

3) Avec $f(n) = P/n^{1/2}$, nous avons constaté le même comportement mais d'une façon moins prononcée que pour le cas "sans contrôle". En fait, en injectant un nombre de bloqués n, tel que $nf(n) = n \frac{p}{n^{1/2}}$ soit suffisamment supérieur à un, le trafic sur le canal devient trop grand et l'on assiste à un phénomène d'instabilité avec débit nul. (Fig. 3)

4) Avec $f(n) = P/n$, nous avons le seul cas où le nombre moyen de bloqués qui réémettent par slot est égal à p et est indépendant de n. Nous voyons qu'alors, avec un nombre quelconque de bloqués injectés à n'importe quel instant, le canal reste stable et tend même à libérer au fur et à mesure les bloqués qui se sont accumulés
<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>
<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>
à cause d'une simultanéité d'action fortuite de plusieurs
utilisateurs, à condition d'avoir $\lambda$ sensiblement inférieur
à $\frac{1}{e}$ et une valeur convenable de p (Fig. 4).

Nous avons également constaté que l'instabilité
se manifeste pour un taux d'entrée $\lambda$ supérieur à 1/e ≈
37 % dans tous les cas.

Pour un canal stable, c'est-à-dire une valeur de
$\lambda$ inférieure à 37 %, choisir $p = 1 - \lambda$ confère au canal le
"meilleur" comportement dynamique, en ce sens qu'on maximise
ainsi d et tend à revenir à l'équilibre (caractérisé par un
débit égal au taux d'entrée et un petit nombre de bloqués)
le plus rapidement, à partir d'une situation où un grand
nombre de bloqués se sont accumulés pour une cause quelconque.

Comportement dynamique et temps de recouvrement du canal.

L'étude du comportement dynamique est essentielle
pour deux raisons :

a) Suite à une cause fortuite, un nombre élevé d'utilisa-teurs se mettent à leur console en même temps et émettent leur paquet dans le même intervalle. Il est évident que sans un contrôle efficace, le débit s'annulle et le nombre de bloqués s'accroît en conséquence. Dans quelles condi-tions le système revient-il à l'équilibre et cela au bout de quel temps (temps de recouvrement du canal $τ$) ? Le nombre total de bloqués peut-il décroître et dans quelles conditions ? (Fig. 5)

b) Pour des considérations d'ordre économique ou autre, on est amené à accepter un nombre d'abonnés tel que pendant certaines périodes de pointe, le taux d'entrée $\lambda$ est bien supérieur à 1/e (par exemple $\lambda_{MAX} = 0.8$). Il est clair que, même avec notre contrôle optimal, un
<figure><img src="image_16.png" /><figcaption>Fig. 6</figcaption></figure>
<figure><img src="image_17.png" /></figure>
certain nombre de bloqués vont s'accumuler pendant ce laps de temps. L'évaluation du temps de recouvrement $\tau$ du canal est essentielle pour adopter une politique mixte (PCER) appropriée pendant ces heures critiques.

Par exemple on peut décider que quand le nombre total de bloqués atteint une borne B, l'accès du canal est interdit à tout terminal actif ($\lambda_{MIN} = 0$) ou permis uniquement à un groupe d'utilisateurs actifs prioritaires ($\lambda_{MIN} = 0.1$ par exemple). Le temps de recouvrement $\tau$ est donc a priori fonction de B et de $\lambda_{MIN}$ :

$$ \tau = \tau(B, \lambda_{MIN}). $$

Il est évident que pour un taux $\lambda$ dépendant du temps, il faut une valeur de $p$ dépendant aussi du temps et telle que :

$$ \lambda(t) + p(t) = 1 \quad (\text{Fig. 6}) $$

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

Les prévisions théoriques permettent d'automatiser le processus : on sait qu'à la valeur $\lambda_{MAX}$, le nombre total de bloqués atteint la valeur $B_1$ en un temps $t_1$ et que $\tau(B_1, \lambda_{MIN})$ vaut $\tau_1$ pour des valeurs fixées de $B_1$ et de $\lambda_{MIN}$. On en déduit une règle du genre : pendant les heures de
F197

COMPUTATIONAL RESULTS FOR THE SYSTEMS IN THE PREVIOUS PAGES

<figure><img src="image_19.png" /></figure>
pointe, les non-prioritaires peuvent émettre uniquement pendant la première fraction

$$ \frac{t_1}{t_1 + \tau_1} $$

de chaque minute. La deuxième fraction

$$ \frac{\tau_1}{t_1 + \tau_1} $$

étant réservée aux actifs prioritaires et aux bloqués qui en profitent pour liquider leur paquet arriéré. (Fig.7)

Avec un nombre suffisamment élevé de terminaux bloqués, le trafic du canal constitue lui-même un processus de Poisson et, par conséquent, le nombre total de bloqués décroît linéairement avec le temps. De sorte que $τ$ est donné par :

$$ \tau(B, \lambda_{\text{MIN}}) = \frac{B}{\frac{1}{e} - \lambda_{\text{MIN}}} \quad (\text{Fig. 8}) $$
REFERENCES

[ 1 ] FAYOLLE, G., GELENBE, E., LABETOULLE, J.S., BASTIN, D.
"The stability problem of broadcast packet switching computer
networks", Acta Informatica, Vol. 4, Fasc. 1, 1974, pp. 49-53.

[ 2 ] METCALFE, R.M.
"Steady-state analysis of a slotted and controlled ALOHA system
with blocking", *Proceedings of the sixth Hawaii International Conference
on System Sciences*, University of Hawaii, Honolulu, Janvier 1973.

[ 3 ] ROBERTS, L.G.
"ALOHA Packet System with and without slots and capture", ARPA
Network Information Center, Stanford Research Institute, Menlo Park,
California, ASS Note 8 (NIC 11290), Junin 1972.

[ 4 ] LAM, S., Ph. D. Thesis, Computer Science Dept., UCLA, 1974.

[ 5 ] ABRAMSON, N.
"Packet Switching with Satellites", National Computer Conference,
New York, June 4-8, 1973, *AFIPS Conference Proceedings*, 1973,
Vol. 42, pp. 695-702.

[ 6 ] KLEINROCK, L. and LAM, S.S.
"Packet-switching in a slotted satellite channel", National Computer
Conference, New York, June 4, 1973, *AFIPS Conference Proceedings*,
1973, Vol. 42, pp. 703-710.

[ 7 ] ROBERTS, L.G.
"Dynamic Allocation of Satellite Capacity through Packet Reservation",
National Computer Conference, New York, June 4-8, 1973, *AFIPS
Conference Proceedings*, 1973, Vol. 42, pp. 711-716.

[ 8 ] FELLER, W.
"An introduction to probability theory and its applications", Vol. 1,
J. WILEY and Sons, 1968.

[ 9 ] FAYOLLE, G., GELENBE, E., LABETOULLE, J.
"Stability and controle of packet-switching broadcast channels",
à paraître.

[10] METCALFE, R.W., Ph. D. Thesis, MIT, December 1973.