DBCAN：一种基于de Bruijn 图的高效P2P 模型

毕海波

（中国人民银行乌鲁木齐中心支行，乌鲁木齐830002）

0 引言

CAN（Content Addressable Network，内容可寻址网络）是一个简单、容错的多维空间P2P 模型，采用多维空间拓扑结构。CAN 思想简单、直观，比其他结构化P2P 模型容易理解。CAN 每个节点占有一个属于自己的区域并且负责该区域中所有的“点”，并由负责该点的节点来存储数据对象。每个节点维护一个路由表，记录它在多维空间上的邻居信息。当每个新节点加入CAN 后，它必须拥有自己的空间。每个新节点被映射到一个点，在它加入之后，该点原来所在的区域将一分为二，一半分给新节点来负责，另一半由原来的节点负责，相应的数据对象也会重新分配。当一个节点离开CAN 后，它的某个邻居必须接管原来由它负责的区域，相当于区域合并。随着节点的不断加入和离开，CAN网络的区域将被划分地支离破碎，而且会出现越来越多由一个节点负责多个节点的情况，直到节点的负载超过它能力的上限。为了提高CAN 的性能，本文找到一种方法来合并那些较小的区域，使它们尽量变得规整，从而使节点度、负载均衡和路由路径长度等性能得到进一步优化。

1 de Bruijn图及其性质

1.1 de Bruijn图相关定义

1.1.1 de Bruijn 图

对于两个给定的整数d（≥2）和n（≥1），de Bruijn有向图，记为B（d，n），它的顶点集：

它的边集E 是由从顶点x1x2…xn到d 个x2…xnα 的所有边组成的，其中α ∈{0，1，…，d-1}。图1 表示d=2，n=3 的de Bruijn 图。

图1 de Bruijn图B（2，3）

1.1.2 de Bruijn 串和de Bruijn 空间

de Bruijn 图B（d，n）的顶点x1x2…xn（xi∈{0，1，…，d-1}，1≤i≤n）称为基底为d、长度为n 的de Bruijn 串，de Bruijn 空间de Bruijn Space（d，n）是指所有基底为d、长度为n 的de Bruijn 串的集合。

1.2 de Bruijn图的性质

对于任何d≥2 和n≥1 的de Bruijn 图B（d，n）有以下性质：

（1）B（d，n）有dn个顶点，dn+1条边，d 条环；

（2）B（d，n）直径为n；

（3）B（d，n）中每个节点的出度和入度都为d，即d正则。

1.3 de Bruijn图中最短路径的唯一性

设x=x1x2…xn和y=y1y2…yn是B（d，n）中两个不同的顶点。用l（x，y）表示x 的尾部和y 的首部重叠数字的最大数目，并设这些重叠的数字为z1z2…zl，即l（x，y）是最大的l 使得：

记B（d，n）中（x，y）：

则P（x，y）是B（d，n）中唯一最短（x，y）路径，长为n-l。

B（d，n）中任何两点之间最短路径的唯一性非常重要，它可以保证路由的有效性和正确性，根据这个性质就可以设计B（d，n）中任何两个顶点之间的最短路径路由算法了。

2 DBCAN路由模型

DBCAN 使用de Bruijn 图B（2，n）作为拓扑结构，采用B（2，n）而不是更一般的B（d，n）作为拓扑结构，是为了DBCAN 维护时更易处理。DBCAN 中每个节点都负责维护虚拟2 维笛卡尔空间中的一块区域，节点与其所负责的区域是一一对应的，节点的标识即是它所负责区域的标识。

2.1 数据的命名与分布

2.1.1 数据的命名

DBCAN 中的标识分为数据标识和节点标识：

（1）数据标识

本文采用随机生成的128 位二进制字符串作为数据标识。

（2）节点标识

在介绍节点标识之前首先给出“通用前缀集”的概念。

通用前缀集是一个由二进制字符串组成的集合，对于任何二进制字符串w ∈{0，1}*，集合中都有一个唯一的字符串是它的前缀。

例如，{0，10，110，111}就是一个通用前缀集，因为对于任何二进制字符串，集合中都对应的有唯一的字符串是它的前缀。

在DBCAN 中，每个节点标识对应于通用前缀集中的一个字符串，节点标识空间就是一个通用前缀集。注意：通用前缀集中的字符串长度可能不一样，所以在DBCAN 中，每个节点的标识长度并不一定等长，这与传统的de Bruijn 图中的顶点标识长度等长不同。

2.1.2 数据的分布

本文定义在DBCAN 中，数据对象K=k1k2…km由节点X=x1x2…xn负责，当且仅当x1x2…xn是k1k2…km的前缀。根据上面所述，在DBCAN 中必然有一个节点标识是数据对象K 的前缀，并且可知，标识为x1x2…xn的节点可以负责的数据个数为2m-n，即所有以x1x2…xn为前缀的数据都由它负责。

2.2 节点邻居关系

在DBCAN 中，每个节点的标识都是一个以2 为基底的de Bruijn 串，这些节点根据它们的标识按照de Bruijn 图的规则组织在一起，形成邻居关系。网络的最初状态为空网络，即网络中没有节点。随着网络中节点不断的变化（加入或者退出），DBCAN 中节点维护的区域会进行相应的拆分或合并，变化的区域所对应的节点的标识也会相应的改变，当然节点的邻居关系也会做相应的变化。但是无论网络怎样变化，DBCAN 的节点标识空间都是一个通用前缀集。

本文定义节点X 指向的节点称为X 的孩子，指向X 节点的节点称为X 的父亲。

在DBCAN 中，节点的邻居关系如下：

节点X=x1x2…xk要么只有一个形式为x2…xj的孩子，j≤k；要么有几个形式为x2…xky1…yl的孩子，1≤l ≤m-k+1。后面这种情况，形式为y1…yl的字符串构成一个通用前缀集。相应地，节点X=x1x2…xk的父亲也有两种形式：形式为α x1…xj，α ∈{0，1}，j≤k；形式为β x1x2…xky1…yl，β ∈{0，1}，1≤l ≤m-k-1。后一种情况，形式为y1…yl的字符串构成一个通用前缀集。这两种情况也可以共同存在，但此时α ≠β。

另外，节点如00…0 和11…1 的孩子和父亲的形式与一般情况有所不同。节点U=α α…α，α ∈{0，1}，它的孩子的形式为α…α y1…yl，ι≥1，y1=αˉ，字符串y2…yl构成一个通用前缀集。

2.3 路由算法

DBCAN 的路由算法采用de Bruijn 图的最短路径路由算法。假设在DBCAN 中有一个节点的标识是U=u1u2…uz，X=x1x2…xk为DBCAN 中任意一个节点，现在从节点X 开始定位节点U。

在给出路由算法之前，本文首先规定字符串S 是最长的X 的节点标识的后缀并且是U 的节点标识的前缀，有可能S=Φ，因为有可能X 的节点标识的后缀和U 的节点标识的前缀没有重合部分。

节点X 定位节点U 的路由算法如下：

（1）如果S=x1x2…xk，则说明X=U，即X 就是所要找的节点U，定位完成，否则进入（2）；

（2）如果节点X 只有一个孩子V=x2…xj，那么定位U 的过程转向节点V；如果X 有几个孩子，那么定位U 的过程转向节点V=x2…xky1…yl，其中S y1…yl是u1u2…uz的一个前缀。根据通用前缀集性质，节点X 一定存在这样一个孩子，并且是唯一的。

以下为DBCAN 的路由算法伪码。

2.4 数据的发布

在DBCAN 中，数据的发布也是根据路由算法实现的。如果节点U（U 为DBCAN 中任意一个节点）有数据要发布，其发布过程如下：

（1）节点U 首先获得数据标识K；

（2）然后节点U 发起到数据标识K 的路由，最终路由会到达节点V，节点V 的标识是数据标识K 的前缀；

（3）数据的信息就发布在节点V 上。

3 实验仿真

对P2P 网络来说，由于其规模巨大，实际构建大规模的分布式网络带来的硬件、软件开销通常是难以付出的，因此对P2P 网络来说，实验仿真是非常重要的。本文采用P2Psim 对DBCAN 进行实验仿真。

3.1 节点度数

节点度数是指网络中节点的“连接数”，即逻辑上与其他节点连接的个数。在结构化P2P 网络中则体现在路由表的表项数目上。路由表越小，查询的效率越高，维护的开销越小，网络性能也就越好。

本文分别仿真了节点规模为1 千、1 万和10 万的DBCAN，它们的节点度的分布如图2 所示。

图2 DBCAN节点度数的分布

图2 表明，规模不同的DBCAN，它们的节点度数分布虽然不同，但大致相仿，这表明DBCAN 中节点度数的分布不会随着网络规模的扩大而改变，是稳定的。

通过统计得知，DBCAN 的节点度数平均为2，这与de Bruijn 图的顶点度相吻合。对一个d 维CAN 来说，它的节点度数为2d，所以对于2 维CAN，它的节点度数为4；在Koorde 中，每个节点度为4。可以看出，DBCAN 的节点度是三者中最优的。

3.2 负载均衡

良好的“负载均衡”是所有基于分布式散列表的P2P 网络都希望具有的属性，因为它能使得整个网络更高效地工作，更充分地利用每个网络成员的资源。

由于CAN 中的节点也是维护空间中的一块区域，所以本文对DBCAN 负载均衡性能的评测是将它与CAN 进行比较，对比两者不同面积的区域的分布情况。

本文对负载均衡实验仿真的节点规模为5 万，并与相同规模的CAN 进行了比较。网络中数目最多的区域面积用S 表示，面积是它的1/2 的用S/2 表示，面积是它的2 倍的用2S 表示，其他的以此类推，它们的分布如图3 所示。

图3 区域面积的分布

如图3 所示，DBCAN 的面积分布在4 个区域，面积为S 和2S 的区域占93%；CAN 的面积分布在7 个区域，各区域分布较分散不集中，且存在碎片区域。从而可以看出DBCAN 的负载均衡性能优于CAN。

3.3 路由路径长度

“路由路径长度”是指网络中节点定位时，路由过程中所需要完成的路由跳数。它是衡量P2P 网络性能最重要的指标之一，因为定位是网络中最基本、最常用，同时也是最重要的部分。

本文对DBCAN 的路由路径长度（路由跳数）进行了仿真实验，并将结果与CAN（d=2），CAN（d=3）和Koorde 进行了比较。实验中节点的规模分别为256、512、1024、2K、4K、8K、16K、32K 和64K。对每种规模的网络本文分别进行了100 次实验，然后计算这100次路由的平均路由路径长度，实验结果如图4 所示。

图4 路由路径长度

如图4 所示，在任何规模的网络中，CAN（d=2）和Koorde 的路由跳数都要高于DBCAN。当网络中的节点数在256 至4K 时，CAN（d=3）的路由跳数要小于DBCAN，而当网络中的节点数大于4K 后，CAN（d=3）的路由跳数就都高于DBCAN。从而可以看出，DBCAN总体上的路由路径长度指标要优于其他三者，特别是随着网络规模的不断扩大。

4 结语

本文通过对de Bruijn 图和CAN 等网络模型的研究，提出了一种节点度数、负载均衡和路由路径长度等性能均更优的DBCAN 模型。本文没有采用计算机的IP 地址直接作为P2P 覆盖网上节点的标识，而是采用通用前缀集来实现将物理网上的计算机映射到覆盖网。如何在不损失物理网上节点之间的邻近关系基础上实现物理网到覆盖网映射将是下一步的工作。