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.

Mise à jour à mi-2018#

Voici un graphique pour des noyaux plus récents. Les performances sont plutôt stables. Les recherches sont mesurées par lot de cinq pour réduire les coûts. Les petites régressions des versions 4.2 et 4.16 peuvent ou non être significatives (une variation de 5 ns correspond à une recherche dans le cache de niveau 2).

Performance de la table de routage IPv4 sur des noyaux récents
Temps de recherche d'une route pour diverses versions du noyau Linux. La table de routage contient 500 000 routes. Les zones ombragées représentent l'écart absolu médian.

Les récentes vulnérabilités Meltdown et Spectre ont défrayé la chronique en raison de l’impact sur les performances des correctifs. La recherche d’une route s’effectuant intégralement dans le noyau, les correctifs devraient n’avoir aucun effet, comme confirmé sur les graphiques ci-dessous:

IPv4 route lookup performance with kernels around the Meltdown/Spectre era
Temps de recherche d'une route pour des versions du noyau Linux fin 2017 et début 2018. La table de routage contient 500 000 routes. Les noyaux sont ordonnés par leur date de publication. La zone ombragée contient les noyaux sans correctifs pour Spectre et Meltdown.
IPv4 route lookup performance with kernels around the Meltdown/Spectre era
Graphique similaire au précédent mais les noyaux sont ordonnés par version.

Les mesures ont été faites sur une machine virtuelle avec un seul vCPU. L’hôte est un Intel Core i5-4670K (micro-architecture Haswell) tournant à 3,4 GHz avec un microcode à jour et un noyau 4.16 de Debian. Lorsqu’il est protégé, l’hôte utilise PTI, retpoline et IBPB. Dans le cas contraire, l’hôte tourne avec un ancien microcode et les protections sont désactivées au niveau de la ligne de commande (nopti nospectre_v2). Les noyaux pour la machine virtuelle sont compilés avec GCC 7.3 qui inclus le support de retpoline.


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

  2. Les noyaux sont cependant 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. ↩︎