Incrementally improving lookup latency in distributed hash tables systems

Hui Zhang, Ashish Goel, Ramesh Govindan
Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems (SIGMETRICS’03)

Overview

The overlay networks created by distributed hash tables often do not consider the topology of the underlying network. The latency between two nodes in the overlay network can be much larger than the latency between the nodes in the underlying network. This can result in poor performance. The proposed technique is illustrated with Chord, LPRS-Chord, but is applicable to any system that uses geometric routing. With geometric routing the search space is decreased by a constant factor each time.

A node n in Chord keeps a fingertable. The i-th entry in the fingertable is the first node that succeeds n + 2^{(i-1). In LPRS-Chord the i-th entry is a node in the interval [n + 2}(i-1), n + 2^{i] with low latency. LPRS-Chord is still able to resolve lookups in O(log N) hops.}

To collect the latency samples Lookup-Parasitic Random Sampling(LPRS) is used. Each peer, at which the lookup passes, adds its IP address to the lookup. When the lookup reaches its target, the target informs all the hosts that were added to the request. Subsequently, the informed hosts sample the latency to the target using a simple ping. Each host determines in which range the target lies. If t it is closer than the current node in the fingertable for that range then the fingertable is updated with this new value.