一种带域结构的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～），女（汉族），河南南阳人，南阳理工学院软件学院讲师，硕士，主要从事计算机相关教学研究。