現今網路架構中存在有主從架構與同儕網路兩大架構，主從架構的優點在於virtual world中的事件，都是以server來決定事件的發生順序，所以不會出現事件不同步問題，主從架構缺點在於server是一個瓶頸，當server fail後會造成整個網路失敗。在同儕網路架構下所建構的virtual world，缺點是會存在事件不同步的問題，此外當P2P網路中peer個數增加後，會使得整體網路流量大幅度增加。
本篇論文著手解決在大範圍事件發生後，由最靠近目標的avatar成為本次事件的代理人，透過forwarding model discover所有的leader候選人，最後採用forwarding method選舉出leader，將P2P網路架構轉換成主從架構，來同時解決網路流量過高與事件不同步問題。

There are two major architectures in network, first is P2P and the other is client/server. The advantage of client/server is that server can determine the event ordering therefore, there without any event inconsistent problem. The disadvantage of client/server is that the server is a bottleneck, when the server was failed would cause the whole network fail. In P2P there is no server, every peer communicates to each other and share information. But the problem is that when the peers are increased, it would cause the whole network traffic increased, there also exists the event-inconsistent problem.
In this thesis, when the event is triggered, then the avatar who is most closest to target would become the agent of this event. The agent will discover the leader’s candidates. Finally we use forwarding method to elect a leader and transform P2P to client and server to solve heavy traffic problems and the event-inconsistent.

1.	緒論	1
1.1.	研究動機	1
1.2.	研究目的	2
1.3.	論文架構	2
2.	相關研究	3
2.1.	目前網路上常見的問題	3
2.2.	兩種Event Inconsistent問題	4
2.3.	三種Load-Balance演算法	10
2.3.1.	Forward演算法	10
2.3.2.	Reverse演算法	11
2.3.3.	Symmetric演算法	12
2.4.	Client and Server與P2P的比較	13
3.	系統架構	17
3.1.	大範圍事件之判斷條件	17
3.2.	系統架構	19
3.3.	如何Discover所有候選人	24
3.4.	Leader選舉方式	29
4.	大範圍事件Leader選舉之例子	32
4.1.	最先事件觸發之avatar與最靠近目標之avatar	32
4.2.	discover候選人	33
4.3.	選舉leader	35
5.	結論	37
5.1.	判斷大範圍事件降低網路流量	37
5.2.	事件不同步問題之解決	37
5.3.	未來發展	37
相關文獻	39
附錄一:英文論文 41

圖表目錄
圖2-1(a)  未發生event-inconsistent示意圖	5
圖2-1(b)  發生event-inconsistent示意圖	5
圖2-2(a)  坦克發射砲彈	7
圖2-2(b) 碉堡爆炸…………………………………………………… …7
圖2-3(a)  碉堡先爆炸沒看到坦克發射砲彈	7
圖2-3(a)  最後坦克發射砲彈	7
圖2-4  網路上封包因為delay而產生inconsistent示意圖	8
圖2-5  只看到碉堡爆炸，卻沒有看到坦克發射	9
圖2-6  Client and Server流量圖	15
圖2-7  P2P流量圖	15
圖2-8  client and server與P2P架構所需要的頻寬比較……………....16
圖3-1(a)  client and server與P2P架構所需要的頻寬	18
圖3-1(b)  client and server與P2P架構所需要的頻寬	18
圖3-2  Leader候選人示意圖	21
圖3-3(a)  Forward示意圖(1)	25
圖3-3(b)  Forward示意圖(2)	26
圖3-3(c)  Forward示意圖(3)	26
圖3-4  Forwarding Path示意圖	27
圖3-5  Leader候選人Tasks加權圖	29
圖4-1  範例圖	32
圖4-2  範例之Forward示意圖(1)	34
圖4-3  範例之Forward示意圖(2)	34
圖4-4  範例之Forwarding Path示意圖	35


表2-1  Algorithm of Forwarding Method 16
表3-1  資料結構	23
表3-2  Algorithm of discover_leader	23
表3-3  Algorithm of Discover	23
表3-4  Algorithm of return_candidate	24
表3-5  Algorithm of electing	28

[Cao 97]	P. Cao and C. Liu, “Maintaining Strong Cache Consistency in the World-Wide Web”, Proc. of ICDCSP7, Pages: 12-21, May 1997.
[ Cate 92]	V. Cate, Alex “ A Global File System”, Proceedings of the 1992 USENIX File System Workshop, Pages: l- 12, May 1992.
[Chen 06]	T. H. Chen, “A Forwarding Model on P2P Networked Virtual World,” Master’s thesis, Tamkang Univ., Taiwan, 2006.
[Drew 94]	P. M. Dew, and M. Kara, “A Periodic Symmetrically-Initiated Load Balancing Algorithm for Distributed Systems.” Distributed Computing Systems, 1994., Proceedings of  the 14th International Conference on Pages:616 – 623,1994
[Gautier 99]	Gautier, L.; Diot, C.; Kurose, J.; INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Page(s):1470 – 1479, 1999
[Hu 05]	Shun-Yun. Hu, “Scalable peer-to-peer networked virtual environment,” Master’s thesis, Tamkang Univ., Taiwan, 2005.
[Lamport 78]	Lamport, “Time, Clocks, and the Ordering the Events in a Distributed System”, Communications of the ACM, Volume.21, No.7, Pages:558-565, July 1978
[Lamport 79]	Lamport,, “How to make a Multiprocessor Computer that correctly executes Multiprocess Programs”, IEEE Transactions on Computer Systems, Pages: 690-691, 1979.
[Schwarz 94]	Schwarz, R., and Mattern E, “Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail,” Distributed Computing, Pages: 149-174, 1994
[Torres-Rojas 99]	Francisco J. Torres-Rojas , Mustaque Ahamad , Michel Raynal, Timed consistency for shared distributed objects, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, Pages:163-172, Atlanta, Georgia, United States, 1999 

[Zhou 02]	Suiping Zhou , Wentong Cai , Stephen J. Turner , Francis B. S. Lee, Critical causality in distributed virtual environments, Proceedings of the sixteenth workshop on Parallel and distributed simulation, Washington, D.C, May 12-15, 2002.