DHT: Chord Routing

Chord is one kind of distributed hash table which provides fast distributed computation of a hash function mapping keys to nodes responsible for them.
Chord improves the scalability of consistent hashing by avoiding the requirement that every node know about every other nodes.
In N-node network, each node maintains information about only O(log N) other nodes, and a lookup requires O(log N) messages.

It looks simple but quite slow because it goes to every hop in the circle.

Chord can lookup node in peer-to-peer faster because of it searches by finger table which stores the hop in 2^i series.

e.g. N8+1 (2^0) => N9 , there is no N9, then go to N14,
N8+2 (2^1) => N10, there is no N10, then go to N14,
...
N8+32 (2^5) => N40, there is no N40, then go to N42, etc..

Note: Remember that chord always works on the clockwise for finding the successor.

However, N8 cannot determine the successor of key 34 by itself, as this successor (N38) does not appear in N8's finger table.

We will query K54, lookup(54) from N8.

First, open the finger of N8 and find the closest K54.
That's N8+32 => N40 => N42.
Next, go to N42 and open the finger table of N424
That's N42+8 => N50 => N51
Finally, go to N51 and open the finger table of N51
That's N56. Finish!!

Reference:
Paper Title: Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications
By: Ion Stoicay , Robert Morrisz, David Liben-Nowellz, David R. Kargerz, M. Frans Kaashoekz, Frank Dabekz, Hari Balakrishnan