Il problema che è stato evidenziato riguarda quindi la non uniformità della distribuzione dei topic nelle APT causata dal-la presenza di utenti bizantini che iniettano all’interno dei mes-saggi di advertising popolarità diverse da quelle corrette. Nel-l’implementazione standard di TERA il nodo che riceve queste informazioni assume che i dati trasmessi siano corretti e non effettua alcun controllo di veridicità. Per ovviare a questo conveniente è necessario effettuare una valutazione sui dati in-viati da altri nodi della rete, per riconoscere se sono frutto di manomissione oppure se sono coerenti con il sistema.
Nel modello analizzato fino ad adesso è sempre stato implici-to il fatimplici-to che il servizio di stima della popolarità su cui poggia TERA memorizza solo informazioni sui topic che il nodo stesso ha collocato all’interno della subscription table, quindi se si voles-se confrontare il valore di frequenza di sottoscrizione inviato da un nodo con quello ottenuto dal proprio size estimation service per valutare la bontà del dato, non sarebbe sempre possibile.
3.1 mediazione distribuita della popolarità 39 una indagine distribuita per cercare conferma dei dati ottenuti tramite il subscription advertising.
3.1.1 Uso delle Subscription Table
Per ciascun topic del quale si vuole avere conferma si dovreb-bero interpellare altri nodi della rete di comunicazione chieden-do a ciascuno se ha censito nella propria subscription table il to-pic di interesse ed in caso positivo di rispondere inviando il corrispondente valore di popolarità. Maggiore è il numero di nodi ai quali si chiederà tale valore e maggiore sarà la possibi-lità di trovarne uno che ha a disposizione il dato cercato, ma esiste un limite superiore al numero di richieste derivante dal fatto che il nodo è a conoscenza di un numero limitato di nodi fornitogli dal servizio di campionamento.
Con questo tipo di approccio esistono due problemi distinti: il primo è che esiste la possibilità che tra i nodi ai quali viene effettuata questa richiesta vi siano anche nodi bizantini mentre l’altro deriva dalla probabilità di trovare un nodo che abbia sottoscritto il topic di interesse.
Se volessimo valutare la probabilità di questo ultimo proble-ma potremmo associarlo al noto probleproble-ma di estrazione senza restituzione di biglie da un’urna. In pratica quando un nodo sceglie a caso altri nodi della rete e li interpella chiedendogli se hanno sottoscritto il topic t, sta appunto effettuando una estra-zione senza restituestra-zione da un urna dove le biglie colorate sono i nodi della rete. Se vogliamo continuare a sfruttare questa as-sociazione possiamo collegare le biglie rosse a quei nodi che hanno sottoscritto il topic t mentre quelle di altro colore a tutti gli altri, ricordando banalmente che se un topic ha popolarità f allora vi saranno f nodi che avranno sottoscritto tale topic.
La probabilità di trovare esattamente x nodo che abbia sotto-scritto il topic t selezionandone n a caso, grazie al fatto che il sottostante peer sample service restituisce un campione uniforme, è la seguente, dove f è la popolarità del topic ed N è il numero totale di nodi nel sistema:
P(x) = f x N − f n − x N n (6)
A questo punto possiamo utilizzare la (6) per avere la proba-bilità che scegliendo n nodi almeno 1 contenga il topic t:
40 variazione della popolarità p = x X i=1 P(x) (7)
Traducendo tutto questo in numeri supponendo che un host scelga a caso 10 nodi e che le sottoscrizioni dei topic seguono una distribuzione esponenziale con parametro 0.7, vediamo che è improbabile trovare un topic con popolarità bassa ( probabi-lità di 0.01 ) ed anche anche per il topic con maggiore popola-rità la probabilità è bassa (circa 0.45). Tutto questo lascia poca possibilità nell’utilizzo di questo approccio.
0 50 100 150 200 250 300 350 400 0 10 20 30 40 50 60 70 80 Topic ID Fr equenza 0 0.2 0.4 0.6 0.8 1 Pr obabilità Frequenza di sottoscrizione Probabilità di successo
Figura 9:Grafico che mostra la probabilità di trovare un nodo che abbia sottoscritto un certo topic. Nelle ascisse possiamo vedere il topic da cercare, la curva azzurra mostra la popo-larità del topic mentre quella magenta riporta la probabilità di trovare quel topic effettuando una ricerca distribuita su un campione di 10 nodi.
3.1.2 Uso delle Acces Point Table
Il precedente approccio non ha trovato positiva applicazio-ne a causa della scarsa probabilità di trovare le informazioni di interesse nelle subscription table, ma esiste ovviamente una
3.1 mediazione distribuita della popolarità 41 struttura dati che serve proprio per distribuire uniformemente queste informazioni ed è ovviamente la access point table.
Seguendo sempre l’approccio della ricerca distribuita potrem-mo chiedere al nodo contattato di rispondere utilizzando la pro-pria APT, dove la probabilità di poter trovare informazioni sul topic di interesse dovrebbe essere sicuramente maggiore rispet-to all’uso delle sotrispet-toscrizione, anche se, a causa della presenza di host malevoli nella rete, la distribuzione dei topic non sarà quasi sicuramente uniforme.
Il dato a cui siamo interessati è ovviamente la popolarità di un topic e a causa della mancanza di tale informazioni nella APT, deve essere effettuata una modifica che consenta di me-morizzare anche tale informazione alla ricezione di un messag-gio di subscription advertising. Una volta ricevuti i dati da più di una sorgente il nodo dovrebbe mediarli secondo vari possibili approcci: media, mediana oppure, estraendo i valori caratteri-stici della popolazione ricevuta, selezione casuale basata su di una distribuzione probabilistica.
Andando più a fondo nella questione sorge un problema, di cui tra l’altro era vittima anche l’approccio nella sezione 3.1.1, riguardante i topic sottoscritti esclusivamente da nodi bizantini che, nell’inviare i messaggi di subscription advertising, trasmet-tono sempre popolarità non coerenti con quella reale. La cosa è facilmente chiarificabile prendendo come riferimento un topic sottoscritto esclusivamente da un solo nodo malevolo che invia i propri messaggi di advertising con popolarità errata in tut-ta la rete. Gli hosts che riceveranno il messaggio utilizzeranno la popolarità comunicatagli per inserire il topic nella propria APT ed inoltre, seguendo il nuovo approccio, memorizzeranno al suo interno anche il dato di popolarità stesso. Essendo il nodo mittente il solo ad aver sottoscritto il topic, l’unico dato distribuito nell’intero sistema sarà quello di frequenza errata, che sarà anche l’unico valore ritrovato nell’effettuare l’indagine globale.
C’è da chiedersi se è utile preoccuparsi di mantenere una distribuzione uniforme dei topic nelle APT considerando an-che questi topic non sottoscritti da alcun nodo corretto. Nel caso in cui riteniamo inutile effettuare considerazioni su topic sottoscritti interamente da nodi bizantini è possibile produrre risultati in cui questi dati vengano esclusi.
Abbiamo effettuato quindi dei test che implementavano que-sto tipo di indagine distribuita basata sull’uso delle APT i cui risultati possono essere apprezzati in Figura 10 e 11 in cui è
42 variazione della popolarità 0 50 100 150 200 250 300 350 400 50 100 150 200 250 Topic ID Fr equenza 0 50 100 Per centuale nodi bizantini Popolarità topic APT senza mediazione
APT con mediazione Percentuale nodi bizantini
Figura 10: Frequenza della distribuzione dei topic nelle APT con e senza l’uso della mediazione distribuita tramite APT intro-ducendo nel sistema il 10% di nodi bizantini.L’ambiente di test è costituito da 1.000 nodi, 400 topic, dimensione del sample pari a 10, 2000 cicli di elaborazione, APT di 40 en-try ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7
stata introdotta nella rete una quantità di nodi bizantini pari rispettivamente al 10% e al 30%. In entrambi i grafici sono pre-senti sia la distribuzione dei topic risultante dall’utilizzo della mediazione distribuita, sia quella in cui non è stata messa in atto alcuna politica di mediazione ed inoltre vi è anche la curva che indica la percentuale di nodi bizantini che hanno sottoscrit-to il relativo sottoscrit-topic, dove mancano ovviamente tutti i sottoscrit-topic che avrebbero avuto in tale curva un valore del 100%.
Si può osservare subito come in ciascun grafico entrambe le curve (quella generata tramite mediazione e non) siano in gran parte equivalenti anche c’è una sorta di specularità tra la curva con la distribuzione e la curva della percentuale della quantità di nodi bizantini, che indica come maggiore sia la quantità di nodi malevoli che hanno sottoscritto un topic e maggiore sarà lo scostamento della frequenza di distribuzione nelle APT del topic rispetto al valore ideale.
3.1 mediazione distribuita della popolarità 43 0 50 100 150 200 250 300 350 400 50 100 150 200 250 Topic ID Fr equenza 0 50 100 Per centuale nodi bizantini Popolarità topic APT senza mediazione
APT con mediazione Percentuale nodi bizantini
Figura 11: Frequenza della distribuzione dei topic nelle APT con e senza l’uso della mediazione distribuita tramite APT intro-ducendo nel sistema il 30% di nodi bizantini. L’ambiente di test è costituito da 1.000 nodi, 400 topic, dimensione del sample pari a 10, 2000 cicli di elaborazione, APT di 40 entry ed una distribuzione delle sottoscrizioni che segue una zipf law con parametro 0, 7
Da questo possiamo trarre diverse conclusioni:
• l’utilizzo della tecnica di mediazione distribuita riesce a portare solo un lievissimo miglioramento all’uniformità della distribuzione dei topic che dipende dalla quantità di nodi malevoli che hanno sottoscritto i topic. La sostan-ziale equivalenza tra le due curve di distribuzione detta di fatto l’incapacità dell’approccio di portare un beneficio reale e consistente al sistema.
• ricordando sempre di aver escluso i topic sottoscritti solo da nodi bizantini, si vede dai grafici come non ci siano topic con rappresentazione nulla all’interno delle tabelle degli access point e che una certa uniformità può essere ancora apprezzata seppure con una maggiore variabilità. Questo decreta una certa robustezza del sistema originale TERA alla presenza di nodi bizantini non considerando alcuni topic come appena ricordato.
44 variazione della popolarità
La mediazione dei valori di popolarità con i valori ottenuti da altri nodi della rete non si è rivelata soddisfacente. Esclu-dere dei topic dai risultati non è la strada giusta da percorrere se si pensa che non per forza alcuni nodi che inviano informa-zioni di popolarità errate sono bizantini, ma il loro servizio di size estimation potrebbe non essere stato in grado di giungere a conclusioni corrette.