De la modélisation du trafic

De la modélisation du trafic dans les réseaux de

télécommunications

Michel Marot

Institut National des Télécommunications

Chapitre 12. De la modélisation du trafic dans les réseaux de télécommu-nication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

12.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712.2.Le processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . .. 7

12.2.1.Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712.2.2.Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212.2.3.Loi hyperexponentielle . . . . . . . . . . . . . . . . . . . . . . .. 1712.2.4.Loi hypoexponentielle et loi d’Erlang . . . . . . . . . . .. . . . . 18

12.3.Les modèles à base de processus d’arrivées markovien (M.A.P., B.M.A.P.,D.-M.A.P. et D.-B.M.A.P.) . . . . . . . . . . . . . . . . . . . . . . . . . . 22

12.3.1.Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2212.3.2.Densité de la classe des processus B.M.A.P. dans celle des pro-

cessus ponctuels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2812.3.3.Cas discret : D.-B.M.A.P. . . . . . . . . . . . . . . . . . . . . . .. 3212.3.4.Application du modèle D.-B.M.A.P. : une approximation de la

superposition de sources sporadiques . . . . . . . . . . . . . . . . . 3512.4.Les modèles modulés par un processus de Poisson . . . . . .. . . . . . 41

12.4.1.Définition et propriétés du modèle M.M.P.P. . . . . . . .. . . . . 4212.4.2.Fonction de comptage associée au processus M.M.P.P. . . . . . . 4612.4.3.Matrice des probabilités de transition du processus de renouvel-

lement markovien M.M.P.P. . . . . . . . . . . . . . . . . . . . . . . 4812.4.4.Temps entre deux arrivées . . . . . . . . . . . . . . . . . . . . . .50

5

6

12.4.5.Applications du modèle M.M.P.P. : trafic de débordement, et ap-proximation de trafic par un processus M.M.P.P. . . . . . . . . . . 52

12.5.Le modèle fluide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5712.6.Les modèles fractaux ou autosimilaires . . . . . . . . . . . .. . . . . . 60

12.6.1.Définitions de l’autosimilarité exacte et propriétés . . . . . . . . . 6012.6.2.Définitions de l’autosimilarité asymptotique et propriétés . . . . . 6312.6.3.Dépendances à long-terme . . . . . . . . . . . . . . . . . . . . . .7012.6.4.Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7112.6.5.Application : effet des dépendances à long-terme sur les perfor-

mances d’une file d’attente, lien entre autosimilarité et distribu-tions barycerques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

12.7.Un modèle de trafic modulable, prenant en compte les caractéristiquesimportantes du trafic, et adapté à la simulation . . . . . . . . . . .. . . 82

12.7.1.Modèle à temps discret . . . . . . . . . . . . . . . . . . . . . . . . 8212.7.2.Modèle à temps continu . . . . . . . . . . . . . . . . . . . . . . . . 84

12.8.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Chapitre 13. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

Chapitre 12

De la modélisation du trafic dans les réseauxde télécommunications

Michel MAROTInstitut National des Télécommunications

12.1. Introduction

Il serait vain de prétendre exposer en quelques dizaines de pages un état de l’art ex-haustif sur la modélisation du trafic dans les réseaux de télécommunications. Ce sujetà fait l’objet de nombreux travaux scientifiques, plusieursapproches ont été propo-sées. C’est pourquoi nous avons choisi de ne détailler que quelques modèles, les plusutiles pour la simulation, plutôt que de présenter un survolde tous ceux qui existent.Le lecteur peut se référer à [12] pout un recensement très complet des modèles detrafic.

La théorie des files d’attente est l’arsenal classique utilisé pour s’attaquer auxproblèmes de performances de réseaux. Elle repose sur l’hypothèse que le trafic estpoissonnien, aussi présentons-nous en premier lieu le trafic de Poisson. Cependant,il y a quelques années, on a montré que le trafic paraissait autosimilaire. Fallait-ilalors revoir la théorie des files d’attente ? Pouvait-on continuer à l’appliquer même sises fondements ne sont pas vérifiés ? Entre ces deux extrêmes,certains ont cherchéà l’adapter en proposant des modèles markoviens rendant compte de certaines carac-téristiques des trafics à dépendances à long-terme. C’est dans la dernière partie dece chapitre que deux de ces modèles sont traités. Auparavant, dans les deuxième ettroisième parties les modèles markoviens B.M.A.P. et M.M.P.P. sont présentés, suivisd’un paragraphe sur les trafics autosimilaires.

12.2. Le processus de Poisson

12.2.1. Définition

Le processus de Poisson peut être défini de trois façons différentes, toutes équiva-lentes :

7

8

Définition 1 (Processus de Poisson)Un processus de Poisson de tauxλ est un pro-cessus tel que :

– la probabilité d’avoir une arrivée pendant un intervalle de tempsdt estλdt +o (dt) ;

– la probabilité d’avoir k> 1 arrivées pendantdt est o(dt) ;

– la probabilité de ne pas avoir d’arrivée pendantdt est1− λdt + o (dt).

Définition 2 (Processus de Poisson)Un processus de Poisson de tauxλ est un pro-cessus d’arrivées vérifiant :

– la loi du nombre d’arrivées pendant un intervalle de temps de longueurτ suit

une loi de Poisson : P(k) =(λτ)k

k!e−λτ ;

– les nombres d’arrivées N(t1, t2) et N(t3, t4) dans deux intervalles de temps dis-joints (t1 ≤ t2 ≤ t3 ≤ t4) sont indépendants.

Définition 3 (Processus de Poisson)Un processus de Poisson de tauxλ est un pro-cessus d’arrivées tel que les temps entre arrivées An sont indépendants et suivent uneloi exponentielle de tauxλ P (An ≤ t) = 1− e−λt.

Nous allons démontrer que la définition 1 implique 2 qui, elle-même, implique 3,laquelle implique enfin 1.

Soit N(0, t) le nombre d’arrivées pendant l’intervalle de temps [0;t]. NotonsPk(t) laprobabilité queN(0, t) = k. Pour avoirN(0, t) = k > 0 à l’instantt + dt, il faut soiten avoir euk à l’instant t et ne pas avoir d’arrivée au cours de l’intervalle de temps[t; t + dt], soit en avoir euk− 1 à t et avoir eu exactement une arrivée entret et t + dt,d’où

Pk (t + dt) = Pk−1(t)λdt + (1− λdt) Pk(t)

⇔Pk (t + dt) − Pk(t)

dt= λ [Pk−1(t) − Pk(t)]

⇔dPk(t)

dt= λ [Pk−1(t) − Pk(t)] (12.1)

ns le cas oùk = 0, pour avoirN (0, t) = 0 à l’instantt + dt, il faut avoir euk = 0 àl’instant t et ne pas avoir d’arrivée pendant[t; t + dt], donc

P0 (t + dt) = (1− λdt) P0(t)

⇔P0 (t + dt) − P0(t)

dt= −λP0(t)

⇔dP0(t)

dt= −λP0(t) (12.2)

De la modélisation du trafic dans les réseaux de télécommunication 9

Pour déterminer la loi deN (0, t), il faut résoudre le système différentiel

dPk(t)dt

= λpk−1(t) − λPk(t) (12.3)

dP0(t)dt

= −λP0(t) (12.4)

Montrons par récurrence que la solution estPk(t) =(λt)k

k! e−λt. Pourk = 0, la solutionde l’équation (12.4) estP0(t) = Ae−λt, où A est une constante. CommeN (0,0) = 0 etdoncP0(0) = 1, A = 1 d’où P0(t) = e−λt.

Supposons maintenant quePk(t) =(λt)k

k! e−λt, montrons alors quePk+1(t) = (λt)k+1

(k+1)! e−λt.

Compte tenu de l’hypothèse de récurrence, l’équation (12.3) devient :

ddt

Pk+1(t) =(λt)k

k!e−λtλ − λPk+1(t). (12.5)

La solution de l’équation homogène associée

ddt

Pk+1(t) = −λPk+1(t) (12.6)

est

Pk+1(t) = Ae−λt, (12.7)

oùA est une constante. Pour trouver la constante, utilisons la méthode de variation desconstantes. Posons

Pk+1(t) = A(t)e−λt. (12.8)

On a alors

ddt

Pk+1(t) =dA(t)

dte−λt − λA(t)e−λt (12.9)

10

et l’équation (12.5) donne

dA(t)dt

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

k!e−λtλ − λA(t)e−λt

⇔dA(t)

dt=

(λt)k

k!λ. (12.10)

Donc,

A(t) =1

k+ 1(λt)k+1

k!+Cste, (12.11)

et, carPk+1(0) = 0,

Pk+1(t) =(λt)k+1

(k+ 1)!e−λt. (12.12)

Il existe une autre démonstration plus courte en utilisant les fonctions génératrices.SoitGt(z) = E

[zN(0,t)

]la fonction génératrice de la variable aléatoireN (0, t).

Gt+dt(z) = E[zN(0,t+dt)

]= E[zN(0,t)+N(t,t+dt)

]. (12.13)

Or, puisqueN (0, t) et N (t, t + dt) sont indépendantes,

E

[zN(0,t)+N(t,t+dt)

]= E[zN(0,t)

]E

[zN(t,t+dt)

], (12.14)

et donc,

Gt+dt(z) = E[zN(0,t)

]E

[zN(t,t+dt)

]

= Gt(z)[(1− λdt) z0 + λdtz1

]. (12.15)

On en déduit que

Gt+dt(z) −Gt(z)dt

= λ(z− 1)Gt(z)⇔dGt(z)

dt= λ(z− 1)Gt(z) (12.16)


dont la solution est

Gt(z) = Aeλ(z−1). (12.17)

CommeG0(z) = 1,

Gt(z) = eλ(z−1). (12.18)

On reconnaît ici la fonction génératrice de la loi de Poisson, donc,

Pk(t) =(λt)k

k!e−λt. (12.19)

Montrons maintenant que la définition 2 d’une loi de Poisson implique la définition3. Soit X l’intervalle de temps entre deux arrivées. La probabilité que cet intervallesoit plus grand quet est égale à la probabilité de ne pas avoir d’arrivée pendant unintervalle de longueurt :

P (X > t) = P (N (0, t) = 0)

⇒ P (X ≤ t) = 1− P (N (0, t) = 0)

⇒ P (X ≤ t) = 1− e−λt. (12.20)

Donc, le temps entre deux arrivées est une variable aléatoire qui suit une distributionexponentielle de paramètreλ.

Montrons enfin que la définition 3 implique la définition 1. La probabilité d’avoirexactement une arrivée pendant dt est égale à la probabilité d’avoir un temps entrearrivées inférieur à dt. Cette probabilité est :

P1 (dt) = 1− e−λdt ≃ 1− (1+ λdt + o (dt)) = λdt + o (dt) (12.21)

La probabilité d’en avoir plus d’une seule est donc eno (dt), et la probabilité de ne pasen avoir est 1− λt + o (dt). Q.E.D.

12

12.2.2. Propriétés

Ce processus a une importance particulière en raison d’une part de la relative sim-plicité des calculs dans les modèles qui l’utilisent et d’autre part car dans un grandnombre de cas, la superposition de plusieurs trafics indépendants tend vers un traficde Poisson. Ceci a été démontré par C. Palm en 1943 et expliquepourquoi dans lanature de nombreux phénomènes sont modélisés par des processus de Poisson.

Propriété 1 (Superposition de processus de Poisson)La superposition de deux pro-cessus de Poisson de tauxλ1 etλ2 respectivement est un processus de Poisson de tauxλ1 + λ2.

En superposant les deux processus de Poisson de tauxλ1 etλ2, on obtient un processustel que (cf. [34]) :

– la probabilité d’avoir exactement une arrivée entret et t + dt est la probabilitéd’avoir une arrivée du premier processus et pas du second, oubien de ne pas avoird’arrivée du premier et d’en avoir une du second :

P (Exactement une arrivée)

= [λ1dt + o (dt)] × [1− λ2dt + o (dt)]

+ [1− λ1dt + o (dt)] × [λ2dt + o (dt)]

= (λ1 + λ2) dt + o (dt) ; (12.22)

– la probabilité de ne pas avoir d’arrivée est égale à la probabilité de ne pas avoird’arrivée du premier et de ne pas en avoir du second :

P (Aucune arrivée) = [1− λ1dt + o (dt)] × [1− λ2dt + o (dt)]

= 1− (λ1 + λ2) dt + o (dt) ; (12.23)

– la probabilité d’avoir plus d’une arrivée est la probabilitée d’en avoir plus d’unedu premier processus ou celle d’en avoir plus d’une du second, ou encore celle d’avoirexactement une seule de chacun :

P (k > 1 arrivées) = o (dt) + o (dt) + [λ1dt + o (dt)] × [λ2dt + o (dt)]

= o (dt) (12.24)

La première définition d’un processus de Poisson permet de reconnaître un processusde Poisson de tauxλ1 + λ2. Q.E.D.

Propriété 2 (Echantillonnage d’un processus de Poisson)Si un échantillonnage aléa-toire est fait à partir d’un processus de Poisson de tauxλ et avec une probabilité p,c’est-à-dire que pour chaque arrivée du processus de Poisson chacune est sélectionnéeavec une probabilité p, indépendamment de celles déjà sélectionnées ou à sélection-ner, le processus résultant est un processus de Poisson de tauxλp.


Dans le cas d’un échantillonnage réalisé avec une probabilité p sur un processus dePoisson, la probabilité d’avoir exactement une arrivée entre t et t+dt pour le processusrésultant de l’échantillonnage est la probabilité que le processus de Poisson initial aitune arrivée et que celle-ci soit sélectionnée :

P (Exactement une arrivée) = p× [λdt + o (dt)] . (12.25)

La probabilité de ne pas avoir d’arrivée entret et t + dt pour le processus résultant estla probabilité que le processus initial ait une arrivée et qu’elle ne soit pas sélectionnéeou qu’il n’y ait pas d’arrivée pour le processus initial :

P (Exactement aucune arrivée)

= (1− p) × [λdt + o (dt)] + [1− λdt + o (dt)] . (12.26)

Le fait d’avoir plus d’une arrivée entret et t + dt pour le processus résultant supposed’en avoir plus d’une pour le processus initial, donc

P (Plus d’une arrivée) = o (dt) . (12.27)

La première définition d’un processus de Poisson permet de reconnaître un processusde Poisson de tauxλp.

Propriété 3 (Temps entre appels et temps résiduel avant la prochaine arrivée)Considérons un trafic d’appels téléphoniques. Soient :

– X l’intervalle de temps entre un instant quelconque et le prochain appel,

– θ(t) = P (X ≥ t),

– A l’intervalle de temps entre un appel quelconque et le suivant, de moyenne1y ,

– φ(t) = P (A ≥ t).

– F(t) = − dφ(t)dt la densité de probabilité de la longueur des appels

On a :

φ(t) = −1y

dθ(t)dt

(12.28)

14

Nous reprenons la démonstration de l’article [23] pour cette propriété et la suivante.

En moyenne, il y ay appels par unité de temps. Il y a donc en moyenneyφ(t) intervallesentre appels qui ont au moins la longueurt. Dans l’intervalle de temps entre appels delongueurx+ t, tous les intervalles compris entret et x+ t sont de longueurs supérieuresà t. En moyenne, il y ayF(x+ t)dx intervalles entre appels de longueurx+ t par unitéde temps. La proportion d’intervalles entre appels qui sontde longueurs au moinst estdonc :

θ(t) = y∫ +∞

x=0xF(x+ t)dx (12.29)

En posantu = x+ t, on obtient :

θ(t) = y∫ +∞

x=t(u− t)F(u)du (12.30)

et en intégrant par partie,

θ(t) = y[−uφ(u)

]+∞t − y

∫ +∞

x=t−φ(u)du− yt

∫ +∞

x=tF(u)du (12.31)

ce qui se simplifie en :

θ(t) = y∫ +∞

x=tφ(x)dx (12.32)

On en déduit la relation entreθ(t) etφ(t) :

dθ(t)dt

= −yφ(t) (12.33)

Q.E.D.

Propriété 4 (Superposition de trafics) Soient

– N trafics indépendants ;


– yσ la moyenne du nombre d’arrivées par unité de temps duσème trafic ;

– Xσ l’intervalle de temps entre un instant quelconque t et la prochaine arrivéeaprès t pour leσème trafic ;

– θσ(x) = P (Xσ ≥ x) ;

– Aσ l’intervalle de temps entre un appel quelconque et le suivant pour leσème

trafic ;

– φσ(x) = P (Aσ ≥ x) ;

– Y la moyenne du nombre d’arrivées par unité de temps du traficrésultant de lasuperposition ;

– X l’intervalle de temps entre un instant quelconque t et la prochaine arrivéeaprès t pour le trafic résultant de la superposition ;

– Θ(x) = P (X(t) ≥ x) ;

– A l’intervalle de temps entre un appel quelconque et le suivant pour le traficrésultant de la superposition ;

– Φ(x) = P (A ≥ x).

Supposons que :

– N tende vers l’infini ;

– chaque yσ tende vers 0 ;

–∑Nσ=1 yσ tende vers une constante Y.

Dans ces conditions, on démontre queΘ(x) = e−Yx et donc que la distribution destemps entre appels du processus résultant est exponentielle. On en déduit que le traficrésultant de la superposition tend vers un processus de Poisson.

On peut écrire la fonctionθσ(t) selon la forme suivante :

θσ(t) = 1− yσt + y2σKσ (t, yσ) (12.34)

et donc,

φσ(t) = 1− yσ∂Kσ (t, yσ)∂t

(12.35)

On peut supposer que pour toute valeur finie de t,

limyσ→0

∂Kσ (t, yσ)∂t

(12.36)

16

existe et a une valeur finie. Cela signifie que la probabilité qu’un intervalle entre appelssoit de longueur finie s’approche de 0 quand le nombre moyen d’appels par unité detempsyσ tend vers 0. Maintenant, si la dérivée deKσ (t,0) est borneée avant toutevaleur finiet, Kσ (t,0) ne peut pas croître entre 0 et cette valeur finie d’une valeur finieà une quantité infinie. Si par exempleKσ (0,0) = 0, Kσ (t,0) est donc finie pour toutevaleur finie det.

Comme la probabilité qu’un intervalle d’appel soit plus grand qu’une valeur finietn’est jamais nulle quandyσ s’approche de 0, on doit avoirφσ(t) > 0 pour toute valeurfinie t et yσ arbitrairement petit, et donc, puisqueθσ(t) = y

∫ +∞x=tφσ(x)dx, θσ(t) > 0.

On en déduit l’inégalité

yσt − y2σKσ (t, yσ) < 1 (12.37)

dont le membre de gauche ne peut bien sûr jamais être négatif (sinon θσ(t) seraitstrictement positif).

On peut alors développer lnθσ(t) en série entière :

ln θσ(t) = −[yσt − y2

σKσ (t, yσ)]−

12

[yσt − y2

σKσ (t, yσ)]2− · · · (12.38)

Les trafics superposés étant indépendants,

Θ(t) = θ1(t)θ2(t) · · · θN(t) (12.39)

et donc,

lnΘ(t) = − (y1 + y2 + · · · + yN) − R (12.40)

oùRest une somme de puissances desyσ, négligeable devant la somme desyσ quandceux-ci tendent vers 0. Pour unt donné, la fonctionΘ(t) tend donc verse−Yt, quandN tend vers l’infini,yσ tend vers 0 et

∑Nσ=1 yσ tend vers une constante. Ceci revient à

dire que la suite de fonctionsΘ(t) converge simplement vers la fonctione−Yt avecNdans les conditions déjà dites, et donc qu’il y a convergenceen loi. Q.E.D.


12.2.3. Loi hyperexponentielle

A côté de la loi exponentielle, on trouve deux autres ensembles de lois qu’on définitsouvent en les comparant à la loi exponentielle (cf. [4]) : les lois hyperexponentielleset les lois hypoexponentielles.

Définition 4 (Loi hyperexponentielle) Une variable aléatoire continue suit une dis-tribution hyperexponentielle si elle a comme densité de probabilité :

fHr (t) =

r∑

i=1

αiµie−µi t où

r∑

i=1

αi = 1 (12.41)

Une loi hyperexponentielle peut être vue comme un mélange delois exponentielles.Elle permet de caractériser des variables aléatoires qui varient beaucoup plus qu’unevariable aléatoire suivant une loi exponentielle. En effet, le carré du coefficient devariation, c’est-à-dire le rapport de la variance sur la moyenne, qui mesure le carré del’écart relatif entre l’écart à la moyenne et la moyenne, a pour expression :

CCVH(r) =2∑r

i=1αi

/µ2

i(∑r

i=1 αi

/µ2

i

)2 − 1 (12.42)

Par l’inégalité de Cauchy-Schwartz,

r∑

i=1

aibi

2

≤

r∑

i=1

a2i

r∑

i=1

b2i (12.43)

ce carré du coefficient de variation est strictement supérieur à 1 :

CCVHr > 1 (12.44)

On retrouve cette distribution hyperexponentielle par exemple lorsqu’on a un trafic quiarrive sur un système composé de serveurs indépendants à temps de services exponen-tiels placés en parallèle et que le trafic est dirigé aléatoirement sur l’un ou l’autre desserveurs avec une certaine probabilitépi, i = 1, · · · ,n : cf. Fig. 12.1.

Comme la longueur des files d’attente est fonction du carré ducoefficient de variation,plus celui-ci est grand plus la longueur de la file est grande,c’est pourquoi des traficsdont les temps entre arrivées sont hyperexponentiels conduisent à une dégradation desperformances (cf. [4]).

18

S2

Sn

pn

p2

p1

Arrivees

S1

n serveurs exponentiels en parallele

Figure 12.1 – n serveurs en parallèle

12.2.4. Loi hypoexponentielle et loi d’Erlang

De même qu’on peut avoir des serveurs en parallèle, on peut enavoir placés ensérie. Cela conduit alors à des lois hypoexponentielles : cf. Fig. 12.2.

Arrivees

S1 S2 Sn

n serveurs exponentiels en parallele

Figure 12.2 – n serveurs en série


Définition 5 (Loi hypoexponentielle) Une variable aléatoire continue X=∑r

i=1 Xi

qui est la somme de r variables aléatoires indépendantes exponentielles de densitésfXi (t) = λie−λi t est dite hypoexponentielle.

Propriété 5 (Distribution de la loi hypoexponentielle) Elle a comme densité de pro-babilité :

fHypo(r) (t) =r∑

i=1

Ci,rλie−λi t où Ci,r = Π j,i

λ j

λ j − λi

La démonstration qui suit est reprise du livre [28].

Dans le cas oùr = 2, la densité de probabilité de la somme des deux variablesX1 etX2 est le produit de convolution de leurs densités de probabilité :

fX1+X2 (t) =

∫ t

0fX1 fX2 (t − s) ds

=

∫ t

0λ1e−λ1sλ2e−λ2(t−s)ds

= λ1λ2

∫ t

0e−(λ1−λ2)sds

=λ1

λ1 − λ2λ2e−λ2t

(1− e−(λ1−λ2)t

)

=λ1

λ1 − λ2λ2e−λ2t +

λ2

λ1 − λ2λ1e−λ1t (12.45)

De la même manière, on trouverait avecn = 3 :

fX1+X2+X3 (t) =

3∑

i=1

λie−λi t

(Π j,i

λ j

λ j − λi

)(12.46)

ce qui suggère le résultat général

fX1+X2+···+Xr (t) =

r∑

i=1

Ci,rλie−λi t (12.47)

20

où

Ci,r = Π j,iλ j

λ j − λi(12.48)

Prouvons-le par récurrence. La propriété est vraie au rand r=2. Supposons-là vraie aurangr et montrons-la au rangr + 1. Supposons queX1 et Xr+1 sont renommés de tellefaçon à ce queλ1 ≥ λr+1.

fX1+···+Xr+1 (t) =

∫ t

0fX1+···+Xr (s) λr+1e−λr+1(t−s)ds

=

r∑

i=1

Ci,r

∫ t

0λie−λi sλr+1e−λr+1(t−s)ds

=

r∑

i=1

Ci,r

(λi

λi − λr+1λr+1e−λr+1t +

λr+1

λr+1 − λiλie−λi t

)

= Kr+1λr+1e−λr+1t +

r∑

i=1

Ci,r+1λie−λi t (12.49)

où

Kr+1 =

r∑

i=1

Ci,rλi

λi − λr+1

est une constante qui ne dépend pas det.

Par ailleurs,

fX1+···+Xr+1 (t) =∫ t

0fX2+···+Xr+1 (s) λ1e−λ1(t−s)ds

ce qui implique, selon le même type de calcul que précédemment,

fX1+···+Xr+1 (t) = K1λ1e−λ1t +

r∑

i=2

Ci,r+1λie−λi t

On en déduit que

Kr+1λr+1e−λr+1t +C1,r+1λ1e−λ1t = K1λ1e−λ1t +Cr+1,r+1λr+1e−λr+1t

En multipliant les deux membres de cette équation pareλr+1t, et en faisant tendret vers+∞, on obtient (puisquee−(λ1−λr+1) tend vers 0 quandt tend vers+∞) ;

Kr+1 = Cr+1,r+1


En injectant ce résultat dans l’expression (12.49), on arrive à

fX1+X2+···+Xr+1 (t) =

r+1∑

i=1

Ci,r+1λie−λi t Q.E.D. (12.50)

Propriété 6 (Carré du coefficient de variation) Pour une loi hypoexponentielle, lavariance est

N∑

i=1

1

λ2i

, (12.51)

sa moyenne

N∑

i=1

1λi, (12.52)

et donc le carré de son coefficient de variation est

∑Ni=1

1λ2

i(∑Ni=1

1λi

)2 ≤ 1 (12.53)

L’exemple le plus connu de loi hypoexponentielle est la loi d’Erlang.

Définition 6 (Loi d’Erlang) Une variable aléatoire X suit une loi d’Erlang de para-mètresλ > 0 et k= 1,2, · · · si elle a pour densité de probabilité

f (x) =(λk)k

(k− 1)!xk−1e−kλx, x > 0 (12.54)

Sa moyenne est1/λ, sa variance1/(kλ2)

et sa fonction caractéristique

E

[eitX]=

(kλ

kλ − it

)k. (12.55)

Une somme dek variables aléatoires indépendantes équidistribuées de loi exponen-tielle de paramètreλ suit une loi d’Erlang de paramètresλ et k.

22

12.3. Les modèles à base de processus d’arrivées markovien (M.A.P., B.M.A.P.,D.-M.A.P. et D.-B.M.A.P.)

12.3.1. Définition

Soient un processus de Poisson de tauxλ, et N(t) le nombre d’arrivées corres-pondantes dans l’intervalle de temps [0;t]. {N(t)}t≥0 est un processus markovien surl’ensemble des entiers naturelsN. Son générateur infinitésimal est :

λ −λ 0 0 · · ·

0 λ −λ 0 · · ·

0 0 λ −λ · · ·......

....... . .

Définition 7 (Processus B.M.A.P.)Le processus B.M.A.P. (de l’anglais Batch Mar-kov Arrival Process, i.e. processus d’arrivées groupées markovien) est une générali-sation du processus de Poisson où les arrivées se produisentselon un processus deMarkov à temps continu. Soient :

– {N(t)}t≥0 le nombre d’arrivées dans l’intervalle[0; t] ;

– {J(t)}t≥0 un processus markovien à valeurs dans l’espace discret~1;mÄ.

On appelle processus B.M.A.P. un processus markovien à deuxdimensions{N(t), J(t)}t≥0

dont le générateur infinitésimal est de la forme :

D =

D(0) D(1) D(2) D(3) · · ·

0 D(0) D(1) D(2) · · ·

0 0 D(0) D(1) · · ·...

......

.... . .

(12.56)

où

D(k) =

d(k)11 d(k)

12 d(k)13 · · · d(k)

1m

d(k)21 d(k)

22 d(k)23 · · · d(k)

2m...

....... . .

...

d(k)m1 d(k)

m2 d(k)m3 · · · d(k)

mm

(12.57)

où d(k)i j est le taux de probabilité de passage de l’état(N(t) = l, J(t) = i) à

(N(t) = l + k, J(t) = j) pour tout l≥ 0, ce qui correspond simultanément à un passagede l’état J(t) = i à J(t) = j et à k arrivées.


La classe des processus B.M.A.P. contient plusieurs cas particuliers bien connus.

Définition 8 (Processus M.A.P.)Le processus M.A.P. est processus B.M.A.P. pour le-quel le nombre d’arrivées par groupe d’arrivées est égal à un. En d’autres termes,D(k) = 0 pour k> 1.

Cette classe contient elle-même la famille des processus dePoisson, celle des proces-sus de Poisson modulés par une chaîne de Markov (MMPP) (cf. § 12.4), et celle desprocessus de renouvellement de type phase.

Définition 9 (Processus de renouvellement markovien)Le processus stochastique(J,X) = {(Jn,Xn) ; n ≥ 0} est un processus de renouvellement markovien à espaced’état E si :

Pr (Jn+1 = j,Xn+1 ≤ x /J0, · · · , Jn,X0, · · · ,Xn ) = Pr (Jn+1 = j,Xn+1 ≤ x /Jn )

pour tout n∈ N, j ∈ E, t ∈ [0;+∞[.

Ce processus est à temps homogène si Pr(Jn+1 = j,Xn+1 ≤ x /Jn ) ne dépend pas del’indice du temps n. Dans ce cas, on pose

Pr (Jn+1 = j,Xn+1 ≤ x /Jn ) = Fi j (x)

Plus intuitivement, un processus de renouvellement markovien est un processus quiévolue au cours du temps en passant par différents états et reste dans ces états untemps de séjour qui ne dépend que de l’état courrantJn et de l’état futurJn+1.

Si la distribution du temps passé dans les états est exponentielle, le processus devientune chaîne de Markov : une chaîne de Markov est un cas particulier de processus derenouvellement markovien. Un processus de renouvellementmarkovien peut être vucomme une "chaîne de Markov dans les états de laquelle on passerait un temps suivantune distribution quelconque, pas nécessairement exponentielle".

Soient :

– {Jn}n≥0 la variable aléatoire correspondant à la valeur de l’état duprocessus{J(t)}t≥0 au moment dunième groupe d’arrivées (éventuellement constitué d’une seulearrivée) ;

– Ln le nombre d’arrivées dans ce groupe ;

– {Xn}n≥0 le temps entre lan− 1ième et lanième arrivée, avecX0 = 0 ;

– tn la date de lanième arrivée.

24

Le processus{N(t), J(t)}t≥0 est un processus markovien. En revanche, le processus{Jn,Xn}n≥0 est un processus de renouvellement markovien.

Propriété 7 (Matrice de transition de {Jn,Xn}n≥0) La matrice de transition du pro-cessus{Jn, Ln = k,Xn}n≥0 pour tout k> 0 est :

{P ( Jn = j, Ln = k,Xn ≤ x/ Jn−1 = i)}1≤i≤m,1≤ j≤m

=

∫ x

0eD(0)uduD(k) (12.58)

En effet,

dP ( Jn = j, Ln = k,Xn ≤ x/ Jn−1 = j)

= P ( Jn = j, Ln = k, x ≤ Xn ≤ x+ dx/ Jn−1 = i)

= P ( J (tn−1 + x) = j,N(x) = 0/ Jn−1 = i)(d(k)

j j + o(dx))

+

m∑

l=1,l, j

[P ( J (tn−1 + x) = l,N(x) = 0/ Jn−1 = i)

×(d(k)

i j + o(dx))]

(12.59)

soit, en écriture matricielle, en notantP (N(x) = 0) la matrice d’éléments(P (N(x) = 0))i j = P ( J (tn−1 + x) = j,N(x) = 0/ Jn−1 = i),

(dP ( Jn = j, Ln = k,Xn ≤ x/ Jn−1 = j)

dx

)

1≤i≤m,1≤ j≤m

= P (N(x) = 0) D(k) (12.60)

Par ailleurs,

P ( N (t + dt) = 0, J (t + dt) = j/N(0) = 0, J(0) = i)

= P ( N (t) = 0, J (t) = j/N(0) = 0, J(0) = i) ×1−

m∑

j′=1, j′, j

d(0)j′ jdt −

+∞∑

k=1

m∑

j′=1

d(k)j j ′dt + o(dt)

+

m∑

j′=1, j′, j

P(N (t) = 0, J (t) = j′

/N(0) = 0, J(0) = i

)×

[d(0)

j′ jdt + o(dt)]

(12.61)


donc, puisqued(0)j j = −

∑mj′=1, j′, j d(0)

j j ′ −∑+∞

k=1∑m

j′=1 d(k)j j ′ ,

dPdt

( N (t) = 0, J (t) = j/N(0) = 0, J(0) = i)

=

m∑

j′=1

P(N (t) = 0, J (t) = j′

/N(0) = 0, J(0) = i

)d(0)

j′ j (12.62)

ou encore, en notation matricielle,

ddt

P (N(t) = 0) = P (N(t) = 0) D(0) (12.63)

d’où

P (N(t) = 0) − P (N(0) = 0) =∫ t

u=0eD(0)uduD(0)

⇔ P (N(t) = 0) − I =[I − eD(0)t

] [−(D(0))−1]D(0). (12.64)

Il vient alors,

(ddx

P ( Jn = j, Ln = k,Xn ≤ x/ Jn−1 = j)

)

1≤i≤m,1≤ j≤m

= eD(0) xD(k) (12.65)

et, finalement,

P ( Jn = j, Ln = k,Xn ≤ x/ Jn−1 = j)

=

∫ x

0eD(0)uduD(k) (12.66)

Q.E.D.

26

Propriété 8 (Fonction de comptage)La fonction génératrice matricielle de la fonc-tion de comptage est

P∗(z, t) =

+∞∑

n=0

P(N(t) = n)zn, pour |z| ≤ 1

= eD(z)t (12.67)

oùD(z) =∑+∞

k=0 D(k)zk.

En effet, de la même manière qu’en (12.61), en considérant tous lescas possiblesrésultants enn arrivées pendant l’intervalle de temps [0;t+dt] (i.e. : j arrivées pendantt, etn− j arrivées groupées pendant [t; t + dt]), on peut montrer que

ddt

P (N(t) = n) =

n∑

j=0

P (N(t) = j) D(n−j ), n ≥ 1, t ≥ 0 (12.68)

P (N(t) = 0) = I. (12.69)

En multipliant (12.68) parzn et en sommant surn, on déduit la condition sur la fonctiongénératrice matricielle

ddt

P∗(z, t) = P∗(z, t)D(z) (12.70)

P∗(z,0) = I (12.71)


P∗(z, t) = eD(z)t, pour |z| , t ≥ 0 (12.72)

Q.E.D.

En dérivant successivement cette fonction génératrice matricielle et en faisant tendrez vers 0, on peut obtenir les moments de la fonction de comptage.

L’ensemble des propriétés de cette partie est extrait des articles [22] et [18].


Définition 10 (Produit de Kronecker) Le produit de Kronecker de deux matricesK²

P où K ={Ki j

}1≤i≤p1≤ j≤q

et P ={Pi j

}1≤i≤r1≤ j≤s

est la matrice d’éléments blocs{Ki j P}

1≤i≤p1≤ j≤q

. C’est

donc une matrice de taille pr× qs.

Définition 11 (Somme de Kronecker)La somme de Kronecker de m matricesL k ={Lk

i j

}1≤i≤p,1≤ j≤q

est définie parL1 ¹ L2 ¹ · · · Lm = L1 ²I² · · ·²I +I² L2 ² · · ·²

I + · · · + I² · · ·² I² Lm oùI désigne la matrice identité.

Par exemple, soient

Q =

[−q1 q1

q2 −q2

], R=

[−r1 r1

r2 −r2

], (12.73)

Q ¹ R =

−q1 0 q1 00 −q1 0 q1

q2 0 −q2 00 q2 0 −q2

+

−r1 r1 0 0r2 −r2 0 00 0 −r1 r1

0 0 r2 −r2

=

−(q1 + r1) r1 q1 0r2 −(q1 + r2) 0 q1

q2 0 −(q2 + r1) r1

0 q2 r2 −(q2 + r2)

(12.74)

Propriété 9 (Superposition de processus B.M.A.P.)La superposition de deux (ouplus) B.M.A.P. est toujours un B.M.A.P. Soient deux processus B.M.A.P., de matrices{Dk(i)} i = 1,2. La superposition de ces deux processus est un processus B.M.A.P. dematriceDk = Dk(1) ¹ Dk(2) pour tout k≥ 0.

Propriété 10 (Débit du processus)Soit π le vecteur des probabilités stationnairesdu processus de Markov de générateur infinitésimalD =

∑+∞k=0 D(k), c’est-à-dire le

vecteur satisfaisant le systèmeπD = 0, πe = 1. Le débit du trafic modélisé par leprocessus B.M.A.P. est

λ = π

+∞∑

k=1

kD(k)e (12.75)

28

12.3.2. Densité de la classe des processus B.M.A.P. dans celle des processus ponc-tuels

N’importe quel processus ponctuel marqué peut être approché par un processusB.M.A.P. Cette propriété a été démontrée par MM. A et K (cf. [2]). Lasuite de ce paragraphe est tirée de cet article. L’importance de ce résultat est due à ceque les processus B.M.A.P. conduisent à des problèmes solubles analytiquement alorsque ce n’est pas le cas des processus ponctuels marqués dans le cas général. Cettepropriété peut être utilisée pour démontrer celles d’un système dans le cas généraloù un processus ponctuel marqué y intervient, après les avoir démontrées dans le casdes processus B.M.A.P., et en vérifiant les conditions de continuité par lesquelles ellessont toujours vraies lorsque la suite des processus B.M.A.P. converge vers le processusponctuel marqué. Ainsi pourrait-on prouver qu’une certaine politique de gestion de filed’attente est optimale en termes de temps de réponse dans le cas général où le trafic enentrée est un processus ponctuel marqué, après l’avoir démontré dans le cas où c’estun processus B.M.A.P. et avoir vérifé les conditions de continuité.

Démontrons tout d’abord le lemme suivant, tiré de [13]

Lemme 1 Soit G(y1, · · · , yn) la fonction de répartition d’un n-uplet de variables aléa-toires non négatives(y1, · · · , yN).

∑

0≤ki≤[riλi ]i=1,··· ,N

P

(k1 − 1λ1

< Y1 ≤k1

λ1, · · · ,

kN − 1λN

< YN ≤kN

λN

)

×

N∏

i=1

Ekiλi

(yi) (12.76)

converge simplement vers G(y1, · · · , yn) quand ri etλi tendent vers+∞ pour tout i.

Par le principe d’inclusion et d’exclusion, on peut réécrire (12.76) sous la forme :

∑

0≤ki≤[riλi ]i=1,··· ,N

G

(k1

λ1, · · · ,

kN

λN

) N∏

i=1

(Ekiλi

(yi) − Eki+1λi

(yi)). (12.77)

Remarquons queEkiλi

(yi)−Eki+1λi

(yi) est égal à ((λiyi)ki/ki !)e−λiyi . SoientXi , i = 1, · · · ,NN variables indépendantes telles queλiXi suit une loi de Poisson de paramètreλiyi .On peut alors réécrire (12.77) comme :

E

[G

(X11

(X1 ≤

⌊r1λ1⌋

λ1

), · · · ,XN1

(XN ≤

⌊rNλN⌋

λN

))](12.78)


CommeXi est de moyenneyi et de varianceyi/λi , qui tend vers 0 quandλi tend vers+∞, on voit que (12.78) tend versG (y1, · · · , yN) si (y1, · · · , yN) est un point de conti-nuité de G. Q.E.D.

Soit S = {(Tn,Yn)}n∈N un processus ponctuel marqué.Tn représente des temps entrearrivées etYn un nombre d’arrivées (les "marques").

Soit S(m) ={(

T(m)n ,Y

(m)n

)}n∈N

une suite de processus ponctuels marqués.

S(m) converge simplement versS si et seulement si, pour toutN,{(

T(m)n ,Y

(m)n

)}n≤N

converge simplement vers{(Tn,Yn)}n≤N.

Par ailleurs, on peut écrire n’importe quel processus marqué N de la formeN =∑+∞n=1 δ(Vn,Yn) oùVn est la date de la nième arrivée,Yn sa marque etδ la mesure de Dirac.

On pose alorsT0 = V0, Tn = Vn − Vn−1, pourn = 1,2, · · · et on définit l’opérateurStel queS (N) = {(Tn,Yn)}n≤N.

Propriété 11 SoitN un processus ponctuel marqué. S’il existe une suite de tels pro-cessusN (m) telle queS

(N (m))

converge simplement versS (N) quand m tend vers

+∞, alorsN (m) converge simplement versN .

En effet, soitN ( f ) =∑+∞

n=0 f (Vn,Yn) pour f : R2 → R. Il suffit de montrer queN (m) ( f ) converge simplement versN ( f ) pour f continue sur un support compactB.On définit f N : R2N+2 → R par

f N (x0, · · · , x2N+1) =N∑

n=0

f (x0 + x2 + · · · + x2n, x2n+1)

(si x0, x2, · · · , x2n sont des temps entre arrivées,x0+x2+· · ·+x2n est une date d’arrivée).Alors, f N est bornée et continue et donc,

∑Nn=0 f

(V(m)

n ,Y(m)n

)converge simplement vers

∑Nn=0 f (Vn,Yn) pour toutN. Soientǫ > 0, b < +∞ et N tel queB ⊆ [0;b] × (0;+∞) et

P (VN ≤ b) < ǫ. Alors, P(V(m)

N ≤ b)< ǫ aussi pour toutmsuffisamment grand et donc

P

N (m) ( f ) ,N∑

n=0

f(V(m)

n ,Y(m)n

) < ǫ

et

P

N ( f ) ,N∑

n=0

f (Vn,Yn)

< ǫ

30

Commeǫ est arbitraire,N (m) ( f ) converge simplement versN ( f ) quandm tend vers+∞. Q.E.D.

Propriété 12 (Densité de la classe des B.M.A.P. dans celle desprocessus ponctuels)Soient un processus ponctuel marquéS et son processus ponctuel de comptage associéN .

– Il existe une suite{S(m)}

de processus M.A.P. qui converge simplement versS

quand m tend vers+∞.

– Il existe une suite{N (m)}

de processus M.A.P. qui converge simplement versN

quand m tend vers+∞.

Montrons qu’il existe une suite{S(m)}

de processus M.A.P. qui converge simplement

versS quandm tend vers+∞, l’autre propriété sur la convergence de{N (m)}

versNen découlant immédiatement de part la propriété 11.

Pour touth, soit H la partie entière deh−1 : H =⌊h−1⌋. On définit l’opérateurτ = τ(h)

par :

τ(h)(y) = 1 si 0< y < 2hτ(h)(y) = k si kh< y < (k+ 1)h, pour 2≤ k ≤ H2 − 1τ(h)(y) = H2 si y > H2.

SoitS(h) le processus ponctuel marqué obtenu à partir deS = {(Tn,Yn)} en remplaçantYn par Y(h)

n = τ (Yn) h et Tn par une variable aléatoireτ(h)n suivant une loi d’Erlang à

τ (Tn) étages et d’intensitéh−1 ; en représentant ainsiτ(h)n comme la somme deτ (Tn)

variables aléatoires exponentielles, on les suppose indépendantes mutuellement et in-dépendantes deN . Par le lemme 1,S(h) converge simplement versS quandh tendvers 0. Pour compléterla preuve, il suffit donc de trouver une suiteS(h,m) qui convergesimplement versS(h) quandm tend vers+∞.

Utilisons la représentation équivalente{(

S(h)n ,Y

(h)n

)}de N (h) où S(h)

n est le nombre

d’étages deT(h)n . Pour toutm, on définit l’espace d’étatsEh,m pourS(h,m) par

Eh,m = {(s0, k0, y0) , (s1, y1) , · · · , (sm, ym) ;

1 ≤ sn ≤ H,1 ≤ yn ≤ H,1 ≤ k0 ≤ s0} (12.79)

Les taux de transitions du type

(s0, k0, y0) , (s1, y1) , · · · , (sm, ym)

→ (s0, k0 − 1, y0) , (s1, y1) , · · · , (sm, ym) (12.80)


pour k0 ≥ 2 sont pris égaux àh−1, tandis que ceux correspondant aux transitions dutype

(s0,1, y0) , (s1, y1) , · · · , (sm, ym)

→ (s1, s1, y1) , · · · , (sm, ym) , (sm+1, ym+1) (12.81)

sont choisis arbitrairement sous la contrainte que la sommesur tous les états(sm+1, ym+1)doit être égale àh−1. En termes de matricesD(0) et D(k>0) définissant un B.M.A.P.,les transitions de la forme (12.80) correspondent aux éléments non diagonaux de lamatriceD(0) tandis que celles de la forme (12.81) correspondent àD(k>0). À chaquetransition (12.81), correspond une arrivée de marquey1, l’arrivée suivante se produi-sant aprèss1 phases, tandis qu’à chaque transition (12.80), il n’y a aucune arrivée. Parconséquent, si le processus B.M.A.P. est tel que

{J(h,m)

t

}(12.82)

commence dans l’état

((S0,S0,Y0) , (S1,Y1) , · · · , (Sm,Ym)) , (12.83)

{(T(h,m)

n ,Y(h,m)n

)}n≤m

(12.84)

et

{(T(h)

n ,Y(h)n

)}n≤m

(12.85)

ont même distribution et, donc,S(h,m) converge simplement versS(h). Q.E.D.

Par ailleurs, on peut montrer (cf. [2]) les corollaires suivants.

Propriété 13 SiS est stationnaire, on peut choisirS(m) qui soit aussi stationnaire (1),et de même pourN etN (m) (2).

Propriété 14 Dans le théorème 12, on peut choisirS(m) tel queE[T(m)

np]

tende vers

E

[Tp

n

]etE[Y(m)

np]

tende versE[Yp

n

], pour tout p< +∞.

32

12.3.3. Cas discret : D.-B.M.A.P.

Le modèle D.-B.M.A.P. a été proposé par M. B (cf. [6]). Dans le cas discret,la définition du processus D.-B.M.A.P. est analogue à celle d’un B.M.A.P., et la ma-trice de transition de la chaîne de Markov a la même forme que dans le cas continu,excepté le fait qu’elle est stochastique, c’est-à-dire quela somme des éléments d’uneligne est égale à 1 :

+∞∑

k=0

m∑

j=1

d(k)i, j = 1. (12.86)

La matrice de transition est donnée par :

(P(Jn = j′, Ln = k,Xn = ν

/Jn−1 = j

))1≤ j≤m1≤ j′≤m

=(D(0))ν

D(k) (12.87)

Le processus{N(k), J(k)}k≥0, où N(k) est la variable de comptage etJ(k) la phase, estun processus de Markov à temps discret sur l’espace d’états{(n, j) ; n ≥ 0,1 ≤ j ≤ m},de matrice de transition :

D =

D(0) D(1) D(2) D(3) · · ·

0 D(0) D(1) D(2) · · ·

0 0 D(0) D(1) · · ·...

......

.... . .

.

(12.88)

La matriceD =∑+∞

n=0 D(n) est la matrice de transition de la chaîne de Markov sous-jacente.π étant le vecteur de ses probabilités stationnaires limites, i.e. :

πD = π (12.89)

πe = 1, (12.90)

oùeest le vecteur colonne composé de 1 partout.


Le débit d’arrivée de ce processus est donné par

λ = π

+∞∑

k=1

kD(k)

e (12.91)

Soit (X1, · · · ,Xk) un ensemble de variables aléatoires, oùXi est le nombre d’arrivéesà l’instanti. On notef (x1, · · · , xk) la matrice de la distribution jointe de(X1, · · · ,Xk),c’est-à-dire quefi j (x1, · · · , xk) est la probabilité conditionnelle queX1 = x1, · · · ,Xk =

xk et que la phase du processus d’arrivée à l’instantk soit égale àj, sachant que leprocessus à démarré dans l’étati à l’instant 0. Soitf (z1, · · · , zk) la transformée enzcorrespondante. On a clairement

f (z1, · · · , zk) = D (z1) · · ·D (zk) , (12.92)

oùD (z) =∑+∞

i=0 D(i)zi .

La corrélation entre deux variables aléatoiresX1 et Xk s’exprime à partir de la matricede covariance

COV (X1,Xk)

=

+∞∑

x1=0

· · ·

+∞∑

xk=0

(x1 − µ1) (xk − µk) f (x1, · · · , xk)

= � [X1Xk] − µ1� [Xk] − µk� [X1] + µ1µkf (1, · · · ,1) , (12.93)

µ1 et µk étant des scalaires, respectivement les moyennes deX1 et Xk. La fonction decovariance (scalaire) est alors donnée par

COV(X1,Xk) = πCOV (X1,Xk) e

= π� [X1Xk] e− µ1µk. (12.94)

Rappelons que le coefficient d’autocorrélation est définit comme étant

ρ (X1,Xk) =COV(X1,Xk)σX1σXk

(12.95)

34

oùS2Xi

est la variance deXi , 1 ≤ i ≤ k.

Les matrices des moyennes� [X1], � [Xk] et� [X1Xk] sont données par

� [X1] =∂

∂z1f (z1, · · · , zk) |zi=1 =

+∞∑

l=1

lD(l)

Dk−1 (12.96)

� [Xk] =∂

∂zkf (z1, · · · , zk) |zi=1 = Dk−1

+∞∑

l=1

lD(l)

(12.97)

� [X1Xk] =∂2

∂z1∂zkf (z1, · · · , zk) |zi=1 =

+∞∑

l=1

lD(l)

Dk−2

+∞∑

l=1

lD(l)

. (12.98)

Pour un D.-B.M.A.P. stationnaire, le nombre moyen d’arrivées par unité de temps estdonné par le taux moyenλ, de telle sorte qu’on obtient pourµ1 etµk

µ1 = µk = π

+∞∑

l=1

lD(l)

Dk−1e= λ. (12.99)

Finalement, la matrice de covariance deX1 et Xk est

COV (X1,Xk) =

+∞∑

l=1

lD(l) − λD

Dk−2

+∞∑

l=1

lD(l) − λD

(12.100)

et la covariance scalaire

COV(X1,Xk) = π

+∞∑

l=1

lD(l)

Dk−2

+∞∑

l=1

lD(l)

e− λ2. (12.101)

De cette expression, on déduit le coefficient d’autocorrélation

ρ (X1,Xk) =π[∑+∞

l=1 lD(l)]Dk−2

[∑+∞l=1 lD(l)

]e− λ2

π[∑+∞

l=1 l2D(l)]e− λ2

. (12.102)


La superposition de deux processus D.-B.M.A.P. de paramètres des familles de ma-tricesD(k)(i) i = 1,2 est le processus D.-B.M.A.P. de paramètres

D(k) =

k∑

ν=0

D(ν)(1) ² D(k−ν)(2) pourk ≥ 0 (12.103)

Attention, dans le cas discret, contrairement au cas continu, des arrivées de plusieursprocessus différents peuvent survenir simultanément.

12.3.4. Application du modèle D.-B.M.A.P. : une approximation de lasuperpositionde sources sporadiques

L’exemple présenté dans ce paragraphe concerne la classe des D.-B.M.A.P. Il estextrait de l’article [6]. Supposons le temps discret. Considérons une source de traficalternant des périodes d’activité et d’autres de silence. Une telle source est dite spora-dique. On suppose que la durée des périodes actives est distribuée géométriquementde moyennep et de même pour celle des silences, de moyenneq. Au cours d’une pé-riode d’activité, la source envoie des paquets à intervalles de temps constantsd. À uninstant donné, la probabilité de passer dans une période de silence lorsque la sourceest active est donc deβ = 1/p, et celle de passer dans un état actif lorsqu’elle estsilencieuse est deα = 1/q.

Supposons maintenant queM sources soient ainsi superposées. Le processus résultanta deux caractéristiques importantes : d’une part il présente une certaine périodicitédue à la périodicité du trafic d’une source pendant ses périodes d’activité, et d’autrepart il est modulé par le nombre de sources actives. Un modèledétaillé dans lequelceci serait décrit précisément conduirait à un D.-B.M.A.P.avec un très grand nombred’états. Pour éviter cela, on modélise le processus du nombre de sources actives parun processus de naissance et de mort àM + 1 états : on fait l’approximation qu’à uninstant donné, seule une source peut changer d’état, soit passer de l’état inactif à celuiactif, soit l’inverse. La matrice de transition d la chaîne de Markov correspondante estalors

1− Mα Mα 0 · · · 0 0β 1− β − (M − 1)α (M − 1)α · · · 0 00 2β 1− 2β − (M − 2)α · · · 0 00 0 · · · · · · 0 0...

......

. . ....

...

0 0 0 · · · Mβ 1− Mβ

.

36

Quand cette chaîne est dans l’étatm, lesm sources actives engendrent du trafic selonune distribution très complexe, due au comportement déterministe de chaque sourceactive. Pour garder le nombre d’états raisonnable, on suppose que le nombre d’arrivéesà un instant donné ne dépend que dem. On néglige donc une certaine dépendance entreles nombres d’arrivées. Soitck(m) la probabilité d’avoirk arrivées à un instant donnéquand la chaîne est dans l’étatm. En supposant alors que chaque source active à uneprobabilité d’émission de 1/d à chaque instant,

ck(m) = Ckm

(1d

)k (1−

1d

)m−k

. (12.104)

En posantD(n) = CnD où

Cn =

cn(0)cn(1)

· · ·

cn(i)· · ·

cn(M)

. (12.105)

Clairement, le processus ainsi défini est un processus D.-B.M.A.P. de paramètresD(n).

Étudions les performances d’une file entrée de laquelle un tel processus est placé.On s’intéresse à la file D.-B.M.A.P./G/1/N, file à temps de service discret, distribuéselon une loi quelconque, à un serveur et de capacité finie N. Les services sont suppo-sés indépendants et identiquement distribués (i.i.d.), dedistribution quelconque et detransformée enz G(z) =

∑+∞k=1 gkzk.

Soit{A(k)

n

}i, j

la probabilité conditionnelle que dans l’intervalle ]0;k] il y ait n arrivées

et qu’à la fin la phase du processus soitj, sachant que le processus était dans l’étati àl’instant 0. Si on noteD(z) =

∑n=0+∞,

A(k)(z) =

+∞∑

n=0

A(k)n zn =

[A(1)(z)

]k= [D(z)]k . (12.106)

Soit {An}i, j la probabilité qu’il y aitn arrivées pendant un service et que la phase duprocessus soitj, sachant qu’il a démarré dans l’étati.

An =

+∞∑

k=1

gkA(k)n (12.107)


en prenantg0 = 0. Soit

A(z) =+∞∑

n=0

Anzn et A = A(1). (12.108)

Soit de plus{Bn}i, j la probabilité qu’il y ait eu au moment d’un départn + 1 arrivéesdepuis le départ précédent et que la phase du processus soitj, sachant qu’elle étaitégale ài au moment du précédent départ et que celui-ci a laissé la file vide. On peutmontrer que

Bn = (I − D0)−1n∑

j=0

D j+1An− j . (12.109)

Soit B(z) =∑+∞

n=0 Bnzn, alors

B(z) = z−1 (I − D0)−1 [D(z) − D0] A(z), (12.110)

et

B = B(1) = (I − D0)−1 [D − D0] A. (12.111)

On regarde le système aux instants de départst0, t1, t2, · · · . Soit L(tk) le nombre declients dans la file aux instanttk et soitJ (tk) la phase du processus d’arrivée àtk. Clai-rement, le processus{(L (tk) , J (tk) , tk+1 − tk) k ≥ 0} est un processus semi-markoviend’espace d’états{0,1, · · · ,N − 1} × {1, · · · ,m} ×N. Notons la distribution de probabi-lité du processus joint de la longueur de la file et de la phase du processus d’arrivéesaux instants de départs de la file par

x = {x0, · · · , xN−1} , (12.112)

où

xn =(xn,1, · · · , xn,m

), 0 ≤ n ≤ N − 1, (12.113)

38

avec

xn, j = limk→+∞

P (L (tk) = n, J (tk) = j) . (12.114)

Le vecteurx est le vecteur des probabilités stationnaires de la matriceirréductible

Q =

B0 B1 B2 · · · BN−2∑+∞

n=N−1 Bn

A0 A1 A2 · · · AN−2∑+∞

n=N−1 An

0 A0 A1 · · · AN−3∑+∞

n=N−2 An...

...... · · ·

......

0 0 0 · · · A0∑+∞

n=1 An

. (12.115)

La structure deQ montre que ce système est conduit par une chaîne de Markov dutype M/G/1.

Pour calculer les probabilités stationnaires d’état de cette chaîne, on applique le ré-sultat suivant (cf. [14]) également utilisé par MM. G, T et H dans[9]. Considérons la matricem×m de la forme

X0 =

(x ba′ Y1

), (12.116)

où a′ et b sont des vecteurs de dimensionm−1 etY1 est une matrice (m−1)× (m−1).Considérons la matriceX1 qui est obtenue en ajoutant aux probabilités de transitionde l’étati à l’état j,2 ≤ i, j ≤ m, les transitions qui vont dei à j via l’état 1 :

X1 = Y1+ a′ (1− x)−1 b. (12.117)

Le vecteur des probabilités stationnaires d’état deX0 peut être facilement calculé àpartir de celui deX1. En appliquant cette méthode plusieurs fois, on obtient unesuitede matrices de dimension décroissanteX0,X1,X2, · · · ,Xm. Le dernier élémentXm estun scalaire. On peut alors calculer récursivement le vecteur des probabilités station-naires d’état deX i , i = m− 1,m− 2, · · · ,1, et finalement obtenir celui deX0.

On applique cette méthode, généralisée aux matrices blocs,à la chaîne de Markovprécédente de type M/G/1. On pose

∞∑

n=N−1

Bn = BN−1 et∞∑

n=k

An = Ak. (12.118)


Après la première itération, et notant

C1,i = A i+1 + A0 (I − B0)−1 Bi+1, 0 ≤ i ≤ N − 3 (12.119)

C1,N−2 = AN−1 + A0 (I − B0)−1 BN−1, (12.120)

on arrive à la matrice bloc suivante (le nombre de lignes et decolonnes est diminué dela dimension d’un bloc)

Q1 =

C1,0 C1,1 C1,2 · · · C1,N−3 C1,N−2

A0 A1 A2 · · · AN−3 AN−2

0 A0 A1 · · · AN−4 AN−3...

...... · · ·

......

0 0 0 · · · A0 A1

(12.121)

L’élément (j, k) de la matriceC1,i est la probabilité que le processus passe dans unniveau supérieur ou égal à 1 pour la première fois en atteignant l’état (i+1, k), sachantqu’il démarre dans l’état (1, j). Une interprétation probabiliste similaire est possiblepour la matriceC1,N−2. On peut remarquer que la matriceQ1 est en core du typeM/G/1. En appliquant le résultat de M. G k fois, on obtient

Qk =

Ck,0 Ck,1 Ck,2 · · · Ck,N−k−2 Ck,N−k−1

A0 A1 A2 · · · AN−k−2 AN−k−1

0 A0 A1 · · · AN−k−3 AN−k−2...

...... · · ·

......

0 0 0 · · · A0 A1

, (12.122)

avec, pour 0≤ i ≤ N − k− 2, 2 ≤ k ≤ N − 2,

Ck,i = A i+1 + A0(I − Ck−1,0

)−1 Ck−1,i+1, (12.123)

Ck,N−k−1 = AN−k + A0(I − Ck−1,0

)−1 Ck−1,N−k (12.124)

Finalement, on obtient la matrice

QN−1 = A1 + A0(I − CN−2,0

)−1 CN−2,1. (12.125)

40

Soit le vecteurxN−1 vérifiant

xN−1QN−1 = xN−1. (12.126)

Le vexteur(xN−1 xN−2) des probabilités stationnaires limites deQN−2 peut être calculéfacilement en utilisant

xN−2 = xN−1A0(I − CN−2,0

)−1 . (12.127)

Plus généralement, le vecteur(x0, x1, · · · , xN−1) peut être déterminé en utilisant lesformules récursives suivantes

xN−1

[A1 + A0

(I − CN−2,0

)−1 CN−2,1

]= xN−1, (12.128)

xk = xk+1A0(I − Ck,0

)−1 ,1 ≤ k ≤ N − 2, (12.129)

x0 = x1A0 (I − B0)−1 . (12.130)

La complexité de cet algorithme est de l’ordre deM3N2, où M est la dimension d’unbloc, etN est le nombre de lignes de blocs. La mémoire nécéssaire est 2M2N. En effet,il suffit de stocker les deux premières lignes

(B0 B1 B2 · · · BN−2 BN−1

A0 A1 A2 · · · AN−2 AN−1

). (12.131)

A chaque fois que la méthode de M. G est appliquée, on utilise la pre-mière ligne pour stocker les matricesCk,i et Ck,N−k−1, puisque les matricesBk, k =1, · · · ,N − 2 etBN−1 ne sont plus utilisées après la première itération. De plus,la ma-trice A0

(I − ck,0

)−1 est aussi stockée dans la première ligne et peut être utilisée pourl’évaluation du vecteurxk.

Notons de la façon suivante la distribution de probabilité de la loi jointe de la longueurde la file d’attente et de la phase du processus d’entrée à n’importe quel instantt ∈ N

y (n, j; t/ n0, j0) = P ( L(t) = n, J(t) = j/ L(0) = n0, J(0) = j0) , (12.132)


et

y (n, j) = limt→+∞

y (n, j; t/ n0, j0) (12.133)

yn = (y (n,1) , · · · , y (n,m)) (12.134)

On peut montrer (cf. [6]) que le temps moyen entre deux départs de la file est donnépar

E∗ = E [G] + x0 (I − D0)−1 e. (12.135)

et que les vecteursyn s’obtiennent à partir des formules de récurrence suivantes:

y0 =1E∗

x0 (I − D0)−1 (12.136)

yn+1 =

n∑

i=0

yiDn+1−i +1E∗

(xn − xn+1)

(I − D0)−1 , 0 ≤ n < N − 1, (12.137)

yn = π −

N−1∑

n=0

yn. (12.138)

À partir de ces probabilités d’état on peut déterminer la probabilité de perte depaquet. Celle-ci est le rapport du nombre moyen de paquets perdus par unité de tempssur le nombre moyen d’arrivées par unité de temps, d’où

Pb =1

π(∑+∞

k=1 kDk

)e

N∑

n=0

+∞∑

k=1

max(0, (k− N + n) i) ynDke

. (12.139)

12.4. Les modèles modulés par un processus de Poisson

Cette classe de modèles est encore appelée selon la terminologie anglo-saxoneM.M.P.P., pour "Markov Modulated Poisson Process". C’est un sous-ensemble de laclasse des modèles M.A.P.

42

On a vu que la modélisation du trafic par un processus de Poisson présente beaucoupd’avantages, notamment dans le fait qu’on peut réutiliser toute la théorie des filesd’attente pour étudier les performances des systèmes considérés. On peut par exemplereprésenter un débit par un processus de Poisson.

Par ailleurs, il est évident intuitivement que le trafic varie dans la journée : à cer-taines heures "de pointe", le réseau doit être plus chargé qu’aux "heures creuses"(cf. Fig. 12.3). Il est donc naturel, si on modélise le trafic par un processus de Poisson,de prévoir de faire varier dans le temps le taux du processus de Poisson. Un moyen estde considérer que ce taux est lui aussi une variable aléatoire, suivant par exemple unechaîne de Markov. Si l’on considère le débit, celui-ci est modélisé par deux variablesaléatoires : le débit proprement dit qui suit une loi de Poisson de tauxλ et le tauxλlui-même qui suit une chaîne de Markov. C’est le principe du modèle M.M.P.P.

L’avantage de ce modèle est qu’il permet de bien rendre compte des variations dutrafic sur plusieurs échelles de temps et qu’il reste suffisamment simple pour pouvoirêtre utilisé analytiquement. La suite de cette partie est essentiellement tirée de l’article[8] et des références qui y sont mises.

0

0.05

0.1

0.15

0.2

0.25

0.3

0 5 10 15 20

Figure 12.3 – Exemple de débit moyen dans un réseau en fonction de l’heure dans lajournée

12.4.1. Définition et propriétés du modèle M.M.P.P.

Un processus M.M.P.P. est un processus de Poisson de taux d’arrivéeλ∗ [J (t)], oùJ (t), t ≥ 0, est un processus de Markov irréductible à m états et à tempscontinu.Quand la chaîne de Markov est dans l’état i, le taux d’arrivéeestλi .


On noteQ le générateur infinitésimal de la chaîne de Markov

Q =

−σ1 σ12 · · · σ1m

σ21 −σ2 · · · σ2m...

.... . .

...

σm1 σm2 · · · −σm

oùσi =

m∑

j=1, j,i

σi j (12.140)

etΛ etλ les matrices suivantes

Λ = diag(λ1, λ2, · · · , λm) (12.141)

λ = (λ1, λ2, · · · , λm)T (12.142)

Dans la suite, on suppose que la chaîne de Markov est homogène, c’est-à-dire qu’ellene dépend pas du temps t.

Le vecteurπ des probabilités d’état de la chaîne de Markov est obtenu parles formulesclassiques :

πQ = 0, πe= 1 (12.143)

oùe= (1,1, · · · ,1)T

Dans le cas oùm= 2,

π = (π1, π2) =1

σ1 + σ2(σ2, σ1) (12.144)

Le processus M.M.P.P. est un processus de renouvellement markovien (cf. p.23) uni-quement sous certaines conditions. Ce n’est généralement pas un processus de re-nouvellement, mais un processus de renouvellement markovien. En effet, considérons

44

deux arrivées successives, et supposons que l’état de la chaîne de Markov modulatricesoit i lors de la première arrivée etj lors de la seconde. Entre ces deux événements, ily a une transition de la chaîne dei à j via plusieurs autres états, suivis d’un nombregéométrique de retours àj sans arrivée jusqu’à ce qu’il y en ait une. Le temps entredeux arrivées n’est donc pas exponentiel. La matrice de transition du processus derenouvellement markovien correspondant est donnée plus loin (cf. p.48).

Propriété 15 (M.M.P.P. et processus de renouvellement)Le processus M.M.P.P.est un processus de renouvellement si et seulement si

– Le débit d’arrivée prend des valeursλ > 0 et 0 alternativement sur des in-tervalles successifs d’un processus de renouvellement alternatif (i.e. : à deux états)stationnaire.

– Les temps entre arrivées quandλ > 0 sont distribués exponentiellement.

Une condition suffisante pour qu’un processus M.M.P.P. soit un processus de renou-vellement est qu’il n’y ait d’arrivées que dans un seul état de la chaîne de Markovsous-jacente. C’est le cas du processus de Poisson interrompu (I.P.P. pour InterruptedPoisson Process dans la littérature anglo-saxonne). Toutefois, cette condition est suf-fisante mais non nécessaire : il y a d’autres processus M.M.P.P. qui sont des processusde renouvellement sans avoir des arrivées que dans un seul état.

Définition 12 (Processus I.P.P.)Le processus I.P.P. est un processus M.M.P.P. à deuxétats : un état 0 pendant lequel il n’y a pas d’arrivée et un état 1 pendant lequel lesarrivées se font selon un processus de Poisson. Il est caractérisé par le générateurinfinitésimal et les débits des processus de Poisson suivants :

Q =

[−σ1 σ1

σ2 −σ2

]Λ =

[λ 00 0

](12.145)

Le processus I.P.P. est un processus hyperexponentiel. Notonsp, µ1 etµ2 tels que

fH2(t) = pµ1e−µ1t + (1− p) µ2e−µ2t (12.146)

fH2(t) est la densité d’une loi hyperexponentielle.


Propriété 16 (Relation entre I.P.P. etfH2(t)) Le processus I.P.P. est un processus hy-perexponentiel avec

p =λ − µ2

µ1 − µ2(12.147)

µ1 =12

(λ + σ1 + σ2 +

√(λ + σ1 + σ2)2 − 4λσ2

)(12.148)

µ2 =12

(λ + σ1 + σ2 −

√(λ + σ1 + σ2)2 − 4λσ2

)(12.149)

Le processus hyperexponentiel est un processus I.P.P. avec:

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

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

λ(12.151)

σ2 =µ1µ2

λ(12.152)

Enfin, la superposition dem processus M.M.P.P. indépendants de paramètres(Qi ,Λi)est aussi un processus M.M.P.P. de paramètre(Q,Λ) où

Q = Q1 ¹ Q2 ¹ · · ·¹ Qm (12.153)

Λ = Λ1 ¹ Λ2 ¹ · · ·¹ Λm (12.154)

où¹ désigne la somme de Kronecker (cf. §12.3.1).

Si les processus superposés sont des processus M.M.P.P. à deux états identiques, leprocessus résultant s’exprime retativement simplement. Soient Qn et Λn ses para-mètres, et

Q =

[−σ1 σ1

σ2 −σ2

], Λ =

[λ1 00 λ2

], (12.155)

46

[Qn] i,i = −iσ1 − (n− i)σ2, 0 ≤ i ≤ n (12.156)

[Qn] i,i−1 = iσ1, 1 ≤ i ≤ n− 1 (12.157)

[Qn] i,i+1 = (n− i)σ2, 0 ≤ i ≤ n− 1 (12.158)

0, partout ailleurs (12.159)

et

λn = diag(iλ1 + (n− i)λ2) , 0 ≤ i ≤ n. (12.160)

Les dimensions deΛn et Qn sont alors den+ 1.

12.4.2. Fonction de comptage associée au processus M.M.P.P.

SoientNt le nombre d’arrivées dans l’intervalle [0;t], Jt l’état du processus de Markovà l’instantt et

Pi j (n, t) = Pr (Nt = n, Jt = j /N0 = 0, J0 = i ) . (12.161)

l’élément d’indice (i, j) de la matriceP (n, t). Cette matrice est solution de l’équationde Chapman-Kolmogorov

ddt

P(n, t) = P(n, t) (Q− Λ) + P(n− 1, t)Λ pour n ≥ 1, t ≥ 0,

P(0,0) = I(12.162)

La fonction génératriceP∗(z, t) =∑+∞

n=0 P(n, t)zn est alors solution de l’équation

ddt

P∗(z, t) = P∗(z, t) (Q− Λ) + zP∗(z, t)Λ,

P∗(z,0) = I,(12.163)

d’où l’on déduit que :

P∗(z, t) = e(Q−(1−z)Λ)t. (12.164)


Cette fonction génératrice permet d’obtenir les moments deNt. La matrice des moyennesest :

M(t) =

[∂

∂zP∗(z, t)

]

z=1

, (12.165)

d’éléments :

Mi j (t) =

+∞∑

n=0

nPi j (n, t). (12.166)

La dérivation de la fonction génératrice donne :

M(t) =

+∞∑

n=1

tn

n!

n−1∑

ν=0

QνΛQn−1−ν. (12.167)

Le vecteurµ(t) = M(t)ea pour expression :

µ(t) = eπλt +(eQt − I

)(Q+ eπ)−1 λ. (12.168)

Le vecteur(Q+ eπ)−1 λ a une propriété intéressante. En faisant tendret vers+∞ dansl’expressionµ(t) − eπλt, on remarque que leiième élément de(Q+ eπ)−1 λ est la dif-férence entre l’espérance du nombre d’arrivées du processus M.M.P.P. sachant qu’ila démarré dans l’étati à l’instantt = 0, et l’espérance du nombre d’arrivées pour unprocessus de Poisson de tauxπλ (taux moyen d’arrivées du M.M.P.P.), quandt → +∞.

Lorsque le processus M.M.P.P. est stationnaire (en particulier lorsque le vecteur desprobabilités de l’état initial de la chaîne de Markov est choisi égal au vecteur desprobabilités stationnaires de cette même chaîne),

E [Nt] = πµ(t) (12.169)

= πλt. (12.170)

48

On obtient le second moment deNt d’une façon analogue. Après quelques calculsalgébriques, on arrive à :

µ2(t) =

[∂2

∂z2P∗(z, t)

]

z=1

e (12.171)

= 2+∞∑

n=2

tn

n!

n−2∑

r=0

QrΛQn−2−rλ (12.172)

= 2[M(t) (Q+ eπ)−1 −

(eQt − I

)(Q+ eπ)−1Λ (Q+ eπ)−1

−teπΛ (Q+ eπ)−1 +[eQt − I − Qt

](Q+ eπ)−2 λπ

+t2

2eπλπ

]λ, (12.173)

Lorsque le processus M.M.P.P. est stationnaire,

πµ2(t) = E

[N2

t

]− E [Nt]

= t2 (πλ)2 + 2t[(πλ)2 − πΛ (Q+ eπ)−1 λ

]

+2πΛ(eQt − I

)(Q+ eπ)−2 λ, (12.174)

avec

eπ =

π1 π2 · · · πm

π1 π2 · · · πm....... . .

...

π1 π2 · · · πm

(12.175)

12.4.3. Matrice des probabilités de transition du processus de renouvellement mar-kovien M.M.P.P.

NotonsJk l’état du processus modulateur au moment de la kième arrivée. La pro-babilité infinitésimale que le temps entre lak − 1ème arrivée et lakème soit compriseentrex et x+ dx est la probabilité de ne pas avoir d’arrivée dans un intervalle [0 : x]et d’en avoir une dans l’intervalle [x; x+ dx] :


dFi j (x) = P (Jk = j, x ≤ Xk < x+ dx /Jk−1 = i ) (12.176)

= P (Jk = j,Nx = 0 /Jk−1 = i ) × λ jdx (12.177)

= Pi j (0, x) × λ jdx (12.178)

d’où

dFi j (x)

dx= Pi j (0, x) × λ j (12.179)

soit, en écriture matricielle, commePi j (0, x) = P∗i j (0, x) :

dF(x)dx

= e(Q−Λ)xΛ (12.180)

et donc,

F(x) =

∫ x

0e(Q−Λ)xduΛ

=[I − e(Q−Λ)x

](Λ − Q)−1Λ

=[I − e(Q−Λ)x

]F(∞) (12.181)

La matriceF(∞) = (Λ − Q)−1Λ est stochastique et correspond à la matrice desprobabilités de transition de la chaîne de Markov imbriquéeaux instants d’arrivées.On peut montrer que la distribution stationnaire limite deF(∞) est donné par :

p =1πλ.πΛ. (12.182)

50

12.4.4. Temps entre deux arrivées

À partir de la matrice des probabilités de transition du processus M.M.P.P., don-née par (12.181), on peut déterminer l’espérance des tempsXk entre deux arrivées, ladeuxième arrivée étant dans l’étatj, conditionnellement au fait que la première arri-vée se fait dans l’étati. Pour obtenir ces moments conditionnels, le plus simple estdepasser par la transformée de Laplace de (12.181). Celle-ci apour expression :

f ∗(s) = E

[e−sX]

=

∫ +∞

0e−sxdF(∞)

dxd f

=

∫ +∞

0−e−sxe(Q−Λ)x (Q− Λ) F(∞)dx

=

∫ +∞

0−e−sxe(Q−Λ)x (Q− Λ) (Q− Λ)−1Λdx

=

∫ +∞

0−e−sxe(Q−Λ)xdxΛ

= (Is+ Λ − Q)−1Λ (12.183)

De la même manière, la transformée de Laplace jointef ∗ (s1, · · · , sn) desn ≥ 1 pre-miers temps entre arrivéesX1,X2, · · · ,Xn est, lesXk étant indépendants,

f ∗ (s1, · · · , sn) = E

exp

−n∑

k=1

skXk

=

n∏

k=1

[(skI − Q+ Λ)−1

Λ]. (12.184)

Le facteur correspondant au premier intervalle doit être modifié si l’origine des tempsne correspond pas à une arrivée.


On peut alors calculer les moments conditionnels à partir de(12.184) :

µ′i,k ≡ E

[Xk

i

]

= k![(Λ − Q)−1Λ

]i−1(Λ − Q)−(k+1)Λ, i ≥ 1, k ≥ 1. (12.185)

Notons queµ′i,k est une matrice. Son élément (j, j′) correspond à∫ +∞

0xk

i dF j j ′ .

µi,k+1 ≡ E [X1Xk+1] , k ≥ 1

= (Λ − Q)−2Λ[(Λ − Q)−1Λ

]−(k+1)(Λ − Q)−2Λ. (12.186)

La matrice conditionnelle de corrélation est donnée par :

E [(X1 − E [X1]) (Xk+1 − E [Xk+1])]

= (Λ − Q)−2[(Λ − Q)−1Λ

]k−1×

{I − (Λ − Q)−1Λ

}(Λ − Q)2Λ. (12.187)

Les moments du temps entre arrivées peuvent être obtenus avec un choix judicieux desconditions initiales. En notantTA,i le temps entre laième et la i + 1ème arrivée à l’étatstationnaire du processus M.M.P.P. (qui peut être obtenu par exemple en choisissantF(∞) comme vecteur initial),

E

[Tk

A,i

]= k! p[(Λ − Q)Λ] i−1 (Λ − Q)−(k+1)Λe

= k! p(Λ − Q)−(k+1)Λe, (12.188)

et,

E[(

TA,1 − E[TA,1]) (

TA,k+1 − E[TA,k+1

])]

= p(Λ − Q)−2Λ ×

{[(Λ − Q)−1Λ

]k−1− ep}

(Λ − Q)−2Λe (12.189)

52

avec

pe =

p1 p2 · · · pm

p1 p2 · · · pm......

. . ....

p1 p2 · · · pm

(12.190)

12.4.5. Applications du modèle M.M.P.P. : trafic de débordement, et approximationde trafic par un processus M.M.P.P.

Le modèle M.M.P.P. a essentiellement deux types d’applications. On l’utilise pourrendre compte de trafics dont l’intensité varie au cours du temps. C’est en particulierle cas des trafics de voix faisant alterner des périodes de silence et de parole, ou destrafics de débordement : lorsqu’un lien supporte un trafic quiexcède sa capacité, lapartie du trafic qui déborde peut être vue comme un trafic composé de périodes desilence et d’activité. La deuxième application de ce modèleest de rendre compte d’unecertaine corrélation dans le trafic. Celle-ci est exposée plus loin au paragraphe 12.7.Un modèle dit pseudo-autosimilaire à base de processus M.M.P.P. est présenté.

Comme cas particulier de la première application, remarquons que la superposi-tion de plusieurs trafics peut aussi être modélisée par un processus M.M.P.P. : selonque l’un des trafics est actif ou pas, le processus agrégé passe d’un état du processusM.M.P.P. à un autre. En effet, si dans une superposition de trafics chacun peut être mo-délisé par un processus de Poisson différent et que les durées d’activité de ces traficssont exponentielles, séparées par des temps de silences exponentiels, le flux résultantest clairement un processus M.M.P.P. L’exemple qui suit surle trafic de débordementest tiré de [20].

Trafic de débordement :

Considérons un ensemble de lignes d’abonnés arrivant sur uncommutateur A lui-même relié à plusieurs commutateurs B, C et D par un faisceau de circuits permettantd’écouler le trafic arrivant de A. Il est très rare que l’ensemble de tous les abonnéstéléphonent en même temps, c’est pourquoi, pour des raisonsde coûts l’opérateurdispose entre A et les autres commutateurs un nombre de faisceaux plus petit que lenombre d’abonnés.

La plupart du temps, cela est transparent aux abonnés car ilsne téléphonent pastous en même temps. Toutefois, il peut arriver que le nombre d’abonnés souhaitanttéléphoner dans une direction, par exemple vers C, excède les ressources disponibles ;dans ce cas il y a rejet d’appel. On peut alors utiliser des routes secondaires en redi-rigeant les appels arrivant et ne trouvant pas de ressourcesvers une autre direction,


par exemple vers le commutateur D. Les commutateurs suivants sur cet autre cheminredirigent alors les appels convenablement dans la bonne direction. C’est le mêmeprincipe que celui utilisé avec les itinéraires de délestage dans le trafic routier.

Pour bien dimensionner le réseau, il faut déterminer le tauxde rejet d’appel, dittaux de blocage. Sur le système considéré arrive soit un trafic normal d’appels soit untrafic de débordement. Ce dernier se caractérise par des périodes de silence alternantavec des périodes d’activités : lorsque le trafic arrive sur la route principale et qu’il y asuffisamment de ressources, il n’y a pas de rejet et donc pas de trafic de débordement.Celui-ci est alors silencieux. Quand il n’y a pas assez de ressource il y a redirectiondu trafic de la route principale vers la route alternative et le trafic de débordement estalors non nul. On peut alors modéliser le trafic de débordement par un trafic I.P.P. Celarend bien compte du caractère actif ou inactif de ce trafic.

Le système peut être modélisé par une file avec un tampon de taille k, éventuelle-ment nulle, et c serveurs. Une source de trafic d’appels et m detrafic de débordement ysont placées en entrée. S’il s’agit de trafic téléphonique, le processus d’arrivées d’ap-pel est bien modélisé par un processus de Poisson. On montre aussi que le temps deservice des clients par les serveurs suit une distribution exponentielle de tauxµ.

λ étant le taux d’arrivées du processus de Poisson du flux principal d’appels, onnote(Qi ,Λi) , 1 ≤ i ≤ m les paramètres du flux I.P.P. de débordementi avec :

Qi =

[−σi1 σi1

σi2 −σi2

], Λi =

[λi 00 0

]. (12.191)

Comme le trafic en entrée est une superposition d’un trafic de Poisson et de tra-fics I.P.P., c’est une superposition de trafics M.M.P.P. et donc un trafic M.M.P.P. deparamètres :

Q = Q1 ¹ Q2 ¹ · · ·¹ Qm (12.192)

Λ = λI + λ1 ¹ Λ2 ¹ · · ·¹ Λm (12.193)

Le système est donc une file MMPP/M/c/c+k.

On étudie alors le processus de Markov (j, j′) avec 1≤ j ≤ c+ k, 1 ≤ j′ ≤ 2m oùj correspond au nombre d’appels dans le système etj′ à l’état de la chaîne de Markovdu processus M.M.P.P. d’entrée. Notonsj le vecteur{( j, j′) ; 1 ≤ j′ ≤ 2m}.

Le générateur infinitésimalQ de ce processus est alors :

54

TRAFIC D’APPELS

TRAFIC DEDEBORDEMENT(m entrees)

Figure 12.4 – Modélisation du système : un tampon, c serveurs, une entrée de trafic dePoisson et k entrées de trafic de débordement

0 Q− Λ Λ

1 µI Q− Λ − µI Λ

2 2µI Q− Λ − 2µI Λ

... · · ·

c cµI Q -Λ - cµI Λ

c+1 cµI Q− Λ − cµI Λ

... · · ·

c+k cµI Q− cµI

On peut calculer le vecteur des probabilités stationnairesd’état π =

(π0,π1, · · · ,πc+k) en résolvant le systèmeπQ = 0, πe = 1. Même siQ a une trèsgrande taille, ce vecteur peut être calculé assez rapidement en utilisant une méthodeitérative de Gauß-Seidel. On peut alors calculer les critères de performances du sys-tème :

– La probabilité d’avoirr appels dans le système :

∀r; 0 ≤ r ≤ c+ k, γr = πre (12.194)

– La probabilité qu’un client arrivant voitr appels dans le système :

∀r; 0 ≤ r ≤ c+ k, γ′r =

c+k∑

r=0

πrΛe

−1

πrΛe (12.195)

– La probabilité qu’un client arrivant de l’entréej voit r appels dans le système.Le taux d’arrivées des appels de l’entréej est indépendant du nombre d’appels dansle système et est donné par

Λ( j) = 0 ¹ 0 ¹ · · ·¹ Λ j ¹ · · ·¹ 0 (12.196)

= I2 ² · · ·² I2 ² Λ j ² · · ·² I2 (12.197)


La probabilité qu’un client arrivant de l’entréej voit r appels est alors :

∀r; 0 ≤ r ≤ c+ k, γ′( j) =

c+k∑

r=0

πrΛ( j)e

−1

πrΛ( j)e (12.198)

– La probabilitéb( j) de blocage d’appels arrivant de l’entréej :

∀ j; 0 ≤ j ≤ m, b( j) = γ′c+k( j) (12.199)

Approximation de trafic par processus M.M.P.P. :

Remarquons que le processus de débordement de ce système estaussi un pro-cessus M.M.P.P. En effet, les appels sont refusés lorsque les serveurs et la mémoiretampon sont pleins, c’est-à-dire quand le processus de Markov Q est dans l’étatc+ k.Durant son séjour dans cet état, les appels débordent selon un processus de Poissonde tauxΛrr , i.e. : le r ième élément diagonal de la matrice des arrivéesΛ. Le proces-sus du débordement des appels peut alors être caractérisé par un processus M.M.P.P.de paramètres

(Q,Λ)

oùΛ = diag(0, · · · ,0,Λ). La distribution du débordementde

l’entrée j, 0 ≤ j ≤ m suit aussi un processus M.M.P.P. de paramètres(Q,Λ( j)

)où

Λ( j) = diag(02m, · · · ,02m,Λ( j)). Le processus M.M.P.P.(Q,Λ(0)

)représente le débor-

dement du trafic poissonnien d’arrivée principale des appels et est tel queΛ(0) = λI(On aΛ = Λ(0) ¹ Λ(1) ¹ · · ·¹ Λ(m)).

Toutefois, utiliser le modèle M.M.P.P. est très compliqué,même si c’est une mo-délisation exacte lorsque les temps de services des serveurs sont exponentiels et quele trafic d’arrivée principale des appels est poissonnien. Pour se ramener à un modèledu type de celui présenté ci-dessus, dans lequel les arrivées de trafics de débordementsont I.P.P., on approche le trafic de débordement M.M.P.P. par un modèle I.P.P. Latechnique utilisée par MM-H est l’approche présentée par M. H(cf. [10]). Elle consiste à déterminer les paramètres du processus I.P.P. de telle sorte àfaire coïncider les trois premiers moments non centrés du débit instantané de ce pro-cessus avec ceux du processus M.M.P.P. à approcher, et de même avec une certaineconstante de temps s’exprimant à partir de la fonction d’autocorrélation.

Or, ler ième moment du débit instantané du processus M.M.P.P. (Q,Λ( j) est donnéepar :

αr ( j) = πΛr( j)e (12.200)

= πc+k[Λ( j)]r e (12.201)

= (πAe) λrj (12.202)

avecr ≥ 1, A = {(c + k, r);Λ( j)rr , 0} et λ0 = λ. En notantm( j) la moyenne dudébit instantané du trafic M.M.P.P. etv( j) = α2( j) − (m( j))2 sa variance, on définit la

56

constante de temps comme étant

τc = v−1∫ ∞

0r(t)dt (12.203)

où v = r(0) est la variance du débit d’arrivée etr(t) = E[(λ(τ) − λ)(λ(τ + t) − λ)

]

sa fonction d’autocovariance, oùλ(t) est le débit instantané du processus M.M.P.P. àl’instant t. Comme

r j(t) = πΛ( j)(eQt − eπ

)Λ( j)e, (12.204)

la constante de temps a pour expression

τc( j) = v( j)−1∫ ∞

0r j(t)dt (12.205)

= v( j)−1[πΛ( j)

(eπ − Q

)−1Λ( j)e− (m( j))2

]. (12.206)

Ce processus doit être approché par le processus I.P.P. de paramètres :

Q =

[−σ1 σ1

σ2 −σ2

], Λ =

[λ1 00 λ2

]. (12.207)

Les trois premiers moments non centrés du débit instantané de ce processus I.P.P.et la constante de temps sont :

α1 = λ1π1 + λ2π2 (12.208)

α2 = λ21π1 + λ

22π2 (12.209)

α3 = λ31π1 + λ

32π2 (12.210)

τc =(σ1 + σ2

)−1 (12.211)


On en déduit alors :

λ1 = λ j , (12.212)

λ1 = 0 (12.213)

π1 = πAe. (12.214)

Enfin, commeτc = (σ1 + σ2)−1 et π1 = σ2(σ1 + σ2)−1, il vient :

σ1 = τc( j)−1(1− πc+ke), (12.215)

σ2 = τc( j)−1(πc+ke). (12.216)

On peut remarquer au passage que non seulement le processus I.P.P. approche lestrois premiers moments du processus M.M.P.P. de départ maisaussi que c’est vraipourtousles moments du débit instantané.

Selon les besoins, on peut approcher des trafics à modéliser par des processusM.M.P.P. en fixant leurs paramètres de façon à faire coïncider telle ou telle carac-téristique : moments, fonction d’autocorrélation,... Dans [11], les auteurs modélisentune superposition de trafics par un processus M.M.P.P. en fixant ses paramètres de tellesorte que le débit moyen d’arrivée, le rapport de la variancepar la moyenne du nombred’arrivées dans l’intervalle [0;t1], et à long-terme, ainsi que le moment d’ordre troisdu nombre d’arrivées dans l’intervalle [0 :t2] coïncide avec le trafic à modéliser.

12.5. Le modèle fluide

Lorsqu’un trafic est très intense, il y a beaucoup d’arrivéespar unité de temps, eton ne peut plus le caractériser en considérant chacune en particulier mais seulementpar son débit. Il est alors modélisé de manière globale. Cette modélisation s’inspire dela mécanique des fluides où ceux-ci ne sont pas caractérisés par chacune des moléculesqui les composent mais par leurs débits.

Soit {Y(t)}t≥0 une chaîne de Markov à temps continu et à valeurs dans l’ensemble desvaleurs discrètes comprises entre 0 etN, noté~0;NÄ et Q =

(qi j

)i, j

son générateur

infinitésimal. Quand la chaîne est dans l’étatj, le fluide arrive avec un débita j .

Supposons qu’un tel modèle soit placé en entrée d’une file infinie à temps de serviceconstant de débit c. Le débit de remplissage de la file est alors r j = a j − c (éventuelle-ment négatif, auquel cas la file se vide au lieu de se remplir).

58

Soit X(t) la taille du tampon à t. Notons

F j(x, t) = P (X(t) ≤ x,Y(t) = j)

F j(x) = limt→+∞

F j(x, t)

= P (X ≤ x,Y = j)

On chercheG(x) = P (X > x) = 1−∑N

j=0 F j(x). Le problème consiste alors à résoudreun système différentiel.

F j (x, t + dt) =∑

i,i, j

qi j dtFi

(x− r i j dt, t

)

+

1−∑

i,i, j

q ji dt

F j

(x− r jdt, t

)+ o (dt) (12.217)

donc,

F j (x, t + dt) − F j(x, t) =

∑

i,i, j

qi j dt

[Fi(x, t) +

∂Fi

∂x(x, t)

(−r i j dt

)+ o(dt)

]

+

1−∑

i,i, j

q ji dt

[F j(x, t) − r jdt

∂F j

∂x(x, t) + o(dt)

]

+o(dt) − F j(x, t) (12.218)

soit, commeq j j = −∑

i,i, j q ji ,

F j (x, t + dt) − F j(x, t)

=∑

i,i, j

qi j dtFi(x, t) −∑

i,i, j

q ji dtF j (x, t) − r jdt∂F j

∂x(x, t) + o(dt)

=∑

i

qi j dtFi (x, t) + o(dt) − r jdt∂F j

∂x(x, t) (12.219)


d’où,

F j (x, t + dt) − F j(x, t)

dt=∑

i

qi j Fi(x, t) − r j∂F j

∂x(x, t) +

o(dt)dt

(12.220)

et finalement,

∂F j(x, t)

∂t+ r j∂F j

∂x(x, t) =

∑

i

qi j Fi(x, t). (12.221)

À l’état stationnnaire,∂F j (x,t)∂t = 0 et donc,

r j∂F j

∂x(x, t) =

∑

i

qi j Fi (x, t) . (12.222)

En notantF(x) le vecteur d’élémentsF j (x, t), A la matrice telle queA ii = r i etA i, j,i =

0, le système ci-dessus devient

Addx

F(x) = tQF(x) (12.223)

d’où

ddx

F(x) = A−1(tQ)F(x) (12.224)


F(x) = e(A−1)(tQ)x × k (12.225)

oùk est un vecteur de constantes.

Pour trouver les constantes, on utilise le fait que la probabilité que la file soit videlorsque la chaîne de Markov est dans l’étatj est nulle sir j > 0 et la condition denormalisation (la somme des probabilités est égale à 1).

60

12.6. Les modèles fractaux ou autosimilaires

Les processus autosimilaires et à dépendances longues sontétudiés depuis le mi-lieu du XXe siècle. Les premiers travaux ont été menés par Kolmogorov (cf. [15])et Mandelbrot (cf. [19]), mais c’est seulement depuis 1993,avec la parution de l’ar-ticle [16], que la théorie des objets fractals (du latinfractussignifiant brisé, ces objetsprésentant le plus souvent des caractéristiques importantes d’irrégularité) a pris unegrande importance dans la modélisation du trafic. Il nous estimpossible de présenterles modèles de trafic les plus utilisés sans citer les processus autosimilaires. Toutefois,si ces modèles expliquent les performances observées de systèmes et s’ils rendentcompte de certaines caractéristiques du trafic, nous nous croyons obligés de mettre engarde l’ingénieur devant les difficultés posées par leur utilisation en simulation. Eneffet, ils se comportent en pratique comme des processus non stationnaires.

Intuitivement, un fractal est un objet qui présente les mêmes caractéristiques quelleque soit l’échelle à laquelle on se place pour l’observer. Lechou serait un excellentexemple de fractal s’il avait une taille infinie : lorsqu’on l’effeuille, il garde toujoursla même forme même s’il diminue de taille.

Ce paragraphe est une introduction aux modèles autosimilaires. Nous engageons lelecteur à se référer à la bibliographie donnée en fin de chapitre, et plus spécialement à[24].

12.6.1. Définitions de l’autosimilarité exacte et propriétés

Les paragraphes qui suivent sont extraits des articles [30], et [31]. Une bibliogra-phie très importante est donnée dans [35].

Soient

– X = {Xn}n≥0 un processus stochastique à temps discret stationnaire du secondordre ;

– µ = E [Xn] < ∞ sa moyenne ;

– σ2 = VAR[Xn] < ∞ sa variance ;

– ∀k ≥ 0,b(k) = COV[Xn,Xn+k] = E [XnXn+k]−E [Xn] E [Xn+k] sa fonction d’auto-covariance (qui ne dépend pas den par définition de la stationnarité du second ordre) ;

– r(k) =b(k)σ2

sa fonction d’autocorrélation ;

– f (l) sa densité spectrale ;

– X(m)n =

1m

(Xnm−n+1 + Xnm−m+2 + · · · + Xnm) le processus correspondant à la

moyenne deX sur une fenêtre glissante de taillem;

– X(m) ={X(m)

n

}n≥0

;


– rm(k) la fonction d’autocorrélation deX(m) ;

– bm(k) sa fonction d’autocovariance.

Définition 13 (Autosimilarité du 1er ordre) Le processus X est dit autosimilaire ausens strict, ou autosimilaire du 1er ordre, de paramètre de Hurst H= 1−β/2,0 < β <1, si et seulement si m1−HX(m) a même distribution que X, ou encore si et seulement si

X(m) a même distribution que X oùX(m) ={X(m)

n

}etX(m)

n =1

mH(Xnm−n+1 + Xnm−m+2 + · · · + Xnm).

Le terme "autosimilaire" vient du fait que la transformation qui permet de passer deXà X ne change pas la loi de probabilité. Cette transformation est dite renormalisationd’indice H.

Définition 14 (Autosimilarité du 2ond ordre, 1ère définition) Le processus X est ditautosimilaire du second ordre, de paramètre de Hurst H= 1 − β/2,0 < β < 1, si etseulement si bm(k) = b(k)/mβ, ce qui revient à dire que X(m) et X ont même fonctiond’autocovariance au facteur mβ près ou queX(m) et X ont exactement même fonctiond’autocovariance.

En d’autres termes, la renormalisation d’indiceH ne modifie pas la fonction d’autoco-variance. On trouve aussi dans la littérature une deuxième définition, moins intuitiveque celle-là mais équivalente, et qui permet de définir plus simplement l’autosimilaritéasymptotique du second ordre. La définition que nous venons de donner permet tou-tefois de démontrer plus facilement l’autosimilarité du second ordre d’un processus etde mieux comprendre la notion de dépendance longue (cf. plusbas).

Définition 15 (Autosimilarité du 2ond ordre, 2onde définition) Un processus X estdit autosimilaire du second ordre, de paramètre de Hurst H= 1− β/2,0 < β < 1, siet seulement si

r(k) = g(k), où g(k) =12

[(k+ 1)2−β − 2k2−β + (k− 1)2−β

]. (12.226)

On écrit parfois g(k) =12δ2(k2−β)

oùδ2 est l’opérateurδ appliqué deux fois avec

δ ( f (x)) = f

(x+

12

)− f

(x+

12

). (12.227)

62

Théorème 1 Les assertions suivantes sont équivalentes :

1) X est autosimilaire du second ordre selon la définition 15,i.e. r(k) = g(k),

2) X est autosimilaire du second ordre selon la définiion 14, i.e. bm(k) = b(k)m−β,

3) VAR[X(m)

n

]= σ2m−β

4) f (λ) = c∣∣∣e2πiλ − 1

∣∣∣2∞∑

l=−∞

1

|λ + l|3−β, −

12≤ λ ≤

12,

où c est une constante de normalisation telle que∫ +1/2

−1/2f (λ)dλ = σ2. De plus, chacune

de ces assertions implique∀k, rm(k) = r(k).

VAR[X(m)

n

]= σ2m−β = VAR[Xn] m−β et bm(k) = b(k)m−β peuvent être vues comme

des équations fonctionnelles de l’autocovarianceb(k) puisque

bm(k) =1

m2

m−1∑

i=0

(m− i)b(mk+ i) +m−1∑

i=1

(m− i)b(mk− i)

. (12.228)

On peut montrer, par exemple par récurrence surk, que chacune de ces équations al’unique solution

b(k) =

{b(0), sik = 0b(0)g(k), sik > 0.

(12.229)

Dans la littérature, plusieurs définitions sont données, mais c’est celle qui requiert pourle processus son caractère d’autosimilarité qui correspond le mieux à la définition d’unfractal (cf. déf. 14). Elle est énoncée en termes de fonctiond’autocovariance, et nond’autocorrélation. Pour que la propriété d’autosimilarité sur l’autocovariance expri-mée par la définition 14 soit vérifiée, une définition en termesd’autocorrélation nepeut pas porter que l’autosimilarité de l’autocorrélation(i.e. rm(k) = r(k)) dans lecas général, mais doit aussi imposerVAR

[X(m)

n

]= σ2m−β car l’autosimilarité seule

de l’autocorrélation ne suffit pas à celle de l’autocovariance. C’est pourquoi on trouveparfois une définition d’un processus autosimilaire du second ordre imposant ces deuxconditions. Maintenant, commeVAR

[X(m)

n

]= σ2m−β implique rm(k) = r(k), la pro-

priété sur la variance suffit aussi pour définir l’autosimilarité, ce qui explique qu’ontrouve aussi des articles qui se contentent de cette définition.

Propriété 17 Un processus autosimilaire du 1er ordre est aussi autosimilaire du 2ond

ordre.


En effet, on peut montrer très facilement queVAR[X(m)

n

]= σ2m−β à partir de la défi-

nition de l’autosimilarité du 1er ordre.

Propriété 18 La fonction d’autocorrélation g(k) vérifie

limk→+∞

r(k)k−β

=12

(2− β) (1− β)

= H (2H − 1) . (12.230)

Si le fait qu’un processus autosimilaire du premier ordre l’est aussi du second ordreest exact, la réciproque est fausse dans le cas général, maisvraie pour des proces-sus gaussiens de moyenne nulle. De plus, un processus strictement autosimilaire dupremier ordre ne peut pas avoir une moyenne non nulle, tandisqu’un processus stric-tement autosimilaire du second ordre le peut. Enfin, siX est un processus positif etnon dégénéré, niX ni X − µ ne peuvent être autosimilaires du premier ordre.

MM. L , T et W ont découvert que le trafic présente des caractéris-tiques d’autosimilarité en analysant un trafic éthernet d’un réseau local. Ils ont tracéson débit sur plusieurs échelles de temps (resp. 0,01, 0,1, 1, 10 et 100 secondes) enfonction du temps et ont obtenu les courbes correspondant à la colonne de gauche dela Fig. 12.5. Ils ont ensuite modélisé le trafic observé à l’échelle de temps de l’ordre ducentième de second avec des modèles markoviens classiques,qu’ils ont simulé pourtracer à nouveau le débit sur plusieurs échelles de temps. Ces nouvelles courbes sontsur la deuxième colonne de la Fig. 12.5. On voit que le trafic selisse au fur et à mesurequ’on augmente la fenêtre d’agrégation du trafic. C’est une caractéristique des traficsà dépendances à court-terme. En revanche, pour le trafic autosimilaire, ce n’est pas lecas. Un modèle autosimilaire a alors été proposé, puis simulé. La troisième colonne dela Fig. 12.5 montre que cette fois l’agrégation sur plusieurs échelles de temps donneun résultat similaire à celui obtenu avec les traces du traficréelles. Cette figure estextraite de l’article [36].

12.6.2. Définitions de l’autosimilarité asymptotique et propriétés

Définition 16 (Autosimilarité du 2ond ordre asymptotique) Le processus X est ditasymptotiquement autosimilaire du second ordre si et seulement si

∀k ≥ 0, limm→+∞

rm(k) = g(k) (12.231)

64

Figure 12.5 – Trafics autosimilaire et markovien : comparaison

Par ailleurs, il nous faut introduire la notion de processusà variations régulières.

Définition 17 Une fonction mesurable f(x) > 0 vérifiant

∀u > 0, limx→+∞

f (ux)f (x)

= uρ, (12.232)

est dite fonction à variations régulières d’indiceρ. Si ρ = 0, f est dite fonction àvariations lentes.

Théorème 2 Pour un processus X et H= 1− β/2,0 < β < 1, les assertions suivantessont équivalentes :


1) X est asymptotiquement autosimilaire du second ordre ;

2) ∀k > 0, limm→+∞

VAR[X(km)

n

]

VAR[X(m)

n

] ∼ k−β

3)[r(k) ∼ H (2H − 1) L(k)k−β quand k→ +∞

](a)

implique[VAR

[X(m)

n

]∼ σ2L(m)m−β quand m→ +∞

](b)

où L(k) est une fonction à variations lentes, et chacune des assertions3)(a) et 3)(b)impliquent1) et2).

Commençons par prouver que 1) implique 2).

rm(k) =1

2VAR[X(m)

n

][(k+ 1)2 VAR

[X((k+1)m)

n

]− 2k2VAR

[X(km)

n

]

+ (k− 1)2 VAR[X((k−1)m)

n

]]

=1

2VAR[X(m)

n

]δ2(k2VAR

[X(km)

n

]), (12.233)

En utilisant la définition 16 de l’autosimilarité asymptotique, on voit que pourk = 1

limm→+∞

2VAR

[X(2m)

n

]

VAR[X(m)

n

] − 1

= 22−β − 1 (12.234)

De la même façon pourk = 2, on obtient

limm→+∞

12

32VAR

[X(3m)

n

]

VAR[X(m)

n

] − 23VAR

[X(2m)

n

]

VAR[X(m)

n

] +VAR

[X(m)

n

]

VAR[X(m)

n

]

=12

[32−β − 22−β + 1

]; (12.235)

Pourk > 2, la démonstration se fait par récurrence.

Le fait que 2) implique 1) est une conséquence immédiate de (12.233) et de 2).

66

Que 3)(b) implique 1) est évident également.

Prouvons maintenant que 3)− (a) implique 3)− (b).

VAR[X(m)

n

]= σ2m−1 + 2σ2m−2

m∑

i=1

(m− i)r(i). (12.236)

La propriété 3)− (a) signifie que sur un voisinage de l’infini [a;+∞[, r(k) ∼ cL(x)x−β.On suppose ici et dans la suite quea est un entier plus grand que 1. Il nous fautdémontrer trois lemmes auparavant.

Lemme 2 Si f(x) est une fonction à variations lentes d’indiceρ > −1 et∑n

i=a f (i)→+∞ quand n→ +∞,

∑ni=a f (i) ∼

∫ n

af (x)dx quand n→ +∞.

Notonsai = f (i) et bi =∫ i+1

if (x)dx. Remarquons queai ∼ ai+1 au voisinage de

l’infini et∫ n

af (x)dx =

∑n−1i=a bi . Maintenant, montrons queai ∼ bi en l’infini. mi ≤

bi ≤ Mi et, quandρ > 0,

mi = inf ( f (x); i ≤ x)

Mi = sup( f (x); x ≤ i + 1) ,

et quandρ < 0,

mi = inf ( f (x); x ≤ i + 1)

Mi = sup( f (x); x ≥ i) .

On peut alors montrer (cf. théorème de Karamata dans [5], théorème 1.5.3.) quemi ∼

ai et Mi ∼ ai+1 au voisinage de l’infini. Ceci signifie queai et bi sont équivalents enl’infini. Pour conclure, il suffit d’utiliser les deux lemmes suivants (3 et 4).

Lemme 3 Soit ai > 0 tels que ai ∼ ai+1 au voisinage de l’infini. Alors∑n−1

i=a ai ∼∑ni=a ai ou an

[∑ni=a ai]−1→ 0 pour n→ +∞.


Pour toutǫ > 0, on choisit 0< δ < 1 et N1 tels que(1+ δ + δ2 + · · · + δN1−1

)−1< ǫ.

Puisqueai/ai+1 → 1 quandi → +∞, on peut choisirN2 tel que pouri > N2,ai/ai+1 >

δ. Alors, pourn > N1 + N2 + a,

an

n∑

i=a

ai

−1

< an

n−N1∑

i=a

ai + an

(1+ δ + · · · + δN1−1

)

−1

<(1+ δ + · · · + δN1−1

)−1< ǫ. (12.237)

Lemme 4 Soit ai > 0 tel que ai ∼ bi et∑n

i=a ai → +∞ au voisinage de l’infini. Alors,

n∑

i=a

ai ∼

n∑

i=a

bi , en l’infini. (12.238)

Pour toutǫ > 0,∃N1 > a tel que|bi − ai | < (ǫ/2) ai , i > N1 (car quandbi/ai → 1 pouri → +∞, (bi − ai)a−1

i → 0). On peut alors choisirN2 tel que pour toutn > N2 + a,

∣∣∣∣∣∣∣

N1∑

i=a

(bi − ai)

∣∣∣∣∣∣∣

/ n∑

i=a

ai <ǫ

2(12.239)

(car∑n

i=a ai → +∞ en l’infini). Pourn > N2 + a,

∣∣∣∣∣∣∣

n∑

i=a

bi −

n∑

i=a

ai

/ n∑

i=a

ai

∣∣∣∣∣∣∣

≤

∣∣∣∣∣∣∣

N1∑

i=a

(bi − ai)

/ n∑

i=a

ai

∣∣∣∣∣∣∣+

n∑

i=N1+1

|bi − ai |

/ n∑

i=a

ai

≤ǫ

2+ǫ

2

n∑

i=N1+1

ai

/ n∑

i=a

ai < ǫ. (12.240)

68

Revenons maintenant à la démonstration du théorème. Tout d’abord, puisque pour toutentiera > 0, 3)− (a) et r(i) ≤ 1 donnent

∑a−1i=1 r(i) < a et

∑mi=a r(m) → +∞ quand

m→ +∞,

m∑

i=1

r(i) ∼

m∑

i=a

r(i), m→ +∞. (12.241)

De même

m∑

i=1

ir (i) ∼

m∑

i=a

ir (i), m→ +∞. (12.242)

Ensuite, en posantc = H (2H − 1) et en appliquant le lemme 2 à la fonction à varia-tions régulières d’indice−β r(x), on obtient

m∑

i=a

r(i) ∼ c∫ m

aL(x)x−βdx ∼

cL(m)m−β+1

1− βm→ +∞, (12.243)

en utilisant l’équation de Karamata (cf. [5], proposition 1.5.8)

∫ m

aL(x)xudx ∼ L(m)

∫ m

axudx, m→ +∞ (12.244)

De la même manière,

m∑

i=a

ir (i) ∼cL(m)m−β+2

2− β, m→ +∞. (12.245)

Les équations (12.241) à (12.245) donnent

m∑

i=a

(m− i)r(i) ∼12

L(m)m−β+2, m→ +∞. (12.246)

Finalement, des équations (12.236) et (12.246), il vient

VAR[X(m)

n

]∼ σ2m−1 + σ2L(m)m−β ∼ σ2L(m)m−β. (12.247)

Q.E.D.

On peut encore donner deux définitions équivalentes de l’autosimilarité asymptotiquedu second ordre.


Définition 18 X est asymptotiquement autosimilaire du second ordre de paramètre0 < β < 1 si et seulement si

bm(0) ∼ cm−β, 0 < c < +∞, m→ +∞ (12.248)

Définition 19 X est asymptotiquement autosimilaire du second ordre de paramètre0 < β < 1 si et seulement si

bm(k) ∼

{cm−β, k = 0cm−βg(k), k > 0

0 < c < +∞. (12.249)

Il est facile de constater que la définition 18 implique la définition 16. Le théorèmesuivant permet d’affirmer l’équivalence des deux précédentes définitions et donne desconditions suffisantes d’autosimilarité asymptotique du second ordre pourX en termesde comportement asymptotique debm(0) etb(k).

Théorème 3 1) Les définitions 18 et 19 sont équivalentes.

2) Si

b(k) ∼ cH (2H − 1) k−β, k→ +∞, 0 < c < +∞ (12.250)

alors

bm(0) ∼ cb(0)m−β, m→ +∞. (12.251)

3) Si

bm(0) = cm−β + ǫm, 0 < c < +∞ (12.252)

où ǫm est tel que m2+βǫm→ 0,m→ +∞, alors (12.250) est vérifiée.

4) Chaque équation (12.250) à (12.252) implique que X est asympotiquement au-tosimilaire du second ordre selon la définition 18.

Prouvons 1) Avec l’équation

bm(k) =12

[(k+ 1)2 b(k+1)m(0)− 2k2bkm(0)+ (k− 1)2b(k−1)m(0)

], (12.253)

qui vient de (12.233), l’équation (12.248) implique (12.249) et prouve queX asymp-totiquement autosimilaire du second ordre selon la définition 19 s’il l’est selon 16. Laréciproque est évidente puique (12.249) inclut (12.248).

70

2) découle de (12.236) et (12.246) si on prendL(m) = 1 et utilise l’équationb(k) =b(0)r(k).

Pour 3) : De (12.253) avecm= 1,

b(k) =12

[(k+ 1)2 b(k+1)(0)− 2k2bk(0)+ (k− 1)2b(k−1)(0)

], (12.254)

et (12.252), il vient

b(k) = cg(k) +[(k+ 1)2 ǫ(k+1) − 2k2ǫk + (k− 1)2ǫ(k−1)

], (12.255)

Puisqueg(k) ∼ H (2H − 1) k−β et le terme entre crochets dans (12.255) tend vers 0plus vite quek−β, (12.250) est vérifiée.

La preuve de 4) est évidente après celles de 2) et 3). Q.E.D.

12.6.3. Dépendances à long-terme

Définition 20 Un processus X est dit à dépendances à long-terme s’il existe0 < β < 1tel que sa fonction d’autocorrélation est en telle que r(k) ∼ ck−β pour k au voisinagede l’infini.

Si β est tel que 1< β < 2, on parle de processus à dépendances à court-terme, etdans ce cas,VAR

[X(m)

n

]∼ cm−1 quandm→ +∞. Dans le premier cas, la somme des

termes de la fonction d’autocorrélation est finie, tandis qu’elle diverge dans le second.En pratique, la dépendance à long-terme signifie qu’un événement à une influence surn’importe quel autre événement survenant plutard. Un événement à une date donnée etun autre arrivant bien plus loin dans le temps sont toujours corrélés. Dans le cas d’unprocessus à dépendances à long terme la valeur deβ indique le degré de dépendance :plus β est proche de 0, plus la dépendance est importante, en revanche, plus elle serapproche de 1, plus le processus tend vers un processus à dépendances à court terme.

On peut constater que tout processus exactement autosimilaire du second ordre est àdépendances longues.


12.6.4. Propriétés

Les deux théorèmes qui suivent sont tirés des articles [21] et [31].

Théorème 4 Soient X′ et X′′ deux processus indépendants tels que r(k) ∼ c1k−β1, k→+∞ pour X′ et r(k) ∼ c2k−β2, k→ +∞ pour X′′, où0 < ci < +∞ et0 < βi < 1. X′+X′′

est asymptotiquement autosimilaire de paramètre H= 1− β/2 oùβ = min(β1, β2).

Suposonsβ1 > β2. La fonction d’autocorrélation deX′ + X′′ vérifie (à cause de l’in-dépendance)

r(x) = E

[(X′n+k + X′′n+k − µ

′ − µ′′) (

X′n + X′′n − µ′ − µ′′

)]/(σ′2 + σ′′2

)

= E

[(X′n+k − µ

′) (

X′n − µ′) +(X′′n+k − µ

′′) (

X′′n − µ′′)] /(σ′2 + σ′′2

)

= r ′(k)σ′2/(σ′2 + σ′′2

)+ r ′′(k)σ′′2/

(σ′2 + σ′′2

)(12.256)

Donc,

limk→+∞

r(k)k−β

=σ′2

σ′2 + σ′′2lim

k→+∞

r ′(k)k−β+

σ′′2

σ′2 + σ′′2lim

k→+∞

r ′′(k)k−β

=c1σ

′2

σ′2 + σ′′2+

σ′′2

σ′2 + σ′′2lim

k→+∞c2k−(β2−β1)

=c1σ

′2

σ′2 + σ′′2, (12.257)

ce qui signifie quer(k) ∼ ck−β, k→ +∞, et qui implique par le théorème 2 queX′+X′′

est asymptotiquement autosimilaire. Q.E.D.

Théorème 5 Soient X′ et X′′ deux processus exactement autosimilaires du secondordre de paramètres respectivement H1 et H2. Si H1 = H2 = H, X′+X′′ est exactementautosimilaire du second ordre de paramètre H. En revanche, si H1 , H2, X′ + X′′

est seulement asymptotiquement autosimilaire du second ordre de paramètre H=max(H1,H2).

72

12.6.5. Application : effet des dépendances à long-terme sur les performances d’unefile d’attente, lien entre autosimilarité et distributionsbarycerques

Ces trafics fractaux dégradent considérablement les performances des réseaux car,du fait des corrélations intrinsèques à leur nature, la longueur des files d’attente enentrée desquelles ils sont placés est beaucoup plus grande que dans le cas où le tra-fic n’est pas fractal. Ce résultat n’est pas établi clairement, mais semble bien vérifié.Comme il est écrit dans [25], une des principales difficultés dans l’étude des sys-tèmes à files d’attente à processus d’arrivées autocorréllés est due au fait qu’il n’y apas de modèle universellement accepté de ces processus d’arrivées. La donnée d’unefonction d’autocorrélation et de la distribution de probabilité d’un processus d’interar-rivées n’est suffisante pour décrire le processus que dans le cas gaussien. Desarticlesont paru montrant seulement qu’avec certains processus autosimilaires bien précis leslongueurs des files d’attente croissaient considérablement : on peut se référer à [7]qui présente une étude expérimentale de l’influence des dépendances à long terme surles performances du réseau, et à [35] et aux références qui y sont incluses pour destravaux plus théoriques pour des processus d’arrivées particuliers.

Il est par contre bien établi (cf. [31]) qu’un processus d’arrivées de sessions dedurées distribuées selon des lois barycerques engendre d’une part des processus exhi-bant des propriétés autosimilaires et d’autre part de très mauvaises performances sur leréseau, si bien que derrière les trafics autosimilaires se cachent souvent des variablesaléatoires de distributions barycerques.

Définition 21 (Distribution barycerque) Une variable aléatoire continue X est diteà distribution barycerque (du grecβαρυς, lourd, etκǫρκoς, queue, ou "heavy tailed"en anglais) si sa fonction de répartition F est telle que

1− F(x) = P (X > x) ∼1xα, x→ +∞,0 < α. (12.258)

De telles lois de probabilité peuvent avoir des variances infinies.

La loi de probabilité la plus utilisée parmi les distributions barycerques est la loi dePareto.

Définition 22 (Distribution de Pareto) Une variable aléatoire continue X suit uneloi de Pareto de paramètresα > 0 et k> 0 si sa densité de probabilité est

f (x) = αnα0

xα+11[n0;+∞[(x) (12.259)


et sa fonction de répartition

F(x) = 1−(n0

x

)αx > n0, α > 0 (12.260)

Sa moyenne est

E [X] =αn0

α − 1, α > 1, (12.261)

et sa variance

VAR[X] =αn2

0

(α − 1)2 (α − 2), α > 2. (12.262)

L’application suivante est tirée de l’article [31]. Soit unprocessus à temps discret ré-sultant de la superposition de sources de trafic arrivant selon un processus de Poissonde tauxλ1, i.e. la probabilité d’avoirk arrivées de sources entret et t+1 est

(λk

1/k!)e−λ1.

Lorsqu’une source arrive, elle reste active pendant un temps aléatoireτ, puis devientinactive. Les temps d’activité de chaque source sont pris indépendants et identique-ment distribués. Pendant sa période d’activité, la sources engendreR paquets parunité de temps. SoitYt le nombre de paquets engendrés par le trafic résultant de cettesuperposition, à l’instantt.

Propriété 19 Soit w(k) la fonction d’autocorrélation de Yt, i.e.

w(k) = COV[Yt,Yt+k]

= E [(Yt −E [Yt]) (Yt+k −E [Yt+k])] , (12.263)

Les relations suivantes sont vérifées :

λ1 =w(0)− w(1)

R2(12.264)

P (τ ≥ l + 1) =w(l) − w(l + 1)λ1R2

, l = 1,2, · · · , (12.265)

R = min(Yt; Yt > 0) . (12.266)

74

Pour prouver (12.264) et (12.265), notons par∆i(l) le nombre de sources qui démarrentleur période active de longueurτ = l à l’instanti. On a

Yt = R+∞∑

l=i

t∑

i=t−l+1

∆i(l). (12.267)

Soit Ai l’ensemble des numéros de sources arrivées à l’instanti. La taille deAi estξioù ξi est poissonnien de paramètreλ1. Soitδs(l) la fonction indicatrice telle que, pourla sources,

δs(l) =

{1, avec la probabilitéP (τ = l)0, avec la probabilité 1− P (τ = l) .

(12.268)

Les variables aléatoiresδs(l), s ∈ Ai sont i.i.d. et indépendantes deξi , et

∆i(l) =∑

s∈Ai

δs(l). (12.269)

Par ailleurs,

E [∆i(l)] = λ1P (τ = l) (12.270)

E[∆i(l)∆ j(m)

]= λ2

1P (τ = l) P (τ = m) + λ1P (τ = l) δi jδlm (12.271)

COV[∆i(l),∆ j(m)

]= λ1P (τ = l) δi jδlm. (12.272)

En utilisant les équations (12.263), (12.267) et (12.272),il vient

w(l) = λ1R2+∞∑

t=l+1

P (τ ≥ t) , l = 0,1,2, · · · . (12.273)

Les équations (12.264) et (12.265) découlent de (12.273). Q.E.D.

Par ailleurs, (12.273) et (12.265) permettent non seulement de déterminerλ1 etP (τ ≥ l)à partir de mesures du processusYt, mais aussi de montrer quandYt est exactementautosimilaire.


Propriété 20 Le processus{Yt}t=0,1,2,··· dont les sources sont à débit constant R estexactement autosimilaire de paramètre H= 1− β/2, 0 < β < 1, si et seulement si,

P (τ ≥ l + 1) =E [τ]

2

[3(l + 1)2−β − 3l2−β − (l + 2)2−β + (l − 1)2−β

]

= −E [τ]

2δ3(l +

12

)2−β , l = 1,2, · · · , (12.274)

où δ3( f ) désigne l’opérateurδ ( f (x)) = f(x+ 1

2

)− f(x− 1

2

)appliqué trois fois et

E [τ] =[1+ 1

2

∑+∞l=1 δ

3((

l + l2

)2−β)]−1. La distribution P(τ ≥ l + 1) est du type Pareto,

P (τ ≥ l + 1) ∼E [τ]

2β (1− β) (2− β) l−(β+1), l → +∞. (12.275)

Propriété 21 Le processus{Yt}t=0,1,2,··· est asymptotiquement autosimilaire du secondordre si

P (τ > t) ∼ ct−α, 1 < α < 2. (12.276)

Cela peut être montré facilement à partir de (12.273) et en utilisant le fait que demanière générale si limk→+∞ r(k)/k−β = c pour 0< β < 1, limm→+∞ r (m)(k) = g(k).De plus, si{Yt}t=0,1,2,··· est asymptotiquement autosimilaire du second ordre tel quelimk→+∞ r(k)/k−β = c pour 0< β < 1, P (τ > l) ∼ c (E [τ]) (α − 1) l−α, où α = β +1, l → +∞. Cela découle directement de (12.265).

De manière générale, l’autosimilarité de{Yt}t=0,1,2,··· est étroitement liée à la nature dePareto de la loi deτ.

Nous allons maintenant étudier les performances d’une file àtemps de service constantd’une unité de temps, à un seul serveur, de discipline de service assez générale (cf. plusbas) mais telle qu’à chaque unité de temps un client est servi, et à capacité finie égaleà h+ 1. On suppose queR = 1, et queξt suit une loi quelconque, pas nécessairementPoisson, queE [τ] < +∞ et P (ξ = 0) < 1.

76

Propriété 22 La probabilité de débordement de la file est telle que

Pdébordement≥1

(E [τ] +E [κ])2

+∞∑

n=n1

P (τ ≥ n) , (12.277)

où n1 = ⌊(h+ b) /a⌋ + 2, ⌊x⌋ désigne la partie entière de x, et

E [κ] = (1− P (ξ = 0))−1 − 1

a = (E [τ] +E [κ])−1 ≤ 1,

b = a+ 1.

NotonsG1 cette borne. Pour n’importe quelle fonction d’échantillonnage du traficd’entrée, et à n’importe quelle instantt, un dépassement de tampon et le nombre depaquets rejetés ne dépend pas de la discipline de service, cequi implique que la pro-babilité de débordement de la file d’attente ne dépend que du trafic d’entrée et de lataille du tampon, propriété également valable pour le taux de perte.

Pour présenter la discipline de service, supposons qu’àt = 0 le tampon est vide etune source, la n˚1, arrive. Elle transmet ses paquets dans l’intervalle de temps [0;τ1[,noté T1. Ensuite, après un instantκ1 arrive la source suivante, n˚2, active pendantτ2 unités de temps. L’intervalleI1 = [τ1; τ1 + κ1[ est appelé intermission (du termemédical : temps séparant deux accès de fièvre). Les clients dela deuxième sourcesont transmis dans l’intervalleT2 = [τ1 + κ1; τ1 + κ1 + τ2[. De manière générale,après la transmission de la source n˚i, i ≥ 2 au cours de la périodeTi = [ti−1, ti−1 +

τi [, l’intervalle d’intermissionI i = [ti−1 + τi ; ti [ suit sans arrivée de nouvelle source,avecti =

∑ij=1

(τ j + κ j

), τ j étant la période active de la sourcej et κ j la largeur de

l’intervalle d’intermissionI j .

Supposons maintenant que d’autres sources, la n˚i exceptée, arrivent au cours de l’in-tervalle Ti . Notons parBi l’ensemble de ces sources. A chaque instantt ∈ Ti , ladiscipline de service insère les nouveaux paquets des sources deBi dans le tampon,s’il y a suffisamment de place, ou sinon en éjecte certains parmi les nouveaux arrivésou les anciens et en garde exactementh dans le tampon. Dans le dernier cas, les pa-quets des sourcesB j ne peuvent être supprimés que si ceux des sourcesB1, · · · , B j−1

ont été supprimés ou transmis. Les paquets des sourcesBi peuvent être transmis dansl’intervalle d’intermissionI j , j ≥ i, s’ils n’ont pas été supprimés.

Considérons maintenant la variable aléatoirejt valant 1 s’il y a dépassement de la fileà t et 0 sinon.Pdébordement= limt→+∞ P ( jt = 1). Pour trouver la borne inférieure,


nous allons négliger les dépassements ayant lieu au cours des périodes d’intermissionet ceux des intervallesTi pour lesquels les paquets des sourcesBi ne sont pas suppri-més. On remplace alors la suitejt, t = 0,1,2, · · · par celle desjt en prenantjt = 0 pourtous les débordements négligés etjt = jt pour tous les autres événements. Pour cettenouvelle suite, le nombre d’instantst où jt = 1 surTi ∪ I i ne dépasse naturellementpas ceux oùjt = 1 surTi ∪ I i , oùTi ∪ I i est la réunion deTi et I i d’une part, et, d’autrepart, les segments des suitesjt sur les intervallesTi ∪ I i deviennent indépendants etidentiquement distribués, de telle sorte que la quitejt peut être considérée comme unprocessus régénérateur dont lei ième cycle de régénération est dans l’intervalleTi ∪ I i .

En utilisant le théorème de Smith (cf. [29]), on peut exprimer les probabilités station-naires de dépassement en fonction deE

[ρ]

etE [τ] +E [κ], oùρ, τ et κ désignent demanière générique lesρi , τi et κi . ρi est le nombre d’instants de débordements dansTi

auxquels les paquets deBi sont supprimés. Lesρi sont indépendants et identiquementdistribués, etP (ρi = k) = P (ρ1 = k) et P (ρ1 = k) est lié au cas où le tampon est videà t = 0. En conséquence,

Pdébordement ≥E[ρ]

E [τ] +E [κ]. (12.278)

avec

E [κ] =1

1− P (ξ = 0)− 1 (12.279)

Cherchons maintenant une borne inférieure pourE[ρ]. Considérons l’intervalle de

transmission [0;τ1[ et supposons que sa longueur soit donnée,τ1 = n. On va trouverune borne inférieure surJ(n) où J(n) est la valeur moyenne du nombre de d’instantsde débordements dans [1;n[ sachant que le tampon est vide àt = 1. On noteB′1l’ensemble des sources qui arrivent dans l’intervalle [1;n[.

Appelons instant de génération de [1;n[ l’instant t où au moins une source deB′1engendre un paquet à la datet. Soit J1(n) le nombre moyen d’instants de générationdans [1;n[, sachant que le tampon est vide àt = 1. Dans ce cas,E

[ρ]≥ E [J(τ)] ≥

E [J1(τ)] − h. Cherchons une borne inférieure pourJ2(n) = J1(n) − h.

Le nombre moyen d’instants de génération dans [1;n[ est inférieur ou égal au nombred’instants de génération obtenu avec la suite de sources suivante. La source 1′ est cellequi arrive la première après la date 0. Soitt′1 l’instant d’arrivée de 1′ et τ′1 la durée desa période d’activité. La source 1′ produitτ′1 instants de génération si tous sont dansl’intervalle [1;n[. La source 2′ de la nouvelle suite de sources considérées est celle qui

78

arrive la première après la datet′1+τ′1−1. Soitt′2 son instant d’arrivée etτ′2 la durée de

sa période d’activité. Cette source produitτ′2 instants de génération sit′2 + τ′2 ∈ [1; n[,

et ainsi de suite : la sourcei′ arrive àt′i , est active pendant une période de tempsτ′i etproduitτ′1+ · · ·+ τ

′i instants de génération avec les source précédentes n˚1′ à n˚(i − 1)′

si t′i + τ′i ∈ [1; n[.

Soit π le nombre de sources dans la suite qui terminent leurs périodes d’activité dans]1; n]. Il vient

J2(n) ≥ max

Eπ∑

i=1

τ′i

− h,0

. (12.280)

Puisque

π+1∑

i=1

τ′i + κ′i ≥ n− 1 (12.281)

où κ′1 = t′1 − 1, κ′i = t′i −(t′i−1 + τ

′i−1

)et, puisque la variable aléatoireπ + 1 ne dépend

pas deτ′1 + κ′1 lorsquei > π + 1, on a (E

[τ′i

]= E [τ] etE

[κ′i

]= E [κ])

(E [τ] +E [κ])E [π + 1] ≥ n− 1 (12.282)

et

E [π] ≥ max

[n− (E [τ] +E [κ]) − 1

E [τ] +E [κ],0

]. (12.283)

Commeτ′i ≥ 1,E[∑π

i=1 τ′i

]≥ E [π]. De cette borne et des équations (12.280) et

(12.283), il vient

J2(n) ≥ max

(n− (E [τ] +E [κ]) − 1

E [τ] +E [κ]− h,O

). (12.284)


Avant de faire la moyenne par rapportn, on prendJ(n) ≥ 0 pourn ≤ h et J(n) plusgrand que le membre de droite de l’équation (12.284) pourn ≥ h + 1. L’équation(12.284) permet de déduire

E[ρ]≥

+∞∑

n=h+1

max

(n− (E [τ] +E [κ]) − 1

E [τ] +E [κ]− h,O

)P (τ = n)

≥ a+∞∑

n=⌊(h+b)/a⌋+1

(n−

h+ ba

)P (τ = n) (12.285)

où

a =1

E [τ] +E [κ]≤ 1

b = a+ 1 ≥ 1

(car (h+b)/a ≥ h+1). En subsituant (h+b)/a à⌊(h+ b) /a⌋+1 dans la borne ci-dessus,et en utilisant

+∞∑

n=n0+1

(n− n0 − 1) P (τ = n) =

+∞∑

n=n0+2

P (τ ≥ n) , n0 ≥ 0, (12.286)

on obtient la borne cherchée. Q.E.D.

Appliquons la borne donnée à la propriété 22 à une distribution de ParetoP (τ = n) =cn−α−1,1 < α < 2. Comme

+∞∑

n=n0

n−α ≥n−α+1

0

α − 1, n0 > 1, α > 1, (12.287)

et en remarquant que, dans ce cas,

P (τ ≥ n) ≥cα

n−α, (12.288)

80

on obtient

Pdébordement ≥ αcα (α − 1) (E [τ] +E [κ])2

(⌊h+ bα

⌋+ 2

)−α+1

(12.289)

où

E [τ] = c+∞∑

n=1

n−α, c =

+∞∑

n=1

n−α−1

−1

(12.290)

E [κ] =(1− e−λ1

)−1− 1 (12.291)

NotonsG2 cette borne inférieure de la probabilité de débordement dans le cas Pareto.En conséquence, quandh est grand,Pdébordement≥ c1h−α+1 = c1h−β = c1h−2(1−H),c1 étant une constante indépendante deh, mais dépendante deλ1 etα.

Cette borne prouve le résultat important qui montre que la probabilité de débordementne décroît pas exponentiellement lorsque le trafic est constitué de sessions distribuéesselon des lois barycerques, mais diminue hyperboliquementavech. Comme ce traficprésente des caractéristiques d’autosimilarité, du fait de la distribution barycerquesdes sessions, ce résultat pourrait suggérer que c’est aussile cas pour tout trafic autosi-milaire. En pratique, cela signifie qu’il faut installer desmémoires tampons infinimentplus grandes lorsque les trafics d’entrée sont autosimilaires que dans le cas où ils sontà dépendances à court-terme.

Comme en général on dimensionne les tailles des mémoires tampons en fonction d’untaux de perte à ne pas excéder, nous présentons maintenant une borne sur le taux deperte de la file.

Propriété 23 SiE [τ] < +∞ et P(ξ = 0) < 1,

Pperte ≥ C (E [τ] +E [κ]) G1

=G1

E[ξ]E [τ]

, (12.292)

et dans le cas où la distribution est de Pareto, P(τ = n) = cn−α−1,

Pperte ≥ C (E [τ] +E [κ]) G2

=G2

λ1E [τ]. (12.293)


En effet, Pperte≥ CE[ρ], oùC−1 = E

[ξ]E [τ]

[E [τ] − 1+ P (ξ = 0)−1

], soitC−1 =

E[ξ]E [τ] (E [τ] +E [κ]). Démontrons-le.

Supposons qu’àt = 0, le tampon soit vide et une première source, la source n˚1,arrive et ait une période d’activité de duréeτ1. Numérotons les paquets qui arriventau moyen de l’indicem = 1,2, · · · . Considérons la suite des paquets ordonnés selonleur numéromet partitionons-là en intervallesL1, L2, · · · tels queLi ne contienne queles paquets des sources arrivées dans l’intervalleT j ∪ I j . Considérons alors la suitealéatoireim,m = 1,2, · · · telle queim = 0 si le paquetm est transmis etim = 1 s’ilest perdu et notonsPperte= limm→+∞ P (im = 1). Déduisons-en la suiteim en prenant

im = 0 pour tous les paquets deL j qui ne sont pas rejetés ou transmis dans l’intervalleT j . Ainsi, le nombre de paquets tels queim = 1 surL j n’est-il pas plus grand que celuides paquets tels queim = 1 d’une part, et, d’autre part, les segments de suites deimsur les intervallesL j deviennent-ils indépendants et identiquement distribués, de tellesorte que le processusim peut être considéré comme un processus de régénération dontle j ième cycle de régénération est dans l’intervalleL j . L’application du théorème deSmith (cf. [29]) donne alors

Pperte ≥Nombre moyen deim = 1 surL j

longueur moyenne deL j. (12.294)

Puisque, d’une part, le numérateur du membre de droite est exactementE[ρ](nombre

moyen d’instants de débordement dansT j auxquels les paquets des sourcesB j sontrejetés), et, d’autre part, le dénominateur vaut

E

τ1 +ξ∗0∑

ν=1

τ(0)ν +

τ1−1∑

t=1

ξt∑

ν=1

τ(t)ν

= C−1, (12.295)

oùξ∗0 est le nombre d’autres sources arrivées àt = 0 en même temps que la source n˚1,τ

(0)1 , · · · , τ

(0)ξ∗0

sont les durées de leurs périodes d’activité,τ1 est la durée de la source

initiale n˚1,τ(t)1 , · · · , τ(t)ξ0

pour t > 0 sont les durées des périodes d’activité des sourcesarrivées àt et les sommes enν valent 0 siξt = 0 ou ξ∗t = 0, on obtient finalementPperte ≥ CE

[ρ]. Le reste de la démonstration est immédiat en utilisant les bornes

précédemment trouvées pourE[ρ]. Q.E.D.

L’on peut constater que le taux de perte décroît aussi hyperboliquement avec la tailledu tampon.

82

12.7. Un modèle de trafic modulable, prenant en compte les caractéristiques im-portantes du trafic, et adapté à la simulation

Les résultats présentés dans le §12.6 précédent montrent l’importance de la priseen compte des corrélations dans le trafic pour l’étude des performances d’un sys-tème de télécommunications. Cependant, en pratique, un trafic fractal sur une infinitéd’échelles de temps n’a pas de sens. De plus, c’est un trafic fortement instable qui secomporte comme s’il n’était pas stationnaire. Enfin, ces modèles présentent le fâcheuxinconvénient de nécessiter de revoir toute la théorie des files d’attente qui est établieessentiellement non sur l’hypothèse d’un trafic fractal, mais sur celle d’un trafic pois-sonnien. C’est pourquoi des savants ont proposé une modélisation spécifique pour lestrafics présentant une forte autocorrélation, rendant biencompte de l’autosimilarité dutrafic sur quelques échelles de temps tout en étant markovienne par essence. Pour unediscussion à ce sujet, le lecteur peut se référer à [32] et [33]. Les dépendances à longterme des processus peuvent être expliquées comme étant la résultante de la combi-naison hiérarchique sur plusieurs échelles de temps de plusieurs processus. C’est cetteidée qui est sous-jacente à ces modèles pseudo-autosimilaires.

Nous présentons ici deux types de modélisation, une adaptéeaux problèmes àtemps discrets et due à MM. S. R et J.Y. L B (cf. [26], mais la descriptionqui est donnée au §12.7.1 est tirée de [27]), et une pour les cas où le temps est continuproposée par MM. A.T. A et B.F. N (cf. [1]).

12.7.1. Modèle à temps discret

Ce modèle a été conçu pour le trafic des réseaux ATM. Celui-ci est composé depetits paquets de tailles fixes appeléscellules. L’unité de temps choisie correspondà la durée, fixe, de transfert d’une cellule ; il ne peut donc y avoir qu’au maximumune cellule par unité de temps. Le modèle proposé est du type M.M.P.P. adapté au casdiscret.

Soit Xt la variable aléatoire représentant le nombre de cellules (supposé être 0 ou 1)à l’instant t. Soit Yt ∈ 1,2, · · · ,n une chaîne de Markov à temps discret de matricede transitionA = (ai j ), le processus de modélisation. Soitφi j = Pr(Xt = j/Yt = i).On ne s’intéresse qu’au cas stationnaire et on noteπi = Pr(Yt = i) la distributionstationnaire deYt. Puisque le processusXt est à valeur dans{0,1}, ses moments sontégaux et donnés par :

E[Xk

t

]= E [X] = −→πΛ−→e , k = 1,2 · · · , t = 0,1,2, · · · (12.296)


avec−→π = (π1, π2, · · · , πn), −→e un vecteur colonne composé uniquement de 1, etΛ

définit par :

Λ = diag(E [X/Y = 0] ,E [X/Y = 1] , · · · ,E [X/Y = n]) . (12.297)

Si Nm représente le nombre d’arrivées dans une fenêtre temporelle dem unités detemps, la variance deNm peut s’écrire

VAR[Nm] = mE [X] −m2 (E [X])2 + 2m−1∑

i=1

(m− i)(−→πΛAi+1

Λ−→e). (12.298)

Maintenant, le modèle proposé consiste en la famille telle que A est

1− 1a −(

1a

)2− · · · −

(1a

)n−1 1a

(1a

)2· · ·

(1a

)n−1

ba 1− b

a 0 · · · 0(ba

)20 1−

(ba

)2· · · 0

· · · · · · · · · · · · · · ·(ba

)n−10 0 · · · 1−

(ba

)n−1

(12.299)

etΛ

1 0 0 · · · 00 0 0 · · · 00 0 0 · · · 0· · · · · · · · · · · · · · ·

0 0 0 · · · 0

(12.300)

Cette chaîne de Markov est donc paramétrée par 3 variables :a > 1, b ∈ (0,a) etn. LamoyenneE [X] est indépendante dea et est donnée par

E [X] =1−(

1b

)

1−(

1b

)n (12.301)

84

avec limn→+∞E [X] = 1− 1b quandb > 1. Le processusXt est un processus ON/OFF

à temps discret alternant des périodes d’activités "ON" distribuées géométriquementet d’autres de silence de distribution "presque" barycerque. Les périodes d’inactivitéétant des sommes de variables aléatoires géométriques de moyennes très différentes,elles sont très hétérogènes. Tout cela permet de simuler un modèle à dépendances àlong-terme, tout en étant markovien par essence, c’est pourquoi il est dit modèle detrafic pseudo-autosimilaire.

Pour comprendre le risque qu’il y a à utiliser des modèles autosimilaires en simulation,remarquons que si le nombre d’états de la chaîne de Markov estgrand, la probabilitéde passer dans l’étatn − 1 est extrêmement faible, mais si par aventure le processusy entre, il y reste en moyenne un temps considérable par construction. Ce temps peutêtre de l’ordre de la durée de la simulation, si bien qu’il estimpossible de voir lesestimateurs observés converger.

Pour unn donné, les paramètres du modèle peuvent être fixés pour fairecoïnciderla moyenne et le paramètre de HurstHl à des valeurs déterminées. Le paramètreb

est donné parm =1−( 1

b)1−( 1

b)n , ce qui se résoud facilement numériquement. Le second

paramètre,a, est trouvé, par exemple, itérativement avec une méthode deNewton-Raphson, en estimant la pente de la variance par moindres-carrés. Le domaine, entermes d’échelle de temps où le processus est autosimilairepeut être élargit en aug-mentantn. Un tel modèle peut être utilisé en entrée d’un modèle de commutateur, parexemple.

12.7.2. Modèle à temps continu

Le modèle proposé ici est construit à partir de la superposition de sources M.M.P.P.à deux états superposées. Le trafic résultant est donc un M.M.P.P., ou encore unsous-ensemble de la classe des processus M.A.P. Soitd le nombre de telles sourcesM.M.P.P. superposées. Laième peut être paramétrée de la façon suivante

D0i =

[− (c1i + λ1i) c1i

c2i − (c2i + λ2i)

]D1

i =

[λ1i 00 λ2i

](12.302)

où les éléments diagonaux deD0i sont négatifs et les autres positifs, etD1

i est unematrice non négative avec au moins un élément non nul. La somme deD0

i et D1i est

un générateur infinitésimal irréductibleDi de vecteur des probabilités stationnairesd’état~πi = (c2i/ (c1i + c2i) , c1i/ (c1i + c2i)). Le modèle M.A.P. de la superposition peuts’écrire

(D0, D1) =

d⊕

i=1

D0i ,

d⊕

i=1

D1i

(12.303)


Soit Nit le nombre d’arrivées dans ]0;t] du ième processus M.M.P.P. à deux états. Sa

variance est

VAR[Ni

t

]=(λ∗i + 2k1i

)t −

2k1i

k2i

(1− e−k2i t

)(12.304)

où λ∗i = (c2iλ1i + c1iλ2i) / (c1i + c2i), k1i = (λ1i − λ2i)2 c1ic2i/ (c1i + c2i)

3 et k2i = c1i +

c2i .

Pour leième M.M.P.P. à deux états la fonction de covariance du nombre d’événementsdans deux créneaux de temps de largeur∆t, séparés dek − 1 créneaux de ce type est(k > 0)

γi(k) =(λ1i − λ2i)

2 c1ic2ie−((c1i+c2i )(k−1)∆t)

(c1i + c2i)4

(1− 2e−((c1i+c2i )∆t) + e−((c1i+c2i )2∆t)

)

=k1i

k2ie−(k2i (k−i)∆t)

(1− 2e(−k2i∆t) + e(−k2i2∆t)

). (12.305)

Si on suppose (c1i + c2i)∆t << 1, i ∈ (1,2, · · · ,d), un développement de Taylor duterme de droite donne

(1− e−(c1i+c2i )∆t + e−(c1i+c2i )2∆t

)= ((c1i + c2i)∆t)2+o

(((c1i + c2i)∆t)2

).

Ainsi pour (c1i + c2i)∆t << 1, i ∈ (1,2, · · · ,d) a-t-on

γi(k) ≃(∆t)2 (λ1i − λ2i)

2 ci1c2ie−((c1i+c2i )(k−1)∆t)

(c1i + c2i)2

= (∆)2 k1ik2ie−(k2i (k−1)∆t). (12.306)

Les caractéristiques du premier et du second ordre (moyenne, variance, autocova-riance) du processus de comptage de chaque M.M.P.P. à deux états sont entièrementdéterminées par les trois quantitésλ∗i , k1i et k2i . Comme chaque processus de cetype est à quatre paramètres, cela laisse un degré de libertépour construire différentsM.M.P.P. de base dont les processus de comptage associés ontles mêmes caractéris-

tiques du premier et du second ordre. Or, chaquer i ≥

(k1ik2i/

(λ∗i

)2)définit un tel

processus, fonction der i , de mêmes caractéristiques des premier et second ordres duprocessus de comptage associé si

λ1(r i) = λ∗i +√

k1ik2ir i (12.307)

λ2(r i) = λ∗i −√

k1ik2ir i (12.308)

c1(r i) =k2ir i

1+ r i(12.309)

c2(r i) =k2i

1+ r i(12.310)

86

Ce paramètrer i peut être utilisé pour fixer d’autres caractéristiques de chaque M.M.P.P.de base que les caractéristiques des premier et second ordrede leurs processus decomptage. Le processus résultant de la superposition de chacune de ces sources estdonc àd degrés de liberté, correspondant chacun au degré de libertélaissé par lechoix possible de chaquer i . Cela est exploité pour obtenir la bonne fonction d’auto-corrélation des temps entre arrivées du trafic de la superposition desd sources.

Les mesures faites sur du trafic réel composé de paquets de tailles variables suggèrentque les caractéristiques du second ordre du nombre de paquets arrivant par créneaude temps présentent le même type que celles d’un processus asymptotiquement auto-similaire du second ordre. Supposons que le nombre de paquets arrivant par créneaude temps soit asymptotiquement tel queCOV(k) = ψcovk−β où ψcov est une mesureabsolue de variance (une constante positive), 0≤ β ≤ 1. Les mesures menées parM. A et ses collègues sur du trafic dans un réseau local montrent que ce com-portement asymptotique est très vite atteint, même pour de faibles valeurs dek. Lesr i

sont donc déterminés de telle sorte qu’on ait

γ(k) =

d∑

i=1

γi(k) ≃ ψcovk−β, 1 ≤ k ≤ 10n (12.311)

oùn représente le nombre d’échelles de temps à prendre en comptedans le modèle.

Un algorithme est proposé pour déterminer les paramètres dumodèle. Il requiert fina-lement cinq données :

1) La moyenneλ∗ du trafic ;

2) la valeurρ de la fonction d’autocorrélation au rang 1 ;

3) le paramètre de HurstH = 1− β/2 ;

4) le nombre de processus M.M.P.P. de based ;

5) le nombre d’échelles de temps à prendre en compte.

La prise en compte de la variabilité du modèle de trafic sur plusieurs échelles de tempsest faite à travers le choix des constantes de tempsc1i et c2i de chaque processusM.M.P.P. de base. Celles-ci sont prises telles quec1i = c2i = a1−ic11, i = 1, · · · ,d, i.e.les paramètres de modulation sont fixés logarithmiquement par rapport à un facteura.L’échelle de temps la plus petite qu’il faut prendre en compte est celle de l’ordre de latransmission d’un paquet.

Un résumé de la procédure de détermination des paramètres est donné Fig. 12.6.

1ère étape : le paramètre logarithmiquea est fixé à partir du nombre de processusM.M.P.P. de based et du nombre d’échelles de temps à prendre en compten :

a = 10n/(d−1), d > 1. (12.312)


Figure 12.6 – Algorithme de détermination des paramètres

88

Les paramètresn et d doivent être tels quea ≥ 5 à cause d’une hypothèse fondamen-tale prise à la deuxième étape. Ceci permet finalement de trouverc1i = c2i ,i = 1, · · · ,d.

2ème étape :cette étape permet de déterminer partiellement les intensités d’arrivéesλi1, λi2,i = 1, · · · ,d et requiertH, n, d et a. Sans perte de généralité, supposonsλi1 > λi2. On peut remarquer à partir de la variance du processus de comptage etla fonction d’autocovariance d’un processus M.M.P.P. de base que les taux d’arrivéesn’interviennent que dansk1i à travers la quantité(λ1i − λ2i)

2. Ceci n’est pas surpre-nant car il est toujours possible d’interpréter la superposition de i processus M.M.P.P.à deux états comme étant la superposition dei processus I.P.P. et d’un processus dePoisson. Dans notre cas, les processus I.P.P. ont pour taux d’arrivéesλIPP

i = λ1i − λ2i ,i = 1, · · · ,d et celui du processus de Poisson estλp =

∑di=1 λ2i .

À partir de cette interprétation, on détermine au cours de cette deuxième étape levecteur desλIPP

i à une constante de normalisation prèsκ, i.e.~λIPP = κ~φ. En prenant∆t = 1 dans la formule de l’autocovariance (12.306), et en supposant(c1i + c2i) << 1,la fonction d’autocovariance duième I.P.P. est (où on utilisec1i = c2i)

γi(k) ≃κ2

4φ2

i e−((c1i+c2i )(k−1)∆t). (12.313)

Ce qui est très important dans cette partie de la procédure dedétermination des pa-ramètres, c’est que, pour toutk jusqu’à une certaine valeur telle que(c1i + c2i) k ≃ 1,la fonction d’autocovariance est à peu près constante. A partir d’un certain rang, cen’est plus vrai et elle devient extrêmement plus petite pour(c1i + c2i) k ≥ 5. Puisqueles intensités de modulation ont été choisies logarithmiquement, on peut trouver lestailles relatives des taux d’arrivées des processus M.M.P.P. de base en supposant quele facteura n’est pas trop petit.

Pour illustrer cette méthode, considérons un modèle résultant de la superposition detrois I.P.P. oùλIPP

1 = 6,0, c11 = c21 = 10−2, λIPP2 = 6,0, c12 = c22 = 10−4 et

λIPP3 = 6,0, c13 = c23 = 10−6. La Fig. 12.7, extraite de [1], présente l’allure des

fonctions d’autocorrélations des trois processus I.P.P. en fonction dek. Finalement,seul le troisième processus I.P.P. contribue de manière significative à la corrélationpourk de l’ordre de 106, tandis que les deux autres y contribuent jusqu’àk = 104 etk = 102. Il en va bien sûr de même pour les autocovariance. Cette remarque permetd’appliquer la méthode suivante.

Lesφi sont obtenus en imposant end différents points définis par(c1i + c2i) k = 1 dela fonction d’autocovariance une valeur voulue :


Figure 12.7 – Fonctions d’autocorrélation du nombre d’arrivées par unité de temps

– pour(c1d + c2d) k = 1 :

ψcova−(d−1)β =

κ2

4

d∑

j=1

(φ j

)2e−ad− j

≃κ2

4(φd)2 e−1; (12.314)

– pour(c1(d−1) + c2(d−1)

)k = 1 :

ψcova−(d−2)β =

κ2

4

d∑

j=1

(φ j

)2e−ad−1− j

≃κ2

4(φd)2 e−a−1

+κ2

4(φd−1)2 e−1; (12.315)

– · · · ;

– pour(c11 + c21) k = 1 :

ψcov =κ2

4

d∑

j=1

(φ j

)2e−a−( j−1)

. (12.316)

Les(φi)2 sont déduits itérativement de ce système d’équations. Comme nous ne sommes

intéressés que par les valeurs relatives, nous prenons(φd)2 = 1 dans la première équa-tion, ce qui donne le rapportψcov/κ

2. (φd−1)2 est tiré de la deuxième équation,(φd−2)2

90

de la troisième, et ainsi de suite. Parfois, certaines équations ne peuvent être vérifées.Dans ce cas, il faut prendreφ j = 0.

3ème étape : elle consiste à déterminer la constanteκ à partir du résultat de l’étapeprécédente et l’intensité du processus de PoissonλP. Il faut pour cela les quantitésρ,λ∗, et les résultats des étapes précédentes. Pour queρ puisse exister avec ce modèle, ilfaut que

2ρ

d∑

i=1

φ2i k−2

2i

(k2i −

(1− e−k2i

)) >

d∑

i=1

φ2i k−2

2i

(1− e−k2i

)2, (12.317)

où ∆t = 1, η2 est une constante multiplicative de la fonction d’autocovariance dela superposition desd I.P.P. de taux d’arrivées définis par le vecteur~φ et de taux demodulation obtenus à l’étape 2, c’est-à-direc1i = c2i = (k2i/2). En effet,

ρ =

∑di=1 γi(1)

∑di=1 VAR

[Ni∆t

]

=

η2(∑d

i=1 φ2i c1ic2i (c1i + c2i)

−4(1− e−(c1i+c2i )

)2)

λ∗ + η2(∑d

i=1 2φ2i c1ic2i (c1i + c2i)

−4 ((c1i + c2i) −(1− e−(c1i+c2i )

)))

=

η2(∑d

i=1 φ2i k−2

2i

(1− e−k2i

)2)

4λ∗ + 2η2(∑d

i=1 φ2i k−2

2i

(k2i −

(1− e−k2i

))) . (12.318)

Dans ce cas (si (12.317) est vérifiée), il faut diminuerc1i = c2i = (k2i/2) en les multi-pliant par un facteur compris entre 0 et 1 ou diminuerρ. M. A et ses collèguesn’ont jamais eu ce problème en pratique. Le fait que cette difficulté semble surtoutthéorique est illustrée par l’observation que pour les cas où k2i < 1 etρ < 0,5, cela nedoit jamais arriver, quels que soient les valeurs desφi . Ce problème résolu,η s’obtientpar la formule

η =

√4ρλ∗

∑di=1 φ

2i k−2

2i

((1− e−k2i

)2− 2ρ

(k2i −

(1− e−k2i

))) . (12.319)

Si λ∗ ≥ η∑d

i=1 φic2i/ (c1i + c2i) = η∑d

i=1 (φi/2), il existe une solution réalisable. Dansce cas,κ = η et alorsλIPP

i = κφi . L’intensité du processus de Poisson est alors

λP = λ∗ −12κ

d∑

j=1

φ j . (12.320)


Siλ∗ < η∑d

i=1 (φi/2), il n’y a pas de solution réalisable immédiatement. Une telle solu-tion peut être construite à partir des formules (12.307), (12.308), (12.309) et (12.310)en cherchant une superposition de débit résultantλ∗, de même structure d’autocova-riance que celle définie parη etφi et k2i , i = 1, · · · ,d. En considérant ces formules, ilest évident qu’il y a plusieurs superpositions ded M.M.P.P. à deux états qui peuventconvenir, mais nous n’en donnons ici qu’une seule.

On peut par exemple fixer les constantesk1i =(η2/ (4k2i)

)φ2

i etk2i = c1i + c2i dans lesformules (12.304) et (12.305). Il faut alors trouver les valeurs dec1i etc2i qui donnentune solution réalisable sous la contraintek2i = c1i + c2i . Décidons que la probabilitéd’être dans l’état actif ("ON") est la même pour touti, i.e. pon = c2i/ (c1i + c2i). Enayantk1i fixé,

η2

4φ2

i =c1ic2i

(c1i + c2i)2

(λIPP

i

)2= pon (1− pon)

(λIPP

i

)2(12.321)

pour touti, ce qui donneλIPPi = ηφi (1/ (2pon))

√pon/ (1− pon). En prenantλP = 0,

λ∗ =∑d

i=1 ponλIPPi =

∑di=1 (ηφi/2)

√pon/ (1− pon), pon peut être déterminé :pon =

(2λ∗)2/(

(2λ∗)2 +(η∑d

i=1 φi

))2. Finalement,

λIPPi = φi

(2λ∗)2 +(η∑d

i=1 φi

)2

4λ∗∑d

i=1 φi

(12.322)

et donc,

κ =

((2λ∗)2 +

(η∑d

i=1 φi

))2

4λ∗∑d

i=1 φi

(12.323)

et les différentsci j sont donnés par

c1i =

(η∑d

i=1 φi

)2

(2λ∗)2 +(η∑d

i=1 φi

)2 k2i (12.324)

c2i =(2λ∗)2

(2λ∗)2 +(η∑d

i=1 φi

)2 k2i . (12.325)

92

Il est possible qu’un nombred0,0 ≤ d0 < d desφ j soit égal à 0 après l’exécution decette procédure. Cela arrive quand le paramètre de Hurst estassez grand, typiquementH > 0,8. Le nombre de processus M.M.P.P. à deux états réellement actifs est alorsd− d0, et le modèle M.A.P. correspondant a alors 2d−d0 états. Or la procédure requiertparmi ses paramètres un nombred de processus de base qui sont supposés ne pas êtreinactifs en permanence. On commence donc toujours la procédure avecd = d∗. S’ils’avère qued0 = 0, la procédure de détermination des paramètres est achevéeen uneseule itération, en revanche, sid0 > 0, il faut incrémenterd et la réitérer, et ainsi desuite jusqu’à ce qued − d0 = d∗.

Pour des valeurs assez grandes de H (H > 0,8), utiliser une méthode des moindrescarrés pourc1d et c2d peut aider à mieux approcher deρk−β la fonction d’autocorréla-tion.

Figure 12.8 – Comparaison des fonctions d’autocorrélationdu processus de comptagepour les trafics modélisé et original

M. A et ses collègues ont appliqué ce modèle à un trafic dont les caractéris-tiques sont les suivantes :


Paramètres d’entréesource λIPPi c1i c2i

d = 4 IPP1 2,679 4,571.10−1 3,429.10−1

n=6 IPP2 1,698 1,445.10−2 1,084.10−2

λ∗ IPP3 1,388 4,571.10−4 3,429.10−4

H = 0,90 IPP4 1,234 4,571.10−6 3,429.10−6

ρ = 0,40 Poisson λp = 0,0

Figure 12.9 – Fonction d’autocorrélation du processus de comptage pour p0ct.tL

La Fig. 12.8 représente la fonction d’autocorrélation du processus de comptage dece trafic pour les traces et pour le modèle. À partir d’un certain rang, la fonctiond’autocorrélation pour le modèle chute brutalement, tandis que celle du trafic originalreste hyperbolique. C’est un résultat typique des modèles pseudo-autosimilaires quisimulent un comportement autosimilaire sur un certain nombre d’échelles de temps,mais qui retrouvent leur comportement markovien, c’est-à-dire une autocorrélationdécroissant exponentiellement, à partir d’un certain temps.

MM. A et N ont aussi appliqué leur modélisation aux traces (fichier"p0ct.tL") obtenues à Bellcore (cf. [16]). La Fig. 12.9 représente les fonctions d’auto-corrélation du processus de comptage pour les trafics réels et modélisés.

94

Figure 12.10 – Probabilité que la file d’attente dépassex, en fonction dex, pour p0ct.tL

Pour valider cela, les auteurs ont simulé une file d’attente avec le trafic modélisé enentrée, et les traces originales et tracé la probabilité quela file d’attente dépasse unecertaine valeurx : cette courbe est représentée Fig. 12.10. La vitesse du serveur a étéfixée de telle sorte que la charge soit de 60%.

12.8. Conclusion

Les modèles de trafic ont fait l’objet de nombreuses recherches depuis une quin-zaine d’années. Des mesures ont montré que le trafic dans les réseaux présentait descaractéristiques propres aux objets autosimilaires. C’est pourquoi de nombreuses pu-blications ont porté sur le trafic fractal. Cependant, les modèles markoviens peuventêtre adaptés judicieusement pour simuler le comportement de trafics autosimilairessur un certain nombre d’échelles de temps. Ces modèles paraissent particulièrementadaptés à la simulation de réseaux. Dans la majorité des simulations, où l’on étudiele comportement d’algorithmes, où l’on compare des mécanismes, il importe surtoutd’avoir un modèle de trafic qui soit une référence pour la comparaison, et dans cecas le trafic de Poisson, aussi simple soit-il, reste le plus adéquat. Lorsque les sourcesde trafic doivent rendre compte de phénomènes plus complexes, les modèles de typeB.M.A.P. sont probablement les plus adaptés.

Chapitre 13

Bibliographie

[1] A.T. Andersen, B.F. Nielsen -A Markovian Approach for Modeling Packet Traffic withLong-Range Dependence. IEEE Journal on selected areas in communications, vol. 16, n˚5,juin 1998.

[2] S. Asmussen, G. Koole -Marked point processes as limits of Markovian arrival streams.Jounal of Applied Probability, vol. 30, pp. 365-372, 1993.

[3] P. Baudracco, A.-L. Beylot, C. Fleury, S. Monnier, M. Becker -Performance Measurementof a WEB server, Design of a First Model. Research in Official Statistics. Volume 1, number1, 1998.

[4] M. Becker -Évaluation des performances des systèmes et réseaux. Polycopié de cours,Institut National des Télécommunications, 1996.

[5] N.H. Bingham, C.M. Goldie, J.L. Teugels -Regular Variation. Cambridge, New-York,Melburn : Cambridge Univ. Press, 1987.

[6] C. Blondia -A Discrete-Time Batch Markovian Arrival Process as B-ISDN Traffic Model.Belgian Journal of Operations Research, Statistics and Computer Science, vol. 32, 1993.

[7] A. Erramilli, O. Narayan, W. Willinger -Experimental Queueing Analysis with Long-Range Dependent Packet Traffic. IEEE/ACM Transaction on Networking, vol. 4, n˚2, april1996.

[8] W. Fischer, K. Meier-Hellstern -The Markov-modulated Poisson process (MMPP) cook-book. Performance Evaluation 18 (1992) 149-171. North-Holland.

[9] W. Grassmann, M. Taksar, D. Heyman -Regenerative analysis and steady state distributionfor Markov chains. Operation Research, vol. 33, 1985, pp. 1107-1116.

[10] H. Heffes -A class of data traffic processes - Covariance function characterization andrelated queueing results. Bell Syst. Tech. J., vol. 59, pp. 897-929, 1980.

[11] H. Heffes, D.M. Lucantoni -A Markov modulated characterization of packetized voiceand data traffic and related statistical multiplexer performance. IEEE Journal on selected

95

96

areas in communications, vol. sac-4, n˚6, september 1986.

[12] H. Hlavacs, G. Kotsis, C. Steinkellner -Traffic Source Modelling. Technical Reportn˚TR-99101. Institute of Applied Computer Science and Information Systems, Universityof Vienna.

[13] A. Hordijk, R. Schassenberger -Weak convergence for generalized semi-Markov pro-cesses. Stochastic Processes and their Applications, vol. 12, n˚3, pp. 271-291, 1982.

[14] G. Kemeny, J. Snell -Finite Markov chains. Van Nostrand-Reinhold, New-York, 1960.

[15] A.N. Kolmogorov -Wienersche Spiralen und einige andere interessante Kurven im Hil-bertschen Raum (en russe). Comptes Rendus (Doklady) Acad. Sci. USSR, 26 :115–118,1940.

[16] E. Leland, W. Willinger, D.V. Wilson -On the self-similar nature of Ethernet traffic.Computer Communication Review, 23 (1993), 183-193.

[17] E. Leland, W. Willinger, D.V. Wilson -On the self-similar nature of Ethernet traffic.IEEE/ACM Transactions in Networking, 2 (1994), 1-15. Version étendue de lapublicationprécédente.

[18] D.M. Lucantoni -New results on the single server queue with a batch markovian arrivalprocess. Communications in statistics. Stochastic models ISSN 0992-0287, vol. 7, n˚1, pp.1-46, 1991.

[19] B.B. Mandelbrot -Long-run linearity, locally Gaussian processes, H-spectra, and infinitevariancies. Int. Econ. Rev., vol. 10, pp. 82-113, 1969.

[20] K. Meier-Hellstern -The Analysis of a Queue Arising in Overflow Models. IEEE Trans.on Communications, vol. 37, n˚4, April 1989.

[21] J. K.-Y. Ng, S. Song, B.H. Tang -Some New Findings on the Self-Similarity Property inCommunications Networks and on Statistical End-to-end Delay Garantee. Techical ReportCOMP-03-006, Hong Kong Baptist University, February 21, 2003, Hong Kong.

[22] M.F. Neuts -Models Based on the Markovian Arrival Process. IEICE Trans. Commun.,vol. E75-B, n˚12, pp. 1255-1265, décembre 1992.

[23] C. Palm -Intensitätsschwankungen in Fernsprechverkehr. Ericsson Technics, 44, pp.1-89,1943.

[24] K. Park, W. Willinger (Ed.) -Self-Similar Network Traffic and Performance Evaluation.John Wiley & Son, Inc., 2000.

[25] S. Resnick, G. Samorodnitsky -Performance Decay in a Single Server ExponentialQueueing Model with Long Range Dependence. Oper. Res. 45 (1997), pp. 235-243.

[26] S. Robert, J.-Y. Le Boudec - New models for pseudo-self-similar traffics. PerformanceEvaluation, 30, 1997, pp. 57-68.

[27] J. Roberts, U. Mocci, J. Virtamo (Eds.) -Broadband Network Teletraffic. Final Report ofAction, COST 242. Springer. Lecture Notes in Computer Science, vol. 1155. 1996.

[28] S. M. Ross -Introduction to probability models. 6ème édition, Academic Press, Londres,1997.

Bibliographie 97

[29] W.L. Smith -Regenerative stochastic processes. In Proc. Roy. Soc. Ser. A, 1955, n˚232,pp. 6-31.

[30] B. Tsybakov, N. D. Georganas -Self-similar processes in communications networks,IEEE Trans. Inform. Theory, vol. 44, pp. 713-1725, May 1998.

[31] B. Tsybakov, N. D. Georganas -On Self-similar Traffic in ATM Queues : Definitions,Overflow Probability Bound, and Cell Delay Distribution, IEEE Trans. Inform. Theory,vol. 5, n˚3, pp. 397-409, June 1997.

[32] S. Vaton -Near completely decomposable Markov models of traffic. Eighth IFIP Work-shop on Performance on Modelling and Evaluation of ATM and IP Networks, Bradford,UK, july 2000.

[33] S. Vaton -’Fractal’ versus ’Poisson’ models of traffic. Eighth IFIP Workshop on Perfor-mance Modelling and Evaluation of ATM and IP Networks, Bradford, UK,july 2000.

[34] J. Virtamo -Queueing Theory. S-38.143. Transparents de cours, 2003.

[35] W. Willinger, M. Taqqu, A. Erramilli -A Bibliographical Guide to Self-Similar Trafficand Performance Modeling for Modern High-Speed Networks. In Stochastic Networks :Theory and Applications, F. P. Kelly, S. Zachary and I. Ziedins editors,Clarendon Press(Oxford University Press), Oxford, pages 339-366, 1996.

[36] W. Willinger, M. Taqqu, R. Sherman, D.V. Wilson -Self-Similarity Through High Varia-bility : Statistical Analysis of Ethernet LAN Traffic at the Source Level. IEEE/ACM Tran-sactions on Networking, Vol. 5, n˚1, 1997, 71-86.

Documents

De la modélisation du trafic