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 hops per node, and hops per lookup request with 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 the De Bruijn graph.In a -dimensional de Bruijn graph, there are nodes, each of which has a unique ID with bits. The node with ID is connected to nodes and. Thanks to this property, the routing algorithm can route to any destination in hops by successively "shifting in" the bits of the destination ID but only if the dimensions of the distance between and are equal.
Routing a message from node to node is accomplished by taking the number and shifting in the bits of one at a time until the number has been replaced by. 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 has been shifted, the query will be at node. Node responds whether key exists.
Routing example
For example, when a message needs to be routed from node 2 to 6, the steps are following:- Node 2 routes the message to Node 5, shifts the bits left and puts as the youngest bit.
- Node 5 routes the message to Node 3, shifts the bits left and puts as the youngest bit.
- Node 3 routes the message to Node 6, shifts the bits left and puts as the youngest bit.
Non-constant degree Koorde
Lookup algorithm
function n.lookup
Pseudocode for the Koorde lookup algorithm at node :
- is the key
- is the imaginary De Bruijn node
- is the reference to the predecessor of
- is the reference to the successor of