Multi-low-rank Approximation for Traffic Matrices

Saurabh Verma, Arvind Narayanan, Zhi-Li Zhang

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

5 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
CountryItaly
CityGenoa
Period9/4/179/8/17

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

    Verma, S., Narayanan, A., & Zhang, Z-L. (2017). Multi-low-rank Approximation for Traffic Matrices. In R. Bolla, & F. Ciucu (Eds.), Proceedings of the 29th International Teletraffic Congress, ITC 2017 (pp. 72-80). [8064341] (Proceedings of the 29th International Teletraffic Congress, ITC 2017; Vol. 1). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/ITC.2017.8064341