基于Chord查找算法的P2P系統(tǒng)研究
發(fā)布時(shí)間：2018-03-04 14:56
本文選題：Chord 切入點(diǎn)：物理拓?fù)?/strong> 出處：《北京交通大學(xué)》2014年碩士論文 論文類型：學(xué)位論文
【摘要】：Peer-to-Peer：簡稱P2P)技術(shù)的核心思想是所有參與的節(jié)點(diǎn)在地位上是平等的,各節(jié)點(diǎn)在享受來自其它節(jié)點(diǎn)服務(wù)的同時(shí)也向其它節(jié)點(diǎn)提供服務(wù)。換而言之該技術(shù)并不區(qū)分客戶機(jī)和服務(wù)器,各個(gè)節(jié)點(diǎn)不只是客戶機(jī)還是服務(wù)器,這種模式使互聯(lián)網(wǎng)中的資源被廣泛發(fā)掘和利用,已經(jīng)在各個(gè)領(lǐng)域得到了廣泛應(yīng)用。 P2P系統(tǒng)的最大挑戰(zhàn)是在沒有中心服務(wù)器的情況下,高效的查詢和資源定位。目前這方面的研究都集中在結(jié)構(gòu)化的路由算法上,其中Chord算法因簡單易實(shí)施,良好的魯棒性和擴(kuò)展性等優(yōu)點(diǎn)成為國內(nèi)外研究的熱點(diǎn)。 本文首先對P2P網(wǎng)絡(luò)的理論基礎(chǔ)進(jìn)行簡要概述,簡單分析P2P網(wǎng)絡(luò)的四種拓?fù)浣Y(jié)構(gòu),并介紹了它們的經(jīng)典模型Napster、Gnutella和KaZaa,然后介紹全分布式結(jié)構(gòu)化拓?fù)湎禄诜植际焦?DHT)技術(shù)的四種經(jīng)典資源查找算法,并著重描述了Chord查找算法。傳統(tǒng)Chord查找算法的一個(gè)明顯的缺點(diǎn),是沒有考慮P2P網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu),以致其查找過程的網(wǎng)絡(luò)延遲較大。除此之外,存儲空間的問題也很少被考慮。為彌補(bǔ)這些缺陷,本文的研究工作如下： 1.針對傳統(tǒng)Chord物理拓?fù)浜瓦壿嬐負(fù)洳黄ヅ涞膯栴},結(jié)合螞蟻優(yōu)化算法和雙向查找技術(shù)的優(yōu)點(diǎn),我們提出了一種基于螞蟻優(yōu)化算法的雙向查找Chord算法。首先,利用螞蟻優(yōu)化算法建立Chord環(huán),解決物理拓?fù)浜瓦壿嬐負(fù)洳黄ヅ涞膯栴},在此基礎(chǔ)上,使用雙向查找方法,進(jìn)一步加快查找速度。實(shí)驗(yàn)結(jié)果表明,該算法比傳統(tǒng)的Chord算法有更高的查找效率。 2.針對物理拓?fù)浜瓦壿嬐負(fù)洳黄ヅ湟约翱臻g復(fù)雜度的問題,結(jié)合Counting Bloom Filter技術(shù)和基于位置查找算法的優(yōu)點(diǎn),我們提出一種基于Counting Bloom Filter和物理拓?fù)涞腃hord查找算法。首先,Counting Bloom Filter用于數(shù)據(jù)存儲,以減少空間復(fù)雜度,然后,用基于物理拓?fù)涞姆椒?解決物理拓?fù)浜瓦壿嬐負(fù)洳黄ヅ涞膯栴},進(jìn)一步加快資源定位的速度。實(shí)驗(yàn)結(jié)果表明,該算法能夠進(jìn)一步節(jié)省存儲空間并提高查找效率。 3.在路徑長度、存儲空間、查找跳數(shù)方面,將三種方法進(jìn)行對比,驗(yàn)證兩種改進(jìn)方法各自的優(yōu)缺點(diǎn)。
[Abstract]:The core idea of Peer-to-Peer (P2P) technology is that all participating nodes are equal in status, each node provides services to other nodes while enjoying services from other nodes. In other words, the technology does not distinguish between client and server. Each node is not only a client or a server, this pattern makes the resources in the Internet widely explored and utilized, and has been widely used in various fields. The biggest challenge of P2P systems is to efficiently query and locate resources without a central server. At present, the research in this area is focused on structured routing algorithms, in which Chord algorithm is simple and easy to implement. Good robustness and expansibility have become the focus of research at home and abroad. First of all, this paper gives a brief overview of the theoretical basis of P2P network, and briefly analyzes the four kinds of topology structure of P2P network. This paper also introduces their classical models, Napstern Gnutella and Kazaa, and then introduces four classical resource lookup algorithms based on distributed hash DHT technology in a fully distributed structured topology. This paper mainly describes the Chord lookup algorithm. One obvious disadvantage of the traditional Chord lookup algorithm is that it does not consider the physical topology of the P2P network, resulting in a large network delay in the lookup process. The problem of storage space is rarely considered. In order to make up for these defects, the research work of this paper is as follows:. 1. Aiming at the mismatch of traditional Chord physical topology and logical topology, combining the advantages of ant optimization algorithm and bidirectional lookup technique, we propose a bidirectional lookup Chord algorithm based on ant optimization algorithm. Ant optimization algorithm is used to establish Chord ring to solve the problem of physical topology and logical topology mismatch. On this basis, bidirectional search method is used to further accelerate the search speed. The experimental results show that, The algorithm is more efficient than the traditional Chord algorithm. 2. Aiming at the problem of physical topology and logical topology mismatch and space complexity, combining the advantages of Counting Bloom Filter technology and location-based search algorithm, We propose a Chord lookup algorithm based on Counting Bloom Filter and physical topology. First, count Bloom Filter is used for data storage to reduce the space complexity. Then, the problem of physical topology and logical topology mismatch is solved by the method based on physical topology. Experimental results show that the proposed algorithm can further save storage space and improve the efficiency of searching. 3. In the aspect of path length, storage space and search hops, the advantages and disadvantages of the two improved methods are verified by comparing the three methods.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.02
【參考文獻(xiàn)】
相關(guān)期刊論文 前1條
1 邱彤慶;陳貴海;;一種令P2P覆蓋網(wǎng)絡(luò)拓?fù)湎嚓P(guān)的通用方法[J];軟件學(xué)報(bào);2007年02期
，本文編號：1566115
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/1566115.html
最近更新
教材專著
