Sistemi Sistemi peerpeer--toto--peerpeer

Valeria CardelliniUniversità di Roma Tor Vergata

IW - Valeria Cardellini, A.A. 2007/08 2

Sistemi Sistemi peerpeer--toto--peerpeer (P2P)(P2P)

• Giunti agli oneri della cronaca di recente– Negli anni 1999/2000– Il famoso caso Napster (sistema di file sharing per file MP3)

• Molto popolari– Parte consistente del traffico Internet: più del 30% è riconducibile

ad applicazioni di tipo P2P– Trend crescente (nonostante tutto)

• Qualche anno fa si diceva Internet = Web

• Alcuni pregiudizi sul P2P– P2P = file sharing

• Molti sistemi per il file sharing si basano su un approccio P2P– P2P = illegalità

• Una percentuale massiccia di file scambiati è coperta da copyright

IW - Valeria Cardellini, A.A. 2007/08 3

Cosa è il Cosa è il peerpeer--toto--peerpeer

• Peer: entità con capacità simili alle altre entità nel sistema

• Il termine peer-to-peer si riferisce ad una classe di sistemi ed applicazioni che utilizzano risorse distribuite per eseguire una funzionalità (critica) in modo decentralizzato

• Condivisione delle risorse (cicli di CPU, storage, dati)– Offrire ed ottenere risorse dalla comunità di peer

IW - Valeria Cardellini, A.A. 2007/08 4

Caratteristiche dei sistemi P2PCaratteristiche dei sistemi P2P• Tutti i nodi (peer) hanno la stessa importanza (in linea di

principio)– Nodi indipendenti (autonomi) e localizzati ai bordi (edge) di

Internet• Nessun controllo centralizzato

– Ogni peer ha funzioni di client e server e condivide delle risorse • servent = server + client

– In realtà, possono essere presenti server centralizzati o nodi con funzionalità diverse rispetto agli altri (supernodi)

• I peer sono organizzati in una gerarchia

• Sistemi altamente distribuiti– Il numero di nodi può essere dell’ordine delle centinaia di migliaia

• Nodi altamente dinamici ed autonomi– Un nodo può entrare o uscire dalla rete P2P in ogni momento

• Operazioni di ingresso/uscita (join/leave) dalla rete anche sofisticate– Ridondanza delle informazioni

IW - Valeria Cardellini, A.A. 2007/08 5

Applicazioni P2PApplicazioni P2P• Distribuzione e memorizzazione di contenuti

– Contenuti: file, video streaming, … – Es. di file sharing: Gnutella, KaZaA, BitTorrent, eDonkey ed

eMule, …– Es. di file storage: Freenet

• Condivisione di risorse di calcolo (elaborazione distribuita)– Es.: SETI@home – Search for Extraterrestrial Intelligence

• Collaborazione e comunicazione– Es.: Chat/Irc, Instant Messaging, Jabber

• Telefonia– Es.: Skipe

• Content Delivery Network– Es.: CoralCDN

• Piattaforme– Es:. JXTA (http://www.sun.com/software/jxta/)

IW - Valeria Cardellini, A.A. 2007/08 6

Condivisione di fileCondivisione di file

• E’ la killer application del P2P• Occorrono funzionalità di publishing, searching, retrieval• Vediamo un esempio…

– Alice esegue un’applicazione client P2P sul suo portatile– In modo intermittente si connette ad Internet; ottiene un nuovo

indirizzo IP per ogni connessione– Registra il suo contenuto nel sistema P2P– Cerca “Hey Jude”– L’applicazione visualizza altri peer che hanno una copia di “Hey

Jude”– Alice sceglie uno dei peer, Bob– Il file viene copiato dal PC di Bob al portatile di Alice (P2P)– Mentre Alice esegue il download, altri utenti eseguono un

upload da Alice

IW - Valeria Cardellini, A.A. 2007/08 7

Software per la condivisione di fileSoftware per la condivisione di file

• Consente ad Alice di registrare una directory del proprio file system per la condivisione– Chiunque può ottenere un file dalla directory registrata – Come un Web server

• Consente ad Alice di copiare file dalle directory condivise di altri utenti– Come un Web client

• Consente ad Alice di individuare quali peerpossiedono un determinato file tramite una ricerca basata su keyword– Come Google

IW - Valeria Cardellini, A.A. 2007/08 8

Obiettivi e problemi dei sistemi P2PObiettivi e problemi dei sistemi P2P

• Obiettivi– Condividere/ridurre i costi usando risorse non utilizzate– Migliorare la scalabilità– Aumentare la persistenza e la disponibilità delle risorse– Consentire l’aggregazione di risorse e l’interoperabilità– Aumentare l’autonomia– Aumentare l’anonimato/privacy, nascondendo le operazioni svolte

dagli utenti– Consentire dinamismo e comunicazioni ad-hoc

• Problemi– Sicurezza: garantire integrità e autenticità delle risorse– Disuguaglianza tra i nodi– Elevato tasso con cui i nodi entrano/escono dal sistema P2P

• Può portare ad una instabilità del sistema che ne influenza negativamente le prestazioni

IW - Valeria Cardellini, A.A. 2007/08 9

Architetture P2PArchitetture P2P• Tre tipologie di architetture P2P

– Decentralizzate pure• Tutti i nodi sono peer, nessun coordinatore centralizzato• Ogni peer può funzionare come router, client, o server

– Parzialmente centralizzate• Alcuni nodi (supernodi) facilitano l’interconnessione tra i peer

– Indice locale centralizzato per risorse dei peer locali• Prima comunicazione con un supernodo (a), poi con il peer (b)

– Decentralizzate ibride• Presenza di un server centralizzato che facilita l’interazione tra i peer

(servizio di localizzazione)

Architettura decentralizzata puraArchitettura P2P

parzialmente centralizzataIW - Valeria Cardellini, A.A. 2007/08 10

OverlayOverlay networknetwork• Instradamento delle informazioni su un’infrastruttura di

rete già esistente– Overlay network: è la rete virtuale che interconnette i peer ed è

basata su una rete fisica sottostante (tipicamente IP) – Vantaggi:

• Semplicità di sviluppo di nuove applicazioni• Tempi di sviluppo ridotti

• Instradamento a livello applicativo – Routing content-aware– Routing application semantic-aware

IW - Valeria Cardellini, A.A. 2007/08 11

OverlayOverlay routingrouting

• Idea base:– Il sistema fa trovare la strada per raggiungere una risorsa

• Rispetto al routing tradizionale– La risorsa non è esattamente un indirizzo di un nodo della

rete, ma può essere un file, una CPU disponibile, dello spazio libero su disco, …

• Concentriamo l’attenzione sul routing, non sull’interazione per recuperare una risorsa – Il recupero avviene con un’interazione diretta tra peer,

usando protocolli come HTTP

IW - Valeria Cardellini, A.A. 2007/08 12

Reti strutturate e non strutturateReti strutturate e non strutturate

• Reti non strutturate– Nodi organizzati come un grafo random

• L’organizzazione della rete segue principi molto semplici– Non ci sono vincoli sul posizionamento delle risorse rispetto

alla topologia del grafo• La localizzazione delle risorse è resa difficoltosa dalla

mancanza di organizzazione della rete– L’aggiunta o la rimozione di nodi è un’operazione semplice

e poco costosa– Obiettivo: gestire nodi con comportamento fortemente

transiente (tassi di join/leave elevati)– Esempi: Gnutella, FastTrack, eDonkey/Overnet

IW - Valeria Cardellini, A.A. 2007/08 13

Reti strutturate e non strutturateReti strutturate e non strutturate

• Reti strutturate– Vincoli sul grafo (strutturato) e sul posizionamento delle

risorse sui nodi del grafo• L’organizzazione della rete segue principi rigidi

– L’aggiunta o la rimozione di nodi è un’operazione costosa– Obiettivo: migliorare la localizzazione delle risorse – Esempi: Chord, Pastry, CAN

IW - Valeria Cardellini, A.A. 2007/08 14

Routing in reti non strutturateRouting in reti non strutturate

• Sistemi decentralizzati ibridi: directory centralizzata– Es.: Napster

• Sistemi decentralizzati puri: ricerca flood-based– Es.: Gnutella 0.4

• Sistemi parzialmente centralizzati– Es.: KaZaA, Gnutella 0.6

IW - Valeria Cardellini, A.A. 2007/08 15

Sistemi con directory centralizzataSistemi con directory centralizzata• Un nodo centralizzato (directory server) possiede il

mapping risorse-peer (index), fornendo un servizio di discovery dei peer e di lookup delle risorse

• Limiti– Gestione costosa della directory centralizzata– Collo di bottiglia costituito dal nodo centrale (scalabilità

limitata)– Single point of failure (motivi tecnici e legali, es. Napster)

Napster serverIndex1. File location

2. List of peers

request

offering the file

peers

3. File request

4. File delivered5. Index update

Napster serverIndex

IW - Valeria Cardellini, A.A. 2007/08 16

Sistemi con ricerca Sistemi con ricerca floodflood--basedbased• Approccio completamente distribuito per localizzazione le

risorse • Ogni peer propaga (flood) la richiesta ai peer “vicini”, che

a loro volta inviano la richiesta ai loro “vicini” (escludendo il vicino da cui hanno ricevuto la richiesta) – Fino a che la richiesta è risolta oppure viene raggiunto un

massimo numero di passi (per limitare il “raggio della ricerca”)– L’eventuale risposta viene inviata al peer dal quale è stata ricevuta la richiesta

• Da evitare:– La propagazione all’infinito

• Decremento del TTL ad ogni inoltro

– La circolazione nei cicli del grafo• ID della query per evitare che venga nuovamente elaborata dai nodi da cui è stata già ricevuta

IW - Valeria Cardellini, A.A. 2007/08 17

Esempio di ricerca con Esempio di ricerca con floodingflooding

P1

P4

P2P3

P6

P5 P10

P7P8

P9

A?TTL=2

A?TTL=2A?

TTL=2

A?TTL=2

A?TTL=2

A?TTL=2

A?TTL=1

A?TTL=1

A?TTL=1

A?TTL=1

A?TTL=1

A?TTL=1

A?TTL=1

A?TTL=1A?

TTL=1

A?TTL=1 A?

TTL=1

A?TTL=1

A!A!

A!A!

A?TTL=1

A?TTL=1 richiesta con TTL scaduto A?

TTL=1

A?TTL=1 richiesta già ricevuta

IW - Valeria Cardellini, A.A. 2007/08 18

Problemi del Problemi del floodingflooding

• Crescita esponenziale del numero di messaggi (possibilità di attacchi DOS)– Nodi black-hole in caso di congestione– Non è realistico esplorare tutta la rete

• Costo della ricerca– Le risposte dovrebbero avere tempi ragionevoli– Come determinare il raggio di ampiezza del flooding?

• Non è garantito che vengano interrogati tutti i nodi (o i nodi) che posseggono la risorsa

• Traffico di query: i messaggi che non producono risultati occupano comunque banda

• Mancanza di una relazione tra topologia virtuale e topologia reale– A che distanza sono i “vicini”?

IW - Valeria Cardellini, A.A. 2007/08 19

Case Case studystudy: : GnutellaGnutella

• Gnutella versione 0.4 implementa un’architettura decentralizzata pura– Discovery

• Per accedere alla rete occorre conoscere l’indirizzo di un nodo (problema del bootstrap)

• Esistono servizi di host-caching che forniscono liste di nodi della rete Gnutella

• Ottenuta la lista, il nodo prova a connettersi con alcuni dei nodi noti

• A seconda della velocità di connessione, il nodo prova a mantenere da 3 a 8 connessioni

• Se una connessione viene persa, il nodo cerca di connettersi ad un altro nodo della lista, che viene continuamente aggiornata

– Search• Per le ricerche di risorse, Gnutella utilizza un flooding con

esplorazione breadth-first (BFS)

IW - Valeria Cardellini, A.A. 2007/08 20

Connessione in Connessione in GnutellaGnutella

• Un servent può rifiutare una richiesta di connessione, ad esempio perché ha raggiunto un numero massimo di connessioni ammesse

host-cachingn1n2n3

n1n2n3

IW - Valeria Cardellini, A.A. 2007/08 21

Comunicazione fra Comunicazione fra serventservent

• I servent comunicano fra loro con messaggi (detti descriptor); sono supportati 5 tipi di messaggi:– Ping

• Usato per il discovery dei nodi vicini nella rete P2P – Pong

• Messaggio di risposta a un Ping: un nodo che riceve un Ping risponde con uno o più Pong, includendo il suo indirizzo

– Query• Messaggio di richiesta per localizzare una risorsa

– QueryHit• Messaggio di risposta a una query: contiene le informazioni per

reperire la risorsa– Push

• Permette il download da servent dietro un firewall tramite il protocollo HTTP

IW - Valeria Cardellini, A.A. 2007/08 22

Struttura dei messaggiStruttura dei messaggi

• Descriptor ID è un identificatore univoco del messaggio all’interno della rete– Usato per associare le risposte alle richieste e per evitare di

propagare le stesse richieste più di una volta• Il Payload descriptor identifica il tipo di messaggio• All’i-esimo passo: TTL(i) = TTL(0) - Hops(i)• Payload length è la lunghezza dei dati associati al

messaggio

Descriptor IDDescriptor ID PayloaddescriptorPayload

descriptor TTLTTL HopsHops Payload lengthPayload length

16 byte 1 byte 1 byte 1 byte 4 byte

IW - Valeria Cardellini, A.A. 2007/08 23

PingPing e e PongPong

• Il messaggio di Ping è inviato periodicamente per sondare la rete alla ricerca di altri nodi– Un nodo che riceve un Ping risponde inviando al

mittente un Pong• Il messaggio Pong contiene l’IP e la porta su cui sono

accettate connessioni, il numero di file condivisi e il numero di Kb totali condivisi

– Possono essere inviati più messaggi di pong per comunicare il contenuto della propria host-cache

– ll messaggio di ping viene inoltrato ai vicini fino a che il TTL non si annulla

IW - Valeria Cardellini, A.A. 2007/08 24

QueryQuery e e QueryHitQueryHit

• Query specifica il criterio di ricerca e la velocità di trasferimento minima richiesta ai servent

Number of hitsNumber of hits PortPort IPIP SpeedSpeed Result setResult set

1 byte 2 byte 4 byte 4 byte N byte

server IDserver ID

16 byte

• QueryHit riguarda tutti i risultati trovati su un dato servent che soddisfano il criterio di ricerca– Port: porta su cui il servent accetta

connessioni in entrata– Result set: contiene gli identificatori

delle risorse che soddisfano la query– Servent ID: identifica univocamente il

nodo nella rete

IW - Valeria Cardellini, A.A. 2007/08 25

DownloadDownload di un filedi un file

• Un nodo richiede direttamente il trasferimento di un file ad un peer che ha risposto alla query– Il protocollo usato per il trasferimento è HTTP

GET /get/<file index>/<file name>/ HTTP/1.0Connection: keep-aliveRange: bytes=0-User-Agent: Gnutella

HTTP 200 OKServer: GnutellaContent-type: application/binaryContent-length: 200346

... data...

IW - Valeria Cardellini, A.A. 2007/08 26

Sistemi parzialmente centralizzatiSistemi parzialmente centralizzati

• Non tutti i peer sono uguali– I nodi meglio connessi e con buona capacità computazionale

possono avere funzioni speciali (detti supernodi o super-peer o broker)

– I supernodi sono identificati dinamicamente• I supernodi agiscono da rappresentanti dei loro

sottoposti– Organizzazione gerarchica

• I supernodi hanno funzione di directory semi-centralizzata– I supernodi indicizzano le risorse disponibili nei peer che

gestiscono• Il flooding riguarda solo i supernodi • Rispetto ai sistemi decentralizzati puri

– Si riduce il tempo di discovery– Si sfrutta l’eterogeneità dei nodi presenti in una rete P2P

IW - Valeria Cardellini, A.A. 2007/08 27

QueryQuery di una risorsa con supernodidi una risorsa con supernodi

A?

A?A?A?A?

A?A?A?

A!

A!A!

IW - Valeria Cardellini, A.A. 2007/08 28

Case Case studystudy: : KaZaAKaZaA

• Alcune caratteristiche – FastTrack come rete di file sharing; Kaaza è il client più

popolare– Download parallelo di parti di file – Redirezione automatica ad un altro server quando il server

corrente diviene non disponibile– Stima del tempo di download– Numero massimo di upload/download simultanei

configurabile– Gestione della coda al server/client

• Utenti assidui con priorità più elevata al server– Priorità di incentivo

• Chi collabora alla condivisione dei contenuti è privilegiato nello scaricare file

– Ricerca basata su keyword

IW - Valeria Cardellini, A.A. 2007/08 29

KaZaAKaZaA: la tecnologia: la tecnologia

• Architettura– Architettura parzialmente centralizzata

con organizzazione gerarchica dei peer– Ogni peer è un supernodo oppure è

assegnato ad un supernodo– Ogni supernodo ha informazioni su molti

altri supernodi– Lista di potenziali supernodi inclusa

all’atto del download del software

• Software– Proprietario– File e dati di controllo crittografati– Ogni informazione come richiesta o risposta HTTP– Il download include adware e spyware…

IW - Valeria Cardellini, A.A. 2007/08 30

Case Case studystudy: : BitTorrentBitTorrent

• E’ il più popolare protocollo P2P per la distribuzione di contenuti– Circa 15% del traffico su Internet

• Idea di base: dividere un file in pezzi (da 256 KB) e far ridistribuire ad ogni peer i dati ricevuti, fornendoli a nuovi destinatari; in questo modo:– Si riduce il carico di ogni sorgente– Si riduce la dipendenza dal distributore originale– Si fornisce ridondanza

• Per condividere un file, un peer crea un file .torrent, che contiene metadati sul file condiviso e sul tracker– Tracker: il nodo che coordina la distribuzione del file

IW - Valeria Cardellini, A.A. 2007/08 31

Caratteristiche di Caratteristiche di BitTorrentBitTorrent• Per scaricare un file, un peer

– ottiene un file .torrent per quel file– si connette al tracker individuato in .torrent, che indicherà da

quali peer scaricare i vari pezzi del file– si connette ai peer individuati per scaricare i vari pezzi

• Un gruppo di peer interconnessi per condividere un “torrente” viene detto swarm– Se lo swarm contiene solo il seeder iniziale, il client si connette

direttamente al seeder– Mano a mano che i peer entrano nello swarm, iniziano a

negoziare tra loro pezzi del file (anziché scaricarli dal seeder)• Alcune tecniche usate dai client BitTorrent

– Scaricare i primi 4 pezzi selezionandoli in modo casuale per aumentare la possibilità di trading con gli altri peer

– Scaricare i rimanenti pezzi selezionandoli in base alla strategia rarest first

• Prima il pezzo più raro• Migliore della selezione casuale

– Inviare dati ai peer che inviano dati (tit-for-tat)IW - Valeria Cardellini, A.A. 2007/08 32

Routing in reti strutturateRouting in reti strutturate• Sistemi con Distributed Hash Table (DHT)

– Anche noti come sistemi con document rooting• Ad ogni peer è assegnato un ID ed ogni peer conosce un

certo numero di peer• Ad ogni risorsa condivisa (pubblicata) viene assegnato un

ID, basato su una funzione hash applicata al contenuto della risorsa ed al suo nome

• Routing della risorsa pubblicata verso il peer che ha l’ID più simile a quello della risorsa

• La richiesta per la risorsa specifica sarà instradata verso il peer che ha l’ID più simile a quello della risorsa

• Possibile copia locale della risorsa ad ogni peer attraversato

IW - Valeria Cardellini, A.A. 2007/08 33

DistributedDistributed HashHash TableTable• Le DHT offrono un’astrazione distribuita della struttura

dati hash table• Le risorse sono rappresentate da una coppia chiave

valore (key K, value V)– K identifica l’oggetto, che è contenuto in V– put(K, V): memorizza V in tutti i nodi responsabili per l’oggetto

identificato da K– remove(K, V): cancella tutti i riferimenti a K e all’associato V– V = get(K): recupera V associato a K da uno dei nodi

responsabili• Ogni chiave viene mappata su almeno un nodo della

rete • Ogni risorsa è identificata solo mediante il valore della

chiave – Per cercare una risorsa occorre conoscere il valore esatto della

chiave

IW - Valeria Cardellini, A.A. 2007/08 34

DistributedDistributed HashHash TableTable (2)(2)• Le DHT operano in maniera distribuita con molti nodi

– Elevata scalabilità• Diverse soluzioni che specificano anche la modalità di

routing delle ricerche e della memorizzazione – Più di 20 protocolli e prototipi per reti P2P strutturate, tra cui:

• Chord (MIT)• Tapestry (Berkeley)• CAN (Berkeley)• Pastry (Rice Univ., Microsoft)• Kademlia (NY Univ.)• SkipNet/SkipGraph• Viceroy• Z-Ring• Chimera (UCSB)

IW - Valeria Cardellini, A.A. 2007/08 35

ChordChord

• I nodi e le chiavi sono mappatiin uno spazio circolare mediante funzioni hash

• Ogni nodo è responsabile delle chiavi poste tra sé e il nodo precedente nel cerchio

• Finger table– E’ una tabella di routing

posseduta da ogni nodo– Il nodo in posizione x conosce

nodi competenti per le posizioni • x+1• x+2• x+4• x+8, …

http://www.pdos.lcs.mit.edu/chord/

IW - Valeria Cardellini, A.A. 2007/08 36

Finger Finger tabletable in in ChordChord

• Idea della finger table– Ogni nodo conosce “bene” le posizioni vicine ed ha un’idea

approssimata delle posizioni più lontane• Come avviene la ricerca? Algoritmo di routing:

– Il nodo in posizione x vuole instradare una richiesta per la posizione z

– Se z è nella zona di competenza del nodo, la ricerca termina– Altrimenti, cerca nella finger table un nodo y con y = max

numero < z e invia la richiesta a quel nodo• Caratteristiche

– L’algoritmo raggiunge velocemente le vicinanze del punto cercato, per procedere poi con salti via via più piccoli

– Costo di lookup O(log N), essendo N il numero dei nodi

IW - Valeria Cardellini, A.A. 2007/08 37

lookup(K54)

N1

N14

N48

N38

N8

N21N42

N51

N56K54

finger table

N8+32 N42

... …

N42+16 N1

N42+8 N51

finger table

N51+4 N56

N51+2 N56

finger table

Routing in Routing in ChordChord

Problemi Chord– Meccanismo fragile– Scarso supporto per

ricerche senza matching esatto

– Non considera la topologia fisica IW - Valeria Cardellini, A.A. 2007/08 38

TapestryTapestry e CANe CAN• Tapestry

– Prefix routing basato su algoritmo di Plaxton

• La struttura mesh di Plaxton contiene puntatori ai nodi il cui ID corrisponde agli elementi di una struttura ad albero di prefissi di ID

– Anche in Pastry e Kademlia il routing è basato su Plaxton

• CAN (Content AddressableNetwork)– Nodi e risorse disposti in uno

spazio cartesiano d-dimensionale– Ogni nodo è responsabile di un

sottospazio– Ogni risorsa è individuata da d

coordinate