Master 1 IF, ENS de Lyon Évaluation de performance mercredi 23 novembre TD 9 :
Master 1 IF, ENS de Lyon Évaluation de performance mercredi 23 novembre TD 9 : Analyse de files d’attente lionel.rieg@ens-lyon.fr Exercice 1 (Distribution du temps d’attente) On considère une file d’attente M/M/1 de taux d’utilisation ρ < 1. On rappelle que sous l’hypothèse de régime permanent, on a les résultats suivants (vu au TD précédent) : – la distribution du nombre de personnes dans le système suit une loi géométrique de paramètre ρ (décalée de 1 car elle peut prendre la valeur 0) ; – l’espérance du nombre de personnes dans le système est L = ρ 1−ρ ; – l’espérance du nombre de personnes en attente est Lq = L −(1 −p0) = ρ2 1−ρ ; – pour obtenir la distribution du temps d’attente, il nous faut choisir une politique de service, ici PAPS ; – dans le cas d’arrivée Poissonienne (c’est faux sinon), la probabilité qn qu’un client arrivant dans le système trouve n personnes devant lui est égale à la probabilité pn qu’il y ait n personnes dans le système dans l’absolu ; – la variable aléatoire Tq représentant le temps d’attente est à densité pour t > 0 et possède un point de masse en t = 0 ; – sa fonction de répartition Wq(t) = FTq(t) vérifie Wq(0) = q0 = 1 −ρ. Le temps de service de n clients suit une distribution d’Erlang de paramètres n (paramètre de forme) et µ (paramètre d’intensité) dont la fonction de densité est E(n, µ, x) = µnxn−1e−µx (n −1)! . 4. En utilisant la formule des probabilités totales, donner une expression pour Wq(t). 5. Donner l’espérance Wq de Tq. 6. Adapter les deux questions précédentes pour traiter le cas de T, le temps de séjour total dans le système. 7. Quelle relation y a-t-il entre Lq et Wq d’une part, et L et W d’autre part ? Exercice 2 (Serveur et miroir) On dispose de deux serveurs Web : un serveur principal et un serveur miroir. Les requêtes arrivent à un routeur qui doit essayer de répartir le travail entre le serveur principal ou son miroir, qui est supposé moins performant. Le routeur ne connaissant pas la charge respectives des deux serveurs, il décide d’envoyer chaque requête au serveur principal avec probabilité p ou au serveur miroir avec probabilité 1 −p. On cherche à optimiser le choix de p. On suppose que les arrivées suivent une loi de Poisson de paramètre λ. Les temps de service des serveurs sont exponentiels de paramètres respectifs µ pour le serveur principal et ν pour le miroir. 1. Montrer que les arrivées des paquets dans les files du serveur principal et de son miroir sont des processus de Poisson de paramètres respectifs pλ et (1 −p)λ. 2. Quelles sont les conditions de stabilité du système ? 3. Calculer le nombre de requêtes dans le serveur principal et dans le miroir à l’état stationnaire. 4. Donnez le temps de réponse moyen dans le système global. 5. Déterminez la valeur optimale de p. 1/5 Master 1 IF, ENS de Lyon Évaluation de performance mercredi 23 novembre Exercice 3 (Comparaison de trois modèles de serveur) On souhaite comparer les trois architectures suivantes de file d’attente : λ 2µ λ µ µ λ µ µ 1/2 1/2 1. Intuitivement, quelle configuration semble la meilleure ? Pour chacune des trois configurations : 2. Donnez sa condition de stabilité. 3. Écrire son générateur infinitésimal (en précisant les cas limites). 4. Calculer le nombre moyen de clients dans le système. 5. En déduire le temps moyen de réponse. Où se trouve la différence entre les différentes configurations ? Laquelle préférer ? Exercice 4 (Dimensionnement de buffer) On considère un réseau d’entreprise composé de deux LANs, l’un constituant le réseau de production (LAN 1) et l’autre hébergeant la base de données de l’entreprise (LAN 2). Ces deux sous-réseaux sont connectés par un lien à 1, 5 Mbits/seconde. On suppose que : – Les requêtes provenant du réseau de production pour la base de données arrivent au routeur d’interconnexion selon un processus de Poisson d’intensité égale à 15 requêtes par seconde. – Les documents hébergés par la base de données ont une taille aléatoire de distribution exponentielle, de moyenne 100 kbits. – Les délais de propagation et de traitement sont négligés, de sorte que les temps de transferts de ces documents entre les deux sites sont proportionnels à la taille des documents demandés. – Les temps de traitement par la base de données sont négligés. – La taille des requêtes est négligeable devant la taille des documents demandés. 1. En supposant les buffers de taille infinie, montrer que le processus d’arrivée des documents au routeur d’interconnexion du LAN 2 vers le LAN 1 peut être modélisé par une file M/M/1. Calculer ses taux d’arrivée et de service. 2. Le système est-il stable ? Décrivez l’évolution asymptotique du temps de réponse. 3. On suppose que l’on augmente le débit du lien d’interconnexion a 3 Mbits/seconde. Calculer la taille du buffer du routeur (mise en attente des requêtes) afin de garantir une probabilité de perte inférieure à 10−3. 2/5 Master 1 IF, ENS de Lyon Évaluation de performance mercredi 23 novembre Solutions ▶Exercice 1 4. Wq(t) = P Tq ⩽t = Wq(0) + +∞ X n=1 pn · P les client devant servis en moins de t n client présents à l’arrivée dans la file = 1 −ρ + +∞ X n=1 (1 −ρ)ρn · Z t 0 µnxn−1e−µx (n −1)! dx = 1 −ρ + (1 −ρ)λ +∞ X n=1 Z t 0 e−µx (λx)n−1 (n −1)! dx = 1 −ρ + (1 −ρ)λ Z t 0 e−µx +∞ X n=1 (λx)n−1 (n −1)! dx = 1 −ρ + (1 −ρ)λ Z t 0 e−µxeλx dx = 1 −ρ + (1 −ρ)λ λ −µ h e(λ−µ)xit 0 = 1 −ρ + (1 −ρ)λ −µ(1 −ρ) e(λ−µ)t −1 = 1 −ρ −ρ e(λ−µ)t −1 = 1 −ρe(λ−µ)t 5. On a fTq(t) = W′ q(t) = −ρ(λ −µ)e(λ−µ)t, d’où Wq = E Tq = Z +∞ 0 t · (−ρ)(λ −µ)e(λ−µ)t dt = h −ρte(λ−µ)ti+∞ 0 + Z +∞ 0 ρe(λ−µ)t dt = 0 + ρ "e(λ−µ)t λ −µ #+∞ 0 = ρ µ −λ. 6. Il faudrait compter n + 1 temps de service lorsqu’il y a n personnes à l’arrivée d’un client. Pour cela, on supprime le premier terme (T est une variable à densité), comme pn−1 = 1 ρ pn, cela revient à diviser par ρ le deuxième terme de la somme : W(t) = P(T ⩽t) = 1 ρ · (−ρ) e(λ−µ)t −1 = 1 −e(λ−µ)t on reconnaît là la fonction de répartition d’une loi exponentielle de paramètre µ −λ, d’où W = 1 µ−λ. 7. On découvre la loi de Little : L = λW et Lq = λWq qui est en fait beaucoup plus générale. ▶Exercice 2 1. On va calculer les fonctions de répartition des temps inter-arrivées. Entre deux paquets successifs arrivés dans la file secondaire, il peut y avoir un nombre arbitraire de paquets arrivés dans la file principale. En utilisant la formule des probabilités totales et le fait que l’arrivée de n paquets suit une loi de Erlang de paramètres n et λ, on a, en notant A l’événement « le ne paquet est le premier qui va dans la bonne file » : 3/5 Master 1 IF, ENS de Lyon Évaluation de performance mercredi 23 novembre P(Tn+1 −Tn ⩽t) = +∞ X n=1 P(A) · P n paquets arrivés en moins de t A = +∞ X n=1 P(Geom(p) = n) · Z t 0 E(n, λ, x) dx = +∞ X n=1 (1 −p)n−1p Z t 0 xn−1λne−λx (n −1)! dx = Z t 0 pe−λx +∞ X n=1 (1 −p)n−1 xn−1λn (n −1)! dx = Z t 0 pλe−λx +∞ X n=1 ((1 −p)λx)n−1 (n −1)! dx = Z t 0 pλe−λxe(1−p)λx dx = Z t 0 pλe−pλx dx = 1 −e−pλt On reconnaît la fonction de répartition d’une loi exponentielle de paramètre pλ, donc les temps d’arrivées dans la file principale suivent un processus de Poisson de paramètre pλ. Par symétrie, les temps d’arrivées dans la file secondaire suivent un processus de Poisson de paramètre (1 −p)λ. On peut aussi procéder différemment en comptant le nombre de paquets arrivés dans l’intervalle [0, t[ et en disant qu’au moins l’un d’entre eux doit aller dans la bonne file. Notons cette fois-ci B l’événement « n paquets arrivent dans l’intervalle [0, t[ ». P(Tn+1 −Tn ⩽t) = X n⩾1 P(B) · P au moins un paquet dans la bonne file B = X n⩾1 P(P(λt) = n) · P(B(n, p) ⩾1) = X n⩾1 e−λt (λt)n n! · 1 −(1 −p)n = X n⩾1 e−λt (λt)n n! − X n⩾1 e−λt ((1 −p)λt)n n! = 1 −e−λt −e−λt e(1−p)λt −1 = 1 −e−pλt 2. Les deux conditions sont alors pλ < µ et (1 uploads/s1/ corrige-td09.pdf
Documents similaires
-
25
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Oct 11, 2021
- Catégorie Administration
- Langue French
- Taille du fichier 0.0938MB