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
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.