Skip to content

Graph Reachability Analysis

Method — instantiates Target-Complete Mapping Design

Models sources, intermediate steps, and targets as a directed graph and computes which targets are actually reachable, so any target hidden behind a broken dependency shows up as a provable gap.

Graph Reachability Analysis casts the whole mapping as a directed graph — sources, intermediate nodes, and targets, with edges for every step and every inter-source dependency — and computes the set of targets actually reachable from the sources via transitive closure. Its defining move is handling multi-hop reachability through dependencies: unlike a single-hop coverage grid, it catches a target that looks covered but sits behind a broken or missing intermediate link, so a dependency failure two hops upstream surfaces as an unreachable target rather than staying hidden. Anything outside the computed reachable set is a provable gap.

Example

A carrier must guarantee that traffic from any core node can reach each of 30 required regional endpoints. A flat "each endpoint has an assigned path" table shows full coverage. Reachability analysis instead builds the directed link graph and computes the transitive closure from the core nodes: 28 endpoints come out reachable, 2 do not. Their only assigned paths both traverse a single shared aggregation router currently in maintenance, and no alternate path exists — a dependency that was invisible in the flat table but fatal in the graph, because both "independent" paths silently relied on one node. The result is two provably-unreachable endpoints plus the specific chokepoint to fix, not a vague "mostly fine."

How it works

What distinguishes it is that it treats coverage as a graph property, so shared dependencies become first-class. It models the mapping as edges, computes the reachable set from the sources (a breadth- or depth-first traversal, i.e. the transitive closure of the source set under the edge relation), and diffs that set against the required targets. Because inter-source dependencies are modeled as edges, a single point of failure shared by several nominal routes shows up as targets dropping out of the reachable set — not as coverage that quietly still reads green.

Tuning parameters

  • Edge semantics — what an edge asserts: a path that could exist versus one that is currently healthy. Health-aware edges catch live outages; static edges catch only structural gaps.
  • Dependency depth — ignore inter-source dependencies versus model them fully. Modeling shared dependencies is the whole point, but it enlarges the graph.
  • Constraint on reachability — plain reachability versus capacity- or latency-bounded reachability ("reachable within limits").
  • Snapshot versus dynamic — a one-time structural check versus recomputation as edges go up and down.

When it helps, and when it misleads

Its strength is that it is the only mechanism here that catches gaps created by dependencies — targets that are each individually "covered" but jointly unreachable because they share one broken link. Its weakness is that reachability is only as truthful as the modeled edges: an omitted dependency yields false reachability, and a static graph misses live outages entirely. The classic misuse is declaring reachability on a convenient model that omits the failing dependency — the map says reachable, reality does not. The discipline that guards against it is to model shared dependencies explicitly and validate edges against live state rather than assumed topology, so the graph describes the system that exists, not the one on the architecture diagram.[1]

How it implements the components

Graph Reachability Analysis realizes the routing-and-dependency side of the archetype — the components a graph model of the mapping produces or traverses:

  • mapping_relation_specification — the graph's edges: the concrete source-through-to-target relation it walks.
  • cross_source_dependency_map — inter-source dependency edges, modeled first-class so a shared failure surfaces instead of hiding.
  • uncovered_target_register — its output: the targets that fall outside the computed reachable set, logged as provable gaps.

It does not lay out the two-mode grid for at-a-glance reading — that is the Bipartite Coverage Matrix — nor test a single route's real throughput, which is Source Capacity Load Test; it computes reachability over the dependency graph.

Notes

Reachability proves a path exists in the model; it says nothing about the capacity or the equity of that path. A reachable target can still be under-served when real load arrives (Source Capacity Load Test) or unreachable in practice for some users even though the graph says otherwise (Accessibility Reachability Test). "In the reachable set" is necessary for coverage, not sufficient for it.

References

[1] The reachable set is the transitive closure of the source set under the edge relation — every node arrivable by following edges any number of hops. Computing it (rather than checking one-hop links) is precisely what exposes a target stranded behind a chain of dependencies where each individual hop looked fine. ↩