Post on 28-Jun-2020
1IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
Lezione 1
Introduzione: Caratteristiche Generali,
Applicazioni P2P
Laura Ricci
22-2-2012
Università degli Studi di PisaDipartimento di Informatica
2IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
INFORMAZIONI UTILI
L’esame può essere sostenuto dagli studenti di: Lauree Specialistiche in Informatica, Tecnologie Informatiche,
Informatica per l'Economia el'Azienda.
Lauree Magistrali in Informatica, Informatica per l'Economia e l'Azienda, Informatica e Networking
Laurea triennale (26) (vecchio ordinamento)
Prerequisiti Reti di Calcolatori Algoritmica
3IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
MATERIALE DIDATTICO
Materiale Didattico lucidi delle lezioni (scaricare quelli di quest'anno) tutorial e materiale pubblicato sulla pagina del corso Libri di Testo Sasu Takoma, Overlay Networks, Toward Information Networking, Taylor
and Francis, 2010 Maarten Van Steen, Graph Theory and Complex Networks, Gennaio 2010 Testi di Consultazione Peer to Peer Computing, Applications, Architecture, Protocols and Challanges, Yu-Kwong Ricky Kwok, CRC Press, 2012 Peer to Peer Systems and Applications, R. Steinmetz, K.Wehrle, LNCS 3485,
Springer Verlag, 2005 Peer to Peer Computing, Principles and Applications, Q.Hieu Vu, M.Lupu,
B.Chin Ooi, Springer Verlag, 2010 Buford, Yu, Lua, P2P Networking and Applications, Morgan Kaufmann, 2009
4IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
MODALITA' DI ESAME
Mid term + Final term: lettura di articoli e scrittura di una breve relazione esperienza positiva nell'anno accademico 2010/2011
Scritto o progetto (a scelta)
durante il corso verranno proposti diversi progetti, che possono essererealizzati mediante diversi ambienti di sviluppo
si accettano proposte di progetto, da vagliare
Orale: solo per chi non ha sostenuto o superato midterm e/o final term
5IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
STRUMENTI PER LA REALIZZAZIONE DEL PROGETTO
Peersim simulatore orientato alla simulazione di reti P2P altamente scalabile (fino a 10000 peer per semplici protocolli) http://peersim.sourceforge.net/
Overlay Weaver Supporta diversi algoritmi di routing Definisce una semplice interfaccia verso diverse distributed hash tables http://overlayweaver.sourceforge.net/ La simulazione di una rete P2P richiede l'implementazione di un insiemedi
interfacce/l'estensione di un insieme di classi JAVA PeerfactSim.KOM
nuova proposta supporta simulazioni su larga scala di sistemi P2P http://peerfact.kom.e-technik.tu-darmstadt.de/
6IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
PROPOSTE DI PROGETTO
simulazione di
reti P2P non strutturate
Distributed Hash Tables
sistemi auto-organizzanti
con particolare attenzione alla analisi della topologia risultante
7IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SISTEMI PEER TO PEER: INTRODUZIONE
Definizione 1: Un sistema Peer to Peer è un insieme di entità autonome (peers), capaci di auto-organizzarsi, che condividono un insieme di risorse distribuite presenti all’interno di una rete di computers. Il sistema utilizza tali risorse per fornire una determinata funzionalità in modo completamente o parzialmente decentralizzato.
Peer= Pari, uguale (persona di pari grado, coetaneo)
Risorse condivise: Informazioni (Files) Spazio di memorizzazione (Distributed File System) Potenza di calcolo Banda
8IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SISTEMI PEER TO PEER: INTRODUZIONE
Definizione 2:
Un sistema P2P è un sistema distribuito costituito da un insieme di nodi n
interconnessi capaci di auto organizzarsi costruendo topologie di diverso
tipo con lo scopo di condividere risorse come contenuti, cicli di CPU,
memoria, banda. Il sistema è capace di adattarsi ad un continuo
cambiamento dei nodi partecipanti (churn) mantenendo connettività e
prestazioni accettabili senza richiedere l'intervento di alcuna entità
centralizzata (come un server)
9IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
CONDIVISIONE DI RISORSE
P2P: riguarda il dare e ricevere da una comunità. Ogni peer fornisce una risorsa ed ottiene in cambio altre risorse.
situazione più comune: si offre musica al resto della comunità, si ottiene altra musica in cambio (Napster, Gnutella,…)
un peer ha sia funzionalità di client, che di server (funzionalità simmetrica = SERVENT)
Ma un peer può decidere di offrire gratuitamente risorse, ad esempio per partecipare ad una ‘giusta causa’.
Ricerca di vita extra-terrestre Ricerca sul cancro
Le risorse condivise si trovano ‘ai bordi’ di Internet, cioè sono fornite direttamente dai peers, non esistono nodi ‘special purpose’ definiti solo per la loro gestione.
10IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
CONDIVISIONE DI RISORSE
La connessione dei peers al sistema è intermittente (transiente): le disconnessioni e le riconnessioni al sistema sono frequenti
Le risorse offerte dai peers vengono aggiunte e tolte dinamicamente al sistema
Ad un peer può essere associato un indirizzo IP diverso per ogni diversa connessione al sistema
⇒E’ impossibile localizzare una risorsa mediante un indirizzo IP statico
⇒Definizione di nuovi meccanismi di indirizzamento, definiti a livello superiore rispetto al livello IP
11IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SISTEMI PEER TO PEER: FILE SHARING ED OLTRE
P2P file sharing Napster Gnutella, KaZaa eMule BitTorrent
Instant Messaging and Voice over P2P IMP systems: Instant Message and Presence Applications VoP2P: Skype
P2P TV Video Streaming applications
Content Distribution Network (CDN) P2P distributed storage
Wuala, Freenet
12IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
ALCUNE TAPPE NELLA (ANCORA BREVE) STORIA DEL P2P
2003: Sandvine Study in Europa(France, Germany, ..)
predomina EDonkey/EMule in USA
predomina KaZaA/Fastrack
2005: BitTorrent
il sistema di file sharing P2P più diffuso Skype dominante nel VOIP
KaZaA diventa sempre più irrelevante eDonkey rimpiazzato da eMule che usa un protocollo compatibile, ma esteso
13IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
ALCUNE TAPPE NELLA (ANCORA BREVE) STORIA DEL P2P
2009: Wuala P2P-based storage service
è in grado di mettere a disposizione della rete di utenti lo spazio inutilizzato che risiede sul loro disco fisso e che hanno deciso di mettere a disposizione della rete
sicurezza replicazione
KaZaA and eMule quasi scomparsi PPLive: P2P-based Video Streaming Platform: molto usata in Asia BBC Iplayer: http://www.bbc.co.uk/iplayer/ Vuze (evoluzione di Azureus); P2P-based Video-on demand Le sfide per il futuro: P2P social networks? P2P cloud? P2P MMORG?
14IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P: ANALISI DEL TRAFFICO
15IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING: UNA 'KILLER APPLICATION'
Condivisione di files: nasce con il rapido successo di Napster, alla fine degli anni 90, circa 10 anni dopo l'affermazione del World Wide Web
Prima generazione: Napster introduce un insieme di servers su cui gli utenti registrano i descrittori
dei files che intendono condividere la trasmissione dei contenuti (download/upload) avviene con modalità
P2P La presenza di directory centralizzate è stato il 'tallone di achille' di
questa applicazione Napster è stato giudicato responsabile per non aver rispettatole leggi
sul copyright, proprio perchè avrebbe potuto individuare i contenuti scambiati illegalmente tra gli utenti mediante l'analisi delle directory centralizzate
16IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING: UNA 'KILLER APPLICATION'
Seconda generazione Non esiste alcun punto di centralizzazione Sia la ricerca dei files che il trasferimento del contenuto avviene in modo
completamente distribuito tra i peer Gnutella, FastTrack/Kazaa, BitTorrent Freenet: introduce diversi meccanismi per garantire l'anonimato dei peer
Sostituzione del mittente di un messaggio Tecniche di encrypting
Effetti laterali della diffusione delle applicazioni di file sharing: modifica radicale della modalità di fruizione di contenuti musicali
dai CD a musica online iTunes
17IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING: UN'APPLICAZIONE KILLER
Come funziona un’applicazione perla condivisione di files musicali Tipico utilizzo del sistema P2P
Un utente U possiede un applicativo P2P sul suo notebook Si interconnette ad Internet in modo intermittente: ottiene un nuovo indirizzo
IP per ogni diversa connessione Offre alla comunità alcune canzoni, registrandole in una directory condivisa,
associando ad ogni canzone alcune chiavi per individuarla (titolo, autore, data di pubblicazione,...)
U è interessato a reperire una canzone ed invia una query al sistema L’applicativo visualizza informazioni circa gli altri peers che posseggono la
canzone richiesta U può scegliere un peer P (vedremo in seguito in base a quale criterio) Il file viene copiato dal PC di P a quello di U Mentre U effettua il dowload, altri utenti possono effettuare upload di qualche
file messo a disposizione da U
18IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING: UN'APPLICAZIONE KILLER
Il software P2P consente: All'utente di definire una directory, nel proprio file system, dove
memorizzare i files che vuole condividere con la comunità. Ogni altro peer può reperire files da quella directory
Il peer si comporta come un web server
All'utente di copiare files dalle directory condivise dagli altri utenti Il peer si comporta come un client
Agli utenti di individuare il materiale richiesto, mediante queries sottoposte al sistema
Funzionalità analoga a Google
L'applicativo sull'host dell'utente si comporta come un servlet
19IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING: PROBLEMI
Molti applicativi P2P sono scaricabili gratuitamente dalla rete, ma possono contenere
meccanismi di spyware o di malware, in realtà quindi il software non è gratuito, ma viene pagato attraverso
un'invasione della privacy dell'utente, spesso inconsapevole. Spyware = un software che
raccoglie informazioni riguardanti l'attività online di un utente (siti visitati, acquisti eseguiti in rete etc) senza il suo consenso
trasmette tali informazioni tramite la rete ad un'organizzazione che utilizza tali informazioni per trarne profitto, solitamente attraverso l'invio di pubblicità mirata.
Malware = un software che può causare danni più o meno gravi al computer su cui viene eseguito.
20IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
FILE SHARING : PROBLEMI
Pollution (= Inquinamento) Viene immessa nella rete P2P una grossa mole di materiale corrotto I peer non riescono a distinguere il materiale integro da quello corrotto,
scaricano e contribuiscono alla diffusione di materiale corrotto Il numero delle copie corrotte può superare quello di quelle integre Esistenza di vere e proprie pollution companies: OverpeerPresenza di free riders Peer che utilizzano l'applicazione per scaricare contenuti dagli altri peer,
ma non contribuiscono a fornire contenuti Soluzioni:
Meccanismo di incentivi (crediti in eMule) Meccanismo per l'individuazione e la penalizzazione dei free riders
(Algoritmi basati sulla teoria dei giochi in Bittorrent)
21IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
VOICE OVER P2P Clients VoIP (Voice over IP) iniziano ad apparire a metà degli anno '90
offrono chiamate desktop-to-desktop free bassa qualità della voce diffusione limitata
IMP (Instant Messaging and Presence) applications Microsoft Messanger, Yahoo Messenger, Jabber, tutti basati su una
architettura client server alcune versioni hanno incluso supporti per la telefonia, ma hanno avuto
scarso successo Skype applicazione di VoP2P, voice over P2P, lanciata nel 2003
più di 500 milioni di account e più di 50 milioni di utenti attivi contemporaneamente
offre sia chiamate desktop to desktop che desktop verso la rete pubblica di telefonia
buona qualità delle chiamate integra voice call con caratteristiche IMP
22IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SKYPE: CARATTERISTICHE GENERALI
Architettura derivata da quella di Kazaa e basata sulla presenza di SuperPeer Basato su un protocollo proprietario e traffico crittato
scarsa documentazione, analisi sperimentale del traffico I SuperPeer sono responsabili di
ricerca dei peer e la loro localizzazione a differenza di una applicazione di tipo file sharing è necessario
individuare il peer con cui si vuole stabilire la chiamata localizzazione degli utenti on line a carico dei SuperPeer
agiscono come rely-router per il traffico generato da peer a monte di firewalls e NAT (60% degli utenti si trova a monte di un NAT)
Supporta funzionalità per il supporto di VOIP session a cui partecipano più peer
Algoritmi per il merging di diversi flussi di pacchetti voce
23IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2PTV: VIDEO STREAMING
File multimediali contenenti audio/video possono essere scaricati anche mediante i sistemi di file sharing, tuttavia il video viene prima scaricato (almeno in parte) sul peer e successivamente visualizzato (come un play back)
Limiti evidenti del modello client server dovuti alla alta richiesta di risorse computazionali per questo tipo di applicazioni
Video Streaming: trasferimento e visualizzazione in real time dello stream video cooperazione tra i peer per la distribuzione del contenuto (content
distribution networks) Bittorrent
bufferizzazione di un certo numero di video frames Sistemi commerciali: SopCast, PPlive, TVAnts...
24IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
CONTENT DISTRIBUTION NETWORKS
Un server pubblica un nuovo contenuto (esempio: nuova versione di un gioco, nuova release di un sistema operativo,...)
Modello client server: collo di bottiglia rappresentato dall’unico server centralizzato
Unicast
Router
Receiver Receiver
Router
Router
Receiver Receiver Receiver
Router
Sender
25IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Approcci P2P Ottenere un miglior bilanciamento nell’uso della banda di comunicazione,
utilizzando canali di trasmissione meno utilizzati Peer-to-Peer Content Distribution
Le richieste iniziali di files sono servite da un server centralizzato
Ulteriori richieste vengono inoltrate automaticamente ai peer che hanno già ricevuto e replicato, in precedenza, i files
Router
Sender
Router
Receiver/Sender
Receiver/Sender
Router
Receiver/Sender
Receiver/Sender
Receiver/Sender
Receiver/Sender
Receiver/Sender
26IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
27IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
28IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
Part3
Part3Part
2Part
2 Part3
Part3
Part1
Part1
Part2
Part2
Part3
Part3
29IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
Part3
Part3Part
2Part
2 Part3
Part3
Part1
Part1
Part1
Part1
Part1
Part1
Part2
Part2
Part3
Part3
30IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
Part3
Part3Part
2Part
2 Part3
Part3
Part1
Part1
Part1
Part1
Part2
Part2
Part1
Part1 Part
2Part
2
Part2
Part2
Part3
Part3
31IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
Part3
Part3Part
2Part
2 Part3
Part3
Part1
Part1
Part1
Part1
Part2
Part2 Part
3Part
3
Part1
Part1 Part
2Part
2
Part2
Part2
Part3
Part3
Part3
Part3
32IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P CONTENT DISTRIBUTION
Uso combinato del modello P2P e di quello client-server consente di ottimizzare gli accessi ad un server
Approccio segmentato (esempio:BitTorrent)
DocDoc
Part3
Part3Part
2Part
2 Part3
Part3
Part1
Part1
Part1
Part1
Part2
Part2 Part
3Part
3
Part1
Part1 Part
2Part
2
Part2
Part2
Part3
Part3
Part3
Part3
DocDoc
DocDoc
DocDoc
33IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Una P2P Storage Network è un cluster di computers connessi in rete che utilizza tutta la memoria resa disponibile dai peer per definire un servizio distribuito di memorizzazione
Esempi: PAST, Freenet, OceanStore, XtreemOS Directory Service Organizzazione:
Associazione peer-identificatori mediante funzioni hash Ogni peer offre una parte del proprio spazio di memorizzazione, o paga
una quota di denaro A seconda del suo contributo, ad ogni peer viene assegnato un volume
massimo di dati che possono essere aggiunti alla storage network Assegnazione documenti-identificatori mediante una funzione hash
calcolata sul nome o su parte del contenuto del file La memorizzazione e la ricerca di files nella rete è guidata dagli
identificatori associati dalla funzione hash a peers e files.
34IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Costruzione
1IDHash
1ID
4ID
25ID
3ID
17ID
10ID
8ID
35IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Costruzione
Hello ???
Hello ???1ID
Hash1ID
4ID
25ID
3ID
17ID
10ID
8ID
36IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Costruzione
3ID
25ID
4ID
Hello ???
Hello ???1ID
Hash1ID
4ID
25ID
3ID
17ID
10ID
8ID
37IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Costruzione
3ID
25ID
4ID
Hello ???
Hello ???1ID
Hash
neighbors3
4
25
1ID
4ID
25ID
3ID
17ID
10ID
8ID
38IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
39IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
40IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
41IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
42IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
43IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
44IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
45IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
46IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
11ID
47IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
11ID
48IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Memorizzazione di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
Hash11ID
11ID
11ID
11ID
11ID
49IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS
Ricerca di Documenti
1ID
4ID
25ID
3ID
17ID
10ID
8ID
34
25
11725
14
10
348
11017
1017
38
25
11ID
11ID
11IDrequestor: 1
50IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P STORAGE NETWORKS Realizzate come DHT (Distributed Hash Tables) Utilizzate per:
Realizzazione di un sistema di storage distribuito (Wuala) Memorizzazione distribuita dell'indice dei file condivisi
Rete KAD di Emule File condivisi memorizzati in una directory condivisa L'indice dei file (associazione nome file-peer che condividono i files)
viene memorizzato in una directory distribuita (storage network) memorizzata in una DHT (Kademlia)
File systems distribuiti
51IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
OVERLAY P2P Un protocollo P2P definisce l'insieme dei messaggi che i peer si scambiano, il
loro formato, la loro semantica Caratteristica comune a tutti i protocolli P2P:
identificazione dei peer mediante un identificatore unico, generalmente creato mediante l'applicazione di una funzione hash
i protocolli sono definiti a livello applicazione dello stack TCP/IP e definiscono una strategia di routing
Overlay Network: rete logica definita tra i peer a livello applicazione La rete definisce dei links logici tra i peer, che non corrispondono a
collegamenti fisici ad ogni link logico possono corrispondere
più hops fisici attraversamento di un insieme di routers
52IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
CLASSIFICAZIONE RISPETTO AL TIPO DI OVERLAY
Sistemi P2P non strutturati (Gnutella, Kazaa,…) Un nuovo peer si connette in modo casuale ad un certo numero di peer già
attivi all’interno del sistema
La rete costruita dinamicamente dai peers (overlay network) risultanon strutturata
Algoritmi di Ricerca di informazioni sulla rete: basati su directory centralizzato (Napster). flooding (Gnutella),
Costo della ricerca= lineare in N, dove N è il numero di nodi della rete
Problema: scalabilità.
53IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
OVERLAY NON STRUTTURATI
I peer interagiscono direttamente tra di loro senza l’intervento di un server centralizzato
Paradigma di interazione basato su una cooperazione decentralizzata, piuttosto che su coordinamento centralizzato
S
CC
CC
C
C
Client/Server
P P
P
P PP
PP P
Peer to Peer
54IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
OVERLAY NON STRUTTURATI IBRIDI
Per migliorare la performance del sistema, sono possibili soluzioni ibride Definizione dinamica di Superpeers che indicizzano le risorse dei peer Le risorse possono essere scambiate direttamente tra i peer
SP
PP
P
P
P
Peer to Peer Ibrido
SPSP
P
P
P
55IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
OVERLAY P2P STRUTTURATI
Sistemi P2P strutturati
La scelta dei vicini a cui un nuovo peer si deve collegare è effettuata in
base ad un determinato criterio
La rete dei peer (overlay network) risulta strutturata
obiettivo:garantire la scalabilità
La struttura della rete garantisce che la ricerca di una informazione
abbia complessità limitata (ad esempio O(log N)).
Complessità limitata anche nel caso di aggiunta di un nuovo peer, o
eliminazione di un peer
Utilizzo di distributed hash tables
56IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
CLASSIFICAZIONE OVERLAY Se si considerano gli overlay P2P per il file sharing, si può già parlare di
'generazioni' di sistemi P2P, per gli altri tipi di applicazioni è ancora prematuro Le diverse generazioni si riferiscono alle modalità con cui viene gestito
l'overlay e si con cui si indicizzano i dati Prima Generazione: Sistemi con punti di Centralizzazione
Un server centralizzato che coordina e distribuisce dei task ai peer Seti @home, Napster, Bittorrent,
Seconda generazione, Overlay non strutturati Peer to peer puro, nessun server
Gnutella, Kazaa, Skype (a parte la fase di autenticazione) Terza generazione, Overlay strutturati
Basati su DHT CAN, Chord, Pastry, Emule (Kademlia),...
57IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
PRIMA GENERAZIONE: SETI@home
SETI@Home: Search for Extraterrestrial Intelligence
Progetto di ricerca universitario (UC California, Berkeley) supportato anche da alcune industrie. Inizio: fine anni 90
Analisi delle emissioni radio ricevute dallo spazio, raccolte dal telescopio Arecibo, situato a PortoRico
Scopo: costruire un ‘supercomputer’ aggregando la potenza computazionale offerta da computers connessi in Internet, sfruttando i cicli di inattività
Costo ridotto di un fattore 100 rispetto all’acquisto di un super computer 200 milioni di dollari per l’acquisto di un supercomputer 30 TeraFlops Il progetto è costato meno di 1 milione di dollari
58IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
PRIMA GENERAZIONE: SETI@home
Utilizza un Data Server centralizzato ed un insieme di clients
Client = Screen Saver Program sviluppato per diverse piattaforme
Un unico data server distribuisce i dati Problema: scalabilità ed affidabiltà ridotte In certi periodi i client riescono a connettersi al server solo durante la notte Definizione di proxy servers: il proxy si connette al server centrale durante la notte e
distribuisce i dati durante il giorno
Alto rapporto computazione/comunicazione Ogni client si connette per un breve intervallo di tempo per ricevere i dati, effettua la
computazione (richiesta computazionale alta), invia i risulati Non c’e’ comunicazione tra i peers
59IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
PRIMA GENERAZIONE: SETI@home
In realtà basato su una architettura client server. I peer chiedono tasks da eseguire ad un server centralizzato non possono sottomettere task al server in realtà il progetto possiede delle caratteristiche P2P
gli utenti competono per ottenere crediti, cercando di produrre risultati più velocemente degli altri
gli utenti si raggruppano in 'team' per elaborare i segnali in maniera cooperativa
alcuni utenti 'barano' (cheating)Altri progetti dello stesso tipo Aggregazione' di un alto numero di risorse di calcolo'
Ricerca di numeri primi Einstein@home, Foding@home, ….. BOINC :Software open-source per il calcolo distribuito volontario
60IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
PRIMA GENERAZIONE: BITTORRENT
Concepito per il downlaod di grosse moli di dati Allo stato attuale è il protocollo che genera il maggior volume di traffico
Internet (secondo alcune statistiche >60%) Focus sul download parallelo di contenuti, piuttosto che su strategie sofisticate
di ricerca del contenuto I file vengono divisi in chunks per il download Do ut des: definizione di strategie per l'incentivazione della collaborazione Diverse strategie per la scelta dei pezzi di file da scaricare L'insieme dei peer che partecipano al download di un file (swarm) è coordinato
da un server (tracker) Tracker = punto di centralizzazione Le ultime versioni (trackerless) utilizzano una DHT
61IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SECONDA GENERAZIONE: GNUTELLA P2P puro ( o flat P2P): tutti i nodi hanno lo stesso ruolo e sono interconnessi
mediante un overlay non strutturato Goal: ricerca completamente decentralizzata di files Ogni nodo
Condivide alcuni files Riceve le query sottomesse dall'utente e le forwarda ai vicini Forwarda le query provenienti dai vicini Risponde alle query, analizzando se i file che ha messo in condivisione
soddisfano la query Esplora periodicamente la rete per conoscere eventuali nuovi nodi
Meccanismo di propagazione delle query = flooding Problema principale: bassa scalabilità dovuta all'alto numero di messaggi
scambiati sull'overlay
62IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
SECONDA GENERAZIONE: KAZAA
insieme a Napster, Bittorrent, Emule...uno dei sistemi per il file sharing più popolari...
caratteristica innovative: struttura gerarchica con superpeers i nodi hanno caratteristiche diverse
memoria CPU connettività uptime raggingibilità
si sfrutta l'eterogeneità dei peer per assegnare loro dei ruoli diversi nodi stabili e con buona risorse (calcolo, connettività) diventano superpeer Peer semplici: peer 'instabili', con poca potenza di calcolo, nattati
63IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
TERZA GENERAZIONE: OVERLAY STRUTTURATI
Distributed Hash Tables: Assegnamento di identificatori mediante funzioni hash ai peer ed ai dati Lo stesso spazio di identificatori per peer e dati Definizione di una funzione di mapping dati-peer Key based search:
Definizione di algoritmi di routing in cui ogni hop sull'overlay è guidato dal contenuto della chiave che si sta cercando
Diverse proposte sviluppate in ambito accademico CHORD, CAN, PASTRY,...
Alcuni sistemi di file sharing 'commerciali' utilizzano la DHT Kademlia sviluppata in ambito accademico
Rete KAD di Emule Trackerless Bittorrent
64IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P: VANTAGGI
Vantaggi per l'utente: offrire risorse computazionali 'in eccesso' (cicli idle di CPU, spazio di memoria inutilizzato, banda inutilizzata,...) in cambio di risorse/servizi/partecipazione a social networks,..
Vantaggi per la comunità self scaling property: la partecipazione di un numero sempre maggiore di
utenti/host incrementa in modo naturale le risorse del sistema e la sua capacità di servire un maggior numero di richieste
Vantaggio per il venditore: diminuzione di costo per il lancio di una nuova applicazione
client/server: richiede l'uso di una server farm con alta connettività sulla rete in modo da soddisfare le richieste di milioni di utenti
fault tolerance: la server farm deve essere replicata in diverse locazioni i server devono essere gestiti in modo da offrire un servizio 24*7
65IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
P2P: IL FUTURO Il successo di una applicazione P2P dipende in gran parte dalla definizione
di una 'massa critica' di utenti P2P application critical mass: Livello di partecipazione ad una applicazione P2P che consente alla applicazione stessa di 'auto-sostenersi' Nei primi sistemi P2P hanno giocato un ruola fondamentale per il raggiungimento della massa critica la novità dell'applicazione
File sharing: free content,ampia selezione di contenuti VoP2P: basso costo di chiamate internazionali, buona qualità di audio,... P2PTV: accesso ad una vasta gamma di programmi, possibiltà di accesso da ogni luogo (viaggi,....)
Il successo di nuove applicazioni P2P dipenderà oltre che da una buona ingegnerizzazione delle applicazioni,
dall'appealing della nuova applicazione dalla definizione di ragionevoli 'business model'
66IntroduzioneDipartimento di Informatica Università degli Studi di Pisa Laura Ricci
LE SFIDE SCIENTIFICHE
lo sviluppo di applicazioni P2P costituisce una vera e propria 'sfida' ed apre richiede la soluzione di diversi problemi nuovi
classiche metodologie per lo sviluppo di sistemi distribuiti “di vecchia generazione” non utilizzabili:
l'ordine di grandezza di un sistema P2P è diverso rispetto a quella dei sistemi classici (milioni di nodi vs. centinai di nodi)
algoritmi/tecniche classiche 'non scalano' su reti di questa dimensione il fallimento di uno dei nodi del sistema non costituisce più un evento raro,
bensì un fatto 'naturale' sistemi di queste dimensioni e con questo grado di dinamicità richiedono nuovi
strumenti algoritmi probabilistici analisi statistica di reti complesse teoria dei giochi: strategie per la cooperazione tra peers sviluppo di nuovi modelli computazionali