张亚松

（武汉理工大学 计算机科学与技术学院，湖北 武汉430063）

高效的查找资源决定了P2P网络的性能，是P2P网络研究的重点。Chord[1]是MIT提出的基于分布式哈希表DHT（Distributed Hash Table）的资源搜索算法，在可扩展性和查找确定性方面都有比较好的表现，其他的系统还有 Pastry[2]、CAN[3]和 Tapestry[4]。 Chord 可 以 保 证 在 log2N跳数之内找到所需要的资源，但其存在路由表信息冗余以及逻辑网络与物理网络不匹配的问题，导致查找效率不高。

为了解决上述两个问题，在Chord的基础上，本文提出了一种改进的Chord路由算法。该算法将路由表中重复的路由信息删除，加入原始路由表中覆盖不到的半环的路由信息；为每个节点增加邻居表，邻居表中记录了本节点附近节点的物理位置信息。通过邻居表路由过程不再是由指针表单独决定，而是由指针表和邻居表共同决定。这样既消除了原路由表中的冗余信息，又增大了路由表的覆盖度，也解决了逻辑网络和物理网络不匹配的问题，从而提高了查找效率，降低了平均路由延迟。

1 Chord路由算法

Chord是MIT提出的基于DHT的资源搜索算法，平均路由跳数一般在log2N/2之内。在Chord系统中，节点和关键字都有一个m位的标识符，每个节点的ID可以通过对IP进行哈希运算得到。所有节点按照ID从小到大沿顺时针方向排列成一个逻辑的标识圆环（Chord环）。节点的资源关键字标识符K通过对关键字本身进行哈希运算得到。关键字标识符K存放在节点ID=K或者ID=min{ID-K；ID-K>0}这样的节点上。Chord中每个节点都有一个路由表，路由表有m条记录，其中第i条记录记录了在Chord中和该节点的距离大于等于2i-1（i∈[1，m]）的最近节点。显……