research-article

Free access

Spatio-temporal compressive sensing and internet traffic matrices

Authors:

Matthew Roughan,

Walter Willinger,

Lili QiuAuthors Info & Claims

SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication

Pages 267 - 278

https://doi.org/10.1145/1592568.1592600

Published: 16 August 2009 Publication History

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.

References

[1]

The Abilene Observatory Data Collections. http://abilene.internet2.edu/observatory/data-collections.html.

[2]

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.

[3]

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.

Digital Library

[4]

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.

[5]

E. Candes and B. Recht. Exact matrix completion via convex optimization. preprint.

[6]

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.

Digital Library

[7]

F. R. K. Chung. Spectral Graph Theory. CBMS Lecture Notes. AMS Publications, 1996.

[8]

D. Donoho. Compressed sensing. IEEE Trans. on Information Theory, 52(4):1289--1306, 2006.

Digital Library

[9]

V. Erramilli, M. Crovella, and N. Taft. An independent-connection model for traffic matrices. In Proc. of Internet Measurement Conference (IMC), 2006.

Digital Library

[10]

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.

Digital Library

[11]

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.

[12]

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.

Digital Library

[13]

A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In Proc. of ACM SIGCOMM, 2004.

Digital Library

[14]

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.

Digital Library

[15]

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.

[16]

Y. Mao and L. K. Saul. Modeling distances in large-scale networks by matrix factorization. In Proc. of Internet Measurement Conference (IMC), 2004.

Digital Library

[17]

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.

Digital Library

[18]

I. Norros. A storage model with self-similar input. Queueing Systems, 16:387--396, 1994.

[19]

B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization. preprint.

[20]

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.

[21]

H. Ringberg, A. Soule, J. Rexford, and C. Diot. Sensitivity of PCA for traffic anomaly detection. In Proc. of ACM SIGMETRICS, 2007.

Digital Library

[22]

M. Roughan. Simplifying the synthesis of Internet traffic matrices. SIGCOMM Computer Communications Review, 35(5):93--96, 2005.

Digital Library

[23]

M. Roughan and J. Gottlieb. Large--scale measurement and modeling of backbone Internet traffic. In Proc. of SPIE ITCOM, 2002.

[24]

M. Roughan, M. Thorup, and Y. Zhang. Traffic engineering with estimated traffic matrices. In Proc. of Internet Measurement Conference (IMC), 2003.

Digital Library

[25]

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.

Digital Library

[26]

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.

Digital Library

[27]

Y. Vardi. Network tomography. Journal of the Amer. Stat. Assoc., Mar. 1996.

[28]

G. Varghese and C. Estan. The measurement manifesto. In Proc. of 2nd Workshop on Hot Topics in Networks (HotNets-II), 2003.

[29]

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.

Digital Library

[30]

Y. Zhang, Z. Ge, M. Roughan, and A. Greenberg. Network anomography. In Proc. of Internet Measurement Conference (IMC), 2005.

Digital Library

[31]

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.

Digital Library

[32]

Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An information-theoretic approach to traffic matrix estimation. In Proc. of ACM SIGCOMM, 2003.

Digital Library

[33]

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.

Digital Library

[34]

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.

Digital Library

Cited By

Fan WXiao FHan LHe XWang J(2024)Joint Optimization of Measurement Point Intelligent Selection and End-to-End Network Traffic Calculation in DatacentersIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.327868011:3(2438-2449)Online publication date: May-2024
https://doi.org/10.1109/TNSE.2023.3278680
Chen LYang YWang W(2024)Temporal Autoregressive Matrix Factorization for High-Dimensional Time Series Prediction of OSSIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.327132735:10(13741-13752)Online publication date: Oct-2024
https://doi.org/10.1109/TNNLS.2023.3271327
Shu HWang HPeng JMeng D(2024)Low-Rank Tensor Completion With 3-D Spatiotemporal Transform for Traffic Data ImputationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.342221425:11(18673-18687)Online publication date: Nov-2024
https://doi.org/10.1109/TITS.2024.3422214
Show More Cited By

Index Terms

Spatio-temporal compressive sensing and internet traffic matrices
1. Networks
  1. Network services
    1. Network monitoring

Recommendations

Spatio-temporal compressive sensing and internet traffic matrices
SIGCOMM '09

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. ...
Compressive Sensing of Internet Traffic Matrices using CUR Decomposition
ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and Networking

Missing 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication

August 2009

340 pages

ISBN:9781605585949

DOI:10.1145/1592568

General Chairs:
Pablo Rodriguez
Telefonica Research, Spain
,
Ernst Biersack
Eurecom, France
,
Program Chairs:
Konstantina Papagiannaki
Intel Labs Pittsburgh, USA
,
Luigi Rizzo
Università di Pisa, Italy

ACM SIGCOMM Computer Communication Review Volume 39, Issue 4
SIGCOMM '09
October 2009
325 pages
ISSN:0146-4833
DOI:10.1145/1594977
Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '09

Sponsor:

SIGCOMM '09: ACM SIGCOMM 2009 Conference

August 16 - 21, 2009

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

315
Total Citations
View Citations
2,262
Total Downloads

Downloads (Last 12 months)201
Downloads (Last 6 weeks)32

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan WXiao FHan LHe XWang J(2024)Joint Optimization of Measurement Point Intelligent Selection and End-to-End Network Traffic Calculation in DatacentersIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.327868011:3(2438-2449)Online publication date: May-2024
https://doi.org/10.1109/TNSE.2023.3278680
Chen LYang YWang W(2024)Temporal Autoregressive Matrix Factorization for High-Dimensional Time Series Prediction of OSSIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.327132735:10(13741-13752)Online publication date: Oct-2024
https://doi.org/10.1109/TNNLS.2023.3271327
Shu HWang HPeng JMeng D(2024)Low-Rank Tensor Completion With 3-D Spatiotemporal Transform for Traffic Data ImputationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.342221425:11(18673-18687)Online publication date: Nov-2024
https://doi.org/10.1109/TITS.2024.3422214
He YJia YJia YAn CLu ZXia J(2024)An Integrated Intra-View and Inter-View Framework for Multiple Traffic Variable Data Simultaneous RecoveryIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.341450625:11(17200-17217)Online publication date: Nov-2024
https://doi.org/10.1109/TITS.2024.3414506
Zhang XHe JPan XChi YZhou Y(2024)Structured Low-Rank Tensor Completion for IoT Spatiotemporal High-Resolution Sensing Data ReconstructionIEEE Internet of Things Journal10.1109/JIOT.2023.331818611:5(8299-8310)Online publication date: 1-Mar-2024
https://doi.org/10.1109/JIOT.2023.3318186
Qiao YYuan XWu K(2024)Routing-Oblivious Network Tomography with Flow-Based Generative ModelIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621139(2139-2148)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621139
Chen LWang JWang WLou Z(2024)Back temporal autoregressive matrix factorization for high-dimensional time series predictionExpert Systems with Applications10.1016/j.eswa.2023.121399238(121399)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.121399
Xiao JCong YZhang WWeng W(2024)A cellular traffic prediction method based on diffusion convolutional GRU and multi-head attention mechanismCluster Computing10.1007/s10586-024-04848-y28:2Online publication date: 26-Nov-2024
https://doi.org/10.1007/s10586-024-04848-y
Li BXiong JWan FWang CWang D(2023)Incorporating Multivariate Auxiliary Information for Traffic Prediction on HighwaysSensors10.3390/s2307363123:7(3631)Online publication date: 31-Mar-2023
https://doi.org/10.3390/s23073631
Zhang SLou JXiong LZhang XLiu JFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Closed-form Machine Unlearning for Matrix FactorizationProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614811(3278-3287)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3614811
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents