淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0309200816313700
中文論文名稱 大範圍事件同步問題在同儕網路上的研究
英文論文名稱 A Research of Event-Inconsistent Problem on Large-Scale Peer-to-Peer Network.
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 96
學期 2
出版年 97
研究生中文姓名 李仁晟
研究生英文姓名 Jen-Chen Li
學號 693191651
學位類別 碩士
語文別 中文
口試日期 2008-06-11
論文頁數 48頁
口試委員 指導教授-陳瑞發
委員-王英宏
委員-簡志宇
中文關鍵字 事件不同步  事件候選人  同儕網路  主從架構  轉遞式模組 
英文關鍵字 event-inconsistent  candidate  P2P  client and server  forwarding model 
學科別分類 學科別應用科學資訊工程
中文摘要 現今網路架構中存在有主從架構與同儕網路兩大架構,主從架構的優點在於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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-09-22公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-09-22起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信