The ability to estimate network latencies between arbitrary Internet end hosts would enable new measurement studies and applications, such as investigating routing path inefficiencies on a wide-scale or constructing topologically sensitive overlay networks. In this paper we present King, a tool that accurately and quickly estimates the latency between arbitrary end hosts by using recursive DNS queries in a novel way. Compared to previous approaches, King has several advantages. Unlike IDMaps, King does not require the deployment of additional infrastructure, and unlike GNP, King does not require end hosts to agree upon a set of reference points. Unlike both IDMaps and GNP, King's estimates are based on direct online measurements rather than offline extrapolation. Because King uses existing DNS infrastructure, King scales naturally both in terms of the number of hosts that can be measured and in terms of the number of hosts performing measurements.

After describing the techniques used in King, we present an extensive evaluation and analysis of the accuracy and consistency of our tool. Specifically, our evaluation shows that the accuracy of King is significantly better than the accuracy of IDMaps, and that King tends to preserve order among its latency estimates. Finally, we describe a variety of measurement studies and applications that could benefit from our tool, and present results from one such measurement study.