Koorde
{{short description|Distributed hash table system for peer-to-peer networks}}
In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord DHT and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets {{math|O(log n)}} hops per node (where {{mvar|n}} is the number of nodes in the DHT), and {{tmath|O\left(\frac{\log n}{\log( \log n)}\right)}} hops per lookup request with {{math|O(log n)}} neighbors per node.
The Chord concept is based on a wide range of identifiers (e.g. 2{{sup|160}}) 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
File:De bruijn graph-for binary sequence of order 4.svg
Koorde is based on Chord but also on the De Bruijn graph (De Bruijn sequence).
In a {{mvar|d}}-dimensional de Bruijn graph, there are {{math|2{{sup|d}}}} nodes, each of which has a unique ID with {{mvar|d}} bits. The node with ID {{mvar|i}} is connected to nodes {{math|2i mod 2{{sup|d}}}} and {{math|2i + 1 mod 2{{sup|d}}}}. Thanks to this property, the routing algorithm can route to any destination in {{mvar|d}} hops by successively "shifting in" the bits of the destination ID but only if the dimensions of the distance between {{math|mod 1d}} and {{math|3d}} are equal.
Routing a message from node {{mvar|m}} to node {{mvar|k}} is accomplished by taking the number {{mvar|m}} and shifting in the bits of {{mvar|k}} one at a time until the number has been replaced by {{mvar|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 {{mvar|k}} has been shifted, the query will be at node {{mvar|k}}. Node {{mvar|k}} responds whether key {{mvar|k}} exists.
Routing example
For example, when a message needs to be routed from node 2 (which is {{code|010}}) to 6 (which is {{code|110}}), the steps are following:
- Node 2 routes the message to Node 5 (using its connection to {{math|2i + 1 mod 8}}), shifts the bits left and puts {{code|1}} as the youngest bit (right side).
- Node 5 routes the message to Node 3 (using its connection to {{math|2i + 1 mod 8}}), shifts the bits left and puts {{code|1}} as the youngest bit (right side).
- Node 3 routes the message to Node 6 (using its connection to {{math|2i mod 8}}), shifts the bits left and puts {{code|0}} as the youngest bit (right side).
Non-constant degree Koorde
The {{mvar|d}}-dimensional de Bruijn can be generalized to base {{mvar|k}}, in which case node {{mvar|i}} is connected to nodes {{math|k • i + j mod kd}}, {{math|0 ≤ j < k}}. The diameter is reduced to {{math|Θ(log{{sub|k}} n)}}. Koorde node {{mvar|i}} maintains pointers to {{mvar|k}} consecutive nodes beginning at the predecessor of {{math|k • i mod kd}}. Each de Bruijn routing step can be emulated with an expected constant number of messages, so routing uses {{math|O(log{{sub|k}} n)}} expected hops- For {{math|1=k = Θ(log n)}}, we get {{math|Θ(log n)}} degree and {{tmath|\Theta \left(\frac{\log n}{\log(\log n)}\right)}} diameter.
=Lookup algorithm=
function n.lookup(k, shift, i)
{
if k ∈ (n, s]
return (s);
else if i ∈ (n, s]
return p.lookup(k, shift << 1, i ∘ topBit(shift));
else
return s.lookup(k, shift, i);
}
Pseudocode for the Koorde lookup algorithm at node {{code|n}}:
- {{code|k}} is the key
- {{code|I}} is the imaginary De Bruijn node
- {{code|p}} is the reference to the predecessor of {{code|2n}}
- {{code|s}} is the reference to the successor of {{code|n}}
References
- "Internet Algorithms" by Greg Plaxton, Fall 2003: [https://web.archive.org/web/20040929211835/http://www.cs.utexas.edu/users/plaxton/c/395t/slides/DynamicTopologies-2.pdf]
- "Koorde: A simple degree-optimal distributed hash table" by M. Frans Kaashoek and David R. Karger: [http://iptps03.cs.berkeley.edu/final-papers/koorde.ps]
- Chord and Koorde descriptions: [http://www.cs.jhu.edu/~scheideler/courses/600.348_F03/lecture_10.pdf]
Category:File sharing networks
Category:Distributed data storage