hledat:

QoS v Linuxu

Technická zpráva CESNETu číslo 20/2001
k dispozici též ve formátech PDF, PostScript a XML.

Vladimír Smotlacha
17.12.2001

1   Úvod

Dokument se zabývá implementací QoS (Quality of Services) v prostředí operačního systému Linux. Je popsána filosofie implementace, základní syntaxe a sémantika příkazů a několik typických příkladů včetně změřených hodnot. Cílem je posktytnout informace pro jednodušší případy praktického využití QoS, neboť dostupná dokumentace je dosti neúplná a tím je ztížena prvotní orientace v problému. Dokument se naopak nevěnuje problematice jak aplikovat QoS pro Diffserv, protože ta bude vzhledem ke své rozsáhlosti předmětem samostatného dokumentu.

2   Koncepce QoS v Linuxu

Základním principem implemantace jsou 3 kategorie objektů:

• typ fronty (queueing discipline)

  Queueing discipline (dále jen disciplína) je přiřazena výstupnímu rozhraní. Disciplína definuje způsob obsluhy a parametry příslušné fronty paketů určených k odeslání.

• třída (class)

  Třídy jsou sjednocení datových toků, které mají určité společné charakteristické rysy. Umožňují definovat společný způsob zpracování pro tyto toky v rámci nadřazené disciplíny. Některé typy disciplín (např. TBF - Token Bucket) třídy neobsahují. Protože třídy nedokáží manipulovat s pakety, samy obsahují vnořené disciplíny, např. frontu typu FIFO.

• filtr

  Filtry jsou svázány s třídami a disciplínami. Umožňují klasifikování paketů a jejich rozdělení do tříd a disciplín.

V současné verzi jsou implementovány následující typy disciplín:

• Token Bucket Flow (TBF)

  Jedná se o implementaci klasického algoritmu pro omezení velikosti datového toku, rozšířenou o možnost omezit nejen průměrný, ale i maximální tok. Ve skutečnosti tedy jde o dvojitý token bucket. Typické použití je pro traffic shaping.

• Class Based Queue (CBQ)

  Rozděluje dané přenosové pásmo mezi jednotlivé třídy. Pomocí atributu bounded je možné stanovit, že třída si nebude vypůjčovat momentálně nevyužité přenosové pásmo od jiných tříd a naopak isolated způsobí, že třída neposkytne své volné pásmo.

• First In First Out (FIFO)

  Standardní fronta, která je implementována ve dvou variantách: p-FIFO ukládá data do fronty po paketech (a omezení délky fronty se vztahuje na pakety), zatímco b-FIFO má délku fronty vyjádřenou v bytech.

• Stochastic Fair Queuening (SFQ)

  SFQ implementuje oddělění datových toků. Pomocí funkce hash podle IP hlavičky je paket zařazen do jedné z 256 front a ty jsou pak cyklicky obsluhovány tak, že z každé fronty je vybráno stejné množství dat.

• Traffic Equalizer (TEQL)

  TEQL je pseudo device sdružující dva nebo více reálných rozhraní. Datový tok je pak rovnoměrně rozdělen mezi jednotlivé fyzické linky.

• Random Early Detection (RED)

  RED je algoritmus pro zamezení zahlcení linky, který využívá vlastnost "slow start" TCP protokolu. Pokud celkový datový tok dosáhne stanovené hranice, je náhodně zahozen některý TCP paket a tím se donutí příslušný kanál ke snížení přenosové rychlosti.

• Diffserv Marker (DS_MARK)

  Tato disciplína je určena pro implementaci Diffservu. Pracuje s oktetem TOS z IP záhlaví paketu a umožňuje dynamicky měnit jeho hodnotu (= typ třídy podle výsledků značkování (marking).

• Clark-Shenker-Zhang algoritmus (CSZ)

  CSZ algoritmus dovoluje garantovat datovým tokům minimální přenosové pásmo i maximální zpoždění. Současná implementace algoritmu je komplikovaná a s velkou režijí. Ani její autoři ji nedoporučují používat.

• Asynchronous Transfer Mode (ATM)

  Pomocí této disciplíny je do modelu QoS integrována celá implementace ATM v Linuxu.

Disciplíny CBQ, CSZ, DS_MARK a p-FIFO podporují třídy. Pokud je paket zařazován do fronty v disciplíně s třídami, je pomocí filtru vybrána třída, do které paket patří. Každá třída musí obsahovat vnořenou disciplínu pro skutečnou manipulaci s frontou. Pokud není specifikováno jinak, jde o disciplínu typu FIFO.

Obecný vztah mezi disciplínami a třídami znázorňuje obrázek 1. Konkrétní struktura instancí disciplín, tříd a filtrů je hierarchicky uspořádána pomocí odkazů na nadřazený objekt.

Filtry provádějí klasifikaci paketů založenou na jejich specifických vlastnostech. Filtry, příslušející téže disciplíne nebo třídě, jsou podle své priority seřazeny do seznamu a sekvenčně aplikovány, dokud není podmínka některého filtru splněna.

Typy filtrů:

u32

Filtr u32 je univerzální a rozhoduje na základě vybraných položek v záhlaví paketů typu ICMP, IP, UDP nebo TCP.

TC_INDEX

Filtr TC_INDEX je určen pro Diffserv a testuje hodnotu TOS.

route

Filtr route využívá znalosti, která řádka routovací tabulky byla použita pro daný paket. Tím se může eliminovat opakované rozhodování na základě cílové adresy.

FW

Filtr FW využívá znalosti, jaké řádky z konfigurace firewallu (ipchains) byly aplikovány na daný paket.

3   Použití QoS v Linuxu

3.1   Instalace podpory QoS

Podpora QoS (pod názvem traffic control - TC) je součástí jádra od verze 2.2, pro verzi 2.0 byla dostupná jako patch jádra. Front-end část TC je obsažena v programovém balíku IPROUTE (nyní ve verzi 2.2.4), který nebývá součástí standardní instalace.

Při konfiguraci jádra je třeba zvolit položku QoS and/or fair queuing v sekci Networking options. Tím se dostaneme k výběru disciplín a filtrů, které mohou být začleněny do jádra nebo přeloženy jako moduly.

V rámci standardní metody konfigurace jádra není přístupný parametr, který určuje zdroj času pro scheduler. Parametr se jmenuje PSCHED_CLOCK_SOURCE a je definován v souboru include/net/pkt_sched.h. Má zásadní vliv na funkčnost scheduleru.

Existují tři možnosti:

PSCHED_GETTIMEOFDAY

Čas je získáván voláním funkce do_gettimeoday(). Toto varianta je velmi pomalá a autoři ji nedoporučují používat.

PSCHED_JIFFIES

Čas je odvozen od základního časovače jádra - parametr HZ. Protože pro platformu i386 je standardně HZ = 100, získáme časovou základnu s dosti špatnou granularitou 10 ms, což je hodnota nepoužitelná pro traffic shaping při rychlostech nad 1.5 Mb/s. Tato hodnota je přednastavena.

PSCHED_CPU

Čas je odvozen od čtení registru TSC, který je čítačem taktu procesoru. Registr TSC existuje na platformě Intel od doby Pentia, ale někdy není použitelný jako časovač, např. při zapnutém APM (advanced power management). Volba PSCHED_CPU je jednoznačně preferována, ale bohužel není přednastavena.

3.2   Příkaz tc

Příkaz tc zajišťuje založení, zrušení, modifikaci nebo výpis disciplín, tříd a filtrů.

disciplíny:

tc qdisc [ add | del | replace | change | get ] dev <string>
         [ handle <handle> ] [ root | parent <clasid> ]
         [ <DISC> ] [ help | <options> ]
  nebo

tc qdisc show [ dev <string> ]

  kde 
 DISC := { [p|b]fifo | tbf | prio | cbq | red | csz | dsmark ]

třídy:

tc class [ add | del | change | get ] dev <string>
         [ classid <classid> ] [ root | parent <clasid> ]
         [ <CLASS> ] [ help | <options> ]
  nebo

tc class show [ dev <string> ] [root | parent <classid> ]

  kde
 CLASS := { pfifo | prio | cbq | csz | dsmark } 

filtry:

tc filter[ add | del | change | get ] dev <string>
         [ prio <prio> ] [ protocol <proto> ]
         [ handle <filterid> ] [ root | classid <clasid> ]
         [ <FILT> ] [ help | <options> ]
  nebo

tc filter show [ dev <string> ] [root | parent <classid> ]

  kde

 FILT := { u32 | fw | route | tcindex | rsvp }  

Třídám a disciplínám je přiřazen pomocí atributu handle identifikátor ve tvaru M:N. Hierarchie mezi disciplínami, třídami a filtry je zajištěna atributem parent, jehož hodnotou je identifikátor nadřazeného objektu. Základní disciplína každěho rozhraní má atribut root. Pořadí vykonávání filtrů je určeno atributem prio a v případě splnění podmínky je paket předán disciplíně nebo třídě podle hodnoty atributu flowid (resp. synonymum classid)

Syntaktické detaily příkazu tc (např. volby pro jednotlivé typy disciplín) a zejména jejich přesná sémantika je dosti složitá a nepřehledná záležitost, která není dostatečně nikde dokumentována. Někdy je jedinou metodu získání informací prohlídka zdrojového kodu, kde se občas najde i nějaký vysvětlující komentář.

4   Příklady použití QoS

Dále popsané testy a měření jsme realizovali v testovací laboratoři Cesnetu. Testy byly provedeny na počítači DELL 1400 s PIII 866MHz. Byla použita distribuce RedHat 7.1 s kernelem 2.4.13, parametr PSCHED_CLOCK_SOURCE měl hodnotu PSCHED_CPU. Měření bylo provedeno programem RUDE/CRUDE a zpracováno programem QoSplot.

4.1   Token bucket

Názvem token bucket s parametry R (průměrná rychlost datového toku) a B (velikost bucketu, udávající maximální množství dat, které může přijít rychlostí vyšší než R) se označují buď značkovací algoritmus nebo metoda obsluhy fronty. Rozdíl je přitom podstatný: značkovací algoritmus neprovádí žádnou manipulaci s pakety, jen jim přiřadí atribut splňuje/nesplňuje kriteria token bucket (R,B). Naopak metoda obsluhy fronty token bucket upravuje datový tok tak, aby výstup splňoval parametry (R,B) a tedy přitom dochází ke zpožďování paketů a případně i k jejich ztrátám. Pro QoS v Linuxu, stejně jako v terminologii Cisco, má termín token bucket druhý význam - metoda tvarování datového toku (traffic shaping).

Provedli jsme testy s konfigurací R = 5 Mb/s, B = 10 kbyte, max. délka fronty 100 kbyte

tc qdisc add dev eth2 handle 1:0 root prio
tc qdisc add dev eth2 parent 1:1 tbf rate 5Mbit burst 10kB limit 100kB
tc filter add dev eth2 parent 1:0 protocol ip prio 1 u32 match ip \
   src 195.113.147.42  classid 1:1 

Vstupní datový tok (Obrázek 2) byl zvolen tak, aby byly ilustrovány všechny režimy činnosti token bucketu.

Následující obrázky dokumentují funkci token bucketu. Datový tok s rychlostí nepřevyšující R prochází bez zpoždění, definované množství dat (B) přicházející s vyšší rychlostí projde také bez omezení a další pakety se začnou ukládat do fronty. Pokud velikost fronty nestačí, pakety jsou zahozeny.

4.2   Priority queueing

Základní disciplínou je prioritní fronta. Testování jsme prováděli na síťovém rozhraní 10 Mb/s v zapojení podle následujícího obrázku:

Datové toky 4 Mb/s a 8 Mb/s se částečně časově překrývají a byly zvoleny tak, aby došlo k zahlcení výstupu a projevily se tedy různé priority. V grafech je datový tok z IP adresy 195.113.142.42 (8 Mb/s) vyznačen plnou čarou a tok z IP adresy 195.113.150.179 (4 Mb/s) je vyznačen čárkovaně.

Při konfiguraci

tc qdisc add dev eth2 handle 1:0 root prio
tc qdisc add dev eth2 parent 1:1  sfq quantum 1514b perturb 15
tc qdisc add dev eth2 parent 1:2  sfq quantum 1514b perturb 15
tc filter add dev eth2 parent 1:0 protocol ip prio 5 u32 match ip \
   src 195.113.147.42 flowid 1:1
tc filter add dev eth2 parent 1:0 protocol ip prio 3 u32 match ip \
   src 195.113.150.179 flowid 1:2

získáme následující výstupní datový tok:

a naopak pro

tc qdisc add dev eth2 handle 1:0 root prio
tc qdisc add dev eth2 parent 1:1  sfq quantum 1514b perturb 15
tc qdisc add dev eth2 parent 1:2  sfq quantum 1514b perturb 15
tc filter add dev eth2 parent 1:0 protocol ip prio 5 u32 match ip \
   src 195.113.147.42 flowid 1:2
tc filter add dev eth2 parent 1:0 protocol ip prio 3 u32 match ip \
   src 195.113.150.179 flowid 1:1

dostaneme

Je zřejmé, ze implementace prioritních front je funkční.Priorita je určena hodnotou N v identifikaci vnořené disciplíny M:N (čím nižší hodnota, tím vyšší priorita), nikoliv hodnotou parametru prio v definici filtru.

4.3   Fair queueing

Další testovanou disciplínou je fair queueing (SFQ), která identifikuje datové toky podle IP hlavičky a přiděluje jim stejné přenosové pásmo. Disciplína je implementována cyklickou obsluhou front (round robin) pro jednotlivé datové toky. Při stejném vstupu jako v předchozím případě jsme očekávali, že každému ze dvou toků bude přidělena nejvíce polovina pásma, tedy datový tok 4 Mb/s nebude ovlivněn, zatímco tok 8 Mb/s bude oříznut na přibližně 5 Mb/s.

Při testech jsme zkoušeli několik konfigurací a marně jsme hledali takovou, která by měla očekávaný efekt. Vždy jsme však získali výsledky stejné jako na dále uvedených grafech. Základní použitá konfigurace je:

tc qdisc add dev eth2 handle 1:0 root sfq quantum 1514b perturb 15

Naměřené výsledky svědčí o tom, že došlo k omezení obou datových toků. Pravděpodobně byly všechny pakety zařazeny do jedné fronty - buď nebyla disciplína schopna datové toky rozlišit, nebo se v implementaci vyskytuje další fronta předřazená před disciplínou SFQ.

Použitá literatura

[Rad99]	Saravanan Radhakrishnan: Linux - Advanced Networking Owerview, Version 1 , The University of Kansas, 1999.
[Lin01]	Linux 2.4 Advanced Routing HOWTO, September 2001