(3.238.96.184) 您好!臺灣時間:2021/05/12 15:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:李政翰
研究生(外文):Li, Cheng Han
論文名稱:基於地域性的需求分配策略以提供負載平衡於支援大型多人線上遊戲的伺服器叢集
論文名稱(外文):Locality-based Request Distribution Policies for Load Balancing in a Server Cluster Supporting Massively Multiplayer Online Games
指導教授:姜美玲姜美玲引用關係
口試委員:陳彥錚蔡錫鈞黃光璿姜美玲張軒彬
口試日期:2013/1/30
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊管理學系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:76
中文關鍵詞:多人線上遊戲伺服器叢集內容感知需求分配負載平衡遊戲地圖
外文關鍵詞:MMOGs (Massively Multiplayer Online Games)Server ClusterContent-Aware DispatchingLoad BalancingGame Map
相關次數:
  • 被引用被引用:2
  • 點閱點閱:329
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:16
  • 收藏至我的研究室書目清單書目收藏:0
隨著網路科技與網路應用的發展速度越來越快,大型多人線上遊戲(Massive Multiplayer Online Game, MMOG)更加地蓬勃發展,從2D遊戲介面(如楓之谷[16])轉變為3D遊戲介面(如魔獸世界[1]),遊戲的執行更加地耗費伺服器系統的資源。因此,若只用單一台遊戲伺服器來對整體遊戲內容提供服務,會因為處理的資料量太多,而導致伺服器會無法負荷,所以使用多台伺服器來分散處理已成為趨勢。伺服器叢集(Server Cluster)是一個分散式的架構,能夠藉由伺服器數量的增加來提升系統整體的服務能力,具有高擴充性與高可靠性的優點,成為一個具有成本效益的解決方案。
我們採用的遊戲Stendhal [2,3],原先是屬於單一伺服器架構的多人線上遊戲,它是利用地圖將玩家群集的遊戲類型,此遊戲的特性是玩家只能得知目前所在地圖的資訊,處於不同地圖上的資訊都不會得知。而在論文[28]中設計了Game Connection Handoff機制,讓原本只屬於單一伺服器架構的Stendhal遊戲,變成多台伺服器(Multi-server)的遊戲,且實作在Linux Virtual Server with Content-Aware Dispatching (LVS-CAD) [33,34] 叢集式平台上,讓玩家連線能夠透過此機制轉移到不同伺服器上的地圖去進行遊戲。
由於分配遊戲地圖至伺服器的策略會影響各伺服器所服務地圖及玩家的數量,進而影響伺服器負載是否均衡,在本論文中,我們提出了Game-Server Locality-Aware Request Dispatching(GSLARD)負載分配機制,主要目的是讓相鄰的地圖盡可能交由同一台伺服器來服務,可以減少遊戲連線的轉移。所以在分配地圖至伺服器時,盡可能由目前負載最輕且與該遊戲地圖具有地域性的伺服器來服務,這樣讓遊戲的負載能夠有效地分散至各個伺服器。我們並且將分配地圖的負載機制區分三種類型:第一種屬於動態的地圖分配類型,此類型是當玩家開始登入遊戲後,視伺服器負載或是地圖資訊才會開始動態地進行分配地圖至伺服器。第二種屬於靜態的地圖分配類型,在遊戲開始前,地圖已經被事先地分配給各個伺服器。第三種屬於混合型的地圖分配類型,即包含事先的靜態分配法,以及在遊戲進行後,依遊戲進行的狀態動態的重新分配地圖。在混合型的地圖分配類型中,我們設計了兩種事先分配地圖的方法方式,分為依地圖之間的相鄰性及依地圖之間的相鄰性與權重性分配方式。即在遊戲開始前先進行地圖的分配,而在遊戲進行後,會使用GSLARD負載分配機制在地圖上沒有玩家時,將該地圖動態地自伺服器上釋放,等待下次有玩家進入此張地圖時,再被重新分配到具有地域性的Game Server中,讓具有相鄰性的地圖能夠被分配給同一台伺服器來提供服務。
實驗結果顯示,由於地圖的分配策略考量了地圖的相鄰性,動太的GSLARD負載機制可以降低8%的平均CPU使用率。而加上事先地圖分配的混合類型的GSLARD負載機制,平均CPU使用率比動態的GSLARD負載機制還要再降低約6%。因此,事先將地圖依地圖的資訊分配到Game Server上,不僅能夠降低整體遊戲伺服器叢集的平均CPU使用率,也能夠使地圖盡可能地保持完整性,減少Game Server都處理不相鄰的地圖,降低地圖破碎性的發生。

With the rapid growth of network technology and internet applications, massively multiplayer online games (MMOGs) have become very popular and are transformed from 2D games (such as Maple Valley [16]) into 3D games (such as world of Warcraft [1]). Execution of the games consume lots of the server resources. Therefore, using multiple distributed servers instead of a single server to provide game services has become a trend. Server cluster is a distributed architecture that can increase service capacities and provide a reliable, scalable, and cost-effective solution for game services.
Stendhal [2,3] is a single server architecture for MMOGs. In this game, only players on the same map can know the game status with each other. In the work [28], the Game Connection Handoff mechanism [28] is developed and implemented on the LVS-CAD cluster system [33,34] to turn Stendhal from a single game server architecture into a multiple game servers architecture.
Using this mechanism, in this paper, we have proposed Game-Server Locality-Aware Request Dispatching (GSLARD) policy which dispatches adjacent maps to the same server as much as possible for reducing the transfer of players’ game connections. When assigning a map to a server, the server loading and geographical nature of the game map are considered a player’s ongoing game connection can be transparently migrated among game servers, which allows the game loading to be effectively allocated to each server. We distinguish three types of dispatching policies. The first one is the dynamic distribution of maps, which dynamically assigns maps to the servers depending on the server’s loading or map information after a player logins to the game. The second one is the static distribution of maps. Before the game begins, the maps have been assigned to servers in advance and the assignment will not be changed. The third one is the hybrid distribution of maps, which uses static distribution of maps. Whereas, after the game begins, it depends on the game state to dynamically redistribute maps. We have designed two schemes to pre-allocate maps according to the maps’ adjacency, and the maps’ adjacency and weight value. Before the game starts, all maps are pre-assigned to each server, and after the game begins, GSLARD load distribution mechanism will release maps that have no player from the responsible server. Next time when a player enters this map, this map will be reassigned to a game server in the way that adjacent maps will be assigned to the same server in order to provide games services.
The experiments show that GSLARD policy can by reduce about 8% average CPU utilization since it considers maps’ adjacency when distributing maps to servers. When added in the pre-allocation of maps, the GSLARD with hybrid distribution of maps can further reduce about 6% average CPU utilization. Therefore, the policies with hybrid distribution of maps can not only reduce the overall average CPU utilization of server cluster, but also keep the map integrity and avoid handling maps which are not adjacent in the same server.

誌謝 I
論文摘要 II
Abstract IV
目錄 VII
圖目錄 IX
表目錄 XI
第一章 緒論 1
第二章 相關研究與技術 4
2.1 遊戲伺服器背景簡介 4
2.1.1 Client/Server 架構 5
2.1.2 Peer-to-Peer架構 6
2.1.3 Hybrid Client/Server架構 7
2.1.4 Cluster-based Client/Server架構 8
2.2 遊戲負載平衡相關研究 9
2.2.1 分散式遊戲虛擬環境探討 9
2.2.2 負載平衡相關研究 12
2.2.3 其它相關研究 17
2.3 叢集式系統簡介 18
2.3.1 Linux Virtual Server 18
2.3.2 Linux Virtual Server with Content-Aware Dispatching (LVS-CAD) 21
2.3.3 支援MMOG的LVS-CAD伺服器叢集 22
2.3.4 Game-based Locality-Aware Request Distribution (GLARD) 27
第三章 系統設計與實作 30
3.1 遊戲架構與平台設計 30
3.2 遊戲負載平衡策略 33
3.2.1 GLARD動態分配策略的問題 33
3.2.2 Game-Server Locality Aware Request Distribution (GSLARD)的動態分配策略 ………………… ………………………………………………………34
3.2.3 考慮地圖的相鄰性及權重值的混合分配策略 38
3.2.4 考慮地域性的混合分配策略 39
3.2.5 平均分配的靜態策略 40
3.3 Linux Kernel 的修改與實作 41
3.3.1 IPVS-CAD Module的資料結構的修改 42
3.3.2 GSLARD負載平衡策略的資料結構 42
3.3.3 GSLARD動態策略於Front-end Server的實作 45
3.3.4 具事先分配地圖的GSLARD混合策略於Front-end Server的實作 51
3.3.5 Server地圖名稱的修改 56
第四章 實驗環境與效能評估 57
4.1 實驗環境 57
4.2 Agent-Client與實驗地圖 59
4.3 實驗設計與效能評估 60
4.3.1 各分配策略的CPU負載情形 61
4.3.2 玩家Handoff 次數情形 63
4.3.3 伺服器叢集Throughput情形 65
4.3.4 地圖分配至Server的情形 66
4.3.5 玩家的分佈情形 67
第五章 結論與未來工作 72
5.1 結論 72
5.2 未來工作 73
參考文獻 74

[1]“World of Warcraft”, http://www.battle.net/wow/, 2011.
[2]“A Multiplayer Online Role Playing Framework to develop games - Stendhal”, http://arianne.sourceforge.net/game/stendhal.html.
[3]“Stendhal is a fully fledged free open source multiplayer online adventures game (MMORPG) developed using the Arianne game system”, http://stendhalgame.org/.
[4]B. D. Vleeschauwer, B. V. D. Bossche, T. Verdickt et al., “Dynamic microcell assignment for massively multiplayer online gaming “, in Proceedings of 4th ACM SIGCOMM workshop on network and system support for games, Hawthorne, NY, pp. 1-7, 2005.
[5]“Ganglia Monitor System”, http://ganglia.sourceforge.net/.
[6]“The Linux Virtual Server Project - Linux Server Cluster for Load Balancing”, http://www.linuxvirtualserver.org/.
[7]W. Zhang, “Linux virtual server for scalable network services” , Ottawa Linux Symposium, 2000.
[8]Joseph Mack, “LVS-HOWTO”, http://www.austintek.com/LVS/LVS-HOWTO/HOWTO/.
[9]E. Cronin, B. Filstrup, and A. Kurc, “A Distributed Multiplayer Game Server System” , Electrical Engineering and Computer Science Department, University of Michigan, 2001.
[10]“Blizzard Entertainment: Warcraft III”, http://us.blizzard.com/games/war3/.
[11]“Age of Empires III”, http://www.ageofempires3.com/
[12]F. Lu, S. Parkin, and G. Morgan, “Load balancing for massively multiplayer online games” , in Proceedings of 5th ACM SIGCOMM workshop on network and system support for games, Singapore, 2006.
[13]B. V. D. Bossche, T. Verdickt, B. D. Vleeschauwer et al., “A platform for dynamic microcell redeployment in massively multiplayer online games” , in Proceedings of the 2006 international workshop on network and operating systems support for digital audio and video, Newport, Rhode Island, pp. 1-6, 2006.
[14]“Oracle: Java EE at a Glance”, http://www.oracle.com/technetwork/java/javaee/.
[15]C. Bezerra and C. Geyer, “A load balancing scheme for massively multiplayer online games” , Multimedia Tools and Applications, vol. 45, no. 1, pp. 263-289, 2009.
[16]“MapleStory - A Free Massively Multiplayer Online Role-playing Game”, http://www.maplestory.com/.
[17]“Age of Empires III”, http://www.ageofempires3.com/.
[18]”Counter-Strike Online”, http://cso.iahgames.com/.
[19]B. V. D. Bossche, B. D. Vleeschauwer, and T. Verdickt et al., “Autonomic microcell assignment in massively distributed online virtual environments”, Journal of Network and Computer Applications, Vol. 32, Issue 6, pp. 1242-1256, November 2009.
[20]K. Lee and D. Lee, “A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution”, in Proceedings of the ACM symposium on virtual reality software and technology, Osaka, pp. 160-168, Japan, 2003.
[21]J. Chen, B. Wu, and M. Delap et al., “Locality aware dynamic load management for massively multiplayer games”, in Proceedings of the tenth ACM SIGPLAN symposium on principles and practice of parallel programming, Chicago, IL, USA, pp. 289-300, 2005.
[22]“Oracle: MySQL, The world's most popular open source database”, http://www.mysql.com/.
[23]Kohana, M. Okamoto, S. Ikegami, A.”“Optimal Data Allocation for Keeping Fairness of Online Game”, In Proceeding WAINA 12 Proceedings of the 2012 26th international conference on advanced information networking and applications workshops, pp. 1209-1214, 2012.
[24]C. Bezerra, J. Comba, C. Geyer,” Adaptive Load-Balancing for MMOG Server Using KD-trees”, in Magazine Computers in Entertainment (CIE) - Theoretical and Practical Computer Applications in Entertainment archive ,Vol. 10,Issue 3, No. 5, October 2012.
[25]Yunhua Deng, Rynson W. H. Lau,“On Delay Adjustment for Dynamic Load Balancing in Distributed Virtual Environments”,in Journal IEEE Transactions on Visualization and Computer Graphics archive, Vol.18, Issue 4, pp. 529-537, April 2012.
[26]李政忠, 陳啟彰, “多人線上遊戲伺服器之動態負載平衡機制的設計與製作” , 國立屏東教育大學資訊科學應用期刊, 第3卷, 第1期, 2007年7月.
[27]陳建豪, “支援VoIP之巨量多人線上遊戲架構”, 碩士論文, 中華大學資訊管理學系, 2006.
[28]俞博文, “基於地圖分割實作可延展性的負載平衡伺服器叢集於大型多人線上遊戲”, 碩士論文, 國立暨南國際大學 資訊管理學系, 2011.
[29]F. Lu, S. Parkin, and G. Morgan, “Load balancing for massively multiplayer online games” , in Proceedings of 5th ACM SIGCOMM workshop on network and system support for games, Singapore, 2006.
[30]Diablo II, http://us.blizzard.com/en-us/games/d2/, 2000.
[31]V. Cardellini, E. Casalicchio, and M. Colajanni et al., “The state of the art in locally distributed Web-server systems”, ACM Comput. Surv., vol. 34, no. 2, pp. 263-311, 2002.
[32]陳建宏, “伺服器叢集系統的允入控制與負載平衡機制”, 碩士論文, 國立中山大學電機工程研究所, 2003.
[33]H. H. Liu, M. L. Chiang, and M. C. Wu, “Efficient support for content-aware request distribution and persistent connection in Web clusters”, Software Practice & Experience, vol. 37, pp. 1215-1241, 2007.
[34]H. H. Liu and M. L. Chiang, “TCP rebuilding for content-aware request dispatching in web clusters”, Journal of Internet Technology, vol. 6, pp. 231-240, 2005.
[35]“A Multiplayer Online Role Playing Framework to develop games - The Arianne Project”, http://arianne.sourceforge.net/engine/marauroa.html, 2011.
[36]“Marauroa - Arianne wiki”, http://stendhalgame.org/wiki/Marauroa.
[37]“Second Life”, http://secondlife.com/, .2011
[38]“League of Legends”,http://lol.garena.tw/index/index.php.
[39]V. S. Pai, M. Aron, and G. Banga et al., “Locality-aware request distribution in cluster-based network servers”, SIGOPS Oper. Syst. Rev., vol. 32, no. 5, pp. 205-216, 1998.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔