Estimating Network Proximity and Latency∗

Network proximity and latency estimation is an important compo-nent in discovering and locating services and applications. With the growing number of services and service providers in the large-scale Internet, accurately estimating network proximity/latency with min-imal probing overhead becomes essential for scalable deployment. Although there exist a number of network distance estimation schemes, they either rely on extensive infrastructure support, require the IP address of the potential targets, falsely cluster distant nodes, or per-form poorly with even few measurement errors. We propose Netvi-gator, a scalable network proximity and latency estimation tool that uses information obtained from probing a small number of land-mark nodes and intermediate routers (termed milestones) that are discovered en route to the landmarks, to identify the closest nodes. With very little additional probing overhead, Netvigator uses dis-tance information to the milestones to accurately locate the closest nodes. We developed a Netvigator prototype and report our per-formance evaluation on PlanetLab and in the intranet of a large enterprise. Netvigator is a running service on PlanetLab as a par