Le componenti principali che implementano il protocollo di manutenzione sono:
• la classe PeriodicTimer, che ha il compito di lanciare il protocollo di manutenzione su tutti i nodi effettuando un ciclo su questi invocando il metodo periodicTimerExpired()
implementato nella classe ACEP rotocol. In dettaglio, la classe PeriodicTimer imple- menta la funzionalità principale del protocollo di Manutenzione, cioè l’invio di nuove richieste di vicinato.
• la classe CheckDeletedNodesControl, che ha il compito di controllare i nodi che non sono più attivi nella rete. Ogni volta che viene eseguito tale controllo, ogni nodo della rete verifica se la mappa receivedAnswers nella propria interfaccia Linkable contenga il valore true per ogni nodo a cui si è inviato un messaggio in fase si esecuzione del protocollo di manutenzione:
– se non lo contiene, viene eseguito il metodo che implementa la Remove del nodo – se lo contiene, non viene fatto nulla.
Affinché il protocollo di manutenzione sia simulato correttamente, è necessario che il controllo PeriodicTimer e CheckDeletedNodesControl siano sincronizzati nel loro tempo di esecuzione, con il controllo CheckDeletedNodesControl eseguito un tempo δ dopo il periodicTimer. Nel- l’implementazione effettuata δ = 35 cicli di PeerSim.
Risultati sperimentali
Lo scopo di questo capitolo è quello di presentare i principali risultati sperimentali otte- nuti dall’esecuzione di alcuni test per misurare e confrontare le performance dei protocolli analizzati nel capitolo 4.
Oltre a misurare le effettive performance dei protocolli, i risultati ottenuti consentono di confrontare i protocolli ACE, New ACE e GoDel. Essendo GoDel oggetto di lavori precedenti a questa tesi, è stata utilizzata la precedente implementazione per i risultati descritti in questo capitolo.
I test sono focalizzati nel determinare, per i protocolli, il numero di cicli di simulazione necessari per la costruzione di una triangolazione corretta e il relativo numero di messaggi utilizzato per il raggiungimento di questo risultato.
Una convergenza alla soluzione corretta con un numero di messaggi limitato è importante in applicazioni sviluppate su reti che possiedono requisiti di banda limitata e di consumo di energia, per esempio alle reti di sensori.
Il capitolo presenta inoltre una serie di test aggiuntivi effettuati sui protocolli ACE e New ACE, al fine di fornire una prova sperimentale delle considerazioni effettuate sulla correttezza di ACE e New ACE nel capitolo 4, e al fine di misurare le performance di questi.
Per la definizione dell’accuratezza della triangolazione di Delaunay calcolata è stato uti- lizzato un Oracolo interno al codice di ACE e New ACE, il quale ha lo scopo di costruire la triangolazione di Delaunay sull’insieme dei nodi partecipanti alla rete e di stampare il risul- tato in files xml dedicati, al fine di poterli utilizzare per il confronto con i files dei vicini dei nodi calcolati con gli algoritmi distribuiti.
La misura dell’accuratezza della triangolazione calcolata è definita come hitratio (6.1) ed è il rapporto tra il numero totale di vicini corretti dei nodi nella triangolazione calcolata in maniera distribuita e il numero di vicini totale dei nodi nella triangolazione calcolata dall’Oracolo.
hitratio = #CorrectDistribuitedN eighbors
#OracoloN eighbors (6.1) Per gli esperimenti eseguiti sono stati utilizzati due DataSets diversi:
1. un DataSet sintetico, generato con una distribuzione uniforme, composto da 2000 no- di ed utilizzato principalmente per i test di confronto tra ACE e New ACE. Al fine di valutare reti di diversa dimensione, per i test sono stati utilizzati sottoinsiemi di 500,1000,1500 e 2000 nodi.
2. un DataSet reale, composto da 500 coordinate su di un piano 5000x5000, che rappresen- tano un sottoinsieme delle Vivaldi Coordinates presenti all’interno del dataset originale [5], utilizzato per i test di confronto tra ACE, New ACE e GoDel.
6.1
Convergenza di ACE e New ACE per Join Sequenziali
Questa sezione descrive l’esperimento effettuato per confrontare la convergenza a una trian- golazione di Delaunay corretta di ACE e New ACE nel caso di Join sequenziali, ovvero in cui una join inzia la sua esecuzione quando la precedente join è terminata. Si assuma, quindi, che i nodi eseguano la fase di join sequenzialmente e che non ci siano disconnessioni volontarie o involontarie di nodi. Come descritto nella sezione 4.3, il protocollo ACE non sempre converge a una soluzione corretta a causa di alcune assunzioni fatte nella dimostrazione del Lemma 4.2.2, di cui è stata provata la non completa veridicità tramite l’esempio nella sezione 4.3. Lo scopo di questo test è quello di verificare come tale assunzione errata incida sulla correttezza della triangolazione di Delaunay calcolata in relazione al numero di iterazioni in cui i nodi effettuano delle operazioni di join sequenzialmente e verificare la correttezza di NewACE.
L’esperimento è stato effettuato utilizzando un sottoinsieme di 500, 1000, 1500 e 2000 nodi del dataset sintetico, con lo scopo di valutare la scalabilità degli algoritmi analizzati.
Figura 6.1: Convergenza di ACE e New ACE per 500 e 1000 nodi
La Figura 6.1 mostra i grafici ottenuti dall’esecuzione dell’esperimento su un insieme di nodi generato da i primi 500 (a sinistra) e 1000 (a destra) punti del dataset sintetico. Nel grafico è visibile che l’accuratezza della triangolazione di Delaunay costruita dal protocollo ACE diminuisce già dopo 20 iterazioni di più del 50%. Inoltre, questa continua a scendere all’aumentare del numero di cicli di simulazione, e quindi all’aumentare della dimensione della rete. Questo è motivato dal fatto che non è garantito che un nodo in fase di join trovi il nodo più vicino nella rete, perché la triangolazione in quel momento non è corretta, e questo da luogo ad un processo in cui le inconsistenze aumentano via via che si aggiungono nuovi nodi. New ACE, invece, dopo un primo picco di inconsistenza dovuto probabilmente a messaggi non ancora pervenuti, raggiunge l’accuratezza del 100%. In questo modo abbiamo dato una prova sperimentale della correttezza di New ACE per operazioni di join sequenziali.
Figura 6.2: Convergenza di ACE e New ACE per 1500 e 2000 nodi
La Figura 6.2 mostra l’esperimento eseguito su reti, rispettivamente, di 1500 e 2000 nodi. Dai quattro esperimenti si evince che l’accuratezza finale di ACE dipende dal numero di nodi
nella rete: infatti, il grafico relativo all’esperimento eseguito su 500 iterazioni in cui 500 nodi entrano sequenzialmente mostra per ACE un accuratezza maggiore rispetto al grafico relativo allo stesso esperimento eseguito su 2000 iterazioni in cui 2000 nodi entrano sequenzialmente. Al contrario, l’accuratezza di New ACE rimane stabile sul 100%.