分布式非结构化P2P网络中的搜索技术优化

邱建英 刘进军 周 霞

[摘要]研究介绍一种可选择的Gnutella的搜索算法和数据复制策略。它是一种多次随机漫步(multiple random walks)搜索算法，跟洪泛的搜索算法一样快，但是减少了网络的负载量。

[关键词]P2P搜索随机漫步

中图分类号：TP3文献标识码：A文章编号；1671—7597(2009)1020096--01

Nspster自从1999年出现后在网络上快速的流行了起来，P2P技术也同时迅速发展。由于P2P摆脱了服务器的限制，用户可以更广泛和直接地利用网络资源。最新数据显示P2P应用技术的快速增长强烈冲击着Internet通信。在Gnutella的基础上，我们研究了一种更优的K-Random walk算法，主要研究搜索和复制，可以用来降低每次搜索的负载量。

一、主要的P2P网络模型介绍

现在主要的P2P网络模型有以下几种：

(一)集中式网络模型。在集中式P2P中，所有网上提供的共享资源都存放在提供该资源的客户机上，服务器上只保留目录信息，此外服务器与客户机之间以及客户机与客户机之间都具有交互能力。这种形式具有中心化的特点。集中式P2P主要缺点为：服务器具有接入带宽的瓶颈，一旦中央服务器的瘫痪容易导致整个网络的崩溃。

(二)分布式非结构化网络模型。在分布式非结构化的P2P中，采用洪泛查找机制。可以将一种完全分布的网络看成是一组对等节点之间的自组织网络。节点在进行资源查找时，首先将需要搜索的信息广播到它所有的相邻节点，然后再广播到所有相邻节点的相邻节点，直到找到需要查找的资源。这种查讯机制存在网络负荷过重、难以管理、稳定性差、扩展困难等缺陷。

(三)分布式结构化网络模型。结构化P2P模式是一种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务，目前的主流方法是采用分布式哈希表(DHT)技术，这也是目前扩展性最好的P2P路由方式之一。由于DHT各节点并不需要维护整个网络的信息，只在节点中存储其临近的后继节点信息，因此较少的路由信息就可以有效地实现到达目标节点，同时又取消了泛洪算法。该模型有效地减少了节点信息的发送数量，从而增强了P2P网络的扩展性。同时，出于冗余度以及延时的考虑，大部分DHT总是在节点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也避免了单一节点失效的问题。

(Du)Gnutel I a P2P系统。Gnutella是一个P2P文件共享系统，它和Napster最大的区别在于Gnutella是纯粹的P2P系统，没有索引服务器，它采用了基于完全随机图的洪泛(Floodimg)发现和随机转发(RandomWalker)机制。为了控制搜索消息的传输，通过TTL(Time To Live)的减值来实现。

二、Gnutella的工作原理及更优的搜索方法

在Gnutella的工作过程中，对等结点A在初始化时有在Gnutella网络中的对等结点B的IP地址，当^和B连接后，^可以获得B所知道的所有系统结点信息，这样A就可以选择某一结点建立直接的TCP／IP连接。每个Gnutella节点都定义了本地的共享文件夹，它们可以根据文件名的部分匹配或完全匹配进行查找。查找按照简单洪泛(flooding)方式进行，首先传播到所有相邻结点，再传播到相邻节点的相邻节点，直到达到预先确定的层次为止。每条查找消息都带有全局而惟一的标识符，防止对同样的查找消息进行多次响应。用户可以基于查找结果，选择合适的文件进行下载并可以和每个文件所有者结点建立类{~ITTP的连接。

Gnutella系统采用Flooding查询。在网络中，每个节点都不知道其他节点的资源，当从某一节点要寻找某个文件，就把这个查询信息传递给它的相邻节点，如果相邻节点含有这个资源，就返回一个QueryHit的信息给Requester。如果它相邻的节点都没有命中这个被查询文件。就把这条消息转发给自己的相邻节点。这种方式像洪水在网络中各个节点流动一样，所以叫做Flooding搜索，由于这种搜索策略是首先遍历自己的邻接点，然后再向下传播，所以又称为宽度优先搜索方法(BFS)。很显然，Flooding搜索有一定的盲目性。

Gnutella用基于TTL的洪泛方法来搜索目标。这种方法会产生很多冗余的信息，特别是在高连通的路径中。同时，由于受到网络重叠的拓朴结构和复制率的影响，很难找到合适的TTL，为了解决TTL的设置问题，可以用连续的洪泛并使TTL的值不断增加。这种搜索策略是在初始阶段，给TTL(Time To Live)一个很小的值，如果在TTL减为0时，还没有搜索到资源，则给TTL重新赋更高的值，直到找到目标为止。这个方法叫做反复加深深度搜寻法，这种方法的好处是：相对于比较冷的资源，比较热的资源能被大范围的复制。这种策略可以减少搜索的半径，但是在最坏的情况下，延迟很长。

然而，扩大半径并不能解决洪泛固有的复制问题，所以可以采取另一种方法：Random Walk(随机转发)。在随机转发中。请求者发出查询请求给随机挑选的相邻节点。然后每个查询信息在以后的转发过程中直接与请求者保持联系，询问是否还耍继续下一步。如果请求者同意继续转发，则又开始随机选择下一步转发的节点，否则中止搜索。我们叫这个消息为步，标准的随机漫步仅用一步，这大大减少了消息量，但是会增加延迟。为了减少延迟，我们增加了步数。请求者发出K个查询请求给随机挑选的K个相邻节点，然后每个查询信息在以后的转发过程中直接与请求者保持联系。询问是否还要继续下一步。如果请求者同意继续转发，则又开始随机选择下一步转发的节点，否则中止搜索，这就是k-walker random walk算法。

在非结构化的网络中，加快搜索的方法是在尽可能短的时间里找到对的节点，但是在找到要求的节点前，我们需要考虑以下三点：适度的中止，减少消息的复制量，和小范围的粒度。

1、适度的中止是非常重要的。基于TTL的机构不再工作，任何动态的中止将避免搜索的内部爆炸。

2、消息的复制应该要减到最小。每次搜索应该只对某一节点访问一次。过多访问在消息管理方面会造成浪费。

3、粒度的范围应该要小。在搜索中，每一个步的增加不要求增加大量的节点访问。这可能就是反复加深深度搜寻法和多步随机转发的区别。