Workspace Model for MMOG Load Balancing

From EQUIS Lab Wiki

Contents 1 The Problem 2 The Literature 2.1 De Vleeshauwer et al. 2.1.1 Terminology 2.1.2 Idea of Microcells 2.1.3 Algorithms 2.1.3.1 Balanced Deployment Algorithm 2.1.3.2 Clustering Deployment Algorithm 2.1.3.3 Simulated Annealing Deployment Algorithm 2.1.3.4 Optimal Deployment Algorithm 2.1.4 Metrics for Evaluating 2.1.5 Conclusions 2.1.6 How this can benefit us

The Problem

In order to maintain their enormous virtual environments, Massively Multiplayer Online Games (MMOGs) are often run as distributed systems across vast server farms. Usually, the virtual world is segmented into a contiguous collection of areas which are then assigned to particular server.

Here are the wrinkles:

• Since the tremendous world population of moving entities (monsters, villagers, players) are not constrained to any particular area the load on any particular server is not going to be static. An example could be a gathering where one region would experience an increase in population while the surrounding regions would experience a decrease. A solution to this could be to allow segments to be dynamically resized (even created or deleted) based on their load.
• It is very possible for two entities to be close enough to interact direcly (chat, trade, or engage in violence) and yet be in different segments. This would lead to many cross-segment (and so, cross-server) communications, which are more time consuming. The solution here is to maintain synchronised copies of units in the border areas so that they can communicate more efficiently. This leads to a handful of smaller problems.
• In the unfortunate event of a server breaking down, the segment it was responsible for must be recreated quickly and accurately. This would be done perfectly if every single change was commited to the database, however that quickly becomes a prohibitively expensive affair. In this situation, the paying customers will be more forgiving of a hiccup in their geographical location than the loss of in game resources

The Workspace Model appears to be capable of solving these issues.

The Literature

De Vleeshauwer et al.

Dynamic microcell assignment for massively multiplayer online gaming (Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games) De Vleeschauwer et al. Link

Terminology

In this paper, use refer to segments of the world as cells. At least in the naive approach, where distributing the world over many servers is accomplished by dividing the world into cells, which are simply areas defined by a homogeneous grid, and assigning a server to each one.

Areas where there are higher concentrations of players, are identified as hotspots.

Microcells are much smaller, yet still grid-based, cells. In their simulations they entertain different amounts of microcells (2x2 to 16x16).

Idea of Microcells

Their idea of microcells differs slightly from what we had already discussed regarding the shrinking and growing of the borders of our existing cells. It seems to be a pretty good idea, and should be considered. Instead of having many cells contracting and expanding in order to provide the best 'grip' on the amount of players, they subdivide thier cells into microcells, and then assign sets of microcells to each server. This relaxes the constraint of cells needing to be rectangular, without involving the headaches of polygonal cells.

Algorithms

They provide high level descriptions of existing algorithms, but do not get into their implementation. First, they describe two greedy algorithms, a simulated annealing algorithm, then theoptimal (but time consuming) algorithm.

Balanced Deployment Algorithm

The balanced deployment algorithm iterates through each microcell, in decreasing order of player load, and assigns it to the server with the least responsabilities.

Clustering Deployment Algorithm

The next greedy algorithm is an optimisation of the aforementioned algorithm. It clusters together the microcells based on the likelyhood of inter-cluster communication. This will allow for faster message passing between players on different clusters by placing them on the same server. This will lead to faster message passing at the cost of potential imbalance of computational responsability across servers.

Simulated Annealing Deployment Algorithm

This approach, which has been used to solve combinatorial optimization problems, picks a solution, then repeatedly modifies it in an attempt to find a better one. The problem of having an absolutely terrible, pseudo-random starting solution is sovled by using one of the earlier algorithms to generate the starting position in the solution space.

Optimal Deployment Algorithm

Given enough time (they estimate several days on a desktop computer for a small world of 64 microcells) and integer linear programming you can come up with the best possible deployment. Obviously, in a realtime game this can not be implemented with current technology, but it provides a good benchmark against which we can compare other algorithms.

Metrics for Evaluating

The authors have given us a nice table of event weights that each player might undertake. They are presented as a two dimensional table, where each of the actions have a weight if performed locally and externally. This along with an enormous formula included in the appendix can be used to compare the algorithms provided the state of a virtual world. This data was collected from an existing multiplayer game named Crossfire.

Conclusions

Their microcell approach does do a good job of balancing server load, as well as minimizing the weight of the operations required. There is an optimum amount of microcells (seems to be 4x4), after which the server load starts creeping up again.

How this can benefit us

There doesn't seem to be much about the QOS of the gameplay. It cannot be assumed that less busy servers will increase feedthrough. This would be interesting to take a look at. Their algorithms, and their idea of microcells could be a good architecture to use and apply to the Workspace objects we'll be using. It also means that instead of having 'borders', we can represent the contents of microcells on the edges of servers on each side.