Tiếng Việt
English
中文
Español
हिन्दी
Français
Português
Русский
Deutsch
日本語
한국어
Italiano
Bahasa Indonesia
ไทย
বাংলা
ລາວ
မြန်မာ
العربية
فارسی
اردو
Українська
Română
Azərbaycan
Les passerelles VPN d'entreprise implantées au croisement des réseaux locaux multi-locataires, des architectures SD-WAN et des maillages BGP Anycast gèrent une grande complexité de routage. Contrairement aux équipements grand public qui n'administrent que quelques passerelles par défaut, un concentrateur VPN central maintient fréquemment plus de 100 000 routes réseau distinctes. Ce volume englobe les adresses individuelles des clients (/32), les sous-réseaux des bureaux distants (/24 à /28) ainsi que les tables d'interconnexion BGP.
Chaque paquet arrivant sur une interface réseau (NIC) nécessite une décision immédiate : identification de l'adresse de saut suivant, sélection de l'interface de sortie et encapsulation appropriée. Dans le noyau Linux, ce chemin critique est orchestré par la base d'informations de transfert (FIB) et sa structure de données sous-jacente, le Level-Compressed Trie (LC-trie).
Pour comprendre la capacité du noyau à maintenir des recherches prévisibles sur des centaines de milliers de préfixes, il convient d'analyser les principes mathématiques de net/ipv4/fib_trie.c.
Cheminement d'une recherche de routage :
Paquet entrant ──> ip_rcv() ──> ip_route_input_noref() ──> fib_lookup()
│
┌──────────────────────────────┴──────────────────────────────┐
▼ ▼
Évaluation des règles RPDB Recherche FIB (fib_table_lookup)
(Éviter les listes séquentielles) │
Parcours de l'arbre LC-Trie
(Pointeurs sans verrou via RCU)
│
▼
Plus long préfixe concordant (LPM)
│
▼
Paquet transféré <══ Structure fib_info (Passerelle, Interface, MTU, Poids ECMP) ═══════════════╝
Le défi de la correspondance du préfixe le plus long (LPM)
Le routage IP obéit à la règle de correspondance du préfixe le plus long (Longest Prefix Match - LPM) définie dans la RFC 1812. Lorsqu'une passerelle possède une entrée pour 10.0.0.0/8 (réseau étendu global) et une autre pour 10.24.16.0/24 (tunnel dédié à une filiale), un paquet destiné à 10.24.16.55 doit obligatoirement emprunter la route /24.
Face à des centaines de milliers d'entrées, les structures de données basiques montrent de sérieuses limites :
- Balayage linéaire : Comparer l'adresse de destination séquentiellement engendre une complexité en $O(N)$, saturant les cœurs processeurs dès que le débit augmente.
- Arbres binaires non compressés : Un arbre binaire classique requiert jusqu'à 32 déréférencements de pointeurs pour une adresse IPv4. Parcourir 32 adresses mémoire dispersées provoque de nombreux défauts de cache (cache misses) L1/L2/L3, limitant le débit effectif sur les liaisons 100 GbE.
Le noyau Linux résout cette contrainte grâce à la compression de niveau.
Fonctionnement interne du LC-Trie dans net/ipv4/fib_trie.c
Le sous-système de routage IPv4 sous Linux utilise un arbre à compression de niveau combinant deux mécanismes d'optimisation : la compression de chemin (Path Compression) et la compression de niveau (Level Compression).
1. Compression de chemin (Saut des bits non ramifiés) :
Arbre binaire classique : (Racine) ──> [0] ──> [1] ──> [0] ──> [Feuille]
Arbre avec saut de chemin : (Racine) ──[Saut 3 bits : "010"]───> [Feuille]
──────────────────────────────────────────────────────────────────────────────
2. Compression de niveau (Remplacement des sous-arbres par des tableaux directs) :
Binaire de profondeur 3 : Compressé en niveau (Tableau vectoriel) :
(Nœud) [Vecteur de Nœud]
/ \ ┌───┬───┬───┬───┬───┬───┬───┬───┐
(N1) (N2) ===> │000│001│010│011│100│101│110│111│
/ \ / \ └───┴───┴───┴───┴───┴───┴───┴───┘
F0 F1 F2 F3 ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
F0 F1 F2 F3 F4 F5 F6 F7
Compression de chemin
Dans les tables réelles, de nombreux sous-réseaux partagent une séquence de bits initiaux identique sans branchements intermédiaires. La compression de chemin fusionne les nœuds intermédiaires dépourvus d'alternative en un nœud unique doté d'un décalage binaire pos, réduisant fortement la profondeur globale.
Compression de niveau
Lorsqu'un sous-arbre de profondeur $k$ présente une forte densité—la majorité de ses $2^k$ feuilles potentielles existant réellement—le noyau remplace le sous-arbre par un nœud vectoriel unique (struct key_vector) contenant $2^k$ pointeurs directs.
L'évaluation s'effectue en une seule opération de décalage et de masque logique, trouvant l'élément en temps $O(1)$ :
$$ ext{Indice} = ( ext{Clé} \gg ext{pos}) \ & \ ((1 \ll ext{bits}) - 1)$$
Organisation mémoire et empreinte
Le noyau structure les routes autour de trois entités clés :
struct key_vector: Représente les nœuds internes ou les feuilles de l'arbre.struct fib_alias: Lie une feuille aux métadonnées de routage (longueur de préfixe, classe de service, table).struct fib_info: Stocke les paramètres d'acheminement effectifs (passerelle de saut suivant, interfacenet_device, MTU). Les routes partageant la même passerelle pointent vers une structure unique via un compteur de références, économisant la mémoire vive.
Toutes les lectures dans fib_table_lookup() s'exécutent sans verrou grâce à la protection RCU (Read-Copy-Update). Les modifications s'opèrent sur des copies privées avant d'être publiées de manière atomique via rcu_assign_pointer().
Télémétrie et analyse de l'arbre de routage
Le système expose l'état interne de la structure à travers l'interface /proc/net/fib_triestat.
Inspection de la table principale :
cat /proc/net/fib_triestat
Indicateurs essentiels à surveiller :
- Profondeur moyenne (
Aver depth) : Indique le nombre moyen d'accès mémoire par paquet. Pour une table saine de 100 000 routes, cette valeur reste comprise entre 2,5 et 3,2. - Profondeur maximale (
Max depth) : Mesure le parcours le plus long. Une valeur supérieure à 8 signale un déséquilibre structurel lié à des sous-réseaux isolés et disparates. - Pointeurs nuls (
Null ptrs / Pointers) : Révèle le taux de cases inoccupées dans les tableaux vectoriels.
Recommandations de configuration pour plus de 100 000 routes
Optimiser le traitement des flux massifs exige une gestion rigoureuse des règles et des paramètres système.
1. Simplification de la base de règles RPDB
Le routage par règles (ip rule) permet d'orienter les paquets selon des critères personnalisés. Toutefois, le noyau parcourt la liste chaînée fib_rules de façon linéaire avant d'interroger la table FIB.
Affichage des règles actives :
ip rule show
Multiplier les règles unitaires ralentit chaque décision de routage. Il est recommandé de :
- Conserver une liste minimale de règles (idéalement les trois règles par défaut).
- Regrouper les politiques au sein de tables fwmark ou d'interfaces VRF dédiées.
2. Hachage multiparcours L4
Pour répartir la charge équitablement entre plusieurs dorsales VPN ou transitaires (ECMP), la configuration par défaut de Linux se limite aux adresses IP source et destination.
Pour intégrer les ports de transport, activez le hachage L4 dans /etc/sysctl.d/99-routing.conf :
net.ipv4.fib_multipath_hash_policy = 1
net.ipv4.fib_multipath_hash_fields = 0x0037
3. Gestion des pics d'annonces BGP
Lors de reconvergences réseau rapides, les démons de routage peuvent injecter des dizaines de milliers de modifications par seconde, surchargeant les files RCU.
Ajustez les seuils du cache et de la table de voisinage :
net.ipv4.neigh.default.gc_thresh1 = 8192
net.ipv4.neigh.default.gc_thresh2 = 32768
net.ipv4.neigh.default.gc_thresh3 = 65536
net.ipv4.route.gc_thresh = 131072
net.ipv4.route.gc_min_interval_ms = 500
Application immédiate des paramètres :
sudo sysctl --system
Intégration avec l'architecture de passerelle RiceGuard
Les infrastructures sécurisées associent l'efficacité du noyau à la robustesse cryptographique des protocoles réseau. Le protocole RiceGuard développé par VPNRice s'appuie sur le routage par clé cryptographique (Cryptokey Routing / AllowedIPs), établissant une table de correspondance interne parfaitement alignée avec la table FIB Linux.
Tandis que le LC-trie du noyau dirige les paquets UDP chiffrés vers les cartes physiques, le mécanisme interne de RiceGuard associe les flux déchiffrés aux clés des pairs autorisés. Cet agencement prévient les boucles de routage et assure des temps de transit prévisibles et homogènes sur l'ensemble du réseau mondial.
