A New Variation of Chord with Novel Improvement on Lookup Locality.
Jie Wang, Zhijun Yu · 2006
Abstract- Distributed Hash Tables (DHT) are mechanisms used to locate data in P2P and Grid computing. Early DHT schemes, while providing lookups with optimal or near optimal efficiency at the overlay level, tend to neglect efficiency at the physical level. Although one may extend a DHT scheme by simply adding additional nodes in routing tables to provide extra locality choices, we note that there are intrinsically better ways. We illustrate this point using Chord as an example. We generalize Chord from one-sided lookups to two-sided lookups in a new variation called B-Chord. We show that B-Chord achieves substantially better lookup locality than Chord and 4-Extended Chord, a known variant that has approximately the same node degree of B-Chord. The improvement is achieved using a convex combination of finding a shorter physical path and finding a shorter overlay path. Simulating these protocols on common network models, we show that B-Chord, on average, incurs less than 35 % and 25 % of physical hops than Chord and 4-Extended Chord, respectively.