Evaluation of Enhancement to Chord Routing Algorithm

Priya Avhad
Sphoorti Joglekar

ABSTRACT

A distributed hash table (DHT) is useful to store, lookup and delete
data objects in a distributed environment. One of the primary concerns
of such systems is how to efficiently lookup a node in a cluster that
holds the desired data. Chord, is a distributed routing protocol based
on ring topology that stores routing information in a data structure
called as a finger table to address this problem effectively. Chord
provides lookup of data in logarithmic time as opposed to its linear
time counterparts. A detailed study of the Chord routing algorithm
however, reveals that the finger tables store some redundant
information of the Chord ring, thereby affecting its lookup
performance. Enhancements have been proposed to the original Chord
routing algorithm to further improve its performance. This paper aims
at evaluating one such modification to the routing algorithm in Chord
that makes the finger table denser and increases the lookup bound. We
test the strategy to compare its performance with the original Chord
implementation and study its effectiveness and identify its
limitations. We conclude that the modified routing strategy improves
the lookup efficiency of Chord as the system scales.