Structural Analysis of Network Traffic Matrix via Relaxed Principal Component Pursuit

The network traffic matrix is widely used in network operation and management. It is of crucial importance to analyze the composition and the structure of the network traffic matrix, for which some mathematical approaches such as Principal Component Analysis (PCA) were proposed to handle that problem. In this paper, we first argue that PCA performs poorly for analyzing traffic matrices that are polluted by large volume anomalies, and then propose a new decomposition model for the network traffic matrix. According to our model, structural analysis is carried out by decomposing the network traffic matrix into three sub-matrices, which is similar to the Robust Principal Component Analysis (RPCA) problem previously studied in [13]. Based on the Relaxed Principal Component Pursuit (Relaxed PCP) method and the Accelerated Proximal Gradient (APG) algorithm, an iterative algorithm for decomposing a traffic matrix is presented, and our experimental results demonstrate its efficiency and flexibility. Finally, further discussions on the deterministic traffic and the traffic noise are carried out. Our study gives a proper method for structural analysis of the traffic matrix, which is robust against pollution of large volume anomalies.