Gnutella网络中基于消息跳数的分段搜索策略

董西广，张治国，张文欣

(1.河南工程学院 数理科学系,河南 郑州 451191; 2.河南工程学院 计算机科学与工程系,河南 郑州 451191;3.郑州大学 信息工程学院，河南 郑州 450001)

对等网络(P2P)是构建于因特网结构之上的一层覆盖网[1]，所谓对等是相对于传统的客户/服务器(C/S)模式而言的，它是指网络中所有的主机处于同等地位.在C/S模式网络中,客户机和服务器处于不同的地位，实现不同的功能.中央服务器是整个系统的核心，它完成网络中的大部分工作.客户机需要服务时可直接向服务器发出请求信息，服务器完成相应的功能后，把响应结果返回给请求客户机.C/S模式对服务器的过分依赖，使得网络容易产生瓶颈和单点失效的问题，这限制了网络的可扩展性，严重地影响了网络的整体性能.同时，处于边缘节点的客户机，其潜力常常被忽视而得不到充分发挥，造成了网络资源的浪费.P2P技术的出现,为解决上述问题提供了新的思路.

早期流行的P2P系统，如Naptster，它借助中央服务器来存储节点间的索引，节点与节点之间处于同等地位，发挥了边缘节点的服务能力，提高了系统的可扩展性，但这种中心化的设计仍然无法彻底解决单点失效和性能瓶颈的问题.经过不断的改进和完善，Gnutella网络应运而生，它是一个纯分布式的文件共享系统，没有中央服务器，所有的资源和服务都分散在网络中的不同节点上，从本质上避免了单点失效和性能瓶颈问题.但是,节点间完全对等的模式也使得网络中由于没有严格的拓扑或精确的文件定位信息而对传统C/S模式中很容易实现的资源搜索技术造成了很大的困难，在查询过程中保持一个足够大的查询覆盖范围就显得尤为重要,而洪泛的搜索机制天生就有这个优点.

洪泛机制是当前搜索算法中最重要的策略之一.在标准洪泛中，每个节点都拥有唯一的消息ID，节点通过把查询消息发送给所有的邻居节点(发送该消息给该节点的邻居节点除外)来完成本次消息的转发.节点在收到重复到达的相同消息后，就把该消息作为冗余消息直接丢弃，搜索过程的深度受消息生存期TTL的约束.消息产生时，被赋予一个初始的TTL值，在查询过程中，消息每向前一跳，TTL就减1，当消息变成冗余消息或TTL为0时，该消息被丢弃.

洪泛机制最大的优点是能够保持较高的查询覆盖范围，文献[1]指出，Gnutella网络中采用标准洪泛搜索策略消息可以在7跳内到达整个系统中95%以上的节点，这对于查询的完整性和有效性来说至关重要.在查询中，节点以并行方式转发消息的形式也有助于消息快速到达目标节点，从而缩短查询和响应的时间.正是由于这些原因，洪泛算法被广泛应用于非结构化对等网络中.然而，随着P2P系统的流行和网络规模的不断扩大，洪泛查询中产生的大量冗余消息也严重吞噬了有限的网络带宽和CPU计算资源，制约了网络的更进一步发展[2].

针对洪泛机制产生大量冗余消息的问题，根据搜索在不同阶段产生的不同结果，提出了一种新的基于消息跳数的分段搜索策略hpsearch.hpsearch策略的主要思想如下：根据标准洪泛机制中消息在处于不同跳数时所表现出的不同性能，对整个搜索过程进行分段处理，低跳时仍然采用标准洪泛机制，为查询覆盖范围积累必要的广度，同时有助于查询消息快速接近目标节点；高跳时不再向所有的邻居节点转发查询消息，仅仅随机选择其中的部分节点作为转发对象，尽量降低冗余消息的数量.

1 相关搜索算法

在非结构化P2P网络中，针对资源搜索问题提出了很多影响广泛的改进算法，如文献[3]提到的Rumor Mongering协议、文献[4]提到的Iterative Deepening协议、文献[5]提到的Gnutella with Shortcuts算法、文献[6]提到的Intelligent Search算法和文献[7]提到的Local Indices方法等.在Rumor Mongering算法中,消息在每一跳时仅随机选择部分节点而不是全部邻居节点来作为消息的转发对象，减少了冗余消息的数量，但屡次转发时节点选择的部分性和随机性降低了消息查询的完整性和可靠性.Iterative Deepening算法在增加深度的同时连续使用BFS搜索，初始时给定一个TTL值，在该范围内如果有满足查询的结果响应，则查询结束，否则增大TTL值，继续按照BFS策略进行查询.该算法查找热点信息较快，但对于一般信息的查找则可能与标准洪泛机制的开销相当.Gnutella with Shortcuts算法在系统中引入捷径表，查询时优先选择捷径表中的节点，当所有捷径都无效时再用洪泛算法.该算法在捷径有效时能够快速发现目标节点，但当原始捷径表中的目标文件被删除或目标节点离开时，系统的开销甚至会比洪泛机制还要高.Intelligent Search算法对邻居节点进行了简单的跟踪统计，如返回查询结果数量和网络延迟等信息，根据相应的标准选择最好的邻居转发查询，该算法虽然有助于快速接近目标节点、降低冗余消息数量，但对邻居节点的跟踪统计也要引入不小的开销.Local Indices算法是以索引为基础、系统中每个节点都保存与它距离为k内的所有节点上数据的索引，索引信息的有效性和维护索引的复杂度是影响该算法性能的重要因素.

以上改进算法确实在某些方面提高了效率、改善了网络的整体性能，但这些算法要么以系统搜索的完整性和可靠性为代价，要么仅仅适用于某些特定环境，要么以增加额外的开销为代价，难以在P2P网络中获得大规模的应用，无法在对等网络应用中得到普及.

2 基于消息跳数的分段搜索策略

洪泛机制依据消息的生存期逐跳展开，消息每向前一跳到达一个新的节点，该节点都会把该消息向自己所有的邻居节点转发，随着消息的不断向前推进，节点转发所产生的消息数量以指数级速率迅速增长，消息访问过的节点数量会越来越多，但每一跳时消息所到达的新节点的数量和产生的冗余消息数量是有所变化的.在初始阶段，消息到达的新节点的数量还比较少，尤其是在前3跳中，网络中的绝大部分节点都还没有被访问过，消息到达的节点基本上都是第一次收到该消息，消息到达新节点的数量与产生的转发消息的数量基本成正比，该阶段中查询消息快速覆盖网络且产生的冗余消息数量相对较少；而在后几跳中，网络中的不少节点都已经被访问过，消息到达新节点的概率就比较小，消息访问新节点的数量与转发消息的数量严重不匹配，转发所产生的消息大部分都属于冗余消息.

为了观察标准洪泛中消息的覆盖范围与冗余消息数量的变化情况，根据文献[8]指出的“幂规律”特性和文献[9]指出的“小世界”特性，构造网络N1，网络规模包括70 000个节点，平均连接度为25.3，查询过程中设定TTL=7.实验结果如图1与图2所示，图中分别给出了标准洪泛机制中每一跳时消息到达新节点的数量百分比和产生冗余消息的数量百分比.

图1 不同跳数时消息覆盖百分比Fig.1 Percentage of message coverage with different hop

图2 不同跳数时冗余消息百分比Fig.2 Percentage of redundant message with different hop

在前4跳中，每跳时消息到达新节点的数量直线上升，其中第3、4跳时分别占总数的22.91%和69.55%，而冗余消息的数量增长缓慢，尤其在前3跳中产生的冗余消息数量之和不足总量的1%.但从第5跳开始，消息到达新节点的数量迅速下降，在第5跳时仅占6.4%，第6、7跳时更低，而冗余消息的数量却快速增长，尤其是第5跳时，冗余消息的数量达72.24%，第6、7跳时冗余消息的数量又有所下降，这是因为前一跳时产生的大量转发消息中的大部分都将被视为冗余消息而丢弃，并没有参与后续的转发过程.

前4跳时，消息覆盖的范围持续扩大，冗余消息的数量相对较少，这个阶段中标准洪泛机制表现出很强的优越性；后3跳时，消息覆盖的范围迅速缩小，冗余消息的数量却明显增多，洪泛机制的性能严重下降，查询的覆盖范围和冗余消息的数量在整个消息生存期中表现出了明显的阶段性.因此,很有必要依据消息的跳数对搜索过程进行分段处理，可以把前4跳作为搜索过程的第一阶段，后3跳作为搜索过程的第二阶段.第一阶段时，仍采用原始洪泛搜索策略，节点在收到新的查询消息后把消息向所有的邻居节点转发，在保证消息高查询覆盖范围的同时，快速接近目标节点；第二阶段时，节点仅随机选择部分邻居作为消息转发的对象，尽量减少冗余消息量，提高网络的可扩展性.现有的搜索技术，在整个查询过程中，选择消息转发的目标节点的策略往往并不随着消息跳数的不同而变化，这在一定程度上造成了通信爆炸问题，严重影响了查询的效率.

改进后的基于消息跳数的分段搜索策略hpsearch，能有效地把标准洪泛选择和随机部分选择2个阶段的优势结合起来，能够在保持高覆盖范围的前提下尽量减少冗余消息的数量，有助于提高搜索效率，改善网络的整体性能.

hpsearch的主要过程可以描述如下：

根据TTL把搜索过程分为2个阶段，前h跳时，节点p通过将消息m发送给所有邻居来完成本次消息的传播；h跳以后，节点p通过将消息m发送给k个随机选择的邻居来完成本次消息的传播.

First divide the searching into two stages according to theTTL

When (node p receives a message m)

If(p has received m no more than one time and the hop is less than h)

p sends m to all neighbors that p has.

Else if(p has received m no more than one time and the hop is more than or equal to h)

p sends m to k neighbors which selected randomly that p has.

Else p drops the message.

3 实验结果与分析

实验以网络N1为基础，设定TTL=7，前4跳时按标准洪泛策略转发查询消息，后3跳时通过随机选择E(或EV比例)个邻居来完成消息的转发，从查询覆盖率和冗余消息率两方面来考察算法hpsearch的有效性.

以E=1…7为例，图3与图4给出了在不同参数下消息覆盖率和冗余消息率的变化情况.

由图3和图4可以看出，hpsearch的消息覆盖率相当于Flooding的96.8%以上，而冗余消息率最低却相当于Flooding的28.6%.文献[10]指出了LightFlood若要达到同样的覆盖范围，则需要额外增加2～3跳.不难看出，hpsearch要优于Flooding和LightFlood，它可以在搜索范围基本不变的情况下，减少70%以上的冗余消息.

图3 不同参数下的消息覆盖率Fig.3 Message coverage rate with different parameters

图4 不同参数下的冗余消息率Fig.4 Redundant message rate with different parameters

在实验过程中，通过不断改变后3跳中随机选择的转发消息数量的多少来观察hpsearch的性能，部分实验结果如表1所示.可以看到,hpsearch随着选择转发的消息个数(或比例)的增加，消息的覆盖范围随之增大，冗余消息的数量也会增加；当选择转发消息的数量达到一定比例后，再增加消息的转发数量，消息的覆盖范围就增长缓慢，而冗余消息的数量却增长较快.

表1 不同参数情况下的消息覆盖率和冗余消息百分比Tab.1 Rate of message coverage and redundancy with different parameters

4 结束语

洪泛是非结构化P2P系统中的重要搜索机制，它在查询过程中产生了大量冗余消息，严重浪费了网络资源，降低了网络的可扩展性.基于消息跳数的分段搜索策略hpsearch能够在保持高覆盖范围的同时，尽量降低冗余消息的数量，从而有效提高了查询的效率.对于不同稠密程度的P2P网络，如何更加合理地分段、定量随机选择转发消息的数量以及改进不同阶段的搜索策略是下一个阶段的研究重点.

参考文献：

[1] Ripeanu M, Foster I, Iamnitchi A. Mapping the gnutella network: properties of large-scale peer-to-peer systems and implications for system design [J]. IEEE Internet Computing, 2002(1/2): 50-57.

[2] Chawathe Y, Ratnasamy S, Breslau L, et al. Making Gnutella-like P2P Systems Scalable [C]. Proceedings of ACM SIGCOMM, 2003.

[3] Marius P, Aruna S. Cost-effective broadcast for fully decentralized peer-to-peer networks[J]. Computer Communications,2003,26(11):1159-1167.

[4] Yang B, Garcia H M. Improving search in peer-to-peer systems[A]. Proceedings of the 22nd International Conference on Distributed Computing Systems[C]. Washington:IEEE Computer Society,2002:5-14.

[5] Scipanidkulchai K,Maggs B, Zhang H. Efficient content location using interest-based locality in peer-to-peer systems[A]. Proceedings of IEEE INFOCOM 2003[C]. San Francisco: IEEE Computer Society,2003:2166-2176.

[6] Kalogeraki V, Gunopulos D, Zeinalipouryazti D. A local search mechanism for peer-to-peer networks[A].Proceedings of the 11th ACM Conf on Information and Knowledge Management[C]. New York:ACM,2002.

[7] Yang B，Garcia Molina H. Improving search in peer-to-peer networks[C]. Proceedings of the 22nd IEEE Int Conf on Distributed Computing(IEEE ICDCS’02),Picataway,2002.

[8] Watts D J, Strogatz S H. Collective dynamics of small world networks[J]. Nature, 1998,393(6):440-442.

[9] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999,286(10):509-512.

[10] Jiang Song, Guo Lei, Zhang Xiaodong. LightFlood:an efficient flooding scheme for file search in unstructured peer-to-peer system[C]. Proceedings of the 2003 International on Parallel Processing, 2003.