Inferring Internal Network States from Edge Measurements

This direction is split into other directions: network tomography constraints. Its last version stays readable and citable here.

Version 1 of 132 papers34 conceptsfrozen 2026-10-04

In modern large-scale communication networks, the internal state of the system—the delay on a specific fiber link or the congestion at a particular router—is often invisible. Administrative boundaries, security policies, and the sheer computational overhead of monitoring every node make direct internal measurement impossible.

This challenge has given rise to Network Tomography, a field that treats the network as a "black box." Much like a medical CT scan uses external X-rays to reconstruct internal organs, network tomography uses end-to-end measurements (like latency or packet loss between edge nodes) to infer the health and performance of hidden internal components.

The Linear Inverse Problem

At its core, network tomography is a problem of solving for hidden variables. If we send a packet from node A to node B, the total delay we measure is the sum of the delays on every individual link along that path. Mathematically, this is expressed as a system of linear equations:

$$y = Ax$$

Where $y$ is a vector of observed end-to-end metrics, $x$ is the vector of unknown internal link metrics, and $A$ is a "routing matrix" that describes which links make up which paths.

The fundamental difficulty is that $A$ is usually "fat"—there are far more internal links than there are observable end-to-end paths. This makes the system under-determined, meaning there are infinitely many internal states that could explain the same external observations.

Exploiting Sparsity with Compressive Sensing

To solve this under-determined system, researchers leverage the observation that network issues are rarely uniform. In a network of thousands of links, usually only a handful are congested at any given time. This "sparsity" allows the application of Compressive Sensing.

Weiyu Xu and Ao Tang demonstrated in Compressive Sensing over Graphs that by using random walk paths, one can recover sparse link data using a number of measurements that scales only logarithmically with the number of nodes. Building on this, Sheng Cai and colleagues introduced FRANTIC, which uses local routing loops to cancel out noise and further reduce the complexity of identifying congested links.

Topological Identifiability

Not every network can be fully "seen" from the outside. The ability to uniquely identify a link's performance depends on the network's structure. Liang Ma, Ting He, and Don Towsley have established the rigorous mathematical bounds for this, proving that properties like 3-vertex-connectivity are often required to ensure that internal metrics can be uniquely decomposed from aggregate path data (Additive Link Metrics Identification).

Interestingly, this problem shares deep mathematical roots with biology. Shankar Bhamidi and Sebastien Roch showed that algorithms designed to reconstruct evolutionary trees (phylogenetics) can be adapted to reconstruct network topologies and delays from multicast measurements (Network delay inference from additive metrics).

From Statistical Models to Deep Learning

While early methods relied on rigid linear assumptions, modern approaches treat the network as a dynamic, latent process.

  1. Queueing Theory: Charles Sutton and Michael I. Jordan bridged the gap between tomography and queueing theory, using Markov Chain Monte Carlo (MCMC) methods to diagnose bottlenecks even when internal arrival times are missing (Inference and Learning in Networks of Queues).
  2. Neural Tomography: When the routing matrix $A$ is unknown—essentially a "double black box"—deep learning frameworks like NeuTomography can learn both the topology and the link states simultaneously from raw end-to-end data (Neural Network Tomography).
  3. Generative Models: Recent work by Yan Qiao and others has applied Denoising Diffusion Probabilistic Models (DDPM) to estimate traffic matrices, treating the reconstruction of hidden traffic flows as a gradient-descent optimization over a diffusion process (Traffic Matrix Estimation based on Denoising Diffusion Probabilistic Model).

Real-Time Adaptation

The ultimate goal of this research is to move from static snapshots to real-time control. Hao-Ting Wei and Chung-Shou Liao achieved a 1,000x speedup in link delay estimation, allowing operators to update their view of the network as the topology changes (Link Delay Estimation Using Sparse Recovery). Similarly, the OPAL algorithm by Xuchuang Wang and John C.S. Lui provides a way to dynamically allocate probes to the most informative parts of the network in real-time, maximizing accuracy while minimizing monitoring overhead (Optimal Online Probe Allocation).

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_inferring_internal_network_states_from_e_1e73308e,
  title = {Inferring Internal Network States from Edge Measurements},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inferring-internal-network-states-from-edge-measurements/rdr_1e73308ee5ce4b37aac43ce7c713cae4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_inferring_internal_network_states_from_e_1e73308e_v1,
  title = {Inferring Internal Network States from Edge Measurements},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inferring-internal-network-states-from-edge-measurements/rdr_1e73308ee5ce4b37aac43ce7c713cae4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}