Consistency-aware partitioning algorithm in multi-server distributed virtual environments

Abstract

In DVEs, the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. One of the key issues in the design of an efficient and scalable Multi-server Distributed Virtual Environment (MSDVE) is the partitioning, which concerns with efficiently distributing the workload generated in the virtual environment among multiple servers in the system. Most of the existing work on the partitioning issue in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or improve the interactivity of DVE. In this paper, we study the partitioning issue from a new perspective and aim to reduce the time-space inconsistency of a DVE. Time-space inconsistency is a consistency metric, which has been proven to be an effective performance measure of DVEs. Using the time-space inconsistency metric, we formally formulate our partitioning problem as a mix integer programming problem and propose a solution based on Alternating Optimization (AO) technique. An iterative partitioning algorithm is also developed accordingly. The algorithm gives a partition as well as the corresponding update schedule to minimize the total time-space inconsistency. Different from most of the existing work, the resulted partition is avatar-based rather than zone/region-based. To evaluate the performance of the proposed partitioning algorithm, extensive experiments were conducted and results are reported in the paper.