3.1 - Network Simulator v2 – NS2 Capitolo 3 BitTorrent in ns2

1

Capitolo 3

BitTorrent in ns2

3.1 - Network Simulator v2 – NS2

Il simulatore di reti utilizzato in questo lavoro di tesi è NS2 [17], un software nato nel 1989 come variante del simulatore REAL che, negli ultimi anni, è cambiato molto ed è migliorato notevolmente, tanto da essere riconosciuto oggi, a livello internazionale, come uno fra i migliori della sua categoria.

NS2 è un simulatore di reti di telecomunicazioni a pacchetto ad eventi discreti (event

driven). In un simulatore di questo tipo le variabili di stato del sistema cambiano valore

solo ad istanti discreti di tempo. Il cambiamento di stato del sistema prende il nome di evento. Tale evento non ha durata ed è caratterizzato da un istante di occorrenza. La condizione del sistema è rappresentata per mezzo di attività, contraddistinte da eventi di inizio e fine (l’inizio e la fine della trasmissione di un pacchetto sono eventi, mentre, la trasmissione stessa è un’attività).

NS2 è scritto interamente in C/C++ e utilizza un interprete Tcl/OTcl come interfaccia utente.

Il linguaggio OTcl è la versione Tcl orientata agli oggetti (Object Oriented) e rappresenta il linguaggio interpretato. Esso è un vero e proprio linguaggio di scripting adoperato sia per realizzare moduli nei quali non serve avere elevate velocità di esecuzione, sia come interfaccia ai moduli realizzati in C++. Esso viene normalmente utilizzato nella stesura degli script per descrivere tutte le operazioni necessarie a definire una simulazione. Tali script devono poter essere creati e modificati in maniera semplice e rapida.

Il C++ è un linguaggio compilato, con cui sono implementati in NS2 la maggior parte dei modelli degli oggetti di rete utilizzati durante le simulazioni. Esso ha lo svantaggio, rispetto al linguaggio interpretato, di essere più complesso ma in compenso risulta più efficiente in termini di velocità di calcolo.

Tra i moduli realizzati in OTcl e quelli realizzati in C++ esiste una corrispondenza uno a uno, nel senso che gli oggetti sono visibili e accessibili in entrambi i linguaggi, ma

2

ovviamente sono implementati solo in uno dei due. Il collegamento (linkage) tra le classi definite in C++ e le corrispondenti classi istanziate in OTcl si ottiene attraverso un insieme di funzioni di libreria chiamate Tool Command Language Class (TclCl). Queste librerie forniscono l’interfaccia necessaria per accedere alle funzioni interne dell’interprete OTcl.

Come accennato in precedenza, in NS2 la realtà è modellata come una successione di eventi: uno scheduler tiene traccia del tempo attuale di simulazione (ovviamente completamente incorrelato col tempo reale in cui si esegue il programma e con la sua durata di esecuzione), e della lista di eventi associati.

Appena lo scheduler determina l’esecuzione di un evento, lo ricerca, lo esegue e si prepara all’esecuzione dell’evento successivo: l’esecuzione di eventi contemporanei avviene in ordine di inserimento (questo perché il simulatore è un unico processo single

threaded e non può eseguire più eventi contemporaneamente). È ovvio che il tempo di

esecuzione non ha nulla a che vedere con il tempo di simulazione. L’unità di tempo usata nel simulatore è il secondo.

La struttura logica di NS2 è visualizzata in figura 3.1.

3

La figura 3.2 mostra una vista d’utente del Network Simulator:

Figura 3.2 - Vista d’utente dell’NS.

L’utilizzazione del simulatore prevede, come primo passo, la scrittura di uno script in linguaggio OTcl che deve contenere una schedulazione degli eventi (quando una sorgente deve iniziare o smettere di trasmettere, quando acquisire i parametri da analizzare, ecc.), la creazione della topologia della rete tramite gli oggetti OTcl presenti (classi e sottoclassi) e l’utilizzazione delle funzioni di libreria per la connessione degli oggetti (setup della rete).

Durante la simulazione, se specificato nello script OTcl, NS2 produce in uscita dei file che permettono di effettuare l’analisi prestazionale, oppure di ripercorrere su display l’andamento della simulazione, tramite il Network AniMator (NAM) o XGRAPH. L’utente solitamente sarà interessato solo alle simulazioni, quindi scriverà uno script

OTcl che definisce lo scenario di rete da simulare. Tale script viene interpretato da NS2,

che produce come output i file contenenti i risultati della simulazione, soggetti ad eventuale post processing. Se invece si è interessati a modificare o aggiungere nuovi oggetti, bisogna scrivere e compilare in C++.

La descrizione degli oggetti della rete in NS2 è strutturata a strati sul modello della pila protocollare ISO/OSI.

4

Come mostrato in figura 3.3 si identificano tre livelli:

• Application

• Transport

• Livelli inferiori (network, data-link, fisico, IP…)

Figura 3.3 – Struttura a strati di NS2

Lo strato più alto rappresenta le applicazioni che generano i dati. Nello strato intermedio troviamo gli Agent che si occupano di simulare il livello di trasporto della pila protocollare delle reti IP, rappresentando le terminazioni dove i pacchetti a livello di rete vengono generati per la trasmissione e distrutti dopo la ricezione. Infine, nel livello inferiore, troviamo gli oggetti Node e Link che trasportano i pacchetti IP tra i diversi nodi della rete.

Dal momento che nel nostro studio siamo interessati alla simulazione di reti WLAN ad infrastruttura analizzeremo nel prossimo paragrafo la loro implementazione nel simulatore usato.

3.1.1 – WLAN in NS2

Nel modello delle WLAN presente in NS2, un ruolo fondamentale è ricoperto dall’oggetto MobileNode che aggiunge il supporto alla mobilità e all’uso del mezzo wireless all’oggetto Node.

Come mostrato in figura 3.3, NS2 è organizzato secondo una struttura modulare in cui ciascun oggetto esegue le proprie elaborazioni e poi ne comunica i risultati agli oggetti adiacenti. In particolare un nodo wireless ha differenti oggetti che simulano

5

indipendentemente i tre livelli più bassi del modello ISO-OSI: Link Layer (LL), Media

Access Control (MAC) e Physical Layer (PHY). Un apposito modello è schematizzato in

figura 3.4.

Figura 3.4 - Connettività fra i nodi in una LAN in NS2

Un pacchetto generato dai livelli superiori viene accodato nel LL, inoltrato al MAC e, infine, trasmesso sul PHY, il quale è costituito dall’oggetto Channel.

Il Link Layer è responsabile della simulazione dei protocolli data link, mentre il MAC si occupa di:

1.definire le regole per accedere al canale fisico; 2.implementare meccanismi di controllo quali:

• carrier sense;

• collision detection;

6

Va osservato che se i nodi sono in visibilità radio possono accedere a tutti i pacchetti trasmessi sullo stesso canale. Sarà compito del MAC accettare e trasferire ai livelli superiori solo i pacchetti destinati al nodo.

Il canale fisico è implementato dall’oggetto Channel, che provvede a simulare la propagazione e a far giungere in istanti opportuni i pacchetti ai diversi nodi in ascolto sullo stesso mezzo.

Il pacchetto ricevuto si trova eventualmente ad effettuare il percorso inverso e a risalire i diversi layer, giungendo fino al livello applicativo del nodo destinatario.

Ognuno di questi oggetti è implementato da una classe C++, che fornisce membri pubblici per interfacciarsi con gli altri oggetti. Quando viene creato un nuovo nodo, viene creata una nuova istanza per ciascuna delle classi opportune; l’unica eccezione è costituita dall’oggetto PHY che, per sua stessa natura, è unico ed è messo in comunicazione con tutti i nodi presenti nello scenario di simulazione.

7

Nel modello di nodo wireless rappresentato in figura 3.5 distinguiamo i seguenti oggetti:

• Address Resolution Protocol (ARP): ha il compito di tradurre gli indirizzi IP in

indirizzi MAC generando, nel caso di indirizzi incogniti, dei pacchetti broadcast;

• Interface Queue (IFq): implementa la coda dei pacchetti da trasmettere fornendo

particolari precedenze ai pacchetti generati dai protocolli di routing (priority

queue);

• Routing Agent (RTagent): implementa il protocollo di routing che può essere

scelto fra DSDV, TORA, AODV o DSR;

• Src/Sink: è il generatore o il destinatario ultimo dei pacchetti di dati; esso è

costituito solitamente da un protocollo di trasporto (TCP o UDP) e dalla particolare applicazione; vi possono essere molte istanze diverse di oggetti

Src/Sink in ciascun nodo, gestite opportunamente dai demux di indirizzo e di

porta;

• LL: ha il compito di accodare in IFq i pacchetti ricevuti da RTagent dopo aver

interrogato l’ARP (pacchetti uscenti), oppure di fornire ai demux i pacchetti ricevuti dal MAC (pacchetti entranti);

Per ciascun nodo wireless, NS2 prevede la possibilità di movimento all’ interno di una certa area geografica rettangolare (espressa in m2), e quindi la simulazione della distanza, della velocità di movimento e della visibilità radio in funzione dei livelli di potenza di trasmissione delle diverse stazioni. In particolare, l’oggetto Network

Interface (NetIF) simula l’interfaccia hardware di un nodo.

Il Radio Propagation Model ha il compito di calcolare il range di comunicazione (area entro la quale un ricevitore è raggiungibile). Al fine di calcolare la potenza ricevuta da ciascun nodo fa uso di tre principali modelli di propagazione:

1. modello Free Space:

2. modello di riflessione Two-ray Ground; 3. modello Shadowing;

8

Nel modello Free Space si assume che ci un percorso diretto tra il trasmettitore e il ricevitore. Tale modello utilizza la formula di attenuazione di Friss (attenuazione proporzionale al quadrato della distanza) per calcolare la potenza del segnale ricevuto nello spazio libero ad una distanza d dal trasmettitore.

Nel modello Two-ray ground si considera oltre al raggio diretto anche quello riflesso (considerando la terra come un piano perfettamente riflettente). E’ stato dimostrato [18] che questo modello fornisce una predizione più accurata rispetto al modello precedente al crescere della distanza.

I due modelli precedenti predicono la potenza ricevuta come una funzione deterministica della distanza e rappresentano il range di comunicazione come un cerchio ideale. In realtà, la potenza ricevuta ad una certa distanza è una variabile aleatoria a causa degli effetti della propagazione multipath (fading) e quindi i modelli precedenti ne predicono il valore medio. Il modello Shadowing si occupa di:

• predire la potenza media ad una distanza d (path loss);

• calcolare la varianza della potenza media ricevuta;

Con questo modello si aggiungono proprietà statistiche al range di comunicazione. Un nodo che è in prossimità del limite dell’area di comunicazione può essere raggiunto solamente con una certa probabilità.

Per simulare uno scenario di rete wireless in NS2 bisogna quindi definire, tramite uno script OTcl, una serie di parametri per configurare gli oggetti MobileNode. Una possibile configurazione è la seguente:

#---# #--- Parametri Nodi Mobili ---# #---# set opt(chan) Channel/WirelessChannel; # Tipo di canale

set opt(prop) Propagation/TwoRayGround ; # Modello di propagazione set opt(netif) Phy/WirelessPhy ; # Tipo di interfaccia set opt(mac) Mac/802_11 ; # Tipo di MAC set opt(ifq) Queue/DropTail/PriQueue # Tipologia di coda set opt(ll) LL ; # Link Layer set opt(ant) Antenna/OmniAntenna ; # Modello di antenna set opt(ifqlen) 100 ; # Numero di pacchetti in IFQ set opt(nn) 100 ; # Numero di nodi mobili set opt(adhocRouting) DSDV ; # Protocollo di routing

9

3.2 – Approcci allo studio dell’architettura BitTorrent

Il crescente successo riscosso dal protocollo BitTorrent ha suscitato grande interesse nell’ambito della ricerca. In letteratura si possono trovare quattro principali tipi di approccio allo studio delle sue performance:

• studio analitico [19];

• simulazione a livello applicazione [20];

• studio basato su dati estratti da una rete reale [21];

• simulazione a livello pacchetto;

Mentre i modelli analitici sono basati su assunzioni semplificate, le simulazioni a livello applicazione tengono conto solamente della banda del link d’accesso e modellano il trasferimento dati come un flusso. Queste simulazioni, di conseguenza, sovrastimano le performance del BitTorrent trascurandone le caratteristiche a livello pacchetto. Gli studi basati su esperienze reali, dal loro canto, soffrono la mancata conoscenza delle proprietà di tutti i peers della rete.

A causa della loro elevata complessità, le simulazioni a livello pacchetto delle reti P2P sono state condotte raramente, ma nel caso del BitTorrent si è osservato che, generalmente, il numero dei peers attivi è minore rispetto alle altre reti P2P poiché solamente un unico file è condiviso per ogni overlay network. Osservando le statistiche, si è notato che i file più popolari portano alla creazione di overlay costituite da più di 10000 peers ma tale numero si riduce fino a 1000, o anche meno, nel caso di contenuti meno richiesti. Ciò ha permesso di simulare una rete BitTorrent di media dimensione (1000 peers) anche a livello di pacchetto. Il vantaggio di condurre un’analisi di questo tipo, oltre a quello di permettere la validazione di modelli di simulazione semplificati, è la possibilità di valutare l’influenza che hanno i livelli inferiori della pila protocollare

ISO/OSI sulle performance dell’applicazione BitTorrent. Dal momento che nelle reti

P2P i dati sono trasferiti per mezzo del protocollo di trasporto TCP la simulazione a livello pacchetto può essere condotta, inoltre, per tener conto dell’esatto comportamento di tale protocollo.

10

Il primo codice di simulazione di tipo packet level del protocollo BitTorrent è stato sviluppato da Kolja Eger1 e dai suoi collaboratori per la versione 2.29 del simulatore NS2. Tale codice permette di simulare la condivisione di un file sia a livello di flusso (Flow level) che a livello di pacchetto (Packet level) grazie all’introduzione di quattro classi principali (BitTorrentApp, BitTorrentTracker, BitTorrentConnection, e

BitTorrentData) e di altre due derivate (BitTorrentAppFlowlevel e

BitTorrentTrackerFlowlevel). Come sarà più chiaro in seguito, tali classi svolgono le

funzioni del livello applicativo e del livello di trasporto dell’architettura a strati di NS2 (fig 3.3).

Va osservato che sono state apportate piccole modifiche anche alle classi Agent, Node e

Tcp-full del simulatore. I dettagli di tali modifiche saranno presentati successivamente.

Tramite la simulazione packet level lo studio condotto da Eger [22] ha mostrato l’influenza che ha il protocollo TCP sull’algoritmo di unchoking del BitTorrent. Il throughput del TCP infatti dipende, fra le altre cose, dal RTT sperimentato tra i peers della rete e, più precisamente, esso diminuisce all’aumentare di quest’ultimo. Di conseguenza è ragionevole pensare che un client “sblocchi” i peers che hanno un ritardo

end-to-end minore. Ciò significa che le performance di un peer non dipendono

esclusivamente dalla sua capacità di upload ma anche dall’RTT che sperimenta.

3.3 – Simulazione BitTorrent in NS2

Dal momento che il nostro studio è principalmente incentrato sulle prestazioni delle reti BitTorrent in presenza di utenti wireless si è scelto di utilizzare il codice sopra menzionato applicandolo alla versione del simulatore NS2 da noi utilizzata (2.33) e ad un opportuno scenario di rete wireless. Si è scelto di effettuare uno studio basato su simulazioni di tipo packet level poiché, ai fini dell’analisi, si è interessati al calcolo di parametri di rete quali il throughput di determinati collegamenti.

1

11

3.3.1 – Assunzioni semplificative

Il codice presentato nasce con l’intento di stimare le differenze tra una simulazione a livello applicativo e una a livello di pacchetto di una rete P2P di tipo BitTorrent senza però l’esigenza di implementarne una specifica versione. Di conseguenza nella sua stesura si è tenuto conto di alcune assunzioni semplificative alleggerendo alcune funzionalità del protocollo BitTorrent e omettendone completamente delle altre.

L’implementazione studiata, ad esempio, non prevede la presenza del file .torrent né la verifica dell’integrità dei dati tramite funzioni hash. Il protocollo HTTP del tracker non è implementato e tutti i dati generati da quest’ultimo non sono trasmessi sulla rete ma vengono forniti ai peers tramite funzioni interne alla classe BitTorrentApp. Questa semplificazione è stata adottata poiché si è principalmente interessati all’efficienza nel trasferimento dei dati tra i peers.

Ogni client simulato esegue l’algoritmo base di unchoking del protocollo mentre le modalità anti-snubbing e end-game sono state trascurate. La modalità super-seeding invece è stata implementata poiché essa migliora in maniera considerevole le performance del sistema in determinate condizioni.

Va considerato, inoltre, che l’implementazione del BitTorrent è modulare, quindi, gli algoritmi di selezione dei peers e dei pieces possono essere sostituiti permettendo un semplice confronto tra versioni diverse.

3.3.2 – Script OTcl

Come già accennato in precedenza per poter effettuare il nostro studio di simulazione tramite NS2 è necessario compilare uno script OTcl che sarà interpretato dal simulatore. In primo luogo viene fatta un’istanza alla classe Simulator e si creano i file che saranno utilizzati per la registrazione degli eventi durante la simulazione e successivamente per l’elaborazione dei risultati.

In secondo luogo verrà definito lo scenario di simulazione il cui dettaglio è presentato nel capitolo successivo.

12

A questo punto devono essere definite le applicazioni BitTorrent ma per poterlo fare vi è prima la necessità di:

1. fare un’istanza alla classe BitTorrentTracker;

2. settare un insieme di variabili, proprie dell’applicazione BitTorrent, che saranno utilizzate nel corso della simulazione. Nel dettaglio i parametri che devono essere settati sono:

• Numero di peer che costituiscono lo swarm;

• Seme del generatore di numeri casuali;

• Numero di unchokes e di risposte massime fornite dal tracker;

• Metodologia di abbandono dello swarm;

• Intervallo di ripetizione dell’algoritmo di unchoking;

• Attivazione o meno della modalità super-seeding;

Infine si devono schedulare gli istanti in cui le applicazioni BitTorrent hanno inizio e fine.

3.4 – Analisi del codice BitTorrent

Affinché risultino chiare le dinamiche del codice e in assenza in letteratura di una guida dettagliata il primo passo compiuto nel nostro studio è stato quello di analizzare nel dettaglio le funzionalità delle quattro classi introdotte.

Va notato che nel codice analizzato l’autore ha definito con il termine chunk la sottoparte in cui è suddiviso il file nota nelle specifiche originali del protocollo come

piece. Nel seguito della trattazione sarà utilizzato il termine chunk per favorire

13

3.4.1 – Scenario di rete semplificato

Per comprendere al meglio il funzionamento delle quattro classi illustrate in seguito, in figura 3.6 introduciamo uno scenario di rete semplificato. La figura mostra uno swarm (insieme di tutti i nodi che partecipano alla condivisione del file e su cui è in esecuzione l’applicazione BitTorrent) costituito da sette nodi e un tracker a cui essi fanno riferimento.

Sebbene tutti i nodi dello swarm svolgano le stesse funzioni considereremo soggetto della seguente trattazione solo uno di essi a cui ci riferiremo con il termine di clientBT. Attribuiremo, invece, ai restanti nodi il termine più generico peerBT.

Figura 3.6 – Scenario semplificato

3.4.2 - BitTorrentTracker

Tramite questa classe si gestiscono tutte le comunicazioni con il tracker della rete. Il costruttore di tale classe è il seguente:

14

Come si può notare dalle righe del codice, una nuova istanza di tale classe prevede di fornire in ingresso le due variabili file_size e chunk_size che rappresentano rispettivamente la dimensione del file condiviso dallo swarm e quella del singolo piece che lo costituisce.

I valori delle due variabili fornite in ingresso sono assegnati rispettivamente alle variabili S_F e S_C e vengono utilizzati per calcolare il numero di chunk (N_C) di cui è composto il file. La variabile N_P, inizialmente impostata al valore zero, serve per tenere conto dei nodi che risultano registrati al tracker.

L’oggetto creato istanziando questa classe sarà utilizzato come parametro di ingresso per ogni nuova istanza alla classe BitTorrentApp.

Tale classe ha due compiti principali:

1. gestire le registrazioni (o cancellazioni) dei nodi al tracker;

2. inviare a coloro che ne fanno richiesta, un sottoinsieme, ordinato in maniera random, dei nodi che compongono lo swarm.

15

La funzione reg_peer riceve in ingresso un puntatore ad un oggetto di tipo Node che rappresenta il generico peerBT che richiede la registrazione e lo accoda in un vettore (peer_ids). Tale vettore contiene tutti i puntatori relativi ai nodi attualmente registrati. La funzione, inoltre, aggiorna la variabile (N_P) che tiene conto del numero dei nodi registrati.

La funzione get_peer_set restituisce un vettore (return_set) contenente

req_num_of_peers elementi del vettore peer_ids riordinati in maniera random. Nel caso

in cui il numero di nodi registrati al tracker, al momento della richiesta, sia minore del valore di default esso fornirà gli identificativi di tutti quelli posseduti.

16

Figura 3.7 – Comunicazione con il tracker

3.4.3 - BitTorrentConnection

Questa classe è stata introdotta per consentire al simulatore la creazione e la gestione dei dati relativi alle connessioni TCP instaurate, inclusi gli agenti e consente, inoltre, di connettere l’applicazione BitTorrent ad essi.

Inoltre tale classe ha il compito di creare un oggetto DataBufList vuoto che rappresenta una coda di tipo FIFO. In questa coda sono memorizzati i dati inviati (oggetti di tipo

DataBuf) attraverso una connessione, fino a quando, essi non saranno completamente

ricevuti dal destinatario il quale provvederà a cancellarli.

17

I parametri di ingresso necessari alla creazione di un oggetto BitTorrentConnection sono:

• puntatore al nodo sorgente della connessione (src_node);

• puntatore all’oggetto BitTorrentApp creato sul destinatario (dst);

• puntatore all’oggetto BitTorrentApp creato sulla sorgente (src);

• puntatore all’oggetto Agent creato sul destinatario (dst_tcp);

• intero che identifica univocamente la connessione creata sulla sorgente (conID);

• intero che identifica univocamente la connessione creata sul destinatario (dst_conID);

• puntatore all’oggetto BitTorrentConnection creato sul destinatario (dst_con_);

Nel costruttore tali parametri vengono assegnati ad alcune variabili interne che mantengono lo stesso significato fisico. Va notato, inoltre, come sia stata introdotta una nuova variabile dst_address a cui si è associato il valore dell’indirizzo IP del nodo destinatario richiamando il metodo address() della classe Node.

18

Successivamente viene creata un’istanza alla classe Tcl che permetterà, tramite le sue funzione eval ed evalf, di creare un agente FullTcp di tipo NewReno. Tale agente verrà connesso al nodo che ha generato l’istanza alla classe BitTorrentConnection e all’applicazione BitTorrent che è in esecuzione su di esso.

Si può osservare come venga richiamato il metodo attachApp della classe Agent. Tale metodo costituisce una delle modifiche apportata al codice originale e permette di connettere l’agente creato all’applicazione mantenendo una corrispondenza anche con l’oggetto BitTorrentConnection a cui si riferisce.

3.4.4 - BitTorrentData

Tale classe permette di creare un pacchetto BitTorrent comprensivo di tutti gli header. Una nuova istanza di questa classe prevede di fornire in ingresso:

• intero che specifica il particolare tipo di pacchetto;

• puntatore al nodo che ha generato il pacchetto;

Il pacchetto generato è costituito da un insieme di variabili che ne costituiscono l’intestazione e da altre che, invece, ne rappresentano il payload. Inizialmente esse sono tutte settate a valori di default e successivamente, a seconda del pacchetto che si vuole inviare, si aggiorneranno solamente alcuni campi specifici.

19

La variabile length ricopre un ruolo fondamentale. Essa rappresenta la lunghezza reale di un pacchetto BitTorrent data. Assumerà valori diversi a seconda del tipo di pacchetto che si vuole generare. Indichiamo nel dettaglio i tipi di pacchetti disponibili con il relativo valore in byte della variabile length:

• HANDSHAKE: 68; • CHOKE: 5; • UCHOKE: 5; • INTERESTED: 5; • NOTINTERESTED: 5; • HAVE: 9; • BITFIELD:5; • REQUEST: 17; • PIECE: 13; • CANCEL: 17; • KEEP_ALIVE: 4;

20

3.4.5 - BitTorrentApp

La classe BitTorrentApp costituisce il cuore del codice implementato. Essa comprende un insieme di funzioni, di strutture dati e timers che permettono di simulare il reale comportamento dei clients BitTorrent in esecuzione sui nodi appartenenti allo swarm. Per ogni nodo dello swarm è generata un’istanza di questa classe tramite script OTcl. Il costruttore della classe è il seguente e i parametri che vengono forniti come input sono:

• seed_init: variabile che può assumere i valori 1 ed 0 indicando in questo modo

se il peer_BT interessato si comporta da seed o da leecher;

• capacity: valore della capacità del link di upload;

• global: puntatore ad un oggetto BitTorrentTracker, precedentemente istanziato;

• here: puntatore all’oggetto Node su cui si vuole eseguire l’applicazione;

La prima operazione compiuta consiste nel richiamare la funzione setBTApp della classe

Node. Tale funzione riceve in ingresso il puntatore all’oggetto BitTorrentApp che si sta

creando e lo assegna ad una variabile interna. Tale puntatore potrà essere richiamato successivamente tramite la funzione getBTApp. Queste due funzioni sono state aggiunte al codice originale della classe Node per poter permettere un’associazione tra l’applicazione e il nodo su cui essa è in esecuzione.

In secondo luogo verranno creati tre vettori aventi una dimensione pari al valore della variabile N_C (numero di chunk) dell’oggetto tracker. Di conseguenza l’elemento del vettore di posizione i si riferirà al chunk i-esimo. I tre vettori creati sono:

• chunk_set: vettore che indica se il chunk i-esimo è posseduto (1) o meno (0) dal

nodo;

• download: vettore che indica il numero di byte scaricati per ogni determinato

chunk;

• requested: vettore che indica il numero di byte richiesti per ogni determinato

21

Si osserva che se il nodo è un seed il vettore chunk_set è costituito da soli 1, viceversa da soli 0. Gli altri due vettori sono, in entrambi i casi, inizializzati a 0. Sempre nel caso in cui il nodo sia un seed verrà inizializzato un altro vettore, avente, ancora, una dimensione pari a N_C elementi tutti settati a 0: super_seeding_chunk_set. Tale vettore sarà utilizzato dal codice per implementare la modalità super-seeding.

22

Nella parte di codice sottostante si assegnano i valori di default ad alcune variabili usate nel corso dell’implementazione. Tra esse citiamo:

• act_cons: numero di connessioni attive;

• opt_unchoke_counter: intervallo di ripetizione dell’optimistic unchoking;

• start_time: istante di avvio dell’applicazione BitTorrent;

• stop_time: istante di chiusura dell’applicazione BitTorrent;

• first_chunk_time: istante in cui si completa il download del primo chunk;

• download_finished: istante in cui si completa il download dell’intero file.

Infine si può notare la creazione di tre timer differenti:

• choking_timer_;

• tracker_request_timer_;

• leaving_timer_;

Tali timer servono a gestire rispettivamente l’algoritmo di unchoking, le richieste al tracker e l’abbandono della rete.

23

Introduciamo adesso la struttura dati peer_list_entry che ricopre un ruolo fondamentale nell’esecuzione della simulazione. Il clientBT possiede una struttura di questo tipo per ogni peerBT registrato al tracker, a cui si potrà successivamente connettere. Tali strutture sono memorizzate tutte all’interno di un vettore detto peer_set.

24

Tra le variabili definite di particolare importanza sono:

• connected: indica lo stato della connessione tra il clientBT e lo specifico peerBT.

Può assumere i seguenti valori: -1 il nodo non è connesso; 0 il nodo ha già richiesto l’instaurazione di una connessione; 1 il nodo risulta già connesso;

• x_up e x_down: indicano i rate di upload e download sperimentati dal clientBT

con il relativo peerBT;

• informazioni di stato: variabili necessarie all’implementazione dell’algoritmo di

unchoking;

• informazioni di upload e download: sono costituite dai vettori di richieste

my_requests e peer_requests i quali rappresentano rispettivamente le richieste

fatte dal clientBT al peerBT considerato, e quelle fatte, invece, da quest’ultimo al

clientBT;

Lo studio dei metodi della classe BitTorrentApp è stato affrontato distinguendo cinque principali fasi:

1. Fase iniziale;

2. Creazione e gestione delle connessioni TCP; 3. Scambio e gestione dei messaggi dati; 4. Implementazione algoritmi;

5. Fase finale;

3.4.5.1 – Fase iniziale

In questa sezione analizzeremo i metodi della classe che permettono di implementare la comunicazione con il tracker e che, a partire dalle informazioni ottenute da esso, consentono al clientBT di costruirsi una lista aggiornata dei peerBT che compongono lo swarm.

25

in essa si aggiorna la variabile start_time con il valore del clock di sistema e si setta a true la variabile running che serve ad indicare se l’applicazione è in esecuzione o meno. All’interno della funzione viene, inoltre, richiamata la funzione reg_peer della classe

BitTorrentTracker, che, come abbiamo visto, simula la registrazione del clientBT al

tracker di riferimento.

Infine viene schedulato all’istante 0 il tracker_request_timer, alla scadenza del quale viene richiamata la funzione tracker_request:

attraverso tale funzione, se non è stato ancora raggiunto il numero massimo di connessioni possibili, si richiama la funzione get_ids_from_tracker. La funzione

get_ids_from_tracker, invocando la funzione get_peer_set della classe

BitTorrentTracker, fornisce una lista dei peerBT attualmente registrati. Il clientBT

26 peer_set. In caso negativo, richiamerà la funzione make_new_peer_list_entry per

crearla.

La funzione, inoltre, rischedula all’istante REREQUEST_INTERVAL le future richieste al tracker che permetteranno al clientBT di mantenere aggiornato il suo peer_set.

Viene richiamata infine la funzione check_connections che sarà analizzata in dettaglio nella sezione successiva.

In figura 3.8 è schematizzata la situazione attuale, dal punto di vista del clientBT.

Figura 3.8 – Fase iniziale

3.4.5.2 – Creazione e gestione connessioni

In questa sezione, a partire dalla funzione check_connections precedentemente introdotta, analizzeremo i metodi della classe che permettono di simulare la creazione delle connessioni TCP tra il clientBT e i nodi dello swarm.

Il clientBT possiede un vettore conList_ i cui elementi sono costituiti da oggetti

BitTorrentConnection. Tali oggetti, come precedentemente visto, rappresentano le

27

Nella funzione check_connections, per prima cosa, si controlla se la dimensione di tale vettore supera il massimo numero di connessioni che un nodo può instaurare (max_initiate). Se ciò non accade si procede ad instaurare una connessione con i peerBT del vettore peer_set che risultano non connessi (connected=-1).

La creazione delle connessioni è realizzata per mezzo di tre principali funzioni tra loro dipendenti:

• connect;

• connect_step_2;

28

La funzione connect riceve in ingresso un puntatore ad un oggetto Node (node_dst) che rappresenta uno dei peerBT a cui il clientBT vuole connettersi e un oggetto di tipo

BitTorrentData (msg).

La prima operazione che si compie è quella di ricavare, per mezzo della funzione

getBTApp, il puntatore all’oggetto BitTorrentApp (dst) che rappresenta l’applicazione in

esecuzione sul peerBT.

In secondo luogo si crea la connessione su clientBT (sorgente) istanziando la classe

BitTorrentConnection. Alcune variabili necessarie alla sua realizzazione assumeranno,

in questa prima fase, valori di default dal momento che la connessione sul peerBT (destinatario) non è stata ancora creata.

Nella figura 3.9 mostriamo lo stato attuale della creazione della connessione tra il clientBT e un generico peerBT.

29

Figura 3.9 – Creazione connessione sulla sorgente

A questo punto si deve creare una connessione sul destinatario correlata a quella appena realizzata. Per far ciò si richiama la funzione connect_step_2 dell’applicazione che è in esecuzione sul destinatario fornendogli in ingresso l’identificativo della connessione e l’agente creato sulla sorgente.

Dal momento che tale funzione è stata richiamata dall’applicazione che è in esecuzione su peerBT, quest’ultimo ragionerà come se, idealmente, fosse la sorgente della connessione che si appresta a creare, anche se sappiamo che, in realtà, esso rappresenta il destinatario.

30

Nella figura 3.10 è illustrato quanto detto precedentemente evidenziando le dipendenze che hanno le due connessioni create.

Figura 3.10 – Creazione connessione sul destinatario

Non rimane che aggiornare la connessione creata su clientBT con i parametri relativi a quella creata su peerBT. Ciò si realizza per mezzo della funzione connect_step_3 che, inoltre, provvederà a connettere tra loro gli agenti delle rispettive connessioni. La situazione finale si presenta come in figura 3.11.

31

3.4.5.3 – Scambio e gestione dati

Instaurata la connessione TCP viene invocata la funzione send ogni qualvolta si vuole inviare un dato BitTorrent fornendo l’identificativo della connessione e il messaggio dati da inviare:

Inizialmente si ricava il puntatore all’oggetto BitTorrentConnection sfruttando l’identificativo della connessione e si effettuano dei controlli per verificarne l’esistenza. Nella rimanente parte vengono eseguite le seguenti operazioni:

1. i dati vengono memorizzati nel buffer della sorgente;

2. si richiama il metodo sendmsg della classe Agent per inviare la lunghezza del messaggio;

32

Alla ricezione di un nuovo pacchetto l’agente connesso al destinatario richiama la funzione recv dell’applicazione a cui è connesso, fornendo l’identificativo dell’oggetto

33

All’interno di questa funzione si possono notare le seguenti variabili :

• curdata: oggetto di tipo DataBuf che rappresenta i dati correnti al ricevitore;

• curbytes: intero che rappresenta i byte di curdata ricevuti fino a questo istante;

• nbytes: byte del messaggio correntemente ricevuto;

Alla variabile curdata si assegna un nuovo elemento estratto dal buffer (DataBufList) del mittente e se, rispetto alla sua lunghezza, la somma delle variabili nbytes e curbytes è :

• uguale: è stato ricevuto esattamente un messaggio; tale messaggio viene gestito richiamando handle_recv_msg; si resettano le variabili nbytes e curbytes; si cancella il dato appena gestito (curdata);

• minore: è stato ricevuto meno di un messaggio e, quindi, si aggiorna la variabile

curbytes con il valore di quella nbytes;

• maggiore: è stato ricevuto più di un messaggio. Si passa alla gestione del messaggio completo e si aggiorna la variabile nbytes con il numero di bytes in eccesso (bytes del messaggio successivo).

Come si è accennato in precedenza, la gestione dei messaggi ricevuti è affidata alla funzione handle_recv_msg la quale:

• aggiorna la variabile dei byte ricevuti aggiungendo la lunghezza del dato in ingresso;

• seleziona il peerBT di peer_set che ha inviato il dato e assegna alla sua variabile

last_msg_recv l’istante attuale di clock;

• gestisce il messaggio direttamente o richiamando specifiche funzioni a seconda del tipo di messaggio ricevuto.

34

3.4.5.4 – Algoritmi

In questa sezione analizzeremo i metodi della classe che permettono di implementare i principali algoritmi eseguiti dall’applicazione BitTorrent al fine di favorire la diffusione di un file all’interno dello swarm:

• unchoking algorithm;

• piece selection;

Il primo di questi è l’algoritmo di unchoking che permette al clientBT di decidere quali

peerBT “sbloccare” (unchoke) o “soffocare” (choke). In questa fase, giocano un ruolo

di fondamentale importanza le quattro variabili della struttura peer_list_entry che forniscono le informazioni di stato. Sono quattro variabili booleane che, se assumono il valore true, hanno il seguente significato:

• am_choking: clientBT sta soffocando peerBT;

• am_interested: clientBT è interessato alle parti di file possedute da peerBT;

• peer_choking: peerBT sta soffocando clientBT;

• peer_interested: peerBT è interessato alle parti di file possedute da clientBT;

L’algoritmo di unchoking è simulato per mezzo della funzione check_choking la quale è invocata allo scadere del choking_timer, ogni choking_interval secondi.

La funzione per prima cosa controlla se la lunghezza del vettore peer_set di clientBT è minore del numero di peerBT che si vogliono sbloccare, tale valore è specificato dalla variabile unchokes. Se così fosse, andrà a “sbloccare” per mezzo della funzione

choke_peer tutti quei peerBT che sta al momento soffocando (am_choking=true) e che

35

Se la condizione di prima non è verificata la funzione andrà a creare, per ogni peerBT del peer_set che risulta connesso a clientBT (connected=1) e interessato ad esso (peer_interested=true), una nuova struttura di tipo service_info. Tale struttura rappresenta uno dei possibili peerBT che clientBT sceglierà di “sbloccare” ed è caratterizzata dai seguenti attributi:

• id: identificativo del determinato peerBT;

• index: indice numerico;

• service_rate: variabile di confronto che rappresenta il rate sperimentato da clientBT con lo specifico peerBT;

Va notato come la variabile service_rate sia aggiornata con il numero di byte inviati o scaricati a seconda che clientBT sia seed o leecher. Tutte queste strutture vengono, infine, accodate in un vettore di “candidati” (unchoke_cand).

36

A questo punto se la lunghezza di tale vettore è maggiore del numero di peerBT che si vogliono “sbloccare” (quantità pari ad unchokes-1 poiché la variabile tiene conto anche del peerBT che risulta essere l’optmistic_unchoking) allora:

• si riordinano, in ordine crescente e in funzione della variabile service_rate, gli elementi del vettore unchoke_cand attraverso la classe CompareService;

• si eliminano tutti gli elementi del vettore eccetto gli ultimi unchokes-1 che risultano essere i “migliori” in termini di service_rate;

• si “sbloccano” per mezzo della funzione unchoke_peer i peerBT di peer_set che risultano essere i “candidati” superstiti e sono “soffocati” da clientBT (am_choking=true);

• se uno dei “candidati” superstiti risulta essere anche l’optmistic_unchoking si setterà al valore di default la variabile opt_unchoke_pid; ciò vuol dire che, al momento, non è stato settato l’optimistic_uchoking;

37

• si “soffocano” per mezzo della funzione choke_peer tutti i peerBT che risultano “sbloccati” (am_choking=false) e che non sono risultati i “migliori”;

• si aggiornano gli elementi dei vettori uploaded_bytes e downloaded_bytes di ogni peerBT; tali vettori memorizzano il numero di byte che sono stati inviati o scaricati in un certo numero (ROLLING_AVERAGE) di esecuzioni successive dell’algoritmo di unchoking. Il primo elemento del vettore viene impostato al valore 0 in modo tale che all’esecuzione successiva dell’algoritmo conterrà il numero di bytes scaricati durante gli ultimi unchoking_interval secondi. Le componenti successive, invece, assumono il valore dell’intervallo precedente. Si opera in questo modo per rendere più selettiva la scelta dei “migliori”;

38

Figura 3.12 – Aggiornamento downloaded_bytes[]

• infine si elimina il vettore dei “candidati”.

L’algoritmo di optmistic_unchoking è, invece, implementato ogni

OPTIMISTIC_UNCHOKE_INTERVAL (multiplo del choking_interval). Tale algoritmo

39

Il secondo algoritmo presentato è quello di chunk_selection. Tale algoritmo, come visto nella teoria, consiste nello scegliere quale chunk di un determinato file andare a richiedere di volta in volta.

Sono state implementate due diverse strategie:

1. Strict Priority / Random first 2. Rarest First

Strict Priority: fa uso di due algoritmi di selezione diversi a seconda che si sia iniziato o

meno il download di un primo chunk che compone il file.

Come si può notare dalla porzione di codice, verrà richiesto il chunk posseduto da un certo peerBT di cui si sono già scaricati alcuni byte. Così facendo si facilita il completamento di un intero chunk che verrà reso disponibile per l’upload.

Se invece si deve decidere per la prima volta quale particolare chunk del file richiedere (first_chunk_selection=true) si adotterà un algoritmo di tipo Random First:

40

per mezzo del quale verrà selezionato il chunk posseduto da un particolare peerBT in maniera random.

Rarest First: è utilizzata se la variabile choking_algorithm è impostata al valore BITTORRENT_WITH_PURE_RAREST_FIRST. In questo caso clientBT andrà a

selezionare il chunk che risulterà essere posseduto dal numero minore di peerBT. La funzione si avvale di due vettori:

• occurence: vettore di N_C elementi che memorizza il numero di possessori di

ogni chunk;

• rarest_piece: vettore che memorizza i chunk aventi il numero di occorrenze

minore all’interno dello swarm;

Le occorrenze dei singoli chunk sono calcolate per mezzo del vettore chunk_set di ogni

41

3.4.5.5 – Fase finale

Analizziamo, infine, i metodi della classe che vengono invocati per terminare la simulazione.

Al completamento del download viene richiamata la funzione compute_leaving_time che permette tramite la variabile leave_option di implementare tre diverse modalità di abbandono della rete P2P:

42

• abbandono secondo una distribuzione esponenziale di valor medio pari al valore assunto da leave_option;

• la rete non viene abbandonata (leave_option<0) finché non è specificatamente richiesto;

In qualsiasi caso la rete viene abbandonata richiamando alla scadenza del leaving_timer la funzione stop che si occuperà di:

• cancellare la registrazione al tracker;

• cancellare tutti i timeout pendenti;

• cancellare il vettore peer_set;