Università di Salerno GL7 Distributed Adaptive Directory (DAD)

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


Distributed Adaptive Directory (DAD)


DAD

CHILD

Adaptivity

Bookmarksharing

Chord

Bootstrap Authentication

Kleinberg

UserScores

DHT dump

MOMGraphical user interface

Our extensionto Kleinberg

Distributed Adaptive Directory (DAD)


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


Motivation Peer to Peer Systems (P2P)

File sharing system; File storage system; Distributed file system; Redundant storage; Availability; Performance; Permanence; Anonymity;

Scalability


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


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


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)


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


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


An Example: Chord


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


The Idea


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)


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


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


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]


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


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


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


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


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


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


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


Università di Salerno Dipartimento di Informatica ed Applicazioni ”R.M. Capocelli”,

84081, Baronissi (SA)

[email protected]


GRAZIE

Università di Salerno GL7 Distributed Adaptive Directory (DAD)

Documents

Transcript of Università di Salerno GL7 Distributed Adaptive Directory (DAD)