Matthew Roughan

Traffic Matrices

A Traffic Matrix -- a matrix giving the traffic volumes between origin and destination in a network -- has tremendously potential utility for IP network capacity planning and management.

There are various interesting problems revolving around these matrices, for instance: , traffic matrices are often hard to measure directly in large operational IP networks. On the other hand, link load measurements are readily available in IP networks. This type of problem (commonly called Network Tomography) has been much researched in resent years. Tomo-gravity is a method for practical and rapid estimation of traffic matrices in large IP networks from link load measurements, augmented by readily available network and routing configuration information.

Tomo-gravity, combines the better aspects of transportation modeling (gravity models) with tomo-graphic methods such as applied in medical imaging (CAT scans) and seismology. It has a firm theoretical foundation in information theory, and we have shown that it is is remarkably fast, accurate, flexible and robust on test data from AT&T's North American backbone network, and also on other network topologies obtained via the Rocketfuel project. Note that the method has been implemented and actively is used by AT&T who run one of the largest ISPs in the world.

This page currently provides references to our papers and presentations on traffic matrix estimation, characterization, anomaly detection, and synthesis. The SAMSI tutorial below provides an introduction to TM estimation and the method, and is available in HTML and PDF. In the future we plan to expand this page with examples, data, and maybe a TM estimation portal. Please see below for links to our papers on traffic matrix estimation and its applications.

Our Papers

• Spatio-Temporal Compressive Sensing and Internet Traffic Matrices Yin Zhang, Matthew Roughan, Walter Willinger, and Lili Qui, in ACM Sigcomm, pp.267--278, Barcellona, August 2009. [PDF]
• Robust Network Planning, Matthew Roughan, Chapter 5 of the Guide to Reliable Internet Services and Applications, Editors: Charles R. Kalmanek, Supid Misra, and Richard Yang, Springer, to appear 2009. [PDF]
• The Measurement Paradox in Valiant Network Design, Matthew Roughan, accepted to appear in Research Letters in Communications. [PDF]
• Internet Traffic and Multiresolution Analysis, Y. Zhang, Z. Ge, S. Diggavi, Z.M. Mao, M. Roughan, V. Vaishampayan, W. Willinger, Y. Zhang, IMS Collections, Volume 4, "Markov Processes and Related Topics: A Festschrift for Thomas G. Kurtz," pp. 215--234, Stewart N. Ethier, Jin Feng, Richard H. Stockbridge, Editors, Institute for Mathematical Statistics, 2008. [PDF].
• Towards a meaningful MRA analysis of traffic matrices, David Rincon, Matthew Roughan, Walter Willinger, ACM SIGCOMM Internet Measurement Conference, pp. 331-336, Vouliagmeni, Greece, October 20 - 22, 2008. [PDF]
• The Many Facets of Internet Topology and Traffic, David Alderson, Hyunseok Chang, Matthew Roughan, Steve Uhlig, and Walter Willinger, Networks and Heterogeneous Media, 1, (4), pp. 569--600, December 2006. Networks and Heterogeneous Media. [PDF]
• Simplifying the synthesis of Internet traffic matrices, Matthew Roughan, CCR Editorial, Vol.35, No.5, pp.93-96, October 2005, [PDF]
• Network Anomography, Yin Zhang, Zihui Ge, Albert Greenberg, Matthew Roughan, ACM/Usenix Internet Measurement Conference, Berkeley, CA, USA, 2005. [PDF]
• Simplifying the synthesis of Internet traffic matrices, Matthew Roughan, CCR Editorial, Vol.35, No.5, pp.93-96, October 2005, [PDF]
• Traffic Matrix Reloaded: Impact of Routing Changes,Renata Teixeira, Nick Duffield, Jennifer Rexford and Matthew Roughan, the Workshop on Passive and Active Measurements (PAM), Boston, USA, 2005. [PDF]
• Estimating Point-to-Point and Point-to-Multipoint Traffic Matrices: An Information-Theoretic Approach, Yin Zhang, Matthew Roughan, Carsten Lund and David Donoho, IEEE/ACM Transactions on Networking, 13 (5), pp.947-960, October, 2005. [PDF]
• First Order Characterization of Internet Traffic Matrices,Matthew Roughan, invited paper at the 55th Session of the International Statistics Institute}, Sydney, Australia, April, 2005. [PDF tech report] [Presentation]
• An Information-Theoretic Approach to Traffic Matrix Estimation, Yin Zhang, Matthew Roughan, Carsten Lund, and David Donoho, ACM SIGCOMM 2003. [PS.GZ] [PDF]
• Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads, Yin Zhang, Matthew Roughan, Nick Duffield and Albert Greenberg, ACM SIGMETRICS 2003. [PS.GZ] [PDF]
• Traffic Engineering with Estimated Traffic Matrices, Matthew Roughan, Mikkel Thorup, and Yin Zhang, ACM SIGCOMM Internet Measurement Conference 2003. [PDF]
• Performance of Estimated Traffic Matrices in Traffic Engineering, Matthew Roughan, Mikkel Thorup, and Yin Zhang, poster in ACM SIGMETRICS 2003. [PS.GZ] [PDF] Full technical report (TD-5KYK6Z) [PDF]

Presentations

• Spatio-Temporal Compressive Sensing and Internet Traffic Matrices Yin Zhang, Matthew Roughan, Walter Willinger, and Lili Qui, in ACM Sigcomm, pp.267--278, Barcellona, August 2009. [PDF]
• Towards a meaningful MRA analysis of traffic matrices, David Rincon, Matthew Roughan, Walter Willinger, ACM SIGCOMM Internet Measurement Conference, pp. 331-336, Vouliagmeni, Greece, October 20 - 22, 2008 [PPT].
• Network Anomography, Informs, 2006, Hong-Kong. [PPT]
• Network Anomography, ACM/Usenix Internet Measurement Conference, (see paper above), 2005. [PPT]
• Network Anomography, Large-Scale Network Inference (LSNI) Workshop at ACM Sigmetrics, Banff, Canada, 2005. [PPT]
• Traffic Engineering with Estimated Traffic Matrices, ACM SIGCOMM Internet Measurement Conference presentation, 2003 (see paper above). [PDF] [PPT]
• How to compute accurate traffic matrices for your network in seconds, NANOG 29, Chicago, USA, Oct 2003 [PDF] [HTML]
• Traffic Matrix Estimation Tutorial, SAMSI Workshop on Internet Tomography [PDF]
• ACM SIGMETRICS presentation (see paper above), [PPT]
• ACM SIGCOMM presentation (see paper above), [PPT]
• Information, Gravity and Traffic Matrices, invited talk at the NISS Internet Tomography Technology Workshop, March 28th, North Carolina, 2003. [PDF]
• Estimation of point-to-multipoint demands matrices from SNMP link traffic, Matthew Roughan and Yin Zhang, invited talk at INTIMATE 2003: INternet TraffIc MATrices Estimation Workshop, Paris, France, June 16-17, 2003. [PDF]
• Computing traffic matrices from SNMP link data, Matthew Roughan, Yin Zhang, Nick Duffield and Albert Greenberg invited presentation at the Network Modeling and Simulation Summer Workshop, Dartmouth, Hanover, July 2002.
• Network Tomography and Internet Traffic Matrices Matthew Roughan, invited presentation at the Industrial Maths Initiative (IMI), Korea, 2004.[PDF]

Links to other people's papers I know this bit is very incomplete -- send me details I shall try to get this up to date. And there isn't any particular order at present.

• The Mythical Traffic Matrix, C. Dovrolis, WIRED Workshop on Internet Routing and Design, 2006.
• An Independent-Connection Model for Traffic Matrices, V. Erramilli, M. Crovella and N. Taft. In ACM Internet Measurement Conference (IMC). Rio de Janeiro, Brazil. October, 2006.
• Traffic Matrix Estimation for Traffic Engineering
• Traffic Matrices: Balancing Measurements, Inference and Modeling, A. Soule, A. Lakhina, N. Taft, K. Papagiannaki, K. Salamatian, A. Nucci, M. Crovella and C. Diot. ACM Sigmetrics. June, 2005.
• Traffic Matrix Estimation: Existing Techniques and New Directions, A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, C. Diot. ACM SIGCOMM. August 2002
• A Taxonomy of IP Traffic Matrices, A. Medina, C. Fraleigh, N. Taft, S. Bhattacharyya and C. Diot, SPIE ITCOM: Scalability and Traffic Control in IP Networks II. August 2002.
• Finding Critical Traffic Matrices Yin Zhang, Zihui Ge, DSN '05: Proceedings of the 2005 International Conference on Dependable Systems and Networks, 2005 DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2005.51.
• Best Practices for Determining Traffic Matrices in IP Networks V 4.0 Tutorial, NANOG 43
• The Problem of Synthetically Generating IP Traffic Matrices: Initial Recommendations, Antonio Nucci, Ashwin Sridharan and Nina Taftm ACM Computer Communications Review (CCR). July, 2005
• Traffic Matrix Tracking Using Kalman Filters, A. Soule, K. Salamatian, A. Nucci and N. Taft, ACM SIGMETRICS Performance Evaluation Review (PER) Vol. 33, Issue 3. Special issue on the First ACM Sigmetrics Workshop on Large Scale Networks Inference (LSNI). December, 2005.
• Domination Between Traffic Matrices, Gianpaolo Oriolo, Mathematics of Operations Research, Vol. 33, No. 1, February 2008, pp. 91-96 DOI: 10.1287/moor.1070.0280
• Traffic matrix estimation on a large IP backbone, A Gunnar, Mikael Johansson, and Thomas Telkamp, Internet Measurement Conference 2004.
• Telefoonverkeersrekening, J. Kruithof, De Ingenieur, vol. 52, no. 8, pp. E15--E25, 1937
• An Empirical Approach to Modeling Inter-AS Traffic Matrices, Hyunseok Chang, Sugih Jamin, Z. Morley Mao, and WalterWillinger, Internet Measurement Conference 2005.
• Blind maximum likelihood estimation of traffic matrices under long-range dependent traffic, P.L. Contia, L. De Giovannib and M. Naldic, Computer Networks, doi:10.1016/j.comnet.2010.04.012.
• Time-Varying Network Tomography: Router Link Data, Jin Cao, Drew Davis, Scott Vander Wiel and Bin Yu, Journal of the American Statistical Association, Vol. 95, No. 452 (Dec., 2000), pp. 1063-1075.
• Network tomography: estimating source-destination traffic intensities from link data, Y. Vardi, Journal of the American Statistical Association 91 (1996), pp. 365-377.
• Iterative Bayesian estimation of network traffic matrices in the case of Bursty flows, S. Vaton, A. Gravey, Internet Measurement Workshop IMW2002, Marseille, 2002

Data: The goal is to set of some traffic matrix datasets here to make them a little easier for people to get at. Tell me about your dataset, and I will provide a link.

• GEANT Data: see Providing public intradomain traffic matrices to the research community, S Uhlig, B Quoitin, J Lepropre, S Balon, ACM SIGCOMM Computer Communications Review, 2006.
• Abilene data:

Code: A couple of things need to go here, in particular synthesis and inference code. Send me email to give me a push to get it done.

Matthew Roughan

Last modified: Wed Mar 30 10:55:38 2011