基于優(yōu)化Kademlia協(xié)議的P2P網(wǎng)絡(luò)資源發(fā)現(xiàn)算法研究

◆徐衛(wèi)克

（中國(guó)社會(huì)科學(xué)院大學(xué) 北京 102488）

與以往集中型客戶端模式對(duì)比，P2P 網(wǎng)絡(luò)的優(yōu)勢(shì)在于數(shù)據(jù)共享可在節(jié)點(diǎn)間開(kāi)展。因P2P 技術(shù)無(wú)須中央控制器支持，整個(gè)文件交換不受其他因素干預(yù)。受該技術(shù)去中心化特性影響，P2P 網(wǎng)絡(luò)傳輸中資源很難被追蹤監(jiān)管，很容易導(dǎo)致盜版文件、非法傳播等網(wǎng)絡(luò)安全問(wèn)題。對(duì)此，應(yīng)在Kademlia 協(xié)議基礎(chǔ)上采用DHT 技術(shù)控制非法內(nèi)容傳播，使合法內(nèi)容傳播安全得到切實(shí)保障。

1 Kademlia 協(xié)議概述

該協(xié)議中節(jié)點(diǎn)間可相互通信，無(wú)須中央控制器支持。多個(gè)節(jié)點(diǎn)構(gòu)成分布式網(wǎng)絡(luò)，網(wǎng)絡(luò)中任意節(jié)點(diǎn)均可在網(wǎng)絡(luò)中采集資源。在該協(xié)議基礎(chǔ)上，各個(gè)DHT 節(jié)點(diǎn)均由三項(xiàng)內(nèi)容組成，即IP 地址、端口與節(jié)點(diǎn)ID。其中，節(jié)點(diǎn)ID 是節(jié)點(diǎn)IP 地址與端口經(jīng)過(guò)SHA-1 算法散列后得出，各個(gè)節(jié)點(diǎn)信息都會(huì)存儲(chǔ)到路由表中，且任何2 個(gè)節(jié)點(diǎn)之間的距離可通過(guò)節(jié)點(diǎn)ID 的異來(lái)表示。

1.1 節(jié)點(diǎn)路由表

在該協(xié)議中，各個(gè)節(jié)點(diǎn)在初始狀態(tài)下被分配成一個(gè)160 位的節(jié)點(diǎn)ID，節(jié)點(diǎn)之間距離可通過(guò)計(jì)算得出，公式為：

Distance（A，B）＝IDAXORIDB

式中，IDA 與IDB 分別代表的是節(jié)點(diǎn)A 和B 的節(jié)點(diǎn)ID。節(jié)點(diǎn)之間ID 異是長(zhǎng)度為160 的比特?cái)?shù)組。節(jié)點(diǎn)之間邏輯距離計(jì)算可打破地域上的距離限制，使邏輯距離變得更加貼近。路由表由K 桶列表構(gòu)成，對(duì)于任意編號(hào)為i 的桶而言，各個(gè)節(jié)點(diǎn)均存儲(chǔ)到與自身相距2i距離的節(jié)點(diǎn)信息中。路由表中的節(jié)點(diǎn)可根據(jù)距離不同而分層，如若結(jié)果數(shù)組由倒數(shù)第i 位開(kāi)始并非為0，該節(jié)點(diǎn)存儲(chǔ)在該節(jié)點(diǎn)路由表的第i 層中。路由表可根據(jù)節(jié)點(diǎn)間距離分成160 層，第i 層中無(wú)法存儲(chǔ)全部節(jié)點(diǎn)，只能將與自身距離最近的節(jié)點(diǎn)存入其中，最多可納入2i 個(gè)節(jié)點(diǎn)[1]。

1.2 自組織

該協(xié)議中的自組織包括節(jié)點(diǎn)加入與退出兩項(xiàng)內(nèi)容，對(duì)于一個(gè)新節(jié)點(diǎn)來(lái)說(shuō)，在首次加入Kademlia 網(wǎng)絡(luò)時(shí)應(yīng)經(jīng)歷以下流程。首先，獲取一個(gè)網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)信息，即引導(dǎo)節(jié)點(diǎn)，計(jì)算二者間的邏輯距離，將其納入與之相對(duì)的K 桶中；然后將FIND_NODE 請(qǐng)求發(fā)送到該節(jié)點(diǎn)中，由此尋找與自身距離相近的節(jié)點(diǎn)，最后使全部k 桶被刷新。通過(guò)與自身距離由近到遠(yuǎn)節(jié)點(diǎn)的逐一查詢，新節(jié)點(diǎn)采集的信息不斷增加，在刷新K 桶的同時(shí)，也將自身信息留在了其他K 桶中。節(jié)點(diǎn)在退出網(wǎng)絡(luò)時(shí)無(wú)須發(fā)送任意信息，因?yàn)楦鱾€(gè)資源都會(huì)發(fā)布k 個(gè)副本，因此不會(huì)對(duì)該節(jié)點(diǎn)所有資源產(chǎn)生負(fù)面影響。此外，該協(xié)議還要求各節(jié)點(diǎn)定期發(fā)布自己的數(shù)據(jù)，再將數(shù)據(jù)存儲(chǔ)到與自己相距最近的鄰居位置，鄰居同時(shí)失效的概率較低，這樣可保障某個(gè)節(jié)點(diǎn)失效時(shí)不會(huì)對(duì)其他節(jié)點(diǎn)產(chǎn)生影響，進(jìn)而出現(xiàn)資源無(wú)法查詢等情況。

1.3 資源定位

對(duì)于任意資源來(lái)說(shuō)，HASH 長(zhǎng)度為160 比特?cái)?shù)組，通過(guò)算法對(duì)資源與節(jié)點(diǎn)間的距離進(jìn)行計(jì)算。在對(duì)特定資源進(jìn)行查詢時(shí)，可以資源HASH 為依據(jù)，向與之距離最近的節(jié)點(diǎn)發(fā)出詢問(wèn)，判斷其是否了解那些節(jié)點(diǎn)中帶有所需資源，如若結(jié)果為“不知”，則返回到最可能知道誰(shuí)擁有所需資源的節(jié)點(diǎn)列表中。在對(duì)基礎(chǔ)節(jié)點(diǎn)資源進(jìn)行查詢時(shí)，如若起初就知道帶有該資源的節(jié)點(diǎn)，便可直接返回該節(jié)點(diǎn)中，如若不知誰(shuí)擁有該資源，可采取以下措施進(jìn)行資源定位。對(duì)基礎(chǔ)節(jié)點(diǎn)與HASH 間的邏輯距離進(jìn)行計(jì)算，根據(jù)結(jié)果得出資源處于路由表中的第K 層；在K 層中獲取所需節(jié)點(diǎn)信息后，如若數(shù)量不足則要從相鄰層中采集，再對(duì)該節(jié)點(diǎn)實(shí)施異步查詢；如若被查詢節(jié)點(diǎn)知曉帶有所需資源的節(jié)點(diǎn)，則會(huì)呈現(xiàn)帶有資源的節(jié)點(diǎn)信息，反之，則會(huì)將表中與HASH 值最為接近的節(jié)點(diǎn)信息提供出來(lái)；基礎(chǔ)節(jié)點(diǎn)對(duì)信息進(jìn)行更新，并對(duì)其他節(jié)點(diǎn)實(shí)施異步查詢操作；反復(fù)上述內(nèi)容，直至獲取帶有所需資源的目標(biāo)節(jié)點(diǎn)[2]。

2 P2P 網(wǎng)絡(luò)技術(shù)的主要性能

根據(jù)拓?fù)浣Y(jié)構(gòu)的不同，可將P2P 系統(tǒng)分成全分布式、集中式、非結(jié)構(gòu)化、半分布式四種類型。其中，集中式拓?fù)湟訬apster 為主，通過(guò)中央處理器存儲(chǔ)網(wǎng)絡(luò)中全部節(jié)點(diǎn)用戶信息，使文件查詢與傳輸相互獨(dú)立。全分布式以Gnutella 系統(tǒng)為代表，屬于純P2P 系統(tǒng)，無(wú)中心服務(wù)器，在完全隨機(jī)圖基礎(chǔ)上發(fā)覺(jué)和轉(zhuǎn)發(fā)資源；半分布式網(wǎng)絡(luò)可解決非結(jié)構(gòu)模型中資源發(fā)現(xiàn)效率低等問(wèn)題，在DHT 基礎(chǔ)上創(chuàng)建分布式網(wǎng)絡(luò)，可自適應(yīng)節(jié)點(diǎn)的加入與退出，具有較強(qiáng)的安全性、穩(wěn)健性，成為P2P 系統(tǒng)的主流發(fā)展趨勢(shì)。半分布式拓?fù)淇蓪⒓惺?、全分布式拓?fù)涮攸c(diǎn)整合起來(lái)，將超級(jí)節(jié)點(diǎn)概念加入其中，在此基礎(chǔ)上呈現(xiàn)個(gè)別節(jié)點(diǎn)信息，在超級(jí)節(jié)點(diǎn)間轉(zhuǎn)發(fā)分享，再將查詢請(qǐng)求傳遞到普通節(jié)點(diǎn)。在DHT 基礎(chǔ)上的全結(jié)構(gòu)化網(wǎng)絡(luò)作為PAP 發(fā)展的新路徑，性能優(yōu)良。其中，路徑長(zhǎng)度代表的是目標(biāo)請(qǐng)求在P2P 中的平均跳數(shù)；路由表長(zhǎng)度為各個(gè)節(jié)點(diǎn)所需維護(hù)的表項(xiàng)數(shù)，如表1所示。表中，N 代表的是P2P 網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)值；d 代表的拓?fù)渚S數(shù)；b 代表的是ID 空間基。在上述系統(tǒng)中，Kademlia 協(xié)議得到廣泛應(yīng)用，且主流P2P 軟件均可作為輔助檢索協(xié)議投入使用。

表1 DHT 方案性能對(duì)比

3 Kademlia 協(xié)議下P2P 網(wǎng)絡(luò)資源發(fā)現(xiàn)算法分析

在Kademlia 協(xié)議中，資源請(qǐng)求信息會(huì)率先傳遞到路由表中與資源距離最近的節(jié)點(diǎn)。因節(jié)點(diǎn)ID 具有不確定性，無(wú)法對(duì)節(jié)點(diǎn)在表中所處層級(jí)進(jìn)行控制，導(dǎo)致節(jié)點(diǎn)可接收的資源請(qǐng)求較為有限，需要通過(guò)仿真算法的方式進(jìn)行改進(jìn)，使P2P 網(wǎng)絡(luò)資源發(fā)掘與采集更加準(zhǔn)確全面。

3.1 仿真環(huán)境

該試驗(yàn)的仿真環(huán)境如下，采用主頻為1.73G 的雙核CPU，1G 內(nèi)存筆記本，在XP 系統(tǒng)中安裝VMware 虛擬機(jī)，在D 盤中分配4G 空間，在Fedora 內(nèi)核中安裝Linux 操作系統(tǒng)。以Kademlia 協(xié)議為例對(duì)P2P 網(wǎng)絡(luò)資源發(fā)現(xiàn)算法仿真過(guò)程進(jìn)行分析，在正式仿真之前，需要先寫topology.txt 文件，該文件中包含仿真網(wǎng)絡(luò)拓?fù)鋮?shù)，具體的仿真流程如下[3]。

3.2 仿真流程

3.2.1 資源搜索信息量

節(jié)點(diǎn)率先將資源檢索信息傳遞到表中與資源相距最近的點(diǎn)，任何節(jié)點(diǎn)與資源間的距離均可通過(guò)異或運(yùn)算來(lái)獲取，節(jié)點(diǎn)與資源間的邏輯距離可用以下公式計(jì)算，公式為：

Distance（A，B）＝IDAXOR HASHa

式中，IDA 代表的是節(jié)點(diǎn)A 的節(jié)點(diǎn)ID；HASHa 代表的是資源a的HASH 值。通過(guò)節(jié)點(diǎn)與資源間的距離，可將資源記錄在表中相應(yīng)層內(nèi)。路由表各層資源數(shù)量與層間關(guān)系可由以下公式計(jì)算，即：

Zi＝2i

式中，i 代表的是資源存儲(chǔ)在表中的層數(shù)。資源存儲(chǔ)于表中層數(shù)越高，說(shuō)明指數(shù)便越大。對(duì)此，節(jié)點(diǎn)如若在其他表中的越高層，便可采集更加廣泛的資源信息。表中存儲(chǔ)節(jié)點(diǎn)數(shù)量有限，每間隔15 分鐘便可檢驗(yàn)到節(jié)點(diǎn)的活躍性，如若帶有不活躍節(jié)點(diǎn)，便會(huì)利用新活躍節(jié)點(diǎn)將其替代。隨著活躍時(shí)間不斷延長(zhǎng)，節(jié)點(diǎn)會(huì)更多進(jìn)入到路由表中。根據(jù)節(jié)點(diǎn)邏輯距離公式可知表中各層節(jié)點(diǎn)數(shù)量，層數(shù)與節(jié)點(diǎn)量之間存在線性關(guān)系，層數(shù)越高則數(shù)量越多，節(jié)點(diǎn)被采集到路由表中的難度便越大。對(duì)此，在節(jié)點(diǎn)層數(shù)不斷提升之下，需要更多活躍時(shí)間才可被其他節(jié)點(diǎn)記錄到表中。

3.2.2 動(dòng)態(tài)修改節(jié)點(diǎn)ID

如若某個(gè)節(jié)點(diǎn)可對(duì)自身節(jié)點(diǎn)ID 位于表中的層數(shù)進(jìn)行控制，便可對(duì)其他節(jié)點(diǎn)在層中的位置進(jìn)行查明，從而提前將資源信息傳遞給該節(jié)點(diǎn)，使節(jié)點(diǎn)穩(wěn)定獲取其他節(jié)點(diǎn)中傳輸?shù)馁Y源信息。在遠(yuǎn)程調(diào)用信息中蘊(yùn)含著請(qǐng)求節(jié)點(diǎn)ID，在自身節(jié)點(diǎn)與其他節(jié)點(diǎn)通信時(shí)，便可對(duì)自身節(jié)點(diǎn)ID 進(jìn)行實(shí)時(shí)修正，剩余節(jié)點(diǎn)在采集到信息后便會(huì)將自身節(jié)點(diǎn)存儲(chǔ)到表中的特定層周圍。為了節(jié)點(diǎn)能夠存儲(chǔ)在第K 層的周圍，與剩余節(jié)點(diǎn)利用遠(yuǎn)程調(diào)用通信過(guò)程中，可依據(jù)節(jié)點(diǎn)ID 對(duì)自身進(jìn)行修正，使節(jié)點(diǎn)前的（159-K）位置一致，這樣節(jié)點(diǎn)ID 在異或運(yùn)算結(jié)果之前勢(shì)必為0，對(duì)方節(jié)點(diǎn)便會(huì)將自身節(jié)點(diǎn)ID 保留在K 層的周圍[4]。

3.2.3 提高資源HASH 數(shù)量

當(dāng)節(jié)點(diǎn)處于剩余節(jié)點(diǎn)表的越高層時(shí)，需要較長(zhǎng)時(shí)間才可被存儲(chǔ)到表中。節(jié)點(diǎn)沒(méi)有存儲(chǔ)到表中的期間無(wú)法采集資源信息，一旦被存儲(chǔ)到表后，便可采集大量檢索信息。只要對(duì)節(jié)點(diǎn)ID 進(jìn)行動(dòng)態(tài)修正，便可對(duì)節(jié)點(diǎn)ID 進(jìn)行控制，使其位于剩余各個(gè)節(jié)點(diǎn)表的較高層中，在維持一段時(shí)間活躍狀態(tài)后，節(jié)點(diǎn)便會(huì)被存儲(chǔ)到表中，由此達(dá)到提高資源檢索信息量的目標(biāo)。

3.3 仿真結(jié)果

在平均路徑長(zhǎng)度方面，本次仿真試驗(yàn)結(jié)果采用節(jié)點(diǎn)數(shù)為2000—10000，每1000 個(gè)節(jié)點(diǎn)為間隔。根據(jù)仿真結(jié)果可知，在邏輯跳轉(zhuǎn)方面可能因洪泛增加而有所提升，在查詢路徑長(zhǎng)度均值方面得到良好改善，尤其是在節(jié)點(diǎn)超過(guò)4000 后，可通過(guò)兩條曲線斜率得出，當(dāng)節(jié)點(diǎn)進(jìn)一步增加時(shí)，在平均查詢路徑長(zhǎng)度方面更具優(yōu)勢(shì)。究其原因，主要因查詢前采用洪泛作為系統(tǒng)信息查詢可以提供更多助力，提高了查詢速度，可在較短的查詢時(shí)間內(nèi)采集更多資源信息，且此類信息收集僅占系統(tǒng)中很小的資源，可見(jiàn)具有較強(qiáng)的實(shí)際意義。

在資源查找成功率方面，該項(xiàng)指標(biāo)可對(duì)協(xié)議能否適用進(jìn)行衡量，采用節(jié)點(diǎn)數(shù)為2000—10000，每1000 個(gè)節(jié)點(diǎn)為間隔。根據(jù)仿真結(jié)果可知，模擬節(jié)點(diǎn)數(shù)與真實(shí)值之間存在一定差異，總查詢成功率較高，可達(dá)到95%。Kademlia 查詢成功率下降較為平緩，在5000 節(jié)點(diǎn)以下成功率均為100%，5000 節(jié)點(diǎn)以上成功率較高，可大98%。值得注意的是，在節(jié)點(diǎn)不斷增加時(shí)，可根據(jù)下降曲線程度對(duì)成功率降低幅度進(jìn)行判斷，因加入“雙保險(xiǎn)”，不但邏輯相近節(jié)點(diǎn)可對(duì)關(guān)鍵詞副本進(jìn)行保存，物理鄰居也可對(duì)關(guān)鍵詞副本進(jìn)行存儲(chǔ)，使資源查詢成功率得到極大提升。

在總體帶寬方面，因P2P 網(wǎng)絡(luò)當(dāng)前面臨的主要問(wèn)題便是帶寬的巨大占用，本試驗(yàn)采用節(jié)點(diǎn)數(shù)為2000—10000，每1000 個(gè)節(jié)點(diǎn)為間隔。根據(jù)仿真結(jié)果可知，當(dāng)系統(tǒng)中節(jié)點(diǎn)低于6000 個(gè)時(shí)并不占優(yōu)勢(shì)，只有當(dāng)節(jié)點(diǎn)超過(guò)6000 以上，才會(huì)使平均路徑長(zhǎng)度變短，減少帶寬消耗。

4 結(jié)論

綜上所述，根據(jù)本文研究可知，與普通P2P 節(jié)點(diǎn)相比，路由表層的自定義P2P 節(jié)點(diǎn)可接收更多資源信息；通過(guò)資源搜索信息量、動(dòng)態(tài)修改節(jié)點(diǎn)ID、提高資源HASH 數(shù)量的方式促進(jìn)協(xié)議優(yōu)化創(chuàng)新，改進(jìn)后的Kademlia 協(xié)議可通過(guò)增加節(jié)點(diǎn)數(shù)量提高資源傳播信息速率，達(dá)到高效監(jiān)控網(wǎng)絡(luò)資源信息的目標(biāo)。在未來(lái)的工作中，Kademlia 改進(jìn)方法可為P2P 網(wǎng)絡(luò)監(jiān)管創(chuàng)新提供新思路，支持網(wǎng)絡(luò)內(nèi)部資源監(jiān)控與獲取，為計(jì)算機(jī)發(fā)展提供更多技術(shù)支持。