Computer Science Department
School of Computer Science, Carnegie Mellon University


Recovering Latent Time-Series from their Observed Sums:
Network Tomorography with Particle Filters

Edoardo Airoldi, Christof Faloutsos
May 2004

Also appears as Center for Automated Learning and Discovery
Technical Report CMU-CALD-04-104

Keywords: Origin-destination traffic flows, link loads, self-organizing Bayesian dynamical system, MCMC, particle filter, informative priors, non-parametric empirical Bayes

Hidden variables, evolving over time, appear in multiple settings, where it is valuable to recover them, typically from observed sums. Our driving application is 'network tomography', where we need to estimate the origin-destination (OD) traffic flows to determine, e.g., who is communicating with whom in a local area network. This information allows network engineers and managers to solve problems in design, routing, configuration debugging, monitoring and pricing. Unfortunately the direct measurement of the OD traffic is usually difficult, or even impossible; instead, we can easily measure the loads on every link, that is, sums of desirable OD flows.

In this paper we propose i-FILTER, a method to solve this problem. i-FILTER improves the state-of-the-art by (a) introducing explicit time dependence, and by (b) using realistic, non-Gaussian marginals in the statistical models for the traffic flows, as never attempted before. We give experiments on real data, where i-FILTER scales linearly with new observations and out-performs the best existing solutions, in a wide variety of settings. Specifically, on real network traffic measured at CMU, and at AT&T, i-FILTER reduced the estimation errors between 15% and 46% in all cases.

24 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by