臺灣博碩士論文加值系統

在網路虛擬環境(Networked Virtual Environment, NVE) 中，使用者透過網路連線在電腦產生的虛擬世界中互動，其概念被廣泛地運用在多種領域，像是軍事模擬、教育訓練和網路遊戲。例如，具有上兆美元商機的巨量多人線上遊戲(Massively Multi-player Online Game, MMOG)就是網路虛擬環境的一個例子。每天有數百萬名使用者呼朋引伴連上遊戲伺服器一起互動，為了能夠在虛擬世界中同時容納如此大量的使用者，遊戲公司必須提供足夠的伺服器才能確保遊戲進行的品質。而且日益精緻的聲光效果與更複雜的遊戲邏輯設計使得伺服器的計算負載更為沈重，而使用者高度變化的行為，讓伺服器之間的負載有極大的差異而影響系統整體效能。因此，如何考慮伺服器的容量(capacity)，動態地調整伺服器的計算量以達到負載平衡而增進系統的效能也就成為一個重要的問題。
傳統的網路虛擬環境系統將虛擬世界劃分為數個固定大小的區域(region)，每個區域都由一個伺服器管理，而一般由5~10個區域伺服器(region server, RS)共同管理著整個世界。當使用者聚集在一些像是市集或是演唱會場所等稱為Hotspot的特定地區時，會造成管理Hotspot所在區域的伺服器負載激增而引發負載不平衡。因為Hotspot大多數是暫時性且難以預測的，所以難以由傳統的固定式區域劃分來達成負載平衡。
在本篇論文中，我們進一步將區域劃分為許多稱為Cell的六角形小區域，提出稱為DLD (Directed Load Diffusion) 的動態負載平衡演算法，讓不同的伺服器間以移轉相鄰邊界Cell管理權的方式來達成負載的移轉。各個伺服器根據具有相鄰管理區域之伺服器的負載狀況，計算地區負載比率(Local Load Ratio, LLR)以挑選擁有最小使用率或最大剩餘容量的伺服器來進行負載轉移。如此可以讓不同容量上限的伺服器，都能維持在安全負載量(safety load ratio)以下。另外，當一個伺服器Sx超出負載上限且管理區域直接相鄰的伺服器無法完全分擔其負載時，Sx將發出強迫負載平衡請求(Forced Load Balance Request, FLB-Req)，迫使管理區域直接相鄰伺服器將負載轉移至管理區域與Sx不直接相鄰的伺服器以騰出計算容量而達成負載平衡。在負載移轉時，各個伺服器會盡力維持本身管理區域形狀的連續性，以減少跨伺服器通訊的成本。
我們針對DLD演算法進行模擬實驗，以驗證其執行效能。我們並將模擬結果與相關的ProGReGA負載平衡方法的模擬結果進行比較，我們發現DLD演算法具有不錯的負載平衡特性，而且具有較低的負載移轉成本與跨伺服器通訊成本。

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.

目　　　錄
中文摘要： I
Abstract: III
目　　　錄 V
I. 序論 1
II. 相關研究 5
2.1 虛擬環境伺服器架構 5
2.2 Snap-based動態負載平衡演算法 6
2.3 Greedy-based 動態負載平衡演算法 9
2.4 其他方法 13
III. 系統模型與參數定義 14
3.1 系統模型 14
3.2 邊界Cell資訊交換 15
3.3 負載定義 16
3.4 參數定義 18
3.4.1 地區負載比率 (LLR) 18
3.4.2 門檻值介紹 (Thresholds) 19
IV. 導向性負載擴散演算法(DLD) 21
4.1 Greedy Load Balancing 22
4.1.1 判斷過載機制 22
4.1.2 選擇負載轉移的對象伺服器 22
4.1.3 計算轉移負載量 22
4.2 Forced Load Balancing (FLB) 23
4.2.1 強制負載平衡請求 (FLB-Req) 23
4.2.2 禁止移轉列表 (FT-List) 23
4.2.3 計算FLB轉移負載 24
4.3 Cell 轉移機制 24
4.4 DLD-wLC & DLD-woLC 26
4.5 調整機制 27
4.5.1 伺服器負載與地區負載比率平均數 27
4.5.2 負載平衡時機調整機制Balancing Timing Coordination (BTC) 27
V. 模擬實驗與效能分析 29
5.1 虛擬環境設定 29
5.2 輕載門檻值測試 30
5.3 負載平均的取樣數測試 31
5.4 異質系統動態負載平衡 32
5.5 DLD與ProGReGA的效能比較 33
5.5.1 Avatar Migration 33
5.5.2 跨伺服器通訊 34
5.5.3 負載指標(Load Index) 35
VI. 結論 39
參考文獻 41

[1] B.D. Vleeschauwer, B.V.D. Bossche, T. Verdickt, F.D Turck, B. Dhoedt and P. Demeester , “Dynamic microcell assignment for massively multiplayer online gaming”. Proc of 4th ACM SIGCOMM workshop on Network and system support for games, pp. 1-7, 2005.

[2] B.V.D. Bossche, B.D. Vleeschauwer, T. Verdickt, F.D. Turck, B. Dhoedt, P. Demeester, “Autonomic microcell assignment in massively distributed online virtual environments,” Journal of Network and Computer Applications vol. 32, issue 6, pp. 1242-1256, Nov. 2009.

[3] C.E.B Bazerra and C.F.R. Geyer Multimedia “A load balancing scheme for massively multiplayer online games,” Tools and Applications, vol. 45, no.12, pp. 263-289, Oct. 2009

[4] D.T. Ahmed, S. Shirmohammad and J. Oliveira, “Improving Gaming Experience in Zonal MMOGs,” Proc.15th international conference on Multimedia, pp.51 - 584, 2007.

[5] D.T. Ahmed and S. Shirmohammad, “A microcell oriented load balancing model for collaborative virtual environments,” Proc. IEEE Conference on VirtualEnvironments, Human-Computer Interfaces and Measurement Systems, VECIMS. IEEE, pp. 86-91, 2008.

[6] I. Kazem, D.T. Ahmed and S. Shirmohammadi, “A Zone Based Architecture for Massively Multi-user Simulations,” Proc. Simulaiton Multiconference, vol. 1, pp. 149-156, 2007.

[7] J. Chen, B. Wu, M. Delap, B. Knutsson, H. Lu and C. Amza, “Locality aware dynamic load management for massively multiplayer games,” Proc. tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, PPoP, ACM. pp. 289-300, 2005.

[8] K. Lee and D. Lee, “A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution,” Proc. ACM symposium on Virtual reality software and technology, pp. 160-168, 2003.

[9] J.C.S. Lui and M.F. Chan, “An efficient partitioning algorithm for distributed virtual environment systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, issue 3, pp. 193-211, Mar. 2002.

[10] P. Morillo, J.M. Orduna, M. Fern´andez, and J. Duato. “An adaptive load balancing technique for distributed virtual environment systems,” Proc. Intl. Conf. on Parallel and Distributed Computing and Systems, PDCS, ACTA Press. pp. 256-261, 2003.

[11] S.D. Webb, S. Soh and W. Lau, “Enhanced mirrored servers for network games”. Proc. sixth ACM SIGCOMM workshop on Network and system support for games, pp. 117-122, 2007.

[12] T.N.B. Duong and S. Zhou, “A Dynamic Load Sharing Algorithm for Massively Multiplayer Online Games,” Proc. 11th IEEE International Conference on Networks, ICoN. pp. 131-136.

[13] S-F Wang, Z. Zhou and W. Wu, “A Layered Iterative Load Balancing Algorithm for Distributed Virtual Environment,” Journal of Software, pp. 2471-2482, 2008.

[14] http://bubble.lager.com.tw

[15] http://www.microsoft.com/games/age3

[16] http://www.secondlife.com

[17] http://www.warofwarcraft.com