e viceversa; quindi si deve avere anche che FAB ∩ FBA = . Nel caso contrario
qualsiasi cella appartenente all'intersezione è visibile sia da FAB che da FBA.
Fino a quando due entità rimangono nelle rispettive frontiere non vengono mai a trovarsi in celle visibili tra loro. Eseguendo una mossa una entità potrebbe lasciare la propria frontiera, in questo caso può veri carsi una delle seguenti situazioni:
È possibile stabilire una nuova frontiera in maniera tale che le due entità continuino ad essere mutuamente invisibili
Le due entità si vedono a vicenda e quindi hanno bisogno di scambiarsi mes- saggi per mantenere la consistenza delle loro azioni
In modo analogo per quanto avviene con UFR questo procedimento si ripete nel tempo, veri cando se qualche entità abbandona la propria frontiera e intraprendendo le azioni necessarie.
Le prestazioni di Frontier Set sono state testate attraverso simulazioni con il gioco QuakeII mostrando che grazie a questo sistema è possibile ridurre in maniera drastica i pacchetti inviati ad ogni nodo per ogni frame del gioco.
Ciò nonostante Frontier Set presenta le stesse limitazioni già descritte per UFR. Inoltre è di cilmente adattabile a sistemi completamente distribuiti; in queste ar- chitetture infatti si dovrebbe avere che lo scambio di informazioni tra due peer si ha solo se essi sono visibili a vicenda; in mancanza di un punto di centralizzazione però sarebbe impossibile informare i peer delle loro reciproche relazioni di visibilità.
1.5 Proposte basate su DHT
Il sistema SimMud [8]è caratterizzato principalmente da
Mappa: rappresentazione del mondo virtuale non modi cabile Oggetti con stato: Oggetti modi cabili dai clienti dell'applicazione
Le azioni consentite all'utente sono: cambio di posizione nel mondo interazione con un oggetto interazione con altri utenti
Il mondo virtuale di SimMud è diviso in regioni di dimensione ssata; ogni regione contiene solo i nodi che vi appartengono e che quindi sono direttamente interessati agli avvenimenti che accadono in essa. Per i suddetti motivi tutti gli aggiornamenti riguardanti una certa regione sono inviati solo ai nodi membri della regione stessa.
Il mondo virtuale è caratterizzato oltre che dai nodi anche da oggetti con stato modi cabile. SimMud aronta il problema di mantenere consistente lo stato degli oggetti assegnando per ognuno di essi un nodo coordinatore; questo nodo rappresenta il responsabile per l'oggetto, quindi tute le modi che all'oggetto da parte dei clienti sono inviate al coordinatore che si occuperà dell'aggiornamento dello stato. Ogni cliente mantiene una copia degli oggetti della regione a cui appartiene; ogni volta che il coordinatore modi ca lo stato di un oggetto deve comunicare a tutti i nodi della regione in nuovo stato dell'oggetto.
L'architettura di SimMud si basa su due parti fondamentali: Pastry e Scribe. Pastry viene utilizzato per la creazione di una overlay network distribuita, men- tre Scribe rappresenta il supporto al multicast. Di seguito si fornisce una breve spiegazione del loro utilizzo nell'ambito del sistema SimMud.
Pastry [36] rappresenta una implementazione di Distributed Hash Table (DHT). Una DHT è una struttura che permette l'inserimento e il recupero di informazioni. Sia i nodi dell'applicazione che gli oggetti che si intende utilizzare in essa sono rappre- sentati in un namespace circolare di identi catori. Si possono ottenere identi catori unici attraverso una funzione, come ad esempio SHA-1. Il meccanismo attraverso il quale gli oggetti vengono mappati sui nodi è dato dalla vicinanza numerica dell'ID dell'oggetto rispetto agli ID dei nodi: un oggetto con un certo identi cativo viene mappato sul nodo il cui ID è numericamente più vicino all'identi cativo dell'oggetto.
1.5. PROPOSTE BASATE SU DHT 23 L'obiettivo di questa struttura è l'inserimento di oggetti e il loro successivo recupero in maniera e ciente. Ogni nodo della DHT mantiene dei puntatori ai nodi vicini in entrambi i lati; si de niscono nodi vicini di un certo nodo quelli con ID nume- ricamente vicini all'ID del nodo stesso; i nodi vicini formano il così detto leaf set. Fissato un parametro b, l'instradamento di un messaggio da un certo nodo x verso un nodo y impiega log2bN passi.
Scribe è un'infrastruttura per il supporto del multicast costruita utilizzando Pa- stry come architettura sottostante. L'utilizzo di Scribe in SimMud è il seguente. Si associa ad ogni gruppo un albero multicast, identi cato da un ID appartenente allo stesso namespace di Pastry. La creazione dell'albero multicast associato al gruppo è possibile dall'unione di tutti i cammini da ogni membro del gruppo al nodo radice (che rappresenta la radice dell'albero multicast).
Le regioni costruite sono distribuite su nodi diversi attraverso il mapping nello spazio delle chiavi di Pastry. Dal nome testuale della regione è possibile ricavare un ID unico applicando una funzione hash. La scelta del coordinatore per la regione avviene con il meccanismo della DHT: il coordinatore per una certa regione con identi cativo ID è il nodo il quale ID è più vicino numericamente all'ID della regione. Il nodo coordinatore rappresenta anche la radice dell'albero multicast per la regione. Grazie al mapping random il coordinatore di una certa regione sarà un nodo che quasi sicuramente non appartiene alla regione con il vantaggio di ridurre la possibilità di comportamenti scorretti.
Consistenza del mondo Come sopra descritto il sistema utilizza dei nodi coor- dinatori per mantenere la consistenza dello stato degli oggetti condivisi tra i peer dell'applicazione. Questo approccio presenta l'evidente problema della formazione di punti di centralizzazione nei nodi coordinatori.
Gli autori propongono una soluzione al problema attraverso la replicazione del coor- dinatore appena si rilevano dei guasti sulla rete; l'obiettivo è mantenere almeno una copia consistente del coordinatore vista il suo ruolo centrale nella gestione degli og- getti della regione per cui è responsabile.
merosi messaggi di replica ai nodi designati come riserve: più repliche si creano e più messaggi sono necessari per mantenerle aggiornate e consistenti.
Formazione di partizioni disgiunte Se un grande numero di nodi subisce una disconnessione dalla rete oppure abbandona l'applicazione per altri motivi il sistema corre il rischio di formazione di partizioni di nodi disgiunte. In questo caso si assiste alla formazioni di due o più insiemi di nodi tale per cui un nodo appartenente a una partizione non ha modo di comunicare con un nodo appartenente ad un'altra parti- zione; tuttavia anche in queste situazioni il sistema può proseguire. I nodi possono comunque allocare nuovi oggetti sui nodi rimasti attivi ma si perde la consistenza dello stato per gli oggetti condivisi prima del veri carsi della partizione: gli utenti non hanno alcun modo di comunicare e quindi di scambiarsi aggiornamenti.
La soluzione proposta dagli autori di SimMud per porre rimedio alle conseguenze della formazione di partizioni di nodi disgiunte fa a damento al server centrale dell'applicazione; questo server viene utilizzato dall'applicazione per mantenere le informazioni dell'utente e per gestire la fase di login.
Se due nodi appartengono rispettivamente a due partizioni disgiunte, ma en- trambi sono in grado di comunicare con il server allora sarà proprio questo che farà da intermediario per le modi che di oggetti condivisi tra i due nodi. Dunque, si torna al modello client/server con tutti gli svantaggi di cui sappiamo.
Scalabilità SimMud si basa su una ripartizione statica del mondo virtuale, dove tutte le regioni hanno una dimensione ssata e una densità media di popolazione stabilita. Si pone il problema dell'eccessivo aollamento di alcune regioni a seguito dell'aumento del numero di partecipanti all'applicazione e quindi del superamento dei livelli massimi di densità previsti.
Elenchiamo di seguito le soluzioni proposte:
limitare l'entrata nel sistema ai nuovi clienti quando si raggiunge la densità massima stabilita
1.6. TECNICHE DI SCAMBIO DELLE LISTE DEI VICINI 25