A fast lightweight approach to origin-destination IP traffic estimation using partial measurements
Authors:
- 5 June 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (6) , 2634-2648
Abstract
In this paper, a novel approach is proposed for estimating traffic matrices. Our method, called PamTram for PArtial Measurement of TRAffic Matrices, couples lightweight origin-destination (OD) flow measurements along with a computationally lightweight algorithm for producing OD estimates. The first key aspect of our method is to actively select a small number of informative OD flows to measure in each estimation interval. To avoid the heavy computation of optimal selection, we use intuition from game theory to develop randomized selection rules, with the goals of reducing errors and adapting to traffic changes. We show that it is sufficient to measure only one flow per measurement period to drastically reduce errors-thus rendering our method lightweight in terms of measurement overhead. The second key aspect is an explanation and proof that an Iterative Proportional Fitting algorithm approximates traffic matrix estimates when the goal is a minimum mean-squared error; this makes our method lightweight in terms of computation overhead. A one-step error bound is provided for PamTram that bounds the average error for the worst scenario. We validate our method using data from Sprint's European Tier-1 IP backbone network and demonstrate its consistent improvement over previous methods.Keywords
This publication has 22 references indexed in Scilit:
- Maximum entropy models: convergence rates and applications in dynamic system monitoring2004
- Maximum pseudo likelihood estimation in network tomographyIEEE Transactions on Signal Processing, 2003
- Fast accurate computation of large-scale IP traffic matrices from link loads2003
- Network tomography: an iterative Bayesian analysis2003
- Time-Varying Network Tomography: Router Link DataJournal of the American Statistical Association, 2000
- Spline Models for Observational Data1990
- $I$-Divergence Geometry of Probability Distributions and Minimization ProblemsThe Annals of Probability, 1975
- Generalized Iterative Scaling for Log-Linear ModelsThe Annals of Mathematical Statistics, 1972
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948
- On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are KnownThe Annals of Mathematical Statistics, 1940