Locality aware dynamic load management for massively multiplayer games

ABSTRACT

Most massively multiplayer game servers employ static partitioning of their game world into distinct mini-worlds that are hosted on separate servers. This limits cross-server interactions between players, and exposes the division of the world to players. We have designed and implemented an architecture in which the partitioning of game regions across servers is transparent to players and interactions are not limited to objects in a single region or server. This allows a finer grain partitioning, which combined with a dynamic load management algorithm enables us to better handle transient crowding by adaptively dispersing or aggregating regions from servers in response to quality of service violations.Our load balancing algorithm is aware of the spatial locality in the virtual game world. Based on localized information, the algorithm balances the load and reduces the cross server communication, while avoiding frequent reassignment of regions. Our results show that locality aware load balancing reduces the average user response time by up to a factor of 6 compared to a global algorithm that does not consider spatial locality and by up to a factor of 8 compared to static partitioning.

REFERENCES

• 1: Gagan Aggarwal , Rajeev Motwani , An Zhu, The load rebalancing problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777460]
• 2: Srinivas Aluru , Fatih E. Sevilgen, Parallel Domain Decomposition and Load Balancing Using Space-Filling Curves, Proceedings of the Fourth International Conference on High-Performance Computing, p.230, December 18-21, 1997
• 3: Butterfly.net, Inc. The butterfly grid: A distributed platform for online games, 2003. www.butterfly.net/platform/.
• 4: Guohong Cao, Integrating distributed channel allocation and adaptive handoff management for QoS-sensitive cellular networks, Wireless Networks, v.9 n.2, p.131-142, March 2003 [doi>10.1023/A:1021889515877]
• 5: Jin Chen. Locality aware dynamic load management for massively multiplayer games. Master's thesis, University of Toronto, Jan 2005.
• 6: Prasanna Ganesan, Mayank Bawa, and Hector Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of 30th International Conference on Very Large Data Bases (VLDB), Aug 2004.
• 7: Masato Hori, Takeki Iseri, Kazutoshi Fujikawa, Shinji Shimojo, and Hideo Miyahara. Cittatron: a multiple-server networked game with load adjustment mechanisms on the internet. In SCS Euromedia Conference, pages 253--260, 2001.
• 8: Bjorn Knutsson, Honghui Lu, Wei Xu, and Bryan Hopkins. Peer-to-peer support for massively multiplayer games. In INFOCOM '04, Hong Kong, China, March 2004.
• 9: John C. S. Lui , M. F. Chan, An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.193-211, March 2002 [doi>10.1109/71.993202]
• 10: Mike Mika and Chris Charla. Simple, cheap pathfinding. In Steve Rabin, editor, AI Game Programming Wisdom, pages 155--160. Charles River Media, Inc., 2002.
• 11: Mitch Ferguson and Michael Ballbach. Product review: Massively multiplayer online game middleware, January 2003. http://www.gamasutra.com/features/20030115/ferguson 01.htm.
• 12: Katherine L. Morse. Interest management in large-scale distributed simulations. Technical Report ICS-TR-96-27, University of California, Irvine, 1996.
• 13: NC Soft. Lineage, 2002. http://www.lineage.com/.
• 14: Sony Computer Entertainment Inc. Everquest online adventures, 2002. everquestonlineadventures.station.sony.com/.
• 15: Zona Inc. Terrazona: Zona application frame work white paper, 2002. www.zona.net/whitepaper/Zonawhitepaper.pdf.

INDEX TERMS

Primary Classification:
  D. Software
  D.0 GENERAL

General Terms:
Algorithms, Performance

Keywords:
adaptive, distributed, load balancing, locality aware, massively multiplayer games