Linux Traffic Control v 0.9

Obsah

1. Úvod
2. Implementace QoS
3. Fronty
4. Třídy
5. Filtery
6. Příkaz tc
7. Příklad
8. Použité zdroje

1. Úvod

   Nové verse Linuxového jádra nám přinášejí spoustu nových krásných možností. Oblastí, která zaznamenala velmi bouřlivý vývoj, je networking. Poměrně málo zdokumentovanou částí jsou věci okolo traffic control, příkazu tc a QoS (Quality of Service).
   
   

2. Implementace QoS

   Základní princip implementace QoS na Linuxu nám ukazuje následující obázek. Packet přijde do kernelu, je validován a vystaven přísné kontrole vstupního firewallu. Je-li určen pro lokální stroj, je předán vyšším vrstvám. V opačném případě se vybere výstupní zářízení (forwarding). Pak se uloží do výstupní fronty daného zařízení (interface). Právě v tomto okamžiku se dostává do hry traffic control.

   Z implementčního hlediska to znamená zhruba toto. Po vytvoření fronty (queuing discipline) je ukazatel ve struktuře zařízení (interface) (include/netdevice.h). IP vrstva po přídání nezbytných hlaviček zavolá funkci dev_queue_xmit z net/core/dev.c. Příslušná Část kódu vypadá zhruba takhle:

   
   	/* Grab device queue */
   	spin_lock_bh(&dev->queue_lock);
   	q = dev->qdisc;
   	if (q->enqueue) {
   		int ret = q->enqueue(skb, q);  
   
   		qdisc_run(dev);  
   
   		spin_unlock_bh(&dev->queue_lock);
   		return ret == NET_XMIT_BYPASS ? NET_XMIT_SUCCESS : ret;
   	}                                                                       
   
   	.
   	.
   	.
   	.
   
   				if (dev->hard_start_xmit(skb, dev) == 0) {                     
   
   

   Tahle funkce dokazuje, že dříve než je packet poslán na výstupní interface je uložen do fronty. Linuxová podpora pro QoS se skládá z následujících věcí:
   • Fronty (Queuing discipline)
   • Třídy (Classes)
   • Filtery (Filters/Policers)
   Podívejme se na ně detailněji.
   
   

3. Fronty

   Linux podporuje například následující fronty:
   • Class Based Queue (CBQ) - rozřazení do více front, může na sebe věšet dalši fronty
   • Token Bucket Flow (TBF) - máme děravý kýbl a do něj natýká voda (data) voda odteká konstatne rychle, takže se v kýbli buď hromdí nebo odtéka. Shaper.
   • Clark-Shenken-Zhang (CSZ)
   • First In First Out (FIFO) - obzčejná fronta
   • Priority (p-FIFO) - přidány priority
   • Traffic Equalizer (TEQL) - balancování na více interfacech
   • Stochastic Fair Queing (SFQ) - packety jsou rozděleny do toků a pak slévány round robin.
   • Asynchronous Transfer Mode (ATM)
   • Random Early Detection (RED) - dříve než by se melo pásmo zaplnit, začnou se náhodně se zvětšující se pravděpodobností zahazovat packety. Zabrání se tak oscilaci, tcp si lépe na přeplnění zvyká.
   • Generalized RED (GRED) - lze určit, jaké toky se zahazují pravděpodobněji.
   • Diff-Serv Marker (DS_MARK)

   Fronty jsou identifikovány dvojící <major number:minor number>, kde minor number je 0. Tento identifikátor se používá pro propojení tříd s frontami. Fronty musí implementovat následující metody:

   • Enqueue - Tato funkce zařadí packet do fronty.
   • Denqueue - Tato funkce vyřadí packet z fronty. Který to bude určuje scheduler fronty, což může být poměrně netriviální proces. Jako příklad tedy raději uvedu část z FIFO.

     static struct sk_buff *
     pfifo_dequeue(struct Qdisc* sch)
     {
             return __skb_dequeue(&sch->q);
     }                                                                              
     

   • Requeue - Občas se stane, že po vyřazení packetu z fronty (dequeue), je nutné jej vrátit zpět. V takovém případě se packet vrací zpět na posici, ze které byl odebrán. Obvykle se taková situace nastane pokud nejak selže fyzické odeslání packetu.
   • Drop - Smysl této funkce je patrně každému jasný už z jejího názvu. Zahození packetu se provádí různým způsobem. Třeba takhle to řeší GRED:

     gred_drop(struct Qdisc* sch)
     {                                                                               
     .
     .
     .
     
     	skb = __skb_dequeue_tail(&sch->q);
     	if (skb) {
     		sch->stats.backlog -= skb->len;
     		sch->stats.drops++;
     		q= t->tab[(skb->tc_index&0xf)];
     		if (q) {
     			q->backlog -= skb->len;
     			q->other++;
     			if (!q->backlog && !t->eqp)
     				PSCHED_GET_TIME(q->qidlestart);
     			} else {
     				D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
     			}
     
     		kfree_skb(skb);
     		return 1;
     	}
     
     .
     .
     .
     

     Jak je vidět, funkce pouze zavolá dequeue a pak uvolní po packetu pamět.
   • Init - Funkce inicialisuje konfiguruje parametry fronty v okamžiku jejího vytváření.
   • Reset - Resetuje frontu do jejího počátečního stavu. Například takhle jednodušše vypadá prio:

     static void
     prio_reset(struct Qdisc* sch)
     {
             int prio;
     	struct prio_sched_data *q = (struct prio_sched_data *)sch->data;
     
     	for (prio=0; priobands; prio++)
     		qdisc_reset(q->queues[prio]);
     	sch->q.qlen = 0;
     }
     

   • Destroy - I zde je název myslím dostatečně výmluvný. Tato funkce úplně odstraní frontu a s ní i související třídy a filtery.
   
   
   

4. Třídy

   Jak už jsem říkal, fronty a třídy jsou úzce spojeny. Každá třída vlastní frontu. Implicitně to je FIFO. Je-li zavolána funkce enqueue fronty, filtery uržčí, do jaké třídy packet patří. Pak je zavolána funkce fronty vlastněné touto třídou.

   Jsou dva způsoby, jak je třída identifikována. Jeden identifikátor zadává uživatel, druhý je interní. Ne všechny fronty podporují třídy. S podporou jsou například CBQ, DS_MARK, CSZ, p-FIFO.

   Třídy mají tyto funkce:

   • Graft - Tato funkce přípojí novou frontu ke třídě. Takto to vypadá pro prio:

     static int prio_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
     	struct Qdisc **old)
     {
     	struct prio_sched_data *q = (struct prio_sched_data *)sch->data;
     	unsigned long band = arg - 1;
     
     	if (band >= q->bands)
     		return -EINVAL;
     
     	if (new == NULL)
     		new = &noop_qdisc;
     
     	sch_tree_lock(sch);
     	*old = q->queues[band];
     	q->queues[band] = new;
     	qdisc_reset(*old);
     	sch_tree_unlock(sch);
     
     	return 0;
     }                                                                               
     										

     Funkce má jako parametr novou frontu.
   • Get - Tato funkce vrací interní ID třídy. Tato funkce zvyšuje čítač použití třídy.

     
     static __inline__ struct cbq_class *
     cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
     {
     	struct cbq_class *cl;
     
     	for (cl = q->classes[cbq_hash(classid)]; cl; cl = cl->next)
     	if (cl->classid == classid)
     		return cl;
     	return NULL;
     }
     
     static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
     {
     	struct cbq_sched_data *q = (struct cbq_sched_data *)sch->data;
     	struct cbq_class *cl = cbq_class_lookup(q, classid);
     
     	if (cl) {
     		cl->refcnt++;
     		return (unsigned long)cl;
     	}
     	return 0;
     }
     

   • Put - Tato funkce se volá při dereferencování třídy. Je-li čítač na 0, je možné třídu odstranit.

     
     cbq_put(struct Qdisc *sch, unsigned long arg)
     {
     	struct cbq_class *cl = (struct cbq_class*)arg;
     	 
     	if (--cl->refcnt == 0) {
     #ifdef CONFIG_NET_CLS_POLICE
     		struct cbq_sched_data *q = (struct cbq_sched_data *)sch->data;
     	
     		spin_lock_bh(&sch->dev->queue_lock);
     		if (q->rx_class == cl)
     			q->rx_class = NULL;
     		spin_unlock_bh(&sch->dev->queue_lock);
     #endif
     
     		cbq_destroy_class(cl);
     	}
     }
     
     

   • Change - Používá se pro změnu parametrů asociovných se třídou. Nicméně používá se také k vztvoření třídy.
   • Delete - Smaže třídu. Podivá se na refernční čítač a je-li nulový vymaže třídu.
   • Walk - Touto funkcí se iteruje přes všechny třídy fronty.

     static void csz_walk(struct Qdisc *sch, struct qdisc_walker *arg)
     {
     	struct csz_sched_data *q = (struct csz_sched_data *)sch->data;
     	int prio = 0;
      
     	if (arg->stop)
     		return;
     
     	for (prio = 0; prio < CSZ_FLOWS; prio++) {
     		if (arg->count < arg->skip) {
     			arg->count++;
     			continue;
     		}
     		if (prio < CSZ_GUARANTEED && q->flow[prio].L_tab == NULL) {
     			arg->count++;
     			continue;
     		}
     		if (arg->fn(sch, prio+1, arg) < 0) {
     			arg->stop = 1;
     			break;
     		}
     		arg->count++;
     	}
     }
     

   • Tcf_chain - Vrací ukazatel na senznam filterů asociovaných se třídou.
   • Binf_tcf - Připojí instanci filteru ke třídě.
   • Unbinf_tcf - Zde je myslím veškerý komentář zbytečný. :-)
   • Dump_class - Používá se k diagnostickým účelům.
   
   
   

5. Filtery

   Filtery dokáží klasifikovat packte podle nejrůznejších kriterií, jako je TOS v IP hlavičce, IP adresa, port ... Jsou volany, když je vyvolánana funkce enqueue fronty. Fronty používají filtery pro přiřazení packetů do tříd. Seznam filterů je specifikován strukturou tcf_proto.

   struct tcf_proto
   {
   	/* Fast access part */
   	struct tcf_proto        *next;
   	void                    *root;
   	int                     (*classify)(struct sk_buff*, struct tcf_proto*,
   	struct tcf_result *);
   	u32                     protocol;
   
   	/* All the rest */
   	u32                     prio;
   	u32                     classid;
   	struct Qdisc            *q;
   	void                    *data;
   	struct tcf_proto_ops    *ops;
   

   Elementy filteru jsou identifikovány 32-bitovým identifikátorem. Id. 0 je sám filter. Stejně jako třídy, i filtery mají interní ID, které lze získat pomocí funkce get. Strukturu filteru ukazuje následující obrázek. Filter má tyto funkce
   • Classify - Používá se ke klasifikování packetu. Funkce vrací čtyři možné hodnoty:
     • TC_POLICE_UNSPEC
     • TC_POLICE_OK
     • TC_POLICE_RECLASIFY
     • TC_POLICE_SHOT
   • Init - Inicialisování parametrů filteru.
   • Destroy - Vymazání filteru. Volá unbind_tcf.
   • Get - Jak už jsem říkal, vrátí interní ID a zvýší čítač referencí.
   • Put - Opak Get, sníží čítač. Nepoužívá se.
   • Change - Slouží ke změně parametrů filteru. Obvykle volá unbind_tcf a pak bind_tcf.
   • Delete - Vymaže element z filteru.
   • Walk - Prochází všechny elementy filteru.
   • Dump - Slouží k diagnostikování.

   Filtery se mohou rozdělit na generické a specifické. U generických je pouze jedna instance na frontu, u specifických jich může být více.
   
   

6. Příkaz tc

   Netlink socket je interface mezi kernelem a user space. Pro jeho ovládání nám pan Kuznetsov naprogramoval řádkový interface tc. Dokáže přídávat či ubírat fronty, filtery a pod.
   
   
   
   1. Základní parametry jsou následující.

      Usage: tc [ OPTIONS ] OBJECT { COMMAND | help }
      where  OBJECT := { qdisc | class | filter }
             OPTIONS := { -s[tatistics] | -d[etails] | -r[aw] }
      

      
      
      
   2. Syntaxe pro vytváření fronty je pak takováhle:

      Usage: tc qdisc [ add | del | replace | change | get ] dev STRING
             [ handle QHANDLE ] [ root | ingress | parent CLASSID ]
             [ estimator INTERVAL TIME_CONSTANT ]
             [ [ QDISC_KIND ] [ help | OPTIONS ] ]
      
             tc qdisc show [ dev STRING ] [ingress]
      Where: QDISC_KIND := { [p|b]fifo | tbf | prio | cbq | red | etc. }
      OPTIONS := ... try tc qdisc add  help                       
      

      • Handle - je jednoznačný identifikátor, který uživatel přiřadil frontě.
      • Root - znamená, že fronta je nejvyšší v hierarchii.
      • Parent - nadřazená fronta
      
      
      
   3. Syntaxe pro třídy je takováhle:

      Usage: tc class [ add | del | change | get ] dev STRING
             [ classid CLASSID ] [ root | parent CLASSID ]
             [ [ QDISC_KIND ] [ help | OPTIONS ] ]
      	       
             tc class show [ dev STRING ] [ root | parent CLASSID ]
      Where:
      QDISC_KIND := { prio | cbq | etc. }
      OPTIONS := ... try tc class add  help
      

      QDISC_KIND je nějaká fronta podporující třídy.
      • Classid je ID, které uživatel přiřadil dané třídě.
      • Root - znamená, že třída je nejvyšší v hierarchii.
      • Parent - nadřazená fronta
      
      
      
   4. No a nakonec syntaxe pro filtery:

      Usage: tc filter [ add | del | change | get ] dev STRING
             [ pref PRIO ] [ protocol PROTO ]
             [ estimator INTERVAL TIME_CONSTANT ]
             [ root | classid CLASSID ] [ handle FILTERID ]
             [ [ FILTER_TYPE ] [ help | OPTIONS ] ]
           
             tc filter show [ dev STRING ] [ root | parent CLASSID ]
      Where:
      FILTER_TYPE := { rsvp | u32 | fw | route | etc. }
      FILTERID := ... format depends on classifier, see there
      OPTIONS := ... try tc filter add  help
      

      • Prio - priorita filteru.
      • Protocol - identifikuje, že filter patří pouze tomuto protokolu.
      • Root - filter je nejvýše v hierachii.
      • Classid - ID třídy, na kterou se filter aplikuje.
      • Handle - Identifikace filteru.
      
      
      
   5. Class Based Queue Syntaxe tc pro vytvoření CBQ je následující:

      tc qdisc [ add | del | replace | change | get ] dev STRING\
      cbq bandwidth BPS [ avpkt BYTES] [ mpu BYTES ] [ cell BYTES ] [ ewma LOG ]
      

      Význam jednotlivých položek je následující:
      • Bandwidth - Maximální propustnost interfacu, ke kterému je fronta připojena.
      • Avpkt - průměrná velikost packetu.
      • Mpu - nejmenší počet bytů, ktere lze vyslat packetem. Obvykle je to 64,
      • Cell - vymezuje hrance bztů v packetu.
      Syntaxe pro vytvoření třídy je takováhle:

      tc qdisc [ add | del | replace | change ] cbq bandwidth BPS rate BPS maxburst PKTS \
      [ avpkt BYTES ] [ minburst PKTS ] [ bounded ] [ isolated ] [ allot BYTES ] \
      [ mpu BYTES ] [ weight RATE ] [ prio NUMBER ] [ cell BYTES ] [ ewma LOG ] \
      [ estimator INTERVAL TINE_CONSTANT ] [ split CLASSID ] [ defmap MASK/CHANGE ]
      

      Kde políčka zanmenají následující:
      • Bandwidth - maximálni šířka pásma pro frontu
      • Rate - šířka pásma pro třídu
      • Maxburst - počet bytů vyslaných při největším burstu
      • Avpkt - průměrný počet packetů pro tuto třídu
      • Minburst - počet bytů vyslaných při nejmenším burstu
      • Bounded - Třída nemůže si půjčovat pásmo od předků.
      • Isolated - Třída nemůže si používat pásmo jiných tříd.
      • Split - používá se pro rychlý přístup. Toto je normálně kořen CBQ stromu.
      • Prio - priorita třídy
      
      
      
   6. Route Classifier Klasifikuje packety na základě routovací tabulky. Syntaxe pro vytvoření je následující:

      tc filter [ add | del | change | get ] dev STRING
      [ parent PARENTID ] [ protocol PROTO ]
      [ PRIORITY ] route
      
      Whete:
      PROTO = { ip | icmp | etc. }
      

      
      
      
   7. U32 Classifiers Jsou mnohem obecnější dokážou klasifikovat packet poled jeho libovoného bytu.
      
      

   8. Příklad

      Představme si situaci jako na obrázku. Chceme rozdělit pásmo z routeru A na stanice B a C. Aplikace O běžící na na stanici B a na portu 1111 má dostat 3Mbps pásma, P potřebuje 1Mbps.

      # Pripojeni fronty na eth0. Sirka pasma je 10Mbps
      tc qdisc add dev eth0 root handle 1: cbq bandwidth 10Mbit allot 1514 cell 8 avpkt 1000 mpu 64
      
      # Pridame tridu fronty. Koren ma plnych 10Mbps
      tc class add dev eth0 parent 1:0 classid 1:1 cbq bandwidth 10Mbit rate 10Mbit allot 1514 cell 8 weight 1Mbit prio 8 maxburst 20 avpkt 1000
      
      # Tok na B
      tc class add dev eth0 parent 1:1 classid 1:2 cbq bandwidth 10Mbit rate 4Mbit allot 1514 cell 8 weight 400Kbit prio 4 maxburst 20 avpkt 1000 bounded
      
      # Tok na C
      tc cladd add dev eth0 dev parent 1:1 classid 1:3 cbq  bandwidth 10Mbit rate 6Mbit allot 1514 cell 8 weight 600Kbit prio 4 maxburst 20 avpkt 1000 bounded
      
      # Pripojeni dalsiho CBQ na toky na B
      tc qdisc add dev eth0 parent 1:2 handle 2: cbq bandwidth 4Mbit alot 1514 cell 8 avpkt 1000 mpu 64
      
      # Pripojeni dalsiho CBQ na toky na C
      tc qdisc add dev eth0 parent 1:3 handle 3: cbq bandwidth 6Mbit alot 1514 cell 8 avpkt 1000 mpu 64
      
      # Nastaveni trid pro aplikace na B
      tc class add dev eth0 parent 2:0 classid 2:1 cbq bandwidth 4Mbit rate 4Mbit allot 1514 cell 8 weight 400Kbit prio 4 maxburst 20 avpkt 1000 bounded
      tc class add dev eth0 parent 2:1 classid 2:2 cbq bandwidth 4Mbit rate 3Mbit allot 1514 cell 8 weight 300Kbit prio 1 maxburst 20 avpkt 1000 bounded
      tc class add dev eth0 parent 2:1 classid 2:3 cbq bandwidth 4Mbit rate 1Mbit allot 1514 cell 8 weight 100Kbit prio 2 maxburst 20 avpkt 1000 bounded
      
      # Nastaveni trid pro aplikace na C
      tc class add dev eth0 parent 3:0 classid 3:1 cbq bandwidth 6Mbit rate 6Mbit allot 1514 cell 8 weight 600Kbit prio 7 maxburst 20 avpkt 1000 bounded
      tc class add dev eth0 parent 3:1 classid 3:2 cbq bandwidth 6Mbit rate 4Mbit allot 1514 cell 8 weight 400Kbit prio 1 maxburst 20 avpkt 1000 bounded
      tc class add dev eth0 parent 3:1 classid 3:3 cbq bandwidth 6Mbit rate 2Mbit allot 1514 cell 8 weight 200Kbit prio 2 maxburst 20 avpkt 1000 bounded
      
      # Instalace router classifier na eth0
      tc filter add dev eth0 parent 1:0 protocol ip prio 100 route
      
      # Nastavuji routy pro B a C a pravidla pro jejich toky
      ip route 192.168.1.11 via 192.168.1.1 flow 1:2
      ip route 192.168.1.21 via 192.168.1.1 flow 1:3
      
      # Instaluji u32 classifier pro B
      tc filter add dev eth0 parent 2:0 prio 4 protocol ip u32
      
      # Vytvareni hash tabulky classifeiru pro packety na B
      tc filter add dev eth0 parent 2:0 prio 4 handle 1: u32 divisor 256
      tc filter add dev eth0 parent 2:0 prio 4 handle 2: u32 divisor 256
      
      # Konfigiruji 6. slot tabulky, aby vybral packet urceny pro port 1111 (0x0457) a posla je do tridy 2:2
      tc filter add dev eth0 parent 2:0 prio 4 u32 ht 1:6: match ip dst 192.168.1.11 match tcp dst 0x0457 0xffff flowid 2:2
      
      # Ted to same pro port 1112
      tc filter add dev eth0 parent 2:0 prio 4 u32 ht 2:6: match ip dst 192.168.1.11 match tcp dst 0x0458 0xffff flowid 2:3
      
      # Projdi hash table a pokud neni fragmentovana, pouzij protokol jako hashovaci klic.
      tc filter add dev eth0 parent 2:0 prio 4 handle ::1 u32 ht 800:: match ip nofrag offset mask 0x0f00 shift 6 hashkey mask 0x00ff0000 at 8 link 1:
      tc filter add dev eth0 parent 2:0 prio 4 handle ::1 u32 ht 800:: match ip nofrag offset mask 0x0f00 shift 6 hashkey mask 0x00ff0000 at 8 link 2:
      
      # Instaluji u32 classifier pro B
      tc filter add dev eth0 parent 3:0 prio 7 protocol ip u32
      
      # Vytvareni hash tabulky classifeiru pro packety na B
      tc filter add dev eth0 parent 3:0 prio 7 handle 1: u32 divisor 256
      tc filter add dev eth0 parent 3:0 prio 7 handle 2: u32 divisor 256
      
      # Konfigiruji 6. slot tabulky, aby vybral packet urceny pro port 1113 (0x0459) a posla je do tridy 2:2
      tc filter add dev eth0 parent 3:0 prio 7 u32 ht 1:6: match ip dst 192.168.1.21 match tcp dst 0x0459 0xffff flowid 3:2
      
      # Ted to same pro port 1114
      tc filter add dev eth0 parent 3:0 prio 7 u32 ht 2:6: match ip dst 192.168.1.21 match tcp dst 0x045a 0xffff flowid 3:3
      
      # Projdi hash table a pokud neni fragmentovana, pouzij protokol jako hashovaci klic.
      tc filter add dev eth0 parent 3:0 prio 7 handle ::1 u32 ht 800:: match ip nofrag offset mask 0x0f00 shift 6 hashkey mask 0x00ff0000 at 8 link 1:
      tc filter add dev eth0 parent 3:0 prio 7 handle ::1 u32 ht 800:: match ip nofrag offset mask 0x0f00 shift 6 hashkey mask 0x00ff0000 at 8 link 2:
      
      

      
      
      

   9. Použité zdroje

      • ftp://lrcftp.epfl.ch/pub/linux/diffserv/misc/dsid-01.txt
      • http://www.atnf.csiro.au/~mminhazu/CALU-MEL/
      • http://lrcwww.epfl.ch/linux-diffserv/
      • http://www.ietf.org/html.charters/diffserv-charter.html