结构化p2p中节点的负载不均衡

结构化p2p中节点的负载不均衡

0基于网络定位的负载均衡算法p2p是一个分布系统，参与者共享他们拥有的资源。这些共享资源可以直接访问其他节点，而不需要经过中间节点。网络中的参与者既是资源(服务和内容)提供者,又是资源(服务和内容)获取者。P2P技术使得网络上的沟通变得更容易、更直接。P2P改变了目前Internet以太网站为中心的状态,重返非中心化,并把权利交还给用户。P2P系统一般分为非结构化和结构化两种。近年来,基于DHT的结构化P2P系统以其严格的节点组织规则,良好的容错能力、可扩展性和查找速度等,得到了广泛的应用(如Chord、Pastry、Tapestry和CAN)。结构化P2P系统利用相容hash函数把资源关键字随机分配在各对等节点中,从而各节点以很高的概率分配到相同数目的关键字。文献表明这种情况下,一个节点所负责的关键字数可能是其他节点的O(logN)倍(N是系统的总节点数)。另外,它们假设系统各节点的能力是一样的。但文献表明P2P系统中各节点的能力(CPU处理能力、存储能力、网络连接能力等)有很大的差异。所以必须进行负载均衡,使能力强的节点处理更多的任务。本文针对以上问题,以Chord算法为基础,提出了基于网络定位的负载均衡算法。算法利用网络定位技术产生系统中各节点的距离信息,使负载在物理位置相近的节点间进行转移,从而最小化带宽和延迟的消耗,达到快速有效转移负载的目的。该算法由负载较轻的节点负责主要的负载转移操作,节省了过载节点的资源,提高了负载转移质量。1节点负载均衡现有的负载均衡算法,有的忽略了系统中节点负载能力的差异;有的在负载转移时,没有考虑节点间的位置关系;有的增加了系统的复杂性,减小了容错能力。文献没有考虑节点能力的差异,给每个DHT节点都分配O(logN)个虚拟服务器试图解决负载均衡问题。但根据经典球盒问题(ballsandbinsproblem),这种方案下一些节点的负载可能是其他节点的O(logN/loglogN)倍,所以单纯依靠虚拟服务器并不能完全解决这个问题。CFS根据节点本身的能力来分配虚拟服务器,考虑到了节点能力的差异。当一个节点过载时简单地删除它的部分虚拟服务器。此算法在删除过载节点的服务器时可能引起其他节点过载,过载节点需再次删除虚拟服务器,从而使系统不稳定,收敛时间过长。文献提出了三种简单的负载均衡算法:一对一、一对多、多对多。算法的基本思想是过载节点转移虚拟服务器给非过载节点。在一对一方法中,非过载节点随机选择一个节点进行探测,当发现被探测节点是过载节点时转移虚拟服务器到本节点。在一对多和多对多方法中,系统有d个目录服务节点用来保存节点的负载信息,由目录服务节点生成负载转移策略。文献扩展了一对多和多对多模式,使算法适应了动态P2P系统。然而,此算法在过载与非过载节点间转移虚拟服务器时,并没有考虑它们之间的位置相近关系,负载转移需要消耗过多的带宽和延迟。文献在结构化P2P系统之上再建立一个结构(k-nary树),由k-nary树收集系统负载信息并生成虚拟服务器转移策略。此算法考虑了节点之间的距离相近性,但是复杂化了P2P系统的覆盖网络,使系统容错能力有所下降;同时,系统某些节点(如k-nary树的根节点)的失效将产生单点失败问题。文献中每个资源关键字hash到d(d≥2)个不同的IDs上,然后在其中选择负载最轻的节点存放资源的索引,而其他d-1个节点只存放指向这个索引的索引。仿真实验表明,算法在d=O(logN)时,能达到最优的负载均衡效果,但没有考虑系统在动态环境下对算法的影响。2系统负载的确定本算法主要针对基于DHT的大规模P2P计算网络,网络中的每一项资源都给系统造成相应的负载(存储空间、CPU计算时间和带宽等)。作如下合理的假设:a)系统中只有一种瓶颈资源;b)在负载均衡算法运行期间各虚拟服务器的负载不变。2.1相关概念1物理dct节点本算法利用了虚拟服务器。虚拟服务器的概念在Chord/CFS中作为一种负载均衡的方法被提出。一个虚拟服务器相当于一个DHT节点,并负责一块连续的ID空间。而一个物理DHT节点可以拥有m个虚拟服务器,所以一个物理节点对应的ID空间可能是非连续的。DHT节点之间以虚拟服务器为单位进行负载转移。当某个物理节点过载时,该物理节点对应的一个或多个虚拟服务器将被转移到非过载节点上。同时,虚拟服务器的转移可以由DHT的离开和加入操作来实现,无须引入新的操作。利用虚拟服务器可以很方便地在任意两个节点之间进行负载转移。2基于网络定位的dct如今,网络定位算法已经广泛应用于产生因特网节点间的物理位置信息。网络定位算法分为两种,即基于基础设施的(infrastructured-based)和不基于基础设施的(infrastructured-less)。前者(如GNP)使用路标节点作为参考节点;后者(如Vivaldi)中的任何节点都是其他节点的参考节点。本文使用第一种网络定位算法的思想:物理位置相近的节点到指定的一组参考节点(路标)有相近的距离信息,并作了适当的改动,以使它更好地应用于本算法。在一个基于DHT的结构化网络中,路标节点可以从本结构化网络中选择,也可以在因特网中任意选择。假设有m个路标节点,一个DHT节点A到它们的距离可表示成A的网络坐标〈d1,d2,…,dm〉。如果把节点A的网络坐标映射到m维笛卡儿空间上,这个笛卡儿空间就叫路标空间。根据网络定位技术,两个物理位置相近的DHT节点A和B有相近的网络坐标,并且在路标空间上的位置也是相近的。路标节点越多,相近性误差就越小。实验表明利用15个路标节点足够产生相近性误差极小的坐标信息。本算法实验将使用15个路标节点,然后利用网络定位技术,把十五维坐标空间映射到一维坐标空间并保存坐标的相近性,从而使每一个DHT节点A的网络坐标都对应一个坐标数。网络坐标相近的节点,它们对应的坐标数大小也是相近的。3cc与密度分布系数节点的聚集系数可以反映网络的局部密度。聚集系数越大,局部密度越高。聚集系数定义为CC=(|E(Γv)|)/(C2kk2v)。其中:Γv={i:d(i,v)=1};v为取得的中心点。本算法根据聚集系数的大小来调整星型结构区域。4局部利用率节点A的利用率指A的负载与A的能力比值,即utlA=loadA/capacityA。节点A计算的系统局部利用率指与A物理位置相近的节点(包括A)的负载和与能力和之比,即utl_LA=(∑pi=1loadi)/(∑pi−1capacityi)_LA=(∑pi=1loadi)/(∑pi-1capacityi)。其中:p为满足条件|Hi-HA|<δ(Hi、HA分别为其他节点和A节点的坐标数,δ为常量)的节点个数。5节点个数的表示与系统利用率的偏差dev指系统中的节点利用率与系统利用率utl之差的平方和,即dev=∑Ni=1(utli−utldev=∑Νi=1(utli-utl)2。其中:N表示系统中节点的个数。负载均衡算法的目标就是使偏差dev尽量小。6耗的带宽分析负载转移开销包括转移一定负载所消耗的带宽和链路延迟时间。负载转移消耗的带宽可以通过负载转移经过的跳数来计算。负载转移的延迟是转移负载的大小与转移时节点之间延迟的乘积和,即C=∑Si=1loadi×latC=∑Si=1loadi×lati。其中:S表示转移负载的个数。2.2算法流程2.2.1负载均衡算法仿真本算法利用改进的分布式网络定位技术产生的坐标数作为节点的IDs。文献研究表明,网络坐标相近的节点,物理位置也相近,并且路标节点越多,相近性误差就越小。由于从网络坐标映射到坐标数时,保存了节点间物理位置的相近性关系,坐标数(IDs)相近的节点,物理位置也相近。基于网络定位的负载均衡算法中,结构化P2P系统的每一个节点周期性地计算系统局部利用率utl_LA和负载转移阈值TA(TA=(utl_LA+ε)×CA。其中:utl_LA为系统局部利用率;CA为节点A的能力;ε为可调参数),ε用来在负载均衡质量和负载转移开销之间取得折中,ε为0时,负载均衡质量最好,但此时负载转移开销也最大。当节点A的负载LA小于TA时,节点A通知坐标数满足条件|Hi-HA|<δ(Hi、HA分别为其他节点和本节点的坐标数,δ为常量)的节点,并以A为中心构造一个星型结构,如图1所示。同时,节点A获得周围每一个过载节点需要转移的虚拟服务器的索引及其负载大小,并按负载从小到大的顺序排列成一个链表a;同样,节点A也会获得周围每一个负载较轻节点能够接受的负载数量(Ti-Li),包括节点A本身,并按负载数从小到大的顺序排成一个链表b。仿真实验表明,δ值为CC×log(N)时具有良好的负载均衡效果。这个过程的伪代码如下:2.2.2删除a、b链表,检查dct系统中负载较轻节点完成星型结构和链表a、b的组织之后,进行负载转移。步骤如下:a)链表a中的每一个虚拟服务器V与链表b里符合条件(Ti-Li)≥load(V)中(Ti-Li)值最小的节点匹配。b)利用DHT中的离开和加入操作把虚拟服务器从过载节点转移到负载较轻节点,并删除a、b链表中相应的节点。c)循环执行前面两个步骤,直到链表a为空或者星型结构中没有节点能够接收剩下的虚拟服务器(链表a不为空)。这时,节点A通知其他各节点解散星型结构。对于大规模网络,如果需要加快负载的扩散能力,当匹配完成后,链表a不为空,即还有虚拟服务器没有被转移。这时可以拓展星型结构,即通知δ≤|Hi-HA|<η的节点与原来不能进行负载转移的过载节点构成星型结构,并按上面的方法进行负载转移。转移完成后,解散星型结构。算法的伪代码如下:基于网络定位的负载均衡算法中,负载的转移可以利用DHT中的离开和加入操作来完成,无须引入新的操作。同时需要转移的虚拟服务器索引和负载过轻节点的剩余能力按从小到大的顺序分布在链表中排列,从而生成负载转移策略的速度非常快。另外,负载在物理位置相近的节点之间进行,大大地节约了系统带宽和延时等资源。系统中的节点周期性地执行负载均衡算法,所以本算法能够适应动态P2P系统。3负载均衡优化3.1仿真实验仿真实验在结构化P2P系统的Chord协议上实现。实验中,Chord具有32bit的ID空间,并且虚拟服务器对应的ID空间大小是呈指数分布的。实验用Pareto分布来产生各虚拟服务器的负载,由于Pareto分布的重尾(heavy-tailed)性,算法有效性的验证是在最不利于负载均衡的情况下进行的。其他具体参数的设置如表1所示。实验中,对MIT的kingdata数据库中的mking-t拓扑文件作了适当的扩展,并使用它作为网络拓扑结构。Mking-t拓扑结构是现有网络的一部分,在它上面运行基于网络定位的负载均衡算法能充分说明算法的有效性和实用性。3.2算法性能分析1)负载均衡效果图2是负载均衡效果图。负载均衡过程中的系统利用率为0.8。负载均衡之前,节点利用率与系统利用率的偏差(dev)为957.12;负载均衡之后,dev下降为12.58,比负载均衡之前下降了98.68%。从图2可以看出,基于网络定位的负载均衡算法可以得到理想的负载均衡效果。2)负载转移的开销图3是负载转移带宽消耗累积分布图。实验通过转移虚拟服务器经过的跳数来衡量负载转移需消耗的带宽。从图中可以看出,考虑节点间的物理位置相近关系时,在两跳之内可以转移68%的负载,十跳之内可以转移89%的负载。而不考虑节点间的物理位置相近关系时,十跳之内只转移了15%的负载。从以上的比较可以看出,基于网络定位的负载均衡算法能够有效地在物理位置相近的节点之间进行负载转移,从而减少转移负载所需要的跳数,达到节省带宽的目的。图4是负载转移延迟消耗累积分布图。从图中可以看到,当考虑节点间的物理位置相近关系时,62%的负载转移在链路延迟小于50的节点之间进行,98%的负载转移在链路延迟小于200的节点之间进行;当不考虑节点间的物理位置相近关系时,只有19%的负载转移在链路延迟小于200的节点之间进行。从以上可以看出,基于网络定位的负载均衡算法可以节省负载转移所耗费的时间,加快负载转移速度。3)系统利用率对负载均衡效果的影响负载转移因子(loadmovementfactor)定义为负载转移总的开销与系统中所有负载移动一次时的总开销之比(只考虑延迟开销)。例如,负载移动因子为0.1时,表示负载转移消耗的带宽是初始插入这些负载时的10%。99.9百分位节点利用率(99.9thpercentilenodeutilization)定义为一个利用率,它大于99.9%的节点利用率。节点i的利用率为其负载与能力之比:ui=Li/Ci。从图5可以看出,每一条线代表一个特定的系统利用率。每一个点表示负载均衡周期在60～1200s时取得的一个值。经过负载均衡后,即使系统高达0.912,仍然可保持99.9%的节点非过载,并且其中有一个负载转移因子小于0.08。4仿真实验2:转移在物理位置相近的节点之间进行本文针对结构化P2P系统中的负载均衡问题提出了一种基于网络定位的负载均衡算法。算法由负载较轻的节点负责主要的负载转移操作,节