Scaling Multiplayer Online Games using Proxy-Server Replication: A Case Study of Quake 2 Jens Müller and Sergei Gorlatch Univ. of Münster, Germany jmueller@uni-muenster.de Tobias Schröter Univ. of Brunswick, Germany Dipl.Inf.T.Schroeter@web.de Stefan Fischer Univ. of Lübeck, Germany fischer@itm.uni-luebeck.de ABSTRACT Massively Multiplayer Online Games (MMOGs) are an increasingly popular class of real-time interactive distributed applications that require scalable architectures and parallelization approaches. While games of the role-playing genre already allow thousands of users to concurrently participate in a single game session, there are important genres, in particular action and strategy games, which have not been scaled to the massively multiplayer realm so far. These games have hard requirements in terms of scalability, in particular regarding density: many players tend to congregate in small locations. In this paper, we outline our novel approach of replication-based parallelisation for scaling the density of players. The practical impact of our work is demonstrated by porting the popular action game QFusion, based on the famous Quake 2, onto our proxy-server system architecture using the replication approach. The experiments with the ported QFusion demonstrate its high responsiveness and show that our approach allows to almost triple the maximum number of simultaneous players on four servers as compared with a single-server version. Categories and Subject Descriptors: H.3.4 [Systems and Software]: Distributed Systems General Terms: Design, Measurement, Performance Keywords: Computer games, proxy-server, replication, scalability proach for scaling the density of virtual world entities in FPS and RTS games using our proxy-server architecture [3]. As the novel contribution, we apply this approach to the open-source FPS game QFusion [6] for demonstrating its practical impact of scaling fast-paced action games. 2. GAME WORLD REPLICATION IN THE PROXY-SERVER ARCHITECTURE Our approach of game world replication aims at scaling the entity density in interactive real-time applications. In this multi-server concept, each server holds a complete copy of the world and all entities of the game, but the responsibility for processing the entities is equally distributed among all participating servers: each server computes the new state only for a particular subset of entities; these are called active entities for this server. The entities being updated at other servers are called shadow entities. Each server regularly, i.e., after each update, sends the new state of its active entities to all other participating servers which then update their shadow copies of these entities. The replicas at the different servers can be viewed as "vertical" layers as illustrated in Figure 1 showing the processing of the virtual environment parallelised on three proxyservers A, B and C. The active entities of a particular server are depicted as filled, while the shadow entities maintained at other servers are outlined. We developed the proxy-server architecture as an operational network architecture for the replication-based parallelisation approach. The servers of this architecture participating in a single session can be placed at multiple sites in the Internet, such that the game clients have to option to choose a particular server offering a good communication quality. This approach decreases the required response time for processing an user input, because servers are "near" to the clients in terms of communication latency. In particular, action inputs from clients which only alter the own entity state (e.g., moving the own avatar) can be directly processed at the server connected to, because this server holds the write-enabled, active entity copy. The only inputs that have to remotely processed by all servers are interaction inputs which may change the state of remotely maintained entities: in games, such interactions for example are shooting or healing each other, i.e., changing the amount of health points. The active/shadow entity mechanism implements a primary copy synchronization approach [8] and guarantees eventual consistency [7] of the replicated game state. In general, there is a trade-off between the responsiveness of the distributed state processing and the degree of consistency. We chose to implement eventual consistency because it enables high responsiveness of the game state processing (no communication for entity locking is required) with a reasonable degree of consistency. 1. INTRODUCTION In the broad area of Distributed Virtual Environments (DVE), online games have become a major and highly popular application class operated over the Internet. These applications are distributed and highly responsive: they are required to react in real-time to frequent inputs from remote users. Currently, Massively Multiplayer Online Role-Playing Games (MMORPG) can support a high amount of users (up to thousands) using the zoning parallelisation approach, which subdivides the large virtual environment in independent zones for concurrent processing on several servers. In contrast, First Person Shooter (FPS) and Real-Time Strategy (RTS) games usually take place in a much smaller game world and have not been successfully scaled to massively multiplayer sessions yet, because the zoning approach is not suitable for them. These games require a parallelisation approach which scales the density of players in a small environment: in action games, users tend to go where the action is and therefore cluster themselves in small locations. This paper summarizes our replication-based parallelization apCopyright is held by the author/owner(s). HPDC'07, June 25­29, 2007, Monterey, California, USA. ACM 978-1-59593-673-8/07/0006. 219 shadow entity active entity replicated game world A inter-proxy synchronization A qfusion proxy- server B C send user actions inter-proxy synchronization C qfusion proxy- server B [..] receive game- state updates [..] game client game client game client [..] game client game client game client Figure 1: Ported QFusion-Proxy Architecture: Processing Parallelised at Several Proxy-Servers 3. QFUSION-PROXY ARCHITECTURE We ported QFusion [6], a fast-paced FPS game whose internal engine bases on the popular game Quake 2, onto the proxy-server architecture in order to test our replication-based parallelisation approach for scaling the maximum number and density of players. The resulting QFusion Proxy-Architecture (QPA) is a demanding case study on how the eventual consistency synchronization affects the game's responsiveness and whether a very fast-paced shooter game is not delayed by the inter-proxy synchronization communication. We conducted a variety of responsiveness and scalability tests briefly described in the following, a comprehensive analysis of these experiments and a detailed description of the implementation can be found in [5]. Responsiveness Test: For testing functionality, we set up a distributed session with two QFusion proxy-servers located in Muenster and Luebeck at the distance of ca. 500 km. At each of the two sites, several clients are connected to the server near to them in terms of communication latency. The proxy-servers fully replicated the game state and synchronized their entities according to our active/shadow approach over a public Internet connection with an inter-proxy latency of about 15-20 ms. The distributed play test ran without noticeable delay of interactions between users at different sites. Avatar movements were processed in a highly responsive manner due to the low communication latency of clients to the local proxies. Scalability Test: For testing the maximum number of simultaneous players, we used an autonomous non-graphical bot client of which we started several instances on each client host. The bot client generates inputs at a high rate by continuously moving around and firing weapons, i.e. we tested the worst case: at each tick actions of all users are processed. Due to the high number of required hosts for the clients, coordinating and running the tests was quite complex and took dozens of hours. For easier management, we ran the scalability test for different numbers of proxies in a single LAN environment in Muenster. Using up to 20 hosts at our department for servers and clients, we were able to test sessions with up to four participating proxies. The server machines in the tests were singleCPU Pentium 4, 1.7 GHz hosts. For each setup, we continuously added clients to the session until the servers became congested, i.e., were not able anymore to finish the complete tick calculation in the time of 100 ms given by the QFusion standard tickrate. The maximum number of players before the servers saturated is presented in Table 1, demonstrating a scalable behaviour for up to four servers. The experiments were run on a small quadratic map Table 1: Max. Number of Players for Incr. Number of Servers Number of Servers 1 2 3 4 Max. Number of Players 32 50 69 80 without any additional separating walls, testing the actual scalability of player density. In the single-server setup of QPA, up to 32 users were able to participate in an uncongested session. Using four servers, the parallelized QPA version allows to almost triple the maximum number of participating users to up to 80 players. In comparison, the original, highly optimized sequential QFusionengine on the same server host is able to support 38 users, i.e. the overhead of the additional proxy-related processing is about 19 %. 4. CONCLUSION The presented port of the QFusion-engine demonstrates that our replication approach on top of the proxy-server architecture is a feasible method to scale the overall number of players as well as their density. While the zoning approach as discussed in [1, 2] targets MMORPGs and scales the total number of players in large game environments, it is not suitable to scale the density of players in a small environment which is critically important for fast-paced action games. The presented parallelisation was already successfully used for scaling the strategy game Rokkatan [4] and the QPA demonstrates that our approach also allows to increase the player number at a reasonable cost in a fast-paced action game. 5. REFERENCES [1] W. Cai, P. Xavier, S. J. Turner, and B.-S. Lee. A scalable architecture for supporting interactive games on the internet. In Proc. of the 16th Workshop on Par. and Dist. Sim., Washington, D.C., May 2002. IEEE. [2] B. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peer-to-peer support for massively multiplayer games. In IEEE Infocom 2004, Hong Kong, China, March 2004. [3] J. Muller, S. Fischer, S. Gorlatch, and M. Mauve. A proxy server-network for ¨ real-time computer games. In Euro-Par 2004 Parallel Processing, LNCS 3149, Pisa, Italy, Aug. 2004. Springer-Verlag. [4] J. Muller and S. Gorlatch. Rokkatan: scaling an RTS game design to the ¨ massively multiplayer realm. ACM Computers in Entertainment, 4(3):11, 2006. [5] J. Muller, S. Gorlatch, T. Schroter, and S. Fischer. Entity density scalability of ¨ ¨ multiplayer online games via replication-based parallelisation: A case study of Quake 2. Technical report, Westfalische Wilhelms-Universitat Munster, 2007. ¨ ¨ ¨ [6] QFusion engine . [7] A. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, 2002. [8] M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso. Understanding replication in databases and distributed systems. In ICDCS, 2000. 220