SNIFF: A Scalable Network Inference Framework for Measuring End-to-End Performance Based on Matrix Completion

For Internet measurement, a key challenge is how to measure end-to-end performance accurately and effectively. To achieve this goal, several recent studies suggest to apply advanced matrix completion techniques to recover the complete matrix using a small percentage of samples. While the low-rank properties of matrices are generally utilized in existing studies, important features, which are unique in our domain context and can be used to significantly reduce path sampling overhead with guaranteed recovery accuracy, have not been fully explored. To fill the gap, we propose a scalable network inference framework, namely, SNIFF, to monitor the end-to-end performance of a set of paths overtime. In our framework, we extensively investigate real data sets and identify key features in measurement data, including the low-rank property of the path-time matrix, the smoothness of performance over a short period, and the pair-wise linear correlation of paths. Based on these features, we develop non-uniform random sampling strategies that increase the sampling rate of important paths while reducing the rate if two paths are highly correlated. Moreover, we formulate an optimization problem for matrix completion that takes into accounts important characteristics of data and we develop an efficient algorithm to solve it. To evaluate the proposed framework, we conduct extensive numerical experiments for measuring end-to-end delay and throughput performance. The results confirm the feasibility and advantages of the proposed framework and algorithms.