Tecniche di ltraggio dei messaggi

Presentiamo in questa sezione delle tecniche che consentono di ridurre la quantità dei messaggi scambiati tra i peer di un sistema distribuito; i sistemi che prendiamo in considerazione sono Update Free Regions (UFRs)[6] e Fontier Set [7].

1.4.1 Update Free Region

I sistemi P2P sono caratterizzati dall'assenza di punti di centralizzazione: ogni client dell'architettura distribuita per mantenere una visione aggiornata dello stato degli altri client deve ricevere dalla rete n-1 messaggi per unità di tempo. Osserviamo però che non tutti gli n-1 messaggi ricevuti sono eettivamente utili; infatti per ogni client è suciente solo una vista locale dell'ambiente che lo circonda piuttosto che una conoscenza completa del mondo.

Consideriamo due nodi A e B che appartengono a zone del mondo che non sono visibili reciprocamente allora è possibile individuare due regioni del mondo tale per cui no a quando i nodi A e B rimangono nelle rispettive regioni, si ha che A e B sono invisibili a vicenda; queste regioni sono chiamate Update Free Regions. L'ap- proccio appena descritto permette di ridurre i messaggi scambiati attraverso la rete perché no a quando ogni nodo rimane nella propria UFR i messaggi provenienti da e diretti verso altri nodi possono essere ltrati. Considerando i nodi A e B si ha che no a quando A rimane nelle propria regione non ha bisogno di comunicare con B.

Per gli ambienti a forma poligonale anche le UFRs risultano poligonali e la veri- ca che un nodo si trovi o meno nella regione corrisponde a vericare se un punto è contenuto in un poligono.

Quando uno dei nodi esce dalla propria UFR potenzialmente potrebbe essere visibile agli altri nodi; in questo caso le UFRs devono essere ricalcolate e se la invisibiltà viene meno il nodo inizia ad inviare messaggi di aggiornamento. Il procedimento appena descritto viene iterato ogni volta che un nodo, compiendo uno spostamento, si trova al di fuori della propria UFR.

1.4. TECNICHE DI FILTRAGGIO DEI MESSAGGI 19 Da quanto detto n'ora è evidente che un punto centrale in questa tecnica è il calcolo ottimale delle UFRs in modo tale che possano contenere il nodo il più a lungo possibile. La dimensione della UFR è un fattore importante infatti l'obiettivo è ottenere regioni di maggior dimensione possibile.

La quantità dei messaggi ltrati e quindi l'ecacia dell'algoritmo dipende in ma- niera decisiva dal tipo di spostamento dei nodi all'interno del mondo virtuale. Se il nodo si sposta progressivamente verso un'unica direzione si troverà presto al conne della propria UFR e una volta giunto fuori deve iniziare l'invio dei messaggi oppu- re deve ricalcolare di nuovo la UFR. Spostamenti random del nodo contribuiscono anché esso rimanga all'interno della propria UFR in quanto le nuove posizioni sa- ranno con buona probabilità vicine alla posizione iniziale. Il caso meno probabile, ma anche meno interessante, si verica quando il nodo non si muove mai rimanendo costantemente nella propria UFR.

Data la coppia di nodi A e B si pone in problema di come denire le rispettive UFRs. Il nodo B non ha nessuna conoscenza di quali saranno i futuri spostamenti di A; la stessa cosa vale per A. L'unica cosa che B può dedurre è che A esegua degli spostamenti a partire dalla sua posizione iniziale.

Dal punto di vista di B tutte le direzioni sono equiprobabili quindi assume che A si sia mosso simultaneamente in tutte le direzioni possibili. Lo stesso vale per A rispetto a B. Il processo appena descritto permette di denire la dimensione ottimale delle UFRs e prende il nome di mutually expanding process.

Grazie alle osservazioni fatte n'ora possiamo dare la seguente denizione di Up- date Free Region: ogni nodo partendo dalla propria posizione iniziale conquista uno spazio se raggiunge quello spazio prima degli altri e se lo stato che assume è invisibile rispetto a tutti altri spazi conquistati dagli altri nodi no a quel momento.

Il procedimento continua no a quando il nodo non è più in grado di conquistare altri spazi. La regione che si costruisce con questo procedimento rappresenta la UFR del nodo.

Il principale problema di questo approccio ai sistemi distribuiti è la scalabilità: le tecniche appena descritte si applicano facilmente ad una coppia di nodi; passare ad un ambiente con molti nodi comporta che ogni nodo deve calcolare la propria UFR rispetto ad ognuno degli altri nodi del sistema.

1.4.2 Frontier Set

Frontier Set descritto in [7] si basa sullo stesso approccio di UFR. Il mondo virtuale è diviso in regioni anche chiamate celle.

Per una coppia di nodi una frontiera identica due regioni contenenti rispettiva- mente i due nodi; le regioni sono costruite in modo tale che i nodi siano invisibili reciprocamente. Ad ogni mossa del nodo la relazione di visibilità tra i nodi deve essere valutata nuovamente.

Si introducono i potentially visible set (PVS) con il ne di individuare una coppia di nodi che non sono visibili reciprocamente e quindi non hanno bisogno di scambiarsi messaggi per mantenere il corretto funzionamento del sistema.

Gli autori del sistema introducono una struttura dati chiamata Frontier Set che permette ad una coppia di nodi di sapere rapidamente se la proprietà di mutua invisibilità è ancora valida.

Il Frontier Set viene costruito a partire dai PVS e permette a due entità di sapere rapidamente se sono tra loro mutuamente invisibili oppure se occorre uno scambio di messaggi. In maniera analoga a UFR, Frontier Set osserva che in un mondo virtuale solo una parte limitata dell'ambiente circostante è visibile all'entità che si trova in un certo punto.

In ogni regione (o cella) dell'ambiente è possibile individuare dei punti di collega- mento (aperture) con le altre celle che permettono all'entità che vi è posizionata di osservare gli eventi che accadono nelle celle circostanti.

Per ogni cella è dunque possibile calcolare quali sono le altre celle visibili che quindi costituiscono il potentially visible set (PVS) per essa.

A partire dalla denizione di PVS possiamo introdurre il concetto di Frontier Set; date due entità A e B le Frontier Set FAB e FBA sono tali per cui nessuna cella

1.5. PROPOSTE BASATE SU DHT 21