一种新型的常量度结构化P2P覆盖网络

宋静静

摘 要： 为了改进结构化P2P网络的扩展性，我们设计了BGKR。它是一个具有常量度的新型P2P网络，是以广义Kautz有向图和环作为拓扑结构。在BGKR中，具有相同前缀的节点集上查找每个数据项，这样可维护网络的平衡负载。每个节点维护的路由表大小不超过2d+1，任意两节点间的路由不超过 跳。

关键词： 对等网络；分布式哈希表；覆盖网络；广义Kautz有向图

一、引言

最近几年，Peer-to-Peer（简称P2P）迅速成为计算机界关注的热门话题之一，美国财富杂志将P2P列为影响Internet未来的四项科技之一。P2P网络最大的特点就是用户之间共享资源，其核心技术就是分布式对象的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。

DHT是结构化P2P网络中的关键技术，它的特性直接决定着P2P网络及应用的性能。对基于DHT网络的研究是当前国际学术界的热点问题，它的性能评价的重要参数有节点度数、网络直径和拥塞等。现有的大多数网络都是基于一些传统的多机互联网拓扑扩展而来的，如Chord、Tapestry和Pastry是基于hypercube拓扑，CAN基于d维的torus拓扑，Koorde和D2B基于de Bruijn图，KZCAN基于Kautz图。覆盖网络的特性常受限于所基于的拓扑图。与上面使用的拓扑图相比较，广义Kautz图有着更好的特性，如常量度、最优直径和扩展性。但目前还没有基于广义Kautz图的网络，因此本文对广义Kautz图进行了研究，设计了基于广义Kautz图和环的新型覆盖网络BGKR。

二、BGKR网络

BGKR是以环和广义Kautz有向图作为拓扑结构，同环节点使用广义Kautz有向图KG（d，m）链接，当环上的节点数目达到2D+2D-1（D是环上节点标识符的长度）时形成完全的Kautz有向图。为清楚起见，我们只描述2-维的BGKR（d=2）。

（一）BGKR的基本结构

2-维BGKR中每个节点的标识都是一个基底为2长度不同的Kautz串，按照标识符的长度形成环型结构，且标识符长度相同的节点按照广义Kautz有向图的规则组成邻居关系。我们称具有相同长度标识符的所有节点形成一个环，当环上的节点数达到2D+2D-1时，它们形成一个完全Kautz有向图（D是环上节点标识符的长度）。随着节点的不断加入或退出，BGKR中环数不断的变化，各节点的标识会发生变化，节点的邻居关系也会进行相应的调整，新节点的标识是在其加入过程中根据环的个数产生的。各节点标识的长度可能是不同的，我们用|U|来表示节点U的标识符长度，则BGKR中节点的邻居关系满足下面的性质1。

性质1（邻居关系特性）对BGKR中不同环的任意节点U和V，若节点U和V是邻居，则||U|-|V||=1。如图所示是一个D=3的满环BGKR结构。

从图中可以看出，BGKR中节点的度最大为2d+1，d是Kautz有向图的度。因为，在同环上节点的最大度是d，相邻的外环上最多有d个邻节点且内环上最多有1个邻节点。

一个节点x1…xD有三种不同的邻居：（1）具有相同长度标识符的同环邻节点，即广义Kautz有向图的邻节点；（2）外环邻节点，标识为x1…xDα，α属于{0，1，2}/{xD}；（3）内环邻节点，标识为x1…xD-1。

D=3的BGKR结构

（二）BGKR路由机制

BGKR中路由操作是利用三种不同的邻节点实现的。令节点x的标识符长度为i，节点y的标识符长度为j，节点x路由消息到目的节点y。

1）当i=j，用同环路由，即on-ring-forwarding。on-ring-forwarding操作是利用广义Kautz路由机制从节点x=x1…xi路由到节点y=y1…yj。因此，根据Kautz有向图的性质，同环上的任意两个节点x和y間的最路由长度是Kautz有向图的直径。

2）当i

3）当i>j时，如果y=y1…yj是x=x1…xi的前缀，则向内环邻节点路由，即inwards-forwarding。否则，先利用inwards-forwarding操作，节点x沿着内环邻节点到达标识为x1…xj的节点x，再利用on-ring-forwarding操作，沿着广义Kautz有向图路由到达目的节点y。

下面给出了在BGKR覆盖网中从节点x到节点y的路由算法。

输入：初始节点x和目的节点y。

Procedure route （x， y）

If i== j then /*判断x和y的长度是否相等

return on-ring-forwarding （x， y）

else if i

if x是y的前缀then

return outwards-forwarding （x， y）

else

return on-ring-forwarding （x1…xi， y1…yi）

return outwards-forwarding（y1…yi，y1…yj）

else

if y是x的前缀 then

return inwards-forwarding （x， y）

else

return inwards-forwarding （x1…xi， x1…xj）

return on-ring-forwardsing （x1…xj， y1…yj）

三、结论

P2P系统中资源处理是当前面临的重要问题，而覆盖网的拓扑结构是解决这一问题的重要途径。在传统的互连网络拓扑中，Kautz图具有最优网络直径等良好的特性，本文基于环和广义Kautz有向图提出了一种新的P2P网络（BGKR）。BGKR是一个常量度数、O（logN）网络直径且为常量拥塞的系统。在结点规模较大时，性能优于现有的常量度数的CAN和Koorde。