Nástroje na predchádzanie zahlteniu (Congestion Avoidance)
K zahlteniu dochádza vtedy, ak množstvo dát, ktoré vstupujú do siete je väčšie, ako množstvo, ktoré je v danom momente sieť schopná spracovať. Hlavnou príčinou, prečo dochádza k zahlteniu v sieti je obmedzenosť sieťových prvkov. Napríklad výkon procesora smerovača nemusí stačiť na spracovanie dát, ktoré ním aktuálne prechádzajú, a tým sa predlžuje doba spracovania jednotlivých paketov, alebo rôzna priepustnosť vstupnej a výstupnej linky.
Congestion Avoidance Tools (nástroje na predchádzanie zahlteniu) sú nástroje, ktoré pomáhajú predchádzať zahlteniu v sieti pomocou rôznych algoritmov správania sa.
Transmission Control Protocol (TCP)
TCP je spojovo-orientovaný protokol, čo znamená, že ak chcú spolu komunikovať dve zariadenia, najprv musí byť medzi nimi vytvorené spojenie. Spojenie je založené pomocou 3-way handshake. Jedno z dvojice zariadení, ktoré chcú spolu komunikovať je v pozícii servra a druhé v pozícii klienta. Pre vytvorenie spojenia sa používa 3-way handshake. Server počúva na určitom porte a čaká na prichádzajúce spojenia. Toto sa nazýva pasívne počúvanie. Aktívne spojenie vzniká vtedy, ak klient pošle požiadavku o založenie spojenia a klient posiela SYN segment. Sekvenčné číslo nastaví na ľubovoľnú hodnotu (X). Server odpovedá segmentom SYN-ACK. Potvrdzovacie číslo SYN-ACK je o jedno vyššie ako sekvenčné číslo, ktoré odoslal klient (X+1), a sekvenčné číslo SYN-ACK je ľubovoľné číslo (Y). Klient odpovedá ACK segmentom. Sekvenčné číslo je hodnota prijatého ACK zvýšená o jeden (X+1) a potvrdzovacie číslo je hodnota prijatého sekvenčného čísla zvýšená o jeden (Y+1).
Obr. 1 3-way handshake (založenie TCP spojenia)
Spoľahlivosť TCP protokolu určuje niekoľko dôležitých mechanizmov. Sú to napríklad sekvenčné (SEQ) čísla, ktoré slúžia na identifikovanie každého TCP segmentu. Na základe tohto čísla môže cieľové zariadenie zrekonštruovať dáta v správnom poradí. Takisto dokáže na základe tohto čísla zistiť, ktoré segmenty boli počas prenosu stratené a môže žiadať o ich preposlanie. Prijímateľ po prijatí TCP segmentu potvrdí prijaté segmety a zároveň požiada o poslanie ďalšieho segmentu. Toto číslo sa nazýva potvrdzovacie (ACK).
Kumulatívne potvrdzovanie môže viesť k neefektívnosti, pretože príliš zamestnáva TCP protokol. Predpokladajme, že je potrebné preniesť 1000 bajtov, ktoré sú rozdelené v 10 rôznych TCP segmentoch a prvý paket nebol doručený. Prijímateľ nepotvrdí úspešné prijatie bajtov 100 až 999, pretože v prípade kumulatívneho potvrdzovania musí potvrdiť prijatie bajtov 0 až 99. Odosielateľ nedostanie potvrdenie, tak musí znovu odoslať všetkých 1000 bajtov. Túto situáciu rieši selektívne potvrdzovanie (SACK), ktoré umožňuje prijímateľovi potvrdiť prijatie nesúvislých blokov segmentov. Potvrdenie obsahuje bloky, ktoré boli prijaté. Každý blok je vyjadrený začiatočným a koncovým sekvenčným číslom. V tomto konkrétnom prípade by prijímateľ odoslal SACK so sekvenčnými číslami 100 a 999. Na základe tohto odosielateľ prepošle prvý segment, bajty 0 až 99.
Veľkosť TCP okna (window size) udáva množstvo prijatých dát, ktoré odosielateľ môže poslať, kým nedostane od prijímateľa potvrdzujúcu správu. Po odoslaní tohto množstva dát, odosielateľ musí čakať na potvrdenie. Prvá veľkosť okna sa definuje pri vytváraní TCP spojenia, potom sa táto veľkosť mení podľa situácie. Po prijatí potvrdenia od prijímateľa odosielateľ zväčší veľkosť TCP okna a bude ju zvyšovať dovtedy, kým nezaznamená nedoručenie segmentov (nedostane potvrdenie o prijatí od prijímateľa). Po zistení, že pakety neboli doručené, odosielateľ zmenší veľkosť TCP okna. Odošle niekoľko segmentov s novou veľkosťou okna a ak nezistí žiadnu stratu, znovu začne túto veľkosť zväčšovať. V sieti prebieha naraz množstvo TCP spojení a ak zariadenie začne zahadzovať segmenty, všetci odosielatelia znížia veľkosť TCP okna. Tento stav sa nazýva globálna synchronizácia.
Ukončenie spojenia prebieha pomocou 4-way handshake a spojenie sa ukončuje na každej strane nezávisle. Ak chce niektorá strana ukončiť spojenie, vyšle FIN segment. Druhá strana FIN segment potvrdí pomocou ACK. Ukončenie TCP spojenia vyžaduje odoslanie FIN segmentu na každej strane TCP spojenia.
Výhody potvrdzovania doručených paketov dokážu efektívne využívať nástroje na predchádzanie zahlteniu, pretože ak dôjde k zahodenie pakety, odosielateľ zníži svoju prenosovú rýchlosť
Tail drop
Je to najjednoduchší nástroj pre predchádzanie zahlteniu. Ak sieťové zariadenie nemôže prichádzajúci paket okamžite spracovať, zaradí ho do frontu (queue). Tento front má však obmedzenú veľkosť. Keď dôjde k zaplneniu frontu, zariadenie bude ďalšie prichádzajúce pakety zahadzovať , až kým sa neuvoľní miesto vo fronte.
Mechanizmus má niekoľko nevýhod:
- Tail drop nezaraďuje pakety do tried a po zaplnení frontu sú všetky prichádzajúce pakety zahadzované bez ohľadu na typ.
- Ak smerovač zahadzuje prichádzajúce pakety od viacerých odosielateľov, títo znížia prenosovú rýchlosť, ako odpoveď na zahadzovanie. To má za následok extrémne zníženie využitia šírky pásma. Postupne zvyšujú prenosovú rýchlosť, až pokiaľ znovu nedôjde k zahlteniu. Toto správanie sa nazývame globálna synchronizácia (global synchronization).
Random Early Detection (RED)
RED je mechanizmus, ktorý náhodne zahadzuje prichádzajúce pakety, aby nedošlo k úplnému zaplneniu frontu. Implementovaním RED sa znižuje pravdepodobnosť, že dôjde k globálnej synchronizácii, pretože je malá šanca, že smerovač bude pri plnom zaplnení frontu zahadzovať všetky prichádzajúce pakety, ako to bolo v prípade použitia Tail drop mechanizmu. RED sleduje priemernú veľkosť fronty, na ktorom je založená stratégia zahadzovania paketov. Ak veľkosť fronty dosiahne určitú hranicu, smerovač začne náhodne zahadzovať pakety. Pravdepodobnosť zahodenia rastie spolu s veľkosťou frontu. RED využíva vlastnosti TCP protokolu, ktorý garantuje správne doručenie paketov. Po zahodení paketu zdroj zníži rýchlosť vysielania dát a nezvýši ju dovtedy, pokiaľ nebudú všetky pakety doručované.
Zahadzovanie paketov je založené na veľkosti priemernej dĺžky fronty. Ak je menšia ako spodná hranica, žiadne pakety nebudú zahodené a budú zaradené do fronty. Ak sa nachádza medzi spodnou a vrchnou hranicou, RED začne náhodne zahadzovať prichádzajúce pakety. Po dosiahnutí hornej hranice budú všetky prichádzajúce pakety zahadzované. Proces rozhodovania, či bude paket zahodený je znázornený na Obr. 2 RED stratégia zahadzovania paketu.
Obr. 2 RED stratégia zahadzovania paketu
Výpočet priemernej dĺžky paketu
Priemerná dĺžka frontu je vypočítavaná pri príchode paketu. Vypočítava sa na základe aktuálnej a predchádzajúcej dĺžky. Ak do zariadenia neprichádzajú žiadne pakety, priemer nie je aktualizovaný.
Priemerná dĺžka frontu sa počíta pomocou vzorca:
AVGk = (1-w) * AVGk-1 + w*q
AVGk – nová priemerná dĺžka frontu
AVGk-1 – predchádzajúca dĺžka frontu
w – exponenciálny vážený faktor, Exponential Weighted Moving Average (EWMA), je navrhnutý tak, aby krátkodobé nárasty veľkosti frontu alebo dočasné zahltenie nespôsobilo nárast priemernej dĺžky frontu.
q – aktuálna veľkosť frontu
Výpočet pravdepodobnosti zahodenia paketu
Po vypočítaní priemernej dĺžky frontu sa na základe tejto hodnoty smerovač rozhodne, čo s paketom urobí. Ak sa priemerná dĺžka frontu nachádza medzi spodnou a hornou hranicou, vypočíta pravdepodobnosť zahodenia paketu a na základe nej sa rozhodne, či paket bude zahodený, alebo zaradený do frontu.
Vzorec na výpočet lineárnej pravdepodobnosti:
Pb = PMAX * ( (AVG – MINthres) / (MAXthres – MINthres) )
Pb – pravdepodobnosť zahodenia paketu
PMAX – maximálna pravdepodobnosť zahodenia, kedy AVG je rovné MAXthres
AVG – priemerná dĺžka frontu
MINthres – spodná hranica
MAXthres – vrchná hranica
Potom prevdepodobnosť zahodenia je definovaná ako:
Pa = Pb / (1 – count * Pb )
Pa – pravdepodobnosť zahodenia paketu
count – počet paketov, ktoré boli zaradené do frontu (neboli zahodené)
Tieto vzorce platia pre veľkosť frontu v paketoch. Ak je veľkosť udávaná v bajtoch, je potrebné medzi výpočtom Pa a Pb vykonať nasledujúci výpočet:
Pb = Pb* (VeľkosťPaketu / MaximálnaVeľkosťPaketu)
Výhodou oproti „tail drop“ je, že globálna synchronizácia môže nastať len výnimočne. RED využíva výhody TCP protokolu, ktorý potvrdzuje doručené pakety. Ak zdroj nedostane potvrdenie o doručení paketu od prijímateľa, zníži prenosovú rýchlosť a tým sa zníži aj objem prenášaných dát. Pri „tail drop“ dôjde k zníženiu prenosovej rýchlosti u všetkých zdrojov naraz, a prenosová linka je neefektívne využívaná. RED zahadzuje pakety náhodne, takže k zníženiu prenosovej rýchlosti dôjde len pri niektorých TCP spojeniach, čím sa zníži objem prenášaných dát a uvoľní sa miesto vo fronte pri efektívnom využití prenosovej linky. Znázornené je to na Obr.3 Porovnanie Tail drop (uncontrolled congestion) a RED.
Obr. 3 Porovnanie Tail drop (uncontrolled congestion) a RED
Nevýhodou tohto mechanizmu je, že je efektívny len pre TCP protokol. UDP protokol nepodporuje potvrdzovanie o doručení paketov, takže zahodený paket nie je signálom pre zdroj, aby znížil prenosovú rýchlosť. Medzi ďalšie nedostatky patrí, že pakety, ktoré boli zahodené, sa musia znovu preposielať a tým dochádza k plytvaniu sieťových prostriedkov a zložitosť jeho nastavenia a určenie správnych hraníc.
Model Differentiated Service (DiffServ)
DiffServ je sieťová architektúra, ktorá vytvára triedy rôznej priority, do ktorých zaraďuje pakety. Na základe tried sú paketom pridelené rôzne úrovne služieb. Pakety označujú okrajové smerovače. Tie im priraďujú hodnotu nazývanú differentiated services code point (DSCP) a na základe tejto hodnoty sieťové zariadenia volia Per-hop Behavior (PHB). Táto hodnota je uložená v hlavičke paketu, konkrétne v IPv4 pakete je to pole nazývané Type of service (ToS) o veľkosti 1 Byte. V tejto hlavičke sú zakódované hodnoty IP precedence (IP priorita) a DSCP. IP precedence využíva 3 bity a môže nadobúdať 8 hodnôt (0 až 7), ale bity 6 a 7 sú vyhradené pre potreby siete, 0 je základné označenie pre best efford tok, hodnota 5 je určená pre hlas, hodnota 4 pre video a hodnota 3 pre signalizáciu hovorov. Hodnoty 1 a 2 nemajú definované pre aký typ dát majú byť určené. DSCP využíva ďalšie 3 bity, čo umožňuje nadobúdať 64 hodnôt (0 až 63). Bližšie to znázorňuje obrázok Obr. 4 IPv4 Tos Bajt
Obr. 4 IPv4 ToS Bajt
Hodnoty, ktoré DSCP nadobúda môžu byť vyjadrené číselne, alebo aj výrazmi, nazývanými aj Per-Hop Behavior (PHB). Definované sú tieto PHB triedy:
- Best Efford (BE) – Nemá prioritu a doručuje iba keď sú voľné sieťové prostriedky. Základné označenie, má hodnotu 0. Pakety sa touto hodnotou označia, ak nespĺňajú podmienky žiadnej inej triedy, alebo služby bez požiadvky na kvalitu, napr web, email.
- Assured Forwarding (AF) – Zabezpečené smerovanie. Pri tejto triede je najdôležitejšie správne doručenie paketov a je uprednostnené pred oneskorením a jitter. Za označením AF idú dve číslice. Prvá nadobúda hodnoty 1 až 4 a označuje triedu. Druhá číslica môže mať hodnoty 1 až 3 a pomocou tejto hodnoty sa rozhoduje, či paket bude zahodený (1 malá pravdepodobnosť, 2 stredná pravdepodobnosť, 3 veľká pravdepodobnosť)
- Expedited Forwarding (EF) – Urýchlené smerovanie. Využívajú ho aplikácie, ktoré vyžadujú nízke oneskorenie, minimálnu stratovosť a minimálny jitter. Takto označené pakety majú prednosť pred ostatnými. Nadobúdajú hodnotu DSCP 46.
Existuje ešte jedna trieda, Class-Selector (CS), ktorý je kompatibilný s IP precedence. Nadobúda hodnoty 1 až 7.
Per-hop Behavior (PHB)
PHB je spôsob, ako sa bude smerovač správať k prichádzajúcemu paketu. Je založené na rôznych DSCP hodnotách.
Weighted Fair Queuing (WFQ)
Je jednou z frontovacích techník. Založený je na toku dát. Je vylepšením základných frontovacích metód a znižuje oneskorenie a jitter. WFQ spravodlivo rozdeľuje dostupnú šírku pásma medzi všetky aktívne toky. WFQ nepriraďuje každému toku jeden front, ale definujú sa triedy a každá trieda dostane vlastný front. Klasifikácia do tried sa určuje pomocou parametrov zdrojová a cieľová IP adresa, zdrojový a cieľový TCP alebo UDP port, typ protokolu (TCP alebo UDP) a Type of service field. Pri rozdeľovaní šírky pásma môže využívať IP prioritu ako váhu pri rozdeľovaní. Ak využíva IP prioritu, potom toky s vyššou prioritou majú dostupnú väčšiu šírku pásma ako toky s menšou prioritou. Priraďovanie paketov do jednotlivých tried prebieha automaticky.. WFQ zahadzuje pakety najagresívnejších tokov.
Existujú štyri typy WFQ:
• Flow-based WFQ (WFQ)
• Distributed WFQ (DWFQ)
• Class-based WFQ (CBWFQ)
• Distributed class-based WFQ (DCBWFQ)
Class-Based Weighted Fair Queuing (CBWFQ)
CBWFQ je založený na Weighted fair queuing (WFQ) a navyše umožňuje vytvárať užívateľovi vlastné skupiny prevádzky, definovať rôzne správanie pre rôzne skupiny a zabezpečiť minimálnu šírku pásma pre každú triedu. Tail drop je defaultná technika na zahadzovanie paketov, ktorá sa vo frontoch uplatňuje. Na predchádzanie zahlteniu je možné použiť CBWFQ v kombinácii s WRED.
Weighted Random Early Detection (WRED)
WRED mechanizmus je nástroj na predchádzanie zahlteniu v sieti, ktorý je vylepšením RED. WRED zahadzuje pakety väčšinou výberom na základe IP priorite (IP precedence) alebo differentiated services code point (DSCP). Pravdepodobnosť, že pakety, ktoré sú označené vyššou IP prioritou budú zahodené je menšia ako pakety označené nižšou IP prioritou. To znamená, že dáta s vyššou prioritou budú doručené s väčšou pravdepodobnosťou ako dáta s menšou prioritou. Takto sa docieli uprednostňovanie dát podľa ich dôležitosti.
Podobne ako RED, aj WRED monitoruje priemernú dĺžku frontu v smerovači, a na základe tejto dĺžky sa rozhoduje, či paket zahodí, alebo zaradí do frontu. Ak je priemerná dĺžka frontu väčšia ako užívateľom definovaná spodná hranica, smerovač začne náhodne zahadzovať pakety. Ak dĺžka frontu rastie, rastie aj pravdepodobnosť zahodenia paketu. Po presiahnutí užívateľom nastavenej hornej hranici smerovač začne zahadzovať všetky prichádzajúce pakety. WRED poskytuje rôzne hranice pre odlišné IP priority, čo umožňuje poskytnúť odlišnú kvalitu služby pre rozličný typ prevádzky, pretože pre každú triedu smerovač rozlišuje rôzne stratégie správania sa. Je možné WRED nastaviť, aby ignoroval IP prioritu pri rozhodovaní sa o zahodení paketu, Takéto správanie sa označuje ako non-weighted RED.
WRED znižuje šancu tail drop zahadzovania paketov tým, že pakety zahadzuje ešte pred tým ako nastane naplnenie frontu. Takto sa zabráni veľkému zahadzovaniu paketov v rovnakom čase, čím sa minimalizuje šanca, že dôjde ku globálnej synchronizácii. Výsledkom tejto stratégie je lepšie využitie prenosovej šírky pásma. WRED je účinné len pri TCP spojeniach, pretože odpoveďou na zahodený paket je zníženie prenosovej rýchlosti zdroja. Pri iných protokoloch nemusí byť vôbec účinný, lebo zdroje nemusia na zahodenie paketu reagovať, alebo môžu preposlať nedoručené pakety pri nezmenenej prenosovej rýchlosti a nezníži sa tak stupeň zahltenia. WRED častejšie zahadzuje pakety, ktoré nepochádzajú z TCP spojenia, pretože takéto pakety označuje prioritou 0, čiže najnižšou prioritou.
Rôzne profily WRED správania sa sú založené na IP priorite (8 profilov) a na DSCP (64 profilov). Každý profil má tri konfigurovateľné parametre, ktorými sú spodná hranica, horná hranica a hranica maximálnej pravdepodobnosti zahodenia.
Výpočet priemernej dĺžky frontu
Na výpočet pravdepodobnosti WRED nepoužíva aktuálnu veľkosť frontu. Priemerná dĺžka frontu je počítaná na základe predchádzajúcej priemernej veľkosti a aktuálnej veľkosti.
priemer = (predchádzajúci_priemer *( 1-(1/2)^n )) + ( aktuálna_veľkosť * (1/2) ^ n)
n – hodnota, ktorú užívateľ môže zmeniť. Je to exponenciálny vážený faktor, na ktorom záleží dôležitosť predchádzajúceho priemeru.
Predchádzajúci priemer sa stane dôležitý, ak je hodnota faktora n vysoká. Veľké n spôsobí, že smerovač začne pakety zahadzovať neskoro a v zahadzovaní bude pokračovať aj keď veľkosť frontu klesne pod spodnú hranicu.
Ak je n príliš vysoké, WRED nemusí reagovať na zahltenie.
Ak j n príliš nízke, WRED môže zahadzovať niektoré pakety zbytočne.
Defaultne je hodnota n nastavená na 9.
Hodnoty ovplyvňujúce správanie sa WRED
Existujú 3 základné hodnoty, ktoré ovplyvňujú rozhodovanie smerovača po príchode paketu. Tieto hodnoty majú defaultné nastavenia, ale je možné zmeniť ich poľa potreby.
- Spodná hranica – ak je priemerná dĺžka frontu menšia ako spodná hranica, žiadne pakety nie sú zahadzované a všetky sú zaradzované do frontu. Po presiahnutí spodnej hranice smerovač začne zahadzovať pakety a pravdepodobnosť zahodenia lineárne stúpa s priemernou dĺžkou frontu. Pri veľmi nízkej spodnej hranici môže dôjsť k zbytočnému vyhodeniu paketu a prenosová linka nebude plne využitá.
- Horná hranica – ak priemerná dĺžka frontu presiahne hornú hranicu, všetky prichádzajúce pakety bude smerovač zahadzovať. Ak je rozdiel medzi spodnou a hornou hranicou príliš malý, môže dôjsť ku globálnej synchronizácii. Rozsah, ktorý môže spodná a horná hranica nadobúdať je od 1 po 4096. Defaultne je táto hodnota nastavená na 40.
- Ukazovateľ pravdepodobnosti zahodenia – Môže nadobúdať hodnoty 1 až 65536. Napríklad, ak je ukazovateľ 256, znamená to, že každý 256-ty paket bude zahodený, ked priemerná dĺžka frontu bude na hornej hranici. Defaultne je táto hodnota nastavená na 10.
Class-Based WRED
Class-Based WRED je kombinácia class-based weighted fair queuing (CBWFQ) a WRED. Každá trieda má vlastnú frontu a vlastné hranice. Ako metóda, pomocou ktorej sa bude rozhodovať, či sa paket zahodí, alebo sa zaradí do fronty, je defaultne nastavená metóda tail drop, ale môže byť zvolený WRED. WRED sa bude rozhodovať na základe typu prevádzky a ďalej na IP priorite alebo DSCP hodnote.
DSCP-Based WRED (Expedited Forwarding)
Modifikovaný WRED algoritmus, ktorý používa DSCP označenie paketov, konkrétne pakety patriace do triedy Expedited Forwarding (EF). Zaisťuje čo najrýchlejší odchod paketov zo zariadenia, aby sa tak zaistilo čo najmenšie možné oneskorenie pre citlivé aplikácie. V prípade výskytu viacerých aplikácii, ktoré používajú EF PHB, zaisťuje potrebnú šírku pásma. Pakety označené EF nadobúdajú DSCP hodnotu 46. Spodná hranica, od ktorej smerovač začne vyhadzovať pakety je defaultne nastavené na vysokú hodnotu. Konkrétne je to hodnota 36. Vrchná ja nastavená na hodnotu 40. Týmto sa zaistí, aby takto označené pakety boli zahadzované veľmi neskoro, to znamená, až pri vysokom stupni zahltenia.
DSCP-Based WRED (Assured Forwarding)
Ďalší modifikovaný WRED algoritmus, ktorý je založený na DSCP označovaní. Oproti DSCP-Based WRED (Expedited Forwarding) algoritmu, tento využíva triedy Assured Forwarding (AF). Tento algoritmus zaisťuje určité množstvo šírky pásma pre AF triedy. Pakety, ktoré používajú AF PHB sú označované DSCP hodnotou v binárnom tvare „XXXYY0“, kde „XXX“ je číslo triedy, do ktorej paket patrí a „YY“ je pravdepodobnosť zahodenia paketu. Názorne to zobrazuje Obr. 5 PHB kódovacia schéma (binárny tvar)
Obr. 5 PHB kódovacia schéma (binárny tvar)
Defaultne sú nastavené spodné hranice pradvdepodobnosti zahodenia paketu nasledovne:
- Low Drop Probability (nízka pravdepodobnosť zahodenia) – spodná hranica nastavená na hodnotu 32
- Medium Drop Probability (stredná pravdepodobnosť zahodenia) – spodná hranica nastavená na hodnotu 28
- High Drop Probability (vysoká pravdepodobnosť zahodenia) – spodná hranica nastavená na hodnotu 24
Horná hranica pravdepodobnosti zahodenia paketu je defaultne nastavená na hodnotu 40.
Obr. 6 AF triedy a DSCP hodnoty znázorňuje označenie AF tried a ich prislúchajúce desiatkové DSCP hodnoty.
Obr. 6 AF triedy a DSCP hodnoty