Accurate and fast recovery of network monitoring data: A GPU accelerated matrix completion

Kun Xie, Kun Xie, Kun Xie, Yuxiang Chen, Xin Wang, Gaogang Xie, Gaogang Xie, Jiannong Cao, Jigang Wen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)


Gaining a full knowledge of end-to-end network performance is important for some advanced network management and services. Although it becomes increasingly critical, end-to-end network monitoring usually needs active probing of the path and the overhead will increase quadratically with the number of network nodes. To reduce the measurement overhead, matrix completion is proposed recently to predict the end-to-end network performance among all node pairs by only measuring a small set of paths. Despite its potential, applying matrix completion to recover the missing data suffers from low recovery accuracy and long recovery time. To address the issues, we propose MC-GPU to exploit Graphics Processing Units (GPUs) to enable parallel matrix factorization for high-speed and highly accurate Matrix Completion. To well exploit the special architecture features of GPUs for both task independent and data-independent parallel task execution, we propose several novel techniques: similar OD (origin and destination) pairs reordering taking advantage of the locality-sensitive hash (LSH) functions, balanced matrix partition, and parallel matrix completion. We implement the proposed MC-GPU on the GPU platform and evaluate the performance using real trace data. We compare the proposed MC-GPU with the state of the art matrix completion algorithms, and our results demonstrate that MC-GPU can achieve significantly faster speed with high data recovery accuracy.

Original languageEnglish
Article number9042872
Pages (from-to)958-971
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number3
Publication statusPublished - Jun 2020


  • GPU
  • locality-sensitive hash
  • Parallel matrix completion

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this