HFSC Scheduling mit Linux

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

Der HFSC-

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

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/