Towards Accurate Internet Distance Prediction

Опубликовано 6 сентября 2016, 6:26

Internet distance prediction provides proximity information without extensive network probings. Recent studies have revealed that the quality of existing prediction mechanisms is short of being satisfactory from the application's perspective. In this talk, we first study the impact of uneven prediction accuracy across different distance ranges and propose two new metrics that highlight the interference between predicting short and long links. We further investigate how to improve the distance prediction accuracy and the performance of prediction-based applications. First, we explore a selective measurement scheme which screens the candidates for the shortest link based on predicted distances. Our study finds that with only a small number of measurements, the selective measurement scheme is able a find a short link comparable to the actual shortest link from a large candidate pool. In addition, we study the impact of landmark selection on the prediction accuracy. Our experience with various landmark selection schemes shows that although selecting nearby landmarks can increase the prediction accuracy for short links, longer links are likely to experience degraded accuracy. Our study suggests that it may be fundamentally difficult to predict both short and long links using single coordinate per node. Based on this observation, we propose a hierarchical prediction approach which utilizes multiple coordinate sets at multiple distance scales, with the most suitable scale being chosen for prediction each time. We study two types of hierarchical prediction schemes: the first scheme leverages a shared landmark hierarchy, while in the second scheme, each node is allowed to choose its own landmarks. Experiments with Internet measurement datasets show that the hierarchical approach is very promising for improving the accuracy of network distance prediction.