Accurate and Fast Recovery of Network Monitoring Data with GPU-Accelerated Tensor Completion

Monitoring the performance of a large network would involve a high measurement cost. To reduce the overhead, sparse network monitoring techniques may be applied to select paths or time intervals to take the measurements, while the remaining monitoring data can be inferred leveraging the spatial-temporal correlations among data. The quality of missing data recovery, however, highly relies on the specific inference technique adopted. Tensor completion is a promising technique for more accurate missing data inference by exploiting the multi-dimensional data structure. However, data processing for higher dimensional tensors involves a large amount of computation, which prevents conventional tensor completion algorithms from practical application in the presence of large amount of data. This work takes the initiative to investigate the potential and methodologies of performing parallel processing for high-speed and high accuracy tensor completion over Graphics Processing Units (GPUs). We propose a GPU-accelerated parallel Tensor Completion scheme (GPU-TC) for accurate and fast recovery of missing data. To improve the data recovery accuracy and speed, we propose three novel techniques to well exploit the tensor factorization structure and the GPU features: grid-based tensor partition, independent task assignment based on Fisher-Yates shuffle, sphere facilitated and memory-correlated scheduling. We have conducted extensive experiments using network traffic trace data to compare the proposed GPU-TC with the state of art tensor completion algorithms and matrix-based algorithms. The experimental results demonstrate that GPU-TC can achieve significantly better performance in terms of two relative error ratio metrics and computation time.