Scott Crosby, An Analysis of BitTorrent's Two Kademlia-Based DHTs

Despite interest in structured peer-to-peer overlays and their scalability to millions of nodes, few, if any, overlays operate at that scale. This paper considers the distributed hash table extensions supported by modern BitTorrent clients, which implement a Kademlia-style structured overlay network among millions of BitTorrent users. We demonstrate a measurements-based approach for examining these overlays to discover correcteness and performance bugs, and identify their root causes. We show that Kademlia's choice of iterative routing and its lack of a preferential refresh of its local neighborhood cause correctness problems and poor performance. We also measure, test, and model the effectiveness of potential fixes for the problems we observed.