In questo capitolo descriveremo i protocolli oggetto dello studio simulativo della pre-sente tesi e del lavoro svolto in [11]. Si `e scelto di analizzare, nell’ambito di due lavori di tesi, diverse tipologie di algoritmi: della fattispecie due facenti parte della famiglia dei protocolli reattivi (Lightweight Probabilistic Broadcast e SCAMP) e due della famiglia dei protocolli proattivi (Cyclon e ADH, il protocollo proposto da Allavena, Demers e Hopcroft).
2.1 Lightweight Probabilistic Broadcast
Lightweight Probabilistic Broadcast (LPBcast) `e un protocollo, completamente decen-tralizzato e basto esclusivamente su informazioni locali, in cui i processi hanno una conoscenza parziale del sistema limitata ai loro vicini. Definito in [45], Lpbcast ricorre ad un approccio probabilistico nel trattare la membership; le viste dei singoli processi son in continua evoluzione e limitate alla lunghezza l, fissa durante l’esecuzione ma parametrizzabile; il gossip viene trasmesso periodicamente ad un sottoinsieme della vista (la cui dimensione `e fissata), detto fan-out F, scelto casualmente. Entrambi i valori, l ed F, sono fissati per ogni membro del gruppo, e gli autori hanno ottenuto il risultato per cui, dato F ≤ l, l’ammontare della conoscenza che ogni processo mantiene riguardo la membership complessiva non impatta sulle performance del protocollo che risultano influenzate solo dal fan-out F . Ci`o non significa, per`o, che il valore di l non abbia alcun impatto per quello che riguarda le prestazioni dell’algoritmo; al diminuire di l aumentano le probabilit`a di incappare in un partizionamento del sistema. Gli au-tori hanno determinato che la probabilit`a Ψ(i, n, l) di creazione di una partizione di
dimensione i in un sistema di taglia n con una dimensione della view di l risulta mono-tonicamente decrescente, una volta fissato n, al crescere di l. Detto questo bisogna aggiungere che il nome del protocollo deriva dal fatto che, nelle intenzioni degli au-tori, lpbcast `e lightweight poich`e utilizza un quantit`a limitata di risorse di memoria e non richiede messaggi dedicati per la gestione della membership: i messaggi di gossip, vengono sfruttati non solo per disseminare le notifiche degli eventi e per propagare il di-gest delle notifiche degli stessi ma anche per propagare informazioni relative al sistema stesso e ai suoi membri.
2.1.1 Messaggi di gossip e Strutture dati
LPBCast `e basato sull’invio periodico di messaggi di gossip, attraverso periodi non sincronizzati1. Ogni messaggio mantiene localmente le seguenti strutture dati
• events: contiene le notifiche degli eventi ricevuti per la prima volta con l’ultimo messaggio di gossip;
• eventIds: contiene gli identificativi univoci degli eventi ricevuti in modo tale da mantenere localmente una sorta di cronologia degli eventi;
• unSubs: memorizza le notifiche di leave dei nodi che devono essere diffuse nella rete con i prossimi messaggi di gossip;
• subs: `e il duale del precedente per le sottoscrizioni;
• view: mantine gli identificativi dei vicini del nodo preso in considerazione e con cui quest’ultimo `e in grado di comunicare.
Quando il nodo deve inviare il gossip, predispone il messaggio allegando alcune delle strutture suddette in modo tale da diffondere nella rete sottoscrizioni, uscite e altri eventi di varia natura. I campi di cui `e composto il messaggio sono:
• Event Notifications in cui viene copiato il contenuto del buffer events. Ogni evento viene inviato in gossip almeno una volta ed inoltre le informazioni relative ad eventi pi`u vecchi vengono conservate in un buffer separato poich´e verranno rinviate solo in caso di richieste di ritrasmissione.
1
ciascun processo ha un timer locale al cui scadere viene inviato il gossip ed `e totalmente disaccoppiato da quello degli altri nodi
• Event notification identifiers in cui viene trascritto il contenuto del buffer even-tIds. Gli autori stabiliscono che l’identificatore dell’evento sia unico e che con-tenga, inoltre, l’Id del processo originario. In questo modo `e possibile ottimiz-zare il buffer facendogli contenere, per ogni altro nodo, solo gli identificatori delle notifiche consegnate successivamente all’ultimo evento considerato nella sequenza. • Subscription contiene un insieme di informazioni legate ai nodi che hanno ef-fettuato sottoscrizioni, (vedere la sezione 2.1.2 per maggiori dettagli). Queste informazioni, memorizzate nel buffer subs, vengono utilizzate per aggiornare le propria vista, conservata nel buffer view.
• Unsubscription trasporta un insieme di informazioni sui processi che hanno ab-bandonato il sistema, tali informazioni (rimandiamo anche qui a 2.1.3) vengono utilizzate per la rimozione graduale di tali nodi dalle viste.
Nessuna di queste strutture contiene duplicati e il tentativo di aggiungere elementi gi`a presenti le lascia inalterate. Ogni lista ha inoltre una lunghezza massima fissata, indicata con |L|m per una data lista L (∀L, |L| ≤ |L|m). La lunghezza massima della lista view `e indicata con l.
2.1.2 Procedure Relative al Gossip
L’algoritmo `e composto essenzialmente di tre procedure: la prima `e eseguita alla ricezione di un messaggio di gossip; la seconda `e ripetuta periodicamente nel tentativo di propagare informazioni agli altri processi coinvolti nel sistema; la terza `e utilizzata per la richiesta di event notifications che sono andate perdute o non sono state ricevute da lungo tempo.
Ricezione del messaggio di Gossip
Enunciate tutte le liste contenute in un messaggio di gossip, vi sono alcune fasi che devono essere affrontate per trattare i dati ivi contenuti.
1. La prima fase riguarda i dati relativi alle Unsubscription e contenuti nell’analoga lista: ogni nodo presente in tale lista viene tolto dalla view del nodo che riceve il messaggio ed aggiunto ad unSubs. Il buffer generato viene infine ridimensionato, per rispettare il limite |unSubs|mad esso associato, tramite la rimozione di alcuni
elementi scelti casualmente, presentiamo in Figura 2.1(a) il frammento di pseudo-codice relativo. Il motivo di fondo per cui il nodo eliminato deve essere agginunto in UnSubs `e per continuare la diffusione di questo evento presso gli altri nodi, vista la natura probabilistica della procedura di leave e della sua diffusione.
2. La seconda fase consiste nel tentare di aggiungere alla view le sottoscrizioni non ancora contenute in essa che divengono eligibili per poter essere inviate con il primo messaggio di gossip utile provocando l’aggiornamento dei buffer subs e view con il contenuto della lista gossip.subs estratta dal messaggio appena ricevuto. Va osservato che un processo attivo che invia gossip diffonde informazioni nel gruppo anche riguardo s´e stesso, semplicemente aggiungendo il suo Id alla lista subs che sar`a allegata al seguente messaggio di gossip. Anche in questo caso i buffer subs e view sono troncati, rimuovendo elementi scelti casualmente, per rispettare il loro limite prefissato. Si faccia riferimento allo pseudo-codice in 2.1(b).
3. La terza fase consiste nel consegnare all’applicazione gli event notifications che sono stati ricevuti per la prima volta con l’ultimo messaggio di gossip. Sono im-pedite consegne multiple dello stesso evento dalla memorizzazione in eventIds di tutti gli identificatori delle notifiche finora consegnate. Una notifica consegnata all’applicazione `e comunque elegibile per poter essere contenuta nel prossimo mes-saggio di gossip e quindi diffusa nel resto della rete. Se esiste un Id di un evento che non `e stato ricevuto dopo lungo tempo viene creato un elemento contenente tale Id, il round corrente e il sender del gossip che viene inserito in un ulteriore buffer chiamato retrieveBuf con lo scopo di ottenere pi`u tardi l’evento andato perso.
Invio del messaggio di Gossip
Ogni processo, periodicamente (ogni T ms), genera un messaggio di gossip, come de-scritto in 2.1.1, che invia a F altri processi scelti casualmente all’interno della sua view. Il gossip verr`a comunque generato allo scadere del periodo anche se nel frattempo non `e stata ricevuta alcuna nuova notifica; tale messaggio, infatti, verr`a utilizzato soltanto per scambiarsi digest e mantenere le viste uniformemente distribuite.
Ricezione del Gossip: Fase 1
1 {Fase 1: aggiornamento di view ed unsubs 2 con le unsubscription}
3 for each unsubs ∈ gossip.unSubs 4 view ← view \ {unSubs} 5 subs ← subs \ {unSubs} 6 unSubs ← unSubs ∪ {unSubs} 7 while |unSubs| > |unSubs|m do
8 rimuovi un elemento casuale da unSubs
(a)
Ricezione del Gossip: Fase 2
1 {Fase 2: aggiornamento di view con 2 le nuove subscription}
3 for each (newSubs ∈ gossip.subs)∧ 4 ∧(newSubs 6= pi)
5 if (newSubs /∈ view)
6 then view ← view ∪ {newSubs} 7 subs ← subs ∪ {newSubs} 8 while |view| > l do
9 target ← elemento casuale in view 10 view ← view \ {target}
11 subs ← subs ∪ {target} 12 while |subs| > |subs|m do
13 rimuovi un elemento casuale da subs
(b)
Ricezione del Gossip: Fase 3
1 {Fase 3: aggiornamento di events con 2 le nuove notif iche}
3 for each (e ∈ gossip.events) 4 if (e.id /∈ eventIds)
5 then event ← event ∪ {e}
6 LP BDeliver(e)
7 eventIds ← eventIds ∪ {e.id} 8 for each e.id ∈ eventIds
9 if (e.id /∈ eventIds)
10 then element.e.is ← e.id
11 element.round ← currentRound
12 element.gossip − sender ← gossip.sender 13 while |eventIds| > |eventIds|m do
14 rimuovi l’elemento pi`u vecchio da eventIds 15 while |events| > |events|m do
16 rimuovi un elemento casuale da events
(c)
Recupero di event notification
Il retrieveBuf `e processato per recuperare informazioni andate perdute. Come gi`a detto alla ricezione di un messaggio di gossip, contenente l’Id di un evento, non consegnato, un record composto da Id dell’evento, l’indicazione del round corrente e l’identificatore del nodo che ha generato l’evento stesso viene inserito nel retrieveBuf ; a questo punto per ogni elemento ivi contenuto viene eseguito un test per determinare se il processo pi ha atteso abbastanza (k rounds) prima di inziare la procedura per recuperare l’evento non consegnato. Viene inoltre eseguito un ulteriore test tramite eventIds per determinare se l’evento non sia stato consegnato con un messaggio di gossip successivo, ricevuto durante l’attesa. Se entrambi i test falliscono allora il processo pi inizier`a il recupero attraverso una richiesta al processo tramite cui piha avuto notizia dell’evento stesso. Se in tal modo non si ottiene l’event notification allora pi sceglier`a un processo nella view e invier`a la richiesta a quest’ultimo; in caso di ulteriore fallimento invier`a la richiesta dell’evento direttamente alla sorgente che lo ha generato.
La fase di recupero si basa evidentemente sull’assunzione che alla ricezione di un messaggio i dati in esso contenuti vengano memorizzati dal processo che lo ha ricevuto per un tempo limitato ma sufficientemente lungo da poter attivare con successo tutta la procedura. Va osservato che, senza l’assunzione fondamentale di conoscere chi `e il processo originatore di un evento dato il suo id, questa fase di recupero mancherebbe di uno step.
2.1.3 Dinamismo di Π
Ultima parte da affrontare riguarda uno degli aspetti pi`u rilevanti di un sistema p2p: la dinamica, ossia l’insieme delle procedure necessarie per entrare od uscire da un gruppo di processi.
Un processo pi che voglia sottoscriversi al gruppo Π deve conoscere un processo pj che gi`a fa parte del gruppo. Il processo pi invier`a semplicemente la sottoscrizione al processo pj che la propagher`a attraverso il gruppo. Se la sottoscrizione `e stata correttamente ricevuta e rinviata da pj allora piverr`a gradualmente inserito nel sistema e ne avr`a conoscenza tramite la ricezione di messaggi di gossip. Nel caso di mancata ricezione di messaggi viene fatto scadere un timer che porter`a alla riemissione di una richiesta di sottoscrizione. Il processo pi non inserisce il nodo presso cui si sottoscrive nella sua view e di conseguenza, finch`e non riceve messaggi di gossip, rimane sconnesso
dal resto del gruppo. Similarmente, anche pj non aggiunge direttamente pi alla sua vista ma lo aggiunge solamente al suo buffer locale di subs; la sottoscrizione di pi verr`a pertanto diffusa per mezzo di pjma quest’ultmimo non la considerer`a in prima persona. Pu`o quindi succedere che pi entri a fare parte del gruppo in maniera effettiva solo dopo diversi istanti di tempo.
Allo stesso modo un processo che vuole uscire dal gruppo non deve far altro che inviare la sua richiesta di Unsubscription e verr`a gradualmente rimosso dal sistema. L’unico problema da risolvere risiede nel fatto che unSubs non viene pulito delle sotto-scrizioni pi`u vecchie e quindi una richiesta di leave potrebbe rimanere all’infinito all’in-terno del sistema; il problema viene risolto inserendo nelle unsubscription un timestamp che le fa scadere dopo un certo periodo di tempo trascorso il quale, la richiesta di uscita viene rimossa. Il discorso legato al timestamp non viene applicato alle subscription che continuano ad essere inviate per garantire viste locali uniformemente distribuite; in-oltre, secondo gli autori, poich´e un processo corretto invia fra i nodi della lista subs, del messaggio di gossip, anche il suo identificatore (operazione che non viene evidentemente eseguita da un processo guasto) esiste un’alta probabilit`a che un processo guasto venga rimosso da tutte le viste del sistema dopo un periodo di tempo sufficientemente lungo. Una rimozione degli eventi eseguita in questo modo espone l’algoritmo ad un problema legato alla possibile non completa rimozione di un processo da tutte le viste dei membri del gruppo. In tal caso si potrebbe avere una nuova diffusione dell’informazione legata al nodo in questione, una volta che il timestamp associato alle Unsubscription abbia fatto scadere tali messaggi; tale problema assume particolare rilevanza in contesti di-namici in quanto porta il sistema ad una disconnessione pi`u rapida. A tale proposito pu`o essere fatta una riflessione: `e intuitivo come un elevato tasso di ricambio dei nodi rapportato ad una frequenza di gossip accetabile2 porti ad una immediata disconnes-sione della rete; i nodi che entrano nel sistema potrebbero non riuscire mai ad essere integrati in quanto il nodo usato come punto di ingresso potrebbe lasciare il sistema ancor prima di inviare il gossip successivo o potrebbe conoscere esclusivamente nodi in stato di leaving o gi`a usciti e non ancora notificati. In maniera analoga, un nodo che lascia il sistema invia la notifica esclusivamente ai suoi vicini i quali prima di diffondere tale evento devono attendere il successivo gossip. Va ricordato che nonostante il pe-riodo di gossip sia uguale per tutto il sistema ciascun nodo mantiene un timer locale
2
dove accettabile vuol dire frequente ma non troppo al livello di introdurre un overhead eccessivo per la rete
fecendo si che l’istante in cui viene inviato il messaggio `e, in genere, diverso da processo a processo. Appare quindi evidente come sia critico il problema del dimensionamento del timer di gossip, del timer di risottoscrizione e dei buffer subs e unsubs; `e vero che diminuendo il periodo di gossip si ottiene una maggiore circolazione delle informazioni ma si cerica molto la rete, limitando la sua capacit`a di scalare; diminuendo il periodo di attesa per il rejoin, invece, il nodo entrante rimane meno tempo isolato ma il degree dei nodi tenderebbe a sbilanciarsi. Per quanto riguarda i buffer, aumentandone le di-mensioni si riesce a non perdere eventi o, comunque, a perderne in entit`a minore, ma si contribuisce al fenomeno della trasmissione di falsi vivi nel sistema.
2.1.4 Ottimizzazioni
In lpbcast ogni processo mantiene localmente informazioni sui messaggi pubblicati e sulla membership ma, naturalmente, per preservare la membership `e necessario man-tenere le dimensioni di questi buffer limitate e rimuovere periodicamente elementi. Fino ad ora si `e considerato il caso semplice in cui le informazioni vengono rimosse tramite una scelta completamente casuale ma `e evidente che un comportamento migliore si ot-terrebbe mantenendo le informazioni meno diffuse ed eliminando quelle che sono state gi`a disseminate in maniera consistente.
In lpbcast vi sono due tipi di buffer: il buffer events che mantiene i messaggi (event notification) e il buffer subs che conserva informazioni di membership. Nelle due sezioni successive descriveremo per sommi capi, rimandando a [45] per maggiori informazioni, due tecniche di ottimizzazione applicabili ad ognuno di questi buffer.
Rimozione dei messaggi con modalit`a Age-Based
La tecnica di age viene applicata per fare un buon uso del buffer event mantenuto da ogni processo e per migliorare la reperibilit`a dei messaggi in esso contenuti.
L’idea di base `e quella di associare ad ogni messaggio in event un intero che rapp-resenta il numero di round che il messaggio ha trascorso nel sistema, ossia la sua et`a. L’et`a, aggiornata ad ogni round, riflette il livello di disseminazione del messaggio al-l’interno della rete. Ogni decisione sui messaggi da eliminare viene presa alal-l’interno del singolo processo e non c’`e necessit`a di alcun confronto con le age viste dagli altri.
Si ha il seguente comportamento:
lista degli eventi con age pari a zero. L’event notification pi`u vecchia contenuta nella lista viene rimossa nel caso in cui il buffer abbia superato la sua dimensione limite.
• Invio del gossip: quando viene inviato un nuovo gossip, l’et`a del mesaggio viene incremementata di 1.
• Ricezione del gossip: alla ricezione di un messaggio di gossip gli eventi non anco-ra ricevuti vengono consegnati all’applicazione e memorizzati nel relativo buffer; quelli non ancora consegnati, invece, verrano aggiornati, modificando l’et`a cor-rispondente con il valore pi`u alto fra quello contenuto nel buffer e il corrispettivo ricevuto con il messaggio. Se il buffer supera il limite previsto vengono rimossi i membri pi`u “vecchi”.
La scelta degli elementi da eliminare viene fatta in base a due criteri sequenziali: prima si analizza se il messaggio in questione ´e stato ricevuto molto tempo prima rispet-to ai messaggi successivamente consegnati dalla stessa sorgente e poi se il messaggio ha il valore pi`u alto del paramentro age fra gli eventi contenuti nel buffer.
I risultati ottenuti con questa tecnica, permettono agli autori di mostrare dei miglioramenti sia nell’ambito del delivery ratio che del livello di ridondanza3.
Rimozione dei membri con modalit`a Frequency-Based
La gestione della membership con modalit`a frequency-based `e un’ottimizzazione che si applica ai buffer subs contenuti in ogni nodo. Il principio permane quello di eliminare dal buffer l’Id dei nodi che sono maggiormente conosciuti nel sistema, conservando quelli meno diffusi e cercando di prevenire in tal modo l’isolamento a cui posso pervenire questi ultimi nel caso in cui sia rimosso il loro Id dall’unico nodo, o dai pochi nodi, che li mantengono nel loro buffer subs.
Anche in questo caso si fa’ ricorso ad un intero frequency associato ad ogni Id in subs che rappresenta il numero di volte che l’informazione sul membro in questione `e stata ricevuta dal processo.
In breve (anche qui si faccia riferimento a [45] per informazioni pi`u dettagliate): • Nuova Sottoscrizione Il nuovo processo pi invia la sottoscrizione con frequency 0.
3
intesa come il numero delle volte che un medesimo messaggio viene inviato in gossip e non come il numero di messaggi inviati in un round
• Ricezione del gossip Alla ricezione del gossip da parte di pj se pi non `e in view allora lo aggiunge e incrementa frequency, se gi`a compare in view allora viene semplicemente incrementato il valore di frequency; stesso discorso vale per il buffer subs.Nel caso in cui i buffer superino il valore massimo viene rimosso un elemento in base alle decisioni indicate di seguito.
• Scelta del processo da eliminare La scelta viene fatta in base ad una sequenza di operazioni: per prima cosa pj calcola la media (avg) delle frequenze di tutti gli elementi; sceglie poi un Id e dalla lista da svuotare e, se quell’elemento `e tale che e.f requency > k ∗ avg, con 0 < k ≤ 1, lo elimina altrimenti ne seleziona un altro. La scelta casuale del processo da rimuovere serve a preservare la distribuzione uniforme delle informazioni di membership.
Conseguenze dell’applicazione di questa tecnica sono, per gli autori, una riduzione del ritardo di propagazione delle informazioni relative alle nuove sottoscrizioni e una maggiore probabilit`a per le informazioni di membership meno conosciute, e quindi per i nodi con basso grado di propagazione, di rimanere nei buffer rispetto ai processi con alto grado di propagazione.
2.2 SCAMP
SCAMP `e un protocollo completamente decentralizzato e auto-configurante, in grado di variare la size della local view del singolo nodo in base alle dimensioni complessive del gruppo. E stato illustrato come le dimensioni della local view e il conseguente´