Towards a meaningful MRA of traffic matrices

ABSTRACT

Most research on traffic matrices (TM) has focused on finding models that help with inference, but not with other important tasks such as synthesis of TMs, traffic prediction, or anomaly detection. In this paper we approach the problem of a general model for traffic matrices, and argue that such a model must be sparse, i.e., have a small number of parameters in comparison to the size of the TM. A Multi-Resolution Analysis (MRA) of TMs can provide such a sparse representation. The Diffusion Wavelet (DW) transform is a good choice as a MRA tool here, because it inherently adapts to the structure of the underlying network. The paper describes our construction of the two-dimensional version of the DW transform and shows how to use it for our proposed MRA of TMs. The results obtained with operational networks confirm the sparseness of the DW-based TM analysis approach and its applicability to other TM-related tasks.

REFERENCES

• 1: D. L. Alderson, H. Chang, M. Roughan, S. Uhlig, and W. Willinger. The many facets of Internet topology and traffic. Networks and Heterogeneous Media, 1(4):569--600, December 2006.
• 2: J. Cao, D. Davis, S. V. Wiel, and B. Yu. Time-varying network tomography. Journal of the American Statistical Association, 95(452):1063--1075, 2000.
• 3: F. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, February 1997.
• 4: Mark Coates , Yvan Pointurier , Michael Rabbat, Compressed network monitoring for ip and all-optical networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298340]
• 5: R. R. Coifman and M. Maggioni. Diffusion Wavelets. Applied and Computational Harmonic Analysis, 21(1):53--94, July 2006.
• 6: M. Crovella and E. Kolaczyk. Graph wavelets for spatial traffic analysis. In Proceedings of IEEE Infocom, pages 1848--1857, Apr. 2003.
• 7: J. C. Doyle, D. Alderson, L. Li, S. H. Low, M. Roughan, S. Shalunov, R. Tanaka, and W. Willinger. The "robust yet fragile" nature of the Internet. In Procs. of the Natl. Academy of Sciences, volume 102(40), pages 14123--14475, Oct. 2005.
• 8: 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]
• 9: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Comm. Magazine, 40(10):118--124, Oct. 2002.
• 10: Anukool Lakhina , Mark Crovella , Christophe Diot, Diagnosing network-wide traffic anomalies, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 11: Anukool Lakhina , Konstantina Papagiannaki , Mark Crovella , Christophe Diot , Eric D. Kolaczyk , Nina Taft, Structural analysis of network traffic flows, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
• 12: Sridhar Mahadevan , Mauro Maggioni, Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes, The Journal of Machine Learning Research, 8, p.2169-2231, 12/1/2007
• 13: S. Mallat. A Wavelet Tour of Signal Processing. Academic Press, 1999.
• 14: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 15: 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]
• 16: 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 Procs. of ITC-18, pages 379--388, Berlin, Germany, 2003.
• 17: 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]
• 18: Steve Uhlig , Bruno Quoitin , Jean Lepropre , Simon Balon, Providing public intradomain traffic matrices to the research community, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111341]
• 19: Y. Vardi. Network tomography: estimating source-destination traffic intensities from link data. J. of the Am. Statistical Association, 91:365--377, 1996.
• 20: 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
• 21: 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]

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

General Terms:
Algorithms, Measurement

Keywords:
diffusion wavelets, multi-resolution analysis, traffic characterization, traffic matrices