Proxy Cache szerverek hatékonyságának vizsgálata. Performance Modeling of Proxy Cache Servers

Proxy Cache szerverek hatékonyságának vizsgálata Performance Modeling of Proxy Cache Servers Doktori (PhD) értekezés Bérczes Tamás Témavezet˝o: Prof. Dr. Sztrik János

Debreceni Egyetem Természettudományi Doktori Tanács Informatikai Tudományok Doktori Iskolája Debrecen, 2011

K¨ osz¨ onetnyilv´ an´ıt´ as Ez´ uton is szeretnék k¨ osz¨ onetet mondani mindazoknak akik közvetve vagy közvetlen¨ ul hozz´ aj´ arultak a disszert´ aci´ om elkész´ıtéséhez. Sz¨ uleimnek, akik felneveltek, t´ amogattak és elind´ıtottak az életben. Feleségemnek, aki mindenben t´ amogatott. Bátyámnak, aki végig seg´ıtett tanulm´ anyaim alatt. Témavezet˝omnek, Dr. Sztrik J´ anosnak, a rengeteg hasznos tanácsért, u ´tmutatásért és b´ ator´ıt´ asért, amely nélk¨ ul ez a dolgozat nem kész¨ ulhetett volna el.

i

ii

Tartalomjegyz´ ek 1 Bevezet´ es

1

2 Sorban´ all´ asi rendszerek ´ es h´ al´ ozatok 2.1. Sorbanáll´ asi rendszerek vizsg´ alata: . . . . . . . . . . . . . . 2.2. Sorbanáll´ asi h´ al´ ozatok vizsg´ alata . . . . . . . . . . . . . . .

5 5 8

3 Web szerver modell

13

4 Proxy Cache szerver modell 4.1. A javasolt modell . . . . . . . . . . . . . . . . . . . . . 4.2. Numerikus eredmények . . . . . . . . . . . . . . . . . . 4.2.1. Az érkezési intenzit´ as hat´ asa a válaszid˝ore . . . 4.2.2. A k¨ uls˝ o érkezési intenzit´ as hatása a válaszid˝ore 4.2.3. A f´ ajl méretének hat´ asa a válaszid˝ore . . . . . 4.2.4. A tal´ alati val´ osz´ın˝ uség hat´ asa a válaszid˝ore . . 5 A Web szerver ´ es a Proxy hat´ asa 5.1. A javasolt modell . . . . 5.2. Numerikus eredmények . 5.2.1. Eredmények . . .

. . . . . .

. . . . . .

. . . . . .

19 19 24 24 25 28 30

Cache szerver meghib´ asod´ as´ anak 35 . . . . . . . . . . . . . . . . . . . . 35 . . . . . . . . . . . . . . . . . . . . 40 . . . . . . . . . . . . . . . . . . . . 45

6 A Proxy Cache szerver GI/G/1 approxim´ aci´ os 6.1. A GI/G/1 approxim´ aci´ o . . . . . . . . . . 6.2. A Proxy Cache szerver GI/G/1 modellje . 6.3. Numerikus eredmények . . . . . . . . . . . 6.4. Konkl´ uzi´ o . . . . . . . . . . . . . . . . . .

modellje . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

49 49 53 60 62

7 A heterog´ en forgalom hat´ asa a Proxy Cache szerverek hat´ ekonys´ ag´ ara 65

iii

Tartalomjegyzék 7.1. T¨ obb igény-oszt´ alyt tartalmazó sorbanállási hálózatok . . 7.2. M´ odos´ıtott Proxy Cache szerver modell . . . . . . . . . . 7.3. Numerikus eredmények . . . . . . . . . . . . . . . . . . . . 7.3.1. A bels˝ o igények érkezési intenzitásának hatása a válaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2. A k¨ uls˝ o igények érkezési intenzitásának hatása a válaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . 7.3.3. A f´ ajlméret hat´ asa a válaszid˝ore . . . . . . . . . .

. 65 . 68 . 74 . 74 . 75 . 79

¨ 8 Osszefoglal´ o

85

9 Conclusion

91

Irodalomjegyz´ ek

95

iv

´ Abrajegyz´ ek 1.1. Proxy Szerver konfigur´ aci´ o: (a) egyed¨ ulálló, (b) transzparens

2

2.1. Egyszer˝ u sor . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Folyamatok egyes´ıtése és oszt´ asa . . . . . . . . . . . . . . . 9 2.3. Direkt visszacsatol´ as . . . . . . . . . . . . . . . . . . . . . . 11 3.1. 3.2. 3.3. 3.4.

Web szerver modell . . . . . . . . . . . . . . . . . Fájl méret hat´ asa a Web szerver v´ alaszidejére . . Fájl méret hat´ asa a Web szerver v´ alaszidejére 2 . A Web szerver sebességének hat´ asa a válaszid˝ore

. . . .

. . . .

. . . .

4.1. Proxy Cache szerver modellje . . . . . . . . . . . . . . 4.2. A bels˝o igények érkezési intenzit´ as´ anak hatása 1. . . . 4.3. A bels˝o igények érkezési intenzit´ as´ anak hatása 2. . . . 4.4. A bels˝o igények érkezési intenzit´ as´ anak hatása 3. . . . 4.5. A bels˝o igények érkezési intenzit´ as´ anak hatása 4. . . . 4.6. A k¨ uls˝o igények érkezési intenzit´ asának hatása 1. . . . 4.7. A k¨ uls˝o igények érkezési intenzit´ asának hatása 2. . . . 4.8. A k¨ uls˝o igények érkezési intenzit´ asának hatása 3. . . . 4.9. A k¨ uls˝o igények érkezési intenzit´ asának hatása 4. . . . 4.10. A találati val´ osz´ın˝ uség hat´ asa a v´ alaszid˝ore . . . . . . 4.11. Az érkezési intenzit´ as hat´ asa a v´ alaszid˝ore, módos´ıtott raméter szerver paraméter értékekkel . . . . . . . . . .

. . . .

. . . .

. . . .

15 16 17 17

. . . . . . . . . . . . . . . . . . . . pa. .

. . . . . . . . . .

20 26 26 27 27 28 29 29 30 32

. 32

5.1. Proxy Cache szerver modellje . . . . . . . . . . . . . . . . . 36 5.2. A bels˝o igények érkezési intenzit´ as´ anak hatása a válaszid˝ore blokkolt és nem blokkolt esetben . . . . . . . . . . . . . . . 40 5.3. A foglalt Proxy Cache szerver meghibásodásának hatása a válaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

v

´ Abrajegyz´ ek 5.4. A nem foglalt Proxy Cache szerver meghibásodásának hatása a v´ alaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. A Proxy Cache szerver jav´ıtási intenzitásának hatása a válaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6. A foglalt Web szerver meghibásodási intenzitásának hatása a v´ alaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7. A nem foglalt Web szerver meghibásodási intenzitásának hat´ asa a v´ alaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . 5.8. A Web szerver jav´ıt´ asi intenzitásának hatása a válaszid˝ore . 5.9. Proxy Cache szerver puffer méretének hatása a válaszid˝ore 1 5.10. Proxy Cache szerver puffer méretének hatása a válaszid˝ore 2 6.1. Proxy Cache szerver m´ odos´ıtott modellje

42 42 43 43 44 44

. . . . . . . . . . 53

7.1. Proxy Cache szerver heterogén forgalmi modellje . . . . . 7.2. Heterogén forgalom; bels˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 1 . . . . . . . . . . . . . . . . . . . . 7.3. Heterogén forgalom; bels˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 2 . . . . . . . . . . . . . . . . . . . . 7.4. Heterogén forgalom; bels˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 3 . . . . . . . . . . . . . . . . . . . . 7.5. Heterogén forgalom; bels˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 4 . . . . . . . . . . . . . . . . . . . . 7.6. Heterogén forgalom; k¨ uls˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 1 . . . . . . . . . . . . . . . . . . . . 7.7. Heterogén forgalom; k¨ uls˝o igények érkezési intenzitásának hat´ asa a v´ alaszid˝ ore 2 . . . . . . . . . . . . . . . . . . . . 7.8. Heterogén forgalom; Az a osztály´ u fájlok méretének hatása a v´ alaszid˝ ore 1 . . . . . . . . . . . . . . . . . . . . . . . . 7.9. Heterogén forgalom; Az a osztály´ u fájlok méretének hatása a v´ alaszid˝ ore 2 . . . . . . . . . . . . . . . . . . . . . . . . 7.10. Heterogén forgalom; A b osztály´ u fájlok méretének hatása a v´ alaszid˝ ore . . . . . . . . . . . . . . . . . . . . . . . . .

vi

41

. 69 . 75 . 76 . 76 . 77 . 78 . 78 . 82 . 82 . 83

T´ abl´ azatok jegyz´ eke 3.1. Web szerver modell param´ eterei . . . . . . . . . . . . . 18 4.1. A f´ ajl m´ eret´ enek hat´ asa a v´ alaszid˝ ore . . . . . . . . . 31 4.2. A f´ ajl m´ eret´ enek hat´ asa a v´ alaszid˝ ore, m´ odos´ıtott param´ eterek mellett . . . . . . . . . . . . . . . . . . . . 33 4.3. A Proxy Cache szerver modell jel¨ ol´ esei . . . . . . . . 34 6.1. Szimul´ aci´ o valid´ al´ asa . . . . . . . . . . . . . . . . . . . . 62 6.2. Approxim´ aci´ os eredm´ enyek . . . . . . . . . . . . . . . . 63 7.1. F´ ajlm´ eret hat´ asa a v´ alaszid˝ ore, az a oszt´ aly ar´ anya 20% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2. F´ ajlm´ eret hat´ asa a v´ alaszid˝ ore, az a oszt´ aly ar´ anya 40% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3. Az a oszt´ aly ar´ any´ anak hat´ asa a v´ alaszid˝ ore . . . . 7.4. Heterog´ en forgalomi modell param´ eterei . . . . . .

. 80 . 80 . 81 . 83

vii

1 Bevezet´ es Napjainkban az egyik legink´ abb k¨ ozkedvelt információszerzési lehet˝oség az internet haszn´ alata. Az internet gyors és egyszer˝ u lehet˝oséget biztos´ıt több ezer Webszerver adatainak a megismerésére, letöltésére. Az internet használata az elm´ ult években rohamosan növekedett. A felhasználók száma a 2001-es 474 milli´ or´ ol 2002-re 590 millióra növekedett. 2006-ra az internetet használ´ ok sz´ ama elérte a 948 milliót. Figyelembe véve, hogy 1996-ban mindösszesen 40 milli´ oan haszn´ alták az internetet, a növekedés u ¨teme igen jelent˝ os. A felhaszn´ al´ ok sz´ am´ anak növekedésével párhuzamosan növekedett az internet forgalma is. Ennek hatására egyre nagyobb igény mutatkozik a sz´ınvonalas és gyors internet elérésre és kiszolgálásra. Az információ-keresés és let¨ oltés k¨ ozben a v´ alasz a távoli Web szervert˝ol a kliens gépéig gyakran igen sok id˝ ot vesz igénybe. Egy tartalom többszöri és egyidej˝ u elérése miatt a v´ alaszid˝ ok n¨ ovekednek, ezért indokolt a tartalmak felhasznál´ ok k¨ ornyékén val´ o t´ arol´ asa, amely által a késleltetés csökkenthet˝o. Ennek egyik megold´ asi lehet˝osége a böngész˝o szoftverbe való implementál´ as ( [1]). Ebben az esetben a tárolt adatokhoz azonban csak egy személy férhet hozz´ a. Egy m´ asik lehet˝oség Proxy Cache szerver használata. Telep´ıtési hely¨ uk alapj´ an a Proxy Cache szerverek két t´ıpusát k¨ ulönböztetj¨ uk meg: Kliens oldali Proxy Cache szerverr˝ol beszél¨ unk, amikor a Proxy Cache szerver a kliens h´ al´ ozat´ anak része. Megford´ıtott Proxy Cache szerverr˝ol beszél¨ unk, amikor a Proxy szerver a távoli Web szerver közelébe van telep´ıtve. Ebben az esetben a Web szerver nagyobb igényszámot tud kiszolg´ alni, valamint javul a szolgáltatás min˝osége is. Jelen disszertáció keretében a kliens oldalra telep´ıtett Proxy Cache szervereket fogjuk vizsg´ alni. A kliens oldali Proxy Cache szervereket a konfigurációjuk alapján 2 csoportba soroljuk:

1

1 Bevezetés

1.1. ábra. Proxy Szerver konfiguráció: (a) egyed¨ ulálló, (b) transzparens

• Egyed¨ ul´ all´ o Proxy Cache szerver: Ez a konfigur´ aci´ o l´ athat´ o az 1.1a. ábrán. A konfiguráció egyik h´ atr´ anya, hogy amennyiben a Proxy Cache szerver elromlik, a kliensek sz´ am´ ara az egész internet kapcsolat elérhetetlenné válik. Ilyen esetben a h´ al´ ozat u ´jrakonfigurálása sz¨ ukséges a Proxy Cache szerver jav´ıt´ as´ aig. • Transzparens Proxy Cache szerver: Ez a konfigur´ aci´ o l´ athat´ o az 1.1b. ábrán. Transzparens Proxy Cache szervert haszn´ alva megsz¨ untethetj¨ uk a Proxy Cache szerverek egyik legnagyobb h´ atr´ any´ at, nevezetesen a kliens Web browserek konfigur´ aci´ oj´ anak sz¨ ukségességét. A felhaszn´ al´ o szemsz¨ ogéb˝ ol nézve lényegtelen, hogy az általa keresett fájl fizikailag hol tal´ alhat´ o: egy Proxy Cache szerveren valahol a munkahelyének bels˝ o h´ al´ ozat´ an vagy a világ t´ ulsó felén egy távoli Web szerveren. A keresett dokumentum érkezhet a távoli Web szervert˝ol vagy a Proxy Cache szervert˝ ol. Kliens oldalr´ ol nézve a Proxy Cache szerver funkciója ugyanaz mint egy Web szervernek, valamint a Web szerver fel˝ol nézve a Proxy Cache szerver ugyan´ ugy viselkedik, mint egy kliens. Feltételezhet˝ o, hogy egy Proxy Cache szerver be¨ uzemelése egy cég bels˝o hálózata és az internet k¨ ozé, kisebb sávszélesség igényt valamint kisebb

2

válszid˝oket eredményezhet [14]. Így a v´ allalatok több felhasználót kapcsolhatnak ugyanakkora s´ avszélességre, mivel a Proxy Cache szerver redundánsan tárolja az adatokat, t¨ obb felhasználó számára. Korábbi kutatások els˝ osorban a k¨ ul¨ onb¨ oz˝ o ”Cachelési” algoritmusok vizsgálatával illetve fejlesztésével foglalkoztak [1], [4], [26], [31]. Jelen disszertáció keretében a Proxy Cache szerverek hatékonyságát vizsgáljuk meg. Kutat´ asunk nem a k¨ ul¨ onb¨ oz˝ o algoritmusok közötti k¨ ulönbségekre irány´ ul, hanem kifejezetten azt vizsgálja, hogy milyen környezeti feltételek mellett éri meg egy Proxy Cache szerver u ¨zemeltetése [11], [9], [7], [10]. A disszertáció tov´ abbi része a k¨ ovetkez˝ oképpen van strukt´ urálva: A 2. fejezetben egy r¨ ovid, lényegret¨ or˝ o ismertet˝ot adok a sorbanállási rendszerekr˝ol és hálózatokr´ ol, majd a 3. fejezetben bemutatom a [32] által feláll´ıtott Web szerver modell matematikai alapjait, valamint néhány numerikus eredménnyel szemléltetem a Web szerver modell m˝ uködését. További Web szerver modellek tal´ alhat´ oak a [22], [21], [19] cikkekben. A 4. fejezetben bemutatom az ´ altalunk ´ altalános´ıtott Proxy Cache szerver modellt, majd megvizsg´ altam, hogy milyen paraméterértékek mellett érheti meg egy Proxy Cache szerver u ¨zemeltetése, azaz milyen esetekben lesz egy igény teljes v´ alaszideje alacsonyabb Proxy Cache szerver használatával, mint nélk¨ ule. Az 5. fejezetben tov´ abbi ´ altal´ anos´ıt´ asként feltételeztem, hogy mind a Web szerver mind pedig a Proxy Cache szerver elromolhat, azaz nem megb´ızhatóak. Az ´ıgy kapott modell bonyolultsága miatt a válaszid˝ok kiszám´ıtásához a MOSEL (Modeling, Specification and Evaluation Language) [6] programcsomagot haszn´ altam. A MOSEL egy le´ıró nyelv, mely seg´ıtségével k¨ ulönb¨ oz˝ o programcsomagokat használhatunk, mint például az SPNP-t (Stochastik Petri Net Package) vagy a TimeNet programcsomagot. A MOSEL ´ altal szolg´ altatott eredményeket grafikusan is ábrázolni tudjuk az IGL (Intermediate Graphical Language) seg´ıtségével, mely része a MOSEL-nek. A 6. fejezetben az érkezési folyamat egy u ´gynevezett ”GI - General interarrival” folyamat, melyet az érkezési id˝ ok¨ ozök várható értékével és a relat´ıv szórásnégyzetével (c2 ) jellemz¨ unk, valamint a kiszolgálási id˝o bár-

3

1 Bevezetés milyen ´ altal´ anos eloszl´ as´ u lehet. Az ´ıgy kapott modellben a rendszerparaméterek kisz´ am´ıt´ as´ ahoz a QNA GI/G/1 approximációt használtam [12]. Az aproxim´ aci´ o valid´ al´ as´ ahoz egy szimulációs programot kész´ıtettem. A 7. fejezetben megvizsg´ altam, milyen hatással van a heterogén forgalom a Proxy Cache szerver hatékonyságára. Ebben az esetben a keresett fájlokat a méret¨ uk alapj´ an két osztályba soroljuk. Ebben az esetben a válaszid˝ ok kisz´ am´ıt´ as´ ahoz k¨ ul¨ on kell vizsgálni a két csoportba tartozó kérések v´ alaszidejeit, majd ezek seg´ıtségével kaphatjuk meg egy tetsz˝oleges igény ´ atlagos v´ alaszidejét. Vég¨ ul a 8. fejezetben a disszert´ acióban szerepl˝o eredmények összefoglalója találhat´ o.

4

2 Sorban´ all´ asi rendszerek ´ es h´ al´ ozatok Mint általában a sz´ am´ıt´ ogépes rendszereknél, a Web szerverek is több kérést kell kiszolg´ aljanak, melyek mindegyike verseng a sz¨ ukséges er˝oforrásokért. Mivel egy id˝ oben egy kérés egyszerre csak egy er˝oforrást érhet el, ´ıgy a többi kérésnek v´ arakoznia kell egy pufferben. Amint egy er˝oforrás felszabadul, egy kérés a pufferb˝ ol automatikusan átker¨ ul a kiszolgálócsatornába, valamint minden u ´jonnan érkez˝o kérés a pufferbe ker¨ ul amennyiben a kiszolg´ al´ o csatorna nem szabad. A sorbanállás elmélet seg´ıtségével szám´ıthat´ oak ki a rendszer jellemz˝oi, mint a sorhossz (a rendszerben lév˝o igények sz´ ama), a v´ alaszid˝ o (egy igény rendszerben eltöltött ideje), stb., valamint a sorban´ all´ asi rendszerek és hálózatok seg´ıtségével vizsgálhatóak a bonyolultabb alkalmaz´ asi rendszerek is [21], [18], [20]. Ebben a fejezetben igyeksz¨ unk egy r¨ ovid, lényegretör˝o bemutatást adni a sorbanállási rendszerekr˝ ol és h´ al´ ozatokr´ ol.

2.1.

Sorban´ all´ asi rendszerek vizsg´ alata:

Egy sorbanállási modellt az al´ abbi szerkezet˝ u kóddal jellemezhet¨ unk: A/B/m/k/n/P, ahol • A - az egym´ ast k¨ ovet˝ o igények beérkezése között eltelt id˝o eloszlása: – D - determinisztikus – M - exponenci´ alis

5

2 Sorban´ all´ asi rendszerek és h´ al´ ozatok

2.1. ´ abra. Egyszer˝ u sor

– G-´ altal´ anos • B - a kiszolg´ asi id˝ o eloszl´ asa: – D - determinisztikus – M - exponenci´ alis – G-´ altal´ anos • m - a kiszolg´ al´ o egységek száma. • k - a rendszer kapacit´ asa. Abban az esetben ha nincs megadva akkor a kapacit´ ast végtelennek tekintj¨ uk. • k - az igények forr´ as kapacitása. Abban az esetben ha nincs megadva akkor a kapacit´ ast végtelennek tekintj¨ uk. ´ ekei lehetnek: • P - a kiszolg´ al´ asi protokoll. Ert´ – FIFO - First In Last Out – LIFO - Last In First Out – Priorit´ asos kiszolg´ al´ as. Abban az esetben ha nincs megadva az alapértelmezett a FIFO. A 2.1-es ´ abr´ an egy egyszer˝ u sorbanállási modell látható, ahol az érkezési intenzit´ as (az egységnyi id˝ o alatt beérkezett igények átlagos száma) λ, valamint az ´ atlagos kiszolg´ al´ asi id˝o µ1 . Amennyiben az érkezési intenzitás kisebb mint a kiszolg´ al´ as intenzitása (λ < µ) azt mondjuk, hogy

6

2.1 Sorbanállási rendszerek vizsgálata: a rendszer stabil, azaz minden kérés ki lesz szolgálva, valamint a rendszerben tartózkod´ o igények ´ atlagos sz´ ama (N ) véges. Egy kérés átlagos tartózkodási ideje (T ) a Little formula (l´ asd [27]) alapján:

T =

N . λ

(2.1)

Az M/M/1-es sorban´ all´ asi rendszerr˝ ol beszél¨ unk, amennyiben az érkezések közötti id˝ointervallumok f¨ uggetlen λ paraméter˝ u exponenciális eloszlás´ u valósz´ın˝ uségi változ´ ok valamint a kiszolg´ al´ asi id˝o eloszlása is exponenciális µ paraméterrel. Ebben az esetben a rendszer paramétereket a következ˝o képletek adják (stabil esetben): • P0 annak a stacion´ arius val´ osz´ın˝ usége, amikor a rendszer u ¨res 1

P0 = 1+

P∞ λ k k=1

P0 = 1 −

µ

(2.2) ,

λ . µ

• Pk az a stacion´ arius val´ osz´ın˝ uség, amikor a rendszer a k állapotban van, ahol k λ Pk = P0 . (2.3) µ • A rendszerben tart´ ozkod´ o igények ´ atlagos száma: N=

ρ , 1−ρ

(2.4)

ahol ρ = µλ . • A pufferben tart´ ozkod´ o igények ´ atlagos száma: Nq =

ρ2 . 1−ρ

(2.5)

7

2 Sorban´ all´ asi rendszerek és h´ al´ ozatok • A szerver kihaszn´ alts´ aga Us = 1 − P0 = ρ.

(2.6)

• Az ´ atlagos v´ arakoz´ asi id˝ o W =N

1 ρ = . µ µ(1 − ρ)

(2.7)

• A rendszerben t¨ olt¨ ott ´ atlagos id˝o T =

2.2.

1 . µ−λ

(2.8)

Sorban´ all´ asi h´ al´ ozatok vizsg´ alata

Rendszerint egy egyed¨ uli sor nem alkalmas egy bonyolultabb rendszer modellezéséhez, mint péld´ aul egy Web szervert tartalmazó rendszer. Ilyen rendszereket ´ altal´ aban h´ al´ ozati modellekkel ábrázolhatunk, ahol a rendszerben lév˝ o sorokra u ´gy tekint¨ unk, mint k¨ ulönálló csomópontokra. Az ilyen sorban´ all´ asi h´ al´ ozatokat nyitottnak nevezz¨ uk, ha az u ´j igények a rendszeren k´ıv¨ ulr˝ ol érkeznek, és a kés˝obbiekben el is fogják hagyni a rendszert. Egy nyitott sorban´ all´ asi hálózatot nyitott Jackson hálózatnak nevez¨ unk, ha teljes¨ ulnek a k¨ ovetkez˝o feltételek: • Az i-edik sor kiszolg´ al´ asi ideje µi paraméter˝ u exponenciális eloszlás´ u val´ osz´ın˝ uségi v´ altoz´ o • Az i-edik sorhoz a h´ al´ ozaton k´ıv¨ ulr˝ol érkez˝o kérések Λi paraméter˝ u Poisson-folyamat szerint érkeznek • A kiszolg´ al´ asi protokol FCFS Burke és Jackson tétele alapj´ an (lásd [12]) a következ˝o megállap´ıtásokat tehetj¨ uk: • Poisson-folyamatok véletlen elágaztatásával Poisson-folyamatokat kapunk. (L´ asd 2.2 grafikont.)

8

2.2 Sorbanállási hálózatok vizsgálata

2.2. ´ abra. Folyamatok egyes´ıtése és osztása

• F¨ uggetlen Poisson-folyamatok egyes´ıtése Poisson-folyamat. (Lásd 2.2 grafikont.) • M/M/1-es sorban´ all´ asi rendszer esetében a távozási folyamat Poissonfolyamat, intenzit´ asa pedig megegyezik az érkezési intenzitással. • A rendszerben lév˝ o k¨ ul¨ on´ all´ o sorok u ´gy viselkednek mintha f¨ uggetlenek lennének egym´ ast´ ol. • A sorokhoz érkez˝ o folyamatok Poisson-folyamatként viselkednek abban az esetben is ha val´ oj´ aban nem azok. Ilyen eset például a direkt visszacsatol´ as (L´ asd 2.3 ´ abr´ at), mely esetben a sorhoz érkez˝o folyamat nem Poisson-folyamat, de a t´ avozási folyamat Poisson. Tekints¨ unk egy nyitott Jackson h´ al´ ozatot, melyben K darab sor található. Az i-edik sorhoz a rendszeren k´ıv¨ ulr˝ ol érkez˝o folyamat legyen Poissonfolyamat Λi paraméterrel. A Λi = 0 intenzitás azt jelenti, hogy az i-edik sorhoz nem érkezik k´ıv¨ ulr˝ ol igény. Mivel egy nyitott rendszerr˝ol beszél¨ unk, feltételezz¨ uk, hogy legal´ abb egy Λj > 0. A i-edik csomópont által kiszolgált igény a j-edik csom´ tov´ uséggel, oponthoz abb´ıtódik pi,j valósz´ın˝ PK vagy elhagyja a rendszert 1 − j=1 pij valósz´ın˝ uséggel. A j-edik sor

9

2 Sorban´ all´ asi rendszerek és h´ al´ ozatok kiszolg´ al´ asi ideje µj paraméter˝ u exponenciális eloszlás, valamint a sorhoz érkez˝o folyamat teljes érkezési intenzitása λj , ahol λj = Λj +

K X

λi pij

(2.9)

i=1

minden j = 1, 2, · · · , K esetén. Rendszerparaméterek: • Teljes ´ atereszt˝ oképesség: λ=

K X

Λi .

(2.10)

i=1

´ • Atlagos forgalmi intenzit´ as a j-edik csom´ opontn´ al: ρj =

λj . µj

(2.11)

• Egy igény l´ atogat´ asainak sz´ ama a j-edik csom´ opontn´ al: K

Λj X λj = + Vi pij . Vj = λ λ

(2.12)

i=1

• Az ´ atlagos igénysz´ am a j-edik csom´ opontn´ al: Nj =

ρj . 1 − ρj

(2.13)

• Az ´ atlagos v´ alaszid˝ o a j-edik csom´ opontn´ al: Tj = Vj ∗ azaz Tj =

10

Nj , λj

Nj 1 ρj = . λ λ 1 − ρj

(2.14)

(2.15)

2.2 Sorbanállási hálózatok vizsgálata

2.3. ´ abra. Direkt visszacsatolás

• Az ´ atlagos igénysz´ am a rendszerben: N=

K X

Nj =

j=1

K X j=1

ρj . 1 − ρj

(2.16)

• Az ´ atlagos v´ alaszid˝ o a rendszerben: K

K

j=1

j=1

X Bj 1 X ρj N = = , T = λ λ 1 − ρj 1 − λBj

(2.17)

V

ahol Bj = µjj egy igény teljes ´ atlagos feldolgozási ideje a j-edik csomópontn´ al.

11

2 Sorban´ all´ asi rendszerek és h´ al´ ozatok

12

3 Web szerver modell Ebben a fejezetben bemutatjuk, hogyan lehet modellezni egy egyszer˝ u Web szervert nyitott sorban´ all´ asi h´ al´ ozatok seg´ıtségével. (Lásd [32].) Egy Web szerver m˝ uk¨ odési modellje l´ athat´ o a 3.1 ábrán. A modell részletesebb ismertetése el˝ott sorbavessz¨ uk a v´ alaszid˝ ot meghatározó f˝obb paramétereket: ´ • Erkez´ esi intenzit´ as (λ): A Web szerverhez érkez˝o HTTP fájl kérések átlagos száma m´ asodpercenként. • Az ´ atlagos f´ ajl méret (F ): A Web szerver által kiszolgált fájlok átlagos mérete byteban megadva. Ez az érték természetesen nagyban f¨ ugg a Web szervert˝ ol is. • Puffer méret (B): A Web szerverhez tartozó puffer méret, mely a szerver diszk blokk méretével egyezik meg. [32] alapján az átlagos puffer méretet 2000 byte. • Inicializációs id˝ o (I), Statikus szerver id˝o (Y ) valamint a Dinamikus szerver ar´ any (R) egy¨ uttesen a Web szerver kiszolgálási intenzitását hat´ arozz´ ak meg. Az I ´ abr´ azolja a Web szerverhez való kapcsolódáshoz sz¨ ukséges ¨ osszes egyszeri inicializációs id˝ot, mint például a TCP kapcsolat kiép´ıtése, vagy a ”suffix mapping”. Ennek a csomópontnak a kiszolg´ al´ asi intenzit´ asa I1 . Y reprezentálja a puffer feldolgozásával t¨ olt¨ ott id˝ ot, mely f¨ uggetlen a puffer méretét˝ol. R pedig a byte/másodpercben megadott ar´ anyt jelenti, mellyel a Web szerver a puffer tartalm´ at tov´ abb´ıtja. A Web szerver átlagos kiszolgálási intenzitása ezek alapj´ an: µW eb =

1 Y +

B R

.

(3.1)

13

3 Web szerver modell A Web szerver kiszolg´ al´ asi intenzitását meghatározó paraméterek részletes le´ır´ asa megtal´ alható a [32]-ben. • Kliens h´ al´ ozati s´ avszélesség: Nc , Szerver hálózati sávszélesség: Ns . Amint l´ athat´ o a 3. ´ abr´ an a modell 4 csomópontot tartalmaz. Két csomópont ábr´ azolja a Web szerver architekt´ uráját, valamint 2 csomópont ábrázolja a kliens és szerver oldali hálózati kommunikációs id˝ot (File transfer time). Gyakran az egyszer˝ u hálózati kommunikációt is sorbanállási modellel ´ abr´ azolj´ ak, de jelen esetben megelégsz¨ unk egyszer˝ uen konstans transzfer id˝ ok haszn´ alat´ aval ( [32], [8]). Feltételezz¨ uk, hogy az igények λ paraméter˝ u-Poisson-folyamat alapján érkeznek a kliensek fel˝ol. Miel˝ott az igények megérkeznének a Web szerverhez, el˝oször át kell essenek egy egyszeri inicializ´ aci´ os elj´ ar´ ason, amit az els˝o csomópont szemléltet. Az inicializ´ aci´ os id˝ ot a 1 TInit = 1 (3.2) I −λ képlet szolg´ altatja. Ha a felhasznló által kért fájl mérete nagyobb, mint a szerver kimen˝ o puffere, akkor egy visszacsatolási ciklus kezd˝odik, mely addig tart, m´ıg az igény kiszolg´ alása be nem fejez˝odik. Legyen q annak a valósz´ın˝ usége, hogy a f´ ajlt els˝ o próbálkozásra siker¨ ul feldolgozni, ahol B . (3.3) q = min 1, F Ezek alapj´ an a Web szerverhez érkez˝o igények intenzitása, figyelembe véve az esetleges visszacsatol´ ast: λ λ2 = . (3.4) q A korábbiak alapj´ an a Web szerver kiszolgálási intenzitása: µW eb =

1 Y +

B R

,

(3.5)

´ıgy a Web szerver kiszolg´ al´ asi ideje (2.15) alapján: TW eb =

14

1 λ2 · . λ µW eb − λ2

(3.6)

3.1. ´ abra. Web szerver modell

A teljes válszid˝oh¨ oz (T ) a modell alapj´ an még hozzá kell vegy¨ uk azt a transzfer id˝ot am´ıg az igény ´ atjut a szerver és a kliens hálózatán. Ezek alapján válaszid˝ot az al´ abbi képlet adja:

1 1 λ2 F F + ∗ + + − λ λ µW eb − λ2 Ns Nc YR+B F F I + + + . = 1−λ∗I qR − λ(Y R + B) Ns Nc

T =

1 I

(3.7)

A következ˝o néh´ any grafikonon megvizsg´ aljuk, hogyan változik a Web szerver válaszideje a szerver sebességének valamint a fájl méretének változtatásával. Mivel jelen esetben minket csak a Web szerverrel kapcsolatos válaszid˝ok érdekelnek a 3.7 képletet annyiban módos´ıtjuk, hogy az áthaladási id˝ot a kliens és a szerver h´ al´ ozatokon nem vessz¨ uk figyelembe. Így a

TInit+W eb =

I YR+B + 1−λ∗I qR − λ(Y R + B)

(3.8)

15


3.2. ´ abra. F´ ajl méret hatása a Web szerver válaszidejére

képlettel vizsg´ alni tudjuk a h´ al´ ozati transzfer id˝okt˝ol megtiszt´ıtott válaszid˝ot. A 3.2 grafikonon megfigyelhetj¨ uk, milyen hatással van a fájl méretének növelése a v´ alaszid˝ ore. A sz´ am´ıt´ asban használt paraméterek értékei a 3.1. táblázatban l´ athat´ oak. A (3.3) képlet alapj´ an l´ athatjuk, hogy nem történik visszacsatolás a Web szerveren, am´ıg a f´ ajl mérete el nem éri a puffer méretét. Tehát a válaszid˝o konstans egészen addig, m´ıg el nem éri a fájl a puffer méretet. Ezt figyelhetj¨ uk meg a 3.2 grafikonon is. Amint látható, ahogy a fájl mérete meghaladja a puffer méretét, elkezd˝ odik a Web szervernél a visszacsatolás, azaz a tartózkod´ asi id˝ o n¨ ovekedésnek indul. A 3.3 grafikonon a válaszid˝ot szintén a fájl méret f¨ uggvényeként ´ abr´ azoltuk. Láthatjuk, hogy a válaszid˝o a fájl méretének n¨ ovelésével szintén n¨ ovekszik. A 3.4 grafikonon a Web szerver sebességének hat´ as´ at figyelhetj¨ uk meg a válaszid˝ore. Amint azt várni lehetett, a szerver sebességének növelésével a válaszid˝o csökken.

16

3.3. ábra. F´ ajl méret hat´ asa a Web szerver válaszidejére 2

3.4. ábra. A Web szerver sebességének hatása a válaszid˝ore

17


λ: F: B: I: Y: R:

18

3.1. t´ abl´ azat. Web szerver modell param´ eterei Az érkezési intenzit´ as 50 kérés/másodperc Az ´ atlagos f´ ajl méret (byte-ban) változó A Web szerver kimen˝ o puffere (byte-ban) 2000 byte Inicializ´ al´ asi id˝ o (m´ asodperc) 0.004 másodperc Statikus szerver id˝ o (m´ asodperc) 0.000016 másodperc Dinamikus server ar´ any (byte/másodperc) 1310720 byte/másodperc

4 Proxy Cache szerver modell Ebben a fejezetben részletesen bemutatjuk egy Proxy Cache szerver matematikai modelljét és annak m˝ uk¨ odését. A fejezetben szerepl˝ o eredmények a [9] cikk¨ unkben szerepl˝o modell általános´ıtása.

4.1.

A javasolt modell

Proxy Cache szervert haszn´ alva, ha egy f´ ajlt le akarunk tölteni egy távoli Web szerverr˝ol, el˝ osz¨ or meg kell vizsg´ alni, hogy a keresett fájl megtalálhatóe a Proxy Cache szerveren. Ennek a val´ osz´ın˝ uségét p-vel jelölj¨ uk. Amennyiben a keresett dokumentum megtal´ alhat´ o a Proxy Cache szerveren, egy másolat a fájlról azonnal tov´ abb´ıt´ odik a felhasználónak. Amennyiben a dokumentum nem tal´ alhat´ o meg a Proxy Cache szerveren, az igény tovább´ıtódik a t´ avoli Web szerverhez. A dokumentum a Web szerverr˝ol el˝oször a Proxy Cache szerverre érkezik vissza, ahonnan egy másolat a fájlról azonnal a felhaszn´ al´ ohoz ker¨ ul. Az eredeti példány tárolódik a Proxy Cache szerveren, ´ıgy a kés˝ obbiekben elérhet˝o lesz a felhasználók számára. A Proxy Cache szerver hatékonysága a következ˝o tényez˝okt˝ol f¨ ugg: • találati arány (a kért dokumentum milyen valósz´ın˝ uséggel található meg a Proxy Cache szerveren) • Proxy Cache szerver karakterisztik´ aja - sebessége • kliens oldali s´ avszélesség • szerver oldali s´ avszélesség

19

4 Proxy Cache szerver modell

4.1. ´ abra. Proxy Cache szerver modellje

• a bels˝ o és k¨ uls˝ o igények érkezési intenzitása • Web szerver karakterisztik´ aja - sebessége A Proxy Cache szerver matematikai modelljének megalkotásához a [32] és [11] modelljeit vett¨ uk alapul. A [11]-ben szerepl˝o Proxy Cache szerver modellben a Web szerver és a Proxy Cache szerver ugyanannak a zárt részhál´ ozatnak a csom´ opontjaiként voltak ábrázolva, mely nem tekinthet˝o megfelel˝ onek mivel ebben az esetben a Web szerver leterheltségét csak a Proxy Cache szerveren nem tal´ alható igények határozzák meg, valamint a Proxy Cache szerver ´ abr´ azol´ asa is hiányos, mivel a keresési id˝ot és a Proxy Cache szervert egy csom´ opontként jelölte. Ezen k´ıv¨ ul a Proxy Cache szervert ´ abr´ azol´ o csom´ opontot a Web szerverekre jellemz˝o visszacsatolás nélk¨ ul ´ abr´ azolta, mely szintén torz´ıtja a kapott eredményeket. A [8] cikk¨ unkben részletesen bemutattuk a [11]-ben szerepl˝o modell hiányosságait. Az általunk ´ altal´ anos´ıtott modell a 4.1 ábrán látható. A 4.1 ábra egy igény lehetséges u ´tj´ at mutatja a felhasználótól kiindulva egészen a visszaérkezésig.

20

4.1 A javasolt modell A modellben szerepl˝ o paraméterek list´ aja a 4.3 táblázatban látható. A modell alapján a t´ avoli Web szerverhez két irányból érkezhetnek igények. Egyfelel˝ol a Proxy Cache szerver ir´ any´ ab´ ol, valamint a Proxy Cache szervert˝ol teljesen f¨ uggetlen¨ ul érkezhetnek az u ´gynevezett k¨ uls˝o igények, melyek természetesen nem mennek kereszt¨ ul a Proxy Cache szerveren. Feltételezz¨ uk, hogy az igények a Proxy Cache szerverhez λ paraméter˝ u Poissonfolyamat szerint érkeznek, valamint a Web szerverhez k´ıv¨ ulr˝ol érkez˝o igények Λ paraméter˝ u Poisson-folyamat alapj´ an érkeznek. Az egyenes vonal (λ1 ) reprezent´ alja azt az esetet, amikor a keresett fájl megtalálható a Proxy Cache szerveren. Szaggatott vonallal rajzolva jelölt¨ uk (λ2 ) azon igények u ´tj´ at, melyek nem tal´ alhatóak meg a Proxy Cache szerveren, ´ıgy ezek az igények tov´ abb´ıt´ odnak a távoli Web szerverhez. λ1 és λ2 ezen igények intenzit´ asai: λ1 = p ∗ λ,

(4.1)

λ2 = (1 − p) ∗ λ,

(4.2)

ahol p a találati val´ osz´ın˝ uség. Ahogy már korábban jelezt¨ uk, a Web szerver nem csak a Proxy Cache szerver fel˝ol érkez˝ o igényeket szolg´ alja ki, hanem az u ´gynevezett k¨ uls˝o igényeket is, melyek érkezési intenzit´ asa Λ. λ3 jelöli a Web szerverhez érkez˝o összes kérés érkezési intenzit´ as´ at, mely λ3 = λ2 + Λ.

(4.3)

Ahogy a 3. fejezetben ismertett¨ uk, a Web szerverhez érkez˝o igényeknek el˝oször át kell esni¨ uk egy egyszeri inicializ´ ación. Jelen modell alapján ez az inicializálás a λ3 intenzit´ as´ u folyamaton megy végbe, és az inicializálási id˝o:

1 Is

1 . − λ3

(4.4)

21

4 Proxy Cache szerver modell A Web szerver és a Proxy Cache szerver hatékonyságát három - három paraméterrel ´ırhatjuk le (l´ asd a 3. fejezetet). Ezek rendre a Bs , Ys , Rs illetve Bxc , Yxc , Rxc . Ha a kért fájl mérete nagyobb mint a Web szerver kimen˝ o pufferének mérete, akkor egy visszacsatolási ciklus kezd˝odik, mely addig tart m´ıg a f´ ajl feldolgozása teljes egészében be nem fejez˝odik. Legyen

Bs q = min 1, F

(4.5) 0

annak a val´ osz´ın˝ usége, hogy a f´ ajl tovább´ıtása els˝ore siker¨ ult. Legyen λ3 a Web szerverhez érkez˝ o igények intenzitása figyelembe véve a visszacsatolási ciklust. Így 0

λ3 =

λ3 . q

(4.6)

Hasonl´ oan a Proxy Cache szerver esetén legyen

qxc

Bxc = min 1, F

(4.7)

annak a val´ osz´ın˝ usége, hogy a keresett fájl tovább´ıtása a Proxy Cache 0 szervernél els˝ ore siker¨ ult, valamint legyen λ a Proxy Cache szerverhez érkez˝o igények intenzit´ asa, ahol 0

λ = λ1 + λ2 + (1 − qxc ) ∗ λ

0

(4.8)

azaz 0

λ =

λ . qxc

(4.9)

A fenti eredményeket felhaszn´ alva kapjuk Txc -t, egy bels˝o igény teljes válaszidejét Proxy Cache szerver használatával, ahol

22

4.1 A javasolt modell

( Txc =

)

F Bxc

1 1 −λ I

F Nc

+p + 1 − qλ xc Yxc + Bxc ) ( Rxc   F Bs 1 + (1 − p) 1 −λ + λ 1 − q3  Is 3 s (Ys + B Rs )) xc

+ NFs +

F Bxc 1 Yxc + Bxc Rxc

(

)

− qλ

+

xc

(4.10)

F Nc

valamint 3.7 alapj´ an legyen T egy igény v´ alaszideje Proxy Cache szerver használata nélk¨ ul, ahol

T =

1 Is

1 + − (λ + Λ)

F Bs 1 s Ys + B R

− (λ + Λ)/q

+

F F + . Ns Nc

(4.11)

s

A Txc válaszid˝o h´ arom részb˝ ol tev˝ odik ¨ ossze: az els˝o annak az id˝otartama, m´ıg eld˝ol, hogy az igényelt f´ ajl megtal´ alható-e a Proxy Cache szerveren vagy nem. Ez a (2.8) képletb˝ ol ad´ odik, ahol Ixc az átlagos kiszolgálási id˝o. A képlet m´ asodik tagja annak a v´ alaszideje, amikor az igény megtalálható a Proxy Cache szerveren, melynek kiszolgálási intenzitása (3.5) 1 F alapján asi” id˝o am´ıg a keresett fájl keBxc valamint Nc az ”utaz´ Yxc + R

xc

reszt¨ uljut a kliens h´ al´ ozaton. A képlet harmadik tagja reprezentálja annak az igénynek a v´ alaszidejét, mely nem található meg a Proxy Cache szerveren. Ez tov´ abbi ¨ ot részre tagol´ odik. Az els˝o a 3.2 alapján az egyszeri inicilaiz´ al´ asi id˝ o, a m´ asodik a 2.15 alapján a Web szerver kiszolgálóegységénél t¨ olt¨ ott id˝ o. A harmadik a Web szerver hálózatán való áthaladáshoz sz¨ ukséges Web szerver oldali transzfer id˝o. A negyedik rész a fentiekhez hasonl´ oan a Proxy Cache szerverhez visszaérkez˝o igények kliens felé való tovább´ıt´ as´ anak id˝ otartam´ at ´ abrázolja. Az utolsó ötödik rész pedig a kliens hál´ ozat transzfer idejét ´ abr´ azolja. A rendszer akkor lesz stabil, ha a rendszerben minden sorbanállási csomópont stabil. A 4.1 modellben 4 sorban´ all´ asi csomópont található, melyek mindegyikére teljes¨ ulnie kell a k¨ ovetkez˝ o feltételeknek:

23

4 Proxy Cache szerver modell • Keresési csom´ opont: ρLookup < 1, ahol ρLookup = λ ∗ Ixc , azaz λ < • Proxy Cache szerver: ρP CS < 1, ahol ρP CS =

λ

0

µP CS ,

azaz λ <

• Egyszeri inicializ´ al´ asi csom´ opont: ρInit < 1, ahol ρInit = λ3 ∗ Is , azaz λ < • Web szerver: ρW eb < 1, ahol ρW eb =

0

λ3 µW eb ,

azaz λ <

1 Ixc .

Rxc qxc Yxc Rxc +Bxc . 1 (1−p)Is

−

Λ 1−p .

Rs q (1−p)(Ys Rs +Bs )

−

Λ (1−p) .

Tehát a rendszer stabil, ha

Rxc qxc 1 1 Ixc , Yxc Rxc +Bxc , (1−p)I s Rs q Λ (1−p)(Ys Rs +Bs ) − (1−p) .

λ < min

4.2.

−

Λ 1−p ,

(4.12)

Numerikus eredm´ enyek

A numerikus eredmények a MAPLE 9 program seg´ıtségével lettek kiszámolva. A sz´ am´ıt´ asokhoz a Web és Proxy Cache szerver paraméterek értékeit [28] alapj´ an hat´ aroztuk meg. Ezek az értékek: Is = Ixc = 0.004 másodperc, Bs = Bxc = 2000 byte, Ys = Yxc = 0.000016 másodperc, Rs = Rxc = 1.25 Mbyte/m´ asodperc, Ns = 1544 Kbit/másodperc valamint Nc = 128 Kbit/m´ asodperc. A fejezetben található grafikonokban pontozott vonallal ´ abr´ azoltuk a Proxy Cache szervert tartalmazó esetet, valamint egyenes vonallal a Proxy Cache szervert nem tartalmazó esetet.

4.2.1.

Az ´ erkez´ esi intenzit´ as hat´ asa a v´ alaszid˝ ore

A 4.2 ´ abra a teljes v´ alaszid˝ ot ´ abrázolja a Proxy Cache szerver fel˝ol érkez˝o igények intenzit´ as f¨ uggvényeként. Ezen a grafikonon a k¨ uls˝o igények érkezési intenzit´ asa Λ = 100 igény/m´ asodperc, valamint a találati valósz´ın˝ uség p = 0.1. Mint ahogyan l´ athat´ o, Proxy Cache szerver installálása csak igen magas bels˝ o érkezési intenzit´ as (λ > 100 igény/másodperc) esetén éri meg.

24

4.2 Numerikus eredmények A 4.3 grafikon esetében ugyanazokat a paramétereket használtuk, egyed¨ ul a találati valósz´ın˝ uséget n¨ ovelt¨ uk p = 0.15-re. Megfigyelhetj¨ uk, hogy ilyen paraméterek esetében a Proxy Cache szerver használatával a válaszid˝ok már λ > 80 igény/m´ asodperc esetén alacsonyabbak, mint Proxy Cache szerver használata nélk¨ ul. A 4.4 grafikonon azt az esetet vizsg´ altuk meg, amikor alacsony találati valósz´ın˝ uség mellett p = 0.1, egy relat´ıve leterhelt Web szervert˝ol kér¨ unk le adatot. (A k¨ uls˝ o kérések intenzit´ asa Λ = 150 kérés/másodperc). Mint ahogyan várható volt, terhelt Web szerver esetén a Proxy Cache szerver u ¨zemeltetése már kis bels˝ o igény intenzit´ as esetén is megtér¨ ul. (λ > 50). Amennyiben pedig a bels˝ o keresési szok´ asok hasonlóak, azaz a találati valósz´ın˝ uség magasabb és a Web szerver is leterhelt (p = 0.15 és Λ = 150), a Proxy Cache szerver haszn´ alata m´ ar λ > 20 intenzitás esetén is alacsonyabb válaszid˝oket eredményez, mint ahogyan a 4.5 grafikonon látható. A 4.2, 4.3, 4.4 valamint 4.5 ´ abr´ ak tanulm´ anyozása alapján megállap´ıthatjuk, hogy a Proxy Cache szerver haszn´ alata alacsonyabb válaszid˝oket eredményez, amennyiben magas p > 0.15 tal´ alati valósz´ın˝ uséget vagy leterhelt Web szervert haszn´ alunk.

4.2.2.

A k¨ uls˝ o´ erkez´ esi intenzit´ as hat´ asa a v´ alaszid˝ ore

A következ˝o részben megvizsg´ aljuk, hogyan hat a Web szerverhez érkez˝o k¨ uls˝o igények intenzit´ asa a bels˝ o igények teljes válaszidejére. A 4.6 grafikonon a Proxy Cache szerver fel˝ ol érkez˝ o ”bels˝ o” igények intenzitása viszonylag alacsony λ = 20 kérés/m´ asodperc, valamint a találati valósz´ın˝ uség is alacsony p = 0.1. Mint ahogyan l´ atjuk a válaszid˝o még Λ = 170 kérés/másodperc k¨ uls˝ o érkezési intenzit´ as mellett is nagyobb Proxy Cache szerver használat´ aval mint anélk¨ ul. A 4.7 grafikonon az el˝oz˝o esethez képest csak a bels˝ o érkezési intenzit´ ast n¨ ovelt¨ uk λ = 70 kérés/másodpercre, a találati val´ osz´ın˝ uség maradt v´ altozatlan (p = 0.1). Mint ahogy láthatjuk, amennyiben a Web szerver leterheltsége alacsonyabb (Λ < 130) a válaszid˝ok Proxy Cache szerver haszn´ alatával nagyobbak mint nélk¨ ule. Viszont ha a k¨ uls˝ o igények érkezési intenzitása magas (Λ > 130) akkor a válaszid˝o alacsonyabb Proxy Cache szerver használatával. A 4.8 grafikonon a találati val´ osz´ın˝ uség megdupl´ az´ asa (p = 0.2) mellett vizsgáltuk a

25


4.2. ´ abra. p = 0.1, F = 5275 byte, Λ = 100

4.3. ´ abra. p = 0.15, F = 5275 byte, Λ = 100

26

4.2 Numerikus eredmények

4.4. ´ abra. p = 0.1, F = 5275 byte, Λ = 150

4.5. ´ abra. p = 0.15, F = 5275 byte, Λ = 150

27


4.6. ´ abra. p = 0.1, F = 5275 byte, λ = 20

válaszid˝ oket alacsony bels˝ o érkezési intenzitás mellett (λ = 20). Ebben az esetben azt l´ athatjuk, hogy a válaszid˝ok alacsonyabbak Proxy Cache szerver haszn´ alat´ aval, ha Λ > 100. A 4.9 garfikonon azt láthatjuk, hogy magas tal´ alati val´ osz´ın˝ uség használata mellett (p = 0.3) a válaszid˝ok már minden egyéb paramétert˝ ol f¨ uggetlen¨ ul alacsonyabbak Proxy Cache szerver haszn´ alat´ aval.

4.2.3.

A f´ ajl m´ eret´ enek hat´ asa a v´ alaszid˝ ore

Ebben a fejezetben arra kerest¨ uk a választ, hogyan befolyásolja a fájl mérete a Proxy Cache szerver hatékonyságát. Mint ahogyan a 4.10 képletb˝ol l´ atszik a f´ ajl méret az u ´gynevezett ”transzfer” id˝on k´ıv˝ ul a visszacsatolási val´ osz´ın˝ uség mértékét befolyásolja, mely mind a Web szervert mind a Proxy Cache szervert érinti. A Proxy Cache szerver nélk¨ uli eset 4.11 képletben szintén szerepel mind a kliens mind a szerver oldali ”transzfer” id˝ o, valamint a Web szerver esetében a visszacsatolási valósz´ın˝ uség. Proxy Cache szerver haszn´ alatakor, ha a keresett fájl megtalálható a Proxy

28


4.7. ´ abra. p = 0.1, F = 5275 byte, λ = 70

4.8. ´ abra. p = 0.2, F = 5275 byte, λ = 20

29


4.9. ´ abra. p = 0.3, F = 5275 byte, λ = 20

szerveren az igény nem kell kereszt¨ ulhaladjon a szerver hálózatán, valamint a Web szerveren, csak a kliens hálózaton és a Proxy Cache szerveren. Ezek alapj´ an azt v´ arjuk, hogy a fájl méretének növelésével a Proxy Cache szerver haszn´ alata egyre kifizet˝od˝obb lesz. A 4.1 táblázatban a válaszid˝ oket figyelhetj¨ uk meg a fájl méretének f¨ uggvényében ahol a használt paraméterek: λ = 70, Λ = 50, p = 0.2. Amint láthatjuk kis fájlméret esetén Proxy Cache szerverrel nagyobb válaszid˝oket kapunk, mely a f´ ajl méretének n¨ ovelésével egyre jobban közel´ıti a Proxy Cache szerver nélk¨ uli id˝ oket, m´ıgnem 7000 byte feletti fájlméret esetén a Proxy Cache szerver haszn´ alat´ aval m´ ar alacsonyabb válaszid˝oket kapunk.

4.2.4.

A tal´ alati val´ osz´ın˝ us´ eg hat´ asa a v´ alaszid˝ ore

A 4.10 grafikonon l´ athatjuk a találati valósz´ın˝ uség hatását. A teljes válaszid˝o Proxy Cache szerver használata nélk¨ ul f¨ uggetlen a találati valósz´ın˝ uségt˝ ol. Ezt a grafikonon a konstans T = .3726542708 vonal ábrázolja. A grafikont vizsg´ alva l´ athatjuk, hogy a találati valósz´ın˝ uség növelésével a

30

4.2 Numerikus eredmények Fájl méret 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Válaszid˝ o Proxyval 0.0793576509 0.1476041906 0.2162571163 0.2852891224 0.3548299856 0.4250825771 0.4963874129 0.5693749309 0.6453916529 0.7280473497

Proxy nélk¨ ul 0.0763196223 0.1449469371 0.2139376511 0.2833129458 0.3532714229 0.4241768649 0.4967750462 0.5728735971 0.6582764074 0.7874725350

K¨ ulönbség 0.0030380285 0.0026572535 0.0023194652 0.0019761766 0.0015585627 0.0009057122 -0.0003876333 -0.0034986662 -0.0128847545 -0.0594251853

4.1. táblázat. A f´ ajl m´ eret´ enek hat´ asa a v´ alaszid˝ ore válaszid˝o Proxy Cache szerver haszn´ alat´ aval egyre jobban csökken. p ≈ 0.2 értéknél a két v´ alaszid˝ o megegyezik, m´ıg p > 0.2 esetén Proxy Cache szerver használat´ aval alacsonyabb v´ alaszid˝ oket kapunk. A bemutatott numerikus eredményekhez használt konstans adatok a [28] alapján lettek kiv´ alasztva. Az eml´ıtett konstansokkal rendelkez˝o rendszer a mai hálózatokat tekintve nem tekinthet˝o megfelel˝onek, ezért a paramétereket megv´ altoztattuk. A m´ odos´ıtott konstans értékek: Is = Ixc = 0.004 másodperc, Bs = Bxc = 4000 byte, Ys = Yxc = 0.0000016 másodperc, Rs = Rxc = 50 Mbyte/m´ asodperc, Ns = 5 Mbit/másodperc valamint Nc = 20 Mbit/m´ asodperc. A 4.11 grafikonon l´ athatjuk, hogy a m´ odos´ıtott paraméterek mellett a bels˝o érkezési intenzit´ as´ anak hat´ as´ at a v´ alaszid˝ore. Ha a fájl méretet 1 Mbyte-ra áll´ıtjuk, akkor a v´ alaszid˝ ok Proxy Cache szervert használva lényegesen alacsonyabbak, mint Proxy Cache szerver használata nélk¨ ul. A nagyobb eltérés abb´ ol ad´ odik, hogy a kliens oldali sávszélesség jóval nagyobb mint a szerver oldali, ´ıgy a Proxy Cache szerver használata lényegesen jobb eredményt szolg´ altat. A 4.2 táblázatban a válaszid˝oket figyelhetj¨ uk meg a f´ ajl méretének f¨ uggvényében ahol a használt paraméterek: λ = 20, Λ = 10, p = 0.2. Amint l´ athatjuk kis fájlméret esetén Proxy Cache szerverrel nagyobb v´ alaszid˝ oket kapunk. Amikor a fájlméret eléri a 10 Kbyte-ot alacsonyabb v´ alaszid˝ ot kapunk Proxy Cache szerver használatával,

31


4.10. ´ abra. λ = 20, Λ = 100, F = 5275 byte

4.11. ´ abra. p = 0.25, F = 1 Mbyte, Λ = 10

32

4.2 Numerikus eredmények Fájl méret 1000 byte 5000 byte 10 Kbyte 100 Kbyte 0.5 Mbyte 1 Mbyte 1.5 Mbyte

Válaszid˝ o Proxyval 0.009296574550 0.01575827084 0.02422346863 0.1731753428 0.8572366484 1.717521088 2.623580309

Proxy nélk¨ ul 0.006564973644 0.01464310722 0.02522606314 0.2114664212 1.067839041 2.154404036 3.527825467

K¨ ulönbség 0.002731600906 0.00111516362 -0.00100259451 -0.0382910784 -0.2106023926 -0.436882948 -0.904245158

4.2. táblázat. A f´ ajl m´ eret´ enek hat´ asa a v´ alaszid˝ ore, m´ odos´ıtott param´ eterek mellett de k¨ ulönbség lényegében elenyész˝ o. Amikor a fájl méret eléri a 100 Kbyteot a k¨ ulönbség még mindig csak 0.038 másodperc. Viszont amikor a fájl méretetet 1.5 Mbyte-ra emelt¨ uk Proxy Cache szerver használatával a válaszid˝ok közti k¨ ul¨ onbség m´ ar megk¨ ozel´ıti az 1 másodpercet.

33


λ: Λ: F: p: Bxc : Ixc : Yxc : Rxc : Nc : Bs : Is : Ys : Rs : Ns :

34

4.3. t´ abl´ azat. A Proxy Cache szerver modell jel¨ ol´ esei A bels˝ o igények érkezési intenzitása A k¨ uls˝ o igények érkezési intenzitása Az ´ atlagos f´ ajl méret (byte-ban) A tal´ alati val´ osz´ın˝ uség A Proxy Cache szerver kimen˝o puffere (byte-ban) A Proxy Cache szerver keresési ideje (másodpercben) A Proxy Cache szerver statikus szerver ideje (másodpercben) A dinamikus szerver ar´ any a Proxy szerveren (byte/másodperc) Kliens h´ al´ ozati s´ avszélesség (bit/másodperc) Web szerver kimen˝ o puffere (byte-ban) Inicializ´ al´ asi id˝ o (m´ asodpercben) A Web szerver statikus szerver ideje (másodperc) A Web szerver dinamikus szerver aránya (byte/másodperc) Szerver h´ al´ ozati s´ avszélesség (bit/másodperc)

5 A Web szerver ´ es a Proxy Cache szerver meghib´ asod´ as´ anak hat´ asa Jelen esetben az el˝ oz˝ o fejezetben ismertetett Proxy Cache szerver modellt általános´ıtjuk u ´gy, hogy egy mégink´ abb valóságh˝ u modellt kapjunk. A 4. fejezetben mind a Proxy Cache szerver, mind pedig a távoli Web szerver megb´ızhatóak voltak, most pedig feltessz¨ uk, hogy egyik sem megb´ızható, azaz bármelyik¨ uk elromolhat. Az ´ altal´ anos´ıtással az a célunk, hogy megvizsgáljuk a szerverek meghib´ asod´ as´ anak hatását a rendszerparaméterekre. A továbbiakban vizsg´ alni fogjuk a teljes´ıtménybeli k¨ ulönbségeket, amennyiben ”blokkolt” valamint ”intelligens” forr´ asokat feltételez¨ unk. A fejezetben szerepl˝ o eredmények k¨ ozlésre be vannak ny´ ujtva (J6).

5.1.

A javasolt modell

Mivel a vizsgált Markov-l´ anc ´ allapottere, mely a módos´ıtott modellt le´ırja t´ ul nagy, az egyens´ ulyi egyenlet fel´ır´ asa és ezek megoldása t´ ul bonyolult lenne, ezért a MOSEL programcsomagot használjuk a modell le´ırására valamint a rendszerjellemz˝ ok kisz´ am´ıt´ as´ ara. A MOSEL (Modeling, Specification and Evaluation Language) [6] egy le´ıró nyelv, mely seg´ıtségével k¨ ulönböz˝o programcsomagokat haszn´ alhatunk, mint például az SPNP-t (Stochastik Petri Net Package) vagy a TimeNet programcsomagot. A MOSEL által szolg´ altatott eredményeket grafikusan is ábrázolni tudjuk az IGL (Intermediate Graphical Language) seg´ıtségével, mely része a MOSELnek. A modell¨ unk grafikus ´ abr´ azol´ asa nem változott a módos´ıtásokkal, ´ıgy az 5.1 ábrán láthatjuk egy igény lehetséges u ´tját a felhasználótól kiindulva egészen a visszaérkezésig. A modellben szerepl˝o paraméterek listája a 4.3 táblázatban láthat´ o. Mint ahogyan a 4. fejezetben, most is feltételezz¨ uk,

35

5 A Web szerver és a Proxy Cache szerver meghibásodásának hatása

5.1. ´ abra. Proxy Cache szerver modellje

hogy az igények a Proxy Cache szerverhez λ paraméter˝ u Poisson-folyamat szerint érkeznek, valamint a Web szerverhez k´ıv¨ ulr˝ol érkez˝o igények Λ paraméter˝ u Poisson-folyamat alapján érkeznek. Az 5.1 (hasonlóan a 4.1.hez)ábr´ an egyenes vonal (λ1 ) reprezentálja azt az esetet, amikor a keresett fájl megtal´ alhat´ o a Proxy Cache szerveren valamint szaggatott vonallal rajzolva jel¨ olt¨ uk (λ2 ) azon igények u ´tját, melyek nem találhatóak meg a Proxy Cache szerveren, ´ıgy ezek az igények tovább´ıtódnak a távoli Web szerverhez. A Web szerver valamint a Proxy Cache szerver karakterisztikáját meghat´ aroz´ o paraméterek Bs , Ys , Rs valamint Bxc , Yxc , Rxc rendre a szerver kimen˝ o puffere, a statikus szerver id˝o valamint a dinamikus szerver arány. A (3.5) képlet alapj´ an a Web szerver kiszolgálási intenzitása:

µW eb =

1 YS +

BS RS

,

valamint a Proxy Cache szerver kiszolgálási intenzitása:

36

(5.1)


µP CS =

1 Yxc +

Bxc Rxc

.

(5.2)

Ha a keresett fájl nagyobb mint a Web szerver kimen˝o puffere akkor egy visszacsatolási ciklus kezd˝ odik, mely addig tart m´ıg a teljes fájl kiszolgálása be nem fejez˝ odik. Legyen q annak a valósz´ın˝ usége, hogy a fájlt egyb˝ol siker¨ ul tov´ abb´ıtani, ahol Bs q = min 1, . F

(5.3)

Teljesen hasonlóan modellezhet˝ o a Proxy Cache szerver is, ahol a távozó folyamat visszacsatol´ as´ anak a val´ osz´ın˝ usége 1 − qxc ahol, qxc

Bxc = min 1, . F

(5.4)

A Proxy Cache szerver és a Web szerver meghibásodhat a (t, t + dt) intervallumban δpcs dt + o(dt) valamint δweb dt + o(dt) valósz´ın˝ uséggel ha szabadok, valamint γpcs dt + o(dt) és γweb dt + o(dt) valósz´ın˝ uséggel ha foglaltak. Ha a Proxy Cache szerver vagy a Web szerver foglalt állapotban romlanak el, akkor a megszakadt igény feldolgoz´ asa a jav´ıtás befejezése után folytatódik. A jav´ıt´ asi id˝ o exponenci´ alis eloszlás´ u 1/νpcs és 1/νweb átlaggal. Ha a szerverek k¨ oz¨ ul valamelyik elromlik két k¨ ulönböz˝o eset lehetséges. • Blokkolt eset: a szerver meghib´ asodása alatt nem érkezik u ´j igény a szerverhez. • Nem blokkolt eset: a szerver meghibásodása alatt is érkezhetnek u ´jabb igények a szerverhez. Amint látható a modellezett rendszer figyelembe vesz kétféle meghibásodási esetet: foglalt vagy szabad szerver ´ allapotot, valamint két kiszolgálási esetet: blokkolt és nem blokkolt esetet, mely a rendszer nagymérték˝ u bonyolultságát eredményezi. A rendszer állapot´ at a t id˝ opillanatban a

37


XP CS (t) = (YP CS (t), CP CS (t), QP CS (t)),

(5.5)

XW eb (t) = (YW eb (t), CW eb (t), QW eb (t))

(5.6)

valamint a

folyamat ´ırja le, ahol YP CS (t) = YW eb (t) = 0 ha a szerver m˝ uködik, és YP CS (t) = YW eb (t) = 1 ha a szerver hibás, valamint CP CS (t) = CW eb (t) = 0 ha a szerver nem foglalt, valamint CP CS (t) = CW eb (t) = 1 ha a szerver foglalt. Legyen QP CS (t) és QW eb (t) a pufferben lév˝o igények átlagos száma a Proxy Cache szerver valamint a Web szerver esetén. Mivel a haszn´ alt val´ osz´ın˝ uségi v´ altozók f¨ uggetlen exponenciális eloszlás´ uak a rendszer ´ allapot´ at le´ır´ o folyamatok véges állapotter˝ u Markov-láncok. Legyenek a stacion´ arius val´ osz´ın˝ uségek: PP CS (q, r, j) = lim P (YP CS (t), CP CS (t), QP CS (t)), t→∞

(5.7)

q = 0, 1, r = 0, 1, j = 0, · · · , KP CS , és PW eb (q, r, j) = lim P (YW eb (t), CW eb (t), QW eb (t)), t→∞

(5.8)

q = 0, 1, r = 0, 1, j = 0, · · · , KW eb , ahol KP CS és KW eb a szerverek puffer mérete. Amint siker¨ ult megkapnunk a fenti valósz´ın˝ uségeket, az egyens´ ulyi állapothoz tartoz´ o rendszerjellemz˝ oket a következ˝o képletek alapján kapjuk meg: • A szerverek kihaszn´ alts´ aga US,P CS =

KX P CS j=0

38

PP CS (0, 1, j),

(5.9)


US,W eb =

KX W eb

PW eb (0, 1, j).

(5.10)

j=0

• A szerverek elérhet˝ osége AP CS =

1 K P cs X X

PP CS (0, r, j),

(5.11)

PW eb (0, r, j).

(5.12)

r=0 j=0

AW eb =

1 KX W eb X r=0 j=0

• Az ´ atlagos igénysz´ amok MP CS =

1 X 1 K P cs X X

jPP CS (q, r, j),

(5.13)

jPW eb (q, r, j).

(5.14)

q=0 r=0 j=0

MW eb =

1 X 1 KX W eb X q=0 r=0 j=0

• Az ´ atlagos v´ alaszid˝ ok A Little formul´ ak felhaszn´ al´ as´ aval [27] az átlagos válaszid˝ok a következ˝o összef¨ uggésekkel kaphat´ oak meg: TP CS = MP CS /λP CS ,

(5.15)

ahol λP CS a Proxy Cache szerverhez érkez˝o igények átlagos intenzitása, valamint TW eb = MW eb /λW eb (5.16) ahol λW eb a Web szerverhez érkez˝ o igények átlagos intenzitása • Az igények teljes v´ alaszideje F T = TLookup + p ∗ TP CS + Nc F F + TP CS + , + (1 − p) ∗ TInit + TW eb + Ns Nc

(5.17)

39


5.2. ábra. p = 0.25, Λ = 10, νpcs = νweb = 10, and δpcs = δweb = γpcs = γweb = 0.2

ahol TLookup =

1 1 −λ Ixc

a keresési id˝o, am´ıg eld˝ol, hogy az igényelt

f´ ajl megtal´ alhat´ o-e a Proxy Cache szerveren vagy nem, valamint 1 TInit = 1 −λ az egyszeri inicializálási id˝o. Is

5.2.

3


A következ˝ oekben a numerikus eredményeket grafikusan ábrázoljuk, hogy bemutassuk a meghib´ asod´ asi és a jav´ıtási intenzitások hatását a teljes válaszid˝ okre. A sz´ am´ıt´ asokhoz a Web és Proxy Cache szerver paraméterek értékeit [28] alapj´ an hat´ aroztuk meg mint ahogyan a 4. fejezetben is. Ezek az értékek: Is = Ixc = 0.004 másodperc, Bs = Bxc = 2000 byte, Ys = Yxc = 0.000016 m´ asodperc, Rs = Rxc = 1.25 Mbyte/másodperc, Ns = 1544 Kbit/m´ asodperc valamint Nc = 128 Kbit/másodperc.

40


5.3. ábra. p = 0.25,λ = Λ = 10, νpcs = νweb = 10, and δpcs = δweb = γweb = 0.2

5.4. ábra. p = 0.25,λ = 30, Λ = 10, νpcs = νweb = 10, and δweb = γpcs = γweb = 0.2

41


5.5. ábra. p = 0.25,λ = 40, Λ = 10, νweb = 10, and δpcs = δweb = γpcs = γweb = 2

5.6. ´ abra. λ = Λ = 10, νpcs = νweb = 10, and δpcs = δweb = γpcs = 0.2

42


5.7. ábra. λ = Λ = 10, νpcs = νweb = 10, and δpcs = γpcs = γweb = 0.2

5.8. ábra. λ = Λ = 10, νpcs = 10, and δpcs = δweb = γpcs = γweb = 2

43


5.9. ábra. λ = 30, Λ = 10, νpcs = νweb = 10, and δpcs = δweb = γpcs = γweb = 0.2

5.10. ábra. λ = 40, Λ = 10, νpcs = νweb = 10, and δpcs = δweb = γpcs = γweb = 0.2

44


5.2.1.

Eredm´ enyek

• Az 5.2 grafikonon a haszn´ alt paraméterek értékei: p = 0.25 a találati valósz´ın˝ uség, Λ = 10 igény/m´ asodperc a k¨ uls˝o igények érkezési intenzitása, νpcs = νweb = 10 a jav´ıt´ asi intenzitás, azaz az átlagos 1 1 jav´ıtási id˝ok νpcs = νweb = 0.1, és δpcs = δweb = γpcs = γweb = 0.2 a Proxy Cache szerver és a Web szerver meghibásodásának intenzitása u ¨resjárati és foglalt ´ allapotokban. A grafikonon az igények teljes válaszidejét l´ athatjuk a bels˝ o érkezési intenzitás f¨ uggvényében blokkolt és nem blokkolt esetekben. Amint látható az átlagos válszid˝o a bels˝o érkezési intenzit´ as n¨ ovekedésével szintén növekszik, amint azt a 4. fejezetben l´ athattuk. Megfigyelhetj¨ uk, hogy amennyiben egy szerver blokkolt és nem blokkolt ´ allapot´ aban vizsgáljuk a válaszid˝oket, az érkezési intenzit´ as n¨ ovekedésével a két allapot közötti k¨ ulönbség csökken. • Az 5.3 valamint az 5.4 grafikonokon a Proxy Cache szerver meghibásodásának hat´ as´ at vizsg´ alhatjuk meg a teljes válaszid˝ore, foglalt és u ¨resjárati szerver ´ allapotban. A használt paraméterek: p = 0.25,λ = Λ = 10, νpcs = νweb = 10, és δpcs = δweb = γweb = 0.2 valamint a 5.4 grafikonon haszn´ alt paraméter értékek: p = 0.25,λ = 30, Λ = 10, νpcs = νweb = 10, és δweb = γpcs = γweb = 0.2. Amint megfigyelhetj¨ uk a válaszid˝ ok alacsonyabbak a blokkolt Proxy Cache szerverek esetében, mint a nem blokkolt esetekben. Megvizsgálva a 5.4 (az átlagos v´ alszid˝ o az u ¨resj´ arati Proxy szerver meghibásodásának f¨ uggvénye) grafikont azt tapasztaljuk, hogy abban az esetben amikor a Proxy Cache szerver ugyanabban az állapotban van és csak a Web szerver ´ allapota v´ altozik, pl. Proxy Cache szerver blokkolt és a Web szerver egyik esetben blokkolt a másikban nem (kék grafikonok), valamint a Proxy szerver nem blokkolt és a Web szerver egyik esetben blokkolt a m´ asikban pedig nem (piros grafikonok) a válaszid˝ot ´ abr´ azol´ o g¨ orbék p´ arhuzamosak. Ez abból adódik, hogy a Web szerver meghib´ asod´ asi és jav´ıt´ asi intenzitásai azonosak, csak a Web szerver blokkol´ asi tulajdons´ aga változik. Tovább vizsgálva a 5.4 grafikont azt tapasztaljuk, hogy amennyiben a Proxy Cache szerver blokkolt az igények teljes v´ alaszideje magasabb meghibásodási egy¨ uttható esetén konstans lesz, azaz f¨ uggetlen lesz az u ¨resjárati

45

5 A Web szerver és a Proxy Cache szerver meghibásodásának hatása meghib´ asod´ asi intenzit´ asra. • Az 5.5 grafikonon megvizsgálhatjuk a Proxy Cache szerver jav´ıtási intenzit´ as´ anak hat´ as´ at a v´ alaszid˝okre. A használt paraméterek: p = 0.25,λ = 40, Λ = 10, νweb = 10, és δpcs = δweb = γpcs = γweb = 2. Amint l´ athat´ o a jav´ıt´ asi intenzitás növelésével a válaszid˝ok csökkennek. Ebben az esetben a Web szerver meghibásodási és jav´ıtási intenzit´ asai v´ altozatlanok, ebb˝ol adódik, hogy amikor a Proxy Cache szerver blokkol´ asi algoritmusa megegyezik (blokkolt és nem blokkolt esetek) és csak a Web szerver blokkolási metódusa k¨ ulönböz˝o a v´ alaszid˝ oket ´ abr´ azol´ o g¨ orbék párhuzamosak. (piros illetve kék g¨ orbék). • Az 5.6 és 5.7 grafikonokon a Web szerver meghibásodási intenzit´ as´ anak hat´ as´ at figyelhetj¨ uk meg a válaszid˝okre foglalt valamint u ¨resj´ arati esetekben. A grafikonon használt paraméterek értékei: λ = Λ = 10,νpcs = νweb = 10, és δpcs = δweb = γpcs = 0.2 az 5.6 grafikonon, valamint λ = Λ = 10,νpcs = νweb = 10, és δpcs = γpcs = γweb = 0.2 az 5.7 grafikonon. Amint látható a teljes v´ alaszid˝ ok nagyobbak lesznek minden esetben (blokkolt vagy nem blokkolt esetek) amennyiben nagyobb meghibásodási arányt haszn´ alunk. Az el˝ oz˝ o esetekhez hasonlóan amikor a Web szerver blokkol´ asi met´ odusai megegyeznek és csak a Proxy Cache szerver blokkol´ asi m´ odszerei v´ altoznak a válaszid˝oket ábrázoló görbék párhuzamosak. (Web szerver blokkolt és a Proxy szerver blokkolási m´ odszere v´ altozik valamint a Web szerver nem blokkolt és a Proxy szerver blokkol´ asi m´ odszere változik). • Az 5.8 ´ abra azt mutatja meg, hogyan változik a teljes válaszid˝o a Web szerver jav´ıt´ asi intenzitásának növekedésével. A grafikonon haszn´ alt paraméterek: λ = Λ = 10, νpcs = 10, and δpcs = δweb = γpcs = γweb = 2. Amint látható, a válaszid˝ok az 5.5 grafikonhoz hasonl´ oan cs¨ okkennek a javitási intenzitás növelésével. Az 5.6 és 5.7 grafikonok esetében megmutatott párhuzamosság itt is megfigyelhet˝ o ugyanolyan blokkol´ asi módszer esetén. (A Web szerver blokkol´ asi m´ odszere megegyezik, csak a Proxy Cache szerver blokkolási m´ odszerét v´ altoztatjuk.)

46

5.2 Numerikus eredmények • Az 5.9 és az 5.10 grafikonok a v´ alaszid˝ot a Proxy Cache szerver puffer méretének f¨ uggvényeként ´ abr´ azoltuk. A használt paraméterek: λ = 30, Λ = 10,νpcs = νweb = 10, és δpcs = δweb = γpcs = γweb = 0.2 az 5.9 grafikonon, valamint λ = 40, Λ = 10,νpcs = νweb = 10, és δpcs = δweb = γpcs = γweb = 0.2 az 5.10 grafikonon. Mindkét grafikonon megfigyelhetj¨ uk, hogy amennyiben a Proxy Cache szerver blokkolt, u ´gy a v´ alaszid˝ ok egy bizonyos puffer méret után már nem változnak tov´ abb. Viszont amennyiben a Proxy Cache szerver nem blokkolt, akkor a v´ alaszid˝ ok a puffer méretének növelésével természetesen n¨ ovekszik. A kor´ abban megállap´ıtott párhuzamosság itt is megfigyelhet˝ o.

47


48

6 A Proxy Cache szerver GI/G/1 approxim´ aci´ os modellje A jelen fejezetben bemutatjuk a Proxy Cache szerver GI/G/1 approximációs modelljét, mely egy példa a Paraméter dekompoz´ıciós eljárás használatára (lásd [12]), ahol az egyes csomópontokat egymástól elk¨ ulön¨ ulten vizsgáljuk. A fejezetben szerepl˝ o eredmények a [7] cikkben lettek publikálva. Ebben a modellben az érkezési folyamat egy u ´gynevezett ”GI - General inter-arrival” folyamat, melyet az érkezési id˝oközök várható értékével és a relat´ıv szórásnégyzetével (c2 ) jellemz¨ unk, valamint a kiszolgálási id˝o bármilyen általános eloszl´ as´ u lehet.

6.1.

A GI/G/1 approxim´ aci´ o

Az approximáció haszn´ alat´ ahoz a k¨ ovetkez˝ o feltételeknek kell teljes¨ ulni¨ uk: • Az érkezési folyamat u ´gynevezett ”fel´ uj´ıtási” folyamat kell legyen, azaz az érkezési id˝ ok¨ oz¨ ok f¨ uggetlen, azonos eloszlás´ u valósz´ın˝ uségi változók. • A kiszolgál´ asi id˝ ok val´ osz´ın˝ uségi v´ altozója bármilyen általános eloszlás´ u lehet. • Adott az érkezési folyamat inetenzit´ asa λA , valamint az érkezási folyamat relat´ıv sz´ or´ asnégyzete (c2A ). • Adott a kiszolg´ al´ asi id˝ o v´ arhat´ o értéke τS , valamint a kiszolgálási id˝o relat´ıv sz´ or´ asnégyzete (c2S ).

49

6 A Proxy Cache szerver GI/G/1 approximációs modellje • Az azonnali visszacsatol´ ast, amikor egy sor távozó folyamata vissza van ir´ any´ıtva egyb˝ ol ugyanahhoz a sorhoz, k¨ ulön kell vizsgálni. Ez az aproxim´ aci´ o olyan algoritmusokat szolgáltat, melyekkel modellezhetj¨ uk az ´ altal´ anos h´ al´ ozati folyamatokat, mint például a forgalom egyes´ıtést, a sort´ ol val´ o t´ avoz´ ast, valamint a forgalom szétválását. Minden esetben, a részletes sz´ am´ıtások el˝ott a modellt módos´ıtanunk kell, hogy elimin´ alhassuk az azonnali visszacsatolásokat. Ezt a módos´ıtást az érintett sor kiszolg´ al´ asi idejének megváltoztatásával végezz¨ uk, melyet a kés˝obbiekben részletez¨ unk. A sz¨ ukséges kalkul´ aci´ ok eredményekép az aproximáció seg´ıtségével megkapjuk a sz¨ ukséges rendszerjellemz˝oket (átlagos sorhossz, átlagos várakozási id˝ o, stb.), mind a sorokra, mind pedig az egész hálózatra vonatkozóan. A következ˝ oekben bemutatjuk azon approximációs egyenleteket, melyek seg´ıtségével le´ırhat´ oak a kor´ abban eml´ıtett hálózati forgalomhoz tartozó folyamatok, mint péld´ aul az egyes´ıtés, szétválás, távozás, valamint bemutajuk az azonnali visszacsatol´ as törléséhez sz¨ ukséges paraméter változtatásokat. (l´ asd [12], [5]). 1) GI folyamatok egyes´ıtése: n darab f¨ uggetlen GI folyamat (mindegyiket rendre jellemez a λj és c2j , j = 1, . . . , n) egyes´ıtése amint egy következ˝o csomópontba lépnek, egy GI folyamattal közel´ıthe¨ unk, mely paraméterei: λA és c2A , az ´ atalgos érkezési intenzitás és az érkezési id˝oközök relat´ıv szórásnégyzete. Az ´ atlagos intenzitást és a relat´ıv szórásnégyzetet az alábbi egyenletek szolg´ altatj´ ak (lásd [12]):

λA =

n X

λj ,

(6.1)

j=1

és

c2A = $

n X λj 2 c + 1 − $, λA j j=1

50

(6.2)

6.1 A GI/G/1 approximáció ahol

$=

1 , 1 + 4(1 − ρ)2 (ν − 1)

(6.3)

1

(6.4)

ν=P n

j=1

λj λA

2

és ρ a csomópont kihaszn´ alts´ aga, azaz ρ = λA τS és τS a ksizolgálási id˝o várható értéke. 2) Egy sort´ ol t´ avoz´ o folyamat: Egy csom´ oponttól távozó folyamatot közel´ıthet¨ unk egy GI folyamattal, ahol λD jelenti az átlagos távozási inavoz´ o igények közötti id˝oközök relat´ıv tenzitást, valamint c2D jelenti a t´ szórásnégyzetét. Az egyens´ ulyi ´ allapot k¨ ovetkezményeként tudjuk, hogy az átlagos érkezési intenzit´ as megegyezik az átlagos távozási intenzitással, azaz λD = λA .

(6.5)

A távozási folyamat relat´ıv sz´ or´ asnégyzete pedig megkapható a következ˝o egyenlettel: c2D = ρ2 c2S + 1 − ρ2 c2A .

(6.6)

3) Egy GI folyamat véletlen oszt´ asa: Egy GI folyamatot, melyet a λ és c2 paraméterek jellemeznek n darab f¨ uggetlen folyamatra osztunk, rendre pi P valósz´ın˝ uséggel ( ni=1 pi = 1). Ekkor az i-edik folyamat paramétereit a következ˝oképpen sz´ am´ıthatjuk ki: λi = pi λ,

(6.7)

c2i = pi c2 + (1 − pi ).

(6.8)

51

6 A Proxy Cache szerver GI/G/1 approximációs modellje 4) Az azonnali visszacsatol´ as t¨ orlése: Ha egy csomóponttól távozó folyamatot azonnal visszair´ any´ıtunk ugyanahhoz a sorhoz (Qi ), akkor a Qi sorhoz érkez˝ o folyamat val´ oj´ aban a csomóponton k´ıv¨ ulr˝ol érkez˝o igények intenzitás´ anak (λi ), valamint a visszacsatolt folyamat intenzitásának (pii λi ) az összege. Az azonnali visszacsatol´ as megsz¨ untetése a sor átlagos kiszolgálási idejének valamint a relat´ıv sz´ or´ asnégyzetnek a megfelel˝o módos´ıtásával történik. Feltételezve, hogy a kiszolg´ al´ asi id˝o eloszlásának az eredeti paraméterei: τS,U - az ´ atlagos kiszolg´ al´ asi id˝ o, és c2S,U - a kiszolgálási id˝o relat´ıv szórásnégyzete, az azonnali visszacsatolás eliminálásával a kiszolgálási id˝o eloszlás´ anak m´ odosult paraméterei a következ˝ok: τS,M =

τS,U , 1 − pii

(6.9)

c2S,M = pii + (1 − pii )c2S,U ,

(6.10)

és Wq,M =

Wq,M . 1 − pii

(6.11)

´ 5) Atlagos v´ arakoz´ asi id˝ o: Ha a vizsg´ alt csom´ opont egy GI/G/1 -es sor akkor alkalmazhatjuk a Kramer és Langenbach-Belz approximációt (lásd [37]):

Wq =

τS · ρ(c2A + c2D )β , 2(1 − ρ)

(6.12)

ahol ( βW eb = .

52

exp 1,

2(1−ρ)(1−c2A )2 3ρ(c2A +c2D )

,

c2A < 1 c2A ≥ 1

6.2 A Proxy Cache szerver GI/G/1 modellje

6.1. ábra. Proxy Cache szerver módos´ıtott modellje

6.2.

A Proxy Cache szerver GI/G/1 modellje

Az eddig tanulmányozott Proxy Cache szerver modellt (lásd a 4. fejezetet) u ´gy szeretnénk által´ anos´ıtani, hogy a modellben szerepl˝o M/M/1-es sorok helyett GI/G/1-es sorokat haszn´ alunk. A k´ıvánt rendszerparamétereket a fentebb tárgyalt GI/G/1 -es approxim´ aci´ o seg´ıtségével fogjuk megkapni. Feltételezz¨ uk, hogy a bels˝ o igények a Proxy Cache szerverhez GI folyamat szerint érkeznek λ érkezési intenzit´ assal, és c2λ relat´ıv szórásnégyzettel. A Web szerverhez k´ıv˝ ulr˝ ol érkez˝ o igények szintén GI folyamat alapján érkeznek Λ és c2Λ paraméterekkel. A 6.1 ábra a módos´ıtott modell alapj´ an mutatja egy igény lehetséges u ´tját a felhasználótól kiindulva egészen a visszaérkezésig. A modellben szerepl˝o paraméterek listája a 4.3 t´ abl´ azatban l´ atható. A ”PCS LOOKUP” szemlélteti azt a sort melynél eld˝ol, hogy a keresett

53

6 A Proxy Cache szerver GI/G/1 approximációs modellje fájl megtal´ alhat´ o-e a Proxy Cache szerveren vagy nem. A ”PCS LOOKUP” sorhoz tartoz´ o kiszolg´ al´ asi id˝o bármilyen tetsz˝oleges eloszlás le2 het µLookup , cLookup paraméterekkel. Az ”Initialisation” sor kiszolgálási ideje az el˝ oz˝ oekhez hasonl´ oan szintén általános eloszlás´ u µInit és c2Init paraméterekkel. A Web szerver valamint a Proxy Cache Szerver kiszolgálási idejének eloszl´ as´ at a µW eb , c2W eb és µP CS , c2P CS paraméterek jellemzik ahol: µLookup =

µInit =

1 , Ixc

(6.13)

1 , IS

(6.14)

és µW eb =

1 YS +

BS RS

µP CS =

1 Yxc +

Bxc Rxc

,

(6.15)

,

(6.16)

ahol Ixc a Proxy Cache szerverhez tartozó u ´gynevezett ”keresési” id˝o (lásd a 4. fejezetet) valamint Is a Web szerverhez tartozó u ´gynevezett egyszeri inicializ´ al´ asi id˝ o (l´ asd a 3. fejezetet). A Bs ´ as Bxc paraméterek a Web szerver illetve a Proxy Cache szerver kimen˝ o puffer kapacit´ asa, az Ys és Yxc a statikus szerver id˝ok valamint az Rs és Rxc a dinamikus szerver ar´ any a Web szerver és Proxy Cache szerver esetén. Az eredeti modell m´ odos´ıt´ as´ anak az els˝o lépése a szervereknél esetlegesen el˝ ofordul´ o azonnali visszacsatolások törlése a sorok paramétereinek módos´ıt´ as´ aval. A 6.1-es ´ abra az eredeti 4.1-es ábra módos´ıtása, ahol a Proxy Cache szerver és a Web szerver visszacsatolásai törölve vannak. A visszacsatol´ asok t¨ orlése ut´ an a két szerver módos´ıtott paraméterei a (6.9), (6.10) alapj´ an:

54


µW eb,M = µW eb ∗ q,

(6.17)

c2W eb,M = (1 − q) + q ∗ c2W eb ,

(6.18)

µP CS,M = µP CS ∗ qxc ,

(6.19)

c2P CS,M = (1 − qxc ) + qxc ∗ c2P CS .

(6.20)

és

Az u ´j modellben 2 forgalom szét´ agaz´ asi pont (S1,S2), 2 darab forgalom egyes¨ ulési pont (M1,M2), valamint 4 darab k¨ ulönálló sor található (PCS Lookup, PCS Server, Initialization, Web server). Ezekben a pontokban a folyamatok paramétereit u ´jra kell kalkul´ alnunk. Az S1 pontban az igények két ir´ anyba ´ agaznak szét p és 1−p valósz´ın˝ uséggel. A ”PCS Lookup” sort elhagy´ o igények t´ avozási folyamatának (DLookup ) az u ´jrakalkulált paraméterei (t´ avoz´ asi intenzitás, távozóigények id˝oközeinek relat´ıv szórásnégyzete) a (6.5) és a (6.6) képletek alapján a következ˝oek: λD = λ,

(6.21)

c2DLookup = ρ2 ∗ c2Lookup + 1 − ρ2 ∗ c2λ ,

(6.22)

ahol ρ=

λ . µIxc

(6.23)

A 6.1 ábrán az egyenes vonallal (λ1 ) azokat az igényeket jelölt¨ uk melyek megtalálhat´ oak a Proxy Cache szerveren, azaz egyb˝ol tovább´ıthatóak a kliensnek. Szaggatott vonallal (λ2 ) ´ abrázoltuk azokat az igényeket,

55

6 A Proxy Cache szerver GI/G/1 approximációs modellje melyek nem szolg´ alhat´ ok ki a Proxy Cache szerverrel, azaz az igények tovább´ıt´ odnak a t´ avoli Web szerver felé. A két folyamathoz tartoz´ o paraméterek értékei a (6.7) és a (6.8) alapján: λ1 = p ∗ λD ,

(6.24)

c21 = p ∗ c2DLookup + (1 − p),

(6.25)

λ2 = (1 − p) ∗ λD ,

(6.26)

c22 = (1 − p) ∗ c2DLookup + p.

(6.27)

és

Az M1 pontban a bels˝ o igények egy része (λ2 ) egyes¨ ulnek a k¨ uls˝o igényekkel. Az ´ıgy kapott folyamat (λ3 ) paraméterei felhasználva a (6.1) valamint a (6.2) képleteket: λ3 = λ2 + Λ,

c23

=w∗

(6.28)

λ2 Λ ∗ c22 + ∗ c2Λ λ3 λ3

ahol w=

+ (1 − w),

1 , 4 ∗ (1 − ρ)2 ∗ (ν − 1)

ν=

1 λ2 λ3

2

és ρ=

+

Λ λ3

λ3 . µInit

2 ,

(6.29)

(6.30)

(6.31)

(6.32)

Az egyszeri inicialz´ al´ asi sort´ ol t´ avozó igények (λ3,DInit ) paraméterei: λ3,DInit = λ3 ,

56

(6.33)


c23,DInit = ρ2 ∗ c2Init + 1 − ρ2 ∗ c23 , ahol ρ=

λ3,DInit . µInit

(6.34)

(6.35)

Az egyszeri inicializ´ al´ as ut´ an az igények megérkeznek a Web szerverhez, ahonnan már kor´ abban t¨ or¨ olt¨ uk a visszacsatolást. A Web szervert elhagyó folyamat (λ3,DW eb ) paraméterei: λ3,DW eb = λ3 ,

(6.36)

c23,DW eb = ρ2 ∗ c2W eb,M + 1 − ρ2 ∗ c23,DInit ,

(6.37)

ahol ρ=

λ3 µW eb,M

.

(6.38)

Az S2 pontban a Web szervert elhagy´ o λ3,DW eb folyamat két irányba ágazik el. Az igények egyik része a k¨ uls˝ o igények, melyek λ2Λ+Λ valósz´ın˝ uséggel távoznak, valamint az igények m´ asik része a bels˝o igények (λ2,R ) melyek tovább´ıtódnak a Proxy Cache szerver felé. A λ2,R folyamat paraméterei: λ2,R = λ2 ,

(6.39)

és c22,R

λ2 λ2 2 = ∗c + 1− . λ2 + Λ 3,DW eb λ2 + Λ

(6.40)

Az M2 pontban a λ1 folyamat és a Web szervert˝ol visszatér˝o λ2,R folyamat egyes¨ ul. Az ´ıgy kapott λA folyamat paraméterei:

57

6 A Proxy Cache szerver GI/G/1 approximációs modellje

λA = λ1 + λ2,R = λ1 + λ2 = λ,

c2A

=w∗

λ1 λ2 ∗ c21 + ∗ c22,R λ λ

ahol w=

(6.41)

+ (1 − w),

(6.42)

1 , 4 ∗ (1 − ρ)2 ∗ (ν − 1)

ν=

1 λ1 λ

és ρ=

2

+

λ2 λ

(6.43)

2 ,

(6.44)

λ . µP CS,M

(6.45)

Így a teljes v´ alaszid˝ ot a (4.10) alapján a következ˝o egyenletek adják.

F Txc = TLookup + p ∗ TP CS + Nc F F + (1 − p) ∗ {TInit + TW eb + + TP CS + , Ns Nc

(6.46)

ahol a (6.12) alapj´ an kapjuk: 1 = µLookup ∗ ρLookup ∗ c2λ + c2Lookup ∗ β

TLookup = WLookup +

=

1 µLookup

2 ∗ (1 − ρlookup )

 2 2∗(1−ρLookup )∗(1−c2λ )   ,  exp − 3∗ρ 2 2 Lookup ∗(cλ +cLookup ) β=    1,

58

(6.47) +

1 µLookup

,

c2λ < 1 , c2λ ≥ 1


ρLookup =

λ µLookup

,

valamint

1

= µP CS,M ∗ ρpcs ∗ c2A + c2pcs,M ∗ β

TP CS = WP CS +

=

1 µP CS,M

2 ∗ (1 − ρpcs )

(6.48) +

1 µpcs,M

,

ahol  

2 2∗(1−ρpcs )∗(1−c2A ) exp − 3∗ρ ∗ c2 +c2 , pcs ( A β= pcs,M )  1,

ρpcs =

c2A < 1

,

c2A ≥ 1

λA . µpcs,M

Ismét felhasználva a (6.12) képletet kapjuk:

TInit = WInit + =

1 µInit

1

= µInit ∗ ρInit ∗ c23 + c2Init ∗ βInit 2 ∗ (1 − ρInit )

+

1 µInit

(6.49) ,

ahol

βInit =

 

exp −



1,

2∗(1−ρInit )∗(1−c23 )

2

3∗ρInit ∗(c23 +c2Init )

,

c23 < 1

,

c23 ≥ 1

59


ρInit =

λ3 , µInit

és

TW eb = WW eb +

=

1 µW eb,M

βW eb =

1

= µW eb,M 2 2 ∗ ρweb ∗ cDInit + cweb,M ∗ βweb 2 ∗ (1 − ρweb )

  

exp

2 ! 2∗(1−ρweb )∗ 1−c2D Init , − 3∗ρweb ∗ c2D +c2web,M

+

µweb,M

,

c2DInit < 1

Init

 

c2DInit

1,

ρweb =

6.3.

(6.50) 1

λ3 . µweb,M

,

≥1

(6.51)


A Numerikus eredményekhez az el˝oz˝o fejezetekben használt paramétereket vessz¨ uk alapul. Azaz a haszn´ alt szerver paraméterek a következ˝oek: Is = Ixc = 0.004 m´ asodperc, Bs = Bxc = 2000 bytes, Ys = Yxc = 0.000016 másodperc, Rs = Rxc = 1.25 Mbyte/s, Ns = 1544 Kbit/s, és Nc = 128 Kbit/s. Mint ahogyan a korábbi fejezetekben le´ırtuk a használt paraméterek a [28] eredmények alapján lettek kiválasztva. Az approxim´ aci´ os elj´ ar´ as valid´ al´ asa érdekében egy szimulációs programot kész´ıtett¨ unk. A program Microsoft Visual Basic 2005 -ben ´ıródott, .NET framework 2.0 alatt. A szimul´ aci´ ot egy T2300 Intel processzort (1.66 GHz) és 2 GB RAM mem´ ori´ at tartalmazó PC-n futtattuk. El˝oször az elkész´ıtett szimul´ aci´ os program valid´ al´ as´ at kellett elvégezz¨ uk.

60

6.3 Numerikus eredmények A validálási folyamathoz a szimul´ aci´ os program seg´ıtségével a válaszid˝oket exponenciális eloszl´ as´ u modell esetén sz´ am´ıtottuk ki, melyet már össze tudtunk hasonl´ıtani az analitikus eredményekkel, melyeket a (4.10) képlet alapján számolhatunk. A szimul´ aci´ os és analitikus eredmények exponenciális eloszlás estén a 6.1 t´ abl´ azatban találhatóak. Amint látható a válaszid˝ok nagyon k¨ ozel vannak egym´ ashoz, érték¨ uk az els˝o 4 tizedesjegyig megegyeznek. Az approximációs elj´ ar´ as valid´ al´ as´ ahoz a k¨ ovetkez˝o eloszlásokat használtuk: (Lásd [34]) • Abban az esetben ha a relat´ıv sz´ or´ asnégyzet 0 < c2X < 1 akkor egy Ek−1,k által´ anos´ıtott Erlang-eloszl´ ast használunk ami egy Ek−1 és egy Ek Erlang-eloszl´ as keveréke, melynek a s˝ ur˝ uségf¨ uggvénye:

f (t) = p ∗ µk−1 ∗

tk−2 tk−1 ∗ e−µt + (1 − p) ∗ µk ∗ ∗ e−µt (6.52) (k − 2)! (k − 1)!

ahol 0 ≤ p ≤ 1, és t ≥ 0. Ebben az esetben az Ek−1,k eloszl´ as p (ill. 1 − p) valósz´ın˝ uséggel k − 1 (ill. k) f¨ uggetlen µ paraméter˝ u exponenciális eloszlás összege. Ha p illetve µ értékeit az al´ abbi mennyiségek alapján választjuk p=

1 2 k−p 2 2 2 1/2 kc − k 1 + c − k c és µ = X X X 2 E(X) 1 + cX

akkor az Ek−1,k eloszl´ as v´ arhat´ o értéke E(X) és relat´ıv szórása cX , 1 valamint k1 ≤ c2X < k−1 . • Amennyiben cX > 1 egy H2(p1 ; p2 ; µ1 ; µ2 ) hyper-exponenciális eloszlást haszn´ alunk, melynek s˝ ur˝ uségf¨ uggvénye: f (t) = p1 ∗ µ1 ∗ e−µ1 t + p2 ∗ µ2 ∗ e−µ2 t

(6.53)

ahol 0 ≤ p1 , p2 ≤ 1, és t ≥ 0.

61

6 A Proxy Cache szerver GI/G/1 approximációs modellje Paraméterek Analitikus eredm. Szimuláció Approx. Eltérés λ = 20,Λ = 100 0,425793 0,425706 0,425793 0,000087 λ = 80,Λ = 100 0,430135 0,430136 0,430135 0,000001 6.1. t´ abl´ azat. Szimul´ aci´ o valid´ al´ asa Mivel a hyper-exponenci´ alis eloszlást az els˝o két momentuma nem hat´ arozza meg egyértelm˝ uen, a p1 p2 = µ1 µ2 kiegyens´ ulyozott v´ arhat´ oérték feltételt használjuk. (lásd [34]) Amennyiben a H2 eloszl´ as paramétereit az alábbi értékek alapján v´ alasztjuk s ! c2X − 1 1 , p2 = 1 − p1 , p1 = 1+ 2 c2X + 1 és µ1 =

2p1 2p2 , µ2 = . E(X) E(X)

akkor a H2 hyper-exponenciális eloszlás várható értéke E(X) és relat´ıv sz´ or´ asa cX . A numerikus eredmények egyszer˝ ubb átláthatósága végett a modellben szerepl˝ o minden sor esetében ugyanazt a relat´ıv szórásnégyzet értéket használtuk. A 6.2 t´ abl´ azatban l´ athat´ oak a k¨ ulönböz˝o paraméterekkel szám´ıtott szimuláci´ os és approxim´ aci´ os eredmények.

6.4.

Konkl´ uzi´ o

A disszert´ aci´ o jelen részében m´ odos´ıtottuk a 4. fejezetben bemutatott Proxy Cache szerver modellt u ´gy, hogy az exponenciális eloszlás´ u érkezési

62

6.4 Konkl´ uzió ´ Erkez´ esi intenzit´ as λ = 20 Λ = 100

λ = 80 Λ = 100

c2 0,1 0,8 1,2 1,8 0,1 0,8 1,2 1,8

Szimul´ aci´ o 0,423084 0,425127 0,423042 0,421744 0,423591 0,428624 0,425821 0,424049

Approximáció 0,423129 0,425189 0,426328 0,427979 0,423974 0,428725 0,431507 0,435869

Eltérés 0,000045 0,000062 0,003286 0,006235 0,000383 0,000101 0,005686 0,01182

6.2. t´ abl´ azat. Approxim´ aci´ os eredm´ enyek folyamatok helyett GI folyamatot haszn´ alunk, valamint az exponenciális kiszolgálási id˝ok helyett tetsz˝ oleges G eloszlást használunk. Hogy megkapjuk a teljes v´ alaszid˝ ot a QNA approximációs eljárást használtuk. A szimulációs és approxim´ aci´ os eredmények a 6.2 táblázatban láthatóak. Amennyiben c2 < 1 az approxim´ aci´ os elj´ ar´ assal és a szimulációs programmal kapott válaszid˝ ok nagyon k¨ ozeliek; legalább az els˝o 3-4 tizedesjegyig megegyeznek. Abban az esetben, amikor c2 > 1 a szimulációs és approximációs eljárással kapott v´ alaszid˝ ok csak az els˝o 2-3 tizedes jegyig egyeznek. Látható, hogy amikor a relat´ıv sz´ or´ asnégyzet 1, 2, a két eljárás közöti k¨ ulönbség 0, 005686, valamint ha a relat´ıv szórásnégyzet 1, 8, a válaszid˝ok ´ közötti k¨ ulönbség nagyobb (0, 01182). Eszrevehetj¨ uk, hogy nagyobb relat´ıv szórásnégyzetet haszn´ alva az approximáció pontossága csökken.

63


64

7 A heterog´ en forgalom hat´ asa a Proxy Cache szerverek hat´ ekonys´ ag´ ara Jelen fejezetben a 4. fejezetben megismertetett modellt szeretnénk általános´ıtani u ´gy, hogy a felhaszn´ al´ okt´ ol érkez˝o igényeket két csoportba soroljuk a lekért inform´ aci´ ok, f´ ajlok mérete alapján.

7.1.

T¨ obb ig´ eny-oszt´ alyt tartalmaz´ o sorban´ all´ asi h´ al´ ozatok

Tekints¨ unk egy nyitott Jackson-h´ al´ ozatot, melyben K darab sor található. Tételezz¨ uk fel, hogy a rendszerben lév˝ o és oda érkez˝o igények C k¨ ulönböz˝o osztályba sorolhat´ oak. Minden c oszt´ aly nyitott λc össz érkezési intenzitással. Így a rendszerhez tartoz´ o érkezési intenzitást a λ = (λ1 , λ2 , · · · , λC ) vektor ´ırja le. A k-adik sorhoz a rendszeren k´ıv¨ ulr˝ol érkez˝o, bármely osztályhoz tartoz´ o folyamat legyen Poisson-folyamat Λc,k paraméterrel. A Λc,k = 0 intenzit´ as azt jelenti, hogy a k-adik sorhoz nem érkezik k´ıv¨ ulr˝ol c osztályhoz tartoz´ o igény. Mivel egy nyitott rendszerr˝ol beszél¨ unk, feltételezz¨ uk, hogy legal´ abb egy Λc,j > 0. Az i-edik csomópont ´ altal kiszolg´ alt c osztályhoz tartozó igény a j-edik csomóponthoz tov´ abb´ıt´ odik pc,ij val´ osz´ın˝ uséggel, vagy elhagyja a rendszert

65

7 A heterogén forgalom hat´ asa a Proxy Cache szerverek hatékonyságára

 1 −

K X

 pc,ij 

j=1

valósz´ın˝ uséggel. A j-edik sor kiszolg´ al´ asi ideje µj paraméter˝ u exponenciális eloszlás, valamint a sorhoz érkez˝ o c oszt´ alyhoz tartozó folyamat teljes érkezési intenzitása: K X λc,j = Λc,j + λc,i pc,ij (7.1) i=1

minden j = 1, 2, · · · , K esetén. Rendszerparaméterek: [27] • A c-edik oszt´ aly ´ atereszt˝ oképessége a k-adik csom´ opontn´ al: Xc,k = λc Vc,k ,

(7.2)

ahol Vc,k a c oszt´ alyhoz és k-adik sorhoz tartozó látogatások száma, azaz λc,k Vc,k = . (7.3) λc • A c-edik oszt´ aly teljes ´ atereszt˝ oképessége: Xc = λc .

(7.4)

• A c oszt´ aly kihaszn´ alts´ aga a k-adik csom´ opontn´ al: Uc,k = Xc,k Sc,k = λc Dc,k ,

(7.5)

ahol Sc,k a c oszt´ alyhoz tartozó átlagos kiszolgálási id˝o a k-adik sorn´ al, valamint Dc,k = Vc,k Sc,k . (7.6)

66

7.1 T¨ obb igény-oszt´ alyt tartalmazó sorbanállási hálózatok • A kihaszn´ alts´ ag a k-adik csom´ opontn´ al: Uk =

C X

Uc,k .

(7.7)

c=1

• A c oszt´ alyhoz tartoz´ o´ atlagos igénysz´ am a k-adik csom´ opontn´ al: Nc,k =

1−

Uc,k PC

j=1 Uj,k

.

(7.8)

• A c oszt´ alyhoz tartoz´ o´ atlagos v´ alaszid˝ o a k-adik csom´ opontn´ al:

Tc,k =

1−

Dc,k PC

j=1 Uj,k

.

(7.9)

• A c oszt´ alyhoz tartoz´ o´ atlagos igény sz´ am a rendszerben: Nc =

K X

Nc,j .

(7.10)

j=1

• A c oszt´ alyhoz tartoz´ o´ atlagos v´ alaszid˝ o a rendszerben: Tc =

K X

Tc,j .

(7.11)

j=1

• Egy tetsz˝ oleges igény ´ atlagos v´ alaszideje a rendszerben: T =

C X Tc Xc c=1

X

,

(7.12)

ahol X=

C X

Xc .

(7.13)

c=1

67


7.2.

M´ odos´ıtott Proxy Cache szerver modell

A következ˝ o részben részletesen bemutatjuk a 4. fejezetben ismertetett modellben végrehajtott m´ odos´ıt´ asokat, melyek seg´ıtségével vizsgálni tudjuk a heterogén f´ ajlok hat´ as´ at. A kliensek ´ altal keresett f´ ajlokat két osztályba soroljuk a méret¨ uk alapján. Amennyiben a f´ ajl mérete az ´ atlagosnál nagyobb az a osztályba soroljuk, m´ıg ellenkez˝ o esetben amikor a f´ ajl mérete kicsi ”normál” fájlról beszél¨ unk és a b oszt´ alyba soroljuk. Mindkét osztályba tartozó igény esetén el˝oször megvizsg´ aljuk, hogy a f´ ajl megtalálható-e a Proxy Cache szerveren vagy sem. Ezt a tal´ alati val´ osz´ın˝ uséget pa illetve pb -vel jelölj¨ uk az a illetve a b osztályhoz tartoz´ o f´ ajlok esetén. Amennyiben a keresett fájl megtalálható a Proxy Cache szerveren, akkor mindkét osztály esetén a fájl egy másolata azonnal tov´ abb´ıt´ odik a klienshez. Ellenkez˝o esetben, amikor is a fájl nem találhat´ o meg a Proxy Cache szerveren az igény tovább´ıtódik a távoli Web szerverhez f¨ uggetlen¨ ul az oszt´ aly´ atól. Miután az igényelt fájl visszaérkezik a Proxy Cache szerverhez egy m´ asolat tovább´ıtódik a klienshez. Az 7.1 ´ abra mutatja egy bels˝ o fájl lehetséges u ´tját az igény indulásától egészen a f´ ajl klienshez val´ o megérkezéséig. Az ábrán az a illetve b index jelöli, hogy a keresett f´ ajl az a vagy a b osztályhoz tartozik. Az ábrán és a fejezetben haszn´ alt jel¨ olések megtalálhatóak a 7.4 táblázatban. Feltételezz¨ uk, hogy a bels˝ o a osztályhoz tartozó igények a Proxy Cache szerverhez λa , m´ıg a b oszt´ alyhoz tartozó igények λb paraméter˝ u Poissonfolyamat szerint érkeznek, valamint a Web szerverhez k´ıv¨ ulr˝ol érkez˝o igények Λa illetve Λb paraméter˝ u Poisson-folyamat alapján érkeznek az a illetve b oszt´ alyhoz tartoz´ o igények esetén. Az egyenes vonal (λa,1 ill. λb,1 ) reprezentálja azt az esetet amikor a keresett fájl megtal´ alhat´ o a Proxy Cache szerveren. Szaggatott vonallal rajzolva jel¨ olt¨ uk (λa,2 ill. λb,2 ) azon igények u ´tját, melyek nem találhatóak meg a Proxy Cache szerveren, ´ıgy ezek az igények tovább´ıtódnak a távoli Web szerverhez. A λa,1 és λa,2 valamint λb,1 és λb,2 intenzitások értékei: λa,1 = pa ∗ λa és λb,1 = pb ∗ λb ,

68

(7.14)

7.2 M´ odos´ıtott Proxy Cache szerver modell

7.1. ábra. Proxy Cache szerver heterogén forgalmi modellje λa,2 = (1 − pa ) ∗ λa és λb,2 = (1 − pb ) ∗ λb .

(7.15)

A Web szerverhez érkez˝ o igények teljes intenzitása a Web szerver felé tovább´ıtott bels˝o igények illetve a k¨ uls˝ o igények intenzitásának az összege, azaz

λa,3 = Λa + λa,2 és λb,3 = Λb + λb,2 .

(7.16)

A 4. fejezetben t´ argyaltak alapj´ an a Web szerverhez érkez˝o igényeknek át kell esni¨ uk egy egyszeri inicializ´ al´ asi folyamaton, melyet a 7.1 ábrán az ”Inicializálás” csom´ opont szemléltet. Az egyszeri inicializáláshoz sz¨ ukséges id˝o mindkét oszt´ alyhoz tartoz´ o f´ ajlok esetén: 1 1 Is

− (λa,3 + λb,3 )

.

(7.17)

69

7 A heterogén forgalom hat´ asa a Proxy Cache szerverek hatékonyságára A Web szerver valamint a Proxy Cache szerver karakterisztikáját meghatároz´ o paraméterek Bs , Ys , Rs valamint Bxc , Yxc , Rxc rendre a szerver kimen˝ o puffere, a statikus szerver id˝o valamint a dinamikus szerver arány (lásd a 3. fejezetet), alapj´ an a Web szerver és a Proxy Cache szerver kiszolg´ al´ asi intenzit´ asa

µW eb =

1 YS +

BS RS

µP CS =

1 Yxc +

Bxc Rxc

,

(7.18)

.

(7.19)

Ha a keresett f´ ajl nagyobb mint a Web szerver kimen˝o puffere, akkor egy visszacsatol´ asi ciklus kezd˝ odik, mely addig tart m´ıg a teljes fájl kiszolgál´ asa be nem fejez˝ odik. Legyen qa illetve qb annak a valósz´ın˝ usége, hogy keresett a illetve b oszt´ alyhoz tartozó fájlt egyb˝ol siker¨ ul tovább´ıtani, ahol

illetve

Bs qa = min 1, Fa

(7.20)

Bs . qb = min 1, Fb

(7.21)

Teljesen hasonl´ oan modellezhet˝ o a Proxy Cache szerver is, ahol a távozó folyamat visszacsatol´ as´ anak a val´ osz´ın˝ usége 1−qa,xc illetve 1−qb,xc , ahol

qa,xc

Bxc = min 1, Fa

az a oszt´ alyhoz tartoz´ o f´ ajl esetén, illetve Bxc qb,xc = min 1, Fb a b oszt´ alyhoz tartoz´ o f´ ajl esetén.

70

(7.22)

(7.23)

7.2 M´ odos´ıtott Proxy Cache szerver modell A bels˝o a osztályhoz tartoz´ o igények v´ alaszidejét Taxc -vel valamint a bels˝o b osztályhoz tartoz´ o igények v´ alaszidejét Tbxc -vel jelölj¨ uk, melyeket a következ˝o képletek hat´ aroznak meg: 1 − (λ a + λb ) Ixc   Bxc 1   ∗ (Y + ) xc F qa,xc Rxc a + pa ∗ +  1 − Pb λj (Yxc + Bxc ) Nc  j=a qj Rxc  Bs 1  1 qa ∗ (Ys + Rs ) + (1 − pa ) ∗ 1 +  I − (λa,3 + λb,3 ) 1 − Pb λj,3 (Ys + s j=a qj  Bxc 1 Fa  qa,xc ∗ (Yxc + Rxc ) + + , Pb λj 1− (Yxc + Bxc ) Nc 

Taxc =

1

j=a qj,xc

Bs Rs )

+

Fa Ns

Rxc

(7.24) és 1 Ixc − (λa + λb )   Bxc 1  Fb  qb,xc ∗ (Yxc + Rxc ) + + pb ∗ P λb Bxc 1 − b Nc  j=a qb,xc (Yxc + Rxc )  Bs 1  1 qb ∗ (Ys + Rs ) + (1 − pb ) ∗ 1 +  I − (λa,3 + λb,3 ) 1 − Pb λj,3 (Ys + s j=a qj  Bxc 1 Fb  qb,xc ∗ (Yxc + Rxc ) + + . Pb λb 1− (Yxc + Bxc ) Nc 

Tbxc =

1

j=a qb,xc

Bs Rs )

+

Fb Ns

Rxc

(7.25) Így a teljes válaszid˝ o: Txc =

λa λb ∗ Taxc + ∗ Tbxc . λa + λb λa + λb

(7.26)

71


A Taxc az a oszt´ alyhoz tartoz´ o fájlok esetében egy bels˝o igény átlagos válaszideje. Ennek a kisz´ am´ıt´ as´ ahoz a hálózati modell¨ unket három részhálózatra bontjuk. Ennek megfelel˝ oen a Taxc válaszid˝o három részb˝ol tev˝odik össze. Az els˝ o rész annak az id˝otartama, m´ıg eld˝ol, hogy a keresett a osztály´ u f´ ajl megtal´ alhat´ o-e a Proxy Cache szerveren vagy sem. Ez a (7.9) képletb˝ ol ad´ odik, ahol Ixc az ´ atlagos kiszolgálási id˝o. (Lásd 4. fejezetet.) A képlet m´ asodik tagja annak a válaszideje, amikor a keresett fájl megtalálhat´ o a Proxy Cache szerveren, melynek sebessége, azaz kiszolgálási xc intenzit´ asa a (3.5) alapj´ an Yxc + B osz´ın˝ usége Rxc . Ennek az esetnek a val´ pa . A m´ asodik tag szintén két részb˝ol tev˝odik össze. Az els˝o a (7.9) képlet alapján a Proxy Cache szervernél eltöltött id˝o, ahol a szerverhez érkez˝o a 0 λa osztály´ u f´ ajlok érkezési intenzit´ asa λa = qa,xc . A képletrész második tagja, pedig a kliens h´ al´ ozaton val´ o´ athaladási id˝o, mely a 3. fejezetben le´ırtak Fa alapján N . A képlet harmadik tagja azt az esetet ´ırja le, amikor a fájl c nem tal´ alhat´ o meg a Proxy Cache szerveren, ezért az igény tovább´ıtódik a távoli Web szerverhez. Ennek az esetnek a valósz´ın˝ usége 1 − pa . A képlet ezen része tov´ abbi ¨ ot tagból áll. Az els˝o a (3.2) és (7.9) alapján az u ´gynevezett egyszeri inicializ´ al´ asi id˝o. A második tag az igény Web szervernél elt¨ olt¨ ott ideje, ahol a Web szerverhez érkez˝o igények intenzitása 0 λ λa,3 = qa,3 . A harmadik és az ¨ ot¨ odik tag a fájlnak a szerver illetve kliens a hálózaton val´ o´ atjut´ ashoz sz¨ ukséges ”utazási” id˝o. A negyedik tag a Proxy Cache szerverhez visszaérkez˝ o igény kliens felé tovább´ıtásának az ideje.

A (7.25) képlet egy b oszt´ alyhoz tartozó bels˝o igény válaszidejét jelöli. Amenynyiben nem haszn´ alunk Proxy Cache szervert, akkor a keresett válaszid˝ ok a k¨ ovetkez˝ oképpen alakulnak:

Ta =

1 Is

1 − ((λa + Λa ) + (λb + Λb ))

+ 1−

72

Bs 1 qa ∗ (Ys + Rs ) Pb (λj +Λj ) (Ys j=a qj

+

Bs Rs )

+

Fa Fa + , Ns Nc

(7.27)

7.2 M´ odos´ıtott Proxy Cache szerver modell és Tb =

1 Is

1 − ((λa + Λa ) + (λb + Λb ))

+ 1−

Bs 1 qb ∗ (Ys + Rs ) Pb (λj +Λj ) (Ys j=a qj

Fb Fb + . + Bs + Rs ) Ns Nc

(7.28)

Így egy bels˝o igény v´ alaszideje Proxy Cache szerver nélk¨ ul: T =

λa λb ∗ Ta + ∗ Tb . λa + λb λa + λb

(7.29)

Megvizsgálva a (7.24)-(7.29) képleteket l´ atható, hogy azokban az esetekben amikor valamelyik nevez˝ o null´ ahoz k¨ ozel´ıt a válaszid˝o a végtelenhez tart. Legyen λb /λa = Λb /Λa = m a b illetve a osztályhoz tartozó igények érkezési intenzitás´ anak a h´ anyadosa. Így a válaszid˝o a végtelenhez közel´ıt, amennyiben a lenti egyenletek k¨ oz¨ ul az egyik teljes¨ ul. λ =

1 Ixc ,

λa =

qa,xc qb,xc Rxc (qb,xc +mqa,xc )(Yxc Rxc +Bxc ) ,

λb =

mqa,xc qb,xc Rxc (qb,xc +mqa,xc )(Yxc Rxc +Bxc ) ,

λa,3 + λb,3 =

1 Is ,

λa,3 =

qa qb Rs (qb +mqa )(Ys Rs +Bs ) ,

λb,3 =

mqa qb Rs (qb +mqa )(Ys Rs +Bs ) ,

λ+Λ =

1 Is ,

λa + Λa =

qa qb Rs (qb +mqa )(Ys Rs +Bs ) ,

λb + Λb =

mqa qb Rs (qb +mqa )(Ys Rs +Bs )

73


7.3.


A következ˝ oekben vizsg´ alt numerikus eredményekhez a használt szerver paraméterek a kor´ abbi fejezetekben használtakkal megegyeznek. A szám´ıtásokhoz a Web és Proxy Cache szerver paraméterek értékei [28] alapján: Is = Ixc = 0.004 m´ asodperc, Bs = Bxc = 2000 byte, Ys = Yxc = 0.000016 m´ asodperc, Rs = Rxc = 1.25 Mbyte/másodperc, Ns = 1544 Kbit/m´ asodperc, valamint Nc = 128 Kbit/másodperc. Az a illetve b osztályhoz tartoz´ o f´ ajlok méretét [28] alapján választottuk: Fa = 7000 byte, valamint Fb = 1000 byte. A fejezetben található grafikonokon pontozott vonallal ´ abr´ azoltuk a Proxy Cache szervert tartalmazó esetet, valamint egyenes vonallal a Proxy Cache szervert nem tartalmazó esetet.

7.3.1.

A bels˝ o ig´ enyek ´ erkez´ esi intenzit´ as´ anak hat´ asa a v´ alaszid˝ ore

A 7.2 grafikonon a v´ alaszid˝ ot a bels˝o igények érkezési intenzitásának f¨ uggvényeként ´ abr´ azoltuk. Ebben az esetben az a osztály´ u fájlok aránya az összes igény k¨ oz¨ ott 10 %, a k¨ uls˝o igények érkezési intenzitása 100 kérés/m´ asodperc, a Proxy Cache szerveren a találati valósz´ın˝ uségek rendre pa = pb = 0.25. A két oszt´ alyhoz tartozó fájl méretek pedig Fa = 7000 byte valamint Fb = 1000 byte. Amikor λ kisebb 75 kérés/másodpercnél, a v´ alaszid˝ o Proxy Cache szerver használatával nagyobb mint Proxy használata nélk¨ ul. Azaz ebben az esetben igen magas λ > 75 kell legyen a bels˝ o igények érkezési intenzitása, hogy megérje a Proxy Cache szerver u ¨zemeltetése. A 7.3 grafikonon ugyanazokat a rendszer paramétereket használtuk, csak az a oszt´ alyhoz tartozó igények arányát növelt¨ uk meg 20%-ra. Mint ahogyan l´ athat´ o, ebben az esetben a válaszid˝ok már λ > 65 igény/m´ asodperc esetén alacsonyabbak Proxy Cache szerver használatával. A 7.4 grafikonon azt az esetet l´ atjuk, amikor az a osztály´ u fájlok esetében a találati val´ osz´ın˝ uséget n¨ ovelj¨ uk pa = 0.4-re. A grafikonon használt többi paraméter értékei: az a oszt´ aly aránya = 20%, a k¨ uls˝o érkezési intenzitás Λ = 100 igény/m´ asodperc, a használt fájl méretek Fa = 7000 byte, Fb = 1000 byte, valamint a bels˝o igények esetén a találati valósz´ın˝ uség pa = 0.4 és pb = 0.25. A grafikonon látható, hogy ilyen magas találati valósz´ın˝ uség esetén a v´ alaszid˝ ok minden bels˝o igény érkezési intenzitás

74


7.2. ábra. 10% a oszt´ aly, Λ = 100, pa = pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

mellett alacsonyabbak Proxy Cache szerver használatával. Amennyiben csak az a osztályhoz tartoz´ o f´ ajlok tal´ alati valósz´ın˝ uségét csökkentj¨ uk, természetesen a Proxy Cache szerver hatékonysága drasztikusan romlik. Ezt láthatjuk a 7.5 grafikonon ahol a használt paraméterek megegyeznek a 7.4 grafikonon haszn´ alt értékekkel, kivéve az a osztály´ u fájlok találati valósz´ın˝ uségét, ami pa = 0.15. A grafikonok elemzésével látható, hogy a Proxy Cache szerver hatékonys´ aga alacsonyabb találati valósz´ın˝ uség esetén, csak magas bels˝ o érkezési intenzit´ as mellett jár alacsonyabb válaszid˝okkel. Viszont extrém magas tal´ alati valósz´ın˝ uség használatával (pa = 0.4) a Proxy Cache szerver haszn´ alata minden esetben alacsonyabb válaszid˝oket eredményez.

7.3.2.

A k¨ uls˝ o ig´ enyek ´ erkez´ esi intenzit´ as´ anak hat´ asa a v´ alaszid˝ ore

A következ˝o grafikonok seg´ıtségével a k¨ uls˝ o igények hatását fogjuk megvizsgálni. A 7.6 grafikonon haszn´ alt paraméterek: az a osztály aránya = 30%, a bels˝o igények érkezési intenzit´ asa λ = 10 igény/másodperc, a

75


7.3. ábra. 20% a oszt´ aly, Λ = 100, pa = pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

7.4. ábra. 20% a oszt´ aly, Λ = 100, pa = 0.4, pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

76


7.5. ábra. 20% a oszt´ aly, Λ = 100, pa = 0.15, pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

használt fájl méretek Fa = 7000 byte, Fb = 1000 byte, valamint a Proxy Cache szerveren a tal´ alati val´ osz´ın˝ uségek rendre pa = pb = 0.25. Amint látható, ha a k¨ uls˝ o igények érkezési intenzitása Λ > 125 igény/másodperc alacsony bels˝o érkezési intenzit´ as (λ = 10) és viszonylag alacsony találati valósz´ın˝ uség (pa = pb = 0.25) mellett is alacsonyabb válaszid˝oket kapunk Proxy Cache szerver haszn´ alat´ aval. A 7.7 grafikonon a használt paraméterek megegyeznek a 7.6 grafikon paramétereivel, csak a bels˝o igények érkezési intenzitás´ at n¨ ovelt¨ uk λ = 50-re. Amint várható volt ebben az esetben már alacsonyabb k¨ uls˝ o érkezési intenzitás mellett is alacsonyabb válaszid˝oket kapunk Proxy Cache szerver használatával (Λ > 105). Megvizsgálva a 7.6 - 7.7 grafikonokat ´ altal´ anosságban elmondhatjuk, hogy a k¨ uls˝o igények érkezési intenzit´ as´ anak n¨ ovelésével a válaszid˝ok n˝onek f¨ uggetlen¨ ul a Proxy Cache szerver jelenlétét˝ ol. Amennyiben a k¨ uls˝o igények intenzitása elég nagy, viszonylag kis bels˝ o érkezési intenzitás és találati valósz´ın˝ uség esetén is alacsonyabb v´ alaszid˝oket kaphatunk Proxy Cache szerver használat´ aval.

77


7.6. ábra. 30% a oszt´ aly, λ = 10, pa = pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

7.7. ábra. 30% a oszt´ aly, λ = 50, pa = pb = 0.25, Fa = 7000 bytes, Fb = 1000 bytes

78


7.3.3.

A f´ ajlm´ eret hat´ asa a v´ alaszid˝ ore

A 7.8-7.9 grafikonokon a teljes v´ alaszid˝ ot az a osztályhoz tartozó fájl méretének f¨ uggvényeként, m´ıg a 7.10 grafikonon a b osztályhoz tartozó fájl méretének f¨ uggvényeként ´ abr´ azoljuk. A 7.8 grafikonon a használt paraméterek értékei: az a oszt´ aly ar´ anya = 40%, a bels˝o igények érkezési intenzitása λ = 50 igény/m´ asodperc, a k¨ uls˝o igények érkezési intenzitása Λ = 100 igény/m´ asodperc, a haszn´ alt b osztályhoz tartozó fájlok mérete Fb = 1000 byte, valamint a Proxy Cache szerveren a találati valósz´ın˝ uségek rendre pa = pb = 0.25. Amint a grafikonon látható, az a osztály´ u fájlméret növelésével a válaszid˝ ok mind Proxy Cache szerver használatával, mind nélk¨ ule növekednek. Az ´ abr´ azolt két g¨ orbe csak Fa > 15000 byte esetén távolodik el egym´ ast´ ol. A részletesebb vizsgálat érdekében a kapott pontos válaszid˝oket a 7.1 illetve a 7.2 t´ abl´ azatokban láthatjuk, ahol az a osztály aránya rendre 20 illetve 40 sz´ azalék. A 7.1 táblázatban megfigyelhetj¨ uk, hogy kisebb a oszt´ aly´ u f´ ajlméret esetén a Proxy Cache szerver használata nagyobb v´ alaszid˝ oket eredményez. De amint a fájl mérete eléri a 12000 byte-ot a v´ alaszid˝ ok alacsonyabbak lesznek Proxy Cache szerver használatával. A 7.2 t´ abl´ azatban a teljes válaszid˝oket láthatjuk amikor az a osztály ar´ anya 40%. Megfigyelhetj¨ uk, hogy magasabb a osztály arány mellett a v´ alaszid˝ ok szintén magasabbak, viszont a Proxy Cache szerver használat´ anak az el˝ onye m´ ar kisebb fájl méretnél megmutatkozik (Fa = 6000 byte). A 7.9 grafikonon az alap paraméterek v´ altozatlanok, egyed¨ ul az a osztály arányát növelt¨ uk meg 70%-ra. Megfigyelhetj¨ uk, hogy a grafikonon szerepl˝o két görbe közötti eltérés sz´ amottev˝ oen n˝ o a fájl méret növelésével, azaz magas a osztály´ u ar´ any és nagy f´ ajl méret használatával a Proxy Cache szerver használata kifizet˝ od˝ o. A 7.10 grafikonon a teljes válaszid˝ot a b osztályhoz tartoz´ o f´ ajl méretének f¨ uggvényeként ábrázoljuk. A használt paraméterek: az a oszt´ aly ar´ anya = 40%, a bels˝o igények érkezési intenzitása λ = 50 igény/m´ asodperc, a k¨ uls˝o igények érkezési intenzitása Λ = 100 igény/m´ asodperc, a haszn´ alt a osztály´ u fájl mérete Fa = 7000 byte valamint a Proxy Cache szerveren a találati valósz´ın˝ uségek rendre pa = 0.25 illetve pb = 0.35. Amint látható, Proxy Cache szerver haszn´ alatával a használt paraméterek

79


Fájl méret(a oszt´ aly) Fa = 2000 Fa = 4000 Fa = 6000 Fa = 8000 Fa = 10000 Fa = 12000 Fa = 14000 Fa = 16000 Fa = 18000

Txc 0.09446809706 0.1217843586 0.1491608228 0.1766073005 0.2041361569 0.2317632395 0.2595092442 0.2874017905 0.3154786670

T 0.09317433644 0.1207717535 0.1484324701 0.1761686716 0.2039958857 0.2319342123 0.2600101405 0.2882593062 0.3167308131

Eltérés 0.00129376062 0.0010126051 0.0007283527 0.0004386289 0.0001402712 -0.0001709728 -0.0005008963 -0.0008575157 -0.0012521461

7.1. tábl´ azat. F´ ajlm´ eret hat´ asa a v´ alaszid˝ ore, az a oszt´ aly ar´ anya 20%

Fájl méret(a oszt´ aly) Fa = 2000 Fa = 4000 Fa = 6000 Fa = 8000 Fa = 10000 Fa = 12000 Fa = 14000 Fa = 16000 Fa = 18000

Txc 0.1077452991 0.1624380248 0.2174133590 0.2727864463 0.3287558693 0.3856999610 0.4444483664 0.5072639578 0.5833834923

T 0.1067106059 0.1619687395 0.2175321551 0.2735464100 0.3302670825 0.3881879423 0.4484027240 0.5139139582 0.5970200201

Eltérés 0.0010346932 0.0004692853 -0.0001187961 -0.0007599637 -0.0015112132 -0.0024879813 -0.0039543576 -0.0066500004 -0.0136365278

7.2. tábl´ azat. F´ ajlm´ eret hat´ asa a v´ alaszid˝ ore, az a oszt´ aly ar´ anya 40%

80

7.3 Numerikus eredmények Az a osztály aránya 10 20 30 40 50 60 70 80 90

Txc 0.1219838832 0.1628746062 0.2038840246 0.2450404415 0.2863831749 0.3279687079 0.3698815197 0.4122543652 0.4553092755

T 0.1209124357 0.1622902553 0.2037976778 0.2454704817 0.2873589491 0.3295360446 0.3721118312 0.4152604812 0.4592749103

Eltérés 0.0010714475 0.0005843509 0.0000863468 -0.0004300402 -0.0009757742 -0.0015673367 -0.0022303115 -0.0030061160 -0.0039656348

7.3. táblázat. Az a oszt´ aly ar´ any´ anak hat´ asa a v´ alaszid˝ ore mellett a válaszid˝ ok végig kisebbek mint Proxy Cache szerver használata nélk¨ ul. Megfigyelhetj¨ uk, hogy a ”norm´ al” - azaz b osztály´ u fájl mérete 1000-2000 byte-os intervallumban lényegesen nem befolyásolja a Txc − T k¨ ulönbséget. A 7.3 táblázatban az a oszt´ alyhoz tartoz´ o fájlok arányának hatását láthatjuk a válaszid˝ ore. A haszn´ alt paraméterek: a bels˝o igények érkezési intenzitása λ = 50 igény/m´ asodperc, a k¨ uls˝o igények érkezési intenzitása Λ = 100 igény/m´ asodperc, a haszn´ alt a illetve b osztály´ u fájl méretek Fa = 7000 byte illetve Fb = 1000 byte valamint a Proxy Cache szerveren a találati valósz´ın˝ uségek rendre pa = 0.25 illetve pb = 0.25. Láthatjuk, hogy az a osztályhoz tartoz´ o tartalom ar´ any´ anak növelésével a válaszid˝ok n˝onek f¨ uggetlen¨ ul attól, hogy install´ altunk-e Proxy Cache szervert vagy sem. Valamint megfigyelhetj¨ uk, hogy az a oszt´ alyhoz tartozó fájlok arányának növelésével a k¨ ul¨ onbség a két v´ alaszid˝ o között (Txc − T ) egyre kisebb és 40% fölötti a oszt´ aly´ u tartalom esetén a használt paraméter értékek mellett, Proxy Cache szerver haszn´ alat´ aval már alacsonyabb válaszid˝oket kapunk, mint Proxy Cache szerver haszn´ alata nélk¨ ul.

81


7.8. ábra. 40% a oszt´ aly, λ = 50, Λ = 100, pa = 0.25, pb = 0.25, Fb = 1000 bytes

7.9. ábra. 70% a oszt´ aly, λ = 50, Λ = 100, pa = 0.25, pb = 0.25, Fb = 1000 bytes

82


7.10. ábra. 40% a oszt´ aly, λ = 50, Λ = 100, pa = 0.25, pb = 0.35, Fa = 7000 bytes

λa : λb : Λa : Λb : Fa : Fb : pa : pb : Bxc : Ixc : Yxc : Rxc : Nc : Bs : Is : Ys : Rs : Ns :

7.4. táblázat. Heterog´ en forgalomi modell param´ eterei bels˝o a oszt´ aly´ u igények érkezési intenzitása bels˝o b oszt´ aly´ u igények érkezési intenzitása k¨ uls˝o a oszt´ aly´ u igények érkezési intenzitása k¨ uls˝o b oszt´ aly´ u igények érkezési intenzitása az a oszt´ alyhoz tartoz´ o f´ ajl mérete (byte-ban) a b osztályhoz tartoz´ o f´ ajl mérete (byte-ban) találati val´ osz´ın˝ uség az a oszt´ alyhoz tartozó fájlok esetén találati val´ osz´ın˝ uség a b oszt´ alyhoz tartozó fájlok esetén a Proxy cache szerver kimen˝ o puffere (byte-ban) a Proxy Cache szerver keresési ideje (másodpercben) a PCS Statikus szerver ideje (m´ asodpercben) a dinamikus szerver ar´ any a Proxy Cache szerveren (byte/másodperc) kliens hál´ ozati s´ avszélesség (bit/m´ asodperc) Web szerver kimen˝ o puffere (byte-ban) Inicializál´ asi id˝ o (m´ asodpercben) a Web szerver statikus szerver ideje (másodperc) a Web szerver dinamikus szerver aránya (byte/másodperc) kliens hál´ ozati s´ avszélesség (bit/m´ asodperc)

83


84

¨ 8 Osszefoglal´ o A disszertációban a Proxy Cache szerverek hatékonyságát vizsgáltam meg részletesen. A 2. fejezetben r¨ ovid, lényegretör˝o ismertet˝ot adtam a sorbanállási rendszerek és h´ al´ ozatok elméleti h´ atterér˝ol, majd a 3. fejezetben ismertettem a Slouthber ´ altal fel´ all´ıtott [32] Web szerver modellt. Proxy Cache szervert haszn´ alva, ha egy f´ ajlt le akarunk tölteni egy távoli Web szerverr˝ol, el˝ osz¨ or meg kell vizsg´ alni, hogy a keresett fájl megtalálhatóe a Proxy Cache szerveren. Ennek a val´ osz´ın˝ uségét p-vel jelölj¨ uk. Amennyiben a keresett dokumentum megtal´ alhat´ o a Proxy Cache szerveren, egy másolat a fájlról azonnal tov´ abb´ıt´ odik a felhasználónak. Amennyiben a dokumentum nem tal´ alhat´ o meg a Proxy Cache szerveren, az igény tovább´ıtódik a t´ avoli Web szerverhez. A dokumentum a Web szerverr˝ol el˝oször a Proxy Cache szerverre érkezik vissza, ahonnan egy másolat a fájlról azonnal a felhaszn´ al´ ohoz ker¨ ul. Az eredeti példány tárolódik a Proxy Cache szerveren, ´ıgy a kés˝ obbiekben elérhet˝o lesz a felhasználók számára. A 4. fejezetben részletesen bemutattam az általunk általános´ıtott Proxy Cache szerver modellt, mely egy tetsz˝ oleges igény u ´tját ábrázolja a felhasználótól kiindulva egészen a visszaérkezésig. Feltételeztem, hogy az igények a Proxy Cache szerverhez λ paraméter˝ u Poisson-folyamat szerint érkeznek, és a Web szerverhez k´ıv¨ ulr˝ ol érkez˝o igények Λ paraméter˝ u Poisson-folyamat alapj´ an érkeznek, valamint mind a Proxy Cache szerver mind pedig a Web szerver kiszolg´ al´ asi ideje exponenciális eloszlás´ u valósz´ın˝ uségi változ´ o. Kisz´ am´ıtottam egy tetsz˝oleges bels˝o igény válaszidejét Proxy Cache szerver haszn´ alata esetén, valamint Proxy Cache szerver ´ használata nélk¨ ul. Igy viszg´ alni tudtam a Proxy Cache szerver hatékonyságát k¨ ulönböz˝o paraméterértékek mellett.

85

¨ 8 Osszefoglal´ o Tanulm´ anyoztam a Proxy Cache szerver hatékonyságát a bels˝o valamint k¨ uls˝o érkezési intenzit´ asok f¨ uggvényében, valamint vizsgáltam a keresett fájl méretének és a Proxy Cache szerver találati valósz´ın˝ uségének hatását a válaszid˝ ore. Meg´ allap´ıtottam, hogy a fájlméret növelésével a Proxy Cache szerver hatékonys´ aga javul, azaz Proxy Cache szerver használatával kisebb válaszid˝ oket kapunk mint Proxy Cache szerver használata nélk¨ ul. Szintén növelhet˝ o a Proxy Cache szerver hatékonysága a találati valósz´ın˝ uség valamint a k¨ uls˝ o és bels˝ o érkezési intenzitás növelésével. Az 5. fejezetben a kor´ abban ismertetett Proxy Cache szerver modellt általános´ıtottam u ´gy, hogy egy méginkább valóságh˝ u modellt kapjunk. A korábbiakban mind a Proxy Cache szerver, mind pedig a távoli Web szerver megb´ızhat´ oak voltak, most pedig feltételeztem, hogy egyik sem megb´ızhat´ o, azaz b´ armelyik¨ uk elromolhat. Az általános´ıtással az volt a célom, hogy megvizsg´ aljam a szerverek meghibásodásának hatását a rendszerparaméterekre. A vizsg´ alt Markov l´ anc ´ allapottere, mely a módos´ıtott modellt le´ırja t´ ul nagy, az egyens´ ulyi egyenlet fel´ır´ asa és ezek megoldása t´ ul bonyolult lenne. Ezért a MOSEL (Modeling, Specification and Evaluation Language) [6] programcsomagot haszn´ altam a modell le´ırására valamint a rendszerjellemz˝ok kisz´ am´ıt´ as´ ara. Feltételeztem, hogy a Proxy Cache szerver és a Web szerver meghib´ asodhat a (t, t + dt) intervallumban δpcs dt + o(dt) valamint δweb dt + o(dt) val´ osz´ın˝ uséggel ha szabadok, valamint γpcs dt + o(dt) és γweb dt + o(dt) val´ osz´ın˝ uséggel ha foglaltak. Ha a Proxy Cache szerver vagy a Web szerver foglalt ´ allapotban romlanak el, akkor a megszakadt igény feldolgoz´ asa a jav´ıt´ as befejezése után folytatódik. A jav´ıtási id˝o exponenci´ alis eloszl´ as´ u 1/νpcs és 1/νweb átlaggal. Ha a szerverek köz¨ ul valamelyik elromlik két k¨ ul¨ onb¨ oz˝o esetet k¨ ulönböztettem meg: • Blokkolt eset: a szerver meghibásodása alatt nem érkezik u ´j igény a szerverhez. • Nem blokkolt eset: a szerver meghibásodása alatt is érkezhetnek u ´jabb igények a szerverhez. A MOSEL programcsomagot használva meghatároztam a válaszid˝oket. Megvizsg´ altam a Proxy Cache szerver és a Web szerver k¨ ulönböz˝o meg-

86

hibásodási és jav´ıt´ asi paramétereinek hat´ asát a válszid˝ore mind foglalt mind pedig szabad szerverek esetében. A 6. fejezetben az érkezési folyamat egy u ´gynevezett ”GI - General interarrival” folyamat, melyet az érkezési id˝ ok¨ ozök várható értékével és a re2 lat´ıv szórásnégyzetével (c ) jellemz¨ unk, valamint a kiszolgálási id˝o bármilyen általános eloszl´ as´ u lehet. Az approximáció [12] használatához a következ˝o feltételeknek kell tejes¨ ulni¨ uk: • Az érkezési folyamat u ´gynevezett ”fel´ uj´ıtási” folyamat kell legyen, azaz az érkezési id˝ ok¨ oz¨ ok f¨ uggetlen, azonos eloszlás´ u valósz´ın˝ uségi változók. • A kiszolgál´ asi id˝ ok val´ osz´ın˝ uségi v´ altozója bármilyen általános eloszlás´ u lehet. • Adott az érkezési folyamat inetnzit´ asa λA , valamint az érkezési fo2 lyamat relat´ıv sz´ or´ asnégyzete (cA ). • Adott a kiszolg´ al´ asi id˝ o v´ arhat´ o értéke τS , valamint a kiszolgálási 2 id˝o relat´ıv sz´ or´ asnégyzete (cS ). • Az azonnali visszacsatol´ ast amikor egy sor távozó folyamata vissza van irány´ıtva egyb˝ ol ugyanahhoz a sorhoz, k¨ ulön kell vizsgálni. Ez az aproximáci´ o olyan algoritmusokat szolgáltat, melyekkel modellezhetj¨ uk az általános h´ al´ ozati folyamatokat, mint például a forgalom egyes´ıtést, a sortól val´ o t´ avoz´ ast, valamint a forgalom szétválását. Minden esetben, a részletes sz´ am´ıt´ asok el˝ ott a modellt módos´ıtanunk kell, hogy eliminálhassuk az azonnali visszacsatolásokat. Ezt a módos´ıtást az érintett sor kiszolg´ al´ asi idejének megv´ altoztatásával végezz¨ uk. A sz¨ ukséges kalkul´ aci´ ok eredményeképp az aproximáció seg´ıtségével megkapjuk a sz¨ ukséges rendszerjellemz˝ oket (´ atlagos sorhossz, átlagos várakozási id˝o, stb.), mind a sorokra, mind pedig az egész hálózatra vonatkozóan.

87

¨ 8 Osszefoglal´ o Módos´ıtottam a Proxy Cache szerver modellt, hogy alkalmazni lehessen ´ rá a GI/G/1 approxim´ aci´ ot. Ujrakalkul´ altam a sz¨ ukséges rendszerjellemz˝oket, hogy megkapjam a keresett válaszid˝oket. Az ´ıgy kapott eredmények valid´ al´ as´ ara egy szimul´ aci´ os programot kész´ıtettem, mely seg´ıtségével ellen˝orizhet˝ o az approxim´ aci´ o helyessége. Megvizsgáltam két k¨ ulönböz˝o esetet. Abban az esetben amikor a használt relat´ıv szórásnégyzetek egynél kisebbek illetve azt az esetet amikor a használt relat´ıv szórásnégyzetek egynél nagyobbak. Megállap´ıtottam, hogy amennyiben a használt relat´ıv szórásnégyzet egynél kisebb az approxim´ aci´ oval sz´ am´ıtott válaszid˝ok az els˝o 3-4 tizedesjegyig megegyeznek a szimul´ aci´ os eredményekkel. Amikor a relat´ıv szórásnégyzet egynél nagyobb az approxim´ aci´ oval kapott válaszid˝ok csak az els˝o 2-3 tizedesjegyig egyeznek. A 7. fejezetben m´ odos´ıtottam az eredeti Proxy cache szerver modellt, hoggy vizsg´ alni lehessen a heterogén forgalom hatását a Proxy Cache szerverek hatékonys´ ag´ ara. A kliensek által keresett fájlokat méret¨ uk alapján két osztolyb´ a soroltam. Az ´ atlagosnál nagyobb méret˝ u fájlok az a, m´ıg a kis méret˝ u, u ´gynevezett ”norm´ al” fájlok a b osztályba ker¨ ulnek. Mindkét osztályba tartoz´ o igény esetén el˝oször megvizsgáljuk, hogy a fájl megtalálhat´ o-e a Proxy Cache szerveren vagy sem. Ezt a találati valósz´ın˝ uséget pa illetve pb -vel jel¨ olj¨ uk az a illetve b osztályba tartozó fájlok esetén. Amennyiben a keresett f´ ajl megtalálható a Proxy Cache szerveren, akkor mindkét oszt´ aly esetén a f´ ajl egy másolata azonnal tovább´ıtódik a klienshez. Ellenkez˝ o esetben, amikor is a fájl nem található meg a Proxy Cache szerveren az igény tov´ abb´ıt´ odik a távoli Web szerverhez f¨ uggetlen¨ ul az osztály´ at´ ol. Miut´ an az igényelt fájl visszaérkezik a Proxy Cache szerverhez egy m´ asolat tov´ abb´ıt´ odik a klienshez. Feltételeztem, hogy mindkét osztályhoz tartozó igények a Proxy Cache szerverhez Poisson-folyamat szerint érkeznek, és a Web szerverhez k´ıv¨ ulr˝ol érkez˝o igények szintén Poisson-folyamat alapján érkeznek, valamint mind a Proxy Cache szerver mind pedig a Web szerver kiszolgálási ideje f¨ uggetlen exponenci´ alis eloszl´ as´ u val´ osz´ın˝ uségi változó. Kiszám´ıtottam egy tetsz˝oleges bels˝ o igény v´ alaszidejét Proxy Cache szerver használata esetén, valamint Proxy Cache szerver használata nélk¨ ul. Így viszgálni tudtam a Proxy Cache szerver haszn´ alat´ at k¨ ulönböz˝o paraméterértékek mellett.

88

Megvizsgáltam a Proxy Cache szerver hatékonyságát a bels˝o valamint k¨ uls˝o érkezési intenzit´ asok f¨ uggvényében, valamint vizsgáltam az a illetve b osztályhoz tartoz´ o f´ ajlok méretének és az a illetve b osztály arányának hatását a válaszid˝ ore. Megmutattam, hogy mind a bels˝o mind pedig a k¨ uls˝o érkezési intenzit´ as n¨ ovelésével a v´ alaszid˝ok n˝onek, f¨ uggetlen¨ ul a Proxy Cache szerver jelenlétét˝ ol. Amennyiben az a osztályos kérések arányát növelj¨ uk a v´ alaszid˝ ok szintén n˝ onek, valamint magas a osztály arányt használva m´ ar alacsonyabb érkezési intenzitás esetén is megéri a Proxy Cache szerver haszn´ alata. Alacsony a osztály arány, alacsony érkezési intenzitás és alacsony tal´ alati val´ osz´ın˝ uség használatával Proxy Cache szerverrel magasabb v´ alaszid˝ oket kapunk mint nélk¨ ule.

89

¨ 8 Osszefoglal´ o

90

9 Conclusion The first part of the dissertation (see Chapter 2) was devoted to give a small overview on the queueing and queueing network theory. In Chapter 3. I described a Web server model created by Slouthber [32]. Using Proxy Cache server, if any information or file is requested to be downloaded, first it is checked whether the document exists on the Proxy Cache server or not. (We denote the probability of this existence by p). If the document can be found on the Proxy Cache server then its copy is immediately transferred to the user. In the opposite case the request will be sent to the remote Web server. After the requested document arrived back to the Proxy Cache server then a copy of it is delivered to the user. In Chapter 4. I described a Proxy Cache server model, which illustrates the path of a request starting from the user and ending with the return of the answer to the user. We assume that the requests of the Proxy Cache server users arrive according to a Poisson process with rate λ, and the external requests arrive to the Web server according to a Poisson process with rate Λ, respectively, and the Proxy Cache server and Web server have an exponentially distributed service time distribution. I have calculated the overall response time with and without Proxy Cache server. I analyzed how various factors affect the performance of a Proxy Cache server. These factors include the arrival rates of requests, the ”cache hit rate” probability and the external arrival rates. I also examine the effect of the file size. I noticed that, when the arrival rate of requests increases, then the response times increase as well, regardless of the existence of a Proxy Cache server. When we used a high visit rate with a high cache hit rate probability, then the response time gap was more significant between the cases with and without a Proxy Cache server, so in this case we get smaller response time using Proxy Cache server. Increasing the visit rate for the external users, the difference between response time with and without a Proxy

91

9 Conclusion Cache server was smaller and smaller until this difference vanished and the existence of a Proxy Cache server resulted lower response times. We can increase the performance of Proxy Cache server using higher file size or higher cache hit rate probability. In chapter 5. I generalize the performance model of the Proxy Cache server using a more realistic case when the Proxy Cache server and the remote Web server are unreliable. Our aim is to illustrate graphically the effect of the non-reliability of both Proxy Cache servers and Web servers on the steady state system measures. Since the state space of the describing Markov chain is very large, it is dificult to calculate the system measures in the traditional way of writing down and solving the underlying steady-state equations. To simplify this procedure we used the software tool MOSEL (Modeling, Specification and Evaluation Language), see [6], to formulate the model and to obtain the performance measures. The Proxy Cache server and the Web server can fail during the interval (t, t+dt) with probability δpcs dt+o(dt) and δweb dt+ o(dt) if they are idle, and with probability γpcs dt + o(dt) and γweb dt + o(dt) if they are busy, respectively. If the Proxy Cache server or the Web server fails in busy state, it continues servicing the interrupted request after it has been repaired. The repair time is exponentially distributed with a finite mean 1/νpcs and 1/νweb . If one of the servers fails two different cases can be treated: • Blocked case: during the CPU is down, no new requests may come to the server buffer. • Unblocked case: the new requests can fill the server buffer during the breakdown, until it is full. All the times involved in the model are assumed to be mutually independent of each other. Using Mosel I had to calculate the overall response time. I examined the effect of the non-reliability of both Proxy Cache servers and Web servers on the steady state system measures and the difference in the performance using blocked and intelligent sources. In Chapter 6. we assume that the arrival process is a general (GI) arrival process characterised by a mean arrival rate and a squared coefficient of variation (SQV) of the inter-arrival time, and the service time may have

92

any general distribution. In order to apply the GI/G/1 approximation we assume the following: • The arrival process to a network node is renewal, so the arrival intervals are independent, identically distributed random variables. • The service time may have any general distribution. • We know the parameters of the arrival process: λA - the mean arrival rate and c2A - the SQV of the inter-arrival time. • We know the parameters of the service time τS - the mean service time, and c2S - the SQV of the service time. • Immediate feedback, where a fraction of the output of a particular queue enters the queue once again, needs special treatment. This approximation contains procedures required for modeling of the basic network operations of merging, departure and splitting, arising due to the common sharing of the resources and routing decisions in the network. Before the detailed analysis of the queueing network is done, the method first removes immediate feedback in a queue by suitably modifying its service time. The approximation provide performance measures (i.e. mean queue lengths, mean waiting times, etc.) for both per-queue and pernetwork. I modified the performance model of Proxy Cache servers to get a more powerful variant when the inter-arrival times and the service times are generally distributed. In this case we can use the GI/G/1 approximation to obtain the overall response time. I recalculated the basic performance parameters of the modified performance model using the approximation method. The accuracy of the new model is validated by means of a simulation study over an extended range of test cases. I studied two different cases. When the SQV < 1 the overall response time obtained by approximation is very close to the response time obtained by simulation; they are the same at least up to the 3rd-4th decimal digit. In case when the SQV > 1 the response times are the same only to 2nd-3rd decimal digit. So, using greater SQV the approximation error is greater.

93

9 Conclusion The focus of the Chapter 7. is to examine the performance behavior of Proxy Cache servers when we use heterogeneous traffic. In this thesis we describe the multi-class queuing network model of the Proxy Cache server, where we separate the requests in two classes by virtue of their size. If the size of the requested document is greater than average we put it into class a. In the opposite case, when the size of the requested file is small we put it into class b. In booth cases first it is checked whether the document (class a or class b) exists on the Proxy Cache server or not. We denote the probability of this existence by pa in case of class a and by pb in case of class b. If the document can be found on the Proxy Cache server then its copy is immediately transferred to the user. In the opposite case the request will be sent to the remote Web server. After the requested document arrived back to the Proxy Cache server then a copy of it is delivered to the user. We assume that the requests of the Proxy Cache server users for both classes arrive according to a Poisson process with rate λa and λb , and the external requests for booth classes arrive to the Web server according to a Poisson process with rate Λa and Λb , respectively, and the Proxy Cache server and Web server have an exponentially distributed service time distribution. I have calculated the overall response time with and without a Proxy Cache server. I analyzed how various factors affect the performance of a Proxy Cache server when we use heterogeneous traffic. In general when the arrival rate of requests increases, then the response time increases as well regardless of the existence of a Proxy Cache server. Increasing the percentage of the class a the response time increases too. When we use a higher percentage of the class a and we use a high arrival rate, then the response time gap is more significant between the cases with and without a Proxy Cache server. Using a low percentage of class a files, a low arrival rate and low cache hit rate probability we get higher response time in presence of a Proxy Cache server.

94

Irodalomjegyz´ ek [1] C. Aggarwal, J.L. Wolf, and P.S. Yu. Caching on the world wide web. IEEE Transactions on Knowledge and Data Engineering, 11:94–107, 1999. [2] V.A.F. Almeida, J.M. de Almeida, and C.S. Murta. Performance analysis of a www server. Proceedings of the 22nd International Conference for the Resource Management and Performance Evaluation of Enterprise Computing Systems, 13, 1996. [3] Allen A.O. Probability, statistics, and queueing theory : with computer science applications. Academic Press, New York, 1997. [4] M.A. Arlitt and C.L. Williamson. Internet web servers: workload characterization and performance implications. IEEErACM Transactions on Networking, 5:631–645, 1997. [5] I. Atov. Qna inverse model for capacity provisioning in delay constrained ip networks. Centre for Advanced Internet Architectures. Technical Report, 2004. [6] K. Begain, G. Bolch, and H. Herold. Practical performance modeling, application of the MOSEL language. Kluwer Academic Publisher, Boston, 2001. [7] T. Berczes. Approximation approach to performance evaluation of proxy cache server systems. Annales Mathematicae et Informaticae, 36:15–28, 2009. [8] T. Berczes, G. Guta, G. Kusper, W. Schreiner, and J. Sztrik. Analyzing web server performance models with the probabilistic model checker prism. Technical report no. 08-17 in RISC Report Series, 2008.

95

Irodalomjegyzék [9] T. Berczes and J. Sztrik. Performance modeling of proxy cache servers. Journal of Universal Computer Science, 12:1139–1153, 2006. [10] T. Berczes, J. Sztrik, and C.S. Kim. The impact of multimedia traffic on the performance of a proxy cache server. Annales Univ. Sci. Budapest, Sect. Comp., 25:153–169, 2005. [11] I. Bose and H.K. Cheng. Performance models of a firms proxy cache server. Decision Support Systems and Electronic Commerce, 29:45– 57, 2000. [12] S.K. Bose. An introduction to queueing systems. Kluwer Academic/Plenum Publishers, New York, 2002. [13] L. Breuer and D. Baum. An Introduction to Queueing Theory and Matrix-Analytic Methods. Springer Verlag, Netherlands, 2005. [14] S.J. Caughey, D.B. Ingham, and M.C. Little. Flexible open caching for the web. Computer Networks and ISDN Systems, 29:1007–1017, 1997. [15] X. Chao, M. Miyazawa, and M. Pinedo. Queueing Networks : Customers, Signals and Product Form Solutions. John Wiley & Sons, New York, 1999. [16] H. Chen and D. Yao. Fundamentals of Queuing Networks: Performance, Asymptotics, and Optimization. Springer, New York, 2001. [17] R. Disney and P. Kiessler. Traffic processes in queueing networks : a Markov renewal approach. Johns Hopkins University Press, 1987. [18] T. V. Do and R. Chakka. Simulation and analytical approaches for estimating the performability of a multicast address dynamic allocation mechanism. Simulation Modelling Practice and Theory, 18(7):971–983, 2010. [19] T. V. Do, U. R. Krieger, and R. Chakka. Performance modeling of an apache web server with a dynamic pool of service processes. Telecommunication Systems, 39(2):117–129, 2008.

96

Irodalomjegyzék [20] Tien Van Do. A new solution for a queueing model of a manufacturing cell with negative customers under a rotation rule. Performance Evaluation, 68(4):330 – 337, 2011. G-Networks and their Applications - G-Networks. [21] V.T Do, R. Chakka, T. Le Nhat, and O. Gemikonakli. A new performance model for web servers. Federation of European Simulation Societies, pages 19–21, 2004. [22] V.T Do, R. Chakka, T. Le Nhat, and U. Krieger. Performance modelling of a web server with a dynamic pool of service processes. Center for Mathematics and Computer Science, pages 19–21, 2006. [23] G. Fayez. Analysis of Computer and Communication Networks. Springer, 2008. [24] Bolch G., Greiner S., H. de Meer, and Trivedi K.S. Queueing Networks and Markov Chains. Wiley-Interscience, 2006. [25] E. Gelenbe and G. Pujolle. Introduction to Queueing Networks. John Wiley & Sons, 1998. [26] M. Kurcewicz, W. Sylwestrzak, and A. Wierzbicki. A filtering algorithm for web caches. Computer Networks and ISDN Systems, pages 2203–2209, 1998. [27] E.D. Lazowska, J. Zahorjan, G.S. Graham, and K.C. Sevcik. Quantitative System Performance. Prentice Hall, 1984. [28] D.A. Menasce and V.A.F. Almeida. Capacity Planning for Web Performance: Metric, Models, and Methods. Prentice Hall, 1998. [29] Balsamo S. and Onvural R. Person V. de Nitto. Analysis of queueing networks with blocking. International Series in Operations Research and Management Science, 31. [30] R. Sahner, K. Trivedi, and A. Puliafito. An Example-Based Approach Using the SHARPE Software Package. Kluwer Academic Publisher, 2002.

97

Irodalomjegyzék [31] P. Scheuermann, J. Shim, and R. Vingralek. A case for delayconscious caching of web documents. Computer Networks and ISDN Systems, 29:997–1005, 1997. [32] L.P. Slothouber. A model of web server performance. 5th International World Wide Web Conference, 1996. [33] H. Takagi. Stochastic analysis of computer and communication systems. Elsevier Science Inc., New York, 1990. [34] H.C. Tijms. Stochastic Modelling and Analysis. A computational approuch. John Wiley & Sons, New York, 1986. [35] N.M. Van Dijk. Queueing Networks and Product Forms: A Systems Approach. John Wiley & Sons, 1993. [36] W. Whitt. Approximations for the gi/g/m queue. Productions and Operations Management, 2:114–161, 1933. [37] W. Whitt. Performance of the queueing network analyzer. Computer Networks and ISDN Systems, 62:2817–2843, 1983.

98

Irodalomjegyzék Publik´ aci´ oim: • [J] Foly´ oiratcikkek: J1 T. Berczes, J. Sztrik, Kim, C.S., The impact of multimedia traffic on the performance of a proxy cache server. Annales Univ. Sci. Budapest, Sect. Comp., 25 (2005), 153-169 J2 T. Berczes and J. Sztrik, Performance Modeling of Proxy Cache Servers. Journal of Universal Computer Science., 12 (2006), 1139–1153 J3 T. Berczes and J. Sztrik, Performance evaluation of proxy cache servers. H´ırad´ astechnika., Selected Papers LXI (2006/1), 2-5 J4 T. Berczes, Approximation approach to performance evaluation of Proxy Cache Server systems. Annales Mathematicae et Informaticae., 36 (2009), 15-28 J5 T. Berczes, G. Guta, G. Kusper, W. Schreiner and J. Sztrik, Comparing the Performance Modeling Environment MOSEL and the Probabilistic Model Checker PRISM for Modeling and Analysing Retrial Queueing Systemszes, Annales Mathematicae et Informaticae., 37 (2010), 51-75 J6 T. Berczes, A. Hazy, and J. Sztrik, The impact of servers breakdown on the performance of proxy cache servers Mathematical and Computer Modelling (Submitted) • [C] Konferencia kiakdv´ anyok: C1 T. Berczes and J. Sztrik, A queueing network model to study Proxy Cache Servers. Proceedings of 7th International Conference on Applied Informatics., Eger, Hungary Vol. 1 (2007), 203-211. C2 T. Berczes, G. Guta, G. Kusper, W. Schreiner and J. Sztrik, Analyzing a Proxy Cache Server Performance Model

99

Irodalomjegyzék with the Probabilistic Model Checker PRISM. WWV 2009 Automated Specification and Verification of Web Systems 5th International Workshop., Linz (2009). – Angel Vassilev Nikolov, Effects of the coherency on the Performance of the Web Cache Proxy Server. International Journal of Computer Science and Network Security., 9 (2009), 158-162. – LIU Xu-jun, MA Yue and YU Dong Analysis and Evaluation of Real-time Performance of Publish/Subscribe Communication Mode. Computer Engineering., Vol. 9, No. 20 (2010), 229-231. • [O] Egy´ eb: O1 T. Berczes, G. Guta, G. Kusper, W. Schreiner and J. Sztrik, Analyzing Web Server Performance Models with the Probabilistic Model Checker PRISM. Technical report no. 0817 in RISC Report Series , University of Linz, Austria. November 2008 O2 T. Berczes, G. Guta, G. Kusper, W. Schreiner and J. Sztrik, Comparing the Performance Modeling Environment MOSEL and the Probabilistic Model Checker PRISM for Modeling and Analysing Retrial Queueing Systems. Technical report no. 07-17 in RISC Report Series , University of Linz, Austria. November 2007

100

Proxy Cache szerverek hatékonyságának vizsgálata. Performance Modeling of Proxy Cache Servers

Recommend Documents