Data reconstruction in internet traffic matrix

Traffic matrix is an abstract representation of the traffic volume flowing between sets of source and destination pairs. It is a key input parameter of network operations management, planning, provisioning and traffic engineering. Traffic matrix is also important in the context of OpenFlow-based networks. Because even good measurement systems can suffer from errors and data collection systems can fail, missing values are common. Existing matrix completion methods do not consider traffic exhibit characteristics and only provide a finite precision. To address this problem, this paper proposes a novel approach based on compressive sensing and traffic self-similarity to reconstruct the missing traffic flow data. Firstly, we analyze the real-world traffic matrix, which all exhibit low-rank structure, temporal smoothness feature and spatial self-similarity. Then, we propose Self-Similarity and Temporal Compressive Sensing (SSTCS) algorithm to reconstruct the missing traffic data. The extensive experiments with the real-world traffic matrix show that our proposed SSTCS can significantly reduce data reconstruction errors and achieve satisfactory accuracy comparing with the existing solutions. Typically SSTCS can successfully reconstruct the traffic matrix with less than 32% errors when as much as 98% of the data is missing.