Consistency-aware scheduling and load balancing in multi-server distributed virtual environments

Abstract

A distributed virtual environment (DVE) is a kind of distributed interactive application which allows a group of participants connected via a network to interact with a shared application state. DVEs have been widely used in many areas such as military training, collaborative design, e-learning and networked multi-user games. Zone-based multi-server DVEs (MSDVEs) have been shown to have good scalability to support a large population of users. The fundamental goal of a DVE is to create a consistent view of the virtual world among participants. However, resource saturations may occur at servers due to huge resource demand and imbalanced workload distribution. Due to resource limitations, some state updates cannot be timely disseminated to the relevant participants, and thus inconsistency is likely to occur. The inconsistency can have a great influence on the experiences of clients and the problem will become even more serious as the scale of the DVE grows. In this thesis, we study the position update scheduling and load balancing issues for improving consistency in MSDVEs with a set of servers constrained by upload bandwidth. In the update scheduling issue, we aim at investigating update schedules for minimizing the overall inconsistency in a MSDVE. Depending on how inconsistency is measured, we first formulate the update scheduling problems as inequality constrained optimization problems.Then, the update scheduling algorithms are investigated for minimizing the overall inconsistency in practical systems. The performance of the proposed algorithms is experimentally evaluated. The results show that our proposed algorithms generally outperform other algorithms under the same experimental settings. In the load balancing issue, we consider zone mapping and client assignment to minimize the total time-space inconsistency in a MSDVE. Zone mapping refers to determining which zone is maintained by which server while client assignment refers to determining which client is connected to which server. Similarly, the zone mapping and client assignment problem is first formulated as a mix-integer programming problem. Then, a centralized algorithm and a distributed adaptive tuning algorithm are proposed for minimizing the total inconsistency in practical systems. The performance of these algorithms is experimentally evaluated. The results show that the centralized algorithm normally performs close to the theoretical lower bound and the proposed algorithms significantly outperform other algorithms under the same experimental settings. To evaluate the proposed algorithms in practical system, a multi-server Battle City Game has been implemented.Various experiments have been designed in the game. The results show high efficiency of the proposed algorithms for reducing the inconsistency of the game. The results also show that the proposed algorithms can greatly improve the playability of the game.