The simulation harness

You can’t trust a traceroute algorithm just because it passes a handful of hand-built fixtures. Hand-built topologies encode the author’s assumptions — they exercise the cases you already thought of. The cases that bite you in production are the ones you didn’t. So l2trace borrows a methodology from the literature: generate thousands of random fabrics, compute the correct answer independently, run the real query against a real database, and count how often the two agree.

This is Bejerano 2009 §VIII, the parameterized simulation methodology that paper used to evaluate its own L2-path reconstruction. The whole harness lives under tests/sim/ and the parameter cell is named after it: TopologyParams carries the docstring “Bejerano §VIII parameter cell.”

The four moving parts

The harness is four small modules that compose into one measurable rate.

Module	Job
`tests/sim/topology.py`	Generate a random fabric deterministically from a seed
`tests/sim/oracle.py`	Compute the ground-truth path by BFS over the per-VLAN spanning tree
`tests/sim/seeder.py`	Load the generated fabric into Postgres using the live schema
`tests/sim/harness.py`	Run `trace_as_of`, compare against the oracle, classify, aggregate

The generator builds the world, the oracle says what the right answer is, the seeder makes the world queryable, and the harness asks the real query the same question and grades the answer.

Generating a fabric

generate_topology(params) is deterministic in params.seed — that’s the load-bearing property. Run it twice with the same params and you get byte-identical devices, ports, links, hosts, and STP state. When a trial fails three hundred iterations into a sweep, the seed that produced it reconstructs that exact fabric so you can debug it in isolation. There’s a test (test_topology_is_deterministic_in_seed) that holds this property still, because the moment it drifts, “reproducible failing trial” becomes a lie.

The generation algorithm, in order:

1. Random spanning tree over n_switches — pick a permutation, link each
   switch (after the first) to a uniformly-chosen earlier one. This
   guarantees connectivity, so the oracle never sees a spurious "no path".
2. Add non-tree edges with probability extra_link_prob per remaining
   pair. This is the density knob — it creates the redundant links that
   STP then has to block.
3. Allocate one trunk port per link end; allocate access ports for hosts.
4. Distribute n_hosts across switches, assign each a VLAN round-robin.
   With multi_host_port_fraction > 0, some access ports carry >1 host.
5. Compute per-VLAN spanning trees (PVST) or one shared tree (CST).
   Tree edges forward; non-tree edges block for that VLAN.
6. Mark gnmi_unavailable_fraction of switches "blind" — the seeder will
   omit their telemetry entirely.

The parameters

@dataclass(frozen=True)
class TopologyParams:
    n_switches: int = 8
    n_hosts: int = 20
    n_vlans: int = 2
    extra_link_prob: float = 0.2
    multi_host_port_fraction: float = 0.0
    gnmi_unavailable_fraction: float = 0.0
    stp_mode: Literal["pvst", "cst"] = "pvst"
    seed: int = 0

extra_link_prob controls how far the fabric is from a pure tree — higher values mean more redundant links and more STP-blocked ports, which is where blocking-edge bugs hide. multi_host_port_fraction is the modern spelling of Bejerano’s hub count: a single access port carrying several hosts, the way a desk switch or a hypervisor vSwitch aggregates MACs behind one physical port. stp_mode flips between per-VLAN spanning trees (PVST rotates the root across VLANs for load-balancing realism) and one shared tree (CST).

And then there’s gnmi_unavailable_fraction, which deserves its own section.

Why gNMI-unavailability is the parameter that matters

Every other parameter varies the shape of the fabric. This one varies how much of it l2trace can actually see — and that’s the realistic failure mode. In a real deployment some switches stream gNMI, some only answer SNMP, some are EOL boxes that emit nothing useful, and some are just unreachable at the moment you run the query. A traceroute tool that only works on a fully-instrumented fabric is a tool that works in the lab and nowhere else.

When the generator marks a switch blind, the seeder omits its CAM and STP rows from Postgres entirely. The device still exists as a topology node — adjacencies on its neighbors still point at it, exactly as a real LLDP scrape would still see the silent box — but trace_as_of has zero forwarding telemetry for it. The walk hits a switch it knows is there and can say nothing about where the frame goes next.

The right behavior in that situation is to stop and say so, not to guess. That’s the whole point of the classification scheme below.

The oracle: ground truth with total information

oracle_path(topo, src, dst, vlan) computes the path a perfectly-informed traceroute would return. It does a BFS from the source switch to the destination switch over the VLAN’s spanning-tree forwarding edges, reconstructs the device chain, and emits hops — access ingress on hop 0, trunk hops in the middle, access egress on the last. Same-switch pairs collapse to a single hop; cross-VLAN pairs return None (no L2 path exists, so the harness scores it as degenerate rather than a failure).

The oracle has total information — it sees every CAM entry that would exist on a fully-instrumented fabric — so its answer is strictly an upper bound on what l2trace could ever produce from partial telemetry. That asymmetry is deliberate: the oracle is the ceiling, the tool is measured against the ceiling, and the gap is either an honest blind spot or a bug.

Seeding and trial isolation

seed_topology writes the generated fabric into the real schema — one row per device, port, bidirectional adjacency, per-(port, vlan) STP state, and the propagated CAM entries. CAM propagation mirrors what a real fabric produces: for every host, every non-blind switch in that VLAN’s spanning tree gets a CAM row pointing at the port toward the host, found by BFS from the host’s switch. Blind switches get nothing.

Each trial runs inside a SAVEPOINT that’s rolled back when the trial finishes:

savepoint = await session.begin_nested()
try:
    seed = await seed_topology(session, topo)
    ...
finally:
    await savepoint.rollback()

This is what makes the paper-scale 2000-trial sweep feasible. Without rollback, a sweep would accumulate millions of rows and every trial would query a database polluted by its predecessors. With it, each trial starts from a clean slate, and the whole run is a pure read against the schema — the outer transaction is rolled back too, so you can run a sweep alongside live data and never commit a single simulated row.

The four classifications

For every (src, dst, vlan) query, the harness compares trace_as_of’s result against the oracle and drops it in exactly one bucket:

Classification	Meaning	Verdict
`success`	Reached, and the device chain matches the oracle exactly	Correct
`false_path`	Reached, but along a different path than the oracle	The headline failure — the tool lied
`false_negative`	Didn’t reach, but the oracle path was fully instrumented	Bug — the tool should have found it
`blind_truncation`	Didn’t reach, and the oracle path crosses a blind device	Expected — graceful degradation working

false_path is the one that matters most, and it’s the metric Bejerano’s evaluation centers on. A tool that fails to answer costs you a debugging session. A tool that confidently answers wrong costs you a wrong fix in production, applied to a fabric that wasn’t broken the way you were told. The CI tests assert false_paths == 0 even under heavy partial visibility — that’s the invariant the whole design protects:

# from test_blind_devices_cause_truncation_not_false_paths
assert result.false_paths == 0, (
    "tool reported a wrong path under partial visibility"
)

The separation of false_negative from blind_truncation is what keeps the score honest under partial telemetry. A naive harness would count every non-reaching query as a failure and the success rate would crater as gnmi_unavailable_fraction rises — but most of that drop is the tool correctly declining to guess. By checking whether the oracle’s path actually crosses a blind device, the harness credits graceful degradation as expected behavior and reserves false_negative for the genuine bug: the tool went silent on a path it had every row it needed to walk.

CI scale vs. paper scale

The harness runs at two scales. CI runs a handful of small cells on every commit under the db pytest marker — enough to catch a regression in trace_as_of or a drift between seeder and oracle, fast enough not to slow the gate down:

uv run pytest tests/test_sim_harness.py -m db

The paper-scale sweep is the standalone runner. It walks a grid of parameter cells, runs the full trial count per cell, and writes a JSON record with success and false-path rates for the evaluation figure:

DATABASE_URL='postgresql+asyncpg://l2trace:l2trace@localhost:5432/l2trace_test' \
uv run python -m tests.sim \
    --switches 4,8,16 \
    --gnmi-fraction 0.0,0.1,0.3 \
    --trials 2000 \
    --output results.json

That’s 3 switch-counts × 3 visibility fractions × 2000 trials × 10 queries — sixty cells of statistical signal, each trial a fresh random fabric, all rolled back. The --gnmi-fraction sweep is the interesting axis: watch success_rate fall and blind_truncation rise together while false_path_rate stays pinned at zero. That’s the shape of a tool that degrades instead of lying.

Coverage diversity, not depth, found a real bug

The harness earned its keep. An early version of the recursive-CTE walk misclassified same-switch hits — when source and destination sat on the same switch, the CTE fell through to the flood branch instead of recognizing the single-hop egress. No hand-written fixture had paired two hosts on one switch in a way that tripped it, because when you write fixtures by hand you reach for the interesting multi-hop cases. The random generator doesn’t have that bias. Across enough trials it pairs hosts on the same switch constantly, and the oracle’s one-hop ground truth (test_oracle_returns_one_hop_for_same_switch_hosts) disagreed with the tool’s flood result. The mismatch surfaced as a false_path, the seed reproduced it exactly, and the fix was a one-line egress check.

The lesson is the Bejerano lesson: it wasn’t a deeper test that found it, it was a more diverse one. Random parameterization explores the boring corners of the input space that a human author skips precisely because they look boring — and the boring corners are where the off-by-one lives.