朱永琼，罗飞

1、武汉商学院430056

2、武汉大学430072

摘要：P2P网络中负载均衡已成为一个突出、需要解决的问题。本文提出一种负载均衡的路由模型并在此基础上实现搜索算法。本文设计的搜索算法的目标是在提高系统吞吐率的基础上最大化资源利用率、尽可能减少平均搜索延迟，并且网络开销要小。

关键字：P2P网络；负载均衡；洪泛；随机漫步；

1 引言

近年来,P2P软件用户增长迅速,负载均衡已成为一个突出、需要解决的问题。由于在P2P环境下,单个结点无法准确了解全局负载分布信息和用户查询具有不平衡性,使平衡各结点负载成为一个难以解决的问题。

在无结构P2P网络中，针对其搜索效率低下的问题提出了很多改进的算法，如yang的APS，这些算法的目标是使搜索的平均延时（往往以跳数来衡量）尽可能的小并且开销要小，但是这些搜索算法都没有考虑到P2P系统中的负载不均衡导致网络某些链路出现拥塞或者“热点”现象。在网络搜索过程中，查询消息在节点间的延迟是由三个方面组成的，即节点间的传输延时、消息在节点中的排队等待时间和消息的处理时间。一旦网络负载不均衡则会在部分负荷较重的节点上出现消息滞留排队或丢包的现象，导致查询延时增大，搜索效率降低，严重的还能使节点停止工作网络瘫痪。而引起负载不均衡的原因主要有以下几点：1)节点能力的异构性。由于P2P系统中节点加入的随意性，使得网络中的节点在接入带宽、CPU计算能力，磁盘和内存空间等方面存在许多的异构性。节点能力的不同导致节点对消息处理的效率存在明显的差异，能力强的节点能够处理更多的消息而能力弱的节点相对来说更容易产生滞留排队的倾向。2)节点共享文件的差异较大。每个节点共享文件的内容和数目都不一定相同，共享的文件越流行数目越多，其被访问的概率也越大。3）查询分布的不均衡。研究发现,P2P系统中的查询请求分布服从Zif分布定律，各关键字查询的概率存在数量级差异,承载热点文件的结点负载将远大于其他结点.节点之间的负载及不均衡。

为了改善网络性能，充分利用网络的传输能力，人们必须要在设计无线自组网路由协议时考虑负载均衡问题。做到在新的路由建立过程中，避开负载较重的节点或者区域，使得网络业务流尽量从负载较轻的区域穿过；在数据沿路由传送过程中在遇到负载较重或者部分区域拥塞时有相应的机制进行处理。避免网络的部分区域的节点会由于承受较大的网络负载而产生网络拥塞，而部分区域的节点则会因为中继任务少而处于相对轻闲的状态，导致网络负载失衡。负载均衡的实质，是利用网络中可能存在的不同分组传输路径来构建分组的实际传输路由，通过有足够剩余容量的节点转发分组，以减轻网络的局部拥塞，适应网络中负载的动态变化，尽可能减少分组丢失和提高网络吞吐率，为业务提供更好的QoS保证。

针对大部分搜索算法均未考虑到节点负载均衡的不足，本文提出一种负载均衡的路由模型并在此基础上实现搜索算法。本文设计的搜索算法的目标是在提高系统吞吐率的基础上最大化资源利用率、尽可能减少平均搜索延迟，并且网络开销要小。

 

2 相关工作

在P2P网络中，为了提高搜索效率提出了各类高效的搜索机制，即盲搜索算法和基于知识的算法。盲搜索算法是针对基础的洪泛和随机漫步搜索算法的优化。由于采用洪泛搜索机制的P2P系统会产生70%的冗余消息，文献[1]提出一种轻量级的洪泛机制在保证有相似搜索范围的同时能够将查询消息的数目降低69%。文献[2]将洪泛和随机漫步交替使用，短路径搜索使用洪泛而长路径搜索使用随机漫步。文献[3]对网络中节点最感兴趣的共享文件和全局最不流行的共享文件建立部分索引帮助节点找到兴趣相似的节点，加速定位不流行的文件，显著提高了搜索成功率和命中率。文献[4]中的节点根据缓存内容来计算节点之间的语义相似度并提供一种全分散的方法来评估文件的流行性，在真实的eDonkey上验证了方法的有效性。文献[5]基于概率理论框架构建了用户兴趣模型UIM，在此基础上通过开采用户的通用兴趣设计搜索协议和路由表更新协议，并进一步将P2P网络呈现小世界的特性。虽然这些算法都能够从理论和实验上证明其能够获得更好的性能，如获得更高的搜索成功率、命中率，更少的搜索评价延时更少的开销等等，但是其假设的前提是网络的状况是良好的，节点之间的负载是均衡的不会发生拥塞，而网络拥塞是不可避免的，因为节点的能力是有限的，一旦发送消息的速率超过节点的处理速率就会产生拥塞，而拥塞的后果有两种：一种是造成排队现象。一旦大量的消息在节点排队等待处理，就会大大增加消息延迟，那么在以前的评价标准中，消息在每跳间传播的延时赋予固定数目的计算方法在网络发生拥塞时就不准确，消息在拥塞节点上消耗的时间会更长。另一种是产生丢包现象。节点过度拥塞会丢弃部分消息，导致搜索成功率和命中率的下降。而提高搜索效率和达到网络负载均衡往往是相互矛盾的。为了尽快的找到搜索目标，查询消息在路由转发时根据经验（如节点兴趣相似性，命中率等）往往选择最可能找到目标文件的节点进行转发以获得更短的搜索平均跳数，为了达到负载均衡，节点转而会选择负载较轻的节点进行转发消息，但是这样的转发路径往往不是最短路径，因此，需要在搜索效率和负载均衡之间达到一种平衡，希望提出的搜索算法不仅能获得好的搜索效率同时能够保持节点间的负载均衡。

3方法

3.1系统模型、定义和说明

定义一：P2P网络。P2P 网络表示为无向图 ，其中V是网络中节点的集合，E是边的集合。对于网络中的任意节点 ，如果 则必有 。对于任意节点 ，其邻居集合记为 。

定义：P2P搜索模型。假定p是网络中的一个节点，p上共享文件的集合为 ，对于 中的任一文件有 。从P节点发起的一个查询记为 ，以 表示。其中f代表要查询的文件， 记录一个查询消息在查询结束之前所访问过的所有节点，显然， 的尺寸不会超过TTL。

定义：节点的命中率 。假定系统总共发起了N次查询，节点i的命中次数为 ，则节点i的命中率为

                  

定义：节点的能力 。P2P网络中节点的能力是与很多因素相关的，如CPU处理能力，节点的存储能力、带宽等等。将节点i的能力标记为 。

通过对Gnutella系统的观察发现，节点的负载主要由三部分组成：

1）节点的维护负载。每个节点需要周期性的通过ping/pong消息对连接进行维护，处理节点的加入离开，和缓存表的维护。

2）节点的查询负载。每个节点都能够接收查询消息并处理它们。

3）节点的响应负载。一旦节点命中查询，节点会发送响应消息沿原路返回。

这三部分负载产生的消息长度是不一样，其中，维护消息的长度最大，响应消息的长度其次，最短的是查询消息。

定义：节点的负载 。节点的负载是维护负载、查询负载和响应负载三部分的加权和，其权值分别设为 ，并且 。假定单位时间T内节点维护负载的数目为 ，查询负载的数目为 ，响应负载的数目为 ，则节点的总负载 为     。

3.2 负载均衡搜索算法

在P2P网络中设计负载均衡路由协议的目的是在路由过程中避开负载较重的节点，使得查询消息的路由尽量从负载较轻的区域穿过，从而能对网络的业务量进行调度，充分利用网络容量，减轻网络局部拥塞，提高网络处理性能。在路由设计过程中应该重点关注两个关键技术：一是网络节点的负载探测技术；二是路由技术。前者告诉我们网络中节点的负载情况是什么样，后者关注的是在网络负载情况已知的情况下如何实现负载均匀的查询消息路由。

3.2.1负载探测技术

节点的负载状况和节点的度以及邻居节点的活跃度、负载状况有关。

节点的活跃度：如果网络中该节点正在通信，则节点是活跃的，其活跃度为1，否则为0。活跃节点可以是源节点，目的节点或者中间转发节点。

 

假定节点u的度为d，则节点u在时刻K其邻居节点负载估值为 

节点的总负载开销 ， 其中 是平滑因子，且 。

定义：节点的剩余负载 。

3.2.2 缓存机制

每个节点保存两个表，一个是缓存表，一个是邻居节点列表。

节点的缓存表内容如下：

节点ID 共享文件

N1 F1

…… …….

nk Fk

 

为了节省网络开销防止缓存表无限增长，我们为每个节点设定固定大小的缓存空间。假设其存储节点的条目上限为R。当插入到节点的条目超过此上限时，我们可以使用LRU算法删除条目。

节点的邻居列表内容如下

节点ID 命中率 剩余负载

N1 P1 R1

N2 P2 R2

……. …….

 

3.2.2改进的转发机制

本文所采用的转发机制是采用随机漫步式的转发，但不同的是节点在每跳转发时随机漫步的个数K是动态变化的，K的取值与邻居节点的命中率和负载状况相关，分为如下几种情况：

①所有邻居节点的剩余负载 > , 是门限值

在这种情况下，所以的节点都有能力接收新的查询。则K的值等于邻居节点命中率中大于阈值 的个数。

②部分节点的剩余负载大于 

邻居节点已经有一部分达到饱和状态，已经来不及处理新的消息，这时查询消息就不再发往这些饱和的节点，则K的值等于邻居节点中未达到饱和并且其命中率大于阈值 的个数。

③节点的剩余负载均小于 

由于所有的节点都达到饱和状态，则K=1，随机选择下一跳节点进行转发。

负载均衡的查询算法如下：

当节点p接收到一个查询时，它将做以下基本操作：

①将自己添加到 中

②在本地搜索文件f

③转发查询到它的一个邻居节点集K。

节点先在本地搜索目标文件。节点在自己的共享文件和缓存表里查看有没有文件f，如果有，则搜索成功。否则在邻居列表中选择节点集K进行转发。

 

参考文献：

[1]Song, J., et al., LightFlood: Minimizing Redundant Messages and Maximizing Scope of Peer-to-Peer Search. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(5): p. 601-614.

[2]Tsungnan, L., et al., Dynamic Search Algorithm in Unstructured Peer-to-Peer Networks. Parallel and Distributed Systems, IEEE Transactions on, 2009. 20(5): p. 654-666.

[3]Rongmei, Z. and Y.C. Hu, Assisted Peer-to-Peer Search with Partial Indexing. Parallel and Distributed Systems, IEEE Transactions on, 2007. 18(8): p. 1146-1158.

[4]Yann, B. and K. Anne-Marie. PROXSEM: Interest-Based Proximity Measure to Improve Search Efficiency in P2P Systems. in Universal Multiservice Networks, 2007. ECUMN '07. Fourth European Conference on. 2007.

[5]Gang, C., L. Chor Ping, and Y. Zhonghua, Enhancing Search Performance in Unstructured P2P Networks Based on Users' Common Interest. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(6): p. 821-836.