Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Y.Vardi, "Estimating Source-Destination Traffic Intensities from Link Data", Journal of the the American Statistical Association, 91(433), March 1996.
• 2: C.Tebaldi and M.West, "Bayesian Inference of Network Traffic Using Link Count Data", Journal of the the American Statistical Association, 93(442), June 1998.
• 3: J.Cao, D.Davis, S.Vander Weil, and B.Yu, "Time-Varying Network Tomography: Router Link Data", Journal of the the American Statistical Association, 95(452), 2000.
• 4: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 6: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 7: Gang Liang, Bin Yu, "Pseudo Likelihood Estimation in Nework Tomography", IEEE Infocom, San Francisco, CA, March 2003.
• 8: A. Nucci, R. Cruz, N. Taft and C. Diot, "Design of IGP Link Weight Changes for Estimation of Traffic Matrices", IEEE Infocom, Hong Kong, China, March 2004.
• 9: 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]
• 10: Henry Stark , John W. Woods, Probability, random processes, and estimation theory for engineers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Performance, Theory

Keywords:
network tomography, traffic matrix estimation