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
Slide Note
Embed
Share

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.

  • Koorde
  • DHT
  • Distributed Hash Table
  • Chord
  • de Bruijn Graph

Uploaded on Sep 24, 2024 | 0 Views


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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Koorde Koorde: A simple degree optimal DHT : A simple degree optimal DHT M. Frans Kaashoek and David Karger MIT Laboratory of Computer Science

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

  3. 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?

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

  5. Koorde Koorde embeds a de Bruijn graph on the Chord identifier ring shown below.

  6. 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)

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

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#