Structured Overlay without Consistent Hashing: Empirical Results

Abstract

Consistent hashing is at the core of many P2P protocols. It evenly distributes the keys over the nodes, thereby enabling logarithmic routing effort 'with high probability'. However, consistent hashing incurs unnecessary overhead as shown in this paper. By removing consistent hashing from Chord, we derived a protocol that has the same favorable logarithmic routing performance but needs less network hops for updating its routing table. Additionally, our Chord <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">#</sup> protocol supports range queries, which are not possible with Chord. Our empirical results indicate that Chord <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">#</sup> outperforms Chord even under high churn, that is, when nodes frequently join and leave the system