| 摘要(英) |
In a networked virtual environment (NVE), users interact with each other in the computer-generated virtual world through networked links. NVEs are widely applied to a variety of areas like military simulation, education, training and network games. The massively multi-player online game (MMOG), which is nowadays a billion-dollar business, is a typical example of NVEs. Millions of users log on game servers, navigate the virtual world, and interact with each other concurrently. A good enough number of servers are provided to ensure so many concurrent users to go smoothly. However, the dynamic actions of users may lead to load unbalance among servers, so some servers may be overwhelmed and the overall system performance is degraded. Therefore how to dynamically adjust server loads with consideration of server capacities to reach load balance becomes an important issue.
A traditional NVE system divides the virtual world into several fixed-sized regions, each of which is statically managed by a server. When users gather around a hotspot, the load of the server managing the region of the hotspot increases sharply. Since the occurrence of some hotspots is transient and unpredictable, it is hard to reach load balance among servers with traditional fixed-region partitioning.
In this thesis, we further divide a region into many hexagonal subregions called “cells” and propose a dynamic load balancing algorithm, namely “Directed Load Diffusion (DLD), to transfer the management responsibilities of boundary cells among servers to reach server load balance. A overloaded server SX computes the local load ratio (LLR) according to loads of neighbor servers (i.e., the servers managing regions adjacent to those managed by SX) to select the neighbor server with the least utilization or maximum available capacity to transfer the load. In this way, every server keeps its load under the safety load threshold ratio (SLT). When all SX’s neighbor server is overloaded, SX will send a Forced Load Balance Request (FLB-Req) to force its neighbors to distribute their loads to their neighbors not adjacent with Sx for possible load transfer. Furthermore, a server tries to keep the property that its associated region consists of continuous cells to reduce avatar migrations and costs of inter-server communications.
We have performed extensive simulation experiments to demonstrate the performance of DLD algorithm and compared the simulation results with those of the related ProGReGA algorithm. As shown in the thesis, DLD can reach relatively good load balance and has lower costs of load transfer and inter-server communications.
|
| 參考文獻 |
[1] B.D. Vleeschauwer, B.V.D. Bossche, T. Verdickt, F.D Turck, B. Dhoedt and P. Demeester , “Dynamic microcell assignment for massively multiplayer online gaming”. Proc of 4th ACM SIGCOMM workshop on Network and system support for games, pp. 1-7, 2005.
[2] B.V.D. Bossche, B.D. Vleeschauwer, T. Verdickt, F.D. Turck, B. Dhoedt, P. Demeester, “Autonomic microcell assignment in massively distributed online virtual environments,” Journal of Network and Computer Applications vol. 32, issue 6, pp. 1242-1256, Nov. 2009.
[3] C.E.B Bazerra and C.F.R. Geyer Multimedia “A load balancing scheme for massively multiplayer online games,” Tools and Applications, vol. 45, no.12, pp. 263-289, Oct. 2009
[4] D.T. Ahmed, S. Shirmohammad and J. Oliveira, “Improving Gaming Experience in Zonal MMOGs,” Proc.15th international conference on Multimedia, pp.51 - 584, 2007.
[5] D.T. Ahmed and S. Shirmohammad, “A microcell oriented load balancing model for collaborative virtual environments,” Proc. IEEE Conference on VirtualEnvironments, Human-Computer Interfaces and Measurement Systems, VECIMS. IEEE, pp. 86-91, 2008.
[6] I. Kazem, D.T. Ahmed and S. Shirmohammadi, “A Zone Based Architecture for Massively Multi-user Simulations,” Proc. Simulaiton Multiconference, vol. 1, pp. 149-156, 2007.
[7] J. Chen, B. Wu, M. Delap, B. Knutsson, H. Lu and C. Amza, “Locality aware dynamic load management for massively multiplayer games,” Proc. tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, PPoP, ACM. pp. 289-300, 2005.
[8] K. Lee and D. Lee, “A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution,” Proc. ACM symposium on Virtual reality software and technology, pp. 160-168, 2003.
[9] J.C.S. Lui and M.F. Chan, “An efficient partitioning algorithm for distributed virtual environment systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, issue 3, pp. 193-211, Mar. 2002.
[10] P. Morillo, J.M. Orduna, M. Fern´andez, and J. Duato. “An adaptive load balancing technique for distributed virtual environment systems,” Proc. Intl. Conf. on Parallel and Distributed Computing and Systems, PDCS, ACTA Press. pp. 256-261, 2003.
[11] S.D. Webb, S. Soh and W. Lau, “Enhanced mirrored servers for network games”. Proc. sixth ACM SIGCOMM workshop on Network and system support for games, pp. 117-122, 2007.
[12] T.N.B. Duong and S. Zhou, “A Dynamic Load Sharing Algorithm for Massively Multiplayer Online Games,” Proc. 11th IEEE International Conference on Networks, ICoN. pp. 131-136.
[13] S-F Wang, Z. Zhou and W. Wu, “A Layered Iterative Load Balancing Algorithm for Distributed Virtual Environment,” Journal of Software, pp. 2471-2482, 2008.
[14] http://bubble.lager.com.tw
[15] http://www.microsoft.com/games/age3
[16] http://www.secondlife.com
[17] http://www.warofwarcraft.com
|
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit