Traffic matrix estimation: existing techniques and new directions

ABSTRACT

Very few techniques have been proposed for estimating traffic matrices in the context of Internet traffic. Our work on POP-to-POP traffic matrices (TM) makes two contributions. The primary contribution is the outcome of a detailed comparative evaluation of the three existing techniques. We evaluate these methods with respect to the estimation errors yielded, sensitivity to prior information required and sensitivity to the statistical assumptions they make. We study the impact of characteristics such as path length and the amount of link sharing on the estimation errors. Using actual data from a Tier-1 backbone, we assess the validity of the typical assumptions needed by the TM estimation techniques. The secondary contribution of our work is the proposal of a new direction for TM estimation based on using choice models to model POP fanouts. These models allow us to overcome some of the problems of existing methods because they can incorporate additional data and information about POPs and they enable us to make a fundamentally different kind of modeling assumption. We validate this approach by illustrating that our modeling assumption matches actual Internet data well. Using two initial simple models we provide a proof of concept showing that the incorporation of knowledge of POP features (such as total incoming bytes, number of customers, etc.) can reduce estimation errors. Our proposed approach can be used in conjunction with existing or future methods in that it can be used to generate good priors that serve as inputs to statistical inference techniques.

REFERENCES

• 1: M. Ben-Akiva and S. Lerman. Discrete Choice Analysis: Theory and Application to Travel Demand. MIT Press, 1985.
• 2: S. Bhattacharyya, C. Diot, J. Jetcheva, and N. Taft. Geographical and Temporal Characteristics of Inter-POP Flows: View from a Single POP. European Transactions on Telecommunications, January/February 2002.
• 3: J. Cao, D. Davis, S. Vander Weil, and B. Yu. Time-Varying Network Tomography. J. of the American Statistical Association., 2000.
• 4: W.E. Deming and F.F. Stephan. On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Annals of Mathematical Statistics, pages 427--444, 1940.
• 5: S. Erlander and N.F. Stewart. The Gravity Model in Transportation Analysis -- Theory and Applications. 1990.
• 6: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 7: O. Goldschmidt. ISP Backbone Traffic Inference Methods to Support Traffic Engineering. In Internet Statistics and Metrics Analysis (ISMA) Workshop, San Diego, CA, December 2000.
• 8: L. Rüschendorf. Convergence of the iterative proportional fitting procedure. Annals of Statistics, pages 1160--1174, 1995.
• 9: G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 1993.
• 10: J. Swait. Probabilistic Choice Set Information in Transportation Demand Models. Technical Report Ph.D. Thesis, MIT, Department of Civil and Environmental Engineering, 1959.
• 11: C. Tebaldi and M. West. Bayesian Inference of Network Traffic Using Link Count Data. J. of the American Statistical Association., pages 557--573, June 1998.
• 12: Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data. J. of the American Statistical Association., pages 365--377, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Measurement, Performance

Keywords:
statistical inference, traffic matrix estimation