Lezione 4
• Consisten Hashing
• Altri sistemi P2P uniformi
• F-Chord :-)
Sistemi P2P avanzati
Facciamo un piccolo test
• Partendo dalla figura, descrivere la procedura Join
• Descrivere le varie tecniche di replicazione e
analizzarne vantaggi e svantaggi
• Descrivere PNS e PRS
• In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora la lookup
impiega
(N) (½ log N) (m) (nessuna prec.)
c
a
b
Sistemi P2P avanzati
Outline
• Consistent Hashing
-
Definizione
Desiderata
Proprietà
Esempio
- Altri Sistemi
- Tapestry
- CAN
- Viceroy
• F-Chord
– Idea
– P2P uniformi
– Risultati
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
0 5
IP=“198.10.10.1”
123
20
ID a 7-bit
101
32
90
Chiave=“LetItBe”
60
Una chiave (risorsa) è memorizzata nel primo nodo che segue in senso orario
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
• Nasce come una tecnica per replicare i dati nei
sistemi C/S
• Problema: memorizzare una copia dei dati
messi a disposizione dal Server su un pool di
Client
– Load balancing
– Fast recovery
• Le funzioni Hash mappano chiavi (risorse) in
interi.
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
• Con N Client una possibile funzione è
x -> ax+b (mod N)
• Cosa accade se varia N?
– Buona parte dei dati va riposizionata
• Se la usassimo in un sistema P2P?
– N varia continuamente
– nessuno sa precisamente quanto vale N
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
x -> ax+b (mod N)
• In particolare se varia N:
– è assicurato un bilanciamento sul numero di dati
per posizione
– molti dati devono cambiare posizione
– il numero di posizioni che un dato può
potenzialmente raggiungere non è limitato
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
• Desiderata
– Vogliamo che quando N varia (cioè un nodo entra
o esce dal sistema)
• la quantità di dati che viene rimappata nel sistema è
bassa
• le posizioni in cui un generico dato (risorsa) è mappato
sono limitate
• i dati vengono assegnati in maniera bilanciata su tutti i
nodi
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
In altre parole, per definizione un Consistent
Hashing deve godere di opportune proprietà:
Bilanciamento
Monotonicità
Spread
Carico
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
• Sia I l’insieme delle risorse e B l’insieme delle
possibili posizioni (I = |I|).
• Ovviamente le possibili configurazioni del
sistema sono 2B
• Quello che cerchiamo è una funzione
f:2B  I -> B
• Se V è una configurazione (V2B) è ovvio che
f(V,id)  V, per qualsiasi id
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
Bilanciamento:
Per ogni sottoinsieme V di posizioni (nodi) ed I dati, il numero
di dati per ogni posizione è O(I/|V|) con alta probabilità.
Monotonicità:
I dati si devono
muovere solo se è
necessario
Se al variare di N le posizioni (i nodi) disponibili passano da V1
a V2 con V1  V2, la migrazione dei dati deve avvenire solo
verso posizioni appartenenti a V2\V1, ma non a V1 .
Se V1  V2, f(V2, i) V1 allora f(V1, i) = f(V2, i)
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
Spread:
Al variare di N, il numero di posizioni che un dato può assumere
è limitato.
Carico:
Al variare di N, il numero di dati che una posizione accoglie è
limitato.
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
Funzioni Hashing Consistenti esistono ?
Siano K(x) ed N(x) due funzioni casuali che hanno come
codominio l’intervallo [0,1).
Definiamo la seguente funzione Hash:
Utilizziamo K(x) per mappare le chiavi
Utilizziamo N(x) per mappare i nodi
F: La chiave i viene memorizzata nel nodo j se la differenza
|K(i)-N(j)| è la minima su tutti i nodi j.
Sistemi P2P avanzati
Consistent Hashing [Karger et al 97]
0
F precedentemente definito:
Bilanciamento ?
Monotonicità ?
Spread ?
Carico ?
Sistemi P2P avanzati
1
DHT Routing (Tapestry)
• Realizzazione dinamica dell’algoritmo di Plaxton et al.(che
non si adattava a sistemi dinamici);
• Supponendo che le chiave è costituita da un intero positivo
l’algoritmo di routing corregge a ogni passo un singolo digit alla
volta;
• Per fare ciò un nodo deve avere informazioni sui nodi
responsabili dei prefissi della sua chiave; (O(log N) nodi)
• Il numero di messaggi necessari per fare lookup è O(log N);
• L’algoritmo in pratica simula un Ipercubo;
Sistemi P2P avanzati
DHT: Routing (CAN)
• I nodi sono mappati su un toro d-dimensionale;
• A ogni nodo è associato un sottoinsieme di questo spazio d-dimensionale;
• Ogni nodo mantiene la lista dei nodi responsabili dei sottospazi che confinano con
il proprio sottospazio;
• Ogni nodo ha O(d) vicini (due per
ogni dimensione);
1
• Il routing avviene in
1
d
media
d
d in N
4
passi,
O(dN
)
;
• Da notare che se usiamo d = log N dimensioni abbiamo O(log N) vicini e il routing
ha costo:
O(log N * N
1
log N
)  O(log N * 2log N
Sistemi P2P avanzati
1
log N
)  O(log N * 2
1
log N
log N
)  O(log N )
DHT: Routing (Viceroy)
• I nodi sono mappati su una butterfly e contemporaneamente su
un array circolare;
• Ogni nodo ha un identificatore addizionale chiamato livello;
• Tre tipi di link:
• General link: predecessore e successore sull’array circolare
(2 link);
• Level ring: connette i nodi di uno stesso livello (2 link);
• Butterfly link: realizza la butterfly (2 link);
• Ogni nodo ha O(1) vicini;
• Il routing avviene in O(log N) passi in media e O(log2 N) passi
WHP;
Sistemi P2P avanzati
DHT: Routing (Viceroy)
Sistemi P2P avanzati
F-Chord: performance metrics
• Tre parametri per la misura delle
performances:
– Dimensione della tabella di routing (degree)
• Memoria utilizzata
• Misura inoltre il costo per la stabilizzazione della rete
successiva a joins/leaves di nodi
– Diametro e Lunghezza media delle path
• Velocità nel reperire i dati
Sistemi P2P avanzati
Uniform Routing Algorithm
• Consideriamo un ring di 2m identificatori, etichettati
da 0 a 2m -1
• Sia N=2m, un algoritmo di routing si dice uniforme se
per ogni nodo n, n è connesso con y iff n+z è
connesso con y+z (i.e. : tutte le comunicazioni sono
simmetriche).
– Vantaggi
• Facili da implementare
• L’algoritmo greedy è sempre ottimale
• Non c’è congestione sui nodi
– Svantaggi
• Sono meno potenti (De Bruijn Graph e Neighbor of Neighbor
Greedy routing sono più potenti)
Sistemi P2P avanzati
Asymptotic tradeoff curve
Diameter
Ring
Uniform Routing
algorithm
N -1
Chord et al.
O(log N)
Totally connected
graph
O(log N)
Non-Uniform
Routing algorithm
1
1
Sistemi P2P avanzati
O(log N)
N -1
Idea (consideriamo un ring [0,1))
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
Sistemi P2P avanzati
Sd≤1/n  d ≤ log N
1 5
 1.618
2
The Idea(2)
 = (1/2)log N
• Possiamo usare solo i jump xi con i dispari
x5, x7, …)
1
x2
x
x2
(x, x3,
x3
x3
x
d = (1/2)log
N
x2
x
x2
Sistemi P2P avanzati
The Idea(3)
Chord
12 4 8
16
32
64
• Costruiamo un nuovo algoritmo di routing uniforme,
basato su una nuova tecnica, in particolare il nuovo
schema è basato sui numeri di Fibonacci.
• Fib(i) denota l’ i-th numero di Fibonacci.
• Ricordiamo che
dove
i


Fib
(
i
)


/
5
è il golden ratio and
 [ ] rappresenta

1 5

1.618
l’intero2più 
vicino.
Sistemi P2P avanzati
Fib-Chord
Fib-Chord
123 5 8
13
21
34
55
• Formalmente
Sia N  (Fib(m-1), Fib(m)]. Lo schema usa m-2 jumps
(fingers) di taglia Fib(i) per i = 2,3, … , m-1
• Fib-Chord
– Diametro :
– Grado :
Sistemi P2P avanzati
1
log N  0.72021 log N 
2
log N  1.44042 log N
89
F-Chord()
Fib-Chord
12 3 5 8
13
21
55
34
• F-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
• F-Chord() usa (m-2) jumps
Sistemi P2P avanzati
even
jumps
Property of F-Chord [CGHNS04]
• Grado:
F-Chord() usa (m-2) jumps
• Diametro:
Theorem
For any value of , the diameter of F-Chord() is
m/2  0.72021 log N
• Lunghezza media delle path:
Theorem
The average path length of the F-Chord() scheme is
bounded by
0.39812 log N + (1)0.24805 log N
Sistemi P2P avanzati
F-Chord(1/2)
Fib-Chord
F-Chord(1/2)
12 3 5 8
13
21
34
55
89
Fib-Chord = F-Chord(1)
1
– Diametro :
log N  0.72021 log N
2
– Grado :
log N  1.44042 log N
• F-Chord(1/2)
1
– Diametro :
log N  0.72021 log N
2
1
log N  0.72021 log N
– Grado :
2
Sistemi P2P avanzati

The Lower Bound
• E’ possibile mostrare che 1.44042 log N è un bound sulla
somma grado e diametro per ogni sistema P2P uniforme
con N identificatori.
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)
Sistemi P2P avanzati
Average path length
• Fib-Chord: 0.39812 log N 
• F-Chord(1/2): 0.522145 log N 
Chord is better
• 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)
Sistemi P2P avanzati
Graphical results
1.60
1.40

Lower is
better
Degree
hops x log n
1.20
Diameter
1.00
Average Path Length
0.80
0.60
Chord APL
0.40
Chord Degree &
Diameter
0.20
0.00
0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00
Sistemi P2P avanzati