# Algorithmes de calcul des probabilités stationnaires d'un réseau de files d'attente

Didier Merle

► To cite this version:

Didier Merle. Algorithmes de calcul des probabilités stationnaires d'un réseau de files d'attente. [Rapport de recherche] IRIA-RR-279, IRIA. 1978, pp.63. hal-04716561

HAL Id: hal-04716561

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

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
<figure><img src="image_2.png" /></figure>

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

ALGORITHMES DE CALCUL DES
PROBABILITÉS STATIONNAIRES
D'UN RÉSEAU
DE FILES D'ATTENTE

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

Didier MERLE

Rapport de Recherche N° 279

Mars 1978
ALGORITHMES DE CALCUL DES PROBABILITÉS STATIONNAIRES
D'UN RÉSEAU DE FILES D'ATTENTE

Didier Merle

Résumé :

Ce rapport présente une étude exhaustive des algorithmes de calcul des probabilités d'état stationnaires et des grandeurs dérivées, pour des réseaux de files d'attente vérifiant les hypothèses des théorèmes de Baskett, Chandy, Muntz et Palacios. Par rapport aux résultats disponibles divers compléments et extensions sont apportés. Les algorithmes proposés ont été implantés dans le produit QNAP de description et d'analyse de réseaux de files d'attente. Des exemples numériques obtenus à l'aide de cet outil sont présentés.

Abstract :

This paper presents an exhaustive study of computing algorithms for the steady state probabilities and derived quantities for queueing networks which satisfy the assumptions of Baskett, Chandy, Muntz and Palacios' theorems. Previous available algorithms are presented and extended to yield further results. They are presently implemented in the software package QNAP (Queueing Network Analysis Package). Numerical examples obtained with this package are presented.
# ALGORITHMES DE CALCUL DES PROBABILITES

## STATIONNAIRES D'UN RESEAU DE FILES D'ATTENTE

### I - INTRODUCTION

Les modèles à reseau de files d'attente ont récemment fait l'objet de développements et d'applications importantes comme outils d'analyse et d'évaluation des performances de systèmes informatiques. En effet, d'un point de vue structurel ces modèles sont bien adaptés à la représentation globale des systèmes d'ordinateurs multiprogrammés modernes. Plusieurs expériences ont confirmé la valeur de cette approche [15, 17, 19].

Le développement et l'utilisation de ces modèles ont été largement favorisés par les progrès théoriques d'analyse mathématique des réseaux de files d'attente. L'un des résultats essentiels, dû à Baskett, Chandy, Muntz et Palacios [3], concerne les réseaux ouverts, fermés ou mixtes avec plusieurs classes de clients. Pour les types de réseaux considérés, le théorème établit en particulier que les probabilités stationnaires d'état du réseau s'expriment sous forme d'un produit de fonctions indépendantes. Cette propriété importante permet le calcul efficace des différentes mesures traduisant le fonctionnement du réseau.

Les théorèmes de Baskett, Chandy, Muntz et Palacios étendent les résultats établis par Jackson [1], repris par Gordon et Newell [2] et pour lesquels Buzen a proposé les premiers algorithmes de calcul [4]. Ces algorithmes ont été ensuite généralisés par différents auteurs dont Reiser et Kobayashi [5], Williams et Bhandiwad [12], Reiser [6], Krzesinski et Teunissen [16].

Ce rapport est un essai de synthèse et de clarification de divers travaux dans le domaine des algorithmes de calcul et plus particulièrement ceux de Reiser [6]. Par rapport à ceux-ci des extensions et compléments ont été introduits :

* Pour des réseaux ouverts ou mixtes (cf. § II.1) et dans les cas particuliers où la stabilité du réseau peut être déduite simplement des données, nous indiquons les formules permettant d'obtenir les grandeurs élémentaires relatives aux stations (taux d'utilisation, longueurs de files, etc...).
Ces grandeurs élémentaires sont calculées pour chaque classe de clients.

Dans le cas de réseaux fermés et dans le cas où les hypothèses théoriques le permettent, nous autorisons le taux de service d'une station à dépendre du nombre de clients par classe dans la station.

Dans tous les cas, nous autorisons les communications entre classes de clients au sortir d'une station.

Nous rappelons les hypothèses et les résultats théoriques principaux au paragraphe II. Le paragraphe III est consacré aux réseaux ouverts. Le paragraphe IV présente les algorithmes de résolution pour les réseaux fermés. Le paragraphe V expose quelques considérations sur les problèmes posés par les réseaux mixtes, problèmes analogues à ceux rencontrés dans la résolution des réseaux fermés. Nous concluons au paragraphe VI par quelques exemples de calcul.

Le travail présenté a été réalisé dans le cadre du projet QNAP (Queueing Network Analysis Package [18]). Le produit QNAP est un outil de construction, de manipulation et de résolution de réseaux de files d'attente qui rassemble les différentes techniques de résolution disponibles [6, 8, 6, 10, 13]. Les algorithmes présentés dans cet article ont été implantés dans le module de résolution par analyse mathématique de QNAP.

## II - TYPES DE RESEAUX CONCERNES

Nous considérons ici des réseaux de files d'attente pour lesquels il existe une solution explicite donnant les probabilités d'états stationnaires. Parmi ces réseaux nous présentons ceux pour qui cette solution est sous forme produit. Ces réseaux sont décrits par Baskett, Chandy, Muntz et Palacios dans [3], Reiser et Kobayashi dans [5].

### II.1 - Routage

- Le réseau est constitué de $N(< \infty)$ stations visitées par des clients appartenant à $R(< \infty)$ classes.

- Un client de classe r quittant la station n se rend à la station l avec la classe s suivant la probabilité $P_{n,r:l,s}$. La matrice de transition $P = ((P_{n,r:l,s}))$ peut être considérée comme définissant une chaîne de Markov. On suppose cette chaîne décomposable en M sous-chaînes ergodiques ($\eta_m$, $m = 1 \to M$) (La recherche de ces sous-chaînes peut être effectuée en déterminant les composantes connexes du graphe associé au réseau [21]). Ces sous-chaînes peuvent être ouvertes
ou fermées (dans ce dernier cas le nombre de clients dans la sous-chaîne reste constant). Un réseau sera dit fermé si les sous-chaînes sont fermées, ouvert si elles sont ouvertes, mixte s'il existe concurement des sous-chaînes ouvertes et fermées.

- Dans le cas de sous-chaînes ouvertes, on peut considérer deux types de processus d'arrivée dans le système :

a) Le processus d'arrivée est poissonnier de paramètre $\lambda(K)$ où K est le nombre total de clients dans le système. La probabilité pour qu'un client de classe r entre dans le réseau à la station n est notée $q_{nr}$, avec $\sum_{n,r} q_{nr} = 1$.

b) Il existe autant de processus d'entrée poissonniens de paramètre $\lambda_m(K_m)$ que de sous-chaînes ouvertes où $K_m$ est le nombre de clients dans la sous-chaîne ouverte m, avec $\sum_{n,r \in m} q_{nr} = 1$.

## II.2 - Les stations

On distingue 4 types de stations :

**Type 1** : discipline de service "Premier Arrivé, Premier Servi" (PAPS). Distribution des temps de service exponentielle. Le taux de service de la station n est $\mu_n(k)$ où k est le nombre total de clients dans la station n. Un seul serveur.

**Type 2** : discipline de service "Dernier Arrivé, Premier Servi" avec préemption (DAPSP). Distribution des temps de service à transformée de Laplace rationnelle. Le taux de service peut dépendre de la classe du client en cours de service, du nombre total de clients dans la station et/ou du nombre de clients par classe dans la station. Un seul serveur.

**Type 3** : discipline de service "Processor Partagé" (PP), Distribution des temps de service à transformée de Laplace rationnelle. Le taux de service peut prendre les formes indiquées dans le cas d'une station de type 2. Un seul serveur.

**Type 4** : serveur Infini (délai pur), (SI). Il existe un nombre de serveurs supérieur ou égal au nombre de clients dans la station. Distributions des temps de service à transformée de Laplace rationnelle identiques pour chaque serveur. Taux de service $\mu_{nr}$ pour des clients de classe r.

## II.3 - Etats du Modèle

Le théorème énoncé dans [3] relatif aux probabilités à l'état stationnaire décrit l'état du système de façon complète. Pour la modélisation d'un système nous ne nous intéressons en fait qu'à des grandeurs plus accessibles telles :
- taux d'utilisation des serveurs

- longueur moyenne des files d'attente.

Il nous suffit pour les calculer de connaître les probabilités marginales relatives aux états suivants :

$$E = \{(\vec{k}_1, \vec{k}_2, \dots, \vec{k}_N)\},$$

$$\text{où} \qquad \vec{k}_n = (k_{n1}, k_{n2}, \dots, k_{nR}),$$

et $k_{nr}$ = nombre de clients de classe r dans la station n.

## II.4 - Probabilités à l'équilibre

Considérons le système d'équation défini pour chaque sous-chaîne :

$$\sum_{n,r} e_{nr} P_{nr} : \ell s + q_{\ell s} = e_{\ell s} \quad (\ell, s) \in \mathcal{M}_{m}$$

Il est clair que $e_{nr}$ peut être interprété comme le taux d'arrivée d'un client de classe r à la station n.

Si la sous-chaîne $\mathcal{M}_m$ est ouverte les $e_{nr}$ sont uniques.

Si la sous-chaîne est fermée les $e_{nr}$ sont définis à une constante près (système homogène).

Alors la probabilité stationnaire d'un état $S$ du système est donné par :

$$P(S = (\vec{k}_1, \vec{k}_2, \dots, \vec{k}_N)) = c^{-1} d(S) f_1(\vec{k}_1) f_2(\vec{k}_2) \dots f_N(\vec{k}_N)$$

où

$$-C : \text{constante de normalisation} \\ - d(S) = \begin{cases} K-1 & \Pi \quad \lambda(i) \text{ dans le cas d'arrivées externes globales (K nombre de clients} \\ & i=0 \quad \text{dans le réseau}). \\ M & \Pi \quad \Pi \quad \lambda_m(j) \text{ dans le cas d'arrivées externes distinctes pour les} \\ & m=1, j=0 \quad \text{sous-chaînes (K_m le nombre de clients dans la sous-} \\ & \quad \text{chaîne m : } \lambda_m(j) = 1 \quad \forall j \text{ si la sous-chaîne } \mathcal{M}_m \text{ est fermée)}. \end{cases}$$
- Dans le cas de taux de service constants on a :

$$
\bullet f_n(\vec{k}_n) = k_n! \left(\frac{1}{\mu_n^0}\right)^k \prod_{r=1}^{R} \frac{e_{nr}}{\mu_{nr}^0} \frac{1}{k_{nr}!} \quad \text{type 1}
$$

$$
\bullet f_n(\vec{k}_n) = k_n! \prod_{r=1}^{R} \frac{1}{k_{nr}!} \left( \frac{e_{nr}}{\mu_{nr}^0} \right)^{k_{nr}} \quad \text{type 2 et 3}
$$

$$
\bullet f_n(\vec{k}_n) = \prod_{r=1}^{R} \frac{1}{k_{nr}!} \left( \frac{e_{nr}}{\mu_{nr}^0} \right)^{k_{nr}} \quad \text{type 4}
$$

$$
\text{avec } k_n = \sum_{r=1}^{R} k_{nr},
$$

et $\mu_n^0$ le taux de service de la station n,

$\mu_{nr}^0$ le taux de service de la station n pour une classe r.

- Dans le cas de taux de service dépendant nous supposerons que :

$$
\mu_{nr} = \mu_{nr}^{0} F_{nr}(k_{n1}, \dots, k_{nR}) ,
$$

où $F_{nr}$ est une fonction strictement positive, et $k_{nr}$ est le nombre de clients de classe r dans la station n. Dans la suite, nous nous limitons aux dependances particulières suivantes :

$$
1) F_{nr}(k_{n1}, \dots, k_{nR}) = g_{nr}(k_{nr})
$$

$$
2) F_{nr}(k_{n1}, \dots, k_{nR}) = h_n \left( \sum_r k_{nr} \right)
$$

$$
3) F_{nr}(k_{n1}, \dots, k_{nR}) = g_{nr}(k_{nr}) h_n \left( \sum_r k_{nr} \right)
$$

avec les restrictions suivantes :

• seule la forme 2) est valide dans le cas d'une station de type 1

• aucune forme n'est possible dans le cas d'une station de type 4.

On notera que du point de vue calculatoire, nous pouvons utiliser la forme 2)
en posant $\mu_{nr} = \mu_{nr}^0 k_{nr}$ s'il y a k_{nr} clients dans la station.

Donc dans le cas de taux de service dépendant de l'état de la file
nous aurons les trois formes possibles :

$$
1) f_n(\vec{k}_n) = k_n! \left[ \prod_{r=1}^{R} \frac{1}{k_{nr}!} \left( \frac{e_{nr}}{\mu_{nr}^0} \right)^{k_{nr}} \prod_{j=1}^{k_{nr}} \frac{1}{g_{nr}^{(j)}} \right]
$$

$$
2) f_n(\vec{k}_n) = k_n! \left[ \prod_{r=1}^{R} \frac{1}{k_{nr}!} \left( \frac{e_{nr}}{\mu_{nr}^0} \right)^{k_{nr}} \prod_{j=1}^{k_{nr}} \frac{1}{h_{nr}^{(j)}} \right]
$$

$$
3) f_n(\vec{k}_n) = k_n! \left[ \prod_{r=1}^{R} \frac{1}{k_{nr}!} \left( \frac{e_{nr}}{\mu_{nr}^0} \right)^{k_{nr}} \prod_{j=1}^{k_{nr}} \frac{1}{g_{nr}^{(j)}} \right] \prod_{j=1}^{k_{nr}} \frac{1}{h_{nr}^{(j)}}
$$
## CONCLUSION

Quelques remarques s'imposent :

- dans l'expression de P(S) les distributions de temps de service n'interviennent que par la moyenne de ces distributions. Ce qui nous dégage de la nécessité de calculer les moments d'ordre supérieur à condition d'avoir validé les hypothèses sur les distributions et les politiques de service ;

- la forme produit de P(S) montre la mutuelle indépendance des stations : cette forme relativement simple nous permettra d'utiliser des algorithmes de calcul efficaces ;

- Il faut bien sûr avoir calculé d'une façon ou d'une autre la constante de normalisation C. Nous verrons que les problèmes posés par ce calcul différent suivant la nature du réseau, ouvert, fermé, mixte.

## III - RESEaux OUVERTS

### III.1 - Fonction génératrice

Par définition la fonction génératrice d'une variable aléatoire vectorielle à valeurs positives et entières $N = (N_1, ..., N_n)$ est :

$$G(z_1, ..., z_n) = E \{ z_1^{N_1} z_2^{N_2} ... z_n^{N_n} \}$$

Si d'autre part on pose $p(k_1, k_2, ..., k_n) = \text{Prob} \{ N_1 = k_1, ..., N_n = k_n \}$

avec
$$ \sum_{k_1=0}^{\infty} \dots \sum_{k_n=0}^{\infty} p(k_1, k_2, ..., k_n) = 1 $$

alors :

$$G(z_1, ..., z_n) = \sum_{k_1=0}^{\infty} \dots \sum_{k_n=0}^{\infty} p(k_1, k_2, ..., k_n) \prod_{i=1}^{n} z_i^{k_i}$$

Cette notion classique a été utilisée par Williams et Bhandiwad [12] et Reiser [6] dans les algorithmes de calcul qu'ils ont proposés (voir aussi [13]).
### III.2 - Application aux réseaux BCMP [5]

Définissons les fonctions $B_n$ et $C_{nr}$ suivantes :

$$ \forall n \quad B_n(k_n) = \prod_{j=1}^{k_n} \frac{1}{h_n(j)}, $$

$$ \forall r \quad C_{nr}(k_n) = \prod_{j=1}^{k_n} \frac{1}{g_{nr}(j)}, $$

Posons $z_i = (z_{i1}, z_{ir}, \dots, z_{iR})$, $i = 1, \dots, N$,

alors d'après ce qui précède :

$$ G(z_1, z_2, \dots, z_N) = C^{-1} \sum_{k_1 \ge 0} \dots \sum_{k_N \ge 0} d(S) \prod_{n=1}^{N} B_n(k_n) \prod_{r=1}^{R} \frac{C_{nr}(k_r)}{k_{nr}!} \left( \frac{e^{z_{nr}}}{\mu_{nr}^0} \right)^{k_{nr}} $$

11 est clair que $G(\bar{1}, \bar{1}, \dots, \bar{1}) = 1$ : $\bar{1} = (1, 1, \dots, 1)$ d'où :

$$ C = \sum_{k_1 \ge 0} \dots \sum_{k_N \ge 0} d(S) \prod_{n=1}^{N} B_n(k_n) \prod_{r=1}^{R} \frac{C_{nr}(k_r)}{k_{nr}!} \left( \frac{e^{z_{nr}}}{\mu_{nr}^0} \right)^{k_{nr}} $$

$$ C = G^*(\bar{1}, \bar{1}, \dots, \bar{1}) \quad \text{avec } G^* = GC $$

Nous verrons dans la suite que les termes de la forme :

$$ \prod_{n=1}^{N} B_n(k_n) \prod_{r=1}^{R} \frac{C_{nr}(k_r)}{k_{nr}!} \left( \frac{e^{z_{nr}}}{\mu_{nr}^0} \right)^{k_{nr}} $$

peuvent se calculer relativement simplement (et efficacement sans utiliser de calculs de factorielles et d'exponentiation). Cependant il est certain que le calcul de $C$ reste ennuyeux si nous ne faisons pas d'hypothèses supplémentaires permettant de mettre $G$ sous une forme plus simple.

D'autre part les problèmes de convergence de la somme dont est issu $C$ se poseront alors avec plus de clarté.
a) **Hypothèse 1** : Taux d'arrivée externes constants (i.e. $\lambda_m(K_m) = \lambda_m \forall m$)

On pose : $\rho_{nr} = \frac{\lambda_m e}{0} \mu_{nr}$ où $r \in \mathcal{M}_m$ (1)

(si le taux d'arrivée externe est global $\lambda_m = \lambda \ \forall m$)

alors :

$$G^*(z_1, z_2, \dots, z_N) = \prod_{n=1}^{N} \left[ \sum_{k_n \ge 0} B_n(k) \right]^{\prod_{r=1}^{R} C_{nr}(k_n)} \left( \frac{\rho_{nr} z_n}{k_{nr}!} \right)^{k_{nr}} \\ G^*(z_1, z_2, \dots, z_N) = \prod_{n=1}^{N} G_n(z_n)$$

b) **Hypothèse 2** : $\forall n \ \forall r \ \forall k_{nr} \ C_{nr}(k_{nr}) = 1$

$$G_n(z_n) = \sum_{k_n \ge 0} B_n(k) \prod_{r=1}^{R} \frac{(\rho_{nr} z_n)^{k_{nr}}}{k_{nr}!} = \sum_{i=0}^{\infty} B_n(i) (\rho_n \cdot z_n)^i$$

avec $\rho_n = (\rho_{n1}, \rho_{n2}, \dots, \rho_{nR})$,

et où la notation $(\cdot)$ désigne le produit scalaire.

Si $G_n(\bar{1})$ existe pour tout $n$ alors $C = \prod_{n=1}^{N} G_n(\bar{1})$. Sinon le réseau n'est pas stable. Bien que sous forme d'une série entière on ne peut conclure généralement quant à la convergence de cette série, sauf dans les cas simples dont nous explicitons plus loin quelques exemples. Il se pose donc (toutes hypothèses exclues) deux problèmes

- Stabilité du réseau ($\Leftrightarrow C < +\infty$)

- Si le réseau est stable quand arrêter les itérations.

### III.3 - Cas particuliers

Il existe cependant des cas importants pour lesquels nous pouvons conclure a priori :

1 - stations à taux constant

$$G_n(z_n) = \sum_{i=0}^{\infty} (\rho_n \cdot z_n)^i = \frac{1}{1 - \rho_n \cdot z_n} \quad (\text{somme d'une série géométrique})$$

$$C_n = \frac{1}{1-\bar{\rho}_n} \text{ si } \bar{\rho}_n < 1 \text{ avec } \bar{\rho}_n = \sum_{r=1}^{R} \rho_{nr}$$

(1) $\rho_{nr}$ = intensité de trafic
2 - Station à délai pur (SI)

$$G_n(z_n) = \sum_{i=0}^{\infty} \frac{1}{i!} (\rho_n \cdot z_n)^i = \exp (\rho_n \cdot z_n)$$

$$C_n = \exp (\bar{\rho}_n)$$

3 - Stations à dépendance limitée

Nous supposons qu'il existe $d_n$ tel que :

$$k_n < d_n \quad \forall r \quad \mu_{nr} = \mu_{nr}^0 h_n(k_n)$$

$$k_n \ge d_n \quad \forall r \quad \mu_{nr}(k_n) = \beta_n \mu_{nr}^0 = \text{este}$$

Dans ce cas :

$$G_n(z_n) = \sum_{i=0}^{\infty} B_n(i) (\rho_n \cdot z_n)^i = 1 + \sum_{i=1}^{d_n-1} B_n(i) (\rho_n \cdot z_n)^i + \sum_{i=d_n}^{\infty} B_n(i) (\rho_n \cdot z_n)^i$$
or pour $i \ge d_n$ : $$B_n(i) = \frac{B_n(d_n-1)}{\beta_n^{i-d_n+1}}$$

Donc :

$$\sum_{i=d_n}^{\infty} B_n(i) (\rho_n \cdot z_n)^i = \frac{B_n(d_n-1)}{\beta_n^{1-d_n}} \quad \sum_{i=d_n}^{\infty} \frac{(\rho_n \cdot z_n)^i}{\beta_n^i} = \frac{B_n(d_n-1)}{\beta_n} \frac{(\rho_n \cdot z_n)^d}{1 - \frac{\rho_n \cdot z_n}{\beta_n}}$$

et

$$G_n(z_n) = \frac{1}{1 - \frac{\rho_n \cdot z_n}{\beta_n}} \left[ 1 - \frac{\rho_n \cdot z_n}{\beta_n} + \sum_{i=1}^{d_n-1} B_n(i) (\rho_n \cdot z_n)^i - \sum_{i=1}^{d_n-1} \frac{B_n(i)}{\beta_n} (\rho_n \cdot z_n)^{i+1} + \right. \\ 
\left. \qquad + \frac{B_n(d_n-1)}{\beta_n} (\rho_n \cdot z_n)^d \right] \\ 
= \frac{1}{1 - \frac{\rho_n \cdot z_n}{\beta_n}} \left[ 1 - \frac{\rho_n \cdot z_n}{\beta_n} + B_n(1) \rho_n \cdot z_n + \sum_{i=2}^{d_n-1} \left( B_n(i-1) - \frac{B_n(i-1)}{\beta_n} \right) (\rho_n \cdot z_n)^i \right]$$
Soit en posant $B_n(0) = 1$

$$G_n(z) = \frac{1}{1 - \frac{\rho_n \cdot z}{\beta_n}} \left[ 1 + \sum_{i=1}^{d_n-1} \left( B_n(i) - B_n \frac{(i-1)}{\beta_n} \right) (\rho_n \cdot z)^i \right] = \frac{\gamma_n(\rho_n \cdot z)}{1 - \frac{\rho_n \cdot z}{\beta_n}}$$

$\gamma_n(x)$ est un polynôme de degré $d_n-1$ au plus.

Donc si $\frac{\bar{\rho}_n}{\beta_n} < 1$ alors : $C_n = \frac{\gamma_n(\bar{\rho}_n)}{1 - \frac{\bar{\rho}_n}{\beta_n}}$.

### III.4 - Grandeur élémentaires concernant les stations

Dans ce paragraphe, nous supposerons que la constante de normalisation a pu être calculée. Nous nous plaçons d'autre part dans l'hypothèse 1. Nous poserons :

$$C_n = G_n(\bar{1})$$

$$\text{et : } p_n(k_{n1}, k_{n2}, \dots, k_{nR}) = \frac{1}{C_n} B_n(k_{n1}) k_{n1}! \prod_{r=1}^{R} C_{nr}(k_{nr}) \frac{\rho_{nr}^k}{k_{nr}!}$$

(les termes $C_n p_n(k_{n1}, k_{n2}, \dots, k_{nR})$ sont calculables par l'algorithme 4 du paragraphe IV.2).

Le but de ce paragraphe est de montrer que le calcul des quantités suivantes :

- taux d'utilisation

- nombre moyen de clients

- débit moyen

relatives à une classe et une station données sont aisément calculables si le problème du calcul de la constante de normalisation $C = \prod_{n=1}^{N} C_n$ est résolu.
### III.4.1 - Cas général

#### * Taux d'utilisation

Pour des stations du type 1, 2 ou 3, nous définirons le taux d'utilisation comme la proportion de temps pendant laquelle le serveur est occupé. Pour un client de classe r et si la station n considérée est dans l'état $(k_{n1}, \dots, k_{nR})$ cette proportion sera :

$$ \frac{k_{nr}}{k_n} p_n(k_{n1}, k_{n2}, \dots, k_{nR}) \quad (1) $$

Dans le cas d'une station du type 4 (SI), nous définirons le taux d'utilisation par classe de clients comme la proportion de service accordée à la classe considérée. Dans ce cas et si la station est dans l'état $(k_{n1}, \dots, k_{nR})$ l'expression ci-dessus convient (2).

Le taux d'utilisation pour la classe r à la station n sera donc :

$$ \text{util}_{nr} = \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{k_{nr}}{k_n} p_n(k_{n1}, k_{n2}, \dots, k_{nR}) $$

soit :

$$ \text{util}_{nr} = \frac{1}{c_n} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{k_{nr}}{k_n} B_n(k_n) \prod_{r=1}^{R} c_{nr}(k_r) \frac{\rho_{nr}}{k_{nr}!} $$

Ce qui nous donne :

$$ \text{util}_{nr} = \frac{\rho_{nr}}{c_n} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 1} \sum_{k_{nR} \ge 0} \begin{bmatrix} R & \rho_{ns}^k & & \\ \prod_{s=1}^{R} \rho_{ns}^{k_s} & \prod_{s \neq r} \rho_{ns}^{k_s} & C_{ns}(k_s) \\ \sum_{s=1}^{R} \rho_{ns}^{k_s} & & \end{bmatrix} \frac{B_n(k_n-1)}{h_n(k_n)} (k_n-1)! \frac{C_{nr}(k_n-1)}{g_{nr}(k_n)} \frac{\rho_{nr}}{(k_n-1)!} $$

Soit après changement de variable $(k_{nr} \leftarrow k_{nr} - 1)$ :

$$ \text{util}_{nr} = \rho_{nr} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{p_n(k_{n1}, k_{n2}, \dots, k_{nR})}{h_n(k_n+1) g_{nr}(k_n+1)} $$

(1) Voir démonstration en annexe A.

(2) Cette définition est équivalente à la première si l'on considère une station SI comme une station "processeur partagé" avec un taux de service égal à $\mu_{nr} k_n$, si $k_n$ est le nombre de clients dans la station ; c'est l'interprétation que nous utiliserons dans la suite.
## Nombre moyen de clients dans la station

Soit $L_{nr}$ la variable aléatoire dont une réalisation est le nombre de clients de classe r dans la station n. Nous avons :

$$lgq_{nr} = E(L_{nr}) = \sum_{k_{nr}=0}^{\infty} k_{nr} p_{nr}(k_{nr})$$

où $p_{nr}(k_{nr}) = \text{Prob}\{k_{nr} \text{ clients de classe r dans la station n}\}$

de façon évidente nous avons :

$$p_{nr}(k_{nr}) = \sum_{s=1}^{R} \sum_{\substack{k_{ns}=0 \\ s \neq r}}^{\infty} p_{n}(k_{n1}, \dots, k_{nR})$$

$$\text{et} \quad \lg q_{nr} = \sum_{k_{n1}=0}^{\infty} \dots \sum_{k_{nR}=0}^{\infty} k_{nr} p_{n}(k_{n1}, \dots, k_{nR})$$

à partir de ce dernier point et par une méthode tout à fait analogue à ce qui précède on obtient :

$$\lg q_{nr} = \rho_{nr} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{\binom{k+1}{n} p_n(k_1, \dots, k_{nR})}{h_n(k+1) g_{nr}(k+1)}$$

## Débit moyen

- Supposons la station n dans l'état $(k_{n1}, \dots, k_{nR})$. Nous avons montré que dans le cas de stations de type 1, 2 ou 3 la probabilité qu'un client de classe r soit en cours de service s'écrit :

$$\frac{k}{k_{nr}} p_{n}(k_{n1}, \dots, k_{nR})$$

Ce client est servi avec un taux égal à $\mu_{nr}^0 h_n(k_n) g_{nr}(k_{nr})$. D'où le débit dans le cas de stations de type 1, 2 ou 3 :

$$\text{deb}_{nr} = \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \mu_{nr}^0 h_n(k_n) g_{nr}(k_{nr}) \frac{k}{k_n} p_n(k_{n1}, \dots, k_{nR})$$
$$
C_{deb\_{nr}} = \sum_{k_{n1} \ge 0} \dots \sum_{k_{nr} \ge 1} \dots \sum_{k_{nR} \ge 0} \\
\rho_{nr} \mu_{nr}^0 B_n^{(k_{n1}-1)(k_{nR}-1)!} \prod_{\substack{s=1 \\ s \ne R}}^{R} C_{ns}^{(k_{ns})} \frac{\rho_{ns}^{k_{ns}}}{k_{ns}!} C_{nr}^{(k_{nr}-1)} \frac{\rho_{nr}^{k_{nr}-1}}{(k_{nr}-1)!}
$$

Après changement de variable ($k_{nr} \leftarrow k_{nr} - 1$) on obtient le résultat prévisible :

$$
deb_{nr} = \mu_{nr}^{0} \rho_{nr}
$$

- Dans le cas d'une station de type 4 (serveur infini) dans l'état $(k_{n1}, \dots, k_{nR})$, il y a k_{nr} serveurs dévolus à des clients de classe r, ces clients sont servis avec le taux $\mu_{nr}^0$. D'où le débit pour la classe r :

$$
deb_{nr} = \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} k_{nr} \mu_{nr}^0 p_n(k_{n1}, \dots, k_{nR})
$$

Cette formule est un cas particulier de ce qui précède dans le cas ou l'on prend
un taux de service égal à $\mu_{nr}^0$. Donc dans tous les cas nous pouvons écrire :

$$
deb_{nr} = \mu_{nr}^{0} \rho_{nr}
$$

III.4.2 - *Cas de l'hypothèse 2*

Il vient :

$$
\text{util}_{nr} = \rho_{nr} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{p_n^{(k_{n1}, \dots, k_{nR})}}{h_n^{(k_{n+1})}} = \rho_{nr} \alpha(n)
$$
$$
\text{et} \quad \lg q_{nr} = \rho_{nr} \sum_{k_{n1} \ge 0} \dots \sum_{k_{nR} \ge 0} \frac{p_n^{(k_{n1}, \dots, k_{nR}) (k_{nR}+1)}}{h_n^{(k_{n1}+1)}} = \rho_{nr} \beta(n)
$$

$$
\text{or} \quad \sum_r \text{util}_{nr} = \text{util}_n
$$

$$
\sum_r \lg q_{nr} = \lg q_n
$$

D'autre part :

$$
\text{util}_n = 1 - \text{Prob}\{\text{aucun client dans la station n}\} = 1 - \frac{1}{c_n}
$$

D'où :

$$
\text{util}_{nr} = \frac{\rho_{nr}}{\rho_n} \frac{c_n - 1}{c_n}
$$

l'expression que l'on obtient pour le nombre moyen de clients (total) dans la
station n n'est pas aussi simple :

$$
G_n(z_n) = \frac{1}{c_n} \sum_{i=0}^{\infty} B_n(i) \rho_n^{-i} z_n^i
$$

$$
\text{d'où} \qquad \lg q_n = \left[ \frac{\partial G_n(z_n)}{\partial z_n} \right]_{z_n=1} = \frac{1}{c_n} \sum_{i=0}^{\infty} i B_n(i) \rho_n^{-i} \qquad (*)
$$

### III.4.3.- Dépendance globale limitée

Dans ce cas la fonction génératrice se met sous la forme :

$$
G_n(z_n) = \frac{\gamma_n(\rho_n \cdot z_n)}{1 - \rho_n \cdot z_n / \beta_n}
$$

où $\gamma_n$ est un polynôme de degré $d_n - 1$ au plus si pour tout $k_n \ge d_n$

$$
\mu_{nr} = \mu_{nr} h_n(k_n) = \mu_{nr} \beta_n.
$$

<footnote>(*) expression qui a un sens si $C_n$ existe.</footnote>
$$ C_n \lg q_{nr} = \left[ \frac{\frac{\partial G_n(z)}{\partial z_{nr}}}{\frac{\partial G_n(z)}{\partial z_{nr}}} \right]_{z_{nr}=1} = \rho_{nr} \frac{\gamma_n^*(\bar{\rho}_n)}{1-\bar{\rho}_n/\beta_n} + \frac{\gamma_n(\bar{\rho}_n)}{\beta_n(1-\bar{\rho}_n/\beta_n)^2} $$

Après un certain nombre de calculs on obtient :

$$ \lg q_{nr} = \frac{\rho_{nr}}{\gamma_n(\bar{\rho}_n)(1-\bar{\rho}_n/\beta_n)} \left[ B_n(1) + \sum_{i=1}^{d-1} (i+1)(B_n(i+1) - \frac{B_n(i-1)}{\beta_n^2}) \rho_{nr}^i \right] $$ avec $B_n(0) = 1$.

### III.4.4. - Stations à taux constant

De façon évidente on obtient :

$$ \text{util}_{nr} = \rho_{nr} $$

D'autre part :

$$ \lg q_{nr} = \left[ \frac{\frac{\partial G_n(z)}{\partial z_{nr}}}{\frac{\partial G_n(z)}{\partial z_{nr}}} \right]_{z_{nr}=1} = \frac{1}{C_n} \frac{\rho_{nr}}{(1-\bar{\rho}_n)^2} \quad \text{d'où} \quad \lg q_{nr} = \frac{\rho_{nr}}{1-\bar{\rho}_n} $$

### III.4.5 - Stations serveur infini

De façon immédiate, $\lg q_{nr} = \rho_{nr}$.

### III.5 - Conclusion

Dans le cas d'un réseau ouvert, nous avons vu que le problème essentiel est le calcul de la constante de normalisation. Il semble difficile dans les cas que nous avons envisagés (donc sous réserve de l'hypothèse 1), de déterminer de façon automatique si la série mono ou multivariable qui définit cette constante converge ou non, et en conséquence de réaliser concrètement un programme effectuant les calculs.

Par contre dans un certain nombre de cas particuliers dont l'importance n'est pas négligeable (ils recouvrent à mon sens la grande majorité des cas pratiques) la constante de normalisation est obtenue explicitement, de même que les grandeurs élémentaires qui nous intéressent.
IV - **RESEAUX FERMES**

IV.1 - Fonctions génératrices

Du point de vue de la stabilité du réseau et des itérations dans les calculs, le problème est réglé, le nombre de clients dans chaque sous-chaîne étant fini.

Par contre la fonction génératrice du réseau est formellement plus
complexe. Il faut en effet prendre en compte la condition supplémentaire suivante :

$$
\forall m \quad \sum_{n} \sum_{r \in \mathcal{M}_m} k_{nr} = K_m = \text{constante}
$$

Soit X = (X₁, X₂, ..., X_M) un vecteur de M variables auxiliaires, et G*(z₁, ..., z_R ; X)
les polynômes défini par :

$$
G^*(z_1, z_2, \dots, z_R ; X) = \prod_{n=1}^{N} \sum_{k_n \ge 0} B_n \binom{k_n}{n} \prod_{r=1}^{R} C_{nr} \binom{\rho_{nr} z_{nr}}{k_{nr} !} \frac{\rho_{nr} z_{nr} X_m}{k_{nr} !}
$$
où l'on associe la variable X_m à la classe r si r ∈ M_m.

La fonction génératrice du réseau est le coefficient du monôme
$X_1^{K_1} X_2^{K_2} \dots X_M^{K_M}$ à la constante de normalisation près. De même que précédemment
on a :

$$
C = G^*(\bar{1}, \bar{1}, \dots, \bar{1} ; X) \text{ au point } X_1^{K_1}, X_2^{K_2}, \dots, X_M^{K_M}
$$

Notons $G_n$ le polynôme défini par :

$$
G_n(X_1, X_2, \dots, X_M) = \sum_{\substack{k=0 \\ n}}} B_n \binom{k}{n} \prod_{r=1}^{R} C_{nr} \binom{(\rho_{nr} X_m)^k}{k_{nr}!} \quad r \in \mathcal{M}_m
$$
et
$$
G(X_1, X_2, \dots, X_M) = \prod_{n=1}^{N} G_n(X_1, X_2, \dots, X_M)
$$

$\Pi^*$ définissant le produit de polynôme (ce qui correspond à un produit de convolu-
tion dans le cas discret).

Le calcul de la constante de normalisation (et en
con séquence directe les probabilités marginales à l'équilibre) nécessite donc le calcul
des coefficients de X₁, X₂, ..., X_M avec i₁ ≤ K₁, ..., i_M ≤ K_M dans les polynômes G_n.

On en déduit ces mêmes coefficients pour G, donc G*(Π, Π, ..., Π : X) au point
K₁, ..., K_M. Les algorithmes sont ceux présentés par Reiser [ε] dont

Nous reprendons en partie le formalisme avec des extensions aux stations dont le
taux de service dépend du nombre de clients par classe.
## IV.2 - Algorithmes de calcul de la constante de normalisation

Nous nous intéressons tout d'abord au calcul de la constante de normalisation. Nous verrons au paragraphe suivant que les algorithmes de calcul des grandeurs caractéristiques de chaque file d'attente sont analogues à ceux présentés ici, lorsque ces grandeurs ne s'en déduisent pas immédiatement.

* $g$: matrice de dimensions ($0 : K_1, 0 : K_2, ..., 0 : K_M$) contient à la fin du calcul les coefficients du polynôme $G$.

* $c_n$: matrice ($0 : K_1^*, ..., 0 : K_M^*$) où $K_r^* = K_m$ si $r \in \mathfrak{M}_n$ contient les les coefficients du type $\sum_{k=1}^{R} \frac{\rho_{nr}}{k}$.

* $p$: matrice ($0 : K_1, ..., 0 : K_M$), coefficients du polynôme $G_n$ au pas n du calcul.

* $\vec{i} : (i_1, ..., i_M), \vec{K} = (K_1, ..., K_M)$

### 1 - Algorithme général

1.1 Calcul de la matrice $c_1$

1.2 Calcul des coefficients de $G_1$, résultats dans $g$

1.3 $n := 2$

1.4 Calcul de la matrice $c_n$

1.5 Calcul des coefficients de $G_n$, résultat dans $p$

1.6 $g := g*p$ (produit de convolution)

1.7 $n := n+1$
Si $n > N$ alors stop
sinon aller en 1.4

### REMARQUE

Cet algorithme n'est pas utilisé tel que dans la réalité, nous verrons en effet que dans certains cas particuliers des plus utiles, des simplifications, génératrices de gains de temps et d'espace mémoire, sont possibles. De même le
processus d'initialisation de la matrice g peut être variable. Nous nous plaçons
pour l'instant dans le cas général.

## 2 - Algorithme de convolution

$$
\left|
\begin{array}{l}
\text{2.1 pour } i_1 = K_1, K_2^{-1}, \dots, 0 \\
\qquad i_2 = K_2, K_3^{-1}, \dots, 0 \\
\qquad i_M = K_M, K_{M-1}^{-1}, \dots, 0
\end{array}
\right.
\qquad \text{faire 2.2} \\
\text{2.2 } g(\vec{i}) = \sum_{\vec{0} \le \vec{j} \le \vec{i}} g(\vec{j}) p(\vec{i} - \vec{j})
$$

## REMARQUE

Dans [5] Reiser et Kobayashi proposent un deuxième algorithme plus favorable du point de vue des erreurs d'arrondi mais nécessitant une matrice auxiliaire de dimension (0: $K_1, \dots, 0: K_{M-1}$).

$$
\begin{gather*}
\text{3 - Algorithme de calcul des coefficients de } G_n \\
G_n(X_1, \dots, X_M) = \sum_{\substack{k \ge 0 \\ n}} \left( \sum_{\substack{B_n(k) \\ n!}} \prod_{r=1}^{R} C_{nr}(k) \right) \frac{\rho_{nr}^{k_{nr}} X_m^{k_{nr}}}{k_{nr}!} \quad r \in \mathcal{M}_m \\
\sum_{n_1 \ge 0} \dots \sum_{n_M \ge 0} \left( \sum_{\substack{B_n(k) \\ n!}} \prod_{m=1}^{M} C_{nr}(k) \right) \left( \sum_{\substack{\Sigma_{k_{nr}} = j_m \\ r \in \mathcal{M}_m}} \prod_{\substack{\Pi \\ r \in \mathcal{M}_m}} \frac{\rho_{nr}^{k_{nr}}}{k_{nr}!} C_{nr}(k) \right) X_m^{j_m} \quad A_n(j_m)
\end{gather*}
$$

On pourrait donc calculer dans le cas général les termes $A_n(j_m)$ directement et en déduire les coefficients de $G_n$. Cependant il est utile de conserver les coefficients $B_n(k)k! \prod_{r=1}^{R} C_{nr}(k)$ (matrice $c_n$) pour le calcul des
grandeurs relatives aux files d'attente. On les calculera donc (pour $k_{nr} = 0 \rightarrow K_r^*$
$\forall r \forall n$) et on en déduira les coefficients de $G_n$ par l'algorithme suivant

3.1 Initialiser $p := 0$

$$
3.2 \quad \text{pour } i_1 = 0, 1, \dots, K_1^* \\
\qquad \vdots \\
\qquad i_R = 0, 1, \dots, K_R^*
$$

faire 3.3

3.3 pour $m=1, \dots, M$ faire 3.4

$$
3.4 \quad j_m = \sum_{r \in \mathfrak{m}_m} i_r
$$

$$
\text{Si } j_m \le K_m \text{ alors } p(\vec{j}) := p(\vec{j}) + c_n(\vec{i})
$$

4 - Algorithme de calcul de $c_n$

Soit :

$$
c_n(k_{n1}, \dots, k_{nR}) = k_{n1}! B_n(k_n) \prod_{r=1}^{R} c_{nr}(k_{nr}) \frac{\rho_{nr}}{k_{nr}!} = B_n(k_n) c_n^!(k_{n1}, \dots, k_{nR})
$$

remarquons que :

$$
c_n^!(k_{n1}, \dots, k_{nR}) = \sum_{r=1}^{R} \rho_{nr} \frac{1}{g_{nr}(k_{nr})} c_n^!(k_{nr}, \dots, k_{nr-1}, \dots, k_{nR})
$$

d'où l'algorithme :

4.1 $c_n(\vec{0}) := 1$

$$
4.2 \quad \text{pour } i_1 = 0, \dots, K_1^* \\
\qquad \vdots \\
\qquad i_R = 0, \dots, K_R^*
$$
4.3 pour $m=1,...,M$ faire

$$j_m = \sum_{r \in \mathcal{M}_m} i_r$$

Si $j_m \le K_m$ alors

$$c_n(\vec{i}) = \sum_{r=1}^{R} \rho_{nr} \frac{1}{g_{nr}(k_{nr})} c_n(\vec{i} - \vec{u}_r)$$

$$\langle\langle \vec{u}_r \rangle\rangle = \begin{pmatrix} 0, & \dots, & 1, & \dots, & 0 \\ 1, & \dots, & r, & \dots, & R \end{pmatrix}$$

$$4.4 \quad \begin{array}{l} \text{pour } i_1 = 0, \dots, K_1^* \\ \quad \vdots \\ \\ i_R = 0, \dots, K_R^* \end{array}$$

faire 4.5

4.5 pour $m=1,...,M$ faire

$$j_m = \sum_{r \in \mathcal{M}_m} i_r$$

Si $j_m \le K_m$ alors

$$s = \sum_{m=1}^{M} j_m$$

$$c_n(\vec{i}) = B_n(s) c_n(\vec{i})$$

Notons que l'algorithme 3 peut s'intégrer à l'étape 4.5.

Nous allons présenter maintenant certains algorithmes permettant de simplifier les calculs dans les cas particuliers suivants :

- taux constants,

- stations serveur infini,

- dépendance globale,

- dépendance globale limitée.

## 5 - stations à taux constant

Le cas correspond aux algorithmes de Buzen [4] repris avec la méthode des fonctions génératrices par Williams et Bhandiwad [12].
$$
G_n(X) = \sum_{k_n \ge 0} \frac{\rho_{nr}^{k_{nr}} X_m^{k_{nr}}}{\Pi_{r=1}^{R} k_{nr}!} \quad r \in \mathfrak{M}_m \\
= \sum_{i=0}^{\infty} \left[ \sum_{r=1}^{R} \rho_{nr} X_m^r \right]^i \quad X = (X_1, X_2, \dots, X_M)
$$

Soit en posant $\bar{\rho}_{nm} = \sum_{r \in \mathfrak{M}_m} \rho_{nr}$ et $\bar{\rho}_n = (\bar{\rho}_{n1}, \dots, \bar{\rho}_{nM})$

$$
G_n(X) = \frac{1}{1 - \bar{\rho}_n \cdot X}
$$

Considérons le produit de convolution $G^* = G * G_n$

$$
G^*(X) = \frac{1}{1 - \bar{\rho}_n \cdot X} G(X)
$$

$$
\text{Soit } G^*(X) = G(X) + \bar{\rho}_n \cdot X \quad G^*(X)
$$

D'où l'algorithme qui se substitue aux algorithmes 2, 3 et 4. Dans l'algorithme
1 on remplace 1.4, 1.5, 1.6 par

$$
\left|
\begin{array}{ll}
5.1 & \text{pour } i_1 = 0, \dots, K_1 \\
    & \vdots \\
    & \vdots \\
    & i_M = 0, \dots, K_M \\
    & \text{faire } 5.2 \\
5.2 & g(\vec{i}) = g(\vec{i}) + \sum_{m=1}^{M} \bar{\rho}_{nm} g(\vec{i} - \vec{u}_m)
\end{array}
\right|
$$

REMARQUE

Le calcul des grandeurs caractéristiques sur les files d'attente ne nécessite pas la connaissance des coefficients de $G_n(X)$. Cet algorithme est dû originellement à J.P. Buzen [4].
## 6 - Stations à serveur Infini

$$ G_n(X) = \sum_{\substack{R \\ k_n \ge 0}} \prod_{r=1}^{R} \frac{\rho_{nr}^{k_{nr}} X_m^{k_{nr}}}{k_{nr}!} \\ = \sum_{i=0}^{\infty} \frac{1}{i!} \left[ \sum_{r=1}^{R} \rho_{nr} X_m \right]^i = \exp \left[ \sum_{r=1}^{R} \rho_{nr} X_m \right] $$

Soit avec les conventions introduites précédemment :

$$ G_n(X) = \exp[\bar{\rho}_n \cdot X] $$

Considérons l'ensemble des stations à serveur infini du réseau.

Soit $n_0$ leur nombre :

$$ \prod_{n=1}^{n_0} G_n(X) = \exp \left[ \left( \sum_{n=1}^{n_0} \bar{\rho}_n \right) \cdot X \right] $$

Nous avons donc intérêt, pour ce qui concerne le calcul de la constante de normalisation, à regrouper ces stations en une station équivalente telle que :

$$ \rho_0 = \sum_{n=1}^{n_0} \bar{\rho}_n $$

et remplacer l'initialisation de la matrice g dans l'algorithme 1 par un calcul préliminaire :

$$ 6.1 \quad g(\vec{0}) := 1 $$

$$ 6.2 \quad \text{pour } m=1, \dots, M \text{ faire} \\ \text{pour } i=1, \dots, K_m \text{ faire} \\ g(i\vec{u}_m) := \rho_{0m} g((i-1)\vec{u}_m)/i $$

$$ 6.3 \quad \text{pour } i_1 = 0, \dots, K_1 \\ \vdots \\ i_M = 0, \dots, K_M $$

$$ \text{faire} \qquad M \\ g(\vec{i}) := \prod_{m=1}^{M} g(i \cdot \vec{u}_m) $$
# 7 - Dépendance globale

On entend par dépendance globale les cas où le taux de service n'est fonction que du nombre total de clients dans la station. On rappelle que dans ce cas :

$$ 
\begin{aligned}
G_n(X) &= \sum_{k \ge 0} B_n(k) \frac{\rho_{nr}^{k_{nr}} X_m^{k_{nr}}}{\Pi_{n}! k_{nr}!} \quad \Pi_{n} \quad r \in \mathbb{N}_m \\
&= \sum_{i=0}^{\infty} B_n(i) (\bar{\rho}_n \cdot X)^i
\end{aligned}
$$

Nous pouvons donc court-circuiter l'algorithme 3 et simplifier l'algorithme 4 :

$$ 7.1 \quad c_n(\vec{0}) := 1 $$

$$ 
\begin{array}{l}
7.2 \quad \text{pour } i_1 = 0, \dots, K_1 \\
\quad \dots \\
\quad \dots \\
\quad i_M = 0, \dots, K_M
\end{array}
$$

faire 7.3

$$ 7.3 \quad c_n(\vec{i}) = \sum_{m=1}^{M} \bar{\rho}_{nm} c_n(\vec{i} - \vec{u}_m) $$

$$ 
\begin{array}{l}
7.4 \quad \text{pour } i_1 = 0, \dots, K_1 \\
\quad \dots \\
\quad i_M = 0, \dots, K_M
\end{array}
$$

faire 7.5

$$ 7.5 \quad s = \sum_{m} i_m $$

$$ c_n(\vec{i}) = B_n(s) c_n(\vec{0}) $$

# 8 - Dépendance globale limitée

Nous nous plaçons dans les hypothèses précédentes en supposant en outre qu'il existe $d_n$ tel que :

$$ k_n < d_n \qquad \mu_{nr} = \mu_{nr}^0 h_n(k_n) $$

$$ k_n \ge d_n \qquad \mu_{nr} = \mu_{nr}^0 \beta_n $$

Dans ce cas d'après le paragraphe III.3 on a :

$$ G_n(X) = \gamma_n(X) / (1 - \bar{\rho} \cdot X / \beta_n) $$

$$ d_n - 1 $$

$$ \text{avec} \quad \gamma_n(X) = 1 + \sum_{i=1}^{d_n-1} \left( B_n(i) - B_n(i-1) / \beta_n \right) (\rho_n \cdot X)^i $$
Donc le produit de convolution pourra se faire en deux étapes :

$$ \text{- produit par } \frac{1}{1 - \frac{\rho_n \cdot X}{\beta_n}} \text{ (phase taux constant)} $$

- produit par $\gamma_n(X)$ en ne calculant que les termes utiles.

Un calcul de ce type peut être utile dans la modélisation d'une station PAPS à $d_n$ serveurs (lois exponentielles). Dans ce cas, on utilise une station monoserveur dont le taux de service dépend de l'état de la station [5] :

$$ \mu_n(k_n) = \mu_n^0 \min(k_n; d_n) $$

où $k_n$ est le nombre de clients dans la station.

## CONCLUSION

Les algorithmes que nous avons présentés ont pour but de calculer la constante de normalisation. Comme sous-produit de ces calculs, on peut déduire (si l'on a conservé les matrices $\tilde{c}_n$) les probabilités stationnaires marginales. Cependant on s'intéresse le plus souvent à des grandeurs dérivées telles que :

- l'utilisation des serveurs,

- les longueurs moyennes des files d'attente,

- les débits.

Le paragraphe suivant présente les algorithmes de calcul de telles quantités.

### IV.3 - Algorithmes de calcul des statistiques

#### IV.3.1 - Probabilités marginales

La fonction génératrice des probabilités marginales $p_n(k_{n1}, \dots, k_{nR})^{(1)}$ est :

$$ G_{p_n}(z_{n1}, z_{n2}, \dots, z_{nR}) = C^{-1} G_{n-}(X) C_n(z_{n1}, z_{n2}, \dots, z_{nR}, X) $$
au point $K_1, \dots, K_M$

où : $G_{n-}(X)$ est le produit de convolution sur les N-1 stations différentes de n ($G_{n-}$ la matrice correspondante)

<footnote>(1) Probabilité qu'il y ait $k_{nr}$ ($r = 1 \to R$) clients de classe i dans la station n.</footnote>
$$
\dot{c}_n(z_{n1}, \dots, z_{nR}, X) = \sum_{\substack{k \ge 0 \\ n}} \prod_{R} \prod_{r=1}^{R} c_{nr}(k) \frac{(p_{nr} z_{nr} x_m)^{k_{nr}}}{k_{nr}!} \quad r \in \mathcal{M}_m
$$

Remarquons que les coefficients de $G_{n-}$ peuvent être obtenus par
l'algorithme 1 où l'on omet la nième convolution. Les coefficients de $C_n$ sont
obtenus par l'algorithme 4. Soit le R-uplet $(i_1, \dots, i_R)$ pour lequel $p_n(i_1, \dots, i_R)$
existe. Alors $(i_1, \dots, i_R)$ satisfait

$$
\forall m \quad \sum_{r \in \mathcal{M}_m} i_r = j_m \le K_m
$$

et on a

$$
C_{p_n}(i_1, \dots, i_R) = g_{n-}(K_1 - j_1, \dots, K_M - j_M) \cdot c_n(i_1, \dots, i_R)
$$

IV.3.2 - Taux d'utilisation des serveurs et nombre moyen de clients
dans les stations

L'utilisation d'une station n pour une classe r est définie comme la proportion
de temps pendant laquelle le serveur est utilisé par un client de classe r.

S'il y a $k_{n1}, \dots, k_{nR}$ clients dans la station, la probabilité pour qu'un
client de classe r soit en cours de service est :

$$
\frac{k}{\sum_{r} k_{nr}} p_{n}(k_{n1}, \dots, k_{nR})
$$

On obtient l'utilisation en sommant sur tous les cas possibles.

Le nombre moyen de clients de classe r dans une station n est donné de même par

$$
\sum_{\text{états}} k_{nr} p_n(k_{n1}, \dots, k_{nR})
$$

On en déduit les algorithmes suivants :
# 1 - Cas général : taux d'utilisation et nombre moyen de clients

8.1 pour $r = 1,...,R$ faire
$\text{util}_{nr} := 0$.
$\text{lgq}_{nr} := 0$.

8.2 pour $i_1 = 0,...,K_1^*$
... $i_r = 1,...,K_r^*$
... $i_R = 0,...,K_R^*$

faire 8.3

8.3 pour $m = 1,...,M$ faire

$$j_m = \sum_{r \in \mathcal{M}_m} i_r$$

Si $j_m \le K_m$ faire 8.4

$$8.4 \quad p_n = g_{n-} (K_1 - j_1, \dots, K_M - j_M) \cdot c_n (i_1, \dots, i_R)$$

pour $r = 1,...,R$ faire

$$\text{util}_{nr} = \text{util}_{nr} + \frac{i_r}{\sum_r i_r} p_n$$

$$\text{lgq}_{nr} = \text{lgq}_{nr} + i_r p_n$$

8.5 $\text{util}_{nr} = \text{util}_{nr}/C$

$$\text{lgq}_{nr} = \text{lgq}_{nr}/C$$

Dans les cas particuliers cités plus haut, certaines simplifications peuvent encore intervenir.

# 2 - Dépendance globale

Nous avons vu au paragraphe précédent que pour les calculs de la constante de normalisation concernant de telles stations nous pouvions créer des classes fictives caractérisées par $\bar{\rho}_n = (\bar{\rho}_{n1}, \dots, \bar{\rho}_{nM})$ où $\bar{\rho}_{nm} = \sum_{r \in \mathcal{M}_m} \rho_{nr}$.
Nous pouvons calculer un taux d'utilisation, une longueur moyenne de file d'attente pour une telle classe. Ce calcul, analogue à l'algorithme précédent, est simplifié en ce sens que les indices portant sur les sous-chaînes, les tests sont supprimés.

Il serait regrettable qu'usant de cette bonne propriété on ne puisse déterminer simplement taux d'utilisation et nombre moyen de clients par classe connaissant le résultat relatif à la sous-chaîne à laquelle appartient cette classe. Nous nous proposons de montrer que :

$$ 
\begin{aligned}
\forall r \in \mathcal{M}_m \quad & \text{util}_{nr} = \frac{\rho_{nr}}{\rho_{nm}} \quad \text{util}_{nm} \\
& \lg q_{nr} = \frac{\rho_{nr}}{\rho_{nm}} \quad \lg q_{nm}
\end{aligned}
$$

## ■ Utilisation

$$ C \text{ util}_{nr} = \sum_{j_1=0}^{K_1} \dots \sum_{j_m=1}^{K_m} \dots \sum_{j_M=0}^{K_M} g_{n-} (K_1-j_1, \dots, K_M-j_M) F(j_1, \dots, j_M) $$

avec

$$ F(j_1, \dots, j_M) = \sum_{s \in \mathcal{M}_1} \dots \sum_{s \in \mathcal{M}_m} \dots \sum_{s \in \mathcal{M}_M} c_n(k_{n1}, \dots, k_{nR}) \frac{k_{nr}}{\sum_{s=1}^{R} k_{ns}} \sum_{k_{ns}=j_1} \sum_{k_{ns}=j_M} \sum_{k_{nr} \neq 0} k_{nr} $$

$$ F(j_1, \dots, j_M) = \sum_{s \in \mathcal{M}_1} \dots \sum_{s \in \mathcal{M}_M} B_n(k_n)_k \prod_{s=1}^{R} \frac{\rho_{ns}}{k_{ns}!} \sum_{s \in \mathcal{M}_m} \left[ \prod_{s \in \mathcal{M}_m} \frac{\rho_{ns}}{k_{ns}!} \cdot \frac{k_{nr}}{k_{nR}} \right] \sum_{k_{ns}=j_1} \sum_{k_{ns}=j_M} \sum_{s \in \mathcal{M}_m} k_{ns} $$

$$ \text{or} \quad \sum_{s \in \mathcal{M}_m} \prod_{k \in \mathcal{M}_m} \frac{k_{ns}}{\rho_{ns}} = \frac{\rho_{nr}}{k_n} \sum_{s \in \mathcal{M}_m} \prod_{k \in \mathcal{M}_m} \frac{k_{nr}}{\rho_{ns}} \cdot \sum_{k \in \mathcal{M}_m} \frac{k_{nr}}{\rho_{ns}} = j_m $$
Donc $C \text{ util}_{nr} = \rho_{nr} \times \mathcal{F}(K_1, \dots, K_m^{-1}, \dots, K_M)$ $\forall r \in \mathcal{M}$

D'autre part $\sum_{r \in \mathcal{M}} \text{util}_{nr} = \text{util}_{nm}$

D'où le résultat pour les taux d'utilisation.

## nombre moyen de clients dans une station

La fonction génératrice de la probabilité marginale $p_n(k_{nr})$ est :

$$G_{nr}(z_{nr}) = C^{-1} G_{n-}(x) \sum_{i=0}^{\infty} B_n(i) (\rho_{n1} x_{\sigma(1)} + \dots + \rho_{nr} x_{\sigma(r)} + \dots + \rho_{nR} x_{\sigma(R)})^i$$
au point $K_1, \dots, K_M$

$$\sigma(r) = m \text{ si } r \in \mathcal{M}$$

La longueur de file d'attente pour la classe r :

$$\left[ \frac{\partial G_{nr}(z_{nr})}{\partial z_{nr}} \right]_{z_{nr}=1} = C^{-1} G_{n-}(x) \sum_{i=1}^{\infty} i B_n(i) \rho_{nr} x_{\sigma(r)} (\rho_{n1} x_{\sigma(1)} + \dots + \rho_{nM} x_{\sigma(M)})^i$$
au point $K_1, \dots, K_M$

Définissons de même $p_n(k_{nm})$ probabilité marginale qu'il y ait $k_{nm}$ clients de la sous-chaîne m dans la station n et sa fonction génératrice :

$$G_{nm}(z_{nm}) = C^{-1} G_{n-}(x) \sum_{i=0}^{\infty} B_n(i) [\bar{\rho}_{n1} x_1 + \dots + \bar{\rho}_{nm} x_m z_{nm} + \dots + \bar{\rho}_{nM} x_M]^i$$
au point $K_1, \dots, K_M$

d'où la longueur de la file :

$$\left[ \frac{\partial G_{nm}(z_{nm})}{\partial z_{nm}} \right]_{z_{nm}=1} = C^{-1} G_{n-}(x) \sum_{i=1}^{\infty} i B_n(i) \bar{\rho}_{n1} x_1 [\bar{\rho}_{n1} x_1 + \dots + \bar{\rho}_{nM} x_M]^i$$
au point $K_1, \dots, K_M$
Donc directement si $r \in \mathfrak{M}_m$

$$lgq_{nr} = \rho_{nr} g(K_1, \dots, K_M)$$

$$lgq_{nm} = \bar{\rho}_{nm} g(K_1, \dots, K_M)$$

et le résultat recherché.

### 3 - Taux Constant

Ce cas étant un cas particulier du précédent, nous posons le problème au niveau des sous-chaînes.

#### ■ Utilisations

$$C_{\text{util}}_{nm} = \sum_{j_1=0}^{K_1} \dots \sum_{j_m=1}^{K_m} \sum_{j_M=0}^{K_M} g_{n-}(K_1-j_1, \dots, K_M-j_M) \stackrel{M}{\underset{q=1}{\Pi}} \frac{j_{q-1}}{j_q} \frac{j_q}{j}$$

$$\text{avec } j = \sum_m j_m$$

$$C_{\text{util}}_{nm} = \bar{\rho}_{nm} \sum_{j=0}^{K_1} \dots \sum_{j_m=1}^{K_m} \dots \sum_{j_M=0}^{K_M} g_{n-}(K_1-j_1, \dots, K_M-j_M) \stackrel{M}{\underset{j_1! \dots (j_M-1)! \dots j_M!}{\Pi}} \frac{j_1}{j} \frac{j-M-1}{M-1} \frac{j_M}{j}$$

Soit en changeant l'individage ($j_M \leftarrow j_M^{-1}$)

$$C_{\text{util},m} = \bar{\rho}_{nm} \sum_{j=0}^{K_1} \dots \sum_{j_m=0}^{K_m-1} \dots \sum_{j_M=0}^{K_M} g_{n-}(K_1-j_1, \dots, K_M-j_M-1, \dots, K_M) \stackrel{M}{\underset{m=1}{\Pi}} \frac{j}{j_M}$$

$$\text{d'où} \quad C_{\text{util}}_{nm} = \bar{\rho}_{nm} g(K_1, \dots, K_{m-1}, \dots, K_M)$$

(ce qui est le résultat classique de Buzen [ 4]).

#### ■ Nombre moyen de clients dans une station

La fonction génératrice de $p_n(k)$ est :

$$G_{nm}(z) = z^{-1} G_{n-}(z) \sum_{i=0}^{\infty} (\bar{\rho}_{n1} z_1 + \dots + \bar{\rho}_{nm} z_m z_{nm} + \dots + \bar{\rho}_{nM} z_M)^i \quad \text{au point } K_1, \dots, K_M$$
$$ = C^{-1} G_{n-}(X) \frac{1}{1 - \left( \bar{\rho}_{n1} X_1 + \dots + \bar{\rho}_{nm} X_m \right) \left( \bar{\rho}_{nM} X_M + \dots + \bar{\rho}_{nM} X_M \right)} $$

D'où

$$ \lg q_{nm} = \left( \frac{\partial G_{nm}}{\partial z_{nm}} \right)_{z_{nm}=1} = C^{-1} G_{n-}(X) \frac{\bar{\rho}_{nm} X_m}{\left[ 1 - \left( \bar{\rho}_{n1} X_1 + \dots + \bar{\rho}_{nM} X_M \right) \right]^2} $$

$$ \lg q_{nm} = C^{-1} G(X) \frac{\bar{\rho}_{nm} X_m}{1 - \left( \bar{\rho}_{n1} X_1 + \dots + \bar{\rho}_{nM} X_M \right)} $$

D'où le calcul :

$$ \text{9.1} \quad \text{appliquer l'algorithme 5 à $g_{n+}$} $$

$$ \text{9.2} \quad C \lg q_{nm} = \bar{\rho}_{nm} g_{n+} (K_1, \dots, K_{m-1}, \dots, K_M) $$

### 4 - Station à Serveur Infini

Le calcul du nombre moyen de clients est très simple :

$$ G_{nm}(z_{nm}) = C^{-1} G_{n-}(X) \exp[\bar{\rho}_{n1} X_1 + \dots + \bar{\rho}_{nm} X_m z_{nm} + \dots + \bar{\rho}_{nM} X_M] $$
au point $K_1, \dots, K_M$

d'où

$$ \lg q_{nm} = C^{-1} G_{n-}(X) \exp[\bar{\rho}_{n1} X_1 + \dots + \bar{\rho}_{nM} X_M] \times \bar{\rho}_{nm} X_m \\ = C^{-1} G(X) \bar{\rho}_{nm} \times X_m \quad \text{au point } K_1, \dots, K_M $$

$$ \text{et} \quad \lg q_{nm} = C^{-1} g(K_1, \dots, K_{m-1}, \dots, K_M) \bar{\rho}_{nm} $$

### IV.3.3 - Calcul du débit

Un client de classe r est en cours de service à la station n dans l'état $(k_{n1}, \dots, k_{nR})$ avec la probabilité :
$$ \frac{k_{nr}}{\sum_{r} k_{nr}} p_n(k_{n1}, \dots, k_{nR}) $$

Ce client est servi suivant le taux $\mu_{nr}^0 h_n^{(k)} g_{nr}^{(k)}$.

D'où le débit :

$$ \sum_{k_n \text{ possible}} \mu_{nr}^0 h_n^{(k)} g_{nr}^{(k)} \frac{k_{nr}}{\sum_{nr} k_{nr}} p_n(k_{n1}, \dots, k_{nR}) $$

Expression qui est complexe. Une simplification s'impose :

$$ \begin{align*} C_{\text{deb}}_{nr} &= \sum_{k_n \text{ possible}} g_{n-}^{(K_1-j_1, \dots, K_M-j_M)} \chi_{(k_{n1}, \dots, k_{nR})} \\ \chi_{(k_{n1}, \dots, k_{nR})} &= B_n^{(k_n)k_n!} \left[ \begin{array}{cc} R & k_{ns} \\ \Pi_{s=1} & \rho_{ns} \end{array} \begin{array}{c} k_{ns} \\ \frac{\rho_{ns}}{k_{ns}!} \end{array} \right] \frac{k_{nr}}{k_n} \mu_{nr}^0 h_n^{(k_n)g_{nr}^{(k_{nr})}} \\ &= B_n^{(k_n-1)(k_n-1)!} \left[ \begin{array}{cc} R & k_{ns} \\ \Pi_{s=1} & \rho_{ns} \end{array} \begin{array}{c} k_{ns} \\ \frac{\rho_{ns}}{k_{ns}!} \end{array} \right] \frac{C_{nr}^{(k_{nr}-1)}}{(k_{nr}-1)!} \rho_{nr}^{k_{nr}-1} e_{nr} \end{align*} $$

D'où, de même que précédemment :

$$ C_{\text{deb}}_{nr} = e_{nr} g(K_1, \dots, K_{M-1}, \dots, K_M) \quad \text{si } r \in \mathcal{M}_M $$

### IV.3.4. - Grandeurs diverses

#### 1 - Temps moyen de résidence dans une station

A l'état d'équilibre nous pouvons utiliser la formule de Little [25] en notant $\omega_{nr}$ ce temps moyen de résidence :

$$ \omega_{nr} = \frac{\lg q_{nr}}{\text{deb}_{nr}} $$

#### 2 - Probabilités marginales

Nous avons vu au paragraphe IV.3.1 que la probabilité marginale que $(k_{n1}, \dots, k_{nR})$ clients de classe $(1, \dots, R)$ se trouvent dans la station n est :
$$p_n(k_{n1}, \dots, k_{nR}) = \frac{1}{C} c_n(k_{n1}, \dots, k_{nR}) \bar{s}_{n-}(K_1 - \bar{k}_{n1}, \dots, K_M - \bar{k}_{nM})$$

$$\text{où} \qquad \bar{k}_{nm} = \sum_{r \in \mathcal{M}_m} k_{nr}$$

Cependant pour des stations à taux constant, nous ne calculerons explicitement ni les matrices $c_n$ ni les matrices $g_{n-}$.

Pour des stations à dépendance globale ou serveur infini la matrice $g_{n-}$ est calculée, mais la matrice $c_n$ porte sur les classes principales.

Le problème du calcul des matrices $c_n$ peut être résolu en utilisant l'algorithme 4 du paragraphe IV.2.

On montre d'autre part très simplement que dans le cas d'une station à taux constant on a :

$$g_{n-}(K_1 - \bar{k}_{n1}, \dots, K_M - \bar{k}_{nM}) = g(K_1 - \bar{k}_{n1}, \dots, K_M - \bar{k}_{nM}) \\ - \sum_m \bar{\rho}_{nm} g(K_1 + \bar{k}_{n1}, \dots, K_M - \bar{k}_{nm} - 1, \dots, K_M - \bar{k}_{nM}) \\ \qquad \bar{k}_{nm} \neq K_M$$

Le calcul est donc réalisable sans trop perdre les avantages que nous avions notés dans les calculs relatifs aux stations à taux constant.

## IV.4 - Mise en oeuvre des algorithmes

### IV.4.1 - Contrôle des débordements

La constante de normalisation est obtenue comme somme de termes positifs. La valeur prise peut alors être très grande et en conséquence dépasser le maximum admissible sur la machine.

D'autre part, nous avons vu que les taux d'arrivée $e_{nr}$ sont pour un réseau fermé définis à une constante près. Nous pouvons donc espérer contrôler la valeur de ces coefficients de façon que le calcul de la constante de normalisation n'entraîne pas de débordement de capacité.
Nous nous proposons de donner une méthode assez brutale pour obtenir
un tel contrôle.

Soient {$\rho_{nr}$ ; n=1 → N} l'ensemble des valeurs des intensités de trafic
obtenu initialement.

Un majorant de la constante de normalisation est :

$$
C_O = \prod_{n=1}^{N} \sum_{k_n \ge 0} B_n(k_n) \prod_{r=1}^{R} C_{nr}(k_{nr})^{\frac{\rho_{nr}}{k_{nr}}} \prod_{n=1}^{N} \rho_{nr}
$$

$$
\text{soient :} \qquad \beta_n = \sup_i B_n(i) \qquad \forall n
$$

$$
\gamma_{nr} = \sup_{j} (C_{nr}(j)) \quad \forall n \forall r
$$

$$
\text{et} \quad \alpha_n = \beta_n \prod_{r=1}^{R} \gamma_{nr}
$$

$$
\text{alors :} \qquad C_O \le \prod_{n=1}^{N} \alpha_n \frac{1}{1-\bar{\rho}_n}
$$

D'autre part :

$$
\text{si} \quad \rho_M = \sup_n (\bar{\rho}_n) \quad \text{alors} \quad C_O \le \left[ \prod_{n=1}^N \alpha_n \right] \left[ \frac{1}{1-\rho_M} \right] = C_f
$$

Soit $\delta$ une constante inférieure au maximum admissible de la machine. Si $C_f$ est inférieur ou égal à $\delta$ alors la constante de normalisation le sera aussi sinon soit a tel que :

$$
a = \frac{1}{\rho_M} \left[ \sqrt{ \frac{N}{\prod_{n=1}^{N} \alpha_n}} \cdot \delta \right] + \rho_M^{-1}
$$

alors si l'on multiplie $\rho_{nr}$ par $(1-a)$ pour tout n et r, la constante de normalisation obtenue avec ces nouvelles valeurs sera inférieure à $\delta$.
■ De même il est possible que les termes qui composent la constante de normalisation soient suffisamment faibles pour que cette constante soit très faible et $1/C$ supérieur au maximum admissible.

Il est toujours possible de multiplier les taux relatifs d'arrivée par un coefficient $b > 1$ bien choisi (tout le problème est là).

■ Une solution heuristique est proposée par Balbo et al. [20]. Elle consiste à minimiser la distance des intensités de traffic par rapport à l'unité. La distance choisie étant une distance quadratique, il faut minimiser le carré des écarts par rapport à 1.

Pour chaque sous-chaîne m on obtient le coefficient multiplicatif suivant :

$$ \forall m \in [1, M] \quad c_m = \frac{\sum_{n=1}^{N} \sum_{r \in \mathcal{M}_m} \rho_{nr}}{\sum_{n=1}^{N} \sum_{r \in \mathcal{M}_m} \rho_{nr}^2} $$

### IV.4.2 - Encombrement Mémoire

Rappelons les notations suivantes :

• $K_m : m = 1 \to M$ nombre de clients dans la sous-chaîne $\mathcal{M}_m$

• $K_r^* : r = 1 \to R$ $K_r^* = K_m$ si $r \in \mathcal{M}_m$.

Pour les algorithmes que nous avons présentés et pour éviter des calculs inutiles il est nécessaire de disposer de :

• une matrice $g(0:K_1, \dots, 0:K_M)$ contenant les constantes de normalisation du réseau $(g(k_1, \dots, k_M))$ est la constante de normalisation si $k_1 \in \mathcal{M}_1, \dots, k_M \in \mathcal{M}_M$ clients parcourent le réseau).

• une matrice tampon $p(0:K_1, \dots, 0:K_M)$

• pour toute station M à taux de service dépendants : une matrice $g_{n-}(0:K_1, \dots, 0:K_M)$ obtenue par convolution sur les $N-1$ stations différentes de la nième.
* pour toute station n à taux globalement dépendant : une matrice de "capacité" $c_n(0:K_1, ..., 0:K_M)$.

* pour toute station n à taux dépendants par classes : une matrice de "capacité" $c_n(0:K_1^*, ..., 0:K_R^*)$. Une matrice de taille $(0:K_1^*, ..., 0:K_R^*)$ sera nécessaire si l'on veut calculer les probabilités marginales pour une ou plusieurs stations.

Pour une réalisation pratique nous voyons donc que la place mémoire requise peut être élevée :

## EXEMPLE

pour un réseau comportant :

- 4 stations (dépendance globale)

- 4 sous-chaînes (1 classe par sous-chaîne)

- 5 clients par classe

nous avons besoin de :

- matrice g : 1296 mots

- 4 matrices $g_n$ : 5184 mots

- 4 matrices $c_n$ : 5184 mots

- 1 matrice tampon : 1296 mots

à moins d'effectuer plusieurs fois les mêmes calculs.

Il peut donc sembler utile de ne réserver que la place strictement nécessaire aux calculs et donc de devoir renourir à des possibilités d'allocation dynamique.

## V - RESEaux MIXTES

* Dans la suite nous supposerons que le réseau considéré est composé de :

$M_1$ sous-chaînes fermées , $R_1$ classes

$M_2$ sous-chaînes ouvertes , $R_2$ classes
le nombre total de client pour une sous-chaine fermée sera noté $K_m, m=1, M_1$.

Les états du réseau constituent l'ensemble $\mathcal{M}$ :

$$ \mathcal{M} = \{ \vec{K} = \{ \vec{k}_1, \dots, \vec{k}_N \} \} $$

où

$$ \vec{k}_n = (k_{n1}, \dots, k_{nR_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2} + R_1) $$

où $k_{nr}$ est le nombre de clients de classe r dans la station n pour une sous-chaine fermée ($r=1, R_1$)

$\ell_{ns}$ est le nombre de clients de classe r dans la station n pour une sous-chaine ouverte ($s=R_1+1, R_1 + R_2$).

Dans [5], Reiser et Kobayashi examinent le cas des réseaux mixtes dans le cadre des hypothèses 1 et 2 du paragraphe II. Les résultats essentiels à retenir sont :

- La stabilité du réseau est liée à la stabilité des sous-chaines ouvertes uniquement.

- Dans le cas où le réseau est stable on a :

$$ C^{-1} = \prod_{n=1}^{N} \sum_{i=1}^{\infty} B_n(i) (\bar{\rho}_{n,2} + \bar{\rho}_{n,1} \cdot X)^i \quad \text{au point } K_1, \dots, K_{M_1} $$

où

$$ \left\{ \begin{array}{ll} \bar{\rho}_{n,1} = \sum_{r=1}^{R_1} \rho_{nr} & \text{sous-chaines fermées} \\ \bar{\rho}_{n,2} = \sum_{s=R_1+1}^{R_1+R_2} \rho_{ns} & \text{sous-chaines ouvertes} \end{array} \right. $$

En conséquence, les réseaux mixtes cumulent les désavantages des réseaux ouverts et des réseaux fermés :
- pour les sous-chaines ouvertes : problème d'existence d'une solution stable,

- pour les sous-chaines fermées : condition supplémentaire pour chaque sous-chaine $m$ :

$$ \sum_{n=1}^{N} \sum_{r \in \mathcal{M}_m} k_{nr} = K_m $$

Dans la suite nous n'examinerons que les cas particuliers que nous pouvons résoudre à priori :

- stations à taux constant

- stations de type serveur infini

- stations à dépendance globale limitée.

dans l'hypothèse d'arrivée de poissonniennes constantes.

## V.1 - Constante de normalisation

Dans le cadre des hypothèses 1 et 2, en supposant que le réseau est stable la probabilité que ce réseau soit dans un état $\vec{K}$ est :

$$ \text{Prob}(\vec{K}) = \frac{1}{C} \prod_{n=1}^{N} B_n(k_n) \prod_{r=1}^{R_1} \frac{\rho_{nr}^{k_{nr}}}{k_{nr}!} \prod_{s=R_1+1}^{R_1+R_2} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} $$

un état $\vec{K}$ est "possible" si et seulement si :

$$ \begin{cases} \forall n \ \forall s = R_1+1, R_2+R_1 : & \ell_{ns} \ge 0 \quad (K_1) \\ \forall n \ \forall r = 1, R_1 : & k_{nr} \ge 0; \ \forall m \ \sum_{n=1}^{N} \sum_{r \in \mathcal{M}_m} k_{nr} = K_m \quad (K_2) \end{cases} $$

D'où la constante de normalisation si elle existe :

$$ C = \sum_{K_2} \sum_{K_1} \prod_{n=1}^{N} B_n(k_n) \prod_{r=1}^{R_1} \frac{\rho_{nr}^{k_{nr}}}{k_{nr}!} \prod_{s=R_1+1}^{R_2+R_1} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} $$
P'ouï : si $K'_1 = \{ \ell_{ns} / \ell_{ns} \ge 0, s = R_1+1, R_1 + R_2 \}$

$$
C = \sum_{K_2} \left[ \sum_{n=1}^{N} \binom{R_1}{\ell_{nr}} \binom{k_{nr}}{\ell_{nr}!} \prod_{s=R_1+1}^{R_1+R_2} \frac{\rho_{ns}}{\ell_{ns}!} \right]
$$

Poisson :

$$
\cdot |\vec{k}_n| = \bar{k}_n + \bar{\ell}_n = k_n
$$

avec
$$
\left\{
\begin{array}{l}
\bar{k}_n = \sum_{r=1}^{R_1} k_{nr} \\
R_2 \\
\bar{\ell}_n = \sum_{s=R_1+1}^{R_2} \ell_{ns} \\
R_1+R_2 \\
\hfill \ell_{ns} = R_1+1
\end{array}
\right.
\quad \prod_{n=R_1+1}^{R_2} \frac{\rho_{ns}}{\ell_{ns}!} = \prod_{n=0}^{\infty} B_n(\bar{k}_n+i) \frac{(\bar{k}_n+i)!}{i!} \rho_n^{-i}
$$

$$
\left\{
\begin{array}{l}
\bar{k}_n = \sum_{r=1}^{R_1} k_{nr} \\
R_2 \\
\bar{\ell}_n = \sum_{s=R_1+1}^{R_2} \ell_{ns} \\
R_1+R_2 \\
\hfill \ell_{ns} = R_1+1
\end{array}
\right.
$$

$$
\cdot \rho_n^{-0} = \sum_{s=R_1+1}^{R_2} \rho_{ns}
$$

$$
\cdot c_n(\bar{k}_n) = \sum_{K_1} B_n(k_n) \rho_{n1}^{k_1} \prod_{s=R_1+1}^{R_2} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} = \sum_{i=0}^{\infty} B_n(\bar{k}_n+i) \frac{(\bar{k}_n+i)!}{i!} \rho_n^{-i}
$$

V.1.1 - Stations à taux constant

Dans ce cas $B_n(k_n) = 1$ pour tout $k_n$

$$
P'\text{où } c_n(\bar{k}_n) = \sum_{i=0}^{\infty} \frac{(\bar{k}_n + i)!}{i!} \rho_n^{-0i} = \frac{\bar{k}_n!}{(1 - \rho_n^{-0})^{\bar{k}_n + 1}} \quad \text{si } \rho_n^{-0} < 1
$$

et les termes correspondant à la station n dans le calcul de la constante
de normalisation :

$$
\frac{1}{1 - \rho_n^{-0}} \left( \bar{k}_n! \sum_{r=1}^{R_1} \frac{1}{k_{nr}!} \left( \frac{\rho_{nr}}{1 - \rho_n^{-0}} \right)^{k_{nr}} \right)
$$

On utilisera donc l'algorithme de Buzen (IV.2.5).
### V.1.2 - Stations serveur infini

$$ \text{On a } B_n(k) = \frac{1}{(\bar{k}_n + \bar{l}_n)!} $$

$$ \text{D'où } C_n(\bar{k}_n) = \sum_{i=0}^{\infty} \frac{\rho_n^{-i}}{i!} = \exp(\rho_n^0) $$

On utilise l'algorithme IV.2.6.

### V.1.3 - Dépendance globale limitée

Rappelons que dans ce cas nous supposons que si $k$ est le nombre total de clients dans la station n :

$$ \mu_{nr} = \mu_{nr}^{0} h_{n}(k) \quad \text{si } k < d_{n} $$

$$ \mu_{nr} = \mu_{nr}^{0} \beta_{n} \quad \text{si } k \geq d_{n} $$

$$ \text{alors :} \quad B_n(k) = \begin{cases} \displaystyle \sum_{i=0}^{k} \frac{1}{h_n(i)} & \text{si } k < d_n \quad (\text{avec } h_n(0) = 1) \\ B_n(d_n-1) \frac{1}{k-d_n+1} & \text{si } k \geq d_n \end{cases} $$

$$ a) \bar{k}_n \geq d_n $$

$$ C_n(\bar{k}_n) = \sum_{i=0}^{\infty} B_n(i+\bar{k}_n) \frac{(i+\bar{k}_n)!}{i!} \rho_n^{-i} = \frac{B_n(d_n-1)}{\bar{k}_n - d_n + 1} \sum_{i=0}^{\infty} \frac{(i+\bar{k}_n)!}{i!} \left( \frac{\rho_n^0}{\beta_n} \right)^i $$

$$ \text{si } \frac{\rho_n^0}{\beta_n} < 1 \text{ alors } A = \frac{B_n(d_n-1)}{\beta_n \frac{k_n - d_n + 1}{\beta_n}} \frac{\bar{k}_n!}{\left(1 - \frac{\rho_n^0}{\beta_n}\right)^{\bar{k}_n + 1}} $$
b) $\bar{k}_n < d_n$

$$C_n(\bar{k}_n) = \sum_{i=0}^{d_n - \bar{k}_n - 1} B_n (i+\bar{k}_n) \frac{(i+\bar{k}_n)!}{i!} \bar{\rho}_n^{-i} + \frac{B_n (d_n - 1)}{\bar{k}_n d_n + 1} \left[ \sum_{i=0}^{\infty} \frac{(i+\bar{k}_n)!}{i!} \left( \frac{\bar{\rho}_n^0}{\bar{\beta}_n} \right)^i - \sum_{i=0}^{d_n - \bar{k}_n - 1} \frac{(i+\bar{k}_n)!}{i!} \left( \frac{\bar{\rho}_n^0}{\bar{\beta}_n} \right)^i \right]$$
et si $\frac{\bar{\rho}_n^0}{\bar{\beta}_n} < 1$

$$C_n(\bar{k}_n) = \frac{B_n (d_n - 1)}{\bar{k}_n d_n + 1} \frac{\bar{k}_n!}{\left(1 - \frac{\bar{\rho}_n^0}{\bar{\beta}_n}\right)^{\bar{k}_n + 1}} + \sum_{i=0}^{d_n - \bar{k}_n - 1} \left( B_n (i+\bar{k}_n) - \frac{B_n (d_n - 1) \bar{\beta}_n}{\bar{k}_n + i} \right) \frac{(i+\bar{k}_n)!}{i!} \bar{\rho}_n^{-i}$$

On pourra donc appliquer les algorithmes IV.2.7 pour la station n,
à condition que $\frac{\bar{\rho}_n^0}{\bar{\beta}_n} < 1$.

## V.2 - grandeurs élémentaires

on ne se préoccupe de ces calculs que dans les cas envisagés précédemment.

De même que pour les réseaux fermés nous nous plagons au niveau sous-chaines (dans le cas de sous-chaines fermées). On définit de même les matrices $g$ et $g_n$ pour chaque station (dimensions $0:K_1, \dots, 0:K_{M_1}$).

## V.2.1 - Débits

On peut démontrer simplement que dans tous les cas de convergence on a :

* pour une classe r appartenant à une sous-chaine ouverte :

$$\text{deb}_{nr} = \rho_{nr} \mu_{nr}^0$$

* pour une classe r appartenant à une sous-chaine fermée :

$$\text{deb}_{nr} = \rho_{nr} \mu_{nr}^0 \frac{g(K_1, \dots, K_{n-1}, \dots, K_{M_1})}{g(K_1, \dots, K_{M_1})}$$

$$\text{si } r \in \mathcal{M}_m$$
### V.2.2. - Nombre moyen de clients dans une station

On définit la probabilité marginale suivante :

$$ \text{Prob}(k_{n1}, \dots, k_{nM_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2+R_1}) = \\ \frac{1}{c} g_{n-} (k_1, -k_{n1}, \dots, k_{M_1}, -k_{nM_1}) B_n (\bar{k}_n + \ell, n) (\bar{k}_n + \ell, n)! \prod_{m=1}^{M_1} \frac{\bar{\rho}_{nm}^{k_{nm}}}{k_{nm}!} \prod_{s=R_1+1}^{R_2+R_1} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} $$

le nombre moyen de clients dans une station n est donc :

$$ \lgq_{nm} = \sum_{K_1'} \sum_{K_2'} k_{nm} \text{Prob}(k_{n1}, \dots, k_{nM_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2+R_1}) $$

pour une sous-chaine m fermée.

$$ \lgq_{ns} = \sum_{K_1'} \sum_{K_2'} \ell_{ns} \text{Prob}(k_{n1}, \dots, k_{nM_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2+R_1}) $$

pour une classe s appartenant à une sous-chaine ouverte avec

$$ K_1' = \{ \ell_{ns} \ge 0 \ \forall s \in \text{ sous-chaine ouverte} \} $$

$$ K_2' = \{ k_{nm} / 0 \le k_{nm} \le K_m \ \forall m \text{ sous-chaine fermée} \} $$

### V.2.2.1 - Cas d'une classe appartenant à une sous-chaine ouverte

$$ \begin{align*} \lgq_{ns} &= \sum_{K_2'} \frac{1}{c} g_{n-} (k_1, -k_{n1}, \dots, k_{M_1}, -k_{nM_1}) \prod_{m=1}^{M_1} \frac{\bar{\rho}_{nm}^{k_{nm}}}{k_{nm}!} \prod_{s=R_1+1}^{R_2+R_1} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} \\ &= \rho_{ns} \sum_{K_2'} A(k_{n1}, \dots, k_{nM_1}) \sum_{K_1'} B_n (\bar{k}_n + \ell, n+1) (\bar{k}_n + \ell, n+1)! \prod_{s=R_1+1}^{R_2+R_1} \frac{\rho_{ns}^{\ell_{ns}}}{\ell_{ns}!} \\ &= \rho_{ns} \sum_{K_2'} A(k_{n1}, \dots, k_{nM_1}) \sum_{i=0}^{\infty} B_n (\bar{k}_n + i + 1) \frac{(\bar{k}_n + i + 1)!}{i!} (-1)^i \rho_n \end{align*} $$

$$ \text{posons } L_n(\bar{k}_n) = \sum_{i=0}^{\infty} B_n (\bar{k}_n + i + 1) \frac{(\bar{k}_n + i + 1)!}{i!} $$
On remarque que le rapport du nombre moyen de clients dans une station n pour deux classes s et s' appartenant à une sous-chaine ouverte est égal au rapport $\rho_{ns}/\rho_{ns'}$.

### Station à taux constant

$$B_n(\bar{k}+i+1) = 1 \quad \forall \bar{k}_n \quad \forall i \\ \sum_{i=0}^{\infty} \frac{(\bar{k}+i+1)!}{i!} \rho_n^{-i} = \frac{(\bar{k}+1)!}{\left(1-\rho_n^{-0}\right)^{\bar{k}+2}}$$

$$\text{d'où l'on déduit : } \lg q_{ns} = \frac{\rho_{ns}}{1-\rho_n^{-0}} \left(1 + \sum_{m=1}^{M_1} \lg q_{nm}\right)$$

### Station à serveur infini

$\text{trivialement on a : } \lg q_{ns} = \rho_{ns}$

### Station à dépendance globale limitée

Le calcul sera effectué en remarquant que $L_n(\bar{k}) = C_n(\bar{k}+1)$.

#### V.2.2.2 - Cas d'une sous-chaine fermée

Nous pouvons sommer le terme $\sum_{i=1}^{n} B_n(\bar{k}+\bar{l}_n)(\bar{k}+\bar{l}_n)! \sum_{\substack{\ell=1 \\ \ell \neq \bar{k}}}^{R_2+R_1} \frac{\rho_{\ell n}^{\ell}}{\ell n!}$ comme indiqué au paragraphe V.1.3 et effectuer ensuite les calculs comme pour un réseau fermé.

#### V.2.3 - Taux d'utilisation

Pour une classe s appartenant à une sous-chaine ouverte nous avons :

$$\text{util}_{ns} = \sum_{k_1} \sum_{k_2} \frac{\ell_{ns}}{\ell_n + \bar{k}_n} \text{Prob}_{n}(k_{n_1}, \dots, k_{nM_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2+R_1})$$

Pour une sous-chaine fermée :

$$\text{util}_{nm} = \sum_{k_1} \sum_{k_2} \frac{k_{nm}}{\bar{k}_n + \bar{l}_n} \text{Prob}_{n}(k_{n_1}, \dots, k_{nM_1}, \ell_{nR_1+1}, \dots, \ell_{nR_2+R_1})$$
### V.2.3.1 - Sous-chaine ouverte

$$ 
\begin{align*}
\text{util}_{ns} &= \sum_{k_1'} A(k_1', \dots, k_{nM_1}) \sum_{k_2'} \frac{\ell^{ns}}{\ell_{n}^{+k} \ell_{n}^{+k}} B_n(\bar{k}_n + \bar{\ell}_n) (\bar{k}_n + \bar{\ell}_n)! \prod_{r=R_1+1}^{R_1+R_2} \frac{\rho_{nr}^{\ell_{nr}}}{\ell_{nr}!} \\
&= \rho_{ns} \sum_{k_1'} A(k_1', \dots, k_{nM_1}) \sum_{i=0}^{\infty} B_n(\bar{k}_n + i + 1) \frac{(k+i)!}{i!} \rho_n^{-i}
\end{align*}
$$

• Et de même que précédemment le rapport des taux d'utilisation pour une station n pour deux classes s et s' appartenant à une sous-chaine ouverte est égal à $\rho_{ns}/\rho_{ns'}$.

Cette propriété peut être utilisée avec profit si l'on connaît les taux d'utilisation pour les sous-chaînes fermées. En effet si $\text{util}_n$ est le taux d'utilisation total de la station n nous avons :

$$ \sum_{s=R_1+1}^{R_1+R_2} \text{util}_{ns} + \sum_{m=1}^{M_1} \text{util}_{nm} = \text{util}_n $$

$$ 
\begin{align*}
\text{or } \text{util}_n &= 1 - \text{Prob}\{\text{aucun client dans la station n}\} \\
&= 1 - \frac{g_{n-}(K_1, \dots, K_{M_1})}{c}
\end{align*}
$$

d'où :

$$ \text{util}_{ns} = \frac{\rho_{ns}}{\rho_n^0} \left[ 1 - \frac{g_{n-}(K_1, \dots, K_{M_1})}{c} - \sum_{m=1}^{M_1} \text{util}_{nm} \right] $$

Dans le cas d'une station à taux fixe nous ne disposons pas de la matrice $g_{n-}$ mais :

$$ \text{util}_{ns} = \frac{1}{c} \rho_{ns} \sum_{k_1'} A(k_1', \dots, k_{nM_1}) \sum_{i=0}^{\infty} \frac{(\bar{k}_n + i)!}{i!} \rho_n^{-i} $$

et $\text{util}_{ns} = \rho_{ns}$
### V.2.3.2 - Sous-chaînes fermées

#### Station à taux fixes

On montre simplement que, dans ce cas, le taux d'utilisation pour une sous-chaîne fermée est tel que :

$$ \text{util}_{nm} = \frac{\bar{\rho}_{nm}}{C} G(K_1, \dots, K_{m-1}, \dots, K_{M_1}) $$

#### Station à serveur infini

Dans ce cas nous aurons :

$$ \text{Cutil}_{nm} = \sum_{k_{n1}=0}^{K_1} \dots \sum_{k_{nm}=1}^{K_m} \sum_{k_{nM_1}=1}^{K_{M_1}} \sum_{K'_1} \frac{k_{nm}}{\bar{k}_n + \ell_n} g_{n-}(K_1 - k_{n1}, \dots, K_{M_1} - k_{nM_1}) \\ M_1 \quad \bar{\rho}_{np}^k \quad R_1 + R_2 \quad \rho_{ns}^\ell \\ \Pi \quad \frac{\bar{\rho}_{nm}}{k_{np}!} \quad \Pi \quad \frac{\rho_{ns}}{\ell_{ns}!} \\ p=1 \quad S=R_1+1 $$

Nous pourrons donc utiliser un algorithme tout à fait analogue à l'algorithme du paragraphe IV.3.2 après avoir calculé les termes suivants :

$$ Q_n(\bar{k}_n) = \sum_{K'_1} \frac{1}{\bar{k}_n + \ell_n} \sum_{S=R_1+1}^{R_1+R_2} \frac{\rho_{ns}^\ell}{\ell_{ns}!} $$

pour $1 \le \bar{k}_n \le K_1 + \dots + K_{M_1}$

On montre que :

$$ Q_n(\bar{k}_n) = \frac{(-1)^{\bar{k}_n - 1}}{\bar{\rho}_n^0} \quad (\bar{k}_n - 1)! \quad \left[ \exp(\bar{\rho}_n^0) \left( \sum_{i=0}^{\bar{k}_n - 1} (-1)^i \frac{\bar{\rho}_n^i}{i!} \right) - 1 \right] $$

et que $Q_n(\bar{k}_n + \uparrow) = \frac{1}{\bar{\rho}_n^0} (1 - \bar{k}_n) Q_n(\bar{k}_n)$

#### Station à dépendance globale limitée

Le problème est analogue et se rapproche au calcul des coefficients suivants :
$$
R_n(\bar{k}_n) = \sum_{K'_1} \frac{B_n(\bar{k}+\bar{l}) B_n(\bar{k}+\bar{l})!}{(\bar{k}+\bar{l})^{K'_1} K'_1!} \prod_{S=R'_1+1}^{R'_1+R'_2} \frac{\rho_{ns}^{\bar{l}}}{\bar{l}^{K'_1} ns!}
$$

pour 1 ≤ $\bar{k}_n$ ≤ $K_1$ + ... + $K_{M_1}$

On montre que :

$$
R_n(\bar{k}_n) = R_n^1(\bar{k}_n) + R_n^2(\bar{k}_n) \text{ avec :}
$$

$$
R_n^1(\bar{k}_n) = \frac{B_n(d-1)}{\bar{k}_n - d + 1} \frac{(\bar{k}_n - 1)!}{\bar{\rho}_n^0 \bar{k}_n} \left(1 - \frac{\bar{\rho}_n^0}{\bar{\beta}_n}\right)
$$

et

$$
R_n^2(\bar{k}_n) = \begin{cases} 0 & \text{si } \bar{k}_n \ge d_n \\ d_n - \bar{k}_n - 1 & \sum_{i=0}^{d_n - \bar{k}_n - 1} \left( B_n(\bar{k}_n + i) - \frac{B_n(d-1)\beta_n^{d_n-1}}{\bar{k}_n + i} \right) \frac{(\bar{k}_n + i-1)!}{i!} \bar{\rho}_n^0 \end{cases}
$$

V.3 - Conclusion

De même que dans le cas des réseaux fermés nous n'autorisons qu'un
type restreint de possibilités pour les stations :

- stations à taux constant

- stations à dépendance globale limitée

- stations à serveur infini

pour lesquels l'existence d'une solution stationnaire peut être oonnue à partir
des intensités de traffic.

La part des sous-chaines ouvertes étant calculée le problème est ramené à un calcul de réseau fermé dont nous avons donné les algorithmes au paragraphe IV.
# VI - EXEMPLES DE RESOLUTION A L'AIDE DE QNAP

Pour illustrer les considérations des paragraphes précédants, nous présentons ici deux exemples de calcul concernant pour le premier un réseau ouvert, et pour le second un réseau fermé.

Ces exemples n'ont qu'une valeur d'école et les paramètres choisis n'ont sans doute pas de signification réelle.

Les données sont introduites au moyen du langage de description de QNAP [24]. Données et résultats sont produits en annexe B.

## VI.1 - Exemple de réseau ouvert

Nous avons utilisé un modèle de CYCLADE [25] où comme indiqué par la figure 1, nous voulons représenter 7 noeuds et 16 lignes.

Les taux d'arrivée de paquets provenant de l'extérieur sont égaux pour chaque noeuds, les destinations équiprobables. Les paquets empruntent le chemin le plus rapide (au sens où ils utilisent le minimum de lignes) ; les ambiguïtes sont levées par la figure 2.

Chaque ligne sera représentée par une station au sens de QNAP, soient 16 stations ; un noeud de destination correspond à une classe de paquets, il y aura donc 7 classes.

Les données et résultats sont reproduits en annexe B.1.1, B.1.2.

## VI.2 - Exemple de réseau fermé

Cet exemple veut illustrer plus particulièrement l'utilisation des classes de clients. Le réseau est du type serveur central et comprend quatre stations (voir figure 3) :

- l'unité centrale : UC,

- trois stations " périphériques" : P1, P2, P3 ;

Nous voulons représenter deux types de comportement vis à vis des stations P1, P2, P3 :

- après une durée de service dans UC, un client accède P1, P2, P3 ou UC de façon aléatoire.
- les stations P1, P2, P3 sont obligatoirement accédées dans cet ordre.

Au premier cas nous ferons correspondre une classe C0.

Dans le deuxième, nous introduisons trois classes C11, C12, C13 telles que :

- à la sortie de UC un client de classe C11 (resp. C12, C13) se rend à la station P1 (resp. P2, P3) ou UC.

- à la sortie de P1 (resp. P2, P3) un client passe en classe C12 (resp. C13, C11).

Les résultats sont donnés en annexes B.2.1, B.2.2.

## VI.3 - Exemple de réseau mixte

Nous considérons un système (voir figure 4) constitué d'une unité centrale (CPU), de périphériques (DISK, TAPE), d'un disque de swapping (SWAP) et de terminaux (TERM). Les clients parcourant le réseau proviennent des requêtes issues des terminaux ou de l'extérieur (EXT) et constituent deux populations appartenant à des classes distinctes (C1 et C2).

Au niveau de la station SWAP un client issu des terminaux ou de l'extérieur sera dirigé vers la station UC. D'autre part un client provenant de UC sera dirigé vers les terminaux ou l'extérieur en fonction de sa classe. Ce comportement sera représenté en introduisant des classes fictives comme pour l'exemple du paragraphe VI.2 (classes C11, C12 et C21, C22).

Les données et résultats sont produits en annexes B.3.1, B.3.2.
<figure><img src="image_5.png" /><figcaption>Figure 1</figcaption></figure>

<table><caption>Figure 2</caption><thead><tr><th>Noeud Source</th><th>Noeud de Destination</th><th>Noeud de Transition</th></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>F</td><td>C, D</td><td>B</td></tr><tr><td>G</td><td>A, B</td><td>C</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>Figure 3</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>
# ANNEXE A

Calcul de la proportion de temps pendant laquelle un client de classe r est en cours de service dans une station n.

## A.I - Cas d'une station de type 1 (PAPS)

Il est nécessaire de considérer des états plus fins que ceux utilisés jusqu'alors.

Un état d'une station n, PAPS, est représenté par une suite $x_n$

$$ \dot{x}_n = \{x_{n1}, \dots, x_{n2}, \dots, x_{nk}\} $$

où $k_n$ est le nombre de clients dans la station et $x_{nj}$ la classe du client j-ième dans l'ordre PAPS. Le client en cours de service est de classe $x_{n1}$.

Nous savons [3] que la probabilité $P_n(x_n)$ que la station n soit dans l'état $x_n$ peut s'écrire :

$$ P_n(x_n) = \frac{1}{K} \left(\frac{1}{\mu_n}\right)^k \prod_{j=1}^{k} e^{\mu_n x_{nj}} $$

Nous noterons que si $x'_n$ est une permutation des éléments de $x_n$ alors
$$ P_n(x_n) = P'_n(x'_n). $$

Supposons que l'état $x_n$ corresponde à $k_{n1}$ clients de classe 1, ..., $k_{nR}$ clients de classe R.

Le nombre de permutation (sans répétition) sur l'ensemble $\{x_{n1}, \dots, x_{nk}\}$ est :

$$ \binom{k}{k_n} \binom{k-k}{k_n n1} \dots \binom{k-k}{k_n n1}^{-\dots^{-k}} nR-1 $$
Ce qui nous permet de vérifier que :

$$p_n(k_{n1}, \dots, k_{nR}) = \frac{k_n!}{k_{n1}! \dots k_{nR}!} \left(\frac{1}{\mu_n}\right)^{\prod_{r=1}^{k_n} \frac{R}{e \cdot a} \cdot \frac{k}{nR}}$$

La probabilité que la station soit dans un état $(k_{n1}, \dots, k_{nR})$ sachant que le client en cours de service est de classe $r$ est :

$$\left(\begin{array}{c} k_{n}-1 \\ k_{n1} \end{array}\right) \cdots \left(\begin{array}{c} k_{n}-k_{n1}-\cdots-k_{nR}-1 \\ k_{nR}-1 \end{array}\right) \cdots \left(\begin{array}{c} k_{n}-k_{n1}-\cdots-k_{nR}-1 \\ k_{nR} \end{array}\right) \\ = \frac{k_{nR}}{k_n} p_n(k_{n1}, \dots, k_{nR})$$

## A.II - Cas d'une station de type 2 (DAPS PR)

Un état fondamental d'une telle station peut être décrit par une suite $x_n$ [3] telle que :

$$x_n = (r_1, m_1), \dots, (r_{k_n}, m_{k_n})$$

où $k_n$ est le nombre total de clients dans la station.

$r_j$ la classe duième client dans l'ordre DAPS dans la station

$m_j$ l'étape de service dans laquelle se trouve le client.

Rappelons que Cox [23] a montré qu'une distribution à transformée de Laplace rationnelle peut être représentée par le réseau suivant :

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

Chaque étape étant une station exponentielle.
D'après [3] la probabilité $P_n(x_n)$ s'exprime par :

$$P_n(x_n) = \frac{1}{K} \prod_{j=1}^{K} \frac{e^{\frac{A}{n} \sum_{j=1}^{n} x_j}}{\mu_{n}^{\frac{A}{n} \sum_{j=1}^{n} x_j}}$$

$$\text{avec } A_{nr,j}^{m,j} = \prod_{k=1}^{m,j} a_{nr,j,k}$$

Soit $\gamma_n = (r_1, \dots, r_{K_n})$ un état tel que $x_j$ soit la classe du client jème dans l'ordre DAPS dans la $n$-ième station $n$. On a :

$$P_n(\gamma_n) = \sum_{m_1=1}^{M_1} \dots \sum_{m_{K_n}=1}^{M_{K_n}} \frac{1}{K} \prod_{j=1}^{K} \frac{e^{\frac{A}{n} \sum_{j=1}^{n} x_j}}{\mu_{n}^{\frac{A}{n} \sum_{j=1}^{n} x_j}} \quad \text{où } M_j \text{ est le nombre de} \\ \text{d'étape pour la classe } r_j.$$

$$= \frac{1}{K} \prod_{j=1}^{K} \frac{e^{\frac{A}{n} \sum_{j=1}^{n} x_j}}{\mu_{n}^{\frac{A}{n} \sum_{j=1}^{n} x_j}}$$

On montre en effet simplement que $\mu_{nr,j} = \frac{M_j}{\sum_{m_j=1}^{M_1} \frac{A}{n} \sum_{j=1}^{n} x_j}$ nous sommes donc ramenés au cas précédent.

### A. III - Cas des stations de type 3 (PP) et de type 4 (SI)

Dans le cas d'une station processeur partagé, chaque client est servi alternativement avec un taux $\frac{1}{K_n}$ d'où la proportion de temps pendant laquelle les clients de classe $r$ reçoivent du service s'il a station est dans un état $(k_{n1}, \dots, k_{nR})$ :

$$\frac{K}{K_n} \sum_{n} p_n(k_{n1}, \dots, k_{nR})$$
Pour une station serveur infini il y a autant de serveurs que de clients dans le réseau. Si une station est dans l'état $(k_{n1}, \dots, k_{nR})$ il y aura $k_n$ serveur dont $k_{nr}$ pour la classe r. Ces clients de classe r utilise une fraction $\frac{nr}{k_n}$ de la station, d'où le taux d'utilisation de la station pour des clients de classe r lorsque la station est dans un état $(k_{n1}, \dots, k_{nR})$. suivant la définition donnée au paragraphe III.4.1 :

$$ \frac{k_{nr}}{k_n} p_n(k_{n1}, \dots, k_{nR}). $$
## B.1 - RESEAU OUVERT

### B.1.1 - Données

& MODELE DE CYCLADE:OUVERT

& 7 NOEUDS, 16 LIGNES.

/*
* DECLARATION/QUEUE S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,
* S11,S12,S13,S14,S15,S16,EXT;
* CLASS A,B,C,D,E,F,G;
*
* LIGNES ...
*
* STATION/NAME=S1;SERVICE=EXP(.3);
* TRANS(B)=OUT;TRANS(C)=S3;TRANS(D)=S3;TRANS(E)=S3;TRANS(F)=S3;TRANS(G)=S4;
* STATION/NAME=S2;SERVICE=EXP(.3);
* TRANS(A)=OUT;
* STATION/NAME=S3;SERVICE=EXP(.3);
* TRANS(C)=OUT;TRANS(D)=S6;TRANS(E)=S7;TRANS(F)=S8;
* STATION/NAME=S4;SERVICE=EXP(.4);
* TRANS(G)=OUT;
* STATION/NAME=S5;SERVICE=EXP(.3);
* TRANS(A)=S2;TRANS(B)=OUT;
* STATION/NAME=S6;SERVICE=EXP(.4);
* TRANS(D)=OUT;
* STATION/NAME=S7;SERVICE=EXP(.4);
* TRANS(E)=OUT;
* STATION/NAME=S8;SERVICE=EXP(.4);
* TRANS(F)=OUT;TRANS(G)=S13;
* STATION/NAME=S9;SERVICE=EXP(.4);
* TRANS(A)=S5;TRANS(B)=S5;TRANS(C)=OUT;TRANS(E)=S7;TRANS(F)=S8;TRANS(G)=S8;
* STATION/NAME=S10;SERVICE=EXP(.4);
* TRANS(A)=S5;TRANS(B)=S5;TRANS(C)=OUT;TRANS(D)=S6;
* STATION/NAME=S11;SERVICE=EXP(.4);
* TRANS(F)=OUT;TRANS(G)=S13;
* STATION/NAME=S12;SERVICE=EXP(.4);
* TRANS(E)=OUT;
* STATION/NAME=S13;SERVICE=EXP(.4);
* TRANS(G)=OUT;
* STATION/NAME=S14;SERVICE=EXP(.4);
* TRANS(A)=S5;TRANS(B)=S5;TRANS(C)=OUT;TRANS(D)=S6;
* STATION/NAME=S15;SERVICE=EXP(.4);
* TRANS(E)=S12;TRANS(F)=OUT;
* STATION/NAME=S16;SERVICE=EXP(.4);
* TRANS(A)=S2;TRANS(B)=OUT;TRANS(C)=S3;TRANS(D)=S3;
*
* SOURCE ...
*
* STATION/NAME=EXT;SCHED=GEN;SERVICE=EXP(.14286);
* TRANS=S1(B),.02381,S1(C),.02381,S1(D),.02381,
* S1(E),.02381,S1(F),.02381,S1(G),.02381,
* S2(A),.02381,S3(C),.02381,S3(D),.02381,
* S3(E),.02381,S4(G),.02381,S5(A),.02381,
* S5(B),.02381,S6(D),.02381,S7(E),.02381,
* S8(F),.02381,S8(G),.02381,S9(A),.02381,
* S9(B),.02381,S9(C),.02381,S9(E),.02381,
* S9(F),.02381,S9(G),.02381,S10(A),.02381,
* S10(B),.02381,S10(C),.02381,S10(D),.02381,
* S11(F),.02381,S11(G),.02381,S12(E),.02381,
* S13(G),.02381,S14(A),.02381,S14(B),.02381,
* S14(C),.02381,S14(D),.02381,S15(F),.02381,
* S15(E),.02381,S16(A),.02381,S16(B),.02381,
* S16(C),.02381,S3(F),.02381,S16(D);
* &
* COMPUTE/&OPTION=TRACE;
* &OPTION=DEBUG;
* EXEC/COMPUTE;
*
B.1.2 - Résultats

<table><tbody><tr><td>*QUEUE S1</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS B</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*CLASS C</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*CLASS D</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*CLASS E</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*CLASS F</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*CLASS G</td><td>.3000</td><td>.5000E-01</td><td>.7143E-01</td><td>.4286</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.3000</td><td>.3000</td><td>.4286</td><td>.4286</td><td>1.0000</td></tr><tr><td>*QUEUE S2</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.3000</td><td>.3000</td><td>.4286</td><td>.4286</td><td>1.0000</td></tr><tr><td>*GLOBAL</td><td>.3000</td><td>.3000</td><td>.4286</td><td>.4286</td><td>1.0000</td></tr><tr><td>*QUEUE S3</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS C</td><td>.3000</td><td>.1500</td><td>.3000</td><td>.6000</td><td>.5000</td></tr><tr><td>*CLASS D</td><td>.3000</td><td>.1500</td><td>.2999</td><td>.6000</td><td>.4999</td></tr><tr><td>*CLASS E</td><td>.3000</td><td>.10000</td><td>.2000</td><td>.6000</td><td>.3333</td></tr><tr><td>*CLASS F</td><td>.3000</td><td>.10000</td><td>.2000</td><td>.6000</td><td>.3333</td></tr><tr><td>*GLOBAL</td><td>.3000</td><td>.5000</td><td>.9990</td><td>.6000</td><td>1.667</td></tr><tr><td>*QUEUE S4</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS G</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*QUEUE S5</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.3000</td><td>.2000</td><td>.3333</td><td>.5000</td><td>.6667</td></tr><tr><td>*CLASS B</td><td>.3000</td><td>.2000</td><td>.3333</td><td>.5000</td><td>.6667</td></tr><tr><td>*GLOBAL</td><td>.3000</td><td>.4000</td><td>.6667</td><td>.5000</td><td>1.333</td></tr><tr><td>*QUEUE S6</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS D</td><td>.4000</td><td>.3999</td><td>.6665</td><td>.6666</td><td>.9999</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.3999</td><td>.6665</td><td>.6666</td><td>.9999</td></tr><tr><td>*QUEUE S7</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS E</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*QUEUE S8</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS F</td><td>.4000</td><td>.2667</td><td>.4444</td><td>.6667</td><td>.6667</td></tr><tr><td>*CLASS G</td><td>.4000</td><td>.1333</td><td>.2222</td><td>.6667</td><td>.3333</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.4000</td><td>.6667</td><td>.6667</td><td>1.0000</td></tr><tr><td>*QUEUE S9</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*CLASS B</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*CLASS C</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*CLASS E</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*CLASS F</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*CLASS G</td><td>.4000</td><td>.6667E-01</td><td>.1111</td><td>.6667</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.4000</td><td>.6667</td><td>.6667</td><td>1.0000</td></tr><tr><td>*QUEUE S10</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS B</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS C</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS D</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*QUEUE S11</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS F</td><td>.4000</td><td>.6667E-01</td><td>.7692E-01</td><td>.4615</td><td>.1667</td></tr><tr><td>*CLASS G</td><td>.4000</td><td>.6667E-01</td><td>.7692E-01</td><td>.4615</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*QUEUE S12</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS E</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*QUEUE S13</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS G</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*QUEUE S14</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS B</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS C</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*CLASS D</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5455</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.2667</td><td>.3636</td><td>.5455</td><td>.6667</td></tr><tr><td>*QUEUE S15</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS E</td><td>.4000</td><td>.6667E-01</td><td>.7692E-01</td><td>.4615</td><td>.1667</td></tr><tr><td>*CLASS F</td><td>.4000</td><td>.6667E-01</td><td>.7692E-01</td><td>.4615</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.1333</td><td>.1538</td><td>.4615</td><td>.3333</td></tr><tr><td>*QUEUE S16</td><td>SERV.AVG</td><td>BUSY.PCT</td><td>LONG.AVG</td><td>WAIT.AVG</td><td>THRUPUT</td></tr><tr><td>*CLASS A</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5454</td><td>.1667</td></tr><tr><td>*CLASS B</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5454</td><td>.1667</td></tr><tr><td>*CLASS C</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5454</td><td>.1667</td></tr><tr><td>*CLASS D</td><td>.4000</td><td>.6667E-01</td><td>.9091E-01</td><td>.5454</td><td>.1667</td></tr><tr><td>*GLOBAL</td><td>.4000</td><td>.2667</td><td>.3635</td><td>.5454</td><td>.6665</td></tr></tbody></table>

*QUEUE EXT SOURCE OF ALL SUBCHUNGS RATE= 6.9999
## B.2 - RESEAU FERME

### B.2.1 - Données

```
& EXEMPLE DE RESEAU FERME...
&       -4 STATIONS,
&       -4 CLASSES,
&       -2 SOUS-CHAINES.
&
/DECLARATION/QUEUE UC,P1,P2,P3;CLASS C0,C11,C12,C13;
&
/STATION/NAME=UC;SCHED=PS;
SERVICE(C0)=EXP(1.);
SERVICE=EXP(2.);
LOAD=1.,1.,1.,1.,10.;
TRANSIT(C0)=P1,1.,P2,1.,P3,1.,UC,1.;
TRANSIT(C11)=P1,.5,UC;
TRANSIT(C12)=P2,.5,UC;
TRANSIT(C13)=P3,.5,UC;
&
/STATION/NAME=P1;
SERVICE=EXP(20.);
TRANSIT(C0)=UC;
TRANSIT(C11)=UC(C12);
/STATION/NAME=P2;
SERVICE=EXP(25.);
TRANSIT(C0)=UC;
TRANSIT(C12)=UC(C13);
/STATION/NAME=P3;
SERVICE=EXP(30.);
TRANSIT(C0)=UC;
TRANSIT(C13)=UC(C11);
&
/COMPUTE/INIT(C0)=2;
INIT(C11)=5,10;
/EXEC/COMPUTE;
```
B.2.2 - Résultats

****SUBCHAIN 1 CUSTNUMBER= 2

****SUBCHAIN 2 CUSTNUMBER= 5

*
*QUEUE UC      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       1.186          .4109E-01     .9205E-01     2.656          .3465E-01
*CLASS C11      2.158          .8782E-01     .1514          3.721          .4069E-01
*CLASS C12      2.158          .8782E-01     .1514          3.721          .4069E-01
*CLASS C13      2.158          .8782E-01     .1514          3.721          .4069E-01
*GLOBAL         1.943          .3045          .5463          3.485          .1567
*

*
*QUEUE P1      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       20.00         .1733          .3670          .42.36         .8664E-02
*CLASS C11      20.00         .4069          .8702          .42.77         .2035E-01
*GLOBAL         20.00         .5802          1.237          .42.64         .2901E-01

*
*QUEUE P2      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       25.00         .2166          .5937          68.53          .8664E-02
*CLASS C12      25.00         .5087          1.413          69.44          .2035E-01
*GLOBAL         25.00         .7253          2.007          69.17          .2901E-01

*
*QUEUE P3      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       30.00         .2599          .9473          109.3          .8664E-02
*CLASS C13      30.00         .6104          2.263          111.2          .2035E-01
*GLOBAL         30.00         .8703          3.210          110.7          .2901E-01

*
****SUBCHAIN 1 CUSTNUMBER= 2
****SUBCHAIN 2 CUSTNUMBER= 10

*
*QUEUE UC      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       9.442          .1424          1.563          103.7          .1508E-01
*CLASS C11      17.33          .2765          2.960          185.6          .1595E-01
*CLASS C12      17.33          .2765          2.960          185.6          .1595E-01
*CLASS C13      17.33          .2765          2.960          185.6          .1595E-01
*GLOBAL         15.44          .9718          10.44         165.9          .6293E-01

*
*QUEUE P1      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       20.00         .7538E-01     .1001          26.56          .3769E-02
*CLASS C11      20.00         .1595          .2359          29.58          .7975E-02
*GLOBAL         20.00         .2349          .3360          28.61          .1174E-01

*
*QUEUE P2      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       25.00         .9423E-01     .1405          37.29          .3769E-02
*CLASS C12      25.00         .1994          .3525          44.19          .7975E-02
*GLOBAL         25.00         .2936          .4930          41.98          .1174E-01

*
*QUEUE P3      SERV.AVG      BUSY.PCT      SIZE.AVG      WAIT.AVG      THRUPUT
*CLASS CO       30.00         .1131          .1993          52.87          .3769E-02
*CLASS C13      30.00         .2393          .5491          68.85          .7975E-02
*GLOBAL         30.00         .3523          .7484          63.72          .1174E-01
## B.3 - RESEAU MIXTE

### B.3.1 - Données

& EXEMPLE DE RESEAU MIXTE ...

& - 1 SOUS-CHAINE FERMEE (2 CLASSES),

& - 1 SOUS-CHAINE OUVERTE (2 CLASSES),

& - 5 STATIONS,

&
/DECLARE/QUEUE EXT,TERM,SWAP,CPU,DISK,TAPE;
CLASS C11,C12,C21,C22;

&
& SOURCE ...
/STATION/NAME=EXT;SCHED=GEN;
SERVICE=EXP(1000.);
TRANSIT=SWAP(C21);

& STATIONS ...

/STATION/NAME=TERM;SCHED=DELAY;
SERVICE=EXP(1000.);TRANSIT(C12)=SWAP(C11);

/STATION/NAME=SWAP;
SERVICE=EXP(50.);
TRANSIT(C11)=CPU;TRANSIT(C12)=TERM;
TRANSIT(C21)=CPU;TRANSIT(C22)=OUT;

/STATION/NAME=CPU;SCHED=PS;
SERVICE(C11)=EXP(10.);SERVICE(C21)=EXP(10.);
TRANSIT(C11)=SWAP(C12),1,DISK,10,TAPE,2;
TRANSIT(C21)=SWAP(C22),1,DISK,10,TAPE,2;

/STATION/NAME=DISK;
SERVICE=EXP(10.);
TRANSIT(C11)=CPU;
TRANSIT(C21)=CPU;

/STATION/NAME=TAPE;
SERVICE=EXP(60.);
TRANSIT(C11)=CPU;
TRANSIT(C21)=CPU;

&
/COMPUTE/INIT(C11)=10;INIT(C12)=0;

&
/EXEC/COMPUTE;
B.3.2 - Résultats

SUBCHAIN 1 IS CLOSED CUSTNB= 10

SUBCHAIN 2 IS OPEN

*QUEUE EXT SOURCE OF SUBCHAIN 2 RATE= .1000E-02

*QUEUE TERM SERV.AVG UTIL.PCT SIZE.AVG WAIT.AVG THRUPUT *
*CLASS C12 1000. .9954 4.761 1000. .4761E-02*
*GLOBAL 1000. .9954 4.761 1000. .4761E-02*

*QUEUE SWAP SERV.AVG UTIL.PCT SIZE.AVG WAIT.AVG THRUPUT *
*CLASS C11 50.00 .2380 .4958 104.2 .4761E-02*
*CLASS C12 50.00 .2380 .4958 104.2 .4761E-02*
*CLASS C21 50.00 .5000E-01 .1106 110.6 .1000E-02*
*CLASS C22 50.00 .5000E-01 .1106 110.6 .9999E-03*
*GLOBAL 50.00 .5761 1.213 105.3 .1152E-01*

*QUEUE CPU SERV.AVG UTIL.PCT SIZE.AVG WAIT.AVG THRUPUT *
*CLASS C11 10.00 .6189 1.787 28.88 .6189E-01*
*CLASS C21 10.00 .1300 .4165 32.04 .1300E-01*
*GLOBAL 10.00 .7489 2.204 29.43 .7489E-01*

*QUEUE DISK SERV.AVG UTIL.PCT SIZE.AVG WAIT.AVG THRUPUT *
*CLASS C11 10.00 .4761 .9916 20.83 .4761E-01*
*CLASS C21 10.00 .9999E-01 .2213 22.13 .9999E-02*
*GLOBAL 10.00 .5760 1.213 21.06 .5760E-01*

*QUEUE TAPE SERV.AVG UTIL.PCT SIZE.AVG WAIT.AVG THRUPUT *
*CLASS C11 60.00 .5713 1.469 154.3 .9521E-02*
*CLASS C21 60.00 .1200 .3366 168.3 .2000E-02*
*GLOBAL 60.00 .6913 1.805 156.7 .1152E-01*
BIBLIOGRAPHIE

[ 1 ] Jackson S.R. - "Job shop-like queueing systems" - Management Science, Vol. 10, n° 1, Octobre 1963, pp. 131-142.

[ 2 ] Gordon W.J., Newell G.F. - "Closed queueing systems with exponential servers" - Operation Research 15, 1967, pp. 254-265.

[ 3 ] Baskett F., Chandy K.M., Muntz R.R., Palacios F.G. - "Open, closed and mixed networks of queues with different classes of customers" - J.ACM 22, 2, Avril 1975, pp. 248-260.

[ 4 ] Buzen J.P. - "Computational algorithms for closed queueing network with exponential servers" - C.ACM 16, September 1973, pp. 527-531.

[ 5 ] Reiser M, Kobayashi H. - "Queueing networks with multiple closed chains : theory and computational algorithms" - IBM Journal of Res. and Dev., Mai 1975, pp. 283-294.

[ 6 ] Reiser M. - "Numerical methods in separable queueing networks" - IBM Research Report RC 5842, Mai 1976.

[ 7 ] Chandy K.M., Herzog V., Woo L. - "Approximate analysis of general queueing networks" - IBM Journal of Res. and Dev., Janvier 1975, pp. 43-49.

[ 8 ] Marie R. - "Sur les réseaux de files d'attente non markoviennes" - IRISA Rennes - Séminaires de probabilités, 1976, à paraître.

[ 9 ] Kobayashi H. - "Application of the diffusion approximation to queueing networks : Part I - Equilibrium queue distribution" - J.ACM 21, 1974, pp. 316-328.

[10] Gelenbe E. - "On approximate computer system models" - J.ACM 22, 1975, pp. 261-269.

[11] Stewart W.J. - Ph.D Thesis - "Markov analysis of operating system techniques", Queen's University of Belfast, Juillet 1974.

[12] Williams A.C., Bhandiwad K.A. - "Queueing networks models of computer systems" - Proceedings of the 3rd Texas Conference on Computer Systems Novembre 1974.

[13] Knuth D.E. - "The art of computer programming" - Vol. 1, Fundamental Algorithms Addison Wesley, 1968.

[14] Leroudier J., Parent M. - "Discrete event simulation modelling of computer system for performance evaluation" - IRIA-LABORIA, Rapport de Recherche n° 177 Juin 1976.

[15] Rose C.A. - "Validation of a queueing model with classes of customers" - Proc. of the International Symposium on Computer Performance, Mars 1976.
[16] Krzcsinski A.E, Teunissen P. - "Efficient computational forms for the normalizing constant and the statistical measures of mixed, multiclass queueing networks" - University of Stellenbosch, Dept. of computer Science, Report n° R'77-04, June 1977.

[17] Buzen J.P. - "Cost effective analytic tools for computer performance evaluation" Proceedings of COMPCON, pp. 293-295, Septembre 1975.

[18] Merle D., Potier D., Véran M. - "QNAP : Manuel de Présentation" - En préparation, 1977.

[19] Hughes P.H., Moe G. - "A structural approach to computer performance analysis" Proc. National Computer Conference, 1973.

[20] Balbo G.F., Bruell S.C., Schwetman H.D. - "Customer classes and closed network models : a solution technique", Submitted to IFIP 1977.

[21] Derniame J.P., Pair C. - "Problèmes de cheminement dans les graphes" - Monographie d'informatique, AFCET, DUJOD, 1971.

[22] Little J.D.C. - "A proof of the Queueing Formula $L = \lambda W$" - Operation Research, Vol. 9, n° 3, May 1971.

[23] Cox D.R. - "A use of complex probabilities in the theory of stochastic processes" - Proc. of the Cambridge Phil. Society, 51, pp. 313-319, 1955.

[24] Véran M. - "QNAP : Manuel d'utilisation" - En préparation, 1977.

[25] Pouzin L. - "CIGALE The packet switching machine of the CYCLADE computer network" - Proc. IFIP Congress 1974, Stockholm, North-Holland, Août 1974.