Fonctionnement de la table de routage IPv4 sous Linux

Vincent Bernat

En bref

Avec une im­plé­men­ta­tion des tables de rou­tage IPv4 uti­li­sant les tries « LPC », Li­nux offre de bonnes per­for­mances pour la re­cherche de routes (50 ns pour une vue com­plète d’In­ter­net). L’uti­li­sa­tion mé­moire est de plus très mo­dé­rée (64 Mio de mé­moire suf­fisent pour 500 000 routes).

Une étape im­por­tante du voyage d’un da­ta­gramme IPv4 à l’in­té­rieur du noyau Li­nux est la re­cherche de la route à uti­li­ser via la fonc­tion fib_​lookup(). À par­tir des in­for­ma­tions es­sen­tielles concer­nant le da­ta­gramme (adresses IP source et des­ti­na­tion, in­ter­faces, …), cette fonc­tion doit four­nir ra­pi­de­ment une dé­ci­sion. Quelques unes des op­tions pos­sibles sont :

  • li­vrai­son lo­cale (RTN_LOCAL) ;
  • rou­tage via un in­ter­mé­diaire fourni (RTN_​UNICAST) ;
  • des­truc­tion sans no­ti­fi­ca­tion (RTN_​BLACKHOLE).

De­puis la ver­sion 2.6.39, Li­nux stocke les routes dans un arbre pré­fixe com­pressé (com­mit 3630b7c050d9). Au­pa­ra­vant, un cache des routes était main­tenu mais ce­lui-ci a été re­tiré1 de Linux 3.6.

Recherche d’une route dans un trie#

Re­cher­cher une route dans une table de rou­tage re­vient à trou­ver le pré­fixe le plus spé­ci­fique cor­res­pon­dant à la des­ti­na­tion. Consi­dé­rons par exemple la table de rou­tage suivante :

$ ip route show scope global table 100
default via 203.0.113.5 dev out2
192.0.2.0/25
        nexthop via 203.0.113.7  dev out3 weight 1
        nexthop via 203.0.113.9  dev out4 weight 1
192.0.2.47 via 203.0.113.3 dev out1
192.0.2.48 via 203.0.113.3 dev out1
192.0.2.49 via 203.0.113.3 dev out1
192.0.2.50 via 203.0.113.3 dev out1

Voici quelques exemples de re­cherches et les dé­ci­sions as­sociées :

IP destination Prochain saut
192.0.2.49 203.0.113.3 via out1
192.0.2.50 203.0.113.3 via out1
192.0.2.51 203.0.113.7 via out3 ou 203.0.113.9 via out4 (ECMP)
192.0.2.200 203.0.113.5 via out2

Une struc­ture très cou­rante pour re­cher­cher une route est le trie, une struc­ture de re­cherche en arbre où chaque nœud a son père pour préfixe.

Recherche dans un trie simple#

Le trie sui­vant en­code la table de rou­tage ex­po­sée ci-dessus :

Simple routing trie
Trie primitif de recherche pour une petite table de routage. Pour des raisons de lisibilité, le trie a été coupé en deux. Les nœuds avec une flèche contiennent une entrée de routage.

À tout mo­ment, la lon­gueur du pré­fixe cor­res­pond à la pro­fon­deur ac­tuelle et le pré­fixe lui-même cor­res­pond au che­min de­puis la racine.

Une re­cherche dans un tel trie est simple. À chaque étape, ré­cu­pé­rer le nème bit de l’adresse IP où n est la pro­fon­deur ac­tuelle dans le trie. Si ce­lui-ci est 0, conti­nuer avec le fils de gauche. Si­non, conti­nuer avec ce­lui de droite. Si un fils est man­quant, re­mon­ter dans l’arbre jusqu’à trou­ver une en­trée de rou­tage. Par exemple, pour 192.0.2.50, le par­cours de l’arbre se ter­mine sur la feuille cor­res­pon­dante. Par contre, pour 192.0.2.50, lorsque le nœud 192.0.2.50/31 est at­teint, il n’y a pas de fils à droite. On re­monte donc l’arbre jusqu’à trou­ver l’en­trée 192.0.2.0/25.

Ajou­ter ou re­ti­rer des routes est tri­vial. Du point de vue de la per­for­mance, la pro­fon­deur étant bor­née par 32, la re­cherche se fait en temps constant par rap­port au nombre de routes.

Quagga est un exemple de lo­gi­ciel de rou­tage uti­li­sant tou­jours cette approche.

Recherche dans un trie compressé#

Dans l’exemple pré­cé­dent, la plu­part des nœuds n’ont qu’un seul fils. Cela en­traîne beau­coup de com­pa­rai­sons bit à bit ainsi qu’un usage sous-op­ti­mal de la mé­moire. Pour ré­soudre ce pro­blème, il est pos­sible de com­pres­ser les che­mins : chaque nœud ayant un fils unique (et n’hé­ber­geant par une en­trée de rou­tage) est sup­primé. Les nœuds res­tants gagnent une pro­priété sup­plé­men­taire in­di­quant le nombre de bits en en­trée qui doivent être igno­rés. Un tel trie est aussi connu sous le nom d’arbre Pa­tri­cia ou d’arbre ra­dix. Voici la ver­sion avec des che­mins com­pres­sés du trie précédent :

Arbre Patricia
Arbre Patricia pour une petite table de routage. Certains nœuds indiquent combien de bits supplémentaires doivent être ignorés dans l’adresse IP recherchée.

Parce que cer­tains bits ont été igno­rés, une vé­ri­fi­ca­tion fi­nale est né­ces­saire pour s’as­su­rer que l’en­trée trou­vée cor­res­pond à l’IP re­cher­chée. Dans le cas contraire, on consi­dère que l’en­trée n’a pas été trou­vée et on re­monte l’arbre pour trou­ver une route adé­quate. La fi­gure ci-des­sous montre deux adresses IP qui abou­tissent à la même feuille :

Recherche dans un arbre Patricia
Recherche de deux adresses IP dans un arbre Patricia. Les deux IP partagent les mêmes bits aux endroits clefs mais sont différents sur les parties ignorées.

La ré­duc­tion de la pro­fon­deur du trie com­pense la com­plexité sup­plé­men­taire ré­sul­tant de la né­ces­sité de gé­rer les faux po­si­tifs. L’in­ser­tion et la sup­pres­sion de routes res­tent re­la­ti­ve­ment aisées.

De nom­breux sys­tèmes de rou­tage uti­lisent des arbres Patricia :

Recherche dans un trie doublement compressé#

En plus de la com­pres­sion le long des che­mins, il est pos­sible de com­pres­ser cer­tains sous-arbres2. Cela consiste à dé­tec­ter les sous-arbres den­sé­ment peu­plés et de les rem­pla­cer par un unique nœud conte­nant un vec­teur de 2k fils. Ce nœud consomme donc k bits en en­trée au lieu d’un seul. Par exemple, voici une ver­sion dou­ble­ment com­pres­sée de notre trie précédent :

Trie doublement compressé
Trie doublement compressé. La fusion d’un sous-arbre produit un nœud avec un vecteur de 4 éléments. Le dernier élément est vide.

Un tel trie est ap­pelé trie LC (le­vel com­pres­sed trie) ou trie LPC (le­vel and path com­pres­sed trie). Il offre des per­for­mances plus éle­vées par rap­port à un arbre radix.

Une heu­ris­tique est uti­li­sée pour dé­ci­der com­bien de bits un nœud doit trai­ter. Li­nux consi­dère que si le ra­tio du nombre de fils non vides sur le nombre to­tal de fils est su­pé­rieur à 50 % quand le nœud traite un bit sup­plé­men­taire, alors le bit en ques­tion est al­loué au nœud. Par contre, si le ra­tio est ac­tuel­le­ment in­fé­rieur à 25 %, le nœud perd la res­pon­sa­bi­lité d’un bit. Ces va­leurs ne sont pas confi­gurables.

L’in­ser­tion et la sup­pres­sion d’une route de­vient une tâche beau­coup plus com­plexe mais le temps de re­cherche est éga­le­ment sen­si­ble­ment réduit.

Implémentation sous Linux#

L’im­plé­men­ta­tion pour IPv4 existe de­puis Li­nux 2.6.13 (com­mit 19baf839ff4a) et est uti­li­sée par dé­faut de­puis la ver­sion 2.6.39 (com­mit 3630b7c050d9).

Voici la re­pré­sen­ta­tion en mé­moire de notre table de routage3 :

Représentation en mémoire d'un trie
Représentation en mémoire d’un trie LPC sous Linux

Plu­sieurs struc­tures sont utilisées :

  • struct fib_​table re­pré­sente une table de routage ;
  • struct trie re­pré­sente un trie ;
  • struct key_​vector re­pré­sente un nœud in­terne (quand bits est dif­fé­rent de 0) ou une feuille ;
  • struct fib_​info contient des at­tri­buts par­ta­gés par plu­sieurs routes (comme l’adresse du pro­chain saut ou l’in­ter­face de sortie) ;
  • struct fib_​alias as­sure le lien entre les feuilles et les struc­tures fib_info.

Le trie peut etre vi­sua­lisé à tra­vers /proc/​net/​fib_trie:

$ cat /proc/net/fib_trie
Id 100:
  +-- 0.0.0.0/0 2 0 2
     |-- 0.0.0.0
        /0 universe UNICAST
     +-- 192.0.2.0/26 2 0 1
        |-- 192.0.2.0
           /25 universe UNICAST
        |-- 192.0.2.47
           /32 universe UNICAST
        +-- 192.0.2.48/30 2 0 1
           |-- 192.0.2.48
              /32 universe UNICAST
           |-- 192.0.2.49
              /32 universe UNICAST
           |-- 192.0.2.50
              /32 universe UNICAST
[…]

Pour les nœuds in­ternes, les trois nombres sui­vant le pré­fixe sont :

  1. le nombre de bits consom­més par ce nœud,
  2. le nombre de fils qui ne gèrent qu’un seul bit,
  3. le nombre de fils vides.

De plus, si le noyau a été confi­guré avec l’op­tion CONFIG_​IP_​FIB_​TRIE_​STATS, des sta­tis­tiques sur la struc­ture sont dis­po­nibles dans /proc/​net/​fib_​triestat4:

$ cat /proc/net/fib_triestat
Basic info: size of leaf: 48 bytes, size of tnode: 40 bytes.
Id 100:
        Aver depth:     2.33
        Max depth:      3
        Leaves:         6
        Prefixes:       6
        Internal nodes: 3
          2: 3
        Pointers: 12
Null ptrs: 4
Total size: 1  kB
[…]

Quand une table de rou­tage est très dense, un nœud peut gé­rer de nom­breux bits. Par exemple, si une table de rou­tage contient un mil­lion d’en­trées /32 pla­cées dans un /12, un seul nœud in­terne peut gé­rer 20 bits. Dans ce cas, la re­cherche se ré­duit à ré­cu­pé­rer l’élé­ment adé­quat dans un tableau.

Le gra­phique sui­vant montre le nombre de nœuds in­ternes uti­li­sés par rap­port au nombre de routes in­sé­rées. Dif­fé­rents scé­na­rios sont en­vi­sa­gés (routes pro­ve­nant d’une vue com­plète d’In­ter­net, routes /32 ré­par­ties sur 4 sous-ré­seaux dif­fé­rents avec des den­si­tés va­riées). Lorsque les routes sont denses, le nombre de nœuds in­ternes est très réduit.

Nœuds internes et pointeurs nuls
Nombre de nœuds internes et de pointeurs nuls par rapport au nombre de routes. L’axe horizontal utilise une échelle logarithmique. La ligne bleue est une régression linéaire.

Performance#

À quel point la re­cherche d’une route est-elle per­for­mante ? La pro­fon­deur maxi­male du trie reste li­mité (en­vi­ron 6 pour une vue com­plète d’In­ter­net) ce qui rend la re­cherche par­ti­cu­liè­re­ment ra­pide. À l’aide d’un pe­tit mo­dule noyau, il est pos­sible de me­su­rer pré­ci­sé­ment5 le temps uti­lisé par la fonc­tion fib_​lookup() :

Profondeur maximale et temps de recherche
Profondeur maximale du trie et temps de recherche selon le nombre de routes insérées. L’axe horizontal utilise une échelle logarithmique.

Le temps de re­cherche est em­pi­ri­que­ment lié à la pro­fon­deur maxi­male. Quand la table de rou­tage est den­sé­ment peu­plée, la pro­fon­deur maxi­male est li­mi­tée et les temps de re­cherche sont rapides.

Pour rou­ter à 10 Gbps, le bud­get pour le trai­te­ment d’un pa­quet est d’en­vi­ron 50 ns. C’est aussi le temps né­ces­saire pour re­cher­cher une route dans cer­tains scé­na­rios. Il n’est donc pas pos­sible de rou­ter à pleine vi­tesse avec un seul cœur. Tou­te­fois, les ré­sul­tats res­tent très bons.

Les me­sures sont faites avec un noyau Li­nux 4.11 em­pa­queté dans De­bian uns­table. Pour des chiffres concer­nant dif­fé­rentes ver­sions du noyau, je­tez un œil sur l’ar­ticle « Pro­gres­sion des per­for­mances de la table de rou­tage IPv4 sous Linux ».

Un autre chiffre in­té­res­sant est le temps pour in­sé­rer un grand nombre de routes dans le noyau. Li­nux est éga­le­ment par­ti­cu­liè­re­ment ef­fi­cace dans ce do­maine puisque deux mil­lions de routes sont in­sé­rées en moins de 10 secondes :

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

Utilisation mémoire#

La quan­tité de mé­moire uti­li­sée est in­di­quée di­rec­te­ment dans le fi­chier /proc/​net/​fib_​triestat. Cela ne prend pas en compte l’es­pace uti­lisé par les struc­tures fib_​info. Tou­te­fois, celles-ci sont nor­ma­le­ment peu nom­breuses (une par saut pos­sible). Comme on peut le voir sur le gra­phique ci-des­sous, la quan­tité de mé­moire uti­li­sée est li­néaire avec le nombre de routes in­sé­rées, quelle que soit la forme des routes.

Utilisation mémoire
Utilisation mémoire du trie par rapport aux nombres de routes insérées. L’axe horizontal utilise une échelle logarithmique. La ligne bleue est une régression linéaire.

Les ré­sul­tats sont très bons : deux mil­lions de routes tiennent dans 256 Mio !

Règles de routage#

À moins d’être confi­guré sans l’op­tion CONFIG_​IP_​MULTIPLE_​TABLES, Li­nux gère plu­sieurs tables de rou­tage et dis­pose d’un sys­tème de règles pour choi­sir la table à uti­li­ser. Ces règles peuvent être confi­gu­rées avec ip rule. Par dé­faut, il en existe trois :

$ ip rule show
0:      from all lookup local
32766:  from all lookup main
32767:  from all lookup default

Li­nux va d’abord uti­li­ser la table local et en cas d’échec se ra­battre sur main puis default.

Tables par défaut#

La table local contient les routes pour la li­vrai­son locale :

$ ip route show table local
broadcast 127.0.0.0 dev lo proto kernel scope link src 127.0.0.1
local 127.0.0.0/8 dev lo proto kernel scope host src 127.0.0.1
local 127.0.0.1 dev lo proto kernel scope host src 127.0.0.1
broadcast 127.255.255.255 dev lo proto kernel scope link src 127.0.0.1
broadcast 192.168.117.0 dev eno1 proto kernel scope link src 192.168.117.55
local 192.168.117.55 dev eno1 proto kernel scope host src 192.168.117.55
broadcast 192.168.117.63 dev eno1 proto kernel scope link src 192.168.117.55

Cette table est gé­rée au­to­ma­ti­que­ment par le noyau quand des adresses IP sont confi­gu­rées. Re­gar­dons d’abord les trois der­nières lignes. Quand l’adresse IP 192.168.117.55 a été confi­gu­rée sur l’in­ter­face eno1, trois nou­velles routes ont été ajou­tées au­to­ma­ti­quement :

  • une route pour 192.168.117.55 pour la li­vrai­son lo­cale en unicast ;
  • une route pour 192.168.117.63 pour une li­vrai­son de type « broadcast » ;
  • une route pour 192.168.117.0 pour une li­vrai­son de type « broad­cast » vers l’adresse de réseau.

Quand 127.0.0.1 est confi­gu­rée sur l’in­ter­face de loop­back, des routes si­mi­laires sont ajou­tées. Tou­te­fois, une adresse de loop­back re­çoit un trai­te­ment spé­cial et le noyau ajoute éga­le­ment le sous-ré­seau en­tier à la table local. Cela per­met d’uti­li­ser n’im­porte quelle adresse dans 127.0.0.0/8 :

$ ping -c1 127.42.42.42
PING 127.42.42.42 (127.42.42.42) 56(84) bytes of data.
64 bytes from 127.42.42.42: icmp_seq=1 ttl=64 time=0.039 ms

--- 127.42.42.42 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.039/0.039/0.039/0.000 ms

La table main contient ha­bi­tuel­le­ment toutes les autres routes :

$ ip route show table main
default via 192.168.117.1 dev eno1 proto static metric 100
192.168.117.0/26 dev eno1 proto kernel scope link src 192.168.117.55 metric 100

La route default a été mise en place par un dé­mon DHCP. La route connec­tée (scope link) a été ajou­tée au­to­ma­ti­que­ment par le noyau (proto kernel) lors de la confi­gu­ra­tion de l’adresse IP sur l’in­ter­face eno1.

La table default est vide et est ra­re­ment uti­li­sée. Elle reste là de­puis Li­nux 2.1.68 en hom­mage à la pre­mière ten­ta­tive de rou­tage avancé dans Li­nux 2.1.156.

Performance#

De­puis Li­nux 4.1 (com­mit 0ddcf43d5d4a), quand les règles de rou­tage ne sont pas mo­di­fiées, les tables main et local sont fu­sion­nées en une seule table. De plus, de­puis Li­nux 3.0 (com­mit f4530fa574df), sans règles spé­ci­fiques confi­gu­rées, il n’y a pas d’im­pact sur les per­for­mances à uti­li­ser un noyau sup­por­tant plu­sieurs tables de rou­tage. Tou­te­fois, dès qu’une nou­velle règle est ajou­tée, quelques cycles CPU sont uti­li­sés pour chaque da­ta­gramme à l’éva­lua­tion des règles. Voici une paire de gra­phiques dé­mon­trant l’im­pact des règles de rou­tage sur les per­formances :

Impact des règles de routage sur les performances
Temps de recherche d’une route selon le nombre de règles de routage. La dernière règle de routage est utilisée. L’échelle du premier graphique est logarithmique tandis que celle du second est linéaire. La ligne bleue est une régression linéaire.

La re­la­tion est li­néaire quand le nombre de règles est entre 1 et 100 mais la pente aug­mente sen­si­ble­ment au-delà. Le se­cond gra­phique met en évi­dence l’im­pact né­ga­tif de la pre­mière règle de rou­tage (en­vi­ron 30 ns).

Une uti­li­sa­tion cou­rante des règles de rou­tage est la créa­tion de rou­teurs vir­tuels : les in­ter­faces sont iso­lées en do­maines et quand un da­ta­gramme entre par une in­ter­face du do­maine A, la table de rou­tage A est utilisée :

# ip rule add iif vlan457 table 10
# ip rule add iif vlan457 blackhole
# ip rule add iif vlan458 table 20
# ip rule add iif vlan458 blackhole

Les règles de type « black­hole » peuvent être sup­pri­mées si on s’as­sure qu’il y a tou­jours une règle par dé­faut dans chaque table de rou­tage. Par exemple, on peut y ajou­ter une route par dé­faut qui re­jette si­len­cieu­se­ment tout da­ta­gramme. Une mé­trique im­por­tante est uti­li­sée pour co­ha­bi­ter avec une éven­tuelle route par dé­faut existante :

# ip route add blackhole default metric 9999 table 10
# ip route add blackhole default metric 9999 table 20
# ip rule add iif vlan457 table 10
# ip rule add iif vlan458 table 20

Pour ré­duire l’im­pact sur les per­for­mances quand de nom­breuses règles de ce type sont uti­li­sées, les in­ter­faces peuvent être at­ta­chées à des ins­tances VRF et une unique règle de rou­tage per­met de sé­lec­tion­ner la table de rou­tage adéquate :

# ip link add vrf-A type vrf table 10
# ip link set dev vrf-A up
# ip link add vrf-B type vrf table 20
# ip link set dev vrf-B up
# ip link set dev vlan457 master vrf-A
# ip link set dev vlan458 master vrf-B
# ip rule show
0:      from all lookup local
1000:   from all lookup [l3mdev-table]
32766:  from all lookup main
32767:  from all lookup default

La règle spé­ciale l3mdev-table est ajou­tée au­to­ma­ti­que­ment lors de la dé­fi­ni­tion de la pre­mière in­ter­face VRF. Cette règle sé­lec­tionne la table de rou­tage as­so­ciée à l’ins­tance VRF à la­quelle l’in­ter­face d’en­trée (ou de sor­tie) a été attachée.

VRF a été in­tro­duit dans Li­nux 4.3 (com­mit 193125dbd8eb). Les per­for­mances ont été gran­de­ment amé­lio­rées dans Li­nux 4.8 (com­mit 7889681f4a6c). La règle de rou­tage gé­né­rique a éga­le­ment été in­tro­duite dans Li­nux 4.8 (com­mit 96c63fa7393d, com­mit 1aa6c4f6b8cd). La do­cu­men­ta­tion du noyau contient des dé­tails sup­plé­men­taires sur son uti­lisation.

Les points à re­te­nir sont :

  • le temps de re­cherche d’une route aug­mente très peu avec le nombre de routes,
  • la re­cherche d’une route parmi des /32 den­sé­ment dis­tri­buées est ex­trê­me­ment rapide,
  • l’uti­li­sa­tion mé­moire est très mo­dé­rée (128 Mio par mil­lion de routes),
  • au­cune op­ti­mi­sa­tion n’est ef­fec­tuée sur les règles de routage.

Pour IPv6, je­tez un œil sur « Fonc­tion­ne­ment de la table de rou­tage IPv6 sous Linux ».

Mise à jour (10.2026)

Cet ar­ticle a été dis­cuté sur Ha­cker News.