Over the past few years, several Distributed Hash Tables (DHTs) have
been proposed. These systems impose a certain structure on the
overlay topology, which allows key lookups to be performed in O(log n)
hops. However, all prior studies are based on simulations or
small-scale evaluations.
Recently, DHTs have begun to see wide-scale deployment in P2P
file-sharing applications such as Kad, which has more than one million
simultaneous users. In , we develop new tools
for studying DHTs in operation and present the first study of a
wide-scale DHT in operation. Our main contributions in this work can
be summarized as follows:
- An analytical framework for computing the average performance of
lookups
- The surprising result that redundancy in routing tables, such as
Kademlia's k-buckets, directly improves mean lookup performance by
reducing hop count
- Characterizations of the completeness and freshness of the
routing tables in Kad
- Demonstrating experimentally that parallel lookup can reduce hop
count, as predicted by our framework
- Experiments finding the optimum degree of parallelism
for use over Kad
- Experiments finding the optimum degree of replication
to overcome routing table inconsistencies in Kad
- Methodology that can be applied to studying and tuning
parameters for any widely deployed DHT.
