Koorde


In peer-to-peer networks, Koorde is a Distributed hash table system based on the Chord DHT and the De Bruijn graph. Inheriting the simplicity of Chord, Koorde meets O hops per node, and O hops per lookup request with O neighbors per node.
The Chord concept is based on a wide range of identifiers in a structure of a ring where an identifier can stand for both node and data. Node-successor is responsible for the whole range of IDs between itself and its predecessor.

De Bruijn's graphs

Koorde is based on Chord but also on De Bruijn graph.
In a d-dimensional de Bruijn graph, there are 2d nodes, each of which has a unique d-bit ID. The node with ID i is connected to nodes 2i modulo 2d and 2i+1 modulo 2d. Thanks to this property, the routing algorithm can route to any destination in d hops by successively "shifting in" the bits of the destination ID but only if the dimensions of the distance between modulo 1d and 3d are equal.
Routing a message from node m to node k is accomplished by taking the number m and shifting in the bits of k one at a time until the number has been replaced by k. Each shift corresponds to a routing hop to the next intermediate address; the hop is valid because each node's neighbors are the two possible outcomes of shifting a 0 or 1 onto its own address. Because of the structure of de Bruijn graphs, when the last bit of k has been shifted, the query will be at node k. Node k responds whether key k exists.

Routing example

For example, when a message needs to be routed from node “2” to “6”, the steps are following:
Step 1)
Node #2 routes the message to Node #5, shifts the bits left and puts “1” as the youngest bit.
Step 2)
Node #5 routes the message to Node #3, shifts the bits left and puts “1” as the youngest bit.
Step 3)
Node #3 routes the message to Node #6, shifts the bits left and puts “0” as the youngest bit.

Non-constant degree Koorde

The d-dimensional de Bruijn can be generalized to base k, in which case node i is connected to nodes k * i + j modulo kd, 0 ≤ j < k. The diameter is reduced to Θ. Koorde node i maintains pointers to k consecutive nodes beginning at the predecessor of k * i modulo kd. Each de Bruijn routing step can be emulated with an expected constant number of messages, so routing uses O expected hops- For k = Θ, we get Θ degree and Θ diameter.