Sub-Second Lookups on a Large-Scale Kademlia-Based Overlay

Previous studies of large-scale (multimillion node) Kademlia-based DHTs have shown poor performance, measured in seconds, in contrast to the far more optimistic results from theoretical analysis, simulations and testbeds. In this paper, we unexpectedly find that in the Mainline BitTorrent DHT (MDHT), probably the largest DHT overlay on the Internet, many lookups already yield results in less than a second, albeit not consistently. With the backwards-compatible modifications we present, we show that not only can we reduce median latencies to between 100 and 200 ms, but also consistently achieve sub-second lookups. These results suggest that it is possible to deploy latency-sensitive applications on top of large-scale DHT overlays on the Internet, contrary to what some might have concluded based on previous results reported in the literature. QC 20110825