# Validation d'un modèle à processus de diffusion pour un réseau de files d'attente général : application à cyclades

Marc Badel, Marc Zonzon

► To cite this version:

Marc Badel, Marc Zonzon. Validation d'un modèle à processus de diffusion pour un réseau de files d'attente général : application à cyclades. [Rapport de recherche] IRIA-RR-209, IRIA. 1976, pp.21. hal-04716392

HAL Id: hal-04716392

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

VALIDATION D'UN MODÈLE
A PROCESSUS DE DIFFUSION
POUR UN RÉSEAU
DE FILES D'ATTENTE GÉNÉRAL :
APPLICATION A CYCLADES

Marc BADEL
Marc ZONZON

Rapport de Recherche N° 209

Décembre 1976
VALIDATION D'UN MODÈLE A PROCESSUS DE DIFFUSION POUR
UN RÉSEAU DE FILES D'ATTENTE GÉNÉRAL :
APPLICATION A CYCLADES*

M. Badel**, M. Zonzon***

(présenté par E. Gelenbe)

RÉSUMÉ

Malgré les développements récents des méthodes analytiques de résolution des réseaux de files d'attente, la solution de nombreux cas d'intérêt pratique n'est pas connue. En particulier, certains problèmes issus de l'étude de réseaux d'ordinateurs à commutation de paquets tels que ARA ou CYCLADES ne peuvent être traités par les méthodes classiques basées sur le théorème de JACKSON et ses généralisations. L'objet de cet article est d'étudier les méthodes de résolution de files d'attente par l'utilisation de processus stochastiques continus développés par Gelenbe et Gelenbe-Pujolle pour déterminer leur précision. La simulation aléatoire à évènements discrets est utilisée pour comparer les résultats de simulation. Les intervalles de confiance des résultats de simulation sont calculés par l'utilisation de la méthode de découpage des mesures en blocs faiblement corrélés décrits par Leroudier-Parent. L'étude de la précision est effectuée sur un modèle du réseau d'ordinateur à commutation de paquets à seize files d'attente représentant le sous-système CIGALE du réseau CYCLADES.

ABSTRACT

Although considerable progress has been made in recent years in the area of analytical solutions to queueing network models of complex computer systems, some simple cases such as neworks with FIFO service and general service time distributions can only be solved analytically using approximation methods. Our purpose is to validate using simulation experiments the diffusion approximation developed by Gelenbe and Pujolle-Gelenbe. Confidence intervals for the data collected in the simulations are computed using the method of weakly correlated blocs described by Leroudier-Parent.

<footnote>* Rapport de stage de DEA, Université Paris VI</footnote>

<footnote>** IRIA - LABORIA</footnote>

<footnote>*** Département de mathématiques, Université Paris-Nord, Av. J.B. Clément - 93 Villetaneuse</footnote>
# I. INTRODUCTION

Malgré les développements récents des méthodes analytiques de résolution des réseaux de files d'attente (GEL75a, GEL76a) de nombreux cas d'intérêt pratique existent dont la solution n'est pas connue. En particulier, certains problèmes issus de l'étude de réseaux d'ordinateurs à commutation de paquets tels que ARPA (ROB70) ou CYCLADES (POU74) ne peuvent être traités par les méthodes classiques.

Diverses méthodes ont été proposées (KOB74, GEL76b) pour obtenir des solutions approchées de systèmes d'attente par l'utilisation de processus continus.

L'objet de cet article est d'étudier la précision de la méthode proposée dans (GEL76b) pour le calcul des distributions de probabilités de chaque file dans un réseau de files d'attente. Notre but est de déterminer les limites de l'utilisation de la méthode pour l'analyse des performances des réseaux d'ordinateurs à commutation de paquets. Une étude analogue pour le modèle de (GEL75b) avait été effectuée dans (BAD75).

Nous nous proposons d'utiliser la simulation aléatoire à événements discrets pour déterminer la validité des approximations, pour cela nous comparons celles-ci avec une estimation par intervalle des grandeurs mesurées.
Dans le paragraphe II, nous présenterons le modèle théorique. Dans le paragraphe III, nous rappellerons la méthode de résolution d'un réseau de files d'attente par des processus de diffusion, la structure du simulateur et le calcul des intervalles de confiance seront précisés dans le paragraphe IV. Le Paragraphe V contient une première application à la file GI/G/1. Un modèle plus complexe ayant la structure du réseau de commutation de paquets CIGALE du réseau d'ordinateurs CYCLADE est décrit et les résultats obtenus sur ce réseau sont présentés dans le paragraphe VI. Notre conclusion constitue le paragraphe VI.

## II. PRESENTATION DU MODELE THEORIQUE

Le modèle étudié est un réseau de n files d'attente (voir fig. 1), nous faisons circuler sur ce réseau des entités que nous appellons clients. Nous notons $\lambda_i$ et $\mu_i$ l'inverse de la moyenne et le carré du coefficient de variation de la loi de probabilité du temps séparant deux arrivées à la file i, $\lambda_i$ est plus simplement appelé taux d'arrivée à la file i. De même, nous noterons $C_i$ le carré du coefficient de variation du temps entre deux sorties de la file i.

Les arrivées à la station comprennent les arrivées provenant d'un autre point du réseau ainsi que les arrivées de l'extérieur du réseau. Nous supposons que les temps entre les arrivées de l'extérieur du réseau sont indépendants et identiquement distribués de moyenne $1/\lambda_0$ et de carré de coefficient de variation $C_0$.

Les clients venant de l'extérieur se dirigent avec une probabilité $p_{0,i}$ vers la file i. Ils sont servis à tour de rôle par le serveur i dont les temps de service sont indépendants aussi bien les uns des autres que de l'état du modèle, identiquement distribués de moyenne $1/\mu_i$ et de carré de coefficient de variation $K_i$.

Un client sortant du serveur i se dirige vers la file j avec une probabilité $p_{i,j}$ ou vers la sortie du système avec une probabilité $p_{i,n+1}$.

## III. RESOLUTION THEORIQUE

La résolution théorique a été effectuée par la technique des équations de diffusion, cette méthode est entièrement exposée dans (GEL76b) dont nous rappelons les résultats essentiels.

### a) Résolution pour la file i.

La résolution est basée sur une approximation du nombre de clients dans
la file i par un processus continu dont la fonction de densité $f_i(x,t)$ de la loi de probabilité vérifie une équation de diffusion.

Nous supposerons de plus, qu'après que la file soit passée à l'état vide, son nombre de client saute à 1 selon un processus de retour instantané décrit dans (GEL75b). Nous noterons $m_i(t)$ la masse ponctuelle de probabilité en $0$ à $1$ instant $t$ introduite par le processus de retour instantané (GEL75b).

$f_i$ et $p_i$ vérifient les équations suivantes :

$$1) - \frac{\partial f_i}{\partial t} - b_i \frac{\partial f_i}{\partial x} + \frac{1}{2} \alpha_i \frac{\partial \alpha_i f_i}{\partial x^2} + \lambda_i m_i \delta(x-1) = 0$$

$$2) \quad \frac{\partial m_i}{\partial t} = - \lambda m_i + \lim_{x \to 0} \left( - b_i f_i + \frac{1}{2} \alpha_i \frac{\partial f_i}{\partial x} \right)$$

$$3) \quad f_i(0,t) = 0$$

où $\delta(x-1)$ est une distribution de Dirac au point $1$ et où $\alpha_i$ et $b_i$ sont donnés par

$$4) \quad \alpha_i = \lambda_i \cdot 1_i + \mu_i \cdot K_i$$

$$b_i = \lambda_i - \mu_i$$

La résolution se fait dans le cas stationnaire en annulant les dérivées par rapport au temps et en intégrant en fonction de $x$. En raison de la distribution de Dirac, l'intégration s'effectue séparément dans les intervalles $(0,1)$ et $(1,\infty)$ en assurant la continuité au point $1$.

La solution stationnaire est :

$$5) \quad f_i(x) = u_i(e^{\gamma_i x} - 1) \quad \text{et} \quad e^{\gamma_i x} \quad \text{pour } x > 1$$

$$6) \quad f_i(x) = u_i(1 - e^{\gamma_i x}) \quad \text{pour } 0 < x < 1$$

$$7) \quad m_i = 1 - u_i$$

où nous posons :

$$8) \quad u_i = \lambda_i / \mu_i \quad \text{et} \quad \gamma_i = (2b_i) / \alpha_i$$

### b) Résolution pour le réseau

Les paramètres donnés pour le réseau sont les taux de service $\mu_i$, le taux d'arrivées de l'extérieur $\lambda_0$ et les carrés de variation correspondant $K_i$ et $C$ respectivement, ainsi que les probabilités de circulation $p_{i,j}$ ($0 \le i \le n, 1 \le j \le n+1$).
Les taux d'arrivée $\lambda_i$ dans la file i sont donnés par (GEL.76b)

$$9) \lambda_i = \lambda_{0e_i}$$

où $e_i$, qui représente l'espérance du nombre de passages d'un client dans la file i, est solution du système linéaire.

$$10) e_i = p_{0,i} + \sum_{j=0}^{n} e_j p_{j,i} \quad (1 \le i \le n)$$

Il nous reste à déterminer les carrés des coefficients de variation $L_i$ des temps entre les arrivées à la file i, pour cela nous supposons que les temps entre deux sorties du serveur i forment des variables indépendantes identiquement distribuées. Nous pourrons alors exprimer $L_i$ en fonction du carré de coefficient de variation $C_i$ des intersorties.

$$11) L_i = (1/\lambda_i) \left( \sum_{j=0}^{n} (C_j - 1) p_{j,i} + 1 \right) \lambda_i p_{j,i}$$

Les $C_j$ sont les solutions du système linéaire

$$12) C_i = u_i^2 (K_i + 1) + (1 - u_i) \left( 2u_i + 1 + \lambda_i^{-1} \sum_{j=0}^{n} ((C_j - 1)p_{j,i} + 1) \lambda_j p_{j,i} \right) - 1$$

### c) Calculs pratiques pour un réseau

Les $p_{i,j}$, $\mu_i$, $K_i$, $C_0$, $\lambda_0$ étant donnés, nous calculons $\lambda_i$ d'après (9) par la résolution du système linéaire (10). Les $C_i$ sont alors obtenus par résolution du système (12) ce qui nous permet d'obtenir $\alpha_i$ et $\beta_i$ par (4) d'où $u_i$ et $\gamma_i$ par (8).

Le taux d'utilisation du serveur i est $1 - \mu_i$ soit $u_i$ d'après (7). (5) et (6) nous permettent d'obtenir les fonctions de densité continues approximant le nombre de clients dans la file i pour tout i, les espérances et variances s'en déduisent par intégration.

## IV. SIMULATION DU MODELE

### a) Fonctionnement du simulateur

Le simulateur est un programme de simulation par balayage d'événements.

Les événements sont l'entrée ou la sortie d'un client dans le système et les fins de service. L'entrée d'un client dans le système entraine la planification de l'entrée du client suivant.

Lors d'une fin de service, les actions à entreprendre sont :

- l'aiguillage du client vers une autre file ou vers la sortie du système par tirage suivant les probabilités $p_{i,j}$ ($1 \le j \le n+1$)

- si la file est non vide après le départ du client servi, la planification de
la prochaine fin de service et la diminution de la longueur de la file
- l'augmentation de la longueur de la file d'arrivée et si elle est vide, la
planification d'une fin de service sur le serveur correspondant.

A chaque événement, il est effectué une prise de mesures pour déterminer
les histogrammes des longueurs des files. La probabilité pᵢ(m) qu'il y ait m
clients dans la file i est estimée comme le rapport de la somme des intervalles
de temps où la file contient m client au temps total simulé. En particulier le
taux d'utilisation du serveur i est évalué comme 1 - pᵢ(0).

Ces probabilités estimées servent à former des estimateurs des espérances
et variances de la longueur de chaque file. Les temps des interarrivées à
chaque file sont mesurés et leurs moyennes et variances calculées.

Les générations des temps de services et des temps entre les arrivées de l'extérieur se fait par tirage suivant les lois constantes, d'Erlang, exponentielles ou hyperexponentielles d'ordre 2.

Les paramètres d'une loi sont la moyenne, le carré du coefficient de variation pour l'Erlang et l'hyperexponentielle, pour cette dernière un paramètre supplémentaire a de plus été fixé arbitrairement.

b) Calcul des intervalles de confiance sur les résultats

Pour le calcul des intervalles de confiance nous avons divisé la simulation
en n intervalles de temps égaux et suffisament grands pour que la corrélation
des mesures d'un intervalle sur l'autre soit négligeable (la méthode de
CONWAY (LER76)).

A cet effet un événement supplémentaire "fin d'intervalle de temps" a été
ajouté qui provoque l'actualisation et le relevé des mesures.

Soit X une grandeur physique mesurée tout au long de la simulation et Xᵢ la
moyenne effectuée sur le iᵉme intervalle de temps. D'après la construction des
intervalles pour i ≠ j la covariance de Xᵢ et de Xⱼ est négligeable, nous
calculerons les grandeurs

$$
(13) m = \left( \sum_{i=1}^{n} X_i \right) / n
$$

$$
(14) \sigma^2 = \frac{\sum_{i=1}^{n} (X_i^2 - (\sum_{i=1}^{n} X_i)^2)/n}{n-1}
$$

m est la moyenne de la grandeur X sur toute la simulation

$\sqrt{n} (m-E(X)) / \sigma$ suit alors approximativement une loi de Student à n-1 degrés de
libertés.

Soit $k_{\alpha,n}$ la valeur ayant la probabilité $\alpha$ d'être dépassée en valeur absolue dans une loi de Student à n degré de liberté, nous avons alors

$$ (15) \quad P_r\left( \left| m - E(X) \right| > \sqrt{n} \right) / \sigma < k_{\alpha, n-1} = 1 - \alpha $$

Nous en déduisons un intervalle de confiance sur l'estimateur $m$ de $E(X)$ à la probabilité $1 - \alpha$.

$$ (16) \quad |m - E(X)| < k_{\alpha, n-1} \sigma / \sqrt{n} $$

en particulier pour $1 - \alpha = 95/100$, qui sera la confiance statistique utilisée dans les simulations qui suivent, on aura $k_{\alpha, n-1} < 2,05$ pour $n > 30$ et $\lim_{n \to \infty} k_{\alpha, n} = 1,96$.

Nous pouvons remarquer que l'étendue de l'intervalle de confiance décroit approximativement comme $1/\sqrt{n}$ soit comme l'inverse de la racine carrée du temps simulé.

## V. RESULTATS SUR LA FILE CI/G/1

Le tableau 2 présente les résultats des calculs et des simulations pour les espérances et variances de la longueur d'une file CI/G/1. Le temps simulé est égal à 140.000 fois la moyenne du temps de service. Les intervalles de confiance sont calculés avec une probabilité de 95%. Les carrés des coefficients de variation de l'interarrivée $L$ et du service $K$ prennent les valeurs 1/3, 1 et 3 et le facteur d'utilisation $u = \lambda/\mu$ prend les valeurs 1/1.1 et 1/1.5.

Dans le cas où $u = 1/1.1$ les espérances calculées se trouvent dans l'intervalle de confiance de la simulation pour toutes les valeurs de $L$ et $K$. Dans le cas où $u = 1/1.5$, on observe une certaine dégradation de l'erreur relative (sauf évidemment dans le cas de la file M/M/1 où on montre que la diffusion donne un résultat exact).

L'erreur tend à s'accroître quand $L$ est petit en même temps que $K$ est grand alors que même pour $K = 3$. et $L = 3$, valeurs pourtant éloignées de l'exponentielle, le calcul se trouve encore dans l'intervalle de confiance.

La figure 3 représente l'évolution des espérances calculées et simulées en fonction de $u$ dans le cas où $L = 1/3$ et $K = 1/3$. Nous remarquons que l'erreur absolue n'augmente que très lentement avec $u$ et donc que l'erreur relative décroît rapidement quand $u$ croît.
# VI. LE MODELE DE RESEAU ETUDIE

## a) Description

Le réseau CYCLADE (POU74) nous a servi d'exemple.

Le modèle étudié est un réseau de transmission de paquets de données dont la topologie est indiquée sur la figure 4. Les noeuds du réseau représentent des ordinateurs qui transmettent des paquets d'information aux autres noeuds du réseau via des lignes téléphoniques qui seront modélisées par des serveurs et des files d'attente, ces dernières étant entretenues par les ordinateurs se trouvant aux noeuds.

Des paquets arrivent de l'extérieur du réseau vers chaque noeud et nous supposerons que toutes les destinations sont équiprobables.

Le chemin emprunté est celui qui permet le trajet le plus rapide en cas d'ambiguïté il est donné par le tableau 5.

La rapidité des lignes est de 0.4 seconde en moyenne par paquet pour toutes les lignes sauf les lignes 1, 2, 3, 5 qui transmettent à une moyenne de 0.3 seconde par paquet.

Puisque dans ce modèle les clients (paquets de données) ont une circulation entièrement déterminée par leur lieu de départ et leur destination, il nous faut, pour pouvoir utiliser l'approximation par des diffusions, remplacer ce modèle par un autre à aiguillages probabilistes indépendants des clients. Il nous faut donc calculer les probabilités $p_{i,j}$.

Toute ligne du réseau étant parcourue par des flots de clients de sources et de destinations déterminées, nous prendrons pour $p_{i,j}$ le rapport des flots passant par la file i et se dirigeant vers la file j à la somme totale des flots passant par la file i.

## b) Résultats des diffusions et simulations

Le temps simulé est pour toutes les simulations égal à 9.000 secondes. Le temps moyen entre deux arrivées de l'extérieur a été fixé à 1/7 seconde.

Dans toutes les mesures les lois de service ont été prises toutes de même carré de coefficient de variation K. Les intervalles de confiance sont calculés avec une probabilité de 95%. Le tableau 6 donne une comparaison entre deux simulations effectuées la première avec le modèle déterministe, la seconde avec
un modèle probabiliste avec des probabilités de transition $p_{i,j}$ calculées selon la méthode décrite dans le paragraphe VI.a). Les arrivées de l'extérieur ont été prises exponentielles et les temps de service sont constants. Nous pouvons remarquer que les résultats coïncident. Le tableau 7 compare le calcul du taux d'utilisation aux résultats des simulations qui ont été effectuées pour des arrivées exponentielles, puis hyperexponentielles de carré de coefficient de variation $C_0 = 13$. et des services constants, suivant une loi d'Erlang d'ordre 3, exponentiels, et hyperexponentiels de carré de coefficient de variation $L = 3$. Les résultats de calcul se trouvent ici encore toujours compris dans les intervalles de confiance de la simulation.

Le tableau 8 compare simulation et calcul pour les carrés des coefficients de variation des interarrivées aux files. Ces résultats sont très proches pour des arrivées exponentielles; ils s'éloignent légèrement pour des arrivées hyperexponentielles mais l'erreur relative reste partout inférieure à 15%.

Enfin les espérances des longueurs des files sont données dans le tableau 9. Les résultats sont exacts dans le cas de services et d'interarrivées exponentiels mais sont moins bons dans les autres cas. Les erreurs absolues sont plus grandes pour des services hyperexponentiels que des services constants ou distribués suivant une loi d'Erlang mais les erreurs relatives sont par contre plus petites.

Il est à noter que l'importance des erreurs relatives est due au fait que le facteur d'utilisation est ici très bas ce qui constitue, nous l'avons vu dans le paragraphe V, un cas très défavorable.

## VII. CONCLUSIONS

La comparaison des résultats de diffusions avec ceux obtenus par simulation fait ressortir les points suivants :

- Les taux d'utilisation des serveurs attachés aux files sont corrects partout (cf. Tableau 7). Les résultats obtenus par diffusions sont compris le plus souvent dans les intervalles de confiance de la simulation.

- Les espérances des longueurs des files, tant sur le réseau complet que sur une file $GI/G/1$, sont moins bonnes. Les résultats restent cependant corrects dans deux cas :

* Les lois de temps de service ont des coefficients de variation proches de 1.

* Le réseau est suffisamment chargé.
Les résultats se dégradent lorsqu'on a à la fois des lois de temps de service éloignées des lois exponentielles et un réseau peu chargé.

La simulation nous a servi également à tester des hypothèses faites lors de la résolution par diffusions. C'est ainsi que :

- Remplacer un réseau à circulation déterministe par un réseau aléatoire affecte très peu les résultats (cf. tableau 6),

- Les carrés des coefficients de variation des temps interarrivées dans les files ont été mesurés en simulation. Leurs valeurs obtenues par le calcul sont bonnes pour des arrivées exponentielles dans le réseau et restent proches de la simulation même lorsqu'on s'éloigne de cette hypothèse.
REFERENCES

BAD75 M. Badel, Thèse de 3e Cycle, Université Paris VI, 1975.

CON63 R.W. Conway, "Some Practical Problems in Digital Simulation", Management Sciences 10, 1 (1963).

GEL75a E. Gelenbe, Cours à l'école de l'AFCET, Juillet 1975.

GEL75b E. Gelenbe, "On Approximate Computer System Models", J.A.C.M., p. 261-263 (1975).

GEL76a E. Gelenbe, R.R. Muntz, "Probabilistic Models of Computer Systems. Part I.", Acta Informatica 7, p. 35-60 (1976).

GEL76b E. Gelenbe, G. Pujolle, "The Behaviour of a Single Queue in a Network", Proc. A.C.M./I.F.I.P. WG.7.3. Symp. on Modelling and Performance Evaluation of Computer Systems, Harvard Univ., Cambridge, Mass. (1976).

KOB74 H. Kobayashi, M. Reiser, "Accuracy of the Diffusion Approximation for some Queueing Systems", I.B.M. J. Res. Devel., 18, p. 110-124 (1974).

LER76 J. Leroudier, M. Parent, "Quelques Aspects de la Simulation Aléatoire à Evénements Discrets", Revue d'Informatique de l'AFCET B-1, p. (1976).

POU74 L. Pouzin, "CIGALE The Packet Switching Machine of the CYCLADE Computer Network", Proc. I.F.I.P. Congress 1974, Stockholm, North-Holland, 155-159 (Août 1974).

ROB70 L.G. Roberts, B.D. Wessler, "Computer Network Development to Achieve Resource Sharing", A.F.I.P.S. Conf. Proc., 36, p. 543-549 (1970).
<figure><img src="image_3.png" /><figcaption>FIGURE 1</figcaption></figure>
<table><thead><tr><th rowspan="2">L</th><th rowspan="2">K</th><th rowspan="2">u</th><th colspan="2">Espérance</th><th colspan="2">Ecart-type</th></tr><tr><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th></tr></thead><tbody><tr><td rowspan="3">1/3</td><td rowspan="3">1/3</td><td>1/1.5</td><td>.89</td><td>1.01 ± .02</td><td>.95</td><td>.99</td></tr><tr><td>1/1.1</td><td>3.63</td><td>3.77 ± .23</td><td>3.5</td><td>3.4</td></tr><tr><td>1</td><td>1/1.5</td><td>1.56</td><td>1.41 ± .04</td><td>1.9</td><td>1.6</td></tr><tr><td></td><td></td><td>1/1.1</td><td>6.97</td><td>6.94 ± .80</td><td>7.2</td><td>6.6</td></tr><tr><td></td><td>3</td><td>1/1.5</td><td>3.55</td><td>2.69 ± .15</td><td>4.7</td><td>3.6</td></tr><tr><td></td><td></td><td>1/1.1</td><td>16.96</td><td>16.80 ± 1.8</td><td>18.</td><td>16.</td></tr><tr><td rowspan="3">1</td><td rowspan="3">1/3</td><td>1/1.5</td><td>1.33</td><td>1.55 ± .03</td><td>1.6</td><td>1.7</td></tr><tr><td>1/1.1</td><td>6.67</td><td>6.67 ± 1.0</td><td>6.9</td><td>6.7</td></tr><tr><td>1</td><td>1/1.5</td><td>2.00</td><td>2.00 ± .07</td><td>2.5</td><td>2.4</td></tr><tr><td></td><td></td><td>1/1.1</td><td>10.00</td><td>10.84 ± 1.3</td><td>10.5</td><td>11.</td></tr><tr><td></td><td>3</td><td>1/1.5</td><td>4.00</td><td>3.33 ± .21</td><td>5.3</td><td>4.6</td></tr><tr><td></td><td></td><td>1/1.1</td><td>20.00</td><td>21.02 ± 2.8</td><td>21.</td><td>19.</td></tr><tr><td rowspan="3">3</td><td rowspan="3">1/3</td><td>1/1.5</td><td>2.67</td><td>2.84 ± .11</td><td>3.4</td><td>3.5</td></tr><tr><td>1/1.1</td><td>15.76</td><td>16.97 ± 2.1</td><td>16.</td><td>15.</td></tr><tr><td>1</td><td>1/1.5</td><td>3.33</td><td>3.51 ± .21</td><td>4.4</td><td>4.6</td></tr><tr><td></td><td></td><td>1/1.1</td><td>19.09</td><td>19.27 ± 2.4</td><td>20.</td><td>17.</td></tr><tr><td></td><td>3</td><td>1/1.5</td><td>5.33</td><td>5.07 ± .37</td><td>6.8</td><td>4.4</td></tr><tr><td></td><td></td><td>1/1.1</td><td>29.09</td><td>29.25 ± 5.8</td><td>31.</td><td>24.</td></tr></tbody></table>

Espérance et écart-type d'une file G1/G1

Tableau 2
Espérance mathématique de la
longueur de la file

FILE G/G/1

Simulation

Analytique (diffusion)

4

3

2

1

0

0.5

u

>

1

FIGURE 3
<figure><img src="image_4.png" /><figcaption>FIGURE 4</figcaption></figure>
<table><caption>Tableau 5</caption><thead><tr><td>Source</td><td>Destination</td><td>Noeud de transition</td></tr></thead><tbody><tr><td>A</td><td>F</td><td>C</td></tr><tr><td>B</td><td>F</td><td>C</td></tr><tr><td>C</td><td>G</td><td>F</td></tr><tr><td>D</td><td>G</td><td>F</td></tr><tr><td>C</td><td>C,D</td><td>B</td></tr><tr><td>F</td><td>A,B</td><td>C</td></tr></tbody></table>
<table><thead><tr><th>Numéro des files</th><th>Modèle déterministe</th><th>Modèle aléatoire</th></tr></thead><tbody><tr><td>1</td><td>.36 ± .01</td><td>.36 ± .01</td></tr><tr><td>2</td><td>.34 ± .01</td><td>.33 ± .01</td></tr><tr><td>3</td><td>.72 ± .01</td><td>.72 ± .01</td></tr><tr><td>4</td><td>.14 ± .01</td><td>.14 ± .01</td></tr><tr><td>5</td><td>.52 ± .01</td><td>.51 ± .01</td></tr><tr><td>6</td><td>.52 ± .02</td><td>.51 ± .01</td></tr><tr><td>7</td><td>.30 ± .01</td><td>.30 ± .01</td></tr><tr><td>8</td><td>.52 ± .02</td><td>.52 ± .02</td></tr><tr><td>9</td><td>.53 ± .01</td><td>.53 ± .01</td></tr><tr><td>10</td><td>.32 ± .01</td><td>.31 ± .01</td></tr><tr><td>11</td><td>.14 ± .01</td><td>.14 ± .01</td></tr><tr><td>12</td><td>.14 ± .01</td><td>.14 ± .01</td></tr><tr><td>13</td><td>.30 ± .01</td><td>.30 ± .01</td></tr><tr><td>14</td><td>.32 ± .01</td><td>.31 ± .01</td></tr><tr><td>15</td><td>.15 ± .01</td><td>.15 ± .01</td></tr><tr><td>16</td><td>.32 ± .01</td><td>.32 ± .01</td></tr></tbody></table>

Espérance des longueurs des files

Tableau 6
<table><thead><tr><th colspan="2">Calcul</th><th colspan="5">SIMULATION</th></tr><tr><th colspan="2">C<sub>0</sub></th><th colspan="4">1</th><th>13</th></tr><tr><th colspan="2">L</th><th>0</th><th>1/3</th><th>1</th><th>3</th><th>3</th></tr></thead><tbody><tr><th>N° des files</th><th>1</th><td>.300</td><td>.297 ± .006</td><td>.301 ± .006</td><td>.298 ± .009</td><td>.296 ± .010</td><td>.291 ± .018</td></tr><tr><th>N° des files</th><th>2</th><td>.300</td><td>.296 ± .006</td><td>.297 ± .007</td><td>.294 ± .010</td><td>.296 ± .010</td><td>.295 ± .012</td></tr><tr><th>N° des files</th><th>3</th><td>.500</td><td>.502 ± .008</td><td>.505 ± .011</td><td>.508 ± .012</td><td>.502 ± .012</td><td>.503 ± .017</td></tr><tr><th>N° des files</th><th>4</th><td>.133</td><td>.134 ± .005</td><td>.134 ± .006</td><td>.130 ± .006</td><td>.139 ± .007</td><td>.131 ± .010</td></tr><tr><th>N° des files</th><th>5</th><td>.400</td><td>.399 ± .007</td><td>.395 ± .008</td><td>.396 ± .010</td><td>.398 ± .014</td><td>.400 ± .014</td></tr><tr><th>N° des files</th><th>6</th><td>.400</td><td>.397 ± .009</td><td>.398 ± .012</td><td>.397 ± .013</td><td>.400 ± .018</td><td>.396 ± .020</td></tr><tr><th>N° des files</th><th>7</th><td>.267</td><td>.266 ± .008</td><td>.268 ± .008</td><td>.262 ± .010</td><td>.265 ± .016</td><td>.271 ± .013</td></tr><tr><th>N° des files</th><th>8</th><td>.400</td><td>.400 ± .008</td><td>.408 ± .011</td><td>.400 ± .013</td><td>.399 ± .016</td><td>.397 ± .019</td></tr><tr><th>N° des files</th><th>9</th><td>.400</td><td>.401 ± .009</td><td>.397 ± .011</td><td>.399 ± .011</td><td>.400 ± .019</td><td>.398 ± .022</td></tr><tr><th>N° des files</th><th>10</th><td>.267</td><td>.261 ± .006</td><td>.265 ± .010</td><td>.265 ± .012</td><td>.264 ± .013</td><td>.253 ± .014</td></tr><tr><th>N° des files</th><th>11</th><td>.133</td><td>.131 ± .005</td><td>.133 ± .006</td><td>.137 ± .007</td><td>.137 ± .010</td><td>.131 ± .010</td></tr><tr><th>N° des files</th><th>12</th><td>.133</td><td>.134 ± .006</td><td>.131 ± .006</td><td>.133 ± .007</td><td>.138 ± .009</td><td>.129 ± .010</td></tr><tr><th>N° des files</th><th>13</th><td>.267</td><td>.265 ± .007</td><td>.270 ± .009</td><td>.269 ± .010</td><td>.268 ± .012</td><td>.268 ± .016</td></tr><tr><th>N° des files</th><th>14</th><td>.267</td><td>.263 ± .007</td><td>.271 ± .008</td><td>.265 ± .011</td><td>.282 ± .012</td><td>.264 ± .015</td></tr><tr><th>N° des files</th><th>15</th><td>.133</td><td>.135 ± .006</td><td>.135 ± .005</td><td>.134 ± .008</td><td>.132 ± .008</td><td>.137 ± .011</td></tr><tr><th>N° des files</th><th>16</th><td>.267</td><td>.272 ± .007</td><td>.271 ± .009</td><td>.262 ± .010</td><td>.260 ± .014</td><td>.268 ± .017</td></tr></tbody></table>

Teux d'utilisation

<caption>Tableau 7</caption>
<table><thead><tr><th rowspan="2">C0</th><th rowspan="2">L</th><th colspan="3">1</th><th colspan="3">1/3</th><th colspan="3">1/3</th><th colspan="3">13</th></tr><tr><th>0</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th></tr></thead><tbody><tr><td>1</td><td>1.00</td><td>.97</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>2.71</td><td>3.08</td></tr><tr><td>2</td><td>.94</td><td>.94</td><td>.96</td><td>.97</td><td>1.00</td><td>1.00</td><td>1.03</td><td>1.12</td><td>1.14</td><td>1.12</td><td>1.30</td><td>1.25</td></tr><tr><td>3</td><td>.97</td><td>.95</td><td>.98</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.02</td><td>1.06</td><td>1.06</td><td>1.06</td><td>1.92</td><td>1.69</td></tr><tr><td>4</td><td>1.00</td><td>.98</td><td>1.00</td><td>1.04</td><td>1.00</td><td>1.00</td><td>.97</td><td>1.01</td><td>.95</td><td>1.01</td><td>1.25</td><td>1.36</td></tr><tr><td>5</td><td>.97</td><td>.93</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.06</td><td>1.07</td><td>1.07</td><td>1.50</td><td>1.69</td></tr><tr><td>6</td><td>.95</td><td>.94</td><td>.97</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.09</td><td>1.05</td><td>1.05</td><td>1.27</td><td>1.22</td></tr><tr><td>7</td><td>.97</td><td>.99</td><td>.98</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.04</td><td>1.07</td><td>1.07</td><td>1.07</td><td>1.22</td><td>1.24</td></tr><tr><td>8</td><td>.96</td><td>.98</td><td>.98</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.02</td><td>1.07</td><td>1.07</td><td>1.07</td><td>1.40</td><td>1.30</td></tr><tr><td>9</td><td>1.00</td><td>1.00</td><td>1.00</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.03</td><td>1.00</td><td>1.00</td><td>1.00</td><td>2.71</td><td>2.99</td></tr><tr><td>10</td><td>1.00</td><td>.99</td><td>1.00</td><td>1.01</td><td>1.00</td><td>1.00</td><td>1.02</td><td>1.00</td><td>.99</td><td>1.01</td><td>2.14</td><td>2.18</td></tr><tr><td>11</td><td>1.00</td><td>1.03</td><td>1.00</td><td>.98</td><td>1.00</td><td>1.00</td><td>1.01</td><td>1.00</td><td>1.05</td><td>1.05</td><td>1.57</td><td>1.62</td></tr><tr><td>12</td><td>1.00</td><td>1.06</td><td>1.00</td><td>.99</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.01</td><td>1.02</td><td>1.02</td><td>1.28</td><td>1.30</td></tr><tr><td>13</td><td>.97</td><td>1.00</td><td>.98</td><td>1.03</td><td>1.00</td><td>1.00</td><td>1.02</td><td>1.06</td><td>1.06</td><td>1.06</td><td>1.23</td><td>1.27</td></tr><tr><td>14</td><td>1.00</td><td>1.03</td><td>1.00</td><td>1.02</td><td>1.00</td><td>1.00</td><td>.99</td><td>1.00</td><td>.98</td><td>1.00</td><td>2.14</td><td>2.36</td></tr><tr><td>15</td><td>1.00</td><td>.99</td><td>1.00</td><td>1.01</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>.98</td><td>1.00</td><td>1.57</td><td>1.71</td></tr><tr><td>16</td><td>1.00</td><td>.98</td><td>1.00</td><td>1.01</td><td>1.00</td><td>1.00</td><td>.97</td><td>1.00</td><td>1.06</td><td>1.06</td><td>2.14</td><td>2.36</td></tr></tbody></table>

Carré des coefficients de variation des interarrivées
<table><caption>Espérance des longueurs des files</caption><thead><tr><th rowspan="2">C<sub>0</sub></th><th rowspan="2">L</th><th colspan="3">1</th><th colspan="3">1/3</th><th colspan="3">1</th><th colspan="3">13</th></tr><tr><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th><th>Calcul</th><th>Simulation</th></tr></thead><tbody><tr><td>1</td><td>.21</td><td>.36 ± .01</td><td>.29</td><td>.39 ± .01</td><td>.43</td><td>.43 ± .02</td><td>.86</td><td>.55 ± .04</td><td>.97</td><td>.69 ± .09</td><td>.21</td><td>.33 ± .01</td><td>.29</td><td>.37 ± .01</td><td>.43</td><td>.42 ± .02</td><td>.86</td><td>.58 ± .05</td><td>.88</td><td>.57 ± .05</td></tr><tr><td>2</td><td>.21</td><td>.33 ± .01</td><td>.29</td><td>.37 ± .01</td><td>.43</td><td>.42 ± .02</td><td>.86</td><td>.55 ± .04</td><td>.97</td><td>.69 ± .09</td><td>.21</td><td>.33 ± .01</td><td>.29</td><td>.37 ± .01</td><td>.43</td><td>.42 ± .02</td><td>.86</td><td>.58 ± .05</td><td>.88</td><td>.57 ± .05</td></tr><tr><td>3</td><td>.49</td><td>.72 ± .01</td><td>.66</td><td>.83 ± .01</td><td>1.00</td><td>1.04 ± .07</td><td>2.02</td><td>1.55 ± .18</td><td>2.23</td><td>1.80 ± .18</td><td>.49</td><td>.72 ± .01</td><td>.66</td><td>.83 ± .01</td><td>1.00</td><td>1.04 ± .07</td><td>2.02</td><td>1.55 ± .18</td><td>2.23</td><td>1.80 ± .18</td></tr><tr><td>4</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.14 ± .01</td><td>.15</td><td>.15 ± .01</td><td>.31</td><td>.16 ± .01</td><td>.31</td><td>.18 ± .02</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.14 ± .01</td><td>.15</td><td>.15 ± .01</td><td>.31</td><td>.16 ± .01</td><td>.31</td><td>.18 ± .02</td></tr><tr><td>5</td><td>.33</td><td>.51 ± .01</td><td>.44</td><td>.56 ± .02</td><td>.67</td><td>.66 ± .03</td><td>1.34</td><td>.96 ± .09</td><td>1.40</td><td>1.02 ± .08</td><td>.33</td><td>.51 ± .01</td><td>.44</td><td>.56 ± .03</td><td>.67</td><td>.65 ± .04</td><td>1.34</td><td>.92 ± .10</td><td>1.37</td><td>1.07 ± .16</td></tr><tr><td>6</td><td>.33</td><td>.51 ± .01</td><td>.44</td><td>.56 ± .03</td><td>.67</td><td>.65 ± .04</td><td>1.34</td><td>.92 ± .10</td><td>1.37</td><td>1.07 ± .16</td><td>.33</td><td>.51 ± .01</td><td>.44</td><td>.56 ± .03</td><td>.67</td><td>.65 ± .04</td><td>1.34</td><td>.92 ± .10</td><td>1.37</td><td>1.07 ± .16</td></tr><tr><td>7</td><td>.18</td><td>.30 ± .01</td><td>.24</td><td>.33 ± .01</td><td>.36</td><td>.38 ± .02</td><td>.73</td><td>.45 ± .04</td><td>.74</td><td>.50 ± .05</td><td>.18</td><td>.30 ± .01</td><td>.24</td><td>.33 ± .01</td><td>.36</td><td>.38 ± .02</td><td>.73</td><td>.45 ± .04</td><td>.74</td><td>.50 ± .05</td></tr><tr><td>8</td><td>.33</td><td>.52 ± .01</td><td>.44</td><td>.59 ± .03</td><td>.67</td><td>.66 ± .04</td><td>1.34</td><td>.90 ± .07</td><td>1.39</td><td>1.06 ± .13</td><td>.33</td><td>.52 ± .01</td><td>.44</td><td>.59 ± .03</td><td>.67</td><td>.66 ± .04</td><td>1.34</td><td>.90 ± .07</td><td>1.39</td><td>1.06 ± .13</td></tr><tr><td>9</td><td>.33</td><td>.53 ± .01</td><td>.44</td><td>.57 ± .03</td><td>.67</td><td>.68 ± .04</td><td>1.33</td><td>.90 ± .09</td><td>1.56</td><td>1.21 ± .16</td><td>.33</td><td>.53 ± .01</td><td>.44</td><td>.57 ± .03</td><td>.67</td><td>.68 ± .04</td><td>1.33</td><td>.90 ± .09</td><td>1.56</td><td>1.21 ± .16</td></tr><tr><td>10</td><td>.18</td><td>.31 ± .01</td><td>.24</td><td>.33 ± .03</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.45 ± .05</td><td>.78</td><td>.51 ± .05</td><td>.18</td><td>.31 ± .01</td><td>.24</td><td>.33 ± .03</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.45 ± .05</td><td>.78</td><td>.51 ± .05</td></tr><tr><td>11</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.15 ± .01</td><td>.15</td><td>.16 ± .01</td><td>.31</td><td>.16 ± .01</td><td>.31</td><td>.18 ± .02</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.15 ± .01</td><td>.15</td><td>.15 ± .01</td><td>.31</td><td>.16 ± .01</td><td>.31</td><td>.18 ± .02</td></tr><tr><td>12</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.14 ± .01</td><td>.15</td><td>.15 ± .01</td><td>.31</td><td>.18 ± .02</td><td>.31</td><td>.17 ± .02</td><td>.08</td><td>.14 ± .01</td><td>.10</td><td>.14 ± .01</td><td>.15</td><td>.15 ± .01</td><td>.31</td><td>.18 ± .02</td><td>.31</td><td>.17 ± .02</td></tr><tr><td>13</td><td>.18</td><td>.30 ± .01</td><td>.24</td><td>.33 ± .02</td><td>.36</td><td>.35 ± .02</td><td>.73</td><td>.44 ± .04</td><td>.74</td><td>.48 ± .05</td><td>.18</td><td>.30 ± .01</td><td>.24</td><td>.33 ± .02</td><td>.36</td><td>.35 ± .02</td><td>.73</td><td>.51 ± .05</td><td>.78</td><td>.54 ± .06</td></tr><tr><td>14</td><td>.18</td><td>.31 ± .01</td><td>.24</td><td>.34 ± .02</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.51 ± .05</td><td>.78</td><td>.54 ± .06</td><td>.18</td><td>.31 ± .01</td><td>.24</td><td>.34 ± .02</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.51 ± .05</td><td>.78</td><td>.54 ± .06</td></tr><tr><td>15</td><td>.08</td><td>.15 ± .01</td><td>.10</td><td>.15 ± .01</td><td>.15</td><td>.15 ± .02</td><td>.31</td><td>.18 ± .02</td><td>.31</td><td>.20 ± .03</td><td>.08</td><td>.15 ± .01</td><td>.10</td><td>.15 ± .01</td><td>.15</td><td>.15 ± .02</td><td>.31</td><td>.18 ± .02</td><td>.31</td><td>.20 ± .03</td></tr><tr><td>16</td><td>.18</td><td>.32 ± .01</td><td>.24</td><td>.34 ± .01</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.46 ± .05</td><td>.78</td><td>.59 ± .07</td><td>.18</td><td>.32 ± .01</td><td>.24</td><td>.34 ± .01</td><td>.36</td><td>.36 ± .02</td><td>.73</td><td>.46 ± .05</td><td>.78</td><td>.59 ± .07</td></tr></tbody></table>