Sistemi Peer To Peer (P2P)
Avanzati
Gennaro Cordasco
cordasco[@]dia.unisa.it
 http://www.dia.unisa.it/~cordasco
 Laboratorio ISISLAB2 (L8 a Baronissi)

P2P: Alcune definizioni
Sistema distribuito nel quale ogni nodo ha identiche
capacità e responsabilità e tutte le comunicazioni sono
potenzialmente simmetriche;
Siamo interessati ai sistemi P2P di seconda
generazione, quelli che supportano DHT (Distributed
Hash Table);
P2P Puro;
Es: Chord
Analizzeremo alcuni protocolli Chord like;




Si basano sul ring;
Utilizzano consistent hashing;
Join/Leave uguali a Chord;
Cambiano i vicini (finger) e l’algoritmo di routing;
P2P: Scalabilità
Il lavoro richiesto a un determinato nodo nel
sistema non deve crescere (o almeno cresce
lentamente) in funzione del numero di nodi nel
sistema;
La scalabilità di un protocollo dipende:


dalla topologia della rete;
dall’algoritmo di routing.
Obiettivi:


Minimizzare il numero di messaggi necessari per
fare lookup;
Minimizzare, per ogni nodo, le informazioni relative
agli altri nodi;
Dal punto di vista topologico
Consideriamo una rete P2P come un
grafo G=(V,E), dove V è l’insieme dei
nodi nel sistema e E rappresenta
l’insieme delle interconnessioni fra essi:

Minimizzare, per ogni nodo, le informazioni
relative agli altri nodi:
minimizzare il grado dei nodi;

Minimizzare il numero di messaggi
necessari per fare lookup:
Condizioni necessarie
ma non sufficienti
Minimizzare il diametro;
Minimizzare l’average path lenght (APL), vale a
dire, la distanza media fra due nodi nel grafo.
Es. Chord
Consideriamo un anello con n=2b nodi;
Ogni nodo x ha un etichetta a b bit che
denotiamo con id(x);
jump
I vicini del nodo x sono i nodi (x+2i) mod 2b
 i = 0,1, ,b-1;
000
111
001
110
010
101
011
100
b=3
000
111
Es. Chord
001
110
010
101
011
100
Quanto valgono:



grado?
diametro?
average path lenght?
Il grado è b = log n
b=3
000
111
Es. Chord
001
110
010
101
011
b=3
100
Dati due nodi x e y la loro distanza d(x,y) è
uguale al numero di “1” che ci sono nella stringa
binaria (y-x) mod 2b.
Infatti i jump necessari per passare dal nodo x al
nodo y sono quelli relativi alla posizione degli “1”
nella stringa binaria (y-x) mod 2b.
000
111
Es. Chord
001
110
Il diametro è b = log
n
010
101
011
100
Calcoliamo la distanza tra il nodo 3 e il nodo 6:

(6-3) mod 8 = 3 = 011 (un jump da 2 e uno da 1).
Calcoliamo la distanza tra il nodo 6 e il nodo 3:

(3-6) mod 8 = 5 = 101 (un jump da 4 e uno da 1).
d(x,y) può essere
diverso da d(y,x)
Chord non è
simmetrico
b=3
diametro
Anello
n -1
Chord e altri
Grafo
completo
O(log n)
1
1
O(log n)
n -1
grado
n è il numero dei peer;
000
111
Es. Chord
001
110
010
101
011
100
Quanto vale l’average path lenght?
APL 
 d ( x, y )
x , yN
n
2
N denota
l’insieme dei
nodi
b=3
Sistemi P2P uniformi
k=grado
l=diametro
Per semplicità
consideriamo un
sistema Chord like
Denotiamo con Jx,i l’iesimo jump del nodo x;
Un sistema P2P viene detto uniforme, se per
ogni coppia di nodi x e y, si ha Jx,i = Jy,i  i
=1,2,…,k.
Si
Chord è uniforme?
a è un generico
APL sistemi uniformi:
nodo  N
APL 
 d ( x, y )
x , yN
n2

n  d ( a, x )
xN
n2

 d ( a, x )
xN
n
Sistemi P2P uniformi
Vantaggi:





Facili da implementare e da analizzare;
Algoritmo di routing semplice (greedy);
Routing locale, la procedura di lookup interessa solo i nodi
che si trovano fra sorgente e destinazione;
Non c’è congestione sui nodi, vale a dire il traffico generato
dai messaggi di lookup è più o meno uguale per tutti i nodi.
Fast bootstrap:
Poiché tutti i nodi utilizzano gli stessi jump, è possibile utilizzare
la tabella di routing del proprio predecessore per velocizzare
notevolmente l’operazione di join;
Svantaggi:

Sfortunatamente non sono gli algoritmi più efficienti.
Lo vediamo
fra un pò
000
111
Es. Chord
Quanto vale l’average
path lenght?
APL 
001
110
010
 d ( a, x )
xN
101
n
APL 
 d ( x, y )
x , yN
n2
011
b=3
100
Scegliamo come nodo sorgente
il nodo a=00…0;
La distanza fra a e il generico
nodo x è uguale al numero di bit
a 1 nella codifica binaria di x;
00…0
00…1
a
…
11…0
11…1
APL 
 d ( a, x )
xN
n
b b
2
b
log n
2

 
n
2
2
Fault tolerance and degree
k=grado
l=diametro
Il grado di una rete P2P soggetta a fallimenti deve
essere almeno Ω(log n).
Infatti, Ω(log n) risulta essere il minimo valore che
permette alla rete di rimanere connessa anche nelle
condizioni più proibitive;
Sketch:
Supponiamo che tutti i nodi della rete possono fallire con
probabilità ½;

Ovviamente un nodo rimane disconnesso se tutti i suoi vicini
si disconnettono contemporaneamente;

Vogliamo che la probabilità che un nodo non si disconnetta
sia ≥ 1-1/n;

Pr[un nodo non si disconnette]=1-(1/2)k ≥ 1-1/n 
1/n ≥(1/2)k  2k ≥ n  k ≥ log n

In realtà la prova è
un po’ più
complicata, ma
questa rende bene
l’idea
P2P: grado e diametro
Abbiamo visto che il grado di una rete P2P
soggetta a fallimenti deve essere almeno
Chord, tapestry,
Ω(log n).
pasty…
Esistono in letteratura molti protocolli che
hanno grado e diametro pari a O(log n).
E’ possibile fare di meglio?


Fissiamo il grado pari O(log n), qual è il minimo
diametro che riusciamo ad ottenere?
Fissiamo il grado pari O(log n), qual è il minimo
APL che riusciamo ad ottenere?

Stiamo cercando
dei Lower Bound
k=grado
l=diametro
P2P: Lower Bound
Teorema
Dato un grafo G=(V,E) con |V| = n e grado k = O(log n),
allora il diametro l = Ω(log n / log (log n)).
Prova
Dato che il grado è k e il diametro è l, ogni nodo può raggiungere
l 1
al massimo l k i  k  1  k l 1 altri nodi (compreso il nodo stesso).
i 0
k 1
Poiché il grafo deve essere connesso, allora kl+1 > n 
l > logk (n) - 1 = Ω(log n / log (log n)).
Ma allora Chord
non è ottimale!!!
Con argomentazioni analoghe si può dimostrare che anche l’APL
è Ω(log n / log (log n)) in quanto la maggior parte dei nodi si trova
a distanza l-O(1).
P2P: Lower Bound (Esempio 1)
r
k = log n;
k-1
…
…
…
Ogni nodo ha grado k (k-1 figli e la radice dell’albero);
r raggiunge qualsiasi nodo in al più logk-1 n = O(log n / log (log n))
passi.
Il diametro è 1 + logk-1 n =O(log n / log (log n)).
Il grado in
ingresso della
radice è n-1
P2P: Lower Bound (Esempio 2)
r
k = log n;
k/2 -1
…
…
…
Ogni nodo ha grado(entrante più uscente) k ( k/2 -1 ai figli e 1 al padre (x2));
r raggiunge qualsiasi nodo in al più logk/2 -1 n = O(log n / log (log n)) passi.
Ogni nodo raggiunge r in al più logk/2 -1 n = O(log n / log (log n)) passi
Il diametro è O(log n / log (log n)).
P2P: Lower Bound (Esempio 3)
r
k = 6;
2
…
…
Ogni nodo ha grado(entrante più uscente) 6 ( 2 ai figli e 1 al padre (x2));
r raggiunge qualsiasi nodo in al più log n passi.
Ogni nodo raggiunge r in al più log n passi
Il diametro è 2 log n.
La mole di traffico che
La rete si disconnette se
uno qualsiasi dei nodi
(escluse le foglie) fallisce
spetta al nodo r è
nettamente maggiore
rispetto agli altri nodi
P2P: Lower Bound sistemi uniformi
Teorema
Consideriamo un sistema P2P uniforme con n
nodi, sia k il numero dei vicini che ogni nodo
mantiene, allora il lower bound per il diametro è
1/2log n (l ≥ 1/2log n ) se k  1/2log n.
Prova
Sia J = {Ji}1i k
Consideriamo senza perdita di generalità un nodo
x e calcoliamo tutte le n path fra x e tutti gli altri
nodi.
P2P: Lower Bound sistemi uniformi
x compreso
Sia P = {tutte le path da x agli altri n nodi}
Sia f: P(N{0})k+1
 p  P denotiamo con ap,i il numero di jump di
taglia Ji usati nella path p con 1  i  k.
Es
Sia J={1,4,15}
Sia p una path dal nodo 0 al nodo 9, (es. 4+4+1).
Allora ap,1 = 1 , ap,2 = 2 e ap,3 = 0.
P2P: Lower Bound sistemi uniformi
x compreso
Sia P = {tutte le path da x agli altri n nodi}
Sia f: P(N{0})k+1
k
Ovviamente  a p ,i  l poiché l è il diametro
i 1
della rete.
k
Definiamo a p , 0  l 
a p ,i e ovviamente a p , 0  0.

i 1
f(p):=(ap,0,ap,1,…ap,k).
P2P: Lower Bound sistemi uniformi
P = {tutte le path da x agli altri n nodi}
f: P(N{0})k+1
Claim f(p):=(ap,0,ap,1,…ap,k)
Dominio
Codominio
f è iniettiva (one to one)
Prova
Per assurdo supponiamo che esistano p e q  P tali che
ap,i = aq,i  0  i  k.
k
k
a
i 1
p ,i
J i   aq ,i J i .
i 1
Quindi partendo dal nodo x, entrambe le path terminano
nello stesso nodo destinazione.
Assurdo: per definizione le path in P terminano in nodi
diversi.
P2P: Lower Bound sistemi uniformi
Poiché f è iniettiva, la dimensione del codominio
è maggiore o uguale alla dimensione del dominio
(vale a dire |C| ≥ |D|=n).
Quanto vale la dimensione del codominio?
La dimensione del codominio è uguale al numero
di vettori (a0,a1,…,ak) tali che a0+a1+…+ak =l
P2P: Lower Bound sistemi uniformi
Supponiamo di avere l biglie uguali e k+1
contenitori diversi.
…
l
…
k+1
La dimensione del codominio è uguale al numero
di modi in cui è possibile disporre l biglie
identiche in k+1 contenitori diversi.
P2P: Lower Bound sistemi
uniformi
Primo contenitore vuoto
Rappresentiamo con “0” le
“1” i contenitori
00010000010110100
00110001101000000
10001010100100000
Secondo contenitore 3 biglie
biglie
separiamo
Terzoe
contenitore
1 biglia con
Quarto contenitore 1 biglia
Quinto contenitore 2 biglie
Sesto contenitore 5 biglie
Alcuni esempi 6 contenitori
e 12 biglie
00000110001000011
Con k “1” possiamo rappresentare k+1 contenitori,
mentre con l “0” possiamo rappresentare l biglie;
P2P: Lower Bound sistemi uniformi
00010000010110100
00110001101000000
10001010100100000
Alcuni esempi 6 contenitori
e 12 biglie
00000110001000011
La dimensione del codominio è uguale al numero
di combinazioni di k elementi su l+k;
La dimensione del codominio è uguale al numero
di combinazioni di l elementi su l+k;
P2P: Lower Bound sistemi uniformi
Sappiamo che
l  k  l  k 
  

| C | 
 k   l 
| C | n
l  k  l  k 

  
  n
 k   l 
(1)
Ci rimane da dimostrare che se k 1/2log n
allora l ≥ 1/2log n .
P2P: Lower Bound sistemi uniformi
l  k  l  k 

  
  n
k
l

 

Proviamo che l≥k
Per assurdo l<k
Stirling approx
x
l  k   x x
x
 
E’ facile osservare che  k 2x è crescente
  x! 2 2x in l,
e
e
l  k  k  k 

quindi    

 k   k 
 l  k   k  k   2k  (2k )! 2 2 (2k ) (2k ) 2 k e 2 k

  
    


k k
k k
2k k e
2k k e
 k   k   k  k! k!
2 k (2k )
kk 2 k
Assurdo
2k
( 2k )
 2k
k
2k
 2k 
 
 k 
l  k  l  k 

  
  n
 k   l 
2k
 22k  n
Per ipotesi
k  1/2log n.
P2P: Lower Bound sistemi uniformi
l  k  l  k 

  
  n
 k   l 
lk
Proviamo che l ≥ 1/2log n
Per assurdo l < 1/2log n
l  k 
E’ facile osservare che  k  è crescente in k,


quindi
l  k  l  l 

  
  2 2l  n
 k   l 
Assurdo, quindi l ≥ 1/2log n CVD.
P2P: Lower Bound sistemi uniformi
Teorema
Consideriamo un sistema P2P uniforme con n
nodi, sia k il numero dei vicini che ogni nodo
mantiene, allora il diametro è Ω(log n) se k =
O(log n).
Prova
La prima parte è identica al teorema precedente
l  k  l  k 

  
  n
 k   l 
Solo conti,
abbastanza noiosi.

diametro
Anello
n -1
Chord e altri
Grafo
completo
LB
O(log n)
O(log n/ log(log n))
1
1
O(log n)
n -1
grado
n è il numero dei peer;
Grafico funzione binomiale
n
   y
 x
l  k  l  k 

  
  n
k
l

 

y
1
n/2
x
n-1
Come scegliere l e k?
n
   y
 x
l  k  l  k 

  
  n
k
l

 

Supponiamo di avere un limite sulla somma di grado e diametro
Es l+k = 16
l=k è la
scelta
migliore
Quali sono i valori di l e k ottimali?
14000
12000
10000
8000
6000
4000
2000
0
0
1
2
3
4
5
6
7
8
L
9
10
11
12
13
14
15
16
Alcune osservazioni
Chord è asintoticamente ottimo

Uniforme
Facili da implementare e da analizzare;
Algoritmo di routing semplice (greedy);
Non c’è congestione sui nodi;
Fast bootstrap:
E’ possibile fare meglio di
Routing locale;
Chord, si può arrivare a

GAP
(0.72021 log n, 0.72021 log
n)
Chord (log n, log n)
LB
(½ log n, ½ log n)
Ricapitolando….
Sistemi P2P puri
Sistemi Uniformi
Sistemi Non uniformi
Koorde
Abbiamo detto
abbastanza
Neighbor of Neighbor
routing (NON)