La table n’est pas un arbre
J’ai écrit trois règles pour dessiner le graphe d’AS avant d’en avoir mesuré un seul. Une vraie table complète les a toutes les trois démolies.
Michel Wijnberg
Les douze premiers articles s’appuyaient sur un avantage : à l’intérieur d’un système autonome, les routeurs font office d’oracle. Quoi qu’en dise le modèle, on peut toujours aller interroger l’équipement. Même les chemins inter-AS de l’article trois restaient dans des réseaux où je pouvais me connecter. Cette série parle de ce qui se passe quand cela cesse d’être possible, parce que le sujet, ce sont les réseaux des autres.
Une table BGP n’est pas une image d’internet. C’est une image d’internet depuis l’endroit où l’on se tient, et presque tout ce qu’un opérateur en conclut dépend de ce point de vue d’une manière que personne n’étiquette. Quatre articles sur ce à quoi ressemble vraiment une table réelle, en commençant par la question la plus élémentaire que doit trancher quiconque construit une vue d’AS :
Comment la dessine-t-on ?
J’ai répondu à cette question dans un document de conception avant d’avoir mesuré quoi que ce soit. Trois règles, écrites avec assurance. Les trois se sont révélées fausses, et la façon dont elles ont échoué est plus intéressante que les règles elles-mêmes.
Les trois règles que j’avais écrites
La vue de flux d’AS d’Osprey place votre propre AS au centre et dispose tout le reste autour, par distance. La conception fixait trois propriétés :
| # | Règle | Ce qu’elle supposait |
|---|---|---|
| 1 | L’horizon d’observation est un anneau | Au-delà d’une certaine distance, le graphe s’arrête |
| 2 | La largeur de secteur vaut la part de masse | Chaque AS a un prédécesseur, donc le disque se partitionne proprement |
| 3 | Les origins sont des feuilles (implicite) | Le trafic naît en bordure et transite au centre |
Un mot d’abord, car il décide de la lecture du reste. « Prédécesseur » et « parent » sont mes termes de rendu, pas quelque chose que BGP annonce. Un AS_PATH est une séquence ordonnée ; il ne dit rien d’une hiérarchie. Ce que j’appelle prédécesseur est l’AS situé un cran plus près du point d’observation le long d’un chemin que j’ai réellement reçu. Cette relation est construite par l’observateur, depuis sa position, et c’est là tout l’argument.
La règle 2 est celle qui porte la charge. Si chaque AS vous atteint par exactement un prédécesseur, le graphe est un arbre, et un arbre se dessine en secteurs imbriqués où la largeur signifie le volume. Toute représentation hiérarchique d’un graphe BGP que vous avez vue repose sur cette hypothèse, en général sans le dire.
Puis j’en ai mesuré une vraie.
Ce que dit une table complète
Une table IPv4 complète : 1 071 538 meilleurs chemins sur 79 168 AS apparaissant quelque part dans un chemin, un point de vue avec deux transitaires. (Les AS d’origine sont moins nombreux, 78 538 ; les deux comptes répondent à des questions différentes et tous deux reviennent dans cette série.) À côté, DN42, un réseau entièrement distinct et un ordre de grandeur plus petit. Les deux mesurés, les deux avec le même code.
| Hypothèse | DN42 | Table complète | Verdict |
|---|---|---|---|
| Un prédécesseur par AS | 258 sur 1 138 en ont plusieurs, max. 29 | 22 371 sur 79 168 (28,3 %), max. 202 prédécesseurs | fausse |
| La masse de bordure arrive par le parent le plus lourd | 18,3 % non | 17,5 % non | fausse |
| Pas de cycles | 41–47 cycles à deux | 240 cycles à deux | fausse |
| Les origins sont des feuilles | 187 transits sur 192 (97,4 %) originent aussi | 10 556 sur 11 186 (94,4 %) | fausse |
| Les chemins sont courts | 0,0 % à cinq sauts ou plus | 38,0 %, le plus long 15 | conceptuellement erronée |
Les deux colonnes ne sont pas le même genre de chiffre, et cela compte. La table complète est un instantané d’un flux que je ne peux pas rejouer ; DN42 est un réseau vivant que je peux réinterroger, et la colonne DN42 est ce qu’elle a mesuré le 2026-08-23. Six jours plus tôt, la même requête donnait 33,7 % hors arbre, 138 cycles à deux et 8,7 % de la masse à cinq sauts ou plus. Rien n’a cassé et aucun code n’a changé : des pairs sont arrivés et repartis, et chaque propriété structurelle du graphe a bougé avec eux.
Une partie bouge bien plus vite. Échantillonné toutes les quarante-cinq secondes pendant deux heures, le nombre de cycles à deux erre entre 41 et 47, et c’est pourquoi cette cellule est une plage et non un nombre. Les trois chiffres sur lesquels cet article s’appuie réellement, le nombre d’origines, la part hors arbre et l’anneau extérieur vide, n’ont pas bougé d’un iota sur les mêmes échantillons. C’est l’argument de cette série qui arrive tôt et sans invitation.
Relisez la deuxième ligne, car c’est celle qui compte pour tout ce qui se dessine en hiérarchie. Plus d’un quart des AS visibles depuis ce point de vue ont plus d’un prédécesseur, et l’un d’eux en a 202. Aucune frontière de secteur ne peut contenir ce nœud. Ce n’est pas un problème de mise en page à résoudre par une meilleure géométrie ; la forme que l’on dessine n’existe pas.
L’atténuation que j’avais notée pour la règle 2 disait « placer les nœuds à plusieurs parents sur la frontière de secteur ». Avec 202 parents répartis sur tout le disque, cette instruction n’a aucun sens.
Chaque échec coûte à l’image quelque chose de différent
Les parents multiples cassent la partition. Une disposition en arbre implique que suivre un secteur vers l’intérieur indique d’où venait ce trafic. Dans un graphe où 17,5 % de la masse de bordure n’arrive pas par le parent le plus lourd, le secteur parle d’une majorité relative, pas d’une route. Le dessiner sans le dire transforme une majorité en fait.
« Les origins sont des feuilles » casse la soustraction. Presque tous les nœuds intérieurs originent leurs propres préfixes. Si un rendu montre le volume d’un AS de transit et laisse déduire son espace propre en soustrayant ce qu’apportent ses enfants, il se trompe pour 94 % d’entre eux. L’origination propre doit être dessinée pour elle-même, dans chaque emplacement, jamais impliquée par ce qui reste.
L’anneau n’a jamais été une distance. Celle-là, je l’avais fausse conceptuellement et non numériquement. Pour chaque chemin qu’il fournit, BGP fournit l’AS_PATH entier : il n’y a pas de distance à partir de laquelle le protocole se met à tronquer. Les chemins sont bien raccourcis, mais jamais du fait de l’éloignement. Ce que vous ne voyez pas n’est pas au-delà d’un horizon, c’est absent pour une raison :
- cela ne vous a jamais été annoncé,
- votre propre politique l’a refusé,
- un agrégateur l’a effacé dans un
AS_SET, - ou cela se trouve derrière un route server transparent qui, par conception, ne laisse aucun saut d’AS_PATH (RFC 7947).
Aucune de ces raisons n’a de rayon. Un anneau étiqueté « tout ce qui est au-delà » est une affirmation géométrique que le protocole ne soutient pas. Ce qu’Osprey dessine à la place, c’est une distance en sauts sur les adjacences réellement observées, et la légende dit exactement cela au lieu de suggérer un minimum.
C’est la vue dont parle cet article, dessinée depuis le flux DN42. Le bandeau du haut est la partie qui m’importe : il énonce la forme du graphe qu’il dessine, y compris les 18,3 % de masse qu’aucun arbre ne peut contenir, au lieu de laisser le lecteur supposer que l’image est complète.
Deux graphes, tous deux appelés « la topologie d’AS »
Mettez les deux côte à côte et l’intéressant n’est pas qu’elles diffèrent. C’est là où elles diffèrent :
| Propriété | DN42 | Table complète |
|---|---|---|
| AS à plusieurs parents | 22,7 % | 28,3 % |
| Masse de bordure hors parent le plus lourd | 18,3 % | 17,5 % |
| Transits qui originent aussi | 97,4 % | 94,4 % |
| Chemins à cinq sauts ou plus | 0,0 % | 38,0 % |
Trois de ces quatre lignes concordent assez pour qu’un modèle réglé sur l’une paraisse correct sur l’autre. La quatrième n’est pas une différence de degré. Sur DN42, rien du tout ne se trouve à cinq sauts ou plus ; sur une vraie table, c’est bien plus d’un tiers de la masse. Une disposition validée sur le petit réseau ne serait pas légèrement mal réglée pour le grand : elle aurait été validée contre un graphe dont l’anneau extérieur est vide, puis livrée à un graphe où l’anneau extérieur est l’endroit où vit l’essentiel d’internet.
C’est pire que la version de cet argument que je pensais formuler, et c’est l’argument que le laboratoire fait pour les IGP, un cran plus haut : on ne peut pas valider un modèle contre un environnement incapable de le contredire. Que trois lignes concordent est précisément ce qui rend la quatrième dangereuse. Le petit flux n’annonce pas lesquelles de ses propriétés se généralisent par hasard.
Le refus par lequel cette série commence
Une conséquence mérite d’être énoncée avant que quoi que ce soit d’autre ne soit dessiné dans cette série.
Une arête dans un graphe d’AS est une adjacence de chemin, jamais une affirmation de peering. Deux AS apparaissent côte à côte dans un AS_PATH ; c’est toute l’observation. Cela ne veut pas dire qu’ils ont une session, et le route server transparent ci-dessus en est précisément la raison : deux de ses clients sont adjacents dans le chemin sans aucune relation entre eux, parce que le RFC 7947 dit que le serveur ne laisse pas de saut.
La fiche dit donc « une adjacence dans des chemins, pas une session de peering vérifiée », et elle le dit sur chaque arête.
Il y a exactement un endroit où une affirmation plus forte est disponible : une arête touchant votre propre AS, et seulement quand un enregistrement de session indépendant la corrobore. C’est un anneau de l’image, et l’affirmation est autorisée par la seconde source, non par la position. Tout ce qui est plus loin est de l’inférence sur des chemins, et l’étiqueter autrement reviendrait à inventer des relations entre les réseaux des autres.
Ce que la table m’a réellement donné
Cela mérite d’être isolé, car toutes les règles tombées plus haut sont tombées de la même façon.
Le flux m’a donné trois choses : des préfixes avec leurs meilleurs chemins, l’AS_PATH de chacun, et la session par laquelle ils sont arrivés. C’est toute l’observation.
Tout le reste de cet article, je l’ai calculé. Prédécesseur, distance en sauts, masse d’arête, part hors arbre, le fait qu’un AS origine aussi, le graphe lui-même : tout cela est construction, faite depuis une position, et chaque chiffre changerait si la position changeait.
Et trois choses ne figurent pas du tout dans une table BGP, à aucune distance :
- si deux AS ont une session,
- quel volume de trafic circule là-dessus,
- et les chemins que mes transitaires ont choisi de ne pas m’envoyer, qui ne laissent aucune trace d’avoir été retenus.
Chacune des trois règles que j’avais écrites était une affirmation sur la seconde colonne déguisée en affirmation sur la première. « Chaque AS a un parent » sonne comme une observation. C’est une propriété d’un rendu, et c’est la mesure qui a rendu la différence visible.
L’essentiel
J’ai écrit trois règles et une mesure les a toutes réfutées. C’est un bon résultat, et il n’était possible que parce que les règles étaient assez précises pour pouvoir être fausses.
L’affirmation plus large, dont traite le reste de cette série : une table BGP est un point de vue. Sa forme, son centre, son cœur de réseau et son horizon sont tous des artefacts de l’endroit d’où vient le flux. Tout outil qui en dessine une comme s’il s’agissait de géographie affirme quelque chose sur internet alors qu’il n’a de preuves que sur un point de vue.
La version honnête dessine ce qu’elle a observé et dit quel point de vue l’a produit.
Reste la question dont traite l’article suivant. Une fois renoncé à dessiner la table en hiérarchie, il faut encore décider quoi mettre en haut de la liste, et c’est une question plus difficile qu’il n’y paraît.
Ensuite : l’axe sur lequel tout le monde trie, et pourquoi le plus grand réseau d’internet n’existe pas. Le plus grand AS n’existe pas.