Figura 3.11: un peer sceglie pi`u leader con lo scopo di facilitare la ricerca di rappresentanza di tuttii suoi interessi
che ricoprono gli interessi di un peer. Oppure si scelgono quei leader che coprano la maggior parte degli interessi di un peer. Seguendo tali strategie, si rischia per`o di creare confusione nell’individuazione dei leader migliori che caratterizzano i dati presenti nel sistema. Per ovviare a tale inconveniente, una seconda strada da seguire `e quella di suddividere il profilo di un peer in pi`u sub-profili, cos`ı come avviene in [43] ed eseguire il protocollo in maniera indipendente per ogni sub-profilo, come mostrato in figura 3.12.
Risultato ancora migliori si ottengono eseguendo non solo il protocollo LEADER in maniera indipendente per ogni sub-profilo, ma eseguire in modo separato tutta la struttura del sistema a 3 livelli, fig.3.3. A tale fine, un utente, mantiene un peer differente per ogni suo profilo. Inoltre, avere dei profili pi`u mirati, permette di ottenere una strutturazione migliore delle comunit`a che cos`ı diventano pi`u definite e meno generiche.
3.4
Protocollo in azione
In questa sezione viene descritta l’esecuzione del protocollo attraverso un esempio in cui le tre fasi del protocollo sono eseguite in maniera sincronizzata da tutti i nodi del sistema. Tale scelta `e stata fatta per presentare in modo pi`u chiaro il com- portamento del protocollo semplificandolo e rendendone pi`u leggibile l’evoluzione. Una esecuzione sincronizzata non `e in contrasto con il protocollo stesso e su quanto
Figura 3.12: un peer suddivide il proprio profilo in sotto-profili ed ogni sotto-profilo esegue la ricerca del proprio leader in maniera indipendente dagli altri
annunciato in precedenza in quanto tale scenario non `e altro che il caso ideale in cui il protocollo converge subito alla prima iterazione. Anzi, la capacit`a di adattarsi sia ad ambienti sincroni che asincroni mette in evidenza la sua buona portabilit`a. La sua convergenza in un ambiente asincrono, oltre ad essere dimostrata da numerosi studi sui protocolli gossip, `e confermata in questo caso dai test eseguiti. I risultati delle prove effettuate sono riportati nei capitoli successivi.
La figura 3.13(a) mostra la peer-to-peer overlay network utilizzata nell’esempio. In figura i cerchi rappresentano i peer, le frecce le relazioni fra peer. Inoltre nelle figura 3.13(b)(c)(d)(e) le frecce rappresentano i voti espressi e i numeri vicino ai peer indicano i voti che il relativo peer ha ricevuti nelle varie fasi del protocollo. Nell’esempio la similarit`a tra peer `e misurata utilizzando una funzione che compara dati RGB, generati in modo random, che rappresentano i profili dei peer.
La tabella 3.1 mostra per ogni peer il proprio identificatore (col. PeerID), i suoi vicini (col. Vicini del Peer), i voti ricevuti nella prima fase (col. Voti Candidati Leader),i voti ricevuti nella seconda fase (col. voti Leader Potenziale) e l’id del suo leader potenziale (col. ID Leader Potenziale), i voti ricevuti nel primo e nel secondo step della terza fase (colonne voti Leader Effettivi) e l’id del suo leader effettivo (col. Id Leader Effettivo). In questo esempio la similarit`a tra peer `e calcolata come la somme del valore assoluto delle differenze tra i tre valori degli elementi RGB che costituiscono un profilo. Inoltre, i parametri del protocollo sogliaVicino, nVoti,
3.4. PROTOCOLLO IN AZIONE 55
Figura 3.13: la rete iniziale (a).le fasi intermedie dell’esecuzione del protocollo LEADER (b)(c)(d), e la scelta finale(e)
Peer ID
Overlay Network Fase1 Fase2 Fase3: step1 Fase3: step2 Vicini (id - dist) Voti C.L. ID L.P. Voti L.P. ID L.E. Voti L.E. ID A.L. Voti A.L. 4 id:13 d: 37 id: 8 d: 54 id:12 d: 112 4 4 5 4 6 4 7 19 id: 5 d: 69 id: 1 d: 98 id: 2 d: 119 3 19 4 19 4 19 5 0 id:16 d: 115 id: 7 d: 122 id:17 d: 134 3 0 4 0 4 0 4 10 id:15 d: 100 id:18 d: 109 id: 6 d: 112 3 10 4 10 4 10 4 8 id: 4 d: 54 id: 3 d: 72 id:13 d: 87 3 4 1 4 0 4 0 13 id: 4 d: 37 id: 8 d: 87 id: 3 d: 125 3 4 0 4 0 4 0 1 id: 5 d: 65 id:19 d: 98 id:16 d: 167 2 19 0 19 0 19 0 5 id: 1 d: 65 id:19 d: 69 id: 2 d: 188 2 19 0 19 0 19 0 6 id:18 d: 25 id:10 d: 112 id:15 d: 154 2 10 0 10 0 10 0 7 id:17 d: 48 id: 0 d: 122 id:18 d: 219 2 0 0 0 0 0 0 18 id: 6 d: 25 id:10 d: 109 id:15 d: 155 2 10 0 10 0 10 0 2 id:19 d: 119 id: 9 d: 153 id:12 d: 163 1 19 0 19 0 19 0 3 id: 8 d: 72 id:13 d: 125 id: 4 d: 126 1 8 0 4 0 4 0 9 id: 2 d: 153 id:14 d: 187 id: 1 d: 216 1 - 0 - 0 19 0 12 id: 4 d: 112 id:14 d: 121 id: 8 d: 124 1 4 0 4 0 4 0 14 id:12 d: 121 id: 2 d: 186 id: 9 d: 187 1 - 0 - 0 4 0 15 id:10 d: 100 id: 6 d: 154 id:18 d: 155 1 10 0 10 0 10 0 16 id: 0 d: 115 id: 1 d: 167 id:15 d: 199 1 0 0 0 0 0 0 17 id: 7 d: 48 id: 0 d: 134 id:18 d: 177 1 0 0 0 0 0 0 11 id: 4 d: 131 id:13 d: 152 id: 8 d: 165 0 4 0 4 0 4 0
Tabella 3.1: Esempio: descrizione dei nodi e relativi vicini in una rete P2P con 20 nodi. voti C.L.: voti ricevuti dal nodo per candidato leader, ID L.P.: id del peer scelto dal nodo come proprio leader potenziale, voti L.P.: numero di voti ricevuti dal nodo come leader potenziale, ID L.E.: id del nodo scelto dal peer quale proprio leader effettivo. voti L.E.: voti ricevuti dal peer in quanto leader effettivo.
sogliaLeader sono fissati rispettivamente a 160 , 2 e 3. In questo caso la sogliaVicino `
e rappresenta dalla distanza massima tra due peer al posto della similarit`a minima. La 3.13(b) mostra il risultato della prima fase del protocollo in cui i candidati leader sono scelti. In accordo con i valore dei parametri sogliaV icino e il nV oti ogni peer vota per i suoi 2 migliori vicini, che sono ad una distanza inferiore a 160. Da notare come il peer numero 9 esprime solo un voto in quanto, come si pu`o vedere in tabella 3.1, solo uno dei suoi vicini `e ad una distanza inferiore al valore indicato dal parametro sogliaV icino. I nodi 0, 4, 8, 10, 13 e 19 hanno ricevuto un numero di voti superiore al valore sogliaLeader, e quindi essi sono selezionati come candidati leader.
La seconda fase `e dedicata a selezionare i leader potenziali. Ogni peer vota il vicino candidato leader a lui pi`u simile. La 3.13(c) mostra il risultato di questa seconda fase. Come mostrato in tabella i peer 4, 8, 10, 13 e 19 sono selezionati come peer potenziali in quanto hanno ricevuto almeno un voto dai loro vicini nella seconda votazione. I peer 9 e 14 non hanno alcun potenziale leader perch´e nessuno dei loro vicini `e un candidato leader. Inoltre, essi non possono scegliere se stessi come leader potenziali perch´e hanno ricevuto un numero di voti minore della sogliaLeader. Tali nodi selezioneranno il loro leader nell’ultima fase del protocollo. I nodi 3, 11
3.4. PROTOCOLLO IN AZIONE 57 e 13 hanno pi`u vicini candidati leader. In questo caso essi scelgono come leader potenziale il candidato leader a loro pi`u simile, rispettivamente i peer 8, 13 e 4. I peer 0, 4, 10 e 19 che sono candidati leader, scelgono se stessi come leader potenziali ed incrementano di una unit`a il numero dei voti ricevuti nella seconda votazione. Questo `e mostrato nella 3.13(c).
Nella prima parte della terza fase del protocollo, i peer 0, 4, 10 e 19 che hanno ricevuto nella seconda votazione un numero di voti almeno pari alla sogliaLeader sono eletti leader effettivi. Come si pu`o notare il peer 3 in 3.13(b)(c) cambia il proprio leader. Questo avviene perch´e il leader potenziale da lui scelto, il peer 8 non riceve abbastanza voti. Il peer cerca allora un leader effettivo tra i restanti suoi vicini e trova il peer 4.
Inoltre, i peer 9 e 14 non trovano un leader effettivo tra i suoi vicini perch´e nes- suno di loro `e diventato un leader effettivo. Come si pu`o vedere dalle ultime colonne della tabella 3.1 essi scelgono rispettivamente i nodi 19 e 4 che sono i leader rispetti- vamente dei loro vicini 2 e 12. Come risultato finale (vedere figura 3.13(c)) si ottiene una rete costituita da quattro comunit`a composte dai peer 4 (leader effettivo), 3, 8, 11, 12, 13 e 14 la prima, i peer 0 (leader effettivo), 7, 16, e 17, la seconda, i peer 10 (leader effettivo), 6, 15, e 18, la terza, e i peer 19 (leader effettivo), 1, 2, 5 e 9 la quarta.
Capitolo 4
Implementazione
La valutazione delle prestazioni del protocollo, come spiegato nel capitolo successi- vo, `e stata guidata dalla necessit`a di possedere un ambiente che approssimasse al meglio uno scenario reale formato da peer indipendenti con informazioni reali in proprio possesso. A supporto di tale ricerca anche l’implementazione sia dei peer che del simulatore ha seguito lo stesso fine. In altre parole, `e stato cercato di avere un simulatore che “simulasse” il minimo indispensabile ma che allo stesso tempo permettesse un monitoraggio costante dei peer in esecuzione per poter calcolare i diversi dati statistici presentati nel prossimo capitolo.
Visto i motivi sopra menzionati, e la semplicit`a dell’architettura del simulatore stesso che nella realizzazione non supera le 2000 righe di codice, `e stato deciso di implementarlo invece di utilizzarne uno gi`a presente in letteratura. Durante l’implementazione dei peer, `e stata mantenuta buona compatibilit`a con il simulatore del tool Overlay Weaver con lo scopo di futuri test e utilizzi.
La classe PeersSimulatore, in figura 4.1, si occupa di
• creare i peer : i peer vengono instanziati, ad ognuno di loro viene passato la configurazione dei protocolli richiesta e lo U serP rof ile;
• lanciare i peer in esecuzione: i thread del peer passano allo stato runnable, e ad ogni peer viene presentato l’eventuale peer di boot. I peer non sono lanciati in esecuzione tutti insieme ma distanziati di un piccolo lasso di tempo casuale al fine di ottenere una distribuzione casuale dell’istante in cui ogni peer inizia l’esecuzione dei propri protocolli;
• interrogare i peer per il log: ad intervalli regolari richiede informazioni ai peer necessarie per eseguire calcoli statistici.
Figura 4.1: le classi del simulatore
Oltre al vettore contenente i peer del sistema, all’interno del simulatore `e imple- mentata la classe Indici che, utilizzando le informazioni dello stato di ogni singolo peer, calcola i dati statistici sullo stato della rete.
Infine, nel caso in cui i peer siano in esecuzione in modalit`a multi macchina, il simulatore mette a disposizione la classe StatoV iew: un nodo della rete dedicato alla ricezione dei messaggi di log inviati dai peer.
Al fine di valutare l’approccio proposto, `e stato implementato l’algoritmo LEADER e sono stati condotti vari esperimenti i cui risultati sono descritti nella sezione suc- cessiva. Gli esperimenti sono stati eseguiti utilizzando il simulatore in esecuzione su una macchina multi-core.
La struttura del peer `e formata da moduli indipendenti, figura 4.2. I tre liv- elli di protocollo, rispettivamente Cyclon, Vicinity e Leader sono implementati in blocchi indipendenti che non comunicano direttamente tra di loro ma concorrono ad aggiornare delle strutture di dati condivise.
Il protocollo Cyclon `e adibito ad aggiornare costantemente la lista dei suoi vicini, CyclonNeighbors, scambiando continuamente informazioni con gli altri nodi della rete. Periodicamente Cyclon sceglie in modo casuale un peer presente nella sua lista al quale invia parte delle informazioni in suo possesso. Alla ricezione di nuove informazioni, Cyclon sceglie in modo casuale dei nodi nella propria lista e li rimpiazza con quelli presenti nelle informazioni ricevute.
61
Figura 4.2: la struttura in moduli del peer
presenti nel sistema, implementando a tale scopo la LeaderNeighbors. Durante l’ese- cuzione utilizza i dati presenti in CyclonNeighbors in ricerca di nuovi peer migliori in similarit`a di quelli gi`a presenti tra i LeaderNeighbors. Inoltre, si occupa di ag- giornare tale lista inviando richieste di nuove informazioni qualora esse risultassero troppo datate. Infine Vicinity si occupa di eliminare le vecchie informazioni non pi`u aggiornabili. Al fine di poter eseguire un confronto tra il proprio peer e gli al- tri presenti nella rete, e poter rispondere alle richieste di informazioni provenienti da altri peer, Vicinity accede in sola lettura anche alla struttura dati contenenti le informazioni del peer, MyInfo.
Il blocco Leeader, accedendo alle informazioni del peer e alla lista dei suoi migliori vicini, rispettivamente MyInfo e LeaderNeighbors, esegue il protocollo descritto nel capitolo precedente. Anche Leader aggiorna i LeaderNeighbors quando riceve nuove informazioni durante l’esecuzione del protocollo ed in particolare tiene aggiornato le informazioni del Peer come le informazioni riguardante il proprio leader effettivo, e lo stato delle urne che contengono i voti ricevuti.
Tutti e tre i moduli accedono alla rete tramite un interfaccia, N et, utilizzata per l’invio dei messaggi. L’interfaccia Net `e unica per ogni peer che una volta acquisita
la mette a disposizione dei 3 moduli che implementano i protocolli, vedi figura 4.3.
Figura 4.3: la struttura delle classi per la gestione delle comunicazioni Il simulatore mette a disposizione diverse implementazioni dell’interfaccia Net. • RealNet instanzia per ogni peer le strutture dati necessarie per l’invio e la
ricezione di messaggi UDP. Essa permette l’esecuzione dei peer su pi`u mac- chine.
• PseudoNet `e una rete fittizia che mette a disposizione per ogni peer un vettore contenente i messaggi a lui indirizzati. Nei test realizzati in locale su una singola macchina `e stata quella maggiormente usata in quanto necessita di minime risorse di memoria rispetto a RealNet.
• OWNet `e la rete implementata utilizzando le primitive, send e receive, messe a disposizione dal tool Overlay Weaver.
Il modulo ReceiverMsgs si occupa di smistare i messaggi in ricezioni verso quei moduli che si sono a lui registrati preventivamente.
Ogni peer `e stato implementato utilizzando due Java thread, uno per l’esecuzione del thread attivo, algorithm 1, l’altro per quello passivo, algorithm 6, questo per avere una esecuzione dei peers completamente asincrona e indipendente tra di loro. Inoltre, entrambi i thread eseguono, rispettivamente, le parti attive e passive di due algoritmi, uno Cyclon-like e l’altro Vicinity-like, utilizzati come livello base sul quale viene eseguito LEADER.
63
Figura 4.4: la struttura delle classi del peer
Considerando le classi mostrate in figura 4.4, la classe Peer implementa il thread attivo e richiama i metodi loopProtocol delle classi LeaderNode, VicinityNode e CyclonNode che implementano i rispettivi protocolli.
La classe ReceiverMsgs, in ascolto sulla canale di comunicazione, si occupa di smistare i pacchetti in arrivo richiamando il metodo receiveM sg() della classe che implementa il protocollo a cui `e indirizzato il messaggio.
Come indicato nel codice presente in Algorithm 7 i tre protocolli vengono regis- trati presso il ReceiverMsgs ed ottengono il tag che identificher`a i propri messaggi. Per poter effettuare la registrazione i moduli che eseguono i protocolli, implemen- tano l’interfaccia ReceiverMsgI, ed in particolare il metodo RecevedMsg che verr`a richiamato dal ReceiverMsgs alla ricezione di un nuovo messaggio.
La figura 4.5 mostra le strutture utilizzate dal protocollo LEADER cio`e quelle utilizzate dalla classe LeaderNode che lo implementa: la classe Net utilizzata per inviare messaggi, la classe ReceiverMsgs per la ricezione dei messaggi, la classe MyInfo contenente tutte le informazioni di configurazione del protocollo compresi il profilo dell’utente e le urne, la classe LeiderNeighbors contenente le informazioni su i vicini del peer.
Allo stesso modo, le classi ViciniNode e CyclonNode, che formano il livello di base su cui poggia Leader utilizzano le strutture messe a disposizione dal peer come mostrato in figura 4.6
Algorithm 7 Costruttore del Peer
1: public Peer(...) {
2: ...
3:
4: //creo le informazioni che mi caratterizzano
5: myInfo=new MyInfo(net, profile, leaderConf);
6:
7: //creo le strutture dei protocolli
8: cyclonNeighbors= new CyclonNeighbors(maxCyclonSize);
9: leaderNeighbors=new ClassificationOfNeighbors();
10:
11: //creo i nodi dei protocolli
12: cyclon=new NodoCyclon(cyclonNeighbors, net);
13: vicinity=new NodoVicinity(cyclonNeighbors, leaderNeighbors,
14: myInfo, net);
15: leader = new Nodo(leaderConf, leaderNeighbors, myInfo, net);
16:
17: //creo il thread passivo
18: receiver = new ReceiverMsgs(net);
19:
20: //registro i protocolli al thread passivo
21: int cyclonTag=receiver.recordProtocol(cyclon); 22: cyclon.setMsgProtocolTag(cyclonTag); 23: 24: int vicinityTag=receiver.recordProtocol(vicinity); 25: vicinity.setMsgProtocolTag(vicinityTag); 26: 27: int leaderTag=receiver.recordProtocol(leader); 28: leader.setMsgProtocolTag(leaderTag); 29: }
65
Figura 4.5: le classi utilizzate a supporto del protocollo LEADER
test era quella di poter valutare le prestazioni di LEADER in modo indipendente dalla bont`a del lavoro svolto dai protocolli del livello base su cui esso si appoggia. In tal caso il simulatore “presenta” ad ogni peer i peer a lui pi`u simili presenti nel sistema. Ci`o permette di avere a disposizione di ogni peer un ambiente di partenza ideale.
Un altro scenario richiesto era quello di simulare l’instabilit`a dei nodi. A tal fine `e stata implementata la possibilit`a di disporre anche di ambienti dinamici in cui `e permessa sia la scomparsa e l’introduzione di blocchi di peer, che peer completamente indipendenti nell’alternanza di fasi attive che non attive.
Il simulatore permette l’avvio dei peer sia privi di informazioni sugli altri peer della rete, sia fornendo loro un ambiente di partenza ideale, Nel secondo caso, al- l’avvio del sistema, il simulatore “presenta” ad ogni peer i peer a lui pi`u simili presenti nel sistema. Tale approccio `e stato utilizzato in fase di test nei casi in cui era necessario valutare le prestazioni di LEADER in modo indipendente dalla bont`a del lavoro svolto dai protocolli del livello base su cui esso si appoggia.
Figura 4.6: le classi utilizzate a supporto del protocolli Cyclon e Vicinity che formano il livello base su cui posa Leader
Capitolo 5
Valutazione
5.1
Data Set ed Indici di Valutazione
Al fine di testare la reale efficacia del protocollo proposto, `e stato utilizzato un dataset reale. In particolare, `e stato utilizzato un sottoinsieme del dataset rilasciato da Mendeley [48, 49], un’azienda che produce un tool per la gestione delle pubbli- cazioni dove ogni utente pu`o memorizzare le pubblicazioni per lui pi`u interessanti. Tale dataset contiene un insieme di utenti anonimi, ognuno con un insieme di riferi- menti a riviste. Il sottoinsieme scelto `e composto da 2800 utenti, ognuno di essi con
Figura 5.1: l’esempio mostra come sono stati creati i profili dei peer
al pi`u 20 riviste. Per ogni utente `e stato utilizzato l’insieme dei termini presenti nelle keywords che descrivono la rivista. Il profilo di un utente viene ricavato dall’unione delle keywords che descrivono i documenti indicat dall’utente. Come mostrato in
figura 5.1 il profilo risulta formato da una lista di termini con associato il numero di occorrenze.
Cos`ı come descritto nei paragrafi precedenti, l’obbiettivo `e quello di definire un algoritmo per costruire comunit`a di peer che condividono un interesse comune, le cui dimensione non devono essere n´e troppo piccole n´e troppo grandi e, possibilmente, indipendenti dalle dimensioni della rete. Al fine di valutare la bont`a dei risultati dell’approccio proposto `e stata considerata la similarit`a all’interno della comunit`a, la similarit`a dei leader con il medoide della comunit`a che rappresentano, il numero totale delle comunit`a, la loro dimensione media, l’indice Neighbors with Me (NwM), l’indice Neighbors with Neighbors (NwN) e l’indice di Davies-Bouldin [51]. Con “medoide” si intende per ogni comunit`a quel peer che massimizza la similarit`a fra se e quella dei peer presenti nella sua stessa comunit`a. Per “similarit`a del leader con il medoide” si considera la media della similarit`a tra i leader e i medoidi delle rispettive comunit`a. La metrica utilizzata per misurare la similarit`a `e la Similarit`a di Jaccard Pesata.
Il grado di similarit`a all’interno delle comunit`a della rete `e calcolato nel seguente modo 1 N × X n∈N s(n, L(n))
dove N `e il numero dei peer appartenenti alla rete, L(n) `e il leader dell’n-esimo peer, e s `e la funzione di similarit`a utilizzata per confrontare quanto due peer siano simili e quanto un peer sia vicino alla propria comunit`a.
Dal momento che ogni peer sceglie autonomamente la comunit`a a cui partecipare, questa misura `e utile per constatare quanto il leader scelto sia un buon rappresentate. Avere dei buoni rappresentati garantisce un alto grado di somiglianza tra i membri della comunit`a che permette una comunicazione efficace nella rete. Questo fattore deve essere valutato insieme alla dimensione delle comunit`a al fine di evitare che il sistema crei comunit`a fatte di troppo pochi utenti, ci`o renderebbe vani gli effetti positivi della suddivisione dei peer in cluster.
Gli indici N wM e N wN descritti in seguito sono una specializzazione del “co- efficiente di clusterizzazione” definito per ogni nodo dal rapporto fra il numero dei collegamenti presenti tra i suoi vicini e il numero dei collegamenti possibili tra essi. In un grafo orientato, dove il collegamento fra due nodi i e j rappresenta la presenza di j fra i vicini di i, e considerando Ek come l’insieme dei collegamenti esistenti fra
5.1. DATA SET ED INDICI DI VALUTAZIONE 69 CC = |Ek|
k×(k−1)
Tale coefficiente non da una valutazione utilizzabile per il protocollo LEADER. Il CC `e una caratteristica intrinseca della rete su cui opera LEADER quindi fornisce indicazioni sulla rete creata dal livello sottostante Cyclon-Vicinity. Per rimediare a tale limite, sono stati introdotti gli indici N wM e N wN che specializzano CC e operano su peer appartenenti alla stessa comunit`a.
L’indice N wM indica la percentuale media di quanti vicini di un peer facciano parte della sua stessa comunit`a. Siano:
n il numero di nodi nel sistema
Ni = {peer vicini di pi} l’insieme dei vicini del peer pi,
M Li = {pj ∈ Ni∧ pj.leader = pi.leader} l’insieme dei vicini di pi che hanno scelto
il suo stesso leader.
Viene definito Neighbor with Me di pi come
N wMi = |Ni| |M Li| e N wM =Pn i=1N wMi
L’indice NwN indica in media quanto i vicini di un peer, che sono nella sua stessa comunit`a, siano collegati tra di loro, cio`e viene calcolato il rapporto tra il numero dei collegamenti esistenti e quelli possibili.