Multi-Server Architecture for Distributed Virtual Environments

 

 

A distributed virtual environment (DVE) allows remote users to interact in a 3D virtual environment (VE) through the Internet. Applications of DVEs include multiplayer online games, military/industrial remote training, collaborative engineering and social networks. As the scale of some DVE systems is becoming very large with thousands of concurrent users, the DVE load balancing problem has been attracting a lot of research attention.

 

A popular way to address the DVE load balancing problem is to divide the load among multiple servers by dividing the VE into multiple partitions with each partition being served by a single server. Some load balancing methods may treat this partitioning process as an offline process. This load balancing strategy is referred to as static load balancing. They consider several partitioning methods, such as quad-tree, unconstrained and constrained K-D tree, and region growing. Some popular DVE applications, such as World of Warcraft and Second Life, have adopted the static load balancing strategy. Its advantages are that it is simple and the speed of the partitioning process does not affect the interactivity of the DVE systems. However, as users of a DVE system move inside the VE, some regions may become too crowded while others may have too few users. As a result, the servers managing the crowded regions will become overloaded and the users within them may suffer from significant delay, while other servers may be under-utilized. (In systems like World of Warcraft and Second Life, players of different partitions are not allowed to interact with each other to avoid the synchronization problem. Unfortunately, this also reduces the shared experience of users.) To overcome this limitation, the partitioning process can be performed dynamically during runtime. This load balancing strategy is referred to as dynamic load balancing. The idea is that when the load of a server becomes too high, it may dynamically transfer part of its load to other lightly loaded servers to achieve load balancing.

 

Earlier in this project, we were trying to develop dynamic load balancing methods that are efficient and may produce effective load balancing solutions. Recently, we also look how network latency may affect the effectiveness of the load balancing solutions.

 

Haiyang Hu, Rynson Lau, Hua Hu, and Benjamin Wah, "On View Consistency in Multi-Server Distributed Virtual Environments," IEEE Trans. on Visualization and Computer Graphics, 20(10):1428-1440, Oct. 2014.

[paper] [suppl]

Abstract: A distributed virtual environment (DVE) is a shared virtual environment (VE) that allows remote users to interact with each other through networks. DVEs are becoming very popular due to some prominent applications, such as online games and virtual worlds. To support a large number of users, a multi-server DVE architecture may be adopted, with each server managing a subset of users. However, there are two critical problems with this architecture: view inconsistency caused by delays and server overloading caused by uneven distribution of users. While the first problem affects users' perception of the VE and causes user disputes, the second problem affects the system response time. In this paper, we first show that the view inconsistency problem and the load balancing problem are conflicting objectives. We then propose an efficient joint optimization framework to address both problems. Our results show that the proposed method can improve the view inconsistency problem significantly, which is important to the interactivity of DVE applications.

 

Yunhua Deng and Rynson Lau, "Dynamic Load Balancing in Distributed Virtual Environments using Heat Diffusion," ACM Trans. on Multimedia Computing, Communications and Applications, 10(2), Article 16, Feb. 2014.

[paper]

Abstract: Distributed virtual environments (DVEs) are attracting a lot of attention in recent years, due to the increasing popularity of online gaming and social networks. As the number of concurrent users of a DVE increases, a critical problem is on how the workload among multiple servers can be balanced in order to maintain real-time performance. Although a number of load balancing methods have been proposed, they either try to produce high quality load balancing results and become too slow or emphasize on efficiency and the load balancing results become less effective. In this paper, we propose a new approach to address this problem based on heat diffusion. Our work has two main contributions. First, we propose a local and a global load balancing methods for DVEs based on heat diffusion. Second, we investigate two performance factors of the proposed methods, the convergence threshold and the load balancing interval. We have conducted a number of experiments to extensively evaluate the performance of the proposed methods. Our experimental results show that the proposed methods outperform existing methods in that our methods are effective in reducing server overloading while at the same time being efficient.

 

Yunhua Deng and Rynson Lau, "On Delay Adjustment for Dynamic Load Balancing in Distributed Virtual Environments," IEEE Trans. on Visualization and Computer Graphics (Proc. IEEE VR 2012), 18(4):529-537, April 2012.

[paper]

Abstract: Distributed virtual environments (DVEs) are becoming very popular in recent years, due to the rapid growing of applications, such as massive multiplayer online games (MMOGs). As the number of concurrent users increases, scalability becomes one of the major challenges in designing an interactive DVE system. One solution to address this scalability problem is to adopt a multi-server architecture. While some methods focus on the quality of partitioning the load among the servers, others focus on the efficiency of the partitioning process itself. However, all these methods neglect the effect of network delay among the servers on the accuracy of the load balancing solutions. As we show in this paper, the change in the load of the servers due to network delay would affect the performance of the load balancing algorithm. In this work, we conduct a formal analysis of this problem and discuss two efficient delay adjustment schemes to address the problem. Our experimental results show that our proposed schemes can significantly improve the performance of the load balancing algorithm with neglectable computation overhead.

 

Yunhua Deng and Rynson Lau, "Heat Diffusion Based Dynamic Load Balancing for Distributed Virtual Environments," Proc. ACM VRST, pp. 203-210, Nov. 2012.

[paper]

Abstract: Distributed virtual environments (DVEs) are becoming very popular in recent years, due to their application in online gaming and social networking. One of the main research problems in DVEs is on how to balance the workload when a lot of concurrent users are accessing it. There are a number of load balancing methods proposed to address this problem. However, they either spend too much time on optimizing the partitioning process and become too slow or emphasize on efficiency and the repartitioning process becomes too ineffective. In this paper, we propose a new dynamic load balancing approach for DVEs based on the heat diffusion approach which has been studied in other areas and proved to be very effective and efficient for dynamic load balancing. We have two main contributions. First, we propose an efficient cell selection scheme to identify and select appropriate cells for load migration. Second, we propose two heat diffusion based load balancing algorithms, local and global diffusion. Our results show that the new algorithms are both efficient and effective compared with some existing methods, and the global diffusion method performs the best.

 

Rynson Lau, "Hybrid Load Balancing for Online Games," Proc. ACM Multimedia, pp. 1231-1234, Oct. 2010.

[paper]

Abstract: As massively multiplayer online games are becoming very popular, how to support a large number of concurrent users while maintaining the game performance has become an important research topic. There are two main research directions based on the multi-server architecture, global load balancing, which is optimal but computationally expensive, or local load balancing, which is not optimal but efficient. In this paper, we propose a hybrid load balancing approach to support massively multiplayer online gaming. Our idea is to augment a local load balancing algorithm with some global load information, which may be obtained less frequently. We propose two methods to implement the hybrid approach. Our results show that the proposed methods reduce the frequency of server overloading and improve the overall game performance significantly.

 

repart

Beatrice Ng, Rynson Lau, Antoni Si, and Frederick Li, "Multi-Server Support for Large Scale Distributed Virtual Environments," IEEE Trans. on Multimedia, 7(6):1054-1065, Dec. 2005.

[paper]

Abstract: CyberWalk is a distributed virtual walkthrough system that we have developed. It allows users at different geographical locations to share information and interact within a shared virtual environment (VE) via a local network or through the Internet. In this paper, we illustrate that as the number of users exploring the VE increases, the server will quickly become the bottleneck. To enable good performance, CyberWalk utilizes multiple servers and employs an adaptive region partitioning technique to dynamically partition the whole VE into regions. All objects within each region will be managed by one server. Under normal circumstances, when a viewer is exploring a region, the server of that region will be responsible for serving all requests from the viewer. When a viewer is crossing the boundary of two or more regions, the servers of all the regions involved will be serving requests from the viewer since the viewer might be able to view objects within all these regions. This is analogous to evaluating a database query using a parallel database server, which could improve the performance of serving a viewer's request tremendously. We evaluate the performance of this multi-server architecture of CyberWalk via a detail simulation model.

 

Rynson Lau, Beatrice Ng, Antoni Si, and Frederick Li, "Adaptive Partitioning for Multi-Server Distributed Virtual Environments," Proc. ACM Multimedia, pp. 271-274, Dec. 2002.

[paper]

Abstract: A distributed virtual environment (DVE) allows users at different geographical locations to share information and interact within a common virtual environment (VE) via a local network or through the Internet. However, when the number of users exploring the VE increases, the server will quickly become the bottleneck. To enable good performance, we are currently developing a multi-server DVE prototype. In this paper, we describe an adaptive data partitioning technique to dynamically partition the whole VE into regions. All objects within each region will be managed by a single server. As the loading of the servers changes, we show how it can be redistributed while minimizing the communication cost. Our initial results show that the proposed adaptive partitioning technique significantly improves the performance of the overall system.

 

Beatrice Ng, Antoni Si, Rynson Lau, and Frederick Li, "A Multi-Server Architecture for Distributed Virtual Walkthrough," Proc. ACM VRST, pp. 163-170, Nov. 2002.

[paper]

Abstract: CyberWalk is a distributed virtual walkthrough system that we have developed. It allows users at different geographical locations to share information and interact within a common virtual environment (VE) via a local network or through the Internet. In this paper, we illustrate that when the number of users exploring the VE increases, the server will quickly become the bottleneck. To enable good performance, CyberWalk utilizes multiple servers and employs an adaptive data partitioning techniques to dynamically partition the whole VE into regions. All objects within each region will be managed by one server. Under normal circumstances, when a viewer is exploring a region, the server of that region will be responsible for serving all requests from the viewer. When a viewer is crossing the boundary of two or more regions, the servers of all the regions involved will be serving requests from the viewer since the viewer might be able to view objects within all those regions. We evaluate the performance of this multi-server architecture of CyberWalk via a detail simulation model.

 

Last updated in July 2015