presentazione - Copia.pptx - Università degli Studi di Bari

Università degli Studi di Bari Corso di Laurea Magistrale in Informa9ca Sistemi Distribui9 Il sistema BitTorrent Docente S. Pizzu9lo Studente Bianca G. L. Petrelli Che cos’è BitTorrent? ü Ideato da Bram Cohen ü Si abbandona l’approccio one – to – one perché non riusciva a garan9re buone prestazioni ü Sistema di ﬁle sharing basato su un’architeGura peer – to – peer ü Suddivisione della risorsa in par9 più piccole, «piece» 2 I Componenti ü L’architeGura di BitTorrent si basa sulle componen9: q  .torrent: ﬁle contenente le informazioni necessarie per reperire la risorsa desiderata; q Tracker: coordina le aQvità tra i peer; q Peer: è colui che scarica un ﬁle, e che permeGe di scaricarlo. I peer si suddividono in Seed e Leecher 3 I Componenti .torrent ü  Announce: è una stringa ASCII codiﬁcante l’indirizzo URL del tracker; ü  Announce – list: è una lista di url alterna9vi rappresentan9 l’estensione del protocollo ü  Crea0on – date (opzionale): è la data di creazione del torrent, nel formato UNIX standard ü  Comment (opzionale): è il commento dell’autore del torrent codiﬁcato come stringa ASCII ü  Created – by (opzionale): con9ene il nome e la versione del programma che ha generato il ﬁle torrent ü  Encoding (opzionale): stringa nel formato di encoding usata per generare le par9 del dizionario info nel metaﬁle .torrent ü  Info: è un dizionario che descrive il ﬁle presente nel torrent, fornendo informazioni come il numero o la lunghezza dei pezzi e il nome del ﬁle. Un torrent può contenere anche delle soGo – cartelle e vari ﬁle, invece che uno solo. q Pieces: stringa di byte oGenuta come concatenazione di tuQ i ﬁngerprint da 20 byter SHA1, uno per ogni chunk q Pieces lenght q Private (opzionale): il campo è un intero. Se è seGato a “1”, il client deve pubblicare la sua presenta per prendere altri peer solo tramite i tracker esplicitamente descriQ nel ﬁle metainfo. Se il campo è seGato a “0” o non è presente, il client deve oGenere i peer in un altro modo. 4 I Componenti .torrent Gli elemen9 informa9vi del campo info aggiun9vi in caso di ﬁle singolo sono: ü  Name: è una stringa rappresentante il nome del ﬁle in formato ASCII ü  Lenght: è un intero rappresentante la dimensione del ﬁle in byte ü  Md5sum (opzionale): è una stringa esadecimale di 32 caraGeri corrispondente al MD5 del ﬁle. Non è usato in BitTorret del tuGo, ma è incluso in qualche programma per una maggiore compa9bilità. Gli elemen9 informa9vi del campo info in caso di archivio di ﬁle sono: ü  Name: è una stringa rappresentante il nome della directory proposta per memorizzare i ﬁles in formato ASCII ü  Files: è la lista dei ﬁle contenu9 nel Torrent dove ogni ﬁle è rappresentato per mezzo di un dizionario con la seguente struGura q Lenght: è un intero rappresentante la dimensione del ﬁle in bytes q Path: è la lista di stringhe che permeGe di ricostruire il percorso del ﬁle prendendo gli elemen9 nel loro ordine. q Md5(opzionale): è una stringa esadecimale di 32 caraGeri corrispondente al MD5 del ﬁle. Non è usato in BitTorret del tuGo, ma è incluso in qualche programma per una maggiore compa9bilità. 5 I Componenti Tracker ü Svolge il ruolo di «server» ü È l’unica componente centralizzata ma non è coinvolto nel trasferimento dei da9 q L’insieme dei peer che eﬀeGua il download dello stesso ﬁle prende il nome di «swarm» 6 I Componenti Tracker – le richieste ü info_hash: stringa di 20 byte oGenuta applicando la funzione hash SHA1 al campo info del Metainfo ﬁle; ü peer_id: iden9ﬁca9vo univoco del client generato in fase di startup; ü port: numero della porta su cui è in ascolto il client; ü uploaded: quan9tà di da9 spedi9 dall’invio di un messaggio di 9po started; ü downloaded: quan9tà di da9 scarica9 dall’invio di un messaggio di 9po started; ü leD: numero di byte che il client deve ancora scaricare; ü event: questo campo, se speciﬁcato, deve valere started, completed o stopped; ü ip: (opzionale) indirizzo IP della macchina su cui è aQvo il client. Viene usato se il client comunica con il tracker aGraverso un proxy server altrimen9 è omesso e l’indirizzo IP viene oGenuto direGamente dalla richiesta hGp; ü numwant: (opzionale) numero di peers che il client vuole ricevere dal tracker. Se non speciﬁcato tale numero è 9picamente 50; ü key: (opzionale) un iden9ﬁca9vo aggiun9vo non condiviso con gli altri uten9 che permeGe al client di iden9ﬁcarsi 7 I Componenti Tracker – le risposte ü failure reason: è un messaggio di errore che spiega perché la richiesta non viene processata. Se presente è l’unico campo previsto; ü warning message: (opzionale) messaggio simile al precedente. In questo caso viene no9ﬁcato l’errore ma il messaggio è comunque processato; ü min interval: (opzionale) intervallo minimo per una nuova richiesta; ü tracker id: stringa che il client deve spedire nella successiva richiesta. Se non è presente si usa quella spedita nella precedente; ü complete: numero di peers che possiedono l’intero ﬁle (seeders); ü incomplete: numero di peers che non possiedono l’intero ﬁle (leechers); ü peers: (dizionario) è una lista di dizionari ognuno dei quali è caraGerizzato da un iden9ﬁca9vo, un indirizzo IP e una porta; ü peers: (binario) invece di usare un dizionario si può usare una stringa binaria avente una dimensione mul9pla di 6 byte, dei quali, i primi 4 rappresentano l’indirizzo IP e gli ul9mi 2 il numero di porta; 8 I Componenti Peer ü Esistono due diﬀeren9 9pi di peer: q Seeder: possiede la copia completa del ﬁle q Leecher: possiede nessuna, una o solo alcune par9 del ﬁle di cui si vuole fare il download 9 Instaurazione delle connessioni ü Il client instaura una comunicazione con gli altri peer q U9lizza le porte TCP 6881 – 6999 ü Ogni peer decide se acceGare la richiesta o se «soﬀocarla» (choked) q Un peer decide di «soﬀocare» una richiesta in quanto ha un numero prestabilito di connessioni massime simultanee 10 Instaurazione delle connessioni ü Choked: indica se il client è “soﬀocato” dal peer remoto con cui sta comunicando. ü Interested: indica se il peer è interessato a uno o più piece possedu9 dal client. q Se il peer si trova in questo stato, inizierà a richiedere blocchi non appena sarà unchoked dal client. q La lista sarà del 9po: q Am_choking: il client sta “soﬀocando” il peer;Am_interested: il client è interessato ai contenu9 possedu9 dal peer q Peer_choking: il peer sta “soﬀocando” il client. All’instaurazione della connessione il client risulterà di default choked e not interested: •  Am_choking = 1 •  Am_interested=0 •  Peer_choking=1 •  Peer_interested=0 11 Messaggi e scambio di dati Handshake handshake:<pstrlen><pstr><reserved><info_hash><peer_id> ü  Pstrlen: lunghezza pstr in un singolo byte ü  Pstr: stringa che iden9ﬁca il protocollo ü  Reserved: 8 byte riserva9. Ogni bit può essere usato per modiﬁcare il comportamento del protocollo ü  Info_hash: 20 byte che rappresentano il valore hash SHA1 del campo info del metainfo ﬁle (è lo stesso campo presente sul tracker) ü  Peer_id: 20 byte che iden9ﬁcano univocamente il client (è lo stesso campo presente nelle richieste al tracker). ü  Colui che inizia la connessione trasmeGe il proprio handshake, mentre il peer dall’altro lato aGende se è in grado di servire torrent mul9pli simultaneamente e, non appena questo accade, deve rispondere. ü  La connessione può essere troncata nel caso in cui il campo info_hash contenga un valore errato, o se peer_id non corrisponde al valore aspeGato 12 Messaggi e scambio di dati Bi7ield ü  è opzionale e, nel caso in cui il client non possieda nessun piece, non è necessario spedirlo. Tale messaggio si presenta nella forma: biHield:<len=0001+X><id=5><biHield> ü  ha una lunghezza variabile e indica i pieces possedu9 dal peer che ha inviato il messaggio. ü  Completato lo scambio di bisield tra i peers in comunicazione, cominciano le richieste dei pieces mancan9 aGraverso messaggi di request 13 Messaggi e scambio di dati Request request:<len=0013><id=6><index><begin><length> ü  ha una lunghezza ﬁssa e nel suo payload troviamo le informazioni riguardan9 il piece richiesto. ü  Se un peer è in grado di esaudire una richiesta passa alla fase di upload del piece indicato in quest’ul9ma inviando un messaggio di 9po piece. Piece piece:<len=0009+X><id=7><index><begin><block> ü  ha una dimensione variabile che dipende da quella del blocco del piece (X) che è stato selezionato. 14 Messaggi e scambio di dati Have ü  Appena un piece è stato scaricato viene controllato tramite il valore hash e la sua ricezione è no9ﬁcata alla maggior parte dei peers connessi al client con l’invio di un messaggio di have avente lunghezza preﬁssata. have:<len=0005><id=4><piece index> Cancel ü  Se in seguito ad un par9colare avvenimento un client non è più interessato ad un blocco di cui aveva faGo richiesta invia un messaggio di cancel di dimensione ﬁssa: cancel:<len=0013><id=8><index><begin><length> Keep – alive keep-‐alive:<len=0000> ü I peers che non ricevono nessun messaggio entro un certo periodo di tempo possono abbaGere la connessione; i keep-‐alive devono essere quindi spedi9 per mantenere la connessione aQva se non sono sta9 spedi9 comandi per un dato lasso di tempo, 9picamente due minu9. 15 Algoritmi ü Piece download strategy q Strict Priority, q  Rarest First, q Random First, q Endgame Mode ü Choking e Op0mis0c Chocking ü An0snubbing 16 Algoritmi -‐ Piece download strategy Strict priority ü  Se si eﬀeGua la richiesta di un piece a un peer, tuGe le resta9 richieste saranno associate a quello stesso peer ü  Completamento più veloce del download Esempio: ü  Un ﬁle è cos9tuito da 8 blocchi. ü  Lo swarm si suppone che sia composto da due peers: il peer A che è un seed, e il peer B che è un leecher, e che possiede solo i pieces 2 e 3 comple9, e il primo blocco del piece 1. ü  Prima di poter richiedere blocchi appartenen9 a qualsiasi altro piece, il peer B dovrà completare il piece incompleto. 17 Algoritmi -‐ Piece download strategy Rarest First ü  Il peer sceglie come nuovo piece da scaricare quello con minore occorrenza nello «swarm» ü  Si alleggerisce il carico sul seeder ü  Il piece più raro si determina conservando le informazioni ricevute dagli altri peer presen9 nel biHield, e alla ricezione del messaggio have ü  Questa tecnica dovrebbe prevedere una selezione random dei piece più rari per non incorrere nel rischio che tuQ richiedano lo stesso piece. 18 Algoritmi -‐ Piece download strategy Random First ü  u9lizzato in alterna9va a Rarest First nel caso in cui si voglia iniziare il download di un ﬁle e il peer non è in possesso di nessun piece. ü  Si sceglie in modo random la prima parte e poi si applica il Rarest First, poiché altrimen9 l’operazione potrebbe rallentarsi notevolmente in quanto è più semplice che un piece raro sia in possesso di pochi peer. Endgame ü  U9le quando si sta per terminare il download del ﬁle ü  Per i piece mancan9 viene inviato una richiesta in broadcast e, ogni qualvolta che viene richiesta viene ricevuta, occorre inviare un messaggio in cui si indicano le par9 che non sono più di interesse. 19 Algoritmi -‐ Choking e Optimistic Chocking ü  Non è tecnicamente parte del protocollo BitTorrent, ma è necessario per una buona performance. ü  Ogni peer rende unchoked un numero ﬁssato di altri peer, di solito quaGro, che prendono il nome di downloaders. Il problema diventa scegliere quali peer rendere unchoked. ü  Le decisioni rela9ve a quali peer rendere unchoked sono basate streGamente sul tasso corrente di download. ü  I primi algoritmi di choking erano poco performan9 in quanto il valore della banda di connessione varia rapidamente non appena le risorse diventano disponibili o non lo sono più. ü  Per ovviare a questa problema9ca, i peer in BitTorrent ricalcolano chi vogliono soﬀocare ogni 10 secondi. Tale periodo di tempo è abbastanza lungo per eseguire nuovi trasferimen9. 20 Algoritmi -‐ Choking e Optimistic Chocking ü  Ogni 30 secondi (op0mis0c_unchoke_interval) viene eﬀeGuata un’ulteriore scelta deGa op0mis0c unchoking. ü  Il client riserverà una ulteriore parte della sua banda di upload ad un peer indipendentemente dal download rate che sperimenta nei suoi confron9. ü  Questo meccanismo permeGe al client di saggiare la bontà delle connessioni inu9lizzate alla ricerca di una migliore di quelle aGualmente in uso e fornisce ai peers appena entra9 a far parte dello swarm la possibilità di completare il prima possibile una parte del ﬁle. 21 Algoritmi -‐ Antisnubbing ü  Può accadere che il client venga “soﬀocato” da tuQ i peers da cui sta scaricando ü  In ques9 casi esso con9nuerà ad oGenere bassi download rate ﬁnché l’op9mis9c unchoking non gli permeGerà di trovare peers migliori. ü  Per mi9gare questo problema, un client che non riceve nessun piece, per più di un minuto, da un determinato peer soﬀoca subito la connessione assumendo di essere stato snobbato (snubbed) da quest’ul9mo e avvia un op0mis0c unchoking. ü  Il client potrebbe con9nuare comunque a fornire da9 al peer che lo ha snobbato se esso fosse il bersaglio dell’op0mis0c unchoking o nel caso in cui ricominciasse a ricevere da9 da quest’ul9mo. 22 Modellazione con le Reti di Petri Le Reti di Petri ü Modello astraGo e formale per rappresentare sistemi che esibiscono aQvità asincrone ü Si compone di q Un insieme di pos0 q Un insieme di transizioni q Un insieme di token ü Il comportamento di una PN è determinato dalla propagazione dei token 24 Modellazione di BitTorrent 25 BibliograAia •  Peer-‐to-‐peer networking with BitTorrent , Jahn Arne Johnsen, Lars Erik Karlsen ,Sebjørn Sæther Birkeland , Department of Telema9cs, NTNU. •  BitTorrent Session Characteris0cs and Models, David Erman Dragos Ilie Adrian Popescu, Dept. of Telecommunica9on Systems, Sweden •  BitTorrent, Davide Chiarella •  Modellizzazione del protocollo BitTorrent aWraverso il formalismo delle Abstract State Machines(ASM), Vito Astone •  Re0 di Petri (slide), Prof. A. Bianchi, Modelli per Sistemi Distribui9 Coopera9vi 26

Download Report