L i m , a n d R a n d y H. K a t z C h r i s O v e r t o n , U n i v e r s i t y of C a l i f o r n i a , B e r k e l e y K e y n o t e S y s t e m s , Inc. Overlay network distance monitoring and estimation system can benefit many new applications and services, such as peer-to-peer overlay routing and location. However, there is a lack of such scalable system with small overhead, good usability, and good distance estimation accuracy and stability. Thus we propose a scalable overlay distance monitoring system, Internet Iso-bar, which clusters hosts based on the similarity of their perceived network distance, with no assumption about the underlying network topology. The centers of each cluster are then chosen as monitors to represent their clusters for probing and distance estimation. We compare it with other network distance estimation systems, such as Global Network Positioning (GNP) [1] . Internet Iso-bar is easy to implement and use, and has good scalability and small communication and computation cost for online monitoring. Preliminary evaluation on real Internet measurement data also shows that Internet Iso-bar has high prediction accuracy and stability. Finally, by adjusting the number of clusters, we can smoothly trade off the measurement and management cost for better distance estimation accuracy and stability. Given the rapid growth of the Internet, a new class of large-scale globally-distributed network services and applications have appeared. Examples include distributed content hosting services, overlay routing and location systems, application-level multicast, and peer-to-peer file sharing such as Napster and Gnutella. Because these systems have great flexibility in choosing their communication paths and targets, they can benefit significantly from dynamic network distance prediction in terms of metrics such as latency and bandwidth. This paper aims to solve the following problem: Given N end hosts that may belong to several different administrative domains, how do we select a subset of them as monitoring sites and build an overlay distance estimation/monitoring service without knowing the underlying topology? The N end hosts could belong to a VPN of a globalized company or a peer-to-peer file sharing system such as Napster [2] and Gnutella [3] . To address the scalability problem, we propose a clustering scheme: Internet Iso-bar, which groups the end hosts together based on the similarity of distance perception. We then select a suitable host as a monitoring site for active and continuous probing. We try several correlation metrics for clustering, and compare our scheme with other network distance estimation systems, such as Global Network Positioning (GNP) [1] . Internet Iso-bar is easy to implement and use, and has good scalability and small communication and computation cost for real-time monitoring. We further evaluate its estimation accuracy and stability with two sets of real Internet measurements. One is collected by the National Laboratory of Applied Network Research (NLANR) Active Measurement Project (AMP) [4]. The other is measured by Keynote Inc., the worldwide leader in Internet performance services [5] . These measurements enable us to measure the estimation stability on various time scales: daily, weekly, monthly and six-monthly. The results show that Internet Iso-bar has relatively high prediction accuracy and stability, and we expect to improve it further with better clustering methods. To the best of our knowledge, Internet Iso-bar is the first scalable overlay distance monitoring system and our work is the first attempt to evaluate the stability of various distance estimation schemes with real Internet measurement data. The rest of the paper is organized as follows. In Section 2, we list our design goals and survey previous work. We present the clustering and distance estimation techniques of Internet Iso-bar in Section 3. Simulation methodology is given in Section 4, and stability and accuracy evaluation in Section 5. Finally, we conclude in Section 6. 2.1 I n t e r n e t I s o -b a r G o a l s Scalability There are millions of users for peer-to-peer systems, such as Napster and Gnutella. So we cannot have any centralized point in the system to continuously measure distance to all hosts. S m a l l o v e r h e a d a n d t i m e l y i n f o r m a t i o n Such monitoring system should provide real-time report for network distance between any two hosts. It requires small communication and computation costs for estimation computation.
Internet Iso-bar REF also requires each node to measure distance to landmarks.
On the stability of network distance estimation
PERV
Computer Science