HFSC Scheduling mit Linux

[thrive_text_block color=”note” headline=”Get the Best Web Hosting Deals”] Get Liquid Web Coupon and get discounts up to 50% OFF [/thrive_text_block]
English Version

For complex traffic shaping scenarios, hierarchical algorithms are necessary. Current Linux versions support the algorithms HTB [4] and HFSC [1]. While HTB mainly divides Token-Bucket Filter (TBF) into a hierarchical structure while retaining the essential characteristics of a TBF, the HFSC algorithm allows, in addition to the proportional distribution of bandwidth, the allocation and control of latencies. This allows better and more efficient use of the line in scenarios where both bandwidth-intensive data services and interactive services share a line.

If a Nezuzugang is used by several parties and different services, then a meaningful management of the resources is necessary. Ensuring minimum bandwidths (link-sharing) for each service and user is one possibility. In scenarios with Voice-Over-IP or streaming services, besides the pure bandwidth allocation, the avoidance of delays is also the main focus.

In a scenario in which two users share an internet line with 1000kbit transmission power, both users should at least each have at least 500kbit transmission power at each time. One of the users also uses a maximum of 100kbit of its Internet telephony bandwidth, which uses the remaining transmit power for general data transport services. Figure 1 shows the corresponding hierarchy.

Figure 1: Hierarchy of a shared network access.
Assuming that all packets to be sent correspond to a fixed size of 1500 bytes and all classes transmit with maximum capacity, then due to the line capacity of 1000 kbit 12 ms (8 * 1500 byte / 1000000 bit / s = 12 ms) it takes one data packet to ship. The Voice-Over-IP application broadcasts at 100kbps, which is about 8 packets per second. To comply with the guaranteed rate of 100kbps for this class, the Qdisc must send a data packet of the class at least every 120ms, which would mean a maximum delay of about 132ms per packet. This example illustrates the close relationship between bandwidth and delay time.

The HFSC algorithm is able to handle both resources, bandwidth and delay time separately. For this purpose, the resource allocation algorithm uses the service curve model. A service curve S (t) represents the work done (service) in transmitted bits at a time t. The slope of the curve corresponds to the (transmit) rate.

The idea for influencing the latency times lies in the design of the service curves of the individual classes. If you create a two-part, piecewise linear service curve for the Voice-Over-IP class, with a first section of 400 kbits and 30 ms long, and a second section with a slope of 100 kbits, the transmission delay will stop Reduce 30 ms. However, this gain of about 78 ms delay time is at the expense of the other classes, because at any time the sum of all curves, the service curve of the line, so their total capacity must not exceed. In our example, the shortened delay time for the voice over IP class should be at the expense of the party for unspecified data of party A, whose service curve must be adjusted so as not to exceed the global limit. This increases the maximum transmission delay of this class from 30 ms to a total of 52.5 ms. For pure data transport, such as FTP, the delay time plays only a minor role, in contrast to the data throughput, which is not affected by the adaptation of the service curve.

Figure 2: Scenario with linear and piecewise linear service curves.
The HFSC algorithm distinguishes between a “real time” criterion and a “link sharing” criterion. A leaf class can be assigned a real-time and a link-sharing service curve, inner classes, however, only a link-sharing service curve. The real-time criterion is only applied to leaf classes, since only these classes can actually contain packages. It is real time oriented and is responsible for the adherence to the guaranteed service. The link-sharing criterion is based only on the relationships between neighboring classes. It is responsible only for the fair distribution of the service, but not for absolute guarantees. The separation into two criteria is necessary in order to be able to keep the guaranteed delay times under all circumstances. This also means that a class can send a package because of its real-time warranty, if it briefly violates the link-sharing criterion of classes higher up the hierarchy.

If, for example, the data class of party A is already active, then it sends a maximum of 400 kbit packets. Now, at any time, the voice-over-Ip Kla

Für komplexe Traffic-Shaping-Szenarien sind hierarchische Algorithmen notwendig. Aktuelle Linux Versionen unterstützen die Algorithmen HTB [4] und HFSC [1]. Während HTB hauptsächlich Token-Bucket Filter (TBF) in eine hierarchische Struktur gliedert und dabei die wesentlichen Eigenschaften eines TBFs beibehält, erlaubt der HFSC Algorithmus neben der proportionalen Aufteilung der Bandbreite zudem noch die Vergabe und Kontrolle von Latenzzeiten. Dies ermöglicht eine bessere und effizientere Nutzung der Leitung in Szenarien, in denen sowohl bandbreiten-intensive Daten-Dienste und als auch interaktive Dienste sich eine Leitung teilen.
Wird ein Nezuzugang von mehreren Parteien und verschiedenen Diensten genutzt, so ist ein sinnvolles Management der Ressourcen notwendig. Die Zusicherung von Mindestbandbreiten (link-sharing) für die einzelnen Dienste und Nutzer ist eine Möglichkeit. Bei Szenarien mit Voice-Over-IP oder Streaming-Diensten steht neben der reinen Bandbreitenvergabe zudem noch die Vermeidung von Verzögerungszeiten im Vordergrund.

In einem Szenario, in dem sich zwei Nutzer eine Internetleitung mit 1000kbit Sendeleistung teilen, sollen beide Nutzer zu jedem Zeitpunkt mindestens jeweils über 500kbit Sendeleistung verfügen. Einer der Nutzer verwenden zudem maximal 100kbit seiner Bandbreite für Internet-Telefonie, die restliche Sendeleistung für allgemeine Datentransportdienste verwendet. Abbildung 1 zeigt die entsprechende Hierarchie.

HFSC Scheduling mit Linux 1
Abbildung 1: Hierarchie eines geteilten Netzzugangs.

Angenommen, alle zu sendenden Pakete entsprechen einer festen Größe von 1500 Byte und alle Klassen senden mit maximaler Kapazität, dann dauert es aufgrund der Leitungskapazität von 1000 kbit 12 ms (8 * 1500 byte / 1000000 bit/s = 12ms), um ein Datenpaket zu versenden. Die Voice-Over-IP Anwendung sendet mit 100 kbit, was etwa 8 Paketen pro Sekunde entspricht. Um die garantierte Rate von 100 kbit für diese Klasse einzuhalten, muss die Qdisc spätestens alle 120 ms ein Datenpaket der Klasse versenden, was eine maximale Verzögerung von etwa 132 ms pro Paket bedeuten würde. Dieses Beispiel illustriert den engen Zusammenhang von Bandbreite und Verzögerungszeit.

Der HFSC-Algorithmus ist in der Lage die beiden Ressourcen, Bandbreite und Verzögerungszeit, getrennt zu behandeln. Hierfür nutzt der Algorithmus für die Vergabe der Ressourcen das Modell der Service-Kurve. Eine Service-Kurve S(t) repräsentiert die geleistete Arbeit (Service) in gesendeten Bits zu einem Zeitpunkt t. Die Steigung der Kurve entspricht der (Sende)-Rate.

Die Idee zur Beeinflussung der Latenzzeiten liegt in der Gestaltung der Service-Kurven der einzelnen Klassen. Erstellt man für die Voice-Over-IP Klasse eine zweiteilige, stückweise lineare Service-Kurve, deren erster Abschnitt eine Steigung von 400 kbit aufweist und 30 ms lange ist, und deren zweiter Abschnitt eine Steigung von 100 kbit aufweist, lässt sich die Sendeverzögerung auf 30 ms reduzieren. Dieser Gewinn von etwa 78 ms Verzögerungszeit geht jedoch zu Lasten der anderen Klassen, da zu jedem Zeitpunkt die Summe aller Kurven, die Service-Kurve der Leitung, also deren Gesamtkapazität, nicht überschreiten darf. In unserem Beispiel soll die verkürzte Verzögerungszeit für die Voice-Over-IP Klasse auf Kosten der Klasse für unspezifizierte Daten der Partei A gehen, deren Service-Kurve angepasst werden muss, um das globale Limit nicht zu überschreiten. Dadurch erhöht sich die maximale Sendeverzögerung dieser Klasse von 30 ms auf insgesamt 52,5 ms. Für reinen Datentransport, wie zum Beispiel FTP, spielt die Verzögerungszeit, im Gegensatz zu dem Datendurchsatz, der durch die Anpassung der Service-Kurve nicht beeinträchtigt wird, lediglich eine untergeordnete Rolle.

HFSC Scheduling mit Linux 2
Abbildung 2: Szenario mit linearen und stückweise linearen Service-Kurven.

Der HFSC-Algorithmus unterscheidet zwischen einem “Real-Time”-Kriterium und “Link-Sharing”-Kriterium. Einer Leaf-Klasse kann eine Real-Time und eine Link-Sharing Service-Kurve zugeordnet werden, inneren Klassen hingegen nur eine Link-Sharing Service-Kurve. Das Real-Time-Kriterium wird nur bei Leaf-Klassen angewandt, da nur diese Klassen tatsächlich Pakete enthalten können. Es ist Echtzeit orientiert und ist für die Einhaltung des garantierten Service verantwortlich. Das Link-Sharing Kriterium orientiert sich nur an den Verhältnissen zwischen benachbarten Klassen. Es ist nur für die faire Verteilung des Service, nicht aber für absolute Garantien zuständig. Die Trennung in zwei Kriterien ist notwendig, um die garantierten Verzögerungszeiten unter allen Umständen einhalten zu können. Das bedeutet auch, dass eine Klasse ein Paket aufgrund seiner Real-Time Garantie senden kann, wenn dadurch kurzfristig das Link-Sharing-Kriterium von Klassen weiter oben in der Hierarchie verletzt wird.

Ist beispielsweise die Datenklasse von Partei A bereits aktiv, so sendet diese mit maximal 400 kbit Pakete. Wird jetzt zu einem beliebigen Zeitpunkt die Voice-Over-Ip Klasse von A aktiv, so darf diese aufgrund ihrer Real-Time-Garantie kurzfristig mit einer höheren Rate senden (Abbildung 3). Dadurch summiert sich der Service für die Klasse A auf über 500 kbit, wodurch kurzfristig das Link-Sharing-Kriterium dieser Klasse verletzt wurde. Um langfristig jedoch auch die Link-Sharing Garantien einhalten zu können, wird die Klasse A für diese kurzfristige Überschreitung “bestraft”.

HFSC Scheduling mit Linux 3
Abbildung 3: Zwischen t1 und t2 übersteigt die Gesamtleistung die maximal erlaubte.

Jeder Klasse der Hierarchie ist eine “Virtual-Time” zugeordnet, die dem geleisteten Service entspricht. Sobald ein Paket gesendet werden kann, wird auf jeder Ebene der Hierarchie, beginnend an der Wurzel, diejenige Klasse gesucht, die die geringste virtuelle Zeit aufweist. Die auf diesem Weg gefundene Leaf-Klasse sendet ein Paket und die virtuelle Zeit der Klasse wird, ebenso wie die aller parent-Klassen bis zur Wurzel, entsprechend erhöht. Sendet eine Klasse aufgrund ihres Real-Time Kriteriums, so wird ihre virtuelle Zeit ebenfalls erhöht. Falls dadurch parent-Klassen das Link-Sharing Kriterium verletzen (d.h. senden, obwohl Geschwister-Klassen mit geringerer Virtual-Time existieren), gleicht das Link-Sharing-Kriterium dies bei nächster Gelegenheit aus, indem es die Klasse nicht mehr auswählt, bis die anderen Klassen diesen Vorteil wieder aufgeholt haben.

Nutzung von HFSC unter Linux

Die Einrichtung einer HFSC Qdisc erfolgt zunächst durch die Zuordnung einer Qdisc zu einer Netzwerkschnittstelle mit optionaler Angabe der Default-Klasse:


tc qdisc add dev $dev root handle $ID: hfsc [default $classID ]

In einem zweiten Schritt wird die Klassenhierarchie durch sukzessives Einfügen von Klassen erstellt: 
tc add class dev $dev parent parentID classid $ID hfsc [ [ rt SC ] [ ls SC ] | [ sc SC ] ] [ ul SC ]

Die speziellen Eigenschaften einer Klasse werden durch ihre Service-Kurven (SC) festgelegt, die sich als 
SC := [ umax bytes dmax ms ] rate BPS

beschreiben lässt. Klassen auf den untersten Hierarchie-Ebenen können sowohl eine Real-Time Kurve (rt) als auch eine Link-Sharing Kurve (ls) zugeordnet werden, inneren Klassen nur Link-Sharing Kurven. Mittels der ul Service-Kurve lässt sich eine obere Leistungsschranke für jede Klasse definieren. Alternativ kann statt zwei identischen rt– und ls-Kurven auch nur eine sc-Kurve angegeben werden. Eine Service-Kurve wird durch die (Sende)-Rate (rate) beschrieben, die der ihrer Steigung entspricht. Soll die Kurve aus zwei Teilstücken bestehen, kann durch dmax die maximale Verzögerungszeit für eine bestimmte Sendeleistung umax angegeben werden.

Beispiel

  • # Beispiel aus Abbildung 1.
  • tc qdisc add dev eth0 root handle 1: hfsc
  • tc class add dev eth0 parent 1: classid 1:1 hfsc sc rate 1000kbit ul rate 1000kbit
  • tc class add dev eth0 parent 1:1 classid 1:10 hfsc sc rate 500kbit ul rate 1000kbit
  • tc class add dev eth0 parent 1:1 classid 1:20 hfsc sc rate 500kbit ul rate 1000kbit
  • tc class add dev eth0 parent 1:10 classid 1:11 hfsc sc umax 1500b dmax 53ms rate 400kbit ul rate 1000kbit
  • tc class add dev eth0 parent 1:10 classid 1:12 hfsc sc umax 1500b dmax 30ms rate 100kbit ul rate 1000kbit
Referenzen

[1] http://trash.net/~kaber/hfsc/

[2] http://developer.osdl.org/dev/iproute2/download/

[3] http://lartc.org/

[4] http://luxik.cdi.cz/~devik/qos/htb/