The problem of synthetically generating IP traffic matrices: initial recommendations

ABSTRACT

There exist a wide variety of network design problems that require a traffic matrix as input in order to carry out performance evaluation. The research community has not had at its disposal any information about how to construct realistic traffic matrices. We introduce here the two basic problems that need to be addressed to construct such matrices. The first is that of synthetically generating traffic volume levels that obey spatial and temporal patterns as observed in realistic traffic matrices. The second is that of assigning a set of numbers (representing traffic levels) to particular node pairs in a given topology. This paper provides an in-depth discussion of the many issues that arise when addressing these problems. Our approach to the first problem is to extract statistical characteristics for such traffic from real data collected inside two large IP backbones. We dispel the myth that uniform distributions can be used to randomly generate numbers for populating a traffic matrix. Instead, we show that the lognormal distribution is better for this purpose as it describes well the mean rates of origin-destination flows. We provide estimates for the mean and variance properties of the traffic matrix flows from our datasets. We explain the second problem and discuss the notion of a traffic matrix being well-matched to a topology. We provide two initial solutions to this problem, one using an ILP formulation that incorporates simple and well formed constraints. Our second solution is a heuristic one that incorporates more challenging constraints coming from carrier practices used to design and evolve topologies.

REFERENCES

• 1: 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.
• 2: 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
• 3: 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
• 4: The Abilene Network of Internet2 Community, "Abilene Observatory", http://abilene.internet2.edu/.
• 5: 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]
• 6: 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.
• 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: A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft and C. Diot, "IGP Link Weight Assignment for Transient Link Failures", The 18th International Teletraffic Congress (ITC), Germany, September 2003.
• 10: Augustin Soule , Antonio Nucci , Rene Cruz , Emilio Leonardi , Nina Taft, How to identify and estimate the largest traffic matrix elements in a dynamic environment, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 11: Konstantina Papagiannaki , Nina Taft , Anukool Lakhina, A distributed approach to measure IP traffic matrices, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028808]
• 12: B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS Weights in a Changing World". IEEE Journal on Selected Areas in Communications, vol. 20, no 4., 2002.
• 13: 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]
• 14: Anukool Lakhina , Konstantina Papagiannaki , Mark Crovella , Christophe Diot , Eric D. Kolaczyk , Nina Taft, Structural analysis of network traffic flows, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 15: E. W. Zegura, "GT-ITM: Georgia Tech Internetwork Topology Models (Software)", Georgia Tech, http://www.cc.gatech.edu/fac/Ellen.Zegura/gt-itm/gt-itm/tar.gz, 1996.
• 16: Anders Gunnar , Mikael Johansson , Thomas Telkamp, Traffic matrix estimation on a large IP backbone: a comparison on real data, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028807]
• 17: A. Medina, A. Lakhina, I. Matta, and J. Byers, "BRITE: Boston University Representative Internet Topology Generator", Boston University, http://cs-www.bu.edu/brite, April, 2001.
• 18: Augustin Soule , Anukool Lakhina , Nina Taft , Konstantina Papagiannaki , Kave Salamatian , Antonio Nucci , Mark Crovella , Christophe Diot, Traffic matrices: balancing measurements, inference and modeling, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 19: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 20: John A. Rice, "Mathematical Statistics and Data Analysis", Wadsworth & Brooks/Cole. Chapter 9. 1988.
• 21: A. Nucci, A. Sridharan and N. Taft, "The Problem of Synthetically Generating IP Traffic Matrices: Initial Recommendations",Sprint Technical Report RR05-ATL-1498, May 2005. Available at http://ipmon.sprintlabs.com.
• 22: A. Nucci, N. Taft, C. Barakat and P. Thiran, "Controlled Use of Excess Backbone Bandwidth for Providing New Services in IP-over-WDM Networks", IEEE Journal of Selected Areas in Communications. Nov. 2004.
• 23: 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]
• 24: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

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

  H. Information Systems
  H.1 MODELS AND PRINCIPLES

General Terms:
Design, Measurement, Performance

Keywords:
distribution fitting, hypothesis, internet traffic matrices, testing, topology, traffic characterization