Yin Zhang
Matthew Roughan
ABSTRACT
Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availability and accuracy of traffic matrices. However, in practice it is challenging to reliably measure traffic matrices. Missing values are common. This observation brings us into the realm of compressive sensing, a generic technique for dealing with missing values that exploits the presence of structure and redundancy in many real-world systems. Despite much recent progress made in compressive sensing, existing compressive-sensing solutions often perform poorly for traffic matrix interpolation, because real traffic matrices rarely satisfy the technical conditions required for these solutions.
To address this problem, we develop a novel spatio-temporal compressive sensing framework with two key components: (i) a new technique called Sparsity Regularized Matrix Factorization (SRMF) that leverages the sparse or low-rank nature of real-world traffic matrices and their spatio-temporal properties, and (ii) a mechanism for combining low-rank approximations with local interpolation procedures. We illustrate our new framework and demonstrate its superior performance in problems involving interpolation with real traffic matrices where we can successfully replace up to 98% of the values. Evaluation in applications such as network tomography, traffic prediction, and anomaly detection confirms the flexibility and effectiveness of our approach.
- The Abilene Observatory Data Collections. http://abilene.internet2.edu/observatory/data-collections.html.Google Scholar
- D. 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, 2006.Google ScholarCross Ref
- P. Barford, J. Kline, D. Plonka, and A. Ron. A signal analysis of network traffic anomalies. In Proc. of ACM SIGCOMM Internet Measurement Workshop, 2002. Google ScholarDigital Library
- R. Bell, Y. Koren, and C. Volinksy. Chasing the $1,000,000: How we won the Netflix progress prize. Statistical Computing and Graphics, 18(2), 2007.Google Scholar
- E. Candes and B. Recht. Exact matrix completion via convex optimization. preprint.Google Scholar
- E. Candes and T. Tao. Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. on Information Theory, 52(12):5406--5425, 2006. Google ScholarDigital Library
- F. R. K. Chung. Spectral Graph Theory. CBMS Lecture Notes. AMS Publications, 1996.Google ScholarCross Ref
- D. Donoho. Compressed sensing. IEEE Trans. on Information Theory, 52(4):1289--1306, 2006. Google ScholarDigital Library
- V. Erramilli, M. Crovella, and N. Taft. An independent-connection model for traffic matrices. In Proc. of Internet Measurement Conference (IMC), 2006. Google ScholarDigital Library
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True. Deriving traffic demands for operational IP networks: Methodology and experience. IEEE/ACM Transactions on Networking, pages 265--279, 2001. Google ScholarDigital Library
- B. Fortz and M. Thorup. Optimizing OSPF/IS-IS weights in a changing world. IEEE JSAC Special Issue on Advances in Fundamentals of Network Management, Spring 2002.Google Scholar
- L. Huang, X. Nguyen, M. Garofalakis, J. Hellerstein, M. Jordan, M. Joseph, and N. Taft. Communication-efficient online detection of network--wide anomalies. In Proc. of IEEE INFOCOM, 2007.Google ScholarDigital Library
- A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In Proc. of ACM SIGCOMM, 2004. Google ScholarDigital Library
- A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. D. Kolaczyk, and N. Taft. Structural analysis of network traffic flows. In Proc. of ACM SIGMETRICS / Performance, 2004. Google ScholarDigital Library
- D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Proc. of Neural Information Processing Systems (NIPS), pages 556--562, 2000.Google Scholar
- Y. Mao and L. K. Saul. Modeling distances in large-scale networks by matrix factorization. In Proc. of Internet Measurement Conference (IMC), 2004. Google ScholarDigital Library
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic matrix estimation: Existing techniques and new directions. In Proc. of ACM SIGCOMM, 2002. Google ScholarDigital Library
- I. Norros. A storage model with self-similar input. Queueing Systems, 16:387--396, 1994.Google ScholarCross Ref
- B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization. preprint.Google Scholar
- B. Recht, W. Xu, and B. Hassibi. Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization. In Proc. of 47th IEEE Conference on Decision and Control, 2008.Google ScholarCross Ref
- H. Ringberg, A. Soule, J. Rexford, and C. Diot. Sensitivity of PCA for traffic anomaly detection. In Proc. of ACM SIGMETRICS, 2007. Google ScholarDigital Library
- M. Roughan. Simplifying the synthesis of Internet traffic matrices. SIGCOMM Computer Communications Review, 35(5):93--96, 2005. Google ScholarDigital Library
- M. Roughan and J. Gottlieb. Large--scale measurement and modeling of backbone Internet traffic. In Proc. of SPIE ITCOM, 2002.Google Scholar
- M. Roughan, M. Thorup, and Y. Zhang. Traffic engineering with estimated traffic matrices. In Proc. of Internet Measurement Conference (IMC), 2003. Google ScholarDigital Library
- A. Soule, A. Lakhina, N. Taft, K. Papagiannaki, K. Salamatian, A. Nucci, M. Crovella, and C. Diot. Traffic matrices: Balancing measurements, inference and modeling. In Proc. of ACM SIGMETRICS, pages 362--373, 2005. Google ScholarDigital Library
- S. Uhlig, B. Quoitin, S. Balon, and J. Lepropre. Providing public intradomain traffic matrices to the research community. ACM SIGCOMM CCR, 36(1):83--86, 2006. Google ScholarDigital Library
- Y. Vardi. Network tomography. Journal of the Amer. Stat. Assoc., Mar. 1996.Google ScholarCross Ref
- G. Varghese and C. Estan. The measurement manifesto. In Proc. of 2nd Workshop on Hot Topics in Networks (HotNets-II), 2003.Google Scholar
- K. Xu, J. Chandrashekar, and Z.-L. Zhang. A first step toward understanding inter-domain routing dynamics. In Proc. of ACM SIGCOMM Workshop on Mining Network Data (MineNet), pages 207--212, 2005. Google ScholarDigital Library
- Y. Zhang, Z. Ge, M. Roughan, and A. Greenberg. Network anomography. In Proc. of Internet Measurement Conference (IMC), 2005. Google ScholarDigital Library
- Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg. Fast accurate computation of large-scale IP traffic matrices from link loads. In Proc. of ACM SIGMETRICS, 2003. Google ScholarDigital Library
- Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An information-theoretic approach to traffic matrix estimation. In Proc. of ACM SIGCOMM, 2003. Google ScholarDigital Library
- Y. Zhang, M. Roughan, C. Lund, and D. Donoho. Estimating point-to-point and point-to-multipoint traffic matrices: An information-theoretic approach. IEEE/ACM Transactions on Networking, 13(5):947--960, 2005. Google ScholarDigital Library
- Q. Zhao, Z. Ge, J. Wang, and J. Xu. Robust traffic matrix estimation with imperfect information: Making use of multiple data sources. SIGMETRICS Perform. Eval. Rev., 34(1):133--144, 2006. Google ScholarDigital Library
Index Terms
- Spatio-temporal compressive sensing and internet traffic matrices
Recommendations
Spatio-temporal compressive sensing and internet traffic matrices
SIGCOMM '09Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availability and accuracy of traffic matrices. However, in practice it is challenging to reliably measure traffic matrices. ...
Compressive Sensing of Internet Traffic Matrices using CUR Decomposition
ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and NetworkingMissing values in traffic matrix (TM) is a well known fact which needs to be interpolated with least error as TM is a key input to various network operations and management tasks. Compressive sensing deals with the reconstruction of missing observations ...
Image compressive sensing via Truncated Schatten-p Norm regularization
Low-rank property as a useful image prior has attracted much attention in image processing communities. Recently, a nonlocal low-rank regularization (NLR) approach toward exploiting low-rank property has shown the state-of-the-art performance in ...
Comments