Answers Inf7345 Homework

Multiplexage (5 points) Comparer les performances des systèmes suivants : Une file M/M/2 et deux files M/M/1 1. Utilisation de chaque système : 2 files M/M/1 :

λ 2µ

1 file M/M/2 :

2. Débit du système : Si 2 files M/M/1 : débit =

λ 2µ

(λ < 2 µ )

λ

1 file M/M/2 : débit =

3. Débit maximum : 2 files M/M/1 : débit Max =

λ

2 µ 1 file M/M/2 : débit Max = 2 µ

4. Temps de réponse

Temps de Réponse (R) = Temps d’attente (W) + Temps de Service (S)

Pour 2 files M/M/1 : Soit R qui dénote le temps de réponse, d’après la loi de Little on a pour chaque M/M/1 :

E [R1 ] = E [N ] λ =

2 λ temps − de − service 1µ avec ρ = donc E [R1 ] = = 2µ − λ prob − serveur − idle 1 − ρ 2µ

Pour 1 file M/M/2

E [R2 ] = E [N ] λ En utilisant E [N] pour m=2 sa donne

En comparant on trouve que :

E [R1 ] =

2 4 µ + 2λ = > E [R2 ] 2 µ − λ 4 µ 2 − λ2

E [S1 ] = E [S 2 ] =

5. Temps de service

4µ λ 2ρ avec ρ = donc E [R2 ] = 2 4 µ 2 − λ2 2µ 1− ρ

1

µ

6. Temps d’attente Pour 2 files M/M/1 :

E [W1 ] = E [R1 ] − E [S1 ] =

λ 2 1 − = 2 2 µ − λµ 2µ − λ µ

Pour 1 file M/M/2

E [W2 ] = E [R2 ] − E [S 2 ] =

E [W1 ] =

λ 2 µ 2 − λµ

=

λ2 4µ 1 − = en comparant on trouve : 4 µ 3 − λ2 µ 4 µ 2 − λ2 µ

2 µλ + λ2 > E [W2 ] 4 µ 3 − λ2 µ

7. Nombre de clients dans le système avec

E [N 1 ] =

ρ 1− ρ

et

E [N 2 ] =

ρ=

λ 2µ

ρ ρ + ρ2 2ρ E N > E [N 2 ] = = [ ] en comparant on trouve : 1 1− ρ 1− ρ 2 1− ρ 2 2

Protocole avec 2 phases (7 points) On considère un protocole d’accès à un réseau se passant en 2 phases. Une première phase consiste à mettre en forme le message (calcul de l’entête, encapsulation,...), la deuxième phase émet le message sur le réseau. Lorsque le message est émis on reprend la phase 1 avec un nouveau message. On modélise ce protocole par une file d’attente avec 2 serveurs en série.

Les données du problème sont les suivantes : - débit d’arrivée des messages produits par l’utilisateur : Ȝ ; - temps moyen de traitement du message en local : s ; - temps moyen d’émission du message r. Pour les applications numériques on prendra s = 2 ms et r = 8 ms. Dans chaque question on représentera les courbes avec ces données. 1 - A quelle condition ce système d’attente est-il stable ? Dans ce cas, donner le taux d’utilisation de chaque serveur. Réponse Un système est dit stable si : Taux d’arrivé < taux de service autrement dit :

λ<µ.

D’après l’énoncé, le système traite un message toutes les 10 ms c.à.d

µ=

1 = 100 messages par 10ms

seconde, donc λ < 100 messages par seconde. Le taux d’utilisation de s : Le serveur s traite 1 message toutes les 2 ms donc

µs =

λ 1 = 500 messages par seconde donc ρ s = . 500 2ms

µr =

λ 1 = 125 messages par seconde donc ρ r = . 125 8ms

Le taux d’utilisation de r : Le serveur r traite 1 message toutes les 8 ms donc

2 - En modélisant ce système par une M/M/1, on précisera les approximations faites, calculer, en fonction de Ȝ, le temps de réponse moyen des messages. Réponse

1

Pour une M/M/1 le temps de réponse moyen est

E[ R ] =

1 1 µ = = 1 − ρ µ − λ 100 − λ

3

Fig1 : Temps de Réponse Moyen M/M/1 Dans la suite de l’exercice on supposera les temps de services sur les 2 serveurs de loi exponentielle. 3 - Construire une chaîne de Markov en temps continu décrivant la dynamique du système. Réponse

λ

…

λ

k-1

k

k+1

µ

…

µ

4 - En utilisant les résultats obtenus pour la file M/GI/1 donner le nombre moyen de clients dans le système à l’état stationnaire et calculer en fonction de Ȝ le temps de réponse moyen des messages. Réponse Le nombre moyen de clients dans le système pour une file M/GI/1 est donné par la formule suivante :

E[ N ] = ρ +

λ2 E[σ 2 ] 2 × (1 − ρ )

avec

E[σ 2 ] =

2

µ

2

donc

E[ N ] =

ρ 1− ρ

=

λ 100 − λ

4

Fig2 : Nombre moyen de clients M/GI/1

Le temps de réponse moyen des messages pour une file M/GI/1 est donné par la formule suivante :

E[ R] =

1

µ

+

λ × E[σ 2 ] 2 × (1 − ρ )

avec

E[σ 2 ] =

2

µ2

donc E[ R] =

1

µ

+

1 1 λ µ2 = = (1 − ρ ) µ − λ 100 − λ

Fig3 : Temps de réponse moyen M/GI/1

On décide d’introduire un buffer entre les deux serveurs et donc la préparation d’un message et l’envoi d’un autre message peut se faire de manière concurrente.

5

5 - Reprendre l’étude faite ci-dessus en montrant l’amélioration obtenue sur le temps de réponse moyen. Réponse En introduisant un buffer intermédiaire le système est devenu un réseau de file d’attente. Dans notre cas, le taux de visite ei = 1 , ce qui nous donne λi = ei λ Ÿ λi = λ avec i = s, r

[ ]

Pour la condition de stabilité, on doit toujours vérifier que

­λ < µ s ­λ < 500 λi < µ i d’où ® ⇔® ¯λ < 125 ¯λ < µ r

si on ne respecte

pas cette condition de stabilité, on ne pourra pas poursuivre l’étude. Le nombre moyen de clients dans le système est donné par la formule suivante :

Q=

¦Q

i

i =r ,s

avec

Qi =

ρi λ = 1 − ρi µi − λ λ

Pour le serveur s on aura

Qs =

500 − λ

et pour r on aura

Qr =

λ 125 − λ

donc

Q=

λ 500 − λ

+

λ 125 − λ

Fig4 : Nombre moyen de clients pour le serveur s

Fig5 : Nombre moyen de clients pour le serveur r

6

Fig6 : Nombre moyen de clients dans le système

λ Le temps moyen de réponse est donné par la formule suivante :

R=

Q

λ

= 500 − λ

+

λ 125 − λ

λ

Fig7 : Temps moyen de réponse du système L’amélioration est constatée au niveau du lambda qui est devenu supérieur à 100, donc le système peut servir plus de client. 6 - En supposant la capacité du buffer intermédiaire finie égale à C, calculer la probabilité de perte de message par manque de place. Réponse Au niveau du serveur r, la capacité du buffer intermédiaire est égale à C, donc on peut le modéliser comme une M/M/1/C. La probabilité de perte de message par manque de place est égale à la probabilité que le buffer intermédiaire soit plein :

7

­ 1− ρ C °°1 − ρ C +1 × ρ pour _ λ ≠ µ P=® ° 1 pour _ λ = µ °¯ C + 1 7 - Généraliser au cas d’un système de capacité mémoire finie. Comment répartir cet espace mémoire entre le buffer d’entrée et le buffer intermédiaire. Réponse Pour répartir cet espace mémoire entre les deux buffers, il faut calculer le ratio entre le nombre moyen de clients dans le système

λ

125 − λ Qs = 500 − λ = 500 − λ Qr λ 125 − λ

Contrôle d’accès (7 points) Un fournisseur d'accès a un réseau désire contrôler le débit d'entrée de son client sur le réseau. Pour cela il met en place un mécanisme qui délivre un jeton permettant l'entrée des paquets du client sur le réseau. On suppose que tous les paquets du client sont de même taille (cf. réseaux ATM). Les paramètres que le fournisseur d'accès doit régler sont d'une part - la temporisation D des jetons ; un jeton arrive à la file des jetons toutes les D unités de temps. - la taille K de la file des jetons. 1- Quel est le débit crête offert par le fournisseur d'accès ? Le client peut-il réaliser ce débit crête ? Quel est le rôle de la capacité K ? En quoi améliore-t-elle la qualité de service offerte au client ? Réponse Le débit crête est

D=

1 1 ⇔ PCR = , le client peut réaliser ce débit et le rôle de K est de définir le burst. PCR D

En définissant le burst, le fournisseur d’accès garantie une meilleure qualité de service, ce QoS est un débit très proche du débit crête, car en utilisant le contrôle d’accès le fournisseur optimise l’utilisation des ressources. On suppose que le client émet des paquets avec le débit Ȝ. Le processus d'arrivée des paquets sera supposé Poissonien homogène. Dans un premier temps on supposera la capacité de la file de jeton K = 1.

2 – Calculer les performances de ce système, c'est à dire le débit effectif Ȝe d'émission du client sur le réseau, le taux de rejet des paquets du client et le taux de rejet de jetons.

8

Réponse D’après l’énoncé, le système peut être modélisée comme une M/M/1/K avec K=1 on aura les résultats suivants : Débit effectif :

λe =

1− ρ K 1− ρ ×λ = ×λ K +1 1− ρ 1− ρ 2

Taux de rejet des paquets du client se produit quand la file des jetons est vide :

TRe jet _ Client =

1− ρ 1− ρ = K +1 1− ρ 1− ρ2

Taux de rejet des jetons se produit quand la file est pleine :

TRe jet _ Jetons =

ρ − ρ2 ρ − ρ K +1 × = ×µ µ 1 − ρ K +1 1− ρ2

On suppose maintenant que la capacité de la file de jetons est 3 Réponse Débit effectif :

λe =

1− ρ K 1− ρ3 × = ×λ λ 1 − ρ K +1 1− ρ4

Taux de rejet des paquets du client se produit quand la file des jetons est vide :

TRe jet _ Client =

1− ρ 1− ρ = K +1 1− ρ 1− ρ2

Taux de rejet des jetons se produit quand la file est pleine :

TRe jet _ Jetons =

ρ − ρ4 ρ − ρ K +1 × = ×µ µ 1 − ρ K +1 1− ρ4

3 - Comment négocier la temporisation des jetons de manière à assurer un débit d'entrée effectif Ȝe sur le réseau. 4 - Généraliser cette étude à une capacité K quelconque. A votre avis, comment doit se faire la négociation entre l'opérateur du réseau et le client.

Performances d’un routage probabiliste (6 points) Les messages entre la station émettrice et la station réceptrice peuvent transiter par 2 routes différentes, on notera Ȝ le débit global des messages entre les 2 stations. Le temps de transit du message sur la route i est de moyenne

1

µi

(i=1,2)

Le routeur dont on dispose est élémentaire (il ne possède pas de mémoire locale, ni de connaissance sur la charge des différentes routes), il est juste capable de tirer à pile ou face avec une probabilité p et 1-p s’il envoie respectivement le message sur la route 1 ou sur la route 2.

9

On se propose donc de calculer les performances de ce réseau et d’optimiser le temps moyen de réponse des messages. 1- Donner rapidement un modèle Markovien en temps continu correspondant à ce système. Quelle est la nature du processus d’arrivée de clients dans la file correspondant à la route 1, à la route 2? Quelle est la condition de stabilité du réseau? Réponse Le modèle Markovien correspondant à ce système est le suivant :

(route1, route2) pλ

(1,0)

(1 − p )λ (0,1)

La nature du processus d’arrivée est poissonien, et la condition de stabilité est réalisée par le système suivant :

­ pλ < µ1 ® ¯(1 − p )λ < µ 2 2- Calculer la loi du nombre de message en transit sur la route 1 (resp. 2). Donner la loi du nombre total de message en transit. Réponse Nombre de message en transit sur la route 1 et 2:

pλ ρi pλ µ1 Q1 = = = 1 − ρ i 1 − pλ µ1 − pλ µ1

(1 − p )λ ρi (1 − p )λ µ2 = Q2 = = 1 − ρ i 1 − (1 − p )λ µ 2 − (1 − p)λ µ 2

Le nombre total de message en transit est :

Q=

Q ¦ { }

i

i = 1, 2

=

pλ (1 − p )λ + µ1 − pλ µ 2 − (1 − p)λ

3- Donner la loi du temps de réponse d’un message transitant par la route 1 (resp. 2) (se servir d’un résultat vu en cours sur le temps de réponse dans une file). Calculer la densité du temps de réponse d’un message en fonction de p

10

Réponse Le temps de réponse sur la route 1 et 2 est :

R1 =

1 1 = µ1 − λ1 µ1 − pλ

R2 =

1 1 = µ 2 − λ2 µ 2 − (1 − p )λ

La densité du temps de réponse d’un message est :

R=

Q

λ

=

1 1 + µ1 − pλ µ 2 − (1 − p )λ

λ

4- Pour les paramètres suivants tracer le temps moyen de réponse en fonction de p. Ȝ=1 µ1=1.2 µ2=1. Réponse Pour les valeurs données par l’énoncé on aura :

R=

1 1 + µ1 − pλ µ 2 − (1 − p )λ

λ

=

1 1 + 1 .2 − p p

Fig8 : Temps moyen de réponse 5- Donner la valeur de p optimisant le réseau. Réponse La valeur de p optimisant le réseau est équivalent au temps de réponse le plus faible donc, d’après la courbe on aura p = 0.6 6- Faire une conclusion synthétique sur ce type de routage. Réponse D’après les résultats obtenus, ce type de routage présente un temps moyen de réponse assez élevé, chose qui n’est pas très apprécié lors de l’étude des performances du routage probabiliste.

11