Fonctionnement de la table de routage IPv6 sous Linux

Vincent Bernat

En bref

Li­nux stocke les tables de rou­tage IPv6 à l’aide d’arbres ra­dix. Les per­for­mances ob­te­nues (450 ns pour une vue com­plète d’In­ter­net — 40 000 routes) sont in­fé­rieures à IPv4 (50 ns pour une vue com­plète — 500 000 routes) mais l’uti­li­sa­tion mé­moire reste hon­nête (20 Mio pour la vue complète).

Pré­cé­dem­ment, nous avions re­gardé com­ment fonc­tion­nait la table de rou­tage IPv4 sous Li­nux. Qu’en est-il de l’im­plé­men­ta­tion pour IPv6 ?

Arbre de recherche#

Cher­cher un pré­fixe dans une table de rou­tage re­vient à trou­ver l’en­trée la plus spé­ci­fique cor­res­pon­dant à la des­ti­na­tion sou­hai­tée. Une struc­ture cou­rante pour cette tâche est le trie, un arbre de re­cherche pour le­quel chaque nœud est pré­fixé par son père.

Pour IPv4, Li­nux uti­lise un arbre dou­ble­ment com­pressé (ap­pelé LPC-trie), of­frant de bonnes per­for­mances avec un usage mé­moire faible. Pour IPv6, Li­nux em­ploie le plus clas­sique arbre ra­dix (en­core ap­pelé trie Pa­tri­cia). Il y a trois rai­sons pour ne pas avoir re­cy­clé la so­lu­tion uti­li­sée pour IPv4 :

  • L’im­plé­men­ta­tion IPv6 (in­tro­duite dans Li­nux 2.1.8, 1996) est an­té­rieure à celle pour IPv4 qui date de Li­nux 2.6.13 (com­mit 19baf839ff4a).
  • Les fonc­tion­na­li­tés of­fertes sont dif­fé­rentes. No­tam­ment, IPv6 in­tègre la pos­si­bi­lité d’un rou­tage par l’adresse source1 (de­puis Li­nux 2.1.120, 1998).
  • L’es­pace d’adres­sage IPv4 est beau­coup plus dense que ce­lui d’IPv6, ce qui rend la com­pres­sion par ni­veau du trie par­ti­cu­liè­re­ment efficace.

À titre d’exemple, l’illus­tra­tion ci-des­sous montre un arbre ra­dix co­dant 6 préfixes :

Arbre radix
Arbre radix pour une petite table de routage. Certains nœuds indiquent le nombre de bits supplémentaires à ignorer en entrée. Les nœuds en noir contiennent une entrée.

Pour des ex­pli­ca­tions plus dé­taillées sur les dif­fé­rents co­dages pos­sibles d’une table de rou­tage et des éclair­cis­se­ments sur les arbres ra­dix, je­tez un œil sur les ex­pli­ca­tions pour IPv4.

La fi­gure ci-des­sous montre la re­pré­sen­ta­tion en mé­moire de l’arbre ra­dix pré­cé­dent. Chaque nœud cor­res­pond à une struc­ture fib6_​node. Quand un nœud a le dra­peau RTN_​RTINFO, il contient un poin­teur vers une struc­ture rt6_​info conte­nant des in­for­ma­tions sur le pro­chain saut.

Représentation mémoire d'une table de routage
Représentation mémoire d’une table de routage IPv6 sous Linux. Certains champs ont été omis. Le préfixe 2001:db8:2::/121 est une route ECMP. Quand plusieurs routes sont disponibles pour un préfixe donné, elles sont chaînées via le champ dst (non représenté).

La fonc­tion fib6_​lookup_​1() par­court l’arbre ra­dix en deux étapes :

  1. par­cours des­cen­dant pour lo­ca­li­ser un can­di­dat po­tentiel ;
  2. vé­ri­fi­ca­tion de la va­li­dité du can­di­dat et re­cherche en ar­rière si besoin.

Voici une ver­sion lé­gè­re­ment sim­pli­fiée (sans rou­tage par la source) :

static struct fib6_node *fib6_lookup_1(struct fib6_node *root,
                                       struct in6_addr  *addr)
{
    struct fib6_node *fn;
    __be32 dir;

    /* Step 1: locate potential candidate */
    fn = root;
    for (;;) {
        struct fib6_node *next;
        dir = addr_bit_set(addr, fn->fn_bit);
        next = dir ? fn->right : fn->left;
        if (next) {
            fn = next;
            continue;
        }
        break;
    }

    /* Step 2: check prefix and backtrack if needed */
    while (fn) {
        if (fn->fn_flags & RTN_RTINFO) {
            struct rt6key *key;
            key = fn->leaf->rt6i_dst;
            if (ipv6_prefix_equal(&key->addr, addr, key->plen)) {
                if (fn->fn_flags & RTN_RTINFO)
                    return fn;
            }
        }

        if (fn->fn_flags & RTN_ROOT)
            break;
        fn = fn->parent;
    }

    return NULL;
}

Mise en cache#

Alors qu’IPv4 a perdu son cache dans Li­nux 3.6 (com­mit 5e9965c15ba8), IPv6 dis­pose tou­jours de ce mé­ca­nisme. Tou­te­fois, les en­trées sont pla­cées di­rec­te­ment dans l’arbre ra­dix avec le dra­peau RTF_​CACHE et non dans une struc­ture distincte.

De­puis Li­nux 2.1.30 (1997) et jusqu’à Li­nux 4.2 (com­mit 45e4fd26683c), qua­si­ment toutes les re­cherches abou­tis­saient à la créa­tion d’une en­trée dans le cache. Par exemple, un rou­teur voyant tran­si­ter un ping entre 2001:​db8:1::1 et 2001:​db8:3::1 en crée deux :

$ ip -6 route show cache
2001:db8:1::1 dev r2-r1  metric 0
    cache
2001:db8:3::1 via 2001:db8:2::2 dev r2-r3  metric 0
    cache

La fonc­tion ip6_​dst_​gc() as­sure le net­toyage du cache avec les pa­ra­mètres suivants :

$ sysctl -a | grep -F net.ipv6.route
net.ipv6.route.gc_elasticity = 9
net.ipv6.route.gc_interval = 30
net.ipv6.route.gc_min_interval = 0
net.ipv6.route.gc_min_interval_ms = 500
net.ipv6.route.gc_thresh = 1024
net.ipv6.route.gc_timeout = 60
net.ipv6.route.max_size = 4096
net.ipv6.route.mtu_expires = 600

Le ra­masse-miette est ac­tivé au plus toutes les 500 ms lorsqu’il y a plus de 1024 en­trées dans le cache ou au moins toutes les 30 se­condes. Il ne tourne pas plus de 60 se­condes, sauf s’il y a plus de 4096 en­trées. Lorsqu’il tourne, il va d’abord ef­fa­cer les en­trées vieilles de plus de 30 se­condes. Tant que le nombre d’en­trées reste su­pé­rieur à 4096, il conti­nue d’ef­fa­cer les en­trées de plus en plus ré­centes (mais pas plus ré­centes que 512 jif­fies qui cor­res­pond à la va­leur de gc_​elasticity) avec une pause de 500 ms entre chaque passage.

De­puis Li­nux 4.2 (com­mit 45e4fd26683c), seules les ex­cep­tions PMTU pro­voquent la créa­tion d’une en­trée dans le cache. Un rou­teur ne gè­rant pas ces ex­cep­tions, seuls les hôtes au­ront (ra­re­ment) des en­trées dans le cache2. Mar­tin KaFai Lau, de Fa­ce­book, explique:

De toutes les routes IPv6 de type RTF_​CACHE qui sont créées, le pour­cen­tage qui a un MTU dif­fé­rent est très faible. Sur l’un de nos ser­veurs man­da­taires face à des uti­li­sa­teurs fi­naux, seule­ment 1000 en­trées sur 80 000 ont un MTU plus faible. En ce qui concerne le tra­fic dans notre DC, il n’y a pas d’ex­cep­tion MTU.

Voici à quoi res­semble une en­trée dans le cache avec une ex­cep­tion PMTU :

$ ip -6 route show cache
2001:db8:1::50 via 2001:db8:1::13 dev out6  metric 0
    cache  expires 573sec mtu 1400 pref medium

Performance#

Trois scé­na­rios dif­fé­rents sont étudiés :

Ex­trait d’une vue com­plète d’In­ter­net
Dans ce scé­na­rio, Li­nux se com­porte comme un rou­teur connecté à plu­sieurs tran­si­taires et dis­po­sant d’une vue « com­plète ». Ac­tuel­le­ment, la taille d’une telle table de rou­tage est lé­gè­re­ment su­pé­rieure à 40 000 routes.
Pré­fixes /48 sau­pou­drés li­néai­re­ment avec dif­fé­rentes den­si­tés
Li­nux agit comme un rou­teur au cœur d’un da­ta­centre. Chaque client ou baie ob­tient un ou plu­sieurs sous-ré­seau /48 qu’il convient d’ai­guiller. Avec une den­sité de 1, les /48 sont contigus.
Pré­fixes /128 ré­par­tis aléa­toi­re­ments dans un /108
Li­nux se com­porte comme un rou­teur d’ac­cès pour un ré­seau /64 dans le­quel les hôtes ob­tiennent leur IP par auto-confi­gu­ra­tion. Si tous les hôtes par­tagent le même OUI, les 40 pre­miers bits sont fixes. Dans ce scé­na­rio, la table des voi­sins est conver­tie en routes par un pro­ces­sus ex­terne et re­dis­tri­bué au­près des autres rou­teurs ser­vant le même sous-réseau3.

Performance de la recherche#

À l’aide d’un mo­dule noyau, il est pos­sible de me­su­rer pré­ci­sé­ment le temps d’exé­cu­tion4 de la fonc­tion ip6_​route_​output_​flags():

Profondeur maximale et temps de recherche
Profondeur maximale de l’arbre radix et temps de recherche en fonction du nombre de routes. L’axe horizontal utilise une échelle logarithmique. Les barres d’erreur représentent l’écart médian absolu.

Ob­te­nir des ré­sul­tats sa­tis­fai­sants s’avère com­plexe en rai­son de la taille de l’es­pace d’adres­sage. Au­cun des scé­na­rios ne dis­pose d’une route par dé­faut et les me­sures ne sont conser­vées que lorsque la re­cherche abou­tit à une so­lu­tion5. Pour le scé­na­rio avec la vue com­plète, seules les adresses de 2400::/16 à 2a06::/16 sont uti­li­sées (cela com­prend plus de la moi­tié des routes). Pour le scé­na­rio avec les pré­fixes /128, l’in­té­gra­lité du sous-ré­seau /108 est ba­layé. Pour le scé­na­rio avec les /48, le ba­layage est ef­fec­tué de­puis le pre­mier /48 jusqu’au der­nier. Pour chaque pas­sage, 5000 adresses sont prises semi-aléa­toi­re­ment. De nou­veaux pas­sages sont ef­fec­tués jusqu’à at­teindre 5000 re­cherches réus­sies ou 1 mil­lion de re­cherches au total.

La re­la­tion entre la pro­fon­deur maxi­male de l’arbre et le temps de re­cherche est par­tielle. Il m’est dif­fi­cile d’ex­pli­quer la dif­fé­rence de per­for­mance entre les dif­fé­rentes den­si­tés du scé­na­rio en /48.

On peut tou­te­fois ob­ser­ver deux points im­portants :

  • Avec une vue com­plète, le temps de re­cherche mé­dian est de 450 ns. C’est en­vi­ron 10 fois le bud­get pour ex­pé­dier des pa­quets à 10 Gbps (en­vi­ron 50 ns).
  • Avec une table de rou­tage presque vide, le temps de re­cherche est de 150 ns. C’est en­core au-des­sus du bud­get pour une connexion à 10 Gbps.

Avec IPv4, le temps de re­cherche sur une table presque vide était d’en­vi­ron 20 ns tan­dis qu’avec une vue com­plète (500 000 routes), il est d’en­vi­ron 50 ns. Com­ment ex­pli­quer une telle dif­fé­rence ? Tout d’abord, la pro­fon­deur de l’arbre com­pressé en IPv4 est très faible (6 pour 500 000 routes) tan­dis que la pro­fon­deur de l’arbre ra­dix avec 40 000 routes est d’en­viron 40.

Deuxiè­me­ment, bien que la fonc­tion fib_​lookup() pour IPv4 et la fonc­tion ip6_​route_​output_​flags() pour IPv6 ont des coûts fixes liés à l’éva­lua­tion des règles de rou­tage, IPv4 dis­pose de plu­sieurs op­ti­mi­sa­tions quand ces règles de rou­tage n’ont pas été mo­di­fiées6. Ces op­ti­mi­sa­tions sont re­ti­rées au pre­mier chan­ge­ment. Dans ce cas, IPv4 est im­pacté de 30 ns. Cela laisse en­core un désa­van­tage de 100 ns pour IPv6.

Re­gar­dons où le temps CPU est dé­pensé pour cha­cune des deux fonc­tions. Voici un gra­phique de type flame graph pour la fonc­tion IPv4 fib_​lookup() :

🖼 Graphique flamegraph pour la recherche de routes en IPv4
Répartition par fonctions du temps CPU dépensé lors de la recherche d’une route IPv4. Les tables main et local sont séparées et les règles de routage sont évaluées. L’axe horizontal est le temps total écoulé (65 ns). Le graphique est interactif.

Seule­ment la moi­tié du temps est dé­pensé dans le par­cours d’arbre via la fonc­tion fib_​table_​lookup(). Il convient de no­ter que cette fonc­tion est en réa­lité exé­cu­tée deux fois : une fois pour la table lo­cal et une fois pour la table main. Le reste du temps consiste à éva­luer les règles de rou­tage (en­vi­ron 30 ns). Le ra­tio est dé­pen­dant du nombre de routes in­sé­rées (1000 dans cet exemple).

Voici le gra­phique équi­valent pour la fonc­tion IPV6 ip6_​route_​output_​flags() :

🖼 Graphique flamegraph pour la recherche de routes en IPv6
Répartition par fonctions du temps CPU dépensé lors de la recherche d’une route IPv6. L’axe horizontal est le temps total écoulé (300 ns). Le graphique est interactif.

Gros­siè­re­ment, la ré­par­ti­tion du temps est la suivante :

  • 50% est dé­pensé dans le par­cours de l’arbre pour la table main ;
  • 15% est dé­pensé dans les ver­rous (IPv4 re­pose sur le mé­ca­nisme RCU, plus ef­ficace) ;
  • 5% est dé­pensé dans le par­cours de l’arbre pour la table local ;
  • le reste du temps est dé­pensé dans l’éva­lua­tion des règles de rou­tage (en­vi­ron 100 ns)7.

Pour­quoi l’éva­lua­tion des règles de rou­tage est-elle no­toi­re­ment plus lente en IPv6 ? En­core une fois, je n’ai pas de ré­ponse franche sur ce point.

Historique#

Mise à jour (11.2017)

Cette sec­tion a été dé­pla­cée dans sa propre page.

Performance des insertions#

Une autre mé­trique in­té­res­sante est le temps d’in­ser­tion des routes. La mise en place de 40 000 routes se fait en moins de deux se­condes. Pour cer­taines rai­sons, le temps d’in­ser­tion n’est plus li­néaire au-delà et grimpe ra­pi­de­ment à 60 se­condes pour un demi-mil­lion de routes.

Temps d'insertion
Temps d’insertion (temps système) en fonction du nombre de routes. L’axe horizontal utilise une échelle logarithmique. La ligne bleue est une régression linéaire.

Mal­gré sa lo­gique plus com­plexe pour in­sé­rer des routes, le sous-sys­tème IPv4 est ca­pable d’in­sé­rer 2 mil­lions de routes en moins de 10 secondes.

Utilisation mémoire#

Les nœuds de l’arbre ra­dix (struct fib6_​node) et les in­for­ma­tions de rou­tage (struct rt6_​info) sont al­louées via l’al­lo­ca­teur slab8. Il est donc pos­sible d’ex­traire du fi­chier /proc/​slabinfo la quan­tité de mé­moire uti­li­sée à condi­tion de dé­mar­rer le noyau avec l’op­tion slab_​nomerge :

# sed -ne 2p -e '/^ip6_dst/p' -e '/^fib6_nodes/p' /proc/slabinfo | cut -f1 -d:
♯  name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab>
fib6_nodes         76101  76104     64   63    1
ip6_dst_cache      40090  40090    384   10    1

Dans l’exemple ci-des­sus, la mé­moire uti­li­sée est de 76104×64+40090×384 oc­tets (en­vi­ron 20 Mio). Le nombre de struct rt6_​info cor­res­pond au nombre de routes tan­dis que le nombre de nœuds est en­vi­ron le double du nombre de routes :

Nœuds
Nombre de nœuds dans l’arbre radix en fonction du nombre de routes. L’axe horizontal utilise une échelle logarithmique. La ligne bleue est une régression linéaire.

La quan­tité de mé­moire uti­li­sée est donc sim­ple­ment pré­vi­sible. Elle est éga­le­ment très rai­son­nable puisque qua­si­ment n’im­porte quelle pla­te­forme ac­tuelle peut sto­cker plu­sieurs vues com­plètes (20 Mio chacune) :

Utilisation mémoire
Utilisation mémoire en fonction du nombre de routes. L’axe horizontal utilise une échelle logarithmique. La ligne bleue est une régression linéaire.

L’arbre de re­cherche uti­lisé par IPv4 est plus ef­fi­cace : alors qu’IPv6 né­ces­site 512 Mio pour un mil­lion de routes, IPv4 se contente de 128 Mio. Cela pro­vient prin­ci­pa­le­ment de la dif­fé­rence de taille entre la struc­ture rt6_​info (336 bytes) pour IPv6 et la struc­ture fib_​alias (48 bytes) pour IPv4 qui stocke une bonne par­tie des in­for­ma­tions sur le pro­chain saut dans des struc­tures fib_​info par­ta­gées entre les dif­fé­rentes entrées.

Les points à re­te­nir sont :

  • un noyau 4.2 ou plus ré­cent est né­ces­saire pour évi­ter la mise en cache ex­cessive ;
  • le temps de re­cherche d’une route est su­pé­rieur à IPv4 (d’un ordre de grandeur) ;
  • l’op­tion CONFIG_​IPV6_​MULTIPLE_​TABLES im­plique un coût fixe de 100 ns ;
  • l’uti­li­sa­tion mé­moire reste rai­son­nable (20 Mio pour 40 000 routes).

Com­paré à IPv4, IPv6 dans Li­nux ne sus­cite pas le même in­té­rêt, no­tam­ment en terme d’op­ti­mi­sa­tions. Heu­reu­se­ment, les choses s’amé­liorent avec son adop­tion gra­duelle et son uti­li­sa­tion à l’échelle.