Si sono effettuate le simulazioni applicando l’algoritmo di bilanciamento descrit-
to nel capitolo 3. Lo sbilanciamento del carico `e stato misurato attraverso il
coefficiente di Gini.
A differenza del caso precedente la struttura della rete non `e pi`u statica ma
cambia nel tempo, riorganizzandosi in maniera tale da cercare di bilanciare il carico. La simulazione inizia partendo da un unico server che prende come zona
l’intero spazio di gioco, per poi suddividirlo e affidarlo a nuovi server. `E stato
considerato un numero massimo di server che possono entrare nella rete. Una vol- ta raggiunto il numero massimo di server, un processo si suddivisione assegna le zone ai servernode meno carichi. La suddivisione si ferma o quando non esistono servernode sovraccarichi, o quando la dimensione delle zone sovraccariche ha rag- giunto la dimensione minima consentita. Un altro limite alla suddivisione delle
zone `e stato introdotto nell’algoritmo di bilanciamento usato che non consente di
suddividere zone considerate isolate.
Il numero di servernode considerato `e il numero minimo di servernode necessari
per bilanciare teoricamente la rete. Il numero minimo di server da considerare `e
stato calcolato in base ai parametri usati nell’algoritmo del bilanciamento del
carico. Sia bItT ot(m, k) la banda per iterazione inviata nella rete dove m e k sono
rispettivamente il numero di avatar e di oggetti presenti nella rete, e sia bItT hreshold
la soglia per cui un server viene considerato sovraccarico. Il numero minimo di
server da considerare nmin per bilanciare il carico della rete sar`a quindi:
nmin =
bItT ot(m, k)
bItT hreshold
Si ha che bItT ot(1000, 1000) = 16.876 come visualizzato in 5.4, suppenendo
bItT hreshold = 1000 si avr`a che il numero ottimale di server necessari a bilanciare
il carico pari a:
nmin =
16.876
5.4 Valutazioni con bilanciamento 127
La simulazione per l’algoritmo di bilanciamento ha prodotto i risultati visibili in figura 5.8.
La figura mostra la distribuzione della banda tra i servernode della rete nei seguenti casi:
• griglia: servernode che gestiscono una sola zona con partizione a griglia dello spazio;
• custom: servernode che gestiscono una sola zona con una partizione per-
sonalizzata dello spazio in maniera da dividere le zone in cui `e presente un
hotspot;
• balancing: servernode che possono gestire pi`u zone e che applicano l’algo-
ritmo di bilanciamento del carico illustrato nella sezione 3.4.4.
Dal grafico di Gini `e possibile vedere che per i primi due casi la distribuzione
del carico risulta molto sbilanciato con un valore di Gini vicino a 1 (figura 5.8(a)). Utilizzando l’algoritmo di bilanciamento si ottiene una migliore distribuzione del
carico pari circa a 0.5 come `e mostrato dalla figura 5.8(b).
Dividendo le zone pi`u cariche e distribuendole tra i server meno carichi migliora
la distribuzione della banda tra i server della rete diminuendo cos`ı il carico. Uno
scenario della partizione dello spazio applicando l’algoritmo di bilanciamento `e
mostrato in figura 5.9. La figura mostra chiaramente che le aree pi`u cariche
sono quelle ove `e presente un hotspot e in cui si ha una maggiore divisione dello
spazio, che vengono distribuite tra i servernode. Tuttavia il carico della zona di
dimensione minima non pu`o essere ulteriormente diviso e cos`ı il carico in esso
presente.
Facendo variare il numero massimo di servernode disponibili si ottiene il grafi- co 5.10. Tale grafico mostra che in presenza di un minor numero di servernode disponibili il bilanciamento del carico migliora. Tuttavia avere meno servernode disponibili implica anche un aumento del carico in ciascuno di essi. Occorre quin-
di trovare un compromesso tra bilanciamento e quantit`a di banda trasmessa da
128 Risultati sperimentali
(a) 0.996 ≤ G ≤ 1
(b) 0 ≤ G ≤ 1
Figura 5.8: Coefficiente di Gini sulla banda inviata da ciascun server. Simulazione fatta su 1000 avatar, 1000 oggetti e 1000 iterazioni.
5.4 Valutazioni con bilanciamento 129
130 Risultati sperimentali
Figura 5.10: Coefficiente di Gini al variare del numero massimo di servernode disponibili. Simulazione eseguita su 1000 avatar, 1000 oggetti e 1000 iterazioni.
Capitolo 6
Conclusioni
L’obiettivo principale di questa tesi `e stato quello di definire una DHT che consente
di gestire in modo distribuito informazioni relative alle posizioni delle entit`a di un
DVE. La soluzione proposta si basa su una architettura che mantiene separate la
gestione dello stato (SAM) e la gestione delle posizioni (PAM) delle entit`a presenti
in un DVE. L’architettura sviluppata nella tesi `e quella per PAM. Essa `e stata
progettata adattando l’architettura di CAN realizzata per applicazioni di tipo filesharing, ai DVE.
L’architettura proposta differisce da CAN per i seguenti aspetti:
• movimento delle entit`a nello spazio;
• risoluzione di range query;
• gestione di pi`u zone da parte di ogni peer;
• meccanismi di bilanciamento del carico.
Sono state considerate pi`u zone per ogni peer per consentire un miglior dis-
tribuzione dello spazio tra i peer, in maniera tale da bilanciare il carico. ´E stato
proposto un algoritmo di bilanciamento in grado di distribuire il carico dei server
pi`u carichi tra quelli meno carichi.
Le analisi svolte si mostra che la gestione di pi`u zone da parte di ogni server
permette di distribuire meglio il carico tra i server della rete.
Questa architettura pu`o essere estesa in diversi modi. Potrebbero essere im-
132 Conclusioni
consentano una migliore distribuzione del carico della rete. Una meccanismo di bilanciamento possibile potrebbe consentire lo spostamento di zone da un serv- er all’altro a seconda del carico di ciascun server. Un’altra soluzione potrebbe prevedere l’uscita volontaria dei server dalla rete affidando le proprie zone a server meno carichi. In un ambiente cloud based questi algoritmi possono essere utiliz- zati per gestire in maniera dinamica la richiesta di risorse cloud. In quest’ultimo caso negli algoritmi di bilanciamento entrano in gioco anche altri parametri oltre al carico della rete, come per esempio il costo delle risorse cloud.
Bibliografia
[1] World of Warcraft http://eu.battle.net/wow/it/. [2] Second Life http://secondlife.com/.
[3] Guild Wars 2 https://www.guildwars2.com/en/.
[4] PeerfactSim.KOM - A Large Scale Simulation Framework for Peer-to-Peer System http://peerfact.kom.e-technik.tu-darmstadt.de/.
[5] The Annotated Gnutella Protocol Specification v0.4 http://rfc-gnutella. sourceforge.net.
[6] D.T. Ahmed and S. Shirmohammadi. A Microcell Oriented Load Bal-
ancing Model for Collaborative Virtual Environments. In Virtual Envi-
ronments, Human-Computer Interfaces and Measurement Systems, 2008. VECIMS 2008. IEEE Conference on, pages 86–91. IEEE, 2008.
[7] A. Bharambe, J. Pang, and S. Seshan. Colyseus: A Distributed Architec- ture for Online Multiplayer Games. In Proceedings of the 3rd conference on Networked Systems Design & Implementation, volume 3, pages 12–12, 2006. [8] E. Buyukkaya and M. Abdallah. Data Management in Voronoi-based P2P Gaming. In Consumer Communications and Networking Conference, 2008. CCNC 2008. 5th IEEE, pages 1050–1053. IEEE, 2008.
[9] Emanuele Carlini. Combining Peer-to-Peer and Cloud Computing for Large
Scale On-line Games. PhD thesis, IMT Institute for Advanced Studies,
134 BIBLIOGRAFIA
[10] L. Chan, J. Yong, J. Bai, B. Leong, and R. Tan. Hydra: A Massively- Multiplayer Peer-to-Peer Architecture for the Game Developer. In Proceed- ings of the 6th ACM SIGCOMM workshop on Network and system support for games, pages 37–42. ACM, 2007.
[11] E. Cronin, A.R. Kurc, B. Filstrup, and S. Jamin. An Efficient Synchro- nization Mechanism for Mirrored Game Architectures. Multimedia Tools and Applications, 23(1):7–30, 2004.
[12] B. De Vleeschauwer, B. Van Den Bossche, T. Verdickt, F. De Turck, B. Dhoedt, and P. Demeester. Dynamic Microcell Assignment for Massively Multiplayer Online Gaming. In Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, pages 1–7. ACM, 2005.
[13] E. Esen. How to create an Overlay in PeerfactSim.KOM, 2008.
[14] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load Balancing in Dynamic Structured P2P Systems. In INFOCOM 2004. Twenty- third AnnualJoint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2253–2262. IEEE, 2004.
[15] F. Halsall. Data Communications, Computer Networks and OSI. 1989. [16] T. Hampel, T. Bopp, and R. Hinn. A Peer-to-Peer Architecture for Massive
Multiplayer Online Games. In Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, pages 30–31. ACM, 2006.
[17] S.Y. Hu, J.F. Chen, and T.H. Chen. Von: A scalable peer-to-peer network for virtual environments. Network, IEEE, 20(4):22–31, 2006.
[18] A. Kaluszka. Distributed hash tables. 2010.
[19] V. Kantere, S. Skiadopoulos, and T. Sellis. Storing and indexing spatial data in P2P systems. Knowledge and Data Engineering, IEEE Transactions on, 21(2):287–300, 2009.
BIBLIOGRAFIA 135
[20] K. Kim, Y. Ikjun, and LEE Joonwon. Hyms: A hybrid mmog server archi- tecture. IEICE transactions on information and systems, 87(12):2706–2713, 2004.
[21] B. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peer-to-Peer Support for Mas- sively Multiplayer Games. In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, volume 1. IEEE, 2004.
[22] P.J. Lambert and J.R. Aronson. Inequality decomposition analysis and the gini coefficient revisited. The Economic Journal, pages 1221–1227, 1993. [23] S. Legtchenko, S. Monnet, and G. Thomas. Blue banana: resilience to avatar
mobility in distributed mmogs. In Dependable Systems and Networks (DSN), 2010 IEEE/IFIP International Conference on, pages 171–180. IEEE, 2010. [24] M. Marzolla, S. Ferretti, and G. D’Angelo. Dynamic Resource Provisioning
for Cloud-based Gaming Infrastructures. 2010.
[25] P. Maymounkov and D. Mazieres. Kademlia: A Peer-to-Peer Information System Based on the xor Metric. Peer-to-Peer Systems, pages 53–65, 2002. [26] Z. Niu, Y. Wu, J. Gong, and Z. Yang. Cell Zooming for Cost-Efficient Green
Cellular Networks. Communications Magazine, IEEE, 48(11):74–79, 2010. [27] Ratnasamy, S. and Francis, P. and Handley, M. and Karp, R. and Shenker,
S. A Scalable Content-Addressable Network, volume 31. ACM, 2001.
[28] L. Ricci and E. Carlini. Distributed Virtual Environments: From client serv- er to cloud and P2P architectures. In High Performance Computing and Simulation (HPCS), 2012 International Conference on, pages 8–17. IEEE, 2012.
[29] F. Romani and N. Santoro. On hash techniques in a paged environment. Calcolo, 16(3):289–303, 1979.
136 BIBLIOGRAFIA
[30] A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware 2001, pages 329–350. Springer, 2001.
[31] J. Smed, T. Kaukoranta, and H. Hakonen. Aspects of Networking in
Multiplayer Computer Games. Electronic Library, The, 20(2):87–97, 2002. [32] R. Steinmetz and K. Wehrle. Peer-to-Peer Systems and Applications, volume
3485. Springer, 2005.
[33] D. Stingl, J. R¨uckert, L. Nobach, S. Kaune, K. Pussep, H. Nguyen,
and B. Dollak. Documentation for PeerfactSim.KOM. Technical report,
Technische Universit¨at Darmstadt, 2011.
[34] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balakrishnan. Chord:
A Scalable Peer-to-Peer Lookup Service for Internet Applications. ACM
SIGCOMM Computer Communication Review, 31(4):149–160, 2001.
[35] P. Yu. MOPAR: A Mobile Overlay Peer-to-Peer Architecture for Scalable Massively Multiplayer Online Games. PhD thesis, The University of British Columbia, 2006.