Gnutella环境下资源定位方法的改进

吴明生富美科技有限公司技术研发中心 山东 250306

0 前言

Gnutella网络目前被广泛的用来实现文件，特别是视频及音频文件的共享，作为无中心非结构化的P2P网络，其资源定位的查找效率及网络可扩展性问题一直是针对 Gnutella网络的研究热点。本文在已有研究的基础上提出了一种新的机制，节点在定位资源时仅使用Gnutella网络的部分通路，把该机制简称为基于部分通路的方法。

1 基于部分通路的方法

1.1 基本概念与节点的数据结构

在Gnutella网络中一个节点的“度”是指到达这个节点的边的个数，基于部分通路的方法需要在Gnutella网络上建立一层逻辑结构，把度的概念引入此逻辑结构，节点在此逻辑结构上的“度”称为逻辑度。为了说明基于部分通路的方法给出以下定义：

定义1：度节点与反度节点

对于一个要加入Gnutella网络的节点，选出逻辑度较大的几个邻居节点，这些邻居节点的逻辑度之和刚好大于等于一个设定的值 Degreesum，把这些邻居节点称为加入节点的度节点。把加入节点称为这些邻居节点的反度节点。

定义2：度链接

度节点与反度节点间建立的逻辑链接称为度链接。

定义3：度生成网络

Gnutella网络中所有的度链接形成一个网络，把该网络称为度生成网络。度生成网络是Gnutella网络中所有通路的子集所形成的网络。图1(b)、(c)中的双向箭头链接所形成的结构就是度生成网络。

定义4：逻辑度(Logical Degree)

在度生成网络上与一个节点相连的度链接的个数就是上面所说的逻辑度。例如，在图 1(b)中，节点 P1、P2加入前，P4的逻辑度为1，P5的逻辑度为2。实际上，逻辑度就是节点在度生成网络上的度。

例如，假设Degreesum=2，从图1(a)可知，在P1和P2未加入之前，加入节点P1有2个邻居节点P3、P4，从图1(b)可知，P3、P4的逻辑度均为1，这样在P加入之后，P3、P4成为P1的度节点，P1成为P3、P4的反度节点，在P1与P3间建立的逻辑链接称为度链接。P2加入时，因邻居接点P1、P4和P5的逻辑度均为2，所以仅需选择通讯延迟较小的P5建立一条度链接。

定义5：度广播搜索

把在度生成网络上进行的广播搜索称为度广播搜索。在基于部分通路的方法中，规定查询消息只能在建立了度链接的通路上传输，在其他通路上不能传输。

图1 节点P1、P2加入Gnutella网络

在基于部分通路的方法中，一个节点上要维护两类信息：第一类信息记录度节点的地址，第二类信息记录反度节点的地址，如图2所示。

图2 节点上创建的数据结构

1.2 相关操作的过程

（1）节点加入

节点加入Gnutella网络的过程可以分为两个步骤：①节点通过TTL值为1的传统广播，选出逻辑度较大的几个邻居节点作为度节点，这些邻居节点的逻辑度之和刚好大于等于一个设定的值Degreesum。如果因为邻居节点太少或度太小，所有邻居节点的逻辑度之和小于 Degreesum，就要选出所有邻居节点。②建立加入节点的度节点信息，同时度节点把加入节点加为反度节点。

（2）定位资源

假设 TTL=H。节点使用基于部分通路的方法定位资源时，只需进行跳数为 H的度广播搜索。如果一个节点收到UID相同的Query消息，就把Query消息丢弃，不再转发；如果一个节点存有所求的资源内容，就停止Query消息的转发，响应到达的Query请求，回复QueryHit消息，通知请求节点所求资源已经找到，建立HTTP连接进行文件传输。

（3）节点离开

当一个节点Pleave要离开Gnutella网络时，在真正切断它之前，要通知与其联系的节点，以便这些节点可对Pleave的离开做出相应处理。Pleave的度节点收到Pleave的离开通知时，把Pleave从其反度节点表中删除。Pleave的反度节点收到Pleave的离开通知时，把Pleave从其度节点表中删除，然后执行加入操作。

（4）维护

执行维护操作时，各节点需要检查其度节点和反度节点的活性，并删除或更换无效的信息。在具体实现维护操作时，基于部分通路的方法借助 Gnutella协议的消息传播规则：QueryHit消息总是沿着Query消息转发的路径逆向传输。遵循此规则，节点 P对与自己建立联系的每个节点 Pi发出Query消息，在Pi不失效的情况下，P将收到 Pi发回来的QueryHit消息。如果在一定的时间内未收到来自Pi的回复消息，就可以认为节点 Pi已经失效，就要删除或更换有关 Pi的信息。

2 仿真及其结果分析

2.1 仿真设置及性能指标

在 Red Hat9.0下运用 Gnutella仿真软件 Packet-level Gnutellasim进行实验。仿真时节点数目在1000到3000之间变化。仿真中产生10000个文件作为网络内容，根据记录文件“ClarkNet-HTTP”把它们分到不同节点上，各节点也根据此记录文件发起资源查询请求，查询请求的个数设为2000。TTL值设为 6，邻居节点的逻辑度之和要达到的值Degreesum设为2。每个网络大小使用三个不同的由GT-ITM产生的网络拓扑模拟三次，所列仿真结果是重复实验后计算的平均值。

一般使用以下指标来评估资源定位方法的性能：

（1）询问消息数：用来定位网络中资源的询问消息个数。这里用两种方式统计这个量：①只统计一次资源搜索过程所引起的询问消息个数；②统计所有节点进行资源定位及维护操作所引起的总询问消息个数。

（2）范围：一次搜索过程所访问的节点个数。

在相同搜索范围下，访问消息少的资源定位方法较好，或者说产生相同询问消息数时，搜索范围大的资源定位方法较好。

2.2 对比结果

2.2.1 询问消息数

从图3可以看出，完成一次资源搜索平均所引起的消息个数有如下特点：①使用基于部分通路的方法一次资源搜索过程所引起的消息个数远小于使用传统广播搜索法所引起的消息个数；②当节点个数增加时，两种方法所引起的消息个数都增加。

图3 一次资源搜索过程所引起的消息数

每个节点要定期检查与其建立联系的节点是否存在，每100个节点加入网络后要利用维护消息更新路由信息。从图4可以看出，在节点进行资源定位及维护操作时，使用基于部分通路的方法所引起的通讯负载远小于使用传统广播搜索法所引起的通讯负载；并且当节点个数增加时，两种方法所引起的通讯负载都增加。

图4 资源定位及维护操作所引起的通讯负载

2.2.2 范围

从图5可以看出，使用基于部分通路的方法时查询请求的平均搜索范围低于使用传统广播搜索法时查询请求的平均搜索范围。

图5 查询请求的平均搜索范围

3 结论

为了减少Gnutella网络中资源定位时的冗余消息，提高Gnutella网络的可扩展性，本文提出了基于部分通路的资源定位方法。运用此方法所构建的逻辑结构不但使网络的“幂规律”特征更加突出，而且还减少了网络中的回路。仿真实验的结果显示出，在相同搜索范围下，基于部分通路的方法所引起的通讯负载小于传统广播搜索法所引起的通讯负载，这些对于未来智能网络打印机的研发具有深远意义。

[1]The Gnutella protocol specification v0. 4. http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf.

[2]Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology [J].ACM SIGCOMM Computer Communication Review.1999.

[3]黄道颖,刘刚,张尧.利用Gnutella网络的拓扑特性改进其可扩展性[J].计算机工程与应用.2003.

[4]ClarkNet-HTTP.http://ita.ee.lbl.gov/html/contrib/ClarkNet-HTTP.html.

[5]Zegura E W, Calvert K L, Bhattacharjee S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM’96, San Francisco.CA: IEEE Computer Press.1996.