Geometric Exploration of the Landmark Selection Problem

摘要

Internet coordinate systems appear promising as a method for estimating network distance without direct measurement, allowing scalable configuration of emerging applications such as content delivery networks, peer to peer systems, and overlay networks. However all such systems rely on landmarks, and the choice of landmarks has a dramatic impact on their accuracy. Landmark selection is challenging because of the size of the Internet (leading to an immense space of candidate sets) and because insight into the properties of good landmark sets is lacking. In this paper we explore fast algorithms for landmark selection. Whereas the traditional approach to analyzing similar network-based configurka-tion problems employs the graph structure of the Internet, we leverage work in coordinate systems to treat the problem geometrically, providing an opening for applying new algorithms. Our results suggest that when employing small numbers of landmarks, such geometric algorithms provide good landmarks, while for larger numbers of landmarks even faster methods based on random selection are equally effective.