Queueing Disciplines: Traffic Control mit Linux

Vernetzte Anwendungen wollen ihre Daten meist möglichst schnell transportiert wissen. Diesem Wunsch kommt Linux nach Kräften nach. Aber nicht immer ist das für alle Beteiligten ideal: Besonders bei asynchronen DSL-Anschlüssen sowie VoIP (Voice over IP) ist es viel wichtiger, die Verzögerung und Priorität einzelner Pakete gezielt zu beeinflussen. VoIP beispielsweise braucht kaum Bandbreite, dafür aber einen gleichmäßigen Versand der Pakete mit möglichst kleiner Latenz. Ein FTP-Transfer dagegen ist für jedes Quäntchen Bandbreite dankbar, einzelne verzögerte Pakete fallen aber nicht ins Gewicht.

Teilen sich mehrere Parteien einen Internetzugang, dann sollte der (Linux-)Zugangsrouter die tendenziell knappen Netzressourcen gerecht zuweisen. Die Basis für diese Traffic Engineering genannte Aufgabe legt der Kernel per Queueing Disciplines, kurz QDiscs. Sie dienen jeder Netzwerkschnittstelle als Puffer. Bei einer kurzfristigen Überlastung nimmt die Schnittstelle weiterhin Pakete entgegen und speichert sie per QDisc, statt sie sofort weiterzusenden.

Schön der Reihe nach

Die Puffer sind im Normalfall als einfache Warteschlangen organisiert, die Pakete in unveränderter Reihenfolge weiterreichen (Fifo; First in, first out). QDiscs können den Verkehr aber auch begrenzen, verzögern, aufteilen und anderweitig regeln. Die passenden Module liegen in der Kernelkonfiguration (»make xconfig«) unter »Device Drivers | Networking support | Networking options | QoS and/or fair queueing«.

Aus Sicht der Software dient die Queueing Discipline als allgemeine und abstrakte Schnittstelle zu verschiedenen Implementierungen (im Kernelverzeichnis »net/sched«). Sie definiert Operationen, die jede Implementierung unterstützen muss. Im Mittelpunkt stehen die Funktionen »enqueue()« und »dequeue()«, die Pakete aufnehmen und wieder freigeben.

Für das Zustellen der Pakete an eine Netzwerkschnittstelle ist im Kernel die Funktion »dev_queue_xmit()« (in »net/core/dev.c«) zuständig. Sie hängt das Paket mit »enqueue()« in die konfigurierte QDisc und startet dann den Sendevorgang mit der »qdisc_run()«-Funktion. Letztere sendet so lange die zwischengespeicherten Pakete, bis die QDisc leer ist oder eine Abbruchbedingung eintritt. Das könnte ein Fehler der Netzwerkschnittstelle sein, die sich noch mit einem anderen Paket beschäftigt, oder die QDisc gibt keine weiteren Pakete mehr frei, weil sie ein definiertes Limit überschritten hat.

Schlange marsch

Die Funktion »qdisc_run()« ruft für jeden Sendeversuch einmal »qdisc_restart()« auf. Diese entnimmt mit »dequeue()« ein Paket aus der QDisc und übergibt es an die »hard_start_xmit()«-Funktion des Gerätetreibers. Meldet der Treiber einen Fehler, dann stellt »qdisc _restart()« das Paket durch einen »requeue()«-Aufruf wieder an seine ursprüngliche Position in die QDisc und teilt dem Kernel per »NET_TX_SOFTIRQ« mit, dass noch Pakete in der QDisc warten. Dieser Aufruf steckt in der Inline-Funktion »netif_sched()«. Bei nächster Gelegenheit ruft der Kernel dann »qdisc_run()« auf. Abbildung 1 zeigt die Zusammenhänge.

Abbildung 1: Eine QDisc besteht im Wesentlichen aus den »enqueue()«- und »dequeue()«-Funktionen. Trifft ein Layer-3-Paket ein, hängt »dev_queue_xmit()« es in eine Warteschlange und startet mit »qdisc_run()« die Übertragung.

Jeder Netzwerkschnittstelle darf immer nur eine QDisc zugeordnet sein. Für komplexe Strukturen sind Klassen nötig. Eine klassenbasierte Queueing Discipline muss zusätzliche Funktionen bereitstellen. Deren Prototypen sind in der »Qdisc_class_ops«-Struktur in »include/net/pkt_sched.h« definiert. Einer Klasse lassen sich wiederum QDiscs zuordnen. Die QDisc- und Klasseninstanzen werden im QDisc-Konzept anhand eines zweiteiligen 32-Bit-Werts x:y identifiziert. Die ersten 16 Bit (x) dieser ID bezeichnen die QDisc, die übrigen (y) die Klasse (Abbildung 2).

Abbildung 2: In der QDisc-Klassenhierarchie ist jede Instanz durch ein Paar aus 16-Bit-Werten gekennzeichnet. Die QDisc-Nummer steht vor dem Doppelpunkt, danach folgt die Kennung der Klasse.

Filter ordnen die Netzwerkpakete einer der Klassen zu. Jede QDisc besitzt eine eigene Liste von Filtern, die sie während des Enqueue-Vorgangs zur Klassifikation heranzieht. Das so genannte Policing ist ebenfalls mit der Klassifikation verbunden. Policer begrenzen die Rate, mit der ein Filter die ankommenden Pakete in den Rechner schleust. Treffen doch mehr Pakete ein, verwirft die QDisc das Paket (»TC_POLICE_SHOT«) oder klassifiziert es neu (»TC_POLICE_RECLASSIFY«).