Noyau Linux 3.5 : réduction de la latence réseau en charge

Byte queue limits

La nouvelle infrastructure de « byte queue limits » est entrée dans le nouveau noyau Linux 3.3. Elle vise à combattre les problèmes de latence causés par l'engorgement des paquets réseau.

Tout a commencé avec une alerte lancée en décembre 2010 par Jim Gettys. Pour ceux qui ne connaîtraient pas ce programmeur il s'agit d'un des développeurs originels de l'environnement X Window System au MIT (récipiendaire du USENIX Lifetime Achievement Award) et il a travaillé au W3C en endossant le rôle d'éditeur de la spécification HTTP/1.1 auprès de l'Internet Engineering Task Force. Autrement dit, c'est quelqu'un qu'on écoute quand il signale un problème !

Il y a quelques années, alors qu'il était chercheur dans les Bell Labs d'Alcatel-Lucent, Jim Gettys a découvert un problème d'engorgement réseau d'un nouveau type qu'il a nommé « bufferbloat ». Selon ses tests, le fait d'avoir des tampons mémoires (buffer) de taille excessive conduit à une latence généralisée dans les réseaux. Ce problème est resté inaperçu lors des phases de conception des différentes architectures réseau et la baisse du coût de la mémoire n'a fait que l'aggraver, puisque les ingénieurs ajoutent des tampons mémoire à tire-larigot sans penser aux conséquences.
Tout cela vient du fait que les protocoles se basent sur l'idée qu'une congestion va être détectée automatiquement parce que les paquets réseaux ne seront plus traités. Les algorithmes de gestion de la congestion se servent de ce nombre de paquets perdus (dropped) et c'est comme ça que le réseau s'auto-régule en signalant aux divers èmetteurs que le lien est saturé et qu'il faut réduire le débit d'envoi de paquets.
Dans le monde réel, le chemin que parcourt un paquet réseau d'un point A vers un point B est bourré de tampons mémoires en cascade à toutes les étapes. On en trouve dans les piles réseaux des OS, dans les pilotes réseaux eux-mêmes et dans tous les routeurs et serveurs intermédiaires sur le chemin. Et puis, toujours à cause du prix ridicule de la RAM, la situation tend à s'aggraver et les systèmes d'exploitation sont conçus pour gérer des tampons réseaux de plus en plus dèmesurés.
La conséquence, c'est que l'abandon des paquets en cas de saturation (packet dropping) ne se fait plus immédiatement. Il faut d'abord que le tampon se vide avant que le mécanisme de rétroaction s'enclenche et ce délai perturbe les algorithmes de gestion de la congestion :
Les algorithmes de gestion de la congestion dépendent de l'abandon des paquets réseau juste au bon moment. Le fait d'avoir des tampons saturés invalide ce présupposé architectural.

Après avoir découvert ce mécanisme diabolique d'amplification des latences, Jim Gettys a décidé de partir à l'assaut, flamberge au vent, et il consacre désormais tout son temps à informer les gens et à tenter de trouver des solutions. Cela s'est traduit par une masse impressionnante de posts sur son blog, d'articles officiels, de conférences, d'entretiens, d'entretiens croisés avec des sommités. Un site web spécifique a été mis en place, des vidéos démontrant le problème ont été réalisées.

Cette débauche d'énergie est nécessaire parce que le problème est grave, parce que les algorithmes qui existent, comme RED, ne sont pas efficaces et surtout parce qu'il faudra la coopération de tous les acteurs pour le résoudre. Comme chaque relais sur un chemin réseau est susceptible d'aggraver la latence, il faudra corriger les différentes couches de traitement de tous les systèmes d'exploitation de tous ces routeurs et serveurs !

La solution qui a été retenue pour Linux est un nouveau mécanisme de « byte queue limits ». Comme son nom l'indique, il s'agit de gérer une queue réseau en se basant sur la taille en octet (byte) plutôt que de se baser sur le nombre de paquets.
Évidemment, on ne pouvait pas vraiment se passer de la mise en tampon du flux réseau dans une queue d'attente. Si les développeurs avaient fait ça, le remède aurait été pire que le mal et les performances se serait effondrées car il y aurait eu pénurie de données à traiter (starvation). Les développeurs ont donc choisi d'avoir une queue d'attente dynamique en fonction de la charge de la machine. Cette infrastructure se compose de deux modules :
- La bibliothèque DQL (Dynamic Queue Limits) qui gère le caractère adaptatif d'une queue d'attente. Il s'agit d'un mécanisme très générique qui n'est pas spécialement dédié au réseau.
- Le mécanisme BQL (Byte Queue Limits) qui s'appuie sur la bibliothèque DQL pour implèmenter la gestion dynamique du flux réseau en fonction de la taille mémoire.

Tom Herbert, l'ingénieur Google à l'origine de ces patchs, s'est aperçu qu'il était bien plus facile d'estimer le temps de vidage d'un tampon si on se basait sur la taille mémoire plutôt que sur le nombre de paquets :
    The amount of queuing required to prevent starvation of the transmitter is much more dependent on the serialization time of the bytes as opposed to the number of packets being transmitted.

Ce mécanisme dynamique est réglé de façon à ce que le tampon ne contienne que le strict minimum de données pour éviter la pénurie. Si une situation de famine (starvation) est détectée, alors c'est que le tampon de gestion était trop petit et il est donc agrandi. En revanche, si le nombre d'octets du tampon ne descend jamais sous une certaine limite, alors cela veut dire qu'il est possible de diminuer le tampon d'autant.
Ainsi, on conserve les performances tout en réduisant au maximum les latences de type « bufferbloat ».

Tom Herbert a effectué de nombreux tests qui sont résumés dans son message sur la liste de diffusion linux-netdev. Voici par exemple les résultats d'un test netperf ayant lancé 100 flux TCP_STREAM pour saturer le lien et un flux TCP_RR en haute priorité.
- Sans BQL: 453-454 Ko dans la queue et 234 transactions par seconde pour le test TCP_RR.
- Avec BQL: 66 Ko dans la queue et 914 transactions par seconde pour le test TCP_RR.

Avec cette infrastructure de « byte queue limits », le noyau Linux 3.3 semble donc bien armé pour combattre la redoutable hydre découverte par Jim Gettys et qui hante nos réseaux. Toutefois, il serait dangereux de crier victoire trop tôt et il faut bien rester conscient des problèmes qui subsistent.
Tout d'abord, cette infrastructure est toute nouvelle et, en dépit des benchmarks, il faudra vérifier sur le terrain qu'elle est effectivement capable de réduire les latences. Le problème des réseaux sans fil 802.11 est particulièrement complexe, avec son partage de bande passante entre différents acteurs, et il est probable qu'il faudra encore travailler pour résoudre complètement le problème.

Ensuite, il faut bien voir que ce mécanisme DQL/BQL constitue un changement dans l'API des pilotes réseau Linux et que cela signifie qu'il faudra adapter tous ces pilotes pour qu'ils puissent exploiter cette infrastructure. Certes, dans le monde du logiciel libre, et avec les pilotes incorporés nativement dans le noyau, ce n'est pas un très gros inconvénient… mais il faudra faire ce travail !
Pour l'instant, seuls les pilotes bnx2x, forcedeth, e1000e, tg3 et sfc ont été adaptés.

Enfin, problème bien plus grave, le mécanisme développé par les hackers Linux ne concerne que notre noyau préféré !
Certes, une solution adaptée aux routeurs personnels est en cours de construction (Cerowrt) mais quid de toutes les autres machines présentes sur Internet ? Puisque tous les systèmes d’exploitation, tous les routeurs et tous les serveurs sont à modifier, il faudra une coopération globale des constructeurs, des communautés développant les autres OS libres et aussi des éditeurs commerciaux d’OS (Cisco, Microsoft, Apple, Oracle, etc.).
Dans l’entretien entre Jim Gettys et Vinton Cerf, ce dernier évoque une situation qui s’apparente au dilemme du prisonnier :

Tant que tout le monde ne coopère pas pour réduire les tampons mémoires partout où ils se trouvent, alors la bonne stratégie est, pour chaque constructeur, d'accroître la taille de ses tampons. Vous pouvez rendre plus rapide votre routeur WiFi en lui ajoutant de la mémoire tampon.

Si Vinton Cerf a raison et que chacun des acteurs trouve un intérêt égoïste à accroître encore plus la taille des buffers de ses machines pour avoir des performances supérieures, alors on peut vraiment s'inquiéter du « bufferbloat ».
La coopération et le sens de l'intérêt général pourront-ils s'opposer à cette tendance ?
Source : LinuxFR, le 19 mars 2012 par  patrick_g.


Algorithme CoDel

L'algorithme CoDel a été intégré dans le noyau Linux 3.5. Il constitue une réponse partielle au fameux problème du « bufferbloat » décrit dans la dépêche du noyau 3.3.
Pour résumer, il s'agit de changer le comportement de TCP afin d'éviter l'engorgement des buffers (les mémoires tampons) : quand un buffer est trop rempli par un fichier à envoyer (par exemple), les requêtes interactives (Web, SSH, etc.) sont ralenties car traitées après, il y a donc un équilibre à trouver dans le remplissage des buffers pour être efficace sans augmenter trop la latence..
Les algorithmes actuels utilisés dans TCP sur-utilisent ces buffers ce qui pénalise la latence : CoDel devrait corriger cela.
Notons quand même que tous les buffers induisent de la latence : ceux de l'application, de la pile TCP, de la carte réseau, de la box internet, des routeurs du FAI, etc., une modification de Linux est donc nécessaire mais pas forcèment suffisante…
Source : LinuxFR, le 22 juillet 2012 par  patrick_g.

Là on ne parle pas de la latence à vide que tu obtiens en réalisant un ping mais de la latence quand tu as déjà des connexions qui utilisent ta connexion à 100%.

Un exemple : télécharger un gros fichier et surfer en parallèle (ou pire utiliser une connexion SSH distante)

Le téléchargement va remplir des buffers. Le ping va monter à plusieurs centaines de ms et les connexions qui ont besoin d'un faible ping et qui utilisent peu de débit (comme une connexion SSH ou un surf web) vont être fortement impactées.

Pour s'en rendre compte, il suffit de télécharger deux gros fichiers (par exemple http://1.testdebit.info/fichiers/1000Mo.dat et http://bouygues.testdebit.info/fichiers/1000Mo.dat) et de faire en même temps un simple ping. Dès que le téléchargement commence le ping s'envole à cause de ces buffers.

Voici un exemple pour illustrer mon propos avec une bonne ligne ADSL (synchronisation à 22 Mb/s).

- Les paquets ICMP 1 à 12 sont à vide (ping de 21ms).
- Les paquets ICMP 12 à 24 sont avec un téléchargement d'un fichier en parallèle (ping de 60 à 70ms)

$ ping testdebit.info
PING testdebit.info (89.84.127.55) 56(84) bytes of data.
64 bytes from 89.84.127.55: icmp_req=1 ttl=58 time=21.6 ms
64 bytes from 89.84.127.55: icmp_req=2 ttl=58 time=21.2 ms
64 bytes from 89.84.127.55: icmp_req=3 ttl=58 time=21.1 ms
64 bytes from 89.84.127.55: icmp_req=4 ttl=58 time=21.1 ms
64 bytes from 89.84.127.55: icmp_req=5 ttl=58 time=20.9 ms
64 bytes from 89.84.127.55: icmp_req=6 ttl=58 time=20.7 ms
64 bytes from 89.84.127.55: icmp_req=7 ttl=58 time=21.7 ms
64 bytes from 89.84.127.55: icmp_req=8 ttl=58 time=20.8 ms
64 bytes from 89.84.127.55: icmp_req=9 ttl=58 time=21.2 ms
64 bytes from 89.84.127.55: icmp_req=10 ttl=58 time=20.7 ms
64 bytes from 89.84.127.55: icmp_req=11 ttl=58 time=21.5 ms
64 bytes from 89.84.127.55: icmp_req=12 ttl=58 time=21.6 ms
64 bytes from 89.84.127.55: icmp_req=13 ttl=58 time=70.8 ms
64 bytes from 89.84.127.55: icmp_req=14 ttl=58 time=62.5 ms
64 bytes from 89.84.127.55: icmp_req=15 ttl=58 time=61.6 ms
64 bytes from 89.84.127.55: icmp_req=16 ttl=58 time=51.4 ms
64 bytes from 89.84.127.55: icmp_req=17 ttl=58 time=60.7 ms
64 bytes from 89.84.127.55: icmp_req=18 ttl=58 time=72.7 ms
64 bytes from 89.84.127.55: icmp_req=19 ttl=58 time=70.4 ms
64 bytes from 89.84.127.55: icmp_req=20 ttl=58 time=71.2 ms
64 bytes from 89.84.127.55: icmp_req=21 ttl=58 time=69.3 ms
64 bytes from 89.84.127.55: icmp_req=22 ttl=58 time=69.3 ms

Environnement utilisé : Linux Ubuntu 12.04 64bits + Firefox 14.
Le téléchargement est fait en http (une seule connexion TCP) et en IPv4

Pour moi si tu fais un ping a vide, tu n'a pas de buffers. Si on exclu l'interleave, la latence est surtout fonction du nombre de km de fibre.

Pour le mobile, certains pourront en parler mieux quoi moi mais tu as différents niveau de réservation de ressources radio.

Il me semble (je ne suis pas sur) DCH (Dedicated Channel), FACH (Forward access channel), PCH (Cell Paging channel) et PCH (URA Paging channel).

Faible ressource radio = ping important et petit débit.

L'astuce pour réduire le ping en 3G quand on a besoin d'un bon ping (par exemple en SSH) est de laisser la connexion ouverte via un ping.

Pour l'instant aucune distribution n'utilise ce noyau.

Je ferais les tests lors de la sortie des premières distribution utilisant ce noyau en octobre prochain.

Ah d'accord.
Bon va falloir que je test de mon cote alors.

Le noyau est dispo dans Gentoo