Massivizing Networked Virtual Environments on Clouds

Abstract

Networked Virtual Environments (NVEs) are virtual environments where physically distributed, Internet-connected users can interact and socialize with others. The most popular NVEs are online games, which have hundreds of millions of users and a global market of tens of billions Euros per year. Besides entertainments, NVE techniques are used in education, enterprise training, disaster-scenario analysis, etc. Because the number of NVE users is ever increasing, new NVEs which can host massive number of users are increasingly needed. To meet the demands of NVE users, NVE researchers and designers are continuously seeking novel ways to design NVEs. In recent years, due to the scalability, the flexibility, and the cost-efficiency of cloud computing technologies, clouds are gaining popularity as computing platforms for NVEs. It is challenging to manage large amounts of cloud computing resources to serve NVE users in a scalable, consistent, highly available, cost efficient, and interactive way. To massivize NVEs on clouds, in this thesis, we analyse the workloads of several NVEs, design and implement several NVE mechanisms, and evaluate them using realistic simulations or real-world experiments. Although we validate our approaches using exclusively online gaming data, we believe that the fundamental findings of this thesis can be applied to other fields of NVEs, because online games are often found to be among the most demanding kinds of NVEs. In Chapter 2, we introduce RTSenv, a benchmarking system for NVEs with a focus on Real Time Strategy (RTS) games. RTSenv can operate in several types of computing environments, from desktop-computers, to wide-area multi-clusters and commercial clouds. It leverages reactive fault tolerance techniques to perform robust, multi-machine, multiinstance RTS game experiments. RTSenv can help NVE researchers and practitioners to gain better insight into the real-world performance of NVEs. In Chapter 3, we propose a formalism to understand the implicit social networks of NVEs. The formalism consists of various ways to map interaction to social structure. By applying the formalism to real-world data collected from three different game genres, we analyse the implications of the formalism for in-game and gaming-related services, ranging from network and socially-aware matchmaking of players, to an investigation of social network robustness against player departure. In Chapter 4, we collect a long-term trace from an online meta-gaming networks: XFire. We present a high-level, marginal distribution- and time-based analysis of XFire: its global network, player activity, user-generated content, and social structure. We find that XFire is a slowly growing network whose players spend collectively in-game over 100 years, every hour. We quantify the “hardcore”-ness of XFire players, and find that a significant fraction of them have played over 10,000 in-game hours. In Chapter 5, we collect mobility traces of virtual-world citizens from World of Warcraft (WoW), and compare these traces with mobility traces collected from Second Life. Furthermore, motivated by the existence of numerous studies and models of mobility for networked real-world environments (NRE), we systematically study the characteristics of two NVE and two NRE mobility traces. We find that the mobility of citizens in real-world and virtual-world share many properties but with some differences. Based on the findings of this study, we propose a mobility model which can be used to generate realistic mobility traces for virtual-world citizens. In Chapter 6, we propose Area of Simulation (AoS), a scalability mechanism for multi-avatar virtual environments such as RTS games. The AoS mechanism combines and extends the mechanisms of Area of Interest (AoI) and Event-Based Lockstep Simulation (EBLS). Novel in the AoS mechanism, it uses both event-based and update-based operational models to manage not single, but multiple areas of interest. Moreover, the AoS mechanism synchronizes only selected areas of the virtual world instead of all the virtual world. We further design an AoS-based architecture, which uses the AoS and several scalability mechanisms simultaneously, dynamically trading-off consistency guarantees for scalability. We implement and deploy this architecture and we demonstrate that it can operate with an order of magnitude more avatars and a larger virtual world than common alternatives, yet without exceeding the resource capacity of computers of players. In Chapter 7, we propose CoH, a Cloud-based, online, Hybrid scheduling policy which reduces operational cost of hosting NVEs by making use of both on-demand and reserved instances of clouds. When provisioning and allocating computing resources for NVEs, the CoH policy dynamically selects the best solution among the solutions of some heuristics, and then manages resources accordingly. We show, via simulation and using multiple real-world traces, that the hybrid scheduling policy can obtain significantly lower cost than typical heuristics-based policies. In Chapter 8, we propose Availability-on-Demand (AoD), a mechanism providing high availability (HA) for NVE services when and only when HA is needed. The mechanism consists of an API that allows NVE operators to specify availability requirements which can dynamically change, and an availability-aware scheduler that dynamically manages computing resources based on user-specified requirements. Through trace-based simulation, we show that the AoD mechanism can protect important parts of NVEs dynamically. which also leads to low operational cost.