TD Processus Et Files D'attente [PDF]

Zitiervorschau

Exercices de Files d’Attentes Monique Becker Andr´e-Luc Beylot Alexandre Delye de Clauzade de Mazieux 2006-2007 v.2

ii

Table des mati` eres 1 Exercices g´ en´ eraux 1.1 Mod`ele du dentiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Temps d’attente d’un train . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 1

2 Chaˆınes de Markov ` a temps discret 2.1 Etude d’une Chaˆıne de Markov `a Temps Discret . . . . . . . . . . . . . . . . . . . 2.2 Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Mod`eles de trafic sur un lien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 3 3

3 Chaˆınes de Markov ` a temps continu 3.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5

4 Files d’attentes simples 4.1 Mod`ele du r´eparateur . . . . . . . . . . . . . . . . . . . . 4.2 Unit´e de transmission ` a capacit´e limit´ee . . . . . . . . . . 4.3 Unit´e de transmission avec des erreurs de transmission . . 4.4 Etude de la file M/M/C/C . . . . . . . . . . . . . . . . . 4.5 File ` a Serveurs H´et´erog`enes . . . . . . . . . . . . . . . . . 4.6 Performance d’un ´etage d’abonn´es - File M/M/C/C/N . . 4.7 Influence de la variance des services et de la loi de priorit´e 4.8 Longueur des paquets IP . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

7 7 7 8 8 8 10 11 11

5 R´ eseaux de files d’attentes 5.1 Syst`eme multi-programm´e ` a m´emoire virtuelle . . . . . . . . . . . . . 5.2 Du choix du point o` u l’on compte le d´ebit global dans un r´eseau ferm´e 5.3 Th´eor`eme de Jackson et Analyse Op´erationnelle . . . . . . . . . . . . . 5.4 R´eseau local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

13 13 14 15 15

6 M´ ethodes d’agr´ egation 6.1 R´eseau sym´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Agr´egation de chaˆınes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Agr´egation de files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 17 18

7 Exercices non corrig´ es 7.1 Etude de la transform´ee en z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Etude de la file M/GI/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21 21 22

8 Corrig´ es Mod`ele du dentiste . . . . . . . . . . . . Temps d’attente d’un train . . . . . . . Etude d’une Chaˆıne de Markov a` Temps Processus de naissance et de mort . . . Mod`eles de trafic sur un lien . . . . . . Processus de Poisson . . . . . . . . . . . Modele du r´eparateur . . . . . . . . . .

25 25 25 26 27 27 29 31

. . . . . . . . . . Discret . . . . . . . . . . . . . . . . . . . . iii

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

iv

` TABLE DES MATIERES

Unit´e de transmission ` a capacit´e limit´ee . . . . . . . . . . . . . . . . . Unit´e de transmission avec des erreurs de transmission . . . . . . . . . Etude de la file M/M/C/C . . . . . . . . . . . . . . . . . . . . . . . . File `a Serveurs H´et´erog`enes . . . . . . . . . . . . . . . . . . . . . . . . Performance d’un ´etage d’abonn´es - File M/M/C/C/N . . . . . . . . . Influence de la variance des services et de la loi de priorit´e . . . . . . . Longueur des paquets IP . . . . . . . . . . . . . . . . . . . . . . . . . . Syst`eme multi-programm´e ` a m´emoire virtuelle . . . . . . . . . . . . . Du choix du point o` u l’on compte le d´ebit global dans un r´eseau ferm´e Th´eor`eme de Jackson et Analyse Op´erationnelle . . . . . . . . . . . . R´eseau local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R´eseau sym´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Agr´egation de chaˆınes de Markov . . . . . . . . . . . . . . . . . . . . . Agr´egation de files d’attente . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

32 32 33 34 37 40 41 42 45 48 49 50 50 51

Chapitre 1

Exercices g´ en´ eraux 1.1

Mod` ele du dentiste

On consid`ere une file d’attente ` a un serveur. On suppose que le d´ebit moyen est Λ, le temps moyen de r´eponse est E[R], le temps moyen d’attente est E[W ], le temps moyen de service est [E]S, l’esp´erance de longueur de la file d’attente est E[L], le nombre moyen de clients en train d’attendre est E[LW ], le nombre moyen de clients en train d’ˆetre servis est E[LS ] et la probabilit´e pour que le serveur soit occup´e est U . 1- Ecrire une relation entre E[R], E[S] et E[W ] (relation 1). 2- Ecrire une relation entre E[L], E[LW ] et E[LS ] (relation 2). 3- Exprimer E[LS ] en fonction de U . 4- Montrer que l’on passe de la relation 1 `a la relation 2 en faisant une op´eration simple et montrer qu’on trouve ainsi une relation connue entre U , Λ et E[S]. 5- On consid`ere un dentiste. Le nombre moyen de patients pr´esents chez lui est 2.8, le nombre moyen de patients dans la salle d’attente est 2, le nombre moyen de clients arrivant en une heure est 4. D´eduire les autres crit`eres de performances et caract´eristiques du traitement.

1.2

Temps d’attente d’un train

On consid`ere une voie ferr´ee sur laquelle les passages des trains sont s´epar´es par des dur´ees (dur´ee entre deux trains successifs) de deux types possibles : – 90% de ces dur´ees sont constantes et ´egales `a 6 mn. – 10% de ces dur´ees sont constantes et ´egales `a 54 mn. 1- Calculer la dur´ee moyenne s´eparant deux trains successifs 2- Un individu arrive ` a un instant quelconque. Au bout de combien de temps en moyenne pourrat-il prendre un train ? On fera le calcul de deux fa¸cons diff´erentes : a- En calculant la probabilit´e pour que l’individu arrive pendant un intervalle court entre deux trains. On en d´eduira le temps d’attente r´esiduelle. b- En appliquant la formule de Pollaczek Khintchine. 3- Comparer les r´esultats de 1 et 2. Ces r´esultats semblent-ils paradoxaux ?

1

2

´ ERAUX ´ CHAPITRE 1. EXERCICES GEN

Chapitre 2

Chaˆınes de Markov ` a temps discret 2.1

Etude d’une Chaˆıne de Markov ` a Temps Discret

Soit une chaˆıne de Markov ` a trois ´etats : 1, 2 et 3. Les probabilit´es de transition de l’´etat 1 vers les ´etats 2 et 3 sont respectivement 1 − p et p. La probabilit´e de transition de l’´etat 2 vers l’´etat 1 est 1. Les probabilit´es de transition de l’´etat 3 vers les ´etats 2 et 3 sont respectivement α et 1 − α. 1- Pour quelles valeurs du couple (α, p) cette chaˆıne est-elle irr´eductible et ap´eriodique ? 2- Pour (α, p) v´erifiant ces conditions, d´eterminer les probabilit´es d’´etat `a l’´equilibre. 3- En r´egime permanent, pour quelles valeurs de (α, p) les trois ´etats sont-ils ´equiprobables ? 4- Calculer le temps moyen de premier retour en 2.

2.2

Processus de naissance et de mort

Soit une chaˆıne de Markov infinie dont les ´etats sont num´erot´es `a partir de 0. La probabilit´e de transition de l’´etat n `a n + 1 est p. La probabilit´e de transition de l’´etat n `a n − 1 est q. D´emontrer qu’il faut avoir p < q pour que les ´etats soient r´ecurrents non nuls. On utilisera un th´eor`eme vu en cours et on effectuera des coupes pour trouver rapidement la solution.

2.3

Mod` eles de trafic sur un lien

On consid`ere un lien transportant des cellules de longueur constante. Compte tenu du synchronisme global, on mod´elise le trafic sous forme d’une chaˆıne de Markov `a temps discret. 1- Trafic de Bernoulli On suppose que les cellules sont ind´ependantes les unes des autres et qu’` a chaque unit´e de temps on a une probabilit´e p qu’il y ait une cellule et 1 − p qu’il n’y en ait pas. Si l’on note Z(t) la variable al´eatoire qui vaut 1 s’il y a une cellule `a l’instant t et 0 sinon, on a P [Z(t) = 1] = p et P [Z(t) = 0] = 1 − p pour toutes les valeurs de t. a- Mod´eliser ce processus sous forme d’une chaˆıne de Markov a` deux ´etats. b- Calculer les probabilit´es des ´etats, le d´ebit de cellules et les deux premiers moments du temps s´eparant deux cellules successives. 2- Trafic Bursty Geometric On suppose que le trafic comporte des silences et des rafales. Pendant les silences il n’y a pas de cellule sur le lien ; pendant les rafales, il y a une cellule `a chaque unit´e de temps. On note X(t) la variable al´eatoire qui vaut 1 si l’on est dans une rafale a` l’instant t et 0 dans un silence. On suppose que P [X(t + 1) = 1/X(t) = 1] = p et P [X(t + 1) = 0/X(t) = 0] = q. a- Montrer que l’on peut repr´esenter le processus (X(t)) par une chaˆıne de Markov. 3

4

` TEMPS DISCRET CHAPITRE 2. CHAˆINES DE MARKOV A

b- D´eterminer les probabilit´es stationnaires des deux ´etats et le d´ebit de cellules. Montrer que les dur´ees des silences et des rafales sont g´eom´etriquement distribu´ees. En d´eduire leur dur´ee moyenne. D´eterminer les deux premiers moments du temps s´eparant deux cellules successives. c- Pour quelles valeurs de p et q un processus Bursty Geometric est-il un processus de Bernoulli ? 3- Trafic Interrupted Bernoulli Process (IBP) Le trafic comporte de nouveau des silences et des rafales de dur´ees g´eom´etriquement distribu´ees de param`etres respectifs p et q. Durant les rafales, les cellules arrivent selon un processus de Bernoulli de param`etre α. Soit Y (t) le processus des arriv´ees de cellules. On aura donc P [Y (t) = 1/X(t) = 1] = α et P [Y (t) = 0/X(t) = 0] = 1. a- Y (t) est-il un processus markovien ? b- D´eterminer le d´ebit, les longueurs moyennes des silences et des rafales d’un processus IBP.

Chapitre 3

Chaˆınes de Markov ` a temps continu 3.1

Processus de Poisson

Application des processus de naissance et de mort : cas d’un processus de naissance pure. C’est un processus pour lequel la probabilit´e conditionnelle de naissance entre t et t + dt vaut λdt. Soit K la variable al´eatoire correspondant au nombre de naissances entre 0 et t : P [K(t + dt) = k + 1/K(t) = k] = λdt 1- Ecrire les ´equations diff´erentielles permettant d’´etudier la famille de fonctions (Pk ), o` u: Pk (t) = P [K(t) = k] 2- D´emontrer que l’on obtient

(λt)k −λt e k! 3- Calculer E[K(t)] et E[K(t)(K(t) − 1)]. En d´eduire V ar[K(t)]. 4- Calculer la fonction de r´epartition du temps s´eparant deux arriv´ees. En d´eduire sa densit´e de probabilit´e. Donner son esp´erance math´ematique. Pk (t) =

5

6

` TEMPS CONTINU CHAPITRE 3. CHAˆINES DE MARKOV A

Chapitre 4

Files d’attentes simples

4.1

Mod` ele du r´ eparateur

On consid`ere une chaˆıne de Markov mod´elisant K machines ind´ependantes. Chacune d’elles peut tomber en panne avec un taux λ. Un r´eparateur r´epare une seule machine `a la fois avec le taux µ. 1- Exprimer le taux de passage de l’´etat (n machines en panne) `a l’´etat (n + 1 machines en panne). On fera une d´emonstration rigoureuse. Il sera peut-ˆetre n´ecessaire de d´emontrer au pr´ealable un lemme sur la loi de l’inf d’un certain nombre de variables de loi exponentielle. 2- Calculer la probabilit´e d’avoir K machines en panne. 3- Application num´erique : K = 7, λ = 0.001, µ = 1.

4.2

Unit´ e de transmission ` a capacit´ e limit´ ee N places E[S] = 400 ms Λ = 2 /s Rejet si plein

On suppose que les messages forment un trafic poissonnien, de d´ebit moyen 2 messages par seconde. La dur´ee de transmission est exponentielle de moyenne E[S] = 400 ms et on n´eglige les erreurs de transmission. On suppose que la priorit´e est FIFO. Quelle doit ˆetre la capacit´e du nœud de transmission pour que la probabilit´e de rejet soit inf´erieure `a 10−3 ?

7

8

Unit´ e de transmission avec des erreurs de transmission

E[S] = 400 ms

p = 0.1

4.3

CHAPITRE 4. FILES D’ATTENTES SIMPLES

Λ = 2 /s

On consid`ere un ´emetteur de messages. – Les messages arrivent avec un d´ebit moyen de 2 messages par seconde. – La dur´ee moyenne de transmission est E[S] = 400 ms. – Le taux d’erreur (donc de retransmission) est p = 10%. – La capacit´e est infinie On fait les hypoth`eses suivantes : arriv´ees poissonniennes, services exponentiels, priorit´e FIFO. 1- Calculer l’esp´erance e du nombre de passages d’un client dans cette file. 2- Calculer l’esp´erance du temps R s´eparant l’arriv´ee du message et le moment o` u il est transmis correctement.

4.4

Etude de la file M/M/C/C

Il s’agit d’une file avec arriv´ees poissonniennes de taux λ avec C serveurs exponentiels de taux µ et avec C places dans la file d’attente. Cela signifie que seuls peuvent entrer dans la file les clients qui peuvent imm´ediatement commencer ` a ˆetre servis, les autres sont rejet´es. 1- D´emontrer que le nombre de clients dans la file constitue un processus de naissance et de mort. Calculer les taux d’arriv´ee et de d´epart conditionnels. 2- Calculer la probabilit´e des divers ´etats possibles. 3- En d´eduire la probabilit´e pour qu’un client arrivant de l’ext´erieur soit rejet´e. Le r´esultat est connu sous le nom de premi`ere formule d’Erlang. 4- Calculer le nombre moyen de clients dans la file et le temps moyen de r´eponse.

4.5

File ` a Serveurs H´ et´ erog` enes

On se propose d’´etudier une file d’attente simple ayant 2 serveurs. Dans tout l’exercice, les arriv´ees seront suppos´ees poissonniennes de taux λ. Les temps de service sont exponentiels, la discipline est FCFS (premier arriv´e, premier servi), la file est `a capacit´e infinie. 1- Serveurs homog` enes On suppose dans un premier temps que les deux serveurs sont identiques. Le taux de service est µ (cf. Fig 4.1). Quand un seul serveur est disponible, le premier client en attente choisit ce serveur. Quand les deux serveurs sont disponibles, le client choisit al´eatoirement et ´equiprobablement un des deux serveurs.

Fig. 4.1 – Serveurs homog`enes

` SERVEURS HET ´ EROG ´ ` 4.5. FILE A ENES

9

a- Donner la notation de Kendall de cette file. b- On note N (t) le nombre de clients dans la file `a l’instant t. Montrer que N (t) est un processus markovien (on pourra montrer que l’inf de deux lois exponentielles ind´ependantes de param`etres µ1 et µ2 est une loi exponentielle). D´emontrer que N (t) constitue un processus de naissance et de mort et calculer les taux d’arriv´ee et de d´epart conditionnels. c- On veut calculer les probabilit´es des divers ´etats possibles. On note πi la probabilit´e qu’il y ait i clients dans la file `a l’´etat stationnaire. D´emontrer que : λ ∀i ≥ 1 πi = 2ρi π0 avec ρ = 2µ D´eterminer π0 . Quelle est la condition de stabilit´e de la file ? d- D´eterminer le nombre moyen E[L] de clients dans la file. Quel est le temps moyen de r´eponse E[R] ? ∞ X ρ On rappelle que pour ρ < 1, on a : nρn = (1 − ρ)2 n=0 2- Serveurs h´ et´ erog` enes On suppose maintenant que le serveur 1 est deux fois plus rapide que le serveur 2 (cf. Fig 4.2). On note 2µ le taux de service du serveur 1 et µ le taux de service du serveur 2. Le choix du serveur se fait de la fa¸con suivante : Si un seul serveur est disponible, le premier client en attente choisit ce serveur. Si les deux serveurs sont libres, le premier client en attente choisit le serveur le plus rapide (le serveur 1).

Fig. 4.2 – Serveurs h´et´erog`enes a- On note N (t) le nombre de clients dans la file `a l’instant t. N(t) est-il un processus markovien ? b- On s´epare l’´etat o` u l’on a un seul client dans la file en deux ´etats : ´etat 1′ : il y a un seul client dans la file, il se trouve dans le serveur 1. ´etat 1” : il y a un seul client dans la file, il se trouve dans le serveur 2. On consid`ere le processus E(t) : E(t) = i, avec i = 0 ou i ≥ 2 s’il y a i clients dans la file `a l’instant t. E(t) = 1′ , s’il y a un client dans la file `a l’instant t qui se trouve dans le serveur 1. E(t) = 1”, s’il y a un client dans la file `a l’instant t qui se trouve dans le serveur 2. Montrer que E(t) est un processus markovien. Calculer les taux d’arriv´ee et de d´epart conditionnels. E(t) est-il un processus de naissance et de mort ? c- On cherche la limite stationnaire de ce processus. Pour simplifier les calculs on suppose que λ = µ. On note πi la probabilit´e stationnaire d’ˆetre dans l’´etat i de la chaˆıne de Markov. D´eterminer les probabilit´es des diff´erents ´etats. On pourra suivre la d´emarche suivante : d´eterminer π3 en fonction de π2 , puis πi+2 en fonction de π2 pour i > 0. En ´ecrivant trois ´equations entre π0 , π1′ , π1′′ , et π2 , montrer que : π0 = 5π2

π1′ = 2π2

π1′′ = π2

10

CHAPITRE 4. FILES D’ATTENTES SIMPLES

Utiliser la condition de normalisation et d´eterminer les πi . Le syst`eme est-il stable ? d- Quel est le nombre moyen E[L] de clients dans la file ? Quel est le temps moyen de r´eponse E[R] ? Quel est le taux d’occupation de chacun des serveurs ? Quel est le temps moyen d’attente E[W ] ? Quelle est la proportion de clients servis par chacun des deux serveurs ?

4.6

Performance d’un ´ etage d’abonn´ es - File M/M/C/C/N

Dans le mod`ele d’un lien du r´eseau t´el´ephonique par une file M/M/C/C, on suppose que le nombre d’utilisateurs potentiels du lien est infini. Si cette hypoth`ese est raisonnable dans le cœur du r´eseau, elle peut se r´ev´eler un peu forte dans la partie d’acc`es (commutateurs d’acc`es, cellule d’un r´eseau GSM ...). L’objectif de cet exercice est d’´etudier les performances d’un lien dans le cas o` u le nombre d’utilisateurs pouvant ˆetre joints par ce lien est limit´e `a N (taille de la population N , C 0 f- (fn−1 ) g- (fn−k ) pour k > 0 h- (nfn ) i- (n(n − 1)(n − 2)...(n − m + 1)fn ) pour m > 1 j- (fn ∗ gn ) o` u ∗ est un produit de convolution k- (fn − fn−1 ) n X l- ( fk ) k=0

3- Calculer les fonctions g´en´eratrices associ´ees aux suites suivantes :

a- f0 = 1, fn = 0 pour n ∈ N∗ b- fn = 1 pour n ∈ N c- fn = Aαn d- fn = nαn e- fn = n2 αn 1 (n + m)(n + m − 1)...(n + 1)αn f- fn = m! 1 g- fn = n! 21

´ CHAPITRE 7. EXERCICES NON CORRIGES

22

4- D´emontrer que : fn =

1 n!



 dn F (z) dz n z=0

Consid´erons le processus N (t), nombre de clients dans une file `a l’instant t, les probabilit´es d’´etats limites stationnaire sont : π(n) = lim P [N (t) = n] t→∞

Utilisons les d´efinitions classiques du cours : L = E[N ] =

∞ X

nπ(n)

n=0

E[N 2 ] =

∞ X

n2 π(n)

n=0

D´emontrer que : 

 dF (z) dz z=1   2  N d E z E[N 2 ] − E[N ] = dz 2 z=1 L=

5- On consid`ere une file avec des arriv´ees Poissonniennes de taux λ de groupes de 2 clients, un serveur exponentiel de taux µ, service FIFO, capacit´ee infinie, population infinie. a- Montrer que le nombre de clients dans cette file est un processus de Markov `a temps continu. b- Faire un sch´ema de la Chaˆıne de Markov `a temps continu. c- Ecrire les ´equations obtenues en coupant entre k et k + 1. d- Multiplier cette ´equation par z k et additionner toutes les ´equations. En d´eduire l’esp´erance et la variance du nombre de clients dans la file.

7.2

Etude de la file M/GI/1

Etant donn´ee une suite (fn )n∈Z , v´erifiant ∀n ∈ N∗− fn = 0, on d´efinit la fonction g´en´eratrice (z-transform en anglais) de la variable r´eelle ou complexe z par : F (z) =

∞ X

fn z n

n=0

1- Lorsque les fn sont des probabilit´es d’´etats π(n) avec n ∈ N, montrer que F est analytique sur le disque unit´e puis calculer F (1). 2- Si les fn sont les probabilit´es d’´etats du processus nombre de clients dans une file, exprimer l’esperance de la longueur de la file en fonction de F (z). 3- Consid´erons le processus {Xk }k≥1 = {n(tk )}k≥1 nombre de clients juste apr`es le d´epart du k-i`eme client dans une file M/GI/1. Montrer que ce processus est une CMTD. 4- Soit αc la probabilit´e pour que c clients soient arriv´es durant le temps de service du (k + 1)-i`eme client. Montrer que si fS est la densit´e de probabilit´e du service : Z ∞ (λx)c −λx e fS (x)dx αc = c! 0 Soit π(n) la probabilit´e limite stationnaire d’´etat de la chaˆıne d´efinie `a la question 3 et pi,j la probabilit´e de transition de l’´etat i vers l’´etat j. 5- V´erifier que pi,j = αj−i+1 pour i ≥ 1 et j ≥ i − 1 et que p0,j = αj pour j ≥ 0.

7.2. ETUDE DE LA FILE M/GI/1

23

6- On veut r´esoudre le syt`eme π = πP (1). On d´efinit les transform´ees en z des π(n) et des αj qu’on appelle F (z) et V (z). Montrer `a partir de (1) que : π(0)V (z)(1 − z) F (z) = V (z) − z 7- D´eterminer π(0) de deux mani`eres diff´erentes 8- Questions ”bonus” : a- D´emontrer que le nombre moyen de clients est : L=ρ+

ρ2 (1 + Cs2 ) 2(1 − ρ)

avec Cs le coefficient de variation du temps de service. b- En d´eduire les autres param`etres de performance. c- Donner alors les param`etres de performance pour les files M/M/1, M/D/1 et M/Ek /1.

24

´ CHAPITRE 7. EXERCICES NON CORRIGES

Chapitre 8

Corrig´ es Mod` ele du dentiste 1- Pour chaque client, on a R = W + S. Ce r´esultat est donc vrai en terme d’esp´erance. 2- Pour chaque client, on a L = LW + LS . Ce r´esultat reste donc vrai en terme d’esp´erance. 3- Le nombre de clients en train d’ˆetre servis est de 1 avec la probabilit´e U et de 0 avec la probabilit´e 1 − U . On a donc : E[LS ] = 0 ∗ (1 − U ) + 1 ∗ U d’o` u E[LS ] = U . 4- En multipliant l’´equation (1) par Λ, on a : E[R] ∗ Λ = E[S] ∗ Λ + E[W ] ∗ Λ. En appliquant la loi de Little aux syst`emes global, file seule puis serveur seul, on a : E[L] = E[R] ∗ Λ,

E[LW ] = E[W ] ∗ Λ et E[LS ] = E[S] ∗ Λ

L’´equation (2) vient imm´ediatement. La relation connue entre U , Λ et E[S] s’obtient en utilisant le r´esultat obtenu en appliquant la loi de Little au serveur et celui de la question 3. On a alors : U = E[S] ∗ Λ 5- L’´enonc´e donne E[L] = 2.8 client, E[LW ] = 2 client et Λ = 4 clients par heure. On en d´eduit : – En moyenne, le nombre E[Ls ] de clients soign´es est 0.8, ce qui revient `a dire que le denstiste est occup´e ` a 80% du temps. 2.8 a dire 42 – De plus, aller chez le dentiste occupe pendant E[R] = E[L] Λ = 4 = 0.7 heure, c’est ` minutes. – Plus pr´ecis´ement, on passe E[W ] = E[LΛW ] = 2/4 = 0.5 heure dans la salle d’attente, c’est `a dire 30 minutes. – On en d´eduit que le dentiste nous soigne en 12 minutes...

Temps d’attente d’un train 1- E[X] = 0.9 ∗ 6 + 0.1 ∗ 54 = 10.8 soit 10 minutes 48 secondes. 2- Sur 100 intervalles de temps, il y a en moyenne 90 intervalles courts de 6 minutes qui durent 540 minutes et 10 intervalles longs de 54 minutes qui durent 540 minutes. Donc sur 1080 minutes, il y en a 540 qui correspondent ` a des intervalles courts et 540 qui correspondent `a des intervalles longs. Donc pour un voyageur qui arrive `a un instant quelconque, il a une probabilit´e 21 d’arriver pendant un intervalle court (et pas du tout 90%) et 21 d’arriver pendant un intervalle long. a- Si on arrive pendant un intervalle court, il faudra attendre 3 minutes en moyenne. Si on arrive pendant un intervalle long, on attendra 27 minutes en moyenne. Donc E[Y ] = 12 ∗ 3 + 21 ∗ 27 = 15 minutes. 25

´ CHAPITRE 8. CORRIGES

26

b- On peut ´ecrire la formule de Pollaczek Khintchine qui donne le temps d’attente r´esiduel en 1 + C 2 (X) fonction du temps d’attente : E[Y ] = E[X] ∗ , qui donne le mˆeme r´esultat : 2 0.9[6 − 10.8]2 + 0.1[54 − 10.8]2

V ar[X] = =

207, 3

C 2 [X] =

207.36 V ar[X] = 1.7777 = 2 E [X] 10.82

d’o` u : E[Y ] = 15 minutes 3- On constate que E[Y ] > E[X], c’est le paradoxe de l’auto-stoppeur.

Etude d’une Chaˆıne de Markov ` a Temps Discret 1- Une chaˆıne est irr´eductible si tout ´etat peut-ˆetre atteint (en un nombre fini) de pas. Il est clair que si α = 0, alors l’´etat 3 est absorbant. D’autre part, si p = 0, le couple d’´etats (1, 2) est absorbant. Supposons que α 6= 1. Il existe alors une boucle sur l’´etat 3 et la chaˆıne est donc ap´eriodique. Supposons maintenant que α = 1. Si p 6= 1, il existe alors un circuit de longueur 2 et un circuit de longueur 3. La chaˆıne est donc ap´eriodique. Si p = 1, il n’y a plus qu’un seul circuit de longueur 3 et la chaˆıne est p´eriodique. Les condition d’irr´eductibilit´e et d’ap´eriodicit´e sont donn´ees par : 0 0 Pk (t + dt)

= P [K(t + dt) = k] = P [K(t) = k] ∗ P [K(t + dt) = k/K(t) = k] +P [K(t) = k − 1] ∗ P [K(t + dt) = k/K(t) = k − 1] = Pk (t) ∗ (1 − λdt) + Pk−1 (t) ∗ λdt

′

d’o` u : Pk (t) = λPk−1 (t) − λPk (t) Les ´equations diff´erentielles permettant d’´etudier la famille de fonctions sont :  ′ P0 (t) + λP0 (t) = 0 ∗ ∀k ∈ N ∀t ∈ R Pk′ (t) + λPk (t) = λPk−1 (t) 2- Il suffit de r´esoudre les ´equations diff´erentielles pr´ec´edentes pour r´epondre `a la question. Pour k = 0 En sachant que P0 (0) = 1, il vient : P0 (t) = e−λt Pour k > 0 k −λt pour k ∈ N : Il suffit de proc´eder par r´ecurrence que Pk (t) = (λt) k! e – Pour k=0, c’est d´ej` a d´emontr´e – Supposons le r´esultat vrai pour un certain k et d´emontrons la formule en k + 1 Nous pouvons rechercher Pk+1 (t) sous la forme K(t)e−λt . On a donc ′ Pk+1 (t) = (K ′ (t) − λK(t))e−λt k

En utilisant alors la formule de r´ecurrence, on en d´eduit que K ′ (t) = λ (λt) d’o` u k! (λt)k+1 + C. En utilisant la condition initiale Pk+1 (0) = 0, il vient : K(t) = (k + 1)! Pk+1 (t) =

(λt)k+1 −λt e (k + 1)!

ce qui ´etablie la propri´et´e au rang k + 1. Nous avons donc : ∀k ∈ N ∀t ∈ R

Pk (t) =

(λt)k −λt e k!

´ CHAPITRE 8. CORRIGES

30

3Calcul de E[K(t)] E[K(t)]

= = = =

∞ X (λt)k −λt k e k! k=0 ∞ X (λt)k e−λt k k! k=1 ∞ X (λt)(k−1) e−λt λt (k − 1)! k=1 λt

E[K(t)] = λt Calcul de E[K(t)(K(t) − 1)] En utilisant le th´eor`eme de transfert : E[K(t)(K(t) − 1)]

= =

∞ X

k=0 ∞ X

k(k − 1)

(λt)k −λt e k!

k(k − 1)

(λt)k −λt e k!

k=2

= = = =

∞ X (λt)k (k − 2)! k=2 ∞ X (λt)k−2 e−λt (λt)2 (k − 2)! k=2 ∞ X (λt)k e−λt (λt)2 k! k=0 2 (λt)

e−λt

E[K(t)(K(t) − 1)] = (λt)2 C alcul de E[K 2 (t)] E[K 2 (t)] = E[K(t)(K(t) − 1) + K(t)] = E[K(t)(K(t) − 1)] + E[K(t)] = (λt)2 + λt Calcul de V ar[K(t)] V ar[K(t)] = E[K 2 (t)] − E[K(t)]2 = (λt)2 + λt − (λt)2 = λt 4Fonction de r´ epartition du temps s´ eparant deux arriv´ ees Nous pouvons raisonner ` a partir du temps 0 et rechercher la probabilit´e qu’un ´ev`enement arrive avant t. Soit tˆ le temps s´eparant deux arriv´ees. Nous cherchons P [tˆ < t] = 1 − P [tˆ >= t] = 1 − P [K(t) = 0] d’oˆ u: P [tˆ < t] = 1 − e−λt Densit´ e de probabilit´ e La densit´e de probabilit´e de tˆ est la d´eriv´ee de la fonction de r´epartition de tˆ : ftˆ = λe−λt Esp´ erance math´ ematique L’esp´erance math´ematique de tˆ est, en int´egrant par partie : R∞ E[tˆ] = t=0 tftˆ(t)dt = λ1

La moyenne du temps s´eparant deux arriv´ees est donc l’inverse du param`etre de Poisson de la loi d’arriv´ee... On a donc deux d´efinitions pour les lois de Poisson : celle donn´ee `a la premi`ere question du sujet et celle qui caract´erise le temps entre deux arriv´ees tˆ.

31

Modele du r´ eparateur Nous consid´erons une chaˆıne de Markov `a K ´etats. L’´etat i est atteint lorsque i machines parmi les K sont en pannes. 1Lemme sur la loi de l’inf de n variables ind´ependantes de loi exponentielle Soit n variables al´eatoires ind´ependantes Xi de loi exponentielle de param`etre λi . P [Inf (Xi ) ≤ x] = 1 − P [Inf (Xi ) > x] (Passage au compl´ementaire) n Y P [Xi > x] (Ind´ependance des variables) = 1− i=1 n Y

=

1−

=

1−e

e−λi x

i=1 Pn

i=1

λi x

Lorsque x tend vers 0, nous avons donc : P [Inf (Xi ) ≤ x] =

n X

λi x + o(x)

i=1

Expression du taux de passage de l’´ etat n ` a l’´ etat n + 1 Nous supposons donc qu’il y a K − n machines en ´etat de marche. Soit Xi le temps qui s´epare l’instant courant de la panne de la machine i. La premi`ere machine tombera en panne au bout d’un temps Inf (Xi ). La probabilit´e de passer de l’´etat n `a l’´etat n + 1, c’est `a dire P[X(t+dt)=n+1 / X(t+dt)=n] est donc : P [X(t + dt) = n + 1/X(t) = n] = (K − n)λdt + o(dt) Expression du taux de passage de l’´ etat n + 1 ` a l’´ etat n Le r´eparateur est exponentiel et l’on passe donc de l’´etat n + 1 `a l’´etat n avec le taux µ. 2- On a bien un procesus sans m´emoire, qui de plus, ´evolue uniquement par saut de 1 ou -1. C’est donc un processus de naissance et de mort.

On a donc :

K! λ(0)λ(1)...λ(n − 1) P (0) = P (n) = µ(1)µ(2)...µ(n) (K − n)!

La probabilit´e d’avoir K machines en pannes est donc :  K K! µλ  n P (K) = P K K! n=0 (K−n)!

soit :

P (K) =

1 PK

1 n=0 (K−n)!

d’o` u en r´eindexant (n=K-n) :

λ µ

 n−K λ µ

 n λ P (0) µ

´ CHAPITRE 8. CORRIGES

32

P (K) =

1 −n

( µλ )

1 n=0 n!

PK

3- On trouve : P (7) = 4.7 10−11 .

Unit´ e de transmission ` a capacit´ e limit´ ee On suppose que les messages forment un trafic poissonnien, de d´ebit moyen 2 messages par seconde. La dur´ee de transmission est constante E[S] = 400 ms et on n´eglige les erreurs de transmission. Quelle doit ˆetre la capacit´e du nœud de transmission pour que la probabilit´e de rejet soit inf´erieure `a 10−3 ? Il y a rejet que si et seulement si la file `a capacit´e limit´ee est pleine. En faisant une coupe, on obtient P (n) = (λS)n P (0) d’o` u en utilisant l’´equation de normalisation :

soit, en posant ρ = λS :

(λE[S])n ∀n ∈ [0..N ] P (n) = PN i i=0 (λE[S]) ∀n ∈ [0..N ] P (n) =

1−ρ ρn 1 − ρN +1

La probabilit´e de rejet est donc : Prejet = P (N ) =

1−ρ ρN 1 − ρN +1

1−ρ ρN < 10−3 ´equivaut `a x − ρx < 10−3 1 − ρN +1 10−3 10−3 N d’o` u ρ < . Il faut passer ensuite au en posant x = ρN . Soit x < −3 1 − ρ + 10−3 ρ  1 − ρ−3+ 10 ρ 10 , d’o` u, puisque ρ < 1 et ln(ρ) < 0 : logarithme : N ln(ρ) < ln 1 − ρ + 10−3 ρ On en d´eduit alors N pour que Prejet < 10−3 :

ln N>



10−3 1−ρ+10−3 ρ

ln(ρ)



On trouve alors : ρ = λE[S] = 0.8 et N ≥ 24

Unit´ e de transmission avec des erreurs de transmission 1- Notons λe le flux d’entr´ ee dans la file d’attente, λs le flux `a la sortie du serveur, λd celui de d´ epart du syst`eme et λr le flux de rebouclage. p On a toujours λr = pλs et λd = (1 − p)λs , soit aussi : λr = λd . 1−p L’additivit´e des flux, avant l’entr´ee dans la file d’attente donne toujours : λe = λ + λr . On a λe = λe, de par la d´efinition de e. Il existe au moins quatre fa¸cons de trouver le nombre moyen de passages e dans le syst`eme {file d’attente ; serveur} : Stationnarit´ e du syst` eme {file d’attente ; serveur} Sous cette hypoth`ese, le flux de sortie du serveur est ´egal a` λe : λs = λe . On a donc λr = pλe. En utilisant l’additivit´e des flux, nous pouvons ´ecrire λe = λ + pλe et r´esoudre en e. Stationnarit´ e du syst` eme {file d’attente ; serveur ; rebouclage} p Sous cette hypoth`ese, le flux de d´epart du syst`eme est ´egal `a λ : λd = λ, d’o` u λr = λ 1−p p λ et r´esoudre en e. En utilisant l’additivit´e des flux, nous pouvons ´ecrire λe = λ + 1−p Esp´ erance de e Soit X la variable al´eatoire indiquant le nombre de passages d’un client dans le syst`eme {file

33

d’attente ; serveur}. Un client passe exactement k fois dans la file avec la probabilit´e pk−1 (1 − p) : ∀k ∈ N

P [X = k] = pk−1 (1 − p)

L’esp´erance de E est donc : E[X] =

∞ X

ip

i−1

(1 − p) = (1 − p)

 ∞  X d(xi ) i=1

i=1

dx

x=p

= (1 − p)

∞ X i=1

i

x

!

x=p

k

Sommer les p On passe une fois avec la probabilit´e 1, une deuxi`eme avec la probabilit´e p, une troisi`eme p2 , etc. D’o` u le r´esultat en sommant pk de k = 0 `a l’infini. Conclusion Le nombre moyen de passages e dans la file est : 1 e= 1−p 2- Nous pouvons consid´erer le syst`eme complet {file d’attente ; serveur ; rebouclage} et y appliquer la loi de Little : L = E[R]λ o` u L est le nombre de client dans le syst`eme complet. Soit N (t) le processus indiquant le nombre de client dans le syst`eme complet. Le processus d’arriv´ee dans le syst`eme est poissonnien. Un client ne quitte le syst`eme qu’apr`es un service exponentiel et avec la probabilit´e (1-p). N (t) est donc Markovien. Un seul client ne peut arriver pendant dt et ceci se produit avec la probabilit´e λdt + o(dt). Un seul client ne peut sortir du syst`eme pendant dt, et ceci avec la probabilit´e µ(1 − p) + o(dt). C’est donc λ λ = E[S], on trouve : un processus de naissance et de mort. En posant ρ = (1 − p)µ 1−p πn = (1 − ρ)ρn

∀n ∈ N d’o` uL=

∞ X i=0

iπi =

ρ . On a donc : 1−ρ L=

λE[S] 1 − p − λE[S]

Conclusion et applications num´ eriques En utilisant la loi de Little sur le syst`eme entier, on obtient : E[R] =

E[S] 1 − p − λE[S]

On trouve L = 8 et E[R] = 4s. Remarque On peut aussi consid´erer cela comme un r´eseau de Jackson `a une seule file avec e =

1 1−p .

Etude de la file M/M/C/C 1- Soit N (t) le nombre de clients dans le syst`eme `a l’instant t. N (t) est markovien car la seule connaissance de N (t) permet de pr´evoir les prochains d´eparts de clients (temps r´esiduel de service exponentiel), la prochaine arriv´ee de client (temps r´esiduel de service exponentiel). N (t) est un processus de naissance et de mort si les seules transitions possibles se font entre les ´etats voisins : (λT )k −λT e . La probabilit´e qu’il y ait k arriv´ees pendant un intervalle de temps T est Pk (T ) = k!  −λdt P0 (dt) = e = 1 − λdt + o(dt)  −λdt On a donc : e = λdt + o(dt) P1 (dt) = λdt 1!  ∀k > 1 Pk (dt) = o(dt) Le processus d’arriv´ee est poissonnien et il ne peut y avoir qu’une seule arrive entre t et t + dt.

´ CHAPITRE 8. CORRIGES

34

La probabilit´e qu’il y ait j d´eparts pour k serveurs occup´es pendant un intervalle de temps dt est : Qj (dt) = Ckj (µdt + o(dt))j (1 − µdt + o(dt))k−j  Q0 (dt) = 1 − kµdt + o(dt)  Q1 (dt) = kµdt + o(dt) On a donc :  ∀j > 1 Qj (dt) = o(dt) Le processus N (t) est donc un processus de naissance et de mort. Les taux d’arriv´ees et de d´epart sont respectivement λ et kµ o` u k est le nombre de serveurs occup´es. 2- En ´ecrivant la chaˆıne de Markov associ´ee `a la file et en coupant entre l’´etat n et n + 1, nous avons : ∀n λπ(0) = (n + 1)µ d’o` u ∀n

π(n) =

1 n!

 n λ π(0) µ

d’o` u en ´ecrivant l’´equation de normalisation, on obtient : ∀n

π(n) =

1 1 P 1 k−n n! C ρ k=0 k!

3- La probabilit´e qu’un client qui arrive soit rejet´e est la probabilit´e que la file soit pleine, c’est `a dire : 1 1 Prejet = PC 1 k−C C! k=0 ρ k!

4- Le nombre moyen de clients dans la file est : L = E[N ] ==

C X

n=0

nπ(n) =

C X

n=0

n

1 1 PC 1 k−n = ρ(1 − prejet ) n! k=0 ρ k!

Le temps moyen de r´eponse E[R] est ´egal `a E[W ] + E[S] avec ici E[W ] = 0 (pas d’attente). u E[R] = µ1 . On peut ´ecrire que E[S] = µ1 (temps moyen de service) d’o` Une autre solution est d’appliquer la loi de Little au syst`eme des serveurs. On a E[L] = E[S]Λ o` u Λ est le d´ebit entrant dans ce syst`eme. Ici, nous avons vu que Λ = (1 − prejet )λ d’o` u E[R] = ρ 1 L E[S] = = = . Λ λ µ

File ` a Serveurs H´ et´ erog` enes

1- Serveurs homog` enes a- C’est une file ` a arriv´ees poissonniennes de taux λ (On ´ecrit M car Markovien), `a services exponentiels de param`etre µ (M), comportant 2 serveurs. La priorit´e est celle par d´efaut, FCFS. Le nombre de place est infini (par d´efaut) et la population aussi (par d´efaut). La notation de Kendall de la file est M/M/2. b- N (t) est Markovien car la seule connaissance de N(t) permet de pr´evoir les prochains d´eparts de clients (temps r´esiduel de service exponentiel) ainsi que la prochaine arriv´ee de client (temps r´esiduel d’interarriv´ee exponentiel). C’est un processus de naissance et de mort et les taux de passage sont :   P [N (t + dt) = k + 1/N (t) = k] =λdt + o(dt) ∀k ≥ 0 µdt + o(dt) k=1  P [N (t + dt) = k − 1/N (t) = k] = 2µdt + o(dt) ∀k ≥ 1 c- En ´ecrivant la chaˆıne de Markov associ´ee `a la file et en effectuant une coupe on trouve : ∀i ≥ 1 πi = 2ρi π0

avec ρ =

λ 2µ

Il suffit d’´ecrire l’´equation de normalisation pour d´eterminer π0 . Si la condition de stabilit´e de la file est v´erifi´ee, ρ < 1 , on trouve que :

35

π0 =

1−ρ 1+ρ

πk =

1−ρ k 2ρ 1+ρ

d- Le calcul de L conduit ` a: E[L] =

2ρ 1 − ρ2

En ´ecrivant la loi de Little, on a : E[R] =

2 µ(1 − ρ2 )

2- Serveurs h´ et´ erog` enes a- Le processus N (t) n’est pas Markovien car lorsque N (t) = 1, on ne peut pas pr´edire le passage `a l’´etat 0. En revanche, nous savons que le temps r´esiduel est exponentiel, mais nous ne connaissons pas son param`etre. En effet, si c’est le premier serveur qui est occup´e, alors le param`etre vaut 2µ, si c’est le second, il vaut µ. Le processus N (t) n’est pas Markovien. b- E(t) est un processus Markovien car il permet de savoir dans quel serveur se trouve le client lorsqu’il n’y en a qu’un dans la file. Nous pouvons calculer les probabilit´es de transition : ∀k > 0

∀k > 2

P [N (t + dt) = k + 1/N (t) = k] P [N (t + dt) = 0/N (t) = 1′ ] P [N (t + dt) = 0/N (t) = 1′′ ] P [N (t + dt) = 1′ /N (t) = 2] P [N (t + dt) = 1′′ /N (t) = 2] P [N (t + dt) = k − 1/N (t) = k]

= = = = = =

λdt + o(dt) 2µdt + o(dt) µdt + o(dt) µdt + o(dt) 2µdt + o(dt) 3µdt + o(dt)

Ce n’est pas un processus de naissance et de mort, car l’´etat 2 est reli´e `a trois ´etats diff´erents. c- Nous d´eterminons : π3 =

1 λ π2 = π2 3µ 3

puis

i  i 1 λ π2 = ∀i ≥ 0 πi+2 = 3µ 3 En effectuant une coupe autour de l’´etat 0, nous avons : 

λπ0 = 2µπ1′ + µπ1′′ En effectuant une coupe autour de 1′′ , nous avons : (µ + λ)π1′′ = 2µπ2 En effectuant une coupe ` a gauche de π2 , nous avons : λ(π1′ + π1′′ ) = 3µπ2 On en d´eduit que : π0 = 5π2

π1′ = 2π2

π1′′ = π2

Condition de normalisation : ∞ X

πi = 1 = π2 5 + 2 + 1 +

i=0

or

"

λ < 1 donc le syst`eme est stable . 3µ On en d´eduit :

∞  i X 1 i=0

3

#

´ CHAPITRE 8. CORRIGES

36

π2 =

2 10 4 2 , π0 = , π1′ = , π1′′ = 19 19 19 19 πk+2 =

2 19

 k 1 3

dCalcul du nombre de clients E[L] = 0 ∗ π0 + 1 ∗ π1′ + 1 ∗ π1′′ +

∞ X

kπk

k=2

E[L]

= =

 k−2 ∞ 2 X 6 1 + k 19 19 3 k=2 "  k−1 # ∞ X 1 6 k 1+ 19 3 k=2

Apr`es avoir calcul´e la derni`ere somme, on trouve : E[L] =

27 38

Calcul du temps de r´ eponse En appliquant la loi de Little, nous d´eterminons : E[R] =

27 E[L] = λ 38λ

Calcul du taux d’occupation de chacun des serveurs On a directement : U1 = 1 − π0 − π1′′ =

7 19

U2 = 1 − π0 − π1′ =

5 19

Temps moyen d’attente E[W ] Soit E[LW ] le nombre moyen de clients en attente. Nous avons : E[L] = E[LW ] + E[LS ] o` u E[LS ] = E[L1 ]+E[L2 ], avec E[L1 ] = U1 , E[L2 ] = U2 . On en conclue que E[LW ] = E[L]−U1 −U2 = 3 38 . En appliquant la loi de Little au syst`eme sans les serveurs, nous d´eterminons : E[W ] =

3 E[LW ] = λ 38λ

Nous pouvons calculer de la mˆeme facon le temps E[S] : Soit E[Ls ] le nombre moyen de clients en service. Nous avons : E[LS ] = E[L1 ] + E[L2 ] = U1 + U2 . On en conclue que E[LS ] = 12 19 . En appliquant la loi de Little au syst`eme des deux serveurs, nous d´eterminons : E[S] =

E[LS ] 12 = λ 19λ

Proportion de clients servis par chacun des deux serveurs Soit λ1 le d´ebit de ceux qui sont trait´es par le serveur rapide. Soit λ2 le d´ebit de ceux qui sont U2 U1 = 2µU1 et λ2 = E[S = µU2 . trait´es par le serveur lent. On a λ = λ1 + λ2 . De plus, λ1 = E[S 1] 2] Nous pouvons alors d´eterminer la proportion de clients servis par chaque serveur. La proportion de clients services par le serveur rapide est :

37

2U1 14 2µU1 λ1 = = = = 73, 7% λ 2µU1 + µU2 2U1 + U2 19 La proportion de clients services par le serveur lent est : U2 5 µU2 λ2 = = = = 26, 3% λ 2µU1 + µU2 2U1 + U2 19

Performance d’un ´ etage d’abonn´ es - File M/M/C/C/N 1- Montrons que la seule connaissance de N (t) suffit `a d´eterminer N (t + dt) : Premi` ere m´ ethode Arriv´ ees Supposons que N (t) = k, avec k ∈ [0..C]. Le nombre de client en dans la premi`ere file est donc : (N − k). Il y a exactement i arriv´ees (i tel que k + i ≤ C puisque le nombre de clients pouvant ˆetre servi est limit´e par C et i ≤ N − k puisque le nombre de clients dans la premi`ere file est N − k) dans la seconde file pendant dt si il y a i fins de service exponentiels de param`etre λ dans la premi`ere file et N − k − i clients qui ne finissent pas leur service : i i N −k−i ∀i ∈ [1, C − k] P [N (t + dt) = k + i/N (t) = k] = CN −k (λdt + o(dt)) (1 − λdt + o(dt))

Nous en concluons que : P [N (t + dt) = k + 1/N (t) = k] = (N − k)λdt + o(dt) ∀i ∈ [2, C − k] P [N (t + dt) = k + i/N (t) = k] = o(dt) La connaissance de N (t) = n permet donc de pr´evoir les arriv´ees entre t et t + dt. Un seul client peut arriver pendant dt et il arrive avec le taux (N − n)λ. D´ eparts Supposons que N (t) = k, avec k ∈ [0..C]. Il y a exactement i d´eparts (i tel que i ≤ k puisque le nombre de clients dans la seconde file est k) si il y a i fins de service exponentiels de param`etre µ et k − i clients qui ne finissent pas leur service : ∀i ∈ [0, k] P [N (t + dt) = k − i/N (t) = k] = Cki (µdt + o(dt))i (1 − µdt + o(dt))k−i Nous en concluons que : P [N (t + dt) = k − 1/N (t) = k] = kµdt + o(dt) ∀i ∈ [1, k] P [N (t + dt) = k − i/N (t) = k] = o(dt) La connaissance de N (t) = n permet donc de pr´evoir les d´eparts entre t et t + dt. Un seul client peut partir pendant dt et il part avec le taux nµ. Seconde m´ ethode Arriv´ ees Supposons que N (t) = k, avec k ∈ [0..C]. Nous savons qu’il ne peut y avoir qu’un seul d´epart entre t et t + dt de la premi`ere file de service exponentiel de param`etre λ (il pourrait y avoir deux d´eparts, mais avec une probabilit´e en dt2 infiniment petite par rapport `a la probabilit´e pour qu’il y en est un qui est en dt). Nous savons de plus que ce d´epart suit la loi de l’inf du temps r´esiduel des N − k services exponentiels. Il a ´et´e d´emontr´e que la loi de l’inf de p lois exponentielles de param`etre λi est une loi exponentielle de param`etre la somme des λi . Ici, nous avons N − k services exponentielles de param`etre λ d’o` u: P [N (t + dt) = k + 1/N (t) = k] = (N − k)λdt + o(dt) D´ eparts

´ CHAPITRE 8. CORRIGES

38

Supposons que N (t) = k, avec k ∈ [0..C]. Nous savons qu’il ne peut y avoir qu’un seul d´epart de la seconde file entre t et t + dt. Ce d´epart se fait selon la loi de l’inf des k lois r´esiduelles des clients en service, d’o` u: P [N (t + dt) = k − 1/N (t) = k] = kµdt + o(dt) Conclusion Le processus N (t) est Markovien. De plus, c’est un processus de naissance et de mort `a C + 1 ´etats o` u: ∀n ∈ [0, C − 1] λ(n) = (N − n)λ ∀n ∈ [1, C] µ(n) = nµ La chaˆıne de Markov comporte un nombre fini d’´etats et est fortement connexe. Le processus est donc ergodique. 2- N (t) ´etant un processus de naissance et de mort, nous avons : λ(0)...λ(n − 1) N! ∀n ∈ [0, C] π(n) = = µ(1)...µ(n) (N − n)!n! Ce qui peut s’´ecrire, en posant ρ =

 n λ π(0) µ

λ : µ

n n ∀n ∈ [0, C] π(n) = CN ρ π(0)

Nous d´eterminons alors les probabilit´es stationnaires, apr`es avoir utilis´e la condition de normalisation : C n ρn ∀n ∈ [0, C] π(n) = PC N i i i=0 CN ρ

3- Nous ne pouvons pas appliquer la propri´et´e PASTA ici. Il serait faux d’´ecrire que la probabilit´e de rejet est celle d’avoir C clients dans la file, comme nous allons le montrer. Notons ΠN (C) la probabilit´e que C serveurs soient occup´es lorsqu’il y a N clients dans le r´eseau :

Calcul du d´ ebit au point A : ΛA Le d´ebit au point A est : ΛA

C C ρC ΠN (C) = PC N i i i=0 CN ρ

= =

C X

k=0 C X

(N − k)λπ(k) k k (N − k)λCN ρ π(0)

k=0

Premi` ere m´ ethode Cette premi`ere m´ethode consiste ` a suivre les indications du sujet en calculant le d´ebit au point B: Calcul du d´ ebit au point A : ΛB Le d´ebit au point B est obtenu en consid´erant qu’il y a C clients dans la file 2 (avec la probabilit´e π(C). Il y a alors N − C clients dans la 1. Une fois servi dans la file d’attente, il sont tous rejet´e, d’o` u: ΛB

= =

(N − C)λπ(C) C C (N − C)λCN ρ π(0)

Calcul de la probabilit´ e de rejet La probabilit´e de rejet est le rapport entre le d´ebit rejet´e et le d´ebit offert :

39

P (rejet)

= = =

d’o` u:

ΛB ΛA C (N − C)CN λρC π(0) PC k k k=0 (N − k)λCN ρ π(0) C C (N − C)CN ρ PC k k k=0 (N − k)CN ρ

(N −1)! N! C C ρC ρC (N − C) (N −C)!C! N (N −1−C)!C! CN −1 ρ = P (rejet) = PC = = ΠN −1 (C) P P C C (N −1)! N! k k k k k=0 (N − k) (N −k)!k! ρ k=0 CN −1 ρ k=0 N (N −1−k)!k! ρ

Seconde m´ ethode Cette seconde m´ethode consiste a` calculer le d´ebit au point E : Calcul du d´ ebit au point E : ΛE Le d´ebit au point E est : ΛE

= = = = = = =

C X

k=0 C X

k=1 C X

k=1 C X

k=1 C X

k=1 C X

kµπ(k) kµπ(k) kµ

N! ρk π(0) (N − k)!k!

λρk−1

N! (N − (k − 1))π(0) (N − k + 1)!(k − 1)!

k−1 k−1 λ(N − (k − 1))CN ρ π(0)

λ(N − (k − 1))π(k − 1)

k=1 C−1 X

λ(N − k)π(k)

k=0

Calcul de la probabilit´ e de rejet

ΛD . Or ΛD = ΛE . Nous d´eterminons : ΛA PC−1 λ(N − k)π(k) ΛE P (rejet) = 1 − = 1 − Pk=0 C ΛA k=0 (N − k)λπ(k)

La probabilit´e de rejet est ´egale ` a : 1−

soit :

(N − C)λπ(C) P (rejet) = PC k=0 (N − k)λπ(k)

En simplifiant, comme dans la premi`ere m´ethode, ceci conduit `a P (rejet) = ΠN −1 (C)

Conclusion Dans cet exercice, la propri´et´e PASTA ne s’applique pas. On observe que la probabilit´e de rejet est ´egale ` a la probabilit´e que l’on aurait eu d’avoir C serveurs occup´es si il y avait eu N − 1 clients et non N . En r´ealit´e, ce r´esultat n’est pas le seul fruit du hasard. Il s’agit en fait de l’application particuli`ere `a ce probl`eme d’un th´eor`eme connu sous le nom Sevcik Mitrani : Lorsqu’un client entre dans une file dans un r´ eseau BCMP il voit cette file dans un ´ etat qui est en moyenne l’´ etat de la file dans le mˆ eme r´ eseau ferm´ e mais avec un client de moins au total dans le r´ eseau ferm´ e

´ CHAPITRE 8. CORRIGES

40

Influence de la variance des services et de la loi de priorit´ e Nous avons : Ui = ρi = λi E[Si ] d’o` u: U1 = ρ1 = 0.25 et U2 = ρ2 = 0.375 Pour calculer U , probabilit´e que le serveur soit occup´e, il suffit d’additionner les probabilit´es pr´ec´edentes : U = U1 + U2 = 0.625 On peut aussi ´ecrire que U = ρ = λE[S] o` u λ est le d´ebit global et E[S] le temps moyen de service, toutes classes confondues : λ = λ1 + λ2 = 1/2.4 + 1/0.8 = 1.6667 = 1/0.6 E[S] est la moyenne des temps de service : E[S] =

λ1 λ2 E[S1 ] + E[S2 ] = 0.375 λ λ

ce qui donne : U = ρ = 0.375/0.6 = 0.625 Service PS ρ , d’o` u: Dans ce cas, on a E[Wi ] = E[Si ] 1−ρ ρ ρ E[W1 ] = E[S1 ] = 1 et E[W2 ] = E[S2 ] = 0.5 1−ρ 1−ρ Pour calculer E[W], il suffit de dire que c’est la moyenne des temps de s´ejour dans le buffer : E[W ] =

λ2 λ1 E[W1 ] + E[W2 ] = 0.625 λ λ

On peut aussi dire que : E[W ] = E[S]

ρ = 0.625 1−ρ

Dans le cas d’un service PS, que les services soient constants ou exponentiels, nous avons : E[R1 ] = E[W1 ] + E[S1 ] = 1.6 E[R2 ] = E[W2 ] + E[S2 ] = 0.8 E[R] = E[W ] + E[S] = 1 Service FCFS

C

La formule l’attente E[Wi ] =

1 + Cj2 1 X ρj E[Sj ] montre que l’attente dans le buffer est 1 − ρ j=1 2

ind´ependante des classes, mais d´epend des carr´es des coefficients des services. Services Constants On a alors C1 = 0 et C2 = 0 d’o` u: E[W ] = E[W1 ] = E[W2 ] =

1 ρ1 E[S1 ] + ρ2 E[S2 ] = 0.35 1−ρ 2

Dans le cas d’un service FCFS avec services constants, nous avons : E[R1 ] = E[W1 ] + E[S1 ] = 0.95 E[R2 ] = E[W2 ] + E[S2 ] = 0.65 E[R] = E[W ] + E[S] = 0.725 Services Exponentiels Pour une loi exponentielle, le coefficient de variation est 1, soit C1 = 1 et C2 = 1, d’o` u: E[W ] = E[W1 ] = E[W2 ] =

1 (ρ1 E[S1 ] + ρ2 E[S2 ]) = 0.70 1−ρ

41

Dans le cas d’un service FCFS avec services E[R1 ] = E[W1 ] + E[S1 ] E[R2 ] = E[W2 ] + E[S2 ] E[R] = E[W ] + E[S]

exponentiels, nous avons : = 1.3 = 1 = 1.075

Conclusion Dans le cas d’une discipline FCFS, le temps d’attente dans le buffer est le mˆeme pour toutes les classes. Dans le cas d’une discipline PS, cela lisse la variance des services.

Longueur des paquets IP 1- Soit λi , i = (1, 2, 3) les taux d’arriv´ees en octets par secondes de chacun des trois types de paquets. Le d´ebit d’arriv´ee dans la file de sortie du routeur A est donc : Λ = λ1 + λ2 + λ3 . Nous savons de plus que ces arriv´ees suivent une loi poissonnienne de taux Λ, puisque la somme de plusieurs flux poissonniens est poissonnienne. li Les arriv´ees sont donc poissonniennes, le temps de service Si est constant (Si = ), la discipline D est FCFS, la capacit´ee est infinie et la population est infinie. La discipline ´etant FCFS, le temps d’attente dans le buffer est le mˆeme pour toutes les classes (et donc en moyenne) et vaut, puisque le carr´e du coefficient de variation de ce service est 0 : 3

E[W ] = E[W1 ] = E[W2 ] = E[W3 ] =

1 X ρi S i 1 − ρ i=1 2

ρ est la charge du serveur, c’est a ` dire du lien. Il nous reste a` d´eterminer la somme 3 3 X X λi Si2 (car ρi = λi Si ) ρi S i = i=1

i=1

=

3 X i=1

= = = =

λi



li D

P3

i=1

ρi S i :

2

3 1 X λi (li )2 D2 i=1 3 Λ X λi (li )2 D2 i=1 Λ Λ E[L2 ] D2 Λ (E[L]2 + σ 2 [L]) D2

d’o` u: E[W ] = E[W1 ] = E[W2 ] = E[W3 ] =

Λ (E[L]2 + σ 2 [L]) 2D2 (1 − ρ)

Il reste alors ` a d´eterminer Λ. Nous pouvons d´eterminer le taux de service moyen : E[S] = d’o` u: ρ ρD Λ= = E[S] E[L]

E[L] D

D’o` u:   ρ σ 2 [L] ρ 2 2 (E[L] +σ [L]) = E[L] 1 + 2 E[W ] = E[W1 ] = E[W2 ] = E[W3 ] = 2DE[L](1 − ρ) 2D(1 − ρ) E [L] Le temps d’attente pass´e dans la file de sortie du routeur (attente + service) est donc :   σ 2 [L] li ρ E[L] 1+ 2 + ∀i ∈ [1, 3] E[Ri ] = E[W ] + Si = 1 − ρ 2D E [L] D

´ CHAPITRE 8. CORRIGES

42

et en moyenne : E[L] E[R] = E[W ] + E[S] = D



ρ E[L] 1 − ρ 2D

   σ 2 [L] 1+ 2 +1 E [L]

2- Applications num´eriques Les temps de services pour chaque classe et moyen sont : ES1 = 0.5 µs

S2 = 5 µs

S3 = 15 µs

Syst` eme multi-programm´ e` a m´ emoire virtuelle 1- Le fait que la file WAIT ne soit jamais vide implique qu’il y a toujours M = 4 clients dans le syst`eme central. L’´etude faite ici est ` a forte charge. Pour calculer le temps de r´eponse moyen R du syst`eme complet, on peut ´ecrire la formule de Little, appliqu´ee au r´eseau entier : (E[Z] + E[R])Λ = N On en d´eduit que (formule 1) : E[R] =

N − E[Z] = 21 s Λ

Pour calculer le temps de r´eponse moyen E[R′ ] du syst`eme central, on peut appliquer la formule de Little au syst`eme central : E[R′ ]Λ = M On en d´eduit que : E[R′ ] =

M = 10 s Λ

Le temps moyen E[W ] d’attente dans la file WAIT v´erifie l’´equation : E[R] = E[W ] + E[R′ ]. On en d´eduit que : E[W ] = E[R] − E[R′ ] = 11 s 2- Calculer les demandes totales de traitement au CPU et au disque, par interaction. Les demandes totales de traitement au disque et au CPU sont respectivement eDK E[SDK ] et eCP U E[SCP U ]. Pour une int´eraction, il y a eDK = 50 appels au disque. Nous avons donc : eDK E[SDK ] = 50 40 10−3 = 2 s Ne connaissant pas E[SCP U ] (on peut d´emontrer que eCP U est ´egal `a 51), nous ´ecrivons que eCP U E[SCP U ] = 2s : eCP U E[SCP U ] = 2 s Pour ces demandes totales au disque et au CPU, nous pouvons majorer le d´ebit de sortie du syst`eme central. En effet, le taux d’utilisation de chaque serveur est strictement inf´erieur `a 1. Il y a donc deux in´equations ` a v´erifier : Λ

=

Λ

=

UCP U eCP U E[SCP U ] UDK eDK E[SDK ]

<
0 nDK1 +nDK2 >0

=

=

X

X

UC DK1 DK2 (1 − ρUC )ρnUC (1 − ρDK1 )ρnDK1 (1 − ρDK2 )ρnDK2 nU C >0 nDK1 +nDK2 >0 X X DK1 DK2 UC (1 − ρDK1 )ρnDK1 (1 − ρDK2 )ρnDK2 (1 − ρUC )ρnUC

nDK1 +nDK2 >0

nU C >0

=

ρUC (1 − (1 − ρDK1 )(1 − ρDK2 ))

Taux de recouvrement UC/disque

= =

ρUC (ρDK1 + ρDK2 − ρDK1 ρDK2 ) 148 = 0, 656 = 65, 6% 225

R´ eseau local 1- On peut utiliser le th´eor`eme BCMP. 2- Comme ce qui nous int´eresse est le temps de r´eponse vu des terminaux et que ce temps ne d´epend pas du nombre moyen LT de clients vus les terminaux, on n’a pas besoin de calculer LT . Pour le calcul du d´ebit, on applique la loi de Little a l’ensemble et on divise K par le temps mis par un client pour parcourir l’ensemble du r´eseau entre deux passages successifs par un point o` u on compte le d´ebit global (on peut choisir le point de sortie des terminaux). Au d´enominateur de Λ, on ne compte donc le temps de r´eflexion Z que pour le client auquel on s’int´eresse donc on ne prend E[Z] qu’une fois. Le temps de r´eponse est alors dans la colonne 6 de l’algorithme de Reiser : c’est la somme des termes autres que E[Z]. La demande totale pour le CPU est : eCP U E[SCP U ] = 5 s La demande totale pour le disque 1 est : eDK1 E[SDK1 ] = 500 ∗ 10 ∗ 10−3 = 5 s La demande totale pour le disque 2 est : eDK2 E[SDK2 ] = 500 ∗ 10 ∗ 10−3 = 5 s K eT erm E[RT erm (K)] eCP U E[RCP U (K)] eDK1 E[RDK1 (K)] eDK2 E[RDK2 (K)] Λ(K) LCP U (K) LDK1 (K) LDK2 (K)

1 10 5 5 5 1/25 1/5 1/5 1/5

2 10 6 6 6 1/14 3/7 3/7 3/7

3 10 50/7 50/7 50/7 21/220 15/22 15/22 15/22

4 10 185/22 185/22 185/22 88/775 148/155 148/155 148/155

5 10 303/31 303/31 303/31 155/1219 1515/1219 1515/1219 1515/1219

Le temps de r´eponse E[R] du r´eseau vu des terminaux est donc de : E[R] = 3 ∗

13670 = 33, 64 s 1219

6 10 13670/1219 13670/1219 13670/1219 3657/26600 4101/2660 4101/2660 4101/2660

´ CHAPITRE 8. CORRIGES

50

R´ eseau sym´ etrique On veut utiliser une m´ethode d’agr´egation pour agr´eger les M stations en une seule. Les M stations sont exponentielles, de priorit´e PAPS, de capacit´es suppos´ees infinies. Il y a un seul point d’entr´ee et le routage est probabiliste. Il y a un seul point de sortie. On est donc dans les hypoth`eses du th´eor`eme BCMP. On ferme le r´eseau sur lui-mˆeme et on d´etermine le d´ebit du r´eseau ferm´e en fonction de N , M et E[S] `a l’aide de l’algorithme de Reiser. 1 Tous les ei Ri (K) sont ´egaux ` a M E[S]. Donc Li (n − 1) = n−1 u M . D’o` ei Ri (n) = On en d´eduit :

E[S] n−1 E[S] (1 + Li (n − 1)) = (1 + ) M M M

n n = e R (n) E[S](1 + i i i

Λ(n) = P

n−1 M )

=

nM E[S](M + n − 1)

Le taux du serveur ´equivalent est donc : nM E[S](M + n − 1)

µ(n) =

Agr´ egation de chaˆınes de Markov 1- La chaˆıne de Markov est ` a temps discret. La somme des probabilit´es sortantes de chaque ´etat est donc ´egale ` a 1. D’o` u: 1 7 7 P01 = , P11 = , P22 = 4 8 8 2- Pour d´eterminer les probabilit´es des trois ´etats, on peut ´ecrire π = πP o` u P est la matrice de transition et ´ecrire la condition de normalisation. 1 Nous d´eterminons ici les probabilit´es en effectuant deux coupes qui permettent d’´ecrire π(2) = 8 1 1 5 π(0) d’une part, et π(1) = π(0) d’autre part. 8 8 4 La condition de normalisation, π(0) + π(1) + π(2) = 1 permet alors de conclure : π(0) =

1 1 5 , π(1) = , π(2) = 8 4 8

3- Calcul de P1A Nous avons n´ecessairement : P1A = 1 − P11 =

1 8

Calcul de PA1 En effectuant une coupe entre les ´etats A et 1, nous avons : π(A)PA1 = π(1)P1A d’o` u: PA1 =

1 24

Remarque : la transition de A vers 1 ne se fait pas pour tous ceux qui sont dans A mais seulement parmi ceux-ci pour ceux qui sont dans 0. Donc on trouve : PA1

= = =

Calcul de PAA

P01 ∗ P [O/A] π(0) P01 π(0) + π(2) 1 81 4 18 + 85

51

PAA = 1 − PA1 =

23 24

Rappel du th´ eor` eme de Kemeny ”Une condition n´ecessaire et suffisante pour que l’agr´egation d’une chaˆıne de Markov soit exacte pour la partition A = A1 , ..., As est que pour toute paire d’agr´egats (Ai , Aj ), pkAj ait la mˆeme valeur pour tout k dans Ai . Ces valeurs communes pˆij sont les valeurs de la matrice de transition de la chaˆıne agr´eg´ee.” J.G. Kemeny Cette agr´egation n’est donc pas exacte car P01 6= P21 .

Agr´ egation de files d’attente Pour les r´eseaux de type Gordon et Newell, la m´ethode d’agr´egation est une m´ethode exacte. 1- On ´etudie l’ensemble constitu´e par les files 2 et 3 en refermant cet ensemble sur lui-mˆeme. Pour ce sous-r´eseau, on est de nouveau dans les conditions d’application du th´eor`eme de Gordon et Newell (Files PAPS ` a un serveur exponentiel de capacit´es infinies avec routages probabilistes). Remarques : 1) Comme p12 + p13 = 1, on n’a pas besoin de recalculer les probabilit´es d’aller dans les files 2 et 3. 2) Le point d’observation est forc´ement dans le rebouclage. Deux m´ethodes sont possibles pour d´eterminer le d´ebit Λ(n). Calcul direct des probabilit´ es Entre deux passages dans le rebouclage : e3 = p13 et e2 = p12 . D’o` u e2 E[S2 ] = e3 E[S3 ] = 20. Les ´etats possibles du syst`emes sont (n2 , n3 ) avec n2 + n3 = n : P (n2 , n3 ) = C(e2 E[S2 ])n2 (e3 E[S3 ])n3 = C(20)n2 (20)n3 = C(20)n Toutes ces probabilit´es sont donc ´egales et il y a n + 1 probabilit´es. d’o` u : P (n2 , n3 ) = Il suffit de d´eterminer le taux d’utilisation U2 du serveur 2 pour d´eterminer Λ(n) : Λ(n) =

1 . n+1

1 − P (n, 0) n U2 = = e2 E[S2 ] e2 E[S2 ] 20(n + 1)

Algorithme de Reiser (MVA) Comme e2 E[S2 ] = e3 E[S3 ], les nombres moyens de clients dans les deux files sont identiques : n−1 n−1 et L3 (n − 1) = . En appliquant le th´eor`eme de Sevick-Mitrani : L2 (n − 1) = 2 2   n−1 e2 R2 (n) = e2 E[S2 ](1 + L2 (n − 1)) = 20 1 + , d’o` u: 2   n−1 = 20(n + 1) R = e2 R2 (n) + e3 R3 (n) = 2 ∗ 20 1 + 2 On a donc : Λ(n) =

n 20(n + 1)

2- On remplace l’ensemble file 2 et file 3 par une seule file `a taux de service µ(n) d´ependant du nombre de clients dans la file avec µ(n) = Λ(n). Quelque soit le point d’observation, on a e1 = 1 et e = 1 o` u e est le nombre de passages dans la file composite. Nous sommes encore dans les conditions d’application de Gordon et Newell.  ni ni Y ei ei devient . Pour les files dont le taux de service d´epend de l’´etat, l’expression µi µ (j) j=1 i

´ CHAPITRE 8. CORRIGES

52

Les ´etats possibles du syst`eme sont (0, K), (1, K − 1), . . ., (K, 0), avec :   e e e K−n ∀n ∈ [0, K] P (K − n, n) = C.(e1 E[S1 ]) ... µ(1) µ(2) µ(n) On a e1 E[S1 ] = 10 et e = 1 d’o` u: ∀n ∈ [0, K] P (K − n, n) = C.10K−n .20n .(n + 1) Posons C ′ = 10k , soit ∀n ∈ [0, K] P (K − n, n) = C ′ .2n .(n + 1). En utilisant l’´equation de normalisation, nous obtenons : K X

P (k − n, n) = 1 = C ′

n=0

K X

2n .(n + 1)

n=0

1 . 1 + K2K+1 On en d´eduit le taux d’utilisation du serveur 1 :

Le calcul de la seconde somme conduit ` a : C′ =

U1 (K) = 1 − P (0, K) = 1 −

(K + 1)2K 1 + (K − 1)2K = K+1 1 + K2 1 + K2K+1

On peut remarquer que le num´erateur ` a l’´etape k est ´egal au d´enominateur `a l’´etape k − 1. Les applications num´eriques donnent : U1 (1) =

1 2 17 49 , U1 (2) = , U1 (3) = , U1 (4) = 5 17 49 129

Autre m´ ethode On aurait pu appliquer directement Gordon et Newell `a l’ensemble du r´eseau. Le point d’observation est choisi dans le rebouclage. On a alors e1 = 1, e2 = p12 et e3 = p13 . On a alors e1 E[S1 ] = 10, e2 E[S2 ] = 20 et e3 E[S3 ] = 20. Liste des ´etats possibles et calcul des probabilit´es :  P (0, 0, K) = C.100 .200 .20K = C.100 .20K    P (0, 1, K − 1) = C.100 .201 .20K−1 = C.100 .20K  (K + 1) ´etats .. .. ..  . . .    P (0, K, 0) = C.100 .20K .200 = C.100 .20K  P (1, 0, K − 1) = C.101 .200 .20K−1 = C.101 .20K−1    P (1, 1, K − 2) = C.101 .201 .20K−2 = C.100 .20K−1  K ´etats .. .. ..  . . .    P (1, K − 1, 0) = C.101 .20K−1 .200 = C.101 .20K−1 .. .

P (K, 0, 0) =

.. .

C.10K .200 .200

.. .

=

C.10K .200

en posant C ′ = C.10K , on a encore une fois : K X n X

P (k − n, n1 , n − n1 ) = 1 = C ′

n=0 n1 =0 ′

1 ´etats

(n + 1).2n

n=0

On retrouverait C et :

U1 (K) = 1 −

K X



K X

n=0

P (0, n, K − n) = 1 − (K + 1)C ′ 2K