1
Université Mohammed V de Rabat
Faculté des Sciences, Département d’Informatique
Module performances des réseaux
TD Chaı̂nes de Markov et files d’attentes
Exercice 1 On étudie une file d’attente de capacité infinie avec des arrivées suivant un processus
de Poisson. On dispose initialement d’un serveur unique. On cherche à savoir si l’ajout d’un
nouveau serveur améliorerait le temps d’attente moyen des clients. il y aura donc deux serveurs
en activité pour la même file d’attente.
• Hypothèse 1 : le nouveau serveur est plus lent que le serveur initial.
• Hypothèse 2 : les clients ne savent pas qui est le serveur rapide. Si les deux serveurs sont
disponibles, chaque serveur a la probabilité 0.5 d’être choisi par le client. Dès qu’un serveur
est disponible, il est utilisé par le premier client en attente.
• Hypothèse 3 : les services sont exponentiels d’intensité µ1 pour le premier serveur (rapide)
et µ2 pour le second (lent).
1. Soit Xt le nombre de clients dans la file à l’instant t. Est ce que Xt est une chaı̂ne de
Markov? Sinon proposez une chaı̂ne décrivant le système.
2. Représentez les états et les transitions de la chaı̂ne.
3. Ecrivez les équations de balance globale du système. Résoudre ces équations.
4. Calculez le nombre moyen de clients et le temps moyen de séjour dans la file.
5. Comparer ce temps avec celui du système initial. Est ce qu’il est intéressant pour les clients
d’ajouter un serveur lent avec les hypothèses ci-dessus.
Exercice 2 On considère le mécanisme de Leaky bucket qui permet de réguler l’accès à un
réseau. Dans cet exercice, ce mécanisme est modélisé par deux files d’attente : la file des paquets
qui est infinie et la file des jetons qui est finie de capacité B = 3. Pour effectuer un service, il faut
avoir au moins un paquet et un jeton. Les paquets arrivent selon un processus de poisson de taux
λ, les jetons arrivent selon un processus de poisson de taux γ et les services sont exponentiels de
taux µ. Modélisez ce système par une chaı̂ne de Markov, puis donnez le graphe de la chaı̂ne.
2
Exercice 3 On considère une file d’attente de capacité B avec des clients servis en ordre FIFO.
Les arrivées se produisent selon un processus de Poisson de taux λ. La durée de service est
exponetielle de taux µ. Si un client arrive lorsque la file est pleine, il est perdu. D’autre part, le
serveur peut tomber en panne. La durée entre deux pannes est exponentielle de paramètre α. La
durée d’une panne est exponentielle de paramètre β.
1. Modélisez ce système par une chaı̂ne de Markov.
2. Représentez les états de cette chaı̂ne et les transitions entre états.
3. Ecrivez les équations de balance globale pour les états où le nombre de clients dans la file est
égale à 0 ou 1.
Dans la suite, on suppose que l’effet d’une panne est de vider complètement la file. On
suppose de plus que les clients qui arrivent durant la panne sont perdus.
4. Représentez à nouveau les états de cette chaı̂ne et les transitions entre états.
5. Calculez la distribution stationnaire de cette chaı̂ne pour B=2 (on suppose que
α = β = λ = µ = 1/2).
6. Exprimez la probabilité de perte en fonction des probabilités stationnaires puis la calculer.
7. Exprimez le nombre moyen de clients dans cette file en fonction des probabilités
stationnaires puis le calculer.
8. Calculez le temps moyen de réponse de la file.
9. On suppose maintenant que la file à une capacité infinie et que beta est infini (réparation
instantanée), représentez les états et les transitions de cette nouvelle chaı̂ne.
Exercice 4 On étudie une file d’attente de capacité infinie avec des clients servis en ordre FIFO
et des arrivées suivant un processus de Poisson de taux λ. Il y a deux serveurs S1 et S2. Les
services sont exponentiels de taux µ1 pour le premier serveur et µ2 pour le second. On suppose
que les deux serveurs sont en série. En fait, le service comporte deux phases, le client passe
d’abord dans le serveur S1 et quand son traitement est terminé, il passe dans le serveur S2.
On suppose que le premier client en attente ne peut commencer son service dans S1 que lorsque le
client précédent (le client en service) a fini son service dans S2.
1. Quelles informations doit-on stocker dans un état pour modéliser ce système par une chaı̂ne
de Markov?
2. Pour la chaı̂ne que vous proposez, représentez les états et les taux de transitions entre états.
3. Ecrivez les équations de balance globale pour les états avec un nombre de clients dans le
système inférieur ou égal à deux.
3
4. On autorise maintenant le premier client en attente à rentrer dans S1 dès que le client
précédent passe dans S2, mais si le client en S1 a terminé avant que celui en S2 ait
terminé, il reste dans S1 jusqu’à ce que le client en S2 parte.
Proposez une chaı̂ne de Markov décrivant ce nouveau système et donnez le graphe de la
chaı̂ne avec les états et les taux de transition.
Exercice 5 On considère un réseau à commutaion de paquets constitué de quatre noeuds et de
cinq liaisons(voir figure).
2
λ1
Terminaux λ2 1 4
λ3
3
Trois terminaux engendrent des trafics de taux respectifs λ1 = 0.5, λ2 = 1 et λ3 = 1.5
paquets/seconde. Le noeud 4 est le noeud de destination de tous les paquets. Lorsqu’un paquet
arrive au niveau d’un noeud ce dernier doit décider de la liaison vers laquelle il va diriger le
paquet. Le paquet se place alors dans un buffer d’attente spécifique à la liaison choisie. il y’a dans
chaque noeud de commutation autant de buffers d’attente que de liaisons de sortie. Lorsqu’une
liaison est disponible le premier paquet en attente de transmission sur cette liaison est émis. Un
seul message peut circuler sur chaque liaison. Le temps moyen d’émission d’un paquet est de 1/6
seconde.
On s’intéresse aux deux configurations de routage suivantes :
a) Tous les paquets suivent le chemin 1 → 2 → 3 → 4
b) Le routage des paquets est aléatoire avec les probabilités de routage suivantes :
p12 = 1/3, p13 = 2/3, p23 = 3/4, p24 = 1/4, p34 = 1
1. Modélisez ce réseau par un réseau de files d’attente ouvert dans les deux configurations de
routage a et b ?
2. Calculez les taux de visite des stations de ces deux réseaux de files d’attente.
3. Sous quelles conditions ces réseaux sont des réseaux de Jackson?
4. La condition de stabilité est-elle satisfaite dans les deux cas ?
5. Sous toutes ces conditions et dans les deux cas de routage donnez le temps moyen mis par
un paquet pour traverser le réseau.