¨ ´ asi ´ Tobb szerveres Markov kiszolgal modellek: ´ ıtasi ´ algoritmusok szam´ ´ infokommunikaci ´ os ´ alkalmazasok ´ es
Do Van Tien PhD MTA doktori e´ rtekez´es t´ezisei
Budapesti M˝uszaki e´ s Gazdas´agtudom´anyi Egyetem
2009.
1.
Motiv´aci´ok
Az elm´ult sz´azadban Erlang alkalmazta el˝osz¨or a sorban´all´asi elm´eletet telefonh´al´ozatok m´eretez´es´ere, majd az u´ tt¨or˝o kezdem´enyez´es o´ ta sz´amos munka e´ p´ıtette tov´abb a sorban´all´asi elm´eletet [8, 16, 36, 37, 40, 42] e´ s alapozta meg az eredm´enyek sz´elesk¨or˝u gyakorlati alkalmaz´as´at. 1960-as e´ vekben Kleinrock a sorban´all´asi elm´elet seg´ıts´eg´evel igazolta a csomagkapcsolt h´al´ozat hat´ekonys´ag´at, amely eredm´eny kucsszerepet j´atszott az Internet fejleszt´es´eben. A ter¨ulet ennek megfelel˝oen az elm´ult e´ vtizedekben – e´ s az ut´obbi e´ vekben is – a kutat´ok rendk´ıv¨ul sz´eles k¨or´enek figyelm´et vonta mag´ara [1]. A k´erd´esek nagy r´esze azonban m´eg mindig v´alaszra v´ar, ugyanis a k¨ul¨onb¨oz˝o tulajdons´ag´u szolg´altat´asok elt´er˝o, de meghat´arozott min˝os´eg˝u ny´ujt´asa ugyanazon h´al´ozati er˝oforr´asokkal, az u´ j k´erd´esek sokas´ag´at vetette fel mind az ig´enyek jellemz´ese, mind egym´asra hat´asuk elemz´ese, mind pedig a megfelel˝o h´al´ozati funkci´ok specifik´al´asa ter¨ulet´en. Az elm´eleti teljes´ıt˝ok´epess´egi elemz´esek c´elja a m´eg fel nem e´ p´ıtett rendszer teljes´ıt˝ok´epess´eg´enek becsl´ese. Az elemz´es f˝o pontjai a k¨ovetkez˝ok [29]: • a forgalomforr´asok modellez´ese modellparam´eterek meghat´aroz´asa,
sztochasztikus
folyamatokkal,
a
• a rendszer viselked´es´enek elemz´ese, bele´ertve a h´al´ozatelemek teljes´ıt˝ok´epess´egi modellez´es´et is, • a rendszer teljes´ıt˝ok´epess´eg´enek e´ rt´ekel´ese a forgalmi ig´enyek e´ s a h´al´ozat k¨olcs¨onhat´as´anak figyelembev´etel´evel. A fenti tev´ekenys´egeket [35]: • z´art alak´u v´egk´epleteket eredm´enyez˝o anal´ızissel, • a teljes´ıt˝ok´epess´egi jellemz˝ok numerikus kisz´am´ıt´as´ara alkalmas algoritmusokkal, • sz´am´ıt´og´epes szimul´aci´oval, valamint • a meglev˝o rendszer m˝uk¨odtet´esi tapasztalatainak figyelembev´etel´evel fel´all´ıtott el˝orejelz´esek seg´ıts´eg´evel lehet v´egezni, melyek k¨oz¨ul az e´ rtekez´esben az els˝o h´arom technik´ara koncentr´altam.
2.
T´emak¨orrel kapcsolatos fogalmak e´ s eredm´enyek
Az a´ ltalam el´ert eredm´enyek a szakirodalomban k¨ozismert fogalomhoz (kv´azi-sz¨ulet´esi-hal´aloz´asi folyamat) e´ s egy numerikus m´odszerhez (spektr´alis felbont´as) kapcsol´odnak. Az´ert, hogy k´epbe helyezzem az olvas´ot, r¨oviden o¨ sszefoglalom a kv´azi-sz¨ulet´esi-hal´aloz´asi folyamat e´ s spektr´alis felbont´ason alapul´o m´odszer l´enyeg´et. Tekints¨unk egy folytonos idej˝u, id˝oben homog´en, irreducibilis, v´egtelen a´ llapotter˝u Markov l´ancot, amelyben a rendszer a´ llapot´at a t id˝opontban k´et v´eletlen v´altoz´o ´ırja le: I(t) (I(t) ∈ {0, 1, . . . , N }) e´ s J(t) (J(t) ∈ {0, 1, . . .}). Egy szintnek szokt´ak nevezni 1
az a´ llapotok azon r´eszhalmaz´at, amelyhez ugyanolyan J e´ rt´ek tartozik. A szint fogalm´at haszn´alva a pozit´ıv val´osz´ın˝us´eg˝u egyl´ep´eses a´ tmenetek csak egy szinten bel¨ul illetve a szomsz´edos szintek a´ llapotai k¨oz¨ott lehetnek. Az ilyen a´ tmeneteket tartalmaz´o folyamatot nevezz¨uk kv´azi-sz¨ulet´esi-hal´aloz´asinak (QBD) [37, 39]. A rendszer v´altoz´asai a h´arom t´ıpus´u a´ tmenettel ´ırhat´ok le: • szinten bel¨uli a´ tmenetek: Aj (i, k) az (i, j) a´ llapotb´ol az (k, j) a´ llapotba (0 ≤ i, k ≤ N ; j = 0, 1, . . . , L) val´o a´ tmenetet jel¨oli. • felfel´e l´ep´eses a´ tmenetek: Bj (i, k) az (i, j) a´ llapotb´ol az (k, j + 1) (0 ≤ i, k ≤ N ; j = 0, 1, . . .) a´ llapotba val´o a´ tmenetet reprezent´alja. • lefel´e l´ep´eses a´ tmenetek: Cj (i, k) az (i, j) a´ llapotb´ol az (k, j − 1) (0 ≤ i, k ≤ N a´ llapotba val´o a´ tmenetet jel¨oli. Aj , Bj e´ s Cj az (N + 1) × (N + 1) elem˝u m´atrixok, amelyeknek elemei Aj (i, k), Bj (i, k) e´ s Cj (i, k). A kv´azi-sz¨ulet´esi-hal´aloz´asi folyamatok egyens´ulyi eloszl´as´anak kisz´amol´as´ara t¨obb hat´ekony m´odszert is kidolgoztak. A m´odszerek a szab´alyos r´esz speci´alis szerkezet´et (ahol Aj = A, Bj = B e´ s Cj = C, azaz nem f¨uggnek j-t˝ol) haszn´alj´ak ki e´ s a szab´alytalan r´esz b´armilyen szerkezet˝u fel´ep´ıt´es´et is megengedik, p´eld´aul a szab´alytalan r´eszben lehets´eges a´ tmenet nem szomsz´edos szintek k¨oz¨ott is. A m´atrix egyenlet saj´at´ert´ek feladatk´ent t¨ort´en˝o megold´as´at javasolta Mitrani e´ s Chakka [8, 39]. Ebben a λφ = φ B + λA + λ2 C saj´at´ert´ek feladat (λ komplex sz´am e´ s φ (N + 1) dimenzi´os komplex vektor) 2N + 2 darab megold´asa k¨oz¨ul az N + 1 darab legkisebb abszol´ut´ert´ek˝u saj´at´ert´ek megold´as´at e´ s a hozz´atartoz´o N + 1 darab saj´atvektort keresik meg e´ s ezekb˝ol e´ p´ıtik fel a megold´ast. A kv´azi-sz¨ulet´esi-hal´aloz´asi folyamatok sz´amos t´avk¨ozl´esi probl´em´ak elemz´es´ere alkalmazhat´oak [2–10, 12–15, 19, 24, 25, 27, 28, 30–34, 38, 39, 43, 44]. A kv´azi-sz¨ulet´esi-hal´aloz´asi folyamatok a´ ltal´anos´ıt´asa valamint spektr´alis felbont´ason alapul´o m´odszer e´ s alkalmaz´asai t´emak¨or´eben Prof. Ram Chakkaval (a m´odszer egyik kidolgoz´oja) folytatunk k¨oz¨os kutat´asokat t¨obb mint egy e´ vtizede1 . Jelen e´ rtekez´es foglalja o¨ ssze az el´ert tudom´anyos eredm´enyeimet, amelyek h´arom f˝o csoportban sorolhat´ok: 1. T¨obb szerveres markovi sorban´all´asi rendszerek a´ ltal´anos´ıt´asa [10] e´ s ¨ onb¨oz˝o probl´em´akra val´o alkalmaz´asa [9, 10, 12, 22, 23, 27, 28, 41]: kul¨ P Kidolgoztunk egy m´odszert az u´ n. HetSigma sor (MM K k=1 CP Pk /GE/c/L G) a´ lland´osult a´ llapot-val´osz´ın˝us´egeinek meghat´aroz´as´ara. Bebizony´ıtottam 1
Tran Tuan Hung - volt doktoranduszomnak e´ s Wolfner Gy¨orgy- Jereb L´aszl´o volt doktorandusz´anak Ph.D disszert´aci´oja is szorosan kapcsol´odik a QBD t´emak¨orh¨oz.
2
a HetSigma sor stacion´arius a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´aban fontos szerepet j´atsz´o tulajdons´agokat. Megadtam a szerz˝ot´arsam javasolt transzform´aci´okra alapozottan a karakterisztikus m´atrix polinom egy¨utthat´oira vonatkoz´o z´art k´epletet. Felismertem, hogy a HetSigma sor alkalmas n´eh´any kommunik´aci´os h´al´ozatokban e´ s informatikai rendszerekben lev˝o probl´ema (optikai b¨orszt kapcsolt multiplexer, MPLS forgalomir´any´ıt´as, HSDPA, Apache Web szerver) modellez´es´ere e´ s elemz´es´ere. Megeml´ıtend˝o az a t´eny, hogy az els˝o eredm´eny-csoportban Ram Chakka t´arsszerz˝ovel k¨oz¨osen kidolgoztunk egy m´odszert a HetSigma sor a´ lland´osult a´ llapot-val´osz´ın˝us´egeinek meghat´aroz´as´ara, amely az o˝ kor´abbi cikk´eben [6] megjelent MM CPP/GE/c/L G sor a´ ltal´anos´ıt´as´at jelenti. A k¨oz¨os cikk¨unkben [10] e´ s a 3. fejezetben tal´alhat´o transform´aci´ok alkalmaz´asa Chakka o¨ tlete volt, ugyanakkor a levezet´esek e´ s alkalmaz´asi p´eld´ak a saj´at eredm´enyeim. ´ 2. Az ujra-pr´ ob´alkoz´asi sorokkal (retrial queue) modellezhet˝o rendszerek jellemz˝oinek hat´ekony meghat´aroz´asa [17, 18, 20]: Az u´ jra-pr´ob´alkoz´asi sorok sz´amos infokommunik´aci´os rendszer (DHCP szerver, vezet´ekn´elk¨uli h´al´ozat) elemz´es´ere haszn´alhat´oak, ugyanakkor legt¨obb esetben matematikailag kezelhetetlenek. A t´emak¨orben k¨ozel´ıt˝o modelleket javasoltam. A k¨ozel´ıt˝o modellek fontos tulajdons´againak felhaszn´al´as´aval hat´ekony algoritmusokat sz´armaztattam a rendszer a´ lland´osult a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´ara. A val´os´agot k¨ovet˝o szimul´aci´os vizsg´alatokkal megmutattam, hogy a javasolt m´odszerek k´epesek pontosan meghat´arozni a teljes´ıt˝ok´epess´egi param´etereket. Az a´ ltalam kidolgozott algoritmusok sz´am´ıt´as-ig´enye O(c) (ahol c a szerverek sz´ama), ´ıgy azok nagysz´am´u er˝oforr´assal gazd´alkod´o rendszerek (DHCP szerver, mobil h´al´ozat) m´eretez´es´ere k¨ul¨on¨osen alkalmasak. Az M/M/c/N+c visszacsatol´asos e´ s u´ jrapr´ob´alkoz´asi sorban´all´asi sort vizsg´altam. Felismertem e´ s bebizony´ıtottam, hogy a karakterisztikus m´atrix polinomnak b(N + c + 2)/2c db nulla e´ rt´ek˝u saj´at´ert´eke van. A Grassmann a´ ltal kidolgozott algoritmust m´odos´ıtottam a nulla e´ rt´ek˝u saj´at´ert´ek kezel´es´ere. Megmutattam, hogy az a´ ltalam m´odos´ıtott elj´ar´as a nagy kapacit´as´u rendszer eset´en a hagyom´anyos algoritmusokn´al gyorsabban tudja meghat´arozni a jellemz˝oket. 3. A vak´aci´os sorban´all´asi modellekel kapcsolatos eredm´enyek e´ s azok alkalmaz´asa [21, 26].: A virtu´alis g´ep-szolg´altat´ok vak´aci´os alap´u karbantart´asi politik´aj´anak elemz´es´ere egy u´ j CPP/M/c vak´aci´os sorban´all´asi modellt, valamint egy u´ jrapr´ob´alkoz´asi ig´enyekkel e´ s dolgoz´o vak´aci´os szerverrel rendelkez˝o u´ j M/M/1 sorban´all´asi modellt vezettem be. Bebizony´ıtottam a rendszer stabilit´asi felt´etel´ere vonatkoz´o t´etelt, ennek k¨ovetkezm´enyek´ent a vak´aci´os alap´u karbantart´asi politika a t´ulterhel´es vesz´elye n´elk¨ul alkalmazhat´o a virtu´alis-szerver szolg´altat´okn´al. Levezettem a pontos k´epleteket a rendszer a´ lland´osult a´ llapot-val´osz´ın˝us´egeinek meghat´aroz´as´ara. Megadtam a rendszer sztochasztikus dekompozici´oj´ara vonatkoz´o t´etel bizony´ıt´as´at.
3
3.
T´ezisek
Az e´ rtekez´es eredm´enyei h´arom f˝o t´eziscsoportba2 sorolhat´ok, nagyj´ab´ol a disszert´aci´o t¨orzs´et alkot´o 2., 3. e´ s 4. r´eszek tagol´as´anak megfelel˝oen. 1. T´ezis: T¨obb szerveres Markovi sorban´all´asi rendszer a´ ltal´anos´ıt´asa [10] e´ s t¨obb probl´em´ara val´o alkalmaz´asa [9–12, 22, 23, 27, 28, 41] T¨P obb szerveres Markovi sorban´all´asi rendszer (the K MM k=1 CP Pk /GE/c/L G-Queue with Heterogeneous Servers- HetSigma) anal´ızis´et ismertettem a 3. fejezetben [10]. Felismertem, hogy a HetSigma sor alkalmas n´eh´any kommunik´aci´os h´al´ozatokban e´ s informatikai rendszerekben lev˝o probl´ema modellez´es´ere e´ s elemz´es´ere [10, 12, 27, 28]. Korl´atozott terjedelme miatt a dolgozatban csak az Apache web szerver modellez´es´evel kapcsolatos u´ j eredm´enyeket ismertettem. A t´emak¨orrel kapcsolatos, jelen e´ rtekez´es 3. e´ s 4. fejezet´eben megtal´alhat´o u´ j saj´at tudom´anyos eredm´enyeim a k¨ovetkez˝o pontokba foglalhat´ok o¨ ssze: 1.1. Megadtam a transzform´aci´ok k¨ovetkezm´enyek´ent, a GK,c,m v´egs˝o form´aj´at, valamint a karakterisztikus m´atrix polinom (3.1. t´etel) egy¨utthat´oira (QK−m ) vonatkoz´o 3.22 e´ s 3.23 k´epletet (l´asd. a 3.3.2 alfejezet). 1.2. Bebizony´ıtottam a HetSigma sor tulajdons´agaival kapcsolatos, a sorban´all´asi rendszer stacion´arius a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´aban szerepet j´atsz´o 3.1, 3.2, 3.3, 3.4 e´ s 3.5 t´etelt (l´asd. a 3.3.2 e´ s 3.3.3 alfejezet). 1.3. Felismertem, hogy a HetSigma sor alkalmazhat´o az Apache szerverben zajl´o kiszolg´al´o folyamatok modellez´es´ere (l´asd. 4. fejezet). Megfelel˝o v´altoz´o (I2 (t)) bevezet´es´evel le´ırtam az Apache server MPM (Multi-Processing Module) folyamat-szab´alyoz´asi mechanizmus´at (l´asd. a 4.3.3.2 alfejezet). 1.4. A h´arom-dimenzi´os folyamat megfelel˝o rendez´es´evel e´ s a Kronecker m˝uveletek seg´ıts´eg´evel levezettem, hogy a rendszer a k´etdimenzi´os QBD-M folyamattal (Y = {[I(t), J(t)]; t ≥ 0}) megegyez˝o m´odon jellemezhet˝o, e´ s a´ llapot-val´osz´ın˝us´egeinek meghat´aroz´as´ara a HetSigma sor elemz´es´ere kidolgozott m´odszer haszn´alhat´o (l´asd. 4.3.4. alfejezet). 1.5. Megadtam a k´epleteket az Apache web szerver teljes´ıt˝ok´epess´egi jellemz˝oinek meghat´aroz´as´ara (4.3.5 alfejezet). A modellez´es hat´ekonys´ag´anak vizsg´alat´ara m´er´eseket dolgoztam ki, e´ s ezek seg´ıts´eg´evel igazoltam, hogy a modellre alapozott sz´am´ıt´asok j´ol k¨ozel´ıtik a val´os´agos rendszerben m´ert jellemz˝oket (4.4.1. alfejezet).
2
Az MTA m˝uszaki tudom´anyok oszt´aly´anak k¨ovetelm´enyrendszer´et figyelembev´eve jelen t´ezisf¨uzet els˝oleges c´elja, hogy egy´ertelm˝uen seg´ıtse meg´allap´ıtani az e´ rtekez´esben ismertetett eredm´enyeimet.
4
´ 2. T´ezis: Ujra-pr´ ob´alkoz´asi sorokkal (retrial queue) modellezhet˝o rendszerek jellemz˝oinek hat´ekony meghat´aroz´asa [17, 18, 20] A t´emak¨orrel kapcsolatos, jelen e´ rtekez´es 5., 6. e´ s 7. fejezet´eben megtal´alhat´o u´ j saj´at tudom´anyos eredm´enyeim az al´abbiak: 2.1. A DHCP m˝uk¨od´es e´ s a DHCP kliensek k¨oz¨otti k¨olcs¨onhat´as elemz´es´ere u´ jra-pr´ob´alkoz´asi sorban´all´asi modellt dolgoztam ki (5.3.1. alfejezet). A modell be´erkez´esi folyamat´aval kapcsolatos felt´etelez´est (Poisson e´ rkez´esi folyamat) a H´ırad´astechnikai Tansz´eken m˝uk¨od˝o DHCP szerverben gy˝ujt¨ott adatokkal valid´altam (l´asd. 5.1. a´ bra). 2.2. A DHCP mechanizmus e´ s a DHCP kliensek k¨oz¨otti k¨olcs¨onhat´ast le´ır´o pontos matematikai modell kezelhetetlens´ege miatt egy k¨ozel´ıt˝o modellt javasoltam. Levezettem, hogy a k¨ozel´ıt˝o modell a´ lland´osult a´ llapot-val´osz´ın˝us´egei a karakterisztikus m´atrix polinom egyetlen saj´at´ert´ek-saj´atvektor p´arj´aval e´ s megfelel˝o egy¨utthat´okkal kifejezhet˝oek (5.3. k´eplet). Bebizony´ıtottam (5.1 t´etel), hogy a saj´at´ert´ek a karakterisztikus m´atrix polinom LU-faktoriz´aci´oj´aban szerepl˝o L m´atrix f˝oa´ tl´oj´aban lev˝o utols´o elem gy¨oke a (0,1) intervalumban. Az 5.1 t´etel felhaszn´al´as´aval egy hat´ekony algoritmust (l´asd. az 5.1-es algoritmus) sz´armaztattam az egyetlen saj´at´ert´ek, saj´atvektor, egy¨utthat´ok meghat´aroz´as´ara e´ s a rendszer a´ lland´osult a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´ara. 2.3. A kidolgozott megold´as hat´ekonys´ag´anak e´ rt´ekel´es´ere vizsg´alatokat v´egeztem a DHCP mechanizmus e´ s a DHCP kliensek k¨oz¨otti k¨olcs¨onhat´ast pontosan le´ır´o szimul´aci´os modell seg´ıts´eg´evel. Az o¨ sszehasonl´ıt´as (5.1 t´abl´azat) megmutatja, hogy a sz´am´ıtott e´ s szimul´aci´os eredm´enyek nagyon j´o azonoss´agot mutatnak. ¨ Osszehasonl´ ıt´o tesztek futtat´as´aval kimutattam, hogy az a´ ltalam javasolt algoritmus nagys´agrendekkel gyorsabban tudja meghat´arozni a sz¨uks´eges eredm´enyeket, mint a hagyom´anyos m´odszerek (l´asd. az 5.7 a´ bra). Az a´ ltalam kidolgozott algoritmus sz´am´ıt´as-ig´enye O(c) (ahol c a kioszthat´o IP c´ımek sz´ama), ´ıgy nagy sz´amu´ IP c´ımekkel gazd´alkod´o szervezetekben (pl. Internet szolg´altat´ok) val´o haszn´alatra k¨ul¨on¨osen alkalmas. 2.4. A vezet´ekn´elk¨uli h´al´ozatban haszn´alt v´ed˝ocsatorna mechanizmus elemz´es´ere, a Tran-Gia e´ s Mandjes a´ ltal javasolt modellt vizsg´altam. Arra a k¨ovetkeztet´esre jutottam, hogy a v´ed˝ocsatorna figyelembev´etele miatt kicsi e´ s nagy e´ rt´ekek egyar´ant szerepelnek a kivon´asi m˝uveleteket tartalmaz´o rekurz´ıv sz´am´ıt´asokban, aminek k¨ovetkezm´enyek´ent az a´ llapotval´osz´ın˝us´egek meghat´aroz´as´ara javasolt Tran-Gia e´ s Mandjes k¨ozel´ıt˝o rekurz´ıv m´odszer numerikusan nem stabil. A pontos matematikai modell kezelhetetlens´ege (mathematically intractable) miatt egy k¨ozel´ıt˝o modellt javasoltam. Levezettem, hogy egy v´ed˝ocsatorna alkalmaz´asa eset´en a k¨ozel´ıt˝o modell stacion´arius a´ llapotval´osz´ın˝us´egei a karakterisztikus m´atrix polinom k´et saj´at´ert´ek´evel, k´et saj´atvektor´aval e´ s megfelel˝o egy¨utthat´okkal kifejezhet˝oek (6.6 e´ s 6.7 k´eplet).
5
2.5. Bebizony´ıtottam, hogy a saj´at´ert´ekek a karakterisztikus m´atrix polinom LU-faktoriz´aci´oj´aban szerepl˝o L m´atrix f˝oa´ tl´oj´aban lev˝o utols´o k´et elem szorzat´anak gy¨okei a (0,1) intervalumban vannak. Ennek k¨ovetkezm´enyek´ent egy hat´ekony algoritmust (6.1 algoritmus) sz´armaztattam a k´et saj´at´ert´ek, k´et saj´atvektor, az egy¨utthat´ok meghat´aroz´as´ara e´ s az rendszer a´ lland´osult a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´ara. A k¨ozel´ıt˝o modell a´ llapotval´osz´ın˝us´egeinek meghat´aroz´as´ara kidolgozott algoritmus hat´ekonys´ag´at a pontosan le´ır´o szimul´aci´os modell a´ ltal szolg´altatott eredm´enyekkel vetettem o¨ ssze (6.3 t´abl´azat). A vizsg´alat megmutatja, hogy az eredm´enyek nagyon j´o azonoss´agot mutatnak. Az a´ ltalam javasolt megold´as e´ s a hagyom´anyos algoritmusok fut´asi idej´enek o¨ sszehasonl´ıt´as´aval megmutattam, hogy az a´ ltalam javasolt algoritmus nagys´agrendekkel gyorsabban tudja meghat´arozni a sz¨uks´eges eredm´enyeket mint a hagyom´anyos m´odszerek (6.4 t´abl´azat). Az a´ ltalam kidolgozott algoritmus egy darab v´ed˝o csatorna alkalmaz´asa eset´en sz´am´ıt´as-ig´enye O(c) (ahol c a csatorn´ak sz´ama), ´ıgy nagyobb kapacit´as´u vezet´ekn´elk¨uli h´al´ozatok m´eretez´es´ere k¨ul¨on¨osen aj´anlott. 2.6. Az M/M/c/N+c visszacsatol´asos e´ s u´ jrapr´ob´alkoz´asi sorban´all´asi sort vizsg´altam. Felismertem e´ s bebizony´ıtottam, hogy a karakterisztikus m´atrix polinomnak b(N + c + 2)/2c db nulla e´ rt´ek˝u saj´at´ert´eke van (7.1 t´etel). A Grassmann a´ ltal kidolgozott algoritmust m´odos´ıtottam a nulla e´ rt´ek˝u saj´at´ert´ek kezel´es´ere. Megmutattam, hogy az a´ ltalam m´odos´ıtott elj´ar´as nagykapacit´as´u rendszer eset´en a hagyom´anyos algoritmusokn´al gyorsabban tudja meghat´arozni a jellemz˝oket. 3. T´ezis: a CPP/M/c vak´aci´os sorban´all´asi modellel kapcsolatos eredm´enyek e´ s alkalmaz´asuk [26] A t´emak¨orrel kapcsolatos, jelen e´ rtekez´es 8. fejezet´eben megtal´alhat´o u´ j saj´at tudom´anyos eredm´enyeim a k¨ovetkez˝o pontokba foglalhat´ok o¨ ssze: 3.1. Bevezettem az u´ j CPP/M/c vak´aci´os sorban´all´asi modellt, amelynek seg´ıts´eg´evel a virtu´alis g´ep-szolg´altat´ok vak´aci´os alap´u karbantart´asi politik´aja elemezhet˝o. 3.2. Bebizony´ıtottam a rendszer stabilit´asi felt´etel´ere vonatkoz´o 8.1 t´etelt, ennek k¨ovetkezm´enyek´ent a vak´aci´os alap´u karbantart´asi politika a t´ulterhel´es vesz´elye n´elk¨ul alkalmazhat´o a virtu´alis-szerver szolg´altat´okn´al. 3.3. Levezettem a pontos k´epleteket a rendszer a´ lland´osult a´ llapot-val´osz´ın˝us´egeinek meghat´aroz´as´ara (8.7 k´eplet). 3.4. Megadtam a rendszer sztochastikus dekompozici´oj´ara vonatkoz´o 8.2 t´etel bizony´ıt´as´at.
6
4.
Az eredm´enyek hasznos´ıt´asa
Az e´ rtekez´es elm´eleti eredm´enyeinek k¨ul¨onb¨oz˝o val´os´agos probl´em´ak (OBS Optical Burst Switching, MPLS t¨obbutas forgalomir´any´ıt´as, vezet´ekn´elk¨uli technik´ak, Apache Web szerver, DHCP, MADCAP, virtu´alis szerverek karbantart´asi politik´aja, stb) elemz´es´ere val´o alkalmass´ag´at k¨ul¨onb¨oz˝o publik´aci´okban demonstr´altuk, amely munk´akban az igazi rendszerrel val´o o¨ sszevet´esre is ker¨ult a sor. Az eredm´enyek k¨ozvetlen¨ul felhaszn´alhat´ok az infokommunik´aci´os szolg´altat´asok hat´ekonys´ag´anak n¨ovel´es´ere.
Hivatkoz´asok [1] Jes´us R. Artalejo and Antonio G´omez-Corral. Springer-Verlag, Berlin Heidelberg, 2008.
Retrial Queueing Systems.
[2] R. Chakka. Spectral Expansion Solution for some Finite Capacity Queues. Annals of Operations Research, 79:27–44, 1998. [3] R. Chakka, T.V. Do, and Z. Pandi. Generalized Markovian queues and applications in performance analysis in telecommunication networks. In D. D. Kouvatsos, editor, the First International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs 03), pages 60/1–10, July 2003. [4] R. Chakka and P. G. Harrison. Analysis of MMPP/M/c/L queues. In Proceedings of the Twelfth UK Computer and Telecommunications Performance Engineering Workshop, pages 117–128, Edinburgh, 1996. [5] R. Chakka and P. G. Harrison. The Markov modulated CPP/GE/c/L queue with positive and negative customers. In Proceedings of the 7th IFIP ATM Workshop, Antwerp, Belgium, 1999. [6] R. Chakka and P. G. Harrison. A Markov modulated multi-server queue with negative customers - the MM CPP/GE/c/L G-queue. Acta Informatica, 37:881–919, 2001. [7] R. Chakka and P. G. Harrison. The MMCPP/GE/c queue. Queueing Systems: Theory and Applications, 38:307–326, 2001. [8] Ram Chakka. Performance and Reliability Modelling of Computing Systems Using Spectral Expansion. PhD thesis, University of Newcastle upon Tyne (Newcastle upon Tyne), 1995. P [9] Ram Chakka and Tien Van Do. The M M K k=1 CP Pk /GE/c/L G-Queue and Its Application to the Analysis of the Load Balancing in MPLS Networks. In 27th Annual IEEE Conference on Local Computer Networks (LCN 2002), 6-8 November 2002, Tampa, FL, USA, Proceedings, pages 735–736, 2002.
7
P [10] Ram Chakka and Tien Van Do. The MM K k=1 CP Pk /GE/c/L G-Queue with Heterogeneous Servers: Steady state solution and an application to performance evaluation. Performance Evaluation, 64:191–209, March 2007. [11] Ram Chakka and Tien Van Do. Some New Markovian Models for Traffic and Performance Evaluation of Telecommunication Networks. In D. D. Kouvatsos, editor, Next Generation Internet: Performance Evaluation and Applications, volume 5233. LNCS, 2009. [12] Ram Chakka, Tien Van Do, and Zsolt Pandi. A Generalized Markovian Queue and Its Applications to Performance Analysis in Telecommunications Networks. In D. Kouvatsos, editor, Performance Modelling and Analysis of Heterogeneous Networks, pages 371–387. River Publisher, 2009. [13] Ram Chakka, Enver Ever, and Orhan Gemikonakli. Joint-state modeling for open queuing networks with breakdowns, repairs and finite buffers. In 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 260–266. IEEE Computer Society, 2007. [14] Ram Chakka and Isi Mitrani. Multiprocessor systems with general breakdowns and repairs. In SIGMETRICS, pages 245–246, 1992. [15] Ram Chakka and Isi Mitrani. Heterogeneous multiprocessor systems with breakdowns: Performance and optimal repair strategies. Theor. Comput. Sci., 125(1):91–109, 1994. [16] Robert B. Cooper. Introduction to Queueing Theory. North Holland, New York . Oxford, 1981. [17] Tien Van Do. An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity. Applied Mathematical Modelling, http://dx.doi.org/10.1016/j.apm.2009.10.025. [18] Tien Van Do. An Efficient Computational Method for Retrial Queues to Cellular Mobile Systems with Guard Channels. submitted for publications, 2009. [19] Tien Van Do. Comments on multi-server system with single working vacation. Applied Mathematical Modelling, 33(12):4435–4437, 2009. [20] Tien Van Do. An Efficient Solution to a Retrial Queue for the Performability Evaluation of DHCP. Computers & OR, 37(7):1191–1198, 2010. [21] Tien Van Do. M/m/1 retrial queue with working vacations. Acta Informatica, 2010. [22] Tien Van Do and Ram Chakka. A New Performability Model for Queueing and FDL-related Burst Loss in Optical Switching Nodes. Computer Communications, 2009.
8
[23] Tien Van Do and Ram Chakka. Generalised QBD Processes, Spectral Expansion and Performance Modelling Applications. In D. D. Kouvatsos, editor, Next Generation Internet: Performance Evaluation and Applications, volume 5233. LNCS, 2009. [24] Tien Van Do, Ram Chakka, and Peter G. Harrison. An integrated analytical model for computation and comparison of the throughputs of the UMTS/HSDPA user equipment categories. In MSWiM ’07: Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, pages 45–51, New York, NY, USA, 2007. ACM. [25] Tien Van Do, Nam H. Do, and Ram Chakka. Performance evaluation of the high speed downlink packet access in communications networks based on high altitude platforms. In Khalid Al-Begain, Armin Heindl, and Mikl´os Telek, editors, ASMTA, volume 5055 of Lecture Notes in Computer Science, pages 310–322. Springer, 2008. [26] Tien Van Do and Udo R. Krieger. A performance model for maintenance tasks in an environment of virtualized servers. In IFIP/TC6 NETWORKING 2009, pages 931–942, Aachen, Germany, 5 2009. [27] Tien Van Do, Udo 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. [28] Tien Van Do, Denes Papp, Ram Chakka, and Mai X T Truong. A Performance Model of MPLS Multipath Routing with Failures and Repairs of the LSPs. In D. Kouvatsos, editor, Performance Modelling and Analysis of Heterogeneous Networks, pages 27–43. River Publisher, 2009. [29] Do Van Tien, Jakab Tivadar and Telek Mikl´os. New Services and ATM. Hungarian PTT Journal, May 1993. [30] Steve Drekic and Winfried K. Grassmann. An eigenvalue approach to analyzing a finite source priority queueing model. Annals OR, 112(1-4):139–152, 2002. [31] Enver Ever, Orhan Gemikonakli, and Ram Chakka. A mathematical model for performability of beowulf clusters. In Annual Simulation Symposium, pages 118–126. IEEE Computer Society, 2006. [32] Enver Ever, Orhan Gemikonakli, and Ram Chakka. Analytical modelling and simulation of small scale, typical and highly available beowulf clusters with breakdowns and repairs. Simulation Modelling Practice and Theory, 17(2):327–347, 2009. [33] Winfried K. Grassmann. The use of eigenvalues for finding equilibrium probabilities of certain markovian two-dimensional queueing problems. INFORMS Journal on Computing, 15(4):412–421, 2003. [34] Winfried K. Grassmann and Steve Drekic. An analytical solution for a tandem queue with blocking. Queueing System, (1-3):221–235, 2000.
9
[35] L. Kleinrock. On the modeling and analysis of computer networks. Proceedings of the IEEE, 81(8):1179–1191, August 1993. [36] Leonard Kleinrock. Queueing Systems. Vol I: Theory . John Wiley & Sons, Inc, 1975. [37] G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability, 1999. [38] Isi Mitrani. Approximate solutions for heavily loaded markov-modulated queues. Perform. Eval., 62(1-4):117–131, 2005. [39] Isi Mitrani and Ram Chakka. Spectral expansion solution for a class of Markov models: Application and comparison with the matrix-geometric method. Performance Evaluation, 23:241–260, 1995. [40] M. F. Neuts. Matrix Geometric Soluctions in Stochastic Model. Johns Hopkins University Press, Baltimore, 1981. [41] Papp D´enes and Truong Thi Xuan Mai and Do Van Tien. MPLS t¨obbutas elvezet´es teljes´ıt˝ok´epess´egi elemz´ese. Magyar T´avk¨ozl´es, May 2006. [42] L. Takacs. Introduction to the theory of queues. Oxford University Press, New York, 1962. [43] Hung Tuan Tran and Tien Van Do. Computational Aspects for Steady State Analysis of QBD Processes . Periodica Polytechnica, Ser. El. Eng, pages 179–200, 2000. [44] Y. Zhao and Winfried K. Grassmann. A numerically stable algorithm for two server queue models. Queueing Syst., 8(1):59–79, 1991.
10
¨ reprezentat´ıv A dolgozat t´emak¨or´eben k´eszult publik´aci´ok jegyz´eke Foly´oirat cikkek P [J1] R. Chakka and Tien Van Do. The MM K k=1 CP Pk /GE/c/L G-Queue with Heterogeneous Servers: Steady state solution and an application to performance evaluation. Performance Evaluation, 64:191–209, March 2007. (IF=0.616) [J2] Tien Van 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. (IF=0.40) [J3] Tien Van Do, R. Chakka. A New Performability Model for Queueing and FDL-related Burst Loss in Optical Switching Nodes, Computer Communications, accepted (IF=0.884∗ ) [J4] Tien Van Do. Comments on Multi-Server System with Single Working Vacation. Applied Mathematical Modelling 33 (12) (2009) 4435–4437. (IF=0.931*) [J5] Tien Van Do. An Efficient Solution to a Retrial Queue for the Performability Evaluation of DHCP. Computers and Operations Research 37(7):1191–1198, 2010. http://dx.doi.org/10.1016/j.cor.2009.05.014 (IF=1.366*) [J6] Tien Van Do. An Efficient Computation Algorithm for A Multiserver Feedback Retrial Queue With A Large Queueing Capacity Applied Mathematical Modelling. http://dx.doi.org/10.1016/j.apm.2009.10.025 (IF=0.931*) [J7] Tien Van Do. M/M/1 retrial queue with working vacations. accepted http://dx.doi.org/10.1007/s00236-009-0110-y
Acta Informatica,
(IF=0.789*) [J8] Tien Van Do. Modeling a Resource Contention in the Management of Virtual Organizations. submitted to Information Sciences [J9] Tien Van Do. An Efficient Computational Method for Retrial Queues to Cellular Mobile Systems with Guard Channels. Submitted for publications [J10] Tien Van Do and Ram Chakka. Simulation and Analytical Approaches for Estimating the Performability of a Multicast Address Dynamic Allocation Mechanism. Submitted for publications [J11] Tien Van Do and Ram Chakka. An Efficient Method to Compute the Rate Matrix for Retrial Queues with Large Number of Servers. Submitted for publications [J12] Tien Van Do and Ram Chakka and Nam H. Do. A Markovian Queue with Varying Number of Servers and Applications to Performance Analysis of Wireless Networks Submitted for publications ∗
IF of 2008
11
[J13] Tien Van Do. ”A Computational Algorithm for the CPP/M/c Retrial Queue. Annales Mathematicae Et Informaticae (1787-5021) (2009). [J14] Tien Van Do. The steady state analysis of the CPP/M/1 queue with working vacations. Submitted for publications
K¨onyvfejezetek [B1] D Papp, Tien Van Do, Ram Chakka, X M T Truong. Repair strategies on the operation of MPLS routing In: Nejat Ince, Arnold Bragg (szerk.) Recent Advances in Modeling and Simulation Tools for Communication Networks and Services. Berlin ; Heidelberg: Springer-Verlag, 2007. pp. 319-330. (ISBN:0387739076) [B2] Tien Van Do, Nam H. Do, and Ram Chakka. Performance evaluation of the high speed downlink packet access in communications networks based on high altitude platforms. In Khalid Al-Begain, Armin Heindl, and Mikl´os Telek, editors, ASMTA, volume 5055 of Lecture Notes in Computer Science, pages 310–322. Springer, 2008. [B3] Ram Chakka, Tien Van Do, and Zsolt Pandi. A Generalized Markovian Queue and Its Applications to Performance Analysis in Telecommunications Networks. In D. Kouvatsos, editor, Performance Modelling and Analysis of Heterogeneous Networks, pages 371–387. River Publisher, 2009. [B4] Tien Van Do, Denes Papp, Ram Chakka, and Mai X T Truong. A Performance Model of MPLS Multipath Routing with Failures and Repairs of the LSPs. In D. Kouvatsos, editor, Performance Modelling and Analysis of Heterogeneous Networks, pages 27–43. River Publisher, 2009. [B5] Tien Van Do and Ram Chakka. Generalised QBD Processes, Spectral Expansion and Performance Modelling Applications. In Next Generation Internet: Performance Evaluation and Applications edited by D. D. Kouvatsos, Lecture Notes in Computer Science, Vol. LNCS 5233, Springer-Verlag, Heidelberg, Germany ISBN: 978-3-540-99500-5 [B6] Ram Chakka and Tien Van Do. Some New Markovian Models for Traffic and Performance Evaluation Telecommunication Networks. In Next Generation Internet: Performance Evaluation and Applications edited by D. D. Kouvatsos, Lecture Notes in Computer Science, Vol. LNCS 5233, Springer-Verlag, Heidelberg, Germany ISBN: 978-3-540-99500-5
Konferencia cikkek [C1] H. T. Tran and Tien Van Do. A new iterative method for systems with batch arrivals and batch departures. In Proceedings of CNDS’00, pages 131–137, San Diego, USA, 2000.
12
[C2] Hung T. Tran and Tien Van Do. Comparison of some Numerical Methods for QBD-M Processes via Analysis of an ATM Concentrator. In Proceedings of 20th IEEE International Performance, Computing and Communications Conference, IPCCC 2001, Pheonix, USA, 2001. P [C3] Ram Chakka, Tien Van Do. The MM K k=1 CP Pk /GE/c/L G-Queue and its applications in load balancing of MPLS networks. In: IEEE LCN 2002 Conference., USA 2002., pp. 0735-0736. [C4] Ram Chakka, Tien Van Do, and Zsolt Pandi. Generalized Markovian queues and applications in performance analysis in telecommunication networks. In D. D. Kouvatsos, editor, the First International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs 03), pages 60/1–10, July 2003. [C5] Tien Van Do, R. Chakka, and P. G. Harrison. An integrated analytical model for computation and comparison of the throughputs of the UMTS/HSDPA user equipment categories. In MSWiM ’07: Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, pages 45–51, New York, NY, USA, 2007. ACM. [C6] Tien Van Do and Udo R. Krieger. A performance model for maintenance tasks in an environment of virtualized servers. In IFIP/TC6 NETWORKING 2009, pages 931–942, Aachen, Germany, 5 2009.
Egy´eb foly´oirat cikkek [J14] M Ajmone Marsan, A Bianco, T V Do, L Jereb, R Lo Cigno, M Munafo. ATM Simulation with CLASS. Performance Evaluation 24:(1-2) pp. 137-159. (1995) (IF: 0.513) [J15] Tien Van Do, Thong T Nguyen, Hung T Tran, G Kalvach, B Varga. Topology Optimization of an Overlay ATM Network in an SDH Infrastructure. Computer Networks. 34:(1) pp. 199-210. (2000) (IF: 0.390)
13
