Distributed hash table spaziali per la gestione di ambienti distribuiti virtuali

(1)

Universit`

a di Pisa

Facolt`

a di Scienze Matematiche Fisiche e Naturali

Corso di Laurea Specialistica in Tecnologie

Informatiche

Tesi

Distributed Hash Table spaziali

per la gestione di ambienti

virtuali distribuiti

Roberta Paris

Relatori

Controrelatore

Prof.ssa Laura Ricci

Prof. Francesco Romani

Dott. Emanuele Carlini

(2)

(3)

Indice

1 Introduzione 5

1.1 Struttura della tesi . . . 11

2 Stato dell’arte 13 2.1 Introduzione . . . 13

2.2 Distributed Virtual Enviroment . . . 14

2.2.1 Approccio Client/Server . . . 14

2.2.2 Approccio basato sul Cloud Computing . . . 17

2.2.3 Approccio P2P . . . 18

2.3 Strutture spaziali per DVE . . . 18

2.3.1 CAN (Content Addressable Network) . . . 18

2.3.2 SpatialP2P . . . 22

2.3.3 MOPAR . . . 28

2.4 Cell Zooming . . . 31

2.5 Confronto tra gli approcci visti . . . 33

3 PAM:Architettura generale 35 3.1 Architettura generale del sistema . . . 35

3.2 CAN per DVE: Analisi dei problemi . . . 37

3.3 Positional Action Manager . . . 40

3.4 Architettura della rete . . . 43

3.4.1 Lato Client . . . 43

3.4.2 Lato Server . . . 47

3.4.3 Risoluzione delle range query . . . 53

(4)

4 INDICE

4 PAM:Implementazione 61

4.1 PeerFactSim . . . 61

4.1.1 Architettura di base . . . 63

4.1.2 Lanciare una simulazione con un overlay del simulatore . . 66

4.1.3 Come creare una nuova overlay . . . 68

4.2 Implementazione di PAM . . . 74

4.2.1 PamID e PamContact . . . 76

4.2.2 La classe PamConfig . . . 77

4.2.3 I messaggi . . . 78

4.2.4 Le operazioni . . . 81

4.2.5 Gli overlay node . . . 89

4.2.6 La classe factory . . . 106

4.2.7 Raccolta delle statistiche e visualizzazione . . . 108

4.2.8 Un esempio di simulazione . . . 111

5 Risultati sperimentali 117 5.1 Metriche . . . 117

5.1.1 Coefficente di Gini . . . 118

5.2 Variazione del numero di giocatori . . . 119

5.3 Variazione del numero di server . . . 122

5.4 Valutazioni con bilanciamento . . . 126

(5)

Capitolo 1

Introduzione

Negli ultimi anni, con l’evolvere della tecnologia, si sono diffuse applicazioni per ambienti virtuali distribuiti (Distributed Virtual Enviroment, DVE).

Tali ambienti sono applicazioni che consentono di simulare ambienti virtuali nei quali interagiscono migliaia di utenti contemporaneamente. Queste applicazioni sono molto usate per simulare situazioni di emergenza in campo civile e scopi

militari, ma la killer application `e rappresentata dai giochi virtuali di massa [31].

I MMOGs (Massively Multiplayer Online Game) sono ambienti virtuali dove i giocatori possono interagire e collaborare tra loro. La differenza principale tra i MMOGS e gli altri giochi online sta nel fatto che quest’ultimi posseggono un numero elevato di giocatori che condividono lo stesso ambiente virtuale. Alcuni esempi di MMOGs sono World of Warcraft (WoW)[1], SecondLife[2] e GuildWar2 (GW2)[3], che contano milioni di giocatori attivi in tutto il mondo.

In un MMOGs ogni giocatore interagisce con l’ambiante virtuale e con altri giocatori attraverso un alter-ego detto avatar. All’interno di un ambiente virtuale

possono essere localizzati un insieme di entit`a aventi una posizione e uno stato.

Le entit`a presenti nell’ambiente virtuale possono essere:

• avatar controllati dai giocatori (figura 1.1(a));

• personaggi controllati dal sistema (NPC - Not Player Controlled) (figura 1.1(b));

(6)

6 Introduzione

(a) avatar (b) NPC

Figura 1.1: Esempi di personaggi di un MMOGs.

Per quanto riguarda gli oggetti, essi possono essere classificati in oggetti

mu-tabili, che generalmente posseggono uno stato che pu`o essere modificato (figura

1.2(a)), e oggetti immutabili come per esempio edifici, vegetazione e ulteriori el-ementi che compongono l’ambientazione del gioco (figura 1.2(b)). In particolare gli oggetti immutabili corrispondono a elementi grafici aventi una posizione fissa mantenuta nel client del gioco.

Ogni entit`a possiede uno stato che pu`o comprendere la texture grafica

utiliz-zata per visualizzarlo nel gioco e altre informazioni (ad esempio per un avatar il livello di combattimento, esperienza, ecc..).

Le azioni tipiche eseguite in un MMOGs sono le seguenti: • movimento degli avatar e NPC;

• interazione tra avatar;

• interazioni tra avatar e oggetti.

Ogni avatar possiede una Area di Interesse (AoI), che rappresenta la porzione

del mondo con il quale pu`o interagire. Un’AoI `e in genere di forma sferica avente

come centro la posizione dell’avatar e un raggio in genere configurabile dal client di gioco. Ogni volta che un avatar si muove deve venire periodicamente a

(7)

7

(a) oggetto mutabile (b) oggetto immutabile

Figura 1.2: Esempi di oggetti di un MMOGs.

aggiornamenti, il client deve ricevere periodicamente tali informazioni dal server che gestisce il gioco.

Questi tipi di applicazioni sono caratterizzate da una serie di problematiche che riguardano la gestione di un elevato numero di giocatori. Tali problematiche sono legate ai limiti fisici relativi alla banda della rete, alla latenza che caratterizzano

le reti best effort e alla elevata capacit`a computazionale necessaria per gestire il

gioco.

L’architettura maggiormente utilizzata per questo tipo di applicazioni `e

at-tualmente quella Client/Server. Questa architettura presenta tuttavia una serie

di problemi, prima di tutto quella della scalabilit`a. Un tipico problema `e la banda

richiesta per la gestione del MMOG.

La banda usata per la gestione dipende dal numero di giocatori connessi e dalla loro distribuzione nell’ambiente virtuale. Infatti in un MMOGs la maggior parte

del traffico `e dovuto all’aggiornamento dell’AoI per ciascun giocatore. Inoltre

in giochi di questo tipo si verifica spesso presenza di hotspot che aumentano ulteriolmente il traffico della rete. Un hotspot rappresenta una piccola regione del

mondo virtuale in cui si concentrano un gran numero di giocatori. Ci`o implica

che ciascun giocatore contiene nell’AoI un gran numero di avatar. Il server deve

perci`o inviare ad ogni avatar tutte le entit`a presenti nell’AoI, che risulta quindi

molto grande.

(8)

l’ar-8 Introduzione

chitettura che supporta questo tipo di applicazione. La pi`u diffusa `e quella che

utilizza un server cluster in cui vengono utilizzati un certo numero di server a cui i client si collegano per dividersi il traffico da trasmettere. Per questo tipo di ar-chitettura sono stati studiati diversi criteri secondo i quali dividere l’informazione da mantenere e sono:

• zoning: lo spazio di gioco viene diviso in pi`u zone gestite da diversi server;

• mirroring: lo spazio di gioco viene diviso in pi`u zone ognuna delle quali pu`o

essere gestita da server diversi. Gli avatar presenti nella stessa zona e in server diversi possono interagire tra loro;

• istancing: come il mirroring ma i client presenti in server diversi non possono interagire tra loro.

Gli studi fatti su questi tipi di applicazioni hanno mostrato diversi picchi del carico durante l’arco della giornata, dovuti ad un gran numero di connessioni da parte dei giocatori.

Gli operatori MMOGs sono costretti a utilizzare una grande quantit`a di risorse

hardware per poter far fronte agli elevati picchi di carico che si presentano nell’arco della giornata. D’altra parte usare un numero molto basso di risorse implicherebbe una grande inefficienza nel sistema soprattutto nelle ore in cui si collegano un gran numero di giocatori.

Per risolvere questi problemi sono stati studiati meccanismi basati sul Cloud computing [24]. Il Cloud computing consiste in un insieme di servizi e risorse computazionali che vengono fornite all’utente. L’utente che richiede risorse cloud paga solo quelle che effettivamente utilizza. Le ricerche sul cloud computing hanno richiesto meccanismi in grado risolvere il problema dell’over-provisioning. Per applicazioni di tipo MMOGs sono stati studiati meccanismi in grado di variare le risorse da usare in base al carico della rete. Tali meccanismi devono quindi permettere di richiedere un maggior numero di risorse durante le ore in cui si

presentano i picchi e di rilasciarle al momento in cui non sono pi`u necessarie.

Nonostante l’approccio cloud sia promettente, esso pu`o presentare ancora dei

problemi dovuti al costo delle risorse. In [9] viene proposta un’architettura basata sulla integrazione di risorse cloud e P2P. In tale soluzione i nodi della rete possono

(9)

9

essere risorse cloud o peer che devono distribuirsi tutte le informazioni riguardanti

la posizione delle entit`a nella rete.

La soluzione proposta si basa su una architettura che mantiene separate la

gestione dello stato e la gestione delle posizioni delle entit`a presenti in un DVE.

Tale architettura [9] presenta quindi una approccio integrato che prevede un certo

numero di nodi cloud/P2P che memorizzano lo stato delle entit`a presenti

all’inter-no dell’AoI di un avatar (State Action Manager, SAM) e un altro insieme di all’inter-nodi

che memorizzano la posizione di tutte le entit`a presenti nell’AoI di un giocatore

(Positional Action Manager, PAM).

Nella tesi `e stata realizzata un supporto per la PAM ispirato ad una DHT

quale CAN [27]. Le DHT [18] sono estensioni delle classiche tabelle hash [29] per

ambienti altamente distribuiti. CAN `e una DHT concepita per il filesharing che

mappa peer e dati nel solito spazio d-dimensionale toroidale. Lo spazio logico `e

quindi proiettato su uno spazio d-dimensionale, che viene diviso in zone ognuna

delle quali `e gestita da un singolo peer. Il peer gestisce una singola zona del DVE

e tutte le entit`a posizionate all’interno di essa. La posizione in cui mappare gli

oggetti e i peer viene ricavata applicando una funzione hash sull’indirizzo del peer o sulla chiave del dato, ed estraendovi le coordinate d-dimensionali.

Nella tesi `e stata scelta la soluzione CAN in quanto mantiene una struttura

spaziale che la rende particolarmente adatta per i DVE. In CAN la tabella di routing di ciascuna zona, gestita da un peer, contiene contatti con i peer che gestiscono le zone adiacenti. Inoltre CAN consente la memorizzazione dell’infor-mazione nello spazio d-dimensionale e definisce algoritmi di routing basati sulla distanza tra zona e punto. I problemi principali per l’adattamenti di questo tipo di DHT ad applicazioni DVE sono:

• movimento delle entit`a;

• risoluzione delle range query;

• gestione di pi`u zone da parte di un server;

• meccanismi di bilanciamento del carico.

Una prima differenza sta nel fatto che CAN consente di memorizzare solo

(10)

10 Introduzione

e la componente spaziale ha un ruolo a fondamentale in un DVE. Ci`o provoca

continui cambi di zona e di server da parte dei client a seconda del movimento dell’avatar nello spazio logico. Ogni client infatti si connette al server di PAM che gestisce la zona che lo contiene. Periodicamente il client notifica al server che lo gestisce la sua nuova posizione che cambia in seguito al suo movimento.

Lo spostamento di un avatar pu`o comportare il passaggio della sua gestione tra

server diversi.

In un DVE il movimento implica anche la risoluzione di una range query

sul-l’AoI dell’avatar, mentre nella versione originale di CAN `e impossibile eseguire

query complesse come le range query o query a multi attributo. In PAM invece

`e necessario eseguire range query in quanto le entit`a devono conoscere

periodica-mente gli avatar della propria AoI. Una range query pu`o essere completamente

risolta dal server che gestisce il client ed eventualmente delegata ai server che posseggono una zona vicina che interseca l’AoI del client per risolvere la parte mancante.

In CAN ogni zona viene gestita da un singolo peer e la distribuzione uniforme

delle zone e delle entit`a nello spazio permettono di bilanciarne il carico. In un

DVE invece le entit`a non sono distribuite uniformemente nello spazio e spesso si

verificano hotspot che possono sovraccaricare i server che li gestiscono. In PAM

si `e dovuto affrontare questo problema consentendo a ciascun server della rete

di gestire pi`u zone e definendo algoritmi di bilanciamento in grado di dividerle e

distribuirle tra i server meno carichi. Nella tesi `e stato realizzato un algoritmo di

bilanciamento per dividere e distribuire le zone tra i peer della rete a seconda del carico di ciascuno di essi.

Per implementare e testare PAM `e stato usato un simulatore ad eventi quale

PeerFactSim [4] che consente di simulare overlay a grandi scala. Le simulazioni

sono state effettuate considerando un modello di mobilit`a ispirato a SecondLife.

Le analisi svolte hanno dimostrato che far gestire per ciascun server una singola zona porta ad un elevato sbilanciamento della rete. Sono state eseguite analisi sia su una partizione uniforme dello spazio sia su una partizione dello spazio incen-trata sugli hotspot. L’ultimo caso ha portato insignificanti miglioramenti rispetto al primo a causa della gestione di una singola zona da parte di un peer. Infine

(11)

1.1 Struttura della tesi 11

ciascun server pi`u zone e i risultati hanno dimostrato che tale algoritmo `e riuscito

ad ottenere un buon bilanciamento del carico.

1.1 Struttura della tesi

Nel capitolo 2 vengono illustrate le possibili architetture per i DVE, alcune soluzioni per memorizzare informazioni spaziali con particolare riferimento a CAN. Inoltre viene mostrato un approccio al bilanciamento del carico utilizzato dalle reti di cellulare per diminuire il carico delle celle. Nel capitolo 3 viene dato un accenno

su SAM e PAM, in particolare come si `e realizzato la rete PAM basata su CAN,

in particolar modo l’architettura del sistema e gli algoritmi usati. Nel capito-lo 4 viene introdotto l’ambiente di simulazione usato, gli algoritmi implementati e l’ambiente di simulazione. Nel capitolo 5 vengono analizzati i risultati delle simulazione attraverso grafici. Il capitolo 6 riporto infine alcune conclusioni.

(12)

(13)

Capitolo 2

Stato dell’arte

In questo capitolo verranno illustrati alcuni degli attuali approcci esistenti in let-teratura riguardanti le proposte di supporti di ambienti virtuali. In particolare

verr`a analizzato l’approccio della Distributed Hash Table CAN usata per

appli-cazioni di tipo il file sharing e alcune DHT spaziali introdotte come supporto per

applicazioni per ambienti virtuali distribuiti. Inoltre verr`a dato qualche accenno

a tecniche di bilanciamento del carico che riguardano entit`a in movimento.

2.1 Introduzione

La maggior parte delle applicazioni P2P sono state implementate su dati che gestiscono dati 1D come stringhe e numeri, mentre nei DVE sia i nodi che le informazioni hanno una posizione e le query si basano su questa. Ultimamente sono state sviluppate applicazioni P2P in grado di gestire dati multidimensionali,

che vengono memorizzati tenendo conto delle loro propriet`a spaziali preservendo

la loro localit`a e direzionalit`a. Alcune soluzioni prevedono di mappare i dati

mul-tidimensionali in una singola dimensione e usare Distributed Hash Table (DHT),

utilizzando metriche di distanza per definire la localit`a per dati 1D. Altre

con-siderano uno spazio multidimensionale (per esempio 2D) su cui mappare dati e i peer utilizzando algoritmi di routing basati sulla distanza tra punti nello spazio.

Un esempio di DHT che usa uno spazio logico multidimensionale `e dato da

CAN (Content Addressable Network)[27], in cui ai peer e ai dati vengono asso-ciate coordinate nello spazio, la cui applicazione riguarda applicazioni di tipo file

(14)

14 Stato dell’arte

sharing. Un’altro esempio `e dato da SpatialP2P[19] che stato concepito per

man-tenere informazioni che posseggono di per se una posizione nello spazio. Infine

MOPAR[35] `e una rete P2P completamente decentralizzata concepita per DVE,

dove l’informazione memorizzata non solo possiede una posizione, ma pu`o anche

muoversi nello spazio.

Un caratteristica fondamentale degli ambienti virtuali distribuiti `e il

movimen-to delle entit`a e la presenza di hotspot che possono sbilanciare notevolmente il

carico della rete. Per questo motivo sono state fatte anche delle considerazioni sul bilanciamento del carico prendendo come riferimento la tecnica Cell Zooming[26] effettuato dalle reti di cellulari. Infatti i cellulari rappresentano di per se un

es-empio di entit`a mobili che si spostano e che devono registrarsi presso una cella

della rete di cellulari.

2.2 Distributed Virtual Enviroment

Un Distributed Virtual Enviroment (DVE)[28] `e un mondo virtuale dove pi`u

gioca-tori interagiscono tramite un alterego virtuale detto avatar, alcuni esempi di DVE sono dati da World of Warcraft (WoW)[1], SecondLife[2] e GuildWar2 (GW2)[3], che contano milioni di giocatori attivi in tutto il mondo. I supporti per DVE definiti attualmente adottano uno dei seguenti approcci:

• Client/Server; • Cloud based; • P2P.

2.2.1 Approccio Client/Server

L’approccio Client/Server [20] `e utilizzato dalla maggior parte dei DVE e

uti-lizza un cluster di server che forniscono una grande potenza di calcolo, capaci

quindi di gestire grandi quantit`a di traffico di rete. Ogni utente si collega ad un

server tramite un’applicazione Client tramite la quale pu`o condividere il proprio

stato con il DVE. Il Client gestisce solo una minima parte dell’informazione e corrisponde all’area di gioco rappresentata dalla sua Area di Interesse (AoI), che

(15)

2.2 Distributed Virtual Enviroment 15

contiene le entit`a con le quali interagisce. D’altra parte i server devono gestire

una grande quantit`a di informazione, e rappresentano quindi dei punti di

falli-mento con evidenti problemi di scalabilit`a in DVE in cui si collegano migliaia di

giocatori.

Esistono tuttavia diverse strategie adottate per bilanciare il carico dei server,

rendendo quindi la soluzione client server pi`u scalabile. Tali approcci sono:

• zoning; • mirroring; • instancing.

Figura 2.1: Divisione spazio logico di un ambiente virtuale distribuito.

L’approccio zoning consiste nel dividere lo spazio di gioco in un insieme di zone e di associare ogni server ad una diversa macchina. In genere il mondo virtuale utilizzato nei DVE presenta una naturale divisione dello spazio di gioco

rappre-sentato da stanze, dangeon, citt`a o paesi e si presta facilmente a questo tipo di

approccio. Vanno tuttavia gestiti i cambiamenti di zona dovute allo spostamento dell’avatar e di conseguenza il server che lo gestisce. Inoltre occorre garantire al

giocatore di ricevere tutte le entit`a presenti all’interno della sua AoI nei casi in cui

quest’ultima si sovrapponga a pi`u zone diverse. La presenza di zone quali citt`a

(16)

a raggrupparsi pi`u giocatori. Questa rappresenta la causa principale di

sovrac-carico di un server. Per risolvere questo problema occorre quindi introdurre una partizione dinamica dello spazio in maniera da bilanciare il carico tra i server.

(a) zoning (b) mirroring

Figura 2.2: Connessioni tra client e server.

L’approccio mirroring `e basato anch’esso sulla divisione dello spazio in zone

gestite da server. A differenza del zoning il sovraccarico della rete dovuto alla presenza di hotspot viene risolto replicando la zona che lo contiene e affidando

le varie repliche a server diversi. Per ogni server verr`a distribuito il numero di

giocatori gestiti da esso in modo da bilanciare il carico. Tale soluzione prevede complessi algoritmi per la sincronizzazione dei server che contengono la replica della stessa zona, per consentire a ciascun giocatore di interagire con tutti gli altri giocatori presenti nella sua AoI.

Un versione semplificata del mirroring `e data dall’approccio instancing, dove si

mantiene ancora il concetto di divisione di zone. In questa soluzione ogni replica

`e invece sostituita con una diversa istanza della stessa zona. Ci`o implica che

giocatori presenti in istanze diverse della stessa zona non potranno interagire tra loro.

Per bilanciare ulteriormente il carico si possono prevedere diversi server che si occupano di diversi aspetti del gioco come per esempio:

• gestione della chat; • fase di login;

• scaricamento e installazione delle patch.

Il problema principale di questi sistemi `e l’elevato costo dovuto all’acquisto

dell’hardware e al suo mantenimento. Questi problemi possono essere risolti in parte introducendo un approccio basato su cloud.

(17)

2.2 Distributed Virtual Enviroment 17

2.2.2 Approccio basato sul Cloud Computing

L’approccio basato su cloud [24], invece, permette di variare le risorse a dispo-sizione a seconda del numero dei giocatori presenti nel DVE. Le diverse analisi svolte su un’architettura di tipo client/server per DVE hanno mostrato la pre-senza di diversi picchi di carico nell’arco della giornata. Utilizzare molte risorse implica un grande spreco soprattuto in quelle ore in cui il numero di giocatori

collegati `e molto basso, viceversa considerare poche risorse pu`o portare invece

sovraccarico della rete in quelle ore del giorno in cui `e presente maggior affluenza

dei giocatori. Per garantire maggiore elasticit`a nel considerare il numero di risorse

da usare e quindi risolvere i problemi di sovraccarico, `e possibile utilizzare un

ap-proccio basato su cloud. Per esempio per applicazioni DVE gli operatori di gioco potrebbero richiedere un maggior numero di risorse nelle ore o nei giorni in cui si presentano picchi del carico. Occorre quindi utilizzare meccanismi di

approvvi-gionamento dinamico in grado di richiedere un pi`u grande numero di risorse in

questi tipi di situazioni. Questo implica la definizione di meccanismi di che per-mettano di monitorare e collezionare metriche sulla performance del sistema in realtime, e di decidere dinamicamente il numero ottimale di risorse necessarie per limitare il carico in presenta di picchi. Esempi di metriche da utilizzare riguardano la banda usata, il numero di messaggi inviati e l’utilizzo delle risorse attualmente affitatte.

Per esempio i DVE possono essere strutturati attraverso un’architettura a tre livelli ([24]). Il primo livello formato da un insieme di risorse che si occupano di gestire tutti i protocolli base del gioco usato per la verifica e il controllo. Un secondo livello che si occupa di dividere lo spazio di gioco in un insieme dinamico di zone ognuna delle quali gestita da un server ed un terzo livello che si occupa di

rendere persistente lo stato della rete. Ognuno di questi livelli pu`o essere composto

da un insieme dinamico di server paralleli che varia a seconda del carico della rete. Un approvvigionamento elastico delle risorse libera i DVE dai grandi costi di acquisto, mantenimento e gestione delle risorse hardware. Occorrono tuttavia algoritmi dinamici che consentano un approvigionamento efficiente delle risorse a seconda del carico del sistema.

(18)

2.2.3 Approccio P2P

L’approccio basato su P2P `e completamente distribuito rispetto ai primi due e

offre vantaggi rispetto al cloud. Le infrastrutture P2P sono molto scalabili e possono alleggerire il carico dei vari peer al crescere del numero dei giocatori.

Architetture P2P per DVE presentano molte differenze rispetto alle classiche applicazioni P2P come il filesharing. La principale differenza riguarda le query che vengono eseguite nella rete. Mentre in applicazioni per DVE le ricerche spesso interessano un unico peer della rete, le ricerche eseguite in un DVE sono range query che riguardano l’informazione presente all’interno dell’Area di Interesse dei giocatori. Le informazioni presenti all’interno dell’AoI in un DVE basata su una architettura P2P, possono essere presenti in peer differenti. Un architettura P2P per DVE deve cercare di minimizzare il numero di peer da contattare per risolvere

una range query in maniera da garantire maggiore interattivit`a tra i giocatori della

rete.

Nei paragrafi successivi verranno illustrati alcuni approcci P2P che consentono di memorizzare nella rete dati che posseggono una posizione in uno spazio logico.

In questi approcci ogni peer gestir`a una porzione dello spazio logico e tutti i dati

posizionati al suo interno.

2.3 Strutture spaziali per DVE

In questo paragrafo saranno illustrate strutture spaziali per implementare

architet-ture P2P. In particolar modo verr`a illustrato il funzionamento di CAN su cui si

basa la tesi e altri esempi di architetture spaziali quali SpatialP2P e MOPAR.

2.3.1 CAN (Content Addressable Network)

CAN [27] `e una DHT concepita per il filesharing che considera come spazio degli

indirizzi uno spazio logico cartesiano d-dimensionale toroidale. Lo spazio logico viene suddiviso in aree rettangolari, dette zone, ed assegnate ai peer della rete.

Ogni dato ed ogni peer viene mappato in un punto P nello spazio logico, ogni

(19)

2.3 Strutture spaziali per DVE 19

dato. Per ricavare le coordinate di un dato nello spazio d-dimensionale, viene ap-plicata una funzione hash al suo identificatore. Tale funzione permette di ottenere una sequanza di bit che viene partizionata in d sottosequenze, ognuna delle quali rappresenta una coordinata nello spazio d-dimensionale.

Quando un peer n effettua l’operazione di join, contatta inizialmente un nodo di bootstrap che mantiene la lista di alcuni peer attualmente presenti in CAN. Il nodo di bootstrap comunica al peer n gli indirizzi IP di alcuni peer scelti ca-sualmente. Appena ricevuti i contatti dei peer presenti nella rete, n invia un

messaggio di JOIN a uno di questi. Tale messaggio conterr`a un punto P ricavato

dall’identificatore del peer, che `e utilizzato solo in questa fase per l’assegnamento

della zona.

Infatti il messaggio viene instradato verso la zona che contiene il punto P attraverso un algoritmo di routing greedy. Raggiunta la zona contenente P, viene effettuata l’operazione di split, dove la zona viene dimezzata e la restante parte assegnata ad n. L’operazione di split viene effettuata in modo tale da dividere una zona in due parti uguali, alternando ogni volta la dimensione su cui dividere (ipotizzando uno spazio bidimensionale si alterna la divisione della zona tra l’asse delle Y e quella delle X, un esempio in figura 2.3). Le chiavi contenute nella zona assegnata al nuovo peer, vengono trasferite a quest’ultimo.

(a) Entrata di un nuovo peer. (b) Partizione della zona e aggiorna-mento dei vicini.

(20)

L’algoritmo di routing `e un algoritmo greedy, basato sulla distanza tra le zone

(figura 2.4). La distanza tra una zona ed un qualsiasi punto P `e mostrata in figura

2.4(a). Per instradare quindi i messaggi ogni peer ha una routing table contenente la lista dei peer aventi le zone vicine alla propria.

(a) (b)

(c) (d)

Figura 2.4: Routing in CAN.

In una rete CAN con uno spazio a d dimensioni, due nodi sono considerati vicini se i lati delle loro zone si sovrappongono per d − 1 dimensioni e hanno un lato adiacente nella d-esima dimensione. Considerando uno spazio a d-coordinate,

la lunghezza media del cammino di routing `e di circa (d/4)(n1/d_{) hop ed la}

dimen-sione di ogni routing table pu`o essere al massimo di 2d entrate. Quindi ogni peer

(21)

peer destinatario (figura 2.4(b)) fino a raggiungere la zona contenente P. Durante la fase di split occore anche aggiornare i vicini delle zone coinvolte, per mantenere consistenti le tabelle di routing.

Quando un peer esegue la PUT di un dato, questo viene indirizzato verso il peer che possiede la zona che lo contiene. CAN prevede query semplici che vengono indirizzate anch’esse verso il peer che possiede l’informazione e successivamente l’informazione viene scaricata direttamente da quest’ultimo.

Per quanto riguarda l’uscita volontaria di un peer dalla rete, esistono varie

soluzioni, una di queste `e la seguente. Quando un peer esce dalla rete, informa i

vicini della sua uscita in modo tale che questi ultimi possano eliminarlo dalle loro

tabelle di routing e invia al vicino pi`u promettente la zona e l’insieme dei dati

presenti al suo interno.

(a) Partion Tree (b) Partizione delle zone

Figura 2.5: Quando S7 affida la propria zona a S0 che pu`o fare una merge.

Il vicino pi`u promettente a cui affidare la zona `e quello avente il VID della

zona pi`u simile alla sua. Il VID `e un identificatore costituito da una stringa di

bit diverso per ogni zona ed equivale al cammino radice-foglia del partioning tree

(figura 2.5(a)). Il partioning tree `e un albero binario che visualizza la storia delle

partizioni le cui foglie sono le zone in cui lo spazio `e stato diviso. Due foglie

aventi lo stesso padre indicano due zone adiacenti che possono essere fuse in un unica zona e appartenendo allo stesso sottoalbero dove il VID differisce solo per

(22)

(a) Partion Tree (b) Partizione delle zone

Figura 2.6: Quando S4 effettua una leave pu`o affidare la propria zona a S7 o a S0.

l’ultimo bit (figura 2.5). Il vicino pi`u promettente a cui affidare la zona `e quindi il

peer che possiede la zona vicina avente il VID pi`u simile, in maniera da favorire le

operazioni di merge. In generale favorire il merge implica un numero di hop minore

durante la fase di routing, in quanto le zone sono pi`u grandi. Se non esistono zone

di questo tipo la zona viene semplicemente affidata al peer che gestisce la zona

vicina con VID pi`u simile (figura 2.6). In entrambi i casi occorre poi informare i

vicini dei cambiamenti apportati.

I vantaggi di una rete CAN sono principalmente dimensione delle routing table non dipendente dal numero di peer della rete, ma bens`ı dal numero di dimensioni

dello spazio di CAN, e la possibilit`a di ridurre il numero di hop del routing

all’au-mentare delle dimensioni. Inoltre, la presenza di pi`u cammini verso un punto P,

permette di gestire in maniera affidabile i guasti (fault tolerant). Lo svantaggio

principale `e che CAN non prevede replicazione dei dati e non supporta query pi`u

complesse come range query o query multivalore.

2.3.2 SpatialP2P

SpatialP2P[19] `e una rete P2P per il filesharing la cui struttura `e adatta a

mem-orizzare informazioni spaziali. Essa usa una griglia 2D per partizionare lo spazio degli identificatori, definendo un’appropriata metrica per la distanza necessaria

(23)

per stabilere il concetto di vicinanza. Ogni cella della griglia `e identificata da

co-ordinate cartesiane, e rappresenta la pi`u piccola grana di informazione che viene

memorizzata nel sistema. Lo spazio degli identificatori dei dati e dei peer `e lo

stesso. I dati e i peer vengono posizionati nella griglia secondo le loro rispettive coordinate. Ogni peer memorizza i dati che si trovano nella sua stessa cella e in

quelle di altre celle a lui vicine. La vicinanza relativa tra la celle C e la cella C0

viene stabilita considerando la distanza D(C, C0) cos`ı definita:

D(C, C0) = (d1, d2) dove    d1 = max({|cx− c0x| |cy− c0y|} d2 = min({|cx− c0x| |cy − c0y|}

dove le coordinate (cx, cy) indicano rispettivamente la riga e la colonna della cella

C, mentre (c0_x, c0_y) quelle della cella C0. La relazione di ordinamento tra due

distanze D = (d1, d2) e D0 = (d01, d 0 2) `e definita come: D < D0 sse    d1 < d01 d1 = d2 and d2 < d02

Da D(C, C0) pu`o essere ricavata facilmente sia la distanza euclidea che la

Man-atthan distance.

Rispetto alla Manatthan Distance, questa nozione di distanza consente di man-tenere separate le componenti relative ai deversi assi. Si considerano,ad esempio, le celle s e t in figura 2.7(a). Nel caso di Manatthan Distance, le celle hanno la

stessa distanza da A, nel caso della distanza sopra definita la cella s risulta pi`u

distante da A rispetto alla cella t, il che descrive meglio la realt`a.

Una cella A viene associata al peer p che si trova pi`u vicino secondo la nozione

di distanza data. A questo scopo le celle intorno ad A vengono divise in al massimo otto gruppi di forma triangolare e numerandole in senso antiorario (figura 2.7(a)). Il numero di gruppi dipende dalla posizione di A all’interno della griglia, per esempio nel caso A sia posizionata in un angolo della griglia, i gruppi saranno tre.

I gruppi di celle cos`ı creati hanno la seguente propriet`a: tutte le celle equidistanti

dalla cella A appartengono a gruppi diversi. Tale propriet`a `e necessaria per rendere

l’associazione cella-peer non ambigua. La cella A verr`a infatti associata al peer

(24)

(a) Ordinamento delle celle della griglia.

(b) Partizione dello spazio tra i peer.

Figura 2.7: Come associare aree ai peer con SpatialP2P.

gruppo con il numero pi`u piccolo. Ad esempio in figura 2.7(a) al cella A viene

affidata al peer p0. La figura 2.7(b) mostra un esempio di distribuzione delle celle

tra i peer p1,p2,p3,p4 e p5.

Per garantire la connettivit`a della rete, ogni peer mantiene link con altri peer.

Per ogni peer vengono creati link verso peer detti successori e altri peer detti indexed peer (figura 2.8). Lo spazio intorno al peer viene diviso in quadranti

e viene creato un link con il peer pi`u vicino per ciascun di essi (tali peer sono

i successori). Per trovare gli indexed peer per un peer di coordinate (x, y) si

prendono in considerazionte i peer pi`u vicini alle coordinate: (x±2i_{, y) o (x, y ±2}i₎

per i = 0 . . . N − 1 dove N × N `e la dimensione della griglia. Tale approccio `e

ispirato a Chord.

La ricerca pu`o partire da qualsiasi peer p del sistema. L’algoritmo di

ricer-ca prende come input una o pi`u celle. Sia C l’insieme delle celle da cercare e

CelleT rovate l’insieme delle celle trovate durante la ricerca, l’algoritmo procede nel seguente modo:

• per ogni cella c ∈ C, p controlla se possiede c e in tal caso restituisce informazione corrispondente;

(25)

Figura 2.8: In figura a) i successor peer, mentre in figura b) gli indexed peer.

indexed peer p0 tali che c = p0 e in tal caso inoltra la ricerca di c a p0;

• per ogni c ∈ C \CelleT rovate, p inoltra la ricerca di c al successore o indexed

peer pi`u vicino a c.

L’algoritmo di ricerca `e molto efficiente e ha complessit`a in tempo pari a

O(logN ).

L’aggiornamento dei link dovuti alle operazioni di join e di uscita di un peer

dalla rete, SpatialP2P pu`o usare due possibili soluzioni. La prima soluzione

prevede che il peer p effettui una ricerca per ogni entrata dei suoi link, per

ag-giornarli. La seconda soluzione viene usata per velocizzare l’aggiornamento e

prevede che ogni peer mantenga anche i link dei suoi vicini, in questo modo

lim-iterebbe la ricerca ad una area pi`u piccola. Entrambi i casi hanno un costo in

tempo pari a O(log2_{N ) in tempo.}

Quando un peer p intende fare una join contatta un peer della rete scelto

casualmente, detto bootstrapping peer pB, che si occupa di trovare i successori

di p. Al passo seguente p memorizza l’informazione che pu`o condividere, che `e

memorizzata in altri peer, e notifica agli altri peer la sua presenza nella rete. Infine p trova i proprii indexed peer tramite l’operazione di aggiornamento dei link.

Quando invece un peer p lascia la rete, deve occuparsi di assegnare i dati che ha memorizzato agli altri peer vicini. Il peer p notifica ai vicini la usa intenzione di lasciare la rete, permettendo ai suoi vicini di aggiornare i propri link.

(26)

Per garantire robustezza del sistema ai fallimenti dei nodi della rete, viene presa in considerazione la replicazione delle informazioni in altri peer della rete. Ogni peer che ha un link con p, contiene anche link ai peer contenenti le repliche dei dati di p. I peer replica contengono anche link fra loro in maniera da bilanciare il carico.

In alcune applicazioni le informazioni spaziali possono occupare pi`u celle della

griglia, in questi casi SpatialP2P pu`o consentire anche di memorizzare insiemi di

celle che occupano un’area rettengolare. Ogni area A `e rappresentata tramite una

quadrupla (x1, y1, x2, y2) dove (x1, y1) e (x2, y2) indicano rispettivamente l’angolo

in basso a sinistra e l’angolo in alto a destra del rettangolo, dai quali `e possibile

ricavare la sua dimensione α(A) e il suo centro κ(A).

α(A) =p(x2 − x1)(y2− y1) κ(A) = x2− x1 2 , y2− y1 2

Siano A e A0 due aree, la distanza Dz(A, A0) = (d1, d2) tra le due aree `e calcolata

come: d1 = 2 ∗ Mx+ θ|α(A) − α(A0)| α(A) + α(A0₎ d2 = 2 ∗ My+ θ|α(A) − α(A0)| α(A) + α(A0₎

dove (Mx, M y) = D(α(A), α(A0)) `e la distanza tra i centri di A e A0. Questa

dis-tanza tiene conto della disdis-tanza tra i centri delle due aree e della loro dimensione. La costante θ indica quanto la dimensione delle aree influenza la distanza relati-va. Se θ assume un valore grande, aree di dimensione simile vengono considerate

pi`u vicine. Viceversa se θ assume un valore piccolo, aree di grandi dimensioni

verranno considerate vicine.

Analizziamo come assegnare le aree ai peer. Inanzitutto i peer vengono rap-presentati a loro volte tramite aree e quindi posizionati all’interno della griglia

(figura 2.9(a)). L’area Ai viene assegnata al peer pi pi`u vicino, ovvero al peer la

cui distanza Dz(Ai, pi) `e pi`u piccola.

Nel caso in cui esistano un peer p e p0 la cui distanza da Ai`e uguale, l’ambiguit`a

(27)

(a) Aree nello spazio. (b) Successori di un peer.

Figura 2.9: Gestione delle aree.

piccolo, previlegiando il peer con area pi`u simile ad Ai o scegliendo quello avente

la distanza tra i vertici pi`u lontani che sia minima.

A differenza del caso precedente si hanno sei successori, uno per ciascuno

quadrante seguendo il criterio precedente, uno con il peer pi`u vicino tra quelli

più grandi e uno con il peer più vicino tra quelli più piccoli (figura 2.9(b)). Per

quanto riguarda gli indexed peer, oltre a mantenere link lungo i semiassi relativi alla posizione del punto centrale, si mantengono anche indexed peer relativi alla dimensione secondo un incremento logaritmico.

Gli indexed peer di p(px1, py1, px2, py2) sono infatti i peer q(qx1, qy1, qx2, qy2) tali che α(q) = α(p) e: • κ(q) = κ(p) ± (α(p) · 2i_{, 0);} • κ(q) = κ(p) ± (0, α(p) · 2i_); • κ(q) = κ(p) ± (2i_{, 0);} • κ(q) = κ(p) ± (2i_{, 0);} • κ(q) = κ(p). per i >= 0.

(28)

2.3.3 MOPAR

MOPAR[35] `e una rete P2P pensata specificamente per i DVE. Essa rappresenta

un altro esempio di DHT basata su una divisione dello spazio, ma la divisione

`e in celle esagonali anzich`e quadratiche. MOPAR si appoggia su una DHT tipo

Chord[34] o Pastry[30], che gestiscono dati unidimensionali.

La mappa del mondo viene cos`ı divisa in celle esagonali, ognuna delle quali ha dimensioni tali da approssimare l’area d’interesse del giocatore. Le celle esagonali sono identificate tramite coordinate del tipo (riga,colonna) ottenute considerando una griglia avente righe e colonne passanti per i loro centri come visualizzato in 2.10. In MOPAR sono state scelte celle esagonali in quanto permettono di approssimare meglio l’Area di Interesse di un giocatore rispetto a celle quadratiche.

Figura 2.10: Partizionamento del mondo virtuale con le relative coordinate.

`

E possibile mappare facilmente la posizione del giocatore con la cell-id,

asso-ciandolo cos`ı ad una cella. Quando un giocatore si muove pu`o cambiare cell-id

e quindi cella. Ogni giocatore pu`o essere visto come un peer la cui posizione

co-incide con la posizione del giocatore stesso nel mondo virtuale e che pu`o essere

(29)

Una cella pu`o contenere solo un MN che ha il compito di registrare tutte

le informazioni relative agli SN presenti nella propria cella. Ogni MN mantiene collegamenti interni con i SN e collegamenti esterni con i MN delle celle adiacenti. Quando un SN si muove aggiorna la propria posizione notificandola al MN, mentre

quando il MN si muove notificher`a la sua posizione ai MN vicini. La vicinanza

tra nodi della rete `e espressa tramite l’adiacenza delle celle, infatti i nodi vicini

sono quelli che sono nelle celle adiacenti. Ci`o basta per conoscere i giocatori

presenti nella propria AoI, in quanto quest’ultima, a causa delle sue dimensioni,

pu`o intersecare solo celle adiacenti (figura 2.11).

Figura 2.11: Connessioni tra MN e SN dove i nodi rossi sono i MN e quelli verdi i SN.

Come nel caso di SpatialP2P, le celle vengono partizionate tra i nodi della rete. Viene cos`ı costruita una DHT ad anello con i nodi, ad ognuno dei quali viene assegnato un certo insieme di celle. L’associazione cella peer avviene codificando la cell-id tramite la funzione SHA-1 in un hex-id, ed associando la cella al peer

avente id numericamente pi`u vicino all’hex-id. Abbiamo cos`ı ottenuto una diversa

partizione dello spazio di gioco (figura 2.12).

I nodi della DHT sono detti Home Node (HN). La corrispondena tra una

cella ed il suo HN `e determinato dal mapping definito dalla DHT e, se non si

(30)

statico. L’avatar che corrisponde all’HN di una cella non `e quindi necessariamente

presente in quella cella. Invece gli avatar corrispondenti a MN e sono presenti nella

cella corrispondente. L’HN `e necessario per la gestione delle celle delle celle in

cui non `e presente alcun avatar. Tutte le informazioni relative al gioco e alle

registrazioni dei master node della cella, vengono memorizzate sull’HN. Quindi, quando un SN si registra ad un MN, il MN memorizza le informazioni sull’HN

della cella. La DHT permette di avere la connettivit`a globale della rete.

Figura 2.12: Esempio di una possibile partizione delle celle tra gli HN della DHT secondo Pastry.

La join viene effettuata quando il giocatore intende entrare nel gioco. Per prima cosa il peer contatta il nodo di bootstrap che si occupa di inserirlo nelle DHT

ed inoltra la richiesta di join all’HN della cella in cui il giocatore `e posizionato. Il

peer del giocatore a questo punto pu`o diventare un MN o un SN a seconda che la

cella sia vuota oppure no.

Il movimento del giocatore nel mondo pu`o cambiare la topologia della rete dello

spazio di gioco. Quando un peer si muove all’interno della stessa cella la topologia rimane inalterata. Se un peer cambia cella occorre eseguire una procedura di switching. La procedura di switching si divide un due fasi e si differenzia a seconda che il peer sia MN o SN. Nella prima fase bisogna lasciare la vecchia cella, questo

(31)

2.4 Cell Zooming 31

significa che se il peer `e MN occorre trovare un nuovo MN per la vecchia cella che

lo sostituisca (se esiste) e notificare ai MN vicini la modifica. Diversamente gli SN devono eliminare la registrazione presso il MN della vecchia cella. La seconda fase consiste nella procedura di entrata nella nuova cella. Se un peer entra in una cella in cui esistono altri nodi, diventa SN e si registra presso il MN della nuova cella. Invece se la cella non contiene nodi, il nuovo peer entrante diventa MN della

cella e inizia la procedura di ricerca dei MN vicini. Questa procedura `e coordinata

dall’HN della cella.

Una maniera semplice per cercare i MN vicini `e quello di interrogare la DHT

inviando la query all’HN, che risulta molto costoso. Un modo migliore di procedere `

e quello di sfruttare la conoscenza dei MN vicini per minimizzare il numero di

query alle DHT e se `e possibile cercare di riconoscere quando una cella `e vuota.

Inanzitutto quando un peer si sposta in una nuova cella, la sua vecchia cella diventa

suo vicino, quindi un possibile MN viene gi`a trovato nella fase di switching. Parte

dei vicini della vecchia cella continuano a rimanere vicini della nuova cella, quindi

si pu`o venire a conoscenza di un’altra porzione di eventuali MN. I vicini rimanenti

possono essere ottenuti nella stessa maniera ricercando ricorsivamente tra i vicini dei vicini della vecchia cella adiacenti alla nuova cella fino a quando non vengono

coperti tutti i possibili vicini. Se non `e possibile raggiungere tutte le celle adiacenti

a causa di celle vuote, la copertura delle celle vicine viene garantita interrogando

la DHT per le celle mancanti. Ci`o accade quando gruppi di MN sono isolati tra

loro.

Quando un peer lascia il gioco si comporta come la fase in cui lascia la cella, inoltre deve eliminarsi in maniera sicura dalla DHT.

2.4 Cell Zooming

Il problema della gestione di un grande numero di connessioni da parte di un nodo `

e un problema molto comune che si verifica anche nelle reti di cellulari.

Le connessioni in una rete di cellulari vengono stabilite attraverso la vicinanza tra il mobile (Mobile Unit o MU) e le antenne. Nelle reti di cellulari la vicinanza

mobile-cella viene misurata come la qualit`a del segnale ricevuto dal mobile, in altri

(32)

di trasmissione del segnale, l’altezza dell’antenna della base station sono alcuni dei parametri fisici che determinano la dimensione della cella. Il procedimento di Cell Zooming [26] consiste nel variare la dimensione delle celle, e quindi variare i parametri fisici, a seconda del carico della rete (figura 2.13).

(a) Dimensioni originali. (b) Aumento del carico. (c) Diminuzione del carico.

Figura 2.13: Operazioni di cell zooming in una rete di cellulari.

Pu`o accadere infatti che molti MU avvicinandosi ad una cella, si possano

collegare ad essa e congestionare il traffico nella base station che la gestice. Una

soluzione a questo problema `e quella di diminuire la dimensione della cella,

dimin-uendo per esempio la potenza trasmessa, mantenendo per`o la copertura della

su-perficie (figura 2.13(b)). In questo modo gli MU che non riescono pi`u a ricevere

bene il segnale dalla base station, si collegheranno ad un’altra cella vicina da cui

ricevono meglio il segnale. Lo stesso ragionamento pu`o essere fatto nel caso in

cui una base station sia poco attiva, in questo caso per`o la dimensione della cella

viene aumentata 2.13(c).

Riconducendoci alle reti di cellulari, tale procedimento pu`o essere sfruttato

anche nelle reti P2P che fanno uso di DHT che dividono lo spazio degli indirizzi in aree, aumentando o diminuendo la dimensione di quest’ultime per ovviare a

problemi di congestioni per alcuni nodi. Nelle applicazioni P2P per i DVE ci`o

pu`o essere un punto critico per alcune zone del mondo virtuale che presentano

un’alta densit`a della popolazione (per esempio citt`a o zone di battaglia). Tale

approccio in questo caso presenta problematiche differenti rispetto a quelle delle reti di cellulari.

(33)

2.5 Confronto tra gli approcci visti 33

Diversamente da una rete di cellulari le cui celle si possono intersecare, le DHT viste fino ad ora offrono una partizione del mondo virtuale. Quindi aumentare la dimensione di alcune celle in una DHT implica la diminuzione della dimensione di celle ad esse vicine. Per questo motivo deve essere considerata un’adeguata partizione delle celle tra i nodi, che consenta di poter implementare facilemente tale procedimento.

2.5 Confronto tra gli approcci visti

Nei paragrafi precendenti sono stati visti tre approcci P2P il cui funzionamento `e

basato su uno spazio logico. Tali approcci permettono di mappare e posizionare in uno spazio logico i peer e i dati da memorizzare nella DHT.

In particolare CAN `e stato progettato per il filesharing e consente di

map-pare dati e peer in uno spazio logico d-dimensionale non toroidale attraverso una funzione hash, consentendone una distribuzione uniforme nello spazio.

Anche l’approccio basato su SpatialP2P `e stato concepito per il filesharing,

ma `e stato usato per memorizzare informazioni che posseggono una informazione

spaziale. Lo spazio viene diviso in una griglia, ognuna delle quali gestita da un

diverso peer della rete. L’assegnazione delle celle `e definita attraverso una metrica

di distanza.

Infine MOPAR `e utilizzato per i DVE e consente di memorizzare entit`a che

posseggono informazioni spaziali e che si muovono nello spazio. Lo spazio logico `

e diviso in un insieme di celle di forma esagonale gestite da un insieme di peer detti Home Node. In MOPAR le celle vengono distribuite casualmente tra i peer, attraverso una funzione hash.

(34)

(35)

Capitolo 3

PAM:Architettura generale

Verr`a ora presentata in dettaglio la struttura della PAM, la DHT spaziale ideata

per la gestione degli ambienti virtuali distribuiti. In particolar modo verr`a spiegato

il contesto in cui si colloca la PAM. In seguito verr`a motivata la scelta di usare

la struttura base di CAN per la realizzazione della PAM. Quindi verr`a mostrata

l’architettura base dell’overlay, il suo funzionamento e gli algoritmi usati. Infine

verr`a mostrato un algoritmo in grado di bilanciare il carico della rete progettata.

Nei seguenti capitolo non verranno descritti in dettaglio gli algoritmi di CAN, in

quanto tale sistema `e stato illustrato approfonditamente nella sezione 2.3.1.

3.1 Architettura generale del sistema

Le archittetture DVE devono supportare un numero di funzionalit`a i cui

requi-siti sono spesso in contrasto l’uno con l’altro. Per rendere il sistema scalabile occorrono meccanismi di gestione delle aree di interesse e di bilanciamento del carico.

In [9] `e stata pensata una possibile soluzione architetturale in cui dividere due

aspetti fondamentali di applicazioni DVE: la gestione dello stato e la gestione

della posizione delle entit`a presenti in un DVE.

SAM (State Action Manager) e PAM (Posional Action Manager) sono due componenti separate che gestiscono rispettivamente lo stato e la posizione delle

(36)

36 PAM:Architettura generale

Figura 3.1: Visione dell’architettura proposta da parte di un client.

che fanno uso di DHT, in cui ogni server gestisce una parte delle entit`a presenti

nel mondo virtuale.

Dalla prospettiva di un client entrambe le componenti potrebbero essere usate per realizzare un DVE, le cui iterazioni sono visualizzate in figura 3.1.

Ogni volta che un avatar si muove aggiorna la propria posizione in PAM

(move-ments) e deve venire a conoscienza delle entit`a presenti all’interno della sua AoI.

PAM invia periodicamente ad ogni client connesso le entit`a presenti nelle

rispet-tive AoI (position update). Il client per ricevere gli aggiornamenti di stato per le

entit`a presenti nella propria AoI, si sottoscrive a SAM specificando le entit`a per le

quali vuole ricevere gli aggiornamenti di stato (subscribe). Quando il client esegue

delle azioni le comunica a SAM che si occupa di modificare lo stato delle entit`a

coinvolte nelle azioni (state modification). Infine SAM invia periodicamente al

client gli aggiornamenti sullo stato delle entit`a per le quali si `e sottoscritto (state

update).

In questa tesi `e stata progettata un overlay per PAM che `e stata progettata

attraverso un DHT spaziale che localizza le entit`a presenti nell’AoI di un client e

aggiorna le loro posizioni in seguito al loro movimento. Essa prevede per ciascun server la gestione di una porzione dello spazio logico e la memorizzazione delle

entit`a in essa presenti. I client aggiornano periodicamente la loro posizione nella

DHT, al loro volta ogni server calcola periodicamamente le entit`a presenti nell’AoI

(37)

3.2 CAN per DVE: Analisi dei problemi 37

3.2 CAN per DVE: Analisi dei problemi

Per la realizzazione della PAM si `e deciso di adattare la rete CAN per applicazioni

di tipo DVE, considerando come spazio di gioco uno spazio logico bidimensionale

e applicandovi poi tecniche di bilanciamento del carico. `E stata presa in

consid-erazione questo tipo di DHT perch`e consente di posizionare entit`a in uno spazio

d-dimensionali, nel nostro caso bidimensionale (d = 2), ed utilizza algoritmi di

routing basati sulla localit`a spaziale tra punti di uno spazio euclideo. Inoltre la

struttura delle tabelle di routing basate sull’adiacenza di zone la rendono adatta alla la risoluzione di range query tipiche in un ambiente DVE, utilizzate per il

reperimento di tutte le entit`a nella AoI di un giocatore.

Nonostante ci`o sono state apportate alcune modifiche per rendere la DHT

adatta a questi tipi di applicazioni, le cui caratteristiche sono diverse rispetto alle applicazioni sviluppate per il file sharing. Una prima differenza sta nel fatto che

in un DVE le entit`a si muovono nello spazio e la componente spaziale ha un ruolo

fondamentale, mentre in CAN le entit`a mappate sulla DHT hanno una posizione

fissa creata al solo scopo di distribuirle uniformemente nello spazio logico (figura

3.2(a)). Non essendoci correlazione tra la posizione delle entit`a mappate sulla

DHT e l’informazione contenuta dall’entit`a, `e impossibile realizzare nella versione

originale di CAN query complesse come le range query o query a multi attributo. Consideriamo ad esempio una applicazione per il file sharing e supponiamo si voglia memorizzare un nuovo file nella DHT. Il peer che vuole inserire il dato

esegue un’operazione di put nella rete in cui specifica la posizione su cui `e stato

mappato il dato applicando un funzione hash alla sua chiave ed estraendone le

rispettive coordinate. Ci`o equivale a posizionare il file in un punto casuale nello

spazio logico. Il file viene quindi assegnato al peer che gestisce quella porzione

di spazio. La stessa funzione hash applicata sull’indirizzo IP del peer `e usata

per generare il punto in cui posizionarlo e permette di partizionare in maniera uniforme lo spazio disponibile consentendo quindi un bilanciamento del carico tra i peer della rete.

In un DVE invece le entit`a posseggono una posizione dinamica all’interno del

DVE che rappresenta l’informazione base per le query. Se si vuole usare CAN

(38)

(a) CAN (b) PAM

Figura 3.2: Distribuzione delle entit`a nello spazio.

necessario quindi che vi sia una corrispondenza tra lo spazio del DVE e lo spazio della DHT. Chiaramente in questo modo l’attribuzione delle zone ai peer avviene

mediante l’applicazione della funzione hash, mentre il mapping delle entit`a sui

peer `e determinato dalla posizione del giocatore e non utilizza l’hashing. Come

conseguenza, anche se si mantiene una partizione dello spazio disponibile uniforme

tra i peer della rete, la distribuzione delle entit`a nello spazio non `e detto che lo

sia, in quanto dipende dalla posizione delle entit`a stesse.

Il problema degli hotspot, caratteristico nei DVE, pu`o provocare un alto

gra-do di sbilanciamento del carico tra i peer (figura 3.2(b)) e comporta quindi la definizione di ulteriori tecniche per il bilanciamento del carico. Il peer che contiene

un hotspot infatti non solo deve memorizzare una grande quantit`a d’informazione,

ma deve gestire anche tutte le query inviate dagli avatar che gestisce.

La struttura di PAM (Positional Action Manager) descritta nella sezione

suc-cessiva `e stata progettata quindi con l’obiettivo di adattare l’idea di base di CAN

agli ambienti virtuali distribuiti.

PAM si differenzia da CAN in quanto deve gestire il movimento di entit`a nello

spazio di gioco e deve fornire algoritmi per il bilanciamento del carico.

(39)

3.2 CAN per DVE: Analisi dei problemi 39

diversi picchi del carico nell’arco della giornata [24]. Per garantire maggiore

elas-ticit`a nel considerare il numero di risorse da usare e quindi risolvere i problemi

di sovraccarico, `e possibile considerare in PAM ogni nodo della DHT come una

risorsa cloud e definire di conseguenza algoritmi di bilanciamento del carico per il privisioning di tali risorse.

La presenza di algoritmi di bilanciamento del carico hanno quindi comportato il cambiamento della struttura originale di CAN consentendo per ciascun nodo la

gestione di pi`u zone. L’operazione di split viene quindi sfruttata per dividere il

carico presente in una zona e affidarla ad altri servernode della rete.

La figura 3.3 mostra un esempio in cui il nodo S1 possiede una zona contenente

un hotspot che pu`o renderlo sovraccarico. Dividendo la zona attraverso un

oper-azione di split e affidandone una parte ad un altro nodo meno carico, per esempio

S2, si consente di diminuire il carico di S1.

(a) Una zona sovraccari-ca del peer S1.

(b) Divisione della zona sovraccarica tra i peer S1

e S2.

Figura 3.3: Bilanciamento basato sulla divisione delle zone tra i peer della rete.

Nei capitoli seguenti verr`a indicato un peer di PAM con il nome servernode

e le entit`a presenti nell’AoI con il termine vista. L’alterego del giocatore verr`a

indicato come avatar e con clientnode il nodo della rete PAM a cui `e associato in

(40)

3.3 Positional Action Manager

PAM `e un supporto per DVE il cui spazio logico equivale ad uno spazio logico

N × N partizionato in zone rettangolari e che per semplicit`a `e stato considerato

non toroidale ed equivalente allo spazio virtuale del DVE. Ogni zona viene gestita

da un servernode della rete, e ogni servernode pu`o prendere in gestione pi`u zone.

In figura 3.6(b) `e mostrato un esempio in cui il server S2 prende in gestione pi`u

zone. Una zona ha coordinate spaziali della forma [x1, x2], [y1, y2] (figura 3.4), un

id che la identifica univocamente, e una dimensione minima tale che:

x2− x1 ≥ 2r ∧ y2− y1 ≥ 2r

dove r `e il raggio dell’AoI dell’avatar (figura 3.4). In pratica quest’ultima

con-dizione indica che una zona non può essere più piccola dell’AoI di un giocatore ed è

necessaria per agevolare le operazioni per la risoluzione di range query. Infatti, se

si ammettesse la possibilit`a di avere zone pi`u piccole della AoI, la risoluzione delle

range query potrebbe coinvolgere un alto numero di servernode e ci`o potrebbe

richiedere un alto numero di richieste e un alto consumo di banda.

Figura 3.4: Dimensione minima di una zona.

La risoluzione delle range query avviene controllando quali zone l’AoI dell’a-vatar interseca. A questo proposito, occorre fare alcune considerazioni sulla scelta di mantenere la dimensione delle zone maggiore di quella dell’AoI. In figura 3.5 viene mostrato il numero di zone intersecate dall’AoI a seconda della dimensione

(41)

3.3 Positional Action Manager 41

delle zone considerate. Se per esempio si consente di avere zone aventi lati di

di-mensione inferiore al raggio dell’AoI si avr`a un elevato numero di zone intersecate,

come mostrato in 3.5(a) dove il numero di zone intersecate `e pari a sedici. Se si

suppone ognuna di queste gestita da un server diverso, il numero di messaggi in-viati per risolvere una range query risulterebbe pari al numero di zone intersecate.

Infatti la zona che possiede l’avatar non avr`a modo di conoscere tutte le possibili

zone intersecate, che potrebbero essere invece conosciute dal proprio vicinato che

propagherebbe la query verso le zone pi`u esterne che intersecano l’AoI.

Per diminuire il traffico generato per la risoluzione delle range query, si `e

posto un limite all dimensione della zona. La figura 3.5(b) mostra un esempio in cui ogni lato della zona ha una dimensione maggiore al raggio dell’AoI. Tale limite permette ad ogni zona di avere come vicini tutte le zone che possono essere

intersecate dall’AoI. Il numero minimo di zone intersecate `e tuttavia raggiunto

ponendo ogni lato della zona maggiore del diametro dell’AoI, in cui il numero massimo di zone intersecate risulta essere quattro.

(a) x2− x1≤ r ∨ y2− y1≤ r (b) x2− x1≥ r ∧ y2− y1≥ r

Figura 3.5: Zone intersecate dall’AoI di raggio r.

L’AoI (o Area di Interesse) di un avatar, in un DVE, `e l’area di gioco visibile

dall’avatar la cui forma risulta in genere circolare. In PAM si `e ipotizzata come

(42)

uguale per ciascun avatar. Quando un avatar si muove invia periodicamente delle

query al servernode a cui `e regitrato per venire a conoscenza della propria vista.

Le entit`a memorizzate all’interno della rete possono essere di due tipi:

• oggetti : sono entit`a aventi uno stato ed una posizione fissa o poco dinamica

e che nel DVE rappresentano oggetti con cui i giocatori interagiscono; • avatar : sono gli alterego dei giocatori che si muovono nella mappa di gioco

interagendo con tutto ci`o che `e presente nella sua vista.

Quindi sia oggetti che avatar posseggono una posizione nel mondo virtuale, che nel caso di PAM equivale alla posizione logica della DHT. Lo spazio viene cos`ı diviso per distribuire l’informazione da memorizzare tra i peer per cercare di bilanciare il carico in essi presente. Infatti, supponendo una distribuzione uniforme

delle entit`a nello spazio, un peer che posside zone molto grandi potrebbe dividerle

e cederle ad un peer meno carico.

Il servernode della rete pu`o essere un peer o un nodo cloud il cui compito

`e quello di memorizzare tutte le entit`a presenti all’interno delle sue zone. La

possibilit`a di considerare servernode come nodi cloud permetterebbe di sfruttare

tutti i benefici introdotti dal cloud computing come l’elastaticit`a delle risorse, in

questo caso servernode, a seconda dei picchi del carico della rete.

Il criterio con cui lo spazio di gioco viene partizionato `e quello di CAN e

qiesto criterio `e utilizzato per definire algoritmi da eseguire in seguito ad un

bilanciamento del carico.

Le operazioni che PAM eredita da CAN sono: • la join di un peer alla rete;

• la leave di un peer dalla rete;

• la put di oggetti nella DHT. In questo caso si pu`o pensare che tutti gli

oggetti vengano inseriti nella DHT prima dei join dei client e per semplicit`a

si pu`o supporre che la posiione degli oggetti sia statica.

Ulteriori operazioni sono state introdotte per la gestione degli avatar come entit`a

(43)

3.4 Architettura della rete 43

• la registrazione di un avatar alla rete;

• l’aggiornamento della posizione di un avatar in seguito ad un movimento; • risoluzione delle range query per ciascun avatar.

3.4 Architettura della rete

I servernode, che sono i nodi della DHT, hanno il compito di gestire e mantenere tutte le informazioni presenti nelle zone ad essi assegnate. I clientnode, sono i

client dei giocatori che si collegano alla rete e a cui corrisponde un avatar. `E

stato inoltre introdotto in seguito un terzo nodo detto balancingnode allo scopo di bilanciare il carico dei vari servernode, ripartizionando periodicamente lo spazio

di gioco. La struttura della rete `e visulizzata in 3.6(a) dove `e possibile vedere la

distribuzione dei clientnode tra i servernode secondo la partizione in figura 3.6(b)

e la presenza del balancingnode come unit`a centralizzata il cui scopo `e quello

di monitorare la performance di ogni server in modo da ristribuire il carico, il

cui funzionamento verr`a spiegato dettagliatamente in seguito. `E quindi possibile

dividere il sistema in due parti: un lato server, composto da servernode, che si

occupa della gestione della rete e il funzionamento `e in parte basato su CAN,

e un lato client composto da clientnode ciascun dei quali invia periodicamente operazioni di movimento per aggiornare la propria posizione e range query alla

DHT per venire a conoscenza delle entit`a nella propria vista.

3.4.1 Lato Client

Il clientnode rappresenta quindi l’applicazione usata dal giocatore per connettersi alla rete attraverso il suo avatar. Esso ha un id che lo identifica, una posizione che cambia periodicamente in seguito a operazioni di movimento e la vista. Quest’ul-tima varia continuamente in seguito alle operazioni di movimento che coinvolgono tutte gli avatar della rete. Un clientnode deve eseguire tre importanti operazioni:

• registrarsi alla DHT;

(44)

(a) Architettura della rete.

(b) Partizionamento dello spazio e avatar presenti in esso.

(45)

3.4 Architettura della rete 45

• ricevere la vista dal servernode a cui `e registrato.

Per eseguire le operazioni di movimento ogni clientnode deve conoscere il

servern-ode presso cui `e registrato e l’id della zona che lo contiene.

Registrazione

La registrazione viene eseguita quando un clientnode si collega alla rete PAM.

Nell’algoritmo 1 `e mostrata la registrazione di un nodo alla rete. Se si collega

per la prima volta (riga 4), viene contattato un nodo di bootstrap per conoscere il contatto di un servernode presente nella rete, altrimenti si collega all’ultimo servernode a cui si era collegato durante la precedente connessione. Una volta venuto a conoscenza di tale contatto, gli invia una richiesta di connessione. La

richiesta inviata verr`a poi instradata attraverso un algoritmo di routing verso la

zona che contiene la posizione dell’avatar del clientnode. L’algoritmo di routing

usato `e l’algoritmo greedy di CAN, che si basa sulla distanza euclidea tra punti

e zone. Quando la richiesta arriver`a al servernode che possiede la zona a cui il

clientnode appartiene, il servernode invier`a una risposta di avvenuta registrazione

al clientnode che ha richiesto la registrazione. Il messaggio di risposta (riga 14)

conterr`a il contatto del servernode e l’id della zona in cui `e contenuto che il

clientnode memorizzer`a (riga 16).

Movimento

Quando un avatar si muove, cambia anche la sua AoI, la sua vista, e la sua presenza nelle Aoi di altri giocatori. Gli avatar non interagiscono direttamente tra loro, ma attraverso i servernode che li gestiscono, per questo motivo quando un avatar si muove all’interno dell’area di gioco, il suo clientnode deve aggiornare

periodicamente il servernode che gestisce la zona in cui `e posizionato. Se in seguito

al movimento, un avatar passa in una zona che non `e gestita dal suo servernode

attuale, il suo clientnode non riesegue la procedura di bootstrap, ma `e il servernode

attuale che passa la gestione del clientnode al nuovo servernode.

L’algoritmo 2 mostra le azioni intraprese dal clientnode in seguito al movimen-to del suo avatar. Nell’algorimo, il clientnode invia un messaggio al servernode

(46)

Algorithm 1: register

input : begin

1

myposition = getP osition();

2

if prima connessione then

4 4 servercontact = bootstrap.getServerContact(); 5 end 6 else 7 servercontact = getServerContact(); 8 end 9

msg = createF indM sg(mycontact, myposition);

10

send msg to servercontact;

11

// routing greedy in PAM

12

(newservernode, newzone) = receiveM sg();

14 14 register(newservernode, newzone); 16 16 end 17

posizionato per identificarla tra quelle gestite dal servernode. Il servernode si oc-cupa di gestire aggiornamento la posizione dell’avatar del clientnode in PAM. Se il clientnode riceve un messaggio di registrazione da parte di un servernode (riga 10), allora si occupa di registrare il nuovo servernode che lo gestisce e la nuova

zona in cui `e posizionato.

Aggiornamento della vista

L’aggiornamento della vista di un clientnode avviene in seguito all’operazione di movimento ed implica la risoluzione di una range query da parte del servernode che lo gestisce. Infatti ogni volta che un avatar cambia posizione, cambia la sua AoI e quindi la sua vista. Il servernode deve risolvere periodicamente le range

query di tutti gli avatar che gestisce, ed inviare i risultati. Un clientnode pu`o

ricevere pi`u messaggi provenienti da pi`u servernode diversi, in seguito ad una

risoluzione di una range query avente un AoI che interseca zone gestite da diversi servernode (figura 3.7).

L’algoritmo 3 mostra l’aggiornamento di una vista del clientnode. Nella riga 3 il clientnode riceve la vista da tutti i servernode che posseggono zone che

(47)

in-3.4 Architettura della rete 47

Algorithm 2: move

input : begin

1

myposition = getP osition();

2

mycontact = getContact();

3

(servernode, zone) = getServerN odeZone();

4

msg = createM oveM sg(mycontact, myposition, zone);