Abstract
Traffic matrix estimation is well-studied, but in general has been treated simply as a statistical inference problem. In practice, however, network operators seeking traffic matrix information have a range of options available to them. Operators can measure traffic flows directly; they can perform partial flow measurement, and infer missing data using models; or they can perform no flow measurement and infer traffic matrices directly from link counts. The advent of practical flow measurement makes the study of these tradeoffs more important. In particular, an important question is whether judicious modeling, combined with partial flow measurement, can provide traffic matrix estimates that are signficantly better than previous methods at relatively low cost. In this paper we make a number of contributions toward answering this question. First, we provide a taxonomy of the kinds of models that may make use of partial flow measurement, based on the nature of the measurements used and the spatial, temporal, or spatio-temporal correlation exploited. We then evaluate estimation methods which use each kind of model. In the process we propose and evaluate new methods, and extensions to methods previously proposed. We show that, using such methods, small amounts of traffic flow measurements can have significant impacts on the accuracy of traffic matrix estimation, yielding results much better than previous approaches. We also show that different methods differ in their bias and variance properties, suggesting that different methods may be suited to different applications.
- S. Bhattacharyya, C. Diot, J. Jetcheva, and N. Taft. Geographical and Temporal Characteristics of Inter-POP Flows: View from a Single POP. In European Transactions on Telecommunications, February 2002.Google Scholar
- J. Cao, D. Davis, S. VanderWeil, and B. Yu. Time-Varying Network Tomography: Router Link Data. Journal of the the American Statistical Association, 95(452), 2000.Google ScholarCross Ref
- Cisco. NetFlow Services Solutions Guide, July 2001.Google Scholar
- A. Gunnar, M. Johansson, and T. Telkamp. Traffic Matrix Estimation on a Large IP Backbone - A Comparison on Real Data. In ACM Internet Measurement Conference, Taormina, Italy, October 2004. Google ScholarDigital Library
- A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. Kolaczyk, and N. Taft. Structural Analysis of Network Traffic Flows. In ACM Sigmetrics, New York, June 2004. Google ScholarDigital Library
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic Matrix Estimation: Existing Techniques and New Directions. In ACM SIGCOMM, Pittsburgh, USA, Aug. 2002. Google ScholarDigital Library
- A. Nucci, R. Cruz, N. Taft, and C. Diot. Design of IGP Link Weight Changes for Estimation of Traffic Matrices. In IEEE Infocom, Hong Kong, March 2004.Google ScholarCross Ref
- K. Papagiannaki, N. Taft, and A. Lakhina. A Distributed Approach to Measure Traffic Matrices. In ACM Internet Measurement Conference, Taormina, Italy, October 2004. Google ScholarDigital Library
- A. Soule, A. Nucci, E. Leonardi, R. Cruz, and N. Taft. How to Identify and Estimate the Largest Traffic Matrix Elements in a Dynamic Environment. In ACM Sigmetrics, New York, June 2004. Google ScholarDigital Library
- A. Soule, K. Salamatian, A. Nucci, and N. Taft. Traffic Matrix Tracking using Kalman Filtering. LIP6 Research Report RP-LIP6-2004-07-10, LIP6, 2004.Google Scholar
- Y. Vardi. Estimating Source-Destination Traffic Intensities from Link Data. Journal of the the American Statistical Association, March 1996.Google Scholar
- G. Varghese and C. Estan. The Measurement Manifesto. In HotNets-II, Nov. 2003.Google Scholar
- Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg. Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads. In ACM Sigmetrics, San Diego, CA, 2003. Google ScholarDigital Library
- Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An Information Theoretic Approach to Traffic Matrix Estimation. In ACM SIGCOMM, Karlsruhe, Germany, August 2003. Google ScholarDigital Library
Index Terms
- Traffic matrices: balancing measurements, inference and modeling
Recommendations
Traffic matrices: balancing measurements, inference and modeling
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsTraffic matrix estimation is well-studied, but in general has been treated simply as a statistical inference problem. In practice, however, network operators seeking traffic matrix information have a range of options available to them. Operators can ...
Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsThe traffic volume between origin/destination (OD) pairs in a network, known as traffic matrix, is essential for efficient network provisioning and traffic engineering. Existing approaches of estimating the traffic matrix, based on statistical inference ...
Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices
Performance evaluation reviewThe traffic volume between origin/destination (OD) pairs in a network, known as traffic matrix, is essential for efficient network provisioning and traffic engineering. Existing approaches of estimating the traffic matrix, based on statistical inference ...
Comments