Sistemi Peer To Peer (P2P)
Avanzati
• Gennaro Cordasco
– [email protected]
– http://www.dia.unisa.it/~cordasco
– Laboratorio ISISLAB2 (L8 a Baronissi)
Sistemi P2P avanzati
Chord: A Scalable Peer-to-Peer Lookup Protocol
for Internet Applications
Autori: I. Stoica, R. Morris, D. Liben-Nowell, D. R.
Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan
MIT and Berkley
http://www.pdos.lcs.mit.edu/chord/
Sistemi P2P avanzati
Outline
•
•
•
•
Motivazioni
Idea
Protocollo
Valutazione delle prestazioni: lookup
Sistemi P2P avanzati
Chord: Obiettivi
•
•
•
•
•
Load Balance
Decentralization
Scalability
Availability
Flexibility
Sistemi P2P avanzati
Chord: Lookup
• Come trovare risorse in un sistema completamente
decentralizzato?
• La lookup è semplicemente una operazione, a disposizione di
tutti i peer di un sistema P2P, che data una chiave (una risorsa),
restituisce il gestore/responsabile della risorsa.
• Possiamo vedere l’operazione lookup come una funzione
(dinamica) che prende in input una chiave (un identificatore a
160 bit) e restituisce un indirizzo IP.
Lookup(id)IP address
Sistemi P2P avanzati
Chord: Lookup
• Come trovare risorse in un sistema completamente
decentralizzato?
Publisher
Key=“LetItBe”
Value=MP3 data
N2
N1
Internet
N4
il Lookup è il problema fondamentale
Sistemi P2P avanzati
N3
N5
Client ?
Lookup(“LetItBe”)
Chord: Lookup
• DHTs (Tapestry, Pastry, Chord, CAN,…)
Publisher
Key=“LetItBe”
Value=MP3 data
N2
N1
N3
Internet
N4
N5
Client
Lookup(“LetItBe”)
• Qual’è il modo migliore di realizzare il servizio di lookup?
Sistemi P2P avanzati
Chord
• Quale è il miglior modo per costruire le tabelle
di routing?
• Come facciamo a mantenere sempre corrette le
tabelle di routing in situazioni “molto”
dinamiche?
• Come gestire l’ingresso (join) e l’uscita (leave)
dei nodi?
• Quale è il miglior algoritimo di routing?
Sistemi P2P avanzati
Chord: Consistent Hashing
• Fondamentalmente, l’architettura di Chord è basata su un ring
di 2m identificatori [0, 2m-1] (di solito m = 160)
• Chord usa Consistent Hashing per assegnare identificatori sia
ai nodi/peers sia alle risorse
• Consistent Hashing permette:
– bilanciamento del carico sui nodi (con N nodi e K risorse, ogni nodo
gestisce circa (1+)K/N chiavi (risorse), dove =O(log N))
– basso numero di operazioni di manutenzione a seguito di join/leave dei
nodi (quando entra l’N+1th nodo nel sistema circa O(K/N) chiavi
(risorse) devono cambiare posizione)
• Discuteremo in dettaglio Consisten Hashing nelle prossime
lezioni
Sistemi P2P avanzati
Chord: Overview
• La tabella di routing relativa alle risorse è distribuita
su tutti i nodi attivi del sistema
• Per risolvere una lookup è necessario che i nodi si
scambino informazioni
• Prestazioni: In una rete “stabile” di N nodi, ogni nodo
mantiene informazioni relative a O(log N) vicini e
risolve qualsiasi lookup con al più O(log N)
messaggi
• Tuttavia anche se la rete non è “stabile” con poca
informazione (1 solo link) il protocollo Chord
garantisce la correttezza della lookup
Sistemi P2P avanzati
Chord: Identificatori
• Lo spazio degli identificatori a m bit è
utilizzato sia per le risorse che per i nodi
• identificatore di Chiave = SHA-1(Risorsa)
chiave=“LetItBe”
SHA-1
ID=60
• identificatore di Nodo = SHA-1(indirizzo IP)
IP=“198.10.10.1”
Sistemi P2P avanzati
SHA-1
ID=123
Chord: Identificatori
• Gli identificatori ottenuti utilizzando Consistent
Hashing vengono mappati su un ring circolare
modulo 2m
000000
111000
001000
010000
110000
011000
101000
Sistemi P2P avanzati
m=6
100000
Chord
• Il responsabile di una risorsa x con ID k è il
primo nodo che si incontra procedendo in
senso orario a partire da k.
nodi
risorse
m=6
1
8
56
54
51
48
21
42
38
Sistemi P2P avanzati
10
14
38
32
30
24
Chord
• Esempio leave (nodo 14)
nodi
risorse
m=6
1
8
56
54
51
48
21
42
38
Sistemi P2P avanzati
10
14
38
32
30
24
Chord
• Esempio join (nodo 26)
nodi
risorse
m=6
1
8
56
54
51
48
21
42
38
Sistemi P2P avanzati
10
38
24
26
32 30
Chord: Lookup
• Ogni nodo ha informazioni su tutti gli altri
• Supponiamo che il nodo 8 è interessato alla chiave
54: poiché il nodo 8 conosce tutti i nodi, è in grado di
sapere senza fare nessuna richiesta che la chiave 54 è
gestita dal nodo 56
• Richiede info globali
m=6
nodi
1
• Tabella di routing N
risorse
8
56
• Costo lookup O(1) msg
10
54
51
• Manutenzione:
48
Praticamente ingestibile!!!
21
42
Sistemi P2P avanzati
38
38
24
26
32 30
Chord: Lookup(2)
• Ogni nodo conosce solo il proprio successore
• Supponiamo che il nodo 8 è interessato alla chiave
54: ogni nodo conosce solo il proprio successore e
quindi la query attraversa l’anello in senso orario
finché non raggiunge il predecessore della
destinazione
nodi
1
• Richiede poche info:
risorse
56
• Tabella di routing 1 entry
54
• Costo lookup O(N) msg
51
m=6
8
10
48
21
42
Sistemi P2P avanzati
38
38
24
26
32 30
Simple Key location
Il nodo n chiama
lookup(id)
Sistemi P2P avanzati
Il nodo 8 chiama
lookup(54)
Chord: Correttezza Routing
• Ogni nodo n di Chord mantiene
log N successori del nodo n più il predecessore
• Questo insieme di nodi viene usato per dimostrare la
correttezza del Routing
nodi
1
8
risorse
56
54
51
10
21
Sistemi P2P avanzati
38
38
24
Chord: Lookup(3)
•
•
•
•
Ogni nodo conosce, al più, altri m nodi nel sistema (fingers)
Mostreremo che w.h.p. il numero di finger è O(log N)
La distanza cresce esponenzialmente
In particolare, il finger i del nodo n punta al responsabile
(successor) della chiave n+2i-1
nodi
m=6
1
8
risorse
56
54
51
48
21
42
Sistemi P2P avanzati
10
38
38
24
26
32 30
Chord: Ricapitolando
• Ogni nodo n di Chord mantiene la connessione con log N
successori (successors) del nodo n più il predecessore
• Inoltre, ogni nodo conosce, al più, altri O(log N) w.h.p, nodi
nel sistema (fingers)
• In totale ogni nodo mantiene
log N +1 +
O(log N)=O(log N) connessioni
nodi
m=6
1
8
risorse
56
54
51
48
21
42
Sistemi P2P avanzati
10
38
38
24
26
32 30
Tavola dei finger
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
m=6
Sistemi P2P avanzati
successor(0)=0
0
1
14
15
0
successor(14)=15
successor(1)=1
1
successor(2)=3
2
14
10
13
2
3
12
4
5
11
6
10
successor(6)=6
successor(10)=13
7
9
Sistemi P2P avanzati
successor(9)=9
8
9
6
0
1
14
0
15
i
succ
node
1
2
3
node
2
3
3
14
10
13
12
1
i
succ
1
14
15
3
5
6
2
15
15
4
9
9
3
1
1
4
5
6
11
10
2
Qualcuno vuol provare a
descrivere la tabella di routing
del nodo 9?
i
succ
1
10
?
?13
2
11
?
3
13
?
4
?1
?13
?13
?1
9
node
6
8
Sistemi P2P avanzati
9
4
5
7
2
3
6
Algoritmo Lookup
Il nodo n chiama
lookup(id)
Sistemi P2P avanzati
14
0
15
1
2
14
13
12
i
succ
1
14
15
2
15
15
3
1
1
4
5
6
11
10
node
i
succ
1
10
13
2
11
13
3
13
13
4
1
1
9
Sistemi P2P avanzati
i
succ
node
1
2
3
2
3
3
3
5
6
4
9
9
3
4
node
5
6
7
8
Join e Stabilization
Crea Anello Vuoto
Join
n=N26,
n’=qualunque nodo attivo
Stabilize
n=N26
n=N21
Sistemi P2P avanzati
Join e Stabilization
• Altre operazioni periodiche ma utilizzate con
frequenza minore sono fix.finger e check.predecessor
Sistemi P2P avanzati
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il
numero di ID di nodi atteso in questo intervallo è 1
e O(log N) w.h.p.
Sistemi P2P avanzati
Chord: Risultati
• Teorema
Il numero dei nodi che deve essere
contattato per risolvere una lookup è
O(log N) w.h.p.,
Dim
Supponiamo che il nodo n deve risolvere
una lookup per l’id k
Siano p e s, rispettivamente, il
predecessore e il successore dell’ID k
Se np e ns, n non è in grado di
risolvere da solo la query
n
p
k
s
Sistemi P2P avanzati
Chord: Risultati
• Teorema
Il numero dei nodi che deve essere
contattato per risolvere una lookup è
O(log N) w.h.p.
Dim
…
n contatta, quindi, il più vicino
predecessore di k a lui noto (il più
grande finger che non va oltre k).
Sia i tale che p [n+2i-1, n+2i)
Poiché tale intervallo contiene almeno un
nodo (p) il nodo n contattera l’i-esimo
finger f. Ovviamente tale nodo, ha ID
minore o uguale di p.
Per definizione di finger la distanza fra n e
f è almeno 2i-1
Sistemi P2P avanzati
f
n
p
id
s
Chord: Risultati
• Teorema
Il numero dei nodi che deve essere
contattato per risolvere una lookup è
O(log N) w.h.p.
Dim
…
Per definizione di finger la distanza fra n e
f è almeno 2i-1
Inoltre f e p sono entrambi nell’intervallo
[n+2i-1, n+2i), quindi la loro distanza è al
più 2i-1
In altre parole, f è più vicino a p che a n, e
quindi ad ogni hop la distanza “almeno”
si dimezza
Sistemi P2P avanzati
f
n
p
id
s
Chord: Risultati
• Teorema
Il numero dei nodi che deve essere contattato
per risolvere una lookup è O(log N) w.h.p.
Dim
….
Ad ogni hop la distanza “almeno” si dimezza
La distanza maggiore fra due ID è 2m-1,
poiché tale distanza ad ogni hop si
n
dimezza, in m hop siamo in grado di
eseguire qualunque lookup
f
p
id
s
Sistemi P2P avanzati
Chord: Risultati
• Teorema
Il numero dei nodi che deve essere contattato per risolvere una lookup è
O(log N) w.h.p..
Dim
Sappiamo che ad ogni hop la distanza, in termini di id fra sorgente e
destinazione si dimezza.
Supponiamo di effettuare log N hops, dopo questi passi la distanza dalla
destinazione si riduce ad al più 2m / 2 logN = 2m/N.
Sappiamo dal lemma precedente che in un tale intervallo ci sono al più
O(log N) nodi w.h.p.
Quindi effettuando altri O(log N) passi (anche usando solo i successori
negli ultimi O(log N) passi) arriviamo alla destinazione.
In totale log N + O(log N) = O(log N) passi.
Sistemi P2P avanzati
La Lookup impiega O(log N) hop
5
10
110
20
19
99
32
80
60
Sistemi P2P avanzati
Lookup(19)
Chord: Risultati
• Abbiamo detto che i nodi di Chord mantengono O(log N)
informazioni relative ad altri nodi, d’altra parte abbiamo detto
che un nodo può avere m fingers.
• In realtà, è possibile mostrare che non tutti gli m i finger sono
nodi distinti. Quello che accade è che, w.h.p., i primi m-2logN
finger cadono tutti sul successore del nodo.
• Infatti un lemma analogo a quello mostrato in precedenza
permette di dimostrare che che la distanza minima fra due nodi
(w.h.p.) è almeno 2m/N2
• Abbiamo detto che il finger i del nodo n cade nel successore
dell’ID n+2i-1
• Di conseguenza, per ogni i ≤ m - 2log N +1, il responsabile
dell’ID n+2i-1 ≤ n+ 2m/N2 cade nel successore di n.
• In totale il numero dei nodi distinti che bisogna mantenere nella
tabella di routing è m – (m - 2log N) = O(log N)
Sistemi P2P avanzati
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero di
ID di nodi atteso in questo intervallo è 1 ed O(log N) w.h.p.
Dim
Abbiamo necessita di alcuni risultati intermedi:
– Disuguaglianza di Marcov
• Sia X una variabile casuale a valori positivi, allora per ogni a>0:
E[X]  a Pr[Xa]
Sistemi P2P avanzati
Disuguaglianza di Marcov
Disuguaglianza di Marcov
Sia X una variabile casuale a valori positivi, allora per ogni
a>0:
E[X]  a Pr[Xa]
Dim
Proviamo per una variabile casuale discreta che assume valori
da 1 a k (è il nostro caso): k
Pr[ x  a ]   Pr[ x  i ]
k
ia
a 1
k
i 1
i 1
i a
E[ x]   i Pr[ x  i ]   i Pr[ x  i ]   i Pr[ x  i ]
Sistemi P2P avanzati
Disuguaglianza di Marcov
Disuguaglianza di Marcov
Sia X una variabile casuale a valori positivi, allora per ogni
a>0:
E[X]  a Pr[Xa]
Dim
Proviamo per una variabile casuale discreta che assume valori
da 1 a k (è il nostro caso):
k
k
k
i a
i a
i a
E[ x]   i Pr[ x  i ]   a Pr[ x  i ]  a  Pr[ x  i ]
E[ x]  a Pr[ x  a]
Sistemi P2P avanzati
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero
di ID di nodi atteso in questo intervallo è 1 e O(log N)
w.h.p.
E[ x]  a Pr[ x  a]
Dim
Abbiamo necessita di alcuni risultati intermedi:
– Disuguaglianza di Marcov
– Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per
Pr[Xi=1]=pi, 0 < pi < 1.
n
Se X   X i ,   E[ X ]  i 1 pi ,   0 allora
i 1
Sistemi P2P avanzati
1 ≤ i ≤ n,
n



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per 1 ≤ i ≤ n, Pr[Xi=1]=pi,
0 < pi < 1.
n
exp(x)=ex
n
Se X 
X i ,   E[ X ] 
pi ,   0 allora

i 1
Dim

i 1



e
Pr[ X  (1   )  ]  
(1 ) 
 (1   )


E[ x]  a Pr[ x  a]
E[ x]
Pr[ x  a ] 
a
Pr[ X  (1   )  ]  Pr[exp( tX )  exp( t (1   )  )]
per ogni reale positivo t.
Se applichiamo la disuguaglianza di Marcov a destra si ottiene
E[exp( tX )]
Pr[ X  (1   )  ] 
exp( t (1   )  )
Sistemi P2P avanzati
Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che
per
1 ≤ i ≤ n, Pr[Xi=1]=pi, 0 < pi < 1.
Se X 
n
 X i ,   E[ X ]  i 1 pi ,   0 allora
n
i 1
Dim
…



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



E[exp( tX )]
Pr[ X  (1   )  ] 
exp( t (1   )  )
n
Poichè le Xi sono
indipendenti,
anche le exp(tXi)
lo sono.
E[exp( tX )]  E[exp( t i 1 X i )]  E[ exp( tX i )]  i 1 E[exp( tX i )]
n
i 1
Sistemi P2P avanzati
n
Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per
n, Pr[Xi=1]=pi, 0 < pi < 1.
n
Se X   X i ,   E[ X ]  i 1 pi ,   0 allora
n
i 1
Dim
…



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



E[exp( tX )]
Pr[ X  (1   )  ] 
exp( t (1   )  )
E[exp( tX )]  i 1 E[exp( tX i )]
n
La variabile exp(tXi) assume valore et con
probabilità pi e 1 con probabilità 1-pi.
Sistemi P2P avanzati
1≤i≤
Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per 1 ≤ i ≤ n,
Pr[Xi=1]=pi, 0 < pi < 1.
n
Se X   X i ,   E[ X ]  i 1 pi ,   0 allora
n
i 1



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



Dim
E[exp( tX )]
Pr[ X  (1   )  ] 
exp( t (1   )  )
…
La variabile exp(tXi) assume valore et con probabilità pi e 1 con
probabilità 1-pi.
E[exp( tX )]  i 1 E[exp( tX i )]  i 1 ( pi et  1  pi )  i 1 (1  pi (et  1))
n
Sistemi P2P avanzati
n
n
Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per
1 ≤ i ≤ n, Pr[Xi=1]=pi, 0 < pi < 1.
n
Se X   X i ,   E[ X ]  i 1 pi ,   0 allora
n
i 1



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



Dim
…
E[exp( tX )]
Pr[ X  (1   )  ] 
exp( t (1   )  )
E[exp( tX )]  i 1 (1  pi (et  1))
n
Poichè 1+x<ex
n
n
n
t
t
t
t
(
1

p
(
e

1
))

exp(
p
(
e

1
))

exp(
p
(
e

1
)
)

exp(

(
e
1))
i1 i
i1 i
i1
i
Sistemi P2P avanzati
Chernoff Bound
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per
1 ≤ i ≤ n, Pr[Xi=1]=pi, 0 < pi < 1.
n
Se
Dim
…
X   X i ,   E[ X ]  i 1 pi ,   0
i 1
n
allora



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)



exp(  (e  1))
Pr[ X  (1   )  ] 
exp( t (1   )  )
t
la espressione a destra assume il valore minimo per t=ln(1+δ).
Sostituendo otteniamo il Teorema.
Sistemi P2P avanzati
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero
di ID di nodi atteso in questo intervallo è 1 e O(log N)

w.h.p.


e
Pr[ X  (1   )  ]  
(1 ) 
Dim
 (1   )

Abbiamo necessita di alcuni risultati intermedi:
– Disuguaglianza di Marcov
– Chernoff Bound
Definiamo



e
F ( ,  )  
(1 ) 
 (1   )


Sistemi P2P avanzati

Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero di
ID di nodi atteso in questo intervallo è 1 e O(log N) w.h.p.

Dim



e

F ( ,  )  
(1 ) 
(
1


)






 e1

 e 
e

F ( ,  )  



(1 ) 
(1 ) 
(
1


)
(
1


)
(
1


)






 (1 )
E quindi per >2e-1,
F ( ,  )  2

Sistemi P2P avanzati
  (1 )
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero di
ID di nodi atteso in questo intervallo è 1 e O(log N) w.h.p.
Dim

  (1 )
F ( ,  )  2
La precedente relazione può essere utilizzata per risolvere il problema:
Per quali valori di δ la probabilità che X>(1+δ)μ è trascurabile ?
Sistemi P2P avanzati
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero di
ID di nodi atteso in questo intervallo è 1 e O(log N) w.h.p.
Dim

  (1 )
F ( ,  )  2
Modelliamo il nostro esperimento come il lancio di N palline in N
contenitori. Sia Yi il numero di palline cadute nell’i-esimo contenitore.
Siamo in presenza di prove ripetute indipendenti. La probabilità di successo
pi=1/N.
La media risulta banalmente 1.
Sistemi P2P avanzati
2m/N
Chord: Risultati
• Lemma
Dato un qualunque intervallo di ampiezza 2m/N, il numero di
ID di nodi atteso in questo intervallo è 1 e O(log N) w.h.p.
Dim

  (1 )
F ( ,  )  2
La probabilità che il numero di palline in un contenitore sia k log2 N è limitata
dalla relazione
F ( ,  )  2

Con δ = k log2N -1. Sostituendo otteniamo
  (1 )
1
F ( ,  )  k
N

Sistemi P2P avanzati
2m/N
Altamente
improbabil
e
Ricapitolando
•
•
•
Le chiavi sono mappate su un array circolare costituito da 2m identificatori;
Il nodo responsabile di una determinata chiave è il primo nodo che la succede in senso
orario;
Ogni nodo n di Chord mantiene due insiemi di vicini:
– Il primo contiene gli m successori del nodo n più il predecessore. Questo insieme
viene usato per dimostrare la correttezza del Routing;
– Un insieme di n nodi costituito dai responsabili delle chiavi distanziate
esponenzialmente dal nodo n, vale a dire l’insieme delle chiavi che si trovano a
distanza 2i da n dove 0  i  m-1. Questo insieme viene usato per dimostrare
l’efficienza del Routing;
m=3
Sistemi P2P avanzati
Ricapitolando
• Le informazioni che il nodo
deve mantenere sugli altri
000
nodi sono log N +111
m + 1110
(O(log N)
WHP);
001
• Il numero di messaggi necessari per fare lookup è m
(O(log N) WHP);
110
010
• L’algoritmo di routing effettua a ogni step il passo più
grande che riesce a fare, senza mai superare il target;
101
011
100
Il costo che si paga quando un nodo lascia o si connette
alla rete è di O(log2N) messaggi WHP;
L’algoritmo in pratica simula un Ipercubo, inoltre si
comporta molto bene in un sistema dinamico.
Sistemi P2P avanzati
Fine Lezione 2
• Domande??
Sistemi P2P avanzati