p2p网络中基于动态our算法的负载均衡技术

p2p网络中基于动态our算法的负载均衡技术

1结构与非结构化p2p系统p2p系统越来越多地用于数据处理、资源交换、信息管理、共享等领域。然而，随着问题的普及，这种负荷补偿也出现了。节点之间如何均匀组织负载？系统性能的质量取决于问题的答案。由于不平衡，p2p系统带来了许多性能问题，如此期间的延误。因此，负荷补偿已成为p2p系统研究的一个重要问题。一些p2p系统，如烧香、幻灯片和胡同，通过提供一组有序的噪声补偿机制来平衡噪声，并且在理想的环境中提供了相同的性能。所有文件都具有相同的访问频率，因此生成的节点是统一的。然而，现实系统是不同的。事实上，由于节点性能的不同结构和热点文件的存在，负荷仍然存在。对于一些非结构的p2p系统，如gilla，节点没有显示身份的唯一标识，并且没有与其他节点相关的信息。它只能通过网络上的洪水信息来定位资源，这大大增加了网络负荷。为了解决这些问题，许多文献在非结构pm系统的基础上引入了超级节点。超级节点是能力强的节点，每个超节点管理着一些普通节点。这些普通节点和管理的普通节点构成一个群体（或组）。每个普通节点都是唯一的身份标识符，并且每个普通节点都管理着一些普通节点。超级节点和他们管理的普通节点构成一个群体（或组）。每个普通节点都有一个唯一的身份标识符，并且希望向组织中的超节点提供信息。通过定期沟通，超节点之间交换彼此的信息。本文提出了两种通过副本策略处理负载平衡的技术:周期性的副本策略(PeriodicReplicationPolicy,简称PRP)和基于需求的副本策略(Demand-basedReplicationPolicy,简称DRP).在PRP中,超节点周期性地传递那些全局被访问频率高的文件副本到远程的超节点,从而降低了搜索文件的跳数.当一个超节点收到一个文件副本时,它会在一定范围内通知它的邻居超节点.与PRP不同,DRP是基于当地的访问频率的,而不是像PRP那样从全局来考虑的.如果一个超节点所在组对某个文件的访问频率超过了一定的值,那么这个超节点将会保留这个文件副本在本组内.2理想的副本策略近来已经有很多文献提出了P2P环境下的副本策略,如文献.它们主要讨论的副本策略如下:·统一分配策略:在P2P网络中,所有的文件的副本数目都是相同的.·正比策略:每个文件的副本数目与它被查询的概率成正比关系.·平方根策略:每个文件的副本数目与它被查询的概率的平方根成正比关系.统一分配策略没有考虑文件流行程度,对于热门文件来说,系统中存储的副本数可能并不能满足查询的需求,容易造成瓶颈问题.而对于访问量比较少的文件来说,它们副本的利用率很低,浪费了存储空间.正比策略和平方根策略考虑了文件流行度的差别,使得副本的利用率得到了提高,但是为了存储流行度的相关信息,每个节点的负担大大加重了.在P2P网络中,负载平衡是衡量其性能的一个重要因素,越来越多的文献,如针对这个方面进行了研究.提出了一种通过副本策略来达到负载平衡的策略.它通过文件的流行程度来确定副本数目,并且通过定义多个哈希函数来使得每个副本被访问的频率尽量接近,从而达到负载平衡.但是因为它引入了多个哈希函数,在选择副本的时候就要付出更多的代价.3副策略本节主要来讨论副本策略的两种算法的实现策略—周期性的副本策略和基于需求的副本策略.3.1周期流特征在文件副本策略下的展现在周期性的副本策略里,每个超节点都保存着该组里所有文件被访问频率的信息.如果一个文件被访问的频率超过了某一个预先定义的值,那么该文件的一个副本就会被拷贝到一个访问此文件频率最高的超节点所在的组内.当这个超节点接收到文件副本后,它将根据当前组内节点的空间剩余情况,选择一个剩余存储空间最大的普通节点来存储该文件副本,然后通知它的邻居节点这个文件副本所在地的信息.为了减轻网络的负担,它只通知一定范围内的邻居超节点.在这种副本策略里,超节点之间需要周期性地更新彼此的信息,如图1所示.图1显示了周期性副本策略的操作过程.超节点SP1,SP5等请求某个文件i,假定该文件在超节点SP6所在组内命中,SP6将检查该文件i的访问频率是否超过了预先定义的阈值,如果检测到文件i的访问频率高于这个阈值,那么SP6将拷贝一个副本发送给访问文件i频率最高的超节点(这里我们假定SP1访问文件i的频率最高).SP1收到这个文件副本后,将把该文件副本保存在本组内剩余空间最多的普通节点Pi上,并在一定范围内通知其邻居超节点.3.2基于需求副本策略在基于需求的副本策略里,每个超节点都记录着本组内所有普通节点对每个文件的访问频率信息.当一个普通节点发送对某个文件F的请求到它所在组内的超节点SPi时,SPi首先检查一下本组内对该文件的请求频率是否已经超过了一个预先定义的值,如果超过了,SPi将发送一个副本请求到该文件所在组内的超节点SPj.SPj接收到请求后就会把文件副本发给SPi,SPi收到文件副本后,将把该副本保存在本组内剩余空间最多的普通节点上,并通知自己的邻居节点.当然,为了节省网络代价,它也只通知一定范围内的邻居超节点,如图2所示.图2显示了基于需求的副本策略的操作过程.超节点SP1检查到本组内频繁的发送对文件i的请求,并且其频率已经超过事先定义的阈值,假定该文件在SP6所在组内命中,那么SP1将给SP6发送对文件i副本的请求.SP6收到请求后就会把文件i的副本发给SP1.SP1收到文件副本后,将把该文件副本保存在本组内剩余空间最多的普通节点Pi上,并在一定范围内通知其邻居超节点.4获取文件的概率在这节,我们将分析上面提出的两种副本策略的平均访问代价和副本负载大小.首先我们来看一下它们的平均访问代价.在这里我们把命中分为两种,一种是本地命中(节点请求的文件在它所在组内命中),另一种是远程命中(节点请求的文件在其他组内命中).每个请求的平均代价计算如下:AvgCost=P(local)*LocalCost+P(remote)*RemoteCost(1)其中P(local)表示请求被本地命中的概率,P(remote)表示请求被远程命中的概率,LocalCost是从组内取得文件所需的代价,RemoteCost是从其它组内取得文件所需的代价.P(local)和P(remote)之和为1,并且它们的值能通过查询请求的分布被计算出来.一般文件共享系统中,文件的请求服从Zipf分布,那么文件i被访问的概率如下式:P(i)=1∑x=1D1x*1i(DΡ(i)=1∑x=1D1x*1i(D为系统中不相同文件的数目)(2)P(local)=∑i=1mP(i)(mΡ(local)=∑i=1mΡ(i)(m为本地不同文件的数目)(3)P(remote)+P(local)=1(4)4.1节点平均网络地理位置在PRP方法中,超节点根据组内文件的全局访问频率来决定是否发送文件副本到其他发送请求的超节点.我们用λ来表示一个预先定义好的阈值,当文件的访问次数超过这个值的时候,一个文件副本将会发送给某个访问此文件频率最高的超节点.一个文件i被访问的频率在公式(2)中已经定义了.我们定义每个普通节点发出查询请求的频率为Q,超节点的数目为N,每个超节点平均和k个普通节点连接,在一个周期t内,请求文件i被请求的次数可以计算为:NumberAccess(i)=t*N*k*Q*P(i)(5)P(NumberAccess(i)>λ)表示文件i被访问的次数高于预先定义的值λ的概率,那么在一段时间T内产生的平均副本数量为:NumberReplica−PRP=Tt*∑i=1D(P(NumberAccess(i)＞λ))(6)ΝumberReplica-ΡRΡ=Τt*∑i=1D(Ρ(ΝumberAccess(i)＞λ))(6)副本的负载代价为:Overhead-PRP=NumberReplica-PRP*AverageHops*TransferCost(7)AverageHops表示副本在超节点间传输过程中平均经过的跳数,TransferCost表示每跳的传输所需要的代价.4.2生成的副本数量及负载代价在DRP方法中,超节点Si根据组内对文件i请求的情况来决定是否需要请求拷贝副本到本组内.如果组内对文件i的请求超过了预先定义的阈值θ,那么Si就会发送副本请求到拥有该文件i的超节点Sj.在一段时间T内,每组对文件i发出请求的次数可以计算为:NumberAccess(i)=T*k*Q*P(i)(8)P(NumberAccess(i)>θ)表示文件i被访问的次数高于预先定义的值θ的概率,那么在时间T内产生的副本数量为:NumberReplica−PRP=N*∑i=1D(P(NumberAccess(i)＞θ))(9)ΝumberReplica-ΡRΡ=Ν*∑i=1D(Ρ(ΝumberAccess(i)＞θ))(9)副本的负载代价为:Overhead-DRP=NumberReplica-DRP*AverageHops*TransferCost(10)5性能评价这节将通过模拟实验来验证我们提出的副本策略的有效性,实验参数如表1所示.5.1spsize对平均跳数的影响由第4节的分析,可以得知在网络结构一定的情况下,影响PRP性能的重要参数是周期t,阈值λ,超节点缓存大小SPSize,而评价PRP性能好坏的标准就是副本负载及获得查询结果需要的平均跳数AverageHops.因此在本小节我们将通过实验分析这些参数之间的关系.表2显示了PRP方法中,在其它值固定(取表1中的值)的情况下,平均跳数AverageHops随阈值λ变化而变化的情况.从表中我们可以得知,随着λ值的增大,AverageHops并没有太明显的变化.这是因为节点发出的请求服从Zipf分布,一般请求偏向于比较热门的文件,而这些文件的访问量很快可以达到预定的λ值,所以随着λ值的增加,AverageHops的值并没有明显的变化,而只是略微有点升高的趋势.表3显示了PRP方法中,在其它值固定(取表1中的值)的情况下,平均跳数AverageHops随周期t变化而变化的情况.随着t从1增加到4分钟时,平均跳数有明显的减少,而当它从4增加到6时,平均跳数又开始了慢幅度的增加,这是因为如果t过小,则在一个周期内的请求数也相对比较少,很多相对热门的文件的访问量也没有达到预先定义的阈值λ,因此产生的副本数就很少,平均跳数也就比较高了.我们可以看到,当t=1时,平均跳数接近8,这和没有采用副本策略的情况下的跳数几乎差不多.而当t过大时,一个周期内产生的副本并不会有明显的增加,反而在一定的时间T内产生的副本数会略微下降.表4显示了PRP方法中,在其它值固定(取表1中的值)的情况下,平均跳数AverageHops随SPSize变化而变化的情况.随着SPSize的增加,其存储能力越强,能够存储的副本数越多,当然平均跳数也就会下降了.当超节点的缓存大小从1MB升到2MB时,平均跳数有着明显的降低,继续上升到3MB时,上升的趋势有所减退,继续增加SPSize时,平均跳数几乎保持不变了.5.2drp过程中平均跳数随超节点缓冲溶液的变化表5显示了DRP方法中,平均跳数AverageHops随阈值θ变化而变化的情况.显然,随着θ的增加,AverageHops的值会越来越大,当θ达到30以上时,AverageHops的值几乎不再发生变化,并且接近没有采用副本策略情况下的平均跳数值.当然,如果θ的值越小,AverageHops的值就会越小,但是整个系统中的副本负载就会加重.表6显示了DRP方法中,平均跳数随着超节点缓存大小SPSize变化而变化的情况.从图中,我们可以看到,随着缓存的增加,平均跳数并没有明显的下降趋势.这