Lezione 5Lezione 5

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 consistent hashing per mappare le

chiavi nei nodichiavi nei nodi

De Bruijn graphDe Bruijn graph APL O(log n) con grado costanteAPL O(log n) con grado costante APL O(log n / log(log n)) con grado O(log APL O(log n / log(log n)) con grado O(log

n)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 In altre parole dato un nodo m per ottenere i suoi due vicini basta fare lo shift a sinistra suoi due vicini basta fare lo shift a sinistra della codifica binaria di m (eliminando il bit della codifica binaria di m (eliminando il bit più significativo) e poi aggiungere 0 e 1; più significativo) e poi aggiungere 0 e 1;

de Bruijn graph

Es.: supponiamo di voler conoscere i Es.: supponiamo di voler conoscere i vicini del nodo 011 alloravicini del nodo 011 allora facciamo lo shift a sinistra di 011 e otteniamo facciamo lo shift a sinistra di 011 e otteniamo

0110;0110; eliminiamo il bit più significativo e otteniamo eliminiamo il bit più significativo e otteniamo

110;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=(t) al 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 Es.: b=3 vogliamo passare dal nodo 011 al nodo

100100Passo 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

Routing ottimizzatoRouting ottimizzato Calcolo la dimensione j del più grande suffisso del Calcolo la dimensione j del più grande suffisso del

nodo sorgente s che è anche prefisso del nodo nodo sorgente s che è anche prefisso del nodo destinazione t.destinazione t.

Il routing inizia al passo j+1Il routing inizia al passo j+1 Es.: b=3 vogliamo passare dal nodo s=011 al Es.: b=3 vogliamo passare dal nodo s=011 al

nodo t=100nodo t=100Passo 2: da 011 a 110Passo 2: da 011 a 110

Passo 3: da 110 a 100Passo 3: da 110 a 100000

001

011

111

110

101

100010

b=3

011

100

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

<<j<<j)

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 Il numero medio di passi, durante una operazione di lookup in Koorde è 3b lookup in 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 topbit(ks), ci muoviamo dal nodo m=predecessor(i) al nodo nodo m.dm.d (predecessor di 2m mod 2 (predecessor di 2m mod 2bb) e poi ci spostiamo ) e poi ci spostiamo usando i usando i successor successor pointer fino a raggiungere il pointer fino a raggiungere il predecessor del nodo immaginario ipredecessor del nodo immaginario i topbit(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 I nodi attraversati fra due frecce gialle sono i nodi che si trovano fra 2m e 2i+12i+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-mSapendo che il valore atteso di i-m≤≤ 2 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 Si può dimostrare che anche il diametro

è con alta probabilità (WHP) O(log n).è con 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 Per ogni k, in un grafo di de Bruijn base k, ogni nodo m è connesso a altri k nodi:nodo m è 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)