1 Introduzione 1
2 Stato dell’arte 9
2.1 Distributed Virtual Environment (DVE) . . . 9
2.2 SOLIPSIS . . . 13
2.3 VON: Voronoi-based Overlay Network . . . 19
2.3.1 Diagrammi di Voronoi . . . 19
2.3.2 Triangolazione di Delaunay . . . 22
2.3.3 VON - Struttura di una Voronoi Overlay Network . . . 24
3 X-Nomade 27 3.1 Architettura del sistema . . . 27
3.1.1 Struttura generale e definizioni . . . 27
3.2 Costruzione di una overlay network . . . 30
3.2.1 Connettivit`a e scoperta dei vicini . . . 31
3.2.2 Associazione di un nodo ad una overlay network . . . . 35
3.3 X-Nomade: versione routing con tutti i vicini . . . 41
3.3.1 Valutazione dei links con soli vicini di Voronoi . . . 41
3.3.2 Spostamento di un nodo . . . 41
3.3.3 Valutazione dei links con area dei links diretti . . . 46
3.4 Invio heartbeat: uso di compass routing . . . 48
3.4.1 Descrizione algoritmo . . . 52
3.5 Discovery dei vicini . . . 58
3.6 Uscita volontaria di un nodo . . . 60 i
4 X-Nomade: Implementazione 63
4.1 Packages . . . 63
4.1.1 WorldMap . . . 66
4.1.2 I/O . . . 67
4.2 X-Nomade: versione routing con tutti i vicini . . . 69
4.2.1 Routing con i soli vicini di Voronoi . . . 69
4.2.2 Routing Area Interna . . . 75
4.3 X-Nomade: Compass routing . . . 80
4.4 X-Nomade: API . . . 82
5 X-Nomade: Risultati Sperimentali 87 5.1 L’ambiente Grid5000 . . . 87
5.1.1 Grid’5000 interconnection . . . 90
5.1.2 Rennes Grid’5000 site . . . 94
5.1.3 Portale Grid’5000 . . . 98 5.1.4 I vari siti . . . 98 5.1.5 Utilizzo di Grid’5000 . . . 100 5.1.6 Principali comandi . . . 101 5.1.7 Installare i dati . . . 104 5.1.8 Script X-Nomade . . . 105
5.2 Valutazione delle topologie . . . 109
5.2.1 Configurazione e descrizione dei test . . . 109
5.3 Valutazione del routing . . . 118
5.3.1 Configurazione e descrizione dei test . . . 118
6 Conclusioni 125
Bibliografia 135
Introduzione
Il rapido evolvere della tecnologia e di conseguenza dei supporti sviluppati per le reti ha fatto si che negli ultimi anni si siano diffuse applicazioni come le MMOG (Massively Multiplayer Online Games) [1]. Queste sono applicazioni per personal computer capaci di potere supportare contemporaneamente pi`u giocatori connessi tramite il loro PC al mondo virtuale per poter competere, combattere o interagire con gli altri giocatori. Naturalmente il pi`u delle volte gli attori di queste applicazione sono persone residenti nell’altra parte del globo, esempi famosi sono World Of Warcraft [14], Second Life [2], e tanti altri giochi virtuali online.
L’espansione di queste applicazioni `e stata possibile grazie alla diffusione e allo sviluppo dei cosiddetti ambienti virtuali distribuiti (DVE) [30], [31], [32], [33], che si possono definire, applicazioni che supportano spazi virtuali dove pi`u utenti, rappresentati da avatars, interagiscono tra loro in tempo reale scambiandosi messaggi attraverso la rete.
Infatti gli utenti di queste applicazioni hanno la possibilit`a di connettersi al loro mondo virtuale, ed effettuare diverse azioni come cambiare la loro posizione, disconnettersi, o fare altre azioni in un qualsiasi momento. Le ap-plicazioni di questo tipo pi`u diffuse si basano su architettura di rete del tipo Client-Server [34], naturalmente questo porta a caricare sul singolo server la gestione di tutto lo stato dell’applicazione. Quindi ci si basa sul server
per garantire una corretta interazione tra gli attori dell’applicazione. Sar`a quindi compito dei vari client inviare i loro messaggi al server centrale che aggiorner`a lo stato del DVE e a sua volta informer`a tutti i client del nuovo stato.
Si pu`o ben capire come in un’architettura Client/Server, il server sia il punto di centralizzazione per l’intera applicazione e possa rappresentare un even-tuale collo di bottiglia per l’intera applicazione, inoltre pu`o essere un punto di fallimento del sistema. Analizzando il fattore scalabilit`a `e facile intuire come all’aumentare del numero di utenti di una applicazione distribuita aumenti anche il numero di messaggi scambiati attraverso la rete, e di conseguenza la scalabilit`a pu`o diventare un problema rilevante in applicazioni di questo tipo, quindi possiamo notare come il modello CS [34] non risponda a caratteristiche ottimali per questo tipo di applicazioni. Questi motivi hanno spinto verso la definizione di architetture che non prevedono la presenza di un unico punto di centralizzazione come un server centralizzato ma che si basano su modelli completamente distribuiti. Fanno parte di questa categoria di architetture le reti Peer to Peer (P2P)[24].
Un sistema P2P `e definito da un insieme di entit`a autonome capaci di au-torganizzarsi, che condividono un insieme di risorse distribuite all’interno di una rete di computer. Un sistema P2P non `e altro che una rete paritaria di computer che non definisce una gerarchia tra nodi come client o server fissi (clienti e serventi), ma bens`ı un numero di nodi equivalenti (pari, in inglese
peer appunto) che fungono sia da cliente che da servente verso altri nodi
della rete. Questo modello di rete `e l’antitesi della cosiddetta architettura
cliente-servente, ed `e infatti grazie a questa configurazione che qualsiasi nodo
`e in grado di avviare o completare una transazione autonomamente. I nodi possano differire nella configurazione locale, nella velocit`a di elaborazione, nell’ampiezza di banda e nella quantit`a di dati memorizzati.
Nell’ultimo decennio e in particolare negli ultimi anni abbiamo assistito al-l’evoluzione dei sistemi P2P. A partire da soluzioni centralizzate, con orga-nizzazione non strutturata dell’informazione (centralizzati puri) si arriva ad
approcci dove le informazioni sono ben strutturate per migliorare il recupero dei dati.
Esistono due topologie di sistemi P2P:
• Sistemi non strutturati.
• Sistemi strutturati.
Nei sistemi P2P Non Strutturati[17], [18], ogni risorsa presente nella rete `e localizzata sul nodo che la mette a disposizione, non esistono informazioni relative alla loro locazione e la ricerca risulta essere difficoltosa a causa del-la mancanza di organizzazione all’interno del sistema. D’altra parte, del-la ri-mozione o l’aggiunta di nodi dalla rete `e un’operazione semplice e poco cos-tosa. Fanno parte dei sistemi P2P non strutturati Napster [11], [22], [23] e Gnutella [12], [37], [38].
I sistemi P2P esistenti sono utilizzati soprattutto per la condivisione di file e il loro recupero (file sharing, Napster, il noto sistema di condivisione, `e un esempio di applicazione P2P di prima generazione), per il calcolo distribuito (ad esempio il progetto SETI[36]). Solo negli ultimi anni si stanno diffonden-do anche approcci che utilizzano reti P2P per gli ambienti virtuali distribuiti. SOLIPSIS [3], [4], VON [6] e altri esempi che prenderemo in considerazione nelle sezioni successive.
Ed `e proprio in questo contesto che `e nata l’idea di X-Nomade, un’appli-cazione P2P dedicata alla gestione di DVE (Distributed Virtual Environ-ment), e che si basa su Vast [6], [7], [8] per la configurazione della topologia della rete.
In X-Nomade ogni nodo ha una visione limitata del mondo virtuale. A questo proposito `e stato introdotto il concetto di area di Interesse[24], [25], [26], [27], [28], [29], [35]. L’area di interesse modella l’area del mondo virtuale con cui un giocatore pu`o interagire e pu`o essere ad esempio un cerchio centrato sul giocatore. Le aree di interesse possono essere di due tipi: fisse oppure dinamiche. Le aree di interesse fisse sono aree che hanno come centro la po-sizione del peer e raggio fisso per tutti i nodi del mondo virtuale. Nel caso di
AOI dinamiche un peer ha un raggio dell’area di interesse diverso dagli altri peer e i raggi possono cambiare dinamicamente. 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’AOI `e fondamentale, in quanto ogni utente viene influenzato soltanto da nodi od eventi che avvengono all’interno dell’AOI. Supponiamo che l’area di interesse sia una circonferenza con centro le coordinate dell’avatar, e che un nodo si muova con passi discreti. Nasce il seguente problema: come avviene la scoperta dei nodi rilevanti, se il nodo `e periodicamente in movimento? Ogni nodo crea e gestisce un proprio diagramma di Voronoi in modo da tenere traccia dei vicini all’interno della propria AOI.
I diagrammi di Voronoi[42] prendono il nome dal matematico russo Georgy Fedoseevich Voronoi, che li defin`ı e li studi`o nel 1908, generalizzandoli al caso n-dimensionale. Indichiamo con dist(p, q) la distanza Euclidea tra i punti
p e q. Sia P = {p1, p2..., pn} un insieme di n punti distinti nel piano detti
siti. Definiamo il diagramma di Voronoi di P come la suddivisione del piano in n celle, una per ogni sito in P, con la propriet`a che un punto q giace nella cella corrispondente ad un sito pi se e solo se dist(q, pi) ≤ dist(q, pj)
per ogni pj ∈ P con j 6= i. Ogni nodo gestisce un proprio diagramma di
Voronoi in cui `e presente un sito per il nodo stesso ed un sito per ogni suo vicino sull’overlay network. Tale diagramma consente di classificare i vicini come boundary neighbor e/o enclosing neighbor. I primi agiscono come delle
vedette, consentendo la scoperta di nuovi vicini in seguito ad uno
spostamen-to, mentre i secondi permettono di mantenere connessa l’overlay network e possono trovarsi anche al di fuori dell’area di interesse. In questa tesi uti-lizziamo la libreria VAST[6], [7], [8] che implementa i diagramma di Voronoi. L’AOI (Area of Interest) in applicazioni client-server `e stata introdotta per far fronte a problemi di scalabilit`a. Come dato di fatto, se non si utilizza una AOI per filtrare e ridurre le comunicazioni, se sono connessi N client al
serv-er, ogni heartbeat deve essere inviato a N-1 client. In questo modo si ha un
frequente-mente, anche ogni 200 millisecondi. `E stata introdotta l’AOI per migliorare la scalabilit`a riducendo il numero di heartbeats che deve gestisce il server. Tuttavia, anche utilizzando l’AOI, esistono situazioni in cui si possono avere problemi di scalabilit`a. Queste situazioni si verificano quando un gran nu-mero di avatar si trova in uno spazio ristretto nel mondo virtuale modellato dalla DVE. Questa situazione viene definita come crowding. Quindi l’uso di AOI di grandi dimensioni pu`o scatenare un’esplosione di messaggi. Anche se l’AOI viene ridotta al fine di ridurre il numero di messaggi, non si pu`o ridurre troppo il raggio perch´e un client deve essere consapevole degli eventi che caratterizzano il suo mondo virtuale.
Quindi l’uso di una sola AOI principale in caso di crowding (affollamento) introduce un problema riguardante la banda degli hosts. L’idea base di X-Nomade `e quella di implementare diversi modelli di interazione tra i peer che si trovano all’interno dell’AOI. Pi`u precisamente l’obiettivo che si `e prefis-sato `e stato quello di ridurre le connessioni dirette. Il rilancio dei messaggi si basa su collegamenti diretti con tutti i nodi vicini che sono compresi in una zona interna all’AOI principale. `E stato obiettivo principale della nostra tesi implementare nuove soluzioni e valutarle sviluppando un prototipo testato su una piattaforma reale. Questa tesi propone due diverse soluzioni:
• La prima effettua il routing con tutti i vicini, in particolare abbiamo due varianti:
1. Prima variante: un peer P invia un heartbeat ai vicini di Voronoi, ogni vicino reinoltra l’heartbeat a tutti i vicini che appartengono all’AOI(P), utilizzando un routing basato sul flooding.
2. Seconda variante: introduciamo l’AOI dei link diretti, che `e un’area di raggio minore rispetto all’AOI. Attraverso quest’area si fa fronte a problemi di scalabilit`a, in caso di crowding. Ogni peer sul bor-do dell’area dei link diretti provvede ad inoltrare l’heartbeat ad eventuali altri peer posizionati nella parte periferica dell’AOI.
• Nella seconda soluzione un peer P inoltra l’heartbeat ai vicini di Voronoi, ogni vicino lo rinoltra utilizzando il compass routing.
Il compass routing `e un algoritmo di instradamento applicato su grafi il cui obiettivo non `e quello di trovare il cammino pi`u breve per connettere due vertici, ma quello di garantire il raggiungimento della destinazione. In parti-colare, prendendo qualsiasi coppia di punti appartenenti alla triangolazione di Delaunay[40], il compass routing determina sempre uno ed un solo cammi-no che unisce tali punti. Icammi-noltre, questa tecnica di instradamento permette di costruire uno spanning tree a partire dalla triangolazione di Delaunay. Tale albero viene creato in maniera distribuita da ogni nodo.
Le due versioni di X-Nomade sono state valutate grazie ad un insieme di test sperimentali effettuati sia su una rete Lan che su Grid’5000 [9]. Grid’5000 `e un sistema composto da pi`u cluster eterogenei, distribuiti su siti situati sul territorio francese. I peer sono stati distribuiti uniformemente nel mondo virtuale. Inoltre durante la simulazione i peer si spostano casualmente effet-tuando un cambio di direzione all’interno del mondo. I test sono stati volti a valutare il numero medio di link diretti che ha un singolo peer durante la simulazione in caso di crowding, (per le prima versione). Per la valutazione della seconda versione (quella con il compass routing) valutiamo la consis-tenza dell’approccio attraverso il controllo della ridondanza e della perdita di messaggi.
La tesi `e strutturata come descritto di seguito. Il capitolo 2 analizza il con-testo in cui si colloca il lavoro oggetto della presente tesi: viene presentata una rassegna dei principali sistemi esistenti che realizzano ambienti virtuali distribuiti.
Nel capitolo 3 si definisce l’architettura di X-Nomade: si definiscono i concetti principali (Peer, AOI, Avatar) e tutti gli aspetti riguardanti la manutenzione della overlay network.
Il capitolo 4 descrive l’implementazione del supporto X-Nomade: vengono presentate in dettaglio le scelte effettuate, mostrando i vantaggi e svantaggi che comportano.
Infine il capitolo 5 mostra i risultati sperimentali relativi ai test eseguiti sulla piattaforma Grid’5000. Vengono confrontate le diverse soluzioni proposte e si forniscono valutazioni a riguardo. Il capitolo 6 trae le conclusioni sul lavoro svolto.
Stato dell’arte
2.1
Distributed Virtual Environment (DVE)
Si pu`o definire un ambiente virtuale distribuito o DVE [30], [31], [32], [33] (Distributed Virtual Environment) come un’applicazione distribuita che ha come scopo quello cercare di simulare al meglio un mondo bidimensionale o tridimensionale nel quale pi`u utenti interagiscono e collaborano tra loro in maniera interattiva e naturalmente in tempo reale. Un classico esempio ar-chitetturale di un applicazione virtuale dsistribuita pu`o essere rappresentato dalla figura 2.1. Possiamo analizzare come nello sviluppo di un applicazione DVE attraverso un modello P2P, emergono diverse problematiche come la consistenza dello stato, la persistenza dello stato e la reattivit`a del sistema. Lo stato dell’applicazione `e completamente distribuito tra i peer del sistema; l’assenza di una entit`a centralizzata che ha il compito di mantenere lo stato comporta lo sviluppo di tecniche per la corretta sincronizzazione e comuni-cazione tra i peer. I principali aspetti che si devono considerare nello sviluppo di una applicazione DVE su larga scale sono i seguenti:
1. Consistenza: Garantire la consistenza dello stato significa garantire a ogni partecipante una visione del mondo virtuale che lo circonda il pi`u possibile corretta . Ci`o si realizza attraverso la corretta manutenzione dello stato condiviso e la sincronizzazione degli eventi.
Figura 2.1: Overlay network
2. Performance/Reattivit`a: Spesso le applicazioni DVE richiedono interazioni real time tra i partecipanti, dunque `e importante
tire la tempestivit`a delle loro interazioni. I limiti della percezione umana possono parzialmente nascondere i ritardi dovuti alle comuni-cazioni, mostrando all’utente eventi che soddisfano l’istantaneit`a e la simultaneit`a, entrambe ideali.
3. Sicurezza: Nelle applicazione come i MMOG [1] i partecipanti concor-rono per il raggiungimento di certi obiettivi. Occorre fornire l’autenti-cazione dei partecipanti e la correttezza nello svolgimento della logica dell’applicazione.
4. Scalabilit`a: La scalabilit`a si definisce in base al massimo numero di utenti che il sistema pu`o supportare contemporaneamente. Se il nu-mero di utenti connessi contemporaneamente `e molto elevato il sistema potrebbe fallire.
5. Persistenza: Una caratteristica desiderabile nei DVE `e la persistenza di alcuni di tipi di informazioni come ad esempio oggetti relativi all’ap-plicazione, in modo tale da poter essere recuperati dall’utente anche in sessioni diverse.
6. Affidabilit`a/Tolleranza ai guasti: La partecipazione al sistema di un utente `e compromessa se la sessione si interrompe improvvisamente a causa del fallimento del server. L’affidabilit`a del sistema garantisce una buona qualit`a del servizio fornito.
Gli approcci attuali pi`u diffusi per l’implementazione di DVE ricorrono a soluzioni centralizzate: cluster di server oppure server multipli dove ogni server mantiene una diversa regione del mondo virtuale. I sistemi basati su soluzioni centralizzate presentano problemi sia di progettazione dell’appli-cazione sia di costi elevati in termini di banda lato server e risorse CPU lim-itate. Rispetto all’architettura CS [34] i sistemi P2P offrono diversi vantaggi come:
• accessibilit`a
• tolleranza ai guasti
a discapito della coerenza e sincronizzazione. Il problema di rappresentare un ambiente virtuale distribuito pu`o essere definito nel seguente modo: `e dato un insieme di punti, chiamati nodi; ogni nodo pu`o eseguire spostamenti su un piano in tre dimensioni, ossia il mondo virtuale. In questo contesto gli aspetti chiave sono:
• localit`a
• vincoli temporali
• tolleranza ai guasti
Per quanto riguarda il primo punto definiamo per ogni nodo l’Area of
Inter-est (AOI) [24] cio`e una parte del mondo virtuale rappresentata da un disco di raggio prefissato 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 appli-cazione distribuita. Nel contesto delle reti P2P il concetto di consistenza si riferisce alla consistenza topologica al fine di fornire a ogni partecipante una rappresentazione corretta dell’ambiente che lo circonda. Dunque la consis-tenza `e 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 cor-rettamente la logica dell’applicazione occorre rispettare dei vincoli temporali: il peer deve eseguire certe azioni in un preciso istante affinch´e si producano risultati corretti, 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.
2.2
SOLIPSIS
SOLIPSIS [3], [4] `e un sistema basato sulla creazione di una rete di peer. Una organizzazione di questo tipo gode del vantaggio di poter evitare controlli centralizzati in quanto il sistema non utilizza server centralizzati oppure IP multicast. Ogni peer `e un’entit`a del mondo virtuale che si coordina assieme l’azione di tutti gli altri peer del sistema che ne fanno parte. Il sistema `e stato disegnato e costruito per scalare un numero illimitato di utenti ed essere accessibile da qualsiasi computer collegato in Internet. Esso non fa uso di qualsiasi server ed `e unicamente basato su una rete di peer. Nel sistema, ogni partecipante tramite un specifico software gestisce e controlla uno o pi`u peer. Questi peer implementano l’entit`a del mondo virtuale e percepiscono i loro dintorni. I peer collegati possono scambiare dati come video, audio, movimenti degli avatars o qualsiasi tipo di eventi che interessano la rappresentazione del mondo virtuale.
Ogni entit`a del mondo virtuale SOLIPSIS `e implementata da un nodo o peer della rete di SOLIPSIS. Gli unici elementi di SOLIPSIS sono l’entit`a. La differenza tra gli oggetti virtuali e un avatar `e che un avatar `e associato ad un utente. Ogni entit`a `e identificato da un id univoco e dall’insieme di entit`a che denotiamo con E.
Il mondo virtuale di SOLIPSIS `e rappresentato dalla superficie di un toro a due dimensioni T = {(x, y) ∈ Nsizex × Nsizey}. dove sizex e sizey
rappre-sentano la dimensione del mondo di SOLIPSIS e Nk denota l’insieme degli
interi positivi modulo K. La figura 2.3 mostra la segmentazione definita dalla translazione orizzontale e verticale del segmento.
Ogni entit`a e `e rappresentata da un posizione (xe, ye ∈ T ). Le infinite
posizione nel toro sono {xe+ (m ∗ sizex), ye+ (n ∗ sizey); m, n ∈ Z}.
Propriet`a
SOLIPSIS deve fornire la conistenza e la capacit`a di spostarsi in tutto il mondo virtuale. Queste sfide globali richiedono che ogni entit`a rispetta due propriet`a locali.
Figura 2.3: Segmentazione definita dalla translazione orizzontale e verticale del segmento.
A. Conoscenza locale
Ogni entit`a percepisce solo una parte del mondo virtuale dove giaciono solo alcune entit`a. Essa deve essere a conoscenza di tutte le modifiche apportate dalle entita che giaciono in quell’area. Quando un’entit`a modifica la sua rappresentazione virtuale informa solo i vicini adiacenti dell’evento. Quindi, ogni entit`a dovrebbe essere adiacente a tutti i soggetti appartenenti nella sua percezione dello spazio. Chiamiamo area virtuale locale di un’entit`a e lo spazio virtuale di e e conoscenza locale la prorpiet`a che garantisce che e conosce tutte le entit`a della sua area virtuale. In realt`a la sua area virtuale locale anche chiamata Area of Interest (AOI): questa area `e caratterizzata da un disco A(e) di raggio r(e) e centro (xe, ye) e definiamo A(e) = {(x, y) :
d(e, (x, y)) 6 r(e)}. Il raggio r(e) `e variabile e dipende dalla densit`a di entit`a
nell’area e dalla capacit`a fisica di e. Definiamo a(e0) l’insieme dell’entit`a che
giaciono in A(e0): a(e0) = {e ∈ E : pos
e∈ A(e0)}
Propriet`a 1. Un’entit`a e verifica la propriet`a di conoscenza
locale quando:
B. Connessione globale
Sia G = (V, E) un grafo connesso, per ogni coppia di entit`a e, e0 ∈ V esiste
un insieme di archi appartenenti a E che costituiscono un cammino tra le due entit`a. Introduciamo la notazione ∠(e0, e, e00) per indicare l’angolo in
e tra [e, e0] e [e, e00]. Un entit`a e
i appartiene al settore ∇(e0 e e00) quando
∠(e0 e e00) = ∠(e0 e e
i) + ∠(ei e e00). Il successore di un’entit`a e0 rispetto
all’entit`a e0 `e definita come :
se0e0 = e00 ⇔ ∀e /∈ k(e0) : e ∈ ∇(e0 e0 e00)
Il pesimosuccessore di e0rispetto ad e viene indicato sp
ee0mentre il predecessore
di e0 `e s−1 e e0
A causa della dinamicit`a del sistema, nell’istante t le propriet`a sono rispettate mentre nell’istante t+4t ci`o potrebbe non essere pi`u valido. Questo si verifica ad esempio quando uno dei vicini di una certa entit`a si allontana.
Figura 2.4: Involucro convesso formato dai nodi adiacenti in nodo e: la situazione a sinistra rispetta la Propriet`a di Connessione Globale mentre b no.
L’involucro convesso di un insieme di punti (fig. 2.4) `e noto come il pi`u piccolo poligono convesso contenente questo insieme di punti. Definiamo CH(E0)
l’insieme dei punti che si trovano nell’involucro convesso del sottoinsieme
E0 ⊆ E.
Propriet`a 2. La propriet`a di connessione globale di un’entit`a e
`e garantita quando:
C. Collaborazioni spontanee tra le entit`a
Al fine di rispettare le propriet`a locali, un’entit`a deve conoscere tutte le en-tit`a che sono nel suo ambiente. A causa della mobilit`a, in qualsiasi momen-to, alcune entit`a possono entrare nell’AOI. Un meccanismo richiesta/risposta dovrebbe richiedere che ciascuna entit`a chieda in base ad una regola ai suoi adiacenti se hanno rilevato nuove entit`a nell’AOI rispetto all’ultima richies-ta. SOLIPSIS propone uno schema di collaborazione spontanea in cui cias-cuna entit`a invia un messaggio quando rileva che un’entit`a entra nell’AOI di un’altro. Si potrebbero generare alcuni messaggi ridondanti, ma che riduce il disturbo maligno di qualche entit`a.
Regola 1: ∀e0, e00 ∈ k(e), se e0 entra in A(e00), e deve inviare a
e00 un messaggio specifico contenente l’id
e0 e pose0. Cinque eventi
obbligano e di inviare un messaggio a e00:
• e0 si sposta il vicino da e00
• e00 si sposta il vicino da e0
• e va via da e00
• A(e00) aumenta
• e0 non era in k(e) al tempo t
Il rispetto di questa regola garantisce che e00 sar`a informato dell’arrivo di e0
e e00 ricever`a informazioni relative al nuovo ambiente.
D. Query-Response ricorsive per la connessione gloabale Un’entit`a e `e capace di determinare se rispetta la propriet`a 2 verificando:
∀e0 ∈ k(e) : s
ee0 = e00 ⇒ ∠(e0ee00) < π
Quando un’entit`a rileva due entit`a consecutive adiacenti e1e ef con ∠(e1e ef) ≥
π, allora inizia la ricerca di una o pi`u entit`a nel settore ∇(e1 e ef)(vedi fig.
Figura 2.5: L’entit`a e ripristina la propriet`a di Connessione Globale connessa con un’entit`a e2 che si trova nel semipiano delimitato dalla retta
∆1. L’entit`a e2 verifica ∠(e2 ef) < ∠(e1 ef).
Ora di possono verificare de casi:
• Se l’angolo ∠(e2 ef) < π l’entit`a e rispetta la propriet`a 2.
• Altrimenti l’entit`a e deve ripetere lo stesso procedimento per il settore
∇(e1 e ef). Allo stesso modo, se e2 rispetta la propriet`a 2 conosce
l’entita e3 nel semipiano delimitato dalla retta ∆2. il procedimento
procede ricorsivamente permettendo a e di scoprire l’entit`a ei tali che
∠(e1e ef) < ∠(ei−1e ef). La ricerca termina quando e scopre un’entit`a
ei tale che ∠(ei e ef) < π.
Denotiamo C(e0, e) il disco di raggio d(e0, e) centrato su e0 cos`ı: C(e0, e) =
{(x, y) : d(e0, (x, y)) ≤ d(e0, e)}.
Regola 2: ∀e0, e00∈ k(e), if e00 entra in C(e, e0), deve inviare a e0
un messaggio specifico contenente ide00 e pose00.
E. Connessione al mondo virtuale
SOLIPSIS prevede delle procedure che consentono ad un’entit`a che vuole entrare a far parte del sistema di acquisire la conoscenza dell’ambiente cir-costante e quindi rispettare le regole. Sia e la nuova entit`a, caratterizzata da una posizione target (xe, ye) e supponiamo che sia a conoscenza di un’entit`a
e0 gi`a connessa al sistema. SOLIPSIS propone un algoritmo che prende come
parametro la posizione target e restituisce le entit`a vicine a questa posizione. Il primo passo dell’algoritmo consiste nell’invio da parte di e a e0 di un
mes-saggio contenete il suo identificativo e la posizione target. Alla ricezione di questo messaggio e0 individua un’entit`a e1 ∈ {k(e0) ∪ {e0}} la cui posizione
sia la pi`u vicina alla posizione target di e. L’entit`a e0 inoltra il messaggio a e1
la quale ripeter`a lo stesso procedimento. Alla fine si arriver`a ad un’entit`a en
che non conosce altre entit`a pi`u vicine alla posizione target che essa stessa. Notiamo per`o che en non `e necessariamente l’entit`a pi`u vicina in assoluto a
(xe, ye) e la seconda parte dell’algoritmo esegue questa verifica. L’entit`a en
individua un’entit`a em ∈ {k(en)/{en}} la cui posizione sia la pi`u vicina alla
posizione target di e; a questo punto em apre una connessione con e. em
ripete lo stesso procedimento individuando l’entit`a em+1 ∈ {k(em)/{en}} pi`u
vicina ad e. Dopo di che em confronta le due distanze d(e, em+1) e d(e, en):
• Se em+1 `e pi`u vicina ad e rispetto a en; `e certo che en non pu`o
es-sere l’entit`a pi`u vicina ad e. L’algoritmo riprende dalla prima fase rimpiazzando l’entit`a e0 con l’entit`a em+1.
• Se invece che en`e la pi`u vicina ad e, em invia il messaggio all’entit`a pi`u
vicina ad e appartenente al semipiano delimitato dal segmento (e, em).
Questa operazione si ripete ricorsivamente finch´e il messaggio non at-traversa di nuovo il segmento (e, en). Tutte le entit`a 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`a 2.
2.3
VON: Voronoi-based Overlay Network
2.3.1
Diagrammi di Voronoi
In matematica i diagramma di Voronoi traggono il loro nome dal matematico russo Georgy Fedoseevich Voronoi (o Voronoy) che defin`ı e studi`o il caso generale n-dimensionale nel 1908. Nel corso degli questi diagrammi hanno trovato una larga applicazione in tanti campi come ad esempio la geofisica e la metereologia per analizzare dati distribuiti spazialmente. Un diagramma di Voronoi `e un tipo di decomposizione di uno spazio metrico, determinata dalle distanze rispetto a un determinato insieme discreto di elementi dello spazio (ad esempio, un insieme finito di punti). Un semplice caso d’uso `e quello del piano, dove dato un insieme finito di punti S, il diagramma di Voronoi per S `e la partizione del piano che associa una regione V(p) ad ogni punto p ∈ S in modo tale che tutti i punti di V(p) siano pi`u vicini a
p che ad ogni altro punto in S. Ne deriva che in un piano dati due insiemi X,Y discreti di numeri reali, il diagramma di Voronoi relativo all’insieme {(x, y)|x ∈ X, y ∈ Y } produce una tassellatura composta da rettangoli (i cui
punti non sono necessariamente i centri).
Figura 2.6: Il diagramma di Voronoi di un insieme casuale di punti nel piano (tutti i punti sono compresi nell’immagine).
(topologica-mente) discreto S di punti di uno spazio euclideo e per quasi1 ogni punto x,
c’`e un punto in S che `e il pi`u vicino a x. Se S contiene solo due punti, a e
b, allora il luogo geometrico dei punti equidistanti da a e b `e un iperpiano,
ovvero un sottospazio affine di codimensione 1. Tale iperpiano sar`a il confine tra l’insieme di tutti punti pi`u vicini ad a che a b e l’insieme di tutti i punti pi`u vicini a b che ad a. `E l’asse del segmento ab. In generale, l’insieme dei punti pi`u vicini ad un punto che ad ogni altro punto di S `e la parte interna di un politopo (eventualmente privo di bordi) detto dominio di Dirichlet o cella di Voronoi di c. L’insieme di tali politopi `e una tassellatura dell’intero spazio e viene detta tassellatura di Voronoi corrispondente all’insieme S. Se la dimensione dello spazio `e solo 2, `e facile rappresentare graficamente le tas-sellazioni di Voronoi; `e a questo caso che si riferisce solitamente l’accezione Voronoi diagrams (fig. 2.6).
L’utilizzo informale dei diagrammi di Voronoi pu`o essere fatto risalire a Cartesio gi`a nel 1644. Oppure a Dirichlet che utilizz`o diagrammi di Voronoi bidimensionali e tridimensionali nei suoi studi delle forme quadratiche, nel 1850, o come non citare il medico britannico John Snow che utilizz`o un dia-gramma di Voronoi nel 1854 per illustrare come la maggioranza delle persone morte nell’epidemia di colera a Soho viveva pi`u vicino ad una delle pompe infette di Broad Street che ad ogni altra pompa d’acqua.
Molte tassellazioni di Voronoi di griglie regolari di punti in due o tre dimen-sioni risultano essere tassellazioni familiari:
• una griglia bidimensionale triangolare produce una tassellazione di esag-oni, che saranno regolari se i punti della griglia sono vertici di trian-goli equilateri; una griglia rettangolare avr`a a sua volta un diagramma di Voronoi composto da rettangoli, che saranno inoltre quadrati se la griglia era quadrata
• Due griglie bidimensionali triangolari regolari opportunamente allineate
1Il quasi `e una precisazione necessaria dato che alcuni punti x possono essere
su due piani paralleli producono la configurazione di prismi esagonali con rombi alle estremit`a che si pu`o osservare negli alveari. Supponendo di tassellare lo spazio con dei cubi, la griglia ottenuta ponendo un punto al centro di ogni faccia di un cubo produce come diagramma di Voronoi una Una sezione di un diagramma di Voronoi per un insieme casuale di punti in un cubo. Si noti che in generale con questo procedimento non si ottiene un diagramma di Voronoi bidimensionale, nonostante le celle, che sono poliedri convessi, abbiano sezioni a loro volta convesse.
• Se invece i punti vengono messi al centro di ogni cubo, si ottiene una tassellazione composta di ottaedri tronchi.
Indichiamo con dist(p,q) la distanza Euclidea tra i punti p e q. Nel piano abbiamo che
dist(p, q) =p(px− qx)2+ (py − qy)2
Sia P = {p1, p2..., pn} un insieme di n punti distinti nel piano detti siti.
Definiamo il diagramma di Voronoi di P come la suddivisione del piano in
n celle, una per ogni sito in P, con la propriet`a che un punto q giace nella
cella corrispondente ad un sito pi se e solo se dist(q, pi) ≤ dist(q, pj) per ogni
pj ∈ P con j 6= i. Definiamo con Vor(P) come il diagramma di Voronoi di
P, e con V (pi) la cella corrispondente al sito pi, detta anche cella di pi. Si
noti che abbiamo definito le celle come insiemi chiusi. Alcuni punti possono quindi essere contenuti in due celle distinte, in quanto equamente distanti dai rispettivi siti. L’insieme di tali punti `e chiamato frontiera tra le due celle come mostrato in figura 2.7.
Figura 2.7: (a) I punti indicano i siti, le linee delimitano i confini delle regioni. (b) I quadrati rappresentano i vicini inclusi; i triangoli rappresentano i vicini di confine; le stelle sono sia vicini inclusi che di confine; i cerchi rappresentano i vicini AOI normali.
2.3.2
Triangolazione di Delaunay
La triangolazione di Delaunay [40] si basa sui diagrammi di Voronoi attraverso il principio della dualit`a. Due punti pi e pj si dicono contigui se
le due regioni V (pi) e V (pj) hanno un lato in comune e la triangolazione di
Delaunay si ottiene connettendo tali punti contigui (figura 2.8).
Propriet`a.
Il cerchio circoscritto ad un generico triangolo di Delaunay avente come verti-ci pi, pj e pknon contiene nessun altro punto appartenente alla triangolazione
(figura 2.9)
Figura 2.9: Propriet`a della triangolazione di Delaunay.
Si pu`o per`o verificare un caso degenere, ovvero, possono esistere quattro o pi`u punti concentrici; in tal caso vi sono due o pi`u vertici di Voronoi coincidenti e la triangolazione di Delaunay non `e univocamente determinata.
2.3.3
VON - Struttura di una Voronoi Overlay
Net-work
VON (Voronoi-based Overlay Network) [7], [6], [8], `e un sistema che nasce con l’obiettivo di fornire maggiore scalabilit`a agli DVE, dove per scalabilit`a, si intende la capacit`a da parte di una DVE di gestire una grande quantit`a di utenti senza compromettere la qualit`a del servizio. In un generico DVE, i partecipanti vengono rappresentati come punti in uno spazio 2D, ed og-nuno di essi `e caratterizzato da un’area di interesse (AOI - Area Of Interest). L’AOI `e fondamentale, in quanto ogni utente viene influenzato soltanto da nodi od eventi che sono all’interno dell’AOI. Supponiamo che l’area di inter-esse sia una circonferenza con centro le coordinate dell’utente, e che un nodo si muova con passi discreti. Nasce il seguente problema: come avviene la scoperta dei nodi rilevanti, se il nodo `e periodicamente in movimento? Ogni nodo crea e gestisce un proprio diagramma di Voronoi in modo da tenere traccia dei vicini all’interno della propria AOI; inoltre il nodo mantiene con-nessioni 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 confine giocano un ruo-lo importante nella fase di scoperta di nuovo vicini. Dato un nodo, definiamo:
Definizione: dati due nodi, ni e nj, ed un diagramma di Voronoi V di
dimensioni limitate, possiamo dire che ni e nj sono enclosing neighbors
(vicini di cella) se solo se le rispettive celle nel diagramma sono confinanti,
ovvero se V (ni) ∩ V (nj) 6= ∅.
Definizione: dati due nodi, ni e nj, possiamo dire che nj `e un
AOI-neighbor (vicino di Aoi) di ni se solo se nj risiede all’interno dell’area di
interesse di ni.
ni se solo se nj `e enclosing neighbor oppure AOI-neighbor di ni.
I vicini sopra elencati sono visibili in figura 2.10.
Figura 2.10: La circonferenza in rosso rappresenta l’area di interesse del nodo A. I quadrati sono gli Enclosing Neighbors; i triangoli sono i Boundary Neighbors; le stelle sono sia Enclosing che Boundary Neighbors; le croci rappresentano ii vicini irrilevanti per il nodo A. Tutti gli altri si definiscono AOI-Neighbors (pallino rosso).
X-Nomade
Nell’introduzione e nel capitolo 2 sono stati illustrati alcuni supporti per ambienti virtuali distribuiti esistenti. La maggior parte dei supporti `e sta-to sviluppasta-to per architetture centralizzate progettate secondo il modello Client/Server. X-Nomade `e un sistema P2P che gestisce una overlay net-work definita a partire da un diagramma di Voronoi che nascono in ambienti virtuale distribuito in uno spazio 2D. Questo sistema si ispira alle ricerche che hanno portato alla definizione di VON (Voronoi based Overlay Network) e condivide con quest’ultimo gran parte dei concetti, anche se il protocollo di comunicazione `e stato sostanzialmente riprogettato. La scelta di un’architet-tura completamente distribuita P2P impone una serie di problematiche. In questo capitolo vengono descritte le scelte di progetto e architetturali. In-oltre verranno presentate due versioni di X-Nomade che si differenziano nel modo con cui viene effettuato il routing degli heartbeats e per il numero di vicini con cui viene stabilita una connessione.
3.1
Architettura del sistema
3.1.1
Struttura generale e definizioni
In questa sezione verranno presentati i principali aspetti che caratterizzano il supporto Nomade [13]. Si considerano solo mondi virtuali di dimensioni
limitate.
Gli elementi principali di Nomade sono:
• Peer (nodo)
• Avatar
• Area di interesse del nodo (AOI)
Peer In Nomade un peer (o nodo) `e una istanza di un programma in ese-cuzione su una macchina che dispone di un connessione ad una rete, sia essa una LAN oppure Internet.
Avatar L’avatar controllato dal nodo rappresenta l’entit`a che ha la capacit`a di muoversi all’interno del mondo virtuale. Notiamo che in generale un nodo potrebbe controllare pi`u avatar. In Nomade ogni peer controlla un solo avatar. Nel corso della trattazione si utilizza spesso il termine nodo (o peer) per riferire l’avatar controllato da questo. Osserviamo che la generalizzazione al caso di pi`u avatar controllati dallo stesso host non comporta modifiche sostanziali alle soluzioni scelte per la proget-tazione del supporto: gli stessi meccanismi proposti potrebbero essere utilizzati per la gestione dell’insieme di avatar controllati da un peer. Per semplicit`a dunque consideriamo un solo avatar per ogni host. Ad ogni avatar viene associato:
• Posizione che occupa nel mondo virtuale, espressa dalle coordinate (x, y) del piano.
• Un identificatore unico (id).
• Un indirizzo IP ed un numero di porta.
• Un’area di interesse.
Area di interesse del nodo L’area di interesse di un peer (Area Of Inter-est AOI) `e la zona del mondo virtuale che si trova in prossimit`a del peer. Questa definizione `e molto generale, infatti il concetto di area
di interesse dipende dal tipo di applicazione e alle finalit`a che questa si propone di ottenere. Tutti i peer che si trovano all’interno dell’AOI di un certo nodo sono chiamati vicini. Ogni nodo mantiene solo la conoscenza dei nodi vicini e degli oggetti passivi che si trovano all’in-terno della propria area di interesse, dunque ogni peer ha una visione locale dell’intero mondo virtuale. Gli eventi che avvengono nel mondo virtuale possono essere classificati come transitori o permanenti. Ri-entrano nel primo tipo, ad esempio, il movimento di un giocatore, il lancio di un proiettile, etc. Nel secondo tipo rientrano tutti gli eventi che riguardano la modifica degli oggetti passivi del mondo, ad esempio, la modifica del livello di una pozione magica, lo spostamento di un’ar-ma, etc. Pur mantenendo una visione locale del mondo, ogni peer deve acquisire conoscenza degli eventi permanenti accaduti in altre regioni del mondo quando accade a tali regioni. Nel corso del presente capitolo si far`a riferimento all’area di interesse dinamica del peer come la zona del mondo virtuale rappresenta da un’area circolare centrata sulla po-sizione del nodo stesso. Dunque in questo caso l’AOI del peer cambia ad ogni suo spostamento. Il raggio dell’area di interesse deve essere lo stesso per tutti i nodi della stessa overlay network e deve rimanere costante nel tempo (AOI statiche).
Nel contesto degli ambienti virtuali distribuiti, un importante concetto riguar-da la consistenza topologica che consente di fornire ad ogni partecipante una rappresentazione corretta dell’ambiente che lo circonda. Dunque la consisten-za `e rispettata se ogni nodo del sistema mantiene la conoscenconsisten-za della propria AOI e quindi dei vicini e degli oggetti passivi che si trovano al suo interno. Nella tesi verranno presentati due diverse implementazione del routing dei messaggi heartbeats. Le due implementazioni sono stati valutati effettuando dei test sull’ambiente di simulazione Grid’5000 (vedi Capitolo 5).
3.2
Costruzione di una overlay network
Nella versione originale di Nomade ogni nodo dovrebbe interagire esclusiva-mente con i nodi le cui coordinate giacciono all’interno della propria area di interesse, attraverso un insieme di connessioni dirette con essi. Cos`ı facendo si limita il numero di messaggi scambiati da ogni nodo ed il numero di connes-sioni che questo deve gestire, garantendo perci`o una considerevole scalabilit`a. In questa tesi saranno presentati tre diversi modi di interagire con i nodi che giacciono all’interno dell’AOI.
Figura 3.1: AOI - NomadeV0: connessioni dirette.
Come si pu`o notare in figura 3.1 il nodo blu mantiene un collegamento soltan-to con i nodi che giacciono all’interno della sua area di interesse, ovvero quelli che controllano gli avatar presenti nelle immediate vicinanze dell’avatar del nodo blu.
3.2.1
Connettivit`
a e scoperta dei vicini
Ogni volta che un avatar si sposta l’overlay network cambia. Questo pu`o provocare l’ingresso di nuovi nodi e/o l’uscita di altri dall’area di interesse, e di conseguenza una variazione dell’insieme delle connessioni attive.
Figura 3.2: Scoperta di nuovi vicini in seguito ad uno spostamento. Poich´e il sistema `e completamente distribuito, e quindi ogni nodo ha soltanto conoscenze locali, nasce il problema di come scoprire i nuovi vicini1 in seguito
ad uno spostamento.
Un altro problema importante `e quello della connettivit`a. Prendiamo ad esempio in considerazione la situazione in figura 3.3.
Figura 3.3: Caso in cui non esiste alcun nodo all’interno dell’area di interesse.
In questo caso non c’`e nessun peer all’interno dell’area di interesse del nodo
blu. Di conseguenza quest’ultimo non ha nessuna connessione con il resto del sistema, rimanendo cos`ı isolato e non avendo alcuna possibilit`a di individuare nuovi vicini nei successivi spostamenti. `E quindi indispensabile che, anche in assenza di avatar all’interno dell’area di interesse, vengano mantenute delle connessioni con i nodi che si trovano nelle immediate vicinanze, in modo che questi possano contribuire al processo di discovery. Nomade risolve questi problemi utilizzando i digrammi di Voronoi (vedi Capitolo 2, paragrafo 2.3.1). Ogni nodo gestisce un proprio diagramma di Voronoi in cui `e presente un sito per il nodo stesso ed un sito per ogni suo vicino sull’overlay network. Tale diagramma consente di classificare i vicini come boundary neighbours e/o enclosing neighbours. I primi agiscono come delle vedette, consentendo la scoperta di nuovi vicini in seguito ad uno spostamento, mentre i secondi permettono di mantenere connessa l’overlay network e possono trovarsi anche al fuori dell’area di interesse.
Figura 3.4: Diagramma di Voronoi.
`
E importante precisare che non `e necessario costruire un unico diagramma di Voronoi in maniera distribuita. Invece ogni nodo costruisce un proprio di-agramma di Voronoi utilizzando esclusivamente la propria posizione e quella
dei vicini di cui `e a conoscenza. In figura 3.5 viene mostrato il diagramma di
Figura 3.5: Diagramma di Voronoi costruito tenendo conto di tutti i nodi presenti nel sistema.
Figura 3.6: a) Diagramma di Voronoi costruito dal nodo rosso. b) Diagramma di Voronoi costruito dal nodo blu.
Voronoi costruito tenendo conto di tutti i nodi presenti nel mondo virtuale. Invece in a viene mostrato il diagramma di Voronoi costruito dal nodo rosso e in b quello costruito dal nodo blu.
In figura 3.7 viene mostrato un diagramma di Voronoi di un nodo. Inoltre vengono evidenziati tutti i tipi i vari tipi di relazione di vicinanza.
Figura 3.7: Diversi tipi di relazione di vicinanza.
Come si pu`o notare dalla figura i nodi b e c sono enclosing neighbor di
a, perch´e le rispettive celle condividono un lato. Inoltre b e c sono
AOI-neighbor perch´e appartengono all’area di interesse di a. Infine risultano anche boundary neighbor perch´e le loro celle di Voronoi si estendono sino ai confini del diagramma. Il nodo d `e contemporaneamente boundary ed enclosing neighbor di a, ma non appartenendo all’area di interesse di a e quindi non `e un suo AOI-neighbor. Il nodo e `e sia AOI-neighbor che enclosing neighbor del nodo a, ma non `e boundary perch´e la relativa cella non interseca i bordi del diagramma. Per le stesse ragioni possiamo affermare che il nodo f `e solamente un AOI-neighbor di a, mentre g `e un AOI-neighbor ed un boundary neighbor del nodo a ma non `e enclosing (Si rimanda alla sezione 2.3.3 per le definizioni dei vicini elencati sopra). Prima di passare all’associazione di un nodo all’overlay esaminiamo come
ogni istanza di X-Nomade comunica con i componenti applicativi e con i nodi vicini.
Figura 3.8: Interazione tra X-Nomade e i componenti applicativi. L’interazione tra X-Nomade e le componenti applicative avviene inserendo e prelevando oggetti, che chiameremo messaggi, da due code sincronizzate (ve-di fig. 3.8). X-Nomade utilizza inoltre un socket UDP per inviare (ricevere) messaggi a (da) nodi remoti. In questo caso i messaggi vengono codificati come una sequenza di byte ed inseriti all’interno di un pacchetto UDP. `E stato preferito UDP a TCP perch´e, vista l’elevata dinamicit`a dell’overlay network, aprire e chiudere continuamente connessioni TCP avrebbe potu-to impattare in maniera considerevole sulle prestazioni. Poich´e UDP non fornisce un servizio di trasporto affidabile dei pacchetti, nella stesura del protocollo `e stata presa in considerazione la possibile perdita di pacchetti o il loro arrivo fuori ordine.
3.2.2
Associazione di un nodo ad una overlay network
Per associare un nodo ad una overlay network esistente viene eseguita la procedura di join. Prendiamo in considerazione una overlay network e un nodo n che vuole associarsi nella rete nella posizione occupata. In figura 3.9 viene mostrata la situazione descritta.Descrizione procedura join.
La procedura inizia con l’invio da parte dell’applicazione di una richiesta di Join, per mezzo di un messaggio di JoinRequest contenente la posizione
Figura 3.9: Una overlay network esistente ed un nodo n che intende associarsi.
iniziale dell’avatar all’interno del mondo virtuale, l’indirizzo IP ed il numero di porta del nodo di bootstrap. Il nodo di bootstrap `e un qualsiasi nodo gi`a attivo, e serve come punto di ingresso nell’overlay network. Si suppone che ogni nodo che intende unirsi ad una rete preesistente possa reperire l’indirizzo di alcuni nodi di bootstrap mediante web server noti o meccanismi di caching, simili a quelli del protocollo Gnutella.
Un messaggio di join contiene il suo identificatore, la sua posizione, l’indirizzo IP e il numero di porta di n. In figura vengono mostrati i campi del messaggio Join (fig. 3.10.
Figura 3.10: Formato messaggio Join.
Message Id denota il tipo di messaggio (Join) e la versione del protocollo
(nel capitolo 5 verr`a mostrata l’implementazione dei messaggi).
Il nodo n invia il messaggio di Join al nodo di bootstrap a come mostrato in figura 3.11.
Il messaggio verr`a poi propagato verso il nodo associato alla cella di Voronoi contenente la posizione iniziale di n (detto acceptor node), attraverso un
Figura 3.11: Il nodo n invia il messaggio.
routing di tipo greedy. In pratica ogni nodo individua, nell’insieme costi-tuito da lui stesso e dai suoi vicini, il nodo meno distante da n. Se il nodo individuato `e un vicino, allora propagher`a verso questo il messaggio, altri-menti la Join ha raggiunto l’acceptor node (in questo caso c, fig. 3.12) e la propagazione termina.
Figura 3.12: Il nodo n raggiunge l’accepter node, in questo caso c. Quando il messaggio arriva a c, inserisce n nella propria lista dei vicini, ed il sito relativo a n nel proprio diagramma di Voronoi. Inoltre utilizza il di-agramma cos`ı modificato per individuare i vicini di n di cui `e a conoscenza (in questo caso b e d) ed invia un messaggio di DiscoveryResponse ad n , contenente alcune informazioni (identificatore, posizione, indirizzo IP e
nu-mero di porta) su questi ultimi e su se stesso. In figura 3.13 viene illustrato il diagramma di Voronoi del nodo c dopo l’inserimento del sito relativo a n (la circonferenza in rosso indica l’area di interesse di n).
Figura 3.13: Diagramma di Voronoi del nodo n dopo la ricezione del
DiscoveryResponse.
In figura 3.14 vengono mostrati i campi del messaggio DiscoveryResponse.
Figura 3.14: Formato messaggio DiscoveryResponse.
Message Id denota il tipo di messaggio (DiscoveryResponse) e la versione del protocollo.
Node Id contiene l’identificatore del mittente.
Integer max value `e stato inserito per mantenere la compatibilit`a con il formato delle DiscoveryResponse usate per la scoperta di vicini.
Segue una lista di record dove vengono inseriti i dati relativi ai nodi scoperti. Per ognuno di essi viene riportato l’identificatore, la posizione, il numero di porta e l’indirizzo IP.
Per ogni record contenuto nel DiscoveryResponse, n (fig. 3.13) inserisce un elemento nella lista dei vicini ed un sito nel diagramma di Voronoi.
Per ogni vicino cos`ı scoperto, la componente X-Nomade del nodo n invia alla corrispondente componente applicativa un messaggio di tipo NewAvatar. In figura 3.15 viene mostrato il formato del messaggio NewAvatar.
Figura 3.15: Formato messaggio NewAvatar.
Message Id denota il tipo di messaggio (NewAvatar) e la versione del pro-tocollo.
Node Id contiene l’identificatore del nodo scoperto.
Position contiene la posizione del nodo scoperto.
Payload contiene un eventuale payload applicativo (non presente in questa fase).
Se prendiamo in considerazione la figura 3.16 si nota che il nodo n non `e a conoscenza del fatto che a `e un suo enclosing neighbor.
Il vicino a non `e stato scoperto durante la fase di Join, ma verr`a scoper-to in seguiscoper-to in base dei meccanismi. Per incrementare il numero di vicini scoperti durante la fase di Join viene apportata un’ottimizzazione. Quando un nodo deve rilanciare un messaggio di Join, verifica se il nodo entrante giace all’interno della sua area di interesse. In caso affermativo il nodo
en-Figura 3.16: La figura a sinistra mostra il diagramma di Voronoi del nodo
n dopo la ricezione del DiscoveryResponse, mentre quella a destra mostra il
diagramma di Voronoi contenente tutti i nodi dell’overlay network.
trante sar`a sicuramente suo vicino, per cui pu`o inserire immediatamente un elemento corrispondente nella lista dei vicini e nel diagramma. Inoltre indi-vidua i vicini del nuovo arrivato e glieli notifica con una DiscoveryResponse. Nell’esempio affrontato b si accorge che n giace all’interno della propria area di interesse, quindi risponder`a con una DiscoveryResponse contenente le in-formazioni riguardanti se stesso (b), a e c. In figura 3.17 viene mostrato il diagramma di Voronoi in seguito alle DiscoveryResponse. Si nota che
sta-Figura 3.17: n aggiorna il proprio diagramma in seguito alla ricezione dei due DiscoveryResponse.
sezione verr`a descritto come avviene lo spostamento di un nodo e le tre di-verse implementazione di come inviare la notifica di spostamento a tutti i suoi vicini.
3.3
X-Nomade: versione routing con tutti i
vicini
3.3.1
Valutazione dei links con soli vicini di Voronoi
In questa sezione viene descritta la versione di X-Nomade in cui vengono mantenuto connessioni dirette con solo i vicini di Voronoi. L’idea iniziale che sta alla base di Nomade `e quella di associare ad ogni nodo una cop-pia di coordinate appartenenti ad un cop-piano. Tali coordinate corrispondono alla posizione del relativo avatar all’interno del mondo virtuale e cambiano in funzione degli spostamenti di quest’ultimo. Ad ogni nodo viene inoltre associata un’area di interesse (AOI) che rappresenta il raggio visivo/raggio d’azione dell’avatar nel mondo virtuale. Il punto chiave di Nomade `e che ogni nodo dovrebbe interagire esclusivamente con i peer le cui coordinate giacciono all’interno della propria area di interesse attraverso delle connes-sioni dirette con essi. Cos`ı facendo si limita il numero di messaggi scambiati da ogni nodo ed il numero di connessioni che questo deve gestire, garanten-do perci`o una considerevole scalabilit`a. La modifica consistente apportata a X-Nomade nella prima versione `e stata quella di non avere pi`u connessioni dirette con tutti i peer, ma avere una connessione diretta con tutti i vicini di Voronoi (vicini enclosing) e ogni vicino reinoltra l’heartbeat a tutti i vicini che appartengono all’AOI(P), utilizzando un routing basato sul flooding.3.3.2
Spostamento di un nodo
In questo paragrafo viene esaminata la procedura eseguita in seguito ad allo spostamento di un nodo. Quando un avatar si muove all’interno del mondo
virtuale, l’applicazione che ne detiene il controllo invia un messaggio di Po-sitionUpdateV1 a X-Nomade, contenente la nuova posizione da associare al nodo. In figura 3.18 viene mostrato il formato del messaggio PositionUp-dateV1.
Figura 3.18: Formato messaggio PositionUpdateV1.
Message Id denota il tipo di messaggio (PositionUpdateV1) e la versione del protocollo.
Node Id contiene l’identificatore del nodo che si `e spostato.
Position contiene la nuova posizione.
Payload contiene un eventuale payload applicativo.
Da notare che i messaggi di tipo PositionUpdateV1 vengono utilizzati per due scopi.
1. Se creati dall’applicazione ed inviati a X-Nomade, vengono utilizzati per richiedere lo spostamento del nodo.
2. Se creati da X-Nomade ed inviati all’applicazione servono per informare quest’ultima dello spostamento di un nodo remoto.
In figura 3.19 vengono mostrati i messaggi scambiati tra due nodi in seguito allo spostamento dell’avatar del Nodo 1.
Alla ricezione viene aggiornato il diagramma di Voronoi del nodo ed incre-mentato il relativo time-step. A tutti i vicini enclosing (vedi figura 3.20) conosciuti viene poi inviato un RemotePositionUpdateV1 contenente le
Figura 3.19: Messaggi scambiati in seguito allo spostamento dell’avatar del Nodo 1.
nuove coordinate ed il time-step corrente. Questa fase `e la prima parte dell’invio di messaggi di heartbeats.
Figura 3.20: Connessioni dirette con i vicini enclosing. In figura 3.21 RemotePositionUpdateV1: formato del messaggio.
Message Id denota il tipo di messaggio (RemotePositionUpdateV1) e la versione del protocollo.
Figura 3.21: Formato messaggio RemotePositionUpdateV1. Node Id contiene l’identificatore del nodo che si `e spostato.
Position contiene la nuova posizione.
Payload contiene un eventuale payload applicativo.
DiscoveryRequest `e un flag booleano che indica al destinatario se deve contribuire alla ricerca di nuovi vicini per il nodo mittente.
Time-step contiene il time-step del mittente al momento dell’invio del mes-saggio e viene utilizzato per garantire la ricezione ordinata dei messaggi da parte del destinatario.
L’avatar alla ricezione del messaggio RemotePositionUpdateV1 aggiorna la posizione del nodo mittente nel diagramma di Voronoi. Inoltre informa l’applicazione dell’avvenuto spostamento, inviandole un messaggio di Po-sitionUpdateV1. L’avatar inoltra il messaggio RemotePositionUpdat-eV1 a tutti i suoi vicini enclosing che sono anche vicini del mittente.
In seguito ad uno spostamento si possono perdere alcuni vicini. Questi vicini vengono rimossi dalla lista dei vicini e dal diagramma di Voronoi. Il mes-saggio di RemotePositionUpdateV1 viene inviato anche a tutti i vicini persi affinch´e si rendano conto della perdita di vicinanza. Viene notificata l’applicazione inviando un messaggio di ExitNotificationV1.
In figura 3.22 viene mostrato il formato del messaggio di tipo ExitNotifica-tionV1.
Figura 3.22: Formato messaggio ExitNotificationV1.
Message Id denota il tipo di messaggio (ExitNotification) e la versione del protocollo.
Node Id contiene l’identificatore del nodo rimosso dalla lista dei vicini.
Leaving `e un flag booleano che indica se il nodo ha lasciato la rete o sem-plicemente non `e pi`u un vicino per il nodo corrente.
3.3.3
Valutazione dei links con area dei links diretti
In questa sezione verr`a descritta l’introduzione dell’AOI dei link diretti, che `e un’area di raggio minore rispetto all’AOI. Attraverso quest’area si fa fronte a problemi di scalabilit`a, in caso di crowding. Ogni peer sul bordo dell’area dei link diretti provvede ad inoltrare l’heartbeat ad eventuali altri peer po-sizionati nella parte periferica dell’AOI. Nella prima parte verranno descritte le problematiche introdotte dall’invio di heartbeats.L’AOI, in applicazioni client-server `e stata introdotta per far fronte a prob-lemi di scalabilit`a. Come dato di fatto, senza AOI per filtrare e ridurre le comunicazioni, se sono connessi N client al server, ogni heartbeat deve essere inviato a N-1 client. In questo modo si ha un grande impatto sulla scalabilit`a, perch´e gli heartbeats sono inviati frequentemente, anche ogni 200 millisecon-di. `E stata introdotta l’AOI per migliorare la scalabilit`a riducendo il numero di heartbeats che deve gestisce il server. Tuttavia, anche utilizzando l’AOI, esistono situazioni in cui si possono avere problemi di scalabilit`a. Queste situazioni si verificano quando un gran numero di avatar `e molto vicino al mondo virtuale modellato dalla DVE: questa situazione viene indicata come
crowding. Avere una grande AOI pu`o scatenare un’esplosione di messaggi.
Anche se viene ridotta al fine si ridurre il numero di messaggi, non si pu`o ridurre troppo il raggio perch´e un cliente deve essere consapevole della eventi che caratterizzano il suo mondo virtuale. Quindi riassumendo l’uso di una sola AOI mostra un problema riguardante la latenza degli heartbeats, spe-cialmente nel caso di crowding.
La seconda versione consiste nel definire connessioni dirette con tutti i peer, viceversa vengono mantenute connessioni dirette solo con tutti i peer che risiedono all’interno dell’AOI interna. Cos`ı facendo si limita il numero di messaggi scambiati da ogni nodo ed il numero di connessioni che questo deve gestire, garantendo perci`o una considerevole scalabilit`a (nel capitolo 5 verranno presentati dei risultati sperimentali che mostrano il numero medio
di connessioni dirette ha un peer in caso di croding).
Figura 3.23: Connessioni dirette con i vicini che stanno all’interno della seconda AOI.
In figura 3.23 viene mostrata l’area d’interesse principale in verde e l’AOI interna in blu. In figura si pu`o notare come il nodo s presenti connessioni dirette con solo i peer che risiedono all’interno dell’AOI interna.
La figura 3.23 mostra la prima fase dell’inoltro di un’heartbeat. In questa fase i peer che ricevono l’heartbeat in modo diretto da chi lo ha generato hanno il compito di inoltrare il messaggio ai propri vicini che risiedono all’interno dell’AOI esterna e che si trovano nell’AOI del mittente.
L’applicazione notifica un spostamento di un peer a X-Nomade inviando un messaggio di tipo PositionUpdateV1. Alla ricezione viene aggiornato il diagramma di Voronoi del nodo ed incrementato il relativo time-step. Tra tutti i vicini dell’avatar che ha generato lo spostamento vengono selezionati tutti gli avatar che la loro posizione risiede all’interno dell’AOI interna. L’avatar invia un messaggio di tipo RemotePositionUpdateV1 a tutti i vicini selezionati prima.
ag-giorna la posizione del nodo mittente nel diagramma di Voronoi. Inoltre informa l’applicazione dell’avvenuto spostamento, inviandole un messaggio di PositionUpdateV1.
L’avatar inoltra il messaggio RemotePositionUpdateV1 a tutti i suoi vici-ni che hanno la propria posizione all’interno dell’AOI interna con centro l’a-vatar che ha ricevuto il messaggio ed inoltre deve essere un vicino dell’al’a-vatar che ha generato lo spostamento.
3.4
Invio heartbeat: uso di compass routing
In questa sezione verr`a descritto l’algoritmo di compass routing e mostrato il protocollo per l’inoltro degli heartbeats.
Il compass routing `e un algoritmo di instradamento che viene applicato sui grafi geometrici. Si basa sulla seguente propriet`a.
Propriet`a: dato un grafo, supponiamo che da un vertice iniziale s si voglia raggiungere il vertice t e che tutte le informazioni disponibili ad ogni passo siano le coordinate di t, la posizione corrente p e la direzione dei lati incidenti sul vertice corrente p. A partire da s, ad ogni passo, possiamo scegliere la di-rezione da percorrere, attraversando il lato incidente sulla posizione corrente
p che forma l’angolo pi`u piccolo con il segmento che connette p con t.
L’obiettivo primario del compass routing non `e quello di trovare il cammi-no pi`u breve per connettere due vertici, ma garantire il raggiungimento della destinazione. Questo non `e sempre vero, osserviamo il grafo in figura 3.25. In questo caso vogliamo identificare un tragitto da u1 a t usando il compass
rout-ing, ma il risultato `e un ciclo infinito sull’insieme di vertici ui, wi : i = 0, ..., 5.
Diremo che un grafo geometrico G supporta il compass routing se per ogni coppia dei suoi vertici s e t, tale algoritmo di instradamento, partendo da s, restituisce sempre un cammino da s a t.
Figura 3.24: Cammino risultante dall’applicazione del compass routing da s a t.
Figura 3.25: Il compass routing non riesce a raggiungere t da ui, i = 0,...,5.
Sia Pn un’insieme di n punti del piano, allora la triangolazione di Delaunay
Dimostrazione. Supponiamo di voler raggiungere il vertice t a partire s.
Mostreremo che se il compass routing sceglie di attraversare il lato sv di
D(Pn) allora la distanza da v a t `e strettamente minore della distanza tra s e
t. Sia ¯st il segmento che unisce s a t, e supponiamo che intersechi il triangolo
con vertici 4sxy. Sia C il cerchio sul quale giacciono s, x, y. Sia c il centro di C e s0 l’immagine speculare di s rispetto alla linea che unisce c e t (figura
3.26).
Siano α e β gli angoli formati tra ∠xst e ∠tsy rispettivamente. Si possono verificare due casi: gli angoli formati tra ∠xst e ∠tsy rispettivamente. Si possono verificare due casi:
1. α < β. In questo caso il compass routing sceglier`a il lato sx e dalla
figura 3.26 `e possibile vedere che la distanza tra x e t `e minore rispetto a quella tra s e t.
2. β ≤ α. Sia P1 il punto di intersezione tra C e il segmento che unisce s e
t, e P2 il punto che giace su C tale che la distanza tra P1 e P2 coincida
con la distanza che separa s e P1. Dalla figura 3.26 possiamo vedere
che P2 giace sul semicerchio C0 che unisce s a s0 in senso orario. Poich´e
β ≤ α y deve giacere su C0 e quindi la sua distanza con t `e pi`u piccola
rispetto alla distanza da s a t.
Questa tecnica di instradamento permette di costruire uno spanning tree a partire dalla Triangolazione di Delaunay.
Figura 3.26: Routing sulla triangolazione di Delaunay.
Il compass routing `e una tecnica di instradamento che permette di costruire uno spanning tree a partire dalla Triangolazione di Delaunay. Le decisioni locali avvengono secondo la definizione di Compass Routing: il nodo A, data la radice R, calcola il nodo B come suo genitore nell’albero, perch´e B `e il vicino con l’angolo pi`u piccolo rispetto ad R, figura 3.27(a).
Figura 3.27: Compass routing
In particolar modo, il Compass Routing viene utilizzato per costruire l’albero per il multicast in maniera distribuita. Ad esempio, un nodo A, `e il genitore del nodo C, perch´e l’angolo ∠RCA `e pi`u piccolo rispetto agli angoli ∠RCD e ∠RCB. Nello stesso modo, B e D non sono i genitori di C dal momento
che, ∠RCA < ∠RCB e ∠RCA < ∠RCD, (figura 3.27(b)). Se ogni nodo effettua il calcolo sopra descritto, viene definito uno spanning tree con radice R.
3.4.1
Descrizione algoritmo
In questa sezione verr`a descritto l’algoritmo che implementa il Compass Routing.
Compass Routing - Considerazioni preliminari
Il problema di costruire un albero di copertura sui nodi che si trovano all’in-terno di AOI consiste principalmente nello sfruttare le poche informazioni di cui dispone ogni singolo nodo; infatti ogni nodo, conoscendo esclusivamente le coordinate dei propri vicini, non pu`o fare assunzioni sulla struttura della rete se non per quanto riguarda i confini della propria area e le coordinate dei nodi con cui `e in contatto. Quindi la visione affidabile della rete che pu`o usare il nodo radice r dell’esempio precedente si riduce a quella riportata nella figura 3.28.
