Towards Accurate Internet Distance Prediction

April 14, 2006
Rongmei Zhang | Purdue University

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.

Speaker Details

Rongmei Zhang is a Ph.D candidate in the School of Electrical and Computer Engineering at Purdue University. She received the BS (1998) and MS (2000) degrees from Tsinghua University, both in Electrical Engineering. Rongmei’s research interests are in distributed systems and networking. She is currently exploring Internet measurement and positioning systems for constructing proximity-aware network applications. In summer 2005, she worked on the monitoring and management of large-scale distributed systems at IBM T.J. Watson Research Center. She has also worked in the areas of peer-to-peer systems, overlay networks, multimedia networking and Grid computing.