|
Title:
To Infinity and Beyond: Scaling Massively Multiplayer Games
Theme:
Distributed Systems
Period:
February 1st 2010 - May 31st 2010
Authors:
Ron Cohen
Anders Ejlersen
Rasmus Kristensen
Abstract:
This report pertains to load balancing techniques for use in MMO games. It focuses on the use of geographical partitioning techniques to distribute load in three-dimensional MMO games. These techniques are used to distribute the workload between servers by partitioning the virtual world into smaller sections. These smaller sections are then controlled by a server each. We give special attention the method by which the virtual world is partitioned, when they are partitioned and merged, and how this affects load balancing and the scalability of the solutions.
A brief analysis of network architectures is performed. The analysis concludes that a client/server approach is best suitable for MMO games. Hereafter, the structure of a typical game engine is outlined.
Subsequently, a static and two dynamic two-dimensional geographical partitioning techniques are described and analysed. The dynamic techniques are the Matrix and JoHNUM techniques. The Matrix technique uses a ``split-to-left'' technique which always partitions into into two equally sized partitions. The JoHNUM technique uses a more complex method of partitioning an area into two parts, and it takes into account the distribution of players in the sub-region of the virtual world that is to be partitioned.
The before mentioned techniques were designed for two-dimensional environments. Therefore we have extended them to support three-dimensional environments. For the JoHNUM technique in particular, this yielded a large increase in possible solutions to the partitioning problem. From these possible solutions a few are chosen to represent a variety of solutions.
We created a test game called Rock Pounder, with an appertaining game engine, to be able to evaluate the performance of the different techniques against each other. The game engine was constructed in a manner which makes it possible to create other games than Rock Pounder on top of it.
We performed tests in two test scenarios, the first scenario was with a static load. The static load was a battle in a fixed areas of the virtual world. The other scenario was a moving hotspot scenario in which the two teams were fighting at a location which moved with a given time interval.
From the tests we found that the static division were well suited for the static load. The JoHNUM solution however also performed well under static load, but the increased complexity of creating a dynamic solution is not needed when the workload is static.
In the hotspot scenario we found the Matrix and JoHNUM solutions to perform almost equally well, with the JoHNUM technique performing marginally better. However, it is suspected that the Matrix solution could have significant deficiencies with large virtual worlds and therefore we generally recommended JoHNUM.
Report:
Report (PDF)
Videos:
Scenario A: [Static] [Matrix X] [Matrix Y] [JoHNUM]
Scenario B: [Static] [Matrix X] [Matrix Y] [JoHNUM]
Download (Static Solutions):
Client/Test Client/Server (WIN7)
Client/Test Client/Server (OSX)
Test Client/Server (LINUX)
Download (Dynamic Solutions):
Client/Test Client/Server (WIN7)
Client/Test Client/Server (OSX)
Test Client/Server (LINUX)
|
