The Table Is Not a Tree
I wrote down three rules for drawing the AS graph before I measured one. A real full table killed all three.
Michel Wijnberg
The first twelve posts leaned on one advantage: inside an autonomous system, the routers are the oracle. Whatever the model claims, you can go and ask the box. Even the cross-AS paths in post three stayed inside networks I could log into. This series is about what happens when that stops being available, because the subject is other people’s networks.
A BGP table is not a picture of the internet. It is a picture of the internet from where you are standing, and almost everything an operator concludes from it is conditional on that vantage in ways nobody labels. Four posts on what a real table actually looks like, starting with the most basic question anyone building an AS view has to answer:
How do you draw it?
I answered that question in a design document before I had measured anything. Three rules, written with confidence. All three turned out to be false, and the way they failed is more interesting than the rules were.
The three rules I wrote down
Osprey’s AS-flow view puts your own AS in the middle and arranges everything else around it by distance. The design fixed three properties:
| # | Rule | What it assumed |
|---|---|---|
| 1 | The observation horizon is a ring | Beyond some distance, the graph ends |
| 2 | Sector width equals mass share | Each AS has one parent, so the disc partitions cleanly |
| 3 | Origins are leaves (implicit) | Traffic originates at the edge and transits in the middle |
A word first, because it decides how the rest reads. “Parent” and “predecessor” are my rendering terms, not something BGP advertises. An AS_PATH is an ordered sequence; it says nothing about hierarchy. What I call a predecessor is the AS one step closer to the observation point along a path I actually received. That relationship is constructed by the viewer, from the viewer’s position, which turns out to be the whole argument.
Rule 2 is the load-bearing one. If every AS reaches you through exactly one predecessor, the graph is a tree, and a tree can be laid out as nested sectors where width means volume. Every hierarchical rendering of a BGP graph you have ever seen rests on that assumption, usually without saying so.
Then I measured a real one.
What a full table says
A full IPv4 table: 1,071,538 best paths across 79,168 ASes appearing anywhere in a path, one vantage with two upstreams. (Origin ASes are fewer, 78,538; the two counts are different questions and both turn up in this series.) Next to it, DN42, an entirely separate network an order of magnitude smaller. Both measured, both against the same code.
| Assumption | DN42 | Full table | Verdict |
|---|---|---|---|
| One predecessor per AS | 258 of 1,138 multi-parent, max 29 | 22,371 of 79,168 (28.3%), max 202 predecessors | false |
| Edge mass arrives via the heaviest parent | 18.3% does not | 17.5% does not | false |
| No cycles | 41–47 two-cycles | 240 two-cycles | false |
| Origins are leaves | 187 of 192 transits (97.4%) also originate | 10,556 of 11,186 (94.4%) | false |
| Paths are short | 0.0% at five hops or more | 38.0%, longest 15 | conceptually wrong |
The two columns are not the same kind of number and it matters. The full table is one snapshot of a feed I cannot re-run; DN42 is a live network I can query again, and the DN42 column is what it measured on 2026-08-23. Six days earlier the same query said 33.7% off-tree, 138 two-cycles and 8.7% of mass at five hops or more. Nothing broke and no code changed: peers came and went, and every structural property of the graph moved with them.
Some of it moves much faster than that. Sampled every forty-five seconds over two hours, the two-cycle count wanders between 41 and 47, which is why that cell is a range rather than a number. The three figures this post actually leans on, the origin count and the off-tree share and the empty outer ring, did not move at all across the same samples. That is the argument of this series arriving early and uninvited.
Read the second row again, because it is the one that matters for anything drawn as a hierarchy. More than a quarter of the ASes visible from this vantage have more than one predecessor, and one of them has 202. There is no sector boundary that can hold that node. It is not a layout problem to be solved with better geometry; the shape being drawn does not exist.
The mitigation I had written down for rule 2 was “place multi-parent nodes on the sector boundary”. With 202 parents spread across the whole disc, that instruction has no meaning.
Each failure costs the picture something different
Multi-parent breaks the partition. A tree layout implies that following a sector inward tells you where that traffic came from. In a graph where 17.5% of edge mass does not arrive through the heaviest parent, the sector is telling you about a plurality, not a route. Drawing it without saying so converts a majority into a fact.
Origins-are-leaves breaks subtraction. Almost every interior node originates prefixes of its own. If a rendering shows a transit AS’s volume and lets you infer its own originated space by subtracting what its children contribute, it is wrong for 94% of them. Own origination has to be drawn as its own thing, in every slot, never implied by what is left over.
The ring was never a distance. This is the one I had wrong conceptually rather than numerically. For every path it gives you, BGP gives you the whole AS_PATH: there is no distance at which the protocol starts truncating. Paths do get shortened, but never by being far away. What you cannot see is not beyond a horizon, it is absent for a reason:
- it was never advertised to you,
- your own policy refused it,
- it was erased into an
AS_SETby an aggregator, - or it sits behind a transparent route server, which by design leaves no AS_PATH hop at all (RFC 7947).
None of those have a radius. A ring labelled “everything beyond here” is a claim about geometry that the protocol does not support. What Osprey draws instead is hop distance over the adjacencies actually observed, and the legend says exactly that rather than implying a minimum.
That is the view this post is about, drawn from the DN42 feed. The strip along the top is the part I care about: it states the shape of the graph it is drawing, including the 18.3% of mass that no tree can hold, rather than leaving the reader to assume the picture is complete.
Two graphs, both called “the AS topology”
Put the two side by side and the interesting part is not that they differ. It is where they do:
| Property | DN42 | Full table |
|---|---|---|
| Multi-parent ASes | 22.7% | 28.3% |
| Edge mass off the heaviest parent | 18.3% | 17.5% |
| Transits that also originate | 97.4% | 94.4% |
| Paths at five hops or more | 0.0% | 38.0% |
Three of those four rows agree closely enough that a model tuned on either would look fine on the other. The fourth is not a difference of degree. On DN42 nothing at all sits at five hops or more; on a real table it is well over a third of the mass. A layout validated against the small network would not be slightly mis-tuned for the large one, it would have been validated against a graph where the outer ring is empty and then shipped to one where the outer ring is where most of the internet lives.
That is worse than the version of this argument I expected to make, and it is the same argument the lab makes for IGPs, one level up: you cannot validate a model against an environment that cannot contradict it. Three rows agreeing is exactly what makes the fourth dangerous. The small feed does not announce which of its properties happen to generalise.
The refusal this series starts with
One consequence is worth stating before anything else in this series is drawn.
An edge in an AS graph is a path-adjacency, never a peering claim. Two ASes appear next to each other in an AS_PATH; that is the entire observation. It does not mean they have a session, and the transparent route server above is exactly why: two of its clients are path-adjacent without any relationship between them, because RFC 7947 says the server leaves no hop behind.
So the card says “an adjacency in paths, not a verified peering session”, and it says it on every edge.
There is precisely one place where a stronger claim is available: an edge touching your own AS, and then only when an independent session record corroborates it. That is one ring of the picture, and the claim is licensed by the second source rather than by the position. Everything further out is inference about paths, and labelling it as anything else would be inventing relationships between other people’s networks.
What the table actually handed me
Worth separating, because every rule that failed above failed in the same way.
The feed gave me three things: prefixes with their best paths, the AS_PATH on each, and which session it arrived on. That is the whole of the observation.
Everything else in this post I computed. Predecessor, hop distance, edge mass, the off-tree share, whether an AS also originates, the graph itself: all of it is construction, done from one position, and every number would change if the position did.
And three things are not in a BGP table at all, at any distance:
- whether two ASes have a session,
- how much traffic moves along any of this,
- and the paths my upstreams chose not to send me, which leave no trace of having been withheld.
Each of the three rules I wrote down was a claim about the second column dressed as a claim about the first. “Every AS has one parent” sounds like an observation. It is a property of a rendering, and the measurement is what made the difference visible.
The point
I wrote three rules down and a measurement refuted all three. That is a good outcome, and it is only available because the rules were specific enough to be wrong.
The wider claim, which the rest of this series is about: a BGP table is a viewpoint. Its shape, its centre, its backbone and its horizon are all artefacts of where the feed comes from. Every tool that renders one as though it were geography is making a claim about the internet when it only has evidence about a vantage.
The honest version draws what it observed and says which vantage produced it.
Which leaves the question the next post is about. Once you have given up on drawing the table as a hierarchy, you still have to decide what to put at the top of the list, and that turns out to be a harder question than it sounds.
Next: the axis everyone sorts by, and why the biggest network on the internet does not exist. The Biggest AS Doesn’t Exist.