臺灣博碩士論文加值系統

點對點(Peer to Peer , P2P)網路是一個新的分散式架構，其分散式的架構環境，讓每個節點可以自由的搜尋與儲存、分享資料與檔案。其特色在於，每個節點皆能當做提供者(Server)與使用者(Clint)的的角色，可以主動的儲存資料、分享資料，搜尋檔案等，打破過去傳統的提供者-使用者分開的架構。
點對點網路其搜尋方法主要有兩種方式，Gnutella與DHT(Distributed Hash Table)的方式，使用Gnutella的方式就是利用氾流(Flooding)去詢問所有的節點，它的方法簡單，缺點是訊息會會大量的產生且漫無目的傳送，造成網路訊息流量大增與增加延遲時間，較無效率；而DHT的方法則必須事先提供一套資料與位址對應機制，搜尋與儲存較有條理與規則可依循，但必須增加額外的記憶空間，並要隨時動態地做更新與維持DHT。
在此篇論文中我們試著提出一個新的方法以改善Gnutella，我們使用選擇性詢問去改進搜尋表現，我們期望藉由選擇連接、節點、架構來增加搜尋效率，因此我們提出一套解決方案，整合捷徑(Shortcut)、評價模式(Reputation)、樹狀架構(Tree structure)等，首先依照興趣基礎(Interest-Based)分類好群組方便我們做搜尋，讓我們的搜尋動作有所範圍，而不是用泛流大量而無效率的搜尋。我們以節點的評價為依據，以評價最高的節點為樹根(Root)，依評價高低依序建立成以捷徑為基礎的樹(Shortcut-based Tree)，節點評價越高則位於樹的越上層，也越先搜尋，節點評價越低則位於樹的越下層，也越後搜尋，因此希望能在有限範圍內的搜尋，而搜尋的順序是有依據的，讓節點搜尋到的機率能最大，時間能最短。配合5種Gnutella模式的模擬實驗結果，驗證我們的以捷徑為基礎的樹狀架構是可行的。

Peer-to-Peer (P2P) Networking is a new infrastructure used for distributed network applications. The most popular P2P file sharing system is Gnutella that uses flooding to query all peers. Although flooding is a simple approach, it is inefficient due to its increase of message overhead and latency time. In this paper, we propose “selective query” to improve search performance in Gnutella. In our approach, query messages are restrictedly forwarded to selected peers rather than to be flooded to all peers. We incorporate interest-based locality to limit querying scope. Search latency was reduced by establishing a shortcut-based tree based on the reputation scores of peers. In any event, if a peer has a higher reputation, it is allocated to the upper level of the tree. Thus the peer is queried earlier in order. That improves the efficiency of query and decreases the amount of query messages. We evaluate our simulation by five diverse content distribution applications. Simulation results show that shortcut-based trees increase the query success rate, and the proposed method takes less time to obtain the query results.

1. Introduction…..……..…………………………………………..……1
1.1. Motivation…….…….….....................………………………1
1.2. Thesis Organization.......…….…….…....………………………3
2. Related works………………………………………………………...4
2.1. Random walk…….…….….....................………………………4
2.2. Tree-based structure………….........……………………………4
2.3. Reputation mechanism………….…....……….………………..5
2.4 Interest-based groups..................................................................5
2.5 Interest-based shortcuts.............................................................6
3. Proposed Mechinism…………………........…………………………7
3.1. Applying Interest-Based Shortcuts……………...........………..7
3.2. Applying The Reputation Mechanism……...……....…………..8
3.3. Establishing Shortcut Trees….……………………………….11
3.4. Comparison of Shortcuts and Shortcut Trees………………15
3.5. Ring-Shortcut Trees...................................................................17
4. Simulation experiment and Results…….................................….…23
4.1. Simulation experiment model…………....................................23
4.2. Simulation environment….……………..…………………….24
4.3. Simulation Evaluation…………………..............................….24
4.4. Simulation result……………….…......……………………….24
5. Conclusions and Future Work………..…………………………….28
References………………………………………………………………30

[1] Napster, http//www.napster.com
[2] Gnutella, http://gnutella.wego.com
[3] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A scalable content-addressable network,” in Proc. of ACM SIGCOMM,2001.
[4] A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” in IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001.
[5] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for Internet applications,”in Proc. of ACM SIGCOMM, 2001.
[6] B. Zhao, J. Kubiatowicz, and A. Joseph, “Tapestry: An infrastructure for wide-area fault-tolerant location and routing,” U. C. Berkeley Technical Report UCB//CSD-01-1141,2001
[7] H.C.Hsiao and C.T.King, “Tornado: Capability-Aware Storage Networks”Proc.Int’l Conf. On Parallel and Distributed Processing Symposium(IPDPS 2003),Apr.2003
[8] C.Hang and K.C.Sia. “Peer Clustering and Firework Query Model”. 12th World-Wide-Web Conference.
[9] B. Yang and H. Garcia-Molina. Efficient search in pnternational Conference on Distributed Computing Seer-to-peer networks. In Proceedings of the 22nd IEEE Iystems (ICDCS), 2002.
[10] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In Proceedings of the 16th annual ACM International Conference on supercomputing, 2002.
[11] S. Jiang and X. Zhang, “FloodTrail: an Efficient File Search Technique in Unstructured Peer-to-Peer Systems”Proceedings of 2003 IEEE Globecom Confernece, (Globecom’03), San Fransisco, California, USA, December 1-5, 2003.
[12] S. Jiang and X. Zhang, “LighFlood: an efficient flooding scheme for file search in unstructured peer-to-peer systems, Proceedings of 2003 International Conference on Parallel Processing, (ICPP’03), October, 2003.
[13] Qixiang Sun, Hector Garcia-molina, ”SLIC: A Selfish Link-based Incentive Mechanism for Unstructureed Peer-to-Peer Networks” Proceedings of the 24th International Conference on Distributed Computing Systems(ICDCS’04) IEEE.
[14] K. Aberer and Z. Despotovic. Managing trust in a peer-to-peer information system. In International Conference on Information and Knowledge Management (CIKM), 2001.
[15] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The eigentrust algorithm for reputation management in 12th p2p networks. In International WWW Conference, 2003.
[16] Minaxi Gupta, Paul Judge, Mostafa Ammar,” A Reputation System for Peer-to-Peer Networks” NOSSDAV’03, June 2003, ACM.
[17] Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, Piescopela Samarati, Fabio Violante,“A Reputation-Based Approach for Choosing Reliable Resources in Peer-to-Peer Networks” CCS’02, November ,2002,ACM.
[18] Mujtaba Khambatti, Kyung Dong Ryu, and Partha Dasgupta ”Structuring Peer-to-Peer Networks Using Interest-Based Communities” International
Workshop On Databases, Information Systems and Peer-to-Peer Computing (P2PDBIS), Humboldt University, Berlin, Germany, September 2003
[19] Kunwadee Sripanidkulchai , Bruce Maggs , Hui Zhang “Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems” IEEE INFOCOM 2003.
[20] Jian Yang, Yiping Zhong, Shiyong Zhang , “An Efficient Interest-Group Based Search Mechanism in Unstructured Peer-to-Peer Networks” 2003 International Conference on Computer Networks and Mobile Computing (ICCNMC'03)
[21] M.K.Ramanathan, V.Kalogeraki and J.Pruyne. “Finding Good Peers in Peerto-Peer Networks”. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS’02).
[22] Bobby Bhattacharjee and Sudarshan Chawathe and Vijay Gopalakrishnan and Pete Keleher and Bujor Silaghi", ”Efficient Peer-To-Peer Searches Using Result-Caching",The 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03).
[23] Mihajlo A. Jovanovic, Fred S. Annexstein, Kenneth A. Berman, “Modeling Peer-toPeer Network Topologies Through “Small-World”Models and Power Laws”IX Telecommunications Forum Telfor 2001, Belgrade. ”
[24] Markus Junginger, Yugyung Lee “The Multi-Ring Topology-High-Performance Group Communicaion in Peer-to-Peer Networks” Proceedings of the Second International Conference on Peer-to-Peer Computing (P2P’02)