In questo capitolo viene fornita una breve introduzione ai concetti necessari per la comprensione del lavoro di analisi e valutazione di performance di algoritmi in ambiente p2p e in condizione di churn [11], che rappresenta il primo contributo esposto nella presente tesi e che verr`a ampiamente discusso nel prossimo capitolo. Dopo aver definito il concetto di churn, verr`a descritto il simulatore utilizzato per le valutazioni, e in tale ambito verr`a specificato il contesto in cui sono inserite le simulazioni per poi finire con la definizione delle metriche utilizzate per l’analisi delle performance, il loro significato e le motivazioni che ne hanno determinato la scelta.
3.1 Il Concetto di Churn
Il termine churn, letteralmente, porta al concetto di agitazione, mescolamento; nel con-testo in cui questo lavoro `e inserito, tale parola indica il dinamismo dei nodi all’interno di un sistema. Il churn pu`o essere considerato una variabile fondamentale nell’analisi dei sistemi in condizioni di dinamicit`a e viene parametrizzati in termini di Churn Rate. Nelle reti p2p si definisce Churn Rate il numero di peer che entrano/escono nel/dal sistema in una data unit`a di tempo. Questo parametro `e rilevante nei sistemi a larga scala in quanto contrasta con l’esigenza di mantenere la rete connessa e consistente con la visione della stessa da parte di ciascun nodo. Se il tasso di churn `e alto, per esempio, vuol dire che il sistema `e altamente dinamico e risulta quindi pi`u difficile diagnosticare in ciascun instante di tempo quale sia la reale situazione del sistema.
In [20] viene fornito uno studio dettagliato del churn in tre diversi sistemi p2p di larga scala, con diverse caratteristiche, quali Gnutella, BitTorrent e Kad. Tale studio `e volto ad evidenziare alcune propriet`a:
• la similitudine della dinamica dei peer in tutti e tre i sistemi;
• la distribuzione del tempo di sessione e dei tempi di down segue la power-law; • i tempi di inter-arrivo dei nodi seguono la distribuzione di Poisson;
• nelle applicazioni di file sharing i tempi di sessione (in diverse apparizioni del nodo) sono correlati.
Queste propriet`a hanno portato gli autori alla conclusione per cui all’interno della rete dovrebbe esistere una frazione di nodi stabili a cui si aggiungono peer che si alternano con un’elevata frequenza per ciascuna unit`a di tempo.
3.2 Il Simulatore e l’Ambiente Simulativo
Il simulatore utilizzato per gli esperimenti `e Peersim [46]; la sua caratteristica pi`u interessante `e chepermette di rappresentare le caratteristiche salienti dei sistemi p2p (dinamicit`a e scalabilit`a) imponendo per`o delle assunzioni rilassate sul sistema (ad es-empio non viene rappresentato e gestito l’overhead della cominicazione a livello TCP/IP e non viene gestita esplicitamente la concorrenza). Nel seguito verr`a dettagliato il fun-zionamento del simulatore e le sue caratteristiche principali, nonch`e le assunzioni fatte e la struttura delle simulazioni con i relativi parametri.
3.2.1 Il Simulatore: Peersim
Peersim, nella sua struttura di base, fornisce delle interfacce, e delle classi per rappre-sentare i concetti di Nodo, Rete e Grafo dell’Overlay con appositi metodi per gestire tali oggetti (es. per aggiungere un nuovo nodo alla rete, per vedere lo stato del nodo, per conoscere la dimensione della rete ecc. . . ). L’ambiente fornisce due modalit`a di simu-lazione: a cicli (o cycle-based) e ad eventi (o event-based). La modalit`a di simulazione cycle-based consente di eseguire ad ogni ciclo, per ciascun nodo, tutte le operazioni sta-bilite dal protocollo ed `e adatta per simulare tutti quei protocolli che lavorano a round o che possono assumere un ambiente sincrono a causa della sequenzialit`a che hanno intrinsecamente. La modalit`a di simulazione event-based `e concepita per eseguire delle
azioni ogni qual volta si verifica un determinato evento che viene memorizzato in una struttura ad heap per essere processato al suo turno insieme agli altri eventi schedulati nella medesima unit`a di tempo. Ogni evento pu`o avere associato un delay programma-bile in modo tale da gestire con maggior precisione il momento del processamento. In entrambe le modalit`a di simulazione i parametri dei protocolli sono forniti al simulatore attraverso dei file di configurazione. In Figura 3.1(a) e Figura 3.1(b) sono mostrati due frammenti tratti da un esempio di file di configurazione.
fine Tb+Tc+Ts Tb 10010 Tc 1500 Ts 400 simulation.endtime fine overlay.size 1 overlay.maxSize 50000 Dichiarazione dei parametri di configurazione della rete Espressioni utilizzate come variabili di configurazione (a) protocol.0 edscamp.NewEDScamp protocol.0.c 0 protocol.0.bootstrapTime Tb protocol.0.networkDelay 1 protocol.0.random_delay 1 protocol.0.leaseTimeout 501 protocol.0.heartBeatTimeout 25 Dichiarazione dei parametri di configurazione del protocollo (b)
Figura 3.1: Frammenti di un file di configurazione utilizzato in Peersim
Non essendo esplicitamente modellato il canale di comunicazione, con gli eventuali ritardi, si pu`o simulare nei protocolli basati su scambio di messaggi tramite un delay (secondo le regole che si scelgono per il canale) all’evento di ricezione del messaggio.
Circoscrivendo il discorso nell’ambito di questo lavoro, le simulazioni sono state eseguite sfruttando la modalit`a ad eventi per mettere in luce il comportamento del protocollo a fronte di un’elevata concorrenza tra le operazioni sia a livello locale (un nodo n all’istante ti pu`o sia gestire la ricezione di uno o pi`u messaggi, che decidere di inviarne altri) che a livello di vicinato (diversi nodi n0. . . nkcompiono operazioni nello stesso istante di tempo ti), dell’interleaving dei messaggi (in ciascuna unit`a di tempo vengono processati messaggi di diverso tipo) e del churn.
Va sottolineato come nella versione event-based venga usato un tempo logico in cui ad ogni istante di tempo t possono essere eseguiti uno, diversi o nessun evento.
3.2.2 L’Ambiente di Simulazione
• Il comportamento `e asincrono;
• Non si considerano guasti di nessuna natura;
• La topologia della rete `e quella di un Random-Graph.
I tipi di eventi che vengono considerati nelle nostre simulazioni sono invocazione di join, invocazione di leave, invio di messaggi e ricezione di messaggi. Per tutti i tipi di simulazioni eseguite si `e scelto di ripetere dieci run indipendenti e di rappresentare poi i valori medi risultanti; ciascuna run `e strutturata in tre fasi distinte:
• Creazione • Churn • Stabilit`a
Nella fase di creazione i nodi fanno il proprio ingresso nella rete seguendo le regole di join imposte dal protocollo fino a raggiungere il valore N che rappresenta la dimensione totale della rete; si `e scelto di utilizzare questa tecnica in modo tale da creare un grafo di partenza realistico rispetto alle caratteristiche del protocollo. Iniziare con una rete precostituita, infatti, avrebbe portato il rischi di iniziare con topologie non ottenibili dall’algoritmo in uso. I nodi entrano nel sistema “lentamente” in modo da consentire una parziale stabilit`a e ottenere cos`ı una rete di partenza ottimale. Nella fase di churn i peer entrano ed escono continuamente dalla rete ad una frequenza parametrizzata e stabilita (il churn rate, identificato con C); si `e scelto di esprimere il churn rate come numero di join/leave nell’unit`a di tempo (ad esempio un churn rate pari a 2 indica che in una unit`a di tempo entrano 2 nodi ed escono 2 nodi dal sistema). Questa definizione di churn ci consente di mantenere costante la dimensione della rete. La seconda fase termina al compimento di 3000 operazioni1: la durata della simulazione in termini di tempo dipende quindi dal churn rate.
Osservazione 1. Il churn rate impatta non solo sulla dinamica dell sistema ma anche sulla concorrenza avvertita da ciascun nodo; pi`u il churn rate `e basso meno i nodi ne risentono localmente.
Si `e scelto di mantenere fisso il numero di operazioni piuttosto che il periodo di tem-po per riuscire a valurare se e quando il sistema collassa o scende al di sotto di certe
performance. Questa scelta, apparentemente controintuitiva, `e in realt`a molto impor-tante; nei sistemi reali `e fondamentale riuscire a capire quante operazioni si riescono a tollerare prima di un partizionamento piuttosto che quanto tempo deve passare, in mo-do tale da riuscire a fare un dimensionamento opportuno e un’allocazione delle risorse ridondanti opportuna. Nella fase di stabilit`a non accade pi`u alcuna operazione e viene lasciato al sistema il tempo di assestarsi.
3.2.3 Parametri di Simulazione
I parametri di simulazione che dobbiamo tenere in considerazione sono i seguenti: • Dimensione della Rete N;
• Churn Rate C;
• Tempo di Simulazione; • Delay Massimo della Rete;
In tutti gli esperimenti il parametro N `e stato posto pari ad 1 all’inizio del periodo di bootstrap (cio`e all’inizio della fase di creazione) per poi diventare pari a 1000 alla sua conclusione. Il churn rate `e stato ampiamente discusso in precedenza e nei nostri esperimenti assume i seguenti valori C=2,4,8,16,32,64. Per quanto riguarda il tempo di simulazione, nelle simulazioni eseguite (dove non espressamente specificato) si `e utilizzato un tempo normalizzato τ calcolato come
τ = t ∗ C 3000 ∗ 100
Tale scelta deriva dalla necessit`a di confrontare tra loro le varie curve nelle medesime condizioni rispetto al numero di operazioni eseguite come spiegato nel paragrafo 3.2.2. Il delay dei canali oscilla in modo casuale tra 1 e 10 unit`a.
3.3 Metriche di Valutazione
Le metriche che andremo a valutare sono essenzialmente due: la raggingibilit`a media e il clustering della rete.
La raggingibilit`a media, che indicheremo con R, definisce il numero medio di nodi raggiunti a partire da ciascun nodo della rete, rispetto al numero totale di nodi presenti.
Questa misura risulta profondamente legata alla connettivit`a seppur in realt`a sia in-negabile che forniscano indicazioni parzialmenti dipendenti; mentre possiamo sostenere che un riaultato di R=100% equivale ad una connettivit`a pari al 100%, non `e possibile affermare che se R `e circa paria a 0% allora il grafo `e formato da nodi totalmente scorrelati perch`e potrebbe verificarsi che ci siano cluster di piccole dimensioni total-mente connessi al loro interno ma sconnessi dagli altri e quindi calcolando la media sul valore dei nodi raggiunti a partire da ciascun nodo otteniamo che la raggiungibilit`a `e quasi pari a zero. Negli esperimenti che seguiranno verr`a mostrata la varizione della raggiungibilit`a media in funzione del tempo normalizzato τ al variare del churn rate C. La valutazione del clustering della rete `e complementare alla raggiungibilit`a media; nel conteggiare la dimensione del cluster vengono considerati solo i nodi legati da una relazione di connettivit`a forte in quanto non avrebbe senso valutare la debole in un ambiente in cui la comunicazione avviene su un grafo orientato. Queste due misure ci consentono, se prese insieme, di avere una visione pi`u precisa dello stato di connettivit`a della rete, soprattutto nelle situazioni per cui R risulta inferiore al 100%. Il clustering `e misurato al termine del periodo di stabilit`a e mostra in particolare la percentuale della rete che forma il cluster principale, la percentuale dei nodi isolati e la percentuale di nodi raggruppati in cluster la cui dimensione non supera il 6% della dimensione totale del sistema.