The paper "Turbo King: Framework for Large-Scale Internet Delay Measurements" published by Leonard and Loguinov at INFOCOM'08 shows the inaccuracies of the King delay estimation framework and propose Turbo King to tackle the problem.

The idea of King is to estimate distance between any to nodes by measuring the time required to resolve a DNS query from a DNS server near the source and a DNS server near the destination.

The authors shows that for some cases, King provides bad results. First, King is agnostic of DNS forwarders and thus is not able to give accurate delay estimates in presence of such forwarders. In addition, in presence of multiple authoritative name servers, King can provide bad results when DNS are deployed as recommended by RFC1034 and RFC1035 (i.e., DNS placed at different geographical location on separate networks). Finally, a major drawback of King is the "cache pollution". Indeed, King must send requests with no interest for DNS local users and many queries are sent to the servers.

Turbo King proposes to tackle theses problems of King. To do so, Turbo King just uses the principle of King (estimate delays with DNS response time), but improve the way the queries are performed. Turbo King is a stand alone service that keeps a list of the majority of open recursive and non-recursive DNS servers around the world. When the delay from A to B must be discovered, the service determine the closest DNS server of A by determining the recursive DNS server within the same BGP prefix or, in case of failure, by taking the DNS server with the longest prefix match. The same process is performed for the destination but non-recursive DNS are allowed as it is not required to have recursive DNS at the destination. To estimate the delay, Turbo King uses a 6 steps process:
1. Turbo King sends a query to A's closest DNS for the Turbo King's domain.
2. A's DNS server recursively queries Turbo King's DNS server.
3. Turbo King's DNS answers A's DNS server that B's DNS server is the authoritative server for the query (and impose not to cache this information with a TTL of 0).
4. A's DNS server queries B's server for the query
5. B's DNS server answers with an error,
6. The error is forwarded back to Turbo King's DNS server.

As Turbo King DNS client and server are controlled by the Turbo King service, timestamps can be taken at the correct instants and the delay estimate is the delay between step 3 and step 6 minus the delay between step 1 and step 2.

The cache is not polluted by the queries and a technique to detect forwarders is proposed.

Turbo King can be used in passive mode or active mode. In passive mode, measurements are done on demand and cached for subsequent requests. In active mode, Turbo King builds a delay matrix for all the DNS server in his DNS list and maintain it such that clients receive answers immediately. The cost of the last technique is that some delays are measured but never requested. This technique provides the ability to retrieve delays matrix which is interesting for researches.

The papers shows an evaluation of Turbo King but the evaluation is limited to a comparison between King and Turbo-King, no real answer is given about the accuracy of Turbo King...

In addition, the cost of crawling the DNS list seems to be important 2.3 Mbps during 33.8 hours (but the crawling does not need to be often performed).

The paper is available at http://irl.cs.tamu.edu/people/derek/papers/infocom2008.pdf

This paper can be applied to our IDIPS researches (http://inl.info.ucl.ac.be/idips)