Tecniche per ottenere partial view scalabili in DET

I protocolli deterministici soffrono generalmente di problemi lagati alla scalabilit`a, al-l’impossibilit`a di mantenere le viste locali limitate al crescere della dimensione della membership. L’overhead per nodo `e proporzionale al grado del nodo stesso, e quindi, nel caso di DET, pari a |sponsor| + |sponsored|. In questa sezione accenneremo a due possibili modifiche da applicare a DET per ottenere delle viste locali di dimensioni ra-gionevoli e in grado di crescere pi`u lentamente della dimensione del gruppo. Possiamo immaginare due semplici approcci: il primo di tipo statico ed il secondo adattativo. Entrambe le metodologie verrano descritte per sommi capi ma in modo da chiarire il tipo di miglioramento che si pu`o ottenere con queste tecniche.

Approccio Statico

In questo caso faremo semplicemente ricorso ad una partial view di dimensione limitata e prefissata. Avremo un numero di connessioni accettate, pari al numero degli

sponso-red, finito e non in grado di variare per tutta la durata dell’esecuzione del protocollo..

In questo modo otterremo in maniera semplice, ed assai poco elegante, una vista di dimensione limitata ma ci troveremo di fronte a richieste di sottoscrizione rifiutate da

3.2. DET 67

parte di nodo che hanno gi`a raggiunto il limite prefissato, e indicato con |sponsored|<sub>m</sub>. Una situazione pi`u grave si prefigura nel caso in cui un nodo, in seguito ad una leave di un altro processo p_i, debba aggiungere a sponsored_j gli Id dei nodi facenti parte di sponsored_i, ottenendo come risultato che sponsored_i+ sponsored_j > |sponsored|_m. Alcuni nodi non potrebbero essere aggiunti e di conseguenza si troverebbero con uno

sponsor in meno, venendo in tal modo a cadere quanto detto fino ad ora riguardo alla

procedura di Unsubscription. Una soluzione parziale di questo problema si pu`o trovare soltanto richiedendo al nodo p_i di risottoscriversi da capo al gruppo.

`

E evidente come un approccio di questo tipo crei pi`u problemi di quanti posso portare a risolverne, per questo occorre tenere in conto di utilizzare una metodologia pi`u sofisticata se si vuole pensare di ridurre l’overhead del protocollo DET.

Approccio Adattativo

Per dimensionare in modo corretto le partial view si pu`o pensare di applicare un ap-proccio adattativo affatto dissimile da quello adottato in SCAMP. In pratica si pu`o utilizzare un meccanismo di indirection per permettere ai nodi in join di scegliere in modo casuale, e con distribuzione uniforme, i propri contatti a partire dai nodi con rango 0.

Ogni nodo p_i accetta con probabilit`a uguale a ¹

1 + |sponsored_i|^:

1. un nuova richiesta di sottoscrizione da parte di un nodo p_j, in questo caso p_i diviene il contatto di p_j;

2. un processo p_k che `e gi`a membro del gruppo e di cui lo sponsor ha lasciato. Se p_i non accetta la sottoscrizione di un nuovo nodo p_jallora p_j stesso ritrasmetter`a la sottoscrizione ad un nodo scelto casualmente, e con distribuzione uniforme, all’interno della sua vista.

Se p_i non accetta un processo p_k, che `e gi`a membro del gruppo, allora invier`a a

p_k un messaggio per avvertirlo che il suo grado `e diminuito. Venuto a conoscenza del fatto il nodo p<sub>k</sub> potr`a risottoscriversi, pur mantenendo la sua attuale partial view, per riottenere il suo precedente grado attraverso la ricerca di un nuovo sponsor.

`

E da notare che questo sofisticato meccanismo per mantenere partial view scalabili ha un alto costo in termini di tempi di latenza per le operazioni di join e di leave: un nodo in joining dovr`a attendere che un nuovo nodo accetti la connessione. La latenza potr`a essere ragionevole nel caso si faccia riferimento a sistemi quasi statici ma in

situazioni in cui il gruppo `e sottoposto ad un’alta dinamicit`a la latenza pu`o divenire molto elevata.

Possiamo quindi osservare come la scalabilit`a della partial view venga acquisita al prezzo di un aumento della latenza di join/leave.

Capitolo 4

Valutazione Sperimentale

Le simulazioni sono state svolte utilizzando il simulatore Ns-2 [30], un simulatore ad eventi discreti particolarmente adatto agli studi negli ambiti di networking. Ns-2 `e in grado di offrire pieno supporto agli stack protocollari utilizzati nell’Internet moderno, a simulazioni basate su TCP, UDP, sui protocolli di routing e di multicast. Supporta reti di tipo wired e wireless, e queste ultime sia in ambito locale che satellitare. Esistono inoltre molte estensioni di Ns-2 che permettono di aggiungere protocolli e ambiti pi`u specifici di simulazione, come ad esempio reti gsm e gprs, reti 802.16 ed umts. Detto questo occore spiegare le motivazioni che sottendono all’utilizzo di un tale simulatore: principalmente si `e voluto utilizzare tutto lo stack protocollare presente nelle reti wired e testare i due protocolli SCAMP e DET in condizioni pi`u possibili simili ad uno scenario di lavoro reale1.

Lo scopo delle nostre simulazioni `e di mettere in evidenza il comportamento di DET e SCAMP in condizioni di dinamicit`a. In particolare si vogliono mostrare, e mettere in relazione, le variazioni di vari parametri come il delivery ratio o il node

degree ad esempio, di entrambi i protocolli al variare del churn. Di seguito esporremo

pi`u accuratamente le variabili che sono state oggetto di misura e le condizioni in cui tali misure sono state effettuate. `E molto importante rimarcare, in questo piccolo preambolo, che per meglio comprendere il reale impatto del dinamismo (in termini di join e leave/sec) si sono condotte simulazioni in cui non sono presenti guasti ma solo

1D’altra parte ogni cosa ha un prezzo e l’accuratezza con cui abbia cercato di ricreare uno scenario realistico, e a causa della natura esponenziale del fenomeni come mostrato anche in [3], ha avuto come conseguenza l’impossibilit`a di eseguire simulazioni su viste di dimensioni molto ampie e/o churn rate bassi.

eventi di join e leave. Escluse le uscite non intenzionali dal sistema, si possono studiare accuratamente le eventuali problematiche che possono derivare dalla gestione delle sole leave intenzionali. D’altra parte, `e evidente come la contemporanea presenza di guasti avrebbe finito per contaminare i risultati sperimentali rendendo impossibile dirimere le cause, uscite intenzionali o non dalla membership, dagli effetti, partizionamenti o altro2.

Parametri delle simulazioni Ogni simulazione coinvolge un numero di nodi pari a

n_tot e risulta divisa in quattro intervalli di differente durata: l’intervallo di bootstrap, l’intervallo di perturbazione, un intervallo di transitorio un intervallo di misura (vedi la Figura 4.1). t_{0 t} 1 t₂ t₃

∆

∆

∆

∆

∆

∆

∆

∆

Figura 4.1: Intervalli di tempo in cui sono state divise le simulazioni

L’intervallo di bootstrap L’intervallo di bootstrap ∆_b `e inteso come l’intervallo di tempo iniziale in cui la dimensione del gruppo cresce, fino a raggiungere un valore desiderato, ma senza che vi sia la contemporanea presenza di leave. Il gruppo, nell’in-tervallo di bootstrap, inizia all’istante t<sub>0</sub> con una dimensione di n<sub>0</sub> nodi di bootstrap. Alla fine dell’intervallo, all’istante che indicheremo con t<sub>1</sub>, il gruppo conterr`a n₁ nodi.

La membership subir`a quindi un cambiamento consistente in n₁ join.

L’intervallo di perturbazione e di transitorio L’intervallo di perturbazione `e inteso come l’intervallo di tempo ∆<sub>p</sub> in cui tutti i cambiamenti della membership, intesi come join e leave, sono inseriti nel sistema. L’intervallo di transitorio ∆<sub>t</sub> `e inteso, invece, come l’intervallo in cui tutti i cambiamenti che sono stati apportati

2Si potrebbe obiettare che, con una scelta siffatta, ci si ponga, contrariamente ad ogni criterio ingegneristico, nella situazione migliore per entrambi i protocolli analizzati ma se un protocollo o un algoritmo non `e in grado di funzionare in maniera soddisfacente nel caso migliore, potr`a farlo in quello peggiore?

71

all’interno dell’intervallo ∆_pspiegano i loro effetti. In ogni simulazione il gruppo si trova con un numero di nodi n₁ nell’istante t₁, ottenuti dalla fase di bootstrap, e termina nell’istante t₃ con un numero di nodi pari a n_f = ¹₂n_tot. L’inserimento dell’intervallo di transitorio e il considerare n_f all’istante t₃, invece che in t₂, derivano dal fatto che per SCAMP le operazioni di join e di leave sono istantanee mentre ci`o non `e vero per DET. Non avremmo potuto, in tal caso, considerare il numero di nodi n_f a t₂ poich´e alcune procedure di Subscription e Unsubscription, in DET, potrebbero essere invocate nell’intervallo di perturbazione ma dispiegare i loro effetti soltanto nel transitorio.

Nell’intervallo di perturbazione avremo un numero totale di leave pari a ¹₂n_tot e un numero di join pari a n_tot− n.

L’intervallo di misura Nell’intervallo di misura ∆_m vengono eseguite tutte le misurazioni che verranno presentate nelle sezioni successive. In particolare abbiamo testato per entrambi i protocolli:

1. la proporzione dei nodi raggiunti da un insieme di messaggi, i messaggi di dati, inviati da ogni nodo durante l’intervallo di misura;

2. il grado medio dei nodi, cio`e il numero medio di connessioni attive per nodo. Entrambe queste metriche sono strettamente legate al livello di affidabilit`a del pro-tocollo analizzato ma la seconda metrica permette, anche, di mettere in evidenza l’ove-rhead del protocollo stesso. Inoltre nel caso di DET sono state eseguite delle simulazioni per analizzare la latenza media delle procedure di leave, consistente nel tempo medio che intercorre fra l’istante di invocazione della procedura di leave e l’istante effettivo di uscita dal gruppo.

Tutte le misure sono state prese variando il rate della dinamica del sistema nel-l’intervallo di perturbazione. Per caratterizzare questa dinamica `e stato utilizzata la metrica del churn rate.

Definizione 1. Il churn rate `e il rapporto fra il numero di cambiamenti alla

membership, cio`e join e leave, e la durata dell’intervallo di perturbazione ∆_p.

Considerando fissato il numero di join e leave, otteniamo che il churn rate `e una funzione della durata dell’intervalo ∆_p, in particolare in ogni simulazione ∆_pviene fatto variare da 5sec a 200sec.

Per ultimo occorre aggiungere che i tempi di arrivo e di permanenza dei processi all’interno del gruppo seguono una distribuzione esponenziale.

Scenari delle simulazioni Tutti gli scenari delle simulazioni che seguiranno nel testo constano di un numero di nodi totali pari a n_tot = 160. Per prima cosa si sono comparati i due protocolli in un ambito in cui non vi `e una fase preliminare di bootstrap. Successivamente si `e valutato separatamente SCAMP in un altro scenario per studiare l’impatto del bootstrap sul comportamento del protocollo stesso. La tavola 4 riassume gli scenari che sono stati oggetto di simulazione: lo scenario per cui ∆_b > 0 `e stato

suddiviso in tre casi. In particolare si `e valutato il comportamento di SCAMP nei casi in cui:

1. ¹₄n_tot = 40 nodi entrano nell’intervallo di bootstrap e tutti lasciano il gruppo durante l’intervallo di perturbazione, 0% di nodi stabili3;

2. 1

4n_tot = 40 nodi entrano a far parte del gruppo durante l’intervallo ∆_bdi bootstrap e la met`a di questi lasciano il gruppo durante l’intervallo ∆_p, 50% di nodi stabili;

3. ¹₄n_tot = 40 nodi entrano durante il bootstrap e tutti permangono all’interno del gruppo anche dopo l’intervallo di perturbazione, 100% di nodi stabili.

n0 n1 joins during ∆p leaves during ∆p nf % stable nodes

∆b= 0 - 1 160 80 80

-∆b> 0 1 40 120 80 80

0 50 100

Sia nel primo che nel secondo scenario all’inizio degli intervalli ∆_p e ∆_b, rispettivamente, il nodo di partenza ha una vista locale costituita solo da s´e stesso.

Parametri dei protocolli In conseguenza della scelta di non simulare la presenza di guasti all’interno del nostro sistema, abbiamo imposto per SCAMP c = 0. Il parametro, come gi`a visto in 3.1.1, determina la capacit`a del’algoritmo suddetto di resistere ai guasti che possono verificarsi all’interno del sistema. In mancanza della necessit`a di una propriet`a di failure resilience `e sembrato corretto porlo a zero, riducendo inoltre l’overhead complessivo del protocollo.

3In questo caso la percentuale viene calcolata rispetto al numero totale di nodi n1 presenti nel gruppo nell’istante t1.

73

Nonostante, come ripetuto pi`u volte, si siano trascurati i guasti, il meccanismo di heartbeat di SCAMP `e stato comunque implementato ed utilizzato nelle simulazioni, per prevenire fenomeni di isolamento dovuti alla gestione delle leave⁴. Il meccanismo di heartbeat, richiamato in 3.1.1 e per come `e stato implementato, forza il processo che non ha ricevuto alcun messaggio, di heartbeat appunto, per 2.5 secondi a risottoscriversi.

Alcuni grafici sono stati ottenuti tramite simulazioni in cui `e stato implementato anche il meccanismo della lease di SCAMP. In questo caso la durata dell’intervallo di lease `e stata prefissata, per ogni nodo del gruppo, a 50 secondi. Un tale valore `e sem-brato sufficiente per ottenere un numero ragionionevole di sottoscrizioni nell’intervallo considerato, ma anche in termini di scalabilit`a e di un miglioramento della reliability.

La determinazione dei contatti in DET Nella versione di DET, che `e stata im-plementata, si `e fatto ricorso ad una procedura aggiuntiva in cui ogni nodo in joining

p_i invia un messaggio ad una lista arbitraria, e scelta in maniera casuale, di contatti, tra cui `e sempre compreso cui il nodo di rango 0.

Questa scelta permette di ricevere sempre un acknowledgment in tempi brevi, in-fatti, anche se gli altri nodi contattati non sono al momento attivi, il nodo di rango 0 risponder`a sempre al messaggio, essedo comunque attivo in seguito all’Assunzione 1. Quando il nodo in joining riceve pi`u di un acknowledgment allora sceglie come suo sponsor il nodo di rando pi`u alto, quindi quello con rank_i inferiore.

Ora, poich´e ogni nodo contattato aggiunge il nodo in ingresso al sistema alla sua vista locale, anche se il nodo aggiunger`a un solo Id alla sua lista sponsor saranno neces-sari dei messaggi aggiuntivi e, non previsti direttamente dal protocollo, per eliminare le connessioni non volute. Meccanismi pi`u sofisticati di join possono essere elaborati e realizzati, come visto in [29] e in 3.2.7, ma al costo di un’alta latenza nelle operazioni di join e leave. Un’analisi pi`u approfondita di queste problematiche esula dagli scopi di questo testo.

La determinazione dei contatti in SCAMP In SCAMP il contatto `e solo uno dei nodi del sistema e non vi `e la necessit`a di processi speciale che debbano sempre rimanere all’interno del grupo stesso, come invece accade per il nodo di rango 0 in DET. Per questa ragione, per aumentare la probabilit`a di trovare un contatto attivo

4L’isolamento di una parte pi`u o meno consistente del sistema pu`o essere dovuto, ad esempio, alle leave di nodi utilizzati come contatti, che lasciano il sistema senza informare i nodi che sono entrati nel sistema attraverso di essi.

all’interno del gruppo si `e utilizzato un meccanismo aggiuntivo, rispetto a quelli previsti nel protocollo, e consistente nell’invio in broadcast a Π, da parte del nodo in joining

p_i, di un messaggio e nella scelta del contatto all’interno della lista dei nodi attivi che hanno risposto al broadcast. Chiaramente, in situazioni di churn rate molto elevato, pu`o accadere che un nodo risponda al messaggio per poi divenire inattivo immediatamente dopo l’invio della replica ma si `e cercato di limitare l’insorgere di una simile situazione, facendo scegliere come contatto il primo processo da cui si ottiene una risposta. In tal modo si `e ridotto al valore <sup>3</sup><sub>2</sub>RT T<sub>m</sub>, dove RT T<sub>m</sub> `e il pi`u breve dei RTT fra il nodo

p_i e gli altri nodi attivi, l’intervallo in cui il contatto pu`o uscire prima di ricevere la nuova sottoscrizione da p<sub>i</sub>, lasciandolo di fatto isolato. Bisogna notare per`o che, per SCAMP, dopo l’invio di una richiesta di sottoscrizione il nodo `e gi`a membro del gruppo pertanto un contatto inattivo pu`o essere un problema reale e molto grosso per quello che riguarda l’affidabilit`a. A questa considerazione va aggiunto il fatto che la procedura di indirection non risolve il problema, anzi risulta essere un meccanismo in grado di funzionare in maniera adeguata solo in sistemi quasi statici.

4.1 Risultati sperimentali senza Bootstrapping

Un importante blocco di simulazioni sono state ottenute nello scenario per cui ∆_b = 0, in tale situazione non si ha la presenza di una fase di bootstrap, composta di soli join, ma una situazione di crescita del numero di membri del gruppo costituita da una sequenza casuale di join e leave.