PA159 - Kvalita služeb a fronty 16. 11. 2007 Kvalita služeb ■ Základní parametry ■ Kapacita linky ■ Zpoždění ■ Rozptyl ■ Technické zajištění ■ Kapacita linek * Na lince se data nepředbíhají ■ Vysílající/přijímající ■ Aktivní prvky uvnitř sítě PA159 2 Podzim 2007 Kvalita ■ Vysílající ■ Na aktivních prvcích ■ Na straně výstupních portů ■ Délka souvisí s kapacitou ■ Ovlivňují ■ Zpoždění a jeho rozptyl ■ Řazení paketů na výstupu PA159 ižeb a fronty 3 Podzim 2007 Fronty FIFO (FCFS) Fair Queuing Processor Sharing Bit-round Fair Queuing Generalized Processor Sharing Weighted Fair Queuing PA159 4 FIFO ■ Nejjednodušší uspořádání ■ First In First Out (First Come First Serve) ■ Jedna fronta pro každý výstupní port ■ Nevýhody: 1. Žádná podpora priority 2. Obecně větší průměrné zpoždění paketů (nerozlišuje mezi dlouhými a krátkými pakety) 3. Agresivní TCP proudy zvýhodněny ■ Kdo se dostane dřív do fronty, bude dřív poslán PA159 5 Podzim 2007 Fair Queuing ■ Vícenásobné fronty pro každý výstupní port ■ Rodělení podle vstupních proudů ■ Každý příchozí paket umístěn do příslušné fronty ■ Fronty obsluhovány poradě, vždy po jednom paketu ■ Tím je zajištěna „férovost" obsluhy ■ Prázdná fronta se přeskočí Odstraní většinu nevýhod FIFO front Avšak: penalizuje krátké pakety PA159 6 Podzim 2007 Processor Sharing ■ Idealizovaný, prakticky nepoužitelný protokol ■ Fronty jako u FIFO ■ Namísto paketů posílá bity ■ Každá fronta sdílí přesně 1/N celkové kapacity PA159 7 Podzim 2007 Základní pojmy (všechny údaje jsou normalizovány na výstupní rychlost datového toku) cyklus = jeden průchod frontami R(ť) = „virtuální čas", tedy počet cyklů do času t N (ť) = počet neprázdných front v čase t P? = doba přenosu paketu i ve frontě a. t? = čas příchodu paketu i do fronty a. S? = hodnota R(t) na začátku přenosu paketu i F? = hodnota R(t) na konci přenosu paketu i Změna virtuálního času (závisí na obsazení front): R'(t) = ^R(t) =------ *„ u at max{l, iV(t)} PA159 8 Podzim 2007 PS - doba přenosu ■ Pro velikost paketu sf platí: L kde v^it) je rychlost přenosu výstupního kanálu. ■ Virtuální čas zavádíme proto, že v něm platí: pQL OL tedy doba přenosu je právě rovna velikosti paketu PA159 9 Podzim 2007 PS - vývoj v čase ■ Vztahy pro jednu frontu: FOL _ QOL . pOL Sf = max{FPLi,Ä(rf)} ■ Umožní spočítat virtuální čas konce přenosu paketu ■ Neříká nic o reálném čase (závisí na „plnosti" front) ■ Garantuje zcela férový přístup PA159 10 Podzim 2007 Bit-round Fair Queuing ■ Emulace PS na úrovni paketů ■ Asymptoticky se blíží PS ■ Principy ■ Spočítá Sf a F? každého příchozího paketu ■ Vybere pro přenos vždy paket s nejnižší hodnotou F? ■ Pořadí přenosu paketů (start/konec) různé u PS a BRFQ, avšak asymptoticky se BRFQ chová stejně jako PS ■ Asymptoticky = pakety délky 1 bit PA159 11 Podzim 2007 Prioritní fronty ■ PS (a BRFQ) „férové" ■ Žádný paket „nepředbíhá" ■ Není rozdíl mezi proudy s dlouhými i krátkými pakety ■ Nepodporují prioritu ■ Nemožňují uprednostnení určitých spojení PA159 12 Podzim 2007 Generalized Processor Sharing Založeno na explicitním řízení alokace front GPS jako idealizace akceptovaného řešení: Weighted Fair Queuing Rozšíření PS: ■ 4>a je váha přidělená toku ol\ určuje, kolik bitů se má z fronty ol přenést v každém cyklu na Sf = maxí^i, Ä(7f)} PA159 13 Podzim 2007 GPS-další vztahy Efektivní délka paketu normalizována faktorem l/a ■ Větší váha tedy „zkracuje" pakety Rychlost obsluhy g^ neprázdného toku i je E-J kde C je kapacita výstupní linky a suma jde přes všechny aktivní fronty/toky PA159 14 Podzim 2007 GPS - garance zpoždění Uvažujme několik toků, které jsou dostatečně dlouho nečinné, takže všechny „kyblíčky" (buckets) jsou plné. Poté všechny toky začnou vysílat maximální povolenou rychlostí. Sít musí být konfigurována tak, že je schopna těmto kombinovaným požadavkům vyhovět (garance kvality služby pro každý tok). To znamená, že každý garantovaný tok je R^ Tokeny do „kyblíčků" jsou přidávány stejnou rychlostí, jakou jsou z nich odebírány, tj. délka fronty není větší než velikost „kyblíčku". Maximální zpoždění je tak podíl velikost „kyblíčku" (Bi) a rychlosti toku. Ri PA159 15 Podzim 2007 Wieghted Fair Queuing (WFQ) Emulace GPS při přenosu paketů a nikoliv pouze bitů Vybrán je vždy paket s nejnižším F^ podle rovnice pro GPS. Vlastnosti GPS zůstávají (asymptoticky) zachovány: ■ . B i \Ki — l)Li Ki Xmax Ri Ri ra=l Cm ■ kde Di, Ri a Bi viz výše a pro ostatní parametry platí: Ki = počet uzlů, kterými tok i prochází Li = délka největšího paketu toku i Lmax = délka největšího paketu na všech cestách a uzlech Cm = výstupní kapacita uzlu m PA159 16 Podzim 2007 WFQ - diskuse Term (^ 1)jL^ zahrnuje zpoždění každého paketu na každém uzlu Term e* max je důsledkem přenosu paketů a nikoliv bitů. Komentář: ■ Vybereme-li k přenosu delší paket a v průběhu přenosu přijde kratší paket, pak při GPS by mohl kratší paket být doručen dříve, než se dokončí přenos dlouhého paketu. Při WFQ je třeba počkat na dokončení přenosu delšího paketu, než může být přenesen i ten kratší Výsledkem je delší zpoždění, než garantuje GPS. PA159 17 Podzim 2007 WFQ - důsledky ■ Omezení Di shora je základem pro poskytnutí garantované služby ■ Je možno zvolit odpovídající vlastnosti směrovače (velikost „kyblíčku", rychlost přitékání tokenů, ...) ■ Maximální délka fronty je úměrná největšímu zpoždění a blíží se giDi (kde gi definované výše je rychlost, s jakou odchází tok i). ■ Důsledek: Je možno rozeznat požadavek, který by nebylo lze uspokojit, a takový požadavek odmítnout. Pro ostatní lze služby garantovat. PA159 18 Podzim 2007 Fronty - shrnutí ■ Struktura front a způsob manipulace s nimi zásadně ovlivňuje možnosti garance zpoždění ■ Ukázali jsme, že je možno shora omezit maximální možné zpoždění ■ Nutno kombinovat s dalšími postupy PA159 19 Podzim 2007 Problém ochrany proti zahlcení ■ TCP a podobné algoritmy reagují na přetížení sítě ■ To může být pozdě, navíc použití klasického TCP mechanismu má určité nedostatky: ■ Ztracené pakety musí být znovy přeneseny (další zvýšení zátěže, vysoké zpoždění) ■ Fenomén globální synchronizace: * Při přetížení směrovače se začnou ztrácet pakety všech TCP proudů * Všechny přejdou na slow start a tím začne být sít nedostatečně využívána * To všechny rozeznají a sít opět (synchronně) přetíží PA159 20 Podzim 2007 Proaktivní ochrana ■ Možné řešení: ■ Zvětšení front (buferů): dlouhodobě neúčinné (zvýšení zpoždění, není horní limit) ■ Včasná detekce zahlcení a výběr jednoho (postupně více) TCP proudů, které budou zpomaleny: prokativní ochrana proti zahlcení ■ Odstranění globální synchronizace, lepší využití sítě PA159 21 Podzim 2007 Random Early Detection ■ Zahazuje pakety dříve, než je fronta zcela zaplněna ■ Jednoduchý princip po příchodu paketu: ■ Pokud je ve frontě dostatek místa, paket je zpracován ■ Pokud je fronta delší než THmin ale kratší než THm3L^ pak se některé pakety zahodí ■ Pokud je fronta delší než THm3L^ pak se zahodí každý příchozí paket ■ Náhodným zahozením paketu se předchází zahlcení PA159 22 Podzim 2007 Random Early Detection - Algoritmus Spočti průměrnou velikost fronty avg if avg < THmin ulož paket do fronty else if Tífmin < avg < Tífmax spočti pravděpodobnost Pa s pravděpodobnosti Pa zahoď paket else ulož paket do fronty °/0 Pravděpodobnost 1 — Pa else if Tífmax < avg zahoď paket PA159 23 Podzim 2007 Random Early Detection - avg ■ Průměrná velikost fronty (avg)\ ■ if fronta je neprázdná avg = (1 — wq)avg + wqq else m = f (time — qJbimé) avg = (1 — Wq^avg ■ kde qjtime = čas, kdy se fronta vyprázdnila wq = váha fronty q = aktuální délka fronty Ume = aktuální čas f{t) = lineární funkce času t PA159 24 Podzim 2007 RED-doplnění Váha fronty (wq) filtruje dočasná přetížení (doporučená hodnota 0,002) - zabraňuje přehnaně rychlé reakci na nával (burst) Pravděpodobnost Pa je počítána postupně: ■ Nejprve se spočte Ph\ _ avg - THmin b ~ Ť-řř _ rpTT x ^max ± nmax ± -i^niin ■ Z něj se spočte pravděpodobnost zahození paketu Pa\ i Pn = -^— count kde count je délka serie nezahozených paketů a Pmax je pravděpodobnost zahození paketu při frontě délky THm3L^ (obvykle 1) PA159 25 Podzim 2007 Pravděpodobnost jako funkce paketů ve frontě PA159 26 Podzim 2007 RED - vlastnosti P a Graf Pa jako funkce count: ■ Velmi malá hodnota pro většinu hodnot count ■ Extrémně rychle roste jak se count blíží-------1 ■ count tuto hodnotu nemůže překročit Garantuje vysokou rovnoměrnost zahazování paketů Při zatížení lepší vlastnosti než prosté zahazování paketů při plné frontě PA159 27 Podzim 2007 ■■■f ■ ■ v . v r m m O Zajištěni zdroju ■ Řízení zdrojů ■ Technické predppoklady nestačí ■ Je nutno koordinovat požadavky na zdroje ■ Nezbytné signalizační/řídící protokoly (control protocol) PA159 28 Podzim 2007 Sestavení relace ■ Součástí rezervace zdrojů (resource reservation) ■ Musí zajistit dostatek prostředků pro garanci služby ■ Musí spolupracovat s dynamickým směrováním (IP netvoří okruhy) ■ Princip měkkého stavu (soft state): stavová informace se drží pouze krátkou dobu, pak musí být znovu potvrzena ■ Řešení pro Internet ■ RSVP (Resource ReSerVation Protocol) ■ DiffServ (Differentiated Services) PA159 29 Podzim 2007