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

RÉSEAUX DE
FILES D'ATTENTE
A CAPACITÉ LIMITÉE
AVEC DES APPLICATIONS
AUX SYSTÈMES INFORMATIQUES

Guy PUJOLE
Dominique POTIER

Rapport de Recherche N° 219
Février 1977
RÉSEAUX DE FILES D'ATTENTE A CAPACITÉ LIMITÉE
AVEC DES APPLICATIONS AUX SYSTEMES INFORMATIQUES

Guy Pujolle, Dominique Potier
IRIA/LABORIA

Résumé :

Dans la première partie de cet article, nous présentons des méthodes d'étude de files d'attente en série, avec des stations de capacité limitée. Nous donnons les conditions d'ergodicité de ces systèmes et deux méthodes approchées pour étudier leur comportement à l'état d'équilibre.

Nous appliquons dans la seconde partie les résultats obtenus sur la condition d'ergodicité à l'étude des performances de deux systèmes informatiques :

a) le taux maximal de charge d'un ordinateur à mémoire virtuelle,

b) le coût minimal d'un réseau de transmission de données.

Abstract :

In the first part of this paper, we present methods to study tandem queueing systems having finite capacity constraints. We give ergodicity conditions of these systems and two approximate methods to study their behaviour at steady state.

In the second part, we apply the obtained result on ergodicity to study the performance of two computer systems :

a) the maximal traffic rate of a multiprogrammed virtual memory computer,

b) the minimal cost of a connection in a data-communications network.
RESEaux DE fIlLES D'ATTENTE A CAPACITE LIMITEE
AVEC DES APPLICATIONS AUX SYSTEMES INFORMATIQUES

# I - INTRODUCTION.

Ces dernières années, des efforts considérables ont été prodigués pour
analyser des modèles de systèmes informatiques à l'aide de réseaux de files
d'attente. Ces efforts ont porté sur l'élargissement des hypothèses de façon
à être plus près du réel, telles que la généralisation des temps de service
et des disciplines d'attente ainsi que l'introduction de différentes classes
de clients. L'ensemble de ces nouvelles possibilités est résumé dans un récent
papier de MUNTZ [1]. Cependant, peu d'attention a été portée jusqu'à présent
à l'hypothèse de capacité limitée des différentes files d'attente bien que
cette hypothèse soit essentielle. En effet, presque toutes les files
intervenant dans les phénomènes réels sont finies. Si une file dans un
réseau a une capacité limitée, cela introduit un phénomène de blocage des
stations situées derrière la file qui a atteint sa capacité maximale, et par
conséquent ne permet plus aux files d'être indépendantes les unes des autres.

Les recherches dans cette direction sont importantes puisque les files
d'attente à capacité limitée apparaissent dans la plupart des systèmes
informatiques et des systèmes de communications, et mènent presque toujours
à des situations de blocage. De telles études peuvent permettre de savoir
si l'utilisation d'hypothèses de capacité illimitée peut être faite dans
des cas où une limitation est effective. Elles peuvent également mener à une
meilleure connaissance des problèmes où le blocage se produit.

Quelques études ont déjà été faites sur ce sujet. Le précurseur est
HUNT [2] qui a étudié de cas de 2 ou 3 files en tandem avec serveur
exponentiel et capacité limitée à 1 ou 2 ; puis nous avons les travaux de
SUZUKI [3], MAKINO [4], MORSE [5], et très récemment REISER et KONHEIM [6],
CASEAU [7], CHANG [8] dans le cas exponentiel.
Pour le cas de deux stations en série avec temps de service quelconque, nous avons AVI-ITZHAK et YADIN [9], et dans le cas avec service constant AVI-ITZHAK [10], FRIEDMANN [11], et récemment RUBIN [12, 13], LABETOULLE et PUJOLLE [14].

## Le modèle étudié

Le système de files d'attente que nous allons considérer dans cet article est représenté sur la Figure 1. C'est une suite de K stations en série. Les stations 2,3,...,K ont des capacités limitées à M<sub>2</sub>,M<sub>3</sub>,...,M<sub>K</sub> clients. Quand une unité termine son service à la station i, elle ne peut entrer dans la station suivante que s'il y a de la place (moins de M<sub>i+1</sub> clients) S'il n'y en a pas, le client reste dans la station i et bloque le service jusqu'à ce qu'il puisse rentrer dans la station i+1. Si la station i est bloquée, les services i-1, i-2,...,1 peuvent être bloqués.

Dans notre modèle, la suite des instants d'arrivée des clients au réseau constitue un processus de Poisson de taux b. Nous supposerons encore que les durées de service à la i-ème station sont des variables aléatoires indépendantes, non-négatives et distribuées selon une loi exponentielle négative de taux a<sub>i</sub>.

A un instant t donné, l'état du système est représenté par le vecteur e = (n<sub>1</sub>,n<sub>2</sub>,...,n<sub>K</sub>) où n<sub>i</sub> dénote le nombre d'unités dans la station i à l'instant t. Les clients bloqués sont comptés dans la station où ils doivent rentrer. Donc, nous devons avoir : 0 ≤ n<sub>i</sub> ≤ M<sub>i+1</sub>.

Du aux hypothèses exponentielles le processus (n<sub>1</sub>,n<sub>2</sub>,...,n<sub>K</sub>) est une chaîne de Markov C, qui est évidemment irréductible et apériodique.

Soit p(n<sub>1</sub>,n<sub>2</sub>,...,n<sub>K</sub>) la probabilité d'être dans l'état e lorsqu'il existe un état d'équilibre. S'il existe un tel état d'équilibre, nous devons avoir p(e) > 0 pour tous les vecteurs e possibles et Σ e p(e) = 1.
<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>

## II LES TECHNIQUES DE RESOLUTION

Pour calculer le temps de réponse, la condition d'ergodicité, etc... du modèle présenté dans le paragraphe précédent, il n'existe aucune méthode générale.

Nous décrivons dans les lignes qui viennent les quelques techniques utilisables sur des cas particuliers.

Seul, ou à peu près, le système avec deux files uniquement, a été étudié.

Pour ce modèle représenté sur la Figure 2, nous obtenons, s'il existe un état stable, les équations d'équilibre suivantes :

$$ (1) \qquad \begin{aligned} (b + a_1 + a_2) p(n_1, n_2) &= bp(n_1-1, n_2) + \\ &\quad a_1 p(n_1+1, n_2-1) + a_2 p(n_1, n_2+1) \end{aligned} \\ \text{si } n_1 > 0 \text{ et } M_2+1 > n_2 > 0 \end{aligned} $$
<figure><img src="image_3.png" /><figcaption>Figure 2</figcaption></figure>

$$ (2) \quad (b+a_2) p(0, n_2) = a_1 p(1, n_2) + a_2 p(0, n_2+1) \\ \text{si } n_2 < M_2 + 1 $$

$$ (3) \quad (b+a_2) p(n_1, M_2+1) = b p(n_1-1, M_2+1) + a_1 p(n_1+1, M_2) \\ \text{si } n_1 > 0 $$

$$ (4) \quad (b+a_2) p(0, M_2+1) = a_1 p(1, M_2) $$

Ces équations d'équilibre ne font que refléter les conservations de flux aux noeuds du réseau représenté à la Figure 3.

<figure><img src="image_4.png" /><figcaption>Figure 3</figcaption></figure>
## 2.1 Méthode de résolution exacte (KONHEIM et REISER [6])

Pour résoudre ce système d'équations, KONHEIM et REISER font appel aux fonctions génératrices

$$ (5) \qquad P_j(x) = \sum_{i=0}^{\infty} p(i, j) x^i $$

Nous obtenons alors le système suivant :

(en appelant $\mathcal{P}(x)$ le vecteur $(P_0(x), P_1(x), \dots, P_{M_2+1}(x))$, et $\mathcal{P}_0$ le vecteur $(p(0,0), p(0,1), \dots, p(0,M_2-1))$)

$$ \Gamma \mathcal{P}(x) + \Delta \mathcal{P}_0 = 0 $$

$$ (6) \qquad \Gamma = \frac{1}{x} \left( \begin{array}{c@{\quad}c@{\quad}c} \begin{array}{@{}c@{}} \begin{array}{@{}c@{}} \begin{array}{@{}c@{}} \begin{array}{@{}c@{}} x(\alpha(x) - a_2) & -x & a_2 \\ -a_1 & x\alpha(x) & -x \end{array} & \cdots & -a_1 \\ \multicolumn{3}{@{}c}{\text{pointe de suspension}}} \end{array} & (0) \\ \multicolumn{3}{@{}c}{\text{pointe de suspension}}} \end{array} \end{array} \right) $$

$$ \text{où } \alpha(x) = b(1-x) + a_1 + a_2 $$

$$ (7) \qquad \Delta = \frac{1}{x} \left( \begin{array}{c@{\quad}c} \begin{array}{@{}c@{}} \begin{array}{@{}c@{}} \begin{array}{@{}c@{}} -x & a_1 & -a_1 \\ a_1 & -x & a_1 \end{array} & \cdots & -a_1 \\ \multicolumn{3}{@{}c}{\text{pointe de suspension}} \end{array} & (0) \\ \multicolumn{3}{@{}c}{\text{pointe de suspension}} \end{array} \end{array} \right) $$

d'où la solution symbolique $\mathcal{P}(x) = -\Gamma^{-1}\Delta\mathcal{P}_0$ et $P_j(x) = N_j(x)/D_{M_2+1}(x)$.

Le problème est de trouver $M_2+1$ équations additionnelles pour les paramètres $p(0,0), p(0,1), \dots, p(0,M_2)$.

Une équation est donnée par :

$$ M+1 \sum_{j=0}^{M} P_j(1) = 1 $$
Les autres sont obtenues par le fait que les fonctions génératrices sont
analytiques dans le cercle $|z| < 1$. Donc à chaque racine de $D_{M+1}(x)$ qui se
trouve dans le cercle unité doit correspondre une racine au numérateur $N_j(x)$ ;
chaque racine fournit donc une équation linéaire.

## 2.2 Méthode de résolution par les équilibres globaux

Nous allons donner dans ce paragraphe une méthode plus accessible, mais plus
limitée. Regardons de nouveau la Figure 3, et supposons connus les rapports
suivants entre $p(i,0)$ et $p(i-1,0)$ :

$$q_i = p(i,0)/p(i-1,0) \text{ pour } i = 1, \dots, M_2 + 1.$$

ce qui revient à connaître $p(0, i)$ pour tout $i$ en fonction de $p(0, 0)$.
en écrivant les équations d'équilibre au point $p(0, 1)$ nous obtenons la valeur
de $p(1, 0)$ $[p(0, 1) \to p(1, 0)$ veut dire que la valeur de $p(1, 0)$ est obtenue à
partir de l'équation d'équilibre en $p(0, 1)$. Nous avons :

$$p(0, 2) \to p(1, 1), p(0, 3) \to p(1, 2), \dots, p(0, M_2) \to p(1, M_2-1)$$

$$p(1, 1) \to p(2, 0), p(1, 2) \to p(2, 1), \dots, p(1, M_2-2) \to p(2, M_2-3), \dots$$

Nous obtenons tous les points de la zone $(i,j)$ avec :

$$0 \le j < M_2+1 \qquad 0 \le i \le (M_2+1-j)/2$$

Nous pouvons remarquer que toutes les équations d'équilibre exprimées sont les mêmes que dans le cas où $M_2=+\infty$. Connaissant tous les points de la zone $(i,j)$ décrite, nous pouvons obtenir tous les points du graphe par les relations suivantes :

(supposons $M_2$ pair par exemple)

$$p(0, M_2+1) \to p(1, M_2), p(1, M_2-1) \to p(2, M_2-2), p(M_2/2, 1) \to p(M_2/2+1, 0)$$

$$p(M_2/2 + 1, 0) \to p(M_2/2 + 1, 1), p(M_2/2, 2) \to p(M_2/2, 3)$$

$$p(M_2/2 - 1, 4) \to p(M_2/2 - 1, 5), \dots, p(1, M_2) \to p(1, M_2+1)$$
Maintenant, en augmentant à chaque fois d'un le premier membre des $p(j,k)$, on engendre tous les points du graphe. Donc à partir des $p(0,i)$ $i=0, \dots, M_2+1$, on peut exprimer la valeur de chaque point.

Il nous suffit d'avoir $M_2+2$ relations supplémentaires pour obtenir les valeurs de $p(0,i)$, $i=0, \dots, M_2+1$.

Nous avons déjà $\sum_{i,j} p(i,j) = 1$ et $p(0,1) = \frac{b}{a_2} p(0,0)$.

Les autres sont obtenues à partir des équations (1 à 5) qui nous donnent les relations que doivent vérifier les fonctions génératrices :

$$ (8) \qquad a_1 p_j(1) - a_2 p_{j+1}(1) = a_1 p(0,j), \text{ pour } j=0, \dots, M_2 $$

Cette méthode est évidemment numérique et approchée puisque le nombre d'états est infini. Mais si $\lambda$ n'est pas trop près de la valeur qui provoque la saturation, seuls quelques états peuvent être pris en compte. Pour $M_2=10$, $b/a_1=b/a_2=0.75$ (saturation à partir de 0.90), il suffit de ne prendre en compte que les états $p(i,j)$, $0 \le j \le M_2+1$, $0 \le i \le 20$, pour que $p(20,j)$ soit $10^3$ fois plus petit que $p(0,j)$. Nous n'avons besoin que d'un tableau de 231 valeurs pour obtenir un résultat dont l'erreur relative est inférieure à $10^{-3}$. Si $b/a_1=b/a_2=0.85$ il faut prendre $0 < i \le 40$ pour obtenir une erreur comparable.

Nous nous sommes contentés, à l'aide des deux méthodes décrites jusqu'à présent de calculer les rapports $p(0,j+1)/p(0,j)$. (C'est le point qui nous intéresse pour la suite de cet article).

Ces rapports tendent vers $b/a_2$ lorsque les deux files deviennent indépendantes à l'état stationnaire, c'est à dire lorsque $M_2$ devient infini, ou lorsque le taux d'entrée dans le système devient nul. Au contraire, ces rapports s'écartent le plus possible de $b/a_2$ lorsque $M_2$ est petit et pour un taux de saturation approchant de 1. (Nous avons toujours $p(0,1)/p(0,0) = b/a_2$).
Nous pouvons donc avoir une borne supérieure de l'erreur commise en prenant
$p(0,i+1) / p(0,i)$ égal à $b/a_2$, en regardant le cas où $M_2=1$, et en calculant
le rapport $p(0,2)/p(0,0)$. Celui-ci est aisé à calculer explicitement à l'aide

de la méthode précédente : il vaut
$$ \frac{b^2(b^2 + ba_1 + ba_2)}{a_2^2(2b^2 + ba_1 + ba_2)} $$
et donc l'erreur
relative est : $1 - (b^2 + ba_1 + ba_2)/(2b^2 + ba_1 + ba_2)$.

Compte tenu que la condition de saturation (que nous obtenons dans le paragraphe suivant) est :

$$ \Phi = \frac{\frac{M_2+2}{u_2} - \frac{M_2+2}{u_2+1}}{\frac{M_2+1}{u_2} - \frac{M_2+1}{u_2+1}} = 1 $$
$$ u_1 = a/b_1, \quad u_2 = a/b_2 $$

l'erreur maximale est 19% et décroît très rapidement lorsqu'on s'éloigne de la
condition d'équilibre.

De plus le rapport $p(0,2)/p(0,0)$ dans le cas $M=1$ majore très nettement les rapports $p(0,i+1)/p(0,i)$ pour les cas $M=2,3,...$ qui nous intéressent. Si la condition de saturation est $\Phi=1$, à l'aide des deux méthodes numériques décrites, nous avons pu trouver un écart maximum de 7% lorsque la fonction de saturation vaut $\Phi = 0.95$, et une erreur inférieure à 1% lorsque la condition de saturation est inférieure à 0.75. L'idée donc pour obtenir des formules explicites sera de prendre $p(0,i+1)/p(0,i) = b/a_2$, ce que nous allons faire dans le paragraphe 3.1.

L'erreur calculée sur les résultats donnés par les formules obtenues à partir de l'approximation précédente se révèlera encore bien inférieure à celle des rapports $p(0,i+1)/p(0,i)$.
## 2.3 Etude de deux stations en série par une méthode d'équivalence.

Nous pouvons supposer que le blocage ne s'instaure pas exactement comme nous l'avons décrit précédemment, mais que, lorsque la seconde file atteint M clients, le service à la première station s'arrête. Si nous écrivons alors les équations de balance globale, pour la deuxième station limitée à M + 1 clients, nous retrouvons les expressions (1 à 4). Donc, à partir de l'une ou de l'autre situation de blocage, nous obtenons les résultats pour les deux cas. Prenons donc la nouvelle définition (celle adoptée par KONHEIM et REISER [6]), et soit le réseau représenté sur la Figure 4.

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

Si un client termine son service à la première station et trouve la seconde file pleine, alors il recommence son service à la première station et ce jusqu'à ce qu'il trouve une place dans la station limitée à M clients.

Comme nous avons supposé le premier serveur exponentiel et d'après les propriétés de la distribution exponentielle (pas de mémoire), ce système se comporte exactement comme le système de deux files avec blocage.

Lorsque la seconde station est pleine, les clients qui se présentent sont rejetés, ce qui donne lieu à une probabilité de rejet p.

Pour étudier la première file, nous pouvons prendre une station équivalente dont le temps de service a pour loi :

$$ (9) \qquad h(t) = (1-p) \sum_{n=1}^{\infty} E_n p^{n-1} $$
où $E_n$ est la distribution d'Erlang d'ordre n, de moyenne $n/a_1$.

Le terme $E_n p^{n-1}(1-p)$ représente le fait que le client fait n fois le service de taux $a_1$ avant de pouvoir rentrer dans la station suivante. Donc :

$$ (10) \qquad h(t) = a_1 (1-p) e^{-a_1 (1-p)t} $$

Donc le service équivalent suit une loi exponentielle de taux

$\alpha_1 = a_1(1-p)$. En appelant $F_i(n)$ la probabilité qu'il y ait n clients dans la station i, $i = 1, 2$. Nous avons :

$$ (11) \qquad F_1(n) = u_1^n (1-u_1)^{\alpha_1} \quad \text{où } u_1 = b/a_1 $$

et le temps de réponse $W_1$ de la première station est obtenue par la formule de Little [15] à partir du nombre moyen de clients $E_1$ :

$$ (12) \qquad E_1 = \frac{u_1}{1-u_1} \qquad \text{et } W_1 = \frac{E_1}{b} $$

L'étude de la seconde station nécessite la connaissance de la distribution des interarrivées. Or justement, elle est exponentielle (voir Pujolle [16]) dans notre modèle équivalent. En réalité comme la probabilité de rejet dépend de l'état du système, nous n'avons pas en général exactement un branchement probabiliste au niveau du rebouclage ; c'est l'approximation du modèle équivalent par rapport à la réalité. Cependant dans le cas de saturation, les interarrivées à la seconde station sont exactement exponentielles et nous obtiendrons donc des conditions d'ergodicité exactes.

La probabilité qu'un client soit rejeté est donc égale à la probabilité que la seconde station soit pleine, soit $p= F_2(M)$.

$$ (13) \qquad p = u_2^M \frac{1-u_2}{1-u_2^{M+1}} \qquad \text{et } u_2 = b/a_2 (1-p) $$

Ce système détermine p et nous obtenons :

$$ (14) \qquad F_2(n) = u_2^n \frac{1-u_2}{1-u_2^{M+1}} \quad \text{où} \quad u_2 = b/a_2 (1-p) $$
Le nombre moyen de clients ainsi que le temps de réponse sont donnés par :

$$ (15) \qquad E_2 = \sum_{n=1}^{M} nF(n) \text{ et } W_2 = \frac{E_2}{b}. $$

### III RESOLUTION DU MODELE GENERAL PAR LES METHODES APPROCHEES.

Nous reprenons le modèle général représenté Figure 1 et décrit dans l'intro-duction.

#### 3.1 Calcul d'une solution explicite à l'aide d'une approximation.

Les trois méthodes présentées jusqu'à présent ne donnent pas de formules explicites ; il pourrait être intéressant d'en obtenir même si ce n'est qu'une approximation.

Nous allons maintenant développer une telle méthode qui nous permettra d'obtenir la condition de saturation exacte et les formules explicites qui donnent de bonnes approximations des probabilités du nombre de clients dans la seconde file, ainsi que des temps de réponse moyens de deux stations.

Comme nous l'avons vu dans les résultats du paragraphe 2.2, les rapports

$$ \frac{p(o,i)}{p(o,i+1)}, \quad i=1, \dots, M_2 \text{ sont presque constants et égaux à ceux obtenus dans} $$
le cas où $M_2 = +\infty$

Notre approximation se situera à ce niveau, nous prendrons donc

$$ (16) \qquad \frac{p(o,i)}{p(o,i+1)} = b/a_2 \quad \text{ou} \quad p(o,i) = (b/a_2)^i p(0,0) $$

ce qui revient à admettre les équations de balance locale aux points $(o,i)$. Nous obtenons alors un sytème d'équations entre les fonctions génératrices et $p(o,o)$, qui nous donne des expressions pour la distribution de probabilité du nombre de clients dans la seconde station à l'état d'équilibre, ainsi que $p(o,o)$.

La condition d'ergodicité du système est obtenue en écrivant que $p(o,o) > 0$. De plus, le dénominateur de $p(o,o)$ étant strictement positif, il suffira d'écrire que le numérateur est positif. Or, celui-ci ne faisant pas intervenir les valeurs de $p(o,i)$, la condition d'ergodicité trouvée est une expression exacte.
### 3.1 -a Cas général

Nous n'écrirons les équations de Chapman-Kolmogorov à l'état d'équilibre que pour $0 < n_i < M_i$, $i=1,..., K$.

Les autres cas sont tout aussi faciles à écrire.

$$ (17) \quad \begin{aligned} & (b+a_1 + a_2 + \dots + a_K) \quad p(n_1, n_2, \dots, n_K) = b \ p(n_1-1, n_2, \dots, n_K) \\ & + \sum_{i=1}^{K-1} a_i \ p(n_1, \dots, n_i+1, n_{i+1}-1, \dots, n_K) \\ & + a_K \ p(n_1, \dots, n_i, \dots, n_K+1). \end{aligned} $$

Soit la fonction génératrice :

$$ (13) \quad F_{n_2, n_3, \dots, n_K}(x) = \sum_{n_1=0}^{\infty} F(n_1, n_2, \dots, n_K) x^{n_1} $$

et nous poserons :

$$ (19) \quad F(n_2, \dots, n_K) = F(n_2, n_3, \dots, n_K) \quad (1) $$

$F(n_2 \dots n_K)$ représente la probabilité à l'état d'équilibre qu'il y ait $n_2$ unités dans la station 2, ..., $n_K$ unités dans la station K.

A partir des équations de Chapman-Kolmogorov à l'état d'équilibre, nous obtenons un nouveau système S d'équations linéaires reliant les $F(n_2, \dots, n_K)$ et les probabilités des états frontières pour lesquels il existe au moins un i tel que $n_i = 0$. Ces probabilités des états frontières sont exprimés en fonction de $p(o, o, \dots, o)$ en utilisant les équations de balance locale (c'est notre approximation). Nous complèterons le système S pour qu'il soit de Cramer par les relations suivantes :

$$ (20) \quad \sum_{(n_2, \dots, n_K)} F(n_2, \dots, n_K) = 1, \text{ et} $$

$$ (21) \quad b = a_K \sum_{(n_2, \dots, n_K), n_K > 0} F(n_2, \dots, n_K) \text{ qui n'est autre que l'équation de conservation.} $$
Les solutions de ce système linéaire donnent les probabilités $F(n_2, \dots, n_K)$ et $p(o,o,\dots,o)$. La condition d'ergodicité est obtenue en posant $p(o,o,\dots o) > 0$. Les probabilités de blocage correspondent aux cas ou au moins un $n_i$ vaut $M_i + 1$.

Nous désirons maintenant calculer le temps moyen mis par un client pour traverser l'ensemble du système.

$$ (22) \quad \text{Soit } \hat{F}_{n_i} = \sum_{\{(n_1, n_2, \dots, n_{i-1}, n_{i+1}, \dots, n_K)\}} F(n_2, \dots, n_K) $$

Le nombre moyen d'unités dans la station i est alors donné par :

$$ (23) \quad K_i = \sum_{n_i=0}^{M_i} n_i \hat{F}_{n_i} + M_i \hat{F}_{M_i+1} \quad i=2,3,\dots,K $$

Ces valeurs peuvent être calculées à partir des probabilités $F(n_2, \dots, n_K)$.
Pour rechercher le nombre moyen d'unités dans la première station, nous
utiliserons les dérivées des fonctions génératrices :

$$ (24) \quad F_{n_2, \dots, n_K}(x) = n_1 F(n_1, \dots, n_K) x^{n_1-1} $$

et nous poserons :

$$ (25) \quad F'(n_2, \dots, n_K) = F' n_2, \dots, n_K \quad (1) $$

Le nombre moyen de clients dans la première station est alors de :

$$ (26) \quad K_1 = \sum \{(n_2, \dots, n_K)\} F'(n_2, \dots, n_K) $$

Le calcul de $K_1$ se fait en prenant le système d'équations, en fonction de $F_{n_2, \dots, n_K}(x)$ et $p(o,o,\dots,o)$ obtenu à partir des équations de Chapman-Kolmogorov à l'état d'équilibre. Nous pouvons mettre ce système sous la forme :

$$ A(x) \cdot F(x) = B(x) $$
où $F(x)$ est le vecteur de composants $F_{n_2, \dots, n_K}(x)$, et où $A(x)$ et $B(x)$ sont la matrice et le vecteur des coefficients du sytème. En dérivant deux fois, nous obtenons

$$ (27) \qquad A''(x) F(x) + 2 A'(x) F'(x) + A(x) F''(x) = B''(x) $$

Les relations obtenues à partir des équations de Chapman-Kolmogorov n'étant pas indépendantes, nous avons det $A(x)=0$. Il existe donc un vecteur ligne V tel que $VA = 0$. En multipliant par V nous obtenons une équation supplémentaire :

(28) $2 VA'(x) F'(x) = V [B''(x) - A''(x) F(x)]$, qui nous permet d'avoir un système de Cramer en faisant $x=1$. Les $F'(n_2, \dots, n_K)$ sont les solutions de ce système.

Le nombre moyen de clients dans l'ensemble du système est alors :

$$ E = \sum_{i=1}^{K} K_i \text{ et le temps de réponse moyen vaut : } W = E/b \text{ par la formule de Little.} $$

### 3.1 -b Résultats pour un système de deux stations.

Posons $u_1 = b/a_2$ et $M = M_2$ nous avons le résultat suivant :

$$ \left[ \text{Théorème 1. La condition d'ergodicité est} \right. \\ \left. \psi(u_1, u_2) = \frac{\frac{u_2^{M+2} - u_1^{M+2}}{u_2^{M+1} - u_1^{M+1}}}{\frac{u_2^{M+2} - u_1^{M+2}}{u_2^{M+1} - u_1^{M+1}}} < 1 \right. $$

Si la condition du théorème est réalisée, alors :

$$ (29) \qquad P(o,o) = \frac{1}{D} \left[ \frac{1}{u_1^{M+1}} - \frac{1}{u_2^{M+1}} \right] \left[ 1 - \psi(u_1, u_2) \right] $$
$$ (30) \quad F(0) = 1 - u_2 $$

$$ (31) \quad F(p) = \frac{1}{D} u_2^p \quad \frac{1}{1-u_1} \left[ \frac{1-u_2}{u_1^{M+1}} - \frac{1-u_1}{u_2^{M+1}} - \frac{u_1-u_2}{u_1^p} \right] $$

avec

$$ (32) \quad D = \frac{1}{u_1^{M+1}} \times \frac{1-u_1^{M+2}}{1-u_1} - \frac{1}{u_2^{M+1}} \times \frac{1-u_2^{M+2}}{1-u_2} $$

Lorsque $u_1=u_2=u$ ; la condition d'équilibre est donnée par :

$$ (33) \quad u < \frac{M+1}{M+2} \quad \text{et nous avons} $$

$$ (34) \quad F(p) = (1-u) \frac{u^{M+2} + u^p [M+1 - u(M+2)]}{u^{M+2} + M+1 - u(M+2)} , \quad p=0, \dots, M+1 $$

Cette condition d'ergodicité dans le cas général a déjà été obtenue par Neuts [24] sous la forme : $\frac{1}{b} > \frac{1}{a_1} + \frac{1}{a_2} \theta_{M+1}$

où

$$ (35) \quad \left\{ \begin{array}{ll} \theta_{M+1} = \frac{1 - a_2 / a_1}{1 - a_2^{M+1} / a_1^{M+1}} & \text{si } a_1 \neq a_2 \\ \\ \theta_{M+1} = 1 / (M+1) & \text{si } a_1 = a_2 \end{array} \right. $$

La condition d'équilibre a été représentée sur la Figure 5 comme fonction de $u_1$ et $u_2$ pour différentes valeurs de M.

Une approximation de la probabilité de blocage est donc $F(M+1)$ qui vaut :

$$ (36) \quad F(M+1) = \frac{1}{D} \left[ \left( \frac{u_2}{u_1} \right)^{M+1} - 1 \right] \quad \text{si } u_1 \neq u_2 $$

$$ \text{et} \quad F(M+1) = (1-u)^2 \frac{(M+1) u^{M+1}}{u^{M+2} + M+1 - u(M+2)} \quad \text{si } u_1 - u_2 = u $$
Ces résultats sont illustrés sur la Figure 6 où la probabilité de blocage $F(M+1)$ est calculée en fonction de M pour différentes valeurs de $u_2$, et $u_1$ fixé.

Nous obtenons encore les résultats suivants :

$$ (37) \quad \text{i)} \quad K_1 = \frac{u_1^{M+2} - u_2^{M+2} - (u_1-u_2) \left[ u_1^{M+1} F(M+1) - (1-u_1) C \right]}{u_1^{M+1} (1-u_1) - u_2^{M+1} (1-u_2)} $$

$$ \text{où} \quad C = \sum_{p=1}^{M} u_{1}^{M-p+1} F(p) z_{p} + u_{2} F(M+1) z_{M} $$

$$ \text{et} \quad z_p = \frac{1}{(u_1 - u_2)^2} \{ u_1^{p+1} - u_2^p \left[ (p+1)u_1 - p u_2 \right] \} , \quad p=1, \dots, M $$

$$ (38) \quad \text{ii)} \quad K_2 = \sum_{p=1}^{M} p F(p) + M F(M+1) $$
<figure><img src="image_6.png" /><figcaption>Condition d'équilibre en fonction de u₁ et u₂</figcaption></figure>

Figure 5
<figure><img src="image_7.png" /><figcaption>Probabilité de blocage

Figure 6</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Nombre moyen de clients dans le système
Figure 7</figcaption></figure>
(39) iii) Le nombre moyen d'unités dans le système E et le temps de réponse moyen W sont donnés par

$$E = K_1 + K_2 \qquad W = E/b$$

(40) iii) Si $u_1 = u_2 = u$ et $u < \frac{M+1}{M+2}$

$$K_1 = \frac{u(M+2) - F(M+1) - (1-u)C'}{M+1 - u(M+2)}$$

$$C' = \sum_{p=1}^{M} \frac{p(p+1)}{2} F(p) + \frac{M(M+1)}{2} F(M+1)$$

Quelques valeurs du nombre moyen E de clients dans le système, sont données sur le graphique de la Figure 7, en fonction de $u_2$, pour différentes valeurs de M, et $u_1$ fixé.

Ces courbes montrent que les valeurs obtenues dans le cas où $M = +\infty$ sont pratiquement atteintes pour $M = 9$.

Nous comparons dans le tableau 3 quelques résultats obtenus par cette méthode dans le cas de deux files et référencé par A (approximation) avec ceux obtenus par la méthode par équivalence paragraphe 2.3 et référencé par E (équivalence).

Dans tous les cas testés, la différence est restée en dessous de 3 %.
<table><caption>Tableau 8</caption><thead><tr><th rowspan="2">u<sub>1</sub> = 0,5</th><th colspan="2">M=1</th><th colspan="2">M=2</th><th colspan="2">M=5</th></tr><tr><th>A</th><th>E</th><th>A</th><th>E</th><th>A</th><th>E</th></tr></thead><tbody><tr><td rowspan="2">u<sub>2</sub>=0.1</td><td>E<sub>1</sub></td><td>1.030</td><td>1.018</td><td>1.003</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>E<sub>2</sub></td><td>0.1</td><td>0.1</td><td>0.11</td><td>0.1099</td><td>0.111</td><td>0.111</td></tr><tr><td rowspan="2">u<sub>2</sub>=0.3</td><td>E<sub>1</sub></td><td>1.316</td><td>1.272</td><td>1.082</td><td>1.052</td><td>1.002</td><td>1.001</td></tr><tr><td>E<sub>2</sub></td><td>0.3</td><td>0.3</td><td>0.337</td><td>0.336</td><td>0.427</td><td>0.427</td></tr><tr><td rowspan="2">u<sub>2</sub>=0.5</td><td>E<sub>1</sub></td><td>2.3</td><td>2.241</td><td>1.4702</td><td>1.4664</td><td>1.0508</td><td>1.0313</td></tr><tr><td>E<sub>2</sub></td><td>0.5</td><td>0.5</td><td>0.7353</td><td>0.7282</td><td>0.9579</td><td>0.903</td></tr><tr><td rowspan="2">u<sub>2</sub>=0.7</td><td>E<sub>1</sub></td><td>7.711</td><td>7.586</td><td>3.179</td><td>3.1693</td><td>1.516</td><td>1.470</td></tr><tr><td>E<sub>2</sub></td><td>0.7</td><td>0.7</td><td>1.157</td><td>1.352</td><td>1.879</td><td>1.8078</td></tr><tr><td rowspan="2">u<sub>2</sub>=0.9</td><td>E<sub>1</sub></td><td>Condition d'ergodicité non satisfaite</td><td></td><td>48.428</td><td>46.911</td><td>7.381</td><td>7.189</td></tr><tr><td>E<sub>2</sub></td><td></td><td></td><td>1.640</td><td>1.6339</td><td>3.474</td><td>3.2443</td></tr></tbody></table>

### 3.1 -c Condition d'ergodicité d'un système de deux stations, le second service dépendant du nombre de clients dans la station.

Dans ce paragraphe, nous supposerons que $a_2$ dépend du nombre de clients présents dans la station : $a_2=a_2(n_2)$.

Si cette station provoque le blocage de la première file, alors nous prendrons $a_2=a_2(M+1)$, qui pourra être identique ou non à $a_2(M)$.

Nous poserons $u_2(i) = b/a_2(i)$ et

$$ (41) \quad S(M+1) = u_1^{M+1} + u_1^M u_2(1) + u_1^{M-1} u_2(1) + \dots + u_2(1) u_2(2) + \dots + u_2(1) u_2(2) + \dots + u_2(M+1) $$
**Théorème 2** : La condition d'ergodicité du système lorsque la seconde station est limitée à M est la suivante :
$$ \psi(M) = S(M+1)/S(M) < 1 $$

**Démonstration.** Le système d'équations obtenu à partir des équations de Chapman-Kolmogorov est le suivant :

$$ (42) \quad \left\{ \begin{array}{l} a_1 F_0 - a_2(1) F_1 = a_1 p(0,0) \\ a_1 F_1 - a_2(2) F_2 = a_1 p(0,1) \\ a_1 F_2 - a_2(3) F_3 = a_1 p(0,2) \\ a_1 F_M - a_2(M+1) F_{M+1} = a_1 p(0,M) \end{array} \right. $$

Les deux équations supplémentaires sont :

$$ (4\zeta) \quad \sum_{i=0}^{M+1} F_i = 1 \quad \text{et} \quad b = a_2(1)F_1 + a_2(2)F_2 + \dots + a_2(M+1)F_{M+1} $$

De l'ensemble de ces relations nous pouvons tirer le numérateur de $p(0,0)$ sans avoir à connaître $p(0,i)$, $i=1,..., M$, ce qui nous donne la condition d'ergodicité en le prenant positif.

Exemple : si $a_2(i) = ia_2$ pour $i=1,..., M$ et $a_2(M+1) = a_2(M)$, alors si $M=2$ nous obtenons $u < 4/5$, si $M=3$ $u < 15/16$, si $M=4$ $u < 64/65$.

### 3.1 -d Résultats pour des systèmes de plus de deux stations et de quelques cas spéciaux.

Dans ce paragraphe, nous nous sommes particulièrement intéressés à la condition d'ergodicité des systèmes pour deux raisons :

1. Les résultats obtenus sont des valeurs exactes.

2. Ils sont obtenus plus aisément que les temps de réponse.
Dans le cas de trois stations en série avec $M_2 = M_3 = 1$ nous avons obtenu :

$$ (44) \quad \left[ \begin{array}{l} \text{Théorème 3 : La condition d'ergodicité pour le système de trois stations en série avec } M_2 = M_3 = 1 \text{ est donnée par} \\ \Phi(u_1, u_2, u_3) < 1 \quad \text{où } u_i = \frac{b}{a_i}, i = 1, 2, 3. \end{array} \right. $$

$$ (45) \quad \Phi(u_1, u_2, u_3) = \frac{(u_1^2+u_1 u_2+u_2^2)(u_2^2+u_2 u_3+u_3^2)(u_1^3+u_1^2 u_3+u_1 u_3^2+u_3^3)+\Psi(u_1, u_2, u_3)}{(u_1+u_2)(u_2+u_3)[v_2(u_1+u_3)^3+u_1 u_3(u_1^2+u_1 u_3+u_3^2)]} $$

$$ (46) \text{ et } \Psi(u_1, u_2, u_3) = u_1(u_1+u_2)^3+u_3(u_3+u_2)^3+3 u_1 u_3(u_1^2+u_1 u_3+u_3^2) \\ +u_3^3(u_1+u_3)+5 u_1 u_2 u_3(u_1+u_2+u_3) $$

Cette condition a déjà été trouvée par Hunt [2] sous une autre forme. Dans le cas où $u_1 = u_2 = u_3 = u$ nous obtenons la condition

$$ u < \frac{22}{39} $$

Dans le cas où notre réseau a plus de trois files d'attente, il est possible, toujours par la même méthode, de determiner la valeur du taux des arrivées qui provoque la saturation. Nous nous sommes restreint au cas où toutes les stations sont identiques $u=b/a_i$, $i=1, \dots, K$ (K est le nombre total de stations) et où M est le nombre maximum de clients autorisés dans les stations 2, \dots, K. Nous donnons ces valeurs dans le tableau 9.
<table><thead><tr><th>K<br>M</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>0,666</td><td>0,564</td><td>0,514</td><td>0,485</td><td>0,466</td></tr><tr><td>2</td><td>0,750</td><td>0,670</td><td>0,631</td><td>0,607</td><td></td></tr><tr><td>3</td><td>0,800</td><td>0,734</td><td>0,700</td><td></td><td></td></tr><tr><td>4</td><td>0,833</td><td>0,776</td><td>0,747</td><td></td><td></td></tr><tr><td>5</td><td>0,857</td><td>0,807</td><td></td><td></td><td></td></tr><tr><td>6</td><td>0,875</td><td>0,830</td><td></td><td></td><td></td></tr><tr><td>7</td><td>0,888</td><td></td><td></td><td></td><td></td></tr><tr><td>8</td><td>0,900</td><td></td><td></td><td></td><td></td></tr></tbody></table>

## Tableau 9

Par la même méthode, nous pouvons pour quelques cas spéciaux trouver la condition d'ergodicité ainsi que des approximations des temps de réponse...

Soit le système représenté sur la Figure 10. Ce système consiste en une suite de trois stations dans laquelle le nombre total d'unités dans les deux dernières stations sont limitées à $M = 1$.

<figure><img src="image_9.png" /><figcaption>Figure 10</figcaption></figure>
$$
(47) \quad \left[
\begin{array}{l}
\text{Théorème 4 : La condition d'équilibre du système décrit ci-dessus est donnée par :} \\
\displaystyle\frac{(u_1+u_2)(u_2+u_3)(u_3+u_1) + u_1^3}{(u_1+u_2)(u_1+u_3)} < 1 \\
\text{Si } u_1 = u_2 = u_3 = u \text{ la condition s'écrit } u < \frac{4}{9}
\end{array}
\right.
$$

Dans le cas particulier où $u_2 = u_3$, le système est équivalent à une suite de deux stations, où la seconde station a une capacité limitée égale à 1 et une distribution de temps de service Erlang 2. La condition devient alors

$$
(48) \quad (1-2u_2) (u_1^2+2u_2u_1+u_2^2) - u_1^3 > 0
$$

Soit maintenant le système représenté sur la Figure 11. C'est un réseau d
trois stations avec une probabilité de branchement valant p et 1-p, pour
aller aux stations 2 et 3. Le nombre total d'uni+és dans les stations 2 et 3
est encore limité à M = 1.

<figure><img src="image_10.png" /><figcaption>Figure 11</figcaption></figure>
$$
(49) \quad \left[
\begin{array}{l}
\text{Théorème 5 : La condition d'équilibre du système est donnée par :} \\
\\
\displaystyle \frac{[u_2 u_3 + u_1 (u_2 + u_3)] [u_1 + p u_2 + (1-p)u_3] + u_1^2 (u_1^2 - u_2 u_3)}{u_2 u_3 + u_1 (u_2 + u_3) + u_1^2} \\
\\
\text{si } u_1 = u_2 = u_3 = u \text{ la condition s'écrit } u \stackrel{2}{\leftarrow} u_3
\end{array}
\right.
$$

Ce système est encore équivalent à deux stations en série dans lequel la
seconde station est limitée à 1 et a un temps de service distribué suivant
un processus hyperexponentiel de somme, la somme pondérée par p et 1-p
des exponentielles de taux a₂ et a₃.

La méthode générale décrite ci-dessus est malheureusement difficilement
exploitable pour des files d'attente en série trop longues parce que le
nombre des inconnues croît vite.

Aussi, dans le paragraphe suivant, allons-nous prolonger la méthode
par équivalence, qui nous permettra d'étudier le comportement d'un grand
nombre de files en série.

<figure><img src="image_11.png" /><figcaption>Figure 12</figcaption></figure>
## 3.2 Prolongement de la méthode par équivalence.

Soit toujours le cas général de K files d'attente en tandem décrit dans l'introduction. Nous pouvons remplacer cette file en tandem, par la suite de files d'attente représentée sur la Figure 12. Etudions le comportement d'une station donnée, par exemple la station $M$. Nous pouvons remplacer cette station par une file équivalente de taux de service $\alpha_n = a_n(1-p_{n+1})$ et le taux d'entrée d'une telle station est $b_n = b_n/(1-p_n)$.

Les distributions des interarrivées dans les stations sont certainement très bien approximées par des lois exponentielles de taux $b_n$, $n = 2, ..., K-1$ puisque les serveurs ont des lois exponentielles et que les rebouclages ne font en réalité qu'augmenter la taille de la file d'attente. (Si la taille est infiniment grande, ces distributions sont exactement exponentielles).

Lorsque l'on atteint la saturation, ces distributions sont précisément des lois exponentielles : la condition suffisante donnée par Muntz [25] est satisfaite dans ce cas particulier.

Sous les hypothèses précédentes, nous pouvons donc étudier chaque station indépendamment les unes des autres. Le lien est fait au niveau du calcul de la probabilité de non acceptation d'un client à la station suivante. Chaque station sera examinée comme ayant des interarrivées suivant un processus exponentiel et un service équivalent exponentiel également.

Nous avons donc à résoudre le système suivant pour la station d'ordre $n$ :
$$
(50) \quad \left\{
\begin{array}{l}
b_n = b / (1 - p_n) \\
p_n = u_n^{M_n} (1 - u_n) / (1 - u_n^{M+n}) \quad \text{où } u_n = b_n / \alpha_n
\end{array}
\right.
$$

Comme $\alpha_n$ dépend de $p_{n+1}$, les stations ne sont pas indépendantes, mais si nous commençons l'étude par la station K, nous obtenons $b_K$ et $p_K$ puisque $p_{K+1} = 0$ et de proche en proche, nous obtenons tous les doublets $(b_n, p_n)$.

La condition d'équilibre est réalisée si pour tout i, $b_i < \alpha_i$. Nous obtenons alors pour chaque station i la probabilité qu'il y ait $n_i$ clients :

$$
(51) \quad P(n_i) = u_i^{n_i} \frac{(1-u_i)^{M_i+1}}{(1-u_i)^M} \quad \text{où } u_i = b_i / [a_i(1-p_i)(1-p_{i+1})]
$$

et donc nous obtenons le nombre moyen de clients ainsi que le temps de
réponse de chaque station i :

$$
(52) \quad E_i = \sum_{n_i=1}^{M_i} n_i P(n_i) \quad \text{et} \quad W_i = E_i / b_i
$$

De nombreux exemples de temps de réponse et de nombres moyens de clients
pourraient être donnés sur des sujets très divers dans lesquels on rencontre
des suites de files d'attente à capacité limitée. Nous nous contenterons
de donner juste une application ; le calcul du temps de réponse de 8 files
identiques en série limitées à 1,2,... 10 unités avec des taux d'entrée variant
de 0.01 à 0.90, et des temps moyens de service égaux à une unité de temps.

Nous avons représenté les résultats sur le tableau 13 que nous avons complété
par le temps de réponse pour une capacité infinie. Dans ce dernier cas les
files sont indépendantes les unes des autres et donc :

$$
(53) \quad W_i = \frac{1}{a_i} \frac{1}{1-u_i}
$$

$$
\text{comme } a_i = a = 1, \forall i, \text{ le temps de réponse total est : } W = \frac{8}{1-b}
$$

Nous pouvons également par cette méthode donner un résultat numérique
de la condition d'ergodicité. C'est ce qui est fait dans Pujolle [16]
dans le cas de stations identiques de durée moyenne de service, le temps unité, pour des valeurs de M allant de 2 à 10 et pour 2 à 100 stations en série (tableau 14). On peut alors démonter [16] que le taux de charge maximum pour M places dans chaque station est $[M/(M+1)]^2$. Grâce à une itération sur les matrices stochastiques Caseau [7] donne l'expression exacte du taux de charge maximum lorsque $M=1$ et K stations en série : $\frac{1}{4} \frac{K+1}{K-\frac{1}{2}}$.

<table><caption>Tableau 13</caption><thead><tr><th>d'taux<br>arrivée.</th><th>M = 1</th><th>M = 2</th><th>M = 5</th><th>M = 10</th><th>M = ∞</th></tr></thead><tbody><tr><td>0.01</td><td>8.011</td><td>8.079</td><td>8.082</td><td>8.082</td><td>8.082</td></tr><tr><td>0.10</td><td>8.156</td><td>8.759</td><td>8.889</td><td>8.889</td><td>8.889</td></tr><tr><td>0.20</td><td>8.611</td><td>9.502</td><td>9.990</td><td>10.000</td><td>10.000</td></tr><tr><td>0.30</td><td></td><td>10.350</td><td>11.357</td><td>11.428</td><td>11.428</td></tr><tr><td>0.40</td><td></td><td>11.673</td><td>13.052</td><td>13.327</td><td>13.333</td></tr><tr><td>0.50</td><td></td><td></td><td>14.957</td><td>15.641</td><td>16.000</td></tr><tr><td>0.60</td><td></td><td></td><td>18.189</td><td>19.688</td><td>20.000</td></tr><tr><td>0.70</td><td></td><td></td><td>26.154</td><td>25.558</td><td>26.666</td></tr><tr><td>0.80</td><td></td><td></td><td></td><td>34.545</td><td>40.000</td></tr><tr><td>0.90</td><td></td><td></td><td></td><td></td><td>80.000</td></tr></tbody></table>

Temps moyen de réponse de 8 stations en série
<table><thead><tr><th>Kombre de stations</th><th>N=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><td>2</td><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><td>3</td><td>0.39</td><td>0.509</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><td>4</td><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><td>5</td><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><td>6</td><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><td>7</td><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><td>8</td><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><td>9</td><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><td>10</td><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><td>20</td><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><td>50</td><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><td>100</td><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><td>∞</td><td>0.25</td><td>0.44</td><td>0.56</td><td>0.64</td><td>0.69</td><td>0.73</td><td>0.765</td><td>0.79</td><td>0.81</td><td>0.83</td></tr></tbody></table>

## Taux de charge maximal

### Tableau 14

### 3.3 Conclusion

Nous avons donc pour l'étude de stations en tandem un certain nombre de méthodes qui sont plus ou moins adaptées à l'étude de tel ou tel problème. Dans la réalité il y a un grand nombre d'exemples de telles séries de stations.

Dans l'informatique, un exemple est celui d'un réseau d'ordinateurs ou plus particulièrement du réseau à commutation de paquets. La méthode par équivalence peut être utilisée pour l'étude du temps de réponse d'un chemin particulier à l'intérieur du réseau. Une telle étude est faite dans Irland-Pujolle [17] pour comparer les performances d'un réseau d'ordinateurs sous différents protocoles.
## II APPLICATIONS

Dans la seconde partie de cet article ; nous allons donner quelques applications des méthodes que nous avons développées jusqu'ici. Nous donnons plus précisément deux applications : l'étude des performances d'un système d'exploitation d'un ordinateur, à mémoire virtuelle. Notre critère de performance étant que le nombre maximum de clients puisse être servi. Nous donnons ce maximum étant données les diverses caractéristiques du modèle. Le second problème que nous aborderons est celui du coût minimum d'une suite de files d'attente en série, pour une charge donnée.

Plus explicitement et sur l'exemple d'un réseau d'ordinateurs, si nous connaissons la charge maximale à transporter, quelle capacité de mémorisation et quelle vitesse de transmission adopter pour minimiser le coût.
## 2.1 Performance d'un système d'exploitation

Nous prendrons comme modèle celui du calculateur à mémoire virtuelle présenté par Gelenbe[18] et analysé par Badel, Gelenbe, Leroudier, Potier [19]; puis par Leroudier, Potier [20], et Gelenbe, Kurinckx [21]. Nous l'avons représenté sur la Figure 15.

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

La mémoire peut contenir au maximum M programmes. Le nombre de programmes à l'intérieur de cette mémoire est le degré de multiprogrammation du système. L'ensemble des files d'attente intérieur à la mémoire peut, par une méthode d'équivalence, être représenté par une seule station, le taux de service de cette station dépendant du degré de multiprogrammation.

Nous nous servirons de la méthode d'équivalence introduite par Courtois [22] et par Avi-Itzhak et Heyman [23].

La première station modélise le chargement en mémoire avec tout ce que cela comporte comme temps de gestion. Les travaux se présentent de l'extérieur
suivant un processus de Poisson de taux b. Les différents branchements
à l'intérieur de la mémoire principale seront fonction du degré de multi-
progrma mation.

Les taux de service du tambour de pagination et des E/S seront constants
et égaux respectivement à a₂ et a₁. Nous supposerons également que le temps
entre deux défauts de page dépend du degré de multiprogrammation, suivent
la fonction de vie de Belady, et que la mémoire est équirépartie entre les
programmes présents. Le calcul du taux de service γ(n₂) de la station équi-
valente est effectuée dans [19], en supposant que les temps moyens entre deux
défauts de page, entre deux entrées-sorties, et de calcul unité centrale
demandé, suivent les lois exponentielles de moyenne q, r, c. Avec a₂=200,
a₁=30, r=0.02s, c=1s. La fonction de Belady q=am⁻¹, m = 128 pages de mémoire,
m= m/M, a=10⁵ et k qui dépend de la localité sera pris égal à 1.5 puis 2.5.
Nous obtenons un taux de service équivalent de :

<table>
  <tr>
    <td>k = 1.5</td>
    <td>k = 2.5</td>
  </tr>
  <tr>
    <td>γ(1) = 0.332</td>
    <td>0.375</td>
  </tr>
  <tr>
    <td>γ(2) = 0.405</td>
    <td>0.489</td>
  </tr>
  <tr>
    <td>γ(3) = 0.330</td>
    <td>0.539</td>
  </tr>
  <tr>
    <td>γ(4) = 0.255</td>
    <td>0.565</td>
  </tr>
  <tr>
    <td>γ(5) = 0.197</td>
    <td>0.579</td>
  </tr>
  <tr>
    <td>γ(6) = 0.156</td>
    <td>0.587</td>
  </tr>
  <tr>
    <td>γ(7) = 0.128</td>
    <td>0.591</td>
  </tr>
</table>

Si nous prenons un taux de chargement valant Π =4, nous obtenons à partir
du Théorème 2 du paragraphe 1.4. -c le taux de charge maximal. Ce taux
est représenté sur les figures 16 et 17, pour k=1.5 puis k=2.5.

Pour k=1.5 et chaque programme demandant en moyenne 1 seconde de calcul, pour
que l'ensemble des programmes puisse être traité il ne faut pas qu'il en
arrive plus d'un toutes les 2, 3 secondes en moyenne si le taux de multi-
programmation est 2 et plus d'un toutes les 5, 7 secondes si le taux de multi-
programmation est 5 ; pour k=2.5 et dans les mêmes conditions, nous obtenons
1, 9 seconde et 1, 7 seconde.
<figure><img src="image_13.png" /><figcaption>**Figure 16:** taux maximal des interarrivées dans le système avec $k = 1.5$. temps de clacul moyen 1 seconde</figcaption></figure>
Temps moyen de calcul 1 seconde

<figure><img src="image_14.png" /><figcaption>Figure 17 : taux maximal des interarrivées dans le système avec k = 2.5</figcaption></figure>
## 2.2 Introduction

Dans cette partie, nous posons le problème du coût minimal pour un certain critère de performance. Nous prendrons ici comme critère, le taux de charge maximal du réseau. Nous voulons que pour un certain coût le réseau puisse servir un maximum de paquets par unité de temps.

Ainsi, si le système de K files d'attente en série peut modéliser un réseau à commutation de paquets où les stations représentent les mini-ordinateurs destinés à la retransmission des messages, nous aimerions savoir pour un coût donné, quelles devraient être les caractéristiques de ces mini-ordinateurs pour que le maximum de paquets puisse arriver à destination par unité de temps.

Nous schématisons en prenant dans le coût que deux composants : la mémoire et la vitesse du service. Nous prendrons dans la suite les caractéristiques suivantes : $f(A)$ est le prix pour obtenir A unités de mémoire, $g(B)$ est le prix pour obtenir une vitesse B du service.

Le coût du réseau en tandem de K stations est :

$$C = f(M_1) + f(M_2) + \dots + f(M_K) + g(a_1^{-1}) + \dots + g(a_K^{-1})$$

Nous supposerons pour simplifier que f et g sont des fonctions affines passant par l'origine ; si $\alpha$ et $\beta$ sont les prix d'une unité de mémoire et de l'unité de vitesse, nous avons :

$$C = \alpha(M_1 + \dots + M_K) + \beta(a_1^{-1} + \dots + a_K^{-1})$$

Nous ne chercherons à optimiser que la distribution des vitesses étant donnée la capacité en mémoires et vice-versa. Une optimisation globale dépendra des valeurs de $\alpha$ et $\beta$.
## 2.2 -a Optimisation sur la vitesse

Dans un premier temps supposons que toutes les stations aient la même capacité de mémoire M. Nous cherchons donc pour une somme des $S_i$ donnée ($S_i = a_i^{-1}$) un taux de charge u opt optimum.

$K$

Nous prendrons sans perdre de généralité $\sum_{i=1}^{K} S_i = K$, c'est à dire qu'en moyen-ne $S_i = 1$.

## 2.2.-b Cas de deux files

Nous avons trouvé dans la partie 1.5 que

$$b_{\max} = \frac{\left(\frac{1}{a_2}\right)^{M+1} - \left(\frac{1}{a_1}\right)^{M+1}}{\left(\frac{1}{a_2}\right)^{M+2} - \left(\frac{1}{a_1}\right)^{M+2}} = \frac{S_2^{M+1} - S_1^{M+1}}{S_2^{M+2} - S_1^{M+2}}$$

Etant donnée la symétrie entre $a_1$ et $a_2$, il est facile de démontrer que $b_{\max}$ passe par un maximum pour $a_1=a_2$ et que ce maximum dépend évidemment de M.

Nous avons représenté sur la Figure 18 le taux de charge maximale en fonction de $S_1$ ($S_2 = 2 - S_1$). Le maximum est atteint comme nous venons de le dire pour $S_1 = S_2 = 1$. Il est intéressant de noter que plus la capacité intermédiaire est importante et plus l'effondrement des performances se fait sentir avec un déséquilibre des temps de service.

## 2.2. -c Cas de trois files

Nous avons trouvé dans le paragraphe 1.4 le taux maximum, en fonction des temps de service, de trois files en série de capacité intermédiaire limitée à 1 unité. Cette expression est symétrique en $a_1$ et $a_3$. De plus, elle passe par un maximum pour $a_1 = a_3$. Nous prendrons donc $a_1=a_3$ ($S_1=S_3$) et comme nous avons supposé $S_1 + S_2 + S_3 = 3$, nous avons $S_2 = 3 - 2S_1$. Nous avons représenté sur la Figure 19 le taux de charge maximale d'un tel système en fonction de $S_1$.
Nous remarquons que dans ce cas, le taux maximal n'est pas atteint pour $S_1 = S_2 = S_3 = 1$ mais pour $S_1 = S_3 = 1,08$ et $S_2 = 0,84$. Le système ne doit pas être homogène comme on aurait pu le penser. Ce n'est d'ailleurs pas tant le gain qui est important mais le fait que sur un certain domaine le taux maximal est à peu près égal (ici entre les deux cas 1- 1- 1- et 120-0.60- 1.20 il n'y a que peu de différence).

Il est donc important de se placer au centre de ce domaine puisque de légères fluctuations des temps de service, n'affectent que très peu la charge maximale.
<figure><img src="image_15.png" /><figcaption>Figure 18 : taux maximum en fonction des temps de service $S_1$ et $S_2 = 2 - S_1$</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Figure 19 : taux maximum en fonction des temps de service $S_1 = S_2 = 3 - 25t$</figcaption></figure>
Après avoir exploité les résultats théoriques dont nous disposions, nous nous sommes servis des résultats obtenus par l'approximation du paragraphe 1.6 pour obtenir le taux de charge maximale. Dans le cas de trois files, avec $M > 1$, nous avons pu constater que les mêmes effets se reproduisaient mais avec moins de netteté. Le taux optimum est obtenu pour $a_1 = a_3$ et $a_2 = 3 - 2a_1$ pour des valeurs se rapprochant de 1 - 1 - 1 - lorsque M croît.

## 2.2. -d Cas général

La même étude sur quatre files en série, nous a montré que le taux de charge optimum est obtenu pour $a_1 = a_4$ et $a_2 = a_3$. Le système se comporte de façon symétrique par rapport aux stations centrales. Une démonstration de ce phénomène est la suivante.

Appelons système dual, le même système mais dans lequel les stations sont en ordre inversé (au système $(a_1,a_2,a_3)^T$ correspond le système dual $(a_3,a_2,a_1)^T$). Les clients du système dual sont les places vides du premier système ; (nous supposons que devant le service $a_3$ il y a une file infinie de places vides). Par exemple, lorsqu'un client du premier système sort de $a_2$ pour aller vers $a_3$, une place vide sort de $a_3$ dans le système dual pour aller vers $a_2$. La distribution des temps de service dans le système dual est la même que dans le système initial. A l'état de saturation, les deux systèmes ont exactement le même débit. Or, le système dual, c'est tout simplement le système initial symétrisé, ce qui démontre notre assertion.

Nous avons donc, à l'état de congestion uniquement, une symétrie du composition des stations. De plus, les exemples montrent que si le taux de charge optimal est atteint pour une égalité des temps de service symétriques, les services les plus lents sont à l'extérieur et de plus en plus rapide vers le centre du système. Nous avons étudié le cas de six files en tandem. Nous trouvons que pour toutes les stations identiques, le taux de charge maximale est $0.471(\text{stations de temps de service 1 et capacité M = 1})$ et que

le maximum du taux de charge pour $\sum_{i=1}^{6} S_i = 6$ est obtenu pour la suite de temps de service :
1.29 - 0.96 - 0.75 - 0.96 - 1.29 et que le teux est 0.527. La différence est assez nette et plus il y a de stations en série, plus le cas équilibré est loin du cas optimal.

## 2.3 Optimisation sur la capacité de mémoire.

Nous supposerons maintenant que la vitesse de chaque processeur est la même $a_i = 1$ et supposons que nous ayons M unités de mémoire à disposer devant les serveurs.

La première station étant de capacité illimitée, nous ne la compterons pas dans M. Le cas de deux stations n'a pas d'intérêt puisqu'il suffit de prendre $M_2 = M$. Le cas de trois stations que nous savons résoudre analytiquement n'a pas d'intérêt non plus puisque $M_2 = M_3 = 1$ nous nous servirons donc de l'approximation du paragraphe 1.6.

## 2.3 -a Résultats.

Dans le cas de trois stations nous obtenons les résultats suivants :

$$ \text{Si } M = 3 \text{ le maximum est obtenu pour } M_2 = 2 \text{ et } M_3 = 1 $$

$$ \text{Si } M = 4 \text{ le maximum est obtenu pour } M_2 = 2 \text{ et } M_3 = 2 $$

$$ \text{Si } M = 5 \text{ le maximum est obtenu pour } M_2 = 3 \text{ et } M_3 = 2 $$

Dans le cas de 4 stations en série nous obtenons :

$$ \text{Si } M = 4 \quad M_2 = 2 \quad M_3 = 1 \quad M_4 = 1 \quad \text{ou } M_2 = 1, M_3 = 2, M_4 = 1 $$

$$ \text{Si } M = 5 \quad M_2 = 2 \quad M_3 = 2 \quad M = 1 $$

$$ \text{Si } M = 6 \quad M_2 = 2 \quad M_3 = 2 \quad M_4 = 2 $$

Les autres mesures que nous avons pu faire nous ont donné le même genre de résultats : il faut favoriser les stations centrales si le nombre de places ne peut pas être le même partout sinon il faut répartir équitablement les mémoires.
## 2.4 Conclusion

Dans les deux paragraphe precedents, nous avons examiné l'effet produit sur
le coût, de deux des composantes du prix d'un réseau, la vitesse et la capacité
de mémoire. Les résultats sont concordants par le fait qu'il faut favoriser les
stations centrales sans toutefois qu'un trop grand déséquilibre n'apparaisse.

Ce phénomène qu'il est difficile d'expliquer nous semble-t-il, peut provenir
du fait que les stations centrales influent à la fois sur les stations précé-
dentes et sur les suivantes, ce qui leur confèrent une importance plus grande
sur le comportement du réseau. Il faut donc les favoriser en leur donnant une
vitesse plus grande et une capacité d'attente également, mais dans des limites
raisonnables.
Références

[1] MUNTZ, R.R. "Analytic modelling of interactive systems", Proc. IEEE Interactive Computer System, June 1975.

[2] HUNT, G.C. "Sequential arrays of waiting lines", Operations Research 4, 1956

[3] SUZUKI, T. "On a tandem queue with blocking", J. Oper. Res. Soc. Japon 6, 1964

[4] MAKINO, T "On the mean passage time concerning some queueing problems of the tandem type", J. Oper. Res. Soc. Japon 7, 17-47, 1964

[5] MORSE, P.H. "Queues, inventories and maintenance", John Wiley and son, 1968

[6] KONHEIM, A.G. ; REISER, H. "A queueing model with finite waiting room and blocking", J. ACM 23, 2, 1976

[7] CASEAU, P. "Simulation de processeurs en série au moyen de modèles markovien", Rapport E.D.F. HI/1973.00, 1975

[8] CHANG, W. "Sequential server queues for computer communication system analysis", IBM J. Res. Develop. 476-485, September 1975

[9] AVI-ITZHAK, B. ; YADIN, M. "A sequence of two servers with no intermediate queue" Management Science 11, 553-563, 1965

[10] AVI-ITZHAK, B. "A sequence of service station with arbitrary input and regular service times", Management Science 11, 565-571, 1965.

[11] FRIEDMAN, H.D. "Reduction methods for tandem queueing systems", Operations research 13, 121-131, 1965.
[12] RUBIN, I. "Communication networks : message path delays", IEEE Trans. on Information Theory 20, 738-745, 1974

[13] RUBIN, I. "Message path delays in packet-switching communication networks" IEEE Trans. on Communications 23, 186-192, 1972

[14] LABETOULLE, J. ; PUJOLLE, G. " A study of queueing networks with deterministic service and applications to computer networks", Proc. of ACM SIGMETRICS/IFIP Symposium, Cambridge, 1976

[15] LITTLE, J.D.C. "A proof for the queueing formula $L=\lambda w$" Operations Research 9, May 1961.

[16] PUJOLLE, G. "Files d'attente en série et application au teux de charge maximale d'un réseau d'ordinateurs", Revue d'Informatique de l'AFCET B-2, Mai 1976

[17] IRLAND, M. ; PUJOLLE, G. "Models of tandem networks of queues motivated by packet switching", à paraître.

[18] GELENBE, E. "Modèles de comportement de systèmes informatiques" Thèse d'Etat, Université de Paris VI, Novembre 1973.

[19] BADEL, M. ; GELENBE, E. ; LEROUDIER, J. ; POTIER, D. "Adaptive Optimization of time-sharing system's performance", IEEE Proc. on Interactive Computer Systems, June 1975.

[20] LEROUDIER, J. ; POTIER, D. "A two level scheme for multiprogrammed virtual memory computer systems" Proc. of ACM-SIGMETRIC/IFIP, Cambridge, March 1976

[21] GELENBE, E. ; KURINCKX, A. "Random injection control of multiprogramming in virtual memory", 2nd International Workshop on Modelling and performance Evaluation of computer systems, Stresa, Italy, October 1976
[22] COURTOIS, P.J. "On the near complete decomposability of networks of queues and of stochastic models of multiprogramming systems", Research Report of of Carnegie Mellon University, November 1971

[23] AVI-ITZHAK, B. ; HEYMAN, P. "Approximate models of multiprogramming computer systems" Operations Research 21, 1212-1230, 1973.

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

[25] MUNTZ, R. R. "Poisson departure processes and queueing networks" IBM Research Report R.C. 4145, December 1972.