基于de Bruijn图的大规模网络资源搜索方法

摘要

本发明公开了一种基于de Bruijn图的大规模网络资源搜索方法，要解决的技术问题是解决大规模网络搜索对结点度数小和搜索延迟低的需求。技术方案是先为资源对象命名；然后采用一般化的de Bruijn图实现网络拓扑；接着采用“标识分裂合并法”处理结点的加入退出事件；采用“逐位匹配”方式实现资源的搜索并采用“前后匹配”规则判断是否完成搜索。采用本发明网络拓扑的平均度数为4，最大搜索延迟仅为logdN，能大幅度提高大规模网络的资源搜索效率。

说明书

技术领域

本发明涉及计算机网络中的资源搜索方法，尤其是一种基于de Bruijn图的资源搜索方法。

背景技术

P2P(peer-to-peer)网络是近年来兴起的一种网络。在P2P网络中，各节点在逻辑上是对等的，没有客户端和服务器之分，各个节点之间可以直接进行通信和交互。目前，P2P网络在科学研究、电子商务、电子政务和军事应用等重要领域都有着广阔的应用。为了实现资源的有效共享和综合利用，P2P网络用户需要对符合要求的资源进行搜索，资源搜索是P2P网络的关键技术之一。

根据资源组织模式，P2P网络通常可分为两种：结构化(Structured)P2P网络和非结构化(Unstructured)P2P网络。结构化P2P网络由于具有更加可靠的性能，目前在Internet上得到了大量应用。

结构化P2P网络中的资源搜索问题可以抽象为：如何在大规模网络上实现资源对象的高效搜索，并且适应结点的动态变化。

目前，结构化P2P网络中的资源搜索方法主要包括Chord、CAN、Pastry、Tapestry等。在上述方法中，每个结点都有唯一的标识，并根据一定算法在结点间构建网络拓扑。每个结点都维护一个“转发表”，保存相关邻居结点的信息。每个资源对象根据其关键字，通过哈希函数得到资源对象标识。资源对象的标识和结点标识通常属于相同或相似的名字空间，各结点都负责资源对象标识空间的一部分。当结点加入或退出时，各相关结点需要修改转发表，并动态调整其负责的标识空间范围，以维护分布哈希表的一致性。在资源搜索时，每个结点根据其“转发表”将资源搜索消息转发到相应的邻居结点上，直到最终到达目标结点完成搜索。评价大规模网络资源搜索性能的重要参数包括结点度数和搜索延迟等。结点度数是指各结点上维护的“路由表”的大小；搜索延迟是指一次资源搜索请求在系统中转发的逻辑跳步数。评价网络搜索方法的标准主要包括结点度数和搜索延迟，高效的搜索方法一方面应具有较小的节点度数，另一方面应具有较低的搜索延迟。但是，现有搜索方法均没有实现结点度数和搜索延迟的较好的折中。

发明内容

本发明所要解决的技术问题：针对大规模网络搜索对结点度数小和搜索延迟低的需求，提出一种基于de Bruijn图的大规模网络资源搜索方法，该方法既能够具有较小的节点度数(即较小的路由表)，又具有较低的搜索延迟。

为了解决上述问题，本发明提出的技术方案为：

第一步，为资源对象命名：对每个结点和资源对象，采用文献“RFC 1321：The MD5Message-Digest Algorithm”(http://www.ietf.org/rfc/rfc1321.txt，April 1992)所述的MD5(消息摘要5)算法进行命名。

第二步，采用de Bruijn图实现网络拓扑：de Bruijn图B(d，D)是一种有向图，其中d为各结点标识的基(即结点标识中每个字符的取值范围为0到d-1)、D为各结点标识的长度。每个点u＝u₁u₂...u_D有d条出边：对任意α∈{0，1，2，L，d-1}，点u有一条到点v＝u₂u₃...u_Dα的出边。文献“A Combinatorial Problem”(Proc.of Koninklijke NederlundseAcademic van Watenschappen，vol.A49，pp.758-764，1946)证明，de Bruijn图的最大延迟为log_dN，结点度数为2d。

传统的de Bruijn图的结点数为d^D，不能容纳任意数目的结点。例如，取d＝2，则结点数只能为2¹＝2、2²＝4、2³＝8、……。因此，我们采用文献“Factoring and Scaling KautzDigraphs”(Research Report 94-15，LIP ENSL，69364 Lyon，France，Apr.1994)提出的一股化的de Bruijn图定义：令GB(d，n)代表基为d和结点个数为n的一股化de Bruijn图，那么其点集V(GB(d，n))和边集E(GB(d，n))分别为

V(GB(d，n))＝{0，1，L，n-1}，   (1)

E(GB(d，n))＝{[i，(d×i+α)modn]|0≤α≤d-1}，  (2)

每个结点标识有其对应的二进制表示。由于B(d，D)≡GB(d，d^D)，因此一股化deBruijn图是传统de Bruijn图的超集(即任意传统de Bruijn图都可以表示为一个一股化deBruijn图)，并且一股化de Bruijn图可以容纳任意数目的结点。一股化de Bruijn图的点对应网络拓扑中的结点，边对应网络拓扑中的结点间连接，即可得到相应的网络拓扑。为了简化设计，以二进制数表示一股化de Bruijn图中的点的标识。

第三步，采用“标识分裂合并法”处理结点的加入退出事件：当新结点P加入时，首先选取网络中满足下列条件的任一结点V:V的结点标识长度不大于其任一邻居结点；然后结点V进行分裂，设结点V标识为v₁v₂...v_k，则结点P加入后，v₁v₂...v_k分裂为v₁v₂...v_k0和v₁v₂...v_k1，结点V的标识变为v₁v₂...v_k0，新结点P的标识设置为v₁v₂....v_k1。进而根据一股化de Bruijn图更新P、V以及相关结点的路由表，即各结点的连接关系满足式(2)。结点退出是加入的逆过程。当检测到结点Q离开时，首先选取网络中某一对满足下列条件的兄弟结点Y＝y₁y₂...y_p-10和Y’＝y₁y₂...y_p-11：Y和Y’的标识长度都不小于其各自的邻居；然后将结点Y的标识改为Q的标识，Y’的标识改为y₁y₂...y_p-1(即Y和Y’合并)；并根据一股化de Bruijn图更新相关结点的路由表。

第四步，采用“逐位匹配”方式实现资源的搜索：资源搜索通过结点间转发搜索消息来完成。首先定义“前后匹配值”：对任意两个字符串u＝u₁u₂...u_m和v＝v₁v₂...v_n，u和v的前后匹配值(记为QH(u，v)＝x)是指u的后x位与v的前x位相同，例如10011和11010的前后匹配值为2。各结点在接收到资源对象搜索消息后，计算自己和目标资源对象的前后匹配值x，然后在路由表中选择与目标资源对象的前后匹配值为x+1的邻居进行转发。

第五步，采用“前后匹配”规则判断是否完成搜索：结点u＝u₁u₂...u_m拥有资源s＝s₁s₂...s_r，当且仅当：QH(u，s)＝|u|，或者QH(u，s)＝|u|-1^u₁＝s_r。当满足前后匹配规则时，说明完成资源的搜索，结束，否则转第四步继续进行搜索。

采用本发明可以达到以下技术效果：

1.在本发明中，各结点根据它们的标识通过模拟一股化de Bruijn图组织邻居关系，由文献“Factoring and Scaling Kautz Digraphs”(Research Report 94-15，LIP ENSL，69364Lyon，France，Apr.1994)，可知该网络拓扑的平均度数为4，最大搜索延迟仅为log_dN。

2.在形成良好拓扑结构的基础上，本发明使用前后匹配的方式转发资源搜索消息，能够将资源搜索消息准确地转发到离目标结点近的邻居结点，提高大规模网络的资源搜索效率。

附图说明

图1是本发明总体流程图；

图2是de Bruijn图示例；

图3是结点加入处理过程示例。

具体实施方式

本发明主要包括五步(如图1所示)：①为资源对象命名；②采用de Bruijn图实现网络拓扑；③采用“标识分裂合并法”处理结点的加入退出事件；④采用“逐位匹配”方式实现资源的搜索；⑤采用“前后匹配”规则判断是否完成搜索。

在第二步中，本发明采用de Bruijn图实现网络拓扑，图2给出了两个de Bruijn图的示例，左图为B(2，2)，右图为B(2，3)。

在第三步中，本发明采用“标识分裂合并法”处理结点的加入退出事件，图3给出了一个结点加入处理的示例。新节点加入前，在左图中V＝000；新节点加入后，V的标识变为0000，P的标识为0001，联结关系如右图所示：V＝0000的出边邻居为001、010，入边邻居为010、100；P＝0001的出边邻居为100、101，入边邻居为010、100。