Abstract
It is challenging to recover large-scale internet traffic data purely from link measurements. With the rapid growth of problem scales, sustaining recovery accuracy and managing computational costs becomes extremely difficult. We propose a Sparsity Low-Rank Recovery (SLRR) model and its Schur Complement Based semi-proximal Alternating Direction Method of Multipliers (SCB-spADMM) solver. Our approach distinguishes itself by fully exploiting the spatial low-rank property and sparsity of traffic data. The model is divisible into subproblems relating to individual time intervals, significantly reducing scale. We establish a globally convergent ADMM-type algorithm where all intermediate variables' optimums are calculated analytically. Numerical results on Abilene, GEANT, and a new large-scale Huawei Origin-Destination (HOD) network show that our method achieves superior accuracy with low computational cost, reaching seconds-level feedback for practical scenarios.
Introduction
In modern network management, knowing the traffic volume between every Origin-Destination (OD) pair is crucial for capacity planning and anomaly detection. However, directly measuring every OD pair is prohibitively expensive. Instead, operators typically measure "link loads"—the aggregate traffic passing through specific physical links. Inferring OD traffic from these loads is known as the Network Tomography Problem (NTP). It is notoriously difficult because it is highly underdetermined: there are far more OD pairs than physical links. As networks grow to thousands of nodes, existing mathematical models often become too slow or lose accuracy because they fail to capture the specific structural properties of real-world internet traffic.
The SLRR Model and SCB-spADMM Solver
We propose a two-part solution: the Sparsity Low-Rank Recovery (SLRR) model and a specialized high-performance solver. Most previous models look at spatio-temporal patterns simultaneously. We argue that focusing on the spatial low-rank property (the fact that a few major nodes drive most traffic) and high sparsity (most OD pairs transmit zero traffic) is more effective.
To solve this optimization problem, we developed the Schur Complement Based semi-proximal Alternating Direction Method of Multipliers (SCB-spADMM). Unlike standard ADMM, which can struggle with convergence in multi-block problems, this version is globally convergent. The algorithm breaks the massive problem into smaller time-interval subproblems. Crucially, the optimum for each intermediate variable is calculated analytically using closed-form math, removing the need for slow iterative approximations and enabling parallel processing.
Datasets and Sparsity Analysis
The study utilizes three primary datasets to validate the model:
- Abilene & GEANT: Classic research datasets used to benchmark against existing methods.
- Huawei Origin-Destination (HOD): A newly released, large-scale industrial dataset featuring 243 nodes and 59,049 OD pairs. It is highly sparse, with over 95% of OD pairs transmitting no traffic, reflecting real-world conditions.
By identifying which OD pairs are likely zero (using routing tables or Bloom filters), the model focuses its computational resources on the "elephant flows" that drive network behavior. This chronological decomposition allows the system to provide the "seconds-level feedback" essential for real-time traffic engineering.
Key Results
- Superior Accuracy: On the Abilene dataset with 90% sparsity, the SLRR model achieved a Normalized Mean Absolute Error (NMAE) of 0.047, compared to 0.236 for the previous benchmark (Tomo-SRMF).
- Scalability: On the massive HOD dataset, SLRR maintained high accuracy (NMAE ~0.15) where other methods struggled.
- Real-Time Performance: Despite the complexity of nuclear norm calculations, the algorithm recovers traffic for a 15-minute window in just a few seconds on standard hardware.
Conclusion and Future Work
The SLRR model and SCB-spADMM solver provide a scalable, accurate solution for modern network tomography. While the model currently requires Singular Value Decomposition (SVD), which can be a bottleneck for extremely large networks, its parallel nature and analytical updates offer a significant path forward. Future work will involve optimizing the SVD step through randomized techniques and integrating the model into live software-defined networking (SDN) controllers.
Summary updated