Progression des performances de la table de routage IPv4 sous Linux

Vincent Bernat

En bref : Linux 2.6.39, 3.6 et 4.0 apportent un progrès notable sur les performances de la table de routage IPv4.


Dans un précédent article, j’expliquais comment Linux stockait les routes dans un arbre compressé pour obtenir d’excellents résultats sur les temps de recherche. Le graphique suivant montre la progression des performances à travers les époques :

Performance de la table de routage IPv4
Temps de recherche d'une route pour diverses versions du noyau Linux. La table de routage contient 500 000 routes. Les versions mises en valeur apportent un gain notable.

Deux scénarios sont testés :

  • 500 000 routes extraites d’un routeur Internet (la moitié étant des /24)
  • 500 000 routes /32 réparties consécutivement dans 4 sous-réseaux distincts

Tous les noyaux sont compilés avec GCC 4.9 (issu de Debian Jessie). Cette version est compatible avec des noyaux antiques1 ainsi qu’avec les noyaux les plus récents. La configuration du noyau utilisée est celle par défaut avec les options CONFIG_SMP et CONFIG_IP_MULTIPLE_TABLES activées (sans toutefois utiliser de règles de routage). D’autres options mineures sont activées pour permettre de prendre les mesures.

Le banc d’essai se déroule dans une machine virtuelle utilisant un seul vCPU2. Le CPU hôte est un Intel Core i5-4670K et le gouverneur CPU est configuré en mode « performance ». Les mesures sont faites par un module noyau appelant la fonction fib_lookup() en boucle en variant les destinations. Le chronométrage de chacune des 100 000 itérations est effectuée par la TSC et convertie en nanosecondes en se basant sur une fréquence d’horloge arbitraire. La valeur médiane est retenue.

Quelques noyaux apportent un progrès notable :

  • Avec Linux 2.6.39, commit 3630b7c050d9, David Miller retire l’implémentation basée sur des tables de hachage pour utiliser des arbres compressés (disponible sous forme d’option à la compilation depuis Linux 2.6.13). Cela provoque une légère régression dans le cas des routes en /32 mais améliore grandement les performances dans le cas général.

  • Avec Linux 3.0, commit 281dc5c5ec0f, l’amélioration n’est pas liée à un changement dans le sous-système réseau. Linus Torvalds a désactivé l’optimisation en taille qui était utilisée par défaut. Cette option devait permettre de rendre le cache des instructions plus efficace mais les compilateurs généraient cependant un code plus lent sur x86.

  • Avec Linux 3.6, commit f4530fa574df, David Miller ajoute une optimisation destinée à ne plus évaluer les règles de routage quand elles n’ont pas été modifiées. À partir de cette version, l’option CONFIG_IP_MULTIPLE_TABLES ne dégrade plus les performances à moins de configurer explicitement des règles de routage. Cette version retire également le cache des routes (commit 5e9965c15ba8). Toutefois, cela n’a pas d’effet sur les mesures car l’appel direct à fib_lookup() contourne ce cache.

  • Avec Linux 4.0, notamment le commit 9f9e636d4f89, Alexander Duyck réorganise l’algorithme de recherche des routes pour en augmenter les performances. Le résultat est probant !

  • Avec Linux 4.1, commit 0ddcf43d5d4a, Alexander Duyck fusionne les tables local et main quand aucune règle de routage n’est utilisée. Pour le trafic non local, ces deux tables étaient successivement consultées.


  1. Certains anciens noyaux ne compilent plus avec les outils actuels à moins d’appliquer de petits correctifs

  2. Les noyaux sont toutefois compilés avec l’option CONFIG_SMP pour activer le mécanisme RCU hiérarchique afin de suivre des chemins de code similaires aux routeurs multi-cœurs. Toutefois, tout progrès sur le parallélisme passe inaperçu. 


Partager cet article

Le système de commentaire utilisé sur ce site est Disqus. Il nécessite l’usage de Javascript. Merci d’activer Javascript ou d’essayer avec un navigateur différent.

💬 Vous pouvez consulter ou publier des commentaires. Le système de discussion est animé par Disqus et requiert l’utilisation de cookies.