基于分布式De Brujin圖的P2P覆蓋網(wǎng)設(shè)計(jì)與分析.pdf

1、對(duì)等網(wǎng)絡(luò)(Peer—to—Peer Networks，簡(jiǎn)稱(chēng)P2P網(wǎng)絡(luò))是采用對(duì)等模式工作的計(jì)算機(jī)網(wǎng)絡(luò)，是分布式系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)相結(jié)合的產(chǎn)物．目前，P2P網(wǎng)絡(luò)已經(jīng)被廣泛應(yīng)用于Internet環(huán)境下的文件共享中．在P2P網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)在功能上是平等的，在行為上是自由的，在連接上是互聯(lián)的，打破了傳統(tǒng)的客戶/服務(wù)器模式，讓一切網(wǎng)絡(luò)結(jié)點(diǎn)享有平等、自由、互聯(lián)的功能，不再有客戶、服務(wù)器之分，任何兩個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)之間都能共享文件、傳遞信息．因此，它能夠極

2、大程度地提高網(wǎng)絡(luò)效率、充分利用網(wǎng)絡(luò)帶寬、開(kāi)發(fā)了每個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)的潛力，具有非常高的擴(kuò)展性和容錯(cuò)性．這使得P2P技術(shù)迅速發(fā)展成為計(jì)算機(jī)網(wǎng)絡(luò)的一項(xiàng)重要技術(shù)，在應(yīng)用領(lǐng)域和學(xué)術(shù)界獲得了廣泛的重視．由于它占據(jù)了當(dāng)前Internet超過(guò)一半的帶寬資源，被認(rèn)為是“改變Internet的新一代網(wǎng)絡(luò)技術(shù)”． P2P網(wǎng)絡(luò)高效的一個(gè)重要原因是它在網(wǎng)絡(luò)應(yīng)用層上構(gòu)建了一個(gè)有嚴(yán)格拓?fù)浣Y(jié)構(gòu)的覆蓋網(wǎng)絡(luò)．從設(shè)計(jì)思想和體系結(jié)構(gòu)來(lái)看，P2P覆蓋網(wǎng)絡(luò)的研究可分為結(jié)構(gòu)化和

3、非結(jié)構(gòu)化兩種，它們有各自的優(yōu)缺點(diǎn)．本論文的研究是基于結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)，結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)是基于分布式哈希表(DHT)來(lái)準(zhǔn)確、快速地路由信息和定位數(shù)據(jù)對(duì)象．針對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)涞难芯堪l(fā)現(xiàn)，構(gòu)造的P2P系統(tǒng)性能在很大程度上與該P(yáng)2P系統(tǒng)底層所依據(jù)的靜態(tài)圖的性質(zhì)有關(guān)，因此在學(xué)術(shù)界對(duì)于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的研究，可根據(jù)底層所依據(jù)的靜態(tài)圖形不同，分為常數(shù)度DHT和非常數(shù)度DHT．近年來(lái)，對(duì)于常數(shù)度DHT的研究已經(jīng)引起了學(xué)術(shù)界的高度重視，尤其

4、是對(duì)于平均路由長(zhǎng)度與路由表規(guī)模的折衷方面的研究．常數(shù)度DHT通常是基于一定的常數(shù)度靜態(tài)圖來(lái)構(gòu)造的，例如：CAN是基于d—維環(huán)面的；Viceroy是基于蝶形圖；D2B和Koorde都是依賴于De Brujin有向圖的；FissonE和Moore都是建立在靜態(tài)Kautz圖上的．這些基于常數(shù)度靜態(tài)圖構(gòu)造的P2P系統(tǒng)，其性能不僅在某些方面優(yōu)于非常數(shù)度P2P系統(tǒng)，而且在很大程度上與其所依賴的靜態(tài)圖的性質(zhì)有關(guān)，因此從圖論的角度來(lái)研究P2P系統(tǒng)成為一

5、種行之有效的方法． 本論文首先從圖論的角度入手研究P2P系統(tǒng)，提出了另一種常數(shù)度結(jié)構(gòu)化的P2P覆蓋網(wǎng)絡(luò)協(xié)議，它是基于De Brujin有向圖的．此系統(tǒng)首先對(duì)De Brujin有向圖進(jìn)行修改，然后把分布式線圖技術(shù)應(yīng)用于修改后的De Brujin有向圖，而得到的一種新的P2P協(xié)議—DDBG(Distributed De Brujin Graph)協(xié)議．該協(xié)議融合了De Brujin有向圖和環(huán)的優(yōu)點(diǎn)，使得結(jié)點(diǎn)的動(dòng)態(tài)加入和離開(kāi)過(guò)程更加方

6、便，提高了網(wǎng)絡(luò)的容錯(cuò)性和自由度，具有很高的可用性．其次從圖論與系統(tǒng)拓?fù)湎嘟Y(jié)合的角度，針對(duì)現(xiàn)有的結(jié)構(gòu)化P2P系統(tǒng)和本論文構(gòu)造的P2P系統(tǒng)，提出了一種基于圖論的結(jié)構(gòu)化P2P系統(tǒng)理論分析的通用框架，使圖的性質(zhì)與P2P系統(tǒng)的性能更加合理地聯(lián)系在一起，為以后構(gòu)造結(jié)構(gòu)化P2P系統(tǒng)提供了有利的理論指導(dǎo)． 本文共分為五章． 第一章簡(jiǎn)要介紹了P2P網(wǎng)絡(luò)、P2P網(wǎng)絡(luò)的發(fā)展及現(xiàn)狀，P2P網(wǎng)絡(luò)的核心機(jī)制與增強(qiáng)機(jī)制，及論文的研究?jī)?nèi)容等．