Simplifying the synthesis of internet traffic matrices

ABSTRACT

A recent paper [8] presented methods for several steps along the road to synthesis of realistic traffic matrices. Such synthesis is needed because traffic matrices are a crucial input for testing many new networking algorithms, but traffic matrices themselves are generally kept secret by providers. Furthermore, even given traffic matrices from a real network, it is difficult to realistically adjust these to generate a range of scenarios (for instance for different network sizes). This note is concerned with the first step presented in [8]: generation of a matrix with similar statistics to that of a real traffic matrix. The method applied in [8] is based on fitting a large number of distributions, and finding that the log-normal distribution appears to fit most consistently. Best fits (without some intuitive explanation for the fit) are fraught with problems. How general are the results? How do the distribution parameters relate? This note presents a simpler approach based on a gravity model. Its simplicity provides us with a better understanding of the origins of the results of [8], and this insight is useful, particularly because it allows one to adapt the synthesis process to different scenarios in a more intuitive manner. Additionally, [8] measures the quality of its fit to the distribution's body. This note shows that the tails of the distributions are less heavy than the log-normal distribution (a counterintuitive result for Internet traffic), and that the gravity model replicates these tails more accurately.

REFERENCES

• 1: J. Cao, D. Davis, S. V. Wiel, and B. Yu. Time-varying network tomography. J. Amer. Statist. Assoc, 95(452):1063--1075, 2000.
• 2: 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]
• 3: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Communications Magazine, 40(10):118--124, October 2002.
• 4: J. Kowalski and B. Warfield. Modeling traffic demand between nodes in a telecommunications network. In ATNAC'95, 1995.
• 5: Anukool Lakhina , Mark Crovella , Christophe Diot, Diagnosing network-wide traffic anomalies, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 6: 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
• 7: 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
• 8: Antonio Nucci , Ashwin Sridharan , Nina Taft, The problem of synthetically generating IP traffic matrices: initial recommendations, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070876]
• 9: R. B. Potts and R. M. Oliver. Flows in Transportation Networks. Academic Press, 1972.
• 10: P. Pyhnen. A tentative model for the volume of trade between countries. Weltwirtsch. Arch., 90:93--100, 1963.
• 11: M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang. Experience in measuring Internet backbone traffic variability: Models, metrics, measurements and meaning. In ITC-18, pp. 379--388, Berlin, 2003.
• 12: 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]
• 13: C. Tebaldi and M. West. Bayesian inference on network traffic using link count data. J. Amer. Statist. Assoc, 93(442):557--576, 1998.
• 14: J. Tinbergen. Shaping the world economy: Suggestions for an International economic policy. The Twentieth Century Fund, 1962.
• 15: Y. Vardi. Network tomography: estimating source-destination traffic intensities from link data. J. Am. Statist. Assoc., 91:365--377, 1996.
• 16: 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
• 17: Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An information-theoretic approach to traffic matrix estimation.

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

Keywords:
topology, traffic characterization, traffic matrices