Paper Info
Title
A fast lightweight approach to origin-destination IP traffic estimation using partial measurements
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.
Year
DOI
Venue
2006
10.1109/TIT.2006.874412
IEEE Transactions on Information Theory
Keywords
Field
DocType
game theory,flow measurement,minimum mean square error,minimax,iterative proportional fitting
Minimax,Mathematical optimization,Telecommunications network,Iterative method,Computer science,Minimum mean square error,Iterative proportional fitting,Backbone network,Internet traffic,Computation
Journal
Volume
Issue
ISSN
52
6
0018-9448
Citations 
PageRank 
References 
22
0.98
11
Authors
3
Name
Order
Citations
PageRank
Gang Liang1272.02
Nina Taft22109154.92
Bin Yu31984241.03