Le terme QoS (Quality of Service) désigne de nombreux éléments et mécanismes du réseau, mais il est très souvent réduit aux problématiques de bande passante. Nous allons voir que dans le contexte précis du noyau Linux il s'agit effectivement de gérer les débits au niveau des interfaces, mais aussi leur latence et l'impact plus ou moins direct que cela peut avoir sur différents services.

La question de qualité de service peut se poser à différents endroits: depuis un appareil final (ordinateur, téléphone, etc), depuis un appareil de routage, depuis un backbone, depuis un modem ou un DSLAM, etc. Les stratégies et les besoins seront souvent différents, il sera donc important de bien comprendre le contexte d'un problème avant de le résoudre.

La QoS dans sa définition la plus restreinte désigne un ensemble de fonctions et de paramètres appliqués à une interface réseau et visant à régir son traffic sortant et - dans une moindre mesure - entrant. Les fonctions que nous allons pouvoir gérer sont:

• Le contrôle de bande passante (Shaping) permettant de limiter et arbitrer la répartition d'une bande passante donnée entre diffénts services
• L'ordonnancement (Scheduling) des paquets dans les files d'attente permettant de joueur sur la latence (interactivité) des services
• Le contrôle de congestion (Policing) permettant d'aller plus loin que la simple congestion classique d'une interface (voir ERD).

Il est important de comprendre que si on peut évidemment contrôler et arbitrer totalement ce que l'on fait sortir par une interface, il n'en est pas de même pour le traffic entrant qui dépend de caractéristiques du réseau indépendantes de notre interface. Ainsi la gestion de bande passante et d'ordonnancement n'auront de sens que pour le traffic sortant tandis que le contrôle de congestion pourra n'être appliqué qu'en entrée.

Les queue disciplines représentent une structure de donnée et un algorithme particulier pour traiter un flux de paquet transitant via une interface. Les traitements possibles sont les suivants:

• Limitation de bande passante (en sortie)
• Réordonnancement des paquets
• Lachâge de paquets

Dans le modèle QoS, chaque interface possède une telle qdisc (celle par défaut étant une simple FIFO).

Il existent une catégorie deqdisc dites classless qui se contentent d'accepter quelques paramètres pour être complètement définies et utilisables:

• pfifo, bfifo: simple FIFO avec limite de vitesse par paquets ou octets
• pfifo_fast: une FIFO à trois bandes appliquant un principe de priorité simple et honorant le ToS
• red: pour Random Early Detection (prévention de congestion)
• sfq: pour Stochastic Fairness Queuing (distribution statistique “équitable”)
• tbf: pour Tocken Bucket Filter (contrôle précis de la bande passante)

Enfin il existe des qdisc dites classfull qui permettent de créer des hiérarchies complexes de règles de traffic, et en particulier d'imbriquer des qdisc dans d'autres:

• CBQ: pour Class Based Queuing, le mécanisme historique de QoS
• HTB: pour Hierarchy Tocken Bucket, alternative à CBQ pour des situations différentes
• PRIO: un simple algorithme de gestion de priorité en servant les classes dans l'ordre

Pour nommer les qdisc, on utilise un simple numéro appelé le majeur noté sous la forme 5: (pour le qdisc numéro 1).

Les classes n'interviennent que pour les méthodes de gestion de file (qdisc) dites classfull. Ces algorithmes permettent une hiérarchisation plus ou moins sophistiquée des services et de l'attribution de leur bande passante. Ainsi les classes vont-elles nous servir à établir de structures arborescentes à l'intérieur des qdisc.

Pour nommer les classes, on leur attribue un simple numéro appelé le mineur et on les préfixe toujours avec le numéro (majeur) de leur qdisc, exemple: 5:19.

Pour les qdisc classfull, le traffic doit être distribué entre les classes associées au qdisc, c'est le rôle des filtres. Il s'agit de simples règles basées sur des informations des paquets (protocole, adresses sources ou destination, port, etc) et de la classe qui sera ainsi assignée à chaque paquet. C'est à ce stade qu'on effectue l'identification et la classification des services.

Avant de pouvoir décider de quelle gestion nous allons appliquer aux “services”, il va falloir qualifier ces services en utilisant des critères simples: protocole, adresse, port, etc. La syntaxe générale pour créer un filtre avec la QoS Linux se présente comme suit:

#tc filter add dev eth0 parent x:y protocol ip prio 1 [...filtre...] flowid a:b

• add dev eth0: un filtre est toujours attaché à une interface particulière
• parent x:y: un filtre permet de distribuer les paquets parmi les classes d'un qdisc (voir plus loin
• protocl ip: les filtres dépendent du protocole de transport choisi (ip, atm, etc)
• prio 1: les filtres sont évalués dans l'ordre croissant de priorité (il s'agit d'un classement donc)
• …filtre…: les filtres les plus classiques sont définis ci-dessous
• flowid a:b: si un paquet remplit les critères du filtre il est envoyé à cette classe du qdisc

La classification la plus simple se base sur les IP sources ou destination :

#tc filter ... u32 match ip src 193.82.10.25/28 ...
#tc filter ... u32 match ip dst 193.82.10.51/32 ...

… ou bien les ports source et destination:

#tc filter ... u32 match ip sport 3306 0xffff ...
#tc filter ... u32 match ip dport 80 0xffff ...

Le protocole IP possède un champ standard de quelques bits appelé ToS (Type of Service) qui peut valoir precedence, delay, throughput ou reliability (http://www.faqs.org/rfcs/rfc791.html RFC791). Ce champ peut être réutilisé tel quel, bien que souvent l'administrateur système ne fasse pas confiance aux applications pour annoncer correctement leur type de service.

#tc filter ... u32 match ip tos 0x01 0xff ...

Où 0xff est le masque (le champ ToS fait 8 bits) et 0x01 la valeur recherchée (consulter Type of Service dans la RFC791).

Si l'on a déjà fait un effort de classification pour un parefeu via iptables, on peut le réutiliser pour la QoS. Ce mécanisme permet également d'effectuer des classifications basées sur des paramètres qui dépassent le contexte de l'interface contrôlée, comme par exemple les choix de routage (interface source, etc).

Si le parquet a été marqué avec le mécanisme mangle (numérotage des paquets), il peut être reconnu avec le filtre handle :

#iptables -A PREROUTING -t mangle -i eth1 -j MARK --set-mark 42
#tc filter ... handle 42 ...

Dans le schéma général où l'on désire associer des qualités de service différentes à des flux distincts, les règles qui vont s'appliquer vont être plus complexes: d'une part elles vont s'appliquer spécifiquement à un type de trafic concerné, mais elles vont aussi êtres interdépendantes puisqu'elles doivent cohabiter dans les contraintes de la même interface réseau (bande passante, taille de la file d'attente, etc).

Le qdisc PRIO est l'un des exemples “classfull” les plus simples à expliquer. On le crée en spécifiant un nombre de bandes, où chaque bande est concrétisées par une classe. Les classes sont alors automatiquement numérotées à partir de zéro, et la distribution du trafic sortant va se faire en allant chercher les paquets dans la première bande jusqu'à ce qu'elle soit vide, puis passe à la seconde bande, etc.

Par défaut, cet algorithme permet une classification directe via une liste de correspondance associant le ToS d'un paquet IP avec une bande spécifique (donc il est possible de se passer de tc filter). C'est d'ailleurs cet algorithme, avec un mapping particulier, qui est utilisé par défaut sur une interface sous Linux quand l'option Routeur avancé est sélectionnée dans les paramètres du noyau.

Cet algorithme possède un défaut de conception important: il est possible de se retrouver dans une situation où la première bande ne désemplit jamais, et donc les paquets des bandes suivantes ne sont jamais distribués. On le combine donc en général avec des solutions de limitation de bande passante au niveau des bandes de haute priorité (par ex TBF).

Le qdisc HTB est basé au niveau de ses classes sur le même algorithme que TBF (le tocken bucket, voir plus bas). Il permet de réutiliser des notions intuitives de gestion et de limitation de bande passante mais de manière différenciée sur des flux distincts.

La différence notable est l'apparition d'un nouveau paramètre ceil, qui détermine une nouvelle limite: la possibilité de monter le taux de tranfert maximal (rate) si il reste de la bande passante au niveau du qdisc.

Illustration: si vous associez un qdisc HTB à une interface 100Mbps, avec 2 classes configurées comme suit :

• classe :1 : une limitation de bande passante rate=80mbps (ex: trafic “web”), mais un plafond autorisé de 100Mbps (ceil=100mbps)
• classe :2 : une limitation de bande passante rate=20mbps (ex: trafic “mail”)

Si votre interface est saturée, alors l'algorithme répartira comme demandé (80/20) la bande passante entre les deux classes. Mais si l'interface n'est pas saturée alors:

• classe :1 : le trafic peut dépasser 80Mbps et “emprunter” de la bande passante non utilisée par les autres classes
• classe :2 : le trafic ne dépassera en aucun cas 20Mbps, même si l'interface n'est pas saturée

Les notions de bande passante et de latence sont étroitement liées, selons différents contextes.

• Bande passante: une mesure du flux d'octets traversant une interface. Il s'agit en général d'une moyenne observée, car le phénomène de transmission du point de vue IP est discret et basé sur l'envoi de “paquets d'information” (la durée de transfert du paquet est inconnue, il est considéré “parti” ou non).

• Latence: dans le cadre d'un algorithme de QoS, il s'agit du temps qu'il s'écoule entre l'ordre d'envoi d'un paquet (soure: application ou routage) et l'envoi effectif confirmé par l'interface physique. Dans le cadre d'un protocole de transport comme TCP, il s'agit en général d'une mesure liée au RTT (Round Trip Time), délai d'envoi et de réponse cumulés d'un paquet sur un transport donné (et qui inclu donc en général la latence locale de la QOS sur les deux extrémités).

Chaque interface réseau est associée avec une file d'attente, et la QoS consiste à décider quelle sera la stratégie pour sélectionner les paquets dans la file d'attente. Dans l'algorithme FIFO, un paquet qui entre dans la file d'attente ne pourra en ressortir que losque ces prédécesseurs ont été émis. On a ainsi cette relation simple:

Latence = Longueur_file / Bande_passante

Ex: 2.6ms = 32KB / 100Mbps

Bien qu'il soit objectivement désirable de réduire la file d'attente pour améliorer la latence, plusieurs paramètres exigent une taille de file d'attente minimale :

• Tranferts vers l'interface : afin d'optimiser les efforts effectués par le noyau (interruptions / context switches), il est souhaitable au niveau matériel de tranférer les paquets par blocs. Sur une interface 100mbps, si on veut se limiter à 100 interruptions par seconde, il faudra une file d'attente d'au moins 122KB.
• Efficacité du transfert : afin de profiter au maximum de la bande passante disponible, il est important d'avoir une file d'attente toujours non vide afin que l'interface puisse envoyer des paquets dès qu'elle en a l'occasion, sans attendre. Les modems ADSL sont réputés utiliser cette technique pour maximiser les résultats, qui sont effectivements bons pour les transferts soutenus, mais mauvais pour la latence.

Le protocole TCP a la particularité de contrôler son flux, en d'autres termes il possède par conception ses propres mécanismes de QoS. Il est connu qu'en particulier il s'adapte automatiquement au taux de transfert optimal d'un chemin de transfert, et partage par défaut “équitablement” les ressources entre sessions TCP.

La gestion du flux se fait par l'échange de paquets entre les deux extrémités d'une session TCP. De manière générale, l'envoyeur ne peut procéder tant qu'il n'a pas reçu un message du receveur (typiquement une information ACK et/ou une fenêtre de transmission).

Cela signifie que la bande passante d'un transfert TCP, par exemple dans un sens descendant :

• dépend d'un seuil de latence de transfert entre les deux extrémités (RTT)
• dépend de la bande passante montante

L'algorithme du tocken bucket est très présent dans les mécanismes de gestion de bande passante. Il permet d'implémenter une limitation effective de la bande passante, tout en prenant en compte les effets transitoires et irréguliers de la transmission par paquets.

Le principe est le suivant: on considère que l'on possède un seau que l'on remplit de jetons de manière régulière à un débit constant (le débit de contrôle), sauf quand le seau est “plein” (le seau a donc une taille). Pour émettre un paquet, on doit obtenir un jeton en le piochant dans le seau, sans limite de vitesse particulière. S'il n'y a pas de jeton disponible, on attend jusqu'à ce qu'il en apparaisse.

Le trafic sortant est donc toujours limité par la vitesse de remplissage du seau, mais en moyenne seulement puisqu'il est possible de vider le seau plus vite qu'il n'est rempli.

La taille du seau est en général dénommée burst et désigne la quantité d'information qui peut être potentiellement transmise immédiatement: un “pic de burst” a alors pour hauteur (valeur) la limite physique imposée par l'interface (ex: 100mbps) et pour longueur une distance proportionnelle à la taille du seau.