Multi-Server Dynamic Load Balancing for Networked Virtual Environments
| Autor: | Fu-Hsiang Chang, 張富翔 |
|---|---|
| Rok vydání: | 2010 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 98 In a networked virtual environment (NVE), users interact with each other in the computer-generated virtual world through networked links. NVEs are widely applied to a variety of areas like military simulation, education, training and network games. The massively multi-player online game (MMOG), which is nowadays a billion-dollar business, is a typical example of NVEs. Millions of users log on game servers, navigate the virtual world, and interact with each other concurrently. A good enough number of servers are provided to ensure so many concurrent users to go smoothly. However, the dynamic actions of users may lead to load unbalance among servers, so some servers may be overwhelmed and the overall system performance is degraded. Therefore how to dynamically adjust server loads with consideration of server capacities to reach load balance becomes an important issue. A traditional NVE system divides the virtual world into several fixed-sized regions, each of which is statically managed by a server. When users gather around a hotspot, the load of the server managing the region of the hotspot increases sharply. Since the occurrence of some hotspots is transient and unpredictable, it is hard to reach load balance among servers with traditional fixed-region partitioning. In this thesis, we further divide a region into many hexagonal subregions called “cells” and propose a dynamic load balancing algorithm, namely “Directed Load Diffusion (DLD), to transfer the management responsibilities of boundary cells among servers to reach server load balance. A overloaded server SX computes the local load ratio (LLR) according to loads of neighbor servers (i.e., the servers managing regions adjacent to those managed by SX) to select the neighbor server with the least utilization or maximum available capacity to transfer the load. In this way, every server keeps its load under the safety load threshold ratio (SLT). When all SX’s neighbor server is overloaded, SX will send a Forced Load Balance Request (FLB-Req) to force its neighbors to distribute their loads to their neighbors not adjacent with Sx for possible load transfer. Furthermore, a server tries to keep the property that its associated region consists of continuous cells to reduce avatar migrations and costs of inter-server communications. We have performed extensive simulation experiments to demonstrate the performance of DLD algorithm and compared the simulation results with those of the related ProGReGA algorithm. As shown in the thesis, DLD can reach relatively good load balance and has lower costs of load transfer and inter-server communications. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|