Latency reduction by dynamic core selection and partial migration of game state

ABSTRACT

Massively multi-player online games (MMOGs) require low latency while supporting a large number of concurrent players, often sharing one worldwide instance of the game. As these are conflicting requirements, a common way of distributing load is by dividing the virtual environment into virtual regions. As MMOGs are world-spanning games, it is plausible to disperse these regions on geographically distributed servers. As such, we propose the use of core selection for finding an optimal server for placing a region, and support for migrating the game state to that server. The first goal relies on a set of servers and measurement of the interacting players latencies. In locating an optimal server, we anticipate a decrease in the overall latency for the majority of players. This reduction occurs by migrating the region to a server closer in proximity to the majority of players in that virtual region, thereby lowering the response time of any interaction.

References

1. Armitage, G. Optimising online fps game server discovery through clustering servers by origin autonomous system. In International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV) (May 2008).
2. Balan, R. K., Ebling, M., Castro, P., and Misra, A. Matrix: Adaptive middleware for distributed multiplayer games. In Middleware (2005), G. Alonso, Ed., vol. 3790 of Lecture Notes in Computer Science, Springer, pp. 390--400.
3. Beigbeder, T., Coughlan, R., Lusher, C., Plunkett, J., Agu, E., and Claypool, M. The effects of loss and latency on user performance in unreal tournament 2003. In the Proceedings of NetGames'04, Portland, Oregon, USA (August 2004), 144--151.
4. Beskow, P., Halvorsen, P., and Griwodz, C. Latency reduction in massively multi-player online games by partial migration of game state. Second International Conference on Internet Technologies and Applications, Wrexham, Wales (September 2007), 153--163.
5. Brookes, B. The derivation and application of the Bradford-Zipf distribution. Journal of Documentation 24, 4 (1968), 247--265.
6. C. Chambers, W. Feng, S. S., and Saha, D. Measurement-based characterization of a collection of on-line games. In the Proceedings of the 5th ACM SIGCOMM Workshop on Internet measurement, Berkeley, CA, USA (October 2005), 1--14.
7. C. Chambers, W. Feng, W. F., and Saha, D. A geographic redirection service for on-line games. In Proceedings of the eleventh ACM international conference on Multimedia, Berkeley, CA, USA (November 2003), 227--230.
8. Claypool, M. The effect of latency on user performance in real-time strategy games. Elsevier Computer Networks 49, 1 (Sept. 2005), 52--70.
9. Claypool, M. Network characteristics for server selection in online games. In Proceedings of the fifteenth Annual Multimedia Computing and Networking (MMCN'08), San Jose, CA, USA 6818 (January 2008), 681808.
10. Claypool, M., and Claypool, K. Latency and player actions in online games. Communications of the ACM 49, 11 (Nov. 2005), 40--45.
11. De Vleeschauwer, B., Van Den Bossche, B., Verdickt, T., De Turck, F., Dhoedt, B., and Demeester, P. Dynamic microcell assignment for massively multiplayer online gaming. In the Proceedings of NetGames' 05, Hawthorne, NY, USA (Oct. 2005), 1--7.
12. Dick, M., Wellnitz, O., and Wolf, L. Analysis of factors affecting players' performance and perception in multiplayer games. In the Proceedings of NetGames'05, Hawthorne, NY, USA (October 2005), 1--7.
13. Duong, T., and Zhou, S. A dynamic load sharing algorithm for massively multiplayer online games. In the Proceedings of ICON'03, Sydney, Australia (October 2003), 131--136.
14. Feng, W., and Feng, W. On the geographic distribution of on-line game servers and players. In the Proceedings of NetGames'03, Redwood City, California, USA (May 2003), 173--179.
15. Funcom. Anarchy Online. http://www.anarchy-online.com/, June (2008).
16. Griwodz, C., and Halvorsen, P. The fun of using TCP for an MMORPG. In International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV) (May 2006), ACM Press, pp. 1--7.
17. Karaman, A., and Hassanein, H. S. Core-selection algorithms in multicast routing - comparative and complexity analysis. Computer Communications 29, 8 (2006), 998--1014.
18. Medina, A., Lakhina, A., Matta, I., and Byers, J. Brite: Universal topology generation from a user's perspective. Tech. Rep. BUCS-TR-2001-003, Computer Science Department, Boston University, Apr. 2001.
19. W. Feng, F. Chang, W. F., and Walpole, J. Provisioning on-line games: a traffic analysis of a busy Counter-strike server. In the Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurement, Marseille, France (November 2002), 151--156.
20. Waxman, B. M. Dynamic Steiner tree problem. SIAM J. Discrete Math. 4 (1991), 364--384.
21. Znati, T. B., and Molka, J. A simulation based analysis of naming schemes for distributed systems. In Proceedings of the 25th Annual Simulation Symposium (Los Alamitos, CA, USA, Apr. 1992), pp. 42--53.