P-Grid: A Self-Organizing
Access Structure for P2P
Information Systems
Karl Aberer
Presentazione et codice:
Antonio Gaetani
Marco Montali
Marco Tamburini
Agenda





Stato dell’arte e motivazioni: strutture per
l’accesso ai dati nei sistemi P2P
Definizione e proprietà di P-Grid
Algoritmo di ricerca all’interno di una P-Grid
Costruzione di una P-Grid
Considerazioni sull’efficienza, problematiche e
DEMO!
Stato dell’arte

Tipiche infrastrutture P2P per il file sharing
(Gnutella):


Nessun meccanismo di indicizzazione
Richieste mandate in broadcast
RICERCA INEFFICIENTE
Obiettivo

Lo scopo è quindi quello di costruire una
struttura distribuita per l’accesso ai dati
che sia



totalmente decentralizzata
scalabile
affidabile
L’idea di base

Mediante meeting randomici tra i peer,
essi:



Si partizionano lo spazio di ricerca
Acquisiscono informazioni per interagire con
altri peer durante successive richieste di
ricerca
Il risultato è la struttura
distribuita chiamata P-Grid
di
accesso
Ricerca con Gnutella (Intuitivamente)
No!
Mi dispiace
Commedia
Jeff Kanew
La rivincita dei nerdz
Sì!
Te lo mando
No!
Mi dispiace
Ricerca con P-Grid (Intuitivamente)
Papà:
Gestisco
Commedia
commedie di
Jeff Kanew
Commedia Jeff Kanew, ma
La rivincita
dei nerdz
per i nerds
Jeff Kanew
devo chiedere
La rivincita dei nerdz
a Papà
Gùgù:
Papà:
Papà
Papà
Papà
Tambu:
Gestisco
Commedia
commedie, ma
Jeff Kanew
per Jeff Kanew
La rivincita dei nerdz
devo chiedere
a Tambu
Ce l’ho!
La P-Grid

Una P-Grid è unaProprietà
struttura
di con
accesso
Un peer
path 10 ai dati
distribuita:
r può apparteneregestisce
all’insieme
tutte ledei
chiavi
 I datiriferimenti
sono rappresentati
da
chiavi
di a=p
a binarie
livello i se
che
per
1…p
k cominciano



I peer si ripartiscono lo spazio delle
chiavi effettuando
10!
degli incontri
prefix(i,r)=[prefix(i-1,a),pi]
Ogni peer possiede un path (determinato dagli incontri
fatti) che rappresenta il prefisso del sottospazio delle
chiavi che gestisce
Ogni peer possiede una griglia di riferimenti ad altri peer


I peer riferiti da a a livello i hanno la proprietà che
completano lo spazio delle chiavi di a rispetto all’i-mo bit
del path
La determinazione di tali riferimenti viene effettuata
secondo algoritmi probabilistici
Un peer nella P-Grid
P1
0
PX
Py
Livello 1
0 1 1
Pz
1
chiave owner
doc
011…
Pa
011…
Pb
011…
Pc
011…
Pd
1
Pw
Livello 2
Livello 3
A regime conterrà tutti i
documenti nella rete
con chiave che inizia per 011!
Algoritmo di ricerca
(peer1,
1000, p,livello
1) {
query(peer
a,query
l)
{
found= false;
remanent_path = sub_path(path(a),
l, k);
1000;
Lunghezza
Della query
path(peer1)=1000
iniziale
1000;
common_path = common_prefix_of(p,
rempath); peer1
responsabile
IF length(common_path)
4 = 4
IF
= length(p)
THEN result = peer1
a
per 1000
ELSE IF length(path(a)) > l + length(compath)
THEN
querypath = sub_path(p, length(compath) + 1,length(p));
refs = refs(l + length(compath) + 1, a);
WHILE |refs|  1 AND NOT found
r = random_select(refs);
IF online(peer(r))
found = query(peer(r), querypath, l+length(compath));
RETURN found;
}
Algoritmo di ricerca (altro esempio)
query(peer
a,query
l)
peer1,
1000, p,livello
1 ) {
{
found= false;
path(peer1)=1011
query(peer
a,query
{
remanent_path
=00,
sub_path(path(a),
l, k);
peer3,
3 p,livello l)
1011
found= =false;
common_path
common_prefix_of(p,
rempath);
10
00
remanent_path = sub_path(path(a),
l, k);
Prende la parte
2 = length(p)
4 NO
IF length(common_path)
Estrae i riferimenti
common_path = common_prefix_of(p,
rempath);
00
di query che
THEN result = a
al livello 3, quindi
IF length(common_path) = length(p)rimane togliendo
a peer che
ELSE IF length(path(a))
+ length(compath)
4 > =l a
2
THEN result
peer3
il prefisso
gestiscono path
THEN
ELSE
comune
del
tipo
100…
. . .
querypath
= sub_path(p,
length(compath) + 1,length(p));
00
peer
3è
refs
= refs(l
+ length(compath) + 1, a);path(peer3)=1000…
Esempio:
responsabile
peer3 (ON)
WHILE
|refs|  1 AND NOT found
per la chiave
1000
peer5 (OFF)
r = peer3
random_select(refs);
peer6 (ON)
IF online(peer(r))
query(peer3, 00,
3);
found = peer3
query(peer(r),
querypath,
l+length(compath));
peer3
RETURN found;
}
Algoritmo di ricerca
Si noti come il peer risultante dalla query
non sia l’effettivo owner del documento
ma colui che se interrogato è in grado di
restituire il peer che è il reale possessore
del dato
 Per acquisire l’item il PASKER non dovrà fare
altro che interrogare successivamente il
risultante della query e colui che gli sarà
segnalato come owner del documento

P-Grid (già inizializzata)
P1
0 1 1
P2
P6
1 0
1 1 1
P3
P5
0 0
0 1 0
P4
1 1 0
Esempio di query (1°)
P1
0 1 1
0 1 1
Esempio di query (2°)
P1
0 1 1
0 1 0
P5
0 1 0
X X 0
Esempio di query (3°)
P1
P4
0 1 1
1 1 0
1 1 0
X 1 0
P2
1 0
1 1 0
Esempio di query (4°)
P6
P1
1 1 1
0 1 1
1 1 1
1 1 0
P2
PEER OFF-LINE
Costruzione della P-Grid


Il processo di costruzione della P-Grid si basa sul
concetto di meeting
Un meeting è un incontro di due peer durante il
quale viene effettuata la procedura di exchange

Tramite la procedura di exchange la coppia cerca di



Raffinare il proprio path
Aggiornare i propri riferimenti
Due peer si possono incontrare:



Randomicamente
Durante altre operazioni
Quando si trovano in relazione mentre eseguono una
query
Procedura di exchange
exchange(a1, a2, r)
refmax
{
è un parametro che
commonpath = common_prefix_of(path(a1), indica
path(a2));
il numero
lc = length(commonpath);
massimo di
IF lc > 0
riferimenti per livello
{
commonrefs = union(refs(lc, a1), refs(lc, a2));
refs(lc, a1) = random_select(refmax, commonrefs);
refs(lc, a2) = random_select(refmax, commonrefs);
.
.
.
PA
PB
lc=2
refmax=3
0 1 0
PW
PY
PX
0 1 1
PX
PW
PY
PX
PZ
PW
PY
PZ
Procedura di exchange
l1 = length(sub_path(path(a1), lc + 1, length(path(a1)));
l2 = length(sub_path(path(a2), lc + 1, length(path(a2)));
Caso 1: se i path dei peer sono uguali si introduce un nuovo livello
CASE l1 = 0 AND l2 = 0 AND length(commonpath) < maxlength
path(a1) = append(path(a1), 0);
path(a2) = append(path(a2), 1);
refs(lc + 1, a1) = {a2};
maxlength
refs(lc + 1, a2) = {a1};
è un parametro che indica
la dimensione massima dei
path
Esempio di exchange (1°)
PB
PA
0 1 0
0 1 1
PB
PA
Procedura di exchange
Caso 2: se il path di un peer è prefisso dell’altro e non si è
raggiunta ancora la maxlength splittiamo lo spazio del primo
peer con il valore (lc+1)-esimo complementato del secondo e
aggiorniamo i riferimenti
CASE l1 = 0 AND l2 > 0 AND length(commonpath) < maxlength
path(a1) = append(path(a1), value(lc+1, path(a2)^-);
refs(lc + 1,a1)={a2};
refs(lc + 1,a2)=random_select(refmax,union({a1},refs(lc+1,a2));
Banalmente se l1>0 e l2=0 vale una procedura speculare
alla precedente
Esempio di exchange (2°)
PB
PA
0 1 0
0 1 1
refmax=2
PB
PY
PX
PA
PX
PA
Y
Procedura di exchange
Caso 3: se i path dei due peer sono differenti si considera il
livello corrispondente al primo bit differente (che è l’ lc+1mo).
I riferimenti di quel livello di ciascuno dei due peer saranno
oggetto di exchange con l’altro.
recmax
è un parametro che indica
il massimo grado di
ricorsione della procedura
di exchange
CASE l1 > 0 AND l2 > 0 AND r < recmax,
refs1 = refs(lc+1, a1) \ {a2};
refs2 = refs(lc+1, a2) \ {a1};
FOR r1 IN refs1 DO
IF online(peer(r1))
THEN exchange(a2, peer(r1), r+1);
FOR r2 IN refs2 DO
IF online(peer(r2))
THEN exchange(a1, peer(r2), r+1);
Esempio di exchange (3°)
PB
PA
0 1 1 0
PD
PC
PB
PE
0 1 0 0
PG
PF
PH
PA
Attenzione
CASE l1 > 0 AND l2 > 0 AND r < recmax,
r  parametro di input della procedura
recmax  valore di sistema
PB
PA
(numero massimo di ricorsioni
successive)
0 1 1 0
0 1 0 0
Sperimentalmente:
recmax ottimo =2
PD
PC
PE
PK
Non siete convinti?
Intuitivamente può capitare che uno dei
peer sul percorso sia offline… e allora
addio al file desiderato!!!
 Vi dimostreremo che sarà possibile:

con solo il 30%
di nodi online
99% di possibilità
di reperire il documento
Considerazioni

Definiamo:



refmax  # riferimenti memorizzati dal
singolo peer per ogni livello
k  lunghezza della chiave
p  probabilità che un peer sia on-line
Nel nostro esempio ci riferiamo a valori di
refmax=20, k=10, p=30%
 Consideriamo il caso peggiore


ad ogni livello un nuovo peer deve essere
contattato
Dimostrazione
1-(1-p)refmax
probabilità di raggiungere
un peer al livello successivo
valore relativo:
99,9%
probabilità effettuare una
ricerca con successo
(1-(1-p)refmax)k
valore relativo:
99,2%
Inizializzazione


Come la P-Grid debba essere
start-up è un problema che
dagli algoritmi precedenti
Sarà tra poco pubblicato un
queste tematiche. In breve ad



costruita in fase di
non viene trattato
lavoro riguardante
ogni meeting:
Ciascun peer arricchisce la propria conoscenza sui
documenti presenti nella rete esplorando quelli dell’altro
(aggiungendo item a livello foglia)
Fa una update sui documenti da lui gestiti in caso di
modifica del proprio path (eliminazione di documenti non
più gestiti)
Per maggiori informazioni, le tecniche esposte sono state
implementate nella nostra applicazione
Update


All’aggiunta di un nuovo documento in uno dei
peers facenti parte della P-Grid è necessario
eseguire una procedura di update su ciascun peer
che a livello foglia dovrebbe gestire la chiave
Sperimentalmente è
della nuova entry
risultata la miglior
Varie tecniche sono possibili:
soluzione



Facendo ripetutamente ricerche randomiche depth-first
nella speranza di fare tutte le update necessarie
Facendo un’unica ricerca breadth-first e conseguenti
update
Mantenendo una lista dei peers che sono responsabili
della stessa chiave e facendo una solo ricerca depth-first
N-GRID

E’ un simulatore di una rete P2P basata su P-Grid
le cui parti costituenti sono:


Un peerPooler, che gestisce i meeting tra i peer
N peer, ciascuno dei quali rappresenta un nodo fisico:





È in realtà un thread che esegue in modo indipendente
dagli altri peer
È l’owner di una serie di documenti le cui chiavi sono
generate a caso
Risponde a query per un documento
Manifesta (su richiesta) i suoi riferimenti ai vari livelli
Un’astrazione di rete, che ci ha permesso di
implementare gli algoritmi come se ci trovassimo
effettivamente in un ambiente distribuito
Riferimenti





[1] Karl Aberer, Magdalena Punceva, Manfred Hauswirth, Roman
Schmidt: “Improving Data Access in P2P Systems”
[2] Karl Aberer, Philippe Cudré-Mauroux, Anwitaman Datta, Zoran
Despotovic, Manfred Hauswirth, Magdalena Punceva, Roman
Schmidt: “P-Grid: A Self-organizing Structured P2P System”
[3] Karl Aberer, Philippe Cudré-Mauroux, Anwitaman Datta, Zoran
Despotovic, Manfred Hauswirth, Magdalena Punceva, Roman
Schmidt, Jie Wu :”Advanced Peer-to-Peer Networking: The P-Grid
System and its Applications”
[4] Roman Schmidt: “Gridella: an open and efficient Gnutellacompatible Peer-to-Peer System based on the P-Grid approach”
[5] Karl Aberer, Anwitaman Datta, Manfred Hauswirth, Roman
Schmidt: “Indexing data-oriented overlay networks” (NON
ANCORA PUBBLICATO)