On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks

We study a fundamental tradeoff issue in designing distributed hash table (DHT) in peer-to-peer networks: the size of the routing table v.s. the network diameter. It was observed by Ratnasamy et al. that existing DHT schemes either (a) have a routing table of size 𝒪(log₂n) and network diameter of Ω(log₂n), or (b) have a routing table of size d and network diameter of Ω(n¹d/). They asked whether this represents the best asymptotic "state-efficiency" tradeoffs. Our first major result is to show that there are straightforward routing algorithms, which achieve better asymptotic tradeoffs. However, such algorithms all cause severe congestion on certain network nodes, which is undesirable in a P2P network. We then rigorously define the notion of "congestion" and conjecture that the above tradeoffs are asymptotically optimal for a congestion-free network. In studying this conjecture, we have thoroughly clarified the role that "congestion-free" plays in this "state-efficiency" tradeoff. Our second major result is to prove that the aforementioned tradeoffs are asymptotically optimal for uniform algorithms. Furthermore, for uniform algorithms, we find that the routing table size of Ω(log₂n) is a magic threshold point that separates two different "state-efficiency" regions. Our third and final result is to study the exact (instead of asymptotic) optimal tradeoffs for uniform algorithms. We propose a new routing algorithm that reduces the routing table size and the network diameter of Chord both by 21.4% without introducing any other protocol overhead, based on a novel number-theoretical technique.