Semestrální projekt do TPS

QoS: mechanismy front

Úvod Teoretický základ Praktické návody Statistiky

Teoretický základ

Kvalita služby

Obecně se kvalita služby (Quality of Service, často zkracováno na "QoS") uplatňuje v přenosech multimediálních dat, v IP telefonii, ale čím dál tím častěji se s tímto pojmem setkáváme i na poli běžných TCP/IP sítí. Kvalitu služeb bychom mohli definovat následovně:

Jedná se o komplexní opatření, snažící se zaručit koncovému uživateli doručení dat v potřebné kvalitě. Kvalita služby může být definována pomocí několika kritérií: dostupnost (minimalizace času výpadku spojení), chybovost, latence, propustnost, ztrátovost paketů, doba vytvoření spojení, rychlost, detekce a oprava chyb. .

Kvalita služby je ovlivněna všemi komponentami sítě:

stanicemi (WS, servery)
směrovači, přepínači
linkami (mezi routery, LAN)

Parametry tvořící QoS

šířka pásma (bandwidth)
znamená rychlost přenosu dat (za nějakou časovou jednotku), kritická je především u multimediálních aplikací, ale někdy třeba i u nejběžnějšího přenosu WWW stránek - zde záleží především na hlavním účelu použití dané přenosové trasy a příslušných prioritách uživatelů.
Jednosměrné zpoždění (one-way delay)
je čas potřebný k odeslání paketů a jeho přijetí v cíli [RFC2330]. Skládá se z dvou častí:
- času potřebného na přenesení paketu přes fyzické médium, což je funkce přenosové rychlosti linky a
- času, který představuje zpoždění způsobené řazením do front, zpracováním v síťových zařízeních a přetížením linek .
rozptyl zpoždění (jitter)
je definované pro dva pakety jako rozdíl mezi jednosměrným zpožděním jednoho paketu a jednosměrným zpožděním druhého paketu [RFC3393].
ztrátovost paketů (packet loss)
je poměr poslaných paketů, které nebyly přijaty v cíli nebo byly přijaty s chybou [RFC2680].

Komponenty zpoždění a jejich příčiny

pevná složka: serializační zpoždění, doba šíření
proměnná složka: buffering (fronty) ve směrovačích a přepínačích

Příčiny rozptylu zpoždění

nejednotné zacházení s jednotlivými pakety téhož toku při bufferingu, z toho plynoucí proměnné pozdržení ve frontách

Příčiny ztrát paketů

(fyzické chyby - discard)
přetížení procesoru přepínacích prvků (input drops)
přeplnění výstupních front přepínacích prvků (output drops)

Disciplíny front (Queueing Discipline = qdisc)

Classless qdisc

Classless qdisc (dalo by se přeložit jako Beztřídové disciplíny front, nicméně přidržíme se zde odborného názvu v angličtině) dokáže pakety ve výstupní frontě "přeházet", zdržet či zahodit. Tento způsob řízení provozu - o různých způsobech řízení provozu mluvíme v angličtině jako o disciplines - tedy tyto disciplines mohou být použity pro celkové nastavení přenosového pásma, bez možnosti aplikace složitých pravidel pro detekci, zajišťující komplexní priorizaci vybraných paketů. Tento přístup je standardně použit ve většině operačních systémů a je založen na typu výstupní fronty, označované jako pfifo_fast qdisc.

pfifo_fast

Fronta pfifo_fast qdisc se skládá ze tří pásem, či kanálů (band), které mají interní označení 0, 1 a 2. Každý paket, který dorazí do výstupní fronty je zařazen do jednoho ze tří kanálů. Jediný příznak, který je zde brán v úvahu a který o zařazení rozhoduje je tzv. Type Of Service (často známější ve formě zkratky ToS). Informace, které může nést záhlaví ToS v IP datagramu ukazuje obrázek.

Obrázek 1: Význam bitů v poli ToS hlavičky IP datagramu
Následující tabulka z RFC 1349 znázorňuje jak některé aplikace nastavují ToS bity. Z této tabulky můžeme získat představu o tom co jednotlivé typy služeb znamenají a jak je aplikace využívají.

TELNET		1000	(minimize delay)
FTP
	Control	1000	(minimize delay)
	Data	0100	(maximize throughput)
TFTP
	Command phase	1000	(minimize delay)
	DATA phase	0100	(maximize throughput)
DNS
	UDP Query	1000	(minimize delay)
	TCP Query	0000
	Zone Transfer	0100	(maximize throughput)
ICMP
	Errors	0000
	Requests	0000 (mostly)
	Responses	0000 (mostly)

V zásadě můžeme říci, že pakety s nevyšší prioritou jsou vždy zařazeny do kanálu 0, pakety s nižší prioritou do kanálu 1 a pakety nejnižší prioritou do kanálu 2. Algoritmus FIFO je potom aplikován na každý kanál zvlášť s tím, že dokud jsou nějaké neodeslané pakety v kanálu 0, neodesílají se pakety z kanálu 1 a 2 a analogicky to platí pro kanál 1, který dostane přednost před kanálem 2.

Token Bucket Filter (TBF)

Nejznámějším algoritmem, který používá pro svou práci principy pfifo_fast discipline je TBF (Token Bucket Filter). Tento algoritmus má své použití v případě, že chceme pouze omezit celkovou šířku přenosového pásma na daném síťovém rozhraní - lapidárně řečeno, TBF umožňuje zpomalit datový tok dle přání uživatele. Vzhledem k designu, pfifo_fast není použitelný pro selektivní prioritizaci dle cílového TCP portu či IP adresy a podobně.

Stochastic Fairness Queueing (SFQ)

Stochastic Fairness Queueing je jednoduchá implementace z rodiny fair queueing algoritmů. Klíčovým slovem v SFQ je komunikace které odpovídá TCP session nebo UDP streamu. Provoz je rozdělován do poměrně velkého počtu FIFO front, zjednodušeně řečeno pro každou komunikaci existuje jedna fronta. Pakety jsou rovnoměrně odebírány z každé fronty a předávány nižším vrstvám, tím pádem každý přenos má rovnocennou šanci na přístup k přenosovému pásmu a není možné, aby existovalo jedno spojení, které znemožní přístup ostatním. SFQ má již v názvu slovo "stochastický", protože ve skutečnosti nevytváří jednu frontu pro každý jednotlivý datový tok, to by bylo příliš paměťově náročné, místo toho je zde implementován algoritmus, který rozděluje provoz do určeného, omezeného (byť relativně velkého) počtu front.

Classful qdisc

Princip tohoto omezování spočívá v rozřazení provozu, který přichází do výstupní fronty, do jednotlivých tříd(class). Mluvíme o klasifikaci provozu. Klasifikace se děje na základě filtrů, které jsou definovány uživatelem. Zde je tedy, narozdíl od metody classless qdisc, prostor pro konfiguraci řízení síťového provozu - právě pomocí classfull qdisc je tedy možné dosáhnout definice kvality služby. Na základě rozhodnutí filtrů jsou pakety rozřazeny do tříd. Každá třída můžeme mít dále vlastní filtry, které pakety rozřadí do podtříd. Pokud třída neobsahuje podtřídy, obsahuje vlastní frontu paketů. Navíc ještě může každá třída obsahovat vlastní metodu qdics, a to jak classfull, tak classless. Takto mohou vzniknout i velmi složité stromové struktury hierarchie tříd.

Každý interface má jednu výstupní "root qdisc", implicitně je nastavená výše zmiňovaná pfifo_fast qdisc. Ke každé qdisc může být přiřazen handel, který může být použit v pozdějších konfiguračních příkazech týkajících se této qdisc. Handel těchto qdiscs obsahuje dvě části, majoritní číslo a minoritní číslo.Obvykle je kořenová třída pojmenována "1:" , to je rovno "1:0". Minoritní číslo qdisc je většinou 0. Třídy potřebují mít stejné majoritní číslo jako jejich rodiče.

Typickou hierarchickou strukturu můžeme vidět na následujícím obrázku:

                    root 1:
                      |
                    _1:1_
                   /  |  \
                  /   |   \
                 /    |    \
               10:   11:   12:
              /   \       /   \
           10:1  10:2   12:1  12:2

Paketu může byt přiřazena například tato klasifikace:

1: -> 1:1 -> 12: -> 12:2

Nyní je paket zařazený do fronty, která je připojena k třídě 12:2. V tomto příkladě byl filtr připojen ke každému "uzlu" ve stromu, každý filtr vybírá, která větev bude jako následující. Je možná i klasifikace jako je tato:

1: -> 12:2

V tomto případě filtr připojeny k root rozhodl že paket bude zařazen přímo do fronty připojené k třídě 12:2.

Jakmile jádro rozhodne, že je potřeba vyjmout paket a odeslat ho na interface, root qdisc 1: obdrží dequeue request , který projde do 1:1, dále je v cyklu poslán do 10:, 11: a 12:, každý z těchto "sourozenců" obdrží dotaz a zkusí dequeue() . V tomto případě musí jádro procházet celý strom, protože pouze 12:2 obsahuje paket.
Vnořená třída komunikuje vždy jen se svou rodičovskou qdisc, nikdy s interfacem. Pouze root dostane požadavek na vyjmutí z fronty od jádra.

Priority Queueing (PRIO)

PRIO qdisc ve skutečnosti netvaruje, pouze rozděluje provoz podle toho, jak jsou nakonfigurovány filtry. Můžeme PRIO qdisc přirovnat k pfifo_fast, kde je každý kanál samostatnou třídou, namísto jednoduché FIFO. Když je paket zařazen do fronty s PRIO qdisc, třída již není vybírána pouze na základě zadaných ToS bitů, jako tomu bylo u classless qdisc, ale využívá plné síly, kterou nám poskytuje použití filtrů. Implicitně jsou vytvořeny tři třídy. Tyto třídy implicitně obsahují prosté FIFO qdisc bez vnitřní struktury, toto nastavení lze změnit na jakoukoli dostupnou disciplínu. Jak je vidět z obrázku, fronty s vyšší prioritou mají absolutní přednost, z toho plyne, že pokud existuje paket ve frontě s vyšší prioritou, nebude odeslán žádný paket z fronty s nižší prioritou.

Class-Based Queuing (CBQ)

CBQ je algoritmus, který umí klasifikovat provoz do tříd, a který navíc umí omezit šířku přenosového pásma. Bohužel právě na tomto poli nedosahuje zcela přesných výsledků. Základní myšlenka algoritmu vypadá takto: Pokud se snažíme omezit linku 10 Mb/s na přenosovou kapacitu 1 Mb/s, pak by linka měla být "prázdná" po 90% času. Pokud není, musíme frontováním paketů zajistit, aby byla 90% času prázdná. Problém je v tom, že je poměrně těžké měřit toto procento času, po které je linka prázdná, a tak CBQ tuto hodnotu raději odvozuje od počtu mikrosekund, které uběhnou mezi jednotlivými požadavky z hardwarové vrstvy na předání dalších paketů. Tím algoritmus určí, jak plná či prázdná je právě linka. Je zřejmé, že takový postup je poněkud podezřelý a skutečně ne vždy dává přesné výsledky. Celkově však lze říci, že ve většině případů CBQ pracuje s dobře použitelnou přesností a to je asi hlavní důvod, proč se postupem času stal hlavním algoritmem implementovaným do moderních operačních systémů - ať už se jedná o Linux či Windows XP.

Z obrázku je vidět, na jakém principu CBQ pracuje. Fronty jsou obsluhovány cyklicky, při každém průchodu je fronta buď vyprázdněna, nebo je z ní odebráno definované množství dat.

Hierarchical Token Bucket (HTB)

Máme strom tříd, každá třída má rate ("rychlost" nebo šířka pásma) a prioritu. Pakety jsou rozděleny do toků a přiřazeny do listů stromu, pokud jsou prazdné. Předpokládáme že strom je kompletní, každý uzel má stejnou hloubku. Cílem je rozdělit pakety tak, aby každá třída je uspokojena. Můžeme použít abstrakci a algoritmus popsat takto:
Nejprve vybereme ty listy jejichž rate nebyl dosažen. Odtud pošleme pakety s vysokou prioritou a postupně pokračujeme do listu s nižší prioritou. Pokud je překonaný rate na všech listech, celý cyklus zopakujeme, ale pro každý list testujeme zda-li si může půjčit od rodičů na místo testu vlastního rate. Pokud taková třída není celý cyklus opakujeme, ale na místo rodičů testujeme prarodiče. A tak dále ...
Poznámka: Pokud má třída A vyšší prioritu než B a oba si půjčují z C, potom A dostane to co potřebuje a zbytek slouží třídě B.
Má-li B stejnou prioritu jako A půjčená šířka pásma z C je rozdělena mezi A a B ve stejném poměru jako je jejich základní rate.

HTB používá zde popsanou abstrakci, ale ve skutečnosti provádí cyklus vícekrát. To je pomalejší ale více precizní. Pro snadnější implementaci se používá TBF . Je zaveden pojem "ceil rate" (může být zadán v každé třídě). Třída vždy používá bandwidth mezi základní a "ceil rate" hodnotou, snáze se tak implementuje odepření půjčení.