In this paper, we study a fundamental tradeoff issue in designing distributed hash table (DHT) in peer-to-peer (P2P) networks: the size of the routing table versus the network diameter. It was observed by Ratnasamy et aL that existing DHT schemes either: 1) have a routing table of size O(log(2) n) and network diameter of 0 (log, n), or 2) have a routing table of size d and network diameter of O(n(1/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. We show that the answer to this conjecture is negative in the strict sense. However, the answer becomes positive if the routing algorithm is required to eliminate congestion in a "natural" way, by being uniform. 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 0 (log, n) is a magic threshold point that separates two different "state-efficiency" regions. Our third 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. Our fourth and final result is to present Ulysses, a congestion-free nonuniform algorithm that achieves a better asymptotic "state-efficiency" tradeoff than existing schemes in the probabilistic sense, even under dynamic node joins/leaves.
