Load Balancing for Virtual Worlds by Splitting and Merging Spatial Regions

Abstract

The expansion and contraction are the fundamental operations in systems assigning resources strictly based on load. Previously, an aggregation algorithm was proposed for distributing the load of a space (square in shape initially) comprises of a number of sub-spaces as balanced as possible among two servers. It used the SplitCapacity constraint to get contiguous larger spaces for an improved performance. However, the implementation of this algorithm revealed that, it violates the implicit consideration of the continuity constraint, when it distributes the load for non-square grid spaces. The basic flaw is that it allows non-contiguous and odd combinations. Further, the same was discovered with merging that uses only the MergeCapacity constraint to initiate the contraction process. In this paper, we summarise our previous work and examine the limitations in basic aggregation and merging algorithms. It is demonstrated with theoretical arguments and a simple simulation model that the assignment of contiguous spaces has potential benefits. We, therefore, extend these algorithms to incorporate an explicit continuity check to overcome the issues introduced by allowing odd cases. It is demonstrated with the help of results from our prototype that the extended methods strictly achieves the theoretical goals of the proposed methods.