JaDE: un supporto JXTA per ambienti virtuali distribuiti

i

Sommario

La tesi propone JaDE, JXTA Distributed Environment, un supporto per ambienti virtuali distribuiti basato su una architettura distribuita di tipo Peer-to-Peer e im-plementato mediante JXTA. La prima parte della tesi fornisce una panoramica delle principali proposte di ambienti virtuali distribuiti e descrive alcune tra le più inno-vative. Viene quindi introdotta l'architettura di JaDE, che include un protocollo per la denizione e la manutenzione di un'overlay network che supporti l'interazione tra le entità virtuali. Viene quindi considerato il problema della gestione degli og-getti passivi del mondo virtuale, in particolare della loro consistenza in un ambiente altamente dinamico come quello P2P. La tesi mostra inne un insieme di risultati sperimentali che confrontano implementazioni alternative di JaDE mediante diversi protocolli JXTA (pipe binding protocol, discovery protocol, resolver protocol,...) e dimostrano l'ecacia dell'approccio proposto in situazioni reali.

Indice

Introduzione vii

1 Stato dell'Arte 1

1.1 Introduzione ai sistemi distribuiti . . . 1

1.2 Solipsis . . . 6

1.3 VON: Voronoi-based Overlay Network . . . 10

1.4 Tecniche di ltraggio dei messaggi . . . 18

1.4.1 Update Free Region . . . 18

1.4.2 Frontier Set . . . 20

1.5 Proposte basate su DHT . . . 21

1.6 Tecniche di scambio delle liste dei vicini . . . 25

1.7 Sistemi client-server ibridi . . . 29

1.8 Sistemi P2P ibridi . . . 33

2 JXTA: una piattaforma per lo sviluppo di applicazioni P2P 37 2.1 Introduzione . . . 37

2.1.1 Concetti principali . . . 39

2.2 JXTA Pipe . . . 41

2.3 Architettura di Rete di JXTA . . . 44

2.3.1 Rendezvous Peer . . . 45

2.4 Protocolli JXTA . . . 48

2.5 Query Process e Resolver Protocol . . . 49

2.5.1 Resolver Protocol: Broadcast Ping . . . 50

2.5.2 Indicizzazione delle risorse: SRDI . . . 52

2.6 JXTA Discovery Protocol . . . 54 iii

2.6.1 Pubblicazione di risorse . . . 55

2.6.2 Recupero di risorse . . . 56

2.7 JXTA per applicazioni P2P near Real-Time . . . 56

2.8 Aspetti di sicurezza in JXTA . . . 59

3 JaDE: scelte di progetto 63 3.1 Struttura del sistema . . . 63

3.1.1 Struttura Generale e Denizioni . . . 63

3.1.2 Area di interesse del nodo . . . 65

3.2 Costruzione e manutenzione della overlay network . . . 66

3.2.1 Connessione al mondo virtuale . . . 66

3.2.2 Messaggi scambiati tra i nodi . . . 67

3.2.3 Disconnessione dal mondo virtuale . . . 70

3.2.4 Mantenere la consistenza della overlay network . . . 70

3.2.5 Area di interesse del peer . . . 70

3.3 Gestione degli oggetti passivi . . . 73

3.3.1 Creazione e pubblicazione di oggetti passivi . . . 75

3.3.2 Disconnessione dalla regione . . . 78

3.3.3 Disconnessione dal sistema . . . 81

3.3.4 Recupero di oggetti passivi . . . 82

3.3.5 Modica di oggetti passivi . . . 84

3.4 Architettura del sistema . . . 93

3.4.1 JaDE API . . . 93

4 JaDE: implementazione 97 4.1 Introduzione . . . 97

4.2 Struttura del supporto . . . 97

4.3 Connessione al mondo virtuale . . . 98

4.3.1 Struttura dei gruppi . . . 98

4.3.2 Inizializzazione del peer . . . 99

4.4 Comunicazioni tra peer . . . 101

4.4.1 Eventi . . . 101

INDICE v

4.5 Oggetti passivi . . . 106

4.5.1 Creazione e pubblicazione . . . 106

4.6 Recupero degli oggetti passivi . . . 110

4.6.1 Area di interesse statica . . . 110

4.6.2 Filtro sulle zone di interesse . . . 111

4.6.3 Area di interesse dinamica . . . 113

4.7 Modica oggetti passivi . . . 114

4.7.1 Pubblicazione diretta delle modiche . . . 114

4.7.2 Modica con richiesta al coordinatore . . . 115

4.7.3 Modica oggetti sulla mappa . . . 118

4.8 Disconnessione del peer . . . 118

5 Risultati Sperimentali 123 5.1 Ambiente di simulazione . . . 123

5.2 Prototipo sviluppato . . . 123

5.3 Valutazione latenza messaggi di heartbeat . . . 124

5.4 Valutazione tempi di scoperta di oggetti passivi . . . 128

5.5 Dimensione zona di conne . . . 130

6 Risultati prove su Internet 135 6.1 Risultati dei test eseguiti su Internet . . . 135

6.1.1 Descrizione prova . . . 137

6.2 Avviare la piattaforma JXTA . . . 139

7 Conclusioni 149

Introduzione

Gli ambienti virtuali distribuiti (DVE) [44], [47], [48], [49] comprendono una vasta gamma di applicazioni che si stanno diondendo sempre più rapidamente grazie alla disponibilità delle wide are networks (WAN). Alcuni esempi di questo tipo di ap-plicazioni comprendono ambienti distribuiti per simulazioni civili o militari; molto più diusi e conosciuti sono i MMOG (Massively Multiplayer Online Games): ricor-diamo Second Life [19], che al momento della stesura della presente tesi comprende 6.240.591 abitanti con una media di circa 20.000 utenti connessi ogni istante.

Un ambiente virtuale distribuito consiste in uno spazio virtuale generato da una applicazione software dove più utenti, rappresentati da avatars, interagiscono tra loro in tempo reale scambiandosi messaggi attraverso la rete. I partecipanti all'applicazione possono connettersi al mondo virtuale, cambiare la loro posizione, modicare gli oggetti del mondo e disconnettersi in qualsiasi istante.

Gli approcci attuali più diusi allo sviluppo di questo tipo di applicazioni ricor-rono a soluzioni centralizzate di tipo Client-Server (CS) [38]: il singolo server è responsabile della gestione dello stato dell'applicazione e quindi della corretta inte-razione tra i partecipanti. I client inviano i loro messaggi al server che ha il compito di aggiornare lo stato e a sua volta noticare ai client gli eventuali cambiamenti che li riguardano.

Nell'architettura CS il server è un punto di centralizzazione per l'intera appli-cazione e quindi un singolo punto di fallimento del sistema nonchè un forte vincolo alla scalabilità. Osserviamo infatti che il fallimento del server compromette irri-mediabilmente lo stato dell'applicazione. Inoltre, se il numero di client raggiunge valori elevati il server centralizzato potrebbe non essere in grado di gestirli, sia per quanto riguarda le risorse di calcolo, sia per la banda di trasmissione limitata; in

queste situazioni i tempi di risposta del server aumentano, compromettendo l'inte-rattività dell'applicazione. Le proposte che prevedono l'introduzione di server farm presentano il problema del dimensionamento del farm. In generale è necessario sopra dimensionare il numero di server per far fronte a picchi di richieste che si possono manifestare solo in periodi limitati di tempo.

Per i motivi suddetti negli ultimi anni si stanno aermando architetture che non prevedono la presenza di un server centralizzato ma si basano su modelli completa-mente distribuiti, chiamati Peer to Peer (P2P).

Un sistema P2P è denito da un insieme di entità autonome capaci di auto-organizzarsi, che condividono un insieme di risorse distribuite all'interno di una rete di computer. I sistemi P2P sono costruiti connettendo diversi computer (chiamati nodi o peer) per creare una rete virtuale, chiamata overlay network che si pone al di sopra della rete sica.

Nell'ultimo decennio e in particolare negli ultimi anni abbiamo assistito all'e-voluzione dei sistemi P2P: a partire da soluzioni centralizzate, con organizzazione non strutturata dell'informazione no ad arrivare ad approcci più strutturati per migliorare il recupero dei dati.

Nello sviluppo di DVE attraverso modelli P2P emergono diversi problemi come la consistenza dello stato, la persistenza dello stato e la reattività del sistema.

Lo stato dell'applicazione è completamente distribuito tra i peer del sistema; l'assenza di una entità centralizzata che ha il compito di mantenere lo stato comporta lo sviluppo di tecniche per la corretta sincronizzazione e comunicazione tra i peer.

Il problema di rappresentare un ambiente virtuale distribuito può essere denito nel seguente modo: è dato un insieme di punti, chiamati nodi; ogni nodo può eseguire spostamenti su un piano in tre dimensioni, ossia il mondo virtuale. In questo contesto gli aspetti chiave sono rappresentati dalla località e dai vincoli temporali.

Per quanto riguarda il primo punto è stato denito il concetto di Area of Interest (AOI) [47], [50], [51], [54]; è possibile limitare la visione di ogni entità allo spazio che la circonda entro un'area limitata detta appunto area di interesse. Le aree di interesse possono essere di due tipi: sse oppure mobili. Quelle mobili sono aree

ix strettamente legate allo spostamento del nodo locale, quindi modicate dinamica-mente in base agli spostamenti che esegue. Le aree di interesse sse sono aree legate a particolari porzioni del mondo virtuale che viene diviso in zone; tutte le entità possono entrare o uscire.

Ogni nodo mantiene solo la conoscenza dei nodi vicini appartenenti all'area di interesse; dunque, ha una visione locale dell'ambiente che lo circonda.

L'introduzione del concetto di area di interesse consente di ottimizzare le co-municazioni tra i peer e di denire tecniche di mantenimento della consistenza più ecaci.

Con il termine consistenza di solito si intende la sincronizzazione dello stato e degli eventi tra i partecipanti di una applicazione distribuita. Nel contesto degli am-bienti virtuali distribuiti uno dei concetti di consistenza si riferisce alla consistenza topologica con ne di fornire a ogni partecipante una rappresentazione corretta del-l'ambiente che lo circonda. Dunque la consistenza è rispettata se ogni nodo del sistema mantiene la conoscenza della propria AOI e quindi dei vicini e degli oggetti passivi che si trovano al suo interno. In questa tesi la consistenza topologica sarà l'aspetto principale.

I nodi di un sistema DVE interagisco in real time, dunque per realizzare corret-tamente la logica dell'applicazione occorre rispettare dei vincoli temporali: il peer deve eseguire certe azioni in un preciso istante anché si producano risultati corret-ti, consistenti e tempestivi sia per il peer stesso che per gli altri peer. Tuttavia alcuni ritardi non possono essere evitati, come la latenza di trasmissione dei messaggi.

Questa tesi propone di utilizzare la piattaforma JXTA [13] per lo sviluppo di un supporto per DVE. JXTA propone un insieme di protocolli che permettono la crea-zione di applicazioni distribuite. Dispositivi di diversa natura possono concorrere alla formazione di una applicazione P2P: JXTA permette anche a dispositivi con risorse limitate di partecipare e collaborare alla realizzazione di un sistema distri-buito. Questo si deve all'architettura di rete di JXTA che dierenzia i ruoli assunti dai diversi peer in base alle caratteristiche siche dei dispositivi su cui sono in esecu-zione. La classicazione in Minimal-Edge Peer e Full-Featured Edge Peer risponde proprio a questa esigenza: i primi hanno a disposizione risorse limitate dunque

ese-guono solo le operazioni fondamentali di scambio messaggi con gli altri peer mentre i secondi rappresentano i peer standard. Nella rete JXTA si individuano anche i Relay peer il cui ruolo principale è il routing dei messaggi. I peer che si trovano in sistemi protetti da rewall o da NAT non potrebbero connettersi a JXTA; tuttavia attraverso la connessione ad un Relay i peer riescono comunque a connettersi alla rete JXTA e raggiungere risorse che si trovano al di fuori della propria rete locale.

Tutte le applicazione P2P, oltre a presentare una natura eterogenea, sono caratte-rizzate da forte dinamicità dello stato della connessione in rete dei peer partecipanti: alcuni peer dispongono di connettività limitata o variabile alla rete; basti immagi-nare un PDA che in base agli spostamenti subisce cambi dell'indirizzo IP oppure si disconnetta dalla rete. La piattaforma JXTA risponde a queste esigenze attraverso un sistema di indirizzamento dei peer indipendente dai protocolli di rete standard come il DNS. Ad ogni peer che entra nella piattaforma JXTA viene assegnato un identicatore unico; gli eventuali cambiamenti dell'indirizzo di rete, oppure tempo-ranee disconnessioni non inuiscono sulla sua capacità di essere individuato dagli altri peer.

Ogni risorsa JXTA è associata ad un advertisement, cioè un documento XML utilizzato per rappresentare la risorsa stessa. La pubblicazione e la scoperta di risorse avviene attraverso il protocollo di Discovery che si basa su un modello P2P ibrido. Il Discovery Protocol è caratterizzato dalla collaborazione tra i Rendezvous Peer di JXTA che partecipano alla ricerca di risorse e al servizio di indicizzazione SRDI (Shared Resource Distributed Index). Ogni pubblicazione di una risorsa da parte di un peer comporta l'inserimento dell'indice dell'advertisement nel Rendezvous Peer a cui il peer è connesso. Questo Rendezvous a sua volta, invia l'indice ricevuto ad altri Rendezvous conosciuti secondo un algoritmo basato su DHT [16]. Ogni Rendezvous mantiene solo la cache dell'indice SRDI.

Il recupero di risorse avviene in maniera analoga grazie alla collaborazione dei Rendezvous peer. Inoltre JXTA ore diversi strumenti di comunicazione tra peer, ricordiamo le JXTA Pipe, canali di comunicazione e trasferimento di dati.

xi Questa tesi propone JaDE (JXTA Distributed Virtual Environment) un supporto per applicazioni virtuali distribuite basato su un modello di computazione P2P. Il supporto JaDE ha come obiettivo la creazione di un sistema distribuito basato sulla collaborazione di tutti i peer partecipanti al ne di rendere possibile la manutenzione della overlay network e la corretta gestione di risorse condivise tra i peer. Notiamo che tutti i nodi del sistema sono alla pari; tutti i peer ricoprono lo stesso ruolo e dispongono delle stesse capacità al ne dell'interazione con gli altri nodi.

JaDE propone la creazione di un ambiente virtuale distribuito dove il mondo virtuale è suddiviso in regioni statiche. Ad ogni regione si associa un JXTA Peer Group che rappresenta tutti i peer che in un certo istante si trovano nel territorio della regione.

Gli spostamenti del peer tra le diverse regioni del mondo comportano quindi la connessione e disconnessione ai diversi peer group. I peer group suddividono il mondo virtuale di JaDE in regioni astratte, costituiscono una meccanismo di scoping in quanto l'ambito di applicazione dei servizi JXTA (discovery, resolver, membership, etc.) è proprio il peer group.

I gruppi JXTA sono organizzati in una struttura gerarchica al cui vertice tro-viamo il gruppo jxta-NetGroup. Ogni peer che entra nella piattaforma JXTA è di default un membro di questo gruppo; in modo analogo, ogni peer group creato da una applicazione è di default un sottogruppo del gruppo jxta-NetGroup. JaDE si basa su una gerarchia di gruppi in due livelli: GlobalEnv rappresenta il grup-po principale dell'applicazione ed è il grupgrup-po genitore della gerarchia; i peer group per le regioni sono sottogruppi di GlobalEnv. Dunque tutti i peer che partecipa-no all'applicazione distribuita appartengopartecipa-no al gruppo GlobalEnv; in base ai loro spostamenti nelle diverse regioni eseguiranno anche connessioni e disconnessioni ai diversi sottogruppi.

La corretta formazione della overlay network è possibile grazie allo scambio di messaggi tra i peer, in modo particolare dei messaggi di heartbeat, cioè dei messaggi con cui un peer segnala la propria posizione agli altri. La tesi confronta l'utilizzo di diversi meccanismi oerti da JXTA per lo scambio di messaggi di heartbeat tra i peer.

I peer oltre a compiere spostamenti nel mondo virtuale possono creare ogget-ti passivi, ossia oggetogget-ti privi di capacità autonome che sono visibili dagli altri partecipanti.

La gestione di oggetti condivisi tra tutti i peer pone diversi problemi: in assenza di un server centralizzato, dove mantenere gli oggetti? E ancora, come garantire la consistenza dello stato degli oggetti a fronte delle modiche di più peer?

La soluzione proposta da JaDE utilizza il Discovery Service di JXTA per la pubblicazione e recupero di risorse nella rete di peer. Il peer creatore di un certo og-getto esegue anche l'operazione di publish dell'ogog-getto nella regione di appartenenza in modo da permettere agli altri peer di venire a conoscenza del nuovo oggetto.

Per ogni oggetto passivo si introduce il peer coordinatore come il peer responsabile per quell'oggetto; inizialmente il peer che ha creato e pubblicato un certo oggetto passivo è coordinatore per l'oggetto. Il ruolo di coordinatore non è statico ma cambia in base agli spostamenti del peer tra le regioni.

Il peer che intende modicare un oggetto passivo deve richiedere l'esplicita au-torizzazione al coordinatore per quell'oggetto. JaDE prevede anche alcune ottimiz-zazioni a questo meccanismo basate sulla posizione relativa dei peer rispetto agli oggetti passivi.

La scelta di utilizzare aree di interesse sse comporta una potenziale inecienza in quelle situazioni in cui il peer si trova al limite di una certa regione senza però essere ancora entrato nella successiva; per questo motivo si introduce la zona di conne, rappresentata dal bordo esterno di ogni regione. Un peer trovandosi in questa zona acquisisce le informazioni relative alla regione adiacente, sia per gli oggetti passivi che per i peer vicini. Questa soluzione permette al peer di ottenere una conoscenza ottimale dell'ambiente che lo circonda in base ai suoi spostamenti.

Particolare attenzione è stata posta nello sviluppo delle procedure di connessio-ne e disconconnessio-nessioconnessio-ne dei peer alle regioni del mondo virtuale al connessio-ne di garantire la consistenza degli oggetti passivi e facilitarne il recupero.

La tesi è strutturata come descritto di seguito. Il capitolo 1 analizza il contesto in cui si colloca il lavoro oggetto della presente tesi: viene presentata una rassegna dei

xiii principali sistemi esistenti che realizzano ambienti virtuali distribuiti. Nel capitolo 2 presentiamo lo strumento principale utilizzato per lo sviluppo di JaDE, ovvero JXTA. Si fornisce una panoramica dei concetti principali e dei protocolli di base forniti dalla piattaforma. Vengono esaminati alcuni aspetti riguardanti l'applicabi-lità di JXTA in contesti real-time; inoltre si fornisce la descrizione dettagliata delle funzionalità fornite da JXTA su cui fa riferimento l'implementazione di JaDE. Il capitolo 3 denisce l'architettura di JaDE: si deniscono i concetti principali (peer, peer group, regione del mondo virtuale, oggetti passivi, peer coordinatore, etc.) e tutti gli aspetti riguardanti la manutenzione della overlay network e la gestione de-gli oggetti condivisi tra i peer. Inoltre vengono presentate e confrontate diverse soluzioni per la ricerca di oggetti passivi. Il capitolo 4 descrive l'implementazione attraverso JXTA del supporto JaDE: vengono presentate in dettaglio le scelte ef-fettuate, mostrando i vantaggi e svantaggi che comportano. Si propongono diverse tecniche per l'implementazione dei messaggi di Heartbeat. Inne i capitoli 5 e 6 mostrano i risultati sperimentali relativi ai test eseguiti. Vengono confrontate le diverse soluzioni proposte e si forniscono valutazioni a riguardo. Il capitolo 7 trae le conclusioni sul lavoro svolto.

Capitolo 1

Stato dell'Arte

1.1 Introduzione ai sistemi distribuiti

Gli ambienti virtuali distribuiti (DVE) comprendono una vasta gamma di applica-zioni che si stanno diondendo sempre più rapidamente grazie alla disponibiltà delle wide are networks (WAN). Applicazioni di questo tipo comprendono sia MMOG (Massevly Miltiplayer Online Games), ricordiamo World of Warcraft [18] come uno tra i più popolari, ma anche ambienti distribuiti per simulazioni militari governative. Un ambiente virtuale distribuito consiste in uno spazio virtuale generato da una applicazione software dove più utenti, rappresentati da avatars, interagiscono tra loro in tempo reale scambiandosi messaggi attraverso la rete. I partecipanti all'applicazione possono connettersi al mondo virtuale, cambiare la loro posizione e disconnettersi in qualsiasi istante.

Gli approcci attuali più diusi allo sviluppo di questo tipo di applicazioni ricorrono a soluzioni centralizzate di tipo Client-Server (CS): il singolo server è responsabile della gestione dello stato dell'applicazione e quindi della corretta interazione tra i partecipanti. I client inviano i loro messaggi al server che ha il compito di aggiornare lo stato e a sua volta noticare ai client gli eventuali cambiamenti che li riguardano. Nell'architettura CS il server è un punto di centralizzazione per l'intera appli-cazione e quindi un singolo punto di fallimento del sistema nonchè un forte vincolo alla scalabilità.

Figura 1.1: Overlay network

Quando il numero di utenti di una applicazione distribuita aumenta anche la quantità di messaggi che essi si scambiando attraverso la rete aumenta; la scalabilità è un problema importante in questo tipo di applicazioni e, come detto sopra, il modello CS non risponde alle caratteristiche desiderate.

Per questi motivi negli ultimi anni si stanno aermando architetture che non pre-vedono la presenza di un server centralizzato ma si basano su modelli completamente distribuiti, chiamati Peer to Peer (P2P).

Un sistema P2P è denito da un insieme di entità autonome capaci di auto-organizzarsi, che condividono un insieme di risorse distribuite all'interno di una rete di computer. I sistemi P2P sono costruiti connettendo diversi computer (chiamati nodi o peer) per creare una rete virtuale, chiamata overlay network (v. gura 1.1) che si pone al di sopra della rete sica.

Nell'ultimo decennio e in particolare negli ultimi anni abbiamo assistito all'evo-luzione dei sistemi P2P (v. gura 1.2): a partire da soluzioni centralizzate, con

1.1. INTRODUZIONE AI SISTEMI DISTRIBUITI 3

Figura 1.2: Sistema CS e evoluzione dei sistemi P2P

organizzazione non strutturata dell'informazione (centralizzati [21, 22], puri [23, 24, 25, 21, 22], ibridi[21]) no ad arrivare ad approcci più strutturati dove le informazioni sono ben strutturate per migliorare il recupero dei dati.

I sistemi P2P esistenti sono utilizzati soprattutto per la condivisione di le e il loro recupero (le sharing, Napster[20, 29], il noto sistema di condivisione di le, è un esempio di applicazione P2P di prima generazione), per il calcolo distribuito (ad esempio il progetto SETI); solo negli ultimi anni si stanno diondendo anche approcci che utilizzano reti P2P per gli ambienti virtuali distribuiti. Solipsis, VAST e altri ne sono degli esempi che prenderemo in considerazione nelle sezioni successive.

Nello sviluppo di DVE attraverso modelli P2P emergono diversi problemi come la consistenza dello stato, la persistenza dello stato e la reattività del sistema.

Lo stato dell'applicazione è completamente distribuito tra i peer del sistema; l'assenza di una entità centralizzata che ha il compito di mantenere lo stato comporta lo sviluppo di tecniche per la corretta sincronizzazione e comunicazione tra i peer.

I principali aspetti che si devono considerare nello sviluppo di una applicazione DVE su larga scale sono i seguenti:

ˆ Consistenza: Garantire la consistenza dello stato signica garantire a ogni partecipante una visione del mondo virtuale che lo circonda il più possibile corretta [26], [27], [28]. Ciò si realizza attraverso la corretta manutenzione dello stato condiviso e la sincronizzazione degli eventi.

ˆ Performance/Reattività: Spesso le applicazioni DVE richiedono interazioni in real time tra i partecipanti, dunque è importante garantire la tempestività delle loro interazioni. I limiti della percezione umana [10] possono parzialmente nascondere i ritardi dovuti alle comunicazioni, mostrando all'utente eventi che soddisfano l'istantaneità e la simultaneità, entrambe ideali.

ˆ Sicurezza: Nelle applicazione come i MMOG i partecipanti concorrono per il raggiungimento di certi obiettivi. Occorre fornire l'autenticazione dei parteci-panti e la correttezza nello svolgimento della logica dell'applicazione.

ˆ Scalabilità: La scalabilità si denisce in base al massimo numero di utenti che il sistema può supportare contemporaneamente. Se il numero di utenti connessi contemporaneamente è molto elevato il sistema potrebbe fallire. ˆ Persistenza: Una caratteristica desiderabile nei DVE è la persistenza di

al-cuni di tipi di informazioni come ad esempio oggetti relativi all'applicazione, in modo tale da poter essere recuperati dall'utente anche in sessioni diverse. ˆ Adabilità/Tolleranza ai guasti: La partecipazione al sistema di un

uten-te è compromessa se la sessione si inuten-terrompe improvvisamenuten-te a causa del fallimento del server. L'adabilità del sistema garantisce una buona qualità del servizio fornito.

Gli approcci attuali più diusi per l'implementazione di DVE ricorrono a soluzio-ni centralizzate: cluster di server oppure server multipli dove ogsoluzio-ni server mantiene una diversa regione del mondo virtuale. I sistemi basati su soluzioni centralizza-te presentano problemi sia di progettazione dell'applicazione sia di costi elevati in termini di banda lato server e risorse CPU limitate.

Rispetto all'architettura CS i sistemi P2P orono diversi vantaggi come: ˆ scalabilità

1.1. INTRODUZIONE AI SISTEMI DISTRIBUITI 5 ˆ accessibilità

ˆ tolleranza ai guasti

a discapito della coerenza e sincronizzazione.

Il problema di rappresentare un ambiente virtuale distribuito può essere denito nel seguente modo: è dato un insieme di punti, chiamati nodi; ogni nodo può eseguire spostamenti su un piano in tre dimensioni, ossia il mondo virtuale. In questo contesto gli aspetti chiave sono:

ˆ località

ˆ vincoli temporali

Per quanto riguarda il primo punto deniamo per ogni nodo l'Area of Interest (AOI) cioè una parte del mondo virtuale rappresentata da un disco di raggio ssato con centro il nodo stesso; tutti i nodi che si trovano all'interno dell'AOI di un certo nodo sono chiamati vicini AOI. Ogni nodo mantiene solo la conoscenza dei vicini AOI; dunque, ha una visione locale dell'ambiente che lo circonda. Con il termine consistenza di solito si intende la sincronizzazione dello stato e degli eventi tra i partecipanti di una applicazione distribuita. Nel contesto delle reti P2P il concetto di consistenza si riferisce alla consistenza topologica al ne di fornire a ogni partecipante una rappresentazione corretta dell'ambiente che lo circonda. Dunque la consistenza è rispettata se ogni nodo del sistema P2P mantiene la conoscenza della propria AOI e quindi dei vicini (nodi che si trovano all' interno dell'AOI).

I nodi di un sistema DVE interagisco in real time, dunque per realizzare corret-tamente la logica dell'applicazione occorre rispettare dei vincoli temporali: il peer deve eseguire certe azioni in un preciso istante anchè si producano risultati corret-ti, consistenti e tempestivi sia per il peer stesso che per gli altri peer. Tuttavia alcuni ritardi non possono essere evitati, come la latenza di trasmissione dei messaggi.

1.2 Solipsis

Solipsis [1], [2] propone la creazione di una rete di nodi dove la responsabilità delle relazioni tra le entità è distribuita tra gli stessi partecipanti, attraverso meccanismi collaborativi tra le unità. Una organizzazione di questo tipo gode del vantaggio di poter evitare controlli centralizzati in quanto i nodi sono autonomi. Il sistema assume una certa organizzazione che emerge dall'azione coordinata di tutti i nodi che ne fanno parte.

Mondo Virtuale Il mondo virtuale di Solipsis è rappresentato dalla supercie di un toro T = (x, y) ∈ Nsizex × Nsizey

. La notazione Nk indica l'insieme degli interi

positivi modulo k, mentre sizex e sizey rappresentano la dimensione del mondo di

Solipsis. Ogni punto e può essere rappresentato nel toro da un numero innito di posizioni

{xe+ (m ∗ sizex), ye+ (n ∗ sizey); m, n ∈ Z}

Il toro, inoltre, possiede localmente le proprietà del piano.

Entità L'entità è denita come una istanza di un programma eseguita su una macchina connessa in rete. Ogni entità e che entra a far parte del sistema è ca-ratterizzata da un identicativo unico e dalla posizione pos(e) occupata nel mondo virtuale in un certo istante. Ad ogni entità e è associato un ambiente virtuale locale anche chiamato Area of Interest (AOI): questa zona è rappresentata da un disco A(e) di raggio r(e) e centro pos(e).

Relazioni Due entità si conoscono e quindi hanno la possibilità di interagire solo quando esiste un canale di comunicazione tra esse. Attraverso una fase di inizia-lizzazione le entità si scambiano reciprocamente informazioni come le posizioni che occupano e la dimensione dell'ambiente virtuale locale, dopo di che mantengono la connessione scambiandosi regolarmente messaggi. Data una certa entità e deniamo con k(e) l'insieme di tutti i suoi vicini, cioè tutte le entità e0 _{connesse direttamente}

con e.

1.2. SOLIPSIS 7 Conoscenza Locale

Chiamiamo A(e) = {p ∈ V : pos(p) ∈ A(e)} l'insieme delle entità situate nell'am-biente locale di e. La proprietà è rispettata se l'entità e è connessa con tutte le entità appartenenti a A(e). In altri termini, e rispetta la proprietà quando conosce tutte le entità che appartengono al suo ambiente virtuale locale.

Proprietà 1 Conoscenza Locale

Un'entità e verica la proprietà di Conoscenza Locale quando:

∀e ∈ V, A(e) ⊆ k(e) Connessione Globale

Il grafo G = (V, E) è un grafo connesso: per ogni coppia di entità e, e0 _{∈ V esiste un}

insieme di archi appartenenti a E che costituiscono un cammino tra le due entità. Introduciamo la notazione ∠(e0 _{e e}00_{) per indicare l'angolo in e tra [e, e}0_{] e [e, e}00_].

Una entità ei appartiene al settore ∇(e0 e e00) quando ∠(e0 e e00) = ∠(e0 e ei) +

∠(ei e e00). Il successore di una entità e0 rispetto all'entità e0 é denita come:

se0e0 = e00 ⇔ ∀e /∈ k(e0) : e ∈ ∇(e0 e0 e00)

Generalizzando, il pesimo _{successore di e}0 _{rispetto ad e viene indicato s}p ee

0 _{mentre il}

predecessore di e0 _{è s}−1 e e

0_.

Proprietà 2 Connessione Globale

Un'entità e verica la proprietà di Connessione Globale quando:

∀e0 ∈ k(e) : see0 = e00 ⇒ ∠(e0 e e00) < π

Si può anche vericare il rispetto della proprietà di Connessione Globale attra-verso il costrutto geometrico dell'involucro convesso.

L'involucro convesso di un insieme di punti S (nel nostro caso i punti rappresentano le entità) è il più piccolo poligono convesso contenente tutti i punti di S. Dato il sottoinsieme V0 _{⊆ V indichiamo con CH(V}0_{) l'insieme dei punti che si}

trova-Figura 1.3: Involucro convesso formato dai nodi adiacenti in nodo e: la situazione mostrata a sinistra rispetta la Proprietà di Connessione Globale mentre quella di destra no.

no nell'invucro convesso di V0_{. Una entità e rispetta la proprietà di Connessione}

Globale se

pos(e) ∈ CH(k(e))

A causa della dinamicità del sistema, nell'istante t le proprietà sono rispettate mentre nell'istante t + δ ciò potrebbe non essere più valido. Questo si verica ad esempio quando uno dei vicini di una certa entità si allontana.

Quando un'entità rileva due entità consecutive (nel senso geometrico già esposto) e1 e ef con ∠(e1 e ef) ≥ π (esiste un settore di ampiezza maggiore uguale a 180°

entro il quale non ci sono vicini), allora inzia la ricerca di una o più entità nel settore ∇(e1 e ef).

Se e1 rispetta la proprietà 2, allora è connessa ad una entità e2 che si trova nel

semipiano delimitato dalla retta ∆1 e che verica ∠(e2 e ef) < ∠(e1 e ef).

Ora di possono vericare de casi:

ˆ Se l'angolo ∠(e2 e ef) < π l'entità e rispetta la proprietà 2.

ˆ Altrimenti l'entità e deve ripetere lo stesso procedimento per il settore ∇(e2 e ef).

Allo stesso modo, se e2 rispetta la proprietà 2 conosce un'entità e3 nel

semi-piano delimitato dalla retta ∆2.

1.2. SOLIPSIS 9

Figura 1.4: L'entità e ripristina la Proprietà di Connessione Globale

tali che ∠(e1 e ef) < ∠(ei−1 e ef). La ricerca termina quando e scopre un'entità ei

tale che ∠(ei e ef) < π.

Collaborazioni spontanee tra le entità

Una entità a avverte una entità b quando individua una entità c che entra nell'am-biente virtuale locale di b. Un avvenimento di questo tipo si può vericare quando l'entità c si sposta oppure quando il raggio di connessione di b si modica. Dunque è importante notare che il comportamento di a è a favore di b e di c; allo stesso tempo però a può contare sulla collaborazione di b e c: è proprio questa la collaborazione tra i partecipanti.

Connessione al mondo virtuale

Solipsis prevede delle procedure che consentono ad un'entità che vuole entrare a far parte del sistema di acquisire la conoscenza dell'ambiente circostante e quindi rispet-tare le regole. Sia e la nuova entità, caratterizzata da una posizione target (xe, ye)

(la posizione che vuole assumere nel sistema) e supponiamo che sia a conoscenza di un'entità e0 già connessa al sistema.

Solipsis propone un algoritmo che prende come parametro la posizione target e restituisce le entità vicine a questa posizione.

Il primo passo dell'algoritmo consiste nell'invio da parte di e a e0 di un messaggio

contenete il suo identicativo e la posizione target. Alla ricezione di questo messaggio e0 individua un'entità e1 ∈ {k(e0) ∪ {e0}} la cui posizione sia la più vicina alla

posizione target di e. L'entità e0 inoltra il messaggio a e1, la quale ripeterà lo stesso

procedimento.

Alla ne si arriverà ad un'entità en che non conosce altre entità più vicine alla

posizione target che essa stessa. Notiamo però che en non è necessariamente l'entità

più vicina in assoluto a (xe, ye) e la seconda parte dell'algoritmo esegue questa

verica. L'entità en individua un'entità em ∈ {k(en) 6 {en}} la cui posizione sia la

più vicina alla posizione target di e; a questo punto em apre una connessione con e.

em ripete lo stesso procedimento individuando l'entità em+1 ∈ {k(em) 6 {en}}

più vicina ad e. Dopo di che em confronta le due distanze d(e, em+1)e d(e, en):

ˆ Se em+1 è più vicina ad e rispetto a en, è certo che en non può essere l'entità

più vicina ad e. L'algoritmo riprende dalla prima fase rimpiazzando l'entità e0 con l'entità em+1.

ˆ Se invece che en è la più vicina ad e, em invia il messaggio all'entità più vicina

ad e appartenente al semipiano delimitato dal segmento (e, em).

Questa operazione si ripete ricorsivamente nchè il messaggio non attraversa di nuovo il segmento (e, en).

Tutte le entità che si scoprono lungo il cammino aprono delle connessioni con e e quindi si viene a formare l'involucro convesso richiesto per il rispetto della proprietà 2.

1.3 VON: Voronoi-based Overlay Network

VON [3], [4], [5] propone una architettura peer-to-peer completamente distribuita, con l'obiettivo di ottenere la scalabilità in maniera semplice ad eciente. Il metodo di VON si basa sul costrutto matematico dei diagrammi di Voronoi.

Dato un mondo virtuale rappresentato da un piano in due dimensioni, le entità si muovono continuamente al suo interno. Ogni entità e che entra a fare parte del siste-ma è caratterizzata da una Area di Interesse (AOI ) e tutti i nodi che appartengono a questa zona sono chiamati vicini di e.

1.3. VON: VORONOI-BASED OVERLAY NETWORK 11

Figura 1.5: (a)I punti indicano i siti, le linee delimitano i conni delle regioni. (b) I quadrati rappresentano i vicini inclusi; i triangoli rappresentano i vicini di conne;le stelle sono sia vicini inclusi che di conne; i cerchi rappresentano i vicini AOI normali.

Diagrammi di Voronoi Sia N un insieme nito di punti nel piano. Un dia-gramma di Voronoi è una rappresentazione delle relazioni di vicinanza dei punti appartenenti ad N su un piano. Dato un punto p ∈ N, chiamiamo questo punto sito e indichiamo con V (p) la regione di Voronoi di p:

V (p) = {x ∈ R2 | d(x, p) < d(x, y) ∀y ∈ N 6 {p}}

ovvero il luogo dei punti del piano più vicini a p che a qualunque altro punto in N 6 {p}. Il diagramma di Voronoi può essere utilizzato per trovare facilmente i k vicini di un certo sito. Nel diagramma possiamo individuare vicini di conne, vicini inclusi e vicini AOI. Si deniscono vicini inclusi del sito a i siti le cui regioni hanno un lato in comune con la regione di a. I vicini di conne di a invece, sono i siti le cui regioni si sovrappongono al conne della AOI di a; i vicini AOI sono siti le sui regioni appartengono all'AOI(indicati con • nella gura 1.5). Notiamo che alcuni siti possono essere sia vicini di conne che vicini inclusi, come mostrato in gura 1.5.

Struttura del sistema

Ogni nodo è responsabile della costruzione e gestione un diagramma di Voronoi in modo da tener traccia dei vicini all'interno della propria AOI; inoltre il nodo mantiene connessioni dirette con tutti i siti che sono propri vicini. Per assicurare che la topologia della rete sia connessa ogni nodo deve conoscere almeno tutti i vicini inclusi. Quindi ogni nodo ha una visione parziale del mondo: conosce solo un numero limitato di vicini; tuttavia i vicini di conne giocano un ruolo importante nella fase di scoperta di nuovo vicini.

Descriviamo ora le principali procedure previste da VON per la connessione al mondo virtuale, lo spostamento e la disconnessione.

Connessione

Supponiamo che ogni nodo che vuole entrare nel sistema conosca il gateway server indicato con n0, cioè un nodo già connesso e preposto alla generazione di identicativi

unici da assegnare ai nuovi nodi. Indichiamo con ni il nodo che vuole unirsi al

sistema.

1. ni richiede al gateway server n0 un ID.

2. ni invia a n0 la richiesta di ingresso al sistema specicando la posizione che

vuole assumere nel mondo virtuale.

3. Il messaggio viene inoltrato alla regione che contiene la posizione target spe-cicata da ni.

4. Il nodo responsabile per quella regione invia a ni la lista dei propri vicini.

5. ni apre una connessione con ognuno dei nodi della lista ricevuta; a loro volta

questi aggiornano la propria regione di Voronoi. 6. ni costruisce la propria regione di Voronoi.

1.3. VON: VORONOI-BASED OVERLAY NETWORK 13 Spostamento

Indichiamo con ni il nodo che eettua lo spostamento e con pos(ni) la nuova

posi-zione.

1. ni invia un messaggio contenente la nuova posizione a tutti i vicini (interni, di

conne e i vicini all'interno della propria AOI). I messaggi destinati ai vicini di conni hanno una marca speciale.

2. I vicini di conne controllano se la AOI del nodo, dopo lo spostamento, si sovrappone a qualcuna delle regioni di un proprio vicino incluso. Oppure può vericarsi che dopo lo spostamento ni abbia un nuovo vicino incluso.

3. Se sono stati trovati nuovi vicini ni si connette con loro.

4. ni si disconnette dai vicini di conne le quali regioni non si sovrappongono più

alla propria AOI. Disconnessione

La procedura di disconnessione di un nodo dal sistema comporta l'aggiornamento della regione di Voronoi da parte di tutti i suoi vicini. Se uno dei vicini di conne si disconnette esso sarà rimpiazzato grazie alla collaborazione dei rimanenti vicini di conne.

Modello di inoltro del messaggi

Le procedure appena descritte fanno riferimento ad un modello di connessione di-retta: ogni nodo mantiene una connessione diretta con ognuno dei propri vicini dell'AOI. In questo modello si pone il problema della banda di trasmissione nel caso in cui i vicini dell'AOI siano molto numerosi. Una possibile soluzione al problema è la diminuzione del raggio dell'AOI che comunque comporterebbe una riduzione dell'area visibile per il nodo.

Un altro tipo di approccio al problema è la costruzione un nuovo modello di con-nessione tra nodi: il forwarding model. L'idea principale è che ogni nodo mantiene connessioni dirette solo con i vicini inclusi; saranno poi quest'ultimi a inoltrare i messaggi ad altri nodi. Adottando questo modello ogni nodo diminuisce il numero

di connessioni dirette mantenendo allo stesso tempo una buona visibilità della pro-pria AOI. Per il corretto funzionamento di questo modello e dunque garantire che i messaggi vengano inoltrati a tutti i nodi interessati è fondamentale che la lista dei vicini inclusi di ogni nodo sia corretta e sempre aggiornata.

Consistenza dei vicini

La qualità del grado di connessione tra i nodi di un sistema può essere misurata attraverso la seguente formula che esprime la consistenza dei vicini.

N Ni numero di vicini AOI di cui il nodo i è a conoscenza

Ni numero eettivo di vicini AOI del nodo i

n numero totale di nodi del sistema

N Ci =

N Ni

Ni

consistenza dei vicini per il nodo i N C =

Pn

x=0N Ci

n consistenza dei vicini del sistema

Le principali cause di degradazione della consistenza dei vicini sono: perdita dei pacchetti, mobilità dei nodi, guasti ai nodi.

Perdita dei pacchetti In un ambiente distribuito basato su protocolli di rete come IP che non garantiscono l'adabilità, la perdita di pacchetti è un fattore che deve essere preso in considerazione. Gli autori aermano che la perdita di pacchetti può essere tollerata in molte situazioni mantenendo una suciente consistenza dei vicini.

Mobilià Negli ambienti virtuali distribuiti i nodi si spostano velocemente in di-verse aree del mondo virtuale; la soluzione presentata dall'autore introduce una estensione dell'AOI mantenuta come un buer e chiamata adaptive AOI buer.

1.3. VON: VORONOI-BASED OVERLAY NETWORK 15 Guasti ai nodi Nel mondo virtuale accade spesso che i nodi non siano distribui-ti in maniera uniforme sul territorio ma essi si concentrino in aree di pardistribui-ticolare importanza. Situazioni di questo tipo si vericano al seguito di eventi particolari che richiamano l'attenzione di molti nodi (giocatori), i quali si spostano nelle aree interessate.

In questi casi assistiamo alla formazione di diversi gruppi di nodi e tra questi gruppi troviamo solo pochi nodi i quali rappresentano l'unico mezzo di comunicazione per i nodi appartenenti ai diversi gruppi. Dunque è chiaro che il fallimento simultaneo di questi nodi porta alla formazione di partizioni di nodi disgiunte (∃x, y : x e y non hanno modo per comunicare).

Gli autori di [3] propongono un metodo per individuare i nodi critici, cioè quei nodi che hanno un numero molto limitato di vicini, e duplicare il loro stato.

Introduciamo la seguente denizione di Neighbor_level:

N eighbor_level = AOI_neighbor

AV G_AOI_neighhbor (1.1)

AV G_AOI_neighbor = T otal_AOI_neighbor

N eighbor (1.2)

AOI_neighbor è il numero di vicini del nodo

T otal_AOI_neighbor rappresenta in numero complessivo dei vicini

Ogni nodo ni calcola il proprio Neighbor_level attraverso l'equazione 1.1: se il

valore ottenuto è molto basso oppure prossimo allo zero allora ni è un nodo critico

ed inizia l'operazione di backup descritta di seguito. Indichiamo con nl(n) la lista dei vicini di un nodo n.

ˆ ni invia un messaggio di backup ad ogni nk ∈ nl(ni); il messaggio consiste

nella propria lista dei vicini nl(ni).

ˆ Ogni nodo nk che riceve questo messaggio esegue il seguente controllo:

ˆ se ∃n ∈ nl(ni)tale che n /∈ nl(nk) allora nk aggiunge n alla sua stock neighbor

Questa ulteriore struttura dati viene mantenuta da ogni nodo per evitare la forma-zione di partizioni e la sua dimensione è limitata; per il rimpiazzamento dei nodi si utilizza una politica FIFO.

Mantenimento della consistenza dei vicini

ˆ Periodicamente ogni nodo n invia un messaggio check a ogni nodo u della propria snl

ˆ Il nodo u destinatario del messaggio invia al mittente la propria lista dei vicini nl(u).

ˆ Dopo aver ricevuto nl(u) il nodo n esegue i seguenti controlli:

 se nessuno dei nodi v ∈ nl(u) è un vicino dell'AOI di n, allora n non esegue nessuna operazione

 se ∃v ∈ nl(u) tale che è un vicino dell'AOI di n di cui n è già a conoscenza, allora n non esegue nessuna operazione

 se ∃v ∈ nl(u) tale che dovrebbe essere vicino dell'AOI di n, ma non lo è, n aggiunge v alla propria nl(n) e si connette a v

Confronto tra VON e Solipsis

I due sistemi analizzati hanno molti aspetti in comune: ogni nodo mantiene un certo numero di vicini e la overlay network è mantenuta grazie alla collaborazione tra i nodi stessi. Non si introducono punti di centralizzazione oppure nodi con compiti di gestione della rete.

La dierenza principale è data nei concetti matematici e geometrici che regolano il mantenimento dei vicini di ogni nodo. Von si basa sul concetto dei diagrammi di Voronoi mentre Solipsis richiede che ogni nodo sia contenuto nell'involucro convesso formato dai propri vicini.

Notiamo che l'insieme dei vicini inclusi costituisce anche un involucro convesso, quindi VON soddisfa sempre i requisiti di Solipsis. Tuttavia ci sono dei casi di scarsa ecienza per entrambi i sistemi:

1.3. VON: VORONOI-BASED OVERLAY NETWORK 17

Figura 1.6: Caso sfavorevole per Solipsis

Figura 1.7: Caso sfavorevole per VON

ˆ In Solipsis un nodo potrebbe non scoprire un suo vicino come mostrato in gura 1.6, anche se gli autori indicano questo caso molto raro.

ˆ In VON potrebbero presentarsi situazioni dove i vicini di un nodo sono distri-buiti circolarmente intorno ad esso (v. gura 1.7); questi sono dei vicini inclusi e il nodo sarebbe costretto a mantenere un numero elevato di connessioni. Gli autori ritengono che questo caso sia raro.

1.4 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 veriveri-care 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 ricalcolaoppu-re 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 appartenente alla frontiera FAB è visibile ad una appartenente alla frontiera FBA

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ò vericarsi 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, vericando 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 è dicilmente 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 modicabile ˆ Oggetti con stato: Oggetti modicabili 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 modicabile. 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 modiche 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 modica 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 identicatori. Si possono ottenere identicatori 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 identicativo viene mappato sul nodo il cui ID è numericamente più vicino all'identicativo 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 eciente. Ogni nodo della DHT mantiene dei puntatori ai nodi vicini in entrambi i lati; si deniscono 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, identicato 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 identicativo 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.

nu-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 vericarsi 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 adamento 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 modiche 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 una maggiore densità di popolazione si stabilisce una dimensione maggiore dell'area

ˆ ripartizione dinamica dello spazio in regioni per far fronte all'aumentare del numero di clienti connessi; combinare questo approccio con la progettazione del sistema nel suo complesso comporta delle dicoltà dovute principalmente alla ri-allocazione dei nodi coordinatori.

SimMud rappresenta un importante tentativo alla costruzione e gestione di un ambiente virtuale completamente distribuito; tuttavia l'utilizzo di DHT si rivela più adatto in contesti diversi come ad esempio il le sharing. Abbiamo visto che SimMud presenta diversi punti deboli come la presenza di punti di centralizzazione e dicoltà nel raggiungere la scalabilità.

1.6 Tecniche di scambio delle liste dei vicini

Negli ambienti virtuali distribuiti la parte più signicativa dei messaggi scambiati attraverso la rete dai peer riguarda informazioni di aggiornamento delle posizioni all'interno del mondo virtuale. Questi messaggi sono fondamentali per assicurare che ogni peer disponga di informazioni consistenti sul mondo virtuale a cui appartiene. Quando il numero di partecipanti all'applicazione distribuita aumenta la scalabilità è un aspetto molto importante: anche se la dimensione dei singoli messaggi scambiati è modesta i ritardi di trasmissione devono essere contenuti il più possibile.

A questo scopo gli autori di [9] propongono un sistema completamente distribuito per lo scambio eciente dei messaggi di aggiornamento tra i client dell'applicazione senza introdurre supporti particolari per la comunicazione in multicast e senza adarsi a soluzioni centralizzate caratterizzate da forti investimenti iniziali.

Il sistema proposto è strutturato in maniera completamente decentralizzata; le entità stesse che formano il sistema sono responsabili della formazione e manuten-zione della overlay network. Inoltre viene utilizzato il concetto di area di interesse e di interest management come strumenti di ltraggio dei messaggi; si ricevono in maniera dettagliata i messaggi provenienti da nodi vicini e si ignorano quelli

prove-nienti da nodi troppo lontani per poter inuire sulle scelte della entità.

Ogni entità dell'applicazione mantiene connessioni dirette solo con un sottoinsie-me di altre entità formando in questo modo una overlay network basata sul protocollo IP.

La procedura di connessione proposta è di tipo stateless: i peer al momento della connessione al sistema non dispongono di nessuna informazione riguardante il mondo virtuale che li circonda. I nuovi peer che desiderano entrare nel sistema si connettono al bootstrap server, cioè un server che mantiene solo le informazioni riguardanti entità che sono entrate più di recente.

Lo schema appena descritto si dierenza profondamente dai sistemi centralizzati dove il server mantiene informazioni accurate su tutti i partecipanti all'applicazione, diventando un punto di centralizzazione per l'intero sistema.

Dunque nei sistemi completamente distribuiti non esiste un server che mantiene informazioni di stato aggiornate di tutti i peer; ciò va a discapito della consistenza e integrità della topologia complessiva della overlay network.

Procedura di connessione La fase di connessione di una entità al sistema si basa su informazioni fornite dal bootstrap server: l'entità si connette al server e questo gli comunica le entità che risultano più vicine alla posizione che occupa. L'entità apre delle connessioni dirette con ognuna delle entità comunicate dal server per lo scambio di messaggi di aggiornamento.

Osserviamo che le informazioni fornite dal server potrebbero non essere aggiornate e quindi non più valide a cause delle caratteristiche stesse del bootstrap server. Il sistema prevede quindi una procedura per il ripristino della overlay network a seguito della connessione di un nuovo peer, descritta di seguito.

Ogni entità chiede alle altre entità a cui è connessa la lista dei vicini. Una volta ottenute queste informazioni l'entità dispone di una conoscenza più approfondita dell'ambiente che lo circonda e classica le entità vicine in entità attive e entità latenti. La classicazione può avvenire secondo la metrica che più si adatta

all'ap-1.6. TECNICHE DI SCAMBIO DELLE LISTE DEI VICINI 27 plicazione, ad esempio la distanza euclidea tra entità.

Dopo aver determinato secondo una certa metrica le entità attive ogni entità sta-bilisce una connessione diretta con N di esse e inizia lo scambio di messaggi di aggiornamento delle rispettive posizioni.

Le entità latenti si deniscono come entità che si trovano a una distanza maggiore rispetto alle entità attive e di cui non interessa ottenere informazioni dettagliate; sono accettabili anche informazioni non precise ma solo no a quando rimangono fuori dall'area di interesse. Quando una entità latente è in fase di avvicinamento allora saranno richieste informazioni più precise sulla sua posizione in quanto po-trebbe diventare entità attiva.

Questa tecnica rientra nel concetto più generale e già citato in precedenza in que-sto capitolo di Area di Interesse di un nodo come strumento essenziale per ridurre la comunicazione tra i partecipanti al mondo virtuale e per mantenere la corretta rappresentazione della overlay network.

Gli autori hanno eseguito delle simulazioni del sistema per poi confrontare i risultati con quelli ottenuti con una implementazione centralizzata di tipo client-server dove tutte le entità del mondo virtuale informano il client-server dei loro spostamenti e il server invia i messaggi alle entità interessate.

I risultati ottenuti dalla simulazione mostrano che il modello a scambio di messaggi e il modello basato su architettura C/S sono qualitativamente molto simili.

Il principale parametro preso in considerazione per il confronto è la consistenza della overlay network nell'area di interesse di ogni entità, calcolata come

C(i) = 1 N n X i=1 P (i) Q(i) dove N è il numero totale di entità del mondo virtuale

P (i) è il numero di entità contenute nella lista di entità attive del nodo i Q(i)è il numero di entità attive per il nodo i.

Con un numero elevato di entità attive, il sistema distribuito raggiunge un livel-lo di consistenza molto elevato, circa 0.9; con un numero basso di entità attive si producono eetti negativi sulla consistenza della rete a causa della formazione di sottoinsiemi di nodi indipendenti.

Al vericarsi di questa situazione ogni nodo può comunicare solo con nodi ap-partenenti al suo stesso sottogruppo.

Le simulazioni eseguite mostrano che con almeno 8 entità attive non si verica la formazione di sottogruppi mentre con meno di 8 si assiste alla divisione della overlay network in sottogruppi.

Purtroppo non è possibile imporre ad ogni nodo del sistema un numero ssato di entità attive perché in un ambiente eterogeneo ogni nodo dispone di caratteristiche hardware e connettività alla rete diverse dagli altri nodi. Inoltre l'individuazione della formazione e della presenza di sottogruppi non è banale a causa dell'assenza di una fonte centralizzata di informazioni delle posizioni di tutte le entità. Si cerca di porre rimedio agli eetti negativi derivanti dalla formazione di sottogruppi di nodi attraverso una tecnica chiamata random introduction.

Questa tecnica viene utilizzata per spargere informazioni tra le entità apparte-nenti a gruppi diversi nel tentativo di ristabilire la connessione tra i sottogruppi: a intervalli di tempo regolari ogni entità ei si riconnette al bootstrap server scegliendo

in maniera casuale un insieme di entità E. L'entità ei si connette ad ognuna delle

entità appartenenti ad E e inizia lo scambio di messaggi di aggiornamento sulle re-ciproche posizioni nel mondo virtuale.

Attraverso questa procedura di scelta casuale delle entità è possibile mettere in comunicazione entità appartenenti a diversi sottoinsiemi.

Le simulazioni condotte su questo modello di scambio di messaggi hanno mostrato che la probabilità di riconnessione tra i sottogruppi aumenta all'aumentare della frequenza di accesso al bootstrap server per l'operazione di random introduction. D'altra parte però il frequente accesso delle entità verso bootstrap server comporta per questo un eccessivo carico di richieste e quindi si dovrebbe determinare un intervallo tra gli accessi al server che minimizzi il carico del server e allo stesso

1.7. SISTEMI CLIENT-SERVER IBRIDI 29 tempo renda soddisfacente la connessione tra i sottogruppi.

Le caratteristiche suddette rendono questo sistema simile a Solipsis e VON, in modo particolare per l'assenza di un punto di raccolta delle informazione di posi-zione delle entità e per la caratteristica di auto-organizzaposi-zione delle entità stesse. Tuttavia Solipsis e Von si basano su concetti matematici e geometrici ben deniti che permettono maggiore chiarezza nella determinazione di situazioni irregolari nella overlay network e quindi un recupero delle situazioni di inecienza.

1.7 Sistemi client-server ibridi

L'architettura proposta da federated peer-to-peer [10] è basata sulla divisione del mondo virtuale creato dal gioco (o dalla simulazione) in aree di dimensione limitata, corrispondenti alle diverse aree di interesse che si individuano. Ogni area di interesse è indipendente dalle altre e costituisce un'applicazione a se, dunque sono necessari meccanismi di comunicazione per permettere alle diverse entità di collaborare.

In confronto con l'architettura client-server, dove i costi predominanti sono dovuti alla elaborazione dello stato dell'applicazione, l'applicazione di questo modello ai sistemi distribuiti comporta costi dovuti principalmente alle frequenti comunicazioni tra i nodi.

La progettazione del sistema è basata sul concetto di interest management: si inviano pacchetti solo al sottoinsieme di clienti per i quali le informazioni che si stanno inviando sono davvero rilevanti.

Un client si iscrive ad una area di interesse per ricevere le informazioni inviate dalle altre entità che appartengono a quell'area. I clienti possono sottoscriversi ad una o più aree di interesse.

Multicast Reector L'implementazione del multicast è realizzata attraverso la tecnica dei multicast reectors: entità in grado di mantenere la lista dei client sot-toscritti ad una certa area di interesse e di disseminare i pacchetti tra essi.

tutti i client di una certa area. Quando un client sottoscrive un certo peer group esprime l'interesse nel ricevere tutti gli aggiornamenti che riguardano quel gruppo.

Control Server I control server rappresentano entità alle quali è adato il compi-to di mantenere la corretta corrispondenza tra aree di interesse e multicast reeccompi-tor; essi devono anche gestire casi come il fallimento di alcuni multicast reector oppure la creazione di un nuovo mapping per ottenere un bilanciamento del carico adeguato. Inoltre i control server devono informare i client sottoscritti alle aree che sono state interessate dai suddetti cambiamenti e fornire le informazioni per eseguire la con-nessione ai nuovi multicast reector.

I control server hanno anche il compito di mantenere la struttura dell'applicazione: partizione del mondo virtuale in aree di interesse, autenticazione dei client, account utenti e altri dati dell'applicazione.

I control server intervengono solo in poche fasi e la parte centrale delle elabora-zioni speciche dell'applicazione sono eseguite dagli utenti stessi. Questo permette al provider dell'applicazione di ridurre in maniera drastica i costi perché sono i client stessi ad eseguire la logica dell'applicazione.

Struttura del mondo virtuale In mondo virtuale dell'applicazione è diviso in aree di interesse; come detto sopra questa ripartizione è mantenuta dai control server. Ogni locazione dello spazio virtuale è rappresentata da un numero intero positivo; quando necessario, sarà il client ha eseguire la conversione di questo numero con il corrispondente valore della locazione (ad esempio un punto in tre dimensione nello spazio virtuale).

Avvio del client La fase di join di un peer prevede che il peer stesso contatti un control server, informandolo dell'area di interesse nella quale vuole inserirsi. Il control server mantiene il mapping tra i reector e le aree di interesse, dunque in base alle informazioni specicate dal peer determina i reector ai quali esso deve sottoscriversi.

Traco di rete La latenza di trasmissione dei pacchetti tra i client dell'applicazio-ne è un parametro fondamentale infatti un pacchetto che arriva in ritardo potrebbe