SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMATÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME Minőségbiztosítás IP hálózatokon (vitt9181) Az IP minőségbiztosítás alapvető építőkockáiNémeth Felicián, nemethf@tmit.bme.hu TÁVKÖZLÉSI...
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME |
Minőségbiztosítás IP hálózatokon (vitt9181) |
Az IP minőségbiztosítás alapvető építőkockái |
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM |
2005. szeptember 27. kedd 1 |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME |
Források » Xxxxxxxxx Xxxxxxxx. Quality of Service in IP Networks: Foundations for a Multi-Service Internet. Macmillan Technical Publishing, apr. 2000. ISBN 1-57870-789-9 » Xxxxx Xxxx. Internet QoS: Architectures and Mechanisms for Quality of Service. Xxxxxx Xxxxxxxx Publishers, ISBN 1- 55860-608-4 » Xxx-Xxx Xx and Xxxx Xxxxxxxx. An Architectural Framework for Support of Quality of Service in Packet Networks. In IEEE Communications Magazine, pp 98-105, june 2003, 41(6). » X. Xxxxx. Service disciplines for guaranteed performance service in packet-switching networks. In Proceedings of the IEEE, pp 1374--96. 1995, 83(10). |
2 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd |
Architecture Components of IP QoS Feasible Technology Quality of Service • delay/delay variation • packet loss • accessibility Mechanisms Traffic & Network • classification Management • policing / marking • performance measurement • shaping • traffic monitoring • buffer management • traffic engineering • RED Viable Business Model |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
3 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Az IP QoS felépítése, főbb területei (elsősorban gazdaságossági megközelítésből)
- Quality of Service: Szolgáltatás minőség
Ez, és konkrét paraméterei mondják meg, hogy a hálózat mit képes nyújtani, illetve, hogy mi mit várunk el az átviteltől.
- Traffic & Network Management: Forgalom és hálózat menedzsment
Elsősorban a hálózat szervezését végzi. Ehhez eszköze lehet, pl.: a makró funkciók tervezése és végrehajtása.
traffic engineering: forgalom tervezés
útválasztás, stb. globális meghatározása, valamint a meglévő eszközökkel való minőség biztosítás.
- Mechanisms:
shaping: formázás, pl.: forgalomformázás (ld.: később)
RED: népszerű eszköz, aktív sormenedzsmentet tesz lehetővé (később bővebben lesz róla szó)
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
4 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Management
plane
Az IP QoS szerkezete, réteg-felépítése
Ez a fólia azon lépéseket, építőelemeket tartalmazza, melyek ahhoz kellenek, hogy a hálózaton lehessen QoS t biztosítani. Vezérlési sík (Contol plane):
- hívás beengedés (Admission Control): az a fogalom azt a folyamatot jelenti, amikor egy bejelentkező felhasználó jelzi, hogy ő egy bizonyos minőségű átvitelt szeretne folytatni a hálózaton, s ezután a hálózat kétféleképpen dönthet:
a., vagy megadja neki a kért szolgáltatást
b., vagy jelzi, hogy nem képes rá, és ezzel elutasítja a kérelmét
(ilyen a PSTN-nél (hagyományos telefonhálózatnál) a fogalt, vagy tárcsa hang is.)
- QoS útvonalválasztás (QoS routing): annyiban tér el a hagyományos útvonalválasztástól, hogy míg az a cél felé vezető következő csomópont kiválasztásáért felel, addig a QoS útvonalválasztás feladata ennél szélesebb körű, neki a hálózat egészét ismernie kell, állapotával, aktuális hívásengedélyezésével, stb. együtt, hogy lehetőleg globális szempontból jobb útvonalat választhasson, mint ahogy azt e nélkül tenné.
- Erőforrás foglalás (Resorce Reservation) Egy adott útvonalon a továbbításhoz szükséges erőforrások foglalását végzi (memória, sávszélesség, buffer, stb.), amely foglalást már a hívás beengedésekor elvégez, ezzel biztosítva, hogy amíg a kapcsolat él, addig az átviteli minőség kielégíthető lesz.
Menedzsment sík (Management plane):
- mérések (metering): méréseket végez a hálózati forgalommal kapcsolatban. Fontos, mert ennek segítségével tud beavatkozni, illetve mindenféle rendellenes viselkedést érzékelni. Továbbá ennek segítségével, mérési adatai alapján történik a számlázás is.
- hibák utáni helyreállítás (Service Restoration): meghibásodás után helyreállítja a hálót és az azon futó szolgáltatásokat.
- SLA (Service level agreement): Mintegy a felhasználó és a hálózat közötti szerződésként fogható fel. Specifikálja: a minőségi garanciákat
a forgalom méretét
a felhasználó által a szolgáltatásért fizetendő díjat
pl.: a hálózat 1%-os hibavesztést garantál, ha a felhasználó álltal igényelt sebesség nem nagyobb, mint 25 kbit/s
- irányelvek (policy): például a forgalom kategorizálására, vagy teendőket tartalmazhat arra az esetre, ha a felhasználó megszegi az SLA- ban foglalt paramétereket.
Adat sík (Data plane) – főleg ezzel fogunk foglalkozni:
- várakozási sor menedzsment ( Buffer management ): ez hagyományosan egy FIFO (First In First Out) elven működő várakozási sor. Itt gyűlnek a kiszolgálásra váró csomagok, amelyeket érkezési sorrenben továbbítunk, amennyiben rájuk kerül a kiszolgálás.
Módosítható, kérdés, hogy milyen módosítás a célra vezető. Egy elég kézenfekvő módosítás lehet, hogy prioritásos sorokat hozunk létre,
így a magasabb prioritású csomagokat (érkezéstől függetlenül) előbb szolgáljuk ki, mint az alacsonyabb prioritásúakat.
- torlódáskezelés (Congestion avoidance): azt az esetet szabályozza, ha forgalmi túlterhelés alakul ki. Pl.: egy routerhez hosszabb távon is több csomag érkezik, mint amit ki tud szolgálni, illetve el tud tárolni a buffer-jében. Az ilyen esetekben szükséges teendőket írja le.
- csomag megjelölés (packet marking): pl.: ha valaki túllépi a SLA-ban foglalt adási sebességet, akkor még nem kell feltétlenül eldobnunk a (SLA-ban megszabott határon túli) csomagjait, egy lehetőség, hogy csak megjelöljük őket (azaz nagyon kis prioritásúra állítjuk át őket) és csak akkor kerülnek hátrányos helyzetbe, ha valahol feltétlenül csomagokat kell eldobni.
- várakozási sor és ütemezés (Queuing and scheduling): a várakozási sor menedzsmenthez kapcsolódik.
- forgalomosztályozás (Traffic classification): egy IP csomag egy (vagy több?) osztály tagja lehet, s ez az osztályba tartozás megszabja, hogy hogyan kell kezelnünk (SLA-ban lefektethető).
- forgalomformázás (Traffic shaping): adott forgalmi mintával rendelkező adatfolyamra más mintát kényszerítünk.
pl.: ingadozó adatsebesség esetén (burstök, stb.) ezzel elérhető, hogy ezt az ingadozást kisimítsuk. (csúcssebesség ezzel kordában tartható)
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Általános követelmények » Létezzen megvalósítás, amely » egyszerű, » skálázható, » nagy sebességgel működőképes » Egy ütemező hiába triviális, ha NP-nehéz CAC tartozik hozzá » DiffServ követelmény: » csak aggregált állapotváltozók a hálózat belsejében » Gerinchálózati követelmény: » lehetőleg még aggregált sem » IP hálózat alapvetően kapcsolat- és állapotmentes, ellentétben az áramkörkapcsolt PSTN-nel. |
5 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Általános követelmények
Skálázhatóság fontos, hogy az architektúra megváltoztatása nélkül kellően nagy forgalmat is le tudjunk kezelni.
IntServ elképzelés: Lényege, hogy minden folyamatra (kapcsolatra) különböző minőségi elvárások teljesülhessenek. De ez a megoldás sajnos NEM volt SKÁLÁZHATÓ.
DiffServ elképzelés: Nem a kapcsolatokra fogalmazunk meg követelményeket, hanem azokat osztályokba soroljuk, és ezekre az osztályokra írunk elő feltételeket.
Ha egy csomag már osztályba van sorolva, akkor már csak ez alapján kell különbséget tennünk. Olyan algoritmusokat tesz lehetővé, ahol nem kell folyam szintű információt nyilván tartanunk, csak osztály szintűt.
DiffServ követelmény: Szinte már az osztály szintű megjelölés sem alkalmazható olyan nagy sebességnél, amilyen sebességgel a hálózat belsejében található csomópontok dolgoznak.
Elképzelés: hogy az IP hálózatokat visszavezethetnénk a PSTN (hagyományos telefon) hálózatokra, onnan újra elhasználva, az IP világba visszaemelve az összeköttetés orientáltságot.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Reaktív és Proaktív forgalommenedzsment » Reaktív: visszacsatolás-vezérelt sémák » Dinamikusan derítik fel a torlódási helyzetet » Visszaszabályozzák a kibocsátott forgalmukat » Proaktív: erőforrás-foglalás alapú megoldások » Előre elkerülik a torlódáshoz vezető helyzeteket |
6 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Egyfajta csoportosítás:
Reaktív:
Változás esetén módosítja a kommunikáció paramétereit (pl.: TCP is így működik). Az adott hálózatra, annak aktuális állapotára reagál.
Proaktív:
Cél, hogy eleve elkerüljük a csomagvesztést. Megadjuk előre, hogy ki mennyivel adhat.
Nem engedünk be több kapcsolatot, mint amennyi garantálhatóan kiszolgálható.
Az IP-nél ez a fajta megoldás szóba se jöhet, hiszen ott nincs beengedés szabályozás.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Időskálák szerinti csoportosítás » Kapcsolat élettartam » Hívásengedélyezés » QoS-útvonalválasztás » Erőforrás-foglalás » Körülfordulási idő » reaktív torlódáskezelés » Várakozásisor-menedzsment » Csomagkiszolgálási idő » Várakozásisor-menedzsment » csomagkiszolgálók » forgalom-formázás |
7 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Egy másfajta csoportosítás:
Három különböző szint:
- Kapcsolat élettartam: főleg a control síkra jellemző (de pl.: erőforrás foglalás sűrűbben is lehet (pl.: meghibásodás esetén))
- Körülfordulási idő (RTT Round Trip Time): nem más, mint az az idő, amíg egy csomag eljut a címzetthez, illetve onnan a nyugta megérkezik a feladóhoz. Ez az az idő, aminek minimálisan el kell telnie ahhoz, hogy valami, a hálózatban fellépő változásnak hatás legyen a csomópontban, így az reagálni tudjon rá.
- Csomagkiszolgálási idő:
a., csomagkiszolgálók: ez az, ami meghatározza, hogy éppen melyik csomagot szolgáljuk ki
b., forgalom formázás: hatása csak egy RTT után érzékelhető leghamarabb.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Forgalomleíró technikák
» Sztochasztikus modellek
» Markovi On/off
» Determinisztikus korlátok
» (σ, ρ) modell
» Forgalom formázó módszerek
» lyukas vödör formázó
2005. szeptember 27. kedd
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM
8
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
9 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Management
plane
A megjelölt építőelemek játszanak itt szerepet, azaz ezeket alkalmazzák a forgalom leíró technikáknál. SLA: milyen forgalom karakterisztikát várnak el a felhasználótól, és ezt hogy biztosítjuk. Ezek specifikálása mind forgalom leírással történik.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Forgalomleírás alkalmazásai » Forgalmi típusok » Valós idejű » toleráns » intoleráns » Elasztikus » Felhasználási terület » SLA ellenőrzés, betartatás » analitikus teljesítmény-vizsgálat |
10 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Két forgalom típus:
Elasztikus: azaz összenyomható. Itt nem fontos, hogy az adott adási sebességgel jussanak el a csomagok a cél csomópontig, csak az, hogy az információ biztonsággal átjusson a hálózaton (pl.: FTP).
Valós idejű: azaz nem összenyomható. Fontos az időzítés (pl.: VoIP).
- intoleráns
- toleráns: lehet csomagvesztés, vagy adási sebesség változás szerint is. (ilyen példa lehet egy olyan videó codekkel való tömörítés, ahol ha torlódás van és nem jut el minden csomag a vevőhöz, akkor rosszabb minőségben kezd tömöríteni, mondjuk fekete-fehéren, és így biztosítja az akadálymentes kommunikációt.)
Tradicionális sorbanállási modellek » Sztochasztikus modellek, » Poisson érkezési folyamatok » On-off beszédmodellek
ON OFF 353ms 650ms » Általános Markov lánccal, beágyazott Markov lánccal megadott folyamatok » … |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
11 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
A kiszolgálók felfoghatóak várakozási sorokként. A fenti példa egy kétállapotú Markov lánc, ahol,
- ha ON , akkor adott bitsebességgel továbbít a folyamat
- ha OFF, akkor nincs adás, azaz 0 bit/s az átviteli sebesség. Az ábrán ezen állapotok várható ideje látható.
Ezek a modellek sajnos nem mindig alkalmazhatóak, mert csak az átlagos viselkedést mutatják meg, de minket (minőségbiztosítási szempontból) a legrosszabb eset érdekel.
Csak úgy tudunk minőséget biztosítani, ha a legrosszabb esetbeli viselkedésre készülünk fel.
A tömegkiszolgálási módszerek erre nem alkalmasak, így be kell vezetnünk a korlátozó modelleket. (ez már jó lesz a legrosszabb eset modellezésére is)
on-off is xxxxxx xxxxxxxx (according to Xxxxxxx et al., VoIP project)
Korlátozó modellek » Pontos leírás nehézkes » Lassan lecsengő eloszlások » Pl. Pareto(k,α) » Sorbanállási analízis átlagos viselkedést vizsgálja » Itt legrosszabb esetbeli viselkedés az érdekes » (Xmin, Xave, I, Smax) korlátozó modell » (σ,ρ): börszt méret, hosszútávú átlagos sebesség » D-BIND: Deterministic Bounding Interval-Dependent |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
12 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
!!!!!!! Jegyzet a következő fólián + a jegyzet részében !!!!!!
(Xmin, Xave, I, Smax) : [Ferrari & Xxxxx] (σ,ρ): [Cruz]
D-BIND: [Xxxxxx & Xxxxx], deterministic bounding interval-length dependent
The traffic specification consists of parameters (Xmin, Xave, I, Smax), where Xmin is the minimum packet inter-arrival time, Xave is the worst-case average packet inter-arrival time over an averaging interval, I is the averaging interval, and Smax is the maximum packet size. [IEEE_Multimedia94.pdf]
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
A(t)
σ
ρ
F
1. ábra
2. ábra
3. ábra
A forgalom a korlátozó függvénnyel felülről becsülhető.
t
A grafikon törtvonalakból áll.
A(t)
t
13 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
A hálózati forgalom pontos leírása nehézkes. Az interneten a lassan lecsengő (heavy tailed) eloszlások a jellemzőek. Itt ld.: 1. ábra!
Azaz annak a valószínűsége, hogy X>F : P [X>F] nem Markovi viselkedést mutat. Ez a tulajdonság sok mindent von maga után. => az ingadozás fraktális jellemzőket von maga után, ami nagyban megnehezíti annak matematikai analízisét.
1., (Xmin, Xave, I, Smax) korlátozó modell:
a paraméterek jelentése:
Xmin: mekkora a legkisebb időintervallum, amin belül két csomag elküldésre kerül. Inter arrival time: beérkezések közötti idő – Xmin ennek minimuma.
Xave: a fenti Inter arrival time átlaga I a vizsgált intervallum mérete Smax: a maximális csomagméret.
Ezekből a maximális sávszélesség = Smax / Xmin
A probléma ezzel a modellel, hogy ha egy kimeneti linken egynél több bemeneti link forgalmát kell továbbítanunk, akkor annak a forgalomnak az aggregálása nagyon nehéz.
2., (σ,ρ) korlátozó modell a paraméterek jelentése:
σ: a maximális burst méret
ρ: átlagos sebesség
burst: a rövid idő alatt kiküldött adatmennyiség nagysága. Itt ld.: 2. ábra!
A [t, t + τ] ≤ σ + ρ * τ minden t, δ > 0 –ra. arrival: beérkezés: forrás által generált adatmennyiségként is felfogható. Átlagos adási sebesség: (σ + ρ * τ) / τ .
Ha feltesszük, hogy a forgalom idő invariáns, azaz hogy a vizsgált időintervallum elhelyezkedésétől nem, csak a hosszától függ. Így az A(t, t + τ) függvény A(τ)-é, azaz egy paraméteressé válik, vagyis csak τ-tól függ.
Lehetne más korlátozó függvény is: pl.: D-BIND Itt ld.: 3. ábra!
Leaky/token bucket leaky bucket token bucket (analogue to the leaky bucket) water pours in p r b deepness of the bucket tokens r = token rate p = peak rate >= r b = token bucket length the water flows out a const. (max. nr of tokens) rate through the leak ⇒ Dual leaky bucket |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
14 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
!!!!!!! Jegyzet a következő fólián + a jegyzet részében !!!!!!
peak A(t) ρ σ t A vastag vonal lesz az új korlátozó b modell. 2. ábra A(t) r 1. ábra t 3. ábra |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
15 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
A forgalommodellezésnél gyakran folyadék modellt használnak, mert egyszerűbb, mint a csomagszintű modellek.
A lyukas vödör elv átültethető valós hálózatokra is: amikor adatcsomag érkezik, akkor az a méretének megfelelő mennyiségű folyadékot helyez el a vödörben. Ha annyi víz távozott, ami a csomagnak megfelelő, akkor a rendszer, vagy a csomópont a csomagot képes kiszolgálni.
A token vödör kicsit másképpen működik. Hogy mi a különbség? A tokenek folyamatosan, r sebességgel „csöpögnek”, gyűlnek a token vödörben. Egy, a várakozási sor végén álló csomag akkor kiszolgálható, ha van neki ( a méretének ) megfelelő mennyiségű token egyszerre a vödörben. A kiszolgáláskor ezek a tokenek eltűnnek a token vödörből.
Egy szerre b-nyi lehet benne: maximális burst méret.
r sebességgel generálódnak: hosszú távon ez a sebesség limit.
a (σ,ρ) paraméterek ezzel kikényszeríthetőek ezzel, így megfelel a forgalom leírásnak. Még egy implementáció a token vödörre:
Itt ld.: 1. ábra!
tehát a kiszolgált csomag méretének megfelelő folyadék kerül a vödörbe kiszolgáláskor.
Addig szolgálhatunk ki, míg van annyi hely a vödörben, hogy a soron következő csomag kiszolgálása után sem lenne több folyadék a vödörben, mint amekkora a vödör mérete.
A csúcssebességet is leírhatjuk, de ehhez hozzá kell vennünk a modellhez: (σ, ρ, peak) Itt ld.: 2. ábra!
Ha token vödör kimenetére egy lyukas vödröt teszünk, akkor a peak-et is szabályozni tudjuk: ez a kettős lyukas vödör. D-BIND megvalósítása:
Itt ld.: 3. ábra!
Egyenesenként egy-egy lyukas vödörrel megvalósítható. (az egyeneseket a törtvonal szakaszaira illeszthetjük.)
Exponentially bounded Burstiness (EBB) » Sztochasztikus felső korlát » Lyukas vödör kiterjesztés » A[t1,t2] v.v: a [t1,t2] intervallumban generált forgalom |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
16 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Az előbbiek determinisztikus modellek voltak.
A multiplexálásnál a célunk a sztochasztikus (átlagban vett) nyereség elérése.
Ezek is korlátozó modellek, de itt a beérkező adat egy valószínűségi változóként lesz kezelve. Ennél a modellnél a beérkező adat meghaladhatja a limitet, de csak kis valószínűséggel.
Forgalom-leírás a hálózat belsejében » Best-effort: a hálózat belseje egyre börsztöszebb a forgalom » “Virtual-feedback” A0 0 S (2) S (1) + S (3) S (4) 2 0 2 0 3 1 S (3) + S (1) S (2) 0 2 0 2 |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
17 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
sajnos a forgalom szabályozását csak a hálózat szélén adhatjuk meg, de ez nem elég. Itt hiába mondjuk meg, a hálózat belsejében ez megváltozhat (torlódás, burstösebb viselkedés).
De még ezek a paraméterek se biztosan meghatározhatók a „virtuális visszacsatolások” (virtual feedback) miatt.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Queue Management
összefoglaló:
» Mikor és melyik csomagot dobjuk el a telítetté váló várakozási sorból?
» DFF, RED, ECN
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM
2005. szeptember 27. kedd 18
Queue Management – Várakozási sor menedzsment
A 70-es években kitalált egyszerű modellel szemben, mely során a várakozási sorba be nem férő csomagokat eldobjuk, ma már több megoldás is elképzelhető. Ezeket az alternatívákat tekintjük át a következőkben.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
19 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Management
plane
queuing– telítettség esetén kerül előtérbe Scheduling– normál működés esetén mérvadó
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Goodput
összehangolt reakció
Time
Time
Goodput
Load
Load
Congestion Avoidance
Congestion Collapse
A hagyományos módszer
» Xxxxx a sor végéről, ha a sor megtelt
» Hátrány:
» sorbanállás: késleltetés
» ha telített sor esetén egy börszt érkezése sorozatos csomagdobásokat eredményez
» összehangolt TCP torlódáskezelési reakció
» rossz link-kihasználtság
Kbytes/sec
Kbytes/sec
20 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Hagyományosan FIFO elven működik
Ha a sor megtelik, akkor a sor végére érkező új üzeneteket dobjuk el.
Ezt azért tehetjük meg, mert az IP csak „best effort” jellegű szolgáltatást biztosít, azaz nem kell garantálnunk, hogy a csomagjai célhoz érnek, ugyanis az esetleges csomagvesztésre mindenki felkészült, illetve mindenkinek fel kellett készülnie.
Azért kell egyáltalán a várakozási sor, hogy ha a várakozási sorban fluktuáció (ingadozás) alakulna ki, akkor ez a megoldás
átmenetileg áthidalhatja a problémát. Természetesen hosszú távon nem oldhat meg minden problémát.
Hátrányok:
- sok csomag lesz egyszerre a várakozási sorban - egy csomag sokát kell, hogy várjon
- ha a sor nem üres, akkor lehet, hogy egy beérkező burst egy része eldobásra kerül
- akkor lesz csomagdobás, ha a sor megtelik, DE a TCP sebesség beállító metódusából adódóan ez további problémákat okozhat, mert annak működése az alábbi:
minden adó addig növeli a sávszélességét, amíg csomagvesztés nem lép fel (slow start). Ha több kapcsolat van, akkor mindegyik kb. egyszerre szabályozza vissza a sebességét. Így a kimeneti linken a sebesség 100%-os, ha a várakozási sor telítve van, és könnyen 100% alá eshet, ha csomagvesztés volt, azaz ilyenkor nem maximális az átviteli közeg kihasználtsága. A TCP újra több csomagot küld, és így bezárult a kör.
1. ábra: hiába növeltük a kimenő adatot, egy mérték fölött a teljesítmény összeomlott.
2. ábra: az előbbi probléma kiküszöbölésére találták ki: leszabályozza magát a folyamat, így kerülve el az összeomlást.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Várakozásisor-menedzsment funkciók » Feladat: » csomagok tárolása, » továbbítása, » eldobása » Cél: » állandósult sorhossz minimalizálása (várakozási késleltetés csökkentése) » a link maximális kihasználása mellet » folyamok kiéheztetése nélkül » Megoldások csoportosítása mikor és melyik csomagok dobják el? (melyik sorból) • Drop From Front • Random Early Detection • Explicit Congestion Notification |
21 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Drop From Front » Bonyolultabb a megvalósítása » A forrás hamarabb értesül a torlódásról » Valósidejű forgalom » a legelső csomag már sokat várakozott » talán már felélte a késleltetés-tartalékát » DFF a gyakorlatban nemigen használatos |
22 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Drop from Front – a FIFO várakozási sor elejéről dobja el a csomagot, ha el kell egyet dobnia. (az esetleges okok fent olvashatóak)
A forrás úgy értesülhet hamarabb a torlódásról, mert (pl.: TCP esetén) ahelyett, hogy megvárná, hogy a timer-e jelezzen, elképzelhető hogy így elöbb kap egy duplikált nyugtát, így hamarabb újraküldheti a csomagot.
A legelső csomag már sokat várakozott: ez azért lehet gond, mert elképzelhető, hogy a csomag késleltetése maximalizálva van, és ennek a késleltetésnek egy nagy részét már felélte a várakozási sorban tétlenkedve. Így hasznos, ha minél előbb eltávolítjuk a hálózatból, ugyanis lehet, hogy már érvényét vesztette.
A probléma vele: hogy nagyon bonyolult megvalósítani.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME |
Active Queue Management Random Early Detection (RED) » Célok: » Jobb torlódási jelzés reaktív folyamoknak (TCP) » Rövid várakozási sorok » Börsztök tárolása » Igazságos dobások: többet ad, arányosan többet veszít » Jellemzők » Csomagdobás a sor megtelte előtt » Állandósult torlódás észlelése az átlagos sorhossz alapján » Véletlen dobások a torlódás súlyosságával arányosan |
23 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd |
Célunk vele, hogy elkerüljük az összeszinkronizált TCP szabályozást. (Illetve az ebből fakadó teljesítmény hullámzást.)
Active Queue Management Random Early Detection (RED)
Max Queue Size
Average queue length
Max Threshold
Drop probability
Forced drop
Probabilistic drops
Min Threshold
No drops
Time
» Weighted average accommodates bursty traffic
l Multiple modes based on threshold values
l Probabilistic drops
» avoid consecutive drops
» drops proportional to bandwidth utilization
– (drop rate equal for all flows)
Forrás: Xxxx Xxxxxx,Xxxxx Xxxxxx, F. Xxxxxxxx Xxxxx:
Lightweight Active Router-Queue Management for Multimedia Networking
24 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
A várakozási sor alakulása az idő függvényében.
A függvényt szándékosan simítani szeretnénk, amihez az eszközünk a rövid intervallumú átlagolás.
Probabilistic drops:
If the average is above the minimum threshold the probability the incoming packet will be dropped increases as it approaches the max threshold. If a random value is above the prob. The incoming packet is dropped.
Forced drops:
If the average is above the max threshold a random packet from somewhere in the queue is dropped for each incoming packet.
Does result in shorter queues on average Implemented in many CISCO routers Focus is on responsive flows
Problem still unaddressed:
unresponsive flows can still dominate
Also, all flows will see equal drop %. - this is the way most folks “expect” FIFO to work, evenly distributed.
Random Early Detection, RED profile
|
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
25 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
(a fenti függvény az eldobás valószínűségét mutatja) A profil 3 tartománya:
1.: amikor a várakozási sor (majdnem) üres: ekkor nem dobunk el csomagokat
2.: amikor min(th) és max(th) közötti számosságú csomag van a várakozási sorban, akkor nő annak a valószínűsége, hogy eldobunk egy csomagot
3.: miután a csomagok száma átlép egy meghatározott küszöbértéket, akkor azután minden csomagot eldobunk
A fentihez hasonló profilok definiálják a konkrét megvalósításokat.
+
RED Algorithm Description
–
Network Interface
qlen qavg
= 0
= 0
qavg = (1-w)qavg+w*qlen
Forrás: Xxxx Xxxxxx,Xxxxx Xxxxxx, F. Xxxxxxxx Xxxxx:
Lightweight Active Router-Queue Management for Multimedia Networking
An initially empty queue
26 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
+
RED Algorithm Description
–
Network Interface
qlen qavg
= 1
= 0.25
qavg = (1-w)qavg+w*qlen
Enqueueing one packet
27 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
RED Algorithm Description
+
–
Network Interface
qlen qavg
= 4
= 1.95
qavg = (1-w)qavg+w*qlen
After more enqueues
28 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
+
count = -1
pa = 0.04
pa = f(count,qavg)
<
RAND = 0.88
RED Algorithm Description
–
Network Interface
qlen qavg
= 5
= 2.71
qavg = (1-w)qavg+w*qlen
Exceeding MinTh - No drop
29 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
+
count = 0
pa = 0.09
pa = f(count,qavg)
<
RAND = 0.99
RED Algorithm Description
–
Network Interface
qlen qavg
= 6
= 3.53
qavg = (1-w)qavg+w*qlen
Exceeding MinTh - No drop
30 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
+
count = 3
pa = 1.05
pa = f(count,qavg)
>
RAND = 0.63
minth maxth maxp w
=2
=7
= 0.3
= 1/4
–
Network Interface
qlen qavg
= 8
= 6.22
qavg = (1-w)qavg+w*qlen
Exceeding MinTh - Probabilistic Drop
31 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
RED Algorithm Description
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
+
count = 0
pa = 0.29
pa = f(count,qavg)
<
RAND = 0.77
RED Algorithm Description
–
Network Interface
qlen qavg
= 9
= 6.91
qavg = (1-w)qavg+w*qlen
Exceeding MinTh - No Drop
32 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
minth =2
maxth =7
maxp = 0.3
w = 1/4
+
minth maxth maxp w
=2
=7
= 0.3
= 1/4
–
Network Interface
33 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Exceeding MaxTh
qavg = (1-w)qavg+w*qlen
= 9
= 7.68
qlen qavg
RED Algorithm Description
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
RED tulajdonságok – variánsok » A torlódási szinttel » Weighted RED arányosan generál TCP » Kapcsolatok közös sorban visszacsatolást vannak, különböző RED- » Nagyobb sávszélességű profile-jal (maxp, minth, kapcsolatokat jobban büntet maxth) » A TCP torlódáskezelő » RED with In/Out mechanizmusok kevésbé » Adaptive RED összehangoltak » RED-profile menet közben igazodik a TCP kapcsolatok számához » Az átmeneti torlódásokért » Flow RED legtöbbször TCP-k felelnek » nem-adaptív kapcsolatokból nem dob » RTT-t figyelembe veszi |
34 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Különböző RED variánsok jöttek létre… a fentiek csak példák ezekre.
Weighted RED: minden csomagot osztályokba sorolunk, és minden osztályra vonatkozhat más profil. Például ha van egy fontos osztályunk, akkor a többivel szemben előnyt élvezhet. (szélsőséges megoldás erre a problémára az a modell, ahol csak a fontos folyamat használhatja a várakozási sort, a többit eldobjuk.
RED with IN/OUT: a fenti eset speciális változata. Két osztályt ismer, azon csomagokét, amelyek még beleférnek az SLA által meghatározott keretekbe (IN) és azokét, amelyek már ezen kívüliek(OUT), és amelyeket nem dobunk el mindaddig, míg nem kell csomagot dobnunk. (A szélsőséges megoldás itt is működik: elképzelhető megoldás, hogy minden IN osztályba tartozó csomagot megtartunk, és minden OUT osztályba tartozót 100%-al eldobunk. Ezzel elérhetjük, hogy amelyik csomag az SLA keretein belül van még, az nem érezheti az esetleges hálózati forgalom torlódás hárányát.)
Adaptive RED: Nehéz beszabályozni egy ilyen profilt, így erre a feladatra is kitaláltak egy megoldást. Ez lett az Adaptív RED. Feladata a várakozási sor munkapontját (hosszát) a minimum környékén tartani. Ha nő a sorhossz, akkor növeljük, ha a sorhossz csökken, akkor csökkentjük a p(max)-ot, azaz az esetleges csomagdobás maximális valószínűségét.
Flow RED: Csak a TCP kapcsolatokra alkalmazhat, illetve csak ezeket szabályozza. Az RTT-t is figyelembe veszi a csomag eldobásának döntésekor. Ugyanis, ha az RTT kicsi, akkor a forrás hamar értesül a csomagvesztésről, így az ő csomagjait előnyösebb eldobni, mint azét, aki csak sokára értesülhetne arról, hogy a csomagot újra kellene küldenie.
DE: baj vele, hogy kapcsolat alapú, állapotokat tárol, és ezt nem szeretjük, mert nagy sávszélességnél, sok kapcsolatnál nehéz a gyors fizikai megvalósítása.
Edge routers mark packets as being “in” or “out” of profile. RIO: red with in/out: two profiles; ARED: keves forras: egy kapcsolat nagyobb szazalekban lesz jelen a sorban. Xxx_x dinamikusan valtozik, hogy a munkapont min_th es max_th kozt legyen.
FRED: small RTT => recover quickly, per-flow states required, common queue.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Értesítés küldése a torlódási helyzetről » Visszajelzés a torlódásról: csomagvesztés » TCP újraküldési mechanizmusa kezeli » Explicit Congestion Notification (ECN) » hálózati rétegbeli megoldás » adatcsomag megjelölése » (a sor teljes telítettsége előtt) » tájékoztatás adatvesztés nélkül » RED-hez hasonló megjelölési szabály is elképzelhető |
35 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Egy másik alapötlet.
Csomagvesztés helyett küldünk egy értesítést, hogy torlódás közeli helyzetben van a hálózat (egy része), így a forrás anélkül reagálhatna a helyzetre, hogy az kialakuljon. (reaktív-preiktív megoldás)
A megoldás úgy működik, hogy ha egy olyan hálózati elem lenne az útvonalon, ami nem támogatja ezt a metódust, akkor az is működő képes marad, csak nem használja ki ezt a plusz információt, hanem csak egyszerűen továbbítja a csomagot.
Elképzelhet a két módszer ötvözete is, ami alapján p valószínűséggel tájékoztatnánk egy csomópontot a torlódás közeli helyzetről.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Csomagkiszolgálók / Csomagütemezők (Schedulers)
» Prioritásos kiszolgáló,
» Round-Xxxxx,
» Generalized Processor Sharing
» egyszerű késleltetési korlát
» optimális, csomóponti CAC
» EDF, J-EDF,
» Hierarchikus kiszolgálók
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM
2005. X. 4. 36
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Management
plane
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Ütemezők a QoS architektúrában » Feladata: Kapcsoló, útvonalválasztó kimeneti linkjén a csomagtovábbítási sorrendet határozza meg » Cél: » Kapcsolatok (osztályok) különböző kezelése » ezáltal QoS biztosítása » Megoldások csoportosítása: » Munkamegőrző – nem munkamegőrző » Komplexitás szerint (“sorted priority” schedulers) » Igazságossági paraméterek alapján |
Megoldások csoportosítása:
-Munkamegőrző: amennyiben az egyik kiszolgálási sorban van csomag, akkor biztos, hogy a kimeneten is éppen egy csomagot szolgál ki.
-Nem munkamegőrző: ha van a kiszolgálási sor(ok)ban kiszolgálható csomag, akkor sem biztos, hogy ad, pedig lenne mit
Összetettség:
Elvárás vele szemben, hogy az adott komplexitást nagy sebességen kell megvalósítani.
„sorted priority” ütemezők, azaz valamilyen szempont szerint prioritási szinteket vezetünk be, (és ezek közül kell kiválasztani a legkisebbet) de ez már komplex feladat, sok sor esetén nem biztos, hogy hatékonyan megvalósítható.
Legegyszerűbb utemezők: FIFO elven működnek ( FIFO – First In First Out), azaz lrkezési sorrendben szolgálja ki a csomagokat.
Ez a megoldás:
-Nem teljesíti az első célt
-Munkamegőrző
-Kis komplexitású
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Követelmények az ütemezőkkel szemben » Elkülönítés és megosztás » Késleltetési korlátok » Sávszélesség szétosztás » Hatékonyság » hatékonyabb: ua. az e2e QoS terheltebb hálózatnál » Védelem » rosszul viselkedő felhasználók » meghibásodott eszközök » best-effort forgalom » Rugalmasság » eltérő QoS igényű osztályok » Egyszerűség » nagy sebességű környezetben implementálható |
Elkülönítés osztályoknál:
Jelentése: Az adott osztály a többitől független, a többitől függetlenül tudunk minden osztálynak meghatározott minőségi paramétereket biztosítani.
Megosztás:
Jelentése: A szabad, vagy időközben szabaddá vált, felszabaduló erőforrásokat képesek vagyunk szétosztani azon osztályoknál, amelyeknél azokra szükség van.
A megosztás lehet fair: ez azt jelenti, hogy ha például van 3 folyamatunk (a,b,c), és ezek közül egy nem ad (pl.: c), akkor a annak erőforrásait egyenlő arányban osztjuk szét a másik kettő között (a,b). (Látni fogjuk, hogy az igazságosságnak van más definíciója is)
Hatékonyság:
az egyik ütemező hatékonyabb, mint egy másik, ha az egyiket használva adott körülmények között egy újabb folyamat is beengedhető, míg a másikkal nem.
Védelem:
Rugalmasság:
Egyszerűség:
rosszul viselkedik az a felhasználó, aki nem tarja be az SLA-ban foglalt megállapodást.
osztályokba sorolunk-e (ha igen, akkor hány különböző minőségi osztály választható) vagy esetleg folyamatonként kezeljük a forgalmat?
fontos szempont, hogy nagysebességű környezetben is megvalósítható legyen – itt az
algoritmikus komplexitás a döntő.
Prioritásos kiszolgáló
» A legnagyobb prioritású, nem üres sorból szolgál ki » Alacsonyabb prioritású sorok kiéheztetése » CAC gondoskodik a prioritásos sorok véges forgalmáról » Kis késleltetésű forgalmat a legnagyobb prioritású sorba! » Non-preemptive linkeknél a hosszú kis prioritású csomagok növelik a késleltetést |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Az első komplexebb megoldás:
Működése: a beérkező csomagokat az egyes prioritási szinteknek megfelelő várakozási sorokban helyezi el (annak eldöntése, hogy melyik csomag hová kerül, a traffic classification feladata). Ezt kövezően kiszolgáláskor azon legmagasabb prioritású sorból szolgál ki egy csomagot, amely nem üres.
Problémája az esetlegesen felmerülő kiéheztetés, ami annyit tesz, hogy ha egy magasabb prioritású sorba rendszeresen érkeznek kiszolgálandó csomagok, olyan sebességgel, hogy az ütemező ne tudjon alacsonyabb prioritású sorokból csomagokat kiszolgálni, akkor az alacsonyabb prioritású sorban várakozó csomagok sohasem kerülnek kiszolgálásra (vagy legalábbis sokáig nem lesznek kiszolgálva).
Példa:
b/s)=0.01s késleltetésre.
kimeneti link sebessége (c): 10 Mb/s Nagy prioritású kapcsolat:
Burst mérete: 100 csomag Csomag mérete: 1000 b
kérdés: maximális sorbanállási késleltetés.
egy burst kiszolgálási ideje: (100 * 1000 b)/(10 Mb/s)=(100 Kb)/(10 Mb/s)=(10^5 b)/(10^7 ha az MTU (maximal transfer unit) nincs maximalizálva, akkor nincs felső határ a
ha van felső határ:
pl.: MTU = 10^4 b, akkor a max. késleltetés: 0.01s + 0.001 s = 0.011 s
(nagy prioritású sorban)
Kis prioritású kapcsolat:
Burst mérete: 10 csomag Csomag mérete: 10000 b
max. késleltetés: 10 * 100-as (nagy prioritású) burst kiszolgálása + a saját csomagjainak a
továbbítása
Round-Robin » Minden sorból egy-egy csomagot szolgál ki egymás után » Nincs kiéheztetés » Kiszolgálás erősen függ a többi sortól » Jitter-forrás |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Azzal oldja meg a kiéheztetést, hogy a sorokból egymás után szolgál ki egy-egy csomagot. (Természetesen csak akkor, ha van bennük csomag, mert ha nincs, akkor nem vár egyre, hanem a következőre ugrik, és azt szolgálja ki.)
A várakozási sorok függnek egymástól, így ingadozás lehet a késleltetésben. De korlátok így is adhatóak:
MTUi: Az i. sor maximális transfer unit –xxxxx xxxxxx. C: kimeneti link sebessége
A j. várakozási sorból történő két csomag küldése között eltelő maximális idő: (Summa(minden i-re) MTUi)/(c)
Ugyanerre egy minimum korlát: (MTUj)/(c)
Generalized Processor Sharing (GPS) » Elméleti, folyadék alapú kiszolgálómodell » több kapcsolat egyidejű kiszolgálása » csomag tetszőlegesen kicsivé darabolható » Kiszolgálási sebesség a kapcsolatokhoz rendelt súly (φ) arányában, » pontosabban minden aktív i folyamra |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
GPS – általánosított erőforrás megosztás
Igaz, hogy elméleti modell, de mégis hasznos, mert sok jó tulajdonsága van.
Kiszolgálási sebesség a hozzá rendelt súly arányában: amelyikhez nagyobb súlyt rendeltünk, attól gyakrabban szolgálunk ki egy-egy csomagot.
Aktív az a folyamat, amelyiknek van csomag a várakozási sorában.
1/4 | 1/3 | 1 | 1/2 | |
1/4 | ||||
2/3 | ||||
1/2 | 1/2 |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Nem hasnálja ki a kapott sáv- szélességet
43 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Fair megoldás, mert olyan arányban osztjuk szét a felszabaduló sávszélességet, amilyen arányban az előfizetők kifizették azt.
GPS: egyszerű késleltetési korlát » Garantált sebesség: » Legrosszabb eset: mohó rendszer: A[0,t] = σ + ρ t » Késleltetés felső korlátja: □ σi == gi t Arrival function: σ + ρ t » Ha gi > ρi » a bemeneti leíró érvényes a kimeneten is » Ezen alapuló (e2e) CAC? t |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
gi:: garantál sebesség az a sebesség, amit mindenképpen megadjuk az i. folyamatnak. Ilyen értelemben a folyamatok el vannak szeparálva egymástól. Azt a sebesességet akkor szolgáltatjuk az folyamatoknak, ha mindegyikük aktív, azaz maximális a hálózat leterheltsége.
r: a kimeneti link sebessége
A piros görbe (kiszolgálási görbe) kezdeti meredeksége gi
A maximális késleltetés: a két görbe közötti leghosszabb függőleges szakasz: σ
A maximális sorhossz: a két görbe közötti leghosszabb vízszintes szakasz: (az ábrán kék szaggatott vonallal jelölve)
Ha gi < ρi, akkor instabil a rendszer ( vagy más néven: nem biztos), csak akkor, ha Summa(minden i-re) ρi
> r.
Felmerülő kérdés: milyen hívás engedélyezést lehet itt csinálni, köthető-e SLA a felhasználó és a hálózat között?
Az i. felhasználó megadja a (σi , ρi) forgalom leírókat, melyeket használni kíván, valamint a di késleltetési maximumot, amit hajlandó várni.
Ezekből:
Di* ≤ di
Σρi ≤ r
És pl.: Φi= ρi => ρi ≤ gi ami nekünk megfelel
e2e (végponttól végpontiig) forgalom leírás: megadjuk azt az útvonalat is, ahol a csomagot továbbítani szeretnénk.
Ekkor a hálózati késleltetés ≤ az egyes csomópontokban elszenvedett késleltetések összege. De lehet, hogy ennél szűkebb korlátok is igazak lesznek.
Töréspontos kiszolgálási görbe » A minimális aggregált kiszolgálást adja meg Arrival function: σ + ρ t » W(t,t +τ) ¸ S(τ) 1. kapcs. 8 t, τ > 0 Service » Követelmények az ütemezőkkel function szemben » Elkülönítés és megosztás » Késleltetési korlátok » Sávszélesség szétosztás » Hatékonyság » Védelem g ? » rosszul viselkedő i felhasználók 2. kapcs. » meghibásodott eszközök » best-effort forgalom » Rugalmasság » eltérő QoS igényű osztályok » Egyszerűség » nagy sebességű környezetben implementálható |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Xxxxxx feltételeknek tesz eleget?
Elkülönítés és megosztás - OK Késleltetési korlátok - OK Sávszélesség szétosztás - OK
Hatékonyság – nem értelmezhető ebben az esetben, mert nincs mivel összehasonlítani Védelem
Feladat: r=1
Rugalmasság Egyszerűség
rosszul viselkedő felhasználók - OK meghibásodott eszközök - OK
best-effort forgalom – ez sem értelmezhető
eltérő QoS igényű osztályok - OK
nagy sebességű környezetben implementálható - nem implementálható mert folyadék modell, bár ha az lenne, egyszerű lenne (a komplexitás szempontjából)
1. kapcsolat:
σi: 1
ρi: 0,2
Φi: 20
di : 2/3 2.kapcsolat:
σi: 2
ρi: 0,5
Φi: 10
di : 1/3
A megoldás menete: felrajzolni a két folyamat kiszolgálási görbéjét, majd meghatározni azt a pontot, ahol előszőr erőforrások szabadulnak fel, és azokat az erőforrásokat ettől a ponttól kezdve a másik folyamathoz rendelni, annak a kiszolgálási görbéjének a meredekségét növelni. Majd végül a teljes töréspontos görbe meghatározása.
Ebből végül a maximális függőleges és vízszintes távolság meghatározása.
Optimális csomóponti CAC algoritmus GPS-hez Session 1 Session 3 Arrival function: σ + ρ t » Worst-case scenario » Fixes session weights one Service by one function » Utilizes the excess bandwidth Session 2 » Traffic distortion at output |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
46 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Adottak a fenti folyamatok az alábbi ismert jellemzőkkel: korlátozási függvényük
maximális késleltetésük Most is a legrosszabb esetre kérdezünk rá.
Célunk a legkisebb olyan gi-k (garantált sebességek), megtalálása, amelyek mellett di (maximális késleltetés) még teljesíthető.
gi > ρi
1., Megvizsgáljuk, hogy melyik folyamat távozik először (, vagyis melyik erőforrásai szabadulnak fel először). Ennek a gi -jét rögzítjük.
2., amikor ez távozik, akkor szabad kapacitás szabadul fel.
3., A most szétosztott erőforrások segítségével a többi folyamat gyorsabban adhat, így ezeknek lehet, hogy kisebb garantált sávszélesség is elég, így ezeket csökkentjük.
Innen a megmaradt folyamatokkal az algoritmus rekurzívan ismételendő.
Így végül minimális gi-kkel tuddjuk biztosítani az elvárt di–t. Ezekből a garantált sávszélességekből Φi már számítható.
De2e ≤ σi / min gim (m: minden az útvonalon lévő csomópontra) korláttal felülről becsülhető.
A folyadék modell alkalmazhatósága » Analitikus eredmények átvihetők a csomagos változatokra » Weighted Fair Queuing (WFQ) » Worst-Case Fair WFQ (WF2Q) » …
» Egyik csomag sem távozik később a csomagos rendszerben |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
47 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Weighted Fair Queuing – súlyozott igazságos kiszolgáló
Worst-Case Fair WFQ – legrosszabb esetben igazságos kiszolgáló
Háttérben emulálja a folyadék modell ütemezőket, a valóságban pedig csomagokat kezel.
Valójában egyszerre csak egy 1 csomagot tudunk kiszolgálni, tehát ha 50%-ot kap egy folyamat, akkor is egyszerre csak egy csomagot továbbíthat a kimeneti linken (ez esetben minden második kiszolgált csomag lehet ezen folyamat egy csomagja).
WFQ tulajdonságai » A várakozó csomagok közül a szimulált GPS rendszerben legkorábban távozó csomagot szolgálja ki » Korlátos pontatlansággal közelít a GPS rendszert: » A „virtuális-idő” alapú implementáció |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
48 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Lmax: a maximális csomagméret
Fp kalap – Fp: az elméleti és a tényleges kiszolgálási idő különbsége
Amikor a valós rendszerben dönteni kell, hogy melyik csomagot szolgáljuk ki, akkor megnézzük, hogy az emulált GPS-ben melyik csomag kiszolgálása fejeződik be először és a gyakorlatban ezt szolgáljuk ki.
(virtuális idő segítségével adható egy közös forma, amellyel a kiszolgálók együtt kezelhetőek.)
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
WFQ tulajdonságai » A várakozó csomagok közül a szimulált GPS rendszerben legkorábban távozó csomagot szolgálja ki WF2Q tulajdonságai » A várakozó csomagok közül a szimulált GPS rendszerben legkorábban távozó csomagot szolgálja ki, azok közül, amiknek már elkezdődött a kiszolgálása a GPS rendszerben |
49 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
WFQ vs. WF2Q
|
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
50 | Minőségbiztosítás IP hálózatokon, Az IP minőségbiztosítás alapvető építőkockái (5-10.) | 2005. szeptember 27. kedd
Példa:
Az idő időrésekre van felosztva. (11 kapcsolat, az első időrésben mindegyik kap egy csomagot, utána csak a 10-es súlyú még 10-et)
Kérdés, hogy a csomagok a kimeneti soron milyen sorrendben jelennek meg, milyen sorrendben kerülnek kiszolgálásra.
i
a j – bekerülési idő: az i. folyamat, x. xxxxxxxxxxx a rendszerbe érkezésének ideje sij – GPS-ben a kiszolgálási idő kezdete
i
f j – a kiszolgálás befejezésének ideje.
1
a j = j (minden j-re: 1..11) ai1 = 1 (minden i-re: 2..11)
si1 = 1 (minden i-re: 1..11)
1
f 1 = 2 (<- ez a legkisebb befejeződési idő, tehát a WFQ ezt szolgálja ki először)
2
f 1 = 20
s 2 = 3 f 2 = 4
1 1
s 3 = 5 f 3 = 6
1 1
…
s 10 = 19 f 10 = 20
1 1
s 11 = 21 f 11 = 21 (fontos, gyakori hiba: itt a kiszolgálás már egy időszeleten belül megvalósul, mert
1 1
a többi sor már kiszolgálódott, így a teljes sávszélességet ez a sor használhatja ki.)
i
Amennyiben az f j–k (kettő vagy több) egybe esnek, akkor prioritás dönt arról, hogy éppen melyiket
szolgáljuk ki.
WF2Q esetén kisebb a jitter, nem olyan burs-tös az adás. Jó tulajdonsága, hogy nem tud nagyon elszaladni a GPS-hez képest.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Weighted Round Robin vs. Weighted Fair Queuing » WRR-nal GPS-t közelíteni? |
Weighted Round Robin – súlyozott round robin
Ebben az esetben is egy round robin ütemezőről van szó, azzal a különbséggel, hogy itt megszabható az egyes sorok súlya.
Rounb Xxxxx előnye, hogy egyszerű megvalósítani, így nagysebességű hálózatokban is alkalmazható.
Példa:
4 sor, az alábbi súlyokkal:
10, 4, 2, 1
Feladatunk készíteni egy listát, arról, hogy az egyes sorok, mikor kapják meg a kimeneti linket úgy, hogy ebben a listában a súlyaiknak megfelelően szerepeljenek.
3 példát láttunk:
1: teljesen elosztva, egyenletesen szétterítve a felosztható intervallumban 2: sorban, egyenként teljesen kiszolgálva
3: csomagonként váltva
DE: nem hosszútávon, vagy szélsőséges esetekben rosszabbul viselkedik, mint a WBR Jól működik, de ha az egyik sor kiürül, akkor mintát kell váltani.
Javítgatható, de a GPS minőségét nem lehet elérni vele, ezzel csak a komplexitás nő.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Határidő alapú ütemezők » A kiszolgálás a csomagokhoz rendelt határidők sorrendjében történik » Határidő lehet » e2e késleltetési tartalék » várt beérkezési idő + fix késleltetés » Earliest-Due-Date-First (EDD) or » Earliest-Deadline-First (EDF) » Késleltetési korlát és az allokált sávszélesség független: » nincs „sávszélesség-késleltetés csatolás” » CAC összetett. » Erőforrás-megosztás nem igazságos » azonos QoS kérés mellett eltérő lehet a kapott kiszolgálás » Egy variáns: nincs szükség folyamszintű állapotinformációkra |
Határidő – deadline
Az specifikálja ezeket az ütemezőket, hogy mi számít, mit vesznek figyelembe a deadline meghatározásánál.
Példa: egy ütemező, amelynél minden egyes csomag tartalmaz egy időbélyeget, amikor neki meg kell érkeznie a nyelőhöz.
-Ehhez szinkronizálni kell az órákat
-Nagy a komplexitás, bele kell nézni a fejlécekbe
-Hamisítható téves határidő beállításával (nincsen védelem a rosszul viselkedő felhasználók ellen) EZÉRT EZT NEM HASZNÁLJÁK
Késleltetés: terjedési késleltetés + sorban állási késleltetés (főleg ezek, van még például processzálási késleltetés is, de elhanyagolható méretű)
Az előbbi: fix, az utóbbi az adott forgalmi helyzettől függ (mobil környezetben az előbbi sem fix, dinamikusan változik)
Feltételezzük, hogy periodikusan érkeznek a csomagok. Így a deadline az előző csomag beérkezési idejétől függ (várt beérkezési idő + fix várakozási idő)
Ha a határidő lejár, akkor neki lesz a legkisebb a határideje, így ő rögtön a kimenetre kerül. DE: az ehhez tartozó CAC nagyon bonyolult
Nem igazságos.
Nem munkamegőrző ütemezők (non-work-conserving schedulers) » Várakozó csomag esetén sem feltétlenül történik kiszolgálás » Átlagos csomóponti késleltetés és kihasználtság rosszabb lehet » a legrosszabb végponttól végpontig terjedő késleltetés számít » Kisebb jitter érhető el: pl. Jitter-Earliest-Due-Date » Általános modell: |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Rate Controller: pl egy egyszerű Token vödör
Packet Scheduler: ez egy hagyományos munka megőrző kiszolgáló
Burst mentesít, csökkenti a jitter-t
Elérhetjük vele, hogy a hálózat belsejében lévő csomópontok várakozási sora rövidebb legyen.
Hierarchikus kiszolgálok Class Based Queueing (CBQ) 50 % 30 % 20 % Class A Class B Class C 10 % 10 % 10 % 15 % 20 % 5 % 30 % audio ftp telnet video video audio video |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Ez a modell az előbbiekkel nem megoldható
Ha nem mindenki ad, akkor nem teljesül az előírt arányú sávszélesség megosztás.
Pl.: Ha B nem ad videó forgalmat, akkor annak a felszabaduló erőforrásnak nem mindenki között kellene felosztódnia, hanem csak a saját többi forgalma között. Az ábrán ez például lehet az audió forgalom.
Megoldható például hierarchikusan összekötött ütemezőkkel. Ezek egyenként lehetnek különböző struktúrájúak.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Beengedés-szabályozás alapjai, elemei
» Központosított, elosztott
» Foglalás alapú, mérés alapú
» Folyamszintű, aggregált
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM
2005. X. 18. 55
Hívás engedélyezés:
Egy új folyamat belépésekor el kell döntenie, hogy az kért minőségi feltételek biztosíthatóak-e, azaz, hogy az adott körülmények között a forgalom beengedhető-e a hálózatba, úgy hogy a már beengedettek garanciája sem sérüljön
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Management
plane
Resource Reservation: a hálózat egyszerűen a felhasználó rendelkezésére bocsátja a kért erőforrásokat. Admission Controll: komplexebb feladatot lát el: pl. a kérés alapján ennek a részegységnek kell kikalkulálnia a elfoglalandó erőforrás nagyságát.
A hívásengedélyezés feladata » Garantált minőségű szolgáltatás (Quality of Service, QoS) » Csomagkapcsolt eset: » késleltetés, késleltetés ingadozás, csomagvesztési arány, ... » Garantált szolgáltatásminőség: IP, ATM » Hívásengedélyezés (Call Admission Control, CAC) » Az új igényt beengedjük-e a hálózatba? » Beengedés: ha az új és a meglévő folyamok minősége garantált » De: kihasználtság ↔ garantált minőség |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
ATM:
-Sok elméleti eredményt használtak fel a kialakításánál (amelyek az IP-nél még nem voltak ismertek)
-Eleve QoS-re tervezték
-90-es évek közepéig voltak törekvések, amik ezt követően elhaltak
-Így végül nem terjedt el.
Garantált minőség kell – ezért a legrosszabb esetre tervezünk. Ezzel viszont romlik a hálózat kihasználtsága.
A hívásengedélyezés jelentősége » Kell-e hívásengedélyezés? » Jobb minőség » Rosszabb hálózat elérhetőség » Torlódásmenedzsment: » Preventív » Reaktív » Adatfolyamok: elasztikus v. folyam jellegű » Hívásengedélyezés: folyam jellegűre mindenképp, elasztikusra: ?? |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Torlódás menedzsment:
Preventív: a CAC ilyen
Elasztikus folyamatoknál kérdéses, hogy kell-e egyáltalán sávszélesség garanciát nyújtani
A hívásengedélyezés folyamata » A párbeszéd: » A döntés helye: » IntServ/ATM: minden egyes útvonalválasztó/kapcsoló » DiffServ: Bemeneti útvonalválasztó vagy sávszélesség bróker » Különböző protokollok » Továbbiakban az algoritmust vizsgáljuk |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Hogyan zajlik a döntés?
Lehet elosztottan (pl.: IntServ), vagy központi döntés által (főleg DiffServ).
Elosztott hívásengedélyezés |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Forrás és cél között kapcsolat felépítés
Egy jelzési csomag halad át az útvonalon, amely út során minden érintett csomópont megállapítja, hogy ő
tud-e megfelelő mennyiségű erőforrást rendelkezésre bocsátani. Azaz minden node lokális döntést hoz.
DE: ha a CAC csak félig sikeres, akkor vannak akik erőforrást allokálnak, amit később fel kell szabadítani. Kérdés, hogy mennyivel később szabadulnak fel.
És ha ilyen esetben rendszeresen érkeznek a be nem engedett kérések, akkor azok lefoglalva tarthatják ezeket a fent említett erőforrásokat.
Központosított hívásengedélyezés |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Itt központi egység dönt, majd juttatja vissza a döntést a forráshoz. Az előző hiba nem áll fent.
DE: központi egység van, ami ha meghibásodik, akkor az egész hálózat működésképtelen lesz. (nem hibatűrő megoldás)
A központi egység globális képe lehet elavult, nem valós (ami származhat a késleltetési időkből is)
Az Internet méreteiből adódóan 1 ilyen egység nem elég, ezért a nagy hálózatot tartományokra kell osztani, ahol minden egyes tartományon belül külön-külön Brandwidth Broker (sávszélesség ügynök) kell, hogy döntsön.
A tartományok közötti kommunikáció nem megoldott még (, bár vannak elképzelések).
Végponti CAC próbaforgalom segítségével |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
A hálózat állapotát próba forgalommal derítjük fel.
Statisztikus jellemzőket mérhetünk vele: késleltetés, csomagvesztés, stb. Ebből dönt a forrás, hogy beengedhető-e a forgalom.
DE:
-mivel a forrás dönt, így a rosszul viselkedő forrás ellen nem véd.
-Mivel mérés alapú, így változhat időközben.
A 2. megoldás már véd a rosszul viselkedő felhasználók ellen.
Határponti CAC döntés passzív mérés alapján |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
A mérés történhet passzív mérés segítségével is.
Követelmények » Hiba fajták: » elsőfajú: felesleges elutasítás » másodfajú: beengedés túlterhelt hálózatba » Egyszerűség, gyorsaság » Skálázhatóság » Jó forgalmi modell |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
A hibák közül a másodfajúak a súlyosabbak, ugyanis ez több folyamat kommunikációjára is kihathat, míg az első csak egy-egy folyamatéra.
A gyorsaság biztosíthatóságához van szükségünk pl.: forgalom leírókra.
Algoritmusok csoportosítása » Determinisztikus vagy statisztikus alapú » Forgalmi leíró adatblokk: » Pld: forgalmi paraméterek vagy meglévő osztályok » Várakozási sorok hatása beszámítva? » Igen: sebesség-osztó multiplexálás (rate-sharing multiplexing, RSM) » Nem: sebesség-lefedő multiplexálás (rate-envelope multiplexing, REM) » Túlterheltség meghatározása: » csomagvesztés, késleltetés... » Algoritmus alapja (köv. fólia) » Mérés alapú? (később) |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Statisztikus algoritmusok segítségével nagyobb kihasználtság érhető el
Forgalmi paraméterek: nagyobb rugalmasság Meglévő osztályok: kisebb komplexitás
Sebesség lefedő multiplexálás: egyszerű példa: GPS
Csomagvesztés: egy hálózat akkor telített, ha a csomagvesztés meghalad egy bizonyos szintet. (pl.: 1%- ot)
Hívásengedélyezési módszerek – 1 » Várakozási sor matematikai modellezése » elveszett csomagok aránya » sor telítettségi valószínűség K » Ekvivalens kapacitás » forgalom leíró és igényelt minőségi paraméterekből » egy kapcsolatra illetve folyamok aggregáltjára is |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Matematikai modell: átlagos esetet modellez, pedig nekünk a legrosszabb viselkedés kellene.
A várakozási sor hossza: X (valószínűségi változó)
P[X > Lmax] valószínűséget szeretnénk egy szint alatt tartani
Ekvivalens kapacitás: az átlagos és csúcs kapacitások közötti érték, ami elég jól jellemzi a folyamatot.
Matematikai kitérő: ekvivalens kapacitás » Foglalás » csúcssebességre 🡺 rossz kihasználtság » átlagsebességre 🡺 jelentős csomagvesztés » Ekv.kap valahol a kettő között, egy megadott csomagvesztési valség függvényében: » Farokvalószínűség becslők » Markov-egyenlőtlenség: » Csernoff-korlát: C>M » Hoeffding-korlát: |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Kérdés: mi az a sebesség, ami mellett a csomagvesztés egy bizonyos küszöbérték alatt marad? Egy szűk, de jól számolható modellt keresünk.
Döntés elosztott – egy csomópontban vizsgáljuk: Markov-egyenlőtlenséggel: P[X>0] ≤ M/C < pf – farok eloszlás valószínűség, ahol X az aggregált forgalom. Ez a leíró sem veszi figyelembe a várakozási sort.
M várható értékét az utóbbi időből származó méréssel becsüljük, az új folyamatoknál ezt csúcssebességgel vesszük figyelembe.
Ha M/C-pnew ≤ pf, akkor beengedjük az új hívást, ha nem, akkor nem
Ez az egész azon alapszik, hogy aki régóta bent van, annak az átlagos sebessége lassan változik.
Hívásengedélyezési módszerek – 2 Forgalmi leíró adatblokk tartalma: » Forgalmi paraméterek: új igény, új számítás » Előre definiált osztályok: előre számítható » N osztály: N dimenziós döntési hiperfelület folyamok száma elutasítás 1. osztály elfo- gadás 2. osztály folyamok száma » Neurális hálózatokkal is leírható |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Hogy határozható meg egy, a görbéket közelítő egyenes? (Lehetőleg úgy, hogy a mi szempontrendszerünknek a lehető legjobban megfeleljen…)
Mérés alapú hívásengedélyezés » Probléma a forgalmi leíró megadásával: » túl „nehéz kérdés” → túlbecslés » a hálózat torzítja » új alkalmazás típusok? » Mérés alapú hívásengedélyezés » Egyszerűsített forgalmi leíró blokk » Hálózat terhelése: mérés alapján » Előnyök: az előbb felsorolt nehézségeket kiküszöböli » Hátrányok: » nagyobb hibalehetőség » kevesebb lehetőség a „rendszabályozásra” |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Forgalmi leíró nem mindig adható, ezért inkább túlbecsüljük, amivel romlik a hálózat kihasználtsága Egyszerűsített forgalmi leíró blokk: pl.: csak egy peak rate-et tartalmaz
Kevesebb lehetőség a rendszabályozásra: a torlódást nehezebb elkerülni.
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Mit mérjünk? » Forgalmi terhelés » csomópontokban » határpontok alapján becslés » Kapcsolat-minőség » Próbaforgalom segítségével |
Híváseng. mozgó hálózatokban » Új problémák: » Felhasználó mozog → hívásátadás terheletlen hálózatrészből terheltbe → másodfajú hiba új igény nélkül! » Új és átadott hívások más tartásidő eloszlással modellezhetők » Javasolt megoldások: » Védőcsatornák az átadott hívásoknak » Prioritásos sorbanállás: » minden kérés elfogadása, ha van szabad csatorna » ha nincs: részben elutasítás, részben sorba állítás » különböző sorkezelési algoritmusok |
SZOLGÁLTATÁS-MINŐSÉG BIZTOSÍTÓ INFORMÁCIÓS TECHNOLÓGIÁK LABORATÓRIUMA
TÁVKÖZLÉSI ÉS MÉDIAINFORMATIKAI TANSZÉK, BME
Egy lehetséges megoldás pl.:
Az kap nagyobb prioritást, aki „átesik” a hálózatba, vagyis aki másik hálózatból jött, és az kap kisebbet, aki innen akar hívást kezdeményezni.