# Applications de modeles markoviens aux conditions de stabilite dans les systemes informatiques

Paul Caseau, Guy Pujolle

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

## To cite this version:

Paul Caseau, Guy Pujolle. Applications de modeles markoviens aux conditions de stabilite dans les systemes informatiques. [Rapport de recherche] IRIA-RR-238, IRIA. 1977, pp.45. hal-04716450

HAL Id: hal-04716450

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

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

APPLICATIONS
DE MODÈLES MARKOVIENS
AUX
CONDITIONS DE STABILITÉ
DANS LES
SYSTÈMES INFORMATIQUES

Paul CASEAU
Guy PUJOLLE

Rapport de Recherche N° 238

Juin 1977

45p
APPLICATIONS DE MODELES MARKOVIENS
AUX CONDITIONS DE STABILITÉ DANS LES SYSTEMES INFORMATIQUES

Paul Caseau*, Guy Pujolle**

Résumé :

Les systèmes informatiques peuvent souvent être modélisés par des réseaux de files d'attente dans lesquels :

— les stations ont des contraintes de capacité,

— l'entrée du système a lieu par une file unique de capacité infinie.

Ces réseaux peuvent généralement se simplifier sous la forme d'une suite de files d'attente à capacité limitée. Nous étudions ici, les conditions de stabilité d'un certain nombre de réseaux de ce type. Ceci revient encore à déterminer la relation que doit satisfaire le taux des arrivées vers la file d'entrée, pour que cette file n'ait toujours qu'un nombre fini de clients.

Les résultats sont appliqués à l'étude des conditions de stabilité de quelques systèmes informatiques : réseaux d'ordinateurs et systèmes d'exploitation à mémoire virtuelle.

Abstract :

Computer systems are often analysed using queueing networks in which :

— queues have finite buffer size,

— the input in the system takes place by only infinite buffer size queues.

These networks can be decomposed in tandem queues. In this paper we study the conditions of stability in such a decomposed network. This is equivalent to determining the maximum input that available resources can support. We apply our results to two specific systems, namely computer networks and virtual memory operating systems.

<footnote>* Direction des études et recherches - Electricité de France
1, avenue du Général de Gaulle - 92141 - Clamart.</footnote>

<footnote>** IRIA/LABORIA - 78150 Le Chesnay.</footnote>
APPLICATIONS DE MODELE MARKOVIENS

AUX CONDITIONS DE STABILITE DANS LES SYSTEMES INFORMATIQUES

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

## INTRODUCTION

Les systèmes informatiques peuvent souvent être modélisés par des réseaux de files d'attente dans lesquels :

- les stations ont des contraintes de capacité,

- l'entrée du système a lieu par une file unique de capacité infinie.

Ces réseaux peuvent généralement se simplifier sous la forme d'une suite de files d'attente à capacité limitée, en série, et ceci au moyen d'équivalences.

Nous voulons étudier sur ces systèmes, la condition de stabilité, ou encore trouver la relation que doit satisfaire le taux des arrivées vers la file d'entrée, pour que cette file n'ait toujours qu'un nombre fini de clients. Ceci revient à rechercher la charge maximale que peut supporter le réseau.

Nous avons adopté le plan d'étude suivant :

**Première partie** : Charge maximale d'une suite de files d'attente en série.

I - Suite de files markoviennes

II - Temps de service dépendant du nombre de clients

III - Arrivées intermédiaires

IV - Etude de quelques modèles particuliers avec deux stations en série

A - Système $M/M/1 \rightarrow .G/1/N$

B - Système $M/M/1 \rightarrow .M/1/N$ / "Round-robin"

C - Système $M/M/1 \rightarrow .M/1$ / "uniformly bounded virtual waiting time"

D - Système $M/M/1 \rightarrow .M/1$ / "Time-out T"

E - Système $M/M/1 \rightarrow .M/1$ / "Resume Level N, L "

F - Système $M/M/1 \rightarrow .G/K/K$
# Deuxième partie : Applications aux systèmes informatiques

A - Application au taux de charge des réseaux d'ordinateurs.

B - Application à l'étude des performances d'un système d'exploitation à mémoire virtuelle.

C - Application au contrôle de la congestion dans un réseau.

D - Modèles de protocoles.

Le sujet traité ici n'est pas nouveau, et un certain nombre de résultats sont connus, surtout dans le cas de deux files en tandem : Hunt [1], Avi-Itzhak et Yadin [2], Neuts [3], Konheim et Reiser [4] et dans des cas plus généraux : Hildebrand [5], Caseau [6], Lavenberg [7]. Ce que nous voulons ici, c'est donner une méthode plus générale, facilement applicable, et qui contient un grand nombre d'extensions possibles. La généralité se paye par une approximation sauf dans deux cas intéressants : systèmes à 2 files et systèmes avec une infinité de files identiques en tandem.
# PREMIERE PARTIE

## INTRODUCTION

Dans cette première partie, nous décrivons une technique qui permet de déterminer la charge maximale (ou ce qui est équivalent, la condition de stabilité), d'une suite de files d'attente en série comme celle représentée sur la figure 1.

<figure><img src="image_5.png" /><figcaption>Figure 1</figcaption></figure>

Les caractéristiques de cette suite de files d'attente sont les suivantes :

- Le système comprend N files d'attente.

- Les temps de service sont distribués exponentiellement de taux $\mu_n$ pour la n-ième station.

- Les files sont en tandem : les clients sortant du premier service se dirigent vers la deuxième station et ainsi de suite.

- Dans chaque station la discipline de service est premier entré, premier sorti.

- Le nombre de clients dans la file n est limité à $M_n$, n=2,...,N. La première station n'est pas limitée.

- Les interarrivées et les temps de service sont indépendants, et pour un serveur donné ou pour le processus d'interarrivées, ces temps sont identiquement distribués.

Le fait que les stations soient de capacité limitée, introduit un phénomène de blocage : lorsqu'une station atteint son nombre maximum de clients, nous devons déterminer la politique à suivre. Nous définirons les quatre possibilités suivantes :
1 - soit le service se bloque dans l'état plein, jusqu'au moment où une place se libère dans la station suivante,

2 - soit le client recommence son service en entier, jusqu'à ce qu'il puisse rentrer dans la station suivante. (Ce cas correspond dans un réseau d'ordinateurs à un paquet qui est retransmis),

3 - soit le client entre dans le service et le bloque sans être servi,

4 - soit on ne charge pas de nouveaux clients et le service est bloqué dans l'état vide.

On démontre, dans l'annexe , que :

- la règle 3 et la règle 2 sont équivalentes,

- la règle 1 et la règle 4 sont équivalentes, à condition que le nombre de place soit augmenté de 1 pour la règle 4 par rapport à la règle 1,

- les règles 2 (ou 3) et 1 (ou 4) ne sont pas réductibles l'une à l'autre sauf dans les cas où il n'y a que deux stations.

Dans toute la suite de cet article, nous adopterons la règle 2 qui est représentée sur la figure 2.

<figure><img src="image_6.png" /><figcaption>Figure 2</figcaption></figure>

Nous noterons :

- $p_n$, la probabilité qu'un client soit obligé de recommencer son service,

- $\lambda_n$, le taux des clients qui se présente à la station n.
Lorsque le taux d'arrivée des paquets croît, la première file s'allonge pour devenir infinie pour la valeur $\lambda_{max}$.

Nous appelons $\lambda_{max}$ la charge maximale du système. C'est au calcul de cette valeur que cet article est consacré.

# I - CHARGE MAXIMALE D'UNE SUITE DE FILES D'ATTENTE EN SERIE

L'étude de notre système représenté sur la figure 2, se fait station par station. Un service du réseau est remplacé par un serveur sans rebouclage qui lui est équivalent. La distribution du temps de service de la station équivalente est la suivante : (prenons le cas de la station n)

$$h_n(t) = \sum_{l=0}^{\infty} (+ - p_{n+1}) p_{n+1}^l E_{l+1}$$

où $E_{l+1}$ est la distribution d'Erlang d'ordre $l+1$. Cette loi correspond au fait que lorsqu'un paquet est retransmis $l+1$ fois avant le succès, il passe $l+1$ fois dans le service et ceci se produit avec la probabilité $(1 - p_{n+1}) p_{n+1}^l \cdot h_n(t)$ est la distribution de probabilité de la loi exponentielle négative de taux $v_n = \mu_n(1 - p_{n+1})$.

## REMARQUE

Nous avons en présence deux sortes d'intervalle de sortie de la station n :

- les intersorties au point de vue de la station n+1 dont le taux est $\lambda/(1 - p_{n+1})$,

- les intersorties de la station équivalente qui ont pour moyenne $\lambda^{-1}$.

Pour étudier le comportement de la station équivalente, il nous faut connaître la distribution des interarrivées. La condition suffisante donnée par Gelenbe et Muntz [8] pour que les intersorties d'une station soient exponentiellement distribuées est bien vérifiée lorsque les caractéristiques des stations
ne sont pas trop différentes les unes des autres. Deux cas apporterons une
solution exacte: une infinité de files en série et deux files en série.
Dans ce dernier cas comme il doit toujours y avoir un client au service dans
la première station, les interarrivées à la seconde station forment un processus
exponentiel de taux, le taux de service.

Chaque station est donc représentée par un modèle M/M/1/N, c'est-à-dire,
par un modèle :

$$
- \text{à arrivées poissonniennes de taux } \lambda_n = \frac{\lambda}{1 - p_n}
$$

$$
- \text{à temps de service exponentiel de taux } v_n = \mu_n (1 - p_{n+1})
$$

- à un seul serveur

- à un nombre fini de client $N = M_n$.

Les propriétés de ce modèle sont bien connues. On peut calculer facilement
la probabilité P(h) d'avoir h messages en attente ou traitement dans la station :

$$
P(h) = \frac{\rho_n^h}{(1 + \dots + \rho_n^{M_n})}
$$

En particulier, la probabilité que la file d'attente de la station soit
complètement pleine - probabilité que nous avons notée $p_n$ - vaut :

$$
p_n = \frac{M_n}{\rho_n (1 + \dots + \rho_n^{M_n})} = \rho_n \frac{\frac{1 - \rho_n}{M_n + 1}}{1 - \rho_n}
$$

RELATION DE RECURRENCE ET CONDITION DE SATURATION

Le comportement de la station n de notre modèle est caractérisé par le
système d'équations suivant :
$$
(1) \quad \left\{
\begin{array}{l}
\lambda_n = \lambda / (1 - p_n) \\
\nu_n = \mu_n (1 - p_{n+1}) \\
\rho_n = \lambda_n / \nu_n \\
p_n = \rho_n \frac{M_n (1 - \rho_n)}{1 - \rho_n M_{n+1}}
\end{array}
\right.
\quad \text{pour } n=2, \dots, N \quad \text{et} \quad
\left\{
\begin{array}{l}
\lambda_1 = \lambda \\
\nu_1 = \mu_1 (1 - p_2) \\
\rho_1 = \lambda_1 / \nu_1
\end{array}
\right.
$$

Ce système peut se mettre sous la forme très simple * :

$$
(2) \quad \left\{
\begin{array}{l}
Y_n = \frac{\lambda}{\mu_n} G_{n+1}(\rho_{n+1}) = F_n(\rho_n) & n=2, \dots, N \\
\\
Y_N = \frac{\lambda}{\mu_n} F_N(\rho_N)
\end{array}
\right.
$$

$$
\text{avec } F_n(x) = x \frac{1-x}{1-x M_{n+1}} \quad \text{et} \quad G_n(x) = \frac{M_n + 1}{1-x M_n}
$$

On peut, pour $\lambda$ fixé, calculer de proche en proche $Y_N, Y_{N-1}, \dots, Y_n$.
Nous allons montrer que:

a) $Y_n(\lambda)$ est une fonction croissante de $\lambda$,

b) $Y_n(\lambda) = 1$ définit une suite croissante de racines $\lambda_n$,

c) la saturation du système est définie par $\lambda = \lambda_1$, la plus petite des racines, donc par l'équation :

$$
(3) \quad Y_1 = \frac{\lambda}{\mu_1} G_2(\rho_2) = 1 = F(\rho_1 = \infty)
$$

$$
\lambda = \mu_n F_n(\rho_n) / G_{n+1}(\rho_{n+1})
$$

<footnote>* Le système (2) peut-être interprété d'une autre façon qui aurait parfaitement pu être le point de départ de l'étude :</footnote>

<footnote>peut être interprété comme $\lambda = \mu_n (1 - P_{\text{vide}})(1 - P_{\text{blocage}})$ qui est l'équation
de conservation du flux entre les stations n et n+1. $F_n(\rho_n) = 1 - P_{\text{vide}}$ et
$1/G_{n+1}(\rho_{n+1}) = 1 - P_{\text{blocage}}$.</footnote>
a) $Y_n$ est défini à partir de $Y_{n+1}$

$$ Y_n = \frac{\lambda}{\mu_n} G_{n+1}(\rho_{n+1}) \quad \text{fonction croissante de } Y_{n+1} \text{ et de } \lambda $$

$$ \rho_{n+1} = F_{n+1}^{-1}(Y_{n+1}) \quad \text{fonction croissante de } Y_{n+1} $$

Donc si $Y_{n+1}(\lambda)$ est une fonction croissante de $\lambda$, $\rho_{n+1}$ aussi, et $Y_n$ également.

Comme $Y_N(\lambda) = \frac{\lambda}{\mu_n}$ est une fonction croissante de $\lambda$, la propriété est démontrée.

b) $Y_n(\lambda) = 1$ définit une racine $\lambda_n$ et une seule.

Pour $\lambda = \lambda_n - \epsilon$ $Y_n = 1 - \epsilon'$ et donc $\rho_n = F_n^{-1}(1 - \epsilon')$ est arbitrairement grand, ainsi que $Y_{n-1} = \frac{\lambda}{\mu_{n-1}} G_n(\rho_n)$.

Il existe donc une valeur $\epsilon_0$ telle que $Y_{n-1}$ soit plus grand que 1 tandis que $\lambda = \lambda_n - \epsilon_0$ : ce qui prouve que $\lambda_{n-1}$ est strictement inférieur à $\lambda_n$.

La relation (3) définit la racine $\lambda_1$ la plus petite de toutes les racines $\lambda_n$. Ce qui veut dire que

$\lambda < \lambda_n$ : tous les processeurs sont non-saturés : tous les $Y_n < 1$

$\lambda \to \lambda_n$ : le processeur 1 est saturé : c'est toujours le processeur qui se sature le premier.

La relation (3) est donc bien la condition de saturation du système.

Cette condition peut se mettre sous la forme simple

(4) $$ \lambda_{\max} = \mu_1(1 - p_2) \text{ c'est-à-dire que l'on doit avoir } \lambda_2 = \mu_1. $$
Nous emploierons souvent cette condition dans la suite. On résoudra le système (2) par une méthode de tir. Pour $\lambda$ fixé on calculera successivement : $Y_N = \frac{\lambda}{\mu_N}$, $Y_{N-1} = \rho G(F^{-1}(Y_N))...$, $Y_1$, et on trouvera $\lambda_{max}$ comme solution de $Y_1(\rho, N) = 1$.

## ÉTUDE DE QUELQUES CAS PARTICULIERS

### Cas de deux stations en série

A partir de la condition (4) nous obtenons : $\lambda_{max} = \mu_1 \frac{1 - \rho_2}{1 - \rho_2^{M+1}}$.

Comme $\rho_2$ est parfaitement déterminé dans ce système (*) $\rho_2 = \lambda_2/\mu_2 = \mu_1/\mu_2$ nous obtenons :

$$ (5) \quad \lambda_{max} = \mu_1 \frac{1 - \left(\frac{\mu_1}{\mu_2}\right)^M}{1 - \left(\frac{\mu_1}{\mu_2}\right)^{M+1}} $$

ce qui peut se transformer en :

$$ \frac{\lambda}{\mu_2} = F_2(\rho_2) $$

$$ \frac{\lambda}{\mu_1} = \frac{1}{G_2(\rho_2)} $$

et en faisant le quotient :

$$ \frac{\mu_1}{\mu_2} = F_2(\rho_2) = \rho_2. $$

En effet $F(x) \cdot G(x) = x$ est une identité facile à vérifier.

<footnote>(*) L'égalité $\rho_2 = \frac{\mu_1}{\mu_2}$, évidente si on revient aux définitions de $\lambda_2$ et de $\nu_2$ peut également se déduire du système (2) et de la condition (3). Nous n'avons plus que deux équations :</footnote>
$$ (6) \quad \frac{\left(\frac{\lambda_{\max}}{\mu_1}\right)^M - \left(\frac{\lambda_{\max}}{\mu_2}\right)^M}{\left(\frac{\lambda_{\max}}{\mu_1}\right)^{M+1} - \left(\frac{\lambda_{\max}}{\mu_2}\right)^{M+1}} = 1 $$

Dans le cas de stations identiques :

$$ (7) \quad \rho_{\max} = \frac{\lambda_{\max}}{\mu_1} = \frac{M}{M+1} $$

Cas où toutes les stations en série sont identiques

Dans ce cas les fonctions F et G ne dépendent plus de n et nous avons
alors le système :

$$ (8) \quad \left\{ \begin{array}{l} Y_n = \frac{\lambda}{\mu} G(\rho_{n+1}) = F(\rho_n) \qquad 2 \le n \le N-1 \\ \\ Y_N = \frac{\lambda}{\mu} = F_N(\rho_N) \\ \\ Y_1 = \frac{\lambda}{\mu} G(\rho_2) = 1 \end{array} \right. $$

Ce système se résoud, comme nous l'avons vu, par récurrence. Posons $\frac{\lambda}{\mu} = \rho$, on obtient successivement $Y_N = \rho$, $Y_{N-1} = \rho G(F^{-1}(Y_N))$ jusqu'à $Y_1 = Y_1(\rho, N)$. $\rho_{\max} = \frac{\lambda_{\max}}{\mu}$ est alors la solution de l'équation $Y_1(\rho, N) = 1$.

Au paragraphe suivant, un tableau donne pour différentes valeurs de la capacité M et du nombre de station N, la valeur de $\rho_{\max}$.

On peut alors se poser la question suivante : si $N \uparrow \infty$ quelle est la limite $\rho_{\infty}$ de la solution $Y_1(\rho, N) = 1$ ? Nous allons montrer que cette limite est donnée par :

$$ \rho_{\infty} = \left( \frac{M}{M+1} \right)^2 $$
A partir des relations (8), nous pouvons tracer l'algorithme d'obtention
de $\rho_1$, représenté sur la figure 3.

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

On remarque que $F(1) = \frac{M}{M+1}$ et $G(1) = \frac{M+1}{M}$. Il est alors facile de voir que trois cas sont possibles :

- Si $\rho < \left(\frac{M}{M+1}\right)^2$ $F(x)$ et $\rho G(x)$ se coupent : $F(x) = \rho G(x)$ a une racine $x_0$ plus petite que l'unité. Dans ce cas $Y_1(\rho, N)$ sera inférieur à $F(x_0)$, donc à 1: ce qui signifie que $Y_1(\rho, N) = 1$ n'a pas de solutions dans le domaine $\rho < \left(\frac{M}{M+1}\right)^2$
- Si $\rho > \left(\frac{M}{M+1}\right)^2$ $F(x)$ et $\rho G(x)$ ne se coupent pas. Si $\Delta = \min_x \{|F(x) - \rho G(x)|\}$ on voit que $Y_n \ge Y_{n+1} + \Delta$, ce qui montre clairement que pour $N \uparrow \infty$, $Y_1 \uparrow \infty$ et donc que l'équation $Y_1(\rho, N) = 1$ n'a pas de solution dans le domaine $\rho \ge \left(\frac{M}{M+1}\right)^2 + \varepsilon$ quel que soit $\varepsilon$, pour N assez grand.

- Si $\rho = \left(\frac{M}{M+1}\right)^2$ $F(x) = \rho G(x)$ a une racine double $x_0 = 1$. En faisant tendre $\varepsilon$ vers 0 et donc $\Delta$ vers 0- dans le raisonnement précédent on voit que la limite de la solution de $Y_1(\rho, N)=1$, lorsque $N \uparrow \infty$ vaut $\left(\frac{M}{M+1}\right)^2$. En affinant le raisonnement fait, on pourrait obtenir les termes du développement asymptotique en $\frac{1}{N}$.

## Résultats et comparaison avec les cas déjà connus

Les résultats de la méthode développée ici, ont pu être comparés avec ceux d'une méthode exacte par itération sur les matrices stochastiques : CASEAU [6]. Dans tous les cas qui ont pu être traités (inversion de la matrice d'état sur un ordinateur 370/168) l'erreur n'a jamais dépassé $2 \cdot 10^{-2}$. Dans [6], il est en particulier démontré que dans le cas $M=1$ et $\mu=1$, $\rho_{max} = \frac{1}{4} \frac{N+1}{N - \frac{1}{2}}$, $N \ge 1$.

Lorsque $N = +\infty$, $\rho_{max} = 0.25$ ce qui est le résultat obtenu ici. Dans le tableau 1 sont indiqués quelques unes des valeurs obtenues par la méthode développée ici.

D'autres comparaisons sont possibles, mais avec des systèmes n'employant pas la même forme de blocage (blocage 1 ou 4). Il n'empêche que les résultats ne sont que très peu différents. Dans le tableau 2 sont repportés les résultats d'une méthode théorique avec blocage de type 4 : PUJOLLE, POTIER [17]. Dans le cas de deux stations en série où les méthodes de blocage sont équivalentes la condition d'ergodicité est connue depuis plus longtemps : HUNT [1] et NEUTS [3].
<table><thead><tr><th>Nombre de stations</th><th>M=1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><th>2</th><td>0,5</td><td>0,667</td><td>0,75</td><td>0,80</td><td>0,833</td><td>0,857</td><td>0,875</td><td>0,88</td><td>0,90</td><td>0,90</td></tr><tr><th>3</th><td>0,39</td><td>0,569</td><td>0,671</td><td>0,734</td><td>0,777</td><td>0,80</td><td>0,83</td><td>0,84</td><td>0,86</td><td>0,87</td></tr><tr><th>4</th><td>0,33</td><td>0,522</td><td>0,633</td><td>0,708</td><td>0,748</td><td>0,77</td><td>0,79</td><td>0,81</td><td>0,83</td><td>0,85</td></tr><tr><th>5</th><td>0,31</td><td>0,491</td><td>0,604</td><td>0,67</td><td>0,72</td><td>0,76</td><td>0,79</td><td>0,81</td><td>0,83</td><td>0,85</td></tr><tr><th>6</th><td>0,30</td><td>0,471</td><td>0,59</td><td>0,66</td><td>0,71</td><td>0,76</td><td>0,78</td><td>0,81</td><td>0,82</td><td>0,84</td></tr><tr><th>7</th><td>0,29</td><td>0,46</td><td>0,58</td><td>0,65</td><td>0,71</td><td>0,75</td><td>0,78</td><td>0,80</td><td>0,82</td><td>0,84</td></tr><tr><th>8</th><td>0,28</td><td>0,46</td><td>0,57</td><td>0,65</td><td>0,70</td><td>0,75</td><td>0,78</td><td>0,80</td><td>0,82</td><td>0,83</td></tr><tr><th>9</th><td>0,28</td><td>0,45</td><td>0,57</td><td>0,65</td><td>0,70</td><td>0,74</td><td>0,77</td><td>0,80</td><td>0,82</td><td>0,83</td></tr><tr><th>10</th><td>0,27</td><td>0,45</td><td>0,56</td><td>0,65</td><td>0,70</td><td>0,74</td><td>0,77</td><td>0,80</td><td>0,81</td><td>0,83</td></tr><tr><th>20</th><td>0,27</td><td>0,44</td><td>0,56</td><td>0,64</td><td>0,70</td><td>0,74</td><td>0,77</td><td>0,79</td><td>0,81</td><td>0,83</td></tr><tr><th>50</th><td>0,27</td><td>0,44</td><td>0,56</td><td>0,64</td><td>0,70</td><td>0,74</td><td>0,77</td><td>0,79</td><td>0,81</td><td>0,83</td></tr><tr><th>100</th><td>0,26</td><td>0,44</td><td>0,56</td><td>0,64</td><td>0,70</td><td>0,74</td><td>0,77</td><td>0,79</td><td>0,81</td><td>0,83</td></tr><tr><th>=</th><td>0,25</td><td>0,44</td><td>0,56</td><td>0,64</td><td>0,69</td><td>0,75</td><td>0,765</td><td>0,79</td><td>0,81</td><td>0,83</td></tr></tbody></table>

Taux de charge maximale $\rho_{max}$ lorsque la capacité des stations est M.

<table><thead><tr><th>nombre de stations</th><th>M=2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><th>2</th><td>0,666</td><td>0,75</td><td>0,8</td><td>0,833</td></tr><tr><th>3</th><td>0,564</td><td>0,670</td><td>0,734</td><td>0,777</td></tr><tr><th>4</th><td>0,515</td><td>0,631</td><td>0,707</td><td>0,748</td></tr><tr><th>5</th><td>0,486</td><td>0,608</td><td></td><td></td></tr><tr><th>6</th><td>0,467</td><td></td><td></td><td></td></tr></tbody></table>

Table 2

Valeur obtenue dans [17]
## CONCLUSION

La justification de la méthode développée ici provient du fait que l'on peut calculer très facilement le taux de charge maximale dans le cas de nombreuses stations en série avec une capacité de files intermédiaires importante. De plus, dans le cas de deux stations en séries ainsi que dans le cas d'une infinité de stations en série, les résultats obtenus ne sont plus des approximations, mais des résultats exactes. La justification de cette méthode provient encore du fait qu'elle comporte des extensions que nulle autre méthode théorique ne peut pour le moment atteindre. Nous présentons dans les paragraphes suivants quelques unes de ces extensions.

## II - TEMPS DE SERVICE DEPENDANT DU NOMBRE DE CLIENTS

Nous supposons dans ce paragraphe que les temps de service sont toujours exponentiellement distribués, mais qu'ils dépendent du nombre de clients présents dans la station. Le taux de service à la station n est donc maintenant $\mu_n(j)$ s'il y a j clients dans cette station.

Nous pouvons caractériser la station n par le système d'équations suivant :

$$ \text{si } n = 2, \dots, N \text{ et } P_{n+1} = 0 $$

$$ (9) \quad \left\{ \begin{aligned} \lambda_n &= \lambda / (1 - p_n) \\ v_n(j) &= \mu_n(j) (1 - p_{n+1}) \\ \rho_n(j) &= \lambda_n / \mu_n(j) \prod_{j=1}^{M_n} \rho_n(j) \\ p_n &= \frac{1}{1 + \rho_n(1) + \rho_n(1) \rho_n(2) + \dots + \prod_{j=1}^{M_n} \rho_n(j)} \end{aligned} \right. $$
$$ \sin = 1 $$

$$ (10) \left\{ \begin{array}{l} \lambda_1 = \lambda \\ v_1(j) = \mu_1(j)(1 - p_2) \\ \rho_1(j) = \lambda_1 / v_1(j) \end{array} \right. $$

Le système d'équations (9) parait a priori très complexe puisque, pour chaque station on est conduit à introduire M variables $p_n(j)$. Nous allons montrer que l'on peut ramener (9) à un système (9bis) tout à fait comparable aux systèmes (2) ou (8) du pragraphe précédent. Nous ferons cette réduction dans le cas de N stations identiques uniquement parce que les notations sont plus simples : elle est en fait tout à fait générale.

Nous définirons les inconnues principales

$$ v_n = v_n(M) \quad \rho_n = \rho_n(M) = \frac{\lambda_n}{v_n} $$

et nous montrerons que toutes les quantités qui entrent en jeu dans (9) peuvent s'exprimer à partir de $v_n$ et $\rho_n$.

Nous avons vu en effet que

$$ v_n(j) = \mu_n(j)(1 - p_{n+1}) $$

donc :

$$ v_n(j) = \frac{\mu_n(j)}{\mu_n(M)} v_n $$

de même :

$$ \rho_n(j) = \frac{\mu_n(M)}{\mu_n(j)} \rho_n $$
et donc :

$$p_n = \frac{\sum_{1}^{M} \rho_n(j)}{1 + \rho_n(1) + \dots + \sum_{1}^{M} \rho_n(j)} = \frac{B_M \rho_n^M}{1 + B_1 \rho_n + \dots + B_M \rho_n^M}$$

$$\text{Avec } B_j = \frac{[\mu_n(M)]^j}{\mu_n(1) \dots \mu_n(j)}$$

Les coefficients $B_j$ sont indépendants de la charge de la station et peuvent être calculés a priori. Ainsi le système (9) est il équivalent au système (9bis) qui fait intervenir uniquement $v_n, \rho_n$ et $p_n$.

$$ (9bis) \quad \left\{ \begin{array}{l} \lambda_n = \lambda/(1 - p_n) \\[1em] v_n = \mu_n(M)(1 - p_{n+1}) \\[1em] \rho_n = \lambda_n/v_n \\[1em] p_n = \frac{B_M \rho_n^M}{1 + B_1 \rho_n + \dots + B_M \rho_n^M} \end{array} \right. $$

Ce système est tout à fait semblable à celui étudié au paragraphe précédent. Il est donc possible de le mettre sous la forme récurrente :

$$Y_n = \frac{\lambda}{\mu(M)} G(\rho_{n+1}) = F(\rho_n) \quad 2 \le n \le N-1$$

$$Y_N = \frac{\lambda}{\mu(M)} F(\rho_N)$$

$$Y_1 = \frac{\lambda}{\mu(M)} G(\rho_2) = 1$$
## DEMONSTRATION

Nous définirons les fonctions

$$G(x) = \frac{1 + B_1 x + \dots + B_M x^M}{1 + B_1 x + \dots + B_{M-1} x^{M-1}}$$

$$F(x) = \frac{x + B_1 x^2 + \dots + B_{M-1} x^M}{1 + B_1 x + \dots + B_M x^M}$$

L'équation $\rho_n = \frac{\lambda}{\mu(M)} \frac{1}{(1 - p_n)(1 - p_{n+1})}$ s'écrit alors :

$$\frac{\lambda}{\mu(M)} G(\rho_{n+1}) = F(\rho_n)$$

L'interprétation de F et G est d'ailleurs très simple :

$\frac{1}{G(\rho_n)} = 1 - p_{n+1}$, c'est donc la probabilité de blocage du processeur n,

$F(\rho_n) = \frac{1}{\mu(M)} \sum_{j=1}^{M} \mu(j) p_n(j)$, c'est donc le rapport entre le taux moyen du

processeur n (sans blocage) et le taux $\mu(M)$.

L'équation $\lambda = \mu(M) F(\rho_n) \frac{1}{G(\rho_{n+1})}$ est donc une équation de conservation de flux.

Il reste à montrer que F et G ont bien les propriétés qui ont été utilisées pour démontrer que l'équation de saturation est

$$\frac{\lambda}{\mu(\infty)} G(\rho_2) = 1$$

Cette démonstration reposait sur deux propriétés de F et G :

-d'une part, le fait que $F(x)$ et $G(x)$ sont des fonctions croissantes de $x$ propriété dépendant de la suite $B_M$, et que nous supposerons vérifiée.

-d'autre part, le fait que $F(x) \to 1$ si $x \to \infty$.

Or la limite de F lorsque $x \to \infty$ est donnée par le quotient $B_{M-1}/B_M$, c'est à dire par :
$$ \frac{[\mu(M)]^{M-1}}{\mu(1) \dots \mu(M-1)} / \frac{[\mu(M)]^M}{\mu(1) \dots \mu(M)} \quad \text{qui vaut évidemment 1.} $$

La condition de saturation est donc bien

$$ Y_1 = \frac{\lambda_{\max}}{\mu(\infty)} \quad G_2(\rho_2) = 1 $$

ou encore $\frac{\lambda_{\max}}{\mu(\infty)} = 1 - \rho_2$

On résoudra donc (9bis) par une méthode de tir : pour $\lambda$ fixé on calculera successivement :

$$ Y_N = \frac{\lambda}{\mu(\infty)}, \quad Y_{N-1} = \frac{\lambda}{\mu(M)} G[F^{-1}(Y_N)], \dots, Y_1 $$

et on trouvera $\lambda$ comme solution de $Y_1(\lambda, N) = 1$.

Si nous admettons, pour simplifier que $\mu(\infty)$ et $\mu(M)$ ne sont pas différents, nous pouvons prendre $\frac{\lambda}{\mu(M)} = \rho$ comme variable auxiliaire et chercher

$\rho_{\infty} = \text{limite de la solution de } Y_1(\rho, N) = 1 \text{ lorsque } N \uparrow \infty.$

Comme au § précédent on démontre alors que $\rho_{\infty}$ est la valeur qui conduit à ce que l'équation $F(x) = \rho_{\infty}G(x)$ ait une racine double en x. $\rho_{\infty}$ est donc donné par le système

$$ \begin{cases} F(x) = \rho_{\infty} G(x) \\ \\ \frac{d}{dx} F(x) = \rho_{\infty} \frac{d}{dx} G(x) \end{cases} $$

Il est facile de calculer numériquement $\rho_{\infty}$, mais il n'est pas possible d'en donner une expression simple, sauf dans le cas où les $B_j$ sont symétriques, c'es-à-dire où

$$ B_j = B_{M-j} $$
On peut alors montrer que la racine double est $x = 1$ et que $\rho_{\infty}$ vaut simplement $[F(1)]^2$.

## Cas de deux stations en série

La charge maximale est obtenue pour $\lambda_2 = \mu_1(\infty)$ où $\mu_1(+\infty) = \limsup_{i \to \infty} \mu_1(i)$.

$$ (11) \quad \lambda_{\max} = \lambda_2(1 - p_2) = \mu_1(\infty)(1 - p_2) $$

et

$$ (12) \quad p_2 = \frac{\sum_{j=1}^{M} \rho_2(j)}{1 + \rho_2(1) + \rho_2(1) \rho_2(2) + \dots + \rho_2(1) \rho_2(2) \dots \rho_2(M)} \quad \text{avec } \rho_2(i) = \frac{\lambda_2}{\mu_2(i)} = \frac{\mu_1(\infty)}{\mu_2(i)} $$

La valeur du taux maximal des interarrivées est donc :

$$ (13) \quad \lambda_{\max} = \mu_1(\infty) \frac{1 + \frac{\mu_1(\infty)}{\mu_2(1)} + \dots + \frac{[\mu_1(\infty)]^{M-1}}{\mu_2(1) \dots \mu_2(M-1)}}{1 + \frac{\mu_1(\infty)}{\mu_2(1)} + \dots + \frac{[\mu_1(\infty)]^M}{\mu_2(1) \dots \mu_2(M)}} $$

Exemples :

$$ 1 - \text{Si } \mu_1(j) = \mu_2(j) = j \text{ alors } \lambda_{\max} = \mu_2(M) $$

Ce cas correspond au fait que le premier service a une infinité de stations et qu'il ne joue ici qu'un rôle de réservoir pour la seconde station.

$$ - \text{Si } \mu_1(j) = j \text{ pour } j \le M_1 $$

$$ \text{et } \mu_1(j) = M_1 \text{ si } j > M_1 $$
Alors il suffit de remplacer $\mu_1(\infty)$ par $\mu_1(M_1)$ dans la formule.

Ce cas correspond à une première station ayant $M_1$ guichets de service.

2 - Cas de deux stations en série, la première de taux constant, la seconde de taux dépendant du nombre de clients. Soit $\mu_1$ le taux de la première station et $\mu_2(i)$ celui de la seconde. Nous obtenons alors :

$$ (14) \quad \lambda_{\max} = \mu_1 \frac{1 + \frac{\mu_1}{\mu_2(1)} + \dots + \frac{\mu_1^{M-1}}{\mu_2(1) \dots \mu_2(M-2) \mu_2(M-1)}}{1 + \frac{\mu_1}{\mu_2(1)} + \dots + \frac{\mu_1^M}{\mu_2(1) \dots \mu_2(M-1) \mu_2(M)}} $$

si $\mu_1 = 1$ et si $\mu_2(j) = j$ alors $\lambda_{\max} = \frac{1}{2}, \frac{4}{5}, \frac{15}{16}, \frac{64}{65}$ lorsque $M = 1, 2, 3, 4$.

## REMARQUES

Le cas où $\mu_2(j) = j$ pour $1 \le j \le M$ sera traité dans un cas plus général dans le paragraphe IV-F.

## III - FILES D'ATTENTE EN SERIE AVEC DES ARRIVEES AUX STATIONS INTERMEDIAIRES

La même méthode que celle utilisée jusqu'ici, permet l'étude de modèles avec des arrivées aux stations intermédiaires. Soit le modèle représenté sur la figure 4.

<figure><img src="image_8.png" /><figcaption>Figure 4</figcaption></figure>
Les hypothèses sont exactement les mêmes que précédemment auxquelles il faut ajouter les caractéristiques suivantes, pour les clients externes (ceux qui ne vont pas d'un bout à l'autre du réseau) :

- Les interarrivées à la station n, sont indépendantes et identiquement distribuées,

- La loi de probabilité qui sépare deux arrivées successives est la loi exponentielle de taux $\lambda'_n$.

- Les clients externes ressortent du système après le service,

- Un client externe qui trouve une station pleine est rejeté, pour ne plus revenir.

Le nouveau système d'équations régissant la station n est le suivant :

$$ \text{si } n = 2, \dots, K \quad (p_{K+1} = 0) $$

$$ (15) \left\{ \begin{array}{l} \lambda_n = \lambda / (1 - p_n) \\ \\ \nu_n = \mu_n (1 - p_{n+1}) \\ \\ \rho_n = (\lambda_n + \lambda'_n) / \nu_n \\ \\ p_n = \rho_n^{\frac{M}{M+1}} \frac{1 - \rho_n}{1 - \rho_n^{M+1}} \end{array} \right. $$

et

$$ (16) \left\{ \begin{array}{l} \lambda_1 = \lambda \\ \\ \nu_1 = \mu_1 (1 - p_2) \\ \\ \rho_1 = (\lambda_1 + \lambda'_1) \nu_1 \end{array} \right. $$
Avec ces nouvelles hypothèses nous pouvons encore, exactement par les mêmes méthodes que dans les sections précédentes, obtenir les valeurs des taux de charge maximale dans les divers cas (2 stations, infinité de stations identiques, etc...). Nous donnons dans les tableaux suivants 3, 4, et 5, les valeurs des taux de charge maximale dans le cas de stations identiques de temps de service égal à l'unité de temps et tel que les taux des interarrivées intermédiaires soient égaux à $\lambda'$ ($\lambda'_n = \lambda'$, $\forall n \in [1, N]$).

## IV - QUELQUES MODELES AVEC DEUX STATIONS EN SERIE

La méthode utilisée jusqu'à présent est applicable, aux modèles de files d'attente en série qui ont les propriétés suivantes :

- Les interarrivées aux diverses stations sont exponentiellement distribuées (ou une bonne approximation de cette loi) ; ceci suppose généralement une durée de service exponentielle, ou un nombre de serveurs infini, ou un service type "time-sharing", ou encore une discipline de service avec priorité absolue, dernier arrivé, premier sortie.

- La possibilité de calculer la probabilité de rejet. Une méthode approximative, telle celle de Schweitzer et Konheim [9] peut-être utilisée. Le rejet peut d'ailleurs être occasionné par un autre phénomène qu'une limitation de capacité (voir par exemple IV-C).

### A - Système M/M/1 → .G/1/N

La difficulté de l'étude de ce système provient du calcul de la probabilité de dépassement de capacité d'une station M/G/1/N. Une méthode a été développée par Reiser et Kobayashi [10] : appelons $P_N(n)$ la distribution de probabilité de la longueur de la file d'attente dans le cas d'une capacité limitée à N et $\hat{P}(n) = P_\infty(n)$. [10] nous donne :

$$ (17) \quad P_N(n) = \begin{cases} K_N \hat{P}(n) & \text{si } 0 \le n < N \\ 1 - \frac{[1 - K_N(1 - \rho)]}{\rho} & \text{si } n = N \end{cases} $$
<table><thead><tr><th></th><th>N = 2</th><th>N = 3</th><th>N = 4</th><th>N = 5</th></tr></thead><tbody><tr><th>M = 1</th><td>0.40</td><td>0.25</td><td>0.19</td><td>0.15</td></tr><tr><th>M = 2</th><td>0.53</td><td>0.37</td><td>0.31</td><td>0.27</td></tr><tr><th>M = 3</th><td>0.58</td><td>0.44</td><td>0.37</td><td>0.33</td></tr><tr><th>M = 5</th><td>0.63</td><td>0.50</td><td>0.44</td><td>0.40</td></tr><tr><th>M = 10</th><td>0.66</td><td>0.55</td><td>0.51</td><td>0.49</td></tr></tbody></table>

### Tableau 3

Taux de charge maximale de N stations en série, avec M places intermédiaires et $\lambda' = 0.5$

<table><thead><tr><th></th><th>N = 2</th><th>N = 3</th><th>N = 4</th><th>N = 5</th></tr></thead><tbody><tr><th>M = 1</th><td>0.33</td><td>0.17</td><td>0.10</td><td>0.07</td></tr><tr><th>M = 2</th><td>0.43</td><td>0.25</td><td>0.17</td><td>0.13</td></tr><tr><th>M = 3</th><td>0.47</td><td>0.29</td><td>0.20</td><td>0.15</td></tr><tr><th>M = 5</th><td>0.49</td><td>0.32</td><td>0.23</td><td>0.18</td></tr><tr><th>M = 10</th><td>0.50</td><td>0.33</td><td>0.25</td><td>0.19</td></tr></tbody></table>

### Tableau 4

Taux de charge maximale lorsque $\lambda' = 1$

<table><thead><tr><th></th><th>N = 2</th><th>N = 3</th><th>N = 4</th><th>N = 5</th></tr></thead><tbody><tr><th>M = 1</th><td>0.25</td><td>0.08</td><td>0.03</td><td>0.01</td></tr><tr><th>M = 2</th><td>0.31</td><td>0.13</td><td>0.07</td><td>0.03</td></tr><tr><th>M = 3</th><td>0.33</td><td>0.14</td><td>0.08</td><td>0.04</td></tr><tr><th>M = 5</th><td>0.33</td><td>0.14</td><td>0.08</td><td>0.04</td></tr><tr><th>M = 10</th><td>0.33</td><td>0.14</td><td>0.08</td><td>0.04</td></tr></tbody></table>

### Tableau 5

Taux de charge maximale lorsque $\lambda' = 2$
$$ (18) \quad K_N = \frac{1}{1 - \rho[1 - \sum_{n=0}^{N-1} \hat{P}(n)]} $$

$\hat{P}(n)$ est calculé ou peut être trouvé dans un grand nombre de cas (voir Saaty [11] et Cohen [12]). Une expression explicite approchée dans le cas général peut être donnée en utilisant une approximation par les processus de diffusion d'une file M/G/1 : Kobayashi [13], Gelenbe [14]. Nous obtenons à partir de [13]

$$ (19) \quad \hat{P}(n) = \begin{cases} 1 - \rho & \text{si } n = 0 \\ \rho(1 - \hat{\rho})\hat{\rho}^{n-1} & \text{si } n \ge 1 \end{cases} $$

avec $\hat{\rho} = e^{\gamma}$, $\gamma = \frac{2\beta}{\alpha}$, $\beta = \lambda - \mu$, $\alpha = \lambda + K_s \mu$, $\rho = \lambda/\mu$ où $K_s$ est le carré du coefficient de variation du temps de service. Nous obtenons à partir de (17), (18) et (19) :

$$ (20) \quad P_N(N) = 1 - \frac{1 - \rho \hat{\rho}^{N-1}}{1 - \rho^2 \hat{\rho}^{N-1}} $$

Le taux maximal des interarrivées est atteint, avec les notations usuelles, pour $\lambda_2 = \mu_1$. Nous avons donc :

$$ \lambda_{\max} = \lambda_2(1 - \rho_2) = \mu_1(1 - \rho_2) $$

$$ (21) \quad \text{d'où } \lambda_{\max} = \mu_1 \frac{1 - \rho_2 \hat{\rho}_2^{N-1}}{1 - \rho_2^2 \hat{\rho}_2^{N-1}}. $$

Si $\mu_1 = \mu_2 = 1$, appliquant la règle de l'Hospital nous obtenons :

$$ (22) \quad \lambda_{\max} = \frac{K_s + 2N-1}{2K_s + 2N} $$

Si $K_s = 1$, nous retrouvons $\lambda_{\max} = \frac{N}{N+1}$.
## B - Système M/M/1 → .M/1/N Round Robin

La deuxième station a un service distribué par quanta $q$; lorsqu'un client entre au guichet, soit il retourne dans la file d'attente après un temps $q$, soit il est déjà sorti du système à cette époque.

Nous pouvons supposer qu'à l'intérieur du quanta est compté un temps de gestion $\delta$, ("overhead" ou "swap time"), et que le temps total de présence au service est exponentiellement distribué de taux $\mu$. La probabilité de rejet dans ce cas a été calculée par Bhat et Richard [15]. Le taux maximal des intersorties est encore donné par $\lambda_{max} = \mu_1(1 - p_2)$.

Soit $\mu_1 = \mu_2 = 1$, $q = 0.55$ et $\delta = 0.05$ ; le temps effectif de travail par quanta est 0.5, c'est-à-dire qu'il faut en moyenne deux quantas pour effectuer un service. Nous obtenons pour $\lambda_{max}$ ou $\rho_{max}$ les résultats suivants :

<table><caption>Tableau 6</caption><thead><tr><th></th><th>N = 2</th><th>N = 3</th><th>N = 5</th><th>N = 10</th><th>N = 20</th></tr></thead><tbody><tr><th>ρ<sub>max</sub> =</th><td>0.526</td><td>0.588</td><td>0.593</td><td>0.593</td><td>0.593</td></tr></tbody></table>

Il est intéressant de noter que la capacité de la station ne joue pas un rôle important, et que le $\rho_{max}$ obtenu est moins bon que dans le cas premier entré, premier sorti.

## C - Système M/M/1 → .M/1/ "uniformly bounded virtual waiting time"

Nous étudions maintenant un système dans lequel la seconde station n'est pas limitée en capacité. Un client ne peut entrer dans cette seconde station que si son temps de réponse virtuel est inférieur à une valeur donnée $T$, (virtuel
puisqu'il ne le fera peut être pas ; temps de réponse = temps d'attente plus temps de service). La probabilité de rejet a été analysée dans ce cas par Schweitzer et Gavish [16] : posons $b = e^{-\mu T}$ où $\mu$ est le taux de service (exponentiel) et $\gamma(x, y) = \int_{0}^{y} u^{x-1} e^{-u} du$. Alors la probabilité de rejet est donnée par :

$$ (23) \quad p = 1 - E b^{1-\rho} e^{\rho(b-1)} \quad \text{où} $$

$$ (24) \quad E = (1-\rho)[1 - \rho b^{1-\rho} e^{\rho(b-1)} - (\rho b)^{1-\rho} e^{\rho b} [\gamma(\rho,\rho) - \gamma(\rho,\rho b)]]^{-1} $$

E est la probabilité que le système soit vide. Quelques valeurs de $\rho_{max}$ sont données dans le tableau suivant, pour $\mu_1 = \mu_2 = 1$, en fonction de T.

<table><caption>Tableau 7</caption><thead><tr><th></th><th>T = 1</th><th>T = 0.6</th><th>T = 0.4</th><th>T = 0.2</th><th>T = 0.1</th></tr></thead><tbody><tr><th>ρ<sub>max</sub></th><td>0.40</td><td>0.34</td><td>0.28</td><td>0.17</td><td>0.08</td></tr></tbody></table>

Nous avions trouvé pour N = 1, $\rho_{max} = 0.5$ ($\mu_1 = \mu_2 = 1$) ; il faut donc noter que le taux de charge maximale est moins bon en limitant le temps, plutôt que la capacité.

### D - Système M/M/1 → .M/1/ "Time-out T"

Le système est représenté sur la figure 5

<figure><img src="image_9.png" /><figcaption>Figure 5</figcaption></figure>
La première station du système est une file classique M/M/1. La seconde station est également du type M/M/1, mais dans laquelle intervient un time out T (ou temps de séjour maximum). Si, à partir de sa date d'entrée t, le client n'est pas ressorti à la date t + T, il est rejeté à cette dernière date. Lorsqu'un client est rejeté, il est remis dans la première file, soit en début de file d'attente soit en fin de file d'attente. Comme nous supposerons les clients équivalents, ces deux techniques donnent des temps de réponse moyens égaux et des conditions d'ergodicité égales. La probabilité de rejet par time out d'une station M/M/1 avec time out T de taux d'interarrivée λ et de service µ est [26] :

$$ (25) \quad p = 1 - \frac{1 - e^{(\lambda - \mu)T}}{1 - \rho e^{(\lambda - \mu)T}} $$

La condition d'ergodicité du système est $λ_2 = μ_1 = \frac{λ_{max}}{1 - p}$ ce qui donne :

$$ (26) \quad λ_{max} = μ_1 \frac{1 - e^{(μ_1 - μ_2)T}}{1 - \frac{μ_1}{μ_2} e^{(μ_1 - μ_2)T}} $$

$$ (27) \quad \text{Si } μ_1 = μ_2 = μ \text{ on obtient } λ_{max} = \frac{μT}{\frac{1}{μ} + T} ; $$

et si $μ_1 = μ_2 = μ = 1$ on obtient la formule très simple :

$$ (28) \quad λ_{max} = \frac{T}{1 + T} $$

E - Système M/M/1 → .M/M/1/ Resume Level N. L

Nous avons toujours deux stations en série, la seconde de capacité limitée à N. Mais maintenant lorsque la capacité maximale N est atteinte, la seconde station rejette tous les clients arrivants, jusqu'à ce qu'il n'y en ait plus que L. A l'aide des équations de Chapman-Kolmogorov à l'état d'équilibre nous obtenons la probabilité de rejet :
$$ (29) \quad p = 1 - \frac{\sum_{k=0}^{N-L-1} \sum_{j=0}^{N-1-k} \rho^k (1 + \rho + \dots + \rho^j)}{\sum_{k=0}^{N-L} \sum_{j=0}^{N-k} \rho^k (1 + \rho + \dots + \rho^j)} $$

ou

$$ p = 1 - \frac{\sum_{i=0}^{N-L-1} \rho^i - (N-L) \rho^N}{\sum_{i=0}^{N-L-1} \rho^i - (N-L) \rho^{N+1}} $$

Donc dans ce cas :

$$ (30) \quad \lambda_{\max} = \mu_1 \frac{\sum_{i=0}^{N-L-1} \rho_2^i - (N-L) \rho_2^N}{\sum_{i=0}^{N-L-1} \rho_2^i - (N-L) \rho_2^{N+1}} $$

Cette valeur a été obtenue par une nouvelle méthode développée par Lavenberg [7].

Si $\mu_1 = \mu_2 = 1$, nous obtenons :

$$ (31) \quad \rho_{\max} = \frac{N(N+1) - L(L+1)}{N(N+3) - L(L+3)}, $$

ce qui donne le tableau des résultats suivant :

<table><caption>Tableau 8</caption><thead><tr><th></th><th>N = 1</th><th>N = 2</th><th>N = 3</th><th>N = 4</th><th>N = 5</th><th>N = 6</th></tr></thead><tbody><tr><th>L = 0</th><td>0.5</td><td>0.6</td><td>0.66</td><td>0.71</td><td>0.75</td><td>0.78</td></tr><tr><th>L = 1</th><td></td><td>0.66</td><td>0.71</td><td>0.75</td><td>0.78</td><td>0.80</td></tr><tr><th>L = 2</th><td></td><td></td><td>0.75</td><td>0.78</td><td>0.80</td><td>0.82</td></tr><tr><th>L = 3</th><td></td><td></td><td></td><td>0.80</td><td>0.82</td><td>0.83</td></tr><tr><th>L = 4</th><td></td><td></td><td></td><td></td><td>0.83</td><td>0.85</td></tr><tr><th>L = 5</th><td></td><td></td><td></td><td></td><td></td><td>0.86</td></tr></tbody></table>
Cas où la seconde station a un temps de service qui dépend du nombre de clients

Soit $\mu_1$ et $\mu_2(j)$ les taux de service des stations ; alors :

$$ (32) \quad \lambda_{\max} = \mu_1 \frac{\sum_{i=0}^{N-L-1} \sum_{k=0}^{N-L-1} \prod_{j=1}^{k} \{\rho(j)[1 + \rho(1) + \dots + \prod_{j=1}^{k} \rho(j)]\}}{\sum_{i=0}^{N-L} \sum_{k=0}^{N-i} \prod_{j=1}^{k} \{\rho(j)[1 + \rho(1) + \dots + \prod_{j=1}^{k} \rho(j)]\}} $$

F - Système M/M/1 → . /G/K/K

La deuxième station est constituée de K serveurs en parallèle, sans place d'attente intermédiaire. Lorsqu'un client quitte la première file, il ne peut rentrer dans la seconde station que si un guichet est libre. La seconde station avec perte est un modèle étudié par Erlang puis Takacs [18]. A l'état d'équilibre la probabilité que k serveurs soit occupés (ou k clients dans le système) est :

$$ (33) \quad P(k) = \frac{\frac{k}{k!}}{1 + \rho + \frac{2}{2!} + \dots + \frac{K}{K!}} $$

En particulier, la probabilité pour que cette station soit pleine, et donc qu'il y ait rebouclage sur la première station est, :

$$ (34) \quad P(K) = \frac{\rho^K}{K!} / \left(1 + \rho + \dots + \frac{\rho^K}{K!}\right) $$

La condition d'ergodicité du système (ou la charge maximale) est alors obtenue pour $\lambda_2 = \mu_1$ ou encore $\lambda_{\max} = \mu_1(1 - \rho_2)$. C'est-à-dire :

$$ (35) \quad \lambda_{\max} = \mu_1 \left( 1 - \frac{\frac{\rho}{K!}}{1 + \rho + \frac{2}{2!} + \dots + \frac{K}{K!}} \right) \quad \text{avec } \rho = \frac{\mu_1}{\mu_2} $$
Comparons le taux de charge maximale des deux systèmes suivants :

1. La deuxième station est limitée à M avec un seul server de taux $\mu_2$.

2. La deuxième station est composée uniquement de M serveurs de taux $\mu_2/M$.

Ceci peut se traduire par la question suivante : vaut-il mieux répartir les services ou les concentrer ?

Supposons dans un premier temps des lois d'interarrivée et de service exponentielles et $\mu_1 = \mu_2 = 1$. Nous obtenons le tableau de résultats suivant, donnant la valeur de la charge maximale $\rho_{max}$ (égale à $\lambda_{max}$):

<table><caption>Tableau 9</caption><thead><tr><th>Syst.</th><th>M = 1</th><th>M = 2</th><th>M = 3</th><th>M = 4</th><th>M = 8</th><th>M = 10</th></tr></thead><tbody><tr><th>Syst. 1</th><td>0.5</td><td>0.66</td><td>0.75</td><td>0.80</td><td>0.90</td><td>0.91</td></tr><tr><th>Syst. 2</th><td>0.5</td><td>0.6</td><td>0.67</td><td>0.69</td><td>0.77</td><td>0.78</td></tr></tbody></table>

Nous pouvons remarquer que le second système donne de moins bons résultats. Il faut noter que les résultats dans le second cas ne dépendent pas de la distribution des services. Dans le premier système, ils en dépendent fortement comme nous le montrons dans le tableau qui suit où nous avons pris un temps de service qui suit la distribution hyperexponentielle de carré de coefficient de variation 10.

<table><caption>Tableau 10</caption><thead><tr><th>Syst.</th><th>M = 1</th><th>M = 2</th><th>M = 3</th><th>M = 4</th><th>M = 8</th><th>M = 10</th></tr></thead><tbody><tr><th>Syst. 1</th><td>0.5</td><td>0.54</td><td>0.58</td><td>0.61</td><td>0.69</td><td>0.725</td></tr><tr><th>Syst. 2</th><td>0.5</td><td>0.6</td><td>0.67</td><td>0.69</td><td>0.77</td><td>0.78</td></tr></tbody></table>
Dans ce cas le système 2 est meilleur. Il existe un carré de coefficient de variation X = 3 pour lequel si le carré du coefficient de variation x vérifie :

- x < X alors le système 1 est meilleur

- x > X alors le système 2 est meilleur.
# DEUXIEME PARTIE

## APPLICATIONS AUX SYSTEMES INFORMATIQUES

Un grand nombre d'applications aux systèmes informatiques est possible, nous allons nous contenter d'en donner quelques unes.

### A - Application au taux de charge d'un réseau d'ordinateurs

Nous pouvons déterminer maintenant quel est le taux de charge maximale que peut supporter un chemin particulier à l'intérieur d'un réseau d'ordinateurs lorsque les temps de retransmission sont supposés exponentiellement distribués. Ce chemin est modélisé par une suite de stations en série dans lesquelles circulent, de la première vers la dernière file, des paquets dont la longueur est supposée exponentiellement distribuée. La capacité de stockage limitée des files d'attente représente la faculté de mémorisation des mini-ordinateurs qui effectuent la commutation des paquets.

Les valeurs des taux de charge maximale sont directement données dans les différents cas par les tableaux 1 à 5.

### B - Application à l'étude des performances d'un système d'exploitation à mémoire virtuelle

Un système d'exploitation à mémoire virtuelle peut être modélisé par le système de files d'attente représenté sur la figure suivante ( figure 6).
<figure><img src="image_10.png" /><figcaption>Figure 6</figcaption></figure>

Les caractéristiques de ce modèle sont les suivantes :

- le nombre de travaux présents en mémoire principale ne peut dépasser N ;
  le degré de multiprogrammation n doit donc être inférieur ou égal à N.

- si le degré de multiprogrammation est N, les travaux arrivant attendent dans une file d'entrée qu'une place se libère ; il y a blocage des entrées.

- le service de cette première station représente le chargement en mémoire ;
  la distribution de probabilité de ce temps est exponentielle de taux $\mu_1$.

- la boucle de ressource se compose de l'unité centrale (U.C.). Un travail en U.C. peut être interrompu par un défaut de page ou une demande d'entrée-sortie (E/S). La tâche est alors dirigée soit vers le tambour de pagination soit vers l'unité E/S. Le taux de défaut de page, qui détermine la fréquence des transferts du disque de pagination à la mémoire principale est fonction à la fois de l'algorithme de remplacement de page et l'espace disponible en mémoire principale et donc du degré de multiprogrammation. La boucle de
ressource, appelée modèle à serveur central, a déjà par elle même été très étudiée lorsque les temps de service sont tous exponentiellement distribués ; (voir Buzen [19]). Lorsque les probabilités de branchement dépendent de l'algorithme de remplacement de pages et du degré de multiprogrammation des études de la boucle de ressource ont été effectuées dans [20] et [21].

Le modèle étudié ici comporte un blocage du fait de l'introduction d'une file supplémentaire ; de plus c'est un modèle ouvert. Le modèle tel qu'il a été décrit est étudié dans [17].

Dans ce paragraphe, nous étudions une nouvelle politique du contrôle de multiprogrammation. Au lieu de limiter à N seulement le nombre de travaux présents en mémoire principale, nous fixerons une deuxième borne L telle que lorsque le degré de multiprogrammation N est atteint les travaux ne peuvent accéder à la boucle de ressource que lorsque le degré de multiprogrammation est revenu à L ou en dessous. Si $L = N$, nous revenons à un contrôle classique de la multiprogrammation.

La boucle mémoire peut-être remplacée par un serveur équivalent dans le sens suivant : pour que deux systèmes de files d'attente soient équivalents il faut et il suffit que

1) la distribution de probabilité du nombre total de clients dans ces deux systèmes soient identiques,

2) le système global a le même comportement pour l'un ou l'autre des systèmes équivalents.

Les bases de cette théorie de l'équivalence peuvent être trouvées dans Courtois [22], [23] et Avi-Itzhak, Heyman [24]. Dans notre modèle le calcul
du temps de service équivalent est donné dans Badel et al [21], dans le cas où le temps entre deux défauts de page dépend de N, degré de multiprogrammation, par une fonction de vie de Belady. Nous obtenons les valeurs suivantes pour le taux du service équivalent, dans le cas où :

- le taux de service du disque de pagination $\gamma_1 = 200$

- le taux de service des E/S $\gamma_2 = 30$

- le taux de chargement en mémoire est $\mu_1 = 50$

- la localité des programmes $k = 2$

- le nombre de page de mémoire $\eta = 128$

- la fonction de vie de Belady $q = am^k$ ou $a = 10^5$ et $m = \eta/N$

- le temps de calcul moyen en unité centrale est de 1 unité de temps.

<table><thead><tr><th></th><th>j = 1</th><th>j = 2</th><th>j = 3</th><th>j = 4</th><th>j = 5</th><th>j = 6</th><th>j = 7</th><th>j = 8</th><th>j = 9</th><th>j = 10</th></tr></thead><tbody><tr><th>μ<sub>2</sub>(j) =</th><td>0.356</td><td>0.461</td><td>0.532</td><td>0.540</td><td>0.542</td><td>0.538</td><td>0.489</td><td>0.413</td><td>0.337</td><td>0.245</td></tr></tbody></table>

Tableau 12

Nous appliquons alors la formule (35) pour obtenir le taux maximal des interarrivées dans le système ; les valeurs obtenues sont représentées sur le graphique suivant :
<figure><img src="image_11.png" /><figcaption>Figure 7</figcaption></figure>

Le degré de multiprogrammation optimal est obtenu pour $N = 5$ dans les cas $L = N$ et $L = N-1$, et pour $N = 6$ dans le cas $L = N-2$. Il est à noter que en valeur absolue le cas le meilleur est $N = 5$ et $L = 4$, mais l'amélioration n'est que très peu nette. Par contre, il est important de noter que les courbes se déplacent de la gauche à la droite et donc que l'effondement du système met plus longtemps à venir. D'après cet exemple succinct il semble qu'un contrôle de la forme $L,M$ ne soit pas à rejeter et que tout au contraire il soit efficace puisque :

- il simplifie l'introduction des travaux en mémoire,

- il peut augmenter le taux maximal des interarrivées (et donc améliorer le taux d'utilisation de l'Unité Centrale),

- il repousse l'effondrement du système.
## C - Application au contrôle de la congestion dans un réseau

Une des méthodes de contrôle de la congestion dans un réseau d'ordinateurs est de fixer des seuils de congestion au niveau de chaque noeud, qui accélèrent ou arrêtent l'arrivée des paquets. Un exemple simple de réseau est fourni par deux ordinateurs (ou deux hôtes) reliés par un noeud. Nous supposerons que les ordinateurs ont une capacité de mémorisation infinie, et que le noeud intermédiaire peut mémoriser N paquets au maximum. Lorsque le noeud contient N paquets, il n'accepte plus aucun client jusqu'au seuil L. Si $L = N-1$, nous retrouvons un modèle classique.

En général $L < N-1$ ; ceci permet de supprimer un grand nombre de paquets de contrôle entre les noeuds. L'étude des performances de cette méthode de contrôle à seuil peut être menée à partir des résultats du paragraphe IV-E.

Le modèle du paragraphe IV-D peut également servir à étudier les performances d'un réseau dans lequel intervient un "time-out" T.

## D - Modèles de protocoles

Nous présentons dans ce paragraphe deux modèles de protocole. Ces modèles schématisent peut-être trop le phénomène réel, ils sont cependant aptes à fournir certains renseigements importants et parfois révélateurs.

### - protocole "stop and wait"

Nous supposons le noeud composé uniquement d'une ligne de sortie (la commutation étant généralement négligeable), et la longueur des paquets distribuée exponentiellement ou ce qui est équivalent une distribution de temps de retransmission exponentielle de taux $\mu_1$. L'émission s'accompagne d'une recopie du paquet. Lorsqu'un paquet a été émis on attend un acquit
("acknowledgement") avant d'en envoyer un autre. Nous supposerons cette attente de moyenne égale à $\mu_2^{-1}$. Si l'acquit est positif, et ceci arrive avec la probabilité q, la copie est détruite et le message suivant est pris en compte s'il y en a un. Si l'acquit est négatif, alors le paquet est retransmis aussitôt. Nous pouvons modéliser ce protocole par le système de files d'attente suivant :

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

Nous supposons que la superposition des arrivées externes et des paquets réemis, donnent des interarrivées exponentiellement distribuées. Nous supposons également que le temps d'émission moyen est de une unité de temps, et que le temps d'attente d'un acquit est distribué avec une loi d'Erlang 2 de moyenne 1, et que $q = \frac{9}{10}$. Alors la valeur de $\lambda_{max}/q$ est donnée par la formule (25). Nous obtenons $\lambda_{max} = 0.45$.

- protocole MV8

C'est un protocole utilisé dans le réseau à commutation de paquets "Cigale". Dans ce cas il y a 8 canaux virtuels au lieu d'un seul. La transmission des paquets est bloquée dans un canal jusqu'à ce qu'un acquit (acknowledgement) arrive indiquant que la paquet a bien (ou a mal) été reçu dans le noeud suivant.
Le noeud garde une copie du paquet qui est automatiquement retransmise au bout d'une période de temps T (time-out). Ici, nous schématiserons ce protocole en en prenant le modèle ci-joint. Il se compose d'une première file de

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

capacité infinie suivie de 8 places qui représentent les paquets en attente d'un acquit. Lorsque ces 8 canaux sont occupés les transmissions sont bloquées. Nous supposerons qu'avec probabilité q l'acquit est positif et avec la probabilité $1-q$ il est négatif. Dans ce dernier cas il faut retransmettre le paquet.

Nous obtenons d'après le paragraphe IV-F :

$$ \frac{\lambda_{\max}}{q} = \left(1 - \frac{\frac{1}{8!}}{1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \dots + \frac{1}{8!}}\right). \lambda_{\max} = 0.76 \text{ avec } q = \frac{9}{10}. \text{ Il y a donc} $$

une nette amélioration par rapport au protocole "stop and wait".

## CONCLUSION

Les méthodes décrites dans cet article sont tout à fait applicables à bien d'autres systèmes réels dès qu'apparaîssent des capacités limitées, tel le calcul de la production d'un travail mené à la chaîne. Un autre avantage
qui n'est pas du tout exploité ici, consiste en la possibilité de calculer les temps de réponse. Pour tout taux d'arrivées dans la station d'entrée, nous pouvons calculer les temps de réponse de chaque station. Irland et Pujolle [25] utilisent cette propriété pour analyser la capacité optimale des noeuds, dans un réseau à commutation de paquets.

Enfin dans Pujolle [26] une extension, à l'aide des approximations par les processus de diffusion, est faite au cas où les durées de service ont une distribution de probabilité quelconque.
REFERENCES

[1] Hunt G.C. - "Sequential arrays of waiting lines" - Operations Research 4 - 1956.

[2] Avi-Itzhak B. and Yadin M. - "A sequence of two servers with no intermediate queue" - Management Science 11 - 553-563 - 1965.

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

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

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

[6] Caseau P. - "Simulation de processus en série au moyen de modèles markovien" - Rapport E.D.F. HI/2314/00 - 1977.

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

[8] Gelenbe E. and Muntz R.R. - "Probabilistic models of computer systems" - Acta Informatica 7 - 35-60 - 1975.

[9] Schweitzer P.J. and Konheim A.G. - "Buffer overflow calculations using an infinite capacity model" - IBM Research Report RC 5386 - Yorktown Heights - New York - 1975.

[10] Reiser M. and Kobayashi H. - "The effects of service time distributions on system performance" - Proceeding of IFIP 74 - 230-234 - 1974.

[11] Saaty T.L. - "Element of queueing theory" - Mc Graw-Hill - 1961.

[12] Cohen J.W. - "The single server queue" - North-Holland Publishing Company - Amsterdam - 1969.

[13] Kobayashi H. - "Application of the diffusion approximation to queueing networks : Part I" - J. ACM 21, 2 - 316-328 - 1974.

[14] Gelenbe E. - "On approximation computer system models" - J. ACM 22, 2 - 261-269 - 1975.
[15] Bhat U.N. and Richard E.N. - "Busy period analysis of a time-sharing system modeled as a Semi-Markov process" - J. ACM 18 - 221-238 - April 1971.

[16] Schweitzer P.J. and Gavish B. - "The M/M/1 queue with bounded virtual waiting time" - IBM Research Report RC 5561 - Yorktown Heights - New York - 1975.

[17] Pujolle G. et Potier D. - "Réseaux de files d'attente à capacité limitée avec des applications aux systèmes informatiques" - Rapport de Recherche IRIA/LABORIA 219 - Février 1977.

[18] Takacs L. - "Introduction to the theory of queues" - Oxford University Press - New York - 1962.

[19] Buzen J. - "Queueing network models of multiprogramming" - Ph.D. Thesis - Harvard University - 1971.

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

[21] Badel M., Gelenbe E., Leroudier J., Potier D. - "Adaptive optimization of a virtual memory system" - Proceedings IEEE - Special Issue on Interactive Systems - June 1975.

[22] Courtois P.J. - "On the near complete decomposability of networks of queues and of stochastic models of multiprogramming systems" - Carnegie-Mellon University - Computer Science Department - Research Report - November 1971.

[23] Courtois P.J. - "Decomposability, Instabilities, and saturation in multiprogramming systems" - Comm. ACM 18 - 7 - 371-377 - 1975.

[24] Avi-Itzhak B. and Heyman P. - "Approximate models of multiprogramming computer systems" - Operations Research, 21 - 1212-1230 - 1970.

[25] Irland M. et Pujolle G. - "Models of tandem networks of queues motivated by packet switching" - A paraître en Rapport de Recherche IRIA/LABORIA.

[26] Pujolle G. - "Ergodicity conditions and congestion control in computer networks" - Proc. of 2nd International Workshop on Modelling and Performance Evaluation of Computer Systems - Stresa - Italy - October 1976 - et aussi Rapport de Recherche IRIA/LABORIA 190 - Octobre 1976.
# ANNEXE

Cette annexe est empruntée au travail cité en référence [6], dans lequel $M_i = N_i^{MAX} + 1$.

- Les règles ② et ③ sont équivalentes.

On vérifiera très facilement que le décompte des états est exactement le même, et que les transitions sur le processeur $P_{i-1}$ sont identiques si $n_i < N_i^{MAX} + 1$.

Si $n_i = N_i^{MAX} + 1$, la règle ③ interdit les transitions sur $P_{i-1}$, la règle ② autorise une transition qui est sans influence sur la valeur des probabilités.

- Les règles ① et ④ sont équivalentes.

Il nous suffit de démontrer que ④ est équivalent à 4bis , défini de la façon suivante

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

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

Les deux règles ne diffèrent que par l'endroit où on place le message qui a conduit à l'état bloqué. Elles sont donc équivalentes. Mais on voit tout de suite que 4bis n'est autre que ① , avec $N_i^{MAX}$ diminué de une unité.

- Les règles ② et ① ne sont pas équivalentes.

Soit $T_K$ le nombre d'états d'un système de K processeurs. Nous allons calculer $T_K$ pour la règle ② et pour la règle ① .
Pour la règle ②

$$T_2 = N_2^{\text{MAX}} + 2$$

$$T_K = T_{K-1} (N_K^{\text{MAX}} + 2)$$

Pour la règle ①

$T_2 = N_2^{\text{MAX}} + 3$ il y a en effet un état de plus, qui est l'état "P₁ bloqué"

La relation entre $T_K$ et $T_{K-1}$ s'obtient de la façon suivante :

Chaque état de la file $P_1... P_{K-1}$ engendre $(N_K^{\text{MAX}} + 3)$ états tous différents sauf les états où $P_{K-1}$ est vide (car il ne peut y avoir de blocage). Mais si $P_{K-1}$ est vide, le buffer de rang K-1 est vide. Il y a donc évidemment $T_{K-2}$ états de ce type, car tout état de la chaîne $P_1...P_{K-2}$ engendre exactement 1 état de ce type.

Ainsi :

$$T_K = (T_{K-1} - T_{K-2})(N_2^{\text{MAX}} + 3) + T_{K-2}(N_2^{\text{MAX}} + 2) \quad (*)$$

Il n'y a donc pas de correspondance possible entre les deux règles, sauf dans le cas à 2 processeurs. Dans ce dernier cas, en effet on voit que les règles ③ et ④ sont équivalentes puisque leur différence porte uniquement sur le buffer d'alimentation de $P_1$. Comme $P_1$ puise dans une file d'attente infinie (pour le calcul à la saturation) cette différence ne joue aucun rôle.

Une dernière r=marque dcit être faite: en mettant en correspondance les buffers vides et les buffers pleins on peut établir un principe de symétrie valable pour les règles ② et ③. Il n'y a pas de principe analogue pour ① et ④ (preuve supplémentaire de l'irréduc-tibilité). Pour qu'il y ait symétrie -pour la règle 4 bis équivalente à ① et ④- Il faudrait modifier les transitions relatives aux buffers vides et adopter la règle suivante:

> Lorsque s'effectue la transition qui vide le buffer et le processeur $P_{i-1}$, on bloque $P_{i-1}$ dans l'état plein et on ne fait pas passer le message dans le buffer de rang i.