Polycopie SEP 2021-Converti [PDF]

Zitiervorschau

Support de cours matière

Simulation et évaluation des performances

Faculté MI Département Informatique Filière : Informatique Spécialité : Master Réseaux et multimédia Semestre : S1

Support de cours matière Simulation et évaluation des performances

Contenu du module : le module s’articule en trois chapitres Chapitre I :Rappels- probabilités et variables aléatoires Chapitre II :Processus stochastique et Chaîne de Markov Chapitre III :Files d'attente et réseaux de files d'attente. PS : à la fin de chaque chapitre il y a une série d’exercice + TP

Evaluation des étudiants • Exposé : Rapport ne dépassant pas les dix pages (essayer de donner des exemples pratiques) Choisir un thème d’exposé parmi les trois thèmes : L’outil Java Modelling Tools (JMT) La simulations par le logiciel QNAP2 (Queueing Network Analysis Package). 3. Le simulateur OPNET. Un contrôle de TD de durée 30mn Contrôle régulier 1. 2.

• •

1

Introduction

Simulation et évaluation des performances

Cours simulation et évaluation des Performances 1 Introduction L'évaluation des performances pour des systèmes informatiques notamment réseaux informatique et des télécommunications accentue la nécessité croissante d'outils pour faciliter l’étude de leur comportement. Il est obligatoire d'avoir une assistance dans les trois phases (1) en conception : satisfaire le cahier de charge (2) en exploitation : rendre le système plus performant (3) en recherche : justifier l’intérêt d’une nouvelle solution (algorithme, protocoles, architecture,…etc.) L’évaluation des performances des réseaux couvre les calculs des paramètres de performances : - Temps de réponse d’une requête de traitement d’un client qui peut-être (message ou paquet) - Débit : taux d’utilisation d’une liaison réseau - Nombre de client dans un nœud du réseau voir occupation de mémoire En effet, les calculs de ces paramètres conduit aux types des résultats sous formes de : - Valeur moyenne, - variance - distribution de probabilité (dans ce cas prérequis complet d’une variable aléatoire est nécessaire). - valeur maximale pour garantir (dimensionnement) et pour l’utilisation (gestion des flux et de la QoS : Quality of Service) des systèmes et réseaux. Il existe deux manières pour l’évaluation des performances, par modélisation et par analyse : 1- Modéliser : formuler le système par une architecture en fonction des besoins d’analyse par l’utilisation de modèles et techniques comme les files d’attente, réseaux de pétri, automates stochastiques…etc. 2- Analyser : trois types d’analyses a) Analyse qualitative : ce type d’analyse sera utilisé pour vérifier les propriétés structurelles et comportementales, vivacité, stabilité,….etc. b) Analyse quantitative ou méthodes analytiques (files d’attentes, automates stochastique) c) la simulation à événements discrets pour des systèmes complexes ne pouvant pas être étudiés facilement par des méthodes analytiques (trafic non Markovien ou qui ne peuvent être caractérisés de façon stochastique). Dans ce module, on s'intéressera à la fois aux aspects méthodologiques, aux outils mathématiques, aux techniques de simulation et à des applications spécifiques de l'évaluation de performances. Le domaine d’application privilégié est celui des réseaux de communication.

2. Objectif L'objectif de ce cours est de sensibiliser les étudiants aux problèmes de modélisation et d'évaluation des performances des systèmes informatiques et les réseaux de communication Il se propose de répondre aux questions suivantes : - Pourquoi évaluer les performances d'un système ? 2

Introduction

Simulation et évaluation des performances

- Dans quels cas cela est-il nécessaire ? - Comment modéliser un système ? - Quel type de modèle utiliser ? Comment analyser le modèle ? - Dans quels cas utiliser des méthodes analytiques ou des techniques de simulation ? On arrive alors à : - comprendre le comportement dynamique de système. - Comparer des configurations (solutions modèles et algorithmes). - Evaluer différentes stratégies. - Optimiser les performances. 4. Quelques concepts : Simulation : la simulation est un processus qui consiste à concevoir un modèle d’un système (réel) étudié. Et à mener des expériences sur le modèle construit afin de comprendre le comportement du système afin d’améliorer les performances. « La simulation est l’un des outils d’aide à la décision les plus efficaces à la disposition des concepteurs et des gestionnaires des systèmes complexes. » Mener des expérimentations (Simuler/interpréter) - simuler, c’est expérimenter sur un modèle en exécutant un certain nombre de trajectoires possibles du système. - Interpréter les observations et formuler des décisions Modèle : un modèle est une idéalisation du système réel nous permettant d’apprendre quelques choses d’utile sur son fonctionnement. Système à évènements discrets :systèmes décrits par variables d’état discrètes dont les changements d’état se produisant sous occurrence d’ évènements, exemples : - Nombre de clients dans la file d’attente. (messages ou paquets en attente dans les nœuds de réseaux) - Nombre de processus dans un CPU (système informatique)

3

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

Chapitre I : Rappel- probabilités et variables aléatoires

1

Probabilités généralités

1.1 C'est quoi une probabilité ? La probabilité est un nombre dans l’intervalle [0, 1] qui peut être introduite par deux manières : -

-

La probabilité « subjective » d’un événement désigne un nombre qui caractérise la croyance que l’on a que cet événement est réalisé avec plus ou moins de certitude. Cette croyance peut attendre deux extrêmes : certitude que l'événement est réalisé (probabilité 1) et certitude qu'il n'est pas réalisé (probabilité 0). La probabilité « objective » assimilée à une fréquence ; on ne définit alors la probabilité qu'à partir d'expériences indéfiniment renouvelables. La probabilité d'un événement est la fréquence d'apparition de cet événement.

1.2 Vocabulaire Expérience aléatoire : expérience où le hasard intervient rendant le résultat imprévisible Événement : tout ce qui peut se réaliser ou pas à la suite d’une expérience exemple : « obtenir un 4 », « ne pas obtenir un 4 », « obtenir un chiffre inférieur à 3 » lors d’une expérience de lancer un dé Événement certain : assuré de se produire exemple : « obtenir un chiffre inférieur à 7 » Événement impossible : ne se produira jamais exemple : « obtenir un chiffre supérieur à 7» Événement élémentaire : seulement un seul résultat de l’expérience permet de le réaliser exemple : « obtenir 4 » mais « obtenir un chiffre pair » = pas élémentaire Univers Ω :ensemble d’événements élémentaires.

1.3

Choix d’un modèle

Lors de la réalisation d’une expérience aléatoire, on est amené à choisir successivement : a) Univers Ω : Exemples : Expérience aléatoire 1 : On tire une fois à pile ou face. Il est naturel de considérer  = {P, F} où Pet Fsont les réalisations de l’expérience qui correspondent aux tirages respectifs de pile et de face. - Expérience aléatoire 2 : on lance un dé et on observe le chiffre de la face obtenue  = {1, 2, 3, 4, 5,6} - Expérience aléatoire 3 : on lance deux dés et on observe les chiffres de les faces obtenue  = {(i,j) où 1≤i≤6 , 1≤j≤6 } - Expérience aléatoire 4 : on choisit un nombre entier naturel au hasard  =N - Expérience aléatoire 5 : on choisit un nombre premier au hasard  ={les nombres premiers}  : est l’ensemble des évènements élémentaires On observe qu’il y a deux types d’univers  : Fini →mesurables ; infini →dénombrables -

b) Une famille de parties de  est appelée « Événement »

4

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

Un évènement est défini par une condition conduisant à un ensemble d’issue (résultat d’expérience) - Voici quelques événements : Dans expérience aléatoire 1 (a) la réalisation est face (b) la réalisation est face ou pile (c) la réalisation est face et pile simultanément (d) la réalisation n’est pas face Ces événements peuvent être décrits respectivement par les parties A de  suivantes : (a) A = {f} (b) A = {f}{p} = {f, p} = (c) A = {f}{p} = ∅ (d) A =  f ={p}

Où A représente le complémentaire de la partie A dans  . Dans l’expérience aléatoire 2 (a) la réalisation est 1 (b) la réalisation est un nombre pair (c) la réalisation est un nombre pair inférieur à 3 (d) la réalisation n’est pas un nombre pair. Ces événements peuvent être décrits respectivement par les parties A de  suivantes : (a) A = {1} (b) A = {2, 4, 6} (c) A = {2, 4, 6}{1, 2, 3} = {2}

(d) A = 2,4,6 = {1, 3, 5} Si A et B sont des événements qui correspondent respectivement aux réalisations effectives a et b, on peut avoir besoin de considérer les événements composés : a →A b →B non a → Ac a et b →AB a mais pas b →A\B a ou b →AB a ou bien b

→A B

Arbre des probabilités : Arbre des probabilités permette de visualiser les issues d’une expérience aléatoire.

5

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

La figure représente un arbre de probabilité pour l’expérience aléatoire 1 pour 3 lancers c) Loi de probabilité : La Loi de probabilité est une application P ayant des valeurs dans [0,1] et vérifiant les deux conditions : Condition 1 : P(Ω)=1 Condition 2 : Si ( An) nN est une famille d’évènement deux à deux incompatibles ou disjoints(ne peuvent être réalisés simultanément ) on a alors AiAj=  où i~=j 𝑃 (⋃ 𝐴𝑛 ) = ∑ 𝑝(𝐴𝑛 ) 𝑛∈𝑁

1.4 Liens entre ensembles et probabilités

L’ensemble de tous les événements est noté  , il est inclus dans l’ensemble de toutes les parties de Ω notée 2Ω. A doit au moins satisfaire : 1) A, B    A  B   et A B   2) A    A   3)   

6

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

Exemple : On répète notre lancer de pile ou face jusqu’à ce qu’on obtienne pile. L’univers est alors

 = 1 , 2 ,.... avec 1 = p , 2 = fp 3 = ffp , . . . La réalisation  i est : "on observe pile pour

la première fois au i-ème lancer". L’ensemble correspondant à l’événement : "l’instant de première

sortie de pile est pair" est A = 2  4  6  ... . , c’est une réunion infinie dénombrable. Cette remarque justifie la définition suivante. Définition : Un ensemble  de parties de  est appelée une tribu (ou une σ-algèbre) si: 1)

A1 , A2 ,...     i =1 Ai =   ; i  1,   Ai  

2) A    A c   3)    Les éléments de  (ce sont des parties de  ) sont appelés des événements. Exemple : exemples de tribus a)  =  , , c'est la petite tribu b)  = 2  , c'est la plus grande tribu c) Si A  ,  =

 , A, A ,  c

À une expérience, on associe le couple (, ) où  est une tribu de  . Dire qu’A est un événement, c'est-à-dire: A   . Remarque : Lorsque  est un ensemble dénombrable (en particulier fini), on prend toujours pour tribu  = 2  : l'ensemble de toutes les parties de  .

Système complet d’évènements A1, A2,..., An forment un système complet d’évènements si les partiesA1, A2,..., An de Ω constituent une partition de Ω telle que :

-

∀i Ai≠∅ ∀i≠jAi∩Aj=∅ ⋃iAi=Ω

Système complet d’évènements

1.5 Formules de Probabilité Si on note P(A) la probabilité d'occurrence d'un événement A   on attend que : - 0  P( A)  1 - P () = 1 - A, B  , si A  B =  alors ( A  B) = ( A) + ( B) 7

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

Sinon ( A  B) = ( A) + ( B) − ( A  B) (Axiome de Kolmogorov).

( A) = 1 − ( A) A  B  ( A)  ( B) D'une manière générale, si tous les résultats d'événements ont la même probabilité, on a pour tout événement A   . card ( A) , Nombre de cas favorables / Nombre de cas possibles. ( A) = card () On appel cardinal d'un ensemble fini, A, le nombre d'éléments de cet ensemble et on note card. Exemple: Pile ou face correspond à

 =  f , p avec  =  ,  f , p,  et ( ) = 0, ( f ) = (p) =

1 ,  () = 1 2

Exemple : Dans une salle qui tient 40 personnes (4 rangs de 10) et où je suis placé au hasard, quelle chance ai-je d'être au premier rang? D'être au 1ere rang à la 1ere place à droite ? Il y a deux manières de raisonner : - Il y a 4 rangs : la probabilité d'être à l'un quelconque des 4 rangs est la même. J'ai une chance sur 4 d'être au premier rang. Probabilité ¼. 40! 10 - T Il y a C 40 manière de choisir les personnes du premier rang. = 10!30!

1.6 Probabilités conditionnelles – Indépendance: La probabilité d’un événement A conditionnellement à un événement B, que l’on note P(A|B), est la probabilité que A se produise sachant que B s’est ou va se produire P( A  B) Probabilité conditionnelle de A sachant B (de proba. non nulle) est ( A B) = P( B) Indépendance des évènements On dit que deux évènements A et B sont indépendants si l’on a : P ( A  B )= P( A)  P( B) Il ne faut pas confondre entre 2 évènements (indépendants et incompatibles):: Supposons A et B à la fois indépendants et incompatibles on alors : P ( A  B )= P( A)  P ( B ) P ( A  B )= P ( ) =0 Donc nécessairement P ( A) =0 ou P( B) = 0 Généralisation à N évènement 𝑁

𝑃(⋂ 𝐴𝑖 ) = ∏ 𝑝(𝐴𝑖 ) 𝑖

𝑖=1

Exemple: On considère le lancer d'un dé à 6 faces:  = 1,2,3,4,5,6. Quelle est la probabilité que le nombre de points soit supérieur ou égal à 4 se produise sachant que le résultat du dé est pair? A= le nombre de points soit supérieur ou égal à 4. 8

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

B= le résultat de dé est paire. Supposons que sur 100 jets, il y ait eu 58 réalisations de dé paires et de 12 réalisations du nombre de 12 / 100 12 point est supérieur à 4. Alors P(A|B) = = 58 / 100 58 Evénements indépendants : On dit que A est indépendant de B si : ( A B) = ( A) Si A est indépendant de B, alors B est indépendant de A; en effet

( A  B) = ( A).( B )

Remarque : il ne faut pas confondre entre Evènement indépendant et évènement incompatible Supposons A et B à la fois indépendants et incompatibles : Alors ( A  B) = ( A).( B ) pour indépendant Et ( A  B) = ( ) = 0 d’où nécessairement ( A) = 0 ou ( B) = 0 Exemple: Un serveur web Apache répond à deux types de requêtes A et B. Les requêtes A relatives, portant sur le Web local et les requêtes B absolues (URL) portant sur tout l'Internet. Les requêtes A arrive avec une probabilité de 1/7 pendant une heure et les requête B avec une probabilité 1/5 dans le même temps. Quelle est la probabilité pour que le serveur ne soit pas dérangé en une heure? La probabilité que les requêtes relatives A arrivent est indépendant de l'arrivé des requêtes absolu B. On utilise ( A) = 1 − ( A) , alors les probabilités pour que les deux types de requêtes n'arrivent pas sont : 1 6 P (A n'arrive pas)= 1 − = 7 7 1 4 P (B n'arrive pas)= 1 − = 5 5 6 4 24 P (A et B n'arrive pas) =  = = 0,69 7 5 35 Probabilité composée Soit deux évènement A et B d’un espace probabilisé  la formule suivante : P ( A  B ) =P’ (B/A)P(A)=P(A/B)P’B) Dite formule de probabilité composée

1.7 Théorème des probabilités totales :

A1 , A2 ,..., An Formant une partition de  , Ai  A j =  i  j  Ai =  B ( B) = ( B A1 )( A1 ) + ( B A2 )( A2 ) + ..... + ( B An )( An ) La formule des probabilités totales est : ( B ) =

n

  ( B A ) ( A ) i =1

i

i

Exemple : Un centre de calcul comporte des machines avec seulement deux types de système d'exploitation. 1/3 d'ordinateurs avec un système d'exploitation Windows et 2/3 d'ordinateurs en Linux. Après une statistique, un virus Trojan touche 6% des ordinateurs en Windows et 0,36 des ordinateurs en Linux. La probabilité pour qu'une machine prise au hasard (dont on ignore le système d'exploitation) soit contaminée par un virus est :

9

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

Si A1 = {Windows} et A1 = A2 = {Linux},  = Windows, Linux  Ai =  A1  A2 = 

B = {Contaminée} et B = {Non contaminée} Sachant que ( B) = ( B A)( A) + ( B A)( A) alors ( B) = (0,06 

1 2 + (0,0036  ) = 0,0224 3 3

Soit 2,24 de machine en virus dans ce centre de calcul.

1.8 Le théorème de Bayes Si on considère des évènements A1, A2 et A3 qui forment une partition de l’ensemble  ,. Ces évènements sont donc disjoints et leur réunion forme l’ensemble  ,. Soit B un évènement quelconque de l’ensemble  , A1 , A2 ,..., An Formant une partition de  , Ai  A j =  i  j  Ai =  Cheminement pour arriver au théorème de Bayes : ✓ Théorème des probabilités totales appliqué à B : P(B) = P(A1 ∩ B) + P(A2 ∩ B) + P(A3 ∩ B) ✓ Application du Théorème de la multiplication : P(B) = P(B|A1) x P(A1) + P(B|A2) x P(A2) + P(B|A3) x P(A3) ✓ Application de la formule de Bayes pour A1 par exemple (l’application pourrait être pour A2 ou A3 également): P(A1|B) = P(A1 ∩ B) / P(B) = P(B|A1) x P(A1) / P(B)

Théorème de Bayes : On remplace P(B) par « P(B|A1) x P(A1) + P(B|A2) x P(A2) +P(B|A3) x P(A3) » dans la formule de Bayes pour obtenir le Théorème de Bayes : ( B Ai )( Ai ) Alors ( Ai B) = ( B A1 )( Ai ) + .... + ( B Ai )( Ai ) + ..... + ( B An )( An )

( Ai B ) =

( B Ai )( Ai ) n

  ( B A ) ( A ) i =1

i

i

Exemple : Dans une population pour laquelle 1 habitant sur 100 est atteint d’une maladie génétique A, on a mis au point un test de dépistage. Le résultat du test est soit positif (T) soit négatif T . On sait que :

(T A) = 0,8 et (T A) = 0,9 , On soumet un patient au test. Celui-ci est positif. Quelle est la probabilité que ce patient soit atteint de la maladie A soit P(A) ou P(A|T) ?

( A T ) =

(T A)( A) ( A  T ) 0,01 = = = 0,075 (T ) (T A)( A) + (T A)( A) 0,8  0,01 + 0,1 0,99

10

Chapitre I : Rappel- probabilités et variables aléatoires

2

Simulation et évaluation des performances

Variables aléatoires

Une variable aléatoire est un codage de l’espace des réalisations qui font correspondre à chaque évènement élémentaire (𝜔𝑖 ∈ 𝜔) une valeur numérique réelle (𝑥𝑖 ∈R)

-

Deux types de variables aléatoires ont été définis : • •

Variables aléatoires discrètes (V.A.D.)(des valeurs isolées, dénombrable) Variables aléatoires contenues (tout nombre réel dans un intervalle)

ensemble

2.1 Variables aléatoires discrètes (V.A.D.) On appelle (V.A.D), la variable qui ne prend que des valeurs discontinues dans un intervalle donné borné ou non borné, alors c’est l’application qui à chaque évènement (X=xi) fait correspondre un nombre réel noté P(X=xi)=Pi.

Cette application vérifie les deux propriétés suivantes Propriété 1 : Propriété 2 :

∀Ω𝑖 ∈ Ω ; 0 ≤ 𝑃(Ω𝑖 ) ≤ 1 𝑃(Ω) = 1

Exemple : reprenons l’exemple de l’expérience aléatoire 1 en lançant une pièce de monnaie trois fois

11

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

 = {PPP,PPF,PFP,PFF,FPP,FPF,FFP,FFF} Notons X le nombre de côtés « faces » obtenus

-

X est une (VAD) qui prend les valeurs xi= {0, 1, 2,3} Les probabilités associées à la variable X : Xi P(X=xi)

0 1 2 3 1/8 3/8 3/2 1/8 1 1 3 3 P(X=xi) ou p: P(X=0) = , P(X=1)= , P(X=2)= , P(X=3)= 8 8 8 8 Remarque :On a

 P( x) =  P( X = x) = 1 x

x

2.1.1 Fonction de répartition(F) On appelle fonction de répartition d’une variable aléatoire X, la fonction FX telle que :

FX : R → R

x → FX ( x) = P( X  x) =  P ( y ) y x

Concrètement la fonction de répartition correspond à la distribution des probabilités cumulées. Exemple: Nombre de face sur 3 lancers de pièce Nombre de faces t

FX (t ) = P( X  t )

0 1 1/8 4/8

2 7/8

3 1

Soit FX la fonction de répartition d’une variable aléatoire discrète X alors :

x  0  FX ( x)  1 FXest croissante sur  lim FX ( x) = 0 et lim FX ( x) = 1 x →−

x →+

Si a  b alors P(a  X  b) = FX (b) − FX (a)

12

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

2.1.2 Paramètres d’une V.A.D. : a) Espérance mathématique L’espérance d’une variable aléatoire E(X) correspond à la moyenne des valeurs possibles de X pondérées par les probabilités associées à ces valeurs. L'espérance est considérée comme le centre de gravité. Si X est une variable aléatoire discrète (V.A.D.)de loi de probabilité (xi, pi)définit sur un nombre fini (n) d’évènements élémentaires alors l’Espérance notée E(x) est : E ( X ) =

n

x p i =1

i

i

Remarque : l’espérance est la moyenne des valeurs Xi pondérées par les probabilités Pi. Exemple : Si on reprend l’exemple de la pièce de monnaie : 1 1 3 3 P(X=0) = , P(X=1)= , P(X=2)= , P(X=3)= 8 8 8 8

1 3 3 1 3 E ( X ) = 0  + 1 + 2  + 3  = 8 8 8 8 2

b) La variance La variance d’une variable aléatoire V(X) est l’espérance mathématique du carré de l’écart à l’espérance mathématique. C’est un paramètre de dispersion. Si X est une variable aléatoire ayant une espérance E(X), on appelle variance de X le réel :

V ( X ) = E ([ X − E ( X )] 2 )

V ( X ) = E ( X 2 ) − [ E ( X )] 2 Si X est une variable aléatoire discrète de loi de probabilité (xi, pi), i est défini sur un nombre fini (n) d’évènements élémentaires alors la variance est égale à : n

n

i =1

i =1

V ( X ) =  ( xi − E ( X )) 2 pi =  xi2 pi − E ( X ) 2 Exemple: Si l’on reprend l’exemple de nombre de face sur 3 lancers de pièce. 12 1 12 3 12 3 12 1 V ( X ) = (0 − ) 2  − (1 − ) 2  − (2 − ) 2  − (3 − ) 2  = 1,5 8 8 8 8 8 8 8 8 Remarque :Si X ( ) est infini, il n'est nullement évident que la variable V (X ) existe. De plus comme [ X − E ( X )]  0 nécessairement V ( X )  0 . Par définition, une variance est toujours positive. 2

c) L’écart-type Si X est une variable aléatoire ayant une variance V(X), on appelle écart-type de X, le réel

 ( X ) = V ( X ) alors la variance est également notée  2 .

13

Chapitre I : Rappel- probabilités et variables aléatoires

Simulation et évaluation des performances

2.2 Variables aléatoires continues (V.A.C.) Une V.A. est dite continue si elle peut prendre toutes les valeurs dans un intervalle donné (borné ou non borné).

2.2.1

Fonction densité de probabilité :

On appelle une fonction densité de probabilité toute application continue par morceaux :

f : →  x → f (x) Tel que : +

x   f ( x)  0  f ( x)dx = 1 − Exemple : soit une fonction densité de probabilité f(x)

Sachant que : -

l’aire hachurée en vert correspond à la probabilité

P(X< -10). -

l’aire hachurée en bleu correspond à la probabilité

P(10=0 à espace d’états discret (E) et à temps (T) continu. Si pour tout 0  s  t et pour i, j, x(u), tel que 0  u < s, 𝑃{𝑋(𝑡) = 𝑗/𝑋(𝑠) = 𝑖, 𝑋(𝑢) = 𝑥(𝑢),0 ≤ 𝑢 ≤ 𝑠} = 𝑃{𝑋(𝑡) = 𝑗/𝑋(𝑠) = 𝑖} = 𝑃𝑖𝑗𝑠,𝑡

Une CMTC permet de modéliser des temps (pas des instants). Une CMTC est caractérisée par les transitions d’un état à un autre qui sont probabilistes, décrite par un taux de transition. Le temps passe dans un (état i) est une variable aléatoire distribuée exponentiellement avec le taux µi 4.2.Représentations (graphique et matricielle) On peut décrire une CMTC par : 1- Un diagramme de transition : C’est un graphe orienté et libellé, dont les sommets correspondent aux états de la chaîne, et les arcs sont étiquetés par les taux de la distribution exponentielle. Remarque : dans cette représentation graphique d’une CMTC, on ne trouve pas de boucle. On ignore les boucles quand on parle de CMTC. 2- Une matrice Q : à chaque CMTC on associe une matrice Q, appelée générateur infinitésimal, tel que : Chaque élément qij de la matrice représente le taux de transition de (l’état i) à (l’état j). 27

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

Si i ≠ j alors qij est (µij). Si i = j alors qij est - (la ∑ de tous les autres éléments de la ligne i").

Donc la somme des éléments de chaque ligne de cette matrice doit être égale à 0. En d’autre terme, on peut exprimer les éléments qij de la matrice infinitésimale Q, comme suit: 𝑈𝑖𝑗 𝑙𝑜𝑟𝑠𝑢𝑞𝑒 𝑖 ≠ 𝑗 𝑞𝑖𝑗 = { ∑ 𝑞 𝑖ℎ

𝑙𝑜𝑟𝑠𝑞𝑢𝑒 𝑖 = 𝑗 (𝑑𝑖𝑎𝑔𝑜𝑛𝑎𝑙𝑒)

ℎ=1,ℎ≠𝑖

Exemple : Considérons le processus stochastique modélisant l’état d’une porte (ouverte ou fermée). 0 𝑠𝑖 𝑓𝑒𝑟𝑚é𝑒 𝑋(𝑡) = { 1 𝑠𝑖 𝑜𝑢𝑣𝑒𝑟𝑡𝑒 Nous considérons que les périodes de temps durant lesquels la porte est fermée ou ouverte sont distribuées exponentiellement avec le paramètre λ ou μ (respectivement pour fermée ou ouverte). Donc notre ensemble d’état E = {0, 1} On peut représenter cette CMTC par le graphe des taux de transition suivant :

➢ λ représente le taux d’ouverture ➢ μ représente le taux de fermeture (car on a dit que les périodes de temps durant lesquels la porte est (fermée / ouverte) sont distribuées exponentiellement avec le paramètre (λ , μ)). Et notre matrice infinitésimale est : −𝜆 𝜆 ) 𝑸=( 𝜇 −𝜇

28

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

Définition : La loi exponentielle permet généralement de Modéliser des temps (et pas des instants) dont la valeur n’est pas constante. La loi exponentielle de paramètre λ est une variable aléatoire continue T à valeurs positives , définie par sa densité de probabilité, comme suit : λe−λt ,t ≥ 0 𝑋(𝑡) = { 0 ,𝑡 < 0 La moyenne d’une loi exponentielle de paramètre λ est 1/λ. Par exemple, l’utilisation d’une machine peut être décrite par une variable aléatoire distribuée exponentiellement de taux λ (le temps d’utilisation en moyenne de la machine est 1/ λ). 4.3 Analyse Transitoire et stationnaire Comme pour les CMTD , il existe aussi pour les CMTC un état transitoire et un état stationnaire. Propriété : Une CMTC finie et irréductible est ergodique (c'est-à-dire qu’elle admet une distribution stationnaire). Remarquez ici qu’on n’a pas dit qu’elle est apériodique pour être ergodique ! Précédemment dans les CMTD on avait dit que pour qu’une CMTD soit ergodique il faut qu’elle soit finie, irréductible et apériodique. Mais ici pour les CMTC la notion de périodicité n’existe pas, donc on dit que si une CMTC finie est irréductible alors elle est ergodique. Pour une CMTC ergodique, le vecteur des probabilités stationnaire π existe et est unique, on peut l’obtenir en résolvant le système d’équations suivant : 𝜋𝑄 = 0 { 𝑛 ∑ 𝜋𝑖 = 1 𝑖=1

L’équation d’état : A l’état stationnaire, pour tout état i, le flux sortant de i égal le flux entrant dans i Exemple : Reprenons l’exemple précédant de la porte (ouverte ou fermée). Cette CMTC est finie car la cardinalité de E est 2 (E={0, 1} fini) et elle est irréductible car de tout état i on peut atteindre tout autre état j (i ≠ j), c’est-à-dire de l’état 0 on peut atteindre l’état 1, et de 1 on peut atteindre 0. Puisque cette CMTC est finie et irréductible, elle est donc ergodique (elle atteint l’état stationnaire lorsque t-->∞, c'est-à-dire pour un t très grand). Exemple : Reprenons l’exemple précédant de la porte (ouverte ou fermée).

29

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

Cette CMTC est finie car la cardinalité de E est 2 (E={0, 1} fini) et elle est irréductible car de tout état i on peut atteindre tout autre état j (i ≠ j), c’est-à-dire de l’état 0 on peut atteindre l’état 1, et de 1 on peut atteindre 0. Puisque cette CMTC est finie et irréductible, elle est donc ergodique (elle atteint l’état stationnaire lorsque t-->∞, c'est-à-dire pour un t très grand). 𝜋𝑄 = 0 { 𝑛 ∑ 𝜋𝑖 = 1 𝑖=1

𝜋𝑄 = 0

↔ [𝜋0 , 𝜋1 ] (

−λπ0 + μπ1 = 0 −λ λ )↔{ 𝜇 −𝜇 λπ0 − μπ1 = 0

Donc :

𝜇

λ

λ −λπ0 + μπ1 = 0 𝜋1 = π0 { λπ0 − μπ1 = 0 ↔ { μ 𝜋0 + 𝜋1 = 1 𝜋0 + 𝜋1 = 1

𝜋0 = 𝜇+λ , 𝜋0 = 𝜇+λ Donc le vecteur de probabilité stationnaire est : 𝜇 λ 1 𝜋 = [𝜋0 , 𝜋1 ] = [ , ]= [𝜇, λ] 𝜇+λ 𝜇+λ

𝜇+λ

Note : Le flux sortant de l’état 1 est : μ π1 Le flux sortant de l’état 0 est : λ π0 Le flux entrant dans l’état 1 est : λ π0 Le flux entrant dans l’état 0 est : μ π1 Selon l’équation d’état : a l’état stationnaire, pour tout état i, le flux sortant de i égal le flux entrant dans i. Donc : Flux sortant de l’état 1 = flux entrant dans l’état 1  μπ1 = λπ0 flux sortant de l’état 0 = flux entrant dans l’état 0 λπ0 = μπ1 4.4 Quelques règles importantes : On va voir ici quelques règles de calcul d’indices de performance, en prenant comme exemple,( l’exemple de la porte) : 1. La proportion de temps durant laquelle la porte est dans l’état i (c’est une probabilité) : • La proportion de temps durant laquelle la porte est fermée (état 0): C’est π0 • La proportion de temps durant laquelle la porte est ouverte (état 1): C’est π1 2. Le temps moyen entre deux instants consécutifs, où la porte est ouverte (état 1) C’est : • 1/(flux sortant de 1) = 1/ μπ1 • puisque flux_soratant_de_1 = flux_entrant_dans_1 donc c’est : 30

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

• (1/μπ1 ) =(1/λπ0 ) (Dés qu’il s’agi de calculer le temps moyen entre deux instants consécutifs d’une chose, il faut penser a faire comme ça). 3. La probabilité pour que la porte soit ouverte (ou fermée) : La probabilité d’ouverture de la porte (probabilité de passe de l’état 0 à l’état 1) est : P (ouverte) = λ/(λ+μ) = P01 La probabilité de fermeture de la porte (probabilité de passe de l’état 1 à l’état 0) est : P(fermée) = µ/(λ+μ)= P10 En effet, on peut facilement passer d’un graphe qui représente une CMTC avec des taux de transition, à un graphe qui représente une CMTD avec des probabilités de transition.

31

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

5. Processus de naissance et de mort Une classe importante de processus de Markov, qui intervient dans l'étude des phénomènes d'attente, est celle des processus de naissance et de mort Soit {𝑍(𝑡)}𝑡∈𝑅+ un processus de Markov homogène. Nous identifions les états du processus avec𝐸𝑗 (𝑗 ∈ 𝑁). Le processus {𝑍(𝑡)}𝑡∈𝑅+ est un processus de naissance et de mort, si les seules transitions directes possibles à partir de 𝐸𝑗 (𝑗 ∈ 𝑁) sont: • 𝐸𝑗 → 𝐸𝑗+1 appelée naissance, • 𝐸𝑗 → 𝐸𝑗−1 si j>0 appelée mort. 5.1 Générateur infinitésimal Un processus de naissance et de mort est de générateur infinitésimal suivant :

Pour n =4 le générateur est :

5.2 Distribution stationnaire Calculons la distribution stationnaire π en résolvant l’équation matricielle πA = 0. On obtient le système pour (n = 4) −𝛌0 𝜋0 + 𝜇1 𝜋1 = 0 𝛌0 𝜋0 − (𝛌1 + 𝜇1 )𝜋1 + 𝜇2 𝜋2 = 0 𝛌1 𝜋1 − (𝛌2 + 𝜇2 )𝜋2 + 𝜇3 𝜋3 = 0 𝛌2 𝜋2 − (𝛌3 + 𝜇3 )𝜋3 + 𝜇4 𝜋4 = 0 { 𝛌3 𝜋3 − 𝜇4 𝜋4 = 0 Ces équations se simplifient comme décrit précédemment. Il est plus économique d’écrire directement les équations dites de balance : 32

Chapitre II :Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

𝛌0 𝜋0 = 𝜇1 𝜋1 ; 𝛌1 𝜋1 = 𝜇2 𝜋2 ; 𝛌2 𝜋2 = 𝜇3 𝜋3 ; … … Les calculs pour n quelconque, donnent 𝛌0 𝜋 𝜇1 0 𝛌1 𝜋2 = 𝜋1 𝜇2 𝛌2 𝜋3 = 𝜋2 𝜇3 …..= ⋯.. 𝛌𝑛−1 𝜋𝑛 = 𝜋 { 𝜇𝑛 𝑛−1 𝜋1 =

Et par suite 𝜋𝑘 =

𝛌0 𝛌1 … . 𝛌𝑘−1 𝜋 (𝑘 = 1,2, … . . 𝑛) 𝜇1 𝜇2 … . 𝜇𝑘 0

Compte-tenu de la relation π0 + π1 + · · · + πn = 1, la valeur de π0 est donnée par la formule 1 𝛌0 𝛌0 𝛌1 𝛌0 𝛌1 … . 𝛌𝑛−1 =1+ + + ⋯+ 𝜋0 𝜇1 𝜇1 𝜇2 𝜇1 𝜇2 … . 𝜇𝑛 On obtient finalement la distribution stationnaire 𝜋𝑘 =

𝛌0 𝛌1 ….𝛌𝑘−1 𝜇1 𝜇2 ….𝜇𝑘 𝛌0 𝛌0 𝛌1 𝛌 𝛌 ….𝛌 1+ + +⋯+ 0 1 𝑛−1 𝜇1 𝜇1 𝜇2 𝜇1 𝜇2 ….𝜇𝑛

π = (π0, π1, .. , πn)

(𝑘 = 1,2, … . . 𝑛)

33

Série d’exercice Processus stochastique et Chaîne de Markov

Simulation et évaluation des performances

Série d’exercice : Exercice 1 : Parmi les matrices suivantes, quelles sont celles qui sont des matrices stochastiques ? 1 1 15 1 1 0 − 2) (1) 𝐴 = (16 16) (2) 𝐵 = (1 1) (3) 𝑐 = (2 1 2 2 2 2 2 3 3 3 3 Soient A une matrice stochastique et 𝑢 = (𝑢1 , 𝑢2 , 𝑢3 ) est un vecteur de probabilité Montrer que 𝑢𝐴 est un vecteur de probabilité. 𝑎1 𝑏1 𝑐1 𝐴 = (𝑎2 𝑏2 𝑐2 ) 𝑎3 𝑏3 𝑐3 Exercice 2 : soit 𝑝 = (𝑝1 , 𝑝2 , … … , 𝑝𝑚 ) un vecteur de probabilité et T une matrice stochastique dont chaque ligne est un même vecteur 𝑡 = (𝑡1 , 𝑡2 , … . . , 𝑡𝑚 ). Montrer que 𝑝𝑇 = 𝑡. Exercice 3 : Déterminer l’unique vecteur de probabilité constant de la matrice stochastique régulière P 3

𝑃=

(41 2

1 4 1) 2

Vers quelle matrice , la matrice 𝑃𝑛 tend elle ? Pourquoi ? Si 𝑃𝑛 → 𝑇, que représentent les lignes de T ? Exercice 4 : (i) Montrer que le vecteur u=[b,a] est point fixe de la matrice stochastique : 1−𝑎 𝑎 𝑃=( ) 𝑏 1−𝑏 (ii) A l’aide du résultat de (i) , calculer l’unique vecteur de probabilité constant de chacune des matrices suivante : 1

(iii)

(1) 𝐴 = ( 3 1

1

2 3)

0

(2) 𝐵 =

(22 3

1 2 1) 3

(3) 𝑐 = (0.7 0.3) 0.8 0.2

Exercice 5 : 1 1 0 1 Soit P= ( ). Montrer que pour 𝜋 (0) ≠ [2 , 2], la limite de 𝜋 (𝑡) lorsque 𝑡 → ∞ n’existe pas. 1 0 Exercice 6 : On considère la chaine de Markov suivante : 0.4

06

0.6

0.2 0

0.2

1

0.6 0.4

1.

2

Donner sa matrice de transition P 34

Série d’exercice Processus stochastique et Chaîne de Markov

2. 3. 4.

Simulation et évaluation des performances

La chaine est elle irréductible ? La chaine est elle apériodique ? Si les propriétés sont vérifiées calculer le vecteur limite de 𝑃(𝑛)

Exercice 7:

α  γ

Soit la matrice ➢ Pour quel valeur (α,,γ), la matrice P peut être stochastique ? ➢ Donner Le graphe de transition P ➢ La chaîne est elle irréductible ? ➢ La chaîne est elle apériodique ? ➢ Que peut-on dire sur la chaîne donner la valeur limite du vecteur des probabilités d’états : lim P(n) n→∞ ainsi P(n) Exercice 8 : Considérons un système de télécommunication qui transmet des bits 0 et 1. Chaque bit transmis doit passer par plusieurs étapes. A chaque étape, il y a une probabilité p qu’un bit entré ne change pas lorsqu’il quitte cette étape c’est-à-dire (0 →0 la probabilité est p) ( 0 →1 la probabilité est 1-p) Ce processus peut être modélisé par un chaine de Markov a temps discret ➢ Donner Le graphe de transition et la matrice P . (0.5) ➢ La chaîne est elle irréductible ? (0.5) ➢ La chaîne est elle apériodique ? (0.5) ➢ Que peut-on dire sur la chaîne .(0.5) ➢ donner la valeur limite du vecteur des probabilités d’états : lim P(n) ainsi P(n) Exercice 9 : On considère 4 points équiréparties sur un cercle. Un promeneur saute à chaque instant, d’un point à l’un de ses voisins avec la probabilité 1/2 pour chaque voisin. 1. Déterminer le graphe et la matrice de transition de la chaîne. 2. Quelle est la période de ses états? 3. Si on considère N points où N >=2 , Quelle est la période de ses états? -------------------------------------- -------------------------------------------------------------------------TP02 : (CMTC ; CMTD) Ecrire les fonctions qui vérifient les propriétés suivantes (sous Matlab) : a) Un vecteur v est un vecteur de probabilité b) Une Matrice P est une matrice stochastique c) Un générateur Q est un générateur infinitésimal d) Un programme pour simulation de deux type de chaine (CMTD ; CMTC) TP03 :( processus de naissance et mort) Ecrire une fonction Matlab permettant de calculer le vecteur [𝜋0 , 𝜋1 , … . , 𝜋𝑛 ]en fonctions des vecteurs [𝛌0 , 𝛌1 , … . , 𝛌𝑛 ] et [𝜇1 , 𝜇2 , … . , 𝜇𝑛 ]. 35

Chapitre III: Files d'attente et réseaux de files d'attente

Simulation et évaluation des performances

Chapitre III: Files d'attente et réseaux de files d'attente 1 Introduction :

Un système informatique (Matériel, logiciel, processus) partagent des ressources (CPU, Disques, fichiers ...) dont ces ressources sont utilisées de façon unique à un instant donné, d’autres demandeurs attendent. Donc le besoin d’une file d’attente pour gérer les demandes des ressources est indispensable. Alors la théorie des files d'attente permet une formalisation et une étude quantitative . Un système de file d'attente est une structure qui désigne un ou plusieurs serveurs conçus pour accomplir certaines tâches ou traiter certains travaux et une file d'attente pour les travaux en attente d'être traités. Les travaux arrivent à des files d'attente, et ils attendent qu'un serveur soit disponible, et ils obtiennent un traitement par un serveur et après ils sortent du système. Des exemples de systèmes de files d'attente: - Un ordinateur personnel ou partagé exécute des tâches envoyées par des utilisateurs. - Le fournisseur de service Internet où les internautes connectent, surfent et déconnectent. - Une imprimante de travaux traités et envoyés par plusieurs ordinateurs. - Une chaine TV vue par plusieurs utilisateurs à plusieurs instants. - Un distributeur automatique de banque. 2. Définition Une file d'attente est caractérisée par : ▪ Un flot d'arrivées ▪ Un mécanisme de service ▪ Une salle d'attente ▪ Une discipline de service

Figure illustrative des files d’attentes – Flot d'arrivée : est caractérisé par : 36

Chapitre III: Files d'attente et réseaux de files d'attente

• suite stochastique Tn: est le temps du nième client • sn: la charge apportée par le nième client, service nécessaire. • Les clients arrivent successivement, un à la fois, il n'y a pas d'accumulation: 0