Ancora esercizi!!!
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per 1 ≤ i ≤ n, Pr[Xi=1]=pi,
Pr[Xi=0]=1-pi con 0 < pi < 1.
Se X 
n
 X i ,   E[ X ]  i 1 pi ,   0
i 1
allora
n



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)


Inoltre se >2e-1  4,43, allora
F ( ,  )  2

Sistemi P2P
  (1 )

Ancora esercizi!!!
• Abbiamo una roulette (Americana) (38 settori) proviamo ad effettuare
380 lanci:
– Quale è la probabilità di beccare lo 0 almeno 41 volte?
– Quanto vale ?
(100) (10) (600) (nessuna delle precedenti)
– Quanto vale ?
(2000)(3)(1)(1000)(nessuna delle precedenti)
– Quale formula applicare?
– Se invece dello 0 consideriamo
0 e 00 almeno 41 volte, cambia qualcosa?
– E se effettuiamo 3800 lanci quale è la
probabilità di beccare lo 0 401 volte?
Sistemi P2P
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;
Condizioni necessarie
ma non sufficienti
– Minimizzare il numero di messaggi necessari per
fare lookup:
• Minimizzare il diametro;
• Minimizzare l’average path lenght (APL), vale a dire,
la distanza media fra due nodi nel grafo.
Sistemi P2P
Es. Chord
• Consideriamo un anello con n=2b nodi;
• Ogni nodo x ha un etichetta a b bit;
jump
• I vicini del nodo x sono i nodi (x+2i) mod 2b 
i = 0,1,…,b-1;
000
111
001
110
010
101
Sistemi P2P
011
100
b=3
000
111
Es. Chord
001
110
010
101
011
100
• Quanto valgono:
– grado?
– diametro?
– average path lenght?
Sistemi P2P
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.
Sistemi P2P
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).
Sistemi P2P
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;
Sistemi P2P
000
111
Es. Chord
001
110
010
101
011
100
• Quanto vale l’average path lenght?
APL 
Sistemi P2P
 d ( x, y )
x , yN
n
2
N denota
l’insieme dei
nodi
b=3
Per semplicità
consideriamo un
sistema Chord like
Sistemi P2P uniformi
k=grado
l=diametro
• 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.
• Chord è uniforme?
Si
• APL sistemi uniformi:
a è un generico
nodo  N
APL 
Sistemi P2P
 d ( x, y )
x , yN
n
2

n  d ( a, x )
xN
n
2

 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ò
Sistemi P2P
000
111
Es. Chord
• Quanto vale l’average
path lenght?
APL 
001
110
010
 d ( a, x )
xN
101
n
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
Sistemi P2P11…1
APL 
 d ( a, x )
xN
n
b b
2
b
log n
2

 
n
2
2
Altre DHT?
Sistemi P2P
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
DHT Routing (Tapestry)
• Tabella di routing (base k=4, digit d=4)
Consideriamo il nodo x con id (x1, x2, x3, x4):
(1+x1, *, *, *)
(x1, 1+x2, *, *)
(x1, x2,1+x3, *)
(x1, x2, x3, 1+x4)
(2+x1, *, *, *)
(x1, 2+x2, *, *)
(x1, x2, 2+x3, *)
(x1, x2, x3, 2+x4)
(3+x1, *, *, *)
(x1, 3+x2, *, *)
(x1, x2, 3+x3, *)
(x1, x2, x3, 3+x4)
(in totale sono k-1  d nodi -- n=dk -> d=logk n)
• Es. tabella di routing (1323 base 4)
(2, 1, 3, 0)
(1, 0, 2, 3)
(1, 3, 3, 2)
(1, 3, 2, 0)
(3, 1, 2, 2)
(1, 1, 1, 3)
(1, 3, 0, 1)
(1, 3, 2, 1)
(0, 3, 2, 1)
(1, 2, 1, 2)
(1, 3, 1, 1)
(1, 3, 2, 2)
Sistemi P2P
DHT Routing (Tapestry)
• Es. tabella di routing (1323 base 4)
(2, 1, 3, 0)
(1, 0, 2, 3)
(1, 3, 3, 2)
(1, 3, 2, 0)
(3, 1, 2, 2)
(1, 1, 1, 3)
(1, 3, 0, 1)
(1, 3, 2, 1)
(0, 3, 2, 1)
(1, 2, 1, 2)
(1, 3, 1, 1)
(1, 3, 2, 2)
(2, 2, 2 ,1)
(3, 2, 3, 0)
(0, 2, 2, 3)
(1, 0, 3, 3)
(1, 1, 3, 3)
(1, 2, 0, 2)
(1, 3, 0, 2)
(1, 3, 1, 1)
(1, 3, 2, 1)
• Supponiamo che il nodo 1323 deve risolvere la query per il nodo
1333 … siccome i primi due digit coincidono (si utlizza la terza
colonna) … la query viene inoltrata al nodo 1332… che avrà un
link al nodo 1333 (nella sua quarta colonna).
• Grado (k-1)  logk n
• Diametro logk n
Sistemi P2P
(1, 3, 3, 0)
(1, 3, 3, 1)
(1, 3, 3, 3)
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;
• Grado: Ogni nodo ha O(d) vicini1 (due per ogni dimensione);
• Il routing avviene in
1
d
din media;
N
4
• Da notare che se usiamo d = log N dimensioni abbiamo O(log N) vicini e il routing
ha costo:
O(log N * N
Sistemi P2P
1
log N
d
passi,
O(dN
)
)  O(log N * 2log N
1
log N
)  O(log N * 2
1
log N
log N
)  O(log N )
DHT: Routing (CAN)
• Join
• Al nuovo nodo viene assegnato un punto (random) nello spazio d
dimensionale.
• La zona viene divisa in due :
• Una parte viene gestita dal nuovo nodo
• La rimanente dal vecchio gestore.
•Leave
•La zona gestita dal nodo che lascia la rete viene passata a un suo vicino e se è
possibile le zone vengono raggruppate di nuovo
• problema: frammentazione delle zone
Sistemi P2P
Dall’Ipercubo alla Butterfly
• Ipercubo
Un nodo u è connesso con tutti i nodi che differiscono di un solo bit da u
Nodi = N=2r
Archi = r 2r-1
Bisezione = N/2
Diametro = log N
• Butterfly (r dimensioni) 2r righe e r+1 colonne
Nodo u =(w,i) w (r bit) =riga, i = colonna (da 0 a r)
u=(w,i) e u’=(w’,i’) sono connessi se
–
–
i’=i+1
w=w’ oppure w e w’ differiscono esattamente nell’iesimo bit
Nodi = (r+1)2r nodi
Archi = r2r+1
Bisezione O(N/log N)
Diametro O(log N)
Sistemi P2P
r=3
Butterfly (FFT) Network
0
000
001
010
011
100
101
110
111
Sistemi P2P
1
2
3
000
001
010
011
100
101
110
111
Butterflies
Sistemi P2P
Decomposing a Butterfly
Sistemi P2P
Decomposing a Butterfly
Sistemi P2P
Decomposing a Butterfly
Sistemi P2P
Decomposing a Butterfly
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Decomposing a Butterfly II
Sistemi P2P
Routing on a Butterfly
0
000
001
010
011
100
101
110
111
Sistemi P2P
1
2
0
000
001
010
011
100
101
110
111
DHT: Routing (Viceroy)
Sistemi P2P
DHT: Routing (Viceroy)
• I nodi sono mappati su una butterfly e contemporaneamente su
un array circolare;
• Ogni nodo ha un identificatore addizionale chiamato livello
(scegliendo a caso nell’intervallo 1 e log n’ dove n’ è una stima
di n);
• 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
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 ≥ 11/n;
– Pr[un nodo non si disconnette]=1-(1/2)k ≥ 1-1/n 
1/n ≥(1/2)k  2k ≥ n  k ≥ log n
Sistemi P2P
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 Ω(log n).
• Esistono in letteratura molti protocolli che hanno grado
e diametro pari a O(log n).
Chord, tapestry,
pasty…
• 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
Sistemi P2P
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 le1 il diametro è l, ogni nodo può raggiungere al
l
k 1
 k l 1nodi (compreso il nodo stesso).
massimo
altri
ki 
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 lO(1).
Sistemi P2P
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
Sistemi P2P
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)).
Sistemi P2P
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
spetta al nodo r è
La rete si disconnette se
nettamente maggiore
uno qualsiasi dei nodi
rispetto agli altri nodi
Sistemi P2P
(escluse le foglie) fallisce
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.
Sistemi P2P
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).
Sistemi P2P
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;
Sistemi P2P
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)
Sistemi P2P
Domande:
•
Consideriamo un sistema P2P con N nodi e grado k = O(log N), quale
delle seguenti affermazioni è vera. (giustificare la risposta)
il diametro è (log N)
il diametro è almeno ½ log N
il diametro è (log N / log log N)
Nessuna delle precedenti
–
–
–
–
•
Dato un sistema P2P uniforme con N nodi, grado k e diametro l,
(giustificare la risposta)
–
–
–
–
Sistemi P2P
k è O(log N) se l è O(log N)
l è (log N) se k è O(log N)
l è (log N/ log log N) se k è O(log N)
Nessuna delle precedenti
Domande:
•
Quale delle seguenti affermazioni è vera (giustificare la risposta)
–
–
–
–
•
I protocolli P2P uniformi sono più efficienti
Non esiste un sistema P2P asintoticamente ottimo
Chord è un sistema non uniforme
Nessuna delle precedenti
Consideriamo l’insieme dei protocolli P2P uniformi, quale delle seguenti
affermazioni è vera . (giustificare la risposta)
–
–
–
–
Chord è un sistema P2P asintoticamente ottimo (rispetto al tradeoff grado - diametro)
Non esiste un sistema P2P asintoticamente ottimo (rispetto al tradeoff grado - diametro)
Non esiste un sistema che offre prestazioni migliori del protocollo Chord (rispetto al
tradeoff grado - diametro)
Nessuna delle precedenti
Sistemi P2P