Modélisation Quantitative de la Fiabilité

Modelisation Quantitative de la Fiabilite

J.M. Fourneau

Laboratoire PRiSM, CNRS UMR 8144

Universite de Versailles St-Quentin

M2 ASS-ACSIS 2008, Universite de Versailles St Quentin [1/324]

Fiabilite

• Hypotheses : Les pannes se produisent. . .

• On peut essayer de les rendre moins frequente : ameliorer les

equipements, les logiciels, les methodes de test.

• On peut aussi en limiter les consequences.

• Construire un systeme plus fiable que ses composants elementaires.


Comment ?

• Dupliquer les composants

• Verifier si il est possible de recuperer une faute

• Avoir un composant de secours

• Dupliquer le calcul et choisir le resultat

• Tout ceci a un cout lie a la redondance. . .


Problematique

• Caracteriser la fiabilite des composants : taux de panne, processus de

panne, processus des reparations.

• Evaluer la fiabilite d’un systeme avec ou sans redondance

• Pour choisir la configuration la moins couteuse repondant aux

contraintes de fiabilite imposees.


Plan

• Un peu de vocabulaire

• Un premier rappel de probabilites

• Modeles statiques : RBB et Fault Trees

• Un second rappel de probabilites

• Modeles dynamiques Markoviens

• Un troisieme rappel de probabilites

• Les modeles non Markoviens et la simulation


Fiabilite

• Reliability

• Definie par ITU (International Telecommunications Unions)

recommendation E.800:

• Definition 1 (Reliability;Fiabilite) The ability of an item to

perform a required function under given conditions for a given time

interval.

• Donc prendre en compte un intervalle de temps

• et le systeme doit etre operationnel pendant toute la periode


Disponibilite

• Availability

• Egalement definie par une recommendation ITU

• Definition 2 (Availability;Disponibilite) The ability of an item to

be in a state to perform a required function at a given instant of time

assuming that the external resources, if needed, are provided.

• Donc prendre en compte une date

• et le systeme doit etre operationnel a cette date.


Dependability

• Pour eviter la confusion entre la notion mathematique bien definie et le

mot usuel (Fiabilite),

• Proposee par IFIP WG 10.4


Dependabillity Umbrella


Systemes Fiables

• Applications Critiques (6nines): aviation, espace, industrie nucleaire.

• Applications a Haute Disponibilite (5nines): E-commerce, finance,

telecommunications, reservation avion.

• Applications a Disponobilite usuelle (4nines): mobile


Un premier rappel de Proba

• Probabilites, Aximatique

• Probabilites Conditionnelles, Formules de Bayes

• Theoreme du conditionnement

• Variable Aleatoire,

• MTTF, MTTR


Construire un modele

• Espace d’etat S: l’espace de tous les etats possiblement observables

d’un systeme aleatoire

• Espace des Evenements E : tous les evenements possibles utiles pour

le modele

• Une mesure de probabilites µ sur les evenements.


Espace d’Etats

• Tous les resultats possibles d’un systeme aleatoire.

• Fini (nombre de roues operationnelles sur un vehicule)

• Denombrable (nombre de clients dans une file)

• Continu (temps residuel de service avant absence de client)


Axiomes des Probabilites

• Pour tout evenement A, la probabilite de A verifie :

• O ≤ µ(A) ≤ 1

• µ(E) = 1

• µ(A ∪ B) = µ(A) + µ(B) − µ(A ∩ B)


Consequences

• µ(∅) = 0

• µ(E) = 1 − µ(E)

• A et B sont exclusifs si A ∩ B = ∅

• µ(A ∪ B) = µ(A) + µ(B) si A et B sont exclusifs.

• µ(∪iAi) =∑

i µ(Ai) si les Ai sont deux a deux exclusifs.


Probabilites Conditionnelles

• Pr(A|B) : probabilite que A se produise sachant que B s’est deja

produit.

• Si µ(B) > 0), Pr(A|B) = µ(A∩B)µ(B)

• On peut generaliser (en supposant que toutes les probabilites soient

positives) :

µ(∩ni=1Ai) = µ(A1)Pr(A2|A1)Pr(A3|A1∩A2) . . . P r(An|A1∩A2∩. . . An−1)

• Exemple : D’un lot de 10 pieces dont ma moitie est defectueuse, on

preleve sans remise un echantillon de taille 3, quelle est la probabilite

que l’echantillon ne comprenne aucune piece defectueuse ?

P (A1 ∩ A2 ∩ A3) =5

10

4

9

3

8


Independance

• A et B sont mutuellement independants ssi Pr(A|B) = µ(A).

• Donc, µ(A ∩ B) = Pr(B|A)µ(A) = µ(B)µ(A)

• La probabilite de l’union de deux evenements independants est leur

somme.

• Et la probabilite de l’intersection de deux evenements independants est

leur produit.


Theoreme de Conditionnement

• Theoreme 1 Soit B1, B2, . . . Bn une partition des evenements (deux a

deux mutuellement exclusifs et recouvrant l’ensemble des evenements),

pour tout A on a :

µ(A) =∑n

i=1 Pr(A|Bi)µ(Bi)

• Theorem of Total Probability en Anglais.

• Exemple : D’un lot de 10 pieces dont ma moitie est defectueuse, on

preleve sans remise un echantillon de taille 3, quelle est la probabilite

que la seconde piece soit bonne ?

µ(A2) = Pr(A2|A1)µ(A1) + Pr(A2|A1)µ(A1) =5

10

4

9+

5

10

5

9


Formule de Bayes

• Theoreme 2 (Formule de Bayes)

Pr(A|B) = Pr(B|A)µ(A)

µ(B)

• Preuve:

Par definition, µ(A ∩ B) = Pr(B|A)µ(A)

Et µ(A ∩ B) = µ(B ∩ A)

Donc Pr(B|A)µ(A) = Pr(A|B)µ(B)

• Utilise en Inference Statistique (les opinions a-priori doivent etre

modifiees a la lumiere des experiences)


Exemple Bayes

• Vous utilisez trois types de disques (notes T1, T2 et T3) avec les

proportions (0.6, 0.3 et 0.1). Sur la duree d’une mission les

probabilites de panne sont respectivement de 0.9, 0.8 et 0.5. Quelle est

la probabilite qu’un disque tombe en panne soit de type T1 ?

• On note B = { un disque au hasard tombe en panne } et Ak = {un

disque au hasard est de type Tk }.

• On a

Pr(A1|B) = Pr(B|A1)µ(A1)

µ(B)

et

µ(B) =3∑

i=1

Pr(B|Ai)µ(Ai)


Variable Aleatoire

• Une variable aleatoire est une fonction de l’espace des etats vers

l’espace des reels.

• La fonction affecte un reel a chaque etat

• Si l’image de E est finie ou denombreble, la variable aleatoire est

discrete. On utilise les entiers plutot que les reels.


Fiabilite

• Fiabilite R(t)

• Soit X la date de la panne du systeme.

• R(t) = Pr(X > t)

• R(t) est decroissante.

• F (t) = 1 − R(t) est la distribution de la v.a. du temps de vie du

systeme.


MTTF

• Mean Time To Failure: temps moyen avant panne.

• MTTF = E[X ]

• Donc, MTTF =∫ +∞0 tf(t)dt ou f(t) est la densite de la v.a. temps de

vie du systeme.

• f(t) est la derivee de F (t).

• MTTF =∫ +∞0 R(t)dt


Disponibilite Ponctuelle

• A(t) = Pr(Le systeme est operationnel a la date t).

• Deux parties :

– Pas de panne entre 0 et t.

– Une date a la date x (entre 0 et t et une reparation avant t.

• A(t) = R(t) +∫ t0 A(t − x)dH(x) ou H est la convolee de F

(distribution du temsp de vie du systeme) et G (distribution du temps

de reparation).

• Et donc A(t) ≥ R(t).


MTTR

• Mean Time To Repair: temps moyen de reparation.

• Y : temps de reparation.

• MTTR = E[Y ] =∫ t0 tg(t)dt ou g(t) est la densite de la v.a. Y

• g(t) est la derivee de G.


Disponilite Stationnaire

• Astst = limt→∞A(t).

• Astst = MTTFMTTF+MTTR

• Downtime = (1 − Astst) ∗ 60 ∗ 24 ∗ 365 en minutes par an.

• On parle d’etat UP (operationnels) et DOWN (non operationnels)


Comment evaluer la fiabilite

• Mesures

– Plus precis, plus cher

– Methodes Statistiques

– Faire attention au delai, au cout, et si c’est vraiment possible.

• Modeles

– Plus complexes, moins chers, moins fiables

– Methodes Combinatoires ou Probabilistes ou Statistiques


Modeles

• Simulation : Monte Carlo ou evenements discret ou horloge

• Analytique : Processus Stochastique et en particulier analyse

Markovienne des modeles avec representation explicite des etats.

• Methodes statiques ne reposant pas sur l’espace des etats : RBD et

Arbres de Fautes.


RBD: Reliability Block Diagramm

• Une representation graphique du systeme et de la fiabilite.

• Chaque composant est represente par un bloc.

• Sert a determiner si le systeme est UP ou DOWN en fonction des etats

des composants.

• Idee intuitive : un bloc peut etre vu comme un switch qui est ferme

quand le composant est UP et ouvert quand le composant est DOWN.

• Il y a une entree dans le diagramme S et une sortie T .


RBD-2

• C’est un modele reposant sur la logique et non pas sur les etats.

• Modele Statique : pas de representation du temps ni de l’ordre entre

des evenements successifs.

• Hypothese d’Independence des pannes des differents composants.

• Pas de pannes arrivant conjointement ou de pannes provoquees par la

panne d’un autre composant.


RBD-3

• Le systeme est UP si il y a au moins un chemin passant par des

elements UP et reliant S a T .


Logique

• Le comportement du systeme par rapport a la panne est modelise par

les connexions entre blocs.

• Si tous les composants sont necessaires, les modeliser en serie

• Si un seul des composants est necessaire, les modeliser en parallele.

• Si il en faut au moins K parmi N , utiliser la structure ”K out of N”


Blocs en Serie

• n composants independants en serie.

• Ei le composant i fonctionne.

• Rs = µ(E1 ∩ E2 ∩ . . . ∩ En)

• A cause de l’independance :

µ(E1 ∩ E2 ∩ . . . ∩ En) =n∏

i=1

µ(Ei)

• En notant Ri = µ(Ei), on obtient :

Rs =n∏

i=1

Ri

• On remarque que Rs < min(Ri). Le systeme est moins fiable que sa

composante la moins fiable.


Blocs en Parallele

• n composants independants en prallele.

• Ei le composant i fonctionne.

• Rs = µ(E1 ∪ E2 ∪ . . . ∪ En)

• Le systeme est en panne si tous les composants sont en panne:

1 − Rp =n∏

i=1

(1 − Ri)


Systemes Serie-Paralleles

• Decomposition recursive : un systeme serie-parallele (SP) est soit :

– un bloc isole

– plusieurs sous-systemes SP en serie

– plusieurs sous-systemes SP en parallele

• Utilise la decomposition recursive de la construction pour obtenir la

fiabilite.

• Exemple simple : n etages en serie, chaque etage compose de m

composants en parallele tous identiques:

Rsp = (1 − (1 − R)m)n


Example : Station de Travail/Serveur de Fichiers

• Un serveur de fichiers,

• Deux stations de Travail identiques

• Un reseau pour les connecter. On suppose que le reseau est fiable.

• Le systeme est operationnel si le serveur de fichiers est operationnel et

au moins une des deux stations de travail est operationnelle.


Representation de l’exemple


Etude de la fiabilite de l’exemple

• Rw fiabilite d’une station de travail

• Rf fiabilite du serveur de fichiers

• Rfsw fiabilite du systeme

Rfsw = (1 − (1 − Rw)2)Rw


Systemes NON Serie-Paralleles

• Theoreme 3 Un graphe est SP ssi il ne contient ni structure N ni

structure W.

• Si on ne peut plus utiliser la decomposition SP, on peut enumerer et

construire la table Booleenne.


Exemple non SP: reseau avec bridge


Utilisation de la table Booleenne

• Examiner tous les cas UP et DOWN pour toutes les composantes

• Dans chaque cas, evaluer si le systeme est UP ou DOWN

• Calculer les probabilites de chaque cas (facile, c’est le produit des

probas elementaires a cause de l’hypothese d’independance).

• Exemple : Si E1 = E2 = E4 = 1 et E3 = E5 = 0 le systeme est UP et

la probabilite de cette configuration est R1R2R4(1 − R3)(1 − R5).

• Sommer les probabilites que le systeme soit UP


Premiere partie de la table de l’exemple


Seconde partie de la table de l’exemple


Resultat pour l’exemple

• En agregeant la table precedente et en factorisant on trouve que:

Rbridge = R1R2

+ R1(1 − R2)(R4R5 + R3(1 − R4)R5)

+ (1 − R1)R4(R5 + (1 − R5)R2R3)


Conditionnement et Factorisation

• Mais il faut considerer les 2n configurations si il y a n objets.

• On conditionne sur le l’etat d’un composant (ou de plusieurs

composantes) pour se ramener a des structures deja etudiees ou faciles

(SP)

• Sur l’exemple du bridge, on conditionne sur l’etat du bloc 3.


Conditionnement sur 3 UP


Conditionnement sur 3 DOWN


Conditionnement

• Si le composant 3 est DOWN, on obtient un modele SP

• Si le composant 3 est UP, on obtient egalement un modele SP

• On applique le theoreme de conditionnement et les formules pour les

modeles serie-paralleles.


Conditionnement

• R3down = 1 − (1 − R1R2)(1 − R4R5)

• R3up = (1 − (1 − R1)(1 − R2))(1 − (1 − R4)(1 − R5))

• On applique le theoreme de conditionnement

Rbridge = R3R3up + (1 − R3)R3down


Composant K parmi N

• Systeme consistant en N composants independants.

• Le systeme est UP quand K ou plus de ces composants sont UP.

• Cas Identique : tous les composants ont le meme taux de panne et de

reparation.

• Cas Non Identique : Les composants ont des taux de panne et de

reparation distincts par composant.


Avec sous-composants identiques

• Soit R la fiabilite d’un composant.

• On aditionne les probabilites de toutes les configurations avec au

moins K composantes operationnelles.

R(K, N) =N∑

j=K

Rj(1 − R)N−j N !

j!(N − j)!

• Somme partielle d’une distribution binomiale.

• Algorithme classique (attention aux approximations numeriques)


Recurrence dans le cas general

• Systeme dont les composants sont distincts. La fiabilite de la

composante i est Ri.

• 3 remarques simples :

– Un systeme avec K = 0 (sans contraintes) est toujours UP.

R(0, N) = 1

– Un systeme trop contraint est toujours DOWN.

R(j, N) = 0 si j > N

– En conditionnant sur l’etat de la composante N :

R(i, N) = (1 − RN )R(i, N − 1) + RNR(i − 1, N − 1)

• Algorithme recursif.


Arbres de Fautes

• Une representation graphique de la combinaison d’evenements qui peut

provoquer l’occurence d’une panne.

• Modele combinatoire (i.e. ne representant ni le temps, ni les etats)

• Objets elementaires: feuilles, noeud interne d’un arbre, racine.

• Feuille : composant du systeme

• Noeud interne : porte logique

• racine : un boolean qui porte l’etat du systeme. Il passe a TRUE

quand le systeme est en PANNE. . .


Arbres de Fautes -2

• Portes:

– OR : pour connecter des sous-systemes en serie

– AND : pour connecter des sous-systemes en parallele

– Porte (N − K + 1) of N : pour connecter des composants qui sont

dans un systeme K parmi N

• La panne d’un composant met a TRUE l’entree de la porte ou il est

connecte.

• Dans les autres cas, elle est a FALSE.

• Evaluation de l’arbre. . .

• Si la racine de l’arbre est a TRUE, le systeme est en panne.

• Fiabilite : Probabilite que la racine soit FALSE.


Arbres de Fautes -3

• On peut ajouter de nombreuses autres portes : NOT, XOR, Priority

AND, des dependances fonctionnelles.

• Deux types de Fault Trees: avec ou sans evenements repetes.

• La complexite de la resolution est fonction de la (non) repetition des

evenements.

• Repetition : formellement ce n’est plus un arbre si on regroupe et ce

n’est plus independent si on separe.


Exemple sans repetition: alternate routing

• Un reseau avec 5 noeuds : A, B, C, D, E et 10 liens.

• Le systeme est UP lorsque A est connecte a B et C est connecte a D

par une route directe : AB, et CD ou une route supplementaire : CED,

ACB, ADB, AEB.


Arbre de Faute pour le routage

• Panne de liens. Routeurs Fiables.

• Feuilles : liens du reseau.

• Portes : de type OR ou AND.

• Pas de repetition a cause des chemins consideres.


Arbre de Faute pour le routage


Analyse des portes simples

• Panne sur une porte AND a deux entrees a et b :

(1 − Rs) = (1 − Ra)(1 − Rb)

• Porte sur une porte OR a deux entrees a et b :

(1 − Rs) = (1 − Ra) + (1 − Rb) − (1 − Ra)(1 − Rb)

• Car il faut ne pas compter deux fois le cas ou les composants a et b

sont en panne.

• Cette equation est equivalente a Rs = RaRb.


Analyse de l’arbre de Faute pour le routage

• Ce qui donne pour le modele du routage :

R = R1R2

ou

R1 = 1 − (1 − Rab)(1 − RacRcb)(1 − RadRdb)(1 − RaeReb)

et

R2 = 1 − (1 − Rcd)(1 − RceRed)


Arbre de Fautes avec repetition

• Des feuilles sont dupliquees.

• Exemple : 2 processeurs p1 et p2, deux memoires locales lm1 et lm2 et

une memoire globale gm.

• Le systeme est UP si il existe au moins un processeur UP connecte a

une memoire (locale ou globale) UP.


Arbre de Fautes avec repetition


Analyse Exemple

• On conditionne sur l’etat de gm et le theoreme de conditionnement.


Formule Logique

• On peut aussi ecrire la panne comme une formule logique a partir de

l’arbre de fautes.

• Dans l’exemple precedent, on note P1 la proposition ”le processeur p1

fonctionne”, (notations identiques pour les autres propositions)

• On obtient :

Panne = (P1 + ¯LM1 ¯GM)(P2 + ¯LM2 ¯GM)

• apres developpement :

Panne = P1P2 + P2 ¯LM1 ¯GM + P1 ¯LM2 ¯GM + ¯LM1 ¯LM2 ¯GM


Travail sur la formule

• On a une union de termes (ie la somme)

• Mais les termes obtenus ne sont pas disjoints.

• Avec des termes disjoints, on pourra faire la somme des probabilites.

Si A et B disjoints :

µ(A ∪ B) = µ(A) + µ(B)

• Transformer la formule pour obtenir des termes disjoints.


Algorithmes SDP

• Sum of Disjoint Products

• Transforme une formule pour obtenir une somme de termes disjoints.

• Dans l’exemple precedent on obtient :

Panne = P1P2+P1P2 ¯LM2 ¯GM+P1P2 ¯LM1 ¯GM+P1P2 ¯LM1 ¯LM2 ¯GM

A partir de

Panne = P1P2 + P2 ¯LM1 ¯GM + P1 ¯LM2 ¯GM + ¯LM1 ¯LM2 ¯GM

• Pas d’algorithme optimal

• Plusieurs heuristiques reposant sur des coupes minimales.


Analyse des Arbres de Fautes

• Si il n’y a pas de repetition dans l’arbre, on peut le transformer en un

RBD.

• Et employer les algorithmes du RBD pour calculer la fiabilite

• Si il y a repetition dans l’arbre :

– Factorisation

– Algorithme SDP (sum of disjoint products)

– Structure de donnees BDD pour gerer l’explosion combinatoire


Binary Decision Diagram (BDD-1)

• un BDD est une structure de donnees pour coder une fonction

Booleenne, ou en plus abstrait, un ensemble.

• Une fonction est representee par un graphe oriente acyclique avec une

racine. Ce graphe contient des noeuds de decision et deux feuilles

etiquetees 0 et 1.

• Chaque noeud de decision a deux fils (haut associe 1 et bas 0).

• Un chemin de la racine la feuille 1 represente une affectation partielle

ds variables pour que la fonction soit vraie.


Exemple BDD

Fonction f(X1, X2, X3) = X1X2X3 + X1X2 + X2X3


BDD-2

• Un BDD est ordonne (ordered) ssi les variables sont dans le meme

ordre sur tous les chemins

• Un BDD est reduit (reduced) ssi

– Tous les sous graphes isomorphes ont ete fusionnes

– Tous les noeuds dont les deux fils sont isomorphes ont ete

supprimes.

• En general, BDD signifie Reduced Ordered Binary Decision Diagram.


BDD-3

• La transformation d’une formule en BDD est simple et elle ne necessite

pas la construction de l’arbre de Shannon (l’arbre complet)

• On peut construire de facon compositionnelle

• La taille du BDD est tres sensible a l’ordre des n variables

• La meme formule peut etre codee par un BDD lineaire en n ou

exponentiel en n selon l’ordre des variables retenu.

• L’optimisation de la taille en jouant sur l’ordre est un pb dur mais il y

a des heuristiques

• Le AND ou le OR de 2 BDD a une complexite de l’ordre du produit

des tailles.

• Le NOT d’un BDD a une complexite en la taille.


BDD-4

• Algorithmes recursifs

• NOT

– NOT (0) = BDD(1)

– NOT (1) = BDD(0)

– NOT (x.F1 + −x.F0) = BDD(x, NOT (F1), NOT (F0))

• OP (OR ou AND)

– (x.F1 +−x.F0)OP (x.G1 +−x.G0) = (x.(F1OPG1)+−x.(F0OPG0))


Exemple OR BDD - Recursion



Complexite de l’Analyse

• Arbre de Fautes sans repetition : resolution en temps lineaire.

• Arbre de Fautes avec repetition : resolution en temps exponentiel.

• En pratique : avec BDD et Factorisation, les outils logiciels peuvent

resoudre des problemes avec des centaines de composants.


Un Second Rappel de Probabilites

• Prendre en compte le temps.

• Processus Stochastique.

• Nature du temps, de l’espace.

• Bernoulli, Geometrique, Loi de Poisson

• Processus de Poisson, Loi exponentielle

• Markov


Prendre en compte le temps

• pour prendre en compte l’ordre des evenements

• Exemple : voiture + roue de secours + telephone portable.

• Panne Grave : roue en panne + roue de secours en panne et telephone

en panne avant que les roues ne soient en panne (sinon on appelle le

depanneur).

• pour prendre en compte les dependances temporelles (taux de panne

variant avec le temps).


Bathtub Curve

• DFR : decreasing failure rate, composant en debut de vie (pb de test)

• CFR : constant failure rate, composant a l’etat stationnaire

• IFR : increasing failure rate, composant veillissant


DFR

• Causee par la non detection de defauts hardware ou software.

• Ne pas utiliser des modeles avec taux de panne constant car on

trouverait des resultats peu significatifs.

• Utiliser loi ayant la propriete DFR (par exemple Weibull).


CFR

• Taux de panne constant (ou presque)

• Pannes provenant de l’environnement exterieur

• Processus de Poisson pour arrivees de panne, et loi exponentielle pour

delai entre pannes successives.


IFR

• Effet de veillissement sur des pieces mecaniques

• pb thermiques pour l’electronique

• On peut aussi employer la loi de Weibull pour modeliser un

phenomene IFR.


Processus Stochastique

• Evolution d’une variable aleatoire avec le temps

• Espace :

– discret (fini ou infini) : une population

– continu : des coordonnees

• Temps:

– discret : horloge

– continu : temps physique

– evenement discret :


Exemples

• Temps discret, Espace discret : la fortune d’un joueur

• Temps discret, Espace continu : une hauteur d’eau a un barrage,

chaque jour

• Temps continu, Espace discret : le nombre de particules au cours d’une

reaction

• Temps continu, Espace continu : les positions de corps dans une

interaction gravitationnelle

• Evenement discret, Espace discret : le nombre de paquet dans un

routeur

• Evenement discret, Espace continu : prix d’une action.

•


Trajectoire Temps Discret Espace Discret


Trajectoire Temps Discret Espace Continu


Trajectoire Evenement Discret Espace Discret


Trajectoire Evenement Discret Espace Continu


Limitations

• Temps Discret, Evenement discret (bcp)

• Quelques processus simples en temps continu (pour generer des

evenements)

• Espace Discret


Temps Discret - Bernoulli

• Bloc de base pour la construction des v.a. discretes et des processus.

• 2 resultats possibles : 0 ou 1

• µ(1) = p

• µ(0) = 1 − p


Loi Binomiale

• B(n, p) : La somme de n v.a. indeprendantes Bernoulli de parametres

p.

• Distribution de Probabilites :

µ(k) = pk(1 − p)n−k n!

k!(n − k)!

• Pour modeliser des systemes avec n composants independants ou n

essais pour effectuer une tache.


Aspects Calculatoires

• L’algorithme naif est numeriquement instable

• Si n est petit on peut employer une formule de recurence

µ(k) = µ(k − 1)p

1 − p

n − k + 1

k

• Si n est grand, on peut approximer par une loi Normale.

• La distribution de probabilite a trois formes


Distribution d’une Binomiale 8


Distribution Geometrique

• Le nombre d’essais (incluant le dernier) avant une reussite

• L’espace des etats est infini denombrable

• Soit p la probabilite de succes, la distribution est :

µ(n) = p(1 − p)n−1


Distribution Geometrique et Propriete Sans Memoire

• La distribution geometrique a la propriete Sans Memoire.

• Ce qui signifie que le futur est indepdendent du passe.

• Precisement, apres n echecs, le nombre d’essais avant reusssite a la

meme distribution que la loi initiale.


Preuve

• X date du premier succes, q = 1 − p, j = n + i.

• n premiers essais: echecs.

Pr(X = j > n|X > n) = Pr(X = n + i|X > n)

= Pr(X = n + i ∩ X > n)/µ(X > n)

= Pr(X = n + i)/µ(X > n)

= pqn+i−1/(1 − (1 − qn)) = pqi−1

= µ(Z = i)


Loi de Poisson

• La v.a. represente le nombre d’evenements (par exemple des pannes)

qui se produisent dans l’intervalle [0, t[.

• Un seul parametre : le taux des arrivees, λ.

• Distribution limite d’une binomiale renormalisee lorsque le temps tend

vers 0

• Distribution :

µ(k) = e−λt (λt)k

k!


Variables aleatoires continues

• Pour representer le temps ou les etats.

• Delai entre deux pannes ou delai pour reparer une panne.

• Distribution exponentielle (propriete sans memoire, processus de

Poisson)

• Distribution de Weibull et proprietes IFR, CFR, DFR.


Rappels

• On utilise la notion de distribution FX(t) = µ(X ≤ t).

• Si FX(t) est continue, alors X est une v.a. continue.

• Si FX(t) est en escalier, alors X est une v.a. discrete.

• 0 ≤ FX(t) ≤ 1

• FX(t) est croissant.

• FX(−∞) = 0 et FX(∞) = 1.


Loi Exponentielle

• Une variable aleatoire positive avedc la propriete sans memoire.

• Liee au processus de Poisson, la loi de Poisson et aux chaines de

Markov.

• F (t) = 1 − exp(−λt) et h(t) = λ.

• A cause de la propriete sans memoire, elle modelise :

– un delai avant panne, un delai de reparation

– des durees entre appels, sessions,

– des temps de service (mais les tailles de paquets ne sont jamais

aleatoires).


Attention

• C’est une hypotese. . .

• Il faudrait faire des mesures pour verifier.

• Et chercher des distributions plus realistes en les parametrant par plus

d’un moment (un seul parametre pour exponentiel, deux pour

Weibull).


Fiabilite et Propriete Sans Memoire

• Cela signifie que la distribution du temps resideul de vie ne depent pas

du temps ou le composant est en operation.

• Fiabilite: le composant tombe en panne apres une panne exterieure

soudaine et non a la suite d’une deterioration graduelle.

•


Taux de Panne et Exponentielle

• h(t) est le taux de panne instantane (le nombre de pannes par unite de

temps)

• h(t) = f(t)R(t)

• L’exponentielle est la seule v.a. continue de type CFR.


Loi de Weibull

• Peut modeliser des phenomenes CFR = 1, IFR > 1et DFR < 1 selon

les parametres.

• est le parametre de forme (shape) et est celui d’echelle (scale).

• F (t) = 1 − exp(−λtα), h(t) = λαtα−1.

• Fiabilite : R(t) = exp(−λtα)


Quelques exemples

• Cold Spare

• Warm Spare

• Hot Spare

• Systeme triple avec vote


Cold Spare

• Un seul composant est actif

• L’autre (le spare) est inactif

• Le spare ne tombe pas en panne quand il est inactif

• La duree de vie est exponentielle de λ

• Detection de panne et changement pour le spare : immediat

• La duree de vie totale est la somme de deux exponentielles de meme

taux: Erlang 2

R(t) = 1 + λt)exp(−λt)


Warm Spare

• Un composant est actif

• L’autre (le spare) est en attente

• Le spare peut tomber en panne quand il est en attente

• La duree de vie est exponentielle de λ pour un composant actif

• La duree de vie est exponentielle de α pour un composant en attente



Warm Spare Analysis

• Duree de vie totale : la somme de deux exponentielles mais qui ne sont

pas de meme taux.

• Le premier evenement est la panne du composant principal ou du spare

• La duree avant cet evenement est le minimum de l’exponentielle de λ

et de l’exponentielle de taux α, ce qui est une exponentielle de taux

λ + α.

• La duree de vie pour le composant survivant est une exponentielle de

taux λ (propriete sans memoire).

• Duree de vie totale : la somme de exponentielle de taux λ + α et de

l’exponentielle de taux λ.


Hot Spare

• Les deux composants sont actifs.

• La duree de vie est exponentielle de λ pour un composant actif


• Duree de vie totale : la somme de deux exponentielles mais qui ne sont

pas de meme taux.

• Le premier evenement est la panne du composant principal ou du spare

• La duree avant cet evenement est le minimum de l’exponentielle de λ

et de l’exponentielle de taux λ, ce qui est une exponentielle de taux 2λ.

• La duree de vie pour le composant survivant est une exponentielle de

taux λ (propriete sans memoire).

• Duree de vie totale : la somme de exponentielle de taux 2λ et de

l’exponentielle de taux λ.


Systeme triple avec voteur: TMR

• 3 composants et un voteur

• Le voteur ne tombe pas en panne et ne fait pas d’erreurs.

• C’est un systeme 2 parmi 3.

• Soit RTMR sa fiabilite et R la fiabilite d’un composant.


Analyse

• On obtient d’abord que :

RTMR = 3R2(t) − 2R3(t)

• Si on suppose que la fiabilite d’un composant est exponentielle de taux

λ,

Rt = exp(−λt)

• Finalement,

RTMR(t) = 3exp(−2λt) − 2exp(−3λt)


Esperance-MTTF

• Rappel : E[X ] =∫ ∞

O tfX(t)dt.

• L’esperance peut ne pas exister (voir les lois puissances)

• L’esperance est lineaire

E[X + Y ] = E[X ] + E[Y ]

• Mais pour le produit il faut l’independance. Si X et Y sont

independants, alors :

E[X ∗ Y ] = E[X ] ∗ E[Y ]


Quelques resultats sur le MTTF

• Le MTTF est l’integrale de la fiabilite

• Le MTTF d’un composant dont la duree de vie est exponentielle de

taux λ est 1/λ.

• Si le composant a une duree de vie hypoexponentielle de taux λ1,

λ2,. . .λn, le MTTF est la somme des 1/λi.


MTTF du Systeme triple avec vote

• On suppose que les composants ont une duree de vie exponentielle.

MTTFTMR =

∫ ∞

0RTMR(t)dt =

∫ ∞

03exp(−2λt) − 2exp(−3λt)dt

Donc,

MTTFTMR =3

2λ−

2

3λ=

5

6λ

• On remqrque que MTTFTMR < 1λ qui est le MTTF d’un composant.

• Donc le MTTF du TMR est 16% plus petit que le MTTF d’un

composant mais sa fiabilite est superieure pour une mission de courte

duree.


MTTF des autres exemples

• En utilisant la linearite de l’esperance et l’esperance d’une

exponentielle,

• Cold Spare

MTTFColdSpare =2

λ

• Warm Spare

MTTFWarmSpare =1

λ+

1

λ + α

• Hot Spare

MTTFHotSpare =3

2λ


Processus de Poisson

• Un processus ponctuel tel que le nombre d’evenements entre 0 et t suit

une loi de Poisson.

• La difference entre deux point successifs suit une loi exponenetielle de

meme taux.

• Pour representer

– apparition de pannes

– arrivees de paquets (reseau)

– arrivees de sessions (serveur Web)

– arrivees de jobs (OS)


Proprietes du processus de Poisson

• La superposition de deux processus de Poisson independents est un

processus de Poisson. Le taux global est la somme des taux.

• Le splitting d’un processus de Poisson (de taux λ) selon un processus

de Bernoulli indepdendent (de taux p) cree deux processus de Poisson

independents de taux λp et λ(1 − p).

• PASTA: Poisson Arrivals See Time Average.


Chaınes de Markov en temps discret

• On travaille sur un processus a valeur dans un espace d’etats

denombrable.

• Definition 3 (Markov) Un processus Xt est Markovien si etseulement si

Pr(Xt+1 = j|xt = it, xt−1 = it−1 . . . , x0 = i0) = Pr(Xt+1 = j|Xt = it) (1)

• On note Pr(Xt+1 = j|Xt = it) = Pi,j(t).

• Definition 4 (Chaıne homogene) Une chaine de Markov est

homogene si et seulement si Pi,j(t) est independant de la date t. Cette

probalilite, note Pi,j, est la probabilite de transition de i vers j.


DTMC, Matrice Stochastique

Par construction, la matrice P verifie les proprietes suivantes :

• tous les elements de P sont positifs ou nuls

• pour tout i,∑

j Pi,j = 1


Trajectoire

• Supposons qu’a l’instant 0, le processus soit connu ( valeur de la

probabilite a l’instant 0 Pr(X0 = i) ∀i)

• Appliquons le theoreme de conditionnement

Pr(X1 = j) =∑

i

Pr(X1 = j|X0 = i)Pr(X0 = i) =∑

i

Pi,jPr(X0 = i) (2)

• Soit π(t) le vecteur des probabilites Pr(Xt = i).

π(1) = π(0)P et π(k) = π(0)P k (3)

Ce qui donne un algorithme simple de calcul de la distribution a la date k.


Problemes d’absorbtion, de transitoires et de stationnaire

• Existence d’une limite au vecteur π(t) lorsque le temps t temps vers

l’infini ?

• Que vaut π(t) a une date quelconque ?

• La chaıne est elle absorbee ?

• La chaıne revient elle toujours dans certains etats ?

• Etablir une classification des etats et des chaınes.

• Tenir compte de la taille


Premier Exemple : probabilites limites 0.1 0.4 0.5 0

0 0.2 0.3 0.5

0.3 0.1 0.2 0.4

0.1 0 0 0.9


Convergence des puissances


Deuxieme exemple: etre absorbe en 4


Classification des Etats

On definit pour chaque etat quatre quantites liees aux dates de retour a cet

etat.

• fnj est la probabilite de l’evenement ”(le premier retour en j a lieu en

n transitions)”.

• fj est la probabilite de retour en j : fj =∑∞

n=1 fnj

• Mj est le temps moyen de retour en j : Mj =∑∞

n=1 n × fnj

• γ est le pgcd des valeurs de n telles que fnj est non nulle. γ est la

periode de retour.


Transience ou Recurence

• Si fj < 1 l’etat est transitoire.

• Si fj = 1 l’etat est recurent :

– si Mj = ∞, l’etat est recurent nul.

– si Mj < ∞, l’etat est recurent non nul.

De plus,

– si γ > 1, l’etat est periodique de periode γ.

– si γ = 1, l’etat est aperiodique.


Classification des chaines

• Necessaire d’examiner leur structure.

• Definition 5 Un sous ensemble A d’etats est ferme si et seulement si

il n’y a pas de transition entre cet ensemble et son complementaire.∑i∈A

∑j∈A Pi,j = 0

• Definition 6 (Etat absorbant) un etat absorbant est un sous

ensemble ferme ne comprenant qu’un seul element.

• Definition 7 Une chaine est irreductible si et seulement si le graphe

oriente de la chaine est fortement connexe. C’est a dire si il existe un

suite de transitions menant de i a j pour tous les etats i et j.


• Pour analyser une chaine reductible, il faut la decomposer en

composantes fortement connexes.

• Theoreme 4 Soit une chaine de Markov irreductible, tous les etats

sont:

– tous transitoires

– ou tous recurents non nuls

– ou tous recurents nuls

De plus, si un etat est periodique, alors tous les etats le sont avec la

meme periode.


Existence d’une limite

Theoreme 5 Soit une chaine de Markov, irreductible et aperiodique, alors

la distribution limite π = limt→∞π(t) existe et est independante de la

distribution initiale π(0) (on dit qu’elle est ergodique). De plus,

• soit tous les etats sont transitoires ou recurents nuls et dans ce cas

π(j) = 0, pour tout j.

• soit tous les etats sont recurents non nuls et π est solution unique des

deux equations : π = πP

πe = 1(4)

ou e est un vecteur colonne dont tous les elements sont 1. De plus, on

a π(j) = 1/Mj


Chaıne Finie

• Plus simple: pas de recurrence nulle.

• Theoreme 6 Toute chaine finie,irreductible et aperiodique est

ergodique.


Resoudre le stationnaire

• Analytiquement (voir plus loin)

• Numeriquement (pourquoi pas ?)

• Simulation (en faisant tres attention)


Resoudre etats absorbants

• Probabilite d’etre absorbee sachant que l’on commence en i

• Temps moyen avant d’etre absorbee sachant que l’on commence en i

• Hypothese : il y a plusieurs points absorbants et pas de classes

recurentes (pretraitement pour fusionner chaque classe recurente en un

sommet).


Pb des points absorbants

• On suppose que l’espace des etats est partitionne: les etats absorbants

sont en tete.

• La matrice P peut etre decomposee en bloc

Id 0

R Q

• On peut prouver que P 2 =

Id 0

R + QR Q2

• Et que, pour tout n, P n =

Id 0

(∑n−1

j=0 Qj)R Qn


Matrice Fondamentale

• P n est la matrice de transition pour n sauts successifs.

• limn→∞P n[i, j] est la probabilite d’etre en j a l’infini sachant que l’on

a debute en i.

• La matrice M = (Id − Q)−1 existe si Q ne contient pas de classe

recurrente et elle vaut∑∞

j=0 Qj .

• Et donc,

limn→∞P n =

Id 0

MR 0

• M est la matrice fondamentale.


Probabilites d’etre absorbe

• L’entree [i, j] de la matrice produit M ∗ R donne la probabilite d’etre

absorbe en j sachant que le point initial est i (point non absorbant).

• Si πO est la distribution initiale la probabilite d’etre absorbe en j

s’obtient par conditionnement sur l’etat initial

µ(absorbe en j) =∑

i

(MR)[i, j]π0(i)

• Si il y a un seul point, la proba est 1 (inutile de faire des calculs).


Temps Moyen avant d’etre absorbe

• Soit Xi,j le nombre de visite achant que l’on a debute en i avant d’etre

absorbe.

• On calcule dans un premier temps E[Xi,j ].

• Le temps moyen avant d’etre absorbe sachant que l’on a debute en i

est alors :∑

j E[Xi,j ].

• Le temps moyen avant d’etre absorbe sachant la distribution initiale π0

est alors :∑

i

∑j π0(i)E[Xi,j ].

• On regoupe tous les points d’absorbtion en un seul (de numero 1).


E[Xi,j]

• Theoreme 7 E[Xi,j ] = M(i, j)

• On retouve la matrice fondamentale.


Preuve

• Posons δi,j le symbole de Kronecker,

• En conditionnant sur la premiere etape on a

Xi,j =

δi,j avec proba P (i, 1)

Xk,j + δi,j avec proba P (i, k)

• En passant aux esperances:

E[Xi,j ] = δi,jP (i, 1) +∑k>1

(E[Xk,j ] + δi,j)P (i, k)

• Apres regroupement:

E[Xi,j ] = δi,j +∑k>1

E[Xk,j ]P (i, k)


Preuve - suite et fin

• Posons E[Xi,j ] = Z[i, j].

• En passant a une formulation matricielle :

Z = I + QZ

• Et donc, Z = (I − Q)−1 = M


Temps Continu - CTMC

• On construit et on analyse de facon similaire des processus de Markov

en temps continu.

• Les delais entre transition sont des exponentielles, les differentes

transitions sont rassemblees dans une matrice generatuer Q

• On peut se ramener a la chaine des sauts pour etudier les proprietes

d’existence.


Proprietes

Par construction, la matrice du generateur Q verifie les proprietes

suivantes :

• tous les elements de Q, sauf ceux de la diagonale, sont positifs ou nuls

• pour tout i,∑

j Qi,j = 0


Equilibre Stationnaire

• La distribution d’equilibre est solution de

πQ = 0 et πe = 1

• e est un vecteur plein de 1 (notation classique)

• On n’etudiera pas les distributions transitoires (equations

differentielles)


Flux Stationnaire

• Considerons l’equation d’equilibre sous forme matricielle:

πQ = 0

• En developpant pour un i quelconque, on a:∑j

π(j)Q(j, i) = 0

• Separons la somme: ∑j &=i

π(j)Q(j, i) = −π(i)Q(i, i)

• Mais:

Q(i, i) = −∑k &=i

Q(i, k)


• Donc: ∑j &=i

π(j)Q(j, i) =∑k &=i

π(i)Q(i, k)

• Interpretation en terme de flux: tout ce qui permet de sortir de i

(partie droite) est egal a tout ce qui permet de rentrer en i.

• Interpretation simple et plus facile a utiliser


Analyse

• Pour le probleme stationnaire on doit resoudre πQ = 0.

• Pour le probleme stationnaire on doit resoudre π(t)Q = ∂π∂t connaissant

π(0).

• pour les temps avant absorption on doit resoudre :


Modele de Disponibilite a deux etats

• Q(up, down) = α, Q(up, up) = −α, Q(down, down) = −β,

Q(down, up) = β,

• α est le taux de panne, β le taux de reparation.

• Stationnaire : resoudre πQ = 0

• 2 inconnues, 2 equations, mais une seule independante.

• On rajoute π(up) + π(down) = 1.


• Donc π(up) = βα+β

• Et la fiabilite assymptotique vaut π(up).

• On a aussi π(down) = αα+β


Transitoire

• On doit maintenant resoudre π(t)Q = ∂π∂t sachant πUP (0) = 1.

• ∂πUP

∂t = βπDOWN (t) − απUP (t)

• Mais on a pour tout t, πDOWN(t) = 1 − πUP (t).

• Ce qui donne l’equation (solution connue) :

∂πUP

∂t= β − (α + β)πUP (t)

• Et donc,

πUP (t) =β

α + β−

exp(−(α + β)t)

α + β


Systeme a deux composants

• On suppose maintenant que l’on a ajoute un second composant

redondant.

• Les pannes sont exponentielles (taux α) et indepdendantes.

• Les reparations sont exponentielles et independentes. Il y a un

reparateur et le taux de reparation est β.

• Le systme est DOWN quand tous les composants sont DOWN.

• On ne peut reparer qu’un seul composant a la fois.


Modele

• Etats : nombre de composants en activite: 0, 1, 2.

• Transitions :

– 2 vers 1 : taux 2α

– 1 vers 0 : taux α

– 0 vers 1 : taux β

– 1 vers 2 : taux β


Equation Stationnaire

2απ(2) = βπ(1)

(α + β)π(1) = 2απ(2) + βπ(0)

απ(1) = βπ(0)

1 = π(0) + π(1) + π(2)


Resolution

• Apres substitution on a :

π(1) =β

απ(0) π(2) =

β

2απ(1)

• Donc

π(0)(1 +β

α+

β2

2α2) = 1

• Et la disponibilite stationnaire vaut 1 − π(0).


Processus de Naissance et de Mort

• Definition 8 Une chaıne de Markov est un processus de Naissance et

de Mort si et seulement si, pour tout etat n, les seules transitions

possibles amenent aux etats n − 1 et n + 1, si ces etats existent.

• La transition de l’etat n a l’etat n + 1 est une Naissance.

• La transition de l’etat n a l’etat n − 1 est une Mort.

• λn (resp. µn) est le taux de Naissance (resp. de Mort) a l’etat n.


Equilibre Stationnaire

• Ecrivons l’equation d’equilibre stationnaire pour Xt:

π(n)[µn1{n>0} + λn] = π(n − 1)λn−11{n>0} + π(n + 1)µn+1 (5)


Resolution

• Pour resoudre, considerons l’equation a l’etat 0 pour obtenir π(1) en

fonction de π(0).

π(0)λ0 = π(1)µ1 (6)

• Examinons maintenant l’equation a l’etat 1.

π(1)[µ1 + λ1] = π(0)λ0 + π(2)µ2 (7)

• Apres simplification : π(1)λ1 = π(2)µ2

• Par recurence sur n :

π(n)λn = π(n + 1)µn+1 (8)


• Soit:

π(n) = π(0)

∏n−1i=0 λi∏ni=1 µi

(9)

• Si on peut normaliser:

∞∑n=1


< ∞ (10)

• alors,

π(0) =

[1 +

∞∑n=1


]−1

(11)


Processus de Naissance et de Mort simple

• Description par une file d’attente (capacite = stockage dans la file,

nombre de serveurs = puissance du service).

• Capacite Infinie, 1 serveur

• Capacite Infinie, m serveurs

• Capacite Finie, 1 serveur

• Capacite Finie, m serveurs

• Capacite Infinie, Inifinite de serveurs


La file M/M/1

• Arrivees Poisson, Service iid Exponentiel, 1 Serveur, Capacite infinie

pour garder les clients.

• On note µ le taux de service et λ le taux d’arrivees.

• C’est un processus de Naissance e tde Mort avec les taux de transition: λi = λ ∀ i

µi = µ ∀i(12)

• Posons ρ = λ/µ.


• Equation d’equilibre global :

π(x)[µ1{x>0} + λ] = π(x − 1)λ1{x>0} + π(x + 1)µ (13)

• Condition d’ergodicite:

– la chaine est ergodique si et seulement si (ρ < 1). Dans ce cas la

solution stationnaire est π(x = k) = (1 − ρ)ρk.

– Lorsque ρ = 1 le processus est recurent nul.

– Si ρ > 1 le processus est transitoire.

• Par la suite on suppose que le processus est ergodique


Statistiques Simples

• La moyenne du nombre de clients E(N) dans la file:

E(N) =∞∑

i=1

iπ(x = i) =ρ

1 − ρ(14)

• La probabilite que la file soit vide est (1 − ρ)

• le taux d’utilisation de la file U vaut donc ρ.

• Variance V (N) du nombre de clients dans la file:

V (N) = E(N2)−(E(N))2 =∞∑

i=1

i2π(x = i)−(E(N))2 =ρ

(1 − ρ)2(15)

• Probabilite qu’il y ait au moins n clients dans la file: ρn.


Caracteristiques temporelles

• Theoreme 8 La fonction de repartition F (r) du temps de reponse a

une distribution exponentielle:

F (r) = 1 − e−r(µ−λ)

• En appliquant la formule de Little, on trouve plus simplement le temps

moyen de sejour dans la file E(r) = T = 1/(µ − λ).

• Par inversion de la fonction de repartition les quantiles de la

distribution du temps de reponse. Par exemple, borne sq du temps de

reponse de q pourcent du nombre de clients.

sq =1

µ − λln(

100

100 − q)


Figure 1: Attente, Sejour et Service en fonction de ρ


Quelques chiffres

• Percentile du temps de sejour

– 90 pourcent : 2.3 Temps Moyen de Sejour

– 95 pourcent : 3 Temps Moyen de Sejour

• Le temps moyen de sejour est fortement non lineaire:

• Idem pour le temps moyen d’attente


Non Linearite

• On considere une file dont la duree de service moyenne est 2mn et 24s

(144s)

• Le taux d’arrivee est 10 clients/h

• Que vaut le temps moyen de reponse ?

• Reponse : le temps moyen de service est 0.04h

• Donc la charge vaut 0.4 (10*0.4)

• Et le temps de reponse vaut en seconde 144/(1 − 0.4) = 240

• Le taux d’arrivees augmente de 2 clients/h

• La charge passe a 0.48 et le delai passe a 277s.

• Augmenter les arrivees de 20 pourcent augmente le delai de 17

pourcent


• Le taux d’arrivee est maintenant de 20 clients/h

• Donc la charge vaut 0.8

• Et le temps de reponse vaut en seconde 720s

• Le taux d’arrivees augmente de 2 clients/h

• La charge passe a 0.88

• Le delai passe a 1200s.

• Augmenter les arrivees de 10 pourcent augmente le delai de 67

pourcent


Caracteristiques temporelles

• Distribution du temps d’attente: F (w) = 1 − ρe−w(µ−λ).

• Exponentielle tronquee.

• wq la borne du temps d’attente de q pourcent des clients:

wq = max(0,1

µ − λln(

100ρ

100 − q))

• Si q est inferieur a 100(1 − ρ), le temps d’attente est nul. Ce

pourcentage correspond aux clients entrant dans une file vide.


Figure 2: Distribution de l’attente


Figure 3: distribution du percentile de l’attente divise par l’attente moyenne

en fonction de la charge pour les percentiles 90, 95 et 98


Compromis Usager/Operateur

• Un operateur souhaite que son systeme soit utilise le plus possible

• donc ρ doit etre grand

• Mais lorsque ρ s’approche de 1, le temps d’attente des usagers est non

borne

• Demandes antagonistes : compromis....


Effet d’echelle

• Un systeme avec beaucoup de clients est plus efficace qu’un systeme

avec peu de clients.

• Sur un exemple:

• Arrivees : 5 clients/h. Service moyen de 6mn.

• Donc la charge est 0.5 et le temps moyen de reponse est de 12mn.

• Mais si on double le taux d’arrivees tout en divisant par deux le temps

de service (les clients sont plus petits mais plus nombreux, ou le

serveur est plus rapide)

• La charge reste 0.5 mais le temps moyen de reponse devient 6mn.


Effet d’echelle

• A combien peut-on faire monter le taux d’arrivees tout en gardant le

delai initial de 12mn

12 =1

µ − λ

λ = 15 clients/h

• Un serveur rapide peut fournir des performances superieures en tmps

moyen avec un effet plus que lineraire....


Capacite et Dimensionnement

• Choisir le taux de service pour assurer un temps moyen de service pour

un taux d’arrivee donne.

• Soit R le temps de reponse,

• La capacite C est le debit nominal du serveur = µ

R =1

C − λ

• Donc, C = λ + 1/R

• C ≥ λ assure la stabilite du systeme, le terme 1/R est le cout pour

obtenir les performances demandees sur un systeme aleatoire simple.


Figure 4: Capacite et Effet d’echelle, C/λ en fonction de λ


Analyse M/M/m

• C’est un processus de Naissance et de Mort caracterise par:

λi = λ ∀ i

µi = iµ si i ≤ m

µi = mµ si i > m

(16)

• La probabilite qu’il y ait au moins m clients dans le systeme est une

quantite importante notee γ

• C’est donc aussi la probabilite qu’un client entrant soit contraint

d’attendre avant de commencer son service

γ =(mρ)m

m!(1 − ρ)π0 (17)


Figure 5: Probabilite de ne pas attendre en fonction de ρ pour m = 1, 2, 3


La file M/M/m

Caracteristiques Spatiales

Charge ρ = λ/(mµ)

Probabilite systeme vide π0 =(1 + (mρ)m

m!(1−ρ) +∑m−1

i=1(mρ)i

i!

)−1

Probabilite d’avoir k clients si k¡m π0(mρ)k

k!

sinon π0mmρk

m!

Probabilite d’attente γ = (mρ)m

m!(1−ρ)π0

Nombre moyen de clients E(n) = mρ + ργ1−ρ

Variance du nombre de clients V (n) = mρ + ργ(m + 1+ρ−ργ

(1−ρ)2)

Nombre moyen de

clients en attente E(n) = ργ(1−ρ)

Variance du nombre

de clients en attente V (n) = ργ(1+ρ−ργ)(1−ρ)2


La file M/M/m

Caracteristiques Temporelles

Repartition du temps de reponse si ρ "= (m − 1)/m F (r) =

sinon F (r) = 1 − (1 + γµr)e−rµ

Temps de reponse Moyen E(r) = 1µ(1 + γ

m(1−ρ) )

Variance du temps de reponse V (r) = 1µ2 (1 + γ(2−γ)

m2(1−ρ)2)

Repartition du temps d’attente F (w) = 1 − γe−wµm(1−ρ)

Temps d’attente moyen E(w) = γmµ(1−ρ)

Variance du temps d’attente V (w) = γ(2−γ)m2µ2(1−ρ)2

q-percentile du temps d’attente max(0, E(w)γ

ln( 100γ100−q

)


La file M/M/m/B

• Il y a B places et m serveurs. Donc B > m.

• Le processus du nombre de clients est encore un processus de naissance

et de mort dont les taux sont :

λi = λ ∀ i < B

λB = 0

µi = iµ si i ≤ m

µi = mµ si m < i ≤ B

(18)

• Puisque la chaıne a un nombre fini d’etats, le systeme est toujours

stable.


• Les probabilites stationnaires sont obtenues simplement :

πn =

π0λn

n! µn ∀ n < mπ0λn

m! mn−m µn ∀ n ≥ m(19)

• et π0 est obtenu par normalisation.

• Toutes les arrivees qui se produisent pendant que le buffer est dans

l’etat B sont perdues.

• Le taux d’arrivee reel est donc λ(1 − πB)

• le taux de perte est λπB .

• La formule de Little donne le temps moyen de sejour et le temps

moyen d’attente.

E(r) =E(n)

λ(1 − πB)et E(w) =

E(q)

λ(1 − πB)


La file M/M/m/B

Caracteristiques Spatiales

Charge ρ = λ/(mµ)

π0

(1 + (mρ)m(1−ρB+1−m

m!(1−ρ) +∑m−1

i=1(mρ)i

i!

)−1

Probabilite si k ≤ m π0(mρ)k

k!

d’avoir k clients sinon π0mmρk

m!

Nombre moyen de clients E(n) =∑B

i=1iπi

Nombre moyen de clients

en attente E(q) =∑B

i=m+1(i − m)πi

Taux d’arrivee reel λ(1 − πB)

Utilisation moyenne

d’un serveur ρ(1 − πB)

Taux de perte λπB


La file M/M/m/B

Caracteristiques Temporelles

Temps de reponse moyen E(r) = E(n)λ(1−πB)

Temps d’attente moyen E(w) = E(q)λ(1−πB)


Quelques exemples d’application

• Gateway

• Centre de calcul

• Bases de Donnees


Perte et Gateway par M/M/1

• Des paquets arrivent avec un taux de 125 paquets par seconde dans un

gateway

• Celui ci doit utiliser 2ms pour expedier un paquet.

• En utilisant un modele M/M/1, analyser l’element

• en particulier, trouver la probabilite de perte si le buffer est de taille 12

• et la taille pour que la probabilite soit inferieure a 10−6.


• λ = 125pps

• µ = 10.002 = 500pps

• ρ = 0.25

• Proba n paquets = (1 − ρ)ρn

• Nombre moyen de paquets dans le gateway = ρ1−ρ = 0.333

• Temps moyean de reponse = 1/µ1−ρ = 2.66ms

• On fait mainteant une approximation (buffer fini par buffer infini)

• Probabilite d’overflow = ρ13 = 1.510−8

• Taille : ρn ≤ 10−6 et donc n > 6log(0.1)/log(0.25)


Perte et Gateway par M/M/1/B

• On suppose maintenant qu’il n’y a que deux buffers

• π1 = 0.25π0 et π2 = 0.25 ∗ 0.25π0

• Donc, π0 = 11+0.25+0.0625 = 0.76 et π1 = 0.19 et π2 = 0.0476

• Donc le nombre moyen vaut: 0.19 + 2 ∗ 0.0476 = 0.29

• le taux d’arrivee effectif est : 125 ∗ (1 − π(2)) = 119pps

• et le taux de perte est de 6 pps...

• le temps moyen de reponse est de 2.4ms.


Quelques Lecons

• Augmenter la taille des buffers diminue les pertes

• Augmenter la taille des buffers augmente les delais

• Augmenter la taille des buffers augmente la gigue (la variation du

delai)

• Augmenter la taille des buffers augmente la latence (le premier delai)


Centre de Calcul

• Les etudiants se rendent au centre de calcul selon un processus de

Poisson avec un taux de 10 personnes par heure

• Chaque etudiant travaille 20mn en moyenne. La distribution du temps

de travail est exponentielle.

• Il y a 5 terminaux.

• Les etudiants disent qu’ils attendent trop.....

• Et que le centre de calcul est trop loin...


Analyse du centre par une M/M/5

• λ = 1/6 etudiant/minute

• µ = 1/20

• ρ = 0.666

• Utilisation moyenne d’un terminal = 0.6666

• la probabilite d’attente = probabilite que tous les terminaux soient

occupes = γ = π0(m∗ρ)m

m!(1−ρ) = 0.33

• Nombre moyen d’etudiants dans le centre = mρ + ργ1−ρ = 4.0


• Nombre moyen d’etudiants en attente = ργ1−ρ = 0.65

• Temps moyen de sejour dans le centre = 1/µ(1 + γm(1−ρ) ) = 24mn

• Qui se decomposent en 20 minutes de travail et 4 minutes d’attente...

• Mais 90-Percentile du temps d’attente = 14 minutes...(10 pourcents

des etudiants doivent attendre plus de 14 minutes).


Comment repondre

• Augmenter le nombre de terminaux

• Distribuer les terminaux (sans en augmenter le nombre)


Augmenter le nombre de terminaux

• Combien de terminaux pour que le temps d’attente soit plus petit que

2 minutes en moyenne et plus petit que 5 minutes dans 90 pourcents

des cas ?

• On augmente de 1 terminal. (m=6)

• ρ devient 0.556, γ = 0.15,

• Temps moyen d’attente = 1.1 minute

• 90 percentile = 3 minutes


Repartition

• On distribue les 5 terminaux en 5 places distinctes, avec 5 files

d’attente separees et pas d’informations globales pour choisir.

• On a donc 5 M/M/1

• Le taux de service reste identique

• Le taux d’arrivees est divisee par 5 (repartition equiprobable)


• La charge ρ reste la meme

• Le temps moyen de sejour est 1/µ1−ρ = 60mn

• La variance du temps de sejour est maintenant de 3600 (elle etait de

479 dans le systeme centralise).

• Tres mauvaise solution : le temps moyen de sejour augmente

considerablement (moyenne comme variance).


Autre Lecon

• En premiere analyse, un systeme centralise est plus efficace pour

l’utilisation des ressources et le temps d’attente

• La difference provient des etats ou certaiens files sont vides alors que

des clients attendent dans d’autres

• Mais d’autres points peuvent modifier cette analyse.


Requetes dans un SGBD

• Arrivees selon un processus de Poisson de taux 30 req par seconde.

• Chaque requete prend 0.02 seconde de traitement

• Donc le taux de service est de 1/0.02 = 50 requetes par seconde

• Analyse par une M/M/1

• La charge est de 0.6

• Le serveur est vide pendant 40 pourcent du temps

• Le nombre moyen de requetes est 1.5

• Donc le temps moyen de reponse est 0.05 seconde


Changeons la vitesse du serveur

• La vitesse du serveur double

• La charge devient 0.3

• Le serveur est vide 70 pourcent du temps

• Mais le temps moyen de reponse passe a 0.014 (il a ete divise par plus

de 3)


Resolution Numerique DTMC, Pb Stationnaire

Chaınes finies

Calcul de la distribution stationnaire π

Solution de :

ΠQ = 0 Πe = 1 En Temps Continu (20)

ΠP = Π Πe = 1 En Temps Discret (21)

On suppose que la solution existe


Plan

• Methodes directes

• Methodes iteratives

• Methodes recursives

• Methodes par decomposition

• Lumpabilite


Uniformisation

On peut transformer les matrices pour passer d’un probleme en temps

continu en un probleme en temps discret.

• Soit Q un generateur

• Posons δ = maxi=1..n(|Q(i, i)|)

• Soit ε ≥ 0

• Definissons Pε = Id + Q(δ + ε)−1

• Propriete 1 Pε est une matrice stochastique qui a la meme mesure

invariante que Q.


Preuve :

1. Pε admet Π comme mesure invariante

ΠPε = ΠId + ΠQ(δ + ε)−1 = Π (22)

2. Tous les elements hors diagonaux de Pε sont positifs car ils sont la

somme d’elements positifs.

3. Tous les elements diagonaux de Pε sont positifs : en effet,

−1 ≤Q(j, j)

ε + maxi|Q(i, i)|≤ 0 (23)

4. Pour tout i :∑j

Pε(i, j) =1

ε + δ

∑j

Q(i, j) +∑

j

Id(i, j) = 0 + 1 = 1


Choix de ε

• Une valeur strictement positive de ε implique que Pε a des elements

diagonaux non nuls; elle est donc aperiodique.

• ε permet de changer le spectre de la matrice Pε. Attention aux

methodes iteratives

• Lorsque ε tend vers l’infini, toutes les valeurs propres de Pε tendent

vers 1 en module

• Prendre ε petit, heuristique de Wallace (solveur RQA) ε = δ/100.


Methodes directes

• Resolution d’un probleme lineaire

• Variante de l’elimination de Gauss

• Choisir la variante la plus precise, la complexite est toujours cubique

pour des matrices pleines

• L’elimination a pour consequence de remplir la matrice si elle etait

initialement creuse

• algorithme GTH : beaucoup plus stable numeriquement car il n’y a ni

nombres negatifs ni soustractions


GTH

• Du nom des ses auteurs : Grassman, Taksar et Heyman

• Idee : oter les sommets depuis le dernier

• Equilibre en n :

Πn(n−1∑i=1

P (n, i)) =n−1∑j=1

P (j, n)Πj (24)

• Equation d’equilibre d’un sommet a successeur de n dans la chaine de

Markov

Πa(n∑

i=1

P (a, i)) =n−1∑j=1

P (j, a)Πj + P (n, a)Πn (25)

• Remplacons Πn par sa valeur.


Πa(n∑

i=1

P (a, i)) =n−1∑j=1

P (j, a)Πj +

∑n−1j=1 P (j, n)P (n, a)Πj∑n−1

i=1 P (n, i)(26)

• Posons R(j, a) = P (j, a) + P (j,n)P (n,a)∑n−1

i=1P (n,i)

.

• R est une matrice stochastique de taille n − 1

• Il est possible que P (j, a) soit nul et que R(j, a) ne le soit pas. Il suffit

qu’il y ait, dans la chaıne de Markov, une transition de j a n et une

autre de n a a.

• R est moins dense que la matrice P et on doit modifier la structure des

elements non nuls de P pour construire R.

• Le choix du sommet a eliminer est important pour minimiser le

remplissage de la matrice


Code de GTH

program gth(input,output);

begin

for n:=nr downto 1 do begin

S:=0;

for j:=0 to n-1 do S:=S+P[n,j];

for i:=0 to n-1 do P[i,n]:=P[i,n]/S;

for i:=0 to n-1 do for j:=0 to n-1 do

P[i,j]:=P[i,j]+P[i,n]*P[n,j];

if S<=0.0 then writeln(’erreur’, n) else writeln(n);

end;

Tot:=1;

pi[0]:=1;

for j:=1 to nr do begin

pi[j]:=P[0,j];

for k:=1 to j-1 do pi[j]:=pi[j]+pi[k]*P[k,j];

Tot:=Tot+pi[j];

end;

for j:=0 to nr do pi[j]:=pi[j]/Tot;

end gth.


Comparaison GTH-QR

• En simple precision...

• Le resultat ”exact” est fourni par un algorithme en double precision

• On calcule les erreurs absolues sur GTH et les erreurs absolues min et

max pour QR (ca depend de la colonne enlevee)


Exemple : matrice petite, probabilites fortes

P =

0.2 0 0 0.6 0 0 0 0 0 0.2

0 0.1 0 0 0.6 0 0.3 0 0 0

0 0.1 0 0 0 0 0 0.8 0 0.1

0 0 0.6 0 0.3 0 0 0 0 0.1

0 0.5 0 0 0.5 0 0 0 0 0

0 0.5 0 0 0.2 0 0 0 0.3 0

0 0 0 0 0.7 0 0.2 0 0 0.1

0.1 0 0.9 0 0 0 0 0 0 0

0 0.1 0 0 0 0.8 0 0 0 0.1

0 0.4 0 0 0 0.4 0 0 0 0.2

(27)

erreur-GTH erreur-min-QR erreur-max-QR

4.510−8 6.910−8 3.710−6


Autre exemple : petite matrice mais probabilites assez faibles...

P =

1 − 10−6 10−7 2 10−7 3 10−7 4 10−7

0.4 0.3 0 0 0.3

5 10−7 0 1 − 10−6 0 5 10−7

5 10−7 0 0 1 − 10−6 5 10−7

2 10−7 3 10−7 10−7 4 10−7 1 − 10−6

(28)

erreur-GTH erreur-min-QR erreur-max-QR

3.1 10−8 6.12 10−3 3.89 10−2


Conclusions-methodesdirectes

• Avantages

– Complexite fixe independante des donnees

– Stabilite numerique (GTH)

– Facile a implementer

• Inconvenients

– Complexite cubique en temps, quadratique en espace pour les

matrices pleines

– Peu adaptees aux structures creuses

• Pour des matrices de taille inferieure a 1000


Methodes iteratives

• Resolution d’un probleme de vecteur propre

• Variantes de la methode des puissances

x(k+1) =1

λ1x(k)A (29)


Methode des Puissances

• Soit (λ1, λ2, ..., λn) les vecteurs propres a gauche de la matrice A,

ordonnees par ordre decroissant en module

• Supposons |λ1| > |λ2|

• Les vecteurs propres (y1, ..yn) forment une base; exprimons x(0) dans

cette base.

x(0) =n∑

i=1

αiyi (30)

On suppose que α1 += 0.

• puisque λi est valeur propre associee a yi, on a :

x(1) =1

λ1x(0)A =

1

λ1

n∑i=1

αiyiA =1

λ1

n∑i=1

αiλiyi (31)


Plus generalement :

x(k+1) = (1

λ1)kx(0)Ak =

n∑i=1

αi(λi

λ1)kyi (32)

On separe le premier terme :

x(k+1) = α1y1 + (n∑

i=2

αi(λi

λ1)kyi (33)

• Puisque toutes les valeurs propres a partir de la seconde sont

strictement inferieures a λ1, tous les termes de la somme tendent vers

0.

• L’iteration a pour limite un vecteur propre de A associe a λ1.

• Mais la vitesse de convergence depend des autres valeurs propres et

surtout de la seconde.


Application aux chaınes de Markov

• Iterer :

Π(n+1) = Π(n)P (34)

• Inutile de normaliser car λ1 = 1

• temps de convergence trop long : ameliorations necessaires


Ameliorer

• pour resoudre xA = b par des iterations successives,

• si on peut trouver une decomposition de A en M − N ou M est

facilement inversible, alors

xM = xN + b (35)

et grace a l’inversibilite de M ,

x = xNM−1 + bM−1 (36)

• Ce qui conduit au schema iteratif simple :

x(n+1) = x(n)NM−1 + bM−1

• La matrice H = NM−1 est la matrice de l’iteration.


• Pour la suite, on cherche a resoudre le probleme transpose et en temps

continu, c’est a dire :

QtΠt = 0 (37)

• On suppose que le generateur Qt est decompose en une matrice

diagonale D, une matrice triangulaire inferieure L et une matrice

triangulaire superieure U .

Qt = D − (L + U) (38)


Jacobi

• M = D et N = L + U

• H = D−1(L + U)

• Sous forme scalaire:

x(n+1)i =

1

di,i{∑j &=i

(li,j + ui,j)x(n)j } (39)


Gauss-Seidel

• Les valeurs de la nouvelle iteration x(n+1)j pour j < i peuvent etre

utilises a la place des valeurs de l’iteration (n), pour calculer x(n+1)i .

• Operateur H = (D − L)−1U

• Iteration

x(n+1)i =

1

di,i{∑j<i

li,jx(n+1)j +

∑j>i

ui,jx(n)j } (40)

• Gauss Seidel ascendante (ci-dessus) ou descendante (H vaut

(D − U)−1L)

• La vitesse de convergence peut dependre de l’ordre des variables.


S.O.R.

• La methode de relaxation (SOR) consiste a effectuer, pour l’iteration

(n + 1), une moyenne ponderee entre le resultat de l’iteration (n) et

l’application de l’iteration de Gauss Seidel

• Iteration :

x(n+1)i = (1 − ω)x(n)

i + ω

1

di,i{∑j<i

li,jx(n+1)j +

∑j>i

ui,jx(n)j }

(41)

• Operateur : Hw = (D − ωL)−1((1 − ω)D + ωU)

• Choisir une valeur correcte de ω est un probleme difficile.

• ω peut modifier la valeur propre dominante de l’operateur Hw


program GaussSeidel(input,output);

type element = record ori : integer; prob : real; end;

var nz,n,i,c,j, degre,iter : integer; diff,som,y : real;

p,op : array[0..nodemax] of real;

debut : array[0..nodemax] of integer;

arc : array[0..arcmax] of element;

begin

readln(nz); readln(n); c:=0;

for i:=0 to n-1 do begin

read(degre); debut[i]:=degre;

for j:=1 to degre do begin

read(arc[c].prob); read(arc[c].ori); c:=c+1;

end;

readln; op[i]:=1;

end;

iter:=0; som:=0.0; for i:=0 to n-1 do som:=som+op[i];

for i:=0 to n-1 do op[i]:=op[i]/som;

repeat

iter:=iter+1; c:=0;

for i:=0 to n-1 do begin

som:=0.0;

for j:=c to c+debut[i]-1 do begin

if arc[j].ori > i then y:= op[arc[j].ori] else y:= p[arc[j].ori];

som:=som+op[arc[j].ori]*arc[j].prob;

end;

p[i]:=som; c:=c+debut[i];

end;

som:=0.0; for i:=0 to n-1 do som:=som+p[i]; for i:=0 to n-1 do p[i]:=p[i]/som;

diff:=0.0; for i:=0 to n-1 do diff:=diff+abs(p[i]-op[i]);

op:=p;

until (iter=maxiter) or (diff<maxdiff);

for i:=0 to n-1 do writeln(p[i]);

end.


Comparaisons

• le cout d’une iteration est a peu pres le meme

• le nombre d’iterations depend du spectre de H mais on ne sait pas

comment il a ete change.


Exemple 1 : Pb de Courtois

P =

0.85 0 0.149 9 10−4 0 5 10−5 0 5 10−5

0.1 0.65 0.249 0 9 10−4 5 10−5 0 5 10−5

0.1 0.8 0.0996 3 10−4 0 0 10−4 0

0 4 10−4 0 0.7 0.2995 0 10−4 0

5 10−4 0 4 10−4 0.39 0.6 10−4 0 0

0 5 10−5 0 0 5 10−5 0.6 0.2499 0.15

3 10−5 0 3 10−5 4 10−5 0 0.1 0.8 0.0999

0 5 10−5 0 0 5 10−5 0.1999 0.25 0.55

Methode Iterations pour 10−6

Puissance 69000

Jacobi 23000

Gauss Seidel 11000

SOR opt 3500

C’est un probleme NCD...


Exemple 2

2 classes de composantes avec 2 composantes par classe. Les composantes

de type 1 (resp. 2) tombent en panne avec le taux λ1 (resp. λ2), et sont

reparees avec le taux µ1 (resp. µ2).

Etats (X, Y ) classes par ordre lexicographique ou X (resp. Y ) est le

nombre de composantes de type 1 (resp. type 2) en activite.

Q =

∗ 2λ2 2λ1

µ2 ∗ λ2 2λ1

2µ2 ∗ 2λ1

µ1 ∗ 2λ2 λ1

µ1 µ2 ∗ λ2 λ1

µ1 2µ2 ∗ λ1

2µ1 ∗ 2λ2

2µ1 µ2 ∗ λ2

2µ1 2µ2 ∗

(42)

Independence entre les deux composantes; Calcul analytique exact de la

solution; comparaison des solutions


λ1 = 0.2, λ2 = 0.3, µ1 = 5.0, µ2 = 6.0

Methode 2eme valeur propre Iterations pour 10−6

Puissance 0.76 52

Jacobi 1.0 Diverge

Gauss Seidel 0.072 6

SOR opt 0.018 6


λ1 = 0.2, λ2 = 30.0, µ1 = 0.5, µ2 = 60.0

Methode 2eme valeur propre Iterations pour 10−6

Puissance 0.9942 2375

Jacobi 1.0 Diverge

Gauss Seidel 0.9827 790

SOR opt 0.7677 53

C’est un probleme NCD...


Initialisation

• Ne pas initiliser le vecteur de probabilites par un 1.0 pour le plus petit

etat dans une methode de Gauss Seidel ascendante.

• Employer une approximation pour choisir un vecteur initial proche de

la solution


Conclusions-methodes iteratives

• Avantages

– La complexite d’une iteration est le nombre d’element non nuls de P

– Stabilite numerique (on ne fait que des additions)

– adaptees aux matrices creuses

• Inconvenients

– La complexite en nombre d’iterations depend du spectre (et donc

des donnees)

• Pour des matrices creuses de grande taille dont la seconde valeur

propre est faible


Methode par Recursion

• Construire un systeme recursif sur les probabilites de maniere a les

calculer a un facteur multiplicatif pres qui est obtenu par

normalisation.

• Depend de la structure de la matrice, pas des valeurs numeriques

distinctes de 0.


Matrices Hessenberg

• Hessenberg Superieure : triangle superieur + sous diagonale principale;

Chaıne Incluse aux instants de depart de la G/M/1

. . . . .

. . . . .

0 . . . .

0 0 . . .

0 0 0 . .

• Hessenberg Inferieure : triangle inferieur + sur diagonale principale;Chaıne Incluse aux instants d’arrivees de la M/G/1

. . 0 0 0

. . . 0 0

. . . . 0

. . . . .

. . . . .


Principe pour une Hessenber sup

• Equilibre en j :

πj =j+1∑i=0

πiPi,j

• On en deduit πj+1

πj+1 =1

Pj+1,j

[πi(1 − Pj,j) −

j−1∑i=0

πiPi,j

]

Si Pj+1,j est non nul.

• Cas fini : on pose π0 = 1, on effectue la recurence, on somme toutes les

probabilites et on normalise.

• Cas Infini : il faut que P soit reguliere.


Matrices Block Hessenberg

• Meme structure que les matrices Hessenberg mais par bloc.

Q =

Q0,0 Q0,1 . . .

Q1,0 Q1,1 Q1,2 . .

0 Q2,1 Q2,2 . .

0 0 Q3,2 . .

0 0 0 . .

• Qi,j blocs de taille k × k

• π divise en sous vecteurs de taille k


Algorithme

• Equilibre pour le bloc 0

π0Q0,0 + π1Q1,0 = 0

• Si Q1,0 est inversible

π1 = −π0Q0,0Q−11,0

• Equilibre pour le bloc 1

π0Q1,0 + π1Q1,1 + π2Q2,1 = 0

• Si Q2,1 est inversible

π2 = (π0Q1,0 + π1Q1,1)Q−12,1

• Apres simplification


π2 = π0(Q1,0 + Q0,0Q−11,0Q1,1)Q

−12,1

• On peut continuer... si Qi+1,i est inversible (recursion descendante)

• Si lower block Hessenberg et Qi,i+1 inversible, alors recursion

ascendante

• Si bloc tridiagonal, on peut essayer les deux sens de recursion.


Exemple : M/C2/1/N

• Arrivees Poisson λ, Service Cox a deux phases (µ1, µ2, a)

• Etats (x, y), x : nombre de clients, y : phase du service.

• (0, 2) etat transitoire. N places dans la file

∗ 0 λ 0

0 ∗ 0 λ

(1 − a)µ1 0 ∗ aµ1 λ 0

µ2 0 0 ∗ 0 λ

(1 − a)µ1 0 ∗ aµ1 λ 0

µ2 0 0 ∗ 0 λ

(1 − a)µ1 0 ∗ aµ1

µ2 0 0 ∗

• Blocs sousdiagonaux non inversibles,

• Blocs surdiagonaux inversibles

• Analyse ascendante


Calcul de π(0, 1)

λ = 0.5, µ1 = 1.0, µ2 = 10.0

N Calcul Recursif GTH

2 0.0007158 idem

5 0.0006958 idem

10 0.0006955 idem

16 0.0006808 0.0006955

20 -0.1973 0.0006955

Une probabilite negative ????


Residus πQ

N Residus

2 10−16

3 10−15

5 10−13

10 10−9

12 10−7

16 10−3

20 50.9

Croissance geometrique avec N des erreurs


Raison de l’instabilite

• λ < µ1 et λ << µ2

• Les blocs Qi,i

1/λ 0

0 1/λ

et Qi−1,i

1/λ 0

0 1/λ

ont une norme

tres grande

• A chaque iteration, les erreurs sont multipliees par cette norme.


Conclusions-methodes recursives

• Avantages

– Utilisation de la structure de la matrice

– Problemes de tres grande taille

– associee a des files usuelles

• Inconvenients

– Probleme de stabilite numerique

• Pour des matrices creuses de grande taille quasi Hessenberg


Methodes de Decomposition

Definition 9 une matrice stochastique P est presque completement

decomposable (NCD) ssi on peut decomposer la matrice en blocs Pi,j tels

que :

1. ‖Pi,i‖1 = O(1), ∀i

2. ‖Pi,j‖1 = O(ε), ∀i, j, i += j

3. ε << 1

P =

P1,1 P1,2 P1,3 P1,4 P1,5

P2,1 P2,2 P2,3 P2,4 P2,5

P3,1 P3,2 P3,3 P3,4 P3,5

P4,1 P4,2 P4,3 P4,4 P4,5

P5,1 P5,2 P5,3 P5,4 P5,5

(43)


Approche de Courtois

• Solutions locales

• Matrice de couplage

• Approximations


Solutions Locales de Pi,i

• Chercher ui le vecteur propre normalise a 1 et associe a la valeur

propre dominante de Pi,i.

uiPi,i = λiui

• Cette valeur propre est inferieure a 1 mais tres proche de 1.

• ui(j) est une approximation de la probabilite conditionelle d’etre dans

le sommet d’indice j sachant que l’on est dans le bloc i.


Couplage

• A∗ : Matrice de couplage entre bloc : probabilite d’aller du bloc i au

bloc j

• Etape 1 : sommer les colonnes d’un bloc pour obtenir la probabilite

d’aller d’un etat vers un bloc : Pi,je

• Etape 2 : ponderer les lignes par les poids des ui(k) (probabilite d’etre

dans l’etat k quand on est dans le bloc i)

A∗(i, j) = uiPi,je

• ξ(i) est la probabilite stationnaire de la matrice A∗

ξA∗ = ξ


Approximation NCD

• l’etat x correspond a l’etat k de la composante i

• ui(k) approxime la probabilite d’etre dans l’etat k sachant que l’on est

dans la composante i

• ξ(i) est la probabilite d’etre dans la composante i

π(x) = ui(k)ξ(i)


Algorithme MKS

• Iterer l’approche de Courtois

• Mais agreger les probabilites π calculee par l’equation de

decomposition redonne la quantite ui(.) precedemment calculee.

• L’algorithme modifie π par une simple iteration de la methode de

Gauss-Seidel

• Inutile de calculer les solutions locales, il suffit d’initiliser par une

distribution uniforme


1. Choisir une solution initiale π(0)(x, y). x designe le numero de

l’agregat, y le numero de l’etat dans l’agregat. m designe le compteur

d’iterations. Il est initialise a 0.

2. Calculer les probabilites conditionnelles ui(j) d’etre dans l’etat y

sachant que l’on est dans l’agregat x.

ui(j)(m) =

π(m)(i, j)∑k π(m)(i, k)

(44)

3. Construire la nouvelle matrice de couplage A(m) :

A(m)(i, j) = u(m)i Pi,je (45)

4. Calculer la mesure invariante ξ(m) de A(m).

5. Calculer la nouvelle approximation de la distribution stationnaire

z(m)(x) = ui(j)(m)ξ(i)(m) avec x = (i, j) (46)


6. Perturber z(m) pour obtenir π(m) par une iteration de Gauss Seidel

π(m)(k) = π(m)(k)Pk,k +∑j<k

π(m)(j)Pj,k +∑j>k

z(m)(j)Pj,k

7. Verifier la convergence et dans le cas negatif incrementer m et

recommencer a l’etape 2


Pb de Courtois

P =

0.85 0 0.149 9 10−4 0 5 10−5 0 5 10−5

0.1 0.65 0.249 0 9 10−4 5 10−5 0 5 10−5

0.1 0.8 0.0996 3 10−4 0 0 10−4 0

0 4 10−4 0 0.7 0.2995 0 10−4 0

5 10−4 0 4 10−4 0.39 0.6 10−4 0 0

0 5 10−5 0 0 5 10−5 0.6 0.2499 0.15

3 10−5 0 3 10−5 4 10−5 0 0.1 0.8 0.0999

0 5 10−5 0 0 5 10−5 0.1999 0.25 0.55

Approximation de Courtois : l’approximation est de l’ordre de 10−4.

u1 = (0.401, 0.416, 0.182), u2 = (0.5714, 0.4286), u3 = (0.240, 0.555, 0.204)

A∗ =

[0.99911 0.00079 0.0001

0.00061 0.99929 0.0001

0.00006 0.00004 0.9999

]

Algorithme MKS : en 4 iterations les residus sont de l’ordre de 10−16.


Conclusions-methodes de decomposition

• Avantages

– Traitement efficaces de problemes de grande taille

– Adaptees aux matrices NCD

– Problemes realistes (plusieurs echelles de temps)

• Inconvenients

– Detection de la structure NCD (algorithme de connexite)

• Pour des matrices creuses de grande taille NCD


Lumpabilite ordinaire

• Par rapport a une partition de l’espace des etats,

S = A1 ∪ A2 ∪ . . . ∪ Ak

• Critere de lumpabilite ordinaire :

∀l, m, ∀a, b ∈ Am

∑j∈Al

P (a, j) =∑j∈Al

P (b, j)

• Alors on peut definir la chaine dont les etats sont les Ai (les

macro-etats) et resoudre la chaine agregee.


Lumpabilite : exemple

• On commence par un exemple : taille 4, partition en deux sous

ensmbles.

π1 = P (1, 1)π1+ P (2, 1)π2+ P (3, 1)π3+ P (4, 1)π4

π2 = P (1, 2)π1+ P (2, 2)π2+ P (3, 2)π3+ P (4, 2)π4

π3 = P (1, 3)π1+ P (2, 3)π2+ P (3, 3)π3+ P (4, 3)π4

π4 = P (1, 4)π1+ P (2, 4)π2+ P (3, 4)π3+ P (4, 4)π4

• Regroupons les equations 1 et 2 d’une part, 3 et 4 de l’autre.

π1 + π2 = (P (1, 1) + P (1, 2))π1+ (P (2, 1) + P (2, 2))π2

+ (P (3, 1) + P (3, 2))π3+ (P (4, 1) + P (4, 2)π4

• Lumpabilite ordinaire : la somme en colonne est constante :

P (1, 1) + P (2, 1) = P (2, 1) + P (2, 2). Donc on peut factoriser.


Lumpabilite exacte

• Par rapport a une partition de l’espace des etats,

S = A1 ∪ A2 ∪ . . . ∪ Ak

• Critere de lumpabilite exacte :

∀l, m, ∀a, b ∈ Am

∑j∈Al

P (j, a) =∑j∈Al

P (j, b)

• Alors on peut simplifier la resolution en supposant que toutes les

probabilites dans un macro-etat sont egales.


• Fin de la parenthese Analyse Numerique

• Retour aux methodes analytiques

• Apres un exemple surprenant d’application !


Google

• Comment trouver les pages ?

• Un robot d’exploration et une indexation

• Comment classer les pages pour trouver les plus pertinentes

• algorithme PAGERANK


Fondamentaux de PageRank

• Hypothese 1 : une page pertinente est pointeee par des pages

pertinentes au moyen de son URL.

• Hypothese 2 : on quantifie la pertinence par un flottant positif.

• Hypothese 3 : si une page source pointe vers k pages destinations

(grace a leurs URL), alors chacune recoit 1/k de la pertinence de la

source.

• Hypothese 4 : Une page sans lien de sortie n’est pas pertinente


Quantification simplifiee

• Soit Γ(x) les pages qui pointent sur x

• Soit d(y) le nombre de pages pointees par la page y

• Soit Pe(x) la pertinence de la page x, on obtient,

Pe(x) =∑

y∈Γ(x)

Pe(y)

d(y)

• ou encore, en posant M(y, x) = 1d(y)

Pe(x) =∑

y∈Γ(x)

Pe(y)M(y, x)

• On reconnait la definition de la probabilite stationnaire d’une chaine

de Markov.


Pe = π

• La pertinence est donc egale a la probabilite stationnaire (a une

constante multiplicative pres)

• Inutile de calculer la valeur exacte

• On utilise un algorithme iteratif et on s’arrete avec une precision faible

• On reemploie la distribution initiale precedente lorsqu’on recalcule les

pertinences apres avoir reconstruit un nouvel index.


En fait

• Le systeme est legerement different (plus stable pour la convergence)

Pe(x) = 0.15 + 0.85 ∗∑

y∈Γ(x)

Pe(y)

d(y)

• On peut en deduire comment influencer PageRank et Google.

• L’information est disponible sur le Web (par exemple

http://www.webworkshop.net/pagerank.html)


Se passer de l’hypothese Markov

• Un resultat physique : Little

• Analyse operationnelle

• Simulation Monte Carlo (espace)

• Simulation de processus (temps)


Analyse Operationnelle

• Quelques lois operationnelles

• sur des quantites mesurables (simulations, mesures)

• sans hypotheses probabilistes ou statistiques

• permettant de faire des tests

• et de borner les performances pour valider une premiere analyse.


Quantites Concernees

• Taux d’arrivees, λi: c’est le nombre d’arrivees sur le temps: Ai

T

• Debit, Xi: c’est le nombre de travaux termines sur le temps: Ci

T

• Utilisation, Ui: c’est le temps utilise par les services sur le temps: Bi

T

• Temps moyen de service, Si: c’est le temps utilise par les services sur

le nombre de travaux termines: Bi

Ci


Plan

• Utilisation

• Conservation de Flux

• Formule de Little

• Temps de reponse

• Systemes interactifs

• Bottleneck (engorgement)


Utilisation

• Par definition

Ui =Bi

T=

Ci

T

Bi

Ci

• et donc Ui = XiSi

• L’utilisation est le produit du temps moyen de service par le debit.


Conservation de Flux

• Conservation Entrees Sorties:

• Lorsque T devient grand

• si le systeme est stable,

• alors il y a conservation entre entrees et sorties d’un systeme.

Ai = Ci


Conservation et Routage

• Un job se decompose en taches elementaires et ne quitte le systeme

que lorsqu’elles sont toutes terminees.

• Il demande Vi taches au serveur i

• C0 est le flux entrant dans le systeme (et le flux sortant si le systeme

est stable)

• Donc chaque serveur recoit Ci = ViC0 taches.


• Le debit du systeme est par definition X = C0T

• Le debit du serveur i est Xi = Ci

T = Ci

C0

C0T

• Donc

Xi = XVi

• Loi de conservation du flux


• Puisque l’utilisation Ui vaut par definition XiSi, on a:

Ui = XiSi = XViSi

• On pose Di = ViSi.

• Di est la charge induite par un job

• Le bottleneck est le serveur qui a la charge la plus elevee

• le nombre maximal de job executables est obtenu lorsque la serveur en

bottleneck a une utilisation de 1.


Exemple

• Chaque job demande 5 secondes de CPU, 80 acces sur le disque A et

100 acces sur le disque B.

• Entre chaque job, l’utilisateur attend 18 secondes.

• un acces disque sur A dure 50 ms, et sur B 30 ms.

• Il y a 17 terminaux connectes

• On mesure un debit de 15.7 acces par seconde sur le disque A

• Calcul du debit et de l’utilisation de la CPU et des disques.


Donnees Initiales

• DCPU = 5s

• VA = 80

• VB = 100

• SA = 0.05s

• SB = 0.03s

• XA = 15.7


Utilisations

• DA = SAVA = 4s

• DB = SBVB = 3s

• Donc la CPU est le bottleneck.

• On reprendra l’exemple pour finir....


Specification du routage par des probabilites

• Pi,j est la probalilite d’aller en j apres avoir termine un travail en i.

• Equation de flux : Cj =∑

i CiPi,j

• Donc Vj =∑

i ViPi,j et V0 = 1


Formule de Little

Soit Z un systeme dans lequel arrive des objets. Ces objets demeurent un

certain temps dans le systeme puis sortent de Z.

• N est le nombre moyen d’objets dans Z

• T est le temps moyen passe dans Z par un objet

• λ est le taux d’arrivee en Z des objets.

N = λT (47)


Preuve de Little pour une simulation avec retour a 0

Considerons une trajectoire du systeme. Observons le systeme lorsqu’il se

vide pour la n-ieme fois a l’instant x. Il etait vide a l’origine. Il y a eu m

objets visiteurs entre 0 et x.

Soient ai et di la date d’arrivee et de depart du i-eme client. Le temps de

sejour du i-eme client vaut wi = di − ai.

T est la moyenne des wi.

T =

∑mi=1 wi

m

N(t) est le nombre d’objets a la date t.

N =

∫ xt=0 N(t)dt

x


Preuve de Little pour une simulation avec retour a 0 - suite

x

N

Figure 6: Trajectoire avec retour a 0

Soit S la surface engendree par la trajectoire entre 0 et x.


Preuve de Little pour une simulation avec retour a 0 - suite

Calcul de S dans les deux sens (vertical et horizontal)

• S =∫ x

t=0 N(t)dt = x × N

• S =∑m

i=1 di − ai = m × T

Donc, N = mx T

et par definition λ = mx


Consequence imprevue de la preuve

Autre Consequence : S =∑m

i=1 dα(i) − ai pour toute permutation α qui

garantisse la coherence de la trajectoire (c’est a dire que les arrivees sont

avant les departs).

La moyenne de la duree de sejour est independante de l’ordre de sortie

pour les disciplines conservatives.

Simplification importante pour la simulation ou pour l’analyse : changer la

discipline de service pour la rendre plus simple si on ne s’interesse qu’a la

moyenne du temps de sejour.

Discipline plus simple : simulation plus rapide car il y a moins d’etats ou

analyse plus simple.


Temps de reponse

• Grace a la formule de Little on obtient:

Qi = XiRi

• Qi nombre moyen de clients dans le serveur i

• et Ri temps moyen de reponse du serveur i.

• car λi = Xi si le serveur est stable.

• Ui = XiSi est la formule de Little appliquee sur le serveur sans la file.


Composition des temps de reponse

• Un job se decompose en taches elementaires et ne quitte le systeme

que lorsqu’elles sont toutes terminees.

• Vi passage par job dans la station i

• le temps de reponse total est:

R =∑

i

ViRi


Systemes interactifs

• A la fin d’un job, le resultat est rendu a l’utilisateur qui attend un

certain delai (thinking time Z) avant de recommencer un nouveau job.

• Le temps total de cycle est R (sejour du job) plus Z

• Le taux de generation de job pour un utilisateur est 1Z+R

• Si il y a N utilisateurs, on en deduit

X =N

R + Z

• Et donc,

R =N

X− Z

• c’est la loi du temps de reponse pour les systemes interactifs


Bornes asymptotiques et analyse de bottlenecks

• On cherche le bottleneck (la station de Di maximale).

• Soit b cette station, on a Ub = XDmax et Ub ≤ 1.

• Donc X ≤ 1Dmax

• De plus, R ≥ D


• En apppliquant la loi du temps de reponse des systemes interactifs, on

a:

R =N

X− Z ≥ NDmax − Z

X =N

R + Z≤

N

D + Z

• Ce qui donne les deux formules de bornes asymptotiques

X ≤ min(1

Dmax,

N

D + Z)

R ≥ max(D, NDmax − Z)


Revenons sur l’exemple

• N = 17

• D = 3

• Dmax = 5


Bornes Asymptotiques

Figure 7: Bornes de X en fonction de N


Bornes Asymptotiques

Figure 8: Bornes de R en fonction de N


Fin de l’exemple

• X = XA

VA= 0.1963

• Vcpu = 100 + 80 + 1 car chaque visite a un disque est precedee d’un

passage par la CPU

• XCPU = XVcpu = 35.48

• XB = XVB = 19.6

• Ucpu = XDcpu = 0.98

• Ua = XDa = 0.784

• Ub = XDb = 0.588

• R = N/X − Z = 68, 6s

• X ≤ min(N/30, 1/5)


Fiabilite d’un reseau et Monte Carlo

On considere un reseau (sommets, arcs). Il y a deux sommets particuliers s

et t (extremites du reseau).

• Les sommets sont fiables.

• Les arcs peuvent tomber en panne (proba 1 − qi).

• Pannes independantes.

yi = 1 : arc OK (0 sinon).

y = (y1, ..., yn) un etat du reseau. q le vecteur (q1, ..., qn).

φ(y) vaut 1 si on peut connecter s a t par le reseau lorsque la configuration

de panne y se produit.


Probabilite d’une configuration de panne

P (y, q) =∏

i

qyi

i (1 − qi)1−yi

On veut calculer g(q) =∑

y φ(y)P (y, q)

Probleme difficile: il n’y a pas d’algorithme pour calculer g(q) en un temps

polynomial (en fonction des tailles du probleme).

Monte Carlo : comment representer le probleme comme un calcul de

volume ?



Simulation Sans Interaction

• Simulation d’un processus

(le temps et l’espace sont pris en compte)

• Simulation d’une variable aleatoire : Monte Carlo

seul l’espace est pris en compte


Methodes de Monte Carlo

Version elementaire

• Calculer l’integrale d’une fonction eventuellement difficile sur une

region peu reguliere.

• Compter des objets verifiant une propriete, objets issus d’un ensemble

fini de taille m mais ou la complexite de generation est exponentielle

en m.


Algo : Volume

• j := 1; S := 0;

• tant que j ≤ n faire

– Generer x(j) uniforme sur [0, 1]m

– si x(j) ∈ R alors φ = 1 sinon φ = 0

– S := S + φ;j := j + 1;

Plus rapide a converger que la version deterministe si m > 2.

Hypothese : x(j) ∈ R est relativement facile a calculer.


Algorithme

• On commence par calculer la connectivite c entre le source et la

destination (algorithme de flot max)

• Toute configuration avec moins de c pannes ne deconnecte pas le

reseau.

• Donc on generera uniquement les configurations avec au moins c

pannes.

• La fonction φ se calcule par un algorithme d’atteignabilite (DFS ou

BFS)


Generation d’entiers uniformes

Dispositif Physique ou Algorithme :

Probleme de la reproductibilite : pouvoir reproduire la sequence et donc la

trajectoire (par exemple pour debugger...)

Probleme du Test : pouvoir tester la sequence et ses proprietes statistiques.

On choisit d’utiliser un algorithme...


Principe de Base

Utiliser une fonction f a n arguments pour generer la prochaine valeur.

Les arguments sont les n valeurs precedentes de la serie.

xn+k = f(xn+k−1, xn+k−2, . . . , xk)

• Il faut n valeurs pour initialiser le processus (graines, semences, seed)

• Comportement cyclique potentiel. Si on retombe sur une serie de n

valeurs deja calculees, alors la suite de la serie est la meme.

• La longueur du cycle depend de la fonction mais aussi des racines.


Informatique :

les entiers et des reels informatiques sont codes sur un support fini.

Consequence :

La sequence est finie, periodique et deterministe


La generation de nombres uniformes est une des fonctions les plus utilisees

dans la dynamique de la simulation.

Probleme d’efficacite...

Employer des operateurs simples et rapides (arithmetique entiere, decalage

binaire)

Compromis entre la complexite et des proprietes statistiques a verifier.


Contraintes sur les sequences generees

• avoir une grande longueur avant de recommencer la sequence (longueur

du cycle ou periode).

• reussir un test d’uniformite avec le degre de confiance choisi par

l’utilisateur.

• reussir un test d’independance entre deux valeurs successives avec le

degre de confiance choisi par l’utilisateur.

• reussir des test varies en fonction des besoins specifiques (distributivite

dans l’espace, autocorrelation).


3 Principes

• Ce n’est pas parce-que ca a l’air complique que c’est aleatoire....

• Chercher un algorithme recent etudie par un specialiste...

• Effectuer des tests en cas d’utilisation ”speciale”...


Generateurs simples

• LCG : linear Congruential Generator

• Generateur a decalage sur la representation binaire


Generateur LCG

La fonction f est lineaire et utilise une arithmetique modulo m.

xn = axn−1 + b mod m

ou a et b sont positifs ou nuls. xn est un entier entre O et m − 1. On se

ramene aux reels par division par m.

yn = xn/m

Donc yn ∈ [0, 1[.

Attention la valeur 1 est exclue.


Generateur a decalage

xn est represente comme un vecteur binaire. L’iteration est

xn+1 = Txn

T est une matrice booleenne a diagonale constante (equivalente a un

polynome)

On peut effecteur l’operation Txn par un circuit.


Proprietes simples des generateurs LCG

• Periode maximale m.

• Une seule racine.

• Pour faciliter les calculs, souvent m = 2k.

→ division et modulo = simples decalages de bits.

• si b est nul, on parle de LCG multiplicatif. Calcul plus facile.


Si b > 0, la periode maximale m est obtenue si et seulement si les trois

conditions suivantes sont satisfaites :

• b et m sont premiers entre eux.

• chaque entier premier diviseur de m est aussi diviseur de a − 1.

• si m est multiple de 4, a − 1 doit etre multiple de 4.

Exemple : les generateurs de type m = 2k, a = 4c + 1, et b impair ont un

cycle de longueur m.


La longueur du cycle n’est pas tout; la correlation entre deux valeurs

successives est tres importante.

Exemples :

xn = (234 + 1)xn−1 + 1 mod 235

xn = (218 + 1)xn−1 + 1 mod 235

Le premier a une autocorrelation d’ordre 1 de 0.25 alors que le second a

une autocorrelation d’ordre 1 de 2−18.


LCG multiplicatif

Deux familles interessantes :

1. m = 2k

2. m premier

m = 2k

• Operation modulo = decalage en binaire

• periode maximale m/4

• periode maximale atteinte pour a = 8i ± 3 pour une racine initiale

impaire


m premier

• Periode maximale : m − 1

• Impossible d’atteindre 0 (et de quitter cette valeur)

• Pour obtenir la periode maximale, il faut choisir a comme racine

primitive de m.

a est une racine primitive de m si et seulement si an − 1 n’est pas divisible

par m pour tout n strictement inferieur

Exemple, si m = 31, on peut prendre a = 3 car 3 est une racine primitive

de 31.


Problemes d’Implementation des generateurs LCG

1. Il faut toujours travailler sur de l’arithmetique entiere exacte et non

pas passer en reel et faire une troncature.

2. Verifier que le type entier existe effectivement dans le langage et qu’il

y a une arithmetique exacte associee.

3. il faut que l’operation de multiplication a × xn−1 ne provoque pas

d’erreurs de debordement (depassement de l’entier maximum).

Sinon, le codage du generateur ne verifie pas les proprietes enoncees.


Methode de Schrage

Pour eliminer le probleme du depassement de l’entier maximal.

a × x mod m = g(x) + m × h(x)

q = (m div a) (48)

r = (m mod a) (49)

g(x) = a × (x mod q) − r × (x div q) (50)

h(x) = (x div q) − (a × x div m) (51)

Pour tout x de 0 a m − 1, les termes apparaissant dans le calcul de g(x)

sont plus petits que m.

De plus, si r < q, h(x) vaut 1 si g(x) est negatif et 0 si g(x) est positif. Il

est inutile de calculer h.


Exemple Methode de Schrage

Codage en Pascal du generateur xn = 75 × xn−1 mod (231 − 1). a × x

peut atteindre a peu pres 245. Debordement possible sur une arithmetique

32 bits.

a = 75 = 16807 m = 2147483647

On calcule q et r

q = 12773 r = 2836

et donc q > r.


Function Random(var x : integer) : real;

const q = 12773;

a = 16807;

r = 2836;

m = 2147483647

var x1,x2,g: integer;

begin

x1:= x div q;

x2:= x mod q;

g:=a*x2 - r*x1;

if g<0 then x:=g+m else x:=g;

Random:=x/m;

end;


Problemes et Conseils

• Ne jamais utiliser la fonction random fournie par un langage non

specialise sans l’avoir testee.

• Ne jamais utiliser 0 comme racine, si le generateur est un LCG

multiplicatif, on reste coince a 0.

• Ne jamais prendre de racines aleatoires (inconnues) ou dependantes du

systeme (horloge, pid). 2 Risques : non reproductibilite de la sequence

et choix d’une mauvaise racine.


Ne jamais supposer que si un nombre est aleatoire, un bit de sa

representation l’est egalement. Ne pas se servir de la representation binaire

de xn comme une chaıne binaire aleatoire uniforme.

Exemple, xn = (8789xn−1 + 16384) mod 216 initialise a 1

• le bit 1 (le poids faible) est toujours 1

• le bit 2 est toujours 0

• le bit 3 suit la sequence 01

• le bit 4 suit la sequence 0110

• le bit 5 suit un cyle 11010010

• plus generalement le bit l suit un cycle de longueur 2l−2.

Cette propriete est toujours vraie pour les generateurs LCG avec m = 2k.

Les bits de poids faible sont ”peu aleatoires”.


Exemple d’erreurs provoquees par un generateur de ce type

B

C

D

A

Figure 9: Reseau Multi-etages

Modele du routage : independant, a chaque switch on choisit la destination

avec probabilite 1/2.

Conclusion du modele: Chaque switch du 2eme etage traite 1/4 du trafic.


Implementation a l’aide du generateur precedent et on utilise les bits 1 et 2

des entiers generes pour faire le routage : 0 pour sortie haute, 1 pour sortie

basse.

Conclusion de la simulation : le switch C traite la totalite du trafic.


• Plus generalement, pour eviter les dependances, eviter que les

sequences ne se chevauchent :

– determiner la longueur de la simulation en nombre de tirages

aleatoires pour chaque source (N).

– evaluer a part les differentes racines : x0, xN , x2N , etc.

xN = f (N)(x0)

x2N = f (2N)(x0)


Probleme de la k-distributivite

Illustrons le probleme:

• xn = (216 + 3)xn−1 mod 231 est un generateur utilise par IBM dans

les annees 60, sous le nom de RANDU.

• Il existe une version pour micro 16 bits de ce generateur

xn = (28 + 3)xn−1 mod 215. Les deux sont a eviter....

• si on prend 3 points successifs comme coordonnees (x, y, z), tous les

points ainsi generes se devraient remplir tout le cube.


Figure 10: Triplets de points construits par RANDU


Figure 11: Triplets de points construits par RANDU, changement d’angle

de vue


Tous les points ainsi generes se situent sur 15 plans et non pas dans tout le

cube.

Le probleme est general a tous les generateurs LCG. Tous les

k-uplets sont dans au plus (k!m)1/k hyperplans paralleles.

Illustration en dimension 2 : des droites....


0

5

10

15

20

25

30

0 5 10 15 20 25 30

"generateur.data"

Figure 12: Pavage par un LCG


Amelioration des LCG par combinaison

Methode de la Table (Knuth)

On utilise deux generateurs xn et yn.

1. On initialise un tableau T de taille k avec k valeurs successives du

generateur xn.

2. On utilise yn normalise entre 1 et k. yn = i

3. On retourne T (i),

4. On calcule une nouvelle valeur de xn a ranger dans T (i)

5. On recommence en 2


• Les mauvaises proprietes des LCG se transmettent aux algorithmes qui

les empmloient.

• 3 exemples d’algo de Box et Muller pour generer des lois normales.

• Ne pas croire que NS2 ou les autres logiciels n’ont pas ce type de

probleme.


Figure 13: Box Muller et LCG: exemple


Figure 14: Box Muller et LCG: autre exemple


Figure 15: Box Muller et LCG: dernier exemple


Bibliographie

• Simulation Modeling and Analysis, A. Law, D. Kelton, Mac Graw Hill.

• Methodes statistiques a l’usage des medecins et des biologistes, D.

Schwartz, Flammarion, coll. Medecine-Sciences

• Monte Carlo, concepts, algorithms, and applications, G.S. Fishman,

Springer

• Simulation model design and execution : building digital worlds, P.

Fishwick, Prentice Hall.


Bibliographie

• Introduction to numerical solution of Markov chains, W.J. Stewart,

Princeton University Press, 1994

• Raj Jain, ”The Art of Computer Systems Performance Analysis”,

Wiley, 1991

• Mike Tanner, ”Practical Queueing Analysis”, IBM-Mac Graw Hill,

1995

• D.A. Menasce, V.A.F. Almeida, ”Capacity Planning for Web

Performance”, 1998

• R.A. Sahner, K.S. Trivedi, A. Puliafito, Performance and reliability

analysis of computer systemsn Kluwer Academic Press.


Documents

Modélisation Quantitative de la Fiabilité