The Low-rank Optimization Theory And Algorithms For Internet Traffic Data Recovery Problem

Network traffic data reflects the amount of data transmitting in the network system during a fixed time period,it is the pivotal input of many network problems,such as network activity examination,network resource distribution,congestion control,anomaly detection,etc.However,due to the limitation of monitoring technique,it is impractical to measure the whole traffic data in a network system.Thus,the aim of this thesis is to achieve a fast and accurate estimation to the whole traffic data only based on some low-cost data,such as a part of traffic data or the link-load data.It is common to recover the traffic flows of the whole network system merely based on partial collected data in network traffic recovery research.Although massive studies have been devoted to this issue,the recovery accuracy is still not promising.By exploiting the spatio-temporal low-rankness,time-smoothness and nonnegativity of traffic data,we propose a novel linear-constrained low-rank matrix recovery model.Based on the dual theory,we design a Schur complement based 4-block semi-proximal alternating direction method of multipliers algorithm to solve the dual model,and further find the solution to the primal problem.We prove that the proposed algorithm converges to the global optimum and has the Q-linear convergence rate under some conditions.We implement numerical experiments on two datasets Abilene and GéANT and make comparison with other approaches.The numerical results demonstrate that our algorithm substantially improves the recovery accuracy and satisfies the practical demand of consuming time.In contrast,the cost of measuring the link-load traffics is incredibly low.But the recovery problem purely based on link-loads can be more complicated.So far,little attention has been paid in this scenario.To this end,we propose two kinds of solutions as below.In the first kind of solution,we are the first to develop the recovery model by the spatial low-rankness and the sparsity of network traffic data.It should be noted that the proposed model only relates to the traffic data in one time interval,which sharply reduces the problem scale.Thus,the model is applicable to large-scale network traffic recovery task.We design a Schur complement based 5-block alternating direction method of multiplier algorithm to fix this model.We prove that the algorithm converges to the global optimum and has the Q-linear convergence rate with additional condition.In the second kind of solution,we adopt the novel tensor triple decomposition technique to better exploit the spatial and temporal features of traffic tensor.We develop an unconstrained model whose objective function is differentiable,and design a BB(Barzilai-Borwein)algorithm to solve it.We prove the BB algorithm can converge to the stationary point of the proposed model,and has the R-linear or R-sublinear convergence rate.Finally,we test the recovery performance on three open-source datasets Abilene,GéANT and HOD,and compare the above two kinds of methods with existing works.The numerical results show that our two methods are vastly superior to the others in terms of the recovery accuracy(the second method is better than the first).As for computational efficiency,the first/second method can reach a second-/minute-level feedback for the traffics in one time interval,which can also satisfy the industrial demand.