Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 20.Sistemi distribuiti peer-to-peer - Parte prima


Sommario

  • Motivazioni e caratteristiche
  • Requisiti
  • Classificazione
  • Esempi:
    • Napster
    • Gnutella
    • Chord, Pastry

Motivazioni

Abilitare condivisone di dati e risorse su vasta scala

  • scambio di informazioni
  • cicli di CPU
  • spazio sul disco

Eliminare amministrazione centralizzata.
exploit resources available at the edges of the Internet” [Shirky 2000].

Sistemi distribuiti peer-to-peer (P2P)

Un sistema peer-to-peer (P2P) è un sistema distribuito nel quale i nodi hanno simili responsabilità e capacità funzionali.
Non vi è centralizzazione di attività in specifici nodi e la cooperazione tra i nodi avviene mediante interazioni tra pari (peers).
Il modello P2P trova tipicamente applicazione in sistemi di condivisione di risorse (file, cicli di CPU, documenti multimediali, …).
Ogni nodo contribuisce alla gestione delle risorse globali
utilizza i servizi degli altri nodi e fornisce loro “in cambio” analoghi servizi.
Es.: è possibile per un nodo “scaricare” un file da un altro nodo, a condizione di mettere successivamente a disposizione lo stesso file, ovvero altre risorse locali.

Peer-to-Peer vs Client-Server

Architettura Client-Server

  • Approccio centralizzato
  • Risorse poste nei server
  • Localizzazione e gestione semplificate
  • Limiti di scalabilità e affidabilità

Architettura Peer-to-Peer

  • Approccio distribuito
  • Risorse condivise dai peer
  • Richiede algoritmi per la localizzazione e gestione delle risorse
  • Consente scalabilità e affidabilità

Requisiti funzionali

  • Semplificare la realizzazione di servizi distribuiti.
  • I vari client devono poter individuare e comunicare con i fornitori del servizio.
  • Possibilità di aggiungere e rimuovere servizi.
  • Possibilità di aggiungere e rimuovere host.
  • Trasparenza al tipo di risorsa utilizzata.

Requisiti non funzionali

  • Scalabilità, per sfruttare tutti gli host.
  • Load balancing, da cui dipendono le prestazioni.
  • Ottimizzazione delle interazioni tra pari, migliorando il placement delle risorse.
  • Availability, sebbene un servizio possa essere offerto da host che si connettono e disconnettono in maniera non controllabile nè predicibile.
  • Sicurezza, garantendo privatezza e integrità delle informazioni.
  • Anonimità e sollevamento dalle responsabilità di chi possiede e condivide dei dati.

Possibili applicazioni

  • File sharing system
  • File storage system
  • Distributed file system
  • Redundant storage
  • Chat service
  • Distributed computation

Ciclo di vita

Boot: un’applicazione appena avviata intende far parte del sistema ottenendo informazioni per connettersi agli altri membri del sistema P2P.
Lookup: un’applicazione intende acquisire una risorsa (ad esempio un file), pertanto ricerca chi dei peer del sistema detiene la risorsa di interesse.
Resource Sharing: un’applicazione contatta un peer identificato nella fase di lookup per acquisire una risorsa e effettua lo scambio dati.

Soluzioni architetturali per boot e lookup

Centralizzato: esiste un server centrale a cui ogni peer richiede informazioni di boot e lookup.

Federato: esiste un server per ogni gruppo di peer, e i server sono interconnessi per garantire consistenza dei dati gestiti.

Distribuito: non esiste un server dedicato, ma i dati sono distribuiti tra i peer e sono ottenuti applicando appositi algoritmi decentralizzati.


Classificazione

P2P puro

  • le fasi di boot, lookup e sharing sono P2P

P2P

  • le fasi di lookup e sharing sono P2P
  • la fase di boot utilizza dei SERVER (centralizzati o federati)

P2P Ibrido

  • la fase di sharing è P2P
  • la fase di boot utilizza dei SERVER (centralizzati o federati)
  • nella fase di lookup vengono usati peer particolari (server federati)

Topologia

In base alla topologia della rete, i sistemi P2P sono classificati in:
Strutturati: presenza di una policy globale per la topologia della rete, placement degli oggetti e routing.

  • Maggiore efficienza di ricerca (in termini di garanzie, tempo, numero di messaggi);
  • Complesse strutture dati per memorizzare lo stato.

Non Strutturati: i peer non sono interconnessi secondo una precisa struttura; la topologia della rete è ignota.

  • Sono capaci di autoorganizzarsi e di tollerare fallimenti.
  • Meno efficienti (nessuna garanzia, tempi non stimabili, problemi di scalabilità).

Lookup in reti non strutturate

Expanded ring search: la ricerca viene effettuata inviando più messaggi con time-to-live crescente.
Random walks: vengono utilizzati messaggi che seguono percorsi diversi (scelti in maniera casuale) per fare discovery della rete.
Gossiping: le richieste vengono inoltrate a un vicino (con una certa probabilità) e da questi ad un altro e così via.

Evoluzione sistemi P2P


Napster

Sistema per lo sharing di file musicali lanciato nel giugno 1999.
Nel 2000, 50 milioni di utenti hanno scaricato il software per utilizzare Napster.
Picco di traffico di circa 7 TB in un giorno.
Servizio disattivato nel luglio 2001 per infrazione della legge sui diritti d’autore.
Soluzione con lookup centralizzata.
Utilizza la località della rete: per un client-peer diventerà server-peer il nodo a meno hop di distanza.
Così si evita anche che il primo a rendere disponibile un file diventi hot spot per esso.

Napster


Napster

Napster fu prova della possibilità di creare grossi sistemi costituiti da computer degli utenti di internet.

Gnutella 0.4

Viene lanciato nel 2000.
Fase di boot centralizzata: un Server (gnutellahost.com) viene usato dai nodi per il boot.
Fase di lookup distribuita: le richieste di ricerca vengono propagate con tecniche di flooding.

Gnutella 0.4

La rete non ha una specifica topologia:

  • i nodi sono connessi secondo un grafo casuale
  • ciascuno mantiene una lista degli identificativi dei vicini, che riceve a conclusione la fase di boot.

Per eseguire il lookup:

  • il nodo invia una query a tutti i vicini, i quali inoltrano la richiesta ai propri vicini se non dispongono dell’informazione cercata
  • il messaggio si propaga all’interno del sistema fino a raggiungere un nodo che detiene l’informazione, che viene inoltrata al richiedente.

Gnutella 0.4

Le prestazioni (es. tempo di ricerca di un file) peggiorano all’aumentare del numero dei nodi.
I messaggi possono circolare nel sistema indefinitamente, ripassando per nodi già visitati precedentemente.
Il mittente della query potrebbe ricevere più risposte (da più nodi che hanno il file richiesto).

Ogni nodo mantiene la lista di query già valutate.
Ogni query ha associato un TTL, che viene decrementato ad ogni ricezione, cosicché quando il suo valore è nullo la query viene scartata.

Scalabilità

La scalabilità di un protocollo é direttamente legata all’efficienza dell’algoritmo usato per il lookup.
Due obiettivi:

  1. minimizzare il numero di messaggi necessari per fare lookup
  2. minimizzare, per ogni nodo, le informazioni relative agli altri nodi.

Gnutella 0.6

I peer sono distinti in:

  • foglie
  • ultrapeer (nodi con risorse aggiuntive).

Ogni foglia è connessa ad alcuni (max 3) ultrapeer.
Gli ultrapeer sono connessi tra loro (almeno 32).
Il lookup è realizzato attraverso il Query Routing Protocol (QRP).

Gnutella 0.6

Ciascun nodo produce una Query Routing Table (QRT) con indici (hash values) dei file posseduti.
La QRT viene inviata agli ultrapeer associati.
Ciascun ultrapeer genera la propria QRT come unione di quella relativa ai propri file e delle QRT ricevute.

Un nodo foglia invia una richiesta ad un ultrapeer per volta ed attende per un certo tempo risposta prima di contattare un altro ultrapeer.

Ogni query contiene l’indirizzo di rete del primo ultrapeer contattato dal nodo foglia.
In tal modo chi ha il file contatta direttamente quest’ultimo evitando di ripercorrere a ritroso tutto il path.

Gnutella 0.6


BitTorrent

BitTorrent è una soluzione P2P di seconda generazione per file sharing.
Un server mantiene .torrent files che contengono meta-informazioni sui file da scaricare.
Un tracker tiene traccia di tutti i peer che detengono un dato file.
Un downloader contatta periodicamente il tracker per aggiornare le sue informazioni e ricevere la lista di peer che posseggono il file in download, così da contattarli.


BitTorrent


BitTorrent

Quale frammento del file viene richiesto dal downloader?

Inizialmente un peer richiede frammenti scelti a caso (Random First Policy), quando ne sono stati scaricati almeno 4, si passa ad eseguire il Rarest First Algorithm.
Ogni peer mantiene una peer list col numero di peer aventi ogni frammento (RepID). Gli identificativi dei frammenti con il minore RepID sono memorizzati nella rarest piece list, da cui a caso viene scelto il frammento da scaricare.
Quando un blocco di un frammento è stato scaricato, anche gli altri saranno richiesti con altissima priorità (Strict Priority Policy).

Overlay Network

Per migliorare l’efficienza delle operazioni di lookup è possibile considerare una rete (overlay network) costruita al di sopra del protocollo IP che interconnette i nodi del sistema P2P.
Si ottiene così una policy globale per topologia della rete, placement degli oggetti e routing che rende il sistema strutturato.
I nodi rappresentano applicazioni interconnesse per mezzo di link virtuali o logici, ognuno dei quali corrisponde a uno o più link fisici nella rete sottostante.
Un protocollo di Overlay Routing viene utilizzato per localizzare nodi ed oggetti.

Overlay Routing – Funzionalità

Inastradamento delle richieste verso gli host che posseggono una replica dell’oggetto richiesto.
Aggiunta di un oggetto al servizio.
Eliminazione di un oggetto.
Aggiunta di un nodo.
Che si assumerà alcune delle responsabilità di altri nodi.
Eliminazione di un nodo.

IP Routing vs. Overlay Routing


Distributed Hash Table (DHT)

I sistemi P2P strutturati fanno uso di Distributed Hash Table (DHT) per associare agli identificatori globali unici dei file (Globally Unique IDentifiers – GUID) la loro locazione.
I GUID sono generati con funzioni hash.

DHT: funzionamento di base

Ad 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.
La principale operazione che un sistema DHT deve fornire è lookup(key), la quale restituisce l’identità del responsabile di una determinata chiave.

DHT: funzionamento di base

Tutti i nodi del sistema condividono una tabella hash.
Come identificare il responsabile di una data chiave?

Nodo per oggetto con GUID=4?


DHT: Scalabilità


I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design, V ed., 2011 (Cap. X, da 10.1 a 10.5, eccetto 10.5.2).

I. Stoica et al., “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93