Nel modello utilizzato fino ad ora nel corso di questo capi-tolo, i nodi bizantini hanno come unico comportamento quello di rigettare la richiesta di ricerca di un access point, introdu-cendo un malfunzionamento gestibile attraverso l’incremento del numero di ricerche concorrenti anche se viene considerata equiprobabile la presenza di un determinato topic rispetto ad un altro nelle APT.
Un host malevolo non metterà in atto solamente un tipo di strategia per cercare di rendere inutilizzabile tutto il sistema, per questo è utile vedere quale sarà il comportamento globale introducendo anche la capacità, per un malintenzionato, di po-ter modificare, in maniera arbitraria, la popolarità dei topic che vengono inviati nei messaggi di subscription advertising.
Il risultato è che in questo modo non è più garantita l’unifor-mità della distribuzione dei topic all’interno delle APT e non è più possibile utilizzare la formula (16) per avere una stima, quindi ci limiteremo ad effettuare delle valutazioni empiriche
60 ricerca degli access point
sulla base dei risultati dei test simulazioni effettuati.
0 2 4 6 8 10 12 14 16 18 20 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Numero di ricerche in parallelo
Pr
obabilità
di
successo
rigetto richiesta e variazione popolarità solo rigetto richiesta lookup
variazione sola popolarità nessun nodo bizantino
Figura 20: Grafico in cui viene mostrata il rapporto delle ricerche an-date a buon fine dove i nodi bizantini modificano sia la popolarità negli advertisment che scartano le richieste di ricerca di access point, confrontato con i dati in cui non si modifica la popolarità, non si effettua scarto e non è presente alcun comportamento bizantino. Per ciascun nu-mero di ricerche in parallelo con un TTL pari a 10, so-no stati effettuati 10 test e se ne riporta la media. La configurazione di test è la stessa della Figura19
Nella Figura20sono stati inseriti i risultati delle elaborazioni effettuate per verificare l’andamento della probabilità al variare del numero di ricerche in parallelo con diverse configurazioni dell’ambiente di test dove la probabilità di successo è stata cal-colato effettuando più test per volta, eseguendo il rapporto tra il numero di richieste andate a buon fine e quelle totali.
La curva che rappresenta la probabilità di portare a termine la richiesta in maniera corretta, nel caso in cui non sia presente
4.2 effetti della non uniformità nella apt 61 alcun nodo bizantino, è ovviamente un upper bound e già dopo 4ricerche contemporanee assume un valore di probabilità abba-stanza vicino alla certezza. La curva che rappresenta la stessa probabilità nel caso in cui l’unico comportamento malevolo è quello della variazione della popolarità presenta invece un li-mite che si attesta intorno ad un valore di circa 0.85 che pur aumentando il numero di richieste contemporanee non viene mai valicato. 0 2 4 6 8 10 12 14 16 18 20 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Numero di ricerche in parallelo
Pr
obabilità
di
successo
rigetto richiesta e variazione popolarità solo rigetto richiesta lookup
variazione sola popolarità nessun nodo bizantino
Figura 21: Grafico in cui viene mostrata la probabilità di trovare un access point per un topic nel caso in cui è stato usato l’ap-proccio della sezione 3.3 per mitigare la variazione della popolarità. Ciascuna curva rappresenta un diverso com-portamento da parte dei nodi bizantini. Il TTL di ciascuna ricerca è sempre pari a 10 mentre tutti gli altri parametri sono uguali a quelli di Figura19.
Guardando il comportamento ottenuto nel caso in cui tutti i nodi malevoli cestinino le richieste di lookup e contemporanea-mente alterino la popolarità inviata nei messaggi di advertising
62 ricerca degli access point
invertendola, si può vedere come soffra della combinazione di entrambi i componenti di malfunzionamento ovvero la proba-bilità sale rapidamente fino ad incontrare il vincolo dovuto al-la mancanza di omogeneità delal-la distribuzione dei topic nelle APT.
Poiché abbiamo dedicato tutto il precedente capitolo 3 a cer-care una soluzione per mitigare il problema della non unifor-mità della distribuzione dei topic, possiamo ora utilizzarne i risultati per ridurre il disagio causato dai nodi bizantini e quin-di aumentare la probabilità con la quale un nodo, nel momento in cui produca una richiesta di APT lookup, ottenga un risultato valido. Il risultato atteso è ovviamente uguale a quello ottenuto se non ci fosse stata alcuna alterazione della popolarità poiché come già visto il meccanismo illustrato nella sezione.
La Figura21 riporta il risultato del test che conferma quanto preventivato, le curve si sovrappongono a coppie perché la dif-ferenza è data solamente dallo scarto della richiesta di un mes-saggio di lookup da parte di un nodo bizantino o meno, mentre utilizzando il sistema di mitigazione, non vi è alcuna differenza se i nodi malevoli alterino o meno la popolarità dei topic.
5
D E T TA G L I
I M P L E M E N TAT I V I
Nella sezione 3.2.2 abbiamo annoverato tra i vari problemi della stima della popolarità tramite frequenza dei messaggi di advertising anche quello di doversi preoccupare di una mole di dati linearmente proporzionale rispetto al numero di topic presenti nel sistema.
Per ciascun topic del quale un nodo ha notizia, tramite un messaggio di subscription advertising, abbiamo detto che è ne-cessario instanziare un contatore che andrà incrementato ogni volta che nei pacchetti sarà presente il relativo topic e, pensan-do ad un sistema publish/subscribe costituito da un numero molto elevato di topic e nodi; questo richiederebbe una quantità consistente di memoria.
E’ necessario quindi mettere in atto una serie di politiche per la compressione dei dati il cui scopo è quello di riuscire ad alle-viare questo problema. Tra le prime alternative da vagliare c’è quella di riferirsi ad un sistema di compressione con perdita oppure ad uno lossless, in cui la differenza è ovviamente riferita alla possibilità di perdere informazioni all’atto della compres-sione, nel primo caso, oppure di non perderne, nel secondo. Tra le due strade quella della compressione con perdita è la più interessante da seguire e ci riporta ad un problema già molto conosciuto.
Possiamo infatti considerare l’insieme dei messaggi di adver-tising sottoposti da un nodo come uno stream di dati che con-tinuamente deve essere elaborato per poter essere parte attiva del sistema di comunicazione. Il nostro stream è costituito da una sequenza di topic che si susseguono nel tempo e che vanno ad incrementare un contatore associato ad ognuno di essi, que-sto di fatto è il modello di data streaming cash register codificato in [17].
In questo tipo di modello abbiamo un flusso di dati che con-tiene un elenco di topic, e per ciascun topic un contatore ct(i) che contiene, per ciascun istante temporale i, il numero di volte in cui il topic t era presente nello stream fino all’istante i.
La stessa cosa può essere vista in maniera incrementale: ct(i) = ct(i − 1) + 1 (17)
64 dettagli implementativi
t1 t2 t1 t3
i
Figura 22: Uno stream di topic
se nell’istante temporale i viene incontrato un topic t questo va ad incrementare il corrispondente contatore ct di una unità. Abbiamo quindi un insieme di contatori ognuno referente per un topic tx e il dato che abbiamo necessità di ottenere da questi contatori è proprio il valore attuale: questa operazione è anche detta point query.
In letteratura sono presenti diverse strutture dati che han-no lo scopo di permettere di rispondere ad operazioni di point query con una determinata approssimazione a vantaggio del fatto che la quantità di memoria necessaria è fissabile a priori. Queste strutture dati sono dette sketch poiché restituiscono dei valori che sono una ”bozza“ ovvero che non sono esattamente quelli reali, ma ci si avvicinano con una certa probabilità.
La struttura dati che offre migliori performance sia dal punto di vista dello spazio necessario alla memorizzazione che dal la-to dell’approssimazione dei valori restituiti è il count min sketch illustrato in [5].