基于優化Kademlia協議的P2P網絡資源發現算法研究

◆徐衛克

（中國社會科學院大學 北京 102488）

與以往集中型客戶端模式對比，P2P 網絡的優勢在于數據共享可在節點間開展。因P2P 技術無須中央控制器支持，整個文件交換不受其他因素干預。受該技術去中心化特性影響，P2P 網絡傳輸中資源很難被追蹤監管，很容易導致盜版文件、非法傳播等網絡安全問題。對此，應在Kademlia 協議基礎上采用DHT 技術控制非法內容傳播，使合法內容傳播安全得到切實保障。

1 Kademlia 協議概述

該協議中節點間可相互通信，無須中央控制器支持。多個節點構成分布式網絡，網絡中任意節點均可在網絡中采集資源。在該協議基礎上，各個DHT 節點均由三項內容組成，即IP 地址、端口與節點ID。其中，節點ID 是節點IP 地址與端口經過SHA-1 算法散列后得出，各個節點信息都會存儲到路由表中，且任何2 個節點之間的距離可通過節點ID 的異來表示。

1.1 節點路由表

在該協議中，各個節點在初始狀態下被分配成一個160 位的節點ID，節點之間距離可通過計算得出，公式為：

Distance（A，B）＝IDAXORIDB

式中，IDA 與IDB 分別代表的是節點A 和B 的節點ID。節點之間ID 異是長度為160 的比特數組。節點之間邏輯距離計算可打破地域上的距離限制，使邏輯距離變得更加貼近。路由表由K 桶列表構成，對于任意編號為i 的桶而言，各個節點均存儲到與自身相距2i距離的節點信息中。路由表中的節點可根據距離不同而分層，如若結果數組由倒數第i 位開始并非為0，該節點存儲在該節點路由表的第i 層中。路由表可根據節點間距離分成160 層，第i 層中無法存儲全部節點，只能將與自身距離最近的節點存入其中，最多可納入2i 個節點[1]。

1.2 自組織

該協議中的自組織包括節點加入與退出兩項內容，對于一個新節點來說，在首次加入Kademlia 網絡時應經歷以下流程。首先，獲取一個網絡內部節點信息，即引導節點，計算二者間的邏輯距離，將其納入與之相對的K 桶中；然后將FIND_NODE 請求發送到該節點中，由此尋找與自身距離相近的節點，最后使全部k 桶被刷新。通過與自身距離由近到遠節點的逐一查詢，新節點采集的信息不斷增加，在刷新K 桶的同時，也將自身信息留在了其他K 桶中。節點在退出網絡時無須發送任意信息，因為各個資源都會發布k 個副本，因此不會對該節點所有資源產生負面影響。此外，該協議還要求各節點定期發布自己的數據，再將數據存儲到與自己相距最近的鄰居位置，鄰居同時失效的概率較低，這樣可保障某個節點失效時不會對其他節點產生影響，進而出現資源無法查詢等情況。

1.3 資源定位

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

2 P2P 網絡技術的主要性能

根據拓撲結構的不同，可將P2P 系統分成全分布式、集中式、非結構化、半分布式四種類型。其中，集中式拓撲以Napster 為主，通過中央處理器存儲網絡中全部節點用戶信息，使文件查詢與傳輸相互獨立。全分布式以Gnutella 系統為代表，屬于純P2P 系統，無中心服務器，在完全隨機圖基礎上發覺和轉發資源；半分布式網絡可解決非結構模型中資源發現效率低等問題，在DHT 基礎上創建分布式網絡，可自適應節點的加入與退出，具有較強的安全性、穩健性，成為P2P 系統的主流發展趨勢。半分布式拓撲可將集中式、全分布式拓撲特點整合起來，將超級節點概念加入其中，在此基礎上呈現個別節點信息，在超級節點間轉發分享，再將查詢請求傳遞到普通節點。在DHT 基礎上的全結構化網絡作為PAP 發展的新路徑，性能優良。其中，路徑長度代表的是目標請求在P2P 中的平均跳數；路由表長度為各個節點所需維護的表項數，如表1所示。表中，N 代表的是P2P 網絡中節點數值；d 代表的拓撲維數；b 代表的是ID 空間基。在上述系統中，Kademlia 協議得到廣泛應用，且主流P2P 軟件均可作為輔助檢索協議投入使用。

表1 DHT 方案性能對比

3 Kademlia 協議下P2P 網絡資源發現算法分析

在Kademlia 協議中，資源請求信息會率先傳遞到路由表中與資源距離最近的節點。因節點ID 具有不確定性，無法對節點在表中所處層級進行控制，導致節點可接收的資源請求較為有限，需要通過仿真算法的方式進行改進，使P2P 網絡資源發掘與采集更加準確全面。

3.1 仿真環境

該試驗的仿真環境如下，采用主頻為1.73G 的雙核CPU，1G 內存筆記本，在XP 系統中安裝VMware 虛擬機，在D 盤中分配4G 空間，在Fedora 內核中安裝Linux 操作系統。以Kademlia 協議為例對P2P 網絡資源發現算法仿真過程進行分析，在正式仿真之前，需要先寫topology.txt 文件，該文件中包含仿真網絡拓撲參數，具體的仿真流程如下[3]。

3.2 仿真流程

3.2.1 資源搜索信息量

節點率先將資源檢索信息傳遞到表中與資源相距最近的點，任何節點與資源間的距離均可通過異或運算來獲取，節點與資源間的邏輯距離可用以下公式計算，公式為：

Distance（A，B）＝IDAXOR HASHa

式中，IDA 代表的是節點A 的節點ID；HASHa 代表的是資源a的HASH 值。通過節點與資源間的距離，可將資源記錄在表中相應層內。路由表各層資源數量與層間關系可由以下公式計算，即：

Zi＝2i

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

3.2.2 動態修改節點ID

如若某個節點可對自身節點ID 位于表中的層數進行控制，便可對其他節點在層中的位置進行查明，從而提前將資源信息傳遞給該節點，使節點穩定獲取其他節點中傳輸的資源信息。在遠程調用信息中蘊含著請求節點ID，在自身節點與其他節點通信時，便可對自身節點ID 進行實時修正，剩余節點在采集到信息后便會將自身節點存儲到表中的特定層周圍。為了節點能夠存儲在第K 層的周圍，與剩余節點利用遠程調用通信過程中，可依據節點ID 對自身進行修正，使節點前的（159-K）位置一致，這樣節點ID 在異或運算結果之前勢必為0，對方節點便會將自身節點ID 保留在K 層的周圍[4]。

3.2.3 提高資源HASH 數量

當節點處于剩余節點表的越高層時，需要較長時間才可被存儲到表中。節點沒有存儲到表中的期間無法采集資源信息，一旦被存儲到表后，便可采集大量檢索信息。只要對節點ID 進行動態修正，便可對節點ID 進行控制，使其位于剩余各個節點表的較高層中，在維持一段時間活躍狀態后，節點便會被存儲到表中，由此達到提高資源檢索信息量的目標。

3.3 仿真結果

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

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

在總體帶寬方面，因P2P 網絡當前面臨的主要問題便是帶寬的巨大占用，本試驗采用節點數為2000—10000，每1000 個節點為間隔。根據仿真結果可知，當系統中節點低于6000 個時并不占優勢，只有當節點超過6000 以上，才會使平均路徑長度變短，減少帶寬消耗。

4 結論

綜上所述，根據本文研究可知，與普通P2P 節點相比，路由表層的自定義P2P 節點可接收更多資源信息；通過資源搜索信息量、動態修改節點ID、提高資源HASH 數量的方式促進協議優化創新，改進后的Kademlia 協議可通過增加節點數量提高資源傳播信息速率，達到高效監控網絡資源信息的目標。在未來的工作中，Kademlia 改進方法可為P2P 網絡監管創新提供新思路，支持網絡內部資源監控與獲取，為計算機發展提供更多技術支持。