Giunti a questo punto, con due meccanismi adattivi sviluppati e funzionanti che collegano il processo di determinazione dei free rider a caratteristiche proprie dei nodi o dei messaggi da recapita- re, potrebbe essere interessante studiare cosa succede in presenza contemporanea di entrambi. Questo capitolo della trattazione sarà quindi dedicato allo sviluppo di un terzo meccanismo che ha come scopo quello di produrre nuove soglie probabilistiche adattive dipendenti sia dal TTL del messaggio in procinto di essere spedito che dal numero di vicini del nodo mittente.
5.1 Definizione del meccanismo adattivo
A seguito dei risultati raggiunti nei capitoli 3 e 4, sviluppare un meccanismo adattivo che tenga in considerazione sia l’attributo di time-to-live del messaggio da inviare sia il degree del nodo mittente non è un compito complesso. Ancora più intuitiva risulta essere la posizione nel codice nella quale la nuova versione di lunes_set_freeriding() dovrà essere richiamata. I due meccanismi visti finora sono stati implementati all’interno di funzioni richiamate entrambe esattamente nello stesso punto del codice, cioè all’interno di lunes_real_forward(), immediatamente prima della chiamata a execute_ping(). Ha senso che il nuovo lunes_set_freeriding() per il meccanismo adattivo ibrido sia richiamato sempre in quel punto, stavolta passando tre argomenti invece di due: un riferimento al nodo destinatario, il TTL rimanente del messaggio che deve essere inoltrato ed il numero di vicini del nodo mittente.
Il lavoro di implementazione vero e proprio si riduce in pratica all’operare una fusione tra i due algoritmi preesistenti in maniera che non si crei conflitto tra loro. Nel meccanismo adattivo di- pendente da degree (algoritmo 8, capitolo 4), la nuova soglia di probabilità di incontrare un free rider è calcolata come l’inverso del degree elevato ad una potenza pari alla probabilità impostata dall’uten- te, tranne per due valori speciali di degree (0 e 1) dove si presume che il nodo all’altra estremità del vertice non sia mai un free rider. Nel meccanismo adattivo dipendente da TTL (algoritmo 6, capitolo 3), il valore di TTL viene in tutti i casi utilizzato come base per calcolare un fattore moltiplicativo con il quale giungere alla nuova soglia di probabilità adattiva. La soluzione proposta in questa trattazione è riportata nell’algoritmo 9.
3-4) che troverà comunque un utilizzo qualunque sia il degree del nodo. In seguito si aprirà un’istru- zione condizionale riservata ai casi speciali di degree (riga 5) nella quale la soglia adattiva sarà calco- lata con il solo apporto del fattore moltiplicativo (riga 6) e la determinazione del comportamento da free rider sarà effettuata con il solito sistema della comparazione (riga 7) tra soglia e numero casuale generato per l’occorrenza (riga 2). Per tutti gli altri valori di degree sarà invece calcolata una prima soglia adattiva (riga 13) come l’inverso dell’elevamento a potenza che abbiamo già visto nell’algorit- mo 8 e poi una seconda moltiplicando la prima per il fattore dipendente dal TTL (riga 14). Il numero così ottenuto è quello effettivamente utilizzato per il confronto con il numero casuale (riga 15). L’o- perazione di confronto presenta, come nell’algoritmo 8, un segno di maggiore uguale data la nostra intenzione di studiare overlay network dove la popolazione di free rider è maggiormente concentrata al centro del grafo.
Elementi: il nodo (node) destinatario di un messaggio passato come argomento a lunes_set_freeri-
ding(), la variabile d’ambiente environment_threshold che esprime la probabilità impostata dall’uten- te che un nodo sia un free rider, il degree del nodo mittente, cioè il numero di vicini dei quali il nodo esso è a conoscenza, il ttl del messaggio che sta per essere ricevuto da node ed il valore massimo del TTL di un generico messaggio (max_ttl).
1: if environment_threshold > 0 then
2: freerider ← Generate_random_double(0, 1) 3: delta ← ( max_ttl - ttl ) / max_ttl
4: factor ← 1 - delta
5: if degree = 0 or degree = 1 then
6: adaptive_threshold ← environment_threshold * factor 7: if freerider <= adaptive_threshold then
8: node è un freerider
9: else
10: node non è un freerider 11: end if
12: else
13: adaptive_threshold ← 1 / degreeenvironment_threshold
14: adaptive_threshold_2 ← adaptive_threshold * factor 15: if freerider >= adaptive_threshold_2 then
16: node è un free rider 17: else
18: node non è un free rider 19: end if
20: end if
21: end if
Rispetto al meccanismo adattivo dipendente solo dal degree, non sono presenti casi nei quali l’algoritmo prevede che un nodo non sia un free rider qualunque sia il valore della variabile d’am- biente impostata dall’utente (FREERIDER). Invece, considerando il range del fattore moltiplicativo derivante dal TTL, per degree del nodo pari a 0 o 1 la probabilità di incontrare free rider all’altro capo dei collegamenti è sempre minore o uguale al valore di FREERIDER. Per quanto riguarda tutti
Algoritmo 9 Meccanismo di determinazione dei free rider a soglia di probabilità adattiva
i valori di degree diversi da 0 e 1, il meccanismo di determinazione della nuova soglia di probabilità è effettivamente ibrido, poiché sfrutta entrambe le operazioni matematiche sulle quali si basano gli algoritmi 6 e 8. In base a questo, la soglia risultante sarà sempre inferiore o uguale alla medesima cal- colata seguendo l’algoritmo 8 e questo comporta che in genere ci sia maggiore probabilità che il mes- saggio da inviare venga recapitato ad un free rider. Si rimanda alle tabelle 1-9 riportate nel capitolo 4.1 come riferimenti per avere un’idea generale dei valori di soglia adattiva risultato dell’operazione matematica in riga 13.
Nella fase di test che ci apprestiamo ad iniziare, vedremo le prestazioni di questo nuovo mec- canismo adattivo ibrido a confronto con quelle dei due meccanismi di partenza.
5.2 Fase di simulazione
A differenza delle immagini riportate nei capitoli 3 e 4, i grafici rapporto di copertura/overhe- ad ratio presenti in questa sezione riportano tre insiemi di dati invece di due: in blu l’andamento delle performance del meccanismo adattivo dipendente dal time-to-live del messaggio, in verde il corri- spettivo riferito al meccanismo dipendente dal degree del nodo e la successione di asterischi rossi rappresentano le prestazioni del meccanismo ibrido per probabilità di disseminazione da 1% a 100%. Il caso di studio (topologia di grafo e protocollo di disseminazione) è ovviamente lo stesso dei capitoli precedenti.
Ciò che salta immediatamente all’occhio scorrendo le figure da 5.1 a 5.9 è il fatto che i risul- tati dei test sul meccanismo ibrido si adagiano su curve simil-logaritmiche che ricalcano fedelmente, al netto di scostamenti nell’ordine di grandezza di un errore di arrotondamento, le curve verdi. Per ogni valore della variabile di soglia di probabilità stabile che è stato preso in considerazione per le simulazioni, i risultati del meccanismo ibrido sono in tutto e per tutto assimilabili a quelli prodotti dal meccanismo adattivo dipendente dal degree. L’unica vera discriminante tra i due sistemi è il rapporto di copertura massimo (e di conseguenza l’overhead ratio massimo) che il meccanismo ibrido consen- te di raggiungere per probabilità di disseminazione del 100%.
Per valori di FREERIDER compresi tra 0,1 e 0,4, la copertura massima raggiunta in media alla fine di una simulazione in cui si sia sfruttato il meccanismo adattivo ibrido (che chiameremo
mch) è assimilabile o persino lievemente superiore a quella per il meccanismo adattivo dipendente
dal degree (mcd), con [ mch - mcd ] che si matiene su valori assoluti comunque estremamente ridotti [ -0,002 -0,035 +0,114 +0,023 ]. Passata questa soglia, [ mch - mcd ] si mantiene stabilmente su valori negativi e in diminuzione fino a FREERIDER=0,7 [ -1,112 -2,064 -3,193 ]. Passata questa ulteriore soglia, il valore assoluto di questa differenza cala [ -2,08 -1,475 ], ma il rapporto [ mch / mcd ] continua a diminuire [ 91,6% 89,4% ], a fronte di un [ 92,8% ] per FREERIDER=0,7.
Per FREERIDER=0,3 e FREERIDER=0,4 è possibile anche osservare come questi valori di copertura marginalmente migliori sono ottenuti con un minore overhead ratio rispetto al meccanismo dipendente da degree. La diminuzione dell’overhead ratio è un fenomeno che comincia a diventare veramente percepibile in figura 5.3 ed è presente da lì in poi per ogni valore della variabile d’ambien- te sul quale siano state condotte simulazioni: la differenza tra orh (overhead ratio del meccanismo ibrido) e ord (overhead ratio del meccanismo adattivo dipendente da degree) rimane infatti negativa fino alla figura 5.9. [ orh - ord ] aumenta in valore assoluto fino a FREERIDER=0,5 compreso per poi
dente, il fatto che questa differenza cresca in valore assoluto fino a FREERIDER=0,5 per poi calare è bilanciata dal fatto che il rapporto [ orh / ord ] continui invece a crescere con l’aumentare del valore di FREERIDER. In figura 5.5, dove la differenza è massima in valore assoluto, il rapporto ci dice che orh è il [ 93,6% ] di ord. In figura 5.9, dove la differenza è poco più di un decimo della corrispettiva nell’esempio precedente, orh è l’[ 86,5% ] di ord.
Immagine 5.1 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,1.
Immagine 5.2 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,2.
Immagine 5.3 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,3.
Immagine 5.4 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,4.
Immagine 5.5 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,5.
Immagine 5.6 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,6.
Immagine 5.7 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,7.
Immagine 5.8 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,8.
Immagine 5.9 Confronto tra meccanismo dipendente da degree, meccanismo dipendente da TTL e meccanismo ibrido degree/TTL (con dettaglio), FREERIDER=0,9.
5.3 Interpretazione dei risultati
Spiegare il motivo per cui gli insiemi di dati prodotti dalle simulazioni dove si è usato il meccanismo adattivo ibrido ricalchino così fedelmente le curve verdi del meccanismo dipendente da degree è piuttosto semplice. L’algoritmo 9 rappresenta sì una commistione degli algoritmi riportati nei capitoli 3 e 4, ma l’impianto generale rispecchia maggiormente quella dell’algoritmo 8, imper- niato com’è sull’istruzione condizionale che valuta il modo di procedere in base al degree del nodo mittente. Il criterio di adattività basato sul time-to-live consiste invece nella generazione e successivo uso di un fattore moltiplicativo in congiunzione con la soglia di probabilità stabile senza alcun tipo di discriminazione. L’algoritmo definitivo risulta quindi essere a tutti gli effetti una riedizione dell’algo- ritmo 8 in cui le differenze per quanto riguarda le soglie di probabilità adattive generate non riescono ad essere sostanziali.
La fase di start-up, il momento della simulazione nella quale un nodo non è ancora “consape- vole” del proprio degree, è anche il momento nel quale i nodi cominciano a scambiarsi i primi mes- saggi, che pertanto avranno ancora TTL massimo. Un messaggio appena generato incontra un free rider all’altro capo della connessione che sta percorrendo solo se il numero causale estratto è 0, dal momento che il fattore moltiplicativo associato a tale situazione è 0, che annulla a sua volta la soglia di probabilità adattiva. Nel momento in cui i nodi hanno cognizione di un solo vicino poiché hanno ricevuto un solo messaggio (quindi degree = 1), i messaggi inviati incontrano pochi free rider deter- minati con il meccanismo ibrido, considerato che il TTL è ancora sufficientemente alto da provocare un notevole riduzione della soglia di probabilità adattiva. Nel caso dei nodi effettivamente con un solo vicino, come già spiegato nel capitolo 4.2, non importa se questi siano free rider o meno dal momento che per regola non possono disseminare i messaggi ricevuti. In questo elenco di casi, quindi, la situa- zione tra un algoritmo e l’altro subisce poche o nessuna variazione.
Per tutti gli altri valori di degree del nodo mittente, la prima soglia adattiva calcolata come l’inverso del degree elevato alla soglia di probabilità stabile viene moltiplicata per il fattore moltipli- cativo derivato dal TTL ed essendo quest’ultimo sempre compreso tra 0 e 1, la seconda soglia adat- tiva risultato di questa operazione aritmetica risulta sempre minore della prima. Non potrà nemmeno rimanere la stessa perché per avere un fattore moltiplicativo pari a 1 è necessario che il TTL corrente sià nullo ed in quel caso il messaggio viene automaticamente eliminato dal sistema. A causa del segno maggiore presente nell’istruzione condizionale alla riga 15 dell’algoritmo, la probabilità di incontrare un free rider (con conseguente decadimento del messaggio che non sarà più ritrasmesso) risulterà più elevata e questo causa la diminuzione dell’overhead ratio, percepibile soprattutto a partire dal batch di simulazioni con FREERIDER impostato a 0,3.
Per quanto riguarda il marginale miglioramento delle prestazioni di copertura per alcuni valori di overhead ratio (figure 5.3-5.4), una possibile motivazione dietro questo comportamento, al di là di errori di arrotondamento, potrebbe essere l’efficienza delle cache. Per via della presenza di un mag- gior numero di free rider nel network, viene consegnato un minor numero di messaggi e le cache im- plementate in ciascun nodo sono in grado di operare con un’efficienza lievemente superiore. [xxviii] Questo comporta meno messaggi duplicati in circolazione per la rete e perciò una copertura migliore per un dato valore di overhead ratio.
Il paradigma client-server può rivelarsi inadeguato in situazioni nelle quali deve confrontarsi con un massiccio carico di messaggi scambiati ed un numero di clienti altamente dinamico ed è in situazioni come queste che il paradigma peer-to-peer dimostra il suo valore garantendo efficienza, robustezza e scalabilità. Il grande successo a partire dai primi anni 2000 dei sistemi di file-sharing, una presenza oggi quasi irrinunciabile nella vita di tutti i giorni per milioni di persone, funge da te- stimonianza di quanto solida sia la base offerta da quest’architettura di rete basata su un criterio di decentralizzazione.
Nell’ambito di queste applicazioni distribuite, dove la natura dinamica dei peer implica la necessità di garantire sempre un alto grado di robustezza e scalabilità, un modo semplice per gestire il sostrato di interazione è offerto dalla combinazione di strategie agili di connessione allo scopo di creare diverse topologie di overlay network e disseminazione epidemica dei dati all’interno di questi ultimi. Ed è proprio nell’ambito della disseminazione che i protocolli di gossip risultano essere un caso di studio particolarmente interessante in quanto caratterizzati dall’assenza di piani di dirotta- mento precisi e non basati sui contenuti trasmessi, peculiarità dovute al criterio randomico con il quale il protocollo gestisce le comunicazioni.
In questa tesi si è affrontato il comportamento tipico delle reti P2P noto come free riding e grazie a LUNES, applicazione sviluppata allo scopo di testare le performance di protocolli di dissemi- nazione tramite gossip, si sono condotte sperimentazioni su uno specifico caso di studio (topologia di rete + protocollo di gossip) per osservare come il fenomeno incidesse su due parametri in particolare, cioè il rapporto di copertura e l’overhead ratio. Nei primi test presentati nel capitolo 2 il criterio di determinazione dei nodi free rider all’interno del grafo era basato su una soglia di probabilità definita dall’utente di LUNES. Nei capitoli successivi (3, 4 e 5) invece i risultati dei test sono stati prodotti da versioni leggermente modificate dell’applicazione, nelle quali la soglia di probabilità che il nodo destinatario sia un free rider viene ricalcolata all’invio di ogni messaggio per far sì che sia dipendente anche dal numero di hop rimasti prima che il messaggio decada, dal numero di vicini del nodo mit- tente o da entrambi. Un sistema dove un nodo viene individuato o meno come free rider in base ad un criterio governato esclusivamente dalla casualità è un caso di studio interessante a livello teorico, ma facendo in modo che questo processo di determinazione dipenda anche da caratteristiche interne al sistema è possibile condurre analisi mirate sulle performance dei protocolli in scenari caratterizzati da concentrazioni di free rider in particolari regioni del network (quella centrale, nel caso di questa trattazione) oppure dove il numero di free rider cambia (e quindi, per esempio, può aumentare) con il passare del tempo.
Le simulazioni condotte sul meccanismo a soglia di probabilità fissa nel capitolo 2, che riprendono ed espandono gli studi sugli effetti del free riding riportati in [xxix], hanno confermato che la presenza di free rider ha un impatto sui livelli di copertura raggiungibili assai limitato fino a quando la percentua- le di questo tipo di nodi rispetto a tutti quelli contenuti nel grafo si mantiene al di sotto del 50%. Allo
un brusco declino se la percentuale di free rider nel grafo supera la metà dei nodi totali, al punto che per scenari con l’80% di free rider o più il livello di copertura è minore, anche notevolmente, della percentuale di nodi che ricevono e ritrasmettono i messaggi normalmente.
Anche per quanto riguarda i meccanismi adattivi sviluppati nell’ambito di questa tesi, che proiettano questa ricerca verso territori ancora poco esplorati vista la penuria di letteratura scientifica a riguardo, le simulazioni hanno portato alla luce comportamenti interessanti. Nel caso di dipendenza dal time-to-live del messaggio, si è osservato che la bassa probabilità che un messaggio incontri un free rider durante i suoi primi hop fa sì che il volume di traffico veicolato dal sistema aumenti con- siderevolmente e che ciò permetta un notevole miglioramento del rapporto di copertura, in special modo per valori di soglia di probabilità impostata dall’utente superiori a 0,5. Nel caso di dipendenza dal degree del nodo, si è notato invece un peggioramento delle prestazioni relative al parametro di copertura nonostante anche in questo caso il traffico di messaggi per lo più aumentasse rispetto allo scenario a soglia di probabilità fissa, almeno fino a valori della variabile d’ambiente pari a 0,8 o su- periori, per i quali questo secondo meccanismo adattivo si conferma essere il più robusto tra quelli affrontati. Nel caso infine di dipendenza da caratteristiche sia del messaggio che del nodo, i risultati sono paragonabili come andamento a quelli del meccanismo dipendente da degree ma con prestazioni massime via via più ridotte all’aumentare della soglia stabile.
Il fenomeno del free riding si conferma quindi essere un grande ostacolo alla disseminazione di informazioni su overlay network, ma gli esperimenti compiuti su particolari scenari nei quali lo status di free rider di un particolare nodo non è dovuto a criteri basati esclusivamente sulla casualità gettano luce su aspetti del come questi ostacoli influenzino le performance della disseminazione tra- mite gossip che in certi casi possono non essere ovvi.
[i] G. Cirnigliaro, Data dissemination on overlay networks through gossip. Tesi di laurea in reti
di calcolatori, Alma Mater Studiorum - Università di Bologna, Campus di Cesena, Scuola di Scienze,
a.a. 2012-2013, pag. iii
[ii] G. D’Angelo, S. Ferretti, Highly intensive data dissemination in complex networks, Journal of Parallel and Distributed Computing, Elsevier, vol. 99, January 2017, pag. 2
[iii] Devavrat Shah, Network gossip algorithms. Acoustics, speech and signal processing, 2009. ICAS- SP 2009, IEEE International Conference on, pagg. 3673-3676
[iv] G. D’Angelo, S. Ferretti, Simulation of scale-free networks, Simutools ’09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques, ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), Brussels, Belgium, 2009, pagg. 1–10
[v] R. K. Kincaid, N. M. Alexandrov, Scale-Free Networks: A discrete event simulation approach, International Conference on Computational Science (1), 2005
[vi] R. Dobrescu, S. Taralunga, S. Mocanu, Web traffic simulation with scale free network models, AIC ‘07: Proc. of the 7th Conference on 7th WSEAS Internatinal Conference on Applied Informatics and Communications, WSEAS, 2007
[vii] D. Hughes, G. Coulson, J. Walkerdine, Free riding on Gnutella revisited: the bell tolls?, Distribu- ted Systems Online, IEEE 6 (6)
[viii] J. Eberspächer, R. Schollmeier, First and second generation of peer-to-peer systems, all’inter- no di Peer-to-Peer Systems and Applications, Lecture Notes in Computer Science vol. 3485, Sprin- ger, 2005, pagg. 35–56
[ix] P. Erdös, A. Rényi, On random graphs, 1, Publicationes Mathematicae, Debrecen, 1959, pagg. 290-297
[x] A.-L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286, 1999, pagg. 509-512
[xi] R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 2002, pagg. 47–97
[xii] D. J. Watts, S. H. Strogatz, Collective dynamics of ’small-world’ networks, Nature 393 (6684), 1998, pagg. 409–10
[xiii] M. Iliofotou, P. Pappu, M. Faloutsos, M. Mitzenmacher, S. Singh, G. Varghese, Network moni-
toring using traffic dispersion graphs (tdgs), Proceedings of the 7th ACM SIGCOMM Internet Mea-
surement Conference, ACM, New York, NY, USA, 2007, pagg. 315–320
[xiv] G. D’Angelo, S. Ferretti, Highly intensive data dissemination in complex networks, Journal of