Peer To Peer (P2P)
pastry
can
napster
united devices
aim
gnutella
uddi
freenet
Kelips
ocean store
farsite
morpheus
Viceroy
bearshare
grove
kazaa
?
open cola
icq
ebay
limewire
folding@home
chord
Koorde
netmeeting
jabber
process tree
Kademlia
fiorana
jxta
seti@home
popular power
tapestry
mojo nation
Gennaro Cordasco
Sommario
Introduzione
Classificazione
Storia ed Esempi
Concetto di Scalabilità
Distributed Hash Table (DHT)

Chord
Sommario(2)
Open Questions





Capacità di far fronte ai fallimenti
Routing Hot Spots
Incorporating Geography
Extreme Heterogeneity
Sicurezza
Applicazioni




WinMx
Kazaa
Overnet
Freenet
Cosa vuol dire Peer to Peer (P2P)?
Sistema distribuito nel quale ogni nodo ha
identiche capacità e responsabilità e tutte le
comunicazioni sono potenzialmente
simmetriche;
Peer to peer (obiettivi): condividere risorse e
servizi (dove per risorse e servizi intendiamo:
scambio di informazioni, cicli di CPU, spazio sul
disco …);
I sistemi P2P possiedono molti aspetti tecnici
interessanti:



controllo decentralizzato;
adattabilità;
si organizzano e si gestiscono da soli;
DHT Utilità
File sharing system;
File storage system;
Distributed file system;
Redundant storage;
Availability;
Performance;
Permanence;
Anonymity;
Chat service;
P2P: Classificazione
Le applicazioni P2P sono costituite da tre fasi
principali:



Boot: permette a un peer di trovare la rete e di
connettersi ad essa; (nessuno o quasi fa boot P2P)
Lookup: permette ad un peer di trovare il
gestore/responsabile di una determinata
informazione; (pochi sono P2P, alcuni usano
SuperPeer)
Scambio di file; (sono tutti P2P)
P2P: Classificazione(2)
Parleremo di applicazioni:

P2P pure se:
le fasi di boot, lookup e scambio di file sono P2P;

P2P se:
le fasi di lookup e scambio di file sono P2P;
la fase di boot utilizza qualche SERVER;

P2P Ibride se:
la fase di scambio dei file è P2P;
la fase di boot utilizza qualche SERVER;
nella fase di lookup vengono usati Peer particolari:
Hub (Direct Connect)
Supernodo (KaZaA)
MainPeer (EDonkey)
SuperPeer , Ultra Peer(Gnutella2)
NodoRandezVous (JXTA)
Server (WinMX)
P2P: Classificazione(2)
Consideriamo solo l’operazione lookup:

Lookup Centralizzato
Indice centralizzato;

Lookup Decentralizzato
Indice completamente distribuito;

Lookup Ibrido
Più sistemi centralizzati collegati in un sistema
decentralizzato;
In tutti e tre questi sistemi il trasferimento
e la memorizzazione dei file è P2P;
Un po’ di storia
Proposti già da oltre 30 anni;
Sviluppati nell’ultimo decennio;
L’interesse verso questo tipo di protocolli è
aumentato con la nascita dei primi sistemi per
file-sharing (Napster (1999), Gnutella(2000));
Nel 2000, 50 milioni di utenti hanno scaricato il
client di Napster;
Napster ha avuto un picco di traffico di circa 7
TB in un giorno;
Un po’ di storia(2)
L’eredità di Napster è stata raccolta da Gnutella;
Il 14 / 03 / 2000 Justin Frankel e Tom Pepper
realizzano la prima release di Gnutella (!!! Solo
14 ore !!! );
La taglia della rete cresce in 7 mesi da 2K a 48K
nodi;
Tuttavia nel 95% delle query il diametro è di 7-8
hop;
Le applicazioni più conosciute che si basano sul
protocollo Gnutella sono:



BearShare;
LimeWire;
…
Un po’ di storia(2)
GET X.mp3
X
X
La lista degli host presenti nella rete è
C
disponibileA sul Server gnutellahost.com;
Il Server gnutellahost.com(127.186.112.097)
viene usato dai nodi per il boot:


Single point of failure;
B
Gnutella non è P2P Puro!!!;
D
La Ricerca di un file usa il flooding (non è
A’s query (e.g., X)
scalabile):
E
C’s query hit


controllo
dei
E’s query
hitcicli;
X
TTL per evitare di congestionare la rete;
Gnutella: Flooding
Scalabilità
Il lavoro richiesto a un determinato nodo nel
sistema non deve crescere (o almeno cresce
lentamente) in funzione del numero di nodi nel
sistema;
I protocolli usati da Napster e Gnutella non sono
scalabili;
Per migliorare la scalabilità sono nati i cosiddetti
protocolli P2P di seconda generazione che
supportano DHT (Distributed Hash Table);
Alcuni esempi di questi protocolli sono: Tapestry,
Chord, Can, Viceroy, Koorde, kademlia,kelips …;
Scalabilità(2)
Messaggi necessari per trovare
una chiave
Anello
La scalabilità di un protocollo è direttamente legata
all’efficienza dell’algoritmo Chord
usato
per il routing
e
altri
n -1
(lookup);
Grafo
In questo senso, sostanzialmente gli obiettivi
Totalmentesono
connesso
due:
O(log n)


Minimizzare il numero di messaggi necessari per fare
1
lookup;
Minimizzare, per ogni nodo, le informazioni relative agli
1
O(log n)
n -1
altri nodi;
I vari DHT conosciuti differiscono
proprio
Dimensione
tabella dinel
routing
n è routing;
il numero dei peer;
P2P di seconda generazione e DHT
A ogni file e ad ogni nodo è associata una chiave;
La chiave viene di solito creata facendo l’hash del
nome del file o dell’IP del nodo;
Ogni nodo del sistema è responsabile di un
insieme di file/chiavi e tutti realizzano una DHT;
L’unica operazione che un sistema DHT deve
fornire è lookup(key), la quale restituisce l’identità
del responsabile di una determinata chiave.
IP Address
P2P di seconda generazione e DHT
Tutti i nodi del sistema condividono una tabella hash;
Conoscono la struttura della tabella;
Ma non conoscono il responsabile di una determinata
entry;
ID
Nodo x
Nodo y
Nodo z
…
0
1
2
3
4
5
6
…
2m
DHT: Chord
Le chiavi sono mappati su un array circolare costituito da 2m
identificatori;
Il nodo responsabile di una determinata chiave è il primo
nodo che la succede in senso orario;
Ogni nodo x di Chord mantiene due insiemi di vicini:
 Il primo contiene gli m successori del nodo x più il
predecessore. Questo insieme viene usato per dimostrare
la correttezza del Routing;
 Un insieme m nodi costituito dai
responsabili delle chiavi
distanziate esponenzialmente
m=3
dal nodo x, vale a dire l’insieme
delle chiavi che si trovano a
distanza 2i da x dove 0  i  m-1.
Questo insieme viene usato per
dimostrare l’efficienza del
Routing;
DHT: Chord(2)
Successors
ID
Resp.
indice
Nod
o
1
14
8+1=9
14
2
8+2=11
21
14
3
8+4=12
4
8+8=16
5
24
14
32
21
38
8+16=24
6
24
42
8+32=40
42
Predecessor
Nodo 1
m=6
DHT: Chord(3)
Le informazioni che il nodo deve mantenere sugli altri nodi
000
sono m + m + 1 = 2m +1 (O(log
N) WHP);
110
111 necessari
Il numero di messaggi
per
001fare lookup è m
(O(log N) WHP);
L’algoritmo di routing effettua a ogni step il passo più
grande che riesce
110 a fare;
010
Il costo che si paga quando un nodo lascia o si connette
alla rete è di O(log2N) messaggi WHP;
101 simula un Ipercubo,
011
L’algoritmo in pratica
inoltre si
comporta molto bene in un sistema
dinamico.
100
DHT: Capacità di far fronte ai fallimenti
Cosa succede se un nodo cade?




I dati presenti nel nodo possono essere recuperati solo
se ci sono duplicati.
Il routing continua a funzionare? Con quale efficienza?
Quanto costa una procedura per ripristinare tutti i link?
Chi chiama questa procedura? (vale a dire chi si
accorge che un nodo non è attivo).
DHT: Routing Hot Spots
Se una chiave è richiesta più spesso, il
responsabile della chiave e anche i suoi vicini
potrebbero sovraccaricarsi;

Per ovviare al problema si possono usare meccanismi
di caching e di duplicazione;
Diverso è il problema relativo ai nodi che si
sovraccaricano per il traffico generato dalle
lookup;

Questo tipo di traffico è abbastanza difficile da
individuare e da gestire;
DHT: Incorporating Geography
Finora abbiamo misurato le prestazioni del routing
contando il numero di hop necessari a individuare il
responsabile di una chiave;
Sarebbe utile, inoltre, minimizzare la latenza del singolo
hop;
s
t
s
t
DHT: Incorporating Geography(2)
Alcune tecniche:



Geographic Layout: Usare un algoritmo per attribuire le
chiavi ai nodi in modo che nodi “fisicamente” vicini
abbiano identificatori simili. (Controindicazioni:
Bilanciamento del carico, Routing Hot Spots e
Sicurezza);
PNS(Proximity neighbor selection) La scelta dei vicini
non dipende solo dalla distanza fra i nodi sulla rete di
overlay ma è influenzata anche dalle distanze reali.
PRS(Proximity routing selection) Durante la ricerca
l’algoritmo di routing non sceglie il successivo step
basandosi solo sulla distanza fra i nodi nella rete di
overlay; considera anche la distanza effettiva fra i nodi
(in termini di RTT);
DHT: Incorporating Geography(3)
Osservazioni:


PRS e PNS sono i sistemi più usati,(sembra che PNS
offre prestazioni migliori di PRS);
PRS e PNS partono dal presupposto che è possibile
conoscere il RTT con ogni altro nodo (non è fattibile, ma
è possibile ottenere delle stime a un costo relativamente
basso);
Incorporating geography: Chord
Chord e PRS:
L’algoritmo di routing non 000
va semplicemente al nodo più
vicino sulla rete di 111
overlay,110
ma ad esempio
potrebbe
001
considerare i due nodi più vicini e scegliere quello con
RTT minore;
110
010
Le path-lenght si allungano ma rimangono O(log n);
011
In particolare: ad 101
ogni passo la distanza
fra il nodo
destinazione e il nodo corrente
100 si riduce da  a 3/4 
Nel caso peggiore la path lenght è quindi log4/3 n.
Incorporating geography: Chord
Chord e PNS:
000
La finger table viene
riempita considerando anche il RTT:
111
001
l’i-esimo finger del nodo  non è semplicemente il
‘‘responsabile’’ della chiave +2i ma è il nodo più
010 chiavi
vicino(RTT) fra110
i nodi ‘‘responsabili’’ delle
nell’intervallo [+2i-1, +2i ].
Anche in questo caso
le path-lenght si allungano ma
101
011
rimangono O(log n) (dimostrazione analoga alla
100
precedente).
Anche usando simultaneamente PRS e PNS la
lunghezza asintotica delle path non varia;
DHT: Extreme Heterogeneity
I nodi connessi a questo tipo di reti sono
eterogenei (Es. capacità di calcolo e banda);
E’ possibile progettare algoritmi di routing che
considerino anche questa eterogeneità;
La tecnica più diffusa per risolvere questo
problema consiste nel considerare dei nodi virtuali
tutti con le stesse capacità e assegnare a ogni
nodo reale un numero di nodi virtuali
proporzionale alle proprie capacità;
DHT: Sicurezza
E’ possibile realizzare un protocollo P2P che
resiste ad attacchi di tipo denial of service;
E’ necessario replicare i dati;
E’ importante usare funzioni hash “One Way” (per i
dati e per i nodi);
E’ importante osservare che tutte le dimostrazioni
relative alla sicurezza dei vari algoritmi incontrati
finora si basano sul fatto che le chiavi vengono
associate ai files in modo casuale (quasi tutti gli
algoritmi usano SHA);
P2P(quasi): Direct Connect (DC++)
Usa una serie di hub (server) che mantiene le informazioni
relative a un gruppo di utenti;
Una volta connessi ad un hub si condivide file solo con i
nodi connessi a tale hub;
E’ possibile connettersi a più hub contemporaneamente;
Gli hub sono connessi tra loro ma non si scambiano
informazioni relative alla ricerca di una determinata chiave
(Sono tanti piccoli Napster);
La lista degli hub attivi viene mantenuta da tutti gli hub e
aggiornata periodicamente dagli altri hub mediante
messaggi del tipo “I am here”;
P2P ibrido
P2P(quasi): WinMx
E’ basato su una rete di Server (circa 50) chiamata
OpenNap nata subito dopo che è stato chiuso il
Server di Napster;
Viene usata anche da NapMx;
In WinMx viene fatta una distinzione fra nodi di
connessione primaria:


direttamente connessi ai server;
sono usati anche per il Routing;
e nodi di connessione secondaria:


connessi solo ai nodi di connessione primaria;
non si occupano di Routing;
P2P ibrido
P2P(quasi): KaZaA
Viene usata una rete proprietaria;
In KaZaA viene fatta una distinzione fra nodo e
Supernodo(server):



Ogni nodo semplice collabora con il proprio Supernodo;
I Supernodi collaborano tra loro e con i propri sottonodi;
Come sono connessi i Supernodi?
P2P ibrido
Gnutella2: meglio un uovo oggi….
L’obbiettivo della lookup in Gnutella è trovare tutti i peer
che dispongono di un determinato oggetto (non ci sono
limitazioni sul tempo);
L’obbiettivo della lookup in Gnutella2 è trovare, nel minor
tempo possibile, almeno un peer (se c’è) che dispone di
un determinato oggetto; una volta trovata un’istanza
dell’oggetto desiderato è possibile scegliere se fermarsi o
continuare la ricerca;
L’abilità di trovare almeno un’istanza di un oggetto è molto
importante, altrimenti non sono possibili altre azioni;
Bisogna trovare un modo per tenere sotto controllo la
ricerca;
Gnutella2: Ricerca…(1)
Esistono tre approcci per controllare la
ricerca;

Gnutella2
Future


Random walker approach;(il nodo che origina la
query ne controlla l’esecuzione e in ogni istante
può decidere se continuare o abortire la ricerca).
Random or crawling mesh approach;(il nodo che
origina la query iterativamente contatta alcuni nodi
della rete, finché non si verifica una determinata
condizione).
Guided mesh approach;(DHT)
Gnutella2: Ricerca…(2)
Su una rete pubblica di grandi dimensioni non
è possibile effettuare direttamente la ricerca di
un oggetto:




ci sono troppi nodi da contattare;
il costo per mettersi in contatto con un nodo è
troppo alto paragonato alla probabilità di successo
su quel nodo;
la maggior parte dei nodi non dispongono di
risorse sufficienti per far fronte a un numero
notevole query;
non tutti i nodi si possono contattare direttamente
(es. firewall);
Gnutella2: Ricerca…(3)
Soluzione? P2P Ibrido:



Hub
Gnutella2 organizza i nodi in un sistema gerarchico
a due livelli dove i nodi ad alta capacità chiamati
Hub rispondono alle query per le proprie foglie;
La restizione della rete agli Hub è P2P;
Hub vantaggi:

Nodo
Viene ridotto il numero totale dei nodi da
contattare;
Un Hub contiene informazioni relative a tanti
oggetti, quindi è maggiore la probabilità che una
query trovi un’istanza di un oggetto;
E’ possibile avere informazioni su nodi down;
Gnutella2: Ricerca…(4)
Per evitare che questo sistema degeneri in un
sistema centralizzato viene limitato il numero
di leaves per ogni hub;(circa 150)
La comunicazione fra leaves e hub è diretta;
Problema Inter-Hub Communication;
Gnutella2: Inter-Hub Communication(1)
Nodo
Hub
Ogni hub conosce solo i propri vicini;
Quando un hub riceve una query dal nodo di origine,
oltre a elaborarla, la inoltra ai propri vicini che non la
inoltrano ulteriormente; (in pratica TTL = 2)
Ad esempio se la ricerca viene inviata ad un hub che
ha 5 vicini in un solo passo (con una query) vengono
analizzate le foglie relative a 6 hub;
L’insieme dei nodi raggiunto in un passo viene
chiamato cluster;
Gnutella2: Inter-Hub Communication(2)
Nodo
Hub
Quando un nodo richiede la ricerca di un oggetto al
proprio hub:




Viene ricercato l’elemento nel proprio cluster
Viene ricercato l’elemento nei cluster vicini(a distanza 1) più
qualche cluster lontano scelto a caso;
Viene ricercato l’elemento nei cluster vicini dei vicini (a
distanza 2) più qualche cluster lontano scelto a caso;
…
Gnutella2: Inter-Hub Communication(3)
Nodo
Hub
Non è possibile per ogni hub mantenere la lista di tutti
gli hub; (Non è scalabile);
La lista dei cluster a distanza i+1 è ottenuta in risposta
alla ricerca effettuata sui cluster a distanza i;
Le risposte contengono inoltre altre informazioni utili
per le statistiche (es. numero di nodi presenti nel
cluster);
…
Gnutella2: Inter-Hub Communication(4)
Nodo
Hub
Ogni hub mantiene la lista degli hub vicini (direttamente
connessi) più una cache di hub lontani aggiornata di tanto in
tanto;
Viene mantenuta una done list;
Le ricerche all’interno del cluster sono fatte usando TCP;
Le ricerche fra cluster sono fatte usando UDP;
UDP SEARCH
TCP SEARCH
Gnutella2: Inter-Hub
Communication(Esempio)
try list
cluster
Gnutella2: Inter-Hub Communication(5)
Nodo
Hub
Ogni hub deve mantenere quindi:




la lista dei propri vicini;
una lista di hub lontani (da aggiornare di tanto in
tanto);
una done list (i nodi a cui abbiamo inviato una
query più i loro vicini);
una try list; (i vicini dei vicini dei nodi a cui abbiamo
inviato una query);
per
ogni
query
Gnutella2: Boot
Come fa un nuovo nodo a connettersi alla
rete?


E’ necessario conoscere almeno un host attivo;
Chi mantiene la lista degli host attivi?
un Server; (Gnutella, Napster)
tanti Server; (Gnutella2)
nessun Server.()
Overnet
Sistema P2P per il file sharing sviluppato
dalla MetaMachine;
Non ci sono server; (P2P puro)
Usano DHT (Distribuited Hash Table) con
ID a 128 bit;
Purtroppo non è Open Source;
Overnet:boot
Ogni nodo mantiene una cache dei nodi
connessi alla rete;
Durante la fase di boot il nodo tenta di
connettersi ai nodi presenti nella cache;
Se questa fase non ha successo viene
richiesto l’indirizzo di un nodo on-line;(A
regime non capita praticamente mai)
In ogni caso è stato creato un canale IRC
per mantenere queste informazioni;
P2P(file-storage-service): FreeNet
Ogni nodo mette a disposizione un po’ di spazio;
Le operazioni possibili sono get e put di un file;
Per aggiugere un nuovo file si invia un send message nella
rete e un identificatore GUID (Global Unique Identifier) in
base al quale il file viene memorizzato in un insieme di nodi
(Data Partition);
Per recuperare un file basta inviare un messaggio di
richiesta contenente il GUID del file;
Servizi aggiuntivi:


Persistenza;
Anonimia;
P2P Puro
P2P: FreeNet(Routing)
E’ tutt’altro che efficiente;
Riferimenti
http://www.pdos.lcs.mit.edu/chord/
http://www.napster.com/
http://www.gnutella .com/
http:// www.gnutella2.com/
http:// www.shareaza.com/
http://www.overnet.com/
http:// www.openp2p.com/
S. Ratnasamy, S. Shenker, and I. Stoica. “Routing
algorithms for DHTs: Some open questions”. In In 1st
International Peer To Peer Systems Workshop (IPTPS02).
I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F.
Kaashoek, F. Dabek, H. Balakrishnan, “Chord: A Scalable
Peer-to-peer Lookup Protocol for Internet Applications”.
In IEEE/ACM Trans. on Networking, 2003.