Sistemi Peer To Peer (P2P)
Avanzati
• Gennaro Cordasco
– cordasco[@]dia.unisa.it
– http://www.dia.unisa.it/~cordasco
– Laboratorio ISISLAB2 (L8 a Baronissi)
Sistemi P2P avanzati
Outline
• Peer-to-Peer (P2P)
– Motivazioni
• Un po’ di storia
– Napster
– Gnutella
• Classificazione
• P2P Open Problems
Sistemi P2P avanzati
Peer-to-Peer (P2P)
• File Sharing?
• 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:
– permettono di sfruttare risorse altrimenti non utilizzate;
– controllo decentralizzato (niente Server);
– assenza di punti nevralgici (single point to failure);
– si organizzano da soli;
Sistemi P2P avanzati
P2P: Applicazioni
Kademlia
fiorana
•
freenet
•
open cola
Kelips
ocean
store
• Distributed file system
netmeeting
farsite
•gnutella
Grid Computing
icq
ebay
morpheus
Viceroy
• Redundant storage
limewire
seti@home
bearshare
• Anonymity
system
uddi
grove
jabber
popular power
• Collaboration
system
kazaa
folding@home
tapestry
• Instant Messaging system
pastry systemcan
File Sharing
napster
united
devices
File Storage
system
jxta
?
process tree
Sistemi P2P avanzati
Chord
mojo nation
P2P: Storia
• Proposti già da oltre 30 anni (ARPAnet era una rete P2P!!!);
• L’introduzione del Web e la grande differenza, in termini di prestazioni, fra
macchine “Client” e “Server” ha spostato l’attenzione verso i sistemi
Client\Server;
• Successivamente, l’aumento delle prestazioni delle macchine “Client” e
l’aumento delle capacità di banda della Rete, hanno portato un maggiore
interesse verso le risorse che si trovano sul bordo della Rete.
• Alla fine degli anni novanta sono nati quindi i primi sistemi P2P (ICQ,
Seti@Home)
• 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;
Sistemi P2P avanzati
P2P: Storia(2)
• Sfortunatamente i primi sistemi P2P soffrivano
di gravi problemi di scalabilità
• Napster era un sistema P2P con “lookup”
centralizzata
Sistemi P2P avanzati
P2P: Storia(3)
• 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;
– …
Sistemi P2P avanzati
P2P: Storia(4)
GET X
X
X
• La lista degli host presenti nella rete è disponibile sul Server
C
gnutellahost.com;
A
• Il Server gnutellahost.com(127.186.112.097) viene usato dai
nodi per il boot:
– Single point of failure; B
D
– La ricerca di un file usa il flooding (non è scalabile):
– controllo dei cicli;
query (e.g., X)
E
– TTLA’sper
evitare di congestionare la rete;
C’s query hit
E’s query hit
Sistemi P2P avanzati
X
P2P: Storia(4)
Sistemi P2P avanzati
P2P: 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
DHTs (Distributed Hash Tables);
• Alcuni esempi di questi protocolli sono: Tapestry,
Chord, CAN, Viceroy, Koorde, kademlia, kelips …;
Sistemi P2P avanzati
Esempi
Sistemi P2P avanzati
P2P di seconda generazione e DHT
• A ogni risorsa e ad ogni nodo è associata una chiave
• La chiave viene di solito creata facendo l’hash del
nome della risorsa o dell’IP del nodo
• Ogni nodo del sistema è responsabile di un insieme di
risorse/chiavi e tutti realizzano una DHT
• L’unica operazione che un sistema DHT deve fornire
è lookup(chiave), la quale restituisce l’identità del
responsabile di una determinata chiave
Sistemi P2P avanzati
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
…
Sistemi P2P avanzati
0
1
2
3
4
5
6
…
2m
P2P Classificazione
•
•
•
•
Sistemi P2P Centralizzati (a.k.a. Ibridi)
Sistemi P2P Gerarchici
Sistemi P2P Puri
Sistemi P2P che utilizzano SuperPeer
Sistemi P2P avanzati
P2P Classificazione
• Sistemi P2P Centralizzati (a.k.a. Ibridi)
Resource request
P2P Communication
Sistemi P2P avanzati
P2P Classificazione
• Sistemi P2P Gerarchici
Resource request
P2P Communication
Servers/Coordinators
Communication
Sistemi P2P avanzati
P2P Classificazione
• Sistemi P2P Puri
P2P Communication
Sistemi P2P avanzati
P2P Classificazione
• Sistemi P2P che utilizzano SuperPeer
Resource request
P2P Communication
Servers/Coordinators
Communication
Sistemi P2P avanzati
P2P Classificazione(2)
• E’ possibile classificare i sistemi P2P in base
all’applicazione fornita:
–
–
–
–
File Sharing
Communication
Distributed Computing
Collaboration
Sistemi P2P avanzati
P2P Desiderata
•
•
•
•
•
•
•
Scalability
Stability
Performance
Decentralization
Load Balancing
Topology awareness
Flexibility
Sistemi P2P avanzati
P2P: 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).
Sistemi P2P avanzati
P2P: 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;
Sistemi P2P avanzati
P2P: Performance
• Dal punto di vista topologico:
• Consideriamo una rete P2P come un grafo G=(V,E),
dove V è l’insieme dei nodi nel sistema e E
rappresenta l’insieme delle interconnessioni fra essi:
– Minimizzare, per ogni nodo, le informazioni relative agli
altri nodi:
• minimizzare il grado dei nodi;
– Minimizzare il numero di messaggi necessari per fare
lookup:
Condizioni necessarie
ma non sufficienti
• Minimizzare il diametro;
• Minimizzare l’average path lenght (APL), vale a dire, la distanza
media fra due nodi nel grafo.
Sistemi P2P avanzati
P2P: Incorporating Geography
• Di solito le le prestazioni del routing dei sistemi P2P si
misurano contando il numero di hop necessari a individuare il
responsabile di una chiave a parità di link nella rete
• Sarebbe utile, inoltre, minimizzare la latenza del singolo hop
• In pratica vogliamo che nodi vicini sulla rete DHT, siano
“fisicamente” vicini
s
t
s
Sistemi P2P avanzati
t
P2P: 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)
Sistemi P2P avanzati
P2P: 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à
Sistemi P2P avanzati
P2P: 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 nodi e alle risorse in modo pseudocasuale (quasi tutti gli algoritmi usano SHA-1)
Sistemi P2P avanzati
Riferimenti
•
•
•
•
•
http://www.pdos.lcs.mit.edu/chord/
http://www.napster.com/
http://www.gnutella.com/
http:// www.openp2p.com/
S. Ratnasamy, S. Shenker, and I. Stoica. “Routing
algorithms for DHTs: Some open questions”. 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.
Sistemi P2P avanzati
Fine Lezione 1
Sistemi P2P avanzati