Koorde: A Simple Degree Optimal DHT
K
o
o
r
d
e
:
A
s
i
m
p
l
e
d
e
g
r
e
e
o
p
t
i
m
a
l
D
H
T
M. Frans Kaashoek and David Karger
MIT Laboratory of Computer Science
I
n
t
r
o
d
u
c
t
i
o
n
•
Koorde is a DHT based on
Chord
and
de Bruijn graph
.
•
O(log n)
hops per lookup request with
only 2 neighbors
per node.
•
Can be generalized to
O(log n/ log log n)
hops per lookup
request with
O(log n)
neighbors per node
B
o
u
n
d
s
Lemma
An n-node network with maximum node degree d requires
at least
log
d
(n-1)
routing hops in the worst case.
Why?
D
e
B
r
u
i
j
n
g
r
a
p
h
A node m has two outgoing edges to
nodes
2m mod 2
b
and
2m+1 mod 2
b.
Call them the
0-link
and the
1-link
Koorde
Koorde embeds a de Bruijn graph on the Chord identifier ring shown below.
K
o
o
r
d
e
A message from node
i
to node
j
can be routed as follows:
1.
Shift the bits of
j
so that its
leading r
bits tally with the
last r
bits of
i
2.
Forward the query along the
paths corresponding to the last
(log
n
−
r
) bits of
j
:
Each 0 bit = a hop along the
0-link
Each 1 bit = a hop along the
1-link
.
Route via 0-link, 0-link
Routing takes at most log n hops (
optimal)
G
e
n
e
r
a
l
i
z
e
d
v
e
r
s
i
o
n
o
f
K
o
o
r
d
e
For
k
> 2, the earlier construction can easily be generalized.
From each node
i
, there will be
k
routing fingers pointing to
the nodes
k
⋅
i
,
k
⋅
i
+ 1,
k
⋅
i
+ 2,...,
k
⋅
i
+
k
−1 (additions mod
n
)
The path length will be
at most log
k
n
i.e.
log n/log k
between
any pair of nodes
When
k=log n
, the path length is
log n/log log n
Koorde is a distributed hash table (DHT) algorithm based on Chord and de Bruijn graph, offering optimal lookup performance with a low number of hops. It embeds a de Bruijn graph on the Chord identifier ring, enabling efficient message routing between nodes. The algorithm is designed to provide logarithmic hops per lookup request, making it an efficient solution for decentralized systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Koorde Koorde: A simple degree optimal DHT : A simple degree optimal DHT M. Frans Kaashoek and David Karger MIT Laboratory of Computer Science
Introduction Introduction Koorde is a DHT based on Chord and de Bruijn graph. O(log n) hops per lookup request with only 2 neighbors per node. Can be generalized to O(log n/ log log n) hops per lookup request with O(log n) neighbors per node
Bounds Bounds Lemma An n-node network with maximum node degree d requires at least logd(n-1) routing hops in the worst case. Why?
De De Bruijn Bruijn graph graph A node m has two outgoing edges to nodes 2m mod 2b and 2m+1 mod 2b. Call them the 0-link and the 1-link
Koorde Koorde embeds a de Bruijn graph on the Chord identifier ring shown below.
Koorde Koorde A message from node i to node j can be routed as follows: 1. Shift the bits of j so that its leading r bits tally with the last r bits of i 2. Forward the query along the paths corresponding to the last (log n r) bits of j: Route via 0-link, 0-link Each 0 bit = a hop along the 0-link Each 1 bit = a hop along the 1-link. Routing takes at most log n hops (optimal)
Generalized version of Generalized version of Koorde Koorde For k > 2, the earlier construction can easily be generalized. From each node i, there will be k routing fingers pointing to the nodes k i, k i + 1, k i + 2,..., k i + k 1 (additions mod n) The path length will be at most logkn i.e. log n/log k between any pair of nodes When k=log n, the path length is log n/log log n
