Nagy kommunikációs igényű elosztott alkalmazások dinamikus elhelyezése a hálózaton Goldschmidt Balázs és László Zoltán Budapesti Műszaki és Gazdaságtudományi Egyetem Irányítástechnika és Informatika Tanszék {balage,laszlo}@iit.bme.hu
Absztrakt Az online multimédia letöltések igényének növekedtével egyre fontosabbá válnak a dinamikus adaptációra képes elosztott multimédia rendszerek. Ezeknek a rendszereknek meg kell oldaniuk a komponensek megfelelő elhelyezését, migrációját, amely képes a kliensek QoS igényeit a lehető legjobban kielégíteni. Jelen cikkben javaslatot teszünk a klienskérések költségének kiszámítására, illetve ezen eredmények felhasználásával egy elhelyezés-ajánló részecske-raj algoritmusra. Az algoritmust összehasonlítjuk a hasonló problémáknál sikeresen alkalmazott mohó algoritmussal.
Bevezető Az Internet robbanásszerű terjedésének köszönhetően gyorsan nő az igény az online tartalomszolgáltatásra: a hagyományos tartalomhordozók (CD, DVD, VC) helyébe egyre inkább a "letöltés" lép. Az olyan alkalmazásokban, ahol a felhasználó valós idejű követelményeinek kielégítését korlátozza az erőforrások szűkössége, az adaptáció különösen fontossá válik. Ilyen alkalmazásnak tekinthetők az elosztott multimédia különösen a mozgóképet kezelő - rendszerek.[1,2] A szerzők részvételével korábban kidolgozott és megvalósított rugalmas architektúrájú rendszer képes a hálózaton új szerver számítógépek lefoglalására, majd programok és adatok ezekre igény szerint történő átküldésére.[3] A megfelelő hosztok keresése alapvetően NP-nehéz kombinatorikus optimalizálási feladat. Jelen cikkünkben két, a probléma megoldására szolgáló algoritmust vizsgálunk meg, illetve javaslatot teszünk a klienskérések költségének kiszámítására.
A probléma A vizsgált feladat a Klagenfurti Egyetemen kidolgozott ADMS rendszerhez kötődik.[4] Az ADMS egy elosztott, adaptív multimédia rendszer, amelynek a vizsgált probléma szemszögéből a következő két komponense van (lásd az 1. ábrát): •
•
Data Manager (DM): feladata a multimédia adatok (jelenleg videók) tárolása ún. stripe unitok formájában. Ez azt jelenti, hogy terheléskiegyenlítési megfontolásokból a videót kisebb szeletekre (stripe unit) szedjük szét, és ezeket a szeleteket viszonylag közel elhelyezkedő számítógépeken tároljuk. Mikor a videót le kívánjuk tölteni, több géptől is gyűjtünk szeleteket, így egyrészt a gépek egyenletesen lesznek terhelve, másrészt a divatos filmek is egyenletesen lesznek elosztva a gépek között. Data Collector (DC): a szeletek összegyűjtését végzi. Mikor egy kliens meg
szeretne nézni egy filmet, egy Data Collector fogja összeszedni a kellő szeleteket, majd összefűzve egységes adatfolyamként a kliensnek (C) elküldeni.
1. ábra ADMS rendszer felépítése
A komponensek a szerzők részvételével kifejlesztett Vagabond2 rendszert futtató tetszőleges gépre dinamikusan telepíthetőek. A dinamikus áthelyezés előnyeit azonban csak akkor tudjuk kihasználni, ha tudjuk, hogy melyik komponenst hova kell telepíteni: ez a Host Recommender (hoszt ajánló) modul feladata. A modulnak a következő információkra van szüksége: •
• •
Hálózati topológia. A hálózatot az ADMS Hálózatfelügyelő Alrendszere monitorozza, és állítja elő a hálózat felépítését és statisztikai jellemzőit leíró adatokat. Ezek tartalmaznak jövőre vonatkozó becsléseket is, hiszen a kliensek kérései is a jövőre vonatkoznak (pl. “jövő szerdán este meg szeretném nézni a Gyűrűk Urát”). Komponensek elhelyezkedése. Szükség van arra, hogy tudjuk, melyik komponens melyik számítógépen helyezkedik el, és hogy melyik Data Manager melyik film szeleteit tárolja. Kliensek igényei. Minden klienshez szükség van a kliens szolgáltatásminőségi igényeinek meghatározására, az általa elfogadott legrosszabb minőségtől addig a maximális minőségig, amit az általa használt eszközök megengednek. Ezt egy QoS igény listával adjuk meg. Ennek utolsó, alapértelmezett eleme azt jelenti, hogy a klienst elutasítjuk. Szükség van továbbá arra is, hogy tudjuk, mikor melyik filmet szeretné látni, és ő maga a hálózaton hol helyezkedik el.
A fenti információk alapján a hoszt ajánló modulnak javaslatot kell tennie arra, hogy (egyelőre) hova érdemes Data Collectort telepíteni, és hogy melyik kliens melyik Data Collectorral, melyik Data Collector melyik Data Managerrel álljon kapcsolatban. Egy ilyen kiosztást nevezünk konfigurációnak. A hálózati modell a következő egyszerűsítésekre épül. A hálózatot egy olyan gráfnak tekintjük, amelyen a csomópontok area-kat reprezentálnak. Az area lehet alhálózat (LAN), router vagy backbone kapcsolat. A csomópontok közötti élek a routerek és a hozzájuk csatlakozó alhálózatok/linkek kapcsolatai. A magyarázat egyszerű: egyrészt a hosztok alhálózaton belüli elhelyezkedése számunkra irreleváns, másfelől a routerek az alhálózatokhoz hasonló jellemzőkkel bírnak (pl. sávszélesség, késleltetés stb.). Ahhoz, hogy az algoritmusokat össze tudjuk hasonlítani, szükség van egy költségfüggvényre, amely egy adott bemeneti problémára (konkrét hálózati topológia, kliensek kérései, DC és DM elhelyezkedések) megadja, hogy két konfiguráció közül melyik a jobb. Az itt használt költségfüggvény egy adott konfigurációra ad egy költséget,
amit azután más konfigurációk költségeivel tudunk összehasonlítani. A számított költség tartalmazza a teljes hálózati terhelést, a túlterhelést (amikor egy adott area-n nagyobb sávszélességet kívánunk igénybe venni, mint amennyi rendelkezésre áll), a visszautasított kliensek számát (akiket nem tudunk kiszolgálni), a lineáris rosszaságot (a kliensek elfogadott igényei sorszámainak összege) és az exponenciális rosszaságot, amelyet így definiáltunk:
∑2
ic
c∈C
ahol C a kliensek halmaza, ic a c kliens választott igényének sorszáma. Ez utóbbi metrika abban segít, hogy előnyben tudjuk részesíteni az 'egyenlőbb' igényelosztást az 'elitistával' szemben. A költség kiszámítása során minden klienshez lefoglaljuk a klienstől a hozzá választott DC-ig tartó útvonalon szereplő areákon az igényelt QoS-t. Ezután minden felhasznált DC-től a hozzá rendelt DM-ig tartó útvonalon szereplő areákon a DC által kielégítendő legnagyobb QoS-t. A kapott foglalásokat és túlfoglalásokat külön-külön összeadjuk. Két költség esetén az a kisebb, amelyiknél (csökkenő fontossági sorrendben): • • • •
kevesebb a túlfoglalás (ezt nem engedhetjük meg) kevesebb a visszautasított kliensek száma (minél több klienst szeretnénk elfogadni) kisebb az exponenciális rosszaság (szeretnénk az átlagos megelégedést növelni) kevesebb a teljes foglalás (csökkenteni szeretnénk a hálózat terheltségét)
Az algoritmusok A cikkben két algoritmust mutatunk be, egy mohó és egy részecske-raj alapút.
Mohó A felhasznált mohó algoritmus lényegében azonos azzal, amit [5]-ben már bemutattunk. A különbség az, hogy az eredeti költségfüggvényt lecseréltük a fentire, és az algoritmus most már figyelembe veszi a kliensek igénylistáit is.
Részecske-raj A részecske-raj algoritmus Kennedy és Eberhardt algoritmusán alapul [6]. Az eredeti változat részecskék egy halmazát használja, amelyek mindegyike egy konkrét konfigurációt ír le. Az egyes részecskék egy adott topológiát képezve egymáshoz vannak kapcsolva. A részecskéket véletlen értékekkel inicializáljuk. A részecskék emlékeznek saját legjobb múltbeli konfigurációjukra (bp), és tudják, hogy szomszédaik közül (saját magukat is beleértve) ki adja a legkisebb költségű konfigurációt (b n). Minden körben a részecskék kiszámítják az új konfigurációjukat bp és bn kombinálásával, amiben valószínűségi értékeket használnak fel. Az algoritmus addig fut, amíg valamilyen feltételt el nem érünk.
Az eredeti kombináció definíciója: x(t + 1) = x(t ) + ϕ1 (b p − x(t − 1)) + ϕ2 (b n − x(t − 1)) ahol ϕi a [0,1) intervallumból vett véletlen szám. Az eredeti algoritmus azonban csak azokat a problémákat tudja megoldani, ahol a konfigurációkban használt dimenziók bináris vagy valós értékeket vehetnek fel. Ez az alkalmazott lineáris kombináció következménye. A mi esetünkben azonban a dimenziók olyan halmazokból veszik értékeiket, amelyeken a rendezés nincs értelmezve, emiatt a lineáris kombináció sem jöhet szóba. Ehelyett a következő kombinációt alkalmazzuk: minden dimenzióhoz elsőnek véletlenszerűen választunk x(t)-ből vagy bn-ből (kereszteződés). Azután, egy másik valószínűséggel, ezt az értéket egy a megfelelő halmazból (S) vett véletlen értékre (e) cseréljük (mutáció). bni if ϕ1 ≤ p1 if ϕ 2 ≤ p 2 (kereszteződés) xi (t + 1) = xi (t ) if ϕ1 > p1 e∈S if ϕ 2 > p 2 ( mutáció) A 2. ábrán egy egyszerű példát mutatunk be. A raj négy részecskéből áll, amelyek gyűrű topológiába vannak szervezve. A probléma DC ajánlása két kliens számára. Három DC jelöltünk ({a,b,c}) és öt DM-ünk ({f,g,h,i,j}) van, és minden kliensnek van hat QoS igénye. Minden részecske egy hétdimenziós konfigurációt ír le. Az első két dimenzió adja meg a kliensekhez kijelölt DC-ket, a következő két dimenzió az elfogadott QoS igények sorszámát írja le, a maradék három dimenzióban adjuk meg az egyes DC jelöltekhez rendelt DM-eket. A költségek relációit a részecskék közötti kapcsolatokon jelöljük. Minden p részecske kombinálódik a legkisebb költségű q szomszédjával, ha q költsége kisebb, mint p költsége. A példán a P1 és P2 részecske kombinációja látszik. Először minden dimenzióhoz generálunk egy véletlen értéket a [0,1) intervallumból, és amelyik a p 1=0,2 határ alatt van (a példán keretezve), annak a dimenziónak az értékét P2-től vesszük. Egyébként az érték nem változik. Így kapjuk a kereszteződés eredményét. Ezután minden dimenzióhoz generálunk egy véletlen értéket a dimenzió értékkészletéből, valamint egy véletlen értéket a [0,1) intervallumból. Ha ez utóbbi a p2=0,2 határ alatt van (a példán keretezve), akkor az adott dimenziónál az új, véletlen értéket vesszük, egyébként pedig változatlanul hagyjuk a fent kapottat. Így kapjuk a mutáció eredményét, ami a részecske számára az új konfiguráció lesz. Egy iteráció során minden részecskén lefuttatjuk az eljárást. A kereszteződés és a mutáció a genetikus algoritmusokban is megjelenik [7]. A különbség köztük és a jelen cikkben bemutatott algoritmus között az, hogy a mi esetünkben a részecskék közötti kapcsolat (ki kivel kombinálódik) statikus. A részecskék csak kijelölt szomszédaikkal kereszteződnek, és a kereszteződés az alacsonyabb költségűtől a magasabb felé továbbít információt. Így a legjobb eredmények mindig megőrződnek.
(1) Kezdő konfiguráció négy részecskével (P1, P2, P3, P4, gyűrű topológiába kapcsolva). A költség-összehasonlítások a kapcsolatokon lettek feltüntetve. A DC jelöltek halmaza {a,b,c}, az igényeké {0,1,2,3,4,5,6}, a DM-eké {f,g,h,i,j}.
1. kliens DC-je 2. kliens DC-je 1. kliens igénye 2. kliens igénye a DC jelölt DM-je b DC jelölt DM-je c DC jelölt DM-je
<
a b 2 3 h j f P1
b c 1 3 f h i P2
>
c a 2 4 f j j P3
<
b a 1 4 i g j
<
<
P4
(2) Kombináció (csak P1×P2 lett bemutatva, a vektorokat transzponáltuk, a bekeretezett számok a határérték alattiak): 1. részecske (P1)
a
b
2
3
h
j
f
2. részecske (P2)
b
c
1
3
f
h
i
Véletlen φ 1 értékek a kereszteződéshez
0,16
0,87
0,79
0,18
0,45
0,96
0,23
Kereszteződés eredménye
b
b
2
3
h
j
f
Véletlen értékek a mutációhoz
c
a
4
2
g
h
i
Véletlen φ 2 értékek a mutációhoz
0,31
0,23
0,74
0,45
0,02
0,63
0,73
Mutáció eredménye
b
b
2
3
g
j
f
(3) Következő konfiguráció
1. kliens DC-je 2. kliens DC-je 1. kliens igénye 2. kliens igénye a DC jelölt DM-je b DC jelölt DM-je c DC jelölt DM-je
>
b b 2 3 g j f P1
>
b c 1 3 f h i P2
<
b a 2 2 f j g P3
<
P4
2. ábra Swarm algoritmus példa
a a 1 3 h g j
>
Az algoritmus addig fut, amíg minden részecske azonos költséggel nem rendelkezik. Ez a feltétel azonban a mutációval kombinálva a kezdeti gyors evolúciótól egy végső fluktuációhoz vezet. Néhány részecske megpróbálja elérni a legjobbak költségét, de a mutációk során valami mindig megváltozik, ami megakadályozza a konvergenciát. Ennek a jelenségnek az elkerülésére a mutációs ráta (p 2) szimulált lehűtését alkalmazzuk [8]. A lehűtést vezérlő változó a legutóbbi iterációban megváltozott részecskék száma. Minél kevesebb részecske változik, annál kisebb a mutációs valószínűség. Az algoritmus maga a következő kontrollparaméterekkel rendelkezik: •
részecskék száma: minél több részecskénk van, annál jobb eredményt érhetünk el, de a sebesség is egyre kisebb lesz. A futási idő görbéje a részecskék számának függvényében lineáris, míg a megoldások költségfüggvénye körülbelül 100 részecskénél törik. Emiatt ezt a paramétert 100-nak vettük. • rajtopológia: a végtelen számú lehetséges topológia közül mi kettőt hasonlítottunk össze: a tóruszt (minden részecske négy szomszédját ismeri) és a gyűrűt (minden részecske két szomszédját ismeri). Az előbbi gyorsabb volt, de a megoldásai egy nagyságrenddel rosszabbak voltak, mint az utóbbié. Az ok egyszerű: a tóruszban az információ gyorsabban terjed, ez azonban megöli a kis hibás, de később jobb eredményt szülő konfigurációkat. Mi a gyűrű topológiát választottuk. • kereszteződés valószínűsége: a mérések hasonló eredményt adnak, mint a részecskék száma esetén. Az optimális pont 0,2 körül van. • mutáció valószínűség-függvénye: a korábbi megfontolások miatt nem választhattunk konstans függvényt. A megvizsgált függvények közül a legjobb eredményt a Pm (c) = 0,2 c / N függvénnyel értük el, ahol c a legutóbb megváltozott részecskék száma, N az összes részecske száma.
3. ábra Mérési eredmények
Az eredmények értékelése A két algoritmus mérési eredményeit a 3. ábra mutatja. Ebből jól látszik, hogy a mohó algoritmus, amely más, hasonló esetekben jól bevált [9], itt rosszabb eredményeket ad, és sokkal hosszabb idő alatt, mint a részecske-raj algoritmus. Minden mért érték a mohó esetén többszöröse a raj által ajánlottnak. A jövőben célunk, hogy ne csak a hálózat, hanem az egyes csomópontok jellemzőit is figyelembe vegyük az ajánlások készítése során. Ez a mohó algoritmus esetén az algoritmus átdolgozását igényelné, míg a raj esetén csak a költségfüggvényt kell kiegészíteni, minden mást változatlanul lehet hagyni. Hosszabb távon szeretnénk az alapprobléma egy általános leírását megadni, amivel lehetőség nyílna arra, hogy egy konkrét probléma absztrakt leírásából a megoldást kiszámító költségfüggvényt és részecske-felépítést automatikusan állítsuk elő.
Hivatkozások [1] http://developer.apple.com/darwin/: Darwin project homepage (2004) [2] https://www.helixcommunity.org/: Helix project homepage (2004) [3] Goldschmidt, B., Tusch, R., Boszormenyi, L.: A mobile agent-based infrastructure for an adaptive multimedia server. In: 4th DAPSYS (Austrian-Hungarian Workshop on Distributed and Parallel Systems), Kluwer Academic Publishers (2002) 141–148
[4] Tusch, R.: Towards an adaptive distributed multimedia streaming server architecture based on service-oriented components. In Böszörményi, L., Schojer, P., eds.: Modular Programming Languages, JMLC 2003. LNCS 2789, Springer (2003) 78–87 [5] Goldschmidt, B., László, Z.: A proxy placement algorithm for the adaptive multimedia server. In: 9th International Euro-Par Conference. (2003) 1199–1206 [6] Kennedy, J., Eberhardt, R.C.: Swarm Intelligence. Morgan Kaufmann (2001) [7] Davis, L., ed.: Handbook of Genetic Algorithms. Van Nostrand Reinhold (1991) [8] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science, Number 4598, 13 May 1983 220, 4598 (1983) 671–680 [9] Li, B., Golin, M., Italiano, G., Deng, X., Sohraby, K.: On the optimal placement of web proxies in the internet. In: Proceedings of the Conference on Computer Communications (IEEE Infocom). (1999)
