1
Capitolo 1
Peer to Peer Overlay Networks
1.1 – Introduzione
Le architetture informatiche distribuite note come peer-to-peer sono progettate per consentire agli utenti di condividere risorse, come ad esempio contenuti digitali, storage o potenza di calcolo, senza alcuna intermediazione o controllo da parte di autority o servizi di coordinamento centralizzati. Nati e sviluppati nello specifico contesto della rete Internet, questi sistemi sono ispirati da un semplice e fondamentale principio: la capacità di adattarsi ad un ambiente estremamente dinamico, pur mantenendo sostanzialmente inalterate le proprie caratteristiche di affidabilità e connettività. In un’architettura peer-to-peer le risorse, oltreché remote, possono considerarsi disperse, in quanto la loro disponibilità si considera in genere indipendente dalla disponibilità del nodo che le ha inizialmente condivise. Le tecniche specifiche messe in atto a questo scopo variano secondo le particolari architetture e si basano da un lato sulla ridondanza delle risorse e delle connessioni, dall’altro sulla decentralizzazione degli algoritmi di routing e discovery.
Le peer-to-peer (P2P) overlay networks [1] indicano sistemi distribuiti senza alcuna organizzazione gerarchica o controllo centralizzato. I peers si auto-organizzano in reti logiche (overlay networks) al di sopra della rete IP, offrendo un insieme di caratteristiche quali, ad esempio, architetture di routing robuste, ricerca efficiente dei dati, selezione dei peers vicini.
Il modello P2P rappresenta l’antitesi della classica architettura client-server nella quale ogni nodo è un server o un client che dipende da un’autorità centrale; i dati sono memorizzati in un server il quale li invia a quei clients che ne fanno richiesta. Il modello P2P, invece, fa si che ogni nodo si comporti sia da server che da client a seconda che si trovi ad essere fornitore o richiedente di un particolare servizio.
Nella figura seguente è possibile vedere come i nodi, sui quali è in esecuzione l’applicazione P2P, generano l’overlay network creando tra di loro dei link virtuali.
Figura 1.1 – Overlay Network
1.2 –Confronto: P2P vs. Client-Server
Come accennato sopra il modello P2P è ben diverso da quello client-server, vediamone adesso le principali differenze:
Client-Server
Asimmetrico: client e server sono ben distinti e svolgono compiti differenti;
Conoscenza globale: i server hanno una visione globale della rete;
Approccio centralizzato: le comunicazioni e la gestione sono centralizzate;
Singolo punto di rottura: il malfunzionamento di un server comporta il malfunzionamento di tutto il sistema;
Scalabilità limitata: i server sono soggetti ad un facile “overhead” che limita la scalabilità della rete;
P2P
Simmetrico: ogni nodo ha le stesse funzioni e può essere sia client che server;
Conoscenza locale: i peers conoscono solo un sottoinsieme dei nodi della rete;
Approccio decentralizzato: non vi è alcuna conoscenza globale ma solo interazioni locali; Robustezza: le conseguenze in
caso di malfunzionamento di qualche nodo sono minime o nulle;
Elevata scalabilità: grazie alla distribuzione del carico e alla elevata capacità aggregata, la rete risulta altamente scalabile;
3
Costo elevato: il mantenimento dei server e delle risorse della rete risulta costoso;
Costo ridotto: ogni utente contribuisce alle risorse della rete abbattendo i costi;
Figura 1.2 – Client – Server network
1.3 – Architetture P2P
E’ opportuno premettere che una rete peer-to-peer assolutamente decentralizzata non può essere realizzata su vasta scala data la necessità di uno o più nodi, detti rendezvous, che hanno il compito di fornire i parametri di comunicazione iniziale ai nuovi nodi che vogliono connettersi al sistema. Al di là di questo, le reti peer-to-peer sono comunemente classificate in base alla relazione esistente tra la posizione delle risorse nella rete e la topologia della rete stessa, e all’uso più o meno sistematico di nodi di coordinamento meglio conosciuti come super-peers.
Le principali architetture cui si fa riferimento quando si parla di sistemi peer-to-peer sono: centralizzate o decentralizzate, strutturate o non strutturate.
Per poter confrontare le diverse soluzioni presenti si deve tener conto di due aspetti principali:
1. Scalabilità del sistema: per ogni nodo si deve controllare l’overhead di comunicazione (numero di passi per raggiungere il nodo che memorizza l’informazione) e la memoria utilizzata (dimensione della tabella di routing) in funzione del numero (N) di nodi nel sistema;
2. Robustezza ed adattabilità ai cambiamenti frequenti e ai malfunzionamenti;
1.3.1 – Centralizzate e Decentralizzate
La distinzione tra reti peer-to-peer centralizzate e decentralizzate è relativa alla presenza o meno di un servizio di coordinamento [2]. Alcune architetture, infatti, sono basate su un’infrastruttura centrale che svolge in genere un servizio di indicizzazione delle risorse, lasciando ai peers l’onere di distribuire le risorse stesse.
5
Figura 1.4 – Esempio di rete P2P centralizzata
Nella figura 1.4 è rappresentata l’organizzazione di un’architettura peer-to-peer centralizzata. I clients si connettono ad un’unità centrale che ha il compito di mantenere:
una tabella degli utenti connessi (indirizzo IP, numero di porta, eventuali informazioni sulla connessione quali ad esempio l’ampiezza della banda, ecc.);
una tabella delle risorse condivise (dati e contenuti multimediali, potenza di calcolo, ecc) da ogni utente, eventualmente corredata da metadati (informazione che descrive un insieme di dati);
Al momento della connessione i clients contattano l’unità centrale pubblicando la lista delle risorse che intendono condividere. Le query (richieste) vengono inoltrate al server centrale che individua nelle proprie tabelle il peer (o eventualmente i peers) che condivide una risorsa rispondente ai vincoli. La successiva comunicazione fra i clients
avviene P2P, con una o più connessioni dirette tra il peer che ha richiesto la risorsa e i peers che la distribuiscono. Se il vantaggio del modello centralizzato risiede nella semplicità e affidabilità del protocollo, il principale problema sta nella presenza di un unico punto di “rottura” e nella vulnerabilità alla censura. Infatti lo sviluppo di Napster, uno dei primi esempi di tale architettura , è stato interrotto a causa dell’incorrere di azioni legali piuttosto che a causa di limiti tecnologici.
In una rete di questo tipo il nodo che possiede la risorsa viene trovato dopo O(1) passi poiché basta inoltrare una richiesta al server. Quest’ultimo dovrà memorizzare una quantità di dati pari a O(N) con N pari al numero di informazioni disponibili nel sistema.
Le reti peer-to-peer decentralizzate sono invece caratterizzate, per loro stessa natura, dalla mancanza di un singolo punto di “rottura”; caratteristica dovuta al fatto che nel sistema non esiste alcun nodo privilegiato necessario al funzionamento. Non esiste alcun controllo centralizzato dell’attività della rete, ed ogni utente esegue un’applicazione che funziona contemporaneamente sia da client che da server, chiamata servent.
Un esempio è costituito dalla rete Gnutella [3] in cui la comunicazione tra i servent è regolata da un protocollo che definisce quattro tipi di messaggi:
ping: rappresenta una richiesta diretta ad un certo host affinchè si annunci; pong: rappresenta un messaggio di risposta ad un ping. Contiene l’indirizzo IP e
la porta del mittente del messaggio e in più il numero e la dimensione dei file condivisi;
query: rappresenta una richiesta di risorse e comprende anche indicazioni sui requisiti di banda;
query hits: rappresenta il messaggio di risposta ad una query. Contiene indirizzo IP e numero di porta ai quali connettersi per il download, informazioni relative alla banda e il numero dei file che corrispondono ai requisiti della richiesta;
Un esempio di comunicazione in una rete peer-to-peer puramente decentralizzata è illustrato nella figura 1.5.
7 Figura 1.5 – Esempio di rete P2P decentralizzata
Dopo essersi connesso alla rete ogni nodo invia un messaggio di ping ad ognuno dei suoi vicini, cioè a tutti quei nodi dei quali conosce direttamente l’indirizzo IP e il numero di porta. Questi, a loro volta, rispondono con un messaggio di pong, identificandosi, e propagano il ping ai propri vicini. La localizzazione di una risorsa nella rete avviene inoltrando un messaggio di query che viene propagato nella rete fino all’esaurimento di un time-to-live (TTL); eventuali risposte vengono inoltrate al nodo che ha originato la query seguendo il cammino inverso. Quando un nodo riceve un messaggio di query hit, che indica che la risorsa è stata localizzata su un certo peer, esso stabilisce una connessione diretta per il download. La scalabilità del sistema è garantita dal time-to-live dei messaggi, che impone di fatto un limite oltre il quale i messaggi non possono propagarsi, evitando il collasso della rete.
I sistemi peer-to-peer decentralizzati, in assenza di ottimizzazioni come il TTL, impiegano O(N2) passi per localizzare la risorsa e, dal momento che l’informazione di routing è condivisa e non dipende dal numero di nodi del sistema, ogni nodo ne immagazzina una quantità pari a O(1).
Una via di mezzo è rappresentata dai sistemi ibridi: essi impiegano il concetto di super-peers, i quali inoltrano le query ricevute ad altri super-peers con cui sono collegati in una struttura totalmente decentralizzata. Questi nodi vengono eletti in base alle capacità di calcolo e banda disponibile e permettono di migliorare le prestazioni complessive
della rete, riducendone i tempi di risposta, senza però introdurre elementi centralizzati che possono essere soggetti a controllo o censura, o costituire un singolo punto di “rottura” dell’intero sistema. La struttura di una rete peer-to-peer ibrida è mostrata in figura 1.6.
Figura 1.6 – Esempio di rete P2P ibrida
1.3.2 – Strutturate e non strutturate
I sistemi si possono classificare, anche, in strutturati e non strutturati intendendo evidenziare con questa distinzione l’esistenza o meno di una relazione tra la topologia della rete e la localizzazione di una risorsa nella rete stessa [4].
Nei sistemi non strutturati non esiste alcuna relazione tra la posizione di una risorsa e la topologia della rete. Le overlay networks usano tecniche non deterministiche quali il flooding (le richieste sono inoltrate a tutti i partecipanti) o la random walks (le richieste
9
sono inoltrate ad un sottoinsieme dei partecipanti scelti in maniera random) per la localizzazione di una risorsa nella rete. Ogni peer valuta le query ricevute in maniera locale e manda al peer mittente una lista di tutti i contenuti che corrispondono alla richiesta. Va osservato che, mentre le tecniche basate sul flooding si adattano bene a quei sistemi nei quali i peers entrano ed escono con frequenza elevata e in cui i dati sono altamente ridondanti, esse risultano poco adatte nel localizzare dati poco diffusi poiché, essendo questi in possesso di pochi peers, le query dovranno essere inoltrate alla quasi totalità di essi. Le reti P2P non strutturate presentano quindi un problema di base: i peers diventano facilmente sovraccarichi e la rete risulta non scalabile nel caso in cui si debbano gestire query aggregate ad elevata frequenza e in seguito all’improvviso aumento della dimensione del sistema che provoca un incremento proporzionale delle richieste all’interno della rete. Esempi di P2P overlay networks non strutturate sono: Gnutella, KaZaA, eDonkey2000 e BitTorrent che verrà trattato in maniera approfondita nei capitoli successivi.
Nei sistemi strutturati, invece, le risorse vengono memorizzate su nodi scelti in maniera deterministica secondo un preciso algoritmo (DHT) che fornisce un mapping tra i contenuti e i nodi, o, più precisamente, tra i rispettivi identificatori sotto forma di tabelle di routing distribuite che permettono di instradare in maniera efficiente le query verso quei peers che possiedono la risorsa cercata. Le reti P2P strutturate sono in grado di localizzare in maniera efficiente dati rari, in quanto il routing basato su algoritmi deterministici risulta scalabile. Esempi di P2P overlay networks strutturate sono: Content Addressable Network (CAN), Tapestry, Chord, Pastry e Kademlia.
1.3.2.1 – Distibuted Hash Tables (DHT)
Una Distributed Hash Table rappresenta una struttura dati distribuita che consente di memorizzare le coppie <key, value>, ottenute tramite una funzione hash, in maniera efficiente, affidabile e robusta. Tale approccio consiste nell’assegnare degli identificatori unici (key), scelti nello spazio degli identificatori, ai dati e contemporaneamente nell’assegnare degli identificatori (value), scelti dallo stesso spazio, ad un set di nodi che possiedono il dato al quale la key si riferisce. Operazioni quali “put(key, value)” e “value=get(key)” possono essere invocate per memorizzare e recuperare il dato corrispondente alla key. Ciò comporta lo scambio di messaggi di
routing verso quel peer cui è associata la key stessa. Ciascun nodo mantiene delle piccole tabelle di routing nelle quali memorizza gli identificatori dei peers vicini e i relativi indirizzi IP. Le richieste di localizzazione o i messaggi di routing sono inoltrati verso i peers dell’overlay in maniera progressiva considerando gli identificatori dei nodi che risultano prossimi alla key nello spazio degli identificatori. In teoria, i sistemi basati sulle Hash Table Distribuite possono garantire che qualsiasi dato possa essere localizzato, in media, in un numero di passi pari a O(logN) e che ogni nodo possieda delle tabelle di routing con O(logN) entrate. E’ opportuno osservare che il percorso tra due nodi, considerando la rete fisica sottostante, può essere ben diverso da quello dell’overlay network basato sull’approccio DHT, determinando un ritardo nella fase di localizzazione che può portare ad un decadimento delle prestazioni della rete.
Il DHT presenta un limite dovuto alla natura transiente (il tempo di connessione media per un nodo è di 60 minuti) dei clients P2P. L’uscita graceful (annunciata) di un nodo comporta in genere O(logN) operazioni per mantenere coerenti le strutture dati mentre una di tipo graceless (senza annuncio e trasferimento preventivo di informazioni di stato) ha esiti peggiori.
1.4 – Applicazioni delle reti P2P
I sistemi peer-to-peer trovano applicazione in una vasta gamma di servizi, caratterizzati da una sostanziale indipendenza da autority di coordinamento. In base a tali servizi è quindi possibile distinguere quattro categorie principali:
File-Sharing e Content Distribution Comunicazione e Collaborazione Calcolo Distribuito
Database
1.4.1 – File-Sharing e Content Distribution
La maggior parte dei sistemi peer-to-peer oggi disponibili rientrano in questa categoria, fino al punto che in taluni ambienti la tecnologia peer-to-peer è stata recepita come sinonimo di pirateria informatica e violazione di copyright. In realtà, le applicazioni di
11
questo tipo spaziano dai più semplici strumenti di file-sharing a complesse piattaforme per la pubblicazione, catalogazione, ricerca e distribuzione di contenuti digitali. Esempi di applicazioni file-sharing sono i già citati Napster (1999), Gnutella ed eDonkey (2000), KaZaA (2001), eMule e BitTorrent (2002).
Le applicazioni di Content Distribution, invece, consistono nella distribuzione real-time di dati audio e video attraverso la rete P2P (live media streaming). Esempi di questo tipo sono i software open-source PPLive, SopCast, CoolStreaming, PPStream e Tvants.
1.4.2 – Comunicazione e collaborazione
In questa tipologia si inquadrano le infrastrutture costruite per agevolare la comunicazione diretta, generalmente interattiva, tra applicazioni o utenti della rete Internet. Esempi classici sono chat, instant-messaging e P2P-VOIP ma, in questo campo, si stanno affermando applicazioni sempre più evolute di telepresenza e collaborazione a distanza, dall’outsourcing al telelavoro.
1.4.3 – Calcolo Distribuito
La possibilità di distribuire job di calcolo su CPU remote, in particolare sfruttando i tempi di inattività dei computer presenti ai margini della rete ha stimolato la nascita di questo tipo di applicazioni, di cui il progetto Seti@home [5] è sicuramente l’esempio più noto. Le applicazioni di calcolo distribuito richiedono un moderato impegno di arbitraggio per dividere un job in frammenti che vengono successivamente inviati agli altri computer per l’elaborazione. I risultati sono successivamente convogliati verso un repository centralizzato. Questo genere di applicazioni ha tuttavia messo in luce una caratteristica tipica degli utenti di applicazioni peer-to-peer: la disponibilità a condividere risorse (in questo caso cicli di CPU) senza un diretto tornaconto, ma solo in virtù di un senso di appartenenza a una community.
1.4.4 – Database
Mentre le applicazioni di file sharing mettono sostanzialmente a disposizione degli utenti una immensa collezione di dati non strutturati, un grande impegno si sta riversando nella progettazione di veri e propri sistemi di Database basati sulle tecnologie peer-to-peer. Edutella [6], ad esempio, è un progetto open source che ha come obiettivo la definizione di standard per la pubblicazione di metadati e la risoluzione di query su reti peer-to-peer.
1.5 – Strumenti di valutazione per architetture P2P
Lo studio e l’analisi dei sistemi P2P può essere distinto in base a due approcci fondamentali: quello sperimentale e quello simulativo.
Considerando l’approccio sperimentale, l’esempio più significativo è costituito da PlanetLab [7], una sorta di comunità mondiale costituita da oltre 900 computers sparsi in più di 35 paesi e che gode dell’appoggio di università e laboratori di ricerca. La rete si erge su un software basato su Linux ed in grado di ricreare un ambiente condiviso grazie al quale simulare un grande laboratorio internazionale.
L’approccio simulativo, invece, si può distinguere in base a due modelli principali: packet-level e flow-level. Le differenze principali tra questi due modelli saranno specificate in dettaglio nel capitolo 3 dove si affronta lo studio di simulazione di reti P2P BitTorrent.
La tabella seguente riassume i principali simulatori di reti P2P disponibili in letteratura mostrandone il livello di dettaglio e di scalabilità:
13 Livello di
dettaglio
Scalabilità Linguaggio di
programmazione
NS-2 Pacchetto Molto bassa C++
PLP2P Pacchetto Media C++
QueryCycle Flusso - Java
3LS Flusso Molto bassa (< 1000 peer)
Java
PeerSim Flusso Molto alta
(> 10^6 peers)
Java
NeuroGrid Flusso Alta
(300.000 peers)
Java
GPS Flusso ? Java
P2PRealm Flusso Media
(100.000)
Java
Tabella 1.1 – Simulatori reti P2P
Vediamo in dettaglio le caratteristiche di alcuni di essi:
PeerSim [8]: è stato sviluppato con l’obbiettivo di fornire principalmente scalabilità e supporto alla dinamicità della rete. Esso si basa sul linguaggio di programmazione Java e ha due motori di simulazione, uno basato sui cicli e l’altro sugli eventi. Il motore basato sui cicli permette simulazioni scalabili ma non è molto accurato. Ciò accade poiché la simulazione di overlay network di grosse dimensioni richiede l’assunzione di semplificazioni circa il livello di dettaglio della simulazione. Il motore basato sugli eventi, invece, supporta la dinamicità ed è maggiormente realistico a scapito di una diminuzione della scalabilità della simulazione.
3LS [9]: è un simulatore open-source di overlay networks progettato per superare i problemi di scalabilità e usabilità. Il sistema è diviso in tre livelli di architettura: un modello di rete, uno di protocollo e uno di utente. Il primo modello usa una matrice bi-dimensionale per memorizzare le distanze fra i nodi. Il secondo definisce il protocollo attualmente simulato mentre il modello di utente fornisce l’interfaccia di input. Il 3LS usa la maggior parte delle risorse di memoria per l’interfaccia grafica poiché il simulatore usa la memoria principale per memorizzare ogni evento eseguito e ciò non permette di simulare sistemi con più di mille nodi.
Query Cycle [10]: è utilizzato principalmente per la simulazione del file-sharing. Comprende modelli realistici per la distribuzione di contenuti, attività di query e gestione di download. La distribuzione dei contenuti si basa su un modello nel quale ogni file appartiene ad una categoria definita dalla sua popolarità. La simulazione si sviluppa attraverso cicli di query rappresentanti il periodo di tempo tra l’invio di una query e la ricezione di una risposta. Le query generate vengono accodate e gestite secondo una disciplina FIFO.
GPS (General P2P Simulator) [11]: è un simulatore che si prefigge di simulare reti P2P in maniera efficiente e accurata. L’efficienza è garantita dall’utilizzo di una simulazione di tipo flow-level invece che packet-level. Un livello di dettaglio più accurato è garantito tenendo traccia dell’infrastruttura di rete ed usando un modello matematico per stimare accuratamente il comportamento dei flussi. Il GPS simula, inoltre, il download di un file, cosa che generalmente non accade negli altri simulatori.
Nel nostro studio di simulazione è stato utilizzato il Network Simulator v2 che sarà presentato nel dettaglio nel capitolo 3.
