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 language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 29th International Teletraffic Congress, ITC 2017 |
| Editors | Raffaele Bolla, Florin Ciucu |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 72-80 |
| Number of pages | 9 |
| ISBN (Electronic) | 9780988304536 |
| DOIs | |
| State | Published - Oct 10 2017 |
| Event | 29th International Teletraffic Congress, ITC 2017 - Genoa, Italy Duration: Sep 4 2017 → Sep 8 2017 |
Publication series
| Name | Proceedings of the 29th International Teletraffic Congress, ITC 2017 |
|---|---|
| Volume | 1 |
Other
| Other | 29th International Teletraffic Congress, ITC 2017 |
|---|---|
| Country/Territory | Italy |
| City | Genoa |
| Period | 9/4/17 → 9/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