Bornes Stochastiques (stochastic Bounds)

Ecole Doctorale d’Informatique de Béjaïa REseaux et SYstèmes Distribués Evaluation des Performances

Bornes Stochastiques (Stochastic Bounds) BOUCHAMA Nadir & YAHIAOUI Saïd JUILLET 2004

PLAN PLAN Introduction Les méthodes des Bornes Ordre Stochastique Fort de Stoyan Algorithme de Vincent : étude, exemples et critique Méthodes pour réduire la complexité : matrices de Hessenberg supérieures, Matrices de la classe C, décomposabilité, etc. Ordre icx Exemple : taux de perte dans un tampon ATM Conclusion

Méthodes Méthodes pour pour l’évaluation l’évaluation de de performances performances

Évaluation de Performances: Consiste en deux étapes :

1. Modélisation - Développement d’une description formelle du système

2. Résolution - Obtention

des prédictions de Performances du système

Introduction Introduction 



Les systèmes complexes à grand espace d’états ont une matrice de transition P très volumineuse  Problème de stockage de la matrice P Une représentation tensorielle de la matrice de transition P

P = ∑⊗ j M i j i

 

Ceci permet un stockage efficace de la matrice de transition Mais, augmente le temps de l’analyse numérique de la chaîne

Introduction Introduction (2) (2) Lorsque la taille du modèle Markovien empêche sa résolution exacte à l’équilibre  se tourner vers une des trois approches classiques : - La simulation - L’approximation - Les méthodes de bornes

Introduction Introduction (3) (3) 

Nous nous intéressons ici aux indices de performance R définis comme des fonctions de récompense à la distribution stationnaire

 L’objectif est le calcul de la distribution stationnaire pour obtenir R.

Motivations Motivations  Des valeurs exactes des indices de performances

sont des fois non nécessaires  Il est souvent suffisant de vérifier la satisfaction des exigences en Qualité de Service  Borner les fonctions de récompense est suffisant

Méthodologie Méthodologie Nous devons modéliser un système à un grand espace d’états  Calculer sa distribution stationnaire Comment procéder ?  Concevoir automatiquement une nouvelle chaîne telle que: - Les fonctions de récompense sont des bornes sup et inf des fonctions exactes - La nouvelle matrice est plus facile à résoudre  Basé sur la notion d’ordre stochastique des variables aléatoires et les chaînes de Markov 

Notion Notion d’ordre d’ordre stochastique stochastique (Stochastic (Stochastic Order) Order)  Définir un ordre  Encadrer stochastiquement les fonctions de récompense  En général, l’espace des états est discret et dénombrable  Dans la littérature, il existe plusieurs types d’ordres selon les problèmes étudiés: st, icx,….  Ici, on va considérer l’Ordre Stochastique Fort (Strong Stochastic Order) défini par Stoyan. Remarque : Borner la distribution stationnaire  borner les indices de performance

Ordre Ordre stochastique stochastique fort fort (strong (strong stochastic stochastic order) order)  L’ordre stochastique fort est définie soit par un ensemble de fonctions non décroissantes ou par la matrice Kst Définition 1 Soient X et Y des variables aléatoires prenant des valeurs dans un espace totalement ordonné. Alors X est dit plus petit que Y dans le sens stochastique fort noté X <st Y si et seulement si E[ f(X)] ≤ E[ f(Y)] Pour toutes les fonctions non décroissantes f où l‘espérance existe.

Ordre Ordre stochastique stochastique fort fort (strong (strong stochastic stochastic order) order) Définition 2 (en utilisant la matrice Kst ) Si X et Y prennent des valeurs dans l’espace d’états fini {1, 2,…, n} avec p et q comme des vecteurs de distribution de probabilité alors: X est dit plus petit que Y dans le sens stochastique fort noté X <st Y si et seulement si

Avec:

Kst =

1 1

0 1

0 0

... 0 ... 0

1 1 1 ... 0 ... ... ... ... 0 1

1

1

... 1

Exemple Exemple de de deux deux vecteurs vecteurs ordonnés ordonnés selon selon l’ordre l’ordre stochastique stochastique fort fort Soient α = (0.1, 0.3, 0.4, 0.2) β = (0.1, 0.1, 0.5, 0.3) deux vecteurs de distributions de probabilités. Alors α <st β car : 

0.2 ≤ 0.3 0.4 + 0.2 ≤ 0.5 + 0.3 0.3 + 0.4 + 0.2 ≤ 0.1 + 0.5 + 0.3

Comparaison Comparaison stochastique stochastique de de deux deux CM CM 

La monotonicité et la comparabilité des matrices de transitions sont des conditions suffisantes pour une comparaison stochastique de CM.



Définition 3 soient P et Q deux matrices stochastiques. Alors P <st Q ssi: P.Kst ≤ Q.Kst Ceci peut être caractérisé par:

Pi,* <st Qi,* pour tout i

st-monotonicité st-monotonicité



Définition 4 Soit P une matrice stochastique, P est st-monotone SSI pour tout u et v, si u <st v alors uP <st vP.



Propriété Soit P une matrice stochastique, P est st-monotone SSI pour tout i, j > i, on a Pi,* <st Pj,*

Algorithme Algorithme de de Vincent Vincent

(construction (construction d’une d’une borne borne supérieure supérieure optimale) optimale) Algorithme 1 : Construction d’une CMTD Q constituant une borne supérieure st-monotone optimale pour une CMTD P

s

Algorithme Algorithme de de Vincent Vincent (Exemple (Exemple de de déroulement) déroulement)

Soit la matrice P définie comme suit :

P= Borne supérieure optimale pour la matrice P

Q = v (P) =

0.5

0.2

0.1

0.2

0.0

0.1 0.2

0.7 0.1

0.1 0.5

0.0 0.2

0.1 0.0

0.1 0.0

0.0 0.2

0.1 0.2

0.7 0.1

0.1 0.5

0.5 0.1

0.2 0.6

0.1 0.1

0.2 0.1

0.0

0.1

0.2

0.5

0.1

0.1

0.1

0.0

0.1

0.7

0.1

0.0

0.1

0.1

0.3

0.5

0.1

Algorithme Algorithme de de Vincent Vincent

(Quelques (Quelques remarques remarques importantes) importantes) 





L’algorithme de Vincent donne la plus petite borne supérieure dans le sens de l’ordre stochastique fort Il peut arriver que la matrice v(P) calculée par l’algorithme de Vincent soit réductible bien que P ne l’est pas. Il arrive que v(P) soit plus difficile à résoudre que P. Par exemple:

0.5 0.2 0.1 0.1 0.1

P=

1.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0

v (P)

=

0.5 0.2 0.1 0.1 0.1 0.5 0.2 0.1 0.1 0.1

1.0 0.0 0.0 0.0 0.0

0.5 0.2 0.1 0.1 0.1 0.5 0.2 0.1 0.1 0.1

1.0 0.0 0.0 0.0 0.0

0.5 0.2 0.1 0.1 0.1

Algorithme Algorithme 22

(Utlisation (Utlisationd’une d’unevaleur valeurεεpositive positiveetetstrictement strictementinférieure inférieureàà1.0) 1.0)

Améliorer Améliorer l’exactitude l’exactitude de de la la distribution distribution de de l’état l’état stationnaire stationnaire (principes (principes de de base) base) Question : Comment peut-on améliorer l’exactitude de la distribution stationnaire ?

 Appliquer quelques transformations sur P avant d’appliquer l’algorithme de Vincent  Utiliser une fonction α ( P, δ ) = (1 − δ ).I + δ .P avec δ ∈ [0.1]  Ceci n’a aucun effet sur la distribution de l’état stationnaire  Ceci a une grande influence sur l’effet de l’algorithme de Vincent

Théorèmes Théorèmes & & définitions définitions



Théorème Soient P une CMTD et deux variables réelles δ1, δ2 ∈ [0,1] et tels que δ1 < δ2. Alors:

πv (α ( P , δ 1)) <st πv (α ( P , δ 2 )) <st πv ( P )

On peut se demander est ce qu’il existe une valeur optimale pour δ ? δ = ½ est suffisant pour que la matrice résultat soit à diagonale dominante (tous les éléments de la diagonale sont ≥ 0.5)

Remarque Remarque & & Exemple Exemple





Remarque : Si Φ(X) = X/2 + I/2 alors, plus le degré de Φ est plus grand, plus la borne de v(Φ(P)) est exacte. Exemple : Ceci est illustré par l’exemple suivant : P=



0.1 0.2 0.1 0.2

0.2 0.3 0.5 0.1

0.4 0.3 0.2 0.3 0.4 0 0.3 0.4

Soit Φ(X) = X/2 + I/2 et ψ(X) = X²/2 + I/2

Remarque Remarque & & Exemple Exemple (suite) (suite)

0.55 0.1

Φ(P) =

0 .1

0.15

0.65 0.1

0.15

0.05 0.25 0.7 0 .1

ψ(P) =

0 .2

0

v(Φ(P)) =

0.55 0.1 0.2 0.1 0.55 0.2

0.05 0.25 0.55 0.15 0.05 0.1

0.05 0.15 0.7

0.15 0.15

0.15 0.7

0.575 0.155 0.165 0.105

0.575 0.155 0.165 0.105

0.08

0.08

0.63

0.155 0.135

0.075 0.185 0.65

0.09

0.075 0.13

0.625

0.17

v(ψ(P)) =

0.63

0.155 0.135

0.075 0.185 0.605 0.135 0.075 0.13

0.17

0.625

Comparaison Comparaison des des résultats résultats



Et,

v(P) =



0 .1 0 .1 0 .1 0 .1

0 .2 0 .2 0 .2 0 .2

0 .4 0 .4 0 .4 0 .3

0 .3 0 .3 0 .3 0 .4

Enfin, nous obtenons les distributions stationnaires suivantes:

π v(P) = (0.1, 0.2, 0.3667, 0.3333) π v (Φ(P)) = (0.1259, 0.2587, 0.2821, 0.3333) π v (ψ(P)) = (0.1530, 0.2997, 0.2916, 0.2557) π P = (0.1530, 0.3025, 0.3167, 0.2278)  Il est clair que, les bornes obtenues par ψ sont plus exactes que les autres bornes

Méthodologie Méthodologie pour pour simplifier simplifier les les calculs calculs numériques numériques 







Utiliser des matrices avec des propriétés structurelles et numériques particulières Utiliser des algorithmes (plus efficaces) pour la résolution numérique Utiliser des matrices à caractéristiques spéciales: matrices de Hessenberg, matrices décomposables en blocs, matrices de classe C,etc Pas de nouvelles hypothèses sur P

Matrices Matrices de de Hessenberg Hessenberg supérieure supérieure



Définition : Une matrice H est dite Hessenberg-supérieure ssi Hi,j= 0 pour

 

i > j+1 Mouvoir la masse de probabilité vers la droite Exemple :

0.1 0.2 0.4 0.3 0.1 0.2 0.4 0.3 0.0 0.3 0.4 0.3 0.0 0.0 0.6 0.4

Algorithme Algorithme de de construction construction d’une d’une borne borne supérieure supérieure st-monotone st-monotone et et Hessenberg Hessenberg supérieure supérieure

Décomposabilité Décomposabilité en en blocs blocs (Lumpability) (Lumpability)   

Utilisé par Truffet pour les réseaux de commutation de l’ATM La décomposabilité implique une réduction de l’espace des états Définition (décomposabilité ordinaire)

Soit X une CMTD finie irréductible, Q sa matrice de transition, soit Ak une partition des états. X est ordinairement décomposable par rapport à Ak, ssi pour tous les états e et f dans le même macro-état Ai on a: pour tout macro-état Ak

Algorithme Algorithme pour pour construire construire une une borne borne supérieure supérieure st-monotone st-monotone et et ordinairement ordinairement décomposable décomposable

Matrices Matrices stochastiques stochastiques de de la la classe classe C C Une matrice stochastique Q = (qi,j )1≤i,j≤n appartient à la classe C si pour chaque colonne j il existe une constante réelle Cj satisfaisant les conditions suivantes: Qi+1,j = Qi,j+ Cj 1≤ i≤ n-1 Puisque Q est une matrice stochastique, la somme des éléments n cj = 0 ∑ de chaque ligne doit être égale à 1, ainsi : j =1 Exemple

0.45 0.15 0.4 0.35 0.20 0.45 0.25 0.25 0.5

Avantages Avantages des des matrices matrices stochastiques stochastiques de de la la classe classe C C  Leur état stationnaire peut être résolu en un temps linéaire

 La caractérisation de la st-monotonicité est très simple aussi dans cette classe. Elle est donnée par la propriété suivante: Propriété: Soit P une matrice stochastique appartenant à la classe C. P est st-monotone ssi

Algorithme Algorithme de de construction construction d’une d’une borne borne supérieure supérieure st-monotone st-monotone et et appartenant appartenant àà la la classe classe C C

Autres Autres ordres ordres entre entre les les matrices matrices stochastiques stochastiques  La monotonicité et la comparaison des matrices stochastiques sont plus générales que ce qu’on a vu  La monotonicité et la comparaison des matrices de transition offre des conditions suffisantes pour comparer les chaînes de Markov dans des relations d’ordre plus générales  Nous allons voir la relation d’ordre icx

L’ordre L’ordre icx icx Définition 1 Soient X et Y des variables aléatoires prenant des valeurs dans un espace totalement ordonné. Alors X est dit X
Autre Autre définition définition de de l’ordre l’ordre icx icx 

Définition 2 (en utilisant la matrice Kicx ) Si X et Y prennent des valeurs dans l’espace d’états fini {1, 2,…, n} avec p et q comme des vecteurs de distribution de probabilité alors X <st Y si et seulement si



Avec

p.Kicx ≤ q.Kicx

Kicx =

1 2

0 1

0 0

... ...

0 0

3 ...

2 ...

1 ...

... ...

0 0

n

n −1

n −2

...

1

Autre Autre définition définition de de l’ordre l’ordre icx icx (suite) (suite) 

Autre notation algébrique:

car

Remarque Remarque 

De façon similaire, l’ordre concave est défini par un ensemble de fonctions concaves non décroissantes ou par la matrice : T

Kicv = - Kicx

Caractéristiques Caractéristiques 



 

La comparaison selon l’ordre « icx » ainsi que la monotonicité des matrices stochastiques sont définies de façon analogue que celles pour l’ordre « st » Une condition suffisante pour la icx-monotonicité est donnée par:

La condition ci-dessus conduit à une chaîne de Markov dont le dernier état est absorbant. Benmammoun à défini ds conditions nécessaires et suffisantes pour la icx-monotonicité

Conditions Conditions de de Benmammoun Benmammoun 





Cette condition est basée sur la matrice Zicx légèrement −1 K différente de la matrice icx −1 Zicx .P. K icx ≥ 0 est une condition nécessaire et suffisante pour la icx-monotonicité

Ceci a donné naissance à un l’algorithme suivant

Algorithme Algorithme de de construction construction d’une d’une borne borne supérieure supérieure icx-monotone icx-monotone

Remarque Remarque sur sur l’algorithme l’algorithme de de construction construction d’une d’une borne borne supérieure supérieure icx-monotone icx-monotone  La sortie de cet algorithme n‘est pas toujours une matrice stochastique  On trouve des fois des élément supérieurs à 1  Il peut donner un bon résultat….

 Comme il peut en donner un mauvais

?  Utiliser des heuristiques….

icx-monotonicité icx-monotonicité pour pour les les matrices matrices stochastiques stochastiques de de la la classe classe C C Proposition 1

Proposition 2 : Si P est de la classe C alors on a :

P est st-monotone

⇒ P est icx-monotone

ATTENTION Ceci n’est pas vrai pour les matrices stochastiques n’appartenant pas à la classe C

Exemple: Exemple: taux taux de de perte perte dans dans un un tampon tampon ATM ATM

 Etude de la politique de gestion de la mémoire tampon (buffer memory) dans un réseau de commutation ATM  Deux niveaux de priorité : Haute (H) et Basse (L)  Taille de la cellule constante  Les arrivées arrivent selon un processus batch suivant une loi de Bernouilli  Principe du PushOut : pousser pour remplacer  Taille du tampon: B

Principe Principe du du PushOut PushOut dans dans un un tampon tampon ATM ATM

Principe Principe du du PushOut PushOut dans dans un un tampon tampon ATM ATM

Modélisation Modélisation

 Hypothèse : Les arrivées de cellules H et L sont i.i.d  Nombre d’états de la chaîne de Markov : (B+1)(B+2)/2  Les états ordonnés selon un ordre lexicographique non décroissant  Nombre Total de Cellules perdues : R = RH + RL  Le mécanisme du PushOut ne change pas le nombre total de cellules perdues  Si B =1000 alors nombre d’états est 5 * 105  Mécanisme du PushOut

Modélisation Modélisation (suite) (suite)

 



 

Soit PklaH probabilité d’arrivées de k cellules durant un intervalle de temps Le taux de cellules de haute priorité perdues est :

Idée clé : Réduire l’espace des états par décomposition de la chaîne initiale en macro-états (ne pas représenter les cas où il y a un nombre élevé de cellules L) On définit des macro états (T,Y) avec T-F ≤ Y ≤ T Pour un processus d’arrivées plus général, la fonction de récompense est donnée par:

Application Application sur sur un un tampon tampon de de taille taille 44

  

  

Considérons un tampon de taille 4 Notation : (T,H) : T= nbre total de cellules H : nbre de cellules H On aura 15 états ordonnées lexicalement comme suit:

p, q et r probabilités des arrivées pour un batch de taille 0,1,2 a (resp.b) probabilité qu’une cellule soit de BASSE (resp. HAUTE) priorité Distribution des cellules dans un batch de taille 2 : c pour 2 cellules de Bas niveau, e pour deux cellules de haut niveau, d pour un mélange

Matrice Matrice de de transition transition

Avec x =qa+rc et y =qb + rd

Comparaison Comparaison des des résultats résultats

       

Soit par exemple : taille du tampon égale à 80 Ceci pour permettre de vérifier les résultats obtenus La charge étant de 0.9 avec 2/3 de cellules de niveau H Résultats exact est 8.9 * 10 -13 (3321 états) F : facteur d’agrégation Si F =10 résultats exacts : 9.5 *10 -13 (798 états seulement !!) Si F=2 très mauvaise borne : 10 -6 Choix de F : compromis entre exactitude des résultats et complexité des calculs

Chaîne Chaîne agrégée agrégée

CONCLUSION CONCLUSION 







L’approche des bornes stochastiques est une très bonne approche pour vérifier la satisfaction des exigences en QoS dans les réseaux informatiques L’ordre stochastique est choisi selon le problème à étudier (souvent on utilise l’ordre «st» de Stoyan) Faire un bon compromis entre l’exactitude des bornes et la complexité des calculs lors du chois de F Beaucoup de recherches sont faites actuellement pour étendre les résultats à l’état transitoire