Matthew Roughan
 
Home
Address
Network Anomaly Detection
Network Performance Measurement Bounds
Lecture notes etc.
CODE
Brief CV
Publications by date
Prob. Distributions
Some recent talks
Traffic Matrices

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
  • 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
  • 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]
Code
Data

Matthew Roughan

Last modified: Tue Jul 21 13:32:44 2009