Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University


Advances in Network Tomography

Edoardo M. Airoldi

October 2003


Keywords:Origin-Destination Traffic Flows, Link Loads, Inverse Problem, Transportation Problem, Log-Normal, Gamma, State-Space Model, MCMC, Bayesian Dynamical System, Particle Filter, Stochastic Dynamics, Informative Priors, non-parametric Empirical Bayes

Knowledge about the origin-destination (OD) traffic matrix allows us to solve problems in design, routing, configuration debugging, monitoring and pricing. Direct measurement of these flows is usually not implemented because it is too expensive. A recent work provided a quick method to learn the OD traffic matrix from a set of available standard measurements, which correspond traffic flows observed on the link of a network every 5 minutes. Such a time span allows for more computationally expensive methods that in turn yield a better estimate of the OD traffic matrix. In this work we are the first to explicitly introduce time in learning the OD traffic matrix. The second contribution is that we are the first to use realistic non-Gaussian marginals, specifically the Gamma and the successful log-Normal ones. We combine both these ideas in a novel, doubly stochastic and time-varying Bayesian dynamical system, and provide a simple and elegant solution to obtain informative prior distributions for the stochastic dynamical behavior. Our method outperforms existing solutions in a realistic setting.

42 pages

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by