# Etude et simulation de reseaux de diffusion sous contrôle

Banh Tri-An, Erol Gelenbe

► To cite this version:

Banh Tri-An, Erol Gelenbe. Etude et simulation de reseaux de diffusion sous contrôle. [Rapport de recherche] IRIA-RR-206, IRIA. 1976, pp.30. hal-04716356

HAL Id: hal-04716356

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inv-02534 RR206

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

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

ÉTUDE ET SIMULATION
DE RÉSEAUX DE DIFFUSION
SOUS CONTRÔLE

BAHN-TRI-AN
Erol GELENBE

Rapport de Recherche N° 206
Décembre 1976
ETUDE ET SIMULATION DE RÉSEAUX DE DIFFUSION SOUS CONTROLE

Banh-Tri-An

Université de Liège*

Erol Gelenbe

Université Paris-Nord**

RÉSUMÉ

Le contrôle optimal sur un canal de diffusion discrétisé exige la connaissance à tout instant d'une variable d'état difficilement accessible aux mesures. C'est pourquoi, après avoir montré les résultats de simulation où cette variable (en l'occurence, le nombre N de terminaux bloqués) est supposée connue, nous proposons un algorithme de contrôle adaptatif que nous comparerons ensuite avec le contrôle optimal utilisant un estimateur au sens des moindres carrés de N. L'article se termine par une étude du canal amélioré par le captage FM qui permettrait d'accroître considérablement le débit au prix d'une technologie plus sophistiquée.

ABSTRACT

An adaptative procedure for the control of the slotted broadcast channel is proposed and simulated. The experiments show that this algorithm, based on maintaining total channel traffic at its optimal value, results in performance which are close to those of the channel under optimal control. We also define a k-ALOHA mode of operation for the channel and device and simulate its optimal operating procedure.

<footnote>* Service d'Informatique - 59, av. des Tilleuls - Liège (Belgique)</footnote>

<footnote>** Département de Mathématique - Av. J.B. Clément - 93 Villetaneuse (France)</footnote>
# 1. INTRODUCTION.

Nous étudions par simulation aléatoire à événements discrets un modèle de réseau d'ordinateurs utilisant la commutation de paquets sur un canal partagé (semblable à celui actuellement opérationnel à l'Université de Hawaii [4]). On parle d'un réseau de "diffusion" de paquets qui représente un certain nombre d'avantages [3,5] par rapport aux réseaux conventionnels. Nos simulations permettent de valider certains résultats théoriques récents [1,2,3] mais aussi d'aborder certains aspects qui s'étudient difficilement par des modèles mathématiques.

Dans une deuxième partie nous proposons une politique de contrôle adaptatif pour gérer les transmissions de paquets qui permet d'obtenir des performances voisines de celles de la politique optimale [2] sans nécessiter une connaissance parfaite de l'état du canal.

Le fonctionnement du système est montré schématiquement sur la Figure 1. Il s'agit d'un ensemble de terminaux pouvant émettre un paquet aux instants $k = 0,1,2,...$ sur le canal de transmission. L'unité de temps correspond à la durée de transmission des paquets qui ont une longueur constante. Si plusieurs paquets sont émis simultanément, il y a brouillage ou "collision" et les terminaux correspondants entrent dans l'état bloqué.

Un terminal bloqué tentera de retransmettre le même paquet jusqu'au moment où la transmission a lieu avec succès et le terminal rejoint l'état actif. Les terminaux sont supposés agir indépendamment les uns des autres et les retransmissions doivent se faire d'une façon aléatoire.

Soit $X(k)$ le nombre de transmissions de paquet à partir des terminaux actifs à l'instant $k$; $\{X(k)\}_{k \in N^+}$ est une suite de v.a. (variables aléatoires) indépendantes et de distribution commune $C_i = \text{pr}\{X(k) = i\} > 0, i \ge 0, \sum_{0}^{\infty} C_i = 1$.
<figure><img src="image_3.png" /><figcaption>Figure 1.</figcaption></figure>

Soit $N(k)$ le nombre de terminaux bloqués et notons $Y(k)$ le nombre de paquets transmis par ces terminaux à l'instant $k$. Nous supposons que

$$ \mathrm{Pr}(Y(k) | N(1), X(1), \dots, 1 \le k, Y(j), 0 \le j < k) = \mathrm{Pr}(Y(k) | N(k)). $$

Plus particulièrement nous prenons

$$ g_i(n) \triangleq \mathrm{Pr}(Y(k) = i | N(k) = n) = \binom{n}{i} f^i (1-f)^{n-i}, \text{ où } 0 < f < 1. $$

Nous dirons que le système est **instable** si

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

Il a été démontré que le système est instable [1,2,3] et il en résulte la nécessité d'une politique de contrôle sur le canal. Nous adopterons la classification de LAM[5]:

1) PCA, politiques de contrôle sur les arrivées, limitant les accès des terminaux actifs;

2) PCR, politiques de contrôle sur les retransmissions, jouant sur les terminaux bloqués;

3) PCAR, politiques mixtes.
Les résultats suivants ont été établis [1,2,3] :

### Théorème 1.

Soit une politique de contrôle PCR du type $f=f(n)$ où $n$ est le nombre de terminaux bloqués et $f$ la probabilité avec laquelle chaque terminal bloqué retransmet dans chaque unité de temps. Les conditions suivantes sont nécessaires à la stabilité du canal :

$$a) \lim_{n \to \infty} f(n) = 0$$

$$b) \quad \infty > \lim_{n \to \infty} n f(n) > 0$$

### Théorème 2.

Notons $d = \lim_{n \to \infty} [C_O g_1(n) + C_I g_O(n)]$. Le canal est stable si $\lambda < d$ et instable si $\lambda > d$.

Si la variable de contrôle sur laquelle on agit est $f$ et si le critère d'optimisation consiste à maximiser la valeur de $d$, qui est la borne supérieure des taux d'arrivées admissibles $\lambda$, alors on obtient :

### Théorème 3.

La forme optimale de $f(n)$ se présente comme suit :

$$f^*(n) = \frac{C_O - C_I}{nC_O - C_I}$$

## II. RESULTATS DE SIMULATION PSEUDO-ALEATOIRE.

Les résultats numériques suivants ont été obtenus par un simulateur programmé du fonctionnement du système. Les arrivées de paquets à partir des terminaux actifs et bloqués sont simulées par deux générateurs de nombres pseudo-aléatoires indépendants réalisés par la méthode de la fonction
inverse à partir de suites congruentielles linéaires.

L'hypothèse que les terminaux actifs forment une source poissonienne de paramètre $\lambda$ a été retenue; nous avons alors $f^*(n) = (1-\lambda)/(n-\lambda)$ et $d = e^{-1}$.

1) La Figure 2 correspond au cas où $f(n) = f$, constante. Si n atteint un seuil tel que $nf$ est suffisamment supérieur à 1, le trafic du canal devient trop élevé, le débit s'annulle et n croît indéfiniment.

2) La Figure 3 correspond à une fonction $f(n)$ décroissant plus vite que $1/n$ : $f(n) = \frac{D}{n^2}$. Le trafic dans le canal reste inférieur à un et le débit reste inférieur à $\lambda$ sans jamais s'annuler. Les bloqués qui redeviennent actifs sont trop largement compensés par les nouveaux bloqués.

3) La Figure 4 correspond à une fonction $f(n)$ décroissant moins vite que $1/n$ : $f(n) = \frac{D}{\sqrt{n}}$ mais qui vérifie la première condition du théorème 1. L'instabilité s'est manifestée néanmoins d'une façon évidente. Bien que le canal présente un comportement meilleur que le cas "sans contrôle", il est instable avec débit nul.

4) La Figure 5 correspond au cas où le nombre moyen de retransmissions par unité de temps est indépendant de $n$ : $nf(n) = p$. On vérifie que, quel que soit le nombre de terminaux bloqués, le canal reste stable et garde un débit supérieur à $\lambda$, à condition d'avoir des valeurs bien choisies de $p$ et un taux d'entrée $\lambda$ inférieur à $e^{-1}$. On remarque que le canal tend même à se débarrasser des terminaux bloqués quand $\lambda$ reste sensiblement inférieur à $e^{-1}$.

5) La Figure 6 correspond au cas où $\lambda = 0.4 > e^{-1}$. Malgré l'application de la politique optimale $f(n) = \frac{1-\lambda}{n-\lambda}$, le débit du canal reste à $e^{-1}$ et le nombre de terminaux bloqués s'accroît à un taux $(\lambda-e^{-1})$.

6) La Figure 7 sert à étudier le comportement dynamique du canal. On peut en effet y mesurer le temps nécessaire
au canal pour liquider ses $n_0$ terminaux bloqués, sous contrôle optimal. En appelant ce temps le temps de recouvrement $\tau$ du canal, on peut facilement déduire de la décroissance linéaire de n l'expression suivante :

$$ \tau = \tau(n_0, \lambda) = \frac{n_0}{e^{-1} - \lambda} $$

7) La Figure 8 montre l'application éventuelle d'une politique mixte PCAR au canal. Pendant les heures de pointes, les terminaux 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 terminaux actifs prioritaires et aux bloqués qui en profitent pour se débarrasser de leur paquet arriéré. En déterminant $t_1$ et $\tau_1$ par l'expression du temps de recouvrement, nous vérifions sur la courbe & l'exactitude de notre déduction.

### III. UNE POLITIQUE DE CONTROLE ADAPTATIF DU CANAL.

La politique optimale de contrôle du canal (Théorème 3) nécessite une connaissance parfaite de l'état du système. Ceci n'étant pas possible, on peut soit utiliser l'estimateur optimal de $N(k)$ obtenu par SEGALL [6], soit utiliser la procédure adaptative suivante. L'inconvénient principal de l'estimateur de SEGALL est le temps de calcul élevé nécessité par les opérations sur des grandes matrices de transition du modèle; il nécessite aussi une connaissance parfaite des caractéristiques du trafic généré par les terminaux actifs.

Une des variables importantes caractérisant le fonctionnement du système est le trafic total du canal. Nous construisons une suite $\{G(k)\}_{k \in \mathbb{N}^+}$ de v.a. en posant $G(k) = X(k) + Y(k)$, $k \ge 0$. $G(k)$ est le trafic total du canal à l'instant $k$, ou le nombre total de paquets transmis à cet
instant par les terminaux actifs et les terminaux bloqués. Le *trafic conditionnel moyen* est défini par

$$G_n = E[G(k) | N(k) = n]$$

et est indépendant de k. Puisque X(k) est indépendant de Y(1), $0 \le 1 \le k$, et que Y(k) ne dépend que de N(k), nous avons tout de suite que

$$(1) \quad G_n = \lambda + \sum_{i=1}^{\infty} ig_i(n)$$

où $\lambda = \sum_{i=1}^{\infty} ig_i$ est le taux moyen des arrivées de paquets au canal à partir des terminaux actifs.

La politique adaptative que nous proposons est fondée sur le résultat suivant.

### Théorème 1.

En supposant que le canal est géré par la politique optimale de retransmission $f^*(n)$, on obtient

$$(2) \quad G_n = 1 + \lambda - C_1/C_0 + (C_1/C_0^n)(1 - C_1/C_0) + O(1/n^2)$$

Dans le cas où le processus des arrivées des paquets à partir des terminaux actifs est poissonien, on a

$$(3) \quad G_n = 1 + (\lambda/n)(1 - \lambda) + O(1/n^2)$$

Ce résultat s'établit sans trop de difficulté en utilisant (1) et la définition de $y_i(n)$; nous n'en donnerons pas la démonstration.

### Remarque 1.
La forme (2) et (3) de $G_n$ est particulièrement intéressante, car elle indique que pour un nombre n de terminaux bloqués suffisamment grand (dans la pratique $n \ge 10$)
$G_n$ tend vers une constante indépendante de n. Cela facilite l'estimation du trafic total du canal. Dans le cas d'un processus poissonien (voir (3)) pour les arrivées à partir des terminaux actifs, la valeur de $G_n$ s'approche de 1.

Soit $\{f_k\}_{k \in \mathbb{N}^+}$ une suite de v.a. prenant des valeurs dans $[0,1[$ et $\{G(k)\}_{k \in \mathbb{N}^+}$ la suite définie par $G(k) = X(k)+Y(k)$. Nous nous intéressons à un estimateur $\hat{G}(k)$ de l'espérance mathématique de $G(k)$ qui est le nombre de paquets transmis dans la k-ème unité de temps.
Soit $D(k) = 1$ si $G(k) = 0$, sinon $D(k) = 0$, ∀k, et $S(k) = (\sum_{0}^{\infty} D(k-j))/m$, pour $0 < m < \infty$. Prenons $\hat{G}(k) = - \log S(k)$. Si le processus $\{G(k)\}_{k \in \mathbb{N}^+}$ est poissonien et stationnaire alors $S(k)$ est l'estimateur de maximum de vraisemblance de $\text{Pr}\{\hat{G}(k)=0\}$, et $\text{E}\{\hat{G}(k)\} = -\log \text{Pr}\{\hat{G}(k')=0\}$.
Le choix de cette approche est dû au fait que dans la pratique à cause des collisions de paquets, il est impossible de connaître le nombre de paquets transmis dans l'unité de temps si ce nombre est supérieur à un. Le processus $\{f_k\}_{k \in \mathbb{N}^+}$ dépend du processus $\{\hat{G}(k)\}_{k \in \mathbb{N}^+}$ de la façon suivante :

$$f_{k+1} = \begin{cases} f_k / (1 + \delta_2) , & \text{si } \hat{G}(k) > 1 + \epsilon_2 \\ f , & \text{si } 1 + \epsilon_2 \ge \hat{G}(k) \ge 1 - \epsilon_1 \\ f_k / (1 - \delta_1) , & \text{si } \hat{G}(k) < 1 - \epsilon_1 \end{cases}$$

où $\delta_1, \delta_2, \epsilon_1, \epsilon_2 > 0$. La suite $\{f_k\}_{k \in \mathbb{N}^+}$ donne les valeurs que prendra la probabilité de retransmission dans le contrôle adaptatif proposé.

Par rapport au système étudié dans les paragraphes 1 et 2, nous avons maintenant les modifications suivantes.

$$\text{Pr}\{Y(k) | N(l), X(l), f, 0 \le l \le k, Y(j), 0 \le j < k\} \\ = \text{Pr}\{Y(k) | N(k), f_k\}$$

$$\text{où } \text{Pr}\{Y(k) = i | N(k) = n, f_k = f\} = \binom{n}{i} f^i (1-f)^{n-i}.$$
Sur les Figures 9, nous montrons l'évolution du nombre de terminaux bloqués avec la politique optimale et la politique adaptative avec $\epsilon_1 = \epsilon_2 = 0.2$, $\delta_1 = \delta_2 = 0.05$ et $\lambda = 0.3$ (qui est une valeur relativement élevée). Sur le Tableau 1 nous montrons l'influence du paramètre $\epsilon = \epsilon_1 = \epsilon_2$.

Sur la Figure 10 A nous présentons le comportement simulé du canal sous l'effet de la politique de contrôle adaptatif. Sur la Figure 10 B la politique de contrôle utilisée est de la forme

$$f^k = \frac{C_1 - C_0}{N(k)C_0 - C_1}$$

où $\hat{N}(k)$ est le nombre de terminaux bloqués estimés par l'estimateur optimal développé par

SEGALL [6]. C'est-à-dire $\hat{N}(k)$ est obtenu par un filtre récursif et $f^k$, la probabilité de retransmission à l'instant $k$ d'un paquet à partir d'un terminal bloqué, est de la forme donnée par le Théorème 3. On remarque que le choix de $f^k$ n'est pas nécessairement optimal. Il le serait si l'estimation optimale $\hat{N}(k)$ et l'utilisation de $\hat{N}(k)$ dans le contrôle optimal du Théorème 3 menait au contrôle optimal compte tenu de l'incertitude de l'estimation.

Nombre de terminaux bloqués après 2000 unités de temps

<table><thead><tr><th>1-</th><th>1-</th><th>Simulation I</th><th>Simulation II</th><th>Simulation III</th><th>Valeur Moyenne</th></tr></thead><tbody><tr><td>1.0</td><td>1.0</td><td>78</td><td>95</td><td>42</td><td>72</td></tr><tr><td>1.1</td><td>0.9</td><td>42</td><td>112</td><td>140</td><td>98</td></tr><tr><td>1.2</td><td>0.8</td><td>16</td><td>70</td><td>16</td><td>34</td></tr><tr><td>1.3</td><td>0.7</td><td>86</td><td>72</td><td>60</td><td>73</td></tr></tbody></table>
## IV. CONTROLE DU CANAL ALOHA DISCRETISE AMÉLIORE PAR LE CAPTAGE FM.

Dans les paragraphes précédents, nous avons examiné différentes méthodes pour contrôler les retransmissions sur le canal ALOHA discrétisé. Aussi bien dans le cas du contrôle optimal que dans le cas du contrôle adaptatif, l'hypothèse suivante a été retenue : un paquet est reçu avec succès si et seulement si il est le seul à être transmis dans une unité de temps. En appelant débit instantané D le nombre de paquets reçus avec succès sur une unité de temps et trafic instantané T le nombre de paquets transmis dans une même unité de temps, nous avons le diagramme de fonctionnement suivant :

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

Dans le cas où l'on a un décodeur FM à chaque station, la situation peut changer considérablement et l'on distingue les cas suivants :

### 1°) FM-ALOHA

En cas de collision, si le nombre de paquets en présence n'est pas trop grand (c'est-à-dire que le niveau de brouillage n'est pas trop élevé), on arrive à décodeur le signal le plus puissant.

<figure><img src="image_5.png" /></figure>
De la superposition de k paquets, on arrive à débrouiller un.

### 2°) k-ALOHA.

On considère le cas où il n'y a pas de système central et que les noeuds se communiquent entre eux. Pour des raisons de proximité (noeuds voisins se communiquant entre eux préférentiellement), tous les paquets entrant en collision sont décodés correctement tant que celle-ci concerne k paquets ou moins.

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

### 3°) k'-ALOHA.

On considère qu'on arrive toujours à reconnaître jusque k' signaux différents quel que soit le niveau de brouillage.

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

Tous ces modèles peuvent être repris dans une classe plus générale :

#### k-∞-ALOHA.

Tant que la collision se fait entre k paquets ou moins, on arrive à en débrouiller jusque $\ell \ge 1 \le \ell \le k$

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

Calculons le débit $D_n$ quand on a n terminaux bloqués :
$$D_n = \sum_{i=1}^{\ell} \text{Pr} [i \text{ paquets transmis}] + \sum_{i=\ell+1}^{k} \text{Pr}[i \text{ paquets tr.}]$$

$$D_n = \sum_{i=1}^{\ell} \sum_{m=0}^{\ell} b_m a_{i-m} + \sum_{j=\ell+1}^{k} \sum_{m=0}^{\ell} b_m a_{j-m}$$

$$\text{où} \quad \left\{ \begin{array}{l} a_i \text{ = probabilité d'avoir i paquets venant des} \\ \text{terminaux actifs} \\ b_i \text{ = probabilité d'avoir i paquets venant des} \\ \text{terminaux bloqués} \end{array} \right.$$

En posant

$$b_m = 0, \quad \forall m > n$$

$$a_i = 0, \quad \forall i < 0$$

$$D_n = \sum_{i=1}^{\ell} \sum_{m=0}^{\ell} b_m a_{i-m} + \sum_{j=\ell+1}^{k} \sum_{m=0}^{\ell} b_m a_{j-m}$$

Supposons que le trafic dans le canal est poissonien de paramètre G :

$$D_n = \sum_{i=1}^{\ell} i e^{-G \frac{i}{i!}} + \sum_{j=\ell+1}^{k} e^{-G \frac{j}{j!}}$$

Les figures 1 et 2 donnent l'allure de $D_n$ en fonction de G.

k et $\ell$ définissent le système et notre problème se formule comme suit : "étant donné n, choisir f pour maximiser le débit". Nous étudions

$$\frac{\partial D_n}{\partial G} = \sum_{i=1}^{\ell} i \left[ i e^{-G \frac{i}{i!}} - e^{-G \frac{i}{i!}} \right] + \sum_{j=\ell+1}^{k} \left[ j e^{-G \frac{j}{j!}} - e^{-G \frac{j}{j!}} \right]$$
ou

$$ \frac{\partial D_n}{\partial G} = e^{-G[\sum_{i=0}^{\ell-1} \frac{G^i}{i!} - \ell \frac{G^\ell}{\ell!}]} + \ell e^{-G[\frac{G^\ell}{\ell!} - \frac{G^k}{k!}]} $$

D'où, pour maximiser $D_n$ :

$$ \frac{\partial D_n}{\partial G} = e^{-G[\sum_{i=0}^{\ell-1} \frac{G^i}{i!} - \ell \frac{G^k}{k!}]} = 0 $$

Puisque le second facteur est un polynôme en $G$ qui n'a qu'un seul changement de signe dans ses coefficients, le théorème de Descartes stipule qu'il peut y avoir au plus une racine réelle *positive*. Un programme de calculs numériques détermine pour chaque couple de valeurs $(k, \ell)$ d'un système, la valeur $G=G^*$ qui maximise $D_n$ (Figure 3a).

Supposons que le trafic provenant des terminaux actifs soit poissonnien de paramètre $\lambda$. Alors $G = \lambda + nf$. Pour $\lambda$ et $n$ connus, le choix de $G^*$ revient au choix d'un $f^*$.

Dans certains cas simples, on peut même établir l'expression analytique de $G^*$ et de $f^*$ :

1°) FM-ALOHA.

$$ \ell = 1 \quad 1 - \frac{G^k}{k!} = 0 \quad , \quad G^* = (k!)^{1/k} $$

$$ \text{et } f^* = \frac{(k!)^{1/k} - \lambda}{n} $$

2°) k'-ALOHA.

$$ \ell = k' \quad , \quad k = \infty \quad . \text{ On remarque que } \frac{\partial D_n}{\partial G} = e^{-G[\sum_{i=0}^{k'-1} \frac{G^i}{i!}]} > 0 $$

Il faut donc prendre $f^* = 1$, pour que $G$ soit aussi grand que possible pour chaque valeur de $n$.
Des simulations à événements discrets ont été effectuées pour différentes valeurs des paramètres $k$ et $\ell$ et concordent parfaitement avec les résultats montrés sur les Figures 13a et 13b.

- Pour $k = 3, \ell = 1$ et $\lambda = 0.65$, les 100 terminaux initialement bloqués redeviennent actifs au bout de 1200 unités de temps. Ceci correspond approximativement à un débit de 0.75 (Figure 14a).

- Pour $k = 5, \ell = 1$ et $\lambda = 0.80$, les 100 terminaux initialement bloqués redeviennent actifs au bout de 1100 unités de temps. Ceci correspond approximativement à un débit de 0.89 (Figure 14b).

- Pour $k = 2, \ell = 2$ et $\lambda = 0.75$, les 100 terminaux initialement bloqués redeviennent actifs au bout de 1100 unités de temps. Ceci correspond approximativement à un débit de 0.84 (Fig. 14 c)

- Pour $k = 5, \ell = 2$ et $\lambda = 1.5$, les 100 terminaux initialement bloqués redeviennent actifs au bout de 800 unités de temps. Ceci correspond approximativement à un débit de 1.62 (Figure 14d)

V. CONCLUSION.

Nous avons vu dans ce qui précède que le contrôle stochastique, même optimal, ne permettait pas de franchir le seuil 1/e en débit dans un canal ALOHA discrétisé. L'introduction de décodeurs plus performants ainsi que la configuration particulière des communications (caractérisée par une matrice de flux bien particulière : des éléments positifs autour de la diagonale et nuls partout ailleurs) permettent cependant d'envisager des débits bien supérieurs à l'unité. Les simulations semblent confirmer
tous les résultats prévus par calculs numériques sur le modèle.

Néanmoins, dans l'attente d'une réalisation en
vraie grandeur d'un canal k-1 ALOHA, la politique adapta-
tive reste le seul contrôle réaliste en vue de donner des
performances raisonnables à un canal ALOHA discrétisé
classique.

Des conditions suffisantes de stabilité des politiques k-(ALOHA et un critère de stabilité de la politique adaptative que nous proposons sont présentés dans [8].
REFERENCES

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

[2] FAYOLLE, G., GELENBE, E., LABETOULLE, J.,
"Stability and optimal control of the packet switching broadcast
channel", à paraître dans *Journal ACM*.

[3] FAYOLLE, G., Thèse de 3ème cycle, Université de Paris
VI, Novembre 1975.

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

[5] LAM, S., Thèse de Doctorat, Computer Science Dept.,
UCLA, 1974.

[6] SEGALL, A.,
"Recursive estimation from discrete time point processes
with applications to ALOHA-type computer systems",
Electronics Systems Laboratory, Massachusetts Institute
of Technology, ESL-P-591, Février 1975.

[7] BANH TRI AN, GELENBE, E.,
"Performance evaluation of adaptive policies for the
broadcast channel", Proc. IIASA Workshop on Computer
Networks, Septembre 1975.

[8] BANH TRI AN, GELENBE, E., G. PUJOLLE.
"Near optimal behaviour of the broadcast channel",
à paraître.

[9] BANH TRI AN, GELENBE, E.,
"Simulation de politiques adaptatives de contrôle de
réseaux de diffusion", Actes des Journées sur les Commu-
nications par Satellites, IRISA et Ecole Supérieure
d'Electricité. Rennes, Juin 1976.
<figure><img src="image_9.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 4</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 6</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 3</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 5</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 7</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 8</figcaption></figure>
<figure><img src="image_16.png" /></figure>
<figure><img src="image_17.png" /></figure>
<figure><img src="image_18.png" /></figure>
<figure><img src="image_19.png" /><figcaption>Fig. 10 A.
Contrôle adaptatif.</figcaption></figure>
Fig. 10 B.
Contrôle optimal avec l'estimateur de Segall.

<figure><img src="image_20.png" /></figure>
<figure><img src="image_21.png" /></figure>

$K = 10$
<figure><img src="image_22.png" /><figcaption>Figure 12.</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>Figure 13a.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 13b.</figcaption></figure>
<figure><img src="image_25.png" /><figcaption>Figure 14a.</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>Figure 14b.</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>Figure 14c.</figcaption></figure>

TEMPS