Inference Method Of Network Measurement Data Based On Low-rank Decomposition

With the rapid development of computer technology,computer networks have also developed rapidly on a large scale.More and more attention has been paid to the performance status of the network.In a large-scale network,it is obviously undesirable to perform largescale network measurement on the network to obtain the network performance status.Such measurement of the large-scale network status will bring about the network performance on the one hand.The extra burden affects your own network environment.On the other hand,it will take a long time to perform network-wide measurements on a large-scale network.Due to the redundancy of the network itself,when obtaining network data,part of the data is often measured to make quick inferences of the entire network data.This paper solves the problem of quickly obtaining network-wide data by quickly inferring the performance data in the network.The main research results are:1.Accurate and Fast Recovery of Network Monitoring Data: A GPU Accelerated Matrix CompletionGaining a full knowledge of end-to-end network performance is important for some advanced network management and services.Although it becomes increasingly critical,end-to-end network monitoring usually needs active probing of the path and the overhead will increase quadratically with the number of network nodes.To reduce the measurement overhead,matrix completion is proposed recently to predict the end-to-end network performance among all node pairs by only measuring a small set of paths.Despite its potential,applying matrix completion to recover the missing data suffers from low recovery accuracy and long recovery time.To address the issues,we propose MC-GPU to exploit Graphics Processing Units(GPUs)to enable parallel matrix factorization for high-speed and highly accurate Matrix Completion.To well exploit the special architecture features of GPUs for both task independent and data-independent parallel task execution,we propose several novel techniques: similar OD(origin and destination)pairs reordering taking advantage of the locality-sensitive hash(LSH)functions,balanced matrix partition,and parallel matrix completion.We implement the proposed MC-GPU on the GPU platform and evaluate the performance using real trace data.We compare the proposed MC-GPU with the state of the art matrix completion algorithms,and our results demonstrate that MC-GPU can achieve significantly faster speed with high data recovery accuracy.2.Accurate and Fast Recovery of Network Monitoring Data with GPU-Accelerated Tensor CompletionMonitoring 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.3.Local Tensor Completion Based on Locality Sensitive HashingTensor completion can be applied to fill in the missing data,which is import for many data applications where the data are incomplete.To infer the missing data,existing tensorcompletion algorithms generally assume that the tensor data have global low-rank structure and apply a single model to fit the overall observed data through the global optimization.However,there are different correlation levels among application data,thus the ranks of some sub-tensors can be even lower relative to that of the large tensor.Fitting a single model to all data will compromise the performance of data recovery.To increase the accuracy in missing data recovery,we propose to apply local tensor completion(Local-TC)to recover data from sub-tensors,with each containing data of higher correlations.Although promising,as the tensor data are only organized logically,it is difficult to determine the relationship among data.We propose to exploit locality-sensitive hash(LSH)to quickly reorganize tensor data,properly formulate lower-rank sub-tensors,and take advantage of projected data to perform similarity-sensitive data fusion.To demonstrate the performance of our LocalTC,we have done extensive experiments to compare the performance of our Local-TC with that of several state-of-the-art tensor completion algorithms(CP-als,CP-opt,CP-wopt,and T K als)using two real traffic flow traces Abilene and G `EANT.The experiment results demonstrate that Local-TC is very effective in increasing the recovery accuracy.4.A GPU-Accelerated Local Tensor Completion Based on Load-BalanceNow more and more applications use tensor filling to recover missing data.However,some existing technologies often ignore the local similarity within the tensor.The local subtensors within the tensor have stronger correlation.Filling the local subtensors will make the effect of tensor filling better.For local sub-tensors,each sub-tensor can be calculated separately,so it is easy to think of parallel calculations.But when the tensor is divided into small local sub-tensors,the existing algorithms often do not consider the load balancing problem of the calculation,so that the parallel calculation cannot be performed most effectively.In order to improve the recovery accuracy of missing data and the calculation time,we propose a new parallel local tensor filling algorithm Local-TCP.This method first uses the local sensitive hash function to split the tensor into three dimensions,so that subtensors with local similarity are formed,and then use the data balance method of thermal conductivity to perform the calculation tasks in each sub-tensor Effective balancing enables the algorithm to perform parallel calculations more efficiently.After balancing the subtensor data,we extend the algorithm to the GPU for calculations to obtain the final filling result.Our algorithm is the same as the classic CP-als,CP-opt,CP-wopt and T K als in two datasets(Abilene,G`EANT)for comparison.From the experimental results,we can get that on the two datasets,our Local-TCP-algorithm has improved both in accuracy and computing time.