Spatio-temporal compressive sensing and internet traffic matrices

By Yin Zhang, Matthew Roughan, Walter Willinger, Lili Qiu. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2009

416 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/fc66dfa2a59416004880c9ec26cb155d300acc68

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

SketchVisor: Robust Network Measurement for Software Packet Processing (2017, methodology): “To this end, we leverage compressive sensing [6, 7, 9, 61] to solve the recovery problem by incorporating domain knowledge into optimization.”
Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction (2016, background): “Most existing MF approaches [2, 14, 16, 23, 26] adapt graph-based approaches to handle temporal dependencies.”
Spatiotemporal modeling and prediction in cellular networks: A big data enabled deep learning approach (2017, methodology): “A spatiotemporal compressive sensing framework was proposed for modeling Internet traffic matrices in [37].”
Compressive sensing: From theory to applications, a survey (2013, background): “Internet TMs mostly do not satisfy the conditions necessary for CS but by exploiting the spatio-temporal structure, TM can be recovered from as less as 2percent values [95].”
Scalable Tensor Factorizations for Incomplete Data (2010, background): “We also encounter the missing data problem in other areas of data mining, such as packet losses in network traffic analysis [2] and occlusions in images in computer vision [3].”