结构化P2P网络访问热点预测与负载均衡机制研究

杜 超，徐 蕾

(沈阳航空航天大学 计算机学院，沈阳 110136)

基于DHT(Distributed Hash Table)的结构化P2P网络具有自组织、扩展性好等优势，进而得到了广泛的应用。但在此环境下，由于节点的处理能力及用户资源使用的不均衡，使P2P环境中的负载均衡成为一个突出、急需解决的问题。

P2P环境中节点的工作负载是动态变化的，负载均衡需要解决P2P环境中节点负载信息的采集，及节点出现过载时系统如何分担过载节点的工作进而实现P2P环境的负载均衡。现有的负载均衡策略，大都依赖P2P网络中某些固定位置的节点收集负载信息并进行热点转移，这种策略对负责收集负载信息的节点依赖性强，容易出现“单点失效”问题；而过载节点的热点转移通常采用复制副本的方法，复制的副本数与副本的存放位置是这种策略需要解决的问题。

文献[1-2]提出利用多个哈希函数重定位指定系统中的副本资源数和存放位置，这种方法可以实现部分热点资源的分布，但是承载热点资源的节点负载仍然远大于一般节点；文献[3-5]提出利用虚拟服务器局部信息调整负载的方法，但该方法是在结点超载时再执行负载均衡算法，此时，负载均衡算法的开销有可能加剧超载结点的过载程度，使算法响应速度变慢，是一种被动的负载均衡方法。文献[6]提出在邻居节点间进行副本缓存，部分资源的查询请求将转由存有副本的邻居节点来处理，进而在一定程度上平衡负载；文献[7]提出了P2P网络性能及流量监测模型,提出了适应高速 P2P 网络环境、扩展性较好的P2P 网络监测模型；文献[8]提出一种自适应的负载均衡算法，能够部分调整系统中节点的负载差异。

为避免结构化P2P网络中承载热点资源的节点过载时再进行系统的负载平衡，本文将查询请求分析机制与缓存策略相结合，提出了一种负载均衡方案。方案利用资源的历史访问信息对资源未来的访问量进行预测，若可能成为热点资源则提前进行资源复制，并在资源的查询路径中存储资源副本，进而降低承载热点资源节点的访问负载。实验结果表明，当系统中文件查询请求极不平衡的情况下，预测模型可以有效识别网络中的文件访问热点，结合网络中的文件缓存策略，提高了P2P系统中文件访问的成功率，降低了文件访问响应时间。

1 基于查询请求分析的热点预测模型

已有研究[10]表明，用户资源查询在结构化P2P网络中具有重复性，节点中文件的近期访问量对未来的访问趋势具有较高的参考价值。因此根据节点中文件的近期访问量，选择一个合适的预测模型对访问热点进行预测，可以更好地预防超载情况的发生。本文对比了三种预测模型对结构化P2P网络访问热点的预测效果。

1.1 基于ARMA模型的预测

ARMA (p,q)模型是自回归模型(AR模型)和滑动平均模型(MA模型)的一般形式，ARMA(p,q)模型可表示为：

其中{yt}是平稳的时间序列，φ1,…,φp是自回归系数，θ1,…,θq是滑动平均系数，εt,εt-1,…,ε1是误差项；根据时间序列理论，通常可以选择模型ARMA(2n,2n-1)(n是正整数)，为了减少计算量，本文采用模型ARMA(2,1)，模型可表示为yt=φ1yt-1+φ2yt-2+εt-θ1εt-1。

图1 网络节点中文件访问请求次数时间序列及平稳化结果对比

ARMA是有限参数线性模型，采用矩估计方法估计ARMA(2,1)模型的参数。设利用有限时间序列{xi}(i=1,2，…,n)的样本数据对ARMA(2,1)模型进行数据拟合，样本的自协方差函数为

样本的自相关系数定义为得

Xt=1.274 2Xt-1-0.436 1Xt-2+εt-0.248 7εt-1

令ε0=0，利用递推的方法逐步向前得出下一项误差项。

1.2 基于BP网络和一次指数平滑的预测

1)利用BP 网络预测

采用三层结构的BP(Back Propagation)神经网络对结构化P2P网络访问热点进行预测。设BP网络的输入层节点数是n，输出层节点数是1(记为节点z)，隐层是一层结构且节点数是m；BP的输入层节点表示P2P网络节点中某个文件n个T时间间隔的访问请求量，输出层节点表示该文件下个时间单位访问请求量的预测值。以P2P网络节点中文件访问请求量的时间序列{xi}作为BP网络的学习数据。

BP神经网络学习算法分为向前计算和向后的参数调整两部分：

向后的参数调整主要是根据输出层节点输出值与输出期望值之间的误差调整网络中边的权值系数。设t表示输出层节点z的输出期望值，BP网络的边权值wij(前一层的第i个节点连接到下一层的第j个节点的边上的权值)的调整公式为：wij(n+1)=wij(n)+η(n)oiδj

其中(n+1)和(n)表示迭代次数，oi是上层第i节点的输出(若第i层是输入层，则输出值即为输入值)，η是学习因子，计算方法为η(n)=η(n-1)+α(e(n)-e(n-1))/e(n)，其中e(n)=t-oz(n)是第n次迭代时期望输出t与实际输出oz(n)的误差，用系数α调整误差变化在η(n)调整中的影响；若j是输出层节点z，δz=oz(1-oz)(t-oz)，若j是隐层节点δj=oj(1-oj)δzwjz。

利用文件访问请求的时间序列作为BP网络的学习数据，并对BP网络输入层及隐层的不同节点数进行误差分析，本文选定误差较小的5-15-1作为文件访问量预测的三层BP网络结构。

2)利用一次指数平滑模型预测以P2P网络节点中文件在T时间间隔内的访问请求量为基本单位，利用一次指数平滑预测模型对节点中第(t+1)时间单位内的文件访问量yt+1进行预测，可表示为：

2 热点文件副本复制算法

根据第2节预测出P2P网络节点中文件的访问量，若访问量的预测值达到或者超过警戒值，就认为该文件是热点访问文件。对预测到的热点文件按照一定的策略创建和复制副本文件。

文件的访问量预测是根据文件的已知访问量完成的，节点中需要保存每个文件的访问信息，在节点中保存一组文件的访问数据，如表1所示。

表1给出的文件访问数据主要是为文件的访问量预测服务的；其中文件F的反向节点定义为：设P2P网络中文件F的存放节点是a，某个节点b在请求查找文件F时，按照结构化P2P查找规则找到节点a的查找路径中最后经过节点是c，则c是a的反向节点；文件的反向节点数据包括反向节点的IP地址和查找文件经过的次数n。热点文件的副本主要存放在该文件的反向节点中。在节点中可以设置专门的副本存放位置(称为副本复制区)，可便于副本的撤销。

表1 P2P网络节点保存的文件访问节点数据

为保持在节点加入或离开动态变化后结构化P2P网络结构的稳定性，网络中节点要定期执行结构的稳定性算法，这样，热点文件的预测和副本复制也可以是节点周期性执行的算法。描述如下：

1)node.Cache() {//节点Node中运行的文件副本复制算法；

2)初始化线性表L；

3)for( node中每个存储的文件Fi)

4)if(Fi.numi> File_access_max) add(L,Fi);//文件Fi访问次数大于文件访问阈值，

文件Fi的标识加入线性表L

5)for(线性表中每个存储的文件Fi) {

6)Fi_pred=access_pred(Fi，Method)；//利用Method模型对文件Fi下一时间

区间的访问量进行预测；

7)if(Fi_pred>hot_limit) { //预测的文件访问量超过热点阈值

8)copy_num=(N*Numi/Total)>M? M:(N*Numi/Total);//按文件Fi访问量与

//与节点文件的总访问量比计算副本的数量，副本数不能超过反向节点数。

9)for(j=1;j<=copy_num;j++) copy( Fi,(IPj,nj))；//向反向节点j副本复制区复制Fi

10)}

11)}

12)}

算法中的文件访问量预测模型Method可以是前面介绍的三种模型之一。

具有副本复制策略的结构化P2P网络中，当节点请求查找文件F时，在查找路径节点的副本复制区首先查找F，若存在，查找终止；否则沿路径查找直到找到存放文件F的节点v，此时需更新节点v上F文件访问计数、节点Total计数及文件F的反向节点数据。

热点文件具有阶段性特征，一段时间后可能变成非热点文件。P2P网络中节点可以在一定时间间隔内定期执行热点文件副本删除算法，算法主要检查节点中的副本复制区，采用“最近最少使用算法(LRU)”删除很少使用的副本。

3 实验结果与分析

设计仿真实验评估不同预测模型的预测效果，并验证副本复制算法在解决P2P网络的热点问题的有效性。实验基于典型的结构化P2P网络结构chord，按照chord结构的构成方法均匀的分布网络中的资源，chord结构中节点id位长是16，网络中的可区别的资源数(不含副本)为节点数的5倍以上，热点资源占总资源数的1/10。在仿真实验中，随机产生的网络中节点文件查询事件服从N(0,10，2)的高斯分布；实验主要是针对热点预测与副本复制，因此选用的是稳定的网络结构。

ARMA和BP模型需要利用实验数据进行训练，设BP模型的初始参数η=0.2，α=0.5，一次指数平滑模型的参数a=0.7。利用仿真实验中前2000次访问对ARMA与BP模型进行训练，不断进行拟合，ARMA模型从第1200次左右误差趋于平稳。BP模型从第1800次开始训练误差保持了平稳。

为测试系统处理资源访问请求不均匀情况的能力，实验中设置节点资源访问事件中，80%的资源访问请求是针对热点资源的；设置的文件访问阈值和热点阈值为File_access_max=10，hot_limit=15。

在热点预测时间方面，ARMA模型预测100个实验数据需要1.749秒，而BP模型预测100个实验数据需要0.085秒，一次指数平滑模型预测100个实验数据只需要0.049秒。各模型性能对比如表2所示。三种预测模型下平均响应时间对比如图2所示，频繁访问热点资源时的访问成功率对比如图3所示。

三种预测模型在减少文件访问的响应时间和提高访问成功率方面效果显著。ARMA模型的预测时间要长于其他两种模型，但其预测效果好，文件访问的平均响应时间小，访问成功率相对较高；由图3中可以看出，在系统仿真的开始阶段，随着热点资源访问量的增加，访问成功率会有一个下降的过程，而后随着系统对热点的识别和预测，访问成功率不断升高并趋于稳定，而ARMA与BP模型由于在训练阶段就与仿真数据基本达到拟合，访问成功率比较稳定。

表2 不同预测模型性能比较

图2 不同规模下频繁访问热点资源的平均响应时间

图3 频繁访问热点资源时访问成功率对比

4 结束语

本文提出结构化P2P网络中访问热点的预测及实现负载均衡的副本复制方法。实验对比了三种访问热点预测模型在结构化网络chord中的仿真效果，三种模型能有效提高文件访问的成功率，缩短文件的响应时间；且ARMA模型比其余两种模型具有更好的性能。

文件的副本复制策略虽然在一定程度上增加了系统存储量和更新开销，但复制的文件副本从某种意义上降低了热点文件的热度及文件所在节点的负载。副本文件的存储量是动态变化的，当热点文件不在是访问热点时，过期的副本会从系统中被删除。

参考文献(References)：

[1] Xia Ye,Chen Shigang,Korgaonkar V.Load balancing with multiple hash functions in peer-to-peer networks[C].Proc.of the 12th International Conf.on Paralleland Distributed Systems.Washington D.C.,USA:IEEE Press,2006.

[2] Byers J，Considine J，Mitzenmacher M.Simple load balancing for distributed hash tables[C].In：Kaashock MF，Stoica I，ads.LNCS.Berlin：Springer-Verlag，2003:80-87.

[3] Zhu Y.Load Balancing in Structured P2P Networks[M].Handbook of Peer-to-Peer Networking.Springer US,2010:1149-1164.

[4] XiaoHai W,YuXing P,DongSheng L.An efficient load balancing method for constant degree P2P systems[C].Computer Design and Applications (ICCDA),2010 International Conference on.IEEE,2010,5:V5-316-V5-319.

[5] Takeda A,Oide T,Takahashi A.New structured p2p network with dynamic load balancing scheme[C].Advanced Information Networking and Applications (WAINA),2011 IEEE Workshops of International Conference on.IEEE,2011:108-113.

[6] 刘柯萍,危韧勇,谷 科.一种解决P2P网络路由热点问题的策略[J].计算机工程与应用,2007,43(6):108-111.

[7] 李江涛，雷振明.P2P网络性能测度及监测系统模型[J].北京邮电大学学报,2006,29(3):17-21.

[8] 熊伟,谢冬青,焦炳旺,等.一种结构化 P2P 协议中的自适应负载均衡方法[J].软件学报,2009,20(3):660-670.

[9] 陈蓉.话务量分析和多种预测模型的比较研究 [D].北京:北京邮电大学,2008.

[10] Stutzbach D,Rejaie R,Sen S.Characterizing unstructured overlay topologies in modern P2P file-sharing systems [J].Networking,IEEE/ACM Transactions on,2008,16(2):267-280.

[11] Box GEP,Jenkins GM,Reinsel GC.Time series analysis:forecasting and control [M].Wiley.com,2013.

[12] Ghosh B,Basu B,O'Mahony M.Multivariate short-term traffic flow forecasting using time-series analysis[J].Intelligent Transportation Systems,IEEE Transactions on,2009,10(2):246-254.