Monitoring Graph Edges Using Shortest Path Distances

20 concepts8 papers1 proposal

To maintain the integrity of large-scale communication networks, operators must quickly detect and locate link (edge) failures. A highly efficient way to achieve this without checking every link individually is through distance-based monitoring. As introduced by Shih-Shun Kao et al. in Monitoring the edges of a graph using distances, this approach places a small set of monitoring "probes" at specific vertices. These probes track the shortest path distances across the network. When a link fails, the shortest path distances between certain nodes change, creating a unique signature that allows the system to both detect and precisely localize the fault.

Why Simple Path Coverage Fails

Intuitively, one might think that an edge is safely monitored as long as it belongs to at least one shortest path between a pair of probes. However, Florent Foucaud et al. demonstrated in Monitoring Edge-Geodetic Sets in Graphs that standard path coverage is fundamentally insufficient for reliable fault detection.

Consider a scenario where an edge lies on a shortest path between two probes, but there exists an alternative path of the exact same length that bypasses this edge. If the edge fails, network traffic is seamlessly rerouted along the alternative path. Because the overall shortest-path distance between the probes remains completely unchanged, the failure remains entirely hidden from the monitoring system.

The All-Shortest-Paths Constraint

To overcome this masking effect, researchers introduced the concepts of Distance-Edge-Monitoring (DEM) sets and Monitoring Edge-Geodetic (MEG) sets. The core insight, as detailed by Florent Foucaud et al. in Monitoring Edge-Geodetic Sets in Graphs: Extremal Graphs, Bounds, Complexity, is that an edge is only truly monitored if it serves as a strict bottleneck. Specifically, the edge must reside on every shortest path between a given pair of monitoring nodes.

By enforcing this constraint, any single link failure guarantees a measurable disruption. As explained by Subhadeep Ranjan Dev et al. in Monitoring edge-geodetic sets in graphs, requiring all shortest paths to cover an edge ensures that its removal forces the network to find a strictly longer alternative route. This forces the shortest-path distance matrix to change, providing a robust and unambiguous signal of the failure.

Signatures and Alternative Tomography Approaches

When a monitored edge fails, the resulting alterations in the distance matrix form a distinct fingerprint. Shih-Shun Kao et al. emphasize that the uniqueness of these distance change patterns is what enables precise localization rather than just binary detection.

A related perspective on network error localization comes from passive network tomography. For instance, Minghua Chen 0001 et al. in Passive Network Tomography for Erroneous Networks: A Network Coding Approach leverage the algebraic properties of network coding rather than pure distance metrics. They use Impulse Response Vectors (IRVs) as unique fingerprints to pinpoint errors even in the presence of adversarial conditions.

Optimizing Probe Placement and Network Topology

The primary algorithmic challenge in distance-based monitoring is minimization: finding the smallest number of probes required to monitor an entire network. This metric is known as the distance-edge-monitoring number ($dem(G)$) or the monitoring edge-geodetic number ($meg(G)$). Ralf Klasing et al., in On the distance-edge-monitoring numbers of graphs, note that the central difficulty lies in determining this minimum size for arbitrary network topologies, a problem proven to be NP-complete.

To understand how network structure influences monitoring efficiency, researchers look at specific graph properties:

Key Foundational Work

Monitoring the edges of a graph using distances (2022) — contributed 3 concept elements to this direction.
Passive Network Tomography for Erroneous Networks: A Network Coding Approach (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_distance_based_failure_detection_f41fe087,
  title = {distance-based failure detection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distance-based-failure-detection/rdr_f41fe087dbed48b6bf331e314073c920},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_distance_based_failure_detection_f41fe087_v1,
  title = {distance-based failure detection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distance-based-failure-detection/rdr_f41fe087dbed48b6bf331e314073c920/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake