Un count min sketch è definibile semplicemente attraverso due parametri e δ che stabiliscono le performance dell’intera strut-tura dati. La strutstrut-tura dati che viene utilizzata è una array di contatori bidimensionale di lunghezza w e profondità d pari rispettivamente a w = de/e e d = dlog(δ)e. Tutti i conta-tori, riferibili tramite un doppio indice c(i, j), devono essere inizialmente posti a 0.
La struttura dati utilizza un insieme di funzioni hash:
h1...hd :{1...n} −→ {1...w} (18) scelte uniformemente a caso da una famiglia di funzioni pairwise-indipendent. Ogni funzione è associata ad una riga e mappa ciascuno degli elementi per i quali è necessario un contatore con una colonna dell’array di contatori. Ovviamente nel nostro caso ciascuna funzione hash dovrà mappare un topic t in una delle colonne dei contatori.
5.1 count min sketch 65 +1 +1 +1 t1 h1 h2 h3
Figura 23: Il topic t1 è mappato tramite le funzioni hash h1,h2
e h3 in 3 colonne diverse, dove verrà incrementato il corrispondente contatore
La procedura di aggiornamento dello sketch prende un topic t in ingresso e prevede l’aggiornamento di almeno un conta-tore per riga, dove la colonna selezionata è calcolata tramite la corrispondente funzione hash, in altri termini se deve essere incrementato il topic t allora:
c(j, hj(t))← c(j, hj(t)) + 1 per j = 1..d (19) L’array di contatori viene quindi pian piano popolato per mezzo del meccanismo appena esposto ed è dimostrato che la struttura permette di rispondere alle point query con una ap-prossimazione dipendente dai parametri e δ. La procedura di approssimazione consiste nel ritrovare il valore minimo tra tutti i contatori ai quali il topic in questione si riferisce o meglio in formule:
ˆct=min
j c(j, hj(t)) (20) E’ dimostrato quindi che il valore ˆct, stimato per mezzo dello sketch, sarà:
• sempre superiore o uguale al valore reale ˆct >= ct
• con una probabilità minima di 1 − δ sarà minore di cr+ |T| con|T| che, nel nostro caso, rappresenta il numero di topic sottoscritti nella rete. Per una trattazione più approfon-dita sulle performance della struttura si può consultare [6].
Effettuiamo quindi dei test sfruttando questa struttura dati paragonandola con l’utilizzo di un insieme di contatori senza perdita di informazione. In particolare riporteremo per ciascun test due grafici:
• in uno valutiamo quale è la differenza tra il conteggio approssimato per mezzo dello sketch e quello reale, ripor-tando anche l’errore assoluto tra i due.
66 dettagli implementativi
• nell’altro grafico potremo valutare come l’approccio stu-diato nel capitolo 3 si comporta utilizzando lo sketch, ri-porteremo infatti la distribuzione dei topic nella APT nel caso di utilizzo dello sketch e nel caso di utilizzo del con-teggio reale.
La figura24e la25mostrano il risultato delle simulazioni ef-fettuate utilizzando una struttura count min sketch di dimensioni rispettivamente 3x70, quindi con = 0.04 e δ = 0.05, e 3x100 con parametri con = 0.03 e δ = 0.05. La prima ci garantisce con una probabilità non inferiore a 0.95 che l’approssimazione non supererà il valore:
ˆct<= cr+ |T| = cr+ (0.04x400) = cr+ 16
mentre lo sketch di dimensione (3x10) ci garantisce un erro-re massimo pari a 0.025x400 = 10 semperro-re con una probabilità sempre non inferiore a 0.95.
Osservando i risultati ottenuti si può vedere come, utilizzan-do le strutture con dimensioni diverse, si ottiene effettivamente un miglioramento dei valori approssimati ottenuti rispetto a quelli reali e questo si può notare dalle figure 24a e 25a in cui la curva dell’errore assoluto si trova ad altezze diverse: un er-rore che mediamente si attesta intorno alle 30 unità nel primo caso e alle 20 nel secondo caso.
Questo errore più o meno costante non è sufficiente a ga-rantire il corretto andamento della distribuzione dei topic nel-le access point query, infatti dalnel-le figure 24b e 25b le distribu-zioni che risultano non sono uniformi ma seguono abbastanza fedelmente la forma della curva del numero di sottoscrizioni.
Il risultato ottenuto dimostra ancora una volta la sensibilità dei risultati rispetto alla variazione dei dati in ingresso e ov-viamente dipende dal fatto che per i topic a bassa popolarità è stato restituito un valore che presenta un errore più gran-de gran-del valore gran-del reale contatore stesso. Dunque è necessario riuscire a migliorare ulterioremente la stima dei valori e per farlo sarebbe necessario aumentare le dimensioni della struttu-ra dati ma un incremento porterebbe il numero dei contatori (pari a 300 nel caso dello sketch di dimensione 3x100) quasi ad eguagliare il numero di contatori necessario per effettuare una memorizzazione senza perdita (400).
In letteratura esistono tuttavia altre tecniche per cercare di migliorare ulteriormente il rendimento di questa struttura dati.
5.1 count min sketch 67 0 200 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 200 400 0 100 200 300 400 Topic ID Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 24: Simulazioni effettuate per valutare la validità dell’appros-simazione tramite count min sketch di dimensione 3x70. L’ambiente utilizzato prevede 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
0 200 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 200 400 0 100 200 300 400 Topic ID Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 25: Simulazioni effettuate per valutare la validità dell’appros-simazione tramite count min sketch di dimensione 3x100. L’ambiente utilizzato prevede 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
68 dettagli implementativi
5.1.1 Conservative Update
In [4] è stata ideata una procedura di ottimizzazione per i spectral bloom filter detta Minimal Increase che permette di rimuo-vere una parte dell’errore, in fase di inserimento, dovuto alle collisioni tra elementi. La stessa idea è stata poi applicata in [8] al count min sketch prendendo il nome di conservative update.
L’idea alla base di questa ottimizzazione è semplice: visto che il contatore con il valore minore è quello che fornisce il risultato più accurato, è chiaro che gli altri hanno assorbito l’incremento da parte di elementi la cui funzione hash ha restituito la stessa colonna. Per non aumentare ancora questo errore la procedu-ra di aggiornamento dei contatori incrementerà solamente il contatore con il valore minimo.
La procedura di aggiornamento ora prevede il calcolo del valore approssimato ˆct e successivamente:
c(j, hj(t))← max[c(j, hj(t)), ˆct+ 1] (21) ovvero l’aggiornamento avviene solo se il contatore contiene un valore più piccolo dell’approssimazione incrementata di 1.
Effettuiamo dei test analoghi a quanto già fatto nel caso di count min sketch semplice, per valutare l’eventuale miglioramen-to della stima del valore memorizzamiglioramen-to dai contamiglioramen-tori rispetmiglioramen-to al caso in cui non si è utilizzata alcuna strategia di ottimizzazione.
Le figure 26 e la 28 riportano i risultati dei test e dal lato dei valori approssimati, che rappresentano i contatori della fre-quenza dei topic nei messaggi di subscription advertising, vedia-mo come c’è stato un miglioramento apprezzabile. I topic a bassa popolarità hanno migliorato la stima di circa una decina di unità mentre i topic ad alta popolarità presentano un erro-re inizialmente nullo che poi va aumentando pian piano fino a stabilizzarsi.
La distribuzione dei topic nelle APT non riesce però ad otte-nere un miglioramento: l’uniformità non è ancora garantita e le curve ricalcano esattamente quelle ottenute senza applicare la tecnica del conservative update. L’unico inizio di flessione verso il valore medio di uniformità lo si può notare in figura27b, per il topic che presenta la maggiore popolarità.
Questa tecnica di ottimizzazione dello sketch non porta alcun beneficio al funzionamento del sistema poichè è incentrata sul miglioramento dei valori degli elementi più frequenti, mentre TERA accusa una sensibilità maggiore per i topic a più bassa
5.1 count min sketch 69 0 200 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 200 400 0 100 200 300 400 Topic ID Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 26: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch con conservative update di dimensione 3x70. Tests con 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
0 200 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 200 400 0 50 100 150 200 250 300 350 400 Topic ID Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 27: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch con conservative update di dimensione 3x100. Tests con 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione
70 dettagli implementativi
diffusione che invece rimangono approssimati con un elevato errore.
5.1.2 Count Mean Min
Un’altro metodo per poter migliorare l’approssimazione ef-fettuata tramite il count min sketch è quella di riuscire a valutare qual’è l’errore che coinvolge ciascun contatore per poi poterlo eliminare in fase di approssimazione. Esistono due tecniche che sfruttano questo approccio: la prima è il least squares estimation mentre la seconda è detta count mean min.
In [14] viene presentato il metodo least squares estimation che cerca di migliorare l’accuratezza della riscotruzione del valore originale attraverso la risoluzione di un sistema lineare. Il si-stema lineare cerca di valutare qual’è la quantità di rumore ge-nerato dagli altri elementi rispetto ad uno di riferimento, quin-di per poter avere maggiore precisione è necessario mettere a sistema la maggior quantità possibile di elementi. Su questo metodo non ci soffermeremo a causa dell’elevato carico compu-tazionale da svolgere per ottenere risultati di un certo livello di precisione.
L’altra soluzione presentata in [7] è il count mean min che uti-lizza una modalità più leggera per stimare il valore approssima-to. Per il contatore x/j, h(t)), l’errore che lo affligge è stimato pensando a tutti gli altri contatori sulla stessa riga, come a delle variabili aleatorie indipendenti che seguono la stessa distribu-zione dell’errore. Quindi la valutadistribu-zione è effettuata mediando il valore di tutti quanti gli altri contatori. Il calcolo del rumore può essere così effettuato per ciascuna riga j:
nj = S − c(j, hj(t))
w − 1 (22)
dove S rappresenta il numero degli aggiornamenti che sono stati effettuati nello sketch mentre w è la larghezza dello stes-so. Una volta ottenuto il rumore lo si sottrae al reale valore del contatore e si dovrà scegliere se prendere la media oppu-re la mediana dei valori risultanti. E’ necessario consideraoppu-re la possibilità che il valore restituito sia negativo oppure che sia superiore al quello dato dallo sketch standard, in entrambi i casi si dovrà restituire come approssimazione il valore della struttura dati senza ottimizzazioni. La figura 28riporta i risul-tati della simulazione effettuata utilizzando questo approccio di stima dell’errore. La curva che rappresenta i valori restituiti
5.1 count min sketch 71 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 Topic ID Fr equenza Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 28: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count mean min sketch di dimensione 3x100. L’ambiente di simulazione prevede 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
72 dettagli implementativi
dai contatori approssimati dei topic (figura28a) è molto vicina al comportamento della curva dei contatori reali ed infatti il massimo errore assoluto che intercorre tra le due è dato da 5 unità. Tutto questo ha ovviamente un risvolto positivo sull’an-damento della distribuzione dei topic nelle tabelle degli access point (figura 28b) che possiamo constatare essere la più vicina, tra tutte le simulazioni fin qui effettuate, alla distribuzione che si otterrebbe senza utilizzare tecniche di approssimazione dan-do quindi una parvenza di uniformità al risultato ottenuto. E’ possibile far di meglio.
5.1.3 Lossy conservative update
Poichè tutte le tecniche di miglioramento del count min sketch sono incentrate sul miglioramento dei risultati degli elemen-ti più frequenelemen-ti, il risultato che si otelemen-tiene non è mai del tutto soddisfacente. In [9] viene presentata una tecnica che permet-te di migliorare anche la stima degli elementi meno frequenti basata sulla tecnica del lossy counting. Lossy counting letteral-mente contare con perdita consiste nel suddividere il flusso di informazioni in finestre di una certa dimensione e, alla fine di ciascuna, decrementare alcuni contatori di una unità.
L’ottimizzazione proposta è una variante del conservative up-date presentato nella sezione 5.1.1 e consiste nel dividere lo stream di dati in finestre pari alla dimensione globale dello sketch (wxd) e al termine di ciascuna finestra effettuare il de-cremento dei contatori.
Decrementare i contatori può essere fatto seguendo diverse politiche definite di seguito:
lcu-all è il caso più semplice che applica alla lettera il lossy counting decrementa tutti quanti i contatori di una unità, a patto che non siano vuoti. Dunque se c(j, z) > 0 allora:
c(j, z) = c(j, z) − 1
lcu-1 questa p la prima politica che cerca di ridure il rumore inserito nei contatori degli elementi di più bassa frequen-za e lo fa cercando di azzerare i contatori che sono riusciti a mantere il valore unitario nell’arco temporale indotto dalla finestrea. In altre parole se c(j, z) > 0 e c(j, z) <= 1 allora sarà effettuata la riduzione c(j, z) = c(j, z) − 1; lcu-ws questo approccio è una versione più permissiva di
5.1 count min sketch 73 non superano il numero delle finestre riempite nello stream. Se c(j, z) > 0 e c(j, z) <= windowsID allora c(j, z) = c(j, z) − 1;
lcu-sws l’ultimo approccio è una versione intermedia tra LCU-1 E LCU-WS che decrementa i contatori dello sketch in maniera più conservativa. La formula di aggiornamento è: se c(j, z) > 0 e c(j, z) <= d√windowsIDe e c(j, z) = c(j, z) − 1;
Presentiamo tutti i test realizzati utilizzando ognuna delle politiche di decremento dei contatori.
Analizzando passo passo i risultati, possiamo notare che già adottando la politica LCU-ALL (figura 29), otteniamo un mi-glioramento rispetto al solo utilizzo del conservative update.
I valori restituiti dallo sketch presentano un basso margine di errore ma, diversamente da quanto fin’ora visto, sono i topic a bassa popolarità a godere di una migliore stima, mentre i topic ad alta popolarità sono sotto-stimati. Questo, in generale, in-fluisce positivamente sulla distribuzione ma poichè i topic ad alta popolarità sono approssimati restituendo un valore che è inferiore a quello reale, la loro probabilità di inserimento nel-le acces point tabnel-le è nel-leggermente superiore a quanto dovrebbe essere in un sistema senza approssimazione. Vediamo infatti la flessione della curva (figura 29b) nella parte in cui vi sono i topic ad alta frequenza di sottoscrizione.
Diverso è il caso dell’approccio LCU-1 (figura 30) che non dimostra un buon rendimento: entrambe le distribuzioni infatti sono analoghe a quelle della figura 28 dove viene utilizzato il conservative update senza nessuna tecnica di decremento. La spiegazione è dovuta al fatto che la politica LCU-1 è troppo rigida riguardo i contatori da decrementare, così che raramente riesce ad essere applicata.
Nella figura32possiamo vedere il risultato dell’utilizzo della SWS che abbiamo detto essere più permissiva della LCU-1. Questo infatti viene dimostrato dai risultati che presentano una distribuzione dei topic nelle APT ancora non uniforme, ma con un picco meno accentuato della politica LCU-1. Anche in questo caso il decremento viene effettuato solo in pochi casi e questo porta a non avere alcuna sottostima per i topic a bassa frequenza di sottoscrizione, mentre per quelli a bassa frequen-za il miglioramento è esiguo e non riesce a portare un reale beneficio.
74 dettagli implementativi 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 Topic ID Fr equenza Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 29: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch con lossy conservative update politica LCU-ALL di dimensione 3x100. L’ambien-te di simulazione prevede 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
5.1 count min sketch 75 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 Topic ID Fr equenza Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 30: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch con lossy conservative update polica LCU-1 di dimensione 3x100. L’ambiente di simulazione prevede 2.000 cicli di elaborazione, 1.000 no-di, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
76 dettagli implementativi 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 Topic ID Fr equenza Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 31: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch lossy conservative upda-te politica LCU-WS di dimensione 3x100. L’ambienupda-te di simulazione prevede 2.000 cicli di elaborazione, 1.000 no-di, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
5.1 count min sketch 77 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza Approssimata Reale Errore
(a)Report dei contatori dei topic
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 Topic ID Fr equenza Approssimata Reale Sottoscrizioni
(b)Frequenze topic nelle APT
Figura 32: Risultato simulazioni per valutare la validità dell’appros-simazione tramite count min sketch con lossy conservative update politica LCU-SWS di dimensione 3x100. L’ambien-te di simulazione prevede 2.000 cicli di elaborazione, 1.000 nodi, 400 topic, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con s = 0, 7
78 dettagli implementativi
Infine con la politica LCU-WS (figura31) otteniamo il giusto compromesso tra tutte le precedenti perchè riesce a non sotto-stimare i topic molto popolari e allo stesso tempo, ad effettuare il giusto numero di decrementi, per permettere di migliorare la stima dei contatori dei topic con poca popolarità, come si può vedere dalla figura31a. Nella figura31bvediamo come la distribuzione dei topic nelle APT si avvicina molto a quella otte-nuta con contatori non approssimati e la deviazione introdotta può essere considerata più che accettabile per il funzionamento dell’intero sistema distribuito.
6
C O N C L U S I O N I
Lo scopo di tutta la nostra tesi è quello di affrontare la pre-senza di comportamenti bizantini nell’ambito di un sistema di-stribuito. La difficoltà di riuscire a dialogare con questo tipo di comportamenti è notevole poichè non è determinale a priori quale sarà il modo di agire di un nodo bizantino.
Si è concentrata l’attenzione su due aspetti in particolare su cui TERA potrebbe essere vulnerabile, ovvero la possibilità di rigettare messaggi e la possibilità di alterare le popolarità comu-nicate dai nodi. Il primo problema non ha causato grandi diffi-coltà visto che era già insita nel modello una certa resistenza a comportamenti di questo tipo.
Per l’alterazione delle popolarità abbiamo proposto vari ap-procci e di questi uno in particolare si è verificato essere più efficace: l’utilizzo di un doppio set di dati dai quali è possibi-le effettuare la scelta migliore. La fattibilità di questo sistema dipende tuttavia da un fattore in particolare: che il numero me-dio di messaggi di subscription advertising sia simile per tutti i nodi. Sarebbe necessario quindi limitare la capacità di invio di ciascun singolo nodo rendendola quantomento paragonabile tra tutti i nodi, a questo scopo si potrebbe utilizzare un sistema di virtual currency da poter spendere tra nodi per l’invio dei messaggi di advertising, nel momento in cui un nodo volesse inviare ad un’altro nodo un messaggio e avesse esaurito il pro-prio credito, dovrebbe attendere che qualche altro nodo invii ad esso dei messaggi, ricevendo del credito.
Un altro sistema, sempre basato sull’uso di contatori, potreb-be essere quello di utilizzare il dato di frequenza come se fosse un valore di popolarità, questo tuttavia non funzionerebbe se le sottoscrizioni fossero dinamiche. Per ovviare questo incon-veniente si dovrebbero resettare tutti i contatori dopo un certo intervallo di tempo, che dovrebbe dipendere dalla stima del numero totale di nodi costituenti la rete di comunicazione; in questo modo la probabilità che due topic con la stessa popolari-tà, ma sottoscritti in istanti temporali totalmente differenti, sia simile, dovrebbe essere garantita dal reset di tutti i contatori.
Il lavoro da compiere per riuscire a rendere TERA bizantyne resilient ancora non è concluso: ci sarebbe ancora da
ragiona-80 conclusioni
re su come traslare il modello sincronizzato, utilizzato per la simulazione, in uno ad eventi, simile ad un ambiente reale ed ancora di ragionare sugli altri problemi che sono risultati dal-l’analisi effettuata nella sezione 2.4, come ad esempio evitare, con una certa probabilità, che i nodi bizantini siano tra quelli