Ricapitolando….
24
Ricapitolando…. Sistemi P2P puri Sistemi Uniformi Sistemi Non uniformi Abbiamo detto abbastanza Koorde Neighbor of Neighbor routing (NON)
description
Ricapitolando…. Sistemi P2P puri. Sistemi Uniformi. Sistemi Non uniformi. Koorde. Neighbor of Neighbor routing (NON). Abbiamo detto abbastanza. Koorde. E’ un protocollo chord like ring consistent hashing per mappare le chiavi nei nodi De Bruijn graph diametro log n con grado costante - PowerPoint PPT Presentation
Transcript of Ricapitolando….
Ricapitolando….Sistemi P2P puri
Sistemi Uniformi Sistemi Non uniformi
Abbiamo detto abbastanza
Koorde Neighbor of Neighbor routing (NON)
Koorde
E’ un protocollo chord likeE’ un protocollo chord like ringring consistent hashing per mappare le chiavi nei consistent hashing per mappare le chiavi nei
nodinodi
De Bruijn graphDe Bruijn graph diametro log n con grado costantediametro log n con grado costante APL O(log n / log(log n)) con grado O(log n)APL O(log n / log(log n)) con grado O(log n)
de Bruijn graph
Un de Bruijn graph ha un nodo per ogni Un de Bruijn graph ha un nodo per ogni numero binario di b bitsnumero binario di b bits
Ogni nodo ha due archi uscenti, in Ogni nodo ha due archi uscenti, in particolare il nodo m haparticolare il nodo m ha un link al nodo 2m mod 2un link al nodo 2m mod 2bb; ; un link al nodo 2m+1 mod 2un link al nodo 2m+1 mod 2bb;;
In altre parole dato un nodo m per ottenere i suoi In altre parole dato un nodo m per ottenere i suoi due vicini basta fare lo shift a sinistra della due vicini basta fare lo shift a sinistra della codifica binaria di m (eliminando il bit più codifica binaria di m (eliminando il bit più significativo) e poi aggiungere 0 e 1; significativo) e poi aggiungere 0 e 1;
de Bruijn graph
Es.: supponiamo di voler conoscere i vicini Es.: supponiamo di voler conoscere i vicini del nodo 011 alloradel nodo 011 allora facciamo lo shift a sinistra di 011 e otteniamo 0110;facciamo lo shift a sinistra di 011 e otteniamo 0110; eliminiamo il bit più significativo e otteniamo 110;eliminiamo il bit più significativo e otteniamo 110; i due vicini sono quindi:i due vicini sono quindi:
110 + 0 = 110110 + 0 = 110
110 + 1 = 111 110 + 1 = 111
Denotiamo conDenotiamo conmm0 il primo vicino di m0 il primo vicino di m
mm1 il secondo vicino di m1 il secondo vicino di m
000
001
011
111
110
101
100010
b=3
de Bruijn graph
Routing Routing Supponiamo di voler passare dal nodo s=(sSupponiamo di voler passare dal nodo s=(s00,s,s11,…,s,…,sb-1b-1) )
al nodo t=(tal nodo t=(t00,t,t11,…,t,…,tb-1b-1))
passo 1: s passo 1: s → s→ s11 = s = stt0 0 ss1 1 =(s=(s11,s,s22,…,t,…,t00) )
passo 2: passo 2: ss11 → s→ s22 = s = s11tt1 1 ss2 2 =(s=(s22,…, t,…, t00,t,t11) )
passo 3: passo 3: ss22 → s→ s33 = s = s22tt2 2 ss3 3 =(…, t=(…, t00,t,t11,t,t22))
passo b: passo b: ssb-1b-1 → s→ sbb = s = sb-1b-1ttb-1 b-1 ssb b =(t=(t00,t,t11,…, t,…, tb-1b-1)=t)=t
000
001
011
111
110
101
100010
b=3
b passidiametro = b = log n
de Bruijn graph
Routing Routing Es.: b=3 vogliamo passare dal nodo 011 al nodo 100Es.: b=3 vogliamo passare dal nodo 011 al nodo 100
Passo 1: da 011 a 111Passo 1: da 011 a 111
Passo 2: da 111 a 110Passo 2: da 111 a 110
Passo 3: da 110 a 100Passo 3: da 110 a 100
000
001
011
111
110
101
100010
b=3
011
100
111
110
de Bruijn graph
m.lookup(k,ks)m.lookup(k,ks)if k=m if k=m
return mreturn m
elseelse
t=m t=m topbit(ks)topbit(ks)
return t.lookup(k,ks<<1)return t.lookup(k,ks<<1)
000
001
011
111
110
101
100010
b=3
m nodo sorgente k nodo destinazione
La prima chiamata è
m.lookup(k,k)
de Bruijn graph
000
001
011
111
110
101
100010
b=3
2
,
),(
n
yxd
APL Nyx
000
101
100
011
010
001
110
111
b=3
E’ difficile da guardare figuriamoci da implementare
secondo vicino
primo vicino
de Bruijn graph
2
,
),(
n
yxd
APL Nyx
000
101
100
011
010
001
110
111
b=3
• La maggior parte delle applicazioni usa un numero di nodi effettivo molto più piccolo di 2b.
•Evitare collisioni nell’assegnare chiavi;
• In generale il sistema deve poter evolversi (n deve poter variare).
E se manca un nodo?
E se ne mancano tanti?
b è di solito 160 (SHA)2160
Gli indirizzi IP sono 232
de Bruijn graph: Koorde
2
,
),(
n
yxd
APL Nyx
b=160
•Aggiungiamo due ulteriori link per ogni nodo:
•Un link al successore nell’anello
•Un link al predecessore di 2m mod 2b
Consideriamo ora un ring non completo
Il nodo m ha due link ai nodi immaginari:
2m mod 2b
2m+1 mod 2bm
Link a nodi effettivi
Koorde
2
,
),(
n
yxd
APL Nyx
b=160
•La nuova procedura di routing, invece di attraversare i nodi del grafo di de Bruijn ne attraversa i predecessori;
• 2 fasi
•Cerca il predecessore di si
•Passa al nuovo nodo si+1
000
001
011
111
110
101
100010
b=3
Koorde
2
,
),(
n
yxd
APL Nyx
m.lookup(k,ks)m.lookup(k,ks)if k=m if k=m
return mreturn m
elseelse
t=mt=mtopbit(ks)topbit(ks)
return t.lookup(k,ks<<1)return t.lookup(k,ks<<1)
m.lookup(k,ks,i)m.lookup(k,ks,i)if k if k (m, m.successor] return successor(m, m.successor] return successor
else if i else if i (m, m.successor] (m, m.successor]
return d.lookup(k,ks<<1, ireturn d.lookup(k,ks<<1, itopbit(ks))topbit(ks))
else else
return m.successor.lookup(k,ks,i)return m.successor.lookup(k,ks,i)
Abbiamo raggiunto la destinazione
?
Abbiamo raggiunto il predecessore del nodo immaginario?
d è il link al predecessore di 2m mod 2b
Koorde
2
,
),(
n
yxd
APL Nyx
m.lookup(k,ks,i)m.lookup(k,ks,i)
11 if k if k (m, m.successor] return successor(m, m.successor] return successor
22 else if i else if i (m, m.successor] (m, m.successor]
33 return d.lookup(k,ks<<1, ireturn d.lookup(k,ks<<1, itopbit(ks))topbit(ks))
44 else else
55 return m.successor.lookup(k,ks,i)return m.successor.lookup(k,ks,i)
Cerchiamo il predecessore del
nodo immaginario?
Passiamo al nuovo nodo del
grafo di de Bruijn
Il passo 3 viene eseguito al massimo b volte
Quante volte eseguiamo il passo 5, vale a dire quanto impieghiamo per trovare il predecessore di un nodo immaginario?
Koorde2
,
),(
n
yxd
APL Nyx
LemmaLemma
Il numero medio di passi, durante una operazione di lookup in Il numero medio di passi, durante una operazione di lookup in Koorde è 3b Koorde è 3b
ProvaProva
Nel passare dal nodo immaginario i al nodo immaginario Nel passare dal nodo immaginario i al nodo immaginario iitopbit(ks), ci muoviamo dal nodo m=predecessor(i) al nodo topbit(ks), ci muoviamo dal nodo m=predecessor(i) al nodo m.dm.d (predecessor di 2m mod 2 (predecessor di 2m mod 2bb) e poi ci spostiamo usando i ) e poi ci spostiamo usando i successor successor pointer fino a raggiungere il predecessor del nodo pointer fino a raggiungere il predecessor del nodo immaginario iimmaginario itopbit(ks), topbit(ks),
Le frecce gialle sono b
Quante sono le frecce verdi?
Ogni hop su un grafo di de Bruijn si traduce in una path in koorde.
Quanto è lunga questa path in
media?
Koorde
2
,
),(
n
yxd
APL Nyx
I nodi attraversati fra due frecce gialle sono i nodi che si trovano fra 2m e 2i+1I nodi attraversati fra due frecce gialle sono i nodi che si trovano fra 2m e 2i+1
Quanti nodi ci sono nell’intervallo I =(2m,2i+1)?Quanti nodi ci sono nell’intervallo I =(2m,2i+1)?
|I|=(2i-2m)/(2|I|=(2i-2m)/(2bb/n)/n)
Sapendo che il valore atteso di i-m= 2Sapendo che il valore atteso di i-m= 2bb/n/n
II(2*2(2*2bb/n )/(2/n )/(2bb/n) =2/n) =2
In totale dunque per ogni freccia In totale dunque per ogni freccia giallagialla vi sono in media 2 frecce vi sono in media 2 frecce verdiverdi
In totale 3b passi In totale 3b passi
mi
2m2i2i+1
Distanza media fra due nodi 22bb/n/n
Koorde
2
,
),(
n
yxd
APL Nyx
m.lookup(k,ks,i)m.lookup(k,ks,i)
11 if k if k (m, m.successor] return successor(m, m.successor] return successor
22 else if i else if i (m, m.successor] (m, m.successor]
33 return d.lookup(k,ks<<1, ireturn d.lookup(k,ks<<1, itopbit(ks))topbit(ks))
44 else else
55 return m.successor.lookup(k,ks,i)return m.successor.lookup(k,ks,i)
Poiché m è responsabile di tutti i nodi immaginari che vanno da m e m.successor è possibile migliorare ulteriormente l’algoritmo.
La distanza fra m e il suo successore è con alta probabilità maggiore di 2b/n2
Koorde
2
,
),(
n
yxd
APL Nyx
Claim
La distanza fra m e il suo successore è con alta probabilità maggiore di 2b/n2
Prova (Sketch)
Fissato un nodo la probabilità che un altro nodo qualsiasi sia più vicino di 2b/n2 è (2b/n2)/2b= 1/n2.
La probabilità che nessuno degli altri n-1nodi sia più vicino di 2b/n2 è (1-1/n2)n-1>1-1/n.
Distanza
media 2b/nDistanza
2b/n2
Koorde
2
,
),(
n
yxd
APL Nyx
Abbiamo dimostrato che la distanza fra m e il suo successore è con alta probabilità maggiore di 2b/n2
Questo significa che il nodo m è responsabile di nodi immaginari con tutte le possibili combinazioni degli ultimi log(2b/n2)= b-2logn bit.
Scegliendo come nodo immaginario iniziale il nodo che ha gli ultimi b-2logn bit uguali a i primi b-2logn del nodo destinazione, dobbiamo effettuare alla fine soltanto (b-(b-2logn))*3 passi = 6logn passi circa.
Koorde
2
,
),(
n
yxd
APL Nyx
Koorde (base 2)Koorde (base 2) Ha APL O(log n) con grado costanteHa APL O(log n) con grado costante Si può dimostrare che anche il diametro è con Si può dimostrare che anche il diametro è con
alta probabilità (WHP) O(log n).alta probabilità (WHP) O(log n).
Koorde (base k)Koorde (base k) Utilizziamo i grafi di de Bruijn base kUtilizziamo i grafi di de Bruijn base k Scegliamo k = log nScegliamo k = log n
de Bruijn graph base kPer ogni k, in un grafo di de Bruijn base k, ogni nodo m è Per ogni k, in un grafo di de Bruijn base k, ogni nodo m è connesso a altri k nodi:connesso a altri k nodi: km mod kkm mod kbb
km+1 mod kkm+1 mod kbb
…… km+(k-1) mod kkm+(k-1) mod kbb
EsempioEsempio k=4, b=3, n=kk=4, b=3, n=kbb=64 e m=321=64 e m=32144= 57= 57
Il primo vicino è 210Il primo vicino è 21044=36=36
Il secondo vicino è 211Il secondo vicino è 21144=37=37
Il terzo vicino è 212Il terzo vicino è 21244=38=38
Il quarto vicino è 213Il quarto vicino è 21344=39=39
000
001
011111
110
101
100010
b=3
k=2
Diametro O(logk n)
de Bruijn graph base kEsempioEsempio k=3, b=2, n=kk=3, b=2, n=kbb=9=9
b=160
00
01
12
11
10b=2
k=3
02
22
21
20
Koorde base kk+1 nuovi linkk+1 nuovi link Il link al Il link al successoresuccessore nell’anello nell’anello k link ai k link ai predecessoripredecessori dei vicini dei vicini
E’possibile fare routing con grado k e APL O(logE’possibile fare routing con grado k e APL O(logkk n) n)
b=160
00
0112
11
10 b=2
k=3
02
22
21
20
2
,
),(
n
yxd
APL Nyx
Koorde base k
Scegliendo k = O(log n):Scegliendo k = O(log n): Grado = O(log n)Grado = O(log n) APL = O(log n / log (log n))APL = O(log n / log (log n))
SvantaggiSvantaggi Bisogna stimare n a priori;Bisogna stimare n a priori; Non è possibile cambiare il grado in un sistema attivo;Non è possibile cambiare il grado in un sistema attivo; E’ molto complicato stabilizzare la rete;E’ molto complicato stabilizzare la rete;
00
0112
11
10 b=2
k=3
02
2221
20
Ricapitolando….Sistemi P2P puri
Sistemi Uniformi Sistemi Non uniformi
Koorde Neighbor of Neighbor routing (NON)
