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
permette di condividere i bookmark con gli utenti connessi
Sistema adattivo 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)
Meeting Firb - Genova, 5-6 luglio 2004
DAD
CHILD
Adaptivity
Bookmarksharing
Chord
Bootstrap Authentication
Kleinberg
UserScores
DHT dump
MOMGraphical user interface
Our extensionto Kleinberg
Distributed Adaptive Directory (DAD)
Meeting Firb - Genova, 5-6 luglio 2004
Suggeriti dal sistema
Inseriti (o copiati)
dall’utente
Trovati nel sistema (su un
altro utente)
Numero di occorrenze
F-Chord: Improved Uniform Routing on Chord Gennaro Cordasco, Luisa Gargano, Mikael Hammar,
Alberto Negro, and Vittorio Scarano
Summary Motivation to our work
Peer to Peer Scalability Distributed Hash table
F-Chord family 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
Routing table size
1
1
N -1
N -1O(log N)
Chord et al.
Ring
O(log N)
Diameter
Uniform Routing algorithm
Non-Uniform Routing algorithm
Meeting Firb - Genova, 5-6 luglio 2004
Totally connected graph
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 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
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
Routing correctness
Routing efficiency
Meeting Firb - Genova, 5-6 luglio 2004
An Example: Chord
Meeting Firb - Genova, 5-6 luglio 2004
ID Resp.
8+1=9 14
8+2=11 14
8+8=16 21
8+16=24 24
8+32=40 42
8+4=12 14
m=6
indice Nodo
1 14
2 21
4 32
5 38
6 42
3 24
Successors
Predecessor
Nodo 1
Previous Results The network diameter lower bound is when
the routing table size is no more than Xu, Kumar, Yu (2003):
The diameter lower bound for the network is if the
degree is when we use an uniform routing
algorithm. In particular, the diameter lower bound for the
network is if the degree is when we use
an uniform routing algorithm;
Show an uniform routing algorithm with degree and diameter
equals to
(log )n(log )N
(1/ )log 0.768 logx N N
log
log log
N
N
log N
1log
2n
1log
2n
Average path length is 0,6135 log N
Meeting Firb - Genova, 5-6 luglio 2004
The Idea
Meeting Firb - Genova, 5-6 luglio 2004
1-2x=0 x=1/2 1-x-x2=0 x=1/
x
x2
618.12
51
S1=1
Si=(1/2)(i-1)
…
Sd≤1/n d ≤ log2 n
S1=1
(1/)2(i-1) ≤ Si ≤ (1/ )(i-1)
…
Sd≤1/n d ≤ log n
Chord
x
The Idea(2)
Meeting Firb - Genova, 5-6 luglio 2004
We can use only the jumps xi s.t. i 1 mod 2 (x, x3, x5, x7, …)
1
x2
xx x3
x3x2x2
x
x2
x3 x2
d = (1/2)log n
= (1/2)log n
The Idea(3)
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.
We recall that where
is the golden ratio and [ ] represents
the nearest integer function
12 4 8 16 32 64
Chord
1 51.618
2
( ) / 5iFib i
Meeting Firb - Genova, 5-6 luglio 2004
Fib-Chord
FormallyLet 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 :
123 5 8 13 21 34 55 89
Fib-Chord
1log 0.72021 log
2N N
log 1.44042 logN N
Meeting Firb - Genova, 5-6 luglio 2004
F-Chord()
Fa-Chord()Fib(2i), for i = 1,2, …,(1-)(m-2)Fib(i), for i = 2 (1-)(m-2) +2, …, m-1
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
2 5 13 34 89
Fib-Chord
1 3 8 21 55
even jumps
all jumpsall jumpseven jumps
[1/2,1]
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 Diameter :
Degree :
F-Chord(1/2) = Fa-Chord(1/2) = Fb-Chord(1/2)
Diameter :
Degree :
log 1.44042 logN N
2 5 13 34 89
Fib-Chord
1 3 8 21 55
F-Chord(1/2)
1log 0.72021 log
2N N
1log 0.72021 log
2N N
1log 0.72021 log
2N N
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.
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, d0, it holds that
N(,d) Fib(+d+1)
F-Chord(1/2) is optimal
Meeting Firb - Genova, 5-6 luglio 2004
Average path length 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)
Chord is better
Meeting Firb - Genova, 5-6 luglio 2004
0,00
0,20
0,40
0,60
0,80
1,00
1,20
1,40
1,60
Degree
Diameter
Average Path Length
Chord APL
Chord Degree &Diameter
hops
x
log
nGraphical results
Meeting Firb - Genova, 5-6 luglio 2004
Lower is better
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
Università di Salerno Dipartimento di Informatica ed Applicazioni ”R.M. Capocelli”,
84081, Baronissi (SA)
Meeting Firb - Genova, 5-6 luglio 2004
GRAZIE