Università di Salerno
GL7
Distributed Adaptive Directory (DAD)
F-Chord: Improved Uniform Routing on Chord
Meeting Firb - Genova, 5-6 luglio 2004
Distributed Adaptive Directory (DAD)


Sistema per il bookmark cooperativo
Ambiente peer-to-peer


Sistema adattivo


permette di condividere i bookmark con gli utenti
connessi
DAD offre suggerimenti sulla base dei bookmark
inseriti
Sistema dinamico

gli utenti possono fornire feedback sui bookmark
di altri utenti modificando il “peso” di bookmark ed
utenti
Meeting Firb - Genova, 5-6 luglio 2004
Distributed Adaptive Directory (DAD)
MOM
Graphical user interface
DAD
Adaptivity
Our extension
to Kleinberg
Bookmark
sharing
Kleinberg
User
Scores
CHILD
Authentication
Bootstrap
Chord
Meeting Firb - Genova, 5-6 luglio 2004
DHT dump
Distributed Adaptive Directory (DAD)
Numero di
occorrenze
Suggeriti dal
sistema
Inseriti (o
copiati)
dall’utente
Trovati nel
sistema (su un
altro utente)
Meeting Firb - Genova, 5-6 luglio 2004
F-Chord: Improved Uniform Routing on Chord
Gennaro Cordasco, Luisa Gargano, Mikael Hammar,
Alberto Negro, and Vittorio Scarano

Summary

Motivation to our work




F-Chord family




Peer to Peer
Scalability
Distributed Hash table
The Idea
Definition
Our result
Conclusions and Open Questions
Meeting Firb - Genova, 5-6 luglio 2004
Motivation

Peer to Peer Systems (P2P)









File sharing system;
File storage system;
Distributed file system;
Redundant storage;
Availability;
Performance;
Permanence;
Anonymity;
Scalability
Meeting Firb - Genova, 5-6 luglio 2004
Distributed Hash Table (DHT)


Distributed version of a hash table data structure
Stores (key, value) pairs





The key is like a filename
The value can be file contents
Goal: Efficiently insert/lookup/delete (key, value)
pairs
Each peer stores a subset of (key, value) pairs in the
system
Core operation: Find node responsible for a key


Map key to node
Efficiently route insert/lookup/delete request to this
node
Meeting Firb - Genova, 5-6 luglio 2004
DHT performance metrics

Three performance metric:

Routing table size (degree)



Storage cost
Measure the cost of self-stabilization for adapting to
node joins/leaves
Diameter and Average path length

Time cost
Meeting Firb - Genova, 5-6 luglio 2004
Uniform Routing Algorithm


We consider a ring of N identifiers labeled from 0 to
N-1
A routing algorithm is uniform if for each identifier x,
x is connected to y iff x+z is connected to y+z (i.e. :
all the connection are symmetric).

Advantages




Easy to implement
Greedy algorithm is optimal
No node congestion
Drawback

Less powerful (De Bruijn Graph and Neighbor of Neighbor
Greedy routing are more powerful)
Meeting Firb - Genova, 5-6 luglio 2004
Asymptotic tradeoff curve
Diameter
Ring
Uniform Routing
algorithm
N -1
Chord et al.
Totally connected
graph
O(log N)
Non-Uniform
Routing algorithm
1
1
O(log N)
N -1
Routing table size
Meeting Firb - Genova, 5-6 luglio 2004
An Example: Chord



Chord uses a one-dimensional circular key space (ring) of N=2b
identifiers
The node responsible for the key is the node whose identifier most
closely follows the key
Routing correctness
Chord maintains two sets of neighbors:




A successor list of k nodes that immediately follows it in the key space
A finger list of b = log N nodes spaced exponentially around the key space
Routing consists in forwarding to the node closest, but not past, the
key
Routing efficiency
Performance:



Diameter: log N (O(log n) whp) where n denote the number of nodes
present in the network
Routing table size: log N (O(log n) whp)
Average path length: ½ log N
Meeting Firb - Genova, 5-6 luglio 2004
An Example: Chord
Successors
ID
Resp.
indice
Nod
o
1
14
8+1=9
14
2
8+2=11
21
14
3
8+4=12
4
8+8=16
5
24
14
32
21
38
8+16=24
6
24
42
8+32=40
42
Predecessor
Nodo 1
Meeting Firb - Genova, 5-6 luglio 2004
m=6
Previous Results

The network diameter lower bound is
the routing table size is no more than

 log N 


 log log N 
when
log N
Xu, Kumar, Yu (2003):

The diameter lower bound for the network is
degree is
(log N )
(log n) if the
when we use an uniform routing
algorithm. In particular, the diameter lower bound for the
1
network is  1 log n  if the degree is   log n 
 2

2

an uniform routing algorithm;

when we use
Show an uniform routing algorithm with degree and diameter
equals to log (1/ x ) N   0.768 log N


Meeting Firb - Genova, 5-6 luglio 2004
Average path length
is 0,6135 log N 
The Idea

Chord
x2
x
x
1-2x=0  x=1/2
1-x-x2=0
 x=1/
S1=1
S1=1
Si=(1/2)(i-1)
(1/)2(i-1) ≤ Si ≤ (1/ )(i-1)
…
…
Sd≤1/n  d ≤ log2 n
Meeting Firb - Genova, 5-6 luglio 2004
Sd≤1/n  d ≤ log n
1 5
 1.618
2
The Idea(2)

 = (1/2)log n
We can use only the jumps xi s.t. i  1 mod 2 (x, x3,
x5, x7, …)
x2
1
x
x2
x3
x3
x
d = (1/2)log n
x2
x
x2
x3
Meeting Firb - Genova, 5-6 luglio 2004
x2
The Idea(3)
Chord
12 4 8
16
32
64

We construct an uniform routing algorithm using a
novel number-theoretical technique, in particular our
scheme is based on the Fibonacci number system.

Fib(i) denote the i-th Fibonacci number.

i

Fib(i)   / 5 
We recall that
where
1 5

 1.618 is the golden ratio and [ ]
2
represents the nearest integer function
Meeting Firb - Genova, 5-6 luglio 2004
Fib-Chord
Fib-Chord
123 5 8

13
21
34
55
89
Formally
Let N  (Fib(m-1), Fib(m)]. The scheme uses m-2 jumps of size
Fib(i) for i = 2,3, … , m-1

Fib-Chord

Diameter :

Degree :
1
log N  0.72021 log N
2
log N  1.44042 log N
Meeting Firb - Genova, 5-6 luglio 2004


F-Chord()
Fib-Chord
12 3 5 8

13
21
55
34
Fa-Chord()
89
[1/2,1]
Fib(2i), for i = 1,2, …,(1-)(m-2)
Fib(i), for i = 2 (1-)(m-2) +2, …, m-1
all jumps

even
jumps
Fb-Chord()
Fib(i), for i = 2, …,m-2(1-)(m-2)
Fib(2i), for i = (m-2(1-)(m-2) )/2 +1, … , (m-1)/2

Fa-Chord() and Fb-Chord() use (m-2) jumps
Meeting Firb - Genova, 5-6 luglio 2004
Property of F-Chord

Degree:
F-Chord() use (m-2) jumps

Diameter:
Theorem
For any value of , the diameter of F-Chord() is
m/2  0.72021 log N

Average Path Length:
Theorem
The average path length of the F-Chord() scheme is
bounded by 0.39812 log N + (1- )0.24805 log N
Meeting Firb - Genova, 5-6 luglio 2004
F-Chord(1/2)
Fib-Chord
F-Chord(1/2)
12 3 5 8


Fib-Chord

Diameter :

Degree :
13
21
34
55
89
1
log N  0.72021 log N 
2
log N  1.44042 log N

F-Chord(1/2) = Fa-Chord(1/2) = Fb-Chord(1/2)

Diameter :

Degree :
1
log N  0.72021 log N 
2
1
log N  0.72021 log N 
2
Meeting Firb - Genova, 5-6 luglio 2004
The Lower Bound


We provide a tradeoff of 1.44042 log N on the sum of
the degree and the diameter in any P2P network
using uniform routing on N identifiers.
F-Chord(1/2) is
optimal
Theorem
Let N(,d) denote the maximum number of consecutive
identifiers obtainable trough a uniform algorithm using
up to  jumps (i.e. degree ) and diameter d. For any
0, d0, it holds that
N(,d) Fib(+d+1)
Meeting Firb - Genova, 5-6 luglio 2004
Average path length
Chord is better



Fib-Chord: 0.39812 log N 
F-Chord(1/2): 0.522145 log N 
Theorem
For each  [0.58929,0.69424] the F-Chord()
schemes improve on Chord in all parameters
(number of jumps, diameter, and average path
length)
Meeting Firb - Genova, 5-6 luglio 2004
Graphical results
1,60
Lower is
better

1,40
Degree
hops x log n
1,20
Diameter
1,00
0,80
Average Path Length
0,60
Chord APL
0,40
Chord Degree &
Diameter
0,20
Meeting Firb - Genova, 5-6 luglio 2004
1,
00
0,
95
0,
90
0,
85
0,
80

0,
75
0,
70
0,
65
0,
60
0,
55
0,
50
0,00
Congestion

Our routing scheme is uniform, hence there is no
node congestion [Xu, Kumar, Yu (2003)].

Theorem
For each  [1/2,1] the F-Chord() schemes is
1.38197-edge congestion free.
A routing scheme is said to be c-edge
congestion free if no edge is handling
more than c times the average traffic per
node
Meeting Firb - Genova, 5-6 luglio 2004
Conclusions and Open Questions

An optimal uniform routing algorithm with
respect to diameter and degree

A family of simple algorithms that improve
uniform routing on Chord with respect to
diameter, average path length and degree

Open problem: Find a lower bound for the
average path length on uniform routing algorithm
Meeting Firb - Genova, 5-6 luglio 2004
GRAZIE
Università di Salerno
Dipartimento di Informatica ed Applicazioni ”R.M. Capocelli”,
84081, Baronissi (SA)
[email protected]
Meeting Firb - Genova, 5-6 luglio 2004