A massively multiplayer online game often deploys dozens or hundreds of servers to support millions of players around the world. A slow response time stemming from an ill-designed network infrastructure could render the game noncompetitive. To establish an efficient infrastructure, the authors focus on selecting host facilities on backbone network nodes, assigning client clusters to these facilities, and determining the required capacity for each host site. An exact solution approach is obtained from solving a minimum cost set-covering problem. The efficiency of the solution approach, in comparison with a greedy heuristic, is also reported.
Massively multiplayer online games (MMOGs) have become one of the most vibrant sectors in the video game industry because of their appeal to the younger generation. MMOGs refer to genres of online role-play videogames in which gamers can freely create or assume a character in a persistent and dynamic virtual community. The global market for these games was estimated to be $6.6 billion in revenue in 2006 and projected to be $14.4 billion in 2012 (PricewaterhouseCoopers, 2008), and a successful game often serves a large group of players with a major economic stake. For example, it was estimated that World of Warcraft, one of the most popular MMOGs, had over ten million users in 2008 with more than 2 million in Europe, 2.5 million in North America, and 5.5 million in Asia (Blizzard, 2008). In order to support millions of players around the world, some MMOG publishers need to create a massive client-server infrastructure with dozens to hundreds of copies of the application deployed globally (Dolbier, 2007).
Some games such as World of Warcraft and Sony Online Entertainment deploy multiple copies of the games in various locations around the world. Others such as EVE Online and Second Life may only use one instance of the game world to support the entire player population. In this paper, we focus on the former configuration. In addition to game contents, the success of a distributed MMOG, hereafter short for MMOG, also hinges on its playability, often measured by server throughput and network response time. Throughput is largely dictated by the capacity of game servers. MMOGs typically employ an n-tiered server architecture, with the front-tier managing security and load balance, the mid-tier handling game simulations, and the database tier keeping track of information about game objects and maneuvers (Dolbier, 2007a, 2007b, 2007c; Van der Steen, 1997). To determine the server capacity for each tier, a game distributor must be able to estimate the number of concurrent players per geography (Dolbier, 2007a). This implies that the service zone of a server must be either known a priori or determined concurrently with server capacities. Network response time, on the other hand, largely depends on the distance between a player and the server (Huffaker, Fomenkov, Plummer, Moore, & laffy, 2002). A slow network response time can adversely affect a player's performance in a game that requires quick reactions to game events (Armitage, 1997). While it is difficult to boost the propagation speed of network signals, an MMOG publisher can strategically locate game servers with adequate service capacity on a network to maintain a certain level of service quality.
To alleviate the last-mile bandwidth constraint, an MMOG server ideally should be hosted within a broadband provider’s facility or in the close proximity (Megler, 2004). Thus, one of MMOG key research questions is how to strategically locate game servers with appropriate capacities on broadband network nodes so that the game distributor’s cost can be minimized while meeting the service quality requirement. In this paper, the problem is formulated as a minimum cost set-covering problem based on an M/M/1 queuing system in each host facility. We believe that we are among the first to study the optimal service design for MMOGs. Although the model and the solution procedure are developed specifically for MMOGs’ service design problem, we expect them to be applicable, with modifications, to many applications with similar structures.
The plan for the paper is as follows. A literature review is provided in the next section. We then develop an exact solution approach for the MMOG deployment problem, which involves solving a minimum cost set-covering problem. Results for computational experiments and sensitivity analyses are presented. Finally, the strengths, the limitations, and future extensions of this study are discussed.