Riuscire ad effettuare una valutazione dei dati trasmessi da altri nodi non è un compito semplice se per riuscirci si utiliz-zano valori prelevati da terzi che sono comunque soggetti agli stessi errori dei dati originali.
Se si potesse giungere ad ottenere le stesse informazioni par-tendo da altri dati il problema sarebbe in parte risolto. In parti-colare l’ottimo sarebbe riuscire ad ottenere il dato di popolarità basandosi esclusivamente sul proprio servizio di size estimation e non su quello degli altri nodi anche se è chiaro che le in-formazioni, di cui si ha necessità per calcolare la frequenza di sottoscrizione di un topic, dovranno per forza provenire dagli altri nodi della rete.
Gli unici dati che possono rivelare informazioni sulle sotto-scrizioni sono i messaggi di subscription advertising dai quali normalmente viene preso il valore di popolarità inserito dal mittente. Anziché considerare questo valore direttamente vo-gliamo provare a sfruttare semplicemente il numero di volte in cui un topic compare all’interno di questi messaggi mantenen-do un contatore per ogni topic incontrato.
Prima di tutto è opportuno verificare quale è la curva risul-tante dal conteggio dei topic all’interno dei messaggi di adverti-sing per vedere se propone dei dati utili. In Figura 12il grafico mostra come la frequenza media con il quale i topic compaiono all’interno dei messaggi ricalca fedelmente la curva della popo-larità di sottoscrizione di un topic, sia nel caso in cui vengono effettuati 1000 cicli di elaborazione della simulazione, sia nel caso in cui ne vengano effettuato 2000 cicli.
A questo punto rimane il problema di come utilizzare questi dati per fornire il giusto valore di probabilità da utilizzare in se-de di inserimento se-dei topic nella Access Point Table. Non
volen-3.2 valutazione locale della popolarità 45 0 50 100 150 200 250 300 350 400 0 100 200 300 400 500 Topic ID Fr equenza Popolarità topic 1000cicli elaborativi 2000cicli elaborativi
Figura 12: Frequenza di comparizione dei topic nei messaggi di sub-scription adverstising effettuanto 1000 e 2000 cicli elaborati-vi. L’ambiente di test è costituito da 1.000 nodi, 400 topic, dimensione del sample pari a 10 ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7
do utilizzare altri dati all’infuori di quelli forniti dal conteggio della frequenza di visione di un topic le possibilità non sono molte e consistono nello sfruttare i valori minimi e massimi della distribuzione di frequenza.
I vari approcci sono:
massimo consiste nel prelevare il massimo tra i contatori che memorizzano la presenza dei topic nei messaggi di adver-tising e di riscalare tutti i contatori tramite questo mas-simo. Per ottenere una probabilità maggiore con i topic poco frequenti e viceversa sottraiamo al valore unitario il rapporto prima formato, indicando con ct il valore del contatore per il topic t abbiamo:
pmax= 1 − ct max
(8)
somma è dato dal valore della somma di tutti i contatori dei to-pic utilizzato nella stessa identica modalità dell’approccio
46 variazione della popolarità
massimo e costituisce idealmente una sorta di integrazio-ne dei dati ottenuti dai calcolatori.
psum= 1 − ct sum
(9)
minimo una volta trovato il minimo tra tutti i contatori deputa-ti alla memorizzazione della frequenza dei topic nei mes-saggi, lo utilizziamo come divisore per il rapporto con i vari contatori. Il ragionamento alla base è che in questo modo potremmo trovare un valore che si accosti in asso-luto al dato di popolarità, quindi una volta calcolato il rapporto lo si utilizzerà come se fosse la frequenza esatta di sottoscrizione dei topic:
pmin = c1 t min = min ct (10) 0 50 100 150 200 250 300 350 400 0 0.2 0.4 0.6 0.8 1 Topic ID Pr obabilità Approccio massimo Approccio somma Approccio minimo Probabilità corretta
Figura 13: Probabilità approcci minimo, massimo e somma nell’uso dei contatori di frequenza dei topic nei messaggi di adver-tising. L’ambiente di test è costituito da 1.000 nodi, 400 to-pic, dimensione del sample pari a 10 ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7
3.2 valutazione locale della popolarità 47 Per verificare l’efficacia di questi approcci li confronteremo con la probabilità che si otterrebbe se usassimo la reale fre-quenza di sottoscrizione. Nella Figura 13 i risultati indicano chiaramente come il criterio minimo è quello che più ricalca il corretto uso della probabilità mentre l’approccio somma è il più lontano ed altro non è che una versione scalata di quello massimo. 0 50 100 150 200 250 300 350 400 0 100 200 300 400 500 Topic ID Fr equenza TERA originale Approccio massimo Approccio minimo
Figura 14: Confronto tra le distribuzioni dei topic nelle APT utiliz-zando l’approccio minimo, massimo e originale nell’uso dei contatori di frequenza dei topic nei messaggi di adver-tising. L’ambiente di test è costituito da 1.000 nodi, 400 to-pic, dimensione del sample pari a 10 ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7
Non rimane altro da fare che implementare queste strategie (escludendo quella che utilizza la somma) per vedere se rical-cano i comportamenti ottenuti valutando le probabilità che ge-neravano. In Figura 14 infatti l’utilizzo del criterio del mini-mo genera una distribuzione dei topic nelle access point table realmente uniforme e lo si può notare confrontandola con il funzionamento standard di TERA. Questo lascia ben sperare nell’utilizzo di questo sistema per contrastare la variazione ar-bitraria dei topic da parte dei nodi bizantini e nell’utilizzo di questi dati per confrontarli con le informazioni inviate.
48 variazione della popolarità
Prima di poter dire di aver raggiunto l’obiettivo è necessario effettuare una analisi formale dei risultati ottenuti per confer-mare o meno quanto ottenuto.
3.2.1 Valutazione del criterio minimo
Tutti gli approcci riportati nella sezione3.2utilizzano dei con-tatori per memorizzare il numero di volte in cui un certo to-pic compare all’interno dei messaggi di subscription advertising inviati ad uno stesso nodo e quindi per riuscire ad effettua-re una valutazione coreffettua-retta dobbiamo prima di tutto effettuaeffettua-re una stima di questo valore.
Prendiamo in considerazione il topic t che presenta una fre-quenza di sottoscrizione pari a ft: in ogni ciclo di elaborazione vi saranno quindi ftnodi che invieranno un messaggio di adver-tising contenente il topic t. In ogni ciclio un nodo invia lo stesso messaggio di subscription advertising ad un numero di nodi, pari ad n, estratti a caso in maniera uniforme per mezzo del servi-zio di peer sampling e quindi ogni nodo ha uguale probabilità di essere il destinatario di tale messaggio o meglio la probabi-lità è pari a n
N dove N è il numero totale dei nodi partecipanti nella rete publish/subscribe. Se consideriamo che in ogni ciclo di elaborazione l’invio di questi messaggi è indipendente dai precedenti invii, allora il valore atteso è:
E(ct) =n N
ft(t − t0) (11)
dove t0indica il ciclo dal quale è iniziato l’invio dei messaggi di advertising per il topic in questione e t è il ciclo corrente. Come al solito valutiamo la correttezza della stima confrontandola con il valore medio reale prelevato dai contatori.
I valori stimati e quello reale si sovrappongono esattamente come si vede dalla Figura 15 e questo indica ovviamente la correttezza del calcolo. Possiamo quindi continuare la nostra valutazione dei risultati ottenuti tramite l’utilizzo della formula (10) sfruttando questa volta il valore stimato nella formula (11). Il rapporto tra la stima dei contatori tra due topic t1 e t2, dove t2 è il topic che rappresenta il minimo, è data da:
3.2 valutazione locale della popolarità 49 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 Topic ID Fr equenza TERA originale Stima
Figura 15: Confronto tra il conteggio reale e quello atteso del numero di volte in cui un topic è contenuto all’interno dei messag-gi di advertising destinati ad uno stesso nodo. L’ambiente di test è costituito da 1.000 nodi, 2.000 ciclio di elabora-zione, 400 topic, dimensione del sample pari a 10 ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7 E(ct1) E(ct2) = n N ft1(t − t01) n N ft2(t − t02) = = n N ft1(t − t01) n N ft2(t − t02) = ft1(t − t01) ft2(t − t02) (12)
Per riuscire ad ottenere una distribuzione uniforme dei topic nelle APT utilizzando il criterio del minimo, il rapporto in for-mula (12) dovrebbe restituire il valore corretto di popolarità e questo è ottenibile solo se le seguenti condizioni sono rispettati:
1. il valore della popolarità del topic al denominatore deve essere unitario (ft1 = 1)
2. i due topic tra i quali viene fatto il rapporto devono essere stati sottoscritti nello stesso istante o l’invio dei
messag-50 variazione della popolarità
gi di advertising deve essere iniziato nello stesso ciclo di elaborazione (t01 = t02)
Applicando queste modifiche la formula(12) infatti diventa: E(ct1) E(ct2) = ft1(t − t01) ft2(t − t02) = = ft1 (t − t0) 1 (t − t0) = ft1 (13)
In un ambiente reale questi vincoli non sono rispettabili poi-chè è impensabile pensare di vincolare la sottoscrizione di tutti i topic in un unico istante temporale ed anche che vi sia ob-bligatoriamente un topic sottoscritto da un solo nodo, dunque neanche questo approccio è utilizzabile.
3.2.2 Stima della frequenza di sottoscrizione
Tutti i tentativi precedenti di utilizzo dei dati memorizza-ti localmente non hanno avuto buon esito per ragioni diver-se. In questa sezione tenteremo di stimare il valore corretto di popolarità di un topic utilizzando proprio questi dati.
Riprendiamo il discorso del valore atteso calcolato in formu-la11che stimava il numero di volte in cui un certo topic veniva visto nei messaggi di advertising da parte di uno stesso nodo. Questa stima si è rivelata correta come verificato in Figura 15
quindi è possibile intercambiare il valore stimato tramite con-siderazioni probabilistiche (E(ct)) con quello reale constatato tramite la sperimentazione(ct), il che ci permetterebbe di inver-tire la formula11per estrarre il valore di popolarità di un certo topic: ft= N n ct (t − t0) (14)
Il valore di popolarità stimato tramite la formula quì indicata dovrebbe essere utilizzato intercambiabilmente con quello rea-le per poter generare la probabilità utilizzata per l’inserimento nelle tabella degli acces point. L’utilizzo di questo metodo di sti-ma della popolarità dovrebbe generare una distribuzione uni-forme verificabile in Figura 16dove è stata effettuata una simu-lazione utilizzando la formula 14per il calcolo della popolarità. Lo scostamento dalla distribuzione ideale è minimo e si può vedere come la curva è suddivisa in due parti in maniera del tutto analoga a quanto già incontrato ad inizio capitolo in Figu-ra 6. Questo approccio quindi fornisce lo stesso risultato che si
3.2 valutazione locale della popolarità 51 avrebbe se si utilizzasse un algoritmo distribuito di conteggio della popolarità che introduce un certo errore di valutazione di cui abbiamo già parlato ad inizio capitolo.
0 50 100 150 200 250 300 350 400 50 100 150 200 250 300 Topic ID Fr equenza TERA originale Utilizzo popolarità stimata
Figura 16: Distribuzione dei topic nelle APT popolate utilizzando la popolarità reale e quella stimata attraverso la formula 14. L’ambiente di test è costituito da 1.000 nodi, 2.000 ciclio di elaborazione, 400 topic, dimensione del sample pari a 10 ed una distribuzione delle sottoscrizioni che segue unazipf law con parametro 0, 7
Con questo approccio che sembra essere il più corretto tra tut-ti quelli presentatut-ti si possono gestut-tire anche topic sottoscrittut-ti in diversi istanti temporali memorizzando per ciascuno il tempo dal quale si è incontrato per la prima volta il topic in questione. Anche questo approccio ha dei punti da chiarire:
• se il numero totale dei nodi non è conosciuto a priori allo-ra è necessario stimarlo tallo-ramite qualche algoritmo distri-buito
• tutti i nodi del sistema debbono usare la stessa dimensio-ne per il campiodimensio-ne di nodi al quale inviare il subscription advertising
52 variazione della popolarità
• i cicli di elaborazione utilizzati nella simulazione fanno quindi riferimento ad un modello temporale sincronizza-to
• ciascun nodo dovrebbe memorizzare informazioni sulla frequenza di tutti i topic contenuti nei messaggi di adver-tising e la quantità di informazioni potrebbe essere molto grande. Affronteremo questo discorso nel capitolo5