SNIFF: A Scalable Network Inference Framework for Measuring End-to-End Performance

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 applying advanced matrix completion techniques to recover the complete matrix using a small percentage of samples. While the low-rank features 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 over time. In our framework, we extensively investigate real datasets and identify key features in measurement data, including the low-rank feature 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 three non-uniform sampling strategies that increase the sampling rate of important paths while reducing the rate if two paths are highly correlated. Moreover, we formulate two types of optimization problems for matrix completion that take into account important characteristics of data and we develop efficient algorithms to solve the corresponding problems. 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.