Reattivi
In questo capitolo viene illustrato nel dettaglio il primo contributo di questa tesi, con-sistente nell’analisi di due particolari protocolli di overlay management, SCAMP e Lightwight Probabilistic Broadcast (LPBcast), in condizioni di churn [11]. ´E impor-tante ricordare che tali protocolli non erano stati pensati, dagli autori, per lavorare sotto dinamismo, quindi non ci si dovr`a stupire eccessivamente se i risultati ottenuti saranno differenti da quelli ottenuti nei paper originali.
4.1 Valutazione di Lightweight Probabilistic Broadcast
In questa sezione verranno descritti i parametri caratteristici del protocollo ed i valori loro assegnati nello studio simulativo.
Purtroppo, per valutare le performance di Lightweight Probabilistic Broadcast (LP-Bcast), non `e stato possibile utilizzare i parametri di simulazione esposti nel Capito-lo 3.2.3, in quanto il simulatore non era in grado di sopportare il carico di tale algoritmo dato dalle molteplici strutture dati che ciascun processo deve mantenere localmente; conseguentemente si `e dovuto scendere di un ordine di grandezza sulla dimensione della rete (N=100) e si `e dovuto fissare il perioco di churn Tc = 200 unit`a di tempo ed il pe-riodo di stabilit`a Ts= 100 unit`a di tempo. Per quanto riguarda la variazione dei churn
rate C, in questi esperimenti partiremo da C=1 e scenderemo per potenze negative di due (fino a C = 2−6). Nei grafici mostrati viene utilizzato, in ascissa, il tempo logico anzi che il tempo normalizzato.
Per quanto riguarda le dimensioni massime imposte ai buffer descritti in 2.1.1, si `e scelto di fissarle tutte uguali e pari a 50 ad eccezione di l (limite per la dimensione della view) impostata pari a 12 (∼= 2log(N )). Il fan-out F `e posto pari a 9, in rispetto di quanto detto dagli autori di mantenerlo ≤ l in quanto il suo dimensionamento non rappresenta un fattore critico per le performance dell’algoritmo. Il periodo di gossip `e pari a 5 unit`a di tempo logico ed il periodo di attesa prima di una richiesta di ritrasmissione di eventi non ricevuti `e pari a 20 unit`a di tempo.
I test che saranno mostrati nelle prossime sottosezioni sono stati eseguiti al fine di valutare il protocollo nella sua forma base, senza considerare, quindi, le ottimizzazioni gi`a proposte dagli autori [45].
4.1.1 Esperimento 1
Questo esperimento `e teso a valutare la variazione di R (ossia della raggiungibilit`a media) sotto churn.
0 25 50 75 100 125 150 175 200 225 250 275 300 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 1 C = 2^(-1) C = 2^(-2) C = 2^(-3) C = 2^(-4) C = 2^(-5) C = 2^(-6)
In Figura 4.1 `e possibile vedere come le prestazioni si degradino in maniera contin-uativa col passare del tempo; va sottolineato che anche se C, in valore assoluto, sembra “piccolo”, in realt`a rapportato alla dimensione della rete diventa abbastanza consis-tente (avere un churn costante di un nodo per unit`a di tempo su una rete di 100 nodi, equivale ad avere l’ 1% del sistema che cambia in ogni istante). Un’osservazione inter-essante che scaturisce dalle curve appena mostrate `e il comportamento che si ottine per valori di C tali da consentire la diffusione dei messaggi di gossip (e cio`e per C < 2−3 che rapportato alla dimensione della rete `e circa lo 0,1%); in questi casi abbiamo che la raggiungibilit`a riesce a rimanere al di sopra della soglia desiderata (e cio`e sopra il 90%). 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 1 2^(-1) 2^(-2) 2^(-3) 2^(-4) 2^(-5) 2^(-6) Churn Rates O ver lay P e rc en ta ge
Isolated Nodes Clusters with dim. <6% Main Cluster
Figura 4.2: Stato di Clustering della rete al termine della simulazione
Per quanto riguarda lo stato di clusterizzazione della rete, mostrato in Figura 4.2, si pu`o vedere come il numero di nodi isolati e di cluster di piccole dimensioni diminuisca fino a diventare “trascurabile” per valori di C < 2−3. Questo `e dovuto al fatto che LPBcast non prevede meccanismi di diagnostica dell’isolamente ne tantomeno di re-join; tutto `e gestito tramite il meccanismo di gossip ed `e regolato dalla durata dell’intervallo temporale tra un gossip ed il successivo e, quindi, una volta che il nodo non riceve pi`u messaggi perch`e tutti i nodi da cui era puntato sono usciti, questo `e automaticamente disconnesso e non avr`a pi`u opportunit`a di essere reintegrato.
4.1.2 Esperimento 2
Come gi`a discusso in 2.1.2 quando si riceve e si gestisce un messaggio di gossip i buffer non devono eccedere la dimensione prefissata e questo viene assicurato rimuovendo elementi scelti casualmente all’interno dei buffer stessi. In [42] gli autori propongono diverse tecniche per selezionare, all’interno della vista, i peer a cui inviare il messaggio di gossip , attraverso quella che viene chiamata la Peer Selection, e diverse tecniche per selezionare i nodi da eliminare, in modo da troncare la loro lista, attraverso la procedura di View Selction. Il protocollo in esame pu`o essere classificato nella categoria dei (rand, rand, push)1.
Lo spirito del presente esperimento `e quello di valutare come il cambiamento della modalit`a di selezione dei peer a cui inviare il gossip e dei peer da sostituire nella view vada ad impattare sulle performance dell’algoritmo in termini di raggiungibilit`a media.
0 50 100 150 200 250 300 0 10 20 30 40 50 60 70 80 90 100 110 % R t RandRandPush RandTailPush RandHeadPush
Figura 4.3: Impatto della politica di View Selection su R
La view selection viene generalmente implementata attraverso la funzione se-lectView(view ) che ritorna un sottoinsieme di x elementi contenuti nella vista del nodo
1
Il primo elemento si riferisce alla tecnica di peer selection, il secondo alla tecnica di view selection e l’ultimo al modo di propagazione delle viste
chiamante; le politiche che saranno prese in considerazione, e con cui sono stati fatti i test riportati in Figura 4.3, sono:
• Rand : seleziona x elementi scelti uniformemente all’interno della view; • Tail : seleziona gli ultimi x elementi della view;
• Head : seleziona i primi x elementi della view;
Il risultato mostrato in Figura 4.3 `e stato ottenuto con C=1 e mostra che non si avverte alcuna differenza sostanziale riguardo la politica utilizzata per rimpiazzare i nodi all’interno della view; tra un gossip e il successivo si assiste ad un cambiamento di circa il 5% dell’intera rete, distribuito su tutti i nodi, quindi l’impatto che questo pu`o avere localmente sulla view di ciascun nodo `e irrisorio quindi i nodi che andranno “eliminati” per consentire il troncamento della view saranno pochi rendendo, di fatto, equivalente la politica di selezione all’interno della view.
0 5 0 1 0 0 1 5 0 2 0 0 2 5 0 3 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 1 0 0 1 1 0 % R t R a n d R a n d P u s h T a ilR a n d P u s h H e a d R a n d P u s h
Figura 4.4: Impatto della politica di Peer Selection su R
La peer selection viene generalmente implementata attraverso la funzione select-Peer() che ritorna un nodo vivo contenuto all’interno della vista del nodo chiamante; le politiche che saranno prese in considerazione, e con cui sono stati fatti i test riportati in Figura 4.4, sono:
• Rand : seleziona uniformemente un nodo all’interno della vista; • Tail : seleziona l’ultimo2 nodo all’interno della vista;
• Head : seleziona il primo3 nodo all’interno della vista;
L’informazione sulla “vecchiaia” dei nodi `e da considerarsi locale in quanto relativa alla presenza all’interno di una vista e non del sistema; la politica che d`a migliori risultati `e la Tail e questo pu`o essere giustificato dal fatto che cos`ı facendo si contribuisce a solidificare i legami dei nodi pi`u conosciuti, che tenderanno a clusterizzarsi, e si favorisce l’uscita e la circolazione all’interno del gruppo degli altri nodi; i nodi meno conosciuti verranno, piano piano, assorbiti grazie al fatto che la politica di view selection `e mantenuta random.
4.2 Valutazione di SCAMP
Per quanto riguarda i parametri caratteristici del protocollo SCAMP, sono stati settati in tutti i test come segue: il parametro C [10] (diverso dal parametro churn rate descritto in 3.2.3) determina la proporzione di guasti tollerati ed `e posto a 0 in quanto il nostro scenario `e fault free; i parametri di lease e di indirection non vengono considerati nei nostri esperimenti, il primo perch`e in condizioni di dinamismo portava un effetto peggiorativo sulle performance dell’algoritmo ed il secondo perch`e la scelta dei nodi usati come contatti dai processi che si stanno sottoscrivendo viene effettuata estraendo l’indice di tale nodo attraverso un generatore pseudo-casuale e quindi il suo scopo `e automaticamente soddisfato da questa soluzione pi`u gestibile e pi`u leggera per il simulatore; il parametro di heartbeat timeout, usato per recuperare l’isolamento dei nodi, `e settato pari a 50 unit`a di tempo logico in modo tale da riuscire a mandare messaggi di heartbeat il pi`u frequentemente possibile, assicurandosi per`o che la procedura di join sia terminata anche nel caso peggiore4. Per valutare che l’implementazione realizzata su Peersim fosse corretta, sono stati eseguiti i medesimi esperimenti condotti dagli autori di cui mostriamo in Figura 4.5 i risultati.
2
in questo caso con il termine ultimo si intende il nodo pi`u “anziano” 3
in questo caso con il termine primo si intende il nodo pi`u “giovane”
4un’operazione di join implica che mediamente vengano scambiati 5 messaggi per concludersi e nel caso peggiore, in cui ciascun messaggio impieghi il tempo massimo ad arrivare, abbiamo che questo ritardo `e pari a 50; da qui la stima per l’impostazione del parametro
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 0 500 1000 1500 2000 2500 3000 3500 4000 4500 Our Implementation GKM Implementation N um be r Of N odes
Partial View Size
Figura 4.5: Comparazione tra la distribuzione del degree nella nostra implementazione e in quella degli autori
Come nell’articolo originale, sono state eseguite dieci run indipendenti in cui si comincia da una rete composta da un solo nodo che `e sottoposta ad una fase di sot-toscrizioni, fino a farla arrivare alla dimensione complessiva di 100.000 nodi; una volta terminata questa fase si eseguono una serie di leave, in cui i nodi interessati sono scelti casualmente, fino ad arrivare a dimezzare la dimensione della rete (portandola quindi a 50.000 nodi).
Procediamo ora alla descrizione degli esperimenti effettuati e mostriamo i risultati ottenuti.
4.2.1 Esperimento 1
In questo caso quello che vogliamo andare a vedere `e come varia la raggiungibilit`a media lungo la dimensione temporale sotto churn.
La Figura 4.6 illustra in maniera evidente la dipendenza di R da C mostrando come ci sia una degradazione continua, sebbene di diversa entit`a, con il passare del tempo (e cio`e col numero di operazioni effettuate nel sistema). Va osservato come al termine del periodo di churn (τ = 100) per valori di C inferiori a 4 si ottiene una raggiungibilit`a
0 10 20 30 40 50 60 70 80 90 100 110 120 0 10 20 30 40 50 60 70 80 90 100 C = 2 C = 4 C = 8 C = 16 C = 32 C = 64 % Reache d No des τ
Figura 4.6: Variazione della raggiungibilit`a media su scala temporale al variare del churn rate
media intorno allo 0%. Questo ci porta a fare delle interessanti considerazioni sullo stato di clusterizzazione della rete, mostrato in Figura 4.7, al termine del periodo di churn.
La rete risulta frammentata in tanti cluster di piccole dimensioni (molti nodi risul-tano isolati) a causa della continua “erosione” conseguente al churn. Nel testo originale [10] viene mostrato un risultato in cui R scende al 99% solo dopo aver rimosso il 50% dei nodi della rete, mentre nel nostro caso questo avviene molto prima, quando circa il 10% dei nodi sono stati rimpiazzati (nel caso C = 2 questo avviene al tempo τ = 10/3 ). Questo accade a causa della debolezza dei link che legano i nuovi nodi entrati al resto della rete, in quanto i link dei vecchi nodi erano stati ottenuti in maniera ideale (e cio`e dando tempo a ciascun join di terminare senza alcuna interferenza di altre operazioni) mentre i nuovi peer, cercando di entrare in un sistema disturbato dalla continua entrata e uscita di altri nodi, non riescono a stabilire dei legami solidi con i loro vicini.
In Figura 4.6 `e possibile notare che per R < 80% la pendenza delle curve `e press-appoco la stessa mentre per 100% > R > 80% risulta molto ripida per churn rate pi`u elevati e morbida per churn rate bassi. Questa osservazione pu`o essere spiegata dalla seguente considerazione: quando la rete `e ben connessa il fattore che impatta di pi`u
0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 2 4 8 16 32 64 churn rate o ver la y p e rc e n ta g e
Main cluster Clusters with dim.<6% Isolated nodes
Figura 4.7: Clustering alla fine del periodo di stabilit`a per differenti churn rate
sulla connettivit`a `e l’identit`a del nodo che esce dal sistema. Un nodo vecchio che esce tenta di “ricucire” il vuoto che lascia mediante la leave attiva ma la forza dei legami dei suoi vicini risulta comunque inferiore; un nodo nuovo che si aggiunge non `e in gra-do di compensare, in quanto l’unico contatto che ha `e quello con il suo contact e per un periodo di tempo non sar`a visto da alcun nodo contribuendo, quindi, in maniera “negativa” al computo della raggiungibilit`a media del sistema. Questo comportamento impatta in maniera sempre meno evidente man mano che si procede con il refresh della rete.
Possiamo inoltre osservare, dal grafico, l’effetto positivo apportato dal meccanismo di heartbeat; purtroppo la ripresa `e di lieve entit`a in quando i nodi isolati non hanno alcuna possibilit`a di essere reintegrati nel cluster principale e come abbiamo visto in Figura 4.7 questi sono una percentuale consistente del sistema.
4.2.2 Esperimento 2
Questo esperimento `e conseguenza diretta dell’osservazione fatta nella sezione prece-dente ed `e volto a valutare l’importanza della presenza di nodi stabili nel sistema. Si `
raggiungibilt`a media mantenendo diverse proporzioni di nodi stabili. I peer uscenti sono scelti sempre casualmente salvo il vincolo di mantenere una certa percentuale di rete stabile. 0 10 20 30 40 50 60 70 80 90 100 110 120 0 10 20 30 40 50 60 70 80 90 100 % R ea che d N od es τ 90% Permanent 50% Permanent 10% Permanent 0% Permanent Random
Figura 4.8: Variazione della raggiungibilit`a media su scala temporale al variare della porzione di rete stabile
La curva etichettata come “Random” `e la stessa vista in Figura 4.6; `e possibile no-tare come le curve Random e 0% Permanent abbiano un andamento identico in quanto imporre di non avere nodi stabili equivale a dire che tutti i nodi sono candidati all’uscita proprio come nel caso random. In Figura 4.8 `e possibile vedere l’effetto positivo appor-tato sulla raggiungibilit`a dalla presenza di nodi stabili; durante il periodo di stabilit`a la percentuale di nodi raggiunti `e sempre superiore al numero di nodi permanenti a significare che la presenza di un componente stabile connesso facilita i nuovi nodi nella procedura di join e gli consente di integrarsi meglio nel cluster principale.
Anche in questo caso `e possibile osservare la ripresa delle curve dopo la fine del churn apportata dal meccanismo di heartbeat.
4.2.3 Esperimento 3
Una domanda che ci si pu`o porre `e come si modifica il comportamento del protocollo scalando sul numero di nodi e se esiste qualche relazione tra i vari parametri presi in considerazione. Per rispondere a questa domanda `e stato fatto il seguente esperimento: si `e preso come riferimento la curva con C = 2 di Figura 4.6 e si `e raddoppiato e dimezzato sia il valore del churn rate che dell’overlay size creando le seguenti coppie di parametri per le simulazioni
- Overlay Size 500 e C = 1 - Overlay Size 1000 e C = 2 - Overlay Size 2000 e C = 4 Il risultato `e mostrato in Figura 4.9
0 200 400 600 800 1000 1200 1400 1600 1800 0 10 20 30 40 50 60 70 80 90 100
Initial Overlay Size = 500, C = 1 Initial Overlay Size = 1000, C = 2 Initial Overlay Size = 2000, C = 4
%
Reached Nodes
t
Figura 4.9: Variazione di R per differenti valori di N e lo stesso rapporto N/C
Come appare evidente dal grafico riportato, esiste una relazione tra l’andamento di R e il rapporto tra grandezza del’overlay e churn rate: mantenendo costante il rapporto N/C si ottiene lo stesso degradamento di R.
4.2.4 Bound
Nelle precedenti sezioni `e stato mostrato come si degrada la raggiungibilit`a media in seguito ad una costante presenza di churn ed `e stato fatto vedere che il sistema prima o poi crolla se continuamente sottoposto a dinamismo, l’unica cosa che cambia `e l’istante in cui tale crollo avviene. A questo punto `e interessante vedere se esiste un valore di C tale da consentire al sistema di sopportare la pressione data dal dinamismo.
0 10 20 30 40 50 60 70 80 90 100 110 120 0 10 20 30 40 50 60 70 80 90 100 110 % R τ C = 2^ ( -6 ) C = 1 C = 2^ ( 6 )
Figura 4.10: Variazione di R per diversi churn rate
In Figura 4.10 `e mostrato l’andamento di R per tre valori di C che ne evidenziano il comportamento su diversi ordini di grandezza. ´E interessante osservare come salendo con gli ordini di grandezza la differenza che si vede tra le curve `e elevata mentre per churn inferiori5 a 1 la differenza diventa esigua ed `e chiaramente osservabile come non sia possibile trovare un valore di C tale che risulti R ≥ 90% a prescindere dal numero di operazioni invocate (e di conseguenza dal tempo trascorso). Un’alternativa per cercare di trovare valori di C tali da rispettare il vincolo su R `e rilassare un p`o le assunzioni fatte sul numero di operazioni; anzi che cercare un churn rate tale da
5In questo caso si ha che esistono unit`a di tempo in cui vengono invocate operazioni ed altre unit`a di tempo in cui questo non avviene e gli unici eventi che ci si trova a gestire sono solo quelli derivanti da precedenti invocazioni
rendere la raggiungibilit`a media maggiore del 90% per qualsiasi numero X di operazioni, chiediamo che tale churn rate mantenga R ≥ 90% per qualche valore di X in un dato intervallo temporale. Tradotto in termini pratici, questo `e realizzabile fissando un periodo di tempo T, in cui avviene la perturbazione, e cercando valori di C tali che rispettino il vincolo su R all’interno del periodo T.
In Figura 4.11 possiamo vedere che con questo rilassamento, fissando il periodo di churn T a 1.000 unit`a di tempo, si ottiene che per ogni C ≤ 1 abbiamo R ≥ 90%.
0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 0 10 20 30 40 50 60 70 80 90 100 110 % R T C = 2^(-5) C = 2^(-4) C = 2^(-3) C = 2^(-2) C = 2^(-1) C = 1 C = 2 C = 4 C = 8
Figura 4.11: Variazione di R nel tempo per differenti valori di C
Ovviamente il bound trovato `e molto debole perch`e da indicazioni limitate; se il dinamismo perdura oltre il periodo T non si ha alcuna assicurazione sul mantenimento di R neanche con i valori di C tollerati in T.
4.3 Valutazioni Complessive
I due protocolli presentati appartengono, come gi`a detto, alla famiglia dei reattivi e, come `e stato possibile osservare dai grafici mostrati, esibiscono un comportamento similare; ovviamente, avendo presentato esperimenti su overlay di diversa dimensione, non sono direttamente confrontabili le curve per pari churn rate ma va fatto un paragone sul churn rate relativo, ossia sull’intensit`a del dinamismo rapportato alla dimensione del
sistema; ad esempio, come effetto disturbatore, sono comparabili la curva di SCAMP con C=4 (che rappresenta un churn rate dello 0,4% per unit`a di tempo) e la curva di LPBcast con C = 2−1 (che rappresenta un churn rate dello 0,5% per unit`a di tempo); in Figura 4.12 mostriamo la variazione di R, per entrambi i protocolli, all’aumentare del numero di operazioni, con i valori di C appena menzionati in modo tale da avere un’idea della differenza di prestazioni fornite dagli algoritmi.
0 20 40 60 80 100 120 140 160 0 10 20 30 40 50 60 70 80 90 100 110 % R # operation LPB cast S CA MP
Figura 4.12: Variazione di R in funzione del numero di operazioni per LPBCast e SCAMP
Scamp `e pi`u resistente rispetto a LPBcast, in condizioni di churn, in quanto strut-turato per cercare di compensare i lati negativi che il meccanismo di gossip ha; in SCAMP `e introdotto un meccanismo di leave attiva che consente di “ricucire” il vuo-to lasciavuo-to da un’uscita assicurando che non lasci completamente scollegate due parti dell’overlay; inoltre il meccanismo di gossip, per sua natura, non riesce, neanche in condizioni di stabilit`a, a mantenere un’affidabilit`a del 100% sulla consegna dei messag-gi in quanto esistono nodi che si isolano e che quindi non contribuiscono a diffondere le informazioni che possiedono e che sono necessarie al mantenimento di un’overlay connessa.
A seguito di queste conclusioni, nel capitolo successivo, si proporranno dei meccan-ismi per cercare di migliorare le performace di SCAMP e si abbandoner`a per il momento