On correctness of scalable multi-server state replication in online games

ABSTRACT

Massively Multiplayer Online Games (MMOG) require novel, scalable network architectures for a high amount of participating players in huge game worlds. Consequently, new and complex multi-server parallelization approaches have been proposed to provide responsive, massively multiplayer gameplay for different game genres. Besides scalability and performance, the issue of correctness of the game state processing is vital for providing a failure-free gameplay as expected by the users. In this paper, we first introduce the concept of correctness for multi-server replication architectures as the ability to preserve the order of user inputs in the virtual processing. We then present two correctness mechanisms optimized for multi-server replication: pessimistic lag and optimistic timewarp. We experimentally show that by implementing the lag mechanism for correctness in our multi-server implementation of the QFusion/Quake2-game the amount of incorrectly ordered actions can be reduced from 50% to 10%.

REFERENCES

• 1: G. Armitage. Sensitivity of Quake3 players to network latency, IMW 2001 poster, 2001.
• 2: Tom Beigbeder , Rory Coughlan , Corey Lusher , John Plunkett , Emmanuel Agu , Mark Claypool, The effects of loss and latency on user performance in unreal tournament 2003®, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016556]
• 3: Y. W. Bernier. Latency compensating methods in client/server in-game protocol design and optimization. In Proceedings of Game Developers Conference'01, 2001.
• 4: A. Bharambe, J. Pang, and S. Seshan. A distributed architecture for multiplayer games. In PACM/USENIX NSDI, San Jose, USA, 2006.
• 5: Thomas A. Funkhouser, RING: a client-server system for multi-user virtual environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.85-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199418]
• 6: B. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peer-to-peer support for massively multiplayer games. In IEEE Infocom, March 2004.
• 7: M. Mauve, J. Vogel, V. Hilt, and W. Effelsberg. Local-lag and timewarp: Providing consistency for replicated continuous applications. IEEE Transactions on Multimedia, 6(1):47--57, February 2004.
• 8: J. Müller, S. Fischer, S. Gorlatch, and M. Mauve. A proxy server-network for real-time computer games. In M. Danelutto, D. Laforenza, and M. Vanneschi, editors, Euro-Par 2004 Parallel Processing, volume 3149 of Lecture Notes in Computer Science, pages 606--613, Pisa, Italy, Aug. 2004. Springer-Verlag.
• 9: Jens Müller , Jan Hendrik Metzen , Alexander Ploss , Maraike Schellmann , Sergei Gorlatch, Rokkatan: scaling an RTS game design to the massively multiplayer realm, Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology, p.125-132, June 15-17, 2005, Valencia, Spain [doi>10.1145/1178477.1178494]
• 10: J. Müller, T. Schröter, S. Fischer, and S. Gorlatch. Porting quake2 onto a scalable multi-server network architecture (in preparation for publication). Technical report, Westfälische Wilherlms-Universität Münster, 2006.
• 11: NCSoft. Tabula rasa <http://www.playtr.com/index.html>.
• 12: Open Source Project. Qfusion engine <http://sourceforge.net/projects/133t/>.
• 13: Nathan Sheldon , Eric Girard , Seth Borg , Mark Claypool , Emmanuel Agu, The effect of latency on user performance in Warcraft III, Proceedings of the 2nd workshop on Network and system support for games, p.3-14, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963901]
• 14: ID Software. Quake 2 <http://www.idsoftware.com/games/quake/quake2/>.
• 15: Sony Online Entertainment. Planetside <http://planetside.station.sony.com/>.
• 16: T. Sweeney. Unreal networking architecture <http://unreal.epicgames.com/network.htm>, July 1999.
• 17: Andrew S. Tanenbaum , Maarten van Steen, Distributed Systems: Principles and Paradigms (2nd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2006
• 18: Webzen. Huxley <http://www.huxleygame.com/>.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server; Distributed applications

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Artificial, augmented, and virtual realities

General Terms:
Design, Performance