Il Problema delle Leave Conflitting - Il Caso SCAMP: Tecniche di Miglioramento e Valutazione

Il Caso SCAMP: Tecniche di Miglioramento e Valutazione

5.1 Il Problema delle Leave Conflitting

In 2.2.1 si è fatto vedere come il meccanismo di heartbeat non sia in grado di eseguire una detection accurata ed è stato detto che la procedura di Unsubscription permette di conservare il valor medio del degree di ogni nodo; nulla si è detto, al contrario, sulle conseguenze in merito alla correttezza delle viste dopo un aggiornamento come quello descritto. Il punto su cui focalizzare l’attenzione è la mancanza di un aggiornamento, o almeno di un tentativo di aggiornamento, delle inView. Infatti, quando un nodo pi

vuole lasciare il gruppo comunica ai nodi, i cui identificatori sono contenuti nella propria inView di aggiornare la loro partialView, sostituendo picon un nuovo Id o cancellandolo solamente. In caso di aggiornamento non viene inviata alcuna comunicazione riguardo l’uscita di p_idal gruppo e il possibile nuovo “padre” ai nodi contenuti nella partialView, molti dei quali conterrano pi nella propria inView. In tal modo quando i nodi contenuti nella partialView vorranno lasciare il sistema potrebbero non comunicare ai loro nuovi vicini di aver invocato la procedura di Unsubscription e questi ultimi si ritroverebbero con dei nodi nelle loro partialView non più validi. Tale situazione può essere etichettata come Leave Conflitting; in Figura 5.1 ne vediamo un esempio. Supponiamo che il nodo B decida di lasciare il gruppo; per le regole di leave imposte dal protocollo, quest’ultimo invierà, prima di lasciare il sistema, un messaggio di replaceOut(C) al nodo A, il quale sostituirà l’arco AB con l’arco AC.

(a) Stato del Sistema prima della leave di B

(b) Stato del Sistema dopo le leave di B e C

Figura 5.1: Situazione di Leave Conflitting

Supponiamo a questo punto che anche il nodo C decida di lasciare il sistema; C non è a conoscenza del fatto che B è uscito ne tanto meno del fatto che ora è puntato da A e quindi non informerà quest’ultimo di sostituirlo, o di eliminarlo, dalla sua vista e di conseguenza A sarà convinto di avere nella sua view un elemento che in realtà non fa

pi`u parte del gruppo.

5.2 Prevenzione dell’Isolamento

Un nodo si può considerare isolato quando non è in grado di trasmettere messaggi ad altri nodi (definendosi nodo pozzo) o quando non è in grado di ricevere messaggi dai vicini (definendosi nodo sorgente). In una situazione del genere, il nodo è in uno stato critico, in quanto è a rischio di disconnessione totale, ma è ancora recuperabile, perchè non è ancora satellite e può sfruttare i nodi da cui riceve, o con cui comunica, per essere re-inglobato. A tal fine è fondamentale riuscire a mantenere le viste il più coerenti possibili in modo tale da iniziare un’azione di re-join non appena una delle due si svuota.

Una prima causa dell’inconsistenza, che non consente di capire se una vista `e realemente vuota, `e intrinseca nell’algoritmo e dipende da

1. assenza del nodo joining nell’ inView del contact;

2. Notifica di leave (con conseguente update) esclusivamente ai membri dell’inView ; Questo `e facilmente risolvibile apportando le modifiche rappresentate in Figura 5.2, per quanto riguarda il nodo leaving, e gestendo i messaggi di update come riportato in Figura 5.3. Procedura di Replace 1 while (j < inDegree − c − 1) do 2 a = inView[j] 3 b = partialView[(j)_{mod(outDegree)}] 4 send [ReplaceOut(b), n] to a 5 send [ReplaceIn(a), n] to b 6 j + + (a)

Procedura di Notifica Leave 1 j = inDegree − c − 1 2 while (j < inDegree) do 3 a = inView[j] 4 send [LeaveOut(), n] to a 5 j + + 6 j = outDegree − c − 1 7 while j < outDegree do 8 b = partialView[(j)_{mod(outDegree)}] 9 send [LeaveIn(), n] to b 10 j + + (b)

Upon Receive ReplaceOut(x) from Node y 1 remove y from partialV iew

2 insert x into partialV iew

(a)

Upon Receive ReplaceIn(x) from Node y 1 remove y from inV iew

2 insert x into inV iew

(b)

Upon Receive LeaveIn() from Node y 1 remove y from inV iew

(c)

Upon Receive LeaveOut() from Node y 1 remove y from partialV iew

(d)

Con questo semplice accorgimento vengono aggiornate entrambe le viste dei nodi favorendo, quindi, il mantenimento di una certa coerenza dei link (ciascun nodo sa da chi è visto e chi vede). In un ambiente sincrono questa modifica assicura che nelle viste non ci siano discrepanze tra la situazione reale del sistema e quella vista localmente da ciascun nodo; in ambiente asincrono questo non è più vero in quanto l’impredicibilità del ritardo sui canali non assicura più né l’ordinamento tra i messaggi né la consegna dei messaggi stessi. Inoltre con questa modifica non riusciamo ad eliminare del tutto i falsi riferimenti che si creano in conseguenza di leave concorrenti; la procedura di leave, infatti, è non bloccante, quindi una volta che il nodo uscente ha inviato i messaggi di update è fuori dal sistema e non si preoccupa più del futuro di tali update, sarà compito dei nodi che perdurano nel sistema gestire in modo coerente la situazione.

Consideriamo ancora la situazione di Figura 5.1; con la sola modifica appena inserita quando il nodo B lascia il sistema porterà a conoscenza di tale evento sia A che C, quindi, se tra l’uscita di B e quella di C trascorre “abbastanza” tempo le viste saranno mantenute coerenti. Purtroppo nei sistemi reali non è possibile fare tali assunzioni sul dinamismo e quindi è neccessario utilizzare dei meccanismi che funzionino anche negli scenari peggiori.

5.3 Meccanismo di Ack

In molti protocolli usati nel mondo delle reti si è soliti scambiare dei messaggi di acknowledgement per essere sicuri che la trasmissione del messaggio sia andara a buon fine (come ad esempio accade con il protocollo di trasporto TCP); tale meccanismo è di semplice utilizzo e non appesantisce in maniera eccessiva la computazione, per questo si può tentare di applicarlo anche al protocollo in esame in modo tale da evitare che un nodo aggiunga un riferimento ad un altro, uscito dal sistema, mentre il messaggio di update era ancora in viaggio, riducendo cos`ı al minimo i falsi riferimenti all’interno delle viste.

Per spiegare come `e stata applicata la tecnica di ack all’algoritmo SCAMP viene fornito lo pseudo-codice in Figura 5.4 e una schematizzazione di come avviene lo scambio di messaggi in Figura 5.5.

Il meccanismo appena mostrato funziona anche in situazioni di leave concorrenti e in ambiente parzialmente sincrono ma soffre ancora se il dinamismo diventa sostenuto. Dai grafici proposti in Figura 5.6 `e possibile vedere il miglioramento apportato

Upon Receive ReplaceOut(x) from Node y 1 remove y from ackOutBuf f er

2 remove y from partialV iew 3 insert x into partialV iew 4 send [ackOut, n] to x 5 set timer chekOut for node x

(a)

Upon Receive AckOut(x) from Node y 1 insert y into ackOutBuf f er

(b)

Upon Elapsed Time checkOut for Node n 1 if (n.id /∈ ackOutBuf f er)

2 then

3 remove n from inV iew 4 if (partialV iew = ∅) 5 then if (inV iew = ∅)

6 then Re-join to random node in the Network 7 else Re-join to random node in the inView

(c)

A

B

C

replaceOut (C) replaceIn (A) ACK ACK TimeOut TimeOut ACK Buffer C ACK Buffer Out View ACK Buffer A C In View B A ACK Buffer C _B A

Figura 5.5: Schematizzazione del Meccanismo di ack

da questo meccanismo per C = 1 e per C = 2; per churn rate superiori, purtroppo, il miglioramento non `e apprezzabile in quanto non tutela i nodi e le loro viste da “apparizioni fugaci” (eventi rari ma possibili) e da concorrenza di leave e update; si pu`o comunque osservare come l’istante temporale in cui il sistema va a zero sia spostato in avanti (in particolare per C=8).

Per ovviare a questi problemi si necessita di strumenti di detection che si comportino bene anche in ambiente asincrono (e a maggior ragione in un ambiente parzialmente sincrono).

5.4 Meccanismi di Heartbeat e Ping

Questi meccanismi sono spesso utilizzati per la realizzazione di failure detector, ed `e con un’accezione simile che verranno utilizzati in questo contesto.

Il meccanismo di heartbeat, gi`a previsto dagli autori, serve per operare la pulizia delle inView e prevede di eseguire una ri-sottoscrizione presso un membro, scelto ca-sualmente, all’interno della partialView; l’unica modifica apportata a tale procedura, ovvia ma non esplicitata degli autori, `e quella di resettare l’inView nel momento in cui si effettua il re-join e di “scegliere” un altro nodo a caso all’interno del sistema, in maniera

0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 1 C = 2 C = 4 C = 8

(a) Scamp Originale

0 100 200 300 400 500 600 700 800 900 10001100120013001400 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 1 C = 2 C = 4 C = 8

(b) Scamp con Meccanismo di Ack

analoga a quanto avviene al momento dell’ingresso, qualora anche la partialView sia vuota.

Il meccanismo di ping, introdotto in questa fase, `e un p`o il duale del precedente ed `

e teso alla pulizia della partialView; allo scadere del timer mantenuto localmente da ciascun nodo, il peer comincia ad inviare dei messaggi di “ping” a tutti i membri della sua partialView e poi esaminerà le risposte pervenute nell’ultimo periodo trascorso, eliminando dalla sua vista tutti quei nodi che non hanno risposto con un messaggio di “pong”; a seconda del grado di asincronia del sistema è possibile introdurre un nuovo timer che consentirà di allungare o accorciare il tempo di attesa prima di esaminare le risposte di pong ricevute: più il sistema è sincrono, più si può settare il timer ad un istante vicino in modo tale da velocizzare la diagnostica dei falsi all’interno della partialView.

Fermo restando che l’idea di base dei due meccanismi è la medesima, la modalità mediante cui avviene l’interazione con i membri delle viste è diversa; l’heartbeat sfrutta una comunicazione di tipo push, ossia è il nodo che in completa autonomia, secondo un proprio timer locale, invia dei messaggi che ne testimoniano la vitalità, mentre il ping si serve di una comunicazione di tipo pull, ossia attraverso l’invio del messaggio di ping si stà implicitamente richiedendo un messaggio di risposta che indica lo stato in vita del nodo.

Questi meccanismi sono molto utili ed efficaci in ambienti con un forte grado di asincronia, ma vanno opportunamente utilizzati, vale a dire che il timer che controlla l’invio di tali messaggi deve essere dimensionato opportunamente per raggiungere il giusto compromesso tra il carico che viene immesso nella rete e il periodo di tempo che intercorre tra un messaggio e il successivo in relazione al grado di dinamismo della rete; in sostanza, maggiore è il churn rate, minore dovrebbe essere l’intervallo tra un ping/heartbeat ed il successivo, fino a raggiungere un livello di carico accettabile per la rete fisica sottostante. Un’altra osservazione che deve essere fatta è che ping ed heartbeat non sono immuni dal riportare falsi, dovuti ai ritardi di trasmissione sui canali, ma questo aspetto non rappresenta un problema nel nostro contesto. Va ricordato, inoltre, che il timer è uguale per tutti i processi ma ciascuno gestisce il suo in maniera del tutto indipendente dagli altri e quindi, fortunatamente, il sistama non risentirà di picchi di carico dovuti allo scadere simultaneo di tutti i timer.

In Figura 5.7(a) viene evidenziato l’effetto positivo apportato dai meccanismi di heartbeat e ping, congiuntamente al meccanismo di ack presentato nella sezione

prece-0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 1 C = 2 C = 4 C = 8

(a) Scamp con Meccanismo di Ack, Heartbeat e Ping

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% C=1 C=2 C=4 C=8 % of N ode s

Isolated Nodes Clusters with dim.< 6% Main Cluster

(b) Scamp con Meccanismo di Ack, Heartbeat e Ping: Clustering

Figura 5.7: Impatto dei Meccanismi di Ack, Heartbeat e Ping sulle Performance dell’Algoritmo Scamp

dente; sia la curva con C=1 che quella con C=2 sono rialzate di più del 10% e la curva con C=4 non scende fino a 0% assestandosi intorno ad un valore di R pari circa a 30% ed infine la curva con C=8 ha una discesa più morbida rispetto all’originale. Se si va a vedere come si è clusterizzata la rete (Figura 5.7(b)), introducendo le modifiche riportate, si vede chiaramente come la percentuale di nodi isolati diminuisca in maniera consistente ed insieme ad essa anche il numero di processi appartenenti a piccoli cluster (confrontare con Figura 4.7).

5.5 Un’Euristica per il Rejoin

I nodi che si distaccano, quando vengono “ripresi”, in generale, si riconnettono mediante i loro vicini; conseguenza è che se un nodo appartiene ad un piccolo cluster, diverso da quello principale, non sarà in grado di essere riassorbito, anzi, con il suo re-join contribuirà a rendere più forti i legami all’interno del cluster secondario e cos`ı anche gli altri nodi (che potrebbero vedere le loro viste svuotarsi) se avvertiranno la necessità di un re-join lo cercheranno nel cluster.

Un’ipotesi di soluzione per questo problema `e cercare di effettuare un re-join verso un nodo che non appartiene al gruppo del nodo isolato.

A B C F D E Main Cluste r Main Cluster

(a) Detection dello Stato di Isolamento del Cluster A B C F D E Main Cluste r Main Cluster

(b) Impossibilit`a di Detection dello stato di Isolamento del Cluster

Figura 5.8: Diagnosi di Clustering all’Interno dell’Overlay

Si consideri la situzione di Figura 5.8; a seguito di ping e heartbeat, il nodo A eventually si accorger`a di avere l’inView vuota e proceder`a al re-join. Se A cercasse il

contatto per il re-join semplicemente all’interno della sua partialView non sarebbe più isolato ma verrebbe riassorbito solo all’interno del suo clusterino e non darebbe alcun contributo significativo in termini di raggiungibilità. L’idea è di tentare di capire se il nodo parzialmente isolato e i suoi vicini formano un raggruppamento distaccato; intuiti-vamente, se un processo pi e i suoi vicini conoscono tutti gli stessi processi è verosimile che siano clusterizzati tra di loro; purtroppo non è possibile, in tempo breve e con certezza, stabilire se si fa parte di un cluster ed eventualmente quale sia la dimensione di quest’ultimo, quello che si può fare è tentare un re-join verso un processo che non si conosce in prima persona, ma solo tramite i peer vicini. Da questa considerazione deriva la seguente euristica di rejoin.

1. Il processo p_i, in attesa di re-join, sceglie un nodo p_j casualmente nella propria vista non vuota e gli chiede una lista L dei suoi vicini ottenuta nel modo seguente

L=partialV iewj ∪ inV iew_j

2. p_i sceglie il suo contatto per il re-join nell’insieme Π ottentuto come Π = L − (partialV iew_i∪ inV iew_i∪ p_i)

Se si ottiene Π = ∅ si torna al passo 1 altrimenti `e possibile procedere al re-join. Se pi

non è in grado di trovare un vicino, eventualmente scandendoli tutti, capace di fornirgli una lista L atta ad ottenere Π 6= ∅, invia un avviso di reJoinAll() in quanto ha dedotto che si trova in un cluster e tenterà di ottenere il contact in maniera analoga a quando è completamente distaccato. Alla ricezione del messaggio di reJoinAll, ciascun nodo potrà provvedere ad una riconnessione analogamente a quanto fatto da pi, sperando di ottenere un contact che appartiene al gruppo principale.

E possibile osservare che se il cluster non è di dimensioni troppo grandi (come succede al nodo A considerato nell’esempio in Figura 5.8(a)) è possibile diagnosticare la clusterizzazione e, in pochi passi, procedere con un re-join verso un altro nodo, sia da parte del nodo isolato, sia da parte degli altri nodi del gruppo. Purtroppo questo non è vero in assoluto, infatti basta considerare l’esempio in Figura 5.8(b) in cui il nodo A sceglierà come contact il nodo D oppure il nodo E.

In Figura 5.9 è mostrato l’andamento di R nel tempo. É interessante vedere come durante il periodo di stabilità tutte le curve tendano a risalire, più o meno rapidamente, verso buoni livelli di raggiungibilità media, grazie all’apporto congiunto delle tecniche

0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 1 C = 2 C = 4 C = 8

Figura 5.9: Impatto dei Meccanismi di Ack, Heartbeat e Ping e dell’euristica di re-join sulle Performance dell’Algoritmo Scamp

mostrate in precedenza e dell’euristica proposta per il re-join. Considerato l’andamen-to mostral’andamen-to per la curva C=8 è lecito chiedersi se avendo a disposizione un periodo di stabilità prolungato, ci si possa aspettare una continua crescita di R o una stabiliz-zazione intorno ad un certo valore; per dare una risposta a questo quesito si è provato ad ampliare il periodo di stabilità ed il risultato è quello ottenuto in Figura 5.10.

La risalita `e lenta ma progressiva e lascia intuire che se il sistema fosse parzial-mente sincrono e il dinamismo cessasse del tutto, la rete sarebbe in grado, in completa autonomia, di ricomporsi.

Purtroppo questa intuizione viene, solo in parte, confermata dalla Figura 5.11 in cui è mostrata l’evoluzione temporale della clusterizzazione del sistema al termine del periodo di churn. Con l’avanzare del periodo di stabilità si osserva come, sia i nodi isolati, che quelli appartenenti a piccoli cluster, vengano riassorbiti; un appunto che non ci consente con certezza di affermare che se il dinamismo cessa per periodi di tempo abbastanza lunghi, allora la rete si ricostruisce, è la presenza di circa il 20% di nodi che si raggruppano in pochi cluster di dimensioni non trascurabili i quali, con molta probabilità, non saranno in grado di diagnosticare il loro stato di clusterizzazione e quindi resteranno separati dalla parte più considerevole del sistema.

1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 0 10 20 30 40 50 60 70 80 90 100 110 % R t C = 8

Figura 5.10: Variazione di R durante il periodo di stabilit`a sfruttando l’euristica di re-join 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% T=1000 T=1900 T=2800 % o f N o d e s

Isolated Nodes Clusters with dim < 6%

6%<Clusters dim.<25% Cluster with dim>25% (Main Cluster)

In questa tesi si è rivolta l’attenzione sul problema della connettività in un sistema p2p, caratteristica fondamentale quando si vuole mantenere un livello del servizio di buona qualità. In letteratura esistono diversi protocolli atti al mantenimento di un’overlay connessa (Capitolo 1) ma, purtroppo, in essi l’aspetto dinamico di una rete p2p viene spesso tralasciato lasciando cos`ı la loro analisi parzialmente incompleta.

Contributo

I contributi apportati da questa tesi sono sostanzialmente due; il primo riguarda l’anal-isi di due Overlay Management Protocol (OMP), SCAMP e Lightweight Probabilistic Broadcast, in condizioni dinamiche (Capitolo 4), e il secondo `e costituito dall’aggiunta di meccanismi di recovery (acknowledgement e ping) e da un’euristica migliorativa per il re-join che si propone di recuperare dall’isolamento non solo i singoli nodi, ma anche i piccoli cluster (Capitolo 5).

Si è potuto osservare come entrambi i protocolli presi in esame, posti sotto stress, abbiano delle performance che degradino costantemente col passare del tempo; in par-ticolare si è potuto osservare come il sistema tenda a sgretolarsi sotto l’azione del churn piuttosto che a spezzarsi in blocchi disgiunti ma ben cementati al loro interno. Questo aspetto è di notevole rilevanza in quanto non consente, in uno scenario reale, di consid-erare il sistema affidabile; se il sistema si partizionasse in due, o più, grandi blocchi, la qualità del servizio offerto dalle applicazioni costruite sfruttando questi OMP sarebbe peggiore rispetto a quella di un sistema totalmente connesso ma comunque accettabile; equivarrebbe al far parte di un sistema più piccolo ma interamente e fortemente con-nesso. Nel momento in cui il sistema si sgretola e i peer si isolano, la qualità del servizio offerto diventa subito nulla e non è possibile reagire se non rientrando nel sistema.

A tale scopo si `e pensato di aggiungere ad uno dei due protocolli (SCAMP, sia per 111

motivi di leggerezza computazionale che per le migliori performance offerte in ambi-ente dinamico) dei meccanismi che consentissero di prevenire l’isolamento o di gestirlo in maniera più efficace prima che diventasse “cronico” (ossia non appena il nodo si rende conto di essere diventato una sorgente o un pozzo). Come si può vedere dalle sperimentazioni, con l’apporto dei meccanismi proposti si ha una ripresa della raggiun-gibilità media di ciascun nodo e la percentuale di nodi isolati, o raggruppati in cluster di piccole dimensioni, diventa molto più bassa anche per churn rate relativamente alti.

Nel documento Universit`a degli Studi di Roma “La Sapienza” (pagine 106-120)