Year

2012

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

The passed decade has seen the tremendous development and growth of online games. Among those, Massively Multiplayer Online Role Playing Games (MMORPGs) are arguably the most resource-intensive, in which thousands of players may play concurrently in a common virtual world. As a result, the current pre-dominant Central Server model may require tremendous resources to support scalable MMORPGs, and cause a potential bottleneck in terms of resource provision. In this dissertation, we conduct a feasibility study of using Peer-to-peer (P2P) architecture to support MMORPGs. In a P2P system, since participating users (peers) contribute computing and network resources for the application, the application could ideally achieve an organic growth by expanding arbitrarily without the requirement of a “forklift upgrade” to the existing infrastructure, hence addressing the scalability bottleneck faced by the Central Server model.

We begin our study with a literature review on issues and techniques for supporting online games. Latency and scalability are the two primary aspects the review is based on. Network latency heavily influences the design of online games with respect to the nature of interactivities involved in the games, and hence remains a critical metric for any technique or network design aiming to support online games. To address the bottleneck faced by Central Server model with respect to resource provision, we reviewed several scalable architectural designs, ranging from Distributed Server Architecture to Peer-to-Peer Architecture. When reviewing Peer-to-Peer Architecture, we focus on the evolution from Unstructured Peer-to-Peer Design to Structured Peer-to- Peer Design, aiming to reveal the characteristics of Structured Peer-to-Peer Network and its potential for dynamic applications such as online games.

Enlightened by the literature review, we then present a distributed game design that marries MMORPG with Pastry, a structured peer-to-peer overlay. In order to closely reflect an advanced MMORPG configuration, the distributed game design considers bandwidth and latency constraints required by the games based on actual MMORPG traffic pattern. A simulation model is then developed to evaluate the performance of Pastry, a structure Peer-to-Peer system, in supporting the distributed game design. The simulation results have shown that Pastry performs well in distributing node stress. However, there is a bottleneck in terms of upstream bandwidth usage. We demonstrate that the bottleneck can be removed by low-cost algorithms. The results also show that using Scribe multicast tree built on top of Pastry to disseminate game traffic is an effective way to save the usage of bandwidth, which is a valuable resource in a P2P system.

We further argue that while Scribe is effective in distributing bandwidth usage for the distributed game design, it is not optimal in terms of latency performance. As a result, we propose two techniques to improve the latency performance of Scribe in the context of MMORPGs. The first technique identifies that the final hop of Scribe traffic path is largely selected without any proximity consideration and incurs the longest distance travelled. To overcome this, we introduce Proximity Neighbour Selection (PNS) into the final hop for latency improvement. The second technique builds a hierarchical twolevel overlay. While PNS can be applied at both levels for latency performance, the bandwidth stress required by applications can now be distributed among the nodes in the higher level overlay. Our simulation using an internet like topology has shown that both techniques have improved the latency performance significantly, and the two-level overlay has reduced the bandwidth stress on some critical nodes in the multicast tree by up to 2.7 times, comparing with what can be achieved by a standard Scribe overlay.

To enhance the playability of MMORPGs, we introduce the concept of a seamless map that aims to make the boundaries in the game world transparent to players. MMORPG usually achieves scalability by dividing a game world into multiple locales, and each locale has a dedicated locale server that simulates a part of the game world. A seamless map requires the communication between locale servers to allow the interactions between players across neighbouring locales. In a P2P system, it is critical to seek approaches to reduce the inter-locale communication cost since locale servers are assigned to peers that can be far apart from each other in terms of latency. We formulate a Locale Assignment Problem that aims to minimize the inter-locale communication cost in a P2P system, and demonstrate through an optimisation model that the problem is NP-hard. We then propose a low-cost heuristic for the Locale Assignment Problem. The key of the heuristic is to partition the physical network into bins so that peers in a common bin are close to each other in terms of latency proximity, as well as aggregate the partitions of a game virtual map by clustering neighbouring locales in the map. We then demonstrate that by assigning clustered neighbouring locales in the virtual map into the peers in common physical network bins, we are able to achieve similar inter-locale communication cost for the Locale Assignment Problem as that can be achieved by the optimization model we formulated, while avoiding the prohibitively high computation cost required by the latter.

We finally study the reliability aspect of a P2P system in supporting MMORPGs. In a P2P system, reliability generally refers to how system performs in response to churn – the continuous process of peer arrival and departure. In the distributed game design in P2P system, since peers contribute resources, the churn of a peer may negate game quality for other peers. To further justify the distributed game design from the reliability perspective, we develop a discrete event simulation to evaluate the churn resilience of the P2P system in supporting the distributed game design. When conducting the evaluation through the simulation, we compare the churn impact on the P2P system with different settings in supporting the distributed game design. Our general findings are two folds. First, the distributed game design based on the P2P multicast traffic model performs well in response to churn, with over 90 percentile of game sessions can achieve a pre-defined quality-of-service. Secondly, a trade-off between game features with respect to how real-time stringent actions are in the game, and the churn resilience is usually required.

We believe the findings in this dissertation will provide significant insights into supporting MMORPGs with P2P systems to address the scalability bottleneck of MMORPGs.

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.