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

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...

Full description

Saved in:
Bibliographic Details
Main Author: Li, Yusen
Other Authors: Cai Wentong
Format: Theses and Dissertations
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/55064
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-55064
record_format dspace
spelling sg-ntu-dr.10356-550642023-03-04T00:41:57Z Consistency-aware scheduling and load balancing in multi-server distributed virtual environments Li, Yusen Cai Wentong School of Computer Engineering Parallel and Distributed Computing Centre DRNTU::Engineering::Computer science and engineering 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. DOCTOR OF PHILOSOPHY (SCE) 2013-12-11T07:49:04Z 2013-12-11T07:49:04Z 2013 2013 Thesis Li, Y. (2013). Consistency-aware scheduling and load balancing in multi-server distributed virtual environments. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/55064 10.32657/10356/55064 en 154 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering
spellingShingle DRNTU::Engineering::Computer science and engineering
Li, Yusen
Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
description 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.
author2 Cai Wentong
author_facet Cai Wentong
Li, Yusen
format Theses and Dissertations
author Li, Yusen
author_sort Li, Yusen
title Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
title_short Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
title_full Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
title_fullStr Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
title_full_unstemmed Consistency-aware scheduling and load balancing in multi-server distributed virtual environments
title_sort consistency-aware scheduling and load balancing in multi-server distributed virtual environments
publishDate 2013
url https://hdl.handle.net/10356/55064
_version_ 1759853794851553280