Multi-low-rank Approximation for Traffic Matrices

Saurabh Verma, Arvind Narayanan, Zhi-Li Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

With the Internet applications become more complex and diverse, simple network traffic matrix estimation or approximation methods such as gravity model are no longer adequate. In this paper, we advocate a novel approach of approximating traffic matrices with multiple low-rank matrices. We build the theory behind the MULTI-LOW-RANK approximation and discuss the conditions under which it is better than Low-Rank SVD in terms of both matrix approximation and preserving the local (and global) structure of the traffic matrices. Further, we develop an effective technique based on spectral clustering of column/row feature vectors for decomposing traffic matrices into multiple low rank matrices. We perform a series of experiments on traffic matrices extracted from a synthetic dataset and two real world datasets - one that represents nationwide cellular traffic and another taken from a tier-1 ISP. The results thus obtained show that: 1) MULTI-LOW-RANK approximation is superior for traffic classification; 2) it can be used to predict complete or missing entries of traffic matrices over time; 3) show it's robustness against noise; and 4) demonstrate that it closely follows the optimal solution (i.e., low-rank SVD solution).

Original languageEnglish (US)
Title of host publicationProceedings of the 29th International Teletraffic Congress, ITC 2017
EditorsRaffaele Bolla, Florin Ciucu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages72-80
Number of pages9
ISBN (Electronic)9780988304536
DOIs
StatePublished - Oct 10 2017
Event29th International Teletraffic Congress, ITC 2017 - Genoa, Italy
Duration: Sep 4 2017Sep 8 2017

Publication series

NameProceedings of the 29th International Teletraffic Congress, ITC 2017
Volume1

Other

Other29th International Teletraffic Congress, ITC 2017
Country/TerritoryItaly
CityGenoa
Period9/4/179/8/17

Bibliographical note

Funding Information:
Fig. 8: (a) MULTI-LOW-RANK decomposition on synthetic dataset (b) Approximation Error Rate with respect to noise variance in synthetic dataset. XI. CONCLUSION In this paper, we have advanced a novel approach of approximating traffic matrices with multiple ranks as opposed to the popular single/global rank approximation approach. We established the theory behind the MULTI-LOW-RANK approximation and identified the conditions under which MULTI-LOW-RANK method is better than Low-Rank SVD in both matrix approximation and preserving the local (and global) structure of the traffic matrices. We developed an effective approach based on spectral clustering for MULTI-LOW-RANK matrix decomposition and approximation. Finally, with a series of experiments on synthetic and real datasets, we demonstrated that the MULTI-LOW-RANK approximation yields better results in traffic classification than Low-Rank SVD and can be used to predict the traffic matrices in the immediate future specially in case of streaming traffic data over different time domains and also show its robustness against noise. ACKNOWLEDGMENT This research was supported in part by DTRA grant HDTRA1-14-1-0040, DoD ARO MURI Award W911NF-12-1-0385, and NSF grants CNS-1411636.

Funding Information:
This research was supported in part by DTRA grant HDTRA1-14-1-0040, DoD ARO MURI Award W911NF-12- 1-0385, and NSF grants CNS-1411636.

Keywords

  • Low rank SVD
  • Traffic classification
  • Traffic matrix approximation

Fingerprint

Dive into the research topics of 'Multi-low-rank Approximation for Traffic Matrices'. Together they form a unique fingerprint.

Cite this