基于Gnutella的LRU查询算法改进

王春枝，孙 航，陈宏伟

（湖北工业大学计算机学院，湖北 武汉430068）

近年来P2P已成为互联网行业非常热门的技术，它既可以极大缓解传统集中式网络架构中服务器压力过大、单点失效等问题，又能够利用终端的丰富资源，因此P2P技术广泛应用于计算机网络的各个领域［1］.经过数十年的发展，P2P网络已经从第一代混合式P2P网络体系发展到现今的纯分布式P2P网络体系［2］.混合式P2P网络体系主要有集中式和层次式两种，他们通过一些中心服务器来维护节点信息和数据信息.这样容易产生单点容错和性能瓶颈等一些问题.无结构P2P网络［3］主要是基于消息泛洪的搜索机制［4］，通过节点之间消息的大量转发实现查询，从而导致其路由效率不高、可扩展性不高、数据无法准确定位等缺陷.纯分布式无结构网络维护开销小，但会产生大量的消息转发和冗余，给系统带来巨大的开销，造成网络流量负担.

1 常见的几种无结构化P2P查询算法

1.1 泛洪算法（Flooding）

该算法的思想是，在网络中节点相互之间都不知道其他节点的资源，当节点需要搜索某个资源时，查询节点向它的所有邻居节点广播查询消息，为了限制搜索范围，发起查询请求的节点会在消息中设置一个初始的TTL值，消息每经过一个节点TTL都会减1，直到TTL值为0停止搜索.

1.2 随机漫步（Randon Walker）

该算法是在响应时间和网络负担之间做了另一种权衡，Randon Walker方法针对泛洪算法的缺陷，严格控制每一步过程中扩散查询的力度Random Walker方法在每次传递查询消息的时候，只把消息传递给随机选择的一部分邻居节点.

1.3 扩展环法（Expanding Ring）

该算法是在初始阶段给定TTL一个比较小的值，等待是否查询到目标资源.如果成功查询到所需资源则结束查询，否则增加TTL的值进行新的查询过程.

2 小世界网络

小世界网络模型的聚类系数C（g）和特征路径长度L（g）的特性都可以看成是重连概率P的函数.规则网络的P＝0，是一个高度聚类，特征路径长度大的网络模型，随着P趋向1时（0＜P≤1），重连得到的网络与原始规则网络的局部属性只有较小的改变，因此网络的聚类系数的变化也不大，但是重连网络的特征路径长度却有大幅的下降.这种有较高的聚类系数特征路径又较短的网络就是小世界网络，它是一种介于随机网络和规则网络之间的网络.小世界网络模型如图1所示.

分析图1的网络模型可以看到：在规则网络中，两个任意节点的连接都是既定的，而随机网络中的任意两个节点是完全随机连接的，这两种网络都不符合小世界现象.经研究表明，Gnutella网络符合小世界特征，因此在Gnutella网络中存在大量的高连通节点，且部分节点间存在短链，也就是说Gnutella是一种具有局部性的网络.针对无结构P2P网络的缺点和Gnutella网络符合小世界网络模型的特点，本文提出一种基于LRU的查询算法来提高无结构P2P网络的查询效率.

图1 小世界网络模型

3 基于LRU的路由学习查询算法

3.1 LRU算法

LRU［5］是根据页面调入内存后使用情况来决策的一种算法.因为页面的将来使用情况是无法预测的，而页面已使用的情况是可以控制的.因此LRU替换算法设计中，假定一个最近被访问过的页面，很可能在不久后又被访问，这明显的是利用局部集的优点.设在t时刻页面r的后面距离为BWDt（r），它是指页面访问流中的同一页从当前点到以前一个访问点的距离.后方的距离总是大于0，如果没有一条访问记录，那它就是无限大.在LRU算法中，被替换的页面是指有最大后方距离的记录：

LRU算法实质上是根据局部性原理，最近一段时间内被访问的页面，在将来的一段时间内会被经常访问，而把最近最长一段时间内没有访问的页面淘汰.

3.2 LRU路由查询算法的思想

本算法是根据Gnutella网络［6］符合小世界网络的特性，利用LRU的思想来更新节点存储邻居节点的 SockMap＿t容器的前 Length个元素［7］.SockMap＿t容器使用的是＜NodeAddr＿t，SockEntry＞的键值对来存储邻居节点.SockEntry类的对象就是邻居节点对应的信息，为该类添加一个时间变量time，用来控制LRU的替换.初始情况下time赋值为0，当节点与其他节点（设该节点为A）发生查询关系时，首先判断容器里是否有相等节点，若有相等节点，则把容器里A节点的time赋0值，然后把容器内所有邻居节点的time加1；若没有相等节点，则把容器内time值最大的邻居节点用节点A替换，同时所有节点time加1.如果在前Length个元素中没有找到所需资源，那么就向SockMap＿t容器的Length长度后面的邻居节点发送查询信息，直到找到资源或者TTL减至0为止，结束整个查询过程.

3.3 泛洪查询模型

Gnutella协议是一种纯分布式网络协议，它使用的查询算法是泛洪算法.当网络中的某个节点需要查询资源时，该节点会向它的所有邻居节点发送查询信息.当接受到查询信息的节点包含所需资源时，就会发送一个查询命中的消息沿查询路径返回；否则就向其邻居节点继续转发查询消息，以此类推，这个过程将不断进行下去.为了限制搜索的范围，查询消息会设置一个初始TTL值，消息每转发一次TTL值就减一，直到TTL减为0或发现资源，搜索过程终止.

图2 泛洪查询模型

图2 中，当网络中节点A需要查询资源S时，它向B、C和D等它的所有邻居节点发送Query查询信息.B、C和D等节点搜索本地资源列表发现没有匹配资源，则继续向它们的所有邻居节点转发Query消息，直到找到资源或者TTL减为0，则停止查询.图2中，节点C向它所有邻居节点转发Query消息，当Query消息到达节点X时，找到匹配资源，节点X回复QueryHit消息，该消息沿Query消息路径回到节点A.然后建立连接进行资源下载.在这个查询过程中，网络的查询消息成指数倍增加［9］.

3.4 改进后的LRU查询模型

本文提出的基于LRU的查询算法是利用LRU的思想来维护节点存储邻居节点的容器SockMap＿t.当需要查询某资源的时候，首先向SockMap＿t容器中使用LRU维护的邻居节点发送查询消息，如果找到资源，则结束查询（图3）.

当网络中节点A需要查询资源S时，它向其部分邻居节点B、C和D发送Query查询信息.B、C和D节点搜索本地资源列表发现没有匹配资源，则继续向它们的部分邻居节点转发Query消息.这里所说部分邻居节点就是利用LRU思想更新，存储在SockMap＿t里的前Length个节点.若TTL减为0还是没找到所需资源，那么就向SockMap＿t容器中Length长度之后的邻居节点发送查询消息［10］（图4）.

通过以上模型可以知道，基于LRU的查询算法首先对节点容器Length长度以内的部分邻居节点发送查询消息，如果没找到所需资源则向节点的其他邻居节点发送查询消息.因此可以在一定的查询成功率的基础上，提高热门资源查询的速度，减少网络中查询消息的转发和冗余，在减小网络开销的情况下，适应较大的网络规模和复杂的网络环境.

4 网络性能参数分析

4.1 时延抖动

网络的状态是随时变化的，网络中的流量也是不稳定的，当流量较大的时候，许多数据分组就在节点的队列中排队，因此每个数据分组在传输中的时延并不一致.时延抖动J（Jitter）描叙的是网络传输时延的变化情况，时延抖动越大，则表示网络越不稳定.本文将时延抖动定义为以前后两个不同分组数据之间的不同时延之差，即

4.2 吞吐量

网络吞吐量（Throughput）是网络性能的一个重要参数，是指没有丢包的情况下单位时间内节点接受的数据量.端到端的吞吐量与网络状况有很大的关系，如果网络中的吞吐量过大，会导致网络的拥塞、分片等一系列问题.本文定义吞吐量为

式中，TB（i）是指到第i个分组被目的节点接受时，已经传输的数据量；RT（i）则是第i个数据包接受的时间；i＞m，表示计算从第m个分组到第i个分组的吞吐量，当且仅当m＝1时，TH（i）m是平均吞吐量.

5 仿真实验

本实验从节点的数量和查询消息数量的关系，以及网络时延抖动和吞吐量两个方面对提出的LRU的查询算法和泛洪算法进行比较.本实验在Linux Redhat操作系统中安装NS－2仿真软件，然后集成Gnutella协议，利用OTCL脚本编写的代码对实验进行仿真，并对仿真实验所产生的实验trace文件数据利用gawk进行分析和计算，最后使用gnuplot进行画图，从而比较泛洪查询和基于LRU的查询的吞吐量和时延抖动.由图5可以看到，使用了LRU查询算法的Gnutella网络中，网络的吞吐量有明显下降，事实上在基于LRU查询算法的Gnutella网络中，可以有效地控制泛滥的查询消息的转发，提高热门资源的查询效率以及降低消息的冗余度.图6显示了Gnutella网络的时延抖动，在使用泛洪搜索的Gnutella网络中，因网络查询消息以指数倍增长，使得网络的某些时刻会产生很大的时延，从而网络可能会出现断链等不稳定的现象，因而网络中的延时抖动幅度较大，并且不稳定.而在采用LRU控制的Gnutella网络中，因其吞吐量的减少，使得基于LRU查询的Gnutella的网络趋于一个比较小的稳定的区间内.

6 结束语

本文针对无结构P2P网络中Gnutella协议的泛洪查询算法的查询效率低和消息泛滥的问题，提出了利用LRU的思想来更新存储邻居节点信息的SockMap＿t容器，可以使网络中的查询消息有效减少，同时可以改善热门资源的查询效率，并且网络趋于一种比较稳定的状态.

［1］杨 舰.对等网络有效搜索机制研究［D］.上海：复旦大学图书馆.2004.

［2］Yang B，Garcia－Molina H.Improving search in peerto－peer networks［J］.In Proceedings of 22nd Int’l Conference，2002，3（9）：5－15.

［3］Liu Y，Xiao L，Liu X.Location awareness in unstructured peer－to－peer system［J］.IEEE Transaction on Parallel and Distributed Systems，2005，16（2）：163－174.

［4］Hongbo Jiang，Shudong jin exploiting dynamic querying like flooding techniques in unstructured peer－topeer networks［C］.Washington DC，USA：IEEE Computer Society，IEEE Computer Society.Proceedings of the 13TH IEEE International Conference on Network Protocols 2005：122－131.

［5］Song Jiang，Lei Guo，Xiaodong Zhang，et al.Light－Flood：Minimizing redundant messages and maximizing scope of peer－to－peer search［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（5）：601－614.

［6］夏启志，谢高岗，无结构P2P网络搜索方法及其改进［J］.计算机应用研究，2005，22（9）：256－260.

［7］Vana Kalogeraki Dimitrios Gunopulos D.Zeinalipour－Yazti.A local search mechanism for peer－to－peer networks CIKM 02［C］.Virginia，USA：Mclean，2002.

［8］黄道颖，刘 刚.利用Gntella网络的拓扑特性改进其可扩展性［J］.计算机工程与应用，2003，39（26）：58－60.

［9］杨东峰，庄 雷.基于稠密P2P网络搜索机制的研究［J］.计算机工程与应用，2006，42（24）：111－114.

［10］庄 雷，董西广，常玉存.非结构化P2P网络中基于连接度的分段搜索策略［J］.计算机应用，2008，28（3）：549－552.