Unstructured peer-to-peer systems, such as Freenet [5] and Gnutella [1] locate objects through on generic graph traversal algorithms, such as iterative depth-first search and flooding-based breadth-first search, respectively. These algorithms are inefficient, do not scale well, and do not provide sublinear bounds on lookup performance.
Several structured peer-to-peer systems, which provide a worst-case bound on lookup performance, have been proposed recently. CAN [21] maps both objects and nodes on a d-dimensional torus and provides O(dn1/d) lookup performance. Plaxton et al. [19] introduce a randomized lookup algorithm based on prefix matching to locate objects in a distributed network in O(logN) probabilistic time. Chord [24], Pastry [22], and Tapestry [28] use consistent hashing to map objects to nodes and use Plaxton's prefix-matching algorithms to achieve O(logN) worst-case lookup performance. Kademlia [24] also provides O(logN) lookup performance using a similar search technique, but uses the XOR metric for routing. Viceroy [17] provides O(logN) lookup performance with a constant degree routing graph. De Bruijn graphs [16,26] provide O(logN) lookup performance with 2 neighbors per node and O(logN/loglogN) with logN degree per node. Beehive can be applied to any of the overlays based on prefix-matching.
A few recently introduced DHTs provide O(1) lookup performance.
Kelips [12] probabilistically provides O(1) lookup performance by dividing the network into
O(
) affinity groups of O() nodes, replicating every object on every node within an
affinity group, and using gossip to propagate updates.
An alternative method [13] relies on maintaining full routing state, that is, a complete list of all system members, at each node.
Farsite [10] uses routing tables of size O(dn1/d) to route in O(d) hops, but does not address rapid membership changes.
Beehive fundamentally differs from these systems in three fundamental ways.
First, Beehive can serve queries in less than one hop on average. And
second, it achieves low storage overhead, bandwidth consumption and
network load by minimizing the amount of replicated data in the system.
Finally, Beehive provides a fine grain control of the trade off between lookup performance and overhead by allowing users to choose the target lookup performance from a continuous range.
Some DHTs pick routing table entries based on network proximity. Recent work [4,27] has shown that this method can reduce the total lookup latency to a constant. However, the performance improvement is limited in large networks because the achieved absolute latency is several times more than the average single-hop latency.
Several peer-to-peer applications, such as PAST [23] and CFS [9], incorporate caching and replication. Both reserve a part of the storage space at each node to cache query results on the lookup path in order to improve subsequent queries. They also maintain a constant number of replicas of each object in the system in order to improve fault tolerance. As shown in this paper, passive caching schemes achieve limited improvement and do not provide provide performance guarantees.
Some systems employ a combination of caching with proactive object updates. In [6], the authors describe a proactive cache for DNS records where the cache proactively refreshes DNS records as they expire. While this technique reduces the impact of short expiration times on lookup performance, it introduces a large amount of overhead and does not qualitatively improve lookup performance. Controlled Update Propagation (CUP) [20] is a demand-based caching mechanism with proactive object updates. CUP nodes propagate object updates away from a designated home node in accordance to a popularity based incentive that flows from the leaf nodes towards the home node. While there are some similarities between the replication protocols of CUP and Beehive, the decision to cache objects and propagate updates in CUP are based on heuristics. [25] describes a distributed hierarchical web cache that replicates objects proactively, selects replica locations based on heuristics and pushes updates to replicas.
The closest work to Beehive is [7], which examines optimal strategies for replicating objects in unstructured peer-to-peer systems. This paper analytically derives the optimal number of randomly-placed object replicas in unstructured peer-to-peer systems. The observations in this work are not directly applicable to structured DHTs, because it assumes that the lookup time for an object depends only on the number of replicas and not the placement strategy. Beehive achieves higher performance with fewer replicas by exploiting the structure of the underlying overlay.