Autonomic microcell assignment in massively distributed online virtual environments

Distributed virtual environments and massively multiplayer online games in particular have been on the rise for several years now. They offer huge digital environments characterized by tens of thousands of users interacting with each other. Efficiently managing these online worlds requires scalable architectures to distribute the load over multiple servers and maintain a high Quality of Experience (QoE). This need will only increase as online virtual worlds become more and more popular. A traditional approach to improve the scalability of this type of system is to statically partition the virtual world in smaller segments called cells, each assigned to a dedicated server.In this paper a novel approach of dividing the virtual world into even smaller parts called microcells is introduced. Critical in this approach are the algorithms that manage the microcell allocation over the available servers. These algorithms must face a number of challenges and have as a central goal to keep the load experienced by the servers below a given threshold. On one hand, clustering interacting microcells on one server allows to limit the overall load by minimizing the communication overhead. On the other hand, locating too many microcells on one server may cause the load to violate the threshold value, resulting in an overload situation. In this paper we present a number of algorithms that determine the microcell allocation and runtime adaptations of the microcell allocation to optimize the deployment. We evaluate the microcell approach by studying the impact of the microcell size and the number of servers. The efficiency of the algorithms in terms of their ability to decrease the maximum server load and their capability to maintain an ideal deployment in dynamic environments is also studied.