A Markovi forgalomanalízis legújabb eredményei és ezek alkalmazása a távközlő hálózatok teljesítményvizsgálatában

A Markovi forgalomanalízis legújabb eredményei és ezek alkalmazása a távközlo˝ hálózatok teljesítményvizsgálatában Horváth Gábor [email protected]

(Horváth András, Telek Miklós)

- p. 1

Tartalom

Tartalom ● Tartalom Problémafelvetés

■

Motiváció, problémafelvetés

■

A Markovi Érkezési Folyamat (MAP)

■

MAP illesztési megoldások

■

MAP alapú sorbanállási hálózatok

■

Példák

■

Konklúzió

MAP-ok Sorbanállási hálózatok Példák Konklúzió

- p. 2

Motiváció ■ Tartalom Problémafelvetés ● Motiváció ● Sorbanállási hálózatok

■

˝ Aggregációs hálózatokban a legérdekesebb minoségi ˝ a bufferekben "keletkeznek" jellemzok Rendszerben lévo˝ buffereket azonosítjuk és a bufferek hálózatát vizsgáljuk tovább


- p. 3


■



- p. 3


■



- p. 3

Motiváció ■ Tartalom Problémafelvetés

■

● Motiváció ● Sorbanállási hálózatok



■

A bufferhálózat vizsgálata történhet szimulációval vagy analízissel

- p. 3

Sorbanállási hálózatok Számos QoS jellemzo˝ gyorsan és pontosan kiszámolható, ha: Tartalom

■

Problémafelvetés ● Motiváció ● Sorbanállási hálózatok

■ MAP-ok Sorbanállási hálózatok Példák Konklúzió

˝ A csomagérkezési idoközök exponenciális eloszlásúak (Poisson folyamat) A csomagméretek exponenciális eloszlásúak

Ezzel szemben a gyakorlati vizsgálatok (mérések) tapasztalatai: ■ ■ ■ ■

A forgalom nem Poisson folyamat ˝ összefüggok ˝ A csomagérkezési idok LRD tulajdonság Fraktális viselkedés

Kérdések: ■ ■

Milyen eszközzel modellezzük az ilyen összetett forgalmat? ˝ Hogy számítsuk a hálózat QoS jellemzoit?

- p. 4

Markovi Érkezési Folyamatok ■ Tartalom Problémafelvetés

■

Egy állapot-átmeneti rendszer (Markov lánc) modulálja az érkezéseket a háttérben Bizonyos átmenetek érkezést generálnak, mások nem:

MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal Sorbanállási hálózatok Példák Konklúzió

- p. 5


■



 −16 0  D0 =  0 −5 6 0





4 0 12   5  , D1 =  0 0 −19 10 3



0  0 0

- p. 5


■



■

˝ Elonyök: ◆ Könnyen szimulálható ◆ Hatékonyan megoldható sorbanállási rendszerek: M/M/1 −→ M AP/M AP/1, M/G/1 −→ M AP/G/1

- p. 5

MAP illesztés

Tartalom Problémafelvetés MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés

˝ / adatsorból MAP? Hogyan lesz mérési eredményekbol Két módszertan: ■

Likelihood alapú: ◆ Olyan MAP-ot készít, ami a leheto ˝ legnagyobb valószínuséggel ˝ generálhatta az adatsort ◆ Az adatsor minden tagját figyelembe veszi ◆ Drasztikusan lassul az adatsor növelésével

■

Statisztikai alapú: ◆ Az adatsorból jól megválasztott statisztikai mennyiségeket számolunk (momentumok, autokorreláció) ◆ Olyan MAP-ot keresünk, amely az adatsorral megegyezo ˝ statisztikával bír ◆ Minél több az adat, annál pontosabb

● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal Sorbanállási hálózatok Példák Konklúzió

- p. 6

Statisztikai alapú MAP illesztés

Tartalom

■

˝ megoldás Hatékony MAP illesztés kulcsa: 2 lépcsos ˝ eloszlásának illesztése 1. Érkezési idok ˝ ˝ illesztése 2. Összefüggoségi jellemzok

■

A hatékonyság oka: két egymást követo˝ optimalizálási feladat sokkal hatékonyabb, mint egy dupla annyi változós optimalizálási feladat

Problémafelvetés MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal Sorbanállási hálózatok Példák Konklúzió

- p. 7

˝ Érkezési idoközök illesztése

Tartalom

A független mintákra való Markovi eloszlásillesztés sokat vizsgált terület, sok eredménnyel.

Problémafelvetés MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal Sorbanállási hálózatok Példák Konklúzió

- p. 8

˝ ˝ illesztése Összefüggoségi jellemzok

Tartalom

˝ Tipikusan autokorrelációval jellemzik az összefüggoséget:

Problémafelvetés

E[(X0 − E(X))(X1 − E(X))] ρ= σ2

MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás

Tulajdonságok: ■

˝ pozitív: átlag feletti idoket várhatóan átlag feletti követi és vice versa

■

˝ negatív: átlag feletti idoket várhatóan átlag alatti követi és vice versa

● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal Sorbanállási hálózatok Példák Konklúzió

- p. 9

˝ ˝ illesztése Összefüggoségi jellemzok

Tartalom Problémafelvetés

˝ Kiterjesztés: a k távolságra lévo˝ érkezési idoközök korrelációja:

MAP-ok ● Markovi Érkezési Folyamatok

ρk =

● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás

Példa: LBL-TCP adatsor (Lawrence Berkeley Laboratory forgalma, 2 óra hosszú) 0.16

● Validálás

0.14

● Az együttes momentumok

0.01

● Inverz karakterizáció együttes

0.12

Példák

Lag-k korr.

momentumokkal Sorbanállási hálózatok

0.1

trace

0.1

Lag-k korr.

˝ ˝ ● Összefüggoségi jellemzok

E[(X0 − E(X))(Xk − E(X))] σ2

0.08 0.06

0.001 0.0001 1e-05

0.04

Konklúzió

1e-06

0.02 0

trace

1e-07 5

10

15 Lag

20

25

1

10

100

1000

10000

100000

Lag

- p. 10

MAP illesztés, összefoglalás

Tartalom

˝ 1. Érkezési idoközök illesztése:

Problémafelvetés MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok

■ ■ ■ ■

Adott: az adatsor ˝ Cél: az érkezési idoközök eloszlásának illesztése Eszköz: momentumillesztés, vagy optimalizálás Eredmény: egy MAP (D0 , D1 ), mely még független érkezéseket generál

˝ 2. Összefüggoség illesztése:

● Inverz karakterizáció együttes momentumokkal

■

Sorbanállási hálózatok Példák Konklúzió

■

■ ■

Adott: az adatsorból kinyert autokorrelációs fv., és a független MAP (D0 , D1 ) ˝ Cél: az érkezési idoközök eloszlásának megtartása ˝ mellett az összefüggoség illesztése Eszköz: nemlineáris optimalizálás Eredmény: a kész MAP (D0′ , D1′ ) - p. 11

Validálás

Tartalom

2 sorbanállási rendszer, determinisztikus kiszolgálással:

Problémafelvetés

+sorhossz eloszlások összehasonlítása

MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése

Tapasztalat:

˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes

■

Relatíve rossz eredmények akkor is, ha jól sikerült a MAP

Tanulság: ■

Az autokorrelációs függvény illesztésére törekedés tévút!


ρk =

Példák

E[(X0 − E(X))(Xk − E(X))] 1 = (E(X0 Xk ) + . . . ) 2 2 σ σ

Konklúzió

■

˝ ˝ is vannak Más összefüggoségi jellemzok

- p. 12

Az együttes momentumok

Tartalom

Az együttes momentumok fogalma:

Problémafelvetés

ηi,j = E(X0i X1j )

MAP-ok ● Markovi Érkezési Folyamatok ● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás ● Validálás

Tulajdonságok: ■

■

● Az együttes momentumok ● Inverz karakterizáció együttes momentumokkal

■ Sorbanállási hálózatok

Csak a szomszédos érkezésekre vonatkoznak, de ez ˝ mert elegendo, a magasabb fokú együttes momentumok meghatározzák a ˝ MAP összefüggoségét ˝ Adatsorból is könnyen eloállítható:

Példák Konklúzió

ηi,j

N −1 1 X i xk · xjk+1 = N −1 k=1

- p. 13

Inverz karakterizáció együttes momentumokkal

Tartalom

Fo˝ eredmény: MAP inverz karakterizáció n2 egyszeru˝

Problémafelvetés MAP-ok ● Markovi Érkezési Folyamatok

statisztikai mennyiséggel

● MAP illesztés ● Statisztikai alapú MAP illesztés ˝ ● Érkezési idoközök illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ˝ ˝ ● Összefüggoségi jellemzok illesztése ● MAP illesztés, összefoglalás

˝ ˝ 1. 2n − 1 momentumból eloállítjuk az érkezési idoközök eloszlását ˝ tesszük a 2. (n − 1)2 együttes momentumból összefüggové MAP-ot

● Validálás ● Az együttes momentumok ● Inverz karakterizáció együttes

Eljárásunk tulajdonságai:


■

Példák

■

Konklúzió

■

Egyértelmu˝ Gyors (azonnali válasz) De adhat rossz MAP-ot: ezeket addig kell transzformálni, amíg érvényes MAP-ot nem kapunk

- p. 14


Tartalom

Poisson helyett MAP bemeno˝ forgalom:

Problémafelvetés MAP-ok Sorbanállási hálózatok ● MAP alapú sorbanállási hálózatok ● MAP alapú sorbanállási hálózatok Példák Konklúzió

- p. 15


Tartalom



- p. 15


Tartalom



■

A MAP osztály zárt: ◆ Elágazásra ◆ Szuperpozícióra

■

˝ A kimenoforgalomra?

- p. 15


Tartalom

Legyen a csomag kiszolgálási folyamat is MAP:


- p. 16


Tartalom



- p. 16


Tartalom


Problémafelvetés MAP-ok Sorbanállási hálózatok ● MAP alapú sorbanállási hálózatok ● MAP alapú sorbanállási hálózatok Példák

˝ A kimenofolyamat egy ∞ állapotteru˝ MAP! n állapotú MAP

Konklúzió

közelítés: ■

■ ■

˝ A MAP/MAP/1 rendszer kimenofolyamatának n2 paraméterének kiszámolása (pontos!) ˝ MAP eloállítása ˝ Az n2 paraméterébol (általában pontos) ˝ ˝ Minél nagyobb n, annál több összefüggoségi jellemzot veszünk figyelembe → egyre pontosabb a közelítés

- p. 16

Tandem hálózat

Tartalom

Topológia:

Problémafelvetés MAP-ok

Node A

Sorbanállási hálózatok

Node B

Példák ● Tandem hálózat ● Tandem hálózat, eredmények

3 vizsgált eset:

● Tandem hálózat, eredmények ● Összetett példa

■

● Összetett példa Konklúzió

■ ■

a) exponenciális eloszlású csomagméretek b) nem exponenciális, de független csomagméretek c) összefüggo˝ csomagméretek

- p. 17

Tandem hálózat, eredmények

Tartalom

#Áll.

a. eset

#Áll.

b. eset

c. eset

n/a 2 3 6 12 22 42 6 12 22 42

0.9517 0.93967 0.954241 0.833259 0.900164 0.936189 0.949793 0.902632 0.939841 0.947761 0.951109

n/a 2 3 18 36 66 126 18 36 66 126

3.48825 2.5053 3.48803 2.58742 2.91293 3.20054 3.41015 3.52804 3.53408 3.5002 3.4889

3.08063 2.55597 3.01978 2.61587 2.73691 2.95097 3.04765 3.05992 3.08245 3.0771 3.07611

Problémafelvetés MAP-ok Sorbanállási hálózatok Példák ● Tandem hálózat ● Tandem hálózat, eredmények ● Tandem hálózat, eredmények ● Összetett példa ● Összetett példa Konklúzió

Szimuláció momentum n=2 alapú n=3 ETAQA n=2 n=5 n=10 n=20 Level n=2 prob. n=5 based n=10 n=20

- p. 18


Tartalom

Case c.: Queue length distribution of Node B

Problémafelvetés

0.6

MAP-ok

Simulation MAP(2) MAP(3)


0.5

Példák ● Tandem hálózat ● Tandem hálózat, eredmények ● Tandem hálózat, eredmények

0.4

● Összetett példa Konklúzió

Probability

● Összetett példa

0.3 0.2 0.1 0 0

2

4

6

8 Buffer size

10

12

14

- p. 19


Tartalom

Case c.: Autocorrelation of departures of Node A

Problémafelvetés

0.35

MAP-ok Sorbanállási hálózatok

Simulation MAP(2) MAP(3)

0.3

Példák ● Tandem hálózat

0.25

● Tandem hálózat, eredmények ● Összetett példa ● Összetett példa Konklúzió

Autocorrelation

● Tandem hálózat, eredmények

0.2 0.15 0.1 0.05 0 -0.05 0

5

10 Lag

15

20

- p. 19

Összetett példa

Tartalom

Topológia:


Node A


Node D

Node C


Node B


˝ ˝ is A csomagérkezési idoközök és a kiszolgálási idok ˝ összefüggok.

- p. 20

Összetett példa

Tartalom

Topológia:


Node A


Node D

Node C


Node B


˝ ˝ is A csomagérkezési idoközök és a kiszolgálási idok ˝ összefüggok. Node D Node A Node B Node C Szimuláció MAP(2) Rel. hiba MAP(3) Rel. hiba

4.24696 4.24962 -0.06% 4.24962 -0.06%

1.0709 1.06936 -0.1% 1.07144 0.05%

1.94556 1.9342 -0.5% 1.94196 -0.2%

5.4563 5.23628 -4% 5.25906 -3.6% - p. 20

Összetett példa Node C, a legrosszabbul közelített csomópont: Tartalom

Queue length distribution of Node C

Problémafelvetés

0.25

Simulation MAP(3)


0.2

Példák ● Tandem hálózat ● Tandem hálózat, eredmények ● Összetett példa ● Összetett példa Konklúzió

Probability

● Tandem hálózat, eredmények

0.15

0.1

0.05

0 0

2

4

6

8

10

12

14

Buffer size

- p. 21

Összetett példa Node C, a legrosszabbul közelített csomópont: Tartalom

Autocorrelation of the arrivals of Node C

Problémafelvetés

0.025

Simulation MAP(3)


0.02

Példák ● Tandem hálózat, eredmények ● Tandem hálózat, eredmények ● Összetett példa ● Összetett példa Konklúzió

Autocorrelation

● Tandem hálózat

0.015

0.01

0.005

0 0

2

4

6

8

10

12

14

Lag

- p. 21

Konklúzió

Tartalom

■

Problémafelvetés

■

MAP-ok

Kifejlesztettük az együttes momentum alapú MAP illesztést Megoldást javasoltunk sorbanállási hálózatok megoldására MAP alapokon

Sorbanállási hálózatok Példák Konklúzió ● Konklúzió

- p. 22

A Markovi forgalomanalízis legújabb eredményei és ezek alkalmazása a távközlő hálózatok teljesítményvizsgálatában

Recommend Documents