Research Of Network Traffic Estimation And Anomaly Detection Algorithm Based On Matrix Completion Theory

With the rapid development of information technology,the scale of IP network shows exponential growth,and it has developed into a heterogeneous and open complex network.As one of the most important data sources for network operation and network management,network traffic data contains rich network behavior information.However,it is extremely difficult to obtain complete and accurate traffic data because: 1)for a large-scale network environment,it is too expensive to directly measure the entire traffic matrix data,and usually only part of the data can be sampled.Therefore,there are a large number of missing values;2)network traffic generated by users' a variety of communication behaviors,there are different types of traffic anomalies.Therefore,it becomes a hot issue in the field of network management and traffic monitoring about how to estimate missing values and detect abnormal values from some sampled traffic data.Researchers at home and abroad have put forward many algorithms for network traffic estimation and anomaly detection based on the above problems.Although these algorithms show good performance on their respective datasets,they are still inadequate in the following aspects: the accuracy in network traffic estimation,the accuracy of anomaly detection,and the scale of the problem as well as traffic estimation under the condition of some OD(Origin-Destination)data are completely missing.Aiming at the above shortcomings,firstly,this thesis introduces the low-rank matrix completion theory based on the approximate low-rank and spatio-temporal correlation inherent in the traffic matrix,and models the traffic matrix estimation and anomaly detection problems into a class of fusion priori structural information of abnormal traffic norm-regularized matrix completion problem,and adopts the ADMM(Alternating Direction Method of Multipliers)method to optimize it which is popular in the field of machine learning.Simulation results show that the proposed algorithm efficiently solves the problem of missing data and anomalies in the network traffic matrix.Secondly,considering that the traditional ADMM is still a serial optimization method and can not be applied to solving large-scale problems,we introduce parallel multi-blocks ADMM and SPGD(Stochastic Proximal Gradient Descent)methods to improve the efficiency of the model.The algorithm can effectively solve the large-scale problem of traffic matrix estimation and anomaly detection.The simulation results show that the proposed algorithm has better estimation performance than the mainstream traffic estimation algorithms.In addition,the proposed algorithm can also provide accurate location of outlier and structural anomalies,which is the premise of large-scale network anomaly diagnosis.Lastly,based on the theory of inductive matrix completion,this paper also designed an algorithm that can perform large-scale traffic estimation and anomaly detection under the condition of some OD data are completely missing,and achieved good results on the synthetic data set.