Decentralized prediction of end-to-end network performance classes

In large-scale networks, full-mesh active probing of end-to-end performance metrics is infeasible. Measuring a small set of pairs and predicting the others is more scalable. Un-der this framework, we formulate the prediction problem as matrix completion, whereby unknown entries of an incom-plete matrix of pairwise measurements are to be predicted. This problem can be solved by matrix factorization because performance matrices have a low rank, thanks to the corre-lations among measurements. Moreover, its resolution can be fully decentralized without actually building matrices nor relying on special landmarks or central servers. In this paper we demonstrate that this approach is also applicable when the performance values are not measured exactly, but are only known to belong to one among some predefined performance classes, such as "good " and "bad". Such classification-based formulation not only fulfills the re-quirements of many Internet applications but also reduces the measurement cost and enables a unified treatment of var-ious performance metrics. We propose a decentralized ap-proach based on Stochastic Gradient Descent to solve this class-based matrix completion problem. Experiments on var-ious datasets, relative to two kinds of metrics, show the accu-racy of the approach, its robustness against erroneous mea-surements and its usability on peer selection