review of King

From: Guoli Li <gli_REMOVE_THIS_FROM_EMAIL_FIRST_at_cs.toronto.edu>
Date: Wed, 2 Nov 2005 18:54:50 -0500

 

This paper presents a latency measurement tool called King, which could estimate the latency between arbitrary end hosts. It could provide useful information for applications, such as building efficient overlay network, selecting a shortest path in a network, etc. Most traditional tools either provide inaccurate estimation results or require an additional infrastructure. King measures the latency between two hosts using existing DNS infrastructure, without additional infrastructure. It provides highly accurate latency estimates in a fast and light-weight way.

 

King works in two phases: first, King finds the DNS name servers that are topologically close to the end hosts. Second, King measures the latency between the two DNS name servers. King takes the estimated latency between name servers as the latency between the end hosts. King uses two heuristics, longest matching DNS suffix and IP prefix, to choose an authoritative name server that is close to an end host. After the two name servers are selected, King issues recursive DNS queries to its selected name server, and guarantees that the queries will be forwarded to the other selected name server, maybe with multiple attempts. Using existing DNS infrastructure, King provides better scalability than other tools and can be used in scaling wide-area measurement studies. The measurement overhead is only a few DNS queries per estimate. The results show that King is more accurate than IDMaps. Moreover, King preserves excellent order among its estimates.

 

There are several assumptions in the King project. First, all evolved DNS name servers should support recursive queries. Second, the authors assume that authoritative DNS name servers are close to the end hosts. Otherwise it may cause inaccurate estimations. This assumption may not always be true. It may depend on the samples collected from the Internet. Another factor of inaccuracy is the application level delay introduced by DNS servers to resolve the recursive query. Third, when there are multiple authoritative name servers, King needs to fool the source server so that the query could be sent to the target server selected by King. This may cause some incorrect DNS information cached. If King is widely used, we cannot ignore the effects.

 

Overall, King is a measurement tool that can estimate latency between arbitrary Internet end hosts, and does not require any additional infrastructure. It provides reasonable accurate estimates and preserves order among them.
Received on Wed Nov 02 2005 - 19:00:27 EST

This archive was generated by hypermail 2.2.0 : Wed Nov 02 2005 - 20:30:53 EST