Deconvolution of mixing time series on a graph

Alexander W. Blocker, Edoardo M. Airoldi

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.

Origin-destination (OD) loads vs. aggregate loads on a network graph.

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:

  1. Intensity Layer: A smooth, log-normal process that models the underlying "potential" for traffic, capturing the inherent bursty behavior.
  2. 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.

Comparison of L1 and L2 errors across different methods for Bell Labs and CMU datasets.

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

BibTeX
@inproceedings{blocker2011deconvolution,
  author = {Alexander W. Blocker and Edoardo M. Airoldi},
  title = {{Deconvolution of mixing time series on a graph}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=29HNP1kCiq},
}
Figure