Lezione 5
Ricapitolando….
Sistemi P2P puri
Sistemi Uniformi
Sistemi Non uniformi
Koorde
Abbiamo detto
abbastanza
Neighbor of Neighbor
routing (NON)
Koorde
E’ un protocollo chord like


ring
consistent hashing per mappare le chiavi nei nodi
De Bruijn graph


APL O(log n) con grado costante
APL O(log n / log(log n)) con grado O(log n)
de Bruijn graph
Un de Bruijn graph ha un nodo per ogni
numero binario di b bits
Ogni nodo ha due archi uscenti, in particolare
il nodo m ha
un link al nodo 2m mod 2b;
b
 un link al nodo 2m+1 mod 2 ;
In altre parole dato un nodo m per ottenere i suoi due
vicini basta fare lo shift a sinistra della codifica
binaria di m (eliminando il bit più significativo) e poi
aggiungere 0 e 1;

de Bruijn graph
Es.: supponiamo di voler conoscere i vicini del
nodo 011 allora



facciamo lo shift a sinistra di 011 e otteniamo 0110;
eliminiamo il bit più significativo e otteniamo 110;
i due vicini sono quindi:
110 + 0 = 110
110 + 1 = 111
Denotiamo con
m0 il primo vicino di m
m1 il secondo vicino di m
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
Routing

Supponiamo di voler passare dal nodo s=(s0,s1,…,sb-1) al
nodo t=(t0,t1,…,tb-1)
passo 1: s → s1 = st0
passo 2: s1 → s2 = s1t1
passo 3: s2 → s3 = s2t2
passo b: sb-1 → sb = sb-1tb-1
s1 =(s1,s2,…,t0)
s2 =(s2,…, t0,t1)
s3 =(…, t0,t1,t2)
sb =(t0,t1,…, tb-1)=t
000
b passi
diametro = b = log n
100
010
101
001
110
011
111
b=3
de Bruijn graph
Routing

Es.: b=3 vogliamo passare dal nodo 011 al nodo 100
Passo 1: da 011 a 111
Passo 2: da 111 a 110
Passo 3: da 110 a 100
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
m nodo sorgente
k nodo destinazione
m.lookup(k,ks)
if k=m
return m
else
t=m  topbit(ks)
return t.lookup(k,ks<<1)
La prima
chiamata è
m.lookup(k,k
)
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
Routing ottimizzato



Calcolo la dimensione j del più grande suffisso del nodo
sorgente s che è anche prefisso del nodo destinazione t.
Il routing inizia al passo j+1
Es.: b=3 vogliamo passare dal nodo s=011 al nodo t=100
Passo 2: da 011 a 110
Passo 3: da 110 a 100
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
m nodo sorgente
k nodo destinazione
m.lookup(k,ks)
if k=m
return m
else
t=m  topbit(ks)
return t.lookup(k,ks<<1)
La prima chiamata
è m.lookup(k,k <<j)
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
000
111
001
010
110
101
E’ difficile da
guardare figuriamoci
da implementare 
APL 
 d ( x, y )
x , yN
n2
011
b=3
100
primo
vicino
secondo
vicino
000
100
010
101
001
110
011
111
b=3
de Bruijn graph
000
E se manca un nodo?
111
001
010
110
101
E se ne mancano tanti?
APL 
 d ( x, y )
x , yN
n2
011
b è di solito 160 (SHA)
2160
Gli indirizzi IP sono
232
b=3
100
• 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).
de Bruijn graph: Koorde
Consideriamo ora un ring
non completo
Il nodo m ha due link ai nodi
immaginari:
APL 
 d ( x, y )
x , yN
n
2
2m mod 2b
m
b=160
2m+1 mod 2b
•Aggiungiamo due ulteriori link per ogni nodo:
•Un link al successore nell’anello
•Un link al predecessore di 2m mod 2b
Link a nodi
effettivi
Koorde
000
100
010
101
001
110
APL 
011
 d ( x, y )
x , yN
n2
111
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
b=3
Koorde
m.lookup(k,ks)
APL 
 d ( x, y )
x , yN
n2
Abbiamo
raggiunto la
destinazione
?
m.lookup(k,ks,i)
if k=m
return m
else
t=mtopbit(ks)
return t.lookup(k,ks<<1)
Abbiamo raggiunto
il predecessore del
nodo immaginario?
if k (m, m.successor] return successor
else if i (m, m.successor]
return d.lookup(k,ks<<1, itopbit(ks)) d è il link al
predecessore
else
di 2m mod 2b
return m.successor.lookup(k,ks,i)
Koorde
m.lookup(k,ks,i)
1 if k (m, m.successor] return successor
2 else if i (m, m.successor]
3
return d.lookup(k,ks<<1, itopbit(ks))
4
else
5
return m.successor.lookup(k,ks,i)
Passiamo al
nuovo nodo del
grafo di de Bruijn
APL 
 d ( x, y )
x , yN
n2
Cerchiamo il
predecessore del
nodo immaginario?
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?
Koorde
Lemma
Il numero medio di passi, durante una operazione di
lookup in Koorde è 3b
Prova
Ogni hop su un grafo di
Bruijn si traduce in
Nel passare dal nodo immaginario i al de
nodo
una path in koorde.
immaginario itopbit(ks), ci muoviamoQuanto
dal nodo
è lunga questa
pathdi
in 2m
media?
m=predecessor(i) al nodo m.d (predecessor
mod
2b) e poi ci spostiamo usando i successor pointer fino a
raggiungere il predecessor del nodo immaginario
itopbit(ks),
Le frecce gialle sono b
Quante sono le frecce verdi?
APL 
 d ( x, y )
x , yN
n2
Koorde
2i+1
2i
2m
APL 
 d ( x, y )
x , yN
n2
i
I 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)?
Distanza media
|I|=(2i-2m)/(2b/n)
fra due nodi 2b/n
Sapendo che il valore atteso di i-m≤ 2b/n
I(2 2b/n )/(2b/n) =2
In totale dunque per ogni freccia gialla vi sono in media
2 frecce verdi
In totale 3b passi
m
Koorde
m.lookup(k,ks,i)
1 if k (m, m.successor] return successor
2 else if i (m, m.successor]
3
return d.lookup(k,ks<<1, itopbit(ks))
4
else
5
return m.successor.lookup(k,ks,i)
APL 
 d ( x, y )
x , yN
n2
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
APL 
Claim
 d ( x, y )
x , yN
n2
La distanza fra m e il suo successore è con alta probabilità maggiore
di 2b/n2
Prova (Sketch)
Distanza
Distanza
media 2b/n
2b/n2
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.
Koorde
APL 
 d ( x, y )
x , yN
n2
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
APL 
 d ( x, y )
x , yN
n2
Koorde (base 2)


Ha APL O(log n) con grado costante
Si può dimostrare che anche il diametro è con alta
probabilità (WHP) O(log n).
Koorde (base k)


Utilizziamo i grafi di de Bruijn base k
Scegliamo k = log n
de Bruijn graph base k
Per ogni k, in un grafo di de Bruijn base k,
ogni nodo m è connesso a altri k nodi:




km mod kb
km+1 mod kb
…
km+(k-1) mod kb
000
100
010 101
001
110
011
111
k=2
Esempio

k=4, b=3, n=kb=64 e m=3214= 57
Il primo vicino è 2104=36
Il secondo vicino è 2114=37
Il terzo vicino è 2124=38
Il quarto vicino è 2134=39
b=3
Diametro O(logk
n)
de Bruijn graph base k
Esempio

k=3, b=2, n=kb=9
b=2
10
k=3
11
01
12
00
20
02
21
b=160
22
Koorde base k
k+1 nuovi link

 Il link al successore nell’anello
 k link ai predecessori dei vicini
E’possibile fare routing con grado k e APL O(logk n)
d ( x, y )
APL 
x , yN
n2
b=2
10
k=3
11
01
12
00
20
02
21
b=160
22
10
Koorde base k
01
11
12
00
02
Scegliendo k = O(log n):


Grado = O(log n)
APL = O(log n / log (log n))
Svantaggi



Bisogna stimare n a priori;
Non è possibile cambiare il grado in un sistema
attivo;
E’ molto complicato stabilizzare la rete;
b=2
k=3
20
21
22
Ricapitolando….
Sistemi P2P puri
Sistemi Uniformi
Sistemi Non uniformi
Koorde
Neighbor of Neighbor
routing (NON)