Luis Diego Briceño
ABSTRACT
The environment considered in this research is a massive multiplayer online gaming (MMOG) environment. Each user controls an avatar (an image that represents and is manipulated by a user) in a virtual world and interacts with other users. An important aspect of MMOG is maintaining a fair environment among users (i.e., not give an unfair advantage to users with faster connections or more powerful computers). The experience (either positive or negative) the user has with the MMOG environment is dependent on how quickly the game world responds to the user's actions. This study focuses on scaling the system based on demand, while maintaining an environment that guarantees fairness. Consider an environment where there is a main server (MS) that controls the state of the virtual world. If the performance falls below acceptable standards, the MS can off-load calculations to secondary servers (SSs). An SS is a user's computer that is converted into a server. Four heuristics are proposed for determining the number of SSs, which users are converted to SSs, and how users are assigned to the SSs and the MS. The goal of the heuristics is to provide a "fair" environment for all the users, and to be "robust" against the uncertainty of the number of new players that may join a given system configuration. The heuristics are evaluated and compared by simulation.
- S. Ali, T. D. Braun, H. J. Siegel, A. A. Maciejewski, N. Beck, L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, and B. Yao. Characterizing resource allocation heuristics for heterogeneous computing systems. In Advances in Computers Volume 63: Parallel, Distributed, and Pervasive Computing, pages 91--128, 2005.Google Scholar
- S. Ali, A. A. Maciejewski, H. J. Siegel, and J.-K. Kim. Measuring the robustness of a resource allocation. IEEE Transactions on Parallel and Distributed Systems, 15(7):630--641, July 2004. Google ScholarDigital Library
- G. J. Armitage. An experimental estimation of latency sensitivity in multiplayer Quake 3. In 11th IEEE International Conference on Networks (ICON '03), pages 137--141, Sept. 2003.Google ScholarCross Ref
- L. Barbulescu, L. D. Whitley, and A. E. Howe. Leap before you look: An effective strategy in an oversubscribed scheduling problem. In 19th National Conference on Artificial Intelligence, pages 143--148, July 2004. Google ScholarDigital Library
- N. E. Baughman and B. N. Levine. Cheat-proof playout for centralized and distributed online games. In IEEE Conference on Computer Communications (INFOCOM '01), pages 104--113, Mar. 2001.Google ScholarCross Ref
- A. Bharambe, J. Pang, and S. Seshan. Colyseus: A distributed architecture for online multiplayer games. In 3rd Symposium on Networked Systems Design and Implementation, pages 155--168, 2006. Google ScholarDigital Library
- T. D. Braun, H. J. Siegel, N. Beck, L. Boloni, R. F. Freund, D. Hensgen, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, and B. Yao. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810--837, June 2001. Google ScholarDigital Library
- L. D. Briceño, M. Oltikar, H. J. Siegel, and A. A. Maciejewski. Study of an iterative technique to minimize completion times on non-makespan machines. In International Heterogeneity in Computing Workshop (HCW '07), page 138, Mar. 2007.Google ScholarCross Ref
- L. D. Briceño, H. J. Siegel, A. A. Maciejewski, Y. Hong, B. Lock, M. N. Teli, F. Wedyan, C. Panaccione, and C. Zhang. Resource allocation in a client/server hybrid network for virtual world environments. In International Heterogeneity in Computing Workshop (HCW '08), 2008.Google ScholarCross Ref
- E. Cronin, A. R. Kurc, B. Filstrup, and S. Jamin. An efficient synchronization mechanism for mirrored game architectures. Multimedia Tools Applications, 23(1):7--30, 2004. Google ScholarDigital Library
- G. Deen, M. Hammer, J. Bethencourt, I. Eiron, J. Thomas, and J. H. Kaufman. Running Quake II on a grid. IBM Systems Journal, 45(1):21--44, 2006. Google ScholarDigital Library
- Q. Ding and G. Chen. A benefit function mapping heuristic for a class of meta-tasks in grid environments. In 1st International Symposium on Cluster Computing and the Grid (CCGRID '01), page 654, May 2001. Google ScholarDigital Library
- S. Ghanbari and M. R. Meybodi. On-line mapping algorithms in highly heterogeneous computational grids: A learning automata approach. In International Conference on Information and Knowledge Technology (IKT '05), May 2005.Google Scholar
- F. Glover. Tabu search --- Part I. ORSA Journal on Computing, 1(3):190--206, 1989.Google ScholarCross Ref
- A. Hertz and D. de Werra. The tabu search metaheurstic: How we used it. Annals of Mathematics and Artificial Intelligence, 1(1--4):111--121, Sept. 1990.Google ScholarDigital Library
- O. H. Ibarra and C. E. Kim. Heuristic algorithms for scheduling independent tasks on non-identical processors. Journal of the ACM, 24(2):280--289, Apr. 1977. Google ScholarDigital Library
- T. Iimura, H. Hazeyama, and Y. Kadobayashi. Zoned federation of game servers: a peer-to-peer approach to scalable multi-player online games. In 3rd ACM SIGCOMM workshop on Network and System Support for Games, pages 116--120, Aug. 2004. Google ScholarDigital Library
- J. Jardine and D. Zappala. A hybrid architecture for massively multiplayer online games. In Seventh Workshop on Network and Systems Support for Games (NetGames '08), 2008. Google ScholarDigital Library
- Z. Jinquan, N. Lina, and J. Changjun. A heuristic scheduling strategy for independent tasks on grid. In Eighth International Conference on High-Performance Computing in Asia-Pacific Region '05, page 6, Nov. 2005. Google ScholarDigital Library
- K. Kaya, B. Ucar, and C. Aykanat. Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories. Journal of Parallel and Distributed Computing, 67(3):271--285, Mar. 2007. Google ScholarDigital Library
- J. Kennedy and R. Eberhart. Particle swarm optimization. In IEEE International Conference on Neural Networks, pages 1942--1948, Nov. 1995.Google ScholarCross Ref
- J.-K. Kim, H. J. Siegel, A. A. Maciejewski, and R. Eigenmann. Dynamic mapping in energy constrained heterogeneous computing systems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS '05), Apr. 2005. Google ScholarDigital Library
- B. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peer-to-peer support for massively multiplayer games. In IEEE Conference on Computer Communications (INFOCOM '04), pages 96--107, Mar. 2004.Google ScholarCross Ref
- K.-W. Lee, B.-J. Ko, and S. Calo. Adaptive server selection for large scale interactive online games. Computer Networks, 49(1):84--102, Sept. 2005. Google ScholarDigital Library
- J. Pugh and A. Martinoli. Discrete multi-valued particle swarm optimization. In IEEE Swarm Intelligence Symposium '06, pages 103--110, May 2006.Google Scholar
- A. Shaikh, S. Sahu, M.-C. Rosu, M. Shea, and D. Saha. On demand platform for online games. IBM Systems Journal, 45(1):7--20, 2006. Google ScholarDigital Library
- V. Shestak, E. K. P. Chong, H. J. Siegel, A. A. Maciejewski, L. Benmohamed, I.-J. Wang, and R. Daley. A hybrid branch-and-bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 28(3):1157--1173, 2008. Google ScholarDigital Library
- D. Whitley. The GENITOR algorithm and selective pressure: Why rank based allocation of reproductive trials is best. In 3rd International Conference on Genetic Algorithms, pages 116--121, June 1989. Google ScholarDigital Library
- M. Wu and W. Shu. Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. In 9th IEEE Heterogeneous Computing Workshop (HCW '00), pages 375--385, Mar. 2000. Google ScholarDigital Library
Recommendations
A peer-to-peer architecture for massive multiplayer online games
NetGames '06: Proceedings of 5th ACM SIGCOMM workshop on Network and system support for gamesMassive Multiplayer Online Games with their virtual gaming worlds grow in user numbers as well as in the size of the virtual worlds. With this growth comes a significant increase of the requirements for server hardware. Today an MMOG provider usually ...
Practical Middleware for Massively Multiplayer Online Games
A massively multiplayer online game (MMOG) lets thousands of players interact simultaneously within a virtual world via the Internet. Middleware plays an important role in the development of next-generation MMOGs, which must be built on platforms that ...
Massively multiplayer online games developed with agents
Transactions on Edutainment VIIMassively Multiplayer Online Games (MMOGs) are online videogames played at the same time by a huge number of players experiencing together the same virtual world. MMOGs are an important focus of research, not only because they are economically ...
Comments