Scalable Interest Management and Load Balancing for MMOG

voronoi-network.gif

When you’re trying to build a massively multiplayer online gaming platform (MMOG), probably the most important part of the system is scalability. After all, if it doesn’t scale, it’s simply a multiplayer online gaming platform – without the “massive”. While it almost seems embarrassing to point this out, it’s extremely interesting to note that there have recently been a lot of discussion about scalability of online systems – in particular, the Web 2.0 applications. I won’t point to these discussions, but suffice it to say that I find it terribly amusing to hear the various forms of the argument that you can worry about scalability later – i.e. it’s not something that has to be designed in from the start. (Arguments of the form “don’t worry about scalability because no one is going to use your application anyway” are perfectly fine, however). As the history of MMOG has shown, the application’s architecture has a huge impact on the ability to scale. As many gaming platforms have discovered, scalability isn’t something you can simply “add on” after you “get things right”. Anyone who thinks that this doesn’t apply to other network application architectures amuse me to no end, given as if they actually produce something of value, it will fall over when it hits the natural scalability limit of their crappy architecture.

In any event, there’s a couple of basic problems with MMOG that limit scalability. The first has to do with what is known as “Area Of Interest”. The idea here is familiar enough to anyone who has done any distributed communication in that the gaming platform doesn’t want to find itself in an N2 connection topology. In MMOG, the entities (gamer avatars, NPC, etc) have to communicate with other entities in the game. If you can’t find a way to limit the communication to the entities in the area of interest – i.e. the other entities that the entity in question is limited to communicating with – then you have a huge scalability issue due to sending messages to entities that simply don’t care about the communication because it can’t possibly affect them. This not only wastes bandwidth and precious OS network resources but causes a host of other issues having to do with the time ordering of distributed events and filtering our events that aren’t relevant. It’s a mess.

Area of interest management is complicated by the fact that the entities in the game don’t stand “still”. They move around the virtual world. This means that you can’t simply statically calculate what the relevant entity neighborhood should be. Even worse, due to flocking behavior, there’s the really nasty issue of crowding in virtual worlds – where you have large populations of entities within small areas (moving, I might add).

As you might expect, there’s been a lot of active research in this area. I’ve spent a non trivial amount of time over the last six months or so pouring through the research and seeing if I could find anything that wasn’t lame that worked the way I thought it would. I won’t review the literature here, as the papers I’m going to site already do a good job of reviewing the various ways of trying to deal with interest management in MMOG.

The second problem that I mentioned – that of load balancing – is closely related to the problem of interest management. The idea here is that you need to split up your processing load across your population – dynamically – so that you aren’t trying to host 100,000 entities on one CPU and distributed the rest of the 50,000 entities across 100 CPUs due to flocking. It’s a dynamic problem due to the movement of the entities which changes the interaction patterns as time progresses.

In any event, what I’ve been playing with over the past week or so is a rather elegant and butt simple mechanism for solving both issues – i.e. interest management and load balancing. The idea is very simple, being based on the use of Voronoi division of the virtual world to create a P2P overlay network between the various entities. You can find all the papers here at their site, a good intro paper is VON:AScalablePeer-to-PeerNetworkforVirtualEnvironments.

While I still have a ways to go on the project, what I have done is taken their 2006 Java demo code and refactored the hell out of it. I mean, geebus. C++ programmers seriously don’t know much about OO programming. I mean, it’s not just a “programming in another language” issue – I’ve seen their C++ code as well. Basically I just think that C++ doesn’t encourage OO and consequently not many of the people who learn OO via C++ actually end up learning OO. Having said that, I do note that they do understand the interest management problem and have come up with a very excellent solution.

A key aspect of the code is the calculation of the Voronoi domains and this is done with a Java translation of the de facto algorithm: Steve Fortune’s algorithm in C++. This is pretty much the only Java translation of this algorithm I’ve been able to find, so that fact alone allows me to completely forget and forgive the absolutely crappy OO design of the system. I’ve cleaned up that code as well, but haven’t gone into a big refactoring frenzy on its ass because it works and quite frankly I’ll hire someone to do this if it ever becomes a problem – there were just certain things I had to do to the Java implemenation and there were other certain things that I couldn’t – quite frankly – allow to exist in source that I actually make use of… :)

In any event, being an LGPL’d source code, I’ve also made my results public domain using the LGPL license as well. You can download both the source and the binaries here. This includes, naturally, the Java version of Steve Fortune’s Voronoi domain generator.

Below is a nice Java applet that I also rewrote which they provided as a demo of how the system works. My changes are to make the demo deterministic through a constant seed of the random generator and to make the simulated behavior a bit more realistic than their previous version had done.

There’s obviously some problems with this initial algorithm that they seem to have taken care of in latter versions of the protocol, and I’m actually adding tests to the system so I can verify the behavior. But it’s a fantastic start at a system which promises to solve two extremely nasty problems in MMOG and allow me to continue on with my Third Space project.

Java applet demo&nbsp&nbsp(compiled with Java 5.0)

    click on the applet then press ‘ENTER’ to start…&nbsp&nbsp&nbsp(other key controls)

Parameters: X dimension Node size AOI radius
&nbsp Y dimension Connection limit




Controls: (need to first click on the applet for key-press to be effective)

    ENTER: pause/resume
    SPACE: next step
    left-click select node to view
    ‘F': toggle “follow mode”
    ‘E': toggle “Voronoi edges”
    ‘O': restore viewport to origin
    ‘A': toggle “AOI-radius”
    ‘G': toggle “global nodes”

3 thoughts on “Scalable Interest Management and Load Balancing for MMOG

  1. Great points. I couldn’t agree more. Building and designing high performance systems as an after thought is a doomed exercise. Yet, many people still say things like that on public forums :)

  2. For your sake, I hope the Mocha is an iced mocha and not a hot mocha. It would be mighty painful to snort hot mocha.

Comments are closed.