Non-negative Matrix Factorization For Network Delay Matrix Completion

Sanaa Ghandi (1, 2) , Alexandre Reiffers-Masson (1, 2) , Sandrine Vaton (2, 1) , Thierry Chonavel (3, 4)

1 Lab-STICC_MATHNET - Equipe Math & Net
2 IMT Atlantique - INFO - Département Informatique
3 Lab-STICC_MATRIX - Equipe Models and AlgoriThms for pRocessIng and eXtracting information
4 IMT Atlantique - MEE - Département Mathematical and Electrical Engineering

Accurate estimation of delays in a network is crucial for its management. In real-world applications, it is not always possible to conduct on-demand measurements regularly on the overall network. Doing so is costly and time-consuming, and it is also possible that not all the equipments respond to the probes sent in the network. In this paper, we formulate the network delay prediction problem as a non-negative matrix factorization problem with piecewise constant coefficients of the approximate instantaneous representation of data. We choose this approach to utilize the strong spatial and temporal correlation that appear in network delay data. To solve this factorization problem, we consider two different algorithms: an alternating projected gradient algorithm and the NeNMF algorithm. We finally study the efficiency of our approach on two datasets. The first dataset is a synthetic dataset produced by a simulator that we have designed, and the second one is composed of RTT measurements from RIPE Atlas.

Mots clés: Non-negative Matrix Factorization; Matrix Completion; Network Measurement; Network Delay

Domaines: Réseaux et télécommunications [cs.NI]; Traitement du signal et de l'image [eess.SP]; Intelligence artificielle [cs.AI]

Sanaa Ghandi, Alexandre Reiffers-Masson, Sandrine Vaton, Thierry Chonavel. Non-negative Matrix Factorization For Network Delay Matrix Completion. NOMS 2022: IEEE/IFIP Network Operations and Management Symposium - 7th IFIP/IEEE International Workshop on Analytics for Network and Service Management, Apr 2022, Budapest, Hungary. ⟨10.1109/NOMS54207.2022.9789871⟩. ⟨hal-03647577⟩