King Review

King: Estimating Latency between Arbitrary Internet End Hosts Review
Review by: Troy Ronda

Measuring the network latency between arbitrary hosts has many
interesting applications. The most obvious examples are nearest server
selection, measurement studies and the topology aware overlays (as
stated in the paper). The stated benefits of the King tool are accuracy,
no additional infrastructure is required (unlike IDMaps), and it only
requires a few packets to produce an estimate. Instead of deploying new
infrastructure, King uses the existing DNS infrastructure for a novel
purpose. The authors cite results showing that most end hosts in the
Internet are close to their DNS name servers, and recursive DNS queries
can measure latency between DNS servers. This simple idea has a number
of complications, as stated in the paper. 1) King must select the
closest DNS server from the list of returned name servers. The authors
use heuristics to decide the closest DNS server. 2) DNS servers can be
configured to disable recursive queries from arbitrary hosts. The
authors found that 72% of name servers associated with web servers
support recursive queries. 3) When there are multiple authoritative name
servers for a single domain, the recursive query is forward to any of
them. The authors first found that this inaccuracy is small. They also
found a method to “trick” the query to be forwarded to the name server
of their choice. The authors state that the Internet path between two
end hosts and between their name servers overlaps significantly. The two
main advantages of this tool, as stated by the authors, is due to not
requiring additional infrastructure and using online measurements. The
authors show that the accuracy of King, for measuring web hosts and
random Napster clients, is higher than IDMaps.

King is an interesting tool in that it exploits existing properties
available in the Internet for a novel purpose. A major downside to the
IDMaps system is that infrastructure must be deployed. This is both
expensive and inconvenient. King, on the other hand, uses infrastructure
that is already deployed for resolving names. IDMaps is also based on
offline extrapolation while King is based on online measurements. This
supports the conclusion that King has higher accuracy. Systems like
Vivaldi also make use of existing infrastructure, namely the hosts
themselves. King also represents an advantage here as Vivaldi is not
widely deployed (yet) but DNS server are ubiquitous. I found this paper
to be strong in its analysis and an interesting read. The accuracy of
King seems to suggest that a geographic tool based on DNS servers should
also have high accuracy. I should mention that our class project is, so
far, suggesting that approximately 65% of DNS name servers on the
Internet support recursive queries.

The authors state that they expect King to work around 94% of the time.
I believe that if an administrator has disabled recursive queries on one
DNS server, odds state that both DNS servers have been disabled.
Therefore it seems that King will probably only work ~70% of the time
but, of course, I could be wrong on this intuition. To be honest, I
found the organization style distracting due to the question/answer
format but perhaps other people like to read papers this way. The other
obvious disadvantage to the King technique is that DNS name servers for
home users can be hundreds of kilometers away from the host (eg. Telus
and Sympatico). Additionally the DNS name server will be collocated at
the ISP but the home user will have a significant last mile. This is, of
course, discussed in the paper as well.
Received on Thu Nov 03 2005 - 09:21:30 EST