Traffic matrix estimation on a large IP backbone: a comparison on real data

ABSTRACT

This paper considers the problem of estimating the point-to-point traffic matrix in an operational IP backbone. Contrary to previous studies, that have used a partial traffic matrix or demands estimated from aggregated Netflow traces, we use a unique data set of complete traffic matrices from a global IP network measured over five-minute intervals. This allows us to do an accurate data analysis on the time-scale of typical link-load measurements and enables us to make a balanced evaluation of different traffic matrix estimation techniques. We describe the data collection infrastructure, present spatial and temporal demand distributions, investigate the stability of fan-out factors, and analyze the mean-variance relationships between demands. We perform a critical evaluation of existing and novel methods for traffic matrix estimation, including recursive fanout estimation, worst-case bounds, regularized estimation techniques, and methods that rely on mean variance relationships. We discuss the weaknesses and strengths of the various methods, and highlight differences in the results for the European and American subnetworks.

REFERENCES

• 1: H. Abrahamsson, J. Alonso, B. Ahlgren, A. Andersson, and P. Kreuger, "A multi path routing algorithm for IP networks based on flow optimisation," in From QoS Provisioning to QoS Charging -- Third COST 263 International Workshop on Quality of Future Internet Services, QoFIS 2002 and Second Interntational Workshop on Internet Charging and QoS Technologies, ICQT 2002, B. Stiller, M. Smirnow, M. Karsten, and P. Reichl, Eds., Zurich, Switzerland, Oct. 2002, pp. 135--144, Springer, LNCS 2511.
• 2: A. Sridarhan, R. Guerin, and C. Diot, "Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks," in Proc. of IEEE INFOCOM 2003, San Francisco, USA, November 2003.
• 3: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 4: Matthew Roughan , Mikkel Thorup , Yin Zhang, Traffic engineering with estimated traffic matrices, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948237]
• 5: J. Cao, D. Davis, S. Vander Wiel, and B. Yu, "Time-varying network tomography: router link data," Journal of Americal Statistical Association, vol. 95, pp. 1063--1075, 2000.
• 6: 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
• 7: A. Medina, C. Fraleigh, N. Taft, S. Bhattacharyya, and C. Diot, "A Taxonomy of IP Traffic Matrices," in SPIE ITCOM: Scalability and Traffic Control in IP Networks II, Boston, Aug. 2002.
• 8: J. Kruithof, "Telefoonverkeersrekening," De Ingenieur, vol. 52, no. 8, pp. E15--E25, 1937.
• 9: Y. Vardi, "Network tomography: Estimating source-destination traffic intensities from link data," Journal of the Americal Statistical Association, vol. 91, no. 433, pp. 365--377, March 1996.
• 10: C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," Journal of the American Statistical Association, vol. 93, no. 442, pp. 557--576, June 1998.
• 11: S. Vaton and A. Gravey, "Network tomography: an iterative bayesian analysis," in Proc. ITC 18, Berlin, Germany, August 2003.
• 12: 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
• 13: 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]
• 14: A. Nucci, R. Cruz, N. Taft, and C. Diot, "Design of IGP link weight changes for estimation of traffic matrices," in Proc. IEEE INFOCOM, Hong Kong, March 2004.
• 15: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.257-270, August 28-September 01, 2000, Stockholm, Sweden
• 16: R. S. Krupp, "Properties of Kruithof's projection method," The Bell System Technical Journal, vol. 58, no. 2, pp. 517--538, February 1979.
• 17: A. Medina, K. Salamatian, N. Taft, I. Matta, Y. Tsang, and C. Diot, "On the convergence of statistical techniques for inferring network traffic demands," Tech. Rep. BUCS-2003-003, Boston University, Computer Science, USA, February 2003.
• 18: G. K. Zipf, "Somde determinants of the circulation of information," American Journal of Psychology, vol. 59, pp. 401--421, 1946.
• 19: J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in Australian Telecommunications and Networks Conference, Sydney, Australia, December 1995.
• 20: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 21: I. Csiszár and G. Tusnády, "Information geometry and alternating minimization procedures," Statistics and Decisions, Suppl. 1, vol. Supplement Issue No. 1, pp. 205--237, 1984.
• 22: I. Csiszár, "Why least squares and maximum entropy? - an axiomatic approach to inverse problems," The Annals of Statistics, vol. 19, pp. 2033--2066, December 1991.
• 23: X. Xiao, A. Hannan, B. Bailey, and L. M. Ni, "Traffic engineering with MPLS in the internet," IEEE Network, vol. 14, no. 2, pp. 28--33, March-April 2000.
• 24: Cariden, Inc., Mountain View, CA, MATE, 2004, http://www.cariden.com.
• 25: R. Morris and D. Lin, "Variance of aggregated web traffic," in Proc. IEEE INFOCOM, Tel Aviv, Israel, March 2000, pp. 360--366.
• 26: M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," Signal Processing Magazine, vol. 19, no. 3, pp. 47--65, May 2002.
• 27: Supratik Bhattacharyya , Christophe Diot , Jorjeta Jetcheva, Pop-level and access-link-level traffic dynamics in a tier-1 POP, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505209]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Measurement, Performance

Keywords:
MPLS, SNMP, optimization, traffic matrix estimation