以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究

On Neighbor Consistency for Voronoi-Diagram-Based P2P Networked Virtual Environments

邱俊翔(Jiun-Shiang Chiou)

指導教授 ： 江振瑞

國立中央大學/資訊電機學院/資訊工程學系/碩士(2006年)

摘要

網路虛擬環境(Networked Virtual Environments, NVEs)近來變得越來越普及，例如多人線上遊戲(Massive Multiplayer Online Games, MMOGs)就是一個例子。傳統的網路虛擬環境使用主從(client/server)架構，然而因為伺服器的資源是有限的，這種架構無法容納大量的使用者。為了能在同一時間容納更多的使用者，使用對等式(peer-to-peer, P2P)架構是一種可行的解決方法。這種系統藉由分散負荷至所有的參與者可以在同一時間容納超過百萬的使用者。雖然對等式網路虛擬環境可以解決規模可變性(scalability)問題，但是其他如一致性這樣的問題也隨之產生。在這篇論文中，我們將重點放在相鄰節點一致性(neighbor consistency)的研究。相鄰節點一致性可以被視為在可視區域(area of interest, AOI)內觀察到的節點與實際上的節點的比例。我們假設底層的覆疊網路是擁有良好相鄰節點一致性的VON網路(Voronoi-based overlay network)。我們指出在此網路上影響相鄰節點一致性的三個因素，分別為封包遺失(packet loss)，移動性(mobility)與節點故障(node failure)。我們並提出可調整可視範圍緩衝區(adaptive AOI buffer)與關鍵節點偵測(critical node detection)來改善上列因素對於相鄰節點一致性的影響。我們並執行模擬以顯示在採用所提方法之前與之後，上列因素所產生的影響。

關鍵字

網路虛擬環境 ； 多人線上遊戲 ； 對等式 ； 規模可變性 ； 相鄰節點一致性 ； 以范諾圖為基礎的覆疊網路 ； 可視範圍

並列摘要

Networked Virtual Environments (NVEs) such as Massive Multiplayer Online Games (MMOGs) are getting more and more popular in recent years. NVEs are implemented by client/server architecture traditionally but do not scale well due to the limitation of server resources. To increase the scalability, another solution, peer-to-peer (P2P) architecture, is recently proposed. P2P NVE can potentially achieve better scalability with an extremely large number of users (e.g. over one million) by distributing the server load to all participants. Although P2P NVE can potentially solve the scalability issues, other important issues such as consistency remain unexplored. In this thesis, we focus on neighbor consistency, which is the ratio between the number of known nodes and the number of actual nodes within a node''s area of interest (AOI). We assume the underlying overlay is Voronoi-based Overlay Network (VON), which can achieve good neighbor consistency. We address three factors that affect neighbor consistency for such a network, namely, packet loss, mobility and node failure. We propose the adaptive AOI buffer and the critical node detection mechanisms to reduce the negative impacts of those factors on neighbor consistency. We also perform simulation to demonstrate the effects of those factors before and after adopting the proposed mechanisms.

並列關鍵字

Networked virtual environment (NVE) ； Voronoi-based overlay network (VON) ； massive multiplayer online game (MMOG) ； peer-to-peer (P2P) ； scalability ； neighbor consistency ； area of interest (AOI)

參考文獻

[A91] F. Aurenhammer, “Voronoi diagrams—a survey of a fundamental geometric data structure,” ACM Computing Surveys (CSUR), vol. 23, no. 3, pp. 345-405, 1991.

[DG99] C. Diot and L. Gautier, “A distributed architecture for multiplayer interactive applications on the Internet,” IEEE Network, vol. 13, no. 4, pp. 6-15, 1999.

[HCC06] Shun-Yun Hu, Jui-Fa Chen and Tsu-Han Chen, "VON: A scalable peer-to-peer network for virtual environments," IEEE Network (accepted pending minor revision), 2006.

[KAM04] Y. Kawahara, T. Aoyama, and H. Morikawa, “A peer-to-peer message exchange scheme for large-scale networked virtual environments,” Telecomm. Sys., vol. 25, no. 3-4, pp. 353–370, 2004.

[LNS02] J. Liebeherr, M. Nahas and W. Si, "Application-layer Multicasting with Delaunay Triangulation Overlays," IEEE JSAC, vol. 20, no. 8, pp. 1472-1488, 2002.