Infer adjacencies from MAC tables

When you need this

“This rack of legacy access switches has LLDP disabled by policy and the trace dead-ends at their uplinks. Can I recover the topology from the MAC tables I’m already collecting?”
“Someone swears sw-edge-9 is patched into sw-core-2, but LLDP shows nothing. Does the CAM evidence agree with the suspected miscable?”
“This switch only speaks SNMP Q-BRIDGE-MIB — no LLDP-MIB at all. I need to bootstrap its adjacencies from FDB data alone.”

The normal path to the adjacency table is LLDP collection. This page is the fallback for when that path returns nothing — it derives links purely from which MACs each port has learned, with no help from the link layer.

How it works, briefly

Lowekamp 2001 §5 gives a Simple Connection Theorem: two ports on different switches are directly connected if and only if their per-port CAM sets are disjoint and their union covers the joint host universe of the two devices. A switch learns a MAC on the egress port that leads toward that host, so a host sits on exactly one side of a direct link — the two sides never overlap, and together they account for everyone.

The catch is sample size. Two ports with one observed MAC each look “disjoint” by accident, and the algorithm would happily invent a link between unrelated parts of the fabric. Lowekamp’s Lemma 5.2 proves that three observed MACs per side is enough to rule out almost all coincidental disjointness on real topologies — which is why the default --min-observations is 3. The through-set inference explainer walks the proof and the failure modes in full.

Prerequisites

A populated mac_observation table — the algorithm reads CAM evidence, so the switches you want to infer between need to have been collected (gNMI / SNMP / SSH, any source). Sparse fabrics with only a handful of hosts per port won’t clear the sample-size bar.
Ports tagged correctly. Inference runs over every cross-device port pair; the more access vs. trunk role data the collectors have recorded, the cleaner the candidate set.

The reconciler container, which carries the l2trace CLI:

docker compose run --rm reconciler l2trace infer-adjacency --help

Step 1 — dry-run the inference

The command is dry-run by default. It reads mac_observation at the requested valid-time point, applies the theorem to every cross-device port pair that isn’t already covered by LLDP, and prints a table. Nothing is written.

docker compose run --rm reconciler l2trace infer-adjacency

You’ll get one row per inferred link:

              Through-set inferences as_of=2026-06-18T00:00:00+00:00
┏━━━━━━━┳━━━━━━━━┳━━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━━━━━┓
┃ dev_a ┃ port_a ┃ dev_b ┃ port_b ┃ |T(a)| ┃ |T(b)| ┃ confidence ┃
┡━━━━━━━╇━━━━━━━━╇━━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━━━━━┩
│ 7     │ 41     │ 12    │ 88     │ 6      │ 9      │ 1.000      │
└───────┴────────┴───────┴────────┴────────┴────────┴────────────┘

Dry run — pass --write to persist 1 inferred adjacencies.

|T(a)| and |T(b)| are the number of MACs each port has observed — the evidence behind the call. confidence is the fraction of the two devices’ joint host universe that the port pair’s union covers; 1.000 is the strict Lowekamp form (full coverage). The dev_* / port_* values are device and port IDs — resolve them to names with the adjacency audit query or a quick make psql join against port.

If you get No adjacencies inferred, the diagnostic line tells you why: how many port observations were loaded, how many ports LLDP already covers (those are excluded), and the thresholds in force. Usually it means not enough MACs per port to clear min_observations.

Step 2 — narrow the scope

Inference runs across the whole MAC universe by default. Two filters tighten it:

# Only consider CAM entries in VLAN 200
docker compose run --rm reconciler l2trace infer-adjacency --vlan 200

# Reconstruct topology as it stood at a past valid-time point
docker compose run --rm reconciler l2trace infer-adjacency \
    --as-of 2026-06-01T09:00:00Z

--vlan is worth running per-VLAN when an access layer is segmented — a port’s CAM set is cleaner when you don’t mix VLANs, and the disjointness test is sharper. --as-of reads the bitemporal log at a valid-time point (Snodgrass §2.1): “what did the fabric look like then, per today’s beliefs.” It defaults to now.

Step 3 — relax the thresholds for small fabrics (carefully)

On a lab or a small closet with only a couple of hosts per port, the default --min-observations 3 will reject everything. You can lower it:

docker compose run --rm reconciler l2trace infer-adjacency \
    --min-observations 2

Be honest with yourself about this. The default is conservative on purpose — every notch you drop it makes coincidental disjointness more likely, and the algorithm will start inventing links between ports that just happen not to share a MAC yet. --min-observations 1 is almost always wrong outside a synthetic test. Treat anything inferred below the default as a hypothesis to confirm, not a fact.

--min-coverage is the companion knob. At the strict 1.0, the port pair’s union must cover the entire joint host universe. Dropping it to, say, 0.9 tolerates a few hosts neither port has observed yet — useful when collection is still warming up, at the cost of admitting weaker candidates:

docker compose run --rm reconciler l2trace infer-adjacency \
    --min-coverage 0.9

The confidence column then shows how much each surviving candidate actually covered, so you can eyeball which ones are solid.

Step 4 — persist the links

Once a dry-run table looks right, --write inserts the inferences into the adjacency table:

docker compose run --rm reconciler l2trace infer-adjacency --write

A few things to know about what gets written:

Rows are inserted bidirectionally (A→B and B→A) so the recursive traceroute CTE can walk the link either direction.
They’re stamped source='reconciler', which flags them as derived rather than observed — distinguishable from real LLDP rows in every audit and OPS view.
The algorithm reads existing LLDP adjacencies first and excludes those ports, so --write never clobbers or duplicates a link the link layer already discovered. It only fills the gaps LLDP left.

After writing, the inferred links behave like any other adjacency: the traceroute walker will traverse them, and the bidirectional audit will check them like any other pair.