Through-set adjacency inference

LLDP and CDP are the easy way to learn who’s plugged into whom: each switch advertises its identity, the neighbor records it, and we read adjacency.remote_chassis_id straight off the wire. But not every link shows up that way. Unmanaged switches in the middle, ports with the discovery protocol disabled, a vendor that only speaks the other protocol from its neighbor — any of these leaves a real cable invisible to peer resolution, and the recursive-CTE traceroute dead-ends there.

Through-set inference is the fallback. It reconstructs the same (local_port, remote_port) pairs from nothing but the CAM tables the switches already learned, using a result from Bruce Lowekamp’s 2001 paper Topology Discovery for Large Ethernet Networks (§5, the Simple Connection Theorem, Theorem 5.1 + Lemma 5.2). No extra protocol, no probe injection — just the forwarding state we’re already collecting.

What a port’s through-set is

A switch learns a MAC by source-address learning: when a frame arrives, the switch records the frame’s source MAC against the port it arrived on, because that’s the egress port to use for anything later destined to that host. The set of source MACs a given port has learned is its through-set, written T(A.p) for port p on device A.

Read that definition carefully, because the whole theorem hinges on the direction. T(A.p) is not “hosts attached to A.p.” It’s “hosts whose traffic arrives at A.p” — which, for a trunk, means every host that lives somewhere on the far side of that link.

The Simple Connection Theorem

Suppose A.p and B.q are directly connected by a cable, with nothing in between:

        ┌──────────┐                 ┌──────────┐
 hosts  │    A     │ A.p ───── B.q   │    B     │  hosts
  on  ──┤          │                 │          ├──  on
 A side │          │                 │          │  B side
        └──────────┘                 └──────────┘

Every host on B’s side sends frames that cross the link and arrive at A.p, so A learns them there: T(A.p) = “all the hosts on B’s side.” Symmetrically, every host on A’s side crosses the other way and lands on B.q, so T(B.q) = “all the hosts on A’s side.” A given host lives on exactly one side of the cable, so:

T(A.p) ∩ T(B.q) = ∅ — disjointness. No host is on both sides.
T(A.p) ∪ T(B.q) covers every host either switch can see — coverage. Between them, the two ports account for the entire joint host universe.

That’s the theorem: a directly-connected port pair has disjoint through-sets whose union is the full joint host population. The algorithm runs it in reverse — find the port pairs that satisfy both conditions, and you’ve found the links.

If T(A.p) and T(B.q) overlap instead, some host is being learned on both ports, which can only happen if an intermediate switch is flooding that host’s frames to both — so the link is not direct. A single shared MAC is enough to disqualify a candidate, which is exactly what test_shared_mac_breaks_disjointness pins.

Why disjointness alone isn’t enough

Here’s the trap, and it’s the reason coverage is in the theorem at all.

Disjointness is necessary but not sufficient. Two ports sitting in completely different segments of the fabric — never connected, never even adjacent — can have disjoint through-sets purely by accident, simply because they happen to have learned different hosts. Disjointness can’t tell “directly connected, so the hosts partition cleanly” apart from “unrelated, so the hosts don’t happen to overlap.”

test_disjoint_but_unrelated_does_not_infer is the worked example. Picture two switches, two ports each, every port seeing three distinct hosts:

obs = {
    (1, 10): {"alpha", "beta", "gamma"},     # switch 1, port a
    (1, 20): {"delta", "epsilon", "zeta"},   # switch 1, port b
    (2, 30): {"eta", "theta", "iota"},       # switch 2, port a
    (2, 40): {"kappa", "lambda", "mu"},      # switch 2, port b
}

Consider the candidate pair (1,10) and (2,30). Their through-sets are disjoint — {alpha, beta, gamma} shares nothing with {eta, theta, iota} — and each side clears the three-host minimum. On disjointness alone, the algorithm would invent a link between two ports that aren’t connected to anything in common.

Coverage is what rejects it. The joint host universe is the union of every host either device has seen across all its ports:

universe(1) = {alpha, beta, gamma, delta, epsilon, zeta}
universe(2) = {eta, theta, iota, kappa, lambda, mu}
joint       = {alpha … mu}   (all twelve)

The candidate union {alpha, beta, gamma, eta, theta, iota} covers 6 of those 12 hosts — coverage 0.5, well under the strict 1.0 threshold — because each switch has other ports seeing hosts the candidate pair knows nothing about. A genuinely direct link wouldn’t leave half the joint universe unaccounted for; those other hosts would have to arrive somewhere, and on a real point-to-point link they’d arrive on one of the two candidate ports. The leftover hosts are the tell that there’s more fabric between these ports than a single cable.

The coverage computation lives right at the heart of the loop:

joint = universe(a_dev) | universe(b_dev)
if not joint:
    continue
union_size = len(a_set | b_set)
confidence = union_size / len(joint)
if confidence < min_coverage:
    continue

confidence is reported on every InferredAdjacency — it’s literally the fraction of the joint universe the pair covers. For the strict Lowekamp form it’s always 1.0; the field only carries a lower value when an operator relaxed min_coverage deliberately.

The three-host floor (Lemma 5.2)

Even with coverage, tiny samples lie. Two ports that have each learned a single host will trivially look disjoint, and on a small or freshly-booted network you can stitch together a plausible-looking but entirely fake topology out of coincidences. Lowekamp’s Lemma 5.2 quantifies the risk and shows that requiring three hosts per side rules out essentially all coincidental disjointness on practical topologies. That’s the default:

def infer_adjacencies(observations, *, min_observations=3, ...):

test_under_min_observations_skipped checks that a side with only two learned MACs is dropped even when disjointness and coverage would otherwise pass. The floor is a knob, not a constant — test_min_observations_one_allows_sparse_pairs exercises min_observations=1 for forensic work on a tiny lab where you’d rather have a low-confidence guess than nothing. Lower it knowing exactly what protection you’re trading away.

Relaxing coverage on noisy networks

Strict min_coverage=1.0 assumes every host has transmitted recently enough to be in someone’s CAM table. Real networks have quiet hosts — a printer that hasn’t sent a frame since its last lease renewal won’t be in any through-set, and its absence drags the coverage ratio below 1.0 even for a genuinely direct link.

min_coverage is the relief valve. Set it to 0.9 and the algorithm accepts pairs that cover 90% of the joint universe, tolerating a handful of silent hosts. test_relaxed_coverage_allows_partial_inference walks a 75%-coverage case: strict rejects it, min_coverage=0.7 accepts it, and the resulting confidence comes back as 0.75 so the operator can see exactly how much benefit of the doubt they extended. The looser you set it, the more false pairs creep back in — coverage is doing real work at 1.0, and every point you give up is a point of that protection gone.

Not re-suggesting links we already know

The loader pulls two things out of the bitemporal log at a given as_of: the per-port through-sets, and the set of ports that already have an open LLDP adjacency.

@dataclass(frozen=True)
class PortObservationsResult:
    port_observations: dict[tuple[int, int], set[str]]
    lldp_known_ports: set[tuple[int, int]]

That second set feeds the algorithm’s excluded_ports parameter, and any candidate touching an excluded port is skipped outright (test_excluded_ports_are_skipped). The point of through-set inference is to fill the gaps LLDP left, so re-deriving links the link-layer protocol already reported would just be noise — and worse, it could disagree with the authoritative LLDP report. We let LLDP win where it spoke, and infer only where it stayed silent.

The loader also takes a vlan filter so inference can run once per VLAN — the right granularity for PVST fabrics where the forwarding topology genuinely differs between VLANs.

A couple of guardrails worth naming

Two ports on the same switch are never proposed as a pair (test_same_device_pairs_never_inferred); they reach each other through the switch fabric, not a direct cable, and InferredAdjacency even raises if you try to hand-build one with both ends on the same device. And the output ordering is deterministic (test_inference_ordering_is_deterministic) — the candidate keys are sorted before iteration so downstream merging across runs stays stable.

Where this sits in the roadmap

Through-set inference is a v1 fallback today: a pure-Python algorithm plus a loader, run on demand by an operator who knows there’s a gap in the LLDP-derived topology. It is not yet wired into continuous collection. The v2 work is sketched but unbuilt — integrating the detector into the orchestrator so it runs as observations stream in, giving inferred links their own adj_proto value so they’re visibly distinct from LLDP/CDP in the adjacency table, and promoting the confidence field into a first-class signal the traceroute walker can weigh rather than trust blindly. Until then, treat an inferred adjacency as a strong hypothesis to confirm, not a measured fact.