Title :
Sequential and adaptive sampling for matrix completion in network monitoring systems
Author :
Kun Xie ; Lele Wang ; Xin Wang ; Gaogang Xie ; Guangxing Zhang ; Dongliang Xie ; Jigang Wen
Author_Institution :
Coll. of Comput. Sci. & Electron. Eng., Hunan Univ., Changsha, China
fDate :
April 26 2015-May 1 2015
Abstract :
End-to-end network monitoring is essential to ensure transmission quality for Internet applications. However, in large-scale networks, full-mesh measurement of network performance between all transmission pairs is infeasible. As a newly emerging sparsity representation technique, matrix completion allows the recovery of a low-rank matrix using only a small number of random samples. Existing schemes often fix the number of samples assuming the rank of the matrix is known, while the data features thus the matrix rank vary over time. In this paper, we propose to exploit the matrix completion techniques to derive the end-to-end network performance among all node pairs by only measuring a small subset of end-to-end paths. To address the challenge of rank change in the practical system, we propose a sequential and information-based adaptive sampling scheme, along with a novel sampling stopping condition. Our scheme is based only on the data observed without relying on the reconstruction method or the knowledge on the sparsity of unknown data. We have performed extensive simulations based on real-world trace data, and the results demonstrate that our scheme can significantly reduce the measurement cost while ensuring high accuracy in obtaining the whole network performance data.
Keywords :
matrix algebra; signal sampling; wireless mesh networks; end-to-end network monitoring system performance; information-based adaptive sampling scheme; large-scale network full-mesh measurement; low-rank matrix completion technique; sampling stopping condition; sequential sampling scheme; Accuracy; Computers; Conferences; Internet; Matrix decomposition; Monitoring; Sparse matrices; Matrix Completion; Round-Trip Time Measurement; Sampling Stopping Condition;
Conference_Titel :
Computer Communications (INFOCOM), 2015 IEEE Conference on
Conference_Location :
Kowloon
DOI :
10.1109/INFOCOM.2015.7218633