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 whetherkey 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.