An accurate and practical algorithm for internet traffic recovery problem

It is challenging to recover the large-scale internet traffic data purely from the link-load measurements. With the rapid growth of the problem scale, it will be extremely difficult to sustain the recovery accuracy and the computational cost simultaneously. For the purpose of fast and accurately recovering the traffic data from link-load measurements, we establish a new Sparsity Low-Rank Recovery (SLRR) model based on the intrinsic properties of traffic data and propose an improved Schur Complement Based semi proximal Alternating Direction Method of Multipliers (SCB-spADMM) to solve the SLRR model. The main contribution lies in the following two aspects. First, we fully exploit the spatial low-rank property and the sparsity of traffic data, which are barely considered in the literature. The model only relates to the traffics in a certain individual time interval. Thus, the scale of the problem is significantly reduced. Second, the global convergence of the proposed ADMM-type algorithm is established and all the intermediate variables' optimums can be calculated analytically in each iteration. According to the numerical results on the classic datasets Abilene and GRANT, our method achieves the best accuracy with a low computational cost. Moreover, in our newly released large-scale real-life network traffic dataset HOD, our method perfectly reaches the seconds-level feedback, which meets the essential requirement for practical scenarios. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

A new Sparsity Low-Rank Recovery (SLRR) model and an improved SCB-spADMM algorithm were proposed to recover traffic data quickly and accurately from link-load measurements. By exploiting the properties of traffic data, the problem scale was significantly reduced and the global convergence of the algorithm was established. The method achieved the best accuracy on classic datasets and reached second-level feedback on a large-scale real-life network traffic dataset.