研究生: |
許力升 Li-sheng Hsu |
---|---|
論文名稱: |
針對非結構化點對點網路一個基於權重調整機率的訊息轉遞策略 An adaptively weighted probabilistic search for message forwarding in unstructured peer to peer network |
指導教授: |
楊英魁
Ying-Kuei Yang |
口試委員: |
黎碧煌
Bih-Hwang Lee 孫宗瀛 Tsung-Ying Sun 李建南 Chien-Nan Lee |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 電機工程系 Department of Electrical Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 中文 |
論文頁數: | 56 |
中文關鍵詞: | 非結構化點對點網路 、訊息轉遞 、選擇機率 、公平性指標 、轉遞廣度 |
外文關鍵詞: | transmission width, fairness index, selection probability, message forwarding, unstructured peer to peer network |
相關次數: | 點閱:292 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來點對點網路技術已經廣泛地被使用如:檔案資源分享、即時訊息及網路電視等等,然而檔案資源分享這方面的用途,在點對點網路的應用上仍為受歡迎的應用之一。現今常用的點對點檔案分享軟體如:Gnutella、Foxy及Limewire等等非結構化點對點網路,擁有良好的容錯能力及適用於高動態網路的情況,然而在檔案資源搜尋方面,常常以泛流法盲目地向所有節點傳送搜尋訊息,因此容易造成過大網路流量的問題存在。而本篇論文提出一個搜尋方法,善用龐大的搜尋訊息負擔對鄰居節點建立權重值列表,並根據權重值列表計算鄰居節點的選擇機率,適當地選擇所要轉遞的鄰居節點。為了克服權重值過於相似所造成的隨機選擇問題,本論文採用公平性指標評估權重值分佈的偏重程度,在訊息轉遞過程中適當地調整轉遞廣度。透過實驗結果得知本論文所提出的方法可以維持良好搜尋成功率,相較於泛流法而言能維持較低的搜尋負擔。
Peer to peer (P2P) network has been used widely in recent years, such as file sharing, instant message (IM), internet TV and so on, and one of popular applications is file sharing. Nowadays, many popular file sharing software, such as Gnutella, Foxy, BT, are in the topology of unstructured peer to peer network that has good fault tolerant ability and is therefore applicable to dynamic network. However, when searching resources, these software demand enormous network traffic load due to the use of flooding query. In this paper, this thesis therefore proposes an efficient search method that uses query messages to construct a weight table for each peer in a network. A mechanism is then derived to determine the selection probability of the peer’s neighbors to make good selections of next searching peers based on the information of the weight table. The fairness index is applied to evaluate weight values among neighboring peers to overcome the random selection problem possibly caused by the weight values and to properly determine the transmission width in message forwarding procedure. Our experimental results demonstrate the proposed approach can retain good success rate and lower overhead during searching procedure.
[1]Gnutella, http://gnutella.wego.com
[2]Q. Lv, P. Cao, E. Cohen, K. Li and S. Shenker, “Search and Replication in Unstructured Peer- to-Peer Networks,” Proceedings of the 16th international conference on Supercomputing, 2002.
[3]Napster homepage, http://www.napster.com
[4]BitTorrent, http://www.bittorrent.com
[5]Limewire, http://www.limewire.com
[6]I. Ricci, L. Pierre, C. Kam-Pui, K. Michael and L. Frank, “Identifying first seeders in foxy peer-to-peer networks”, Sixth IFIP WG 11.9 International Conference on Digital Forensics, pp.185-194, 2010.
[7]I. Stoica, R. Morris, D. Karger, M. F. Kaashoek and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup protocol for internet applications,” IEEE/ACM Transactions on Networking, vol.11, 2003.
[8]A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” Proc.Middleware, 2001.
[9]Z. Shen, S. Ma, J. Wang and X. Tang, “Analyzing the technologies of search algorithm based on P2P,” IC-BNMT '09. 2nd IEEE International Conference on Broadband Network & Multimedia Technology, 2009.
[10]D. S. S. Clip, “Gnutella Protocol Specification v0.4,” 2000.
[11]T. Lin, P. Lin, H. Wang and C. Chen, “Dynamic search algorithm in unstructured peer-to-peer networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, pp.654-666, 2009.
[12]D. Tsoumakos and N. Roussopoulos, “Adaptive Probabilistic Search for Peer-to-Peer Networks,” In P2P ’03: Proceedings of the 3rd International Conference on Peer-to-Peer Computing, IEEE Computer Society, 2003.
[13]G. Feng, Y. Jiang, G. Chen, and Q. Gu, “Replication strategy in unstructured peer-to-peer systems,” in Proceedings of IEEE IPDPS, pp.1-8, 2007.
[14]K. Sripanidkulchai, B. Maggs, and H. Zhang, “Efficient content location using interest-based locality in peer-to-peer systems,” in Proceedings of INFOCOM, 2003
[15]R. Jain, D. Chiu and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” Technical Report EC-TR-301, Digital institution Corporation, Hudson. MA 01749, September 16 1984.
[16]David E. Goldberg and Kalyanmoy Deb, “A Comparative Analysis of Selection Schemes Used in Genetic Algorithms,” in Proceedings of the 1st Workshop on Foundations of Genetic Algorithms, pp.69-93, July 1990.
[17]C. E. Shannon,“A Mathematical Theory of Communication,” Bell System Tech. J., vol. 27, pp. 379-423, 623-656, 1948.
[18]PeerSim, http://peersim.sourceforge.net/
[19]J. C. Chu, K. S. Labonte, and B. N. Levine, “Availability and Locality Measurements of Peer-to-Peer File Systems,” in Proc. SPIE—ITCom: Scalability and Traffic Control in IP Networks, pp.310-321, July 2002.
[20]M. Ripeanu and I. Forster, “Mapping the gnutella network:macroscopic properties of large-scale peer-to-peer systems,” First International Workshop on Peer-to-Peer Systems (IPTPS), vol.68, 2002.
[21]A. Medina, I. Matta and J. Byers, “On the origin of power laws in internet topologies,” ACM Computer Communication Review, pp.160-163, April 2000.
[22]Sabu M. Thampi and Chandra K. Sekaran, “Review of Replication Schemes for Unstructured P2P Networks,” IEEE International Advance Computing Conference, 2009.
[23]Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham and S. Shenker, “Making Gnutella-like P2P Systems Scalable,” in Proceedings of ACM SIGCOMM, 2003.
[24]S.S. Dhillon and P.V. Mieghem, “Searching with Multiple Random Walk Queries,” IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, 2007.
[25]H. Wang and T. Lin, “On Efficiency in Searching Networks,” IEEE International Conference on Computer Communications, 2005.
[26]D. Tsoumakos and N. Roussopoulos, “Analysis and Comparison of P2P Search Methods,” Proceedings of the 1st international conference on Scalable information systems, 2006.
[27]D. Tsoumakos and N. Roussopoulos, “A comparison of peer-to-peer search methods,” WebDB, 2003.
[28]B. Yang and H. Garcia-Molina, “Improving Search in Peer-to-Peer Networks,” In Proceedings of the 22nd International Conference on Distributed Computing Systems, pp.5-14, 2002.
[29]V. Dimakopoulos and E. Pitoura, “On the performance of flooding-based resource discovery,” IEEE Transactions on Parallel and Distributed Systems, vol.17, no.11, pp.1242-1252, 2006.
[30]J. Wang, Y. Li, F. Gong and W. Chen, “A New Strategy of Resource Searching in Unstructured P2P Network,” International Conference on Communication Software and Networks, IEEE Computer Society, 2010.