14. Gestionnaires de mise en file d'attente avancés & et moins communs

Si vous constatez que vous avez des besoins qui ne sont pas gérés par les files d'attente citées précédemment, le noyau contient quelques autres files d'attente plus spécialisées mentionnées ici.

14.1 bfifo/pfifo

Ces files d'attente sans classes sont plus simples que pfifo_fast dans la mesure où elles n'ont pas de bandes internes, tout le trafic étant vraiment équivalent. Elles ont cependant l'important avantage de réaliser des statistiques. Donc, même si vous n'avez pas besoin de mise en forme ou de donner de priorité, vous pouvez employer ce gestionnaire pour déterminer l'arriéré (backlog) de votre interface.

pfifo mesure en paquets et bfifo en octets.

Paramètres & usage

limit

Spécifie la taille de la file d'attente. Mesuré en octets pour bfifo, en paquets pour pfifo. Par défaut, correspond à des paquets de taille égal au paramètre txqueuelen de l'interface (voir le chapitre pfifo_fast) ou txqueuelen*mtu octets pour bfifo.

14.2 Clark-Shenker-Zhang algorithm (CSZ)

Ceci est si théorique que pas même Alexey (l'auteur principal de CBQ) ne prétend le comprendre. De sa source :

"David D. Clark, Scott Shenker and Lixia Zhang Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism.

Comme je le comprends, l'idée principale est de créer des flux WFQ pour chaque service garanti et d'allouer le reste de la bande passante au flux factice, appelé "flow-0". Le Flux-0 inclut le trafic de service prédictif et le trafic "best-effort". Il est traité par un ordonnanceur de priorité qui alloue la bande passante de plus grande priorité aux services prédictifs, et le reste aux paquets "best-effort".

Notez que dans CSZ, les flux ne sont PAS limités à leur bande passante. On suppose que le flux a passé le contrôle d'admission au bord du réseau QoS et qu'il n'a pas besoin de mises en forme supplémentaires. N'importe quelles autres tentatives pour améliorer le flux ou pour le mettre en forme grâce à un seau de jetons lors d'étapes intermédiaires introduiront des retards non désirés et augmentera l'instabilité.

A l'heure actuelle, CSZ est le seul ordonnanceur qui fournit un véritable service garanti. Les autres implémentations (incluant CBQ) n'assurent pas un délai garanti et rendent aléatoires l'instabilité.

Ne semble pas actuellement un bon candidat à utiliser, à moins que vous n'ayez lu et compris l'article mentionné.

14.3 DSMARK

Esteve Camps Chust <marvin@grn.es>
Ce texte est un extrait de ma thèse sur le "support QoS dans Linux", septembre 2000.

Documents sources :

• Draft-almesberger-wajhak-diffserv-linux-01.txt.
• Exemples de la distribution iproute2.
• White Paper-QoS protocols and architectures et Foires Aux Questions IP QoS, les deux par Quality of Service Forum.

Ce chapitre a été écrit par Esteve Camps <esteve@hades.udg.es>.

Introduction

Avant tout, il serait préférable de lire les RFC écrits sur ce sujet (RFC2474, RFC2475, RFC2597 et RFC2598) sur le site web du groupe de travail DiffServ IETF et sur le site web de Werner Almesberger (Il a écrit le code permettant le support des Services Différenciés sous Linux).

A quoi Dsmark est-il relié ?

Dsmark est un gestionnaire de mise en file d'attente qui offre les fonctionnalités dont ont besoin les services différenciés (Differentiated Services) (également appelé DiffServ ou tout simplement DS). DiffServ est l'une des deux architectures actuelles de la Qualité de Service (QoS : Quality of Services) (l'autre est appelée "Integrated Services" (services intégrés)) et il se base sur la valeur du champ DS contenue dans l'entête IP du paquet.

Une des premières solutions dans IP pour offrir des niveaux de qualité de service était le champ Type de Service (octet TOS) dans l'entête IP. En modifiant la valeur de ce champ, nous pouvions choisir un niveau élevé/faible du débit, du délai ou de la fiabilité. Cependant, cela ne fournissait pas une flexibilité suffisante pour les besoins de nouveaux services (comme les applications temps réel, les applications interactives et autres). Après ceci, de nouvelles architectures sont apparues. L'une d'elle a été DiffServ qui a gardé les bits TOS et les a renommés champ DS.

Guide des services différenciés

Les services différenciés sont orientés groupes. Cela signifie que nous ne savons rien des flux (ce sera le but des "integrated Services" (services intégrés)). Nous connaissons par contre les agrégations de flux et nous appliquerons des comportements différents suivant l'agrégation à laquelle appartient le paquet.

Quand un paquet arrive à un noeud de bord (noeud d'entrée du domaine DiffServ) et entre dans un domaine DiffServ, nous devrons avoir une politique, une mise en forme et/ou un marquage de ces paquets (le marquage fait référence à la mise en place d'une valeur dans le champ DS. Cela ressemble aux vaches :-) ). Ce sera cette marque/valeur que les noeuds internes de votre domaine DiffServ regarderons pour déterminer quel comportement ou niveau de qualité de service appliquer.

Comme vous pouvez le déduire, les Services Différenciés impliquent un domaine sur lequel toutes les règles DS devront être appliquées. Vous pouvez raisonner de la façon suivante : "Je classifierai tous les paquets entrant dans mon domaine. Une fois qu'ils seront entrés dans mon domaine, ils seront soumis aux règles que ma classification impose et chaque noeud traversé appliquera son niveau de qualité de service".

En fait, vous pouvez appliquer vos propres politiques dans vos domaines locaux, mais des autorisations au niveau service devront être considérées lors de la connexion à d'autres domaines DS.

En ce moment, vous vous posez peut-être beaucoup de questions. DiffServ est plus vaste que ce que j'ai expliqué. En fait, vous pouvez comprendre que je ne peux pas résumer plus de trois RFC en 50 lignes :-).

Travailler avec Dsmark

Comme le spécifie la bibliographie concernant DiffServ, nous différencions les noeuds frontières et les noeuds intérieurs. Ce sont deux éléments importants dans le chemin qu'emprunte le trafic. Les deux réalisent une classification quand un paquet arrive. Le résultat peut être utilisé à différents endroits lors du processus DS avant que le paquet ne soit libéré vers le réseau. Cela est possible car le nouveau code diffserv fourni une structure appelée sk_buff, incluant un nouveau champ appelé skb->tcindex. Ce champ mémorisera le résultat de la classification initiale et pourra être utilisé à plusieurs reprises dans le traitement DS.

La valeur skb->tc_index sera initialement configurée par le gestionnaire de mise en file d'attente DSMARK. Cette valeur sera extraite du champ DS de l'entête IP de tous les paquets reçus. En outre, le classificateur cls_tcindex lira tout ou une partie de la valeur skb->tcindex et l'utilisera pour sélectionner les classes.

Mais, avant tout, regardons la commande qdisc DSMARK et ses paramètres :

... dsmark indices INDICES [ default_index DEFAULT_INDEX ] [ set_tc_index ]

• indices: taille de la table des couples (masque,valeur). La valeur maximum est 2^n, où n>=0.
• Default_index: l'index d'entrée par défaut de la table si aucune correspondance n'est trouvée.
• Set_tc_index: indique au gestionnaire dsmark de récupérer le champs DS et de l'enregistrer dans skb->tc_index.

Comment SCH_DSMARK travaille.

Ce gestionnaire de mise en file d'attente réalisera les étapes suivantes :

• Si vous avez déclaré l'option set_tc_index dans la commande qdisc, le champ DS est récupéré et mémorisé dans la variable skb->tc_index.
• Le classificateur est invoqué. Celui-ci sera exécuté et retournera un identificateur de classe (class ID) qui sera enregistré dans la variable skb->tc_index. Si aucun filtre correspondant n'est trouvé, nous considérons l'option default_index comme étant l'identificateur de classe à enregistrer. Si, ni set_tc_index, ni default_index n'ont été déclarés, alors les résultats peuvent ne pas être prédits.
• Après avoir été envoyé dans le gestionnaire de file d'attente interne, où le résultat du filtre peut être réutilisé, l'identificateur de classe retourné par le gestionnaire est stocké dans la variable skb->tc_index. Cette valeur sera utilisée plus tard pour indexer la table masque-valeur. Le résultat de l'opération suivante sera assigné au paquet :

  Nouveau_champ_DS = ( Ancien_champ_DS & masque ) | valeur
  
  

• La nouvelle valeur résultera donc d'un ET logique entre les valeurs du champ_DS et du masque, suivi d'un OU logique avec le paramètre valeur. Regarder la figure suivante pour comprendre tout ce processus :

                         skb->ihp->tos
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >
     |                                                       |     ^
     | -- Si vous déclarez set_tc_index, nous configurons    |     |  <-----Peut changer
     |    la valeur DS dans la variable skb->tc_index        |     |O       le champ DS
     |                                                      A|     |R
   +-|-+      +------+    +---+-+  File d'attente-+     +---N|-----|----+
   | | |      |filtre|--->|   | |-->  . . .  -->| |     |   D|     |    |
   | | |----->|  tc  |--->|   | |   interne     | |---->|    v     |    |
   | | |      |index |--->| | | +---------------+ |   ---->(masque,valeur)|
-->| O |      +------+    +-|-+--------------^----+  /  |  (.  ,  .)    |
   | | |          ^         |                |       |  |  (.  ,  .)    |
   | | +----------|---------|----------------|-------|--+  (.  ,  .)    |
   | | sch_dsmark |         |                |       |                  |
   +-|------------|---------|----------------|-------|------------------+
     |            |         | <- tc_index -> |       |
     |            |(lecture)|   peut changer |       |  <--------------Index de la table
     |            |         |                |       |                    des couples 
     v            |         v                v       |                    (masque,valeur)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ->
                         skb->tc_index

Comment faire le marquage ? Il suffit de modifier le masque et la valeur associé à la classe que vous voulez marquer. Regarder la ligne de code suivante :

tc class change dev eth0 classid 1:1 dsmark mask 0x3 value 0xb8

Nous allons maintenant expliquer comment le filtre TC_INDEX travaille, et comment il s'intègre dans tout cela. En outre, le filtre TC_INDEX peut être utiliser dans des configurations autres que celles incluant les services DS.

Le filtre TC_INDEX

Voici la commande de base pour déclarer un filtre TC_INDEX :

... tcindex [ hash SIZE ] [ mask MASK ] [ shift SHIFT ]
            [ pass_on | fall_through ]
            [ classid CLASSID ] [ police POLICE_SPEC ]

Avant tout, supposons que nous recevons un paquet marqué comme EF. Si vous lisez le RFC2598, vous verrez que DSCP recommande une valeur de 101110 pour le trafic EF. Cela signifie que le champ DS sera égal à 10111000 (rappelez- vous que les bits les moins significatifs de l'octet TOS ne sont pas utilisés dans DS) ou 0xb8 en notation hexadécimale.

              FILTRE
              TC INDEX
   +---+      +-------+    +---+-+    +------+                +-+    +-------+
   |   |      |       |    |   | |    |FILTRE|  +-+    +-+    | |    |       |
   |   |----->| MASK  | -> |   | | -> |HANDLE|->| |    | | -> | | -> |       |
   |   |  .   | =0xfc |    |   | |    |0x2E  |  | +----+ |    | |    |       |
   |   |  .   |       |    |   | |    +------+  +--------+    | |    |       |
   |   |  .   |       |    |   | |                            | |    |       |
-->|   |  .   | SHIFT |    |   | |                            | |    |       |-->
   |   |  .   | =2    |    |   | +----------------------------+ |    |       |
   |   |      |       |    |   |       CBQ 2:0                  |    |       |
   |   |      +-------+    +---+--------------------------------+    |       |
   |   |                                                             |       |
   |   +-------------------------------------------------------------+       |
   |                          DSMARK 1:0                                     |
   +-------------------------------------------------------------------------+

Le paquet arrive alors avec la valeur du champ DS configurée à 0xb8. Comme je l'ai expliqué auparavant, le gestionnaire de mise en file d'attente dsmark, identifié par 1:0 dans cet exemple, récupère le champ DS et l'enregistre dans la variable skb->tc_index. L'étape suivante consistera à associer un filtre à ce gestionnaire de mise en file d'attente (la seconde ligne dans cet exemple). Les opérations suivantes seront réalisées :

Valeur1 = skb->tc_index & MASK
Clé = Valeur1 >> SHIFT

Dans cet exemple, MASK=0xFC et SHIFT=2.

Valeur1 = 10111000 & 11111100 = 10111000
Clé = 10111000 >> 2 = 00101110 -> 0x2E en hexadécimal

La valeur retournée correspondra à un identificateur de filtre du gestionnaire de file d'attente interne (dans l'exemple, identifier par 2:0). Si un filtre avec cet identificateur (id) existe, les conditions de contrôle et de performance seront vérifiées (au cas où le filtre inclurait ceci) et l'identificateur de classe sera retourné (dans notre exemple, classid 2:1) et stocké dans la variable skb->tc_index.

Si aucun filtre avec cet identificateur n'est trouvé, le résultat dépendra de la déclaration de l'option fall_through. Si tel est le cas, la valeur Clé est retournée comme identificateur de classe. Si cela n'est pas le cas, une erreur est retournée et le traitement continue avec les filtres restant. Faites attention si vous utilisez l'option fall_through ; ceci ne peut être fait que si une relation existe entre les valeurs de la variable skb->tc_index et les identificateurs de classe.

Les derniers paramètres à commenter sont hash et pass_on. Le premier est relié à la taille de la table de hachage. Pass_on sera utilisé pour indiquer d'essayer le filtre suivant dans le cas où aucun identificateur de classe égal au résultat du filtre ne serait trouvé. L'action par défaut est fall_through (regarder la table suivante).

Finalement, regardons quelles sont les valeurs possibles pour la configuration de tous ces paramètres TCINDEX :

Nom TC                  Valeur          Défaut
-----------------------------------------------------------------
Hash                    1...0x10000     Dépendant de l'implémentation
Mask                    0...0xffff      0xffff
Shift                   0...15          0
Fall through / Pass_on  Flag            Fall_through
Classid                 Major:minor     Rien
Police                  .....           Rien

Ce type de filtre est très puissant. Il est nécessaire d'explorer toutes les possibilités. En outre, ce filtre n'est pas seulement utilisé dans les configurations DiffServ. Vous pouvez l'utiliser comme n'importe quel autre filtre.

Je vous recommande de regarder les exemples DiffServ inclus dans la distribution iproute2. Je vous promets que j'essaierai de compléter ce texte dès que possible. Tout ce que j'ai expliqué est le résultat de nombreux tests. Merci de me dire si je me suis trompé quelque part.

14.4 Gestionnaire de mise en file d'attente d'entrée (Ingress qdisc)

Tous les gestionnaires de mise en file d'attente dont nous avons discuté jusqu'ici sont des gestionnaires de sortie. Chaque interface peut également avoir un gestionnaire de mise en file d'attente d'entrée qui n'est pas utilisé pour envoyer les paquets à l'extérieur du périphérique réseau. Au lieu de cela, il vous autorise à appliquer des filtres tc aux paquets entrants par l'interface, indépendamment de s'ils ont une destination locale ou s'ils sont destinés à être transmis.

Etant donné que les filtres tc contiennent une implémentation complète du Filter à Seau de Jetons, et qu'ils sont également capables de s'appuyer sur l'estimation du flux fourni par le noyau, il y a beaucoup de fonctionnalités disponibles. Ceci vous permet de réglementer le trafic entrant de façon efficace, avant même qu'il n'entre dans la pile IP.

Paramètres & usage

Le gestionnaire de mise en file d'attente d'entrée ne nécessite pas de paramètres. Il diffère des autres gestionnaires dans le fait qu'il n'occupe pas la racine du périphérique. Attaché le comme ceci :

# tc qdisc add dev eth0 ingress

Pour un exemple inventé sur la façon dont le gestionnaire d'entrée peut être utilisé, voir le chapitre Recettes de cuisine.

14.5 Random Early Detection (RED)

Ce chapitre est conçu comme une introduction au routage de dorsales (backbones). Ces liaisons impliquent souvent des bandes passantes supérieures à 100 mégabits/s, ce qui nécessite une approche différente de celle de votre modem ADSL à la maison.

Le comportement normal des files d'attente de routeurs est appelé "tail-drop" (NdT : élimine le reste). Le "tail-drop" consiste à mettre en file d'attente un certain volume de trafic et à éliminer tout ce qui déborde. Ce n'est pas du tout équitable et cela conduit à des retransmissions de synchronisation. Quand une retransmission de synchronisation a lieu, la brusque rafale de rejet d'un routeur qui a atteint sa limite entraînera une rafale de retransmissions retardée qui inondera à nouveau le routeur congestionné.

Dans le but d'en finir avec les congestions occasionnelles des liens, les routeurs de dorsales intègrent souvent des files d'attente de grande taille. Malheureusement, bien que ces files d'attente offrent un bon débit, elles peuvent augmenter sensiblement les temps de latence et entraîner un comportement très saccadé des connexions TCP pendant la congestion.

Ces problèmes avec le "tail-drop" deviennent de plus en plus préoccupants avec l'augmentation de l'utilisation d'applications hostiles au réseau. Le noyau Linux nous offre la technique RED, abréviation de Random Early Detect ou détection précoce directe.

RED n'est pas la solution miracle à tous ces problèmes. Les applications qui n'intègrent pas correctement la technique de "l'exponential backoff" obtiennent toujours une part trop grande de bande passante. Cependant, avec la technique RED elles ne provoquent pas trop de dégâts sur le débit et les temps de latence des autres connexions.

RED élimine statistiquement des paquets du flux avant qu'il n'atteigne sa limite "dure" (hard). Sur une dorsale congestionnée, cela entraîne un ralentissement en douceur de la liaison et évite les retransmissions de synchronisation. La technique RED aide aussi TCP à trouver une vitesse "équitable" plus rapidement : en permettant d'éliminer des paquets plus tôt, il conserve une file d'attente plus courte et des temps de latence mieux contrôlés. La probabilité qu'un paquet soit éliminé d'une connexion particulière est proportionnelle à la bande passante utilisée par cette connexion plutôt qu'au nombre de paquets qu'elle envoie.

La technique RED est une bonne gestion de file d'attente pour les dorsales, où vous ne pouvez pas vous permettre le coût d'une mémorisation d'état par session qui est nécessaire pour une mise en file d'attente vraiment équitable.

Pour utiliser RED, vous devez régler trois paramètres : Min, Max et burst. Min est la taille minimum de la file d'attente en octets avant que les rejets n'aient lieu, Max est le maximum "doux" (soft) en-dessous duquel l'algorithme s'efforcera de rester, et burst est le nombre maximum de paquets envoyés "en rafale".

Vous devriez configurer Min en calculant le plus grand temps de latence acceptable pour la mise en file d'attente, multiplié par votre bande passante. Par exemple, sur mon lien ISDN à 64 Kbits/s, je voudrais avoir un temps de latence de base de mise en file d'attente de 200 ms. Je configure donc Min à 1600 octets (= 0,2 x 64000 / 8). Imposer une valeur Min trop petite va dégrader le débit et une valeur Min trop grande va dégrader le temps de latence. Sur une liaison lente, choisir un coefficient Min petit ne peut pas remplacer une réduction du MTU pour améliorer les temps de réponse.

Vous devriez configurer Max à au moins deux fois Min pour éviter les synchronisations. Sur des liens lents avec de petites valeurs de Min, il peut être prudent d'avoir Max quatre fois plus grand que Min ou plus.

Burst contrôle la réponse de l'algorithme RED aux rafales. Burst doit être choisi plus grand que min/avpkt (paquet moyen). Expérimentalement, j'ai trouvé que (min+min+max)/(3*avpkt) marche bien.

De plus, vous devez configurer limit et avpkt. Limit est une valeur de sécurité : s'il y a plus de Limit octets dans la file, RED reprend la technique "tail-drop". Je choisis une valeur typique égale à 8 fois Max. Avpkt devrait être fixé à la taille moyenne d'un paquet. 1000 fonctionne correctement sur des liaisons Internet haut débit ayant un MTU de 1500 octets.

Lire the paper on RED queueing par Sally Floyd et Van Jacobson pour les informations techniques.

14.6 Generic Random Early Detection

Il n'y a pas grand chose de connu sur GRED. Il ressemble à GRED avec plusieurs files d'attente internes, celles-ci étant choisies en se basant sur le champ tcindex de Diffserv. Selon une diapositive trouvée ici, il possède les capacités 'Distributed Weighted RED' de Cisco, ainsi que les capacités RIO de Clark.

Chaque file d'attente virtuelle peut avoir ses propres "Drop Parameters".

FIXME: Demandez à Jamal or Werner de nous en dire plus

14.7 émulation VC/ATM

Ceci est l'effort principal de Werner Almesberger pour vous autoriser à construire des circuits virtuels au-dessus des sockets TCP/IP. Le circuit virtuel est un concept venant de la théorie des réseaux ATM.

Pour plus d'informations, voir la page ATM sur Linux.

14.8 Weighted Round Robin (WRR)

Ce gestionnaire de mise en file d'attente n'est pas inclus dans les noyaux standard, mais peut être téléchargée à partir de http://wipl-wrr.dkik.dk/wrr/. Ce gestionnaire de mise en file d'attente n'a été testé qu'avec les noyaux 2.2, mais marchera probablement également avec les noyaux 2.4/2.5.

La file d'attente WRR partage la bande passante entre ses classes en utilisant la technique du tourniquet pondéré. Ceci est similaire à la file d'attente CBQ qui contient des classes sur lesquelles l'on peut associer arbitrairement des files d'attente. Toutes les classes qui ont suffisamment de demandes obtiendront la bande passante proportionnellement au poids associé des classes. Les poidss peuvent être configurés manuellement en utilisant le programme tc. Ils peuvent également être configurés pour décroître automatiquement pour les classes transférant moins de données.

La file d'attente a un classificateur intégré qui assigne les paquets venant ou allant vers différentes machines à différentes classes. On peut utiliser soit l'adresse MAC soit l'adresse IP de l'adresse source ou de destination. L'adresse MAC ne peut cependant être utilisée que quand la boite Linux est un pont ethernet. Les classes sont automatiquement assignées aux machines en fonction des paquets vus.

Ce gestionnaire de mise en file d'attente peut être très utile au site comme les résidences étudiantes où des individus sans liens particuliers partagent une connexion Internet. Un ensemble de scripts pour configurer un tel cas de figure pour ce genre de site est proposé dans la distribution WRR.