Quanto discusso finora in merito alla progettazione di una versione distri- buita di Label Propagation è circostritto solamente alla parte di input, ed abbiamo visto che è stato gestito con Python. L’implementazione vera e propria dell’algoritmo invece è stata realizzata in Java, scelta dettata dalla tipologia di API messe a disposizione da PeerSim, anch’esso implementato in Java.
Come primo passaggio necessario alla realizzazione dell’algoritmo abbia- mo analizzato la versione centralizzata di Label Propagation ed abbiamo raggruppato le principali operazioni effettuate dall’algoritmo nelle seguenti macro operazioni:
CAPITOLO 5. DESCRIZIONE TECNICA 61 Algoritmo 5.3 Esecuzione di Label Propagation sul singolo nodo
1. si effettua il parsing del grafo in input.
2. si inizializzano le etichette dei vertici del grafo.
3. si effettua una selezione random dei vertici e si aggiornano le etichette. 4. si verifica la condizione di terminazione, se validata si termina
altrimenti si ripete il passaggio al punto 3.
Abbiamo rinominato questa versione dell’algoritmo in Block Centric La- bel Propagation, il progetto consta di classi e interfacce atte a ricoprire il dominio e le funzionalità utili alla simulazione dell’algoritmo. Di seguito vengono elencate e descritte le componenti del progetto:
GraphNode questa classe di dominio descrive un vertice del grafo in input, con questo oggetto manteniamo alcune informazioni inerenti al vertice, tra cui, un identificativo univoco, l’etichetta associata, l’etichetta associata all’iterazione precedente, una mappa che associa gli idenficativi dei nodi vicini ad alcune informazioni inerenti (GraphNodeDescriptor) ed infine una sorta di history delle etichette (ILabelHistory) che sono state associate al vertice durante le varie iterazioni dell’algoritmo.
GraphNodeDescriptor questa classe di dominio mantiene alcune in- formazioni statiche che vengono associate agli identficativi dei vertici vicini, tra queste figurano un booleano che indica se il vertice vicino è localte cioè gestito dallo stesso nodo PeeSim ed eventualmente l’identificativo del nodo PeerSim che gestisce localmente il vertice.
ILabelHistory questa interfaccia fornisce due metodi, uno per aggiun- gere delle etichette ed uno per riconoscere una situazione di ping pong.
LPConstants questa classe fornisce solamente una serie di costanti utilizzate all’intero del progetto.
LPController questa classe implementa l’intefaccia Controller di Peer- Sim, con il suo unico metodo execute() questa componente si occupa di veri- ficare al termine di ogni ciclo lo stato dei singoli GraphNode (nodi PeerSim). Nel caso in cui tutti i nodi validino la condizione di terminazione, ovvero su nessun nodo vi è stato una variazione di etichetta, questo controller recu- pera le informazioni inerenti alle community locali ottenute sui singoli nodi, ne combina i risultati in modo da ottenere un’unica informazione globale, restituisce i risultati e termina la simulazione.
LPInitializer questa classe implementa l’interfaccia Controller di Peer- Sim, la sua funzione è quella di settare ai vari NodesManager una serie di pa- rametri necessari all’esecuzione della simulazione, come ad esempio il numero di iterazioni locali che ogni nodo PeerSim deve effettuare prima di recuperare le informazioni sui vertici gestiti dagli altri NodesManager, o la folder in cui è posizionato l’edge list che descrive la partizione di grafo associatagli.
LPUtils questa classe fornisce solamente una serie di metodi statici utilizzati dalle altre classi del progetto. Tra i principali metodi presenti in questa classe di utility abbiamo:
updateGraphNodeLabel(): consente di aggiornare l’etichetta di un no- do sulla base di una lista di etichette fornite.
getNeighboorFromExternalNodeById(): permette di ottenere l’etichet- ta corrente di un vertice gestito da un altro nodo PeerSim.
shuffleNodes(): dato un insieme di etichette di vertici restituisce una lista randomica delle etichette.
readNodeConfiguration(): questo metodo inizializza un oggetto Node- sManager con l’edge list che è stata associata al nodo PeerSim. Di fatto vegono istanziati tutti GraphNode rappresentanti i vertici della relativa partizione del grafo.
CAPITOLO 5. DESCRIZIONE TECNICA 63 calculateDominantLabels(): questo metodo dato un GraphNodee estra- pola la lista delle etichette dominanti sui vertici vicini al vertice da esso rappresentato.
printCommunities(): questo metodo stampa su file una lista di com- munity con i relativi vertici associati.
LaberlHistoryMultiple questa classe implementa l’interfaccia ILabe- lHistory ed estende una LinkedList aggiungendo una logica con cui si limita il numero massimo di etichette da poter aggiungere alla history ed espone il metodo foundPingPong() (booleano) con cui è possibile riconoscere se un all’interno della history delle etichette associate al GraphNode è presente una situazione di ping pong.
Ad ogni etichetta che entra a far parte della history viene associato un con- tatore, se questo durante i vari aggiornamenti raggiunge il limite prestabilito il metodo il metodo restituisce true.
NodesManager questa classe implementa l’interfaccia PeerSim CD- Protocol, il metodo principale da che da la logica a questo protocollo è next- Cycle(). Questa componente gestisce tutta la logica di sviluppo locale e globale della versione block centric di Label Propagation, nello specifico si occupa di far evolvere il GraphNode associato al nodo PeerSim.
Inizialmente tutti i GraphNode si trovano nello stato di INIT, recepi- scono la loro partizione di grafo, iniziano ad elaborala applicando i pas- saggi di Label Propagation così come avviene in una computazione locale (LOCAL_COMPUTING).
Durante i vari cicli di simulazione lo stato LOCAL_COMPUTING viene iterato per un numero di volte configurabile prima di passare allo stato succes- sivo INFO_RETRIEVING con cui si ottengono informazioni dai GraphNode vicini.
Con lo stato LABEL_UPDATING le etichette dei vertici gestiti dal Gra- phNode vengono aggiornate, successivamente con lo stato CHECK si verifica se viene soddisfatta la condizione di terminazione sui vertici locali.
NodesManagerStatus questa classe ingloba una enumeration utile a descrivere lo stato in cui si trovano i vari nodi PeerSim e più precisamente le istanze di NodesManager. Gli stati utilizzati sono i seguenti:
INIT: in questo stato il nodo è stato clonato, verrà inizializzato con la relativa partizione del grafo.
LOCAL_COMPUTING: in questo stato il nodo effettua le operazioni di ricalcolo delle etichette dei vertici appartenenti alla partizione del grafo senza tener conto delle informazioni dei vertici gestiti dagli altri nodi PeerSim. Di fatto viene eseguito la versione basilare di Label Propagation considerando esclusivamente le informazioni locali.
INFO_RETRIEVING: in questo stato il nodo recupera solamente le informazioni sui vertici vicini gestiti dagli altri nodi PeerSim. Vengono ricalcolate le etichette di tutti i vertici di bordo della partizione del grafo.
LABEL_UPDATING: in questo stato si aggiornano tutte le etichette dei vertici sulla base delle informazioni ottenute localmente e dagli altri nodi PeerSim, di fatto le nuove etichette calcolate vengono applicate ai nodi, in questo modo riusciamo sullo stesso ciclo riusciamo contem- poraneamente ad aggiornare le etichette di tutti i vertici dei vari noid PeerSim.
CHECK: in questo stato vengono validate le condizioni di terminazioni su tutti i nodi PeerSim, tra queste vengono prese in considerazione anche le situazioni di ping pong.
ERROR: nel caso in cui si verificassero anomalia il nodo assume questo stato e si termina l’esecuzione della simulazione.
La compilazione del progetto ci da modo di mettere a disposizione le fun- zionalità descritte nelle classi sviluppate tramite un unico archivio peersim- label-propagation-1.0.jar. Tra i vari .jar necessari all’avvio della simulazione
CAPITOLO 5. DESCRIZIONE TECNICA 65 va necessariamente fornito quello messo a disposizione da PeerSim: peersim- 1.0.5.jar, i rimanenti jar da fornire come dipendenze vengono elencati di seguito: commons-cli-1.3.1.jar commons-io-2.4.jar djep-1.0.0.jar jep-2.3.0.jar log4j-1.2.17.jar
Una volta compilato il progetto ed organizzato le varie dipendenze in un’ap- posita folder "libs" è possibile avviare una simulazione eseguendo il comando:
java -cp "peersim-label-propagation-1.0.jar:libs/*" peersim.Simulator configuration.conf
Configurazione della simulazione Per poter avviare una simulazio- ne PeerSim è necessario redigere un file di configurazione configuration.conf da passare in input alla classe peersim.Simulator. Il file di configurazione consente di selezionare la modalità di simulazione, di impostare una serie di valori globali all’esecuzione, dei parametri specifici alle implementazioni custom effettuate dagli utenti ed infine a specificare l’ordine con cui devono interagire i vari protocolli e controlli PeerSim.
Il file di configurazione utilizzato per avviare la simulazione di Block Cen- tric Label Propagation contiene una serie di voci, vedremo come influiscono i valori assegnati alle varie voci del file di configurazione:
network.size - indica il numero di nodi PeerSim da attivare durante la simulazione, il valore da associare a questa parametro deve necessaria- mente essere uguale al numero di partizione del grafo create tramite uno dei due partizionatori a disposizione ModulePartitioner o MetisParti- tioner. Il motivo di questo vincolo sta nel fatto che l’implementazione non contempla la possibilità di attivare nodi che non gestiscono alcuna partizione del grafo o che gestiscono più di una partizione del grafo.
simulation.cycles - indica il numero massimo di cicli che la simulazione può eseguire prima che questa termini. L’implementazione del proto- collo prevede la terminazione della simulazione nel caso in cui la con- dizione di terminazione sia soddisfatta su tutti i nodi PeerSim anche prima di aver eseguito tutti i cicli indicati in questa variabile.
protocol.lnk ’IdleProtocol’ - questa direttiva genera un protocollo che nelle altre properties verrà riferito come lnk, il protocollo IdeProtocol ha come unica funzionalità quella fornire l’accesso ai vai nodi PeerSim da parte degli protocolli, nello specifico questo protocollo viene utilizzato quando si costruiscono grafi statici.
init.rnd ’WireKOut’ - questa impostazione permette a PeerSim di ge- nerare un grafo a cui assegnare i vari nodi PeerSim.
init.rnd.protocol ’lnk’ - con questa direttiva assegnamo al protocollo WireKOut il riferimento al protocollo IdleProtocol con cui è possibile ottenere informazioni sugli altri nodi PeerSim.
init.rnd.k ’SIZE’ - questa proprietà deve presentare lo stesso valore del network.size.
init.rnd.undir ’true’ - questa proprietà consente di generare un grafo non diretto.
init.dbg ’it.distributed.label.propagation.LPInitializer’ - questa impo- stazione aggiunge alla fase di inizializzazione della simulazione un ul- teriore initializer, nello specifico questo è stato pensato per poter asse- gnare le varie partizioni ai vari nodi PeerSim.
init.dbg.local ’nodesmanager’ - con questa entry si vuole assegnare alla proprietà local del controllo LPInitializer il riferimento al protocollo NodesManager.
init.dbg.config.edge.list.folder ’/Users/christian/workspace/results/partitions/’ - con questa entry si vuole assegnare alla proprietà config.edge.list.folder
CAPITOLO 5. DESCRIZIONE TECNICA 67 del controllo LPInitializer il percorso all’interno della quale il controllo trova il file di definizione della partizione del grafo.
init.dbg.config.file.prefix ’node-’ - con questa entry si vuole assegnare alla proprietà config.file.prefix del controllo LPInitializer il prefisso del file che descrive la partizione del grafo da elaborare. Ogni nodo Peer- Sim è riferito da un identificativo numerico che concatenato al prefisso definisce il nome del file da ricercare all’interno del path definito dalla proprietà config.edge.list.folder.
include.init rnd dbg - con questa direttiva stiamo indicando a PeerSim quali sono i protocolli da utilizzare in fase di inizializzazione ed in che ordine eseguirli.
protocol.nodesmanager ’it.distributed.label.propagation.NodesManager’ - con questa direttiva stiamo definendo un nuovo protocollo della simu- lazione, in questo caso alla chiave nodesmanager stiamo associando la classe NodesManager.
protocol.nodesmanager.limitPingPong - con questa proprietà del proto- collo NodesManager stiamo definendo il numero di volte che un vertice del grafo può riottenere la stessa etichetta prima di potersi conside- rare in uno stato di ping pong. Il valore in particolare viene applica- to nell’inizializzazione delle LaberlHistoryMultiple di tutti i vertici del grafo.
protocol.nodesmanager.localIterations - con questa proprietà del pro- tocollo NodesManager stiamo definendo il numero di cicli da utilizzare per l’esecuzione di Label Propagation standard sui vertici locali al Gra- phNode (stato LOCAL_COMPUTING) prima di passare allo stato INFO_RETRIEVING con cui eseguire Label Propagation utilizzando anche le informazioni degli altri GraphNode.
protocol.nodesmanager.linkable ’lnk’ - con questa direttiva assegnamo al protocollo NodesManager il riferimento al protocollo IdleProtocol con cui è possibile ottenere informazioni sugli altri nodi PeerSim.
include.protocol ’lnk nodesmanager’ - con questa direttiva indichiamo a PeerSim quali sono i protocolli da utilizzare durante la simulazione, il primo lnk riferisce il protocollo standard IdleProtocol, il secondo node- smanager riferisce la classe it.distributed.label.propagation.NodesManager. control.debug ’it.distributed.label.propagation.LPController’ - con que-
sta direttiva stiamo dichiarando l’aggiunta di un custom Control la cui funzione è quella di verificare le condizioni di terminazione di tutti i GraphNode coinvolti nella simulazione.
control.debug.protocol ’nodesmanager’ - con questa entry stiamo asse- gnando al Control debug il riferimento al protocollo nodesmanager. control.shf Shuffle - questa direttiva indica a PeerSim l’ordine con cui
i vari nodi vengono presi in considerazione, nel caso nostro specifico ci torna molto utile che l’ordine con cui i nodi Peersim vengono elaborati sia random.
CAPITOLO 5. DESCRIZIONE TECNICA 69 # GLOBALS SIZE = 10 CYCLE = 50000 random.seed 1234567890 simulation.cycles CYCLE network.size SIZE # PROTOCOLS protocol.lnk IdleProtocol
protocol.nodesmanager it.distributed.label.propagation.NodesManager pro- tocol.nodesmanager.limitPingPong 3 protocol.nodesmanager.localIterations 5 protocol.nodesmanager.linkable lnk # INCLUDE PROTOCOLS include.protocol lnk nodesmanager # INITIALIZERS init.rnd WireKOut init.rnd.protocol lnk init.rnd.k SIZE init.rnd.undir true init.dbg it.distributed.label.propagation.LPInitializer init.dbg.local nodesmanager init.dbg.config.edge.list.folder /Users/christian/workspace/results/partitions/ init.dbg.config.file.prefix node- # INCLUDE INITIALIZERS include.init rnd dbg # CONTROLS control.debug it.distributed.label.propagation.LPController control.debug.protocol nodesmanager control.shf Shuffle Tabella 5.1: Configurazione