The Day My Topology Lied to Me
An engineering postmortem on my own product, and the lab that caught it
Michel Wijnberg
I built Osprey to tell me the truth about networks. Then I found out it had been lying to me. Confidently, in writing, on a canvas I had been demoing to people.
This is what happened, how I caught it, and what I changed. It is the most useful post in this series, because everything else I have written about honesty is cheap until the thing being audited is your own work.
What I believed
Osprey’s path engine did what nearly every path tool does. Given a source and a destination, it ran an area-aware Dijkstra from the source over the OSPF topology and drew the cheapest route.
I had good reasons to trust it. It respected the RFC 2328 rules I cared about: intra-area preferred over inter-area, inter-area transiting the backbone, E1 before E2, ECMP enumerated rather than collapsed. It had tests. It matched my mental model of the lab. When I clicked two routers, a sensible path lit up.
It was also, on one inter-area query in eight, describing a route that no packet would ever take.
How I found out
Not from a bug report. From a chore.
I was building a validation harness for something else entirely, and I wanted a
ground-truth dataset to check it against. The lab has 64 routers in AS 200, all
reachable over SSH, all willing to print their own routing table. So I did the
dumb obvious thing: I logged into all 64 and dumped show ip route ospf from
every one of them.
Then, instead of eyeballing it, I compared every router’s real table against what Osprey’s path engine claimed the path was, for all 4,032 ordered source/destination pairs.
360 of them disagreed.
Not “the cost is slightly off”. The drawn path contained a router the packet provably never visits.
The canonical case
Here is one, with every row measured on the box rather than modelled:
| Router | Says about the destination | Forwards to |
|---|---|---|
dfw1-gw2 | metric 20031, type inter area | dfw1-cr1 |
dfw1-cr1 | metric 30001, type intra area | ord1-cr1 ← not dfw2-cr1 |
ord1-cr1 | metric 20001, type intra area | jfk1-cr1 |
jfk1-cr1 | metric 10001, type intra area | lhr1-cr1 |
lhr1-cr1 | metric 1, connected | delivered |
Osprey drew:
dfw1-gw2 → dfw1-cr1 → dfw2-cr1 → iad2-cr1 → ams1-cr1 → lhr1-cr1The packet never reaches dfw2-cr1. Osprey’s path was cheaper. It was just
not a path any router would build.
Two independent RFC 2328 rules make dfw1-cr1 refuse the cheap corridor, and I
had implemented neither at the level of an individual intermediate router:
§16 step (3) / §16.2 ¶1: the backbone gate. A router attached to multiple
areas examines only backbone summary-LSAs. dfw2-cr1’s cheaper cost-20011
summary genuinely is in dfw1-cr1’s area-4.6.23.0 database (I confirmed that
with show ip ospf database summary, because I did not believe it either), but
it is not a candidate, because dfw1-cr1 is an ABR and that summary did not
arrive via area 0. RFC 3509 §2.1/§2.2, the Cisco ABR behaviour actually running
on these boxes, conditions this on having an active backbone connection, which
dfw1-cr1 has.
§16.2 step (6): intra beats inter, full stop. “If the paths present in the
table are intra-area paths, do nothing with the LSA.” dfw1-cr1 already holds
an intra-area path at metric 30001. The 20011 summary loses to it. Metric never
enters the comparison. This is a rule about path type.
Either rule alone kills the corridor. My engine could not see either, because it
never asked dfw1-cr1 anything. It asked the source router’s view of the
world and then drew a line through eight other routers as though they shared it.
The shape of the mistake
This is worth naming precisely, because the specific OSPF detail is less interesting than the category.
I had modelled a path when the network implements a sequence of independent decisions. Those two things coincide exactly as long as every router along the way uses the same decision rule over the same input set. Inside a single OSPF area they do (same LSDB, same algorithm, same result), which is why the defect count for intra-area pairs was:
0 out of 1,193.
The moment an ABR is involved, the input set stops being shared: an ABR deliberately looks at a different set of LSAs than the routers around it. My model had no place to put that fact, because my model had one graph and one Dijkstra, not sixty-four routers each with an opinion.
| Pairs | With a hop no router would take | |
|---|---|---|
| Intra-area | 1,193 | 0 |
| Inter-area | 2,839 | 360 (12.68%) |
| All | 4,032 | 360 (8.93%) |
The fix, and how I know it worked
The engine now walks the chain. At each hop it evaluates that router’s own installed route toward the destination address, using that router’s own LSDB, area memberships, ABR status and administrative-distance mix, then follows the next hop it actually selects, and repeats.
Then I ran the same 4,032 pairs again, against the same ground truth:
| Check | Result |
|---|---|
| Router’s own metric reproduced exactly | 4,032 / 4,032 |
| Path type (intra / inter / external) exact | 4,032 / 4,032 |
| Full installed ECMP next-hop set identical | 4,032 / 4,032 |
Chain terminates delivered at the requested destination | 4,032 / 4,032 |
Not “improved”. Identical on every pair, including the complete equal-cost next-hop set rather than one arbitrarily chosen member of it.
That is the same query that used to invent a hop, now showing every router that
actually makes a decision, the area it makes it in, and the physical ports on
both sides. The total, 30061, is the source’s own installed metric: literally
the number show ip route prints on lax1-gw1.
And where the chain is not computable (OSPFv3, IS-IS, EIGRP, a partial
scope, an area carrying a virtual link), the engine does not quietly fall back
to the old picture. It returns the source-rooted view with a model_note naming
the reason, rendered as its own explanation step. That refusal is the subject of
post four, and it exists because of this
bug.
A smaller one, for balance
Not every self-inflicted wound is an algorithm. Here is a two-line one that cost me an afternoon.
Osprey’s GRE recorder forms a real OSPF adjacency, so it must originate a Router-LSA. Early on, it advertised the tunnel’s inner subnet as a stub network: correct-looking, RFC-legal, and completely reasonable.
Every router in the area then installed a route toward the tunnel prefix. That route overrode the underlay path the GRE tunnel itself was riding on. The outer transport broke. The adjacency dropped. The recorder reconnected, re-originated the LSA, and did it again.
The fix is in the code comment now, so nobody removes it by accident:
// Only the P2P link is advertised. NO stub network for the tunnel
// inner subnet. Advertising the tunnel subnet (even at max cost) causes SPF
// on other routers to install a route for the tunnel prefix, which can
// disrupt the GRE outer path and kill the adjacency.A monitoring tool that takes down the thing it is monitoring is a special kind of embarrassing, and I would not have found it on a diagram.
What the lab is actually for
I used to describe the lab as the place where I demo Osprey. That was the wrong job description, and getting it right changed how I build.
The lab is not there to make Osprey look good. It is there to prove Osprey wrong.
Which means the lab is only valuable to the degree that it can contradict me: so it is deliberately awkward. Three carriers that share no protocol. Fifteen OSPF areas where three would demo better. An IS-IS domain with seventeen level-1 areas. EIGRP, which has no link-state database at all and breaks every assumption the OSPF code makes. Dual-stack links whose v4 and v6 costs differ by 10× on all 124 of them.
None of that makes a nicer screenshot. All of it has caught something.
The 360 fictional corridors were not found by careful reading, or by a test I was clever enough to write in advance. They were found because I had 64 real routers that could be asked what they actually thought, and I finally asked them all at once instead of trusting the two or three I had spot-checked.
Which raises the obvious question, and it is the subject of the next post: if the network is the only thing that can tell you whether your model is right, how do you turn that into a test suite?