Abstract
Dynamic network tomography involves inferring individual origin-destination (OD) traffic flows from aggregate measurements. This is an ill-posed inverse problem due to the rank-deficiency of routing matrices and the complex nature of network traffic. This paper introduces a novel two-stage framework combining a multilevel state-space model with a coarse-to-fine calibration strategy. The approach effectively captures traffic burstiness and sparsity, providing significant improvements in accuracy and computational stability over state-of-the-art methods.
Introduction: The Challenge of Network Tomography
Monitoring modern computer networks often involves measuring total data volumes at specific points, such as routers or links. However, understanding the underlying "conversations" between specific pairs of nodes—origin-destination (OD) flows—is significantly more difficult.
This task, known as dynamic network tomography, is a classic ill-posed inverse problem. It is mathematically defined as $y_t = Ax_t$, where $y_t$ represents observed aggregate traffic, $x_t$ the hidden individual flows, and $A$ the routing matrix. Because $A$ is typically rank-deficient, infinitely many solutions for $x_t$ exist. Furthermore, real-world traffic is characterized by "burstiness" (sudden spikes) and "sparsity" (frequent zero values), which standard linear models struggle to represent.
Methodology
The proposed framework utilizes a multilevel state-space model and a two-stage inference strategy to resolve these ambiguities.
Multilevel State-Space Model
The model decouples traffic dynamics into two distinct layers:
- Intensity Layer: A smooth, log-normal process that models the underlying "potential" for traffic, capturing the inherent bursty behavior.
- Observation Layer: A truncated normal error model that generates actual flows ($x_t$) based on the intensity, naturally inducing sparsity.
Two-Stage Inference and Sampling
To ensure stability and accuracy, the authors employ a "coarse-to-fine" approach:
- Stage 1 (Calibration): A simpler, identifiable Gaussian state-space model is fitted to aggregate data to provide initial estimates and set regularization parameters.
- Stage 2 (Filtering): Hidden flows are estimated using a Sequential Importance Resample-Move (SIRM) particle filter.
To navigate the high-dimensional "feasible region" (where traffic is non-negative and sums to observed totals), a Random Directions Algorithm (RDA) is implemented. This allows for efficient sampling within the polytope of possible solutions, avoiding the computational pitfalls of standard samplers.
Experimental Evaluation
The framework was tested on both simulated and real-world datasets:
- Bell Labs "Router1": A network with 4 nodes and 16 OD flows.
- CMU Network: A complex dataset with 12 nodes and 144 OD flows, characterized by high dimensionality and extreme skewness.
Results and Discussion
The two-stage method demonstrates substantial performance gains over previous Bayesian MCMC methods, such as those by Tebaldi & West.
On the CMU dataset, the proposed method reduced the average $L_2$ error by 53% and $L_1$ error by 44% compared to the previous best-performing Bayesian MCMC methods. Beyond accuracy, the model exhibited high computational stability on skewed data where previous methods often failed. The filtering process is efficient enough for real-time monitoring of networks with over 100 flows.
Conclusion
By combining principled model regularization with efficient geometric sampling, this work provides a robust solution for dynamic network tomography. The "two-stage" strategy offers a blueprint for solving other ill-posed inverse problems in fields like social network analysis and biological modeling.
Summary updated