Quality of Service

Introduction

Quality of Service(QoS) is the ability to provide different priority to different applications, users, or data flows, or to guarantee a certain level of performance to a data flow. For example, for a certain category of packets, we can provide a guaranteed bit rate. When two different streams of data packets could be sent on the interface, we can prioritize the traffic. QoS guarantees are used to optimally use scarce bandwidth and also to meet latency requirements of certain traffic classes like VoIP.

Terminology

Queueing Discipline - (qdisc) An algorithm that manages the queue of a device, either incoming (ingress) or outgoing (egress).

root qdisc - The root qdisc is the qdisc attached to the device.

Classless qdisc - A qdisc with no configurable internal subdivisions.

Classful qdisc - A classful qdisc contains multiple classes. Some of these classes contains a further qdisc, which may again be classful, but need not be. According to the strict definition, pfifo_fast *is* classful, because it contains three bands which are, in fact, classes. However, from the user's configuration perspective, it is classless as the classes can't be touched with the tc tool.

Classes - A classful qdisc may have many classes, each of which is internal to the qdisc. A class, in turn, may have several classes added to it. So a class can have a qdisc as parent or an other class. A leaf class is a class with no child classes. This class has 1 qdisc attached to it. This qdisc is responsible to send the data from that class. When you create a class, a fifo qdisc is attached to it. When you add a child class, this qdisc is removed. For a leaf class, this fifo qdisc can be replaced with an other more suitable qdisc. You can even replace this fifo qdisc with a classful qdisc so you can add extra classes.

Classifier - Each classful qdisc needs to determine to which class it needs to send a packet. This is done using the classifier.

Filter - Classification can be performed using filters. A filter contains a number of conditions which if matched, make the filter match

Policing - Delaying or dropping packets in order to make traffic stay below a configured bandwidth. In Linux, policing can only drop a packet and not delay it - there is no 'ingress queue'.

ceil - sets max rate at which class can dequeue packets. This parameter is most easy to understand, by default ceil=rate, but that way that class will not prioritize traffic.

rate - Provides the way to calculate automatic quantums for classes. Also sets the the minimal rate at which class will dequeue packets. ( usefull for those who have fast links. and only few classes)  at low speed links and high number of classes it doesnt work well, since if you will divide 100kbit to 20 classes rate will be only 5kbit, that is not worth typing. so set it to 1kbit in such case.

QoS is implemented by defining policies for the interface. Each policy may contain many more policies defined as its child policies. Each policy may also contain several classes. There can be only one policy at the root, which is applied directly on the interface.

Classful Queueing Disciplines

Flow within classful qdiscs and classes 

When traffic enters a classful qdisc, it needs to be sent to any of the classes within - it needs to be 'classified'. To determine what to do with a packet, the so called 'filters' are consulted. It is important to know that the filters are called from within a qdisc, and not the other way around!

The filters attached to that qdisc then return with a decision, and the qdisc uses this to enqueue the packet into one of the classes. Each subclass may try other filters to see if further instructions apply. If not, the class enqueues the packet to the qdisc it contains.

Besides containing other qdiscs, most classful qdiscs also perform shaping. This is useful to perform both packet scheduling (with SFQ, for example) and rate control. You need this in cases where you have a high speed interface (for example, ethernet) to a slower device (a cable modem).

If you were only to run SFQ, nothing would happen, as packets enter & leave your router without delay: the output interface is far faster than your actual link speed. There is no queue to schedule then.

Qdiscs family : roots, handles, siblings and parents

Each interface has one egress 'root qdisc'. By default, it is the earlier mentioned classless pfifo_fast queueing discipline. Each qdisc and class is assigned a handle, which can be used by later configuration statements to refer to that qdisc. Besides an egress qdisc, an interface may also have an ingress qdisc , which polices traffic coming in.

The handles of these qdiscs consist of two parts, a major number and a minor number : :. It is customary to name the root qdisc '1:', which is equal to '1:0'. The minor number of a qdisc is always 0.

Classes need to have the same major number as their parent. This major number must be unique within a egress or ingress setup. The minor number must be unique within a qdisc and his classes.

The PRIO qdisc

The PRIO qdisc only subdivides traffic based on how you configured your filters. You can consider the PRIO qdisc a kind of pfifo_fast, whereby each band is a separate class instead of a simple FIFO.

Working

When a packet is enqueued to the PRIO qdisc, a class is chosen based on the filter commands you gave. By default, three classes are created. These classes by default contain pure FIFO qdiscs with no internal structure, but you can replace these by any qdisc you have available.

Whenever a packet needs to be dequeued, class :1 is tried first. Higher classes are only used if lower bands all did not give up a packet.

This qdisc is very useful in case you want to prioritize certain kinds of traffic without using only TOS-flags but using all the power of the tc filters. You can also add an other qdisc to the 3 predefined classes, whereas pfifo_fast is limited to simple fifo qdiscs.

Because it doesn't actually shape, the same warning as for SFQ holds: either use it only if your physical link is really full or wrap it inside a classful qdisc that does shape. The latter holds for almost all cable modems and DSL devices.

In formal words, the PRIO qdisc is a Work-Conserving scheduler.

Hierarchical Token Bucket  (HTB)

HTB is meant as a more understandable, intuitive and faster replacement for the CBQ qdisc in Linux. Both CBQ and HTB help you to control the use of the outbound bandwidth on a given link. Both allow you to use one physical link to simulate several slower links and to send different kinds of traffic on different simulated links. In both cases, you have to specify how to divide the physical link into simulated links and how to decide which simulated link to use for a given packet to be sent.

Unlike CBQ, HTB shapes traffic based on the Token Bucket Filter algorithm which does not depend on interface characteristics and so does not need to know the underlying bandwidth of the outgoing interface. 

Working

At each node we look for an instruction, and then go to the class the instruction refers us to. If the class found is a barren leaf-node (without children), we enqueue the packet there. If it is not yet a leaf node, we do the whole thing over again starting from that node. 

All classes can have independent parameters, but if parent parameter is lower than child then of course it will limit child's parameter.  (if you will set parent ceil to 50kbit and its child's ceil to 100kbit then is still will not exceed 50kbit).

Packet classification is done usually by filters, they can direct packets anywhere, probably even in loop, must should be avoided filters have lots of options,  but all are very straight and and usually just match some part of packet memory, with optional mask. nothing more advanced can be done. 

Parameters

1. For Qdiscs

parent major:minor | root - This mandatory parameter determines the place of the HTB instance, either at the root of an interface or within an existing class.

handle major - Like all other qdiscs, the HTB can be assigned a handle. Should consist only of a major number, followed by a colon. Optional, but very useful if classes will be generated within this qdisc.

default minor-id - Unclassified traffic gets sent to the class with this minor-id.

2. For Classes

parent major:minor - Place of this class within the hierarchy. If attached directly to a qdisc and not to another class, minor can be omitted. Mandatory.

classid major:minor - Like qdiscs, classes can be named. The major number must be equal to the major number of the qdisc to which it belongs. Optional, but needed if this class is going to have children.

prio priority - In the round-robin process, classes with the lowest priority field are tried for packets first. Mandatory.

rate rate - Maximum rate this class and all its children are guaranteed. Mandatory.

ceil rate - Maximum rate at which a class can send, if its parent has bandwidth to spare. Defaults to the configured rate, which implies no borrowing

burst bytes - Amount of bytes that can be burst at ceil speed, in excess of the configured rate. Should be at least as high as the highest burst of all children.

cburst bytes - Amount of bytes that can be burst at 'infinite' speed, in other words, as fast as the interface can transmit them. For perfect evening out, should be equal to at most one average packet. Should be at least as high as the highest cburst of all children.

References

http://lartc.org/lartc.html#LARTC.QDISC

http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm

http://linux.die.net/man/8/tc-htb

http://pupa.da.ru/tc/