Since our current implementation does not yet fully support dynamic object migration, we use trace-based simulation to evaluate the impact of object placement. Using traces from a 15-minute Quake II game played by 128 computer controlled players, we simulate the interest-based placement heuristics described in Section 6, an intelligent region-based placement algorithm, and a simple static round-robin assignment of objects to nodes.
To get an intuition about why object placement using an interest graph might function well in a game, consider a typical snapshot of the interest graph between the 128 players (Figure 12). An edge exists between any two players that have been interested in each other for at least 5 seconds. There are many disjoint components that can be placed on separate servers without incurring any inter-node links and some of the larger clusters could be partitioned further with only a few edges crossing the cut; in fact, there were on average 40 disjoint clusters during this 15 minute game.
|
|
Figure 13 shows the bandwidth costs and object migration frequency for the simulated algorithms. We find that the interest-based placement heuristics incurs bandwidth costs close to that based on an intelligent region based placement model and that both do significantly better than a naïve static object placement. We found that the migration frequency using an interest-based approach was much lower than that based on regions. We conjecture that the reasons region-based schemes do worse is that the interest-based scheme handles the following common situations better: (1) there are some interests not related to regions (e.g., two players chasing each other), and (2) many objects are only transiently interested others within the same region (e.g., players may just be ``running through'' a region).