How to identify and estimate the largest traffic matrix elements in a dynamic environment
Authors:
Open Access
- 1 June 2004
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 32 (1) , 73-84
Abstract
In this paper we investigate a new idea for traffic matrix estimation that makes the basic problem less under-constrained, by deliberately changing the routing to obtain additional measurements. Because all these measurements are collected over disparate time intervals, we need to establish models for each Origin-Destination (OD) pair to capture the complex behaviours of internet traffic. We model each OD pair with two components: the diurnal pattern and the fluctuation process. We provide models that incorporate the two components above, to estimate both the first and second order moments of traffic matrices. We do this for both stationary and cyclo-stationary traffic scenarios. We formalize the problem of estimating the second order moment in a way that is completely independent from the first order moment. Moreover, we can estimate the second order moment without needing any routing changes (i.e., without explicit changes to IGP link weights). We prove for the first time, that such a result holds for any realistic topology under the assumption of minimum cost routing and strictly positive link weights . We highlight how the second order moment helps the identification of the top largest OD flows carrying the most significant fraction of network traffic. We then propose a refined methodology consisting of using our variance estimator (without routing changes) to identify the top largest flows, and estimate only these flows. The benefit of this method is that it dramatically reduces the number of routing changes needed. We validate the effectiveness of our methodology and the intuitions behind it by using real aggregated sampled netflow data collected from a commercial Tier-1 backbone.Keywords
This publication has 7 references indexed in Scilit:
- An information-theoretic approach to traffic matrix estimation2003
- Maximum pseudo likelihood estimation in network tomographyIEEE Transactions on Signal Processing, 2003
- Fast accurate computation of large-scale IP traffic matrices from link loads2003
- Traffic matrix estimation2002
- Deriving traffic demands for operational IP networks: methodology and experienceIEEE/ACM Transactions on Networking, 2001
- Time-Varying Network Tomography: Router Link DataJournal of the American Statistical Association, 2000
- Network Tomography: Estimating Source-Destination Traffic Intensities from Link DataJournal of the American Statistical Association, 1996