Di seguito cercheremo di valutare quale è la probabilità di portare a buon fine una operazione di ricerca di un access point nel caso in cui prevediamo che nel sistema siano presenti un cer-to numero di nodi malevoli. Inizialmente effettuiamo una valu-tazione prevedendo una singola ricerca distribuita costituita da k operazioni massime di inoltro della lookup.
56 ricerca degli access point
Se il comportamento di un nodo bizantino durante l’indagine è quello di scartare la richiesta inoltratagli, allora la probabilità di trovare un access point per mezzo di una operazione di lookup distribuita di k passi è data dalla probabilità che durante il routing vengano incontrati solo nodi corretti e che tutti questi, a parte l’ultimo della catena, non abbiano trovato il topic in questione oppure che la ricerca sia terminata prima di arrivare alla fine poiché è stato trovato un access point.
Indichiamo con T il numero totale di topic, con |APT| la di-mensione delle APT, con N il numero globale di nodi e con Nc il numero di nodi non bizantini. La probabilità di trovare un topic t all’interno di una APT è pt = |APT|
T poiché la distribu-zione è uniforme, mentre la probabilità di selezionare un nodo corretto è data da pNc = Nc
N. Dunque se effettuiamo al massi-mo k passi la probabilità che la ricerca produca un access point come risultato è data:
ps = k X
i=1
(pNc(1 − pt))k−1(pNcpt) (15) Nella tabella sottostante sono riportati i valori di probabilità che si avrebbero al variare del TTL se si cercasse un topic in un ambiente di 1000 nodi del quale il 30% sono bizantini, con 400 topic e con APT di 40 item massimo:
1 2 3 4 0,07 0,1141 0,141883 0,15938629 5 6 7 8 0,170413363 0,177360419 0,181737064 0,18449435 9 10 0,186231441 0,187325808
Tabella 4: Probabilità di trovare un topic effettuando una operazione di ricerca nelle APT al variare del TTL. 1000 nodi, 30% nodi bizantini, 400 topic, dimensione APT 40
Nella tabella 4 possiamo vedere come la probabilità è bassa sia se il numero di operazioni di inoltro consentito è alto sia se è basso e questo è spiegabile dal fatto che la probabilità di incappare in un host bizantino durante il percorso di ricerca è molto alta ed è quindi molto probabile che la ricerca fallisca prematuramente.
Per cercare di ovviare al problema, visto che non è possibile ridurre il rischio di incontrare un nodo malevolo durante una
4.1 probabilità in caso di scarto della ricerca 57 ricerca distribuita, sarebbe opportuno effettuare un certo nume-ro di ricerche in parallelo di modo che se anche una operazione di lookup viene interrotta pretestuosamente da un nodo bizanti-no vi è una certa probabilità che almebizanti-no una delle altre vada a buon fine.
Proviamo quindi a valutare quale è questa probabilità, in-dicando con r il numero di ricerche in parallelo e con ps la probabilità che una singola ricerca sia terminata correttamente, ovvero:
p = 1 − (1 − ps)r (16)
La formula calcola preventivamente la probabilità che nessuna delle richieste vada a buon fine, (1 − ps)r per poi ottenere la probabilità inversa che appunto è la probabilità che almeno una delle ricerche in parallelo riesca a trovare un access point
0 2 4 6 8 10 12 14 16 18 20 0 0.1 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 k = 1 k = 6 k = 10 k = 15
Figura 18: Grafico con le probabilità di trovare un certo topic effet-tuando una operazione di ricerca distribuita nelle APT. Con k si indica il TTL della ricerca e con r si indica il nu-mero delle ricerche in parallelo, i calcoli sono effettuati per un ambiente con 1000 nodi ed il 30% dei nodi bizantini, 400topic e APT di dimensioni 40
58 ricerca degli access point
Rimanendo nel campo della deduzione effettuiamo il calcolo della probabilità di successo utilizzando la formula (16) varian-do sia r, ovvero il numero di ricerche contemporanee, sia k, ovvero il Time-To-Live del messaggio di lookup
Osservando il grafico riportato in figura 16 che riporta i ri-sultati del calcolo appena menzionato si intuisce come il pa-rametro di riferimento è il numero di ricerche in parallelo e non il TTL A parità di numero di ricerche infatti la variazione indotta dal numero massimo di operazioni di inoltro del mes-saggio di lookup è esigua e tende a diminuire all’incremento del parametro che lo rappresenta, infatti superato il numero di 10 operazione di inoltro la variazione diventa molto vicina a zero sicché non vi è alcun vantaggio nel continuare ad aumentare k. Tutto questo è dovuto al fatto che aumentando il TTL diventa sempre più ampia la probabilità di inoltrare la lookup verso un nodo bizantino. 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 k = 10 reale k = 10 previsto
Figura 19: Grafico con le probabilità di trovare un certo topic effet-tuando una operazione di ricerca distribuita nelle APT. Con k si indica il TTL della ricerca e con r si indica il nu-mero delle ricerche in parallelo, i calcoli sono effettuati per un ambiente con 1000 nodi ed il 30% dei nodi bizantini, 400topic e APT di dimensioni 40
4.2 effetti della non uniformità nella apt 59 Diversamente modificando il numero delle ricerche effettuate contemporaneamente il miglioramento della probabilità di suc-cesso è apprezzabile, ad esempio effettuando in numero assolu-to 15 operazioni di lookup, se effettuate in maniera sequenziale si ottiene una probabilità pari circa a 0.19 mentre effettuando lo stesso numero di ricerche in parallelo la probabilità è vicina a 0.66.
Proviamo quindi ad effettuare dei test di simulazione, per verificare effettivamente la veridicità dei valori di probabilità ottenuti dalla formula 16, utilizzando 10 come valore di TTL dei messaggi di ricerca visto che rappresenta una sorta di limi-te oltre il quale un incremento non produrrebbe miglioramenti. In figura 19 è possibile visualizzare l’esito dei vari test effet-tuati, nel quale le due curve presentano valori di probabilità estremamente simili confermando la validità della stima.
Dunque TERA è in grado di dialogare con un certo nume-ro di nodi bizantini, i quali scartano le richieste di lookup, in-crementando il numero di richieste in parallelo così da ottene-re, con un probabilità abbastanza elevata, un access point per il topic richiesto.