Précédemment, nous avions regardé comment fonctionnait la table de routage IPv4 sous Linux. Qu’en est-il de l’implémentation pour IPv6 ?

Arbre de recherche#

Chercher un préfixe dans une table de routage revient à trouver l’entrée la plus spécifique correspondant à la destination souhaitée. Une structure courante pour cette tâche est le trie, un arbre de recherche pour lequel chaque nœud est préfixé par son père.

Pour IPv4, Linux utilise un arbre doublement compressé (appelé LPC-trie), offrant de bonnes performances avec un usage mémoire faible. Pour IPv6, Linux emploie le plus classique arbre radix (encore appelé trie Patricia). Il y a trois raisons pour ne pas avoir recyclé la solution utilisée pour IPv4 :

• L’implémentation IPv6 (introduite dans Linux 2.1.8, 1996) est antérieure à celle pour IPv4 qui date de Linux 2.6.13 (commit 19baf839ff4a).
• Les fonctionnalités offertes sont différentes. Notamment, IPv6 intègre la possibilité d’un routage par l’adresse source¹ (depuis Linux 2.1.120, 1998).
• L’espace d’adressage IPv4 est beaucoup plus dense que celui d’IPv6, ce qui rend la compression par niveau du trie particulièrement efficace.

À titre d’exemple, l’illustration ci-dessous montre un arbre radix codant 6 préfixes :

Pour des explications plus détaillées sur les différents codages possibles d’une table de routage et des éclaircissements sur les arbres radix, jetez un œil sur les explications pour IPv4.

La figure ci-dessous montre la représentation en mémoire de l’arbre radix précédent. Chaque nœud correspond à une structure fib6_node. Quand un nœud a le drapeau RTN_RTINFO, il contient un pointeur vers une structure rt6_info contenant des informations sur le prochain saut.

La fonction fib6_lookup_1() parcourt l’arbre radix en deux étapes :

1. parcours descendant pour localiser un candidat potentiel,
2. vérification de la validité du candidat et recherche en arrière si besoin.

Voici une version légèrement simplifiée (sans routage 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 Linux 3.6 (commit 5e9965c15ba8), IPv6 dispose toujours de ce mécanisme. Toutefois, les entrées sont placées directement dans l’arbre radix avec le drapeau RTF_CACHE et non dans une structure distincte.

Depuis Linux 2.1.30 (1997) et jusqu’à Linux 4.2 (commit 45e4fd26683c), quasiment toutes les recherches aboutissaient à la création d’une entrée dans le cache. Par exemple, un routeur voyant transiter 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 fonction ip6_dst_gc() assure le nettoyage du cache avec les paramè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 ramasse-miette est activé au plus toutes les 500 ms lorsqu’il y a plus de 1024 entrées dans le cache ou au moins toutes les 30 secondes. Il ne tourne pas plus de 60 secondes, sauf s’il y a plus de 4096 entrées. Lorsqu’il tourne, il va d’abord effacer les entrées vieilles de plus de 30 secondes. Tant que le nombre d’entrées reste supérieur à 4096, il continue d’effacer les entrées de plus en plus récentes (mais pas plus récentes que 512 jiffies qui correspond à la valeur de gc_elasticity) avec une pause de 500 ms entre chaque passage.

Depuis Linux 4.2 (commit 45e4fd26683c), seules les exceptions PMTU provoquent la création d’une entrée dans le cache. Un routeur ne gèrant pas ces exceptions, seuls les hôtes auront (rarement) des entrées dans le cache². Martin KaFai Lau, de Facebook, explique:

De toutes les routes IPv6 de type RTF_CACHE qui sont créées, le pourcentage qui a un MTU différent est très faible. Sur l’un de nos serveurs mandataires face à des utilisateurs finaux, seulement 1000 entrées sur 80 000 ont un MTU plus faible. En ce qui concerne le trafic dans notre DC, il n’y a pas d’exception MTU.

Voici à quoi ressemble une entrée dans le cache avec une exception 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énarios différents sont étudiés :

Extrait d’une vue complète d’Internet

Dans ce scénario, Linux se comporte comme un routeur connecté à plusieurs transitaires et disposant d’une vue « complète ». Actuellement, la taille d’une telle table de routage est légèrement supérieure à 40 000 routes.

Préfixes /48 saupoudrés linéairement avec différentes densités

Linux agit comme un routeur au cœur d’un datacentre. Chaque client ou baie obtient un ou plusieurs sous-réseau /48 qu’il convient d’aiguiller. Avec une densité de 1, les /48 sont contigus.

Préfixes /128 répartis aléatoirements dans un /108

Linux se comporte comme un routeur d’accès pour un réseau /64 dans lequel les hôtes obtiennent leur IP par auto-configuration. Si tous les hôtes partagent le même OUI, les 40 premiers bits sont fixes. Dans ce scénario, la table des voisins est convertie en routes par un processus externe et redistribué auprès des autres routeurs servant le même sous-réseau³.

Performance de la recherche#

À l’aide d’un module noyau, il est possible de mesurer précisément le temps d’exécution⁴ de la fonction ip6_route_output_flags():

Obtenir des résultats satisfaisants s’avère complexe en raison de la taille de l’espace d’adressage. Aucun des scénarios ne dispose d’une route par défaut et les mesures ne sont conservées que lorsque la recherche aboutit à une solution⁵. Pour le scénario avec la vue complète, seules les adresses de 2400::/16 à 2a06::/16 sont utilisées (cela comprend plus de la moitié des routes). Pour le scénario avec les préfixes /128, l’intégralité du sous-réseau /108 est balayé. Pour le scénario avec les /48, le balayage est effectué depuis le premier /48 jusqu’au dernier. Pour chaque passage, 5000 adresses sont prises semi-aléatoirement. De nouveaux passages sont effectués jusqu’à atteindre 5000 recherches réussies ou 1 million de recherches au total.

La relation entre la profondeur maximale de l’arbre et le temps de recherche est partielle. Il m’est difficile d’expliquer la différence de performance entre les différentes densités du scénario en /48.

On peut toutefois observer deux points importants :

• Avec une vue complète, le temps de recherche médian est de 450 ns. C’est environ 10 fois le budget pour expédier des paquets à 10 Gbps (environ 50 ns).
• Avec une table de routage presque vide, le temps de recherche est de 150 ns. C’est encore au-dessus du budget pour une connexion à 10 Gbps.

Avec IPv4, le temps de recherche sur une table presque vide était d’environ 20 ns tandis qu’avec une vue complète (500 000 routes), il est d’environ 50 ns. Comment expliquer une telle différence ? Tout d’abord, la profondeur de l’arbre compressé en IPv4 est très faible (6 pour 500 000 routes) tandis que la profondeur de l’arbre radix avec 40 000 routes est d’environ 40.

Deuxièmement, bien que la fonction fib_lookup() pour IPv4 et la fonction ip6_route_output_flags() pour IPv6 ont des coûts fixes liés à l’évaluation des règles de routage, IPv4 dispose de plusieurs optimisations quand ces règles de routage n’ont pas été modifiées⁶. Ces optimisations sont retirées au premier changement. Dans ce cas, IPv4 est impacté de 30 ns. Cela laisse encore un désavantage de 100 ns pour IPv6.

Regardons où le temps CPU est dépensé pour chacune des deux fonctions. Voici un graphique de type flame graph pour la fonction IPv4 fib_lookup() :

Seulement la moitié du temps est dépensé dans le parcours d’arbre via la fonction fib_table_lookup(). Il convient de noter que cette fonction est en réalité exécutée deux fois : une fois pour la table local et une fois pour la table main. Le reste du temps consiste à évaluer les règles de routage (environ 30 ns). Le ratio est dépendant du nombre de routes insérées (1000 dans cet exemple).

Voici le graphique équivalent pour la fonction IPV6 ip6_route_output_flags() :

Grossièrement, la répartition du temps est la suivante :

• 50% est dépensé dans le parcours de l’arbre pour la table main,
• 15% est dépensé dans les verrous (IPv4 repose sur le mécanisme RCU, plus efficace),
• 5% est dépensé dans le parcours de l’arbre pour la table local,
• le reste du temps est dépensé dans l’évaluation des règles de routage (environ 100 ns)⁷.

Pourquoi l’évaluation des règles de routage est-elle notoirement plus lente en IPv6 ? Encore une fois, je n’ai pas de réponse franche sur ce point.

Historique#

Performance des insertions#

Une autre métrique intéressante est le temps d’insertion des routes. La mise en place de 40 000 routes se fait en moins de deux secondes. Pour certaines raisons, le temps d’insertion n’est plus linéaire au-delà et grimpe rapidement à 60 secondes pour un demi-million de routes.

Malgré sa logique plus complexe pour insérer des routes, le sous-système IPv4 est capable d’insérer 2 millions de routes en moins de 10 secondes.

Utilisation mémoire#

Les nœuds de l’arbre radix (struct fib6_node) et les informations de routage (struct rt6_info) sont allouées via l’allocateur slab⁸. Il est donc possible d’extraire du fichier /proc/slabinfo la quantité de mémoire utilisée à condition de démarrer le noyau avec l’option 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-dessus, la mémoire utilisée est de 76104×64+40090×384 octets (environ 20 Mio). Le nombre de struct rt6_info correspond au nombre de routes tandis que le nombre de nœuds est environ le double du nombre de routes :

La quantité de mémoire utilisée est donc simplement prévisible. Elle est également très raisonnable puisque quasiment n’importe quelle plateforme actuelle peut stocker plusieurs vues complètes (20 Mio chacune) :

L’arbre de recherche utilisé par IPv4 est plus efficace : alors qu’IPv6 nécessite 512 Mio pour un million de routes, IPv4 se contente de 128 Mio. Cela provient principalement de la différence de taille entre la structure rt6_info (336 bytes) pour IPv6 et la structure fib_alias (48 bytes) pour IPv4 qui stocke une bonne partie des informations sur le prochain saut dans des structures fib_info partagées entre les différentes entrées.

Les points à retenir sont :

• un noyau 4.2 ou plus récent est nécessaire pour éviter la mise en cache excessive,
• le temps de recherche d’une route est supérieur à IPv4 (d’un ordre de grandeur),
• l’option CONFIG_IPV6_MULTIPLE_TABLES implique un coût fixe de 100 ns,
• l’utilisation mémoire reste raisonnable (20 Mio pour 40 000 routes).

Comparé à IPv4, IPv6 dans Linux ne suscite pas le même intérêt, notamment en terme d’optimisations. Heureusement, les choses s’améliorent avec son adoption graduelle et son utilisation à l’échelle.