一種帶域結構的Kademlia網絡模型的設計與實現

引言：如今P2P已經成為網絡中不可缺少的應用技術，Kademlia網絡是應用最廣泛的基于DHT協議的P2P網絡。本文針對Kademlia網絡缺點提出了一種帶域結構的Kademlia網絡，并完成了該網絡的路由表設計，路由設計和資源發布設計等。最后通過OverSim軟件仿真可知該網絡結構優于Kademlia網絡。

Kademlia[1]是一種分布式哈希表（DHT）技術。由于Kademlia網絡的資源搜索過程消耗了一些不必要的網絡路由，減慢了資源查詢速度；同時該網絡忽視了網絡節點能力的差異，不符合負載均衡的基本理念，降低整個網絡的整體性能。本文針以上缺點提出了一種帶域結構的Kademlia網絡。

一、帶域結構的Kademlia網絡

該網絡模型的主要改進及實現如下。

1.1 主要改進

（1）邏輯空間增加物理拓撲信息，：采用二層的Kademlia結構，將IP地址的32位地址的前16位作為節點ID的前16位，域內ID采用隨機112位ID，存儲兩張路由表，一個域路由表，一個域內路由表。

（2）網絡中區分節點的性能：該網絡中的節點按照存儲能力、運算能力、網絡能力和穩定性來分類，有利于充分發揮整個網絡的性能。

（3）網絡中加入集合節點，負責離線節點收集和域信息轉發。集合節點優先采用穩定在線的節點來承擔，其次根據節點性能來確定，這樣能保證域間路由的穩定。

（4）網絡中加入注冊節點，給節點的加入帶來了便利，給整個網絡穩定和效率提供了保障，還可以緩存部分路由信息來加速新節點的路由初始化。

1.2網絡節點結構

1.節點ID生成

節點由16位的域ID，112位的節點ID構成，域ID由IP地址生成，節點ID采用隨機算法生成。

2.資源ID生成

資源ID采用128位ID，前16位ID由文件內容MD5[2]值對216取模生成，后112位ID根據文件內容MD5生成的。

3.節點路由表

（1）普通節點路由表

每個普通節點存儲一張域路由表和域內路由表。具體內容參考Kademlia路由表。

（2）集合節點路由表

每個集合節點也存儲一張域路由表和域內路由表。集合節點是由普通節點升級或注冊生成的，負責域間消息轉發，離線節點收集，它不僅保存了域內路由表，還保存了所有域ID以及每個域的集合節點信息。

（3）注冊節點路由表

注冊節點負責集合節點的更新和新注冊節點的路由更新，該節點不僅需要保存集合節點信息，還需要保存一個域內所有節點的power值列表以便于動態更新集合節點。

1.3 節點更新策略

1.3.1 集合節點的同步與更新

由注冊節點動態檢查與更新機制來完成集合節點的更新，更新完成后，發送消息給所有原來的在線集合節點，要求他們更新自己路由表中的集合節點。

1.3.2 路由表動態更新

注冊節點周期性的檢查集合節點的在線狀況，并動態更新域路由表，同時通知所有集合節點更新他們的路由表。

1.3.3 數據發布更新

每個節點將發布文件的信息數據緩存在自己的P個最近的域以及每個域的K個最近的鄰居處，當存放數據的節點失效時，以便數據會很快被更新到其他新節點上。

1.4資源定位機制

1.4.1 資源發布

本網絡中資源發布采用對，其中，Value存儲文件的IP地址、大小和評論信息等。存放數據的過程為：

1、節點A首先取出根據文件內容MD5生成的112

位NodeID，再對216取模得到AreaID。

2、發起者首先向注冊服務器發送<查詢域>請求，尋

找最接近AreaID的P個域。

3、發起者收到返回的對應最接近的P個域的集合節點后，向這P個集合節點發起<加入域> 消息，如果不存在AreaID值最接近的域，則生成該域；發布節點成為該域集合節點。

4、這P個集合節點發起<查找節點>消息，在該P個域中定位最接近NodeID的每個域的的K個節點，然后在這P*K個節點上發起<存儲>操作。

5、執行<存儲>操作的P*K個節點每小時重新發布節點數據對信息。

6、規定在任何時候，域中若有w上的NodeID對數據更接近，w將對數據復制到u上。

1.4.2資源定位

資源定位步驟：

1、節點A首先取出根據文件內容MD5生成的112位NodeID，再將該ID模216取得AreaID。

2、查詢本地域路由表，向本地集合點發送<查詢節點>消息，集合節點返回對應的NodeID位置信息，然后發送<下載>消息到目標節點完成下載。

3、如果本地域沒有找到NodeID，則直接向服務器發送<查詢域>消息，返回P個域的集合節點，并向這些集合節點發送<查詢節點>消息。

4、集合節點根據文件的NodeID，根據Kademlia定位算法，負責本域內的NodeID定位，最終由集合點返回給請求節點對應的文件位置信息，然后由請求節點發送<下載>消息到由集合節點最先返回的目標節點，并和此目標節點聯系完成下載。

二、系統仿真

仿真實驗模擬了1500個節點在1個小時內Kademlia和帶域結構Kademlia網絡的仿真測試，利用OverSim[3]的應用程序類模擬了接近真實網絡的拓撲，利用網絡波動類模擬節點的頻繁退出和加入的操作。通過仿真可知該網絡充分考慮了節點間的物理位置信息及網絡異構性，加入了集合節點與注冊節點，優于傳統的Kademlia網絡。

參考文獻

[1]Petar Maymounkov and David Maziμeres. Kademlia： A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems （IPTPS'02）， pages 53～65， March 2002.

[2]RFC1321，The MD5 Message-Digest Algorithm.

[3]http：//www.oversim.org.

（作者單位：南陽理工學院軟件學院）

作者簡介：邱雅（1981～），女（漢族），河南南陽人，南陽理工學院軟件學院講師，碩士，主要從事計算機相關教學研究。