| 摘要: | 近年來隨著電腦設備的計算能力提升與網路的普及，使得越來越多的使用者可透過網際網路進入網路虛擬環境(Networked Virtual Environment, NVE)中以虛擬化身(avatar)的方式與其他的使用者進行各種即時互動；而NVE中最有名的例子為目前非常熱門的巨量多人線上遊戲(Massively Multi-player Online Game, MMOG)。客戶端/多伺服器(Client/Multi-Server, C/MS)架構是最常見的MMOG運作架構。因為常有成百上千的使用者或玩家(player)在MMOG中進行各種遊覽與互動，為了能夠同時容納且穩定管理巨量的使用者，MMOG需要功能強大且數量足夠的伺服器才能提供良好的遊戲品質。另外，MMOG也需要負載平衡(load balancing)方法，以便能夠將負載平均分配至各伺服器而更進一步提升伺服器整體效能。目前主要的C/MS負載平衡方法可以分為兩大類: player/object-based和zone-based 方法。在player/object-based方法中，當有多個化身群集於某處並有許多互動時，有很大的機率各個化身都分別由不同的伺服器管理。這會造成過多的跨伺服器通訊(inter-server communication)而降低伺服器整體效能;在zone-based方法中，虛擬世界會依伺服器的數量分割成相同數量而大小不一的區域，各個區域中的所有玩家化身與物件則會分配給一個伺服器管理，而由變更區域的大小達成負載平衡。因為zone-based方法較無上述在player/object-based中出現的問題，所以有許多MMOG採用zone-based負載平衡方法。然而在zone-based方法中，當大量玩家聚集於所謂的熱區(hotspot)時，熱區所在區域的伺服器負載會因而增加許多，影響伺服器整體服務品質甚鉅。本篇論文聚焦於zone-based負載平衡方法，藉由模擬實驗比較四個著名的zone-based負載平衡方法: 分別為ProGReGA、DLD、KD-tree以及Ahmed的方法。我們從化身遷徙(avatar migration)、跨伺服器通訊(inter-server communication)與負載偏差比(load deviation rate)三個不同的效能面向檢視各個方法的優缺點並加以分析比較，最後總結一些要點並提出各方法的可能改進方向。With the improvement of computer capability and the wide spread of high-speed internet access in recent years, more and more users can log in an NVE (Networked Virtual Environment) as an avatar to interact with other users via network connections. The most popular NVE is MMOG (Massively Multi-player Online Game), and Client/Multi-Server(C/MS) is the most popular MMOG system architecture. Because an MMOG usually has thousands of users or players interacting with each other concurrently, it needs a sufficient number of powerful and stable servers for accommodating the massive users. Besides, it needs a load balancing scheme to distribute the load evenly among the servers to pursuit better overall server performance. The load balancing schemes can be classified as two categories: player/object-based and zone-based. One critical problem in player/object-based schemes is that when a number of avatars gather together and interact concurrently, they are likely to be managed by different servers, leading to a large overhead of inter-server communications, which in turn lowers the overall server performance. In zone-based schemes, the MMOG virtual environment or virtual world is divided into several various-sized regions each of which is managed by a server. The server will be in charge of all the avatars and NPCs in its own region. When some servers are overloaded, regions are resized to relief the loads of them. Because the overheads problem in player/object-based schemes are usually lower in zone-based schemes, so most MMOGs nowadays adopt zone-based load balancing schemes. However, in zone-base schemes, when tons of players gather together in some place so-called hotspot, the load of the server managing the hotspot increases dramatically, and the overall service quality degrades significantly. This thesis focuses on zone-based load balancing schemes. It investigates thoroughly four famous zone-based load balancing schemes proposed currently, namely ProGReGA, DLD, KD-tree, and Ahmed’s algorithm. By extensive simulation experiment results, it compares the schemes in three different aspects of performance: avatar migration, inter-server communication and load deviation rate. In the end, it concludes some key points for zone-based load balancing schemes and presents some possibilities for improvement. |
