基于节点流行度的Gnutella路由查询策略

1、基于节点流行度的Gnutella路由查询策略    论文导读：Gnutella网络因为没有中心服务器，对等节点查询消息完全由加入系统的对等节点转发，所以被认为是纯分布式P2P系统。传统的Gnutella网络搜索算法8利用广播方法来进行查询。研究表明1，Gnutella网络中文件被访问的频率呈幂律特征，即少数文件流行度很高,被频繁请求查询，而多数文件则很少被访问。 关键词：Gnutella，无结构，查询，流行度    1 引言 Gnutella网络因为没有中心服务器，对等节点查询消息完全由加入系统的对等节点转发，所以

2、被认为是纯分布式P2P系统。传统的Gnutella网络搜索算法8利用广播方法来进行查询。这种方法会造成网络中查询消息以指数级增长，在网络中产生大量冗余查询消息，造成局部网络拥塞，出现分片现象。 研究表明1，Gnutella网络中文件被访问的频率呈幂律特征，即少数文件流行度很高,被频繁请求查询，而多数文件则很少被访问。科技论文。网络中流行度较高的文件会在网络中留下较多副本，因此，流行度较高的文件更容易查询成功。Gnutella网络呈现典型的“幂规律”（power-low）和明显的”小世界”(small world)特征2。 研究表明，Gnutella网络节点的拓扑特征具有“幂规律（Power-l

3、ower）2”特性和“小世界”特征2。 1)“幂规律”(Power Law)特征即“度”为k的节点的分布概率满足以下公式： 2)“小世界”(Small World)特征的意思是网络拓扑具有高聚集度低特征路径长特征。科技论文。网络聚集度和特征路径长的定义简述如下。在符合“小世界”特征的网络模型中，可以根据节点的聚集度将节点划分为一个个的Clusters具有强聚集性的节点具有很高的连通度。 如何提高Gnutella网络查询效率近年来一直是研究热点，传统的Flooding算法虽然可以获得较高的查询效率，但是会造成大量冗余查询消息产生，造成网络局部拥塞。本文根据文件流行度研究成果1和Gnutella网

4、络拓扑特征2提出一种基于节点流行度和Gnutella网络拓扑特征的查询算法。 2 相关工作 以往的研究提出了很多Gnutella网络查询改进算法。Grokster、KaZaA和Morpheus等提出一种基于超级节点的路由查询策略3。超级节点维护本区域内对等节点文件索引，查询只在超级节点之间转发，避免网络中大量冗余消息的产生。文献4提出了改进的广度优先搜索(Modified BFS)方法 ，该方法在转发查询消息时随机选择几个邻居节点，这样可以避免产生大量的冗余消息，但查询时节点覆盖度有限。随机漫步(Random walkers) 5 :该方法节点随机选择一个邻居节点，转发查询消息，直到TTL为0

5、，该方法查询响应时间长。 3 基于流行度的Gnutella网络路由查询策略 本文提出的搜索方法充分利用Gnutella网络拓扑特性和文件流行度的研究成果。文献1中提到，文件访问频率呈幂规律特征，少数文件流行度很高，频繁的被访问和查询。流行度高的文件会在网络留存较多副本，查询命中的概率较大。本文提出一种结合Gnutella网络拓扑和节点流行度的查询算法，该方法充分利用Gnutella网络拓扑特征和节点流行度的概念。 3.1 用到的概念 3.2 基于流行度的Gnutella路由改进策略 本算法的主要思想是查询时充分利用Gnutella网络拓扑特征和流行度的研究成果。查询充分利用节点流行度和Gnut

6、ella网络拓扑特征，采用类似随机漫步的思想，转发查询消息给节点度和流行度大的节点。 在介绍本文算法前，先给出以下定义： 3.2.1 节点要保存的数据结构 节点中除了要保存邻居节点的信息之外，还要保存每个邻居节点的查询度信息。查询消息到达时，节点根据每个邻居节点的查询度信息来确定查询消息转发对象。该数据结构通过定期的心跳机制来更新。 节点要保存的数据结构 节点将每个邻居节点按查询度排序，由高到低。查询时，在邻居节点中选择一定数量的邻居节点发出查询消息。选择的策略将在下文详细介绍。 3.2.2 基于流行度的Gnutella无结构化网络路由查询策略 本文提出的搜索方法利用节点的流行度和Gnutel

7、la网络特征，节点加入网络后，通过和邻居节点交换信息从而得到每个邻居节点的查询度信息。查询度信息是综合节点的流行度和节点的聚集度的一个参数。查询时，节点选择邻居节点中查询度较高的作为路由查询消息转发对象。节点的流行度和聚集度越高，查询成功的概率越大，因为由文献1中的研究结果表明，网络中某些文件被查询的概率较大，被频繁的查询和请求，因而会在网络中留下较多的副本，查询成功的概率也较大。 本文把查询消息分为两类，一类是路由查询消息，一类是查询消息。科技论文。 本文提出的算法，当某个节点查询时，首先扫描自己的邻居节点，选择自己邻居节点查询度较大的节点，发出路由查询消息。为了使得流行度较低的节点也能被查

8、询到，使每个节点按查询度大小有序排列，发起查询的时候，将邻居节点按查询度大小分为两部分，一部分查询度较大，一部分节点查询度较小。某个节点要发起查询时，可以在两部分中分别随机的选择一个节点发出路由查询消息。这样就可以避免流行度和聚集度较低的节点不能被查询的情况和网络中的很少被查询的节点可以被查询到。当一个节点收到消息，首先检查该消息类型，若是查询消息，则检索自己的资源索引表，然后将结果反馈给来源节点；若是查询路由消息，则查询自己文件索引表，看是否有需要的资源；然后，向自己除来源节点之外的所有邻居节点发出查询消息，查看有无此资源。返回后，若无此资源，则依据上面提到的规则转发路由查询消息。 在每个路

9、由查询消息中设置一个TTL域（生存周期），每次发起查询请求时，都给它设定一个初始值。当节点收到查询消息时，首先检查是否已经收到过该路由查询消息。如果是则丢弃；若不是，则检查TTL，若为0，则丢弃；若不为0，首先在自己的资源索引中查询所要查询的资源，若无，则向除消息来源节点以外的节点发送查询消息，等待返回；若无查询命中，则依据上面的规则转发路由查询消息。这样可以充分的控制查询的深度和控制大量冗余查询消息的产生。节点转发查询消息的时要遵循将来源节点排除在外的原则。 本算法的伪代码如下： If(Recv(querrymessage) Search(Index); /节点收到查询消息 Else Rec

10、v(querryroutemessage); /一个节点收到路由查询消息 If (Check(querrymessage); Drop(querrymessage); /检查是否收到过次路由查询消息 If(qerrymessage.TTL=0) Drop(querrymessage); /检查查询消息生命周期 Search(Index); /查询本地索引表 Search(Neighbor)； /查询邻居节点 Transmit(querrymessage); /转发查询消息 网络中局部图结构（a>b>c） 4 改进后性能分析 本文提出的算法，由于频繁被查找的资源在网络中有着较多副本，

11、所以频繁被查找的资源更容易查询成功。本文算法充分利用了流行度的研究成果，来提高网络的查询成功率。这样可以大幅度提高网络中查询成功的概率，但是也会造成网络中边缘节点流行度较低的节点不能被查询到的情形，所以我们利用类似随机漫步的思想，在查询度较小的节点中随机选择部分节点作为查询消息的转发对象，这样就可以保证流行度较低的节点也可以被查寻到。 本文算法所要维护的数据结构只是在邻居节点的基础上另外维护了一个邻居节点的查询度信息，因而不会对网络造成额外的维护负担，查询度信息的更新利用心跳机制来完成，在发送心跳信息时可以携带本节点的查询度信息，因而不会对网络造成很大的维护负担。 由于本文算法利用了随机漫步的

12、思想，所以可以有效的控制查询消息和冗余查询消息的产生，不会对网络造成太大的负担。查询效率方面，由于本算法充分利用了节点的流行度信息，因而可以在不用覆盖太多节点的情况下获得较高的查询效率。 1 ADAMIC L A , LUKOSE R M, PUNIYANI A R ,et al . Search in Power-law networks J . 2 Jovanovic MA. Modeling large-scalepeer-to-peer networks and a case study of Gnutella MS. Thesis. University of Cincinnati,

13、 2001. 3 杨舰. 对等网络有效搜索机制研究D . 上海复旦大学. 2004。 4 Vana Kalogeraki,Dimitrios Gunopulos, D. Zeinalipour. ALocal Search Mechanism for Peer-to -PeerNetworksC . ACM Press. 2002. 300 - 307. 5 Qin Lv, Pei Cao, EdithCohen, et al. Search and Replication in unstructured Peer-to-Peer Networks C. ACM Press. 2002. 84 - 95. 6 Beverly Yang, Hector Garcia - Molina.Imp roving Search in Peer - to - Peer Networks C . IEEE Computer Socie2ty.2002. 5. 7 利用网络的拓扑特性改进其可扩展性黄道颖 解放军资讯工程学院，郑州 （郑州轻工业学院，郑州） 8 ht