Megkülönböztetett kiszolgáló routerek az

Megkülönböztetett kiszolgáló routerek az Interneten

Megkülönböztetett kiszolgáló routerek az Interneten ■ Megkülönböztetett kiszolgálás ◆ A kiszolgáló architektúrák minősége az Interneten: ➤ Integrált kiszolgálás (IntServ) ➤ Megkülönböztetett kiszolgálás (DiffServ)

◆ DiffServ: Különböző csomagfeldolgozás az IP-fejléc csomagjelölése alapján (DS-mező) ◆ A komplexitást kivinni a külső routerekhez és a feldolgozást a központi routereknél, amennyire lehet, leegyszerűsíteni ◆ Csomagjelölés és megjegyzés végrehajtása: külső routereknél (előfizetők között), határ routereknél (szolgáltatói tartományok között) és alkalmazásoknál Performance Modelling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg

Számítógép-rendszerek hatékonyság-elemzése Sztrik János, Baják Szabolcs • Debreceni Egyetem, Informatikai Kar

.1


■ Arányos megkülönböztetett kiszolgálás: ◆ A kiszolgálás megkülönböztetésének két megközelítése: ➤ Abszolut megkülönböztetett kiszolgálás: garanciát és statisztikai

biztosítékokat nyújt a hatékonyságjellemzőkre, pl.: E2E delay ➤ Relatív megkülönböztetett kiszolgálás: forgalmi osztályok rendezése a

csomagtovábbító viselkedésük alapján ◆ Arányos megkülönböztetett kiszolgálás: ➤ a relatív megkülönböztetett kiszolgálás további finomítása ➤ meghatározza a forgalmi osztályok közötti távolságokat

◆ Lehetséges megkülönböztetési szempontok: ➤ áteresztőképesség ➤ késleltetés ➤ zaj ➤ veszteségi ráta

Performance Modelling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


.2


■ Arányos késleltetési megkülönböztetés: ◆ N forgalmi osztály definiált ◆ Megkülönböztetési szempont: sorbanállási késleltetés ◆ Definíció az egymást követő osztályok átlagos késleltetésének arányaira:

Æ Æ

◆ Osztálymegkülönböztető paraméterek (késleltetési megkülönböztető paraméterek/delay differentiation parameters: DDP) δ1 > δ2 > .... > δΝ hogy a magasabb osztályok "jobbak" legyenek az alacsonyabb osztályoknál Performance Modelling of Computer Systems  Gunter Bolch • Universität Erlangen-Nürnberg


.3


■ Dinamikus ütemező modell ◆ Prioritásfüggvény

Priority

qr (t)

qr (t)

qr (t) = (t − t0 ) · br

0 ≤ b1 ≤ b2 ≤ . . . ≤ br t0

t0

t

➤ A sorbanállási rendszerben egy r-osztályú csomag prioritása lineárisan nő

az idő előrehaladtával, br arányban



.4


◆ Átlagos várakozási idő:

r−1 W0 bi − ρi W i 1 − 1−ρ br i=1 Wr = R br 1− ρi 1 − bi i=r+1

◆ Kiterjesztett prioritásfüggvény: ➤ függ a mindenkori ρi terheléstől ➤ függ a késleltetési megkülönböztető paraméterektől (DDP-k) δi

Ö

¼ Ö ½ Ê Æ½ ÆÊ



.5


■ Dinamikus prioritásos ütemezési architektúra



.6


■ Optimalizációs probléma: ◆ R forgalmi osztály ◆ Adott DDP-k: δ1 > δ2 > ... > δR ◆ Mért osztály kihasználtságok: ρ1 > ρ2 > ... > ρR ◆ Ideálisan:


◆ Vagy:

Æ

Æ

Æ

Æ


.7


■ Példa két forgalmi osztályra: ◆ Pontos alak a prioritásfüggvények meredekségeinek kiszámolására:

½ ½

¾

Æ¾ Æ½

◆ Megvalósíthatóság:

½

Æ¾ Æ½

◆ Határ: Ahogy a terhelés közeledik a 100%-hoz, az ütemezési paraméterek aránya: b1/b2 a DDP-k reciprokához tart: δ2/δ1



.8


■

Optimalizálás genetikai algoritmusok használatával ◆ A Genetikai Algoritmusok (GA) optimalizáló és keresési eljárások, melyek létrejöttét a genetika és a természetes kiválasztódás folyamata ösztönözte ◆ A genetikai algoritmusok struktúrája ➤ Egyedek populációjának véletlenszerű generálása (bitfüzér). ➤ Minden egyed dekódolása és alkalmasságának kiértékelése. ➤ Új populáció generálása a legalkalmasabb egyedekből részben

klónozással, részben kombinálással és részben mutációval. ➤ A 2-es és 3-as lépések ismétlése egy megállási feltétel teljesüléséig.



.9


■ Példa: 4 forgalmi osztály, szükséges késleltetési arány: 2 ◆ Ütemezési Paraméterek: b1, b2, b3, b4



.10


◆ Átlagos késleltetések és késleltetési arányok



.11


■ Implementáció ◆ Az ütemezési paraméterek offline számolása ◆ Dinamikus utánállítás a router futási idő alatti műveletei során ◆ Utánállítás: ➤ Referenciatáblák: a kihasználtsági értékek intervallumai számára előre

meghatározott értékek halmaza --> diszkretizációs hiba ➤ Egyszerű interpolációs függvények használata

◆ Utánállítás indítása: ➤ Periodikusan ➤ Meghatározott eseményekkor: egy vagy több forgalmi osztály esetén

felmerülő jelentős kihasználtság-változásnál



.12


■ Más prioritásfüggvények kipróbálása ◆ Motiváció ➤ Hatékonyságvizsgálat az alacsony kihasználtságok (főleg 70% körüli)

esetén más prioritásfüggvények használatával ➤ Kezdeti prioritások használata jobban teljesítheti az arányos

megkülönböztetés követelményeit, mivel a beérkező csomagok kezdetben meghatározott prioritása nagyobb mint nulla ◆ Prioritásfüggvény kezdeti prioritásokkal ➤ Nagyobb optimalizálási hiba (részben az approximációs formulák

következtében) ◆ Négyzetes prioritásfüggvények ➤ Nincs számottevő javulás lineáris prioritásfüggvényekkel összehasonlítva



.13

Befejezés

Befejezés ■ A Dinamikus prioritásos ütemezés megközelítése ◆ Nagy és közepes terhelési feltételek esetén is jól alkalmazható

◆ Az ütemezési paraméterek offline meghatározása és referenciatáblák vagy egyszerű interpolációs függvények a futási időben ◆ Genetikai algoritmusok használata az optimalizálásra

■ A jelenlegi kutatás: ◆ Szimuláció a kapott eredmények helyességének bizonyítására ◆ A végtelen puffer approximáció és exponenciális eloszlás hatása ◆ Új Internet forgalommodellező módszerek további meggondolása (Önhasonló forgalom, Pareto eloszlás) ◆ Optimalizálás nemexponenciális eloszlások szimulációjával



.14

Megkülönböztetett kiszolgáló routerek az

Recommend Documents