• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Matrix completion based adaptive sampling for measuring network delay with online support

Vol. 14, No. 7, July 31, 2020
10.3837/tiis.2020.07.018, Download Paper (Free):

Abstract

End-to-end network delay plays an vital role in distributed services. This delay is used to measure QoS (Quality-of-Service). It would be beneficial to know all node-pair delay information, but unfortunately it is not feasible in practice because the use of active probing will cause a quadratic growth in overhead. Alternatively, using the measured network delay to estimate the unknown network delay is an economical method. In this paper, we adopt the state-of-the-art matrix completion technology to better estimate the network delay from limited measurements. Although the number of measurements required for an exact matrix completion is theoretically bounded, it is practically less helpful. Therefore, we propose an online adaptive sampling algorithm to measure network delay in which statistical leverage scores are used to select potential matrix elements. The basic principle behind is to sample the elements with larger leverage scores to keep the traits of important rows or columns in the matrix. The amount of samples is adaptively decided by a proposed stopping condition. Simulation results based on real delay matrix show that compared with the traditional sampling algorithm, our proposed sampling algorithm can provide better performance (smaller estimation error and less convergence pressure) at a lower cost (fewer samples and shorter processing time).


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
W. Meng and L. Li, "Matrix completion based adaptive sampling for measuring network delay with online support," KSII Transactions on Internet and Information Systems, vol. 14, no. 7, pp. 3057-3075, 2020. DOI: 10.3837/tiis.2020.07.018.

[ACM Style]
Wei Meng and Laichun Li. 2020. Matrix completion based adaptive sampling for measuring network delay with online support. KSII Transactions on Internet and Information Systems, 14, 7, (2020), 3057-3075. DOI: 10.3837/tiis.2020.07.018.