Abstract
In a communication network, point-to-point traffic volumes over time are critical for designing protocols that route information efficiently and for maintaining security, whether at the scale of an internet service provider or within a corporation. While technically feasible, the direct measurement of point-to-point traffic imposes a heavy burden on network performance and is typically not implemented. Instead, indirect aggregate traffic volumes are routinely collected. We consider the problem of estimating point-to-point traffic volumes, $x_t$, from aggregate traffic volumes, $y_t$, given information about the network routing protocol encoded in a matrix $A$. This estimation task can be reformulated as finding the solutions to a sequence of ill-posed linear inverse problems, $y_t = A x_t$, since the number of origin-destination routes of interest is higher than the number of aggregate measurements available. Here, we introduce a novel multilevel state-space model of aggregate traffic volumes with realistic features. We implement a naive strategy for estimating unobserved point-to-point traffic volumes from indirect measurements of aggregate traffic, based on particle filtering. We then develop a more efficient two-stage inference strategy that relies on model-based regularization: a simple model is used to calibrate regularization parameters that lead to efficient and scalable inference in the multilevel state-space model. We apply our methods to corporate and academic networks, where we show that the proposed inference strategy outperforms existing approaches and scales to larger networks. We also design a simulation study to explore the factors that influence the performance. Our results suggest that model-based regularization may be an efficient strategy for inference in other complex multilevel models.
The Network Tomography Problem
In large-scale communication networks, understanding the volume of traffic between every pair of nodes—known as Origin-Destination (OD) pairs—is essential for security, capacity planning, and efficient routing. However, direct measurement of every OD pair is computationally prohibitive and can significantly degrade network performance.
Instead, network engineers typically collect aggregate traffic volumes ($y_t$) at routers. The relationship is defined by the linear system $y_t = A x_t$, where $A$ is a routing matrix and $x_t$ represents the hidden OD traffic. This constitutes an ill-posed inverse problem because the number of OD pairs far exceeds the number of measurement points. To resolve this, researchers must leverage temporal correlations and traffic "burstiness" to find unique solutions.
Methodology: A Multilevel State-Space Model
The authors introduce a novel multilevel state-space model designed to handle the complexities of real-world traffic. The model consists of two primary layers:
- The Intensity Layer: This layer models the underlying "demand" for a specific route using a multiplicative process, effectively capturing the heavy-tailed, bursty nature of network traffic.
- The Observation Layer: This layer models actual traffic using a truncated Normal distribution. Unlike traditional log-normal models, this truncation allows the system to handle "zero-traffic" periods without mathematical instability.
Two-Stage Inference Strategy
To solve the inverse problem efficiently, a two-stage strategy is employed:
- Stage 1 (Calibration): A simpler, identifiable Gaussian state-space model is fitted to the data to provide a preliminary estimate of traffic patterns.
- Stage 2 (Refinement): These initial estimates serve as informative priors for a complex Sequential Importance Resample Move (SIRM) particle filter.
A key technical innovation is the use of a Random Directions Algorithm (RDA) to sample from the convex polytope—the geometric space of all feasible traffic solutions. This prevents the filter from becoming trapped in the "corners" of the solution space, a common failure mode for standard samplers.
Empirical Validation and Results
The study validates the model using three distinct real-world datasets that include "ground truth" OD traffic:
- Bell Labs (Corporate): A small network where the two-stage approach reduced average estimation error by 60–80% compared to standard local likelihood models.
- Carnegie Mellon University (Academic): A medium-sized network where the model achieved a 53% reduction in $L_2$ error over then-state-of-the-art algorithms.
- Abilene Network (Backbone): A high-speed backbone network where results suggested that the "best" first-stage model depends heavily on the specific network topology.
The algorithm demonstrated real-time scalability, processing 5-minute intervals for a 144-OD pair network in approximately 210–270 seconds, proving it efficient enough for practical deployment.
Conclusion
This research demonstrates that model-based regularization is a powerful tool for solving ill-posed inverse problems in network tomography. By combining geometric insights with a two-stage inference process, the authors provide a scalable, stable, and highly accurate method for monitoring latent network processes. The success of this approach suggests that model-based regularization may be an efficient strategy for inference in other complex multilevel models beyond network engineering.
Summary updated