一种基于节点信息的负载均衡算法

李成森，黄桂敏，周 娅，刘平山

(1.桂林电子科技大学 信息与通信学院,广西 桂林 541004;2.桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004)

一种基于节点信息的负载均衡算法

李成森1，黄桂敏1，周 娅2，刘平山2

(1.桂林电子科技大学 信息与通信学院,广西 桂林 541004;2.桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004)

在P2P流媒体点播系统中，节点可能收到过多的数据请求造成自身过载，导致网络节点负载的不均衡，影响了系统的整体性能。为了平衡节点间的负载，通过建立节点的信息列表管理节点的动态负载信息，设计了一种基于请求迁移的负载均衡(LBRM)算法。实验结果表明，LBRM算法解决了网络节点负载不均衡，提高了播放质量。

负载均衡；对等网络；请求迁移

对等网络(peer to peer，简称P2P)的诸多优势促进了P2P流媒体应用在视频点播和视频直播领域的发展[1]，但由于网络中节点行为的随意性，每个服务节点所接收到的数据请求量不同，某些节点可能承担过多的请求任务。节点在处理过多的请求时，用户请求被延迟甚至丢失，而其他一些节点却处于空闲状态，带宽没有得到有效利用。同时由于节点的带宽资源、存储容量以及网络环境的差异，各个节点所能承受的请求压力不同，个别节点因负载过重而失效。因此，必须保持节点间的负载平衡以避免个别节点处理的请求量过多而负载过重，并使其他节点的请求得到稳定快速的回应。

为了管理整个网络的节点负载信息，文献[2]采用超级节点管理部分节点的负载信息，然而，节点频繁地与超级节点进行信息交换可能引起单点瓶颈现象的发生。Yao等[3]提出一种基于局部网络信息的负载平衡算法提高系统负载平衡的速度，但该算法建立在假设每个节点的能力和存储容量是一致的基础上，不符合实际情况。文献[4]采用随机步长估算网络中全局负载信息，但在一个含有N个节点的系统中，为了更精确地估计负载分布的情况，该算法需要使用lg N次随机步长来辅助计算，增加了算法的复杂度和网络的开销。

为了有效地均衡网络中的负载，避免节点超载，Xiong等[5]提出了一种自适应的负载均衡策略，该策略基于热门文件创建备用节点用于接收超载节点转移的负载，但未考虑待转移请求的紧急性，可能引起转移请求过期丢失，影响系统的稳定性。Yang等[6]提出一种SQS策略使节点在数据调度时主动向空闲节点发送请求，以避免节点突然收到过多的数据请求，但在系统中周期性检测节点的请求数量并不准确[7]。Takayama等[8]提出了多属性范围查询方法，其采用随机抽样的方式创建近似直方图来管理节点,但引入了较大的计算开销。Gupta等[9]提出了一种基于博弈论的激励机制来改善节点间负载不均衡，但该算法需要获取网络全局信息，并且许多方面处于理论假设阶段。

为此，提出了一种基于节点信息的负载均衡算法。该算法通过构造节点的信息管理列表，避免使用服务器来管理和传播节点的负载信息，然后分析节点收到请求的差异性和网络节点的异构性，采用优先级排序，将优先级低的请求转移到轻载节点处理。通过节点选择机制，选择性能良好、稳定性高的节点作为接收被转移请求的对象。

1 节点负载均衡策略

1.1 节点负载信息管理

为了方便管理和传播节点的负载信息，构造一个节点信息管理列表，该表负责保存节点及其邻居节点的相关信息。节点可通过该列表与其邻居节点进行负载信息交换。由于节点的邻居节点个数取20个左右能使网络中资源共享的效率更高，并且能使系统达到理想的状态[10]。因此，将20个具有邻居关系的节点作为一个节点簇，然后生成基于每个节点簇的节点信息表，它们被用来当作节点负载的定义和负载等级的划分以及负载转移的依据。节点动态负载信息管理列表如表1所示。表1中记录了节点负载的相关数据，它包含节点接收的各种数据包的信息，可用于节点负载度的计算。此外，该表还记录了邻居节点的能力值与负载状态，利用这些信息可筛选出能力值大的轻载节点接收负载。其中，ID为节点的标识符，其值由服务器唯一给定，用于区分不同的邻居节点。

表1 节点动态负载信息管理列表

1.2 节点负载

节点负载度是节点每秒上传的数据总量占节点的带宽资源总量的比例，负载越大，则节点所承受的请求压力越大。

(1)

其中：Li为节点i的带宽负载；Ui为节点i在t时刻上传的数据总量，包含表1中各类数据包消息量总和；T为时间周期；t为任一时刻；B为节点的上传带宽。节点负载的计算仅依赖本地信息，无须获取其他信息，计算方便并节省带宽开销。

1.3 负载的划分及负载信息传播

由于节点负载是动态变化的，因此，管理节点的负载信息是一个难题。解决思路为：将负载划分为3种类型，当Li>80%为超载，记为类型O；Li<30%为轻载节点，记为类型L；其余记为N。划分节点负载类型后则无须实时更新节点的负载值，只需关注节点的负载类型变化，有负载类型变更时才进行负载信息更新和传播。一般在趋于稳态的P2P网络中，有66%的节点不会对系统做任何贡献，而20%的节点却提供98%的共享文件[11]，显然，提供资源的节点数量较少，负载类型变更的节点不多，因而节点无须频繁地更新其负载信息。

在P2P点播系统中，拥有相似资源的节点具有邻居关系，邻居节点间定期地交换缓存位图信息，相互告知节点的缓存信息。当请求节点向某一节点簇中的节点发送数据请求时，其所需要的请求资源存在于该节点簇中的其他节点中。因此，节点负载信息只需要在每个节点簇里面相互传播即可。节点信息的传播形式主要依靠Biased Gossip通信协议形成以节点簇为基础的网络视图，当有节点负载类型变更时，才对这些节点的信息做局部的传播和更新，节省了网络开销。

1.4 负载转移

负载转移的预期目的是节点转移负载时要尽可能地不影响用户的播放流畅度。然而，如果节点超载后把一些未经过筛选的请求转移出去，虽然能缓解节点的负载压力，但可能会出现这么一种情况：节点错误地将特别紧急的请求转移出去，导致该请求不能得到及时回应，此时请求节点将丢失该数据片。因此，在转移负载的过程中，不仅要考虑节点的负载情况，还需要考虑所转移请求的紧急性，才能保证紧急的请求不被丢失。节点在迁移负载的过程中，使用请求优先级来衡量节点处理该请求的优先程度。当节点超载时将其还未处理的请求按优先级从低到高的次序转移给其他节点处理，以保证用户播放的流畅度。请求优先级包含了数据片稀缺度和请求的紧急度。

(2)

其中：Rj为数据片j的稀缺度；N为邻居节点数量；M[k][j]为邻居节点k是否丢失或未缓存有数据片j的情况，若邻居节点k未缓存数据片j，则M[k][j]=0，否则M[k][j]=1。网络中丢失该数据片的节点越多，就应越优先去处理，以降低数据片的稀有度，提升资源共享效率。

请求的紧急度

(3)

其中：Qj为节点请求的数据片j的序号；P为节点当前播放数据片的序号；S为视频中数据片的总数。由式(3)可知，Qj越接近P，则表示该数据请求越紧急。由式(2)、(3)可知，请求的优先级

Pj=Uj×Rj。

(4)

1.5 目标节点选择

在请求迁移的最后，需要分析如何选择合适的轻载节点作为负载的接收者。节点选择的目的是尽可能选择可用带宽大且稳定的节点作为负载的接收者，并采用节点的能力值函数作为选择的依据。然而，节点不会自动知道自身的上传带宽[12]。换句话说，若超载节点在转移负载的时候还要去测量其他节点的可用带宽，势必会影响信息的时效性，导致测量结果不准确。为了不发生额外的信息交换，节点通过记录其历史最大上传速度的方式来预测节点所能提供带宽的能力。此外，节点的能力值计算还要考虑其在线时长。节点的在线概率服从对数正态分布[13]。

(5)

其中：f(t)为节点的在线概率；μ为节点在线时长的均值；σ为节点在线时长的标准差。

为了更好地说明节点的稳定性，在节点能力值的计算中还需考虑其他因素，即节点i的最大上传速度Si和上传的数据片总量Pi。综上所述，节点的能力值为

Wi=f(t)(Si+Pi)。

(6)

节点的f(t)值越大，则节点未来的在线时间越长。评估f(t)和Pi参数的值预示节点的稳定性，而当节点处于轻载状态时，Si越大则预示着它的可用带宽就越大。

基于上述对负载均衡策略的相关分析，LBRM算法基本流程如下:

当节点刚刚变为超载节点时，超载节点将其还未处理的请求按优先级从低到高的顺序排列，然后将优先级低的请求作为转移的对象。超载节点根据缓存位图了解其邻居节点的缓存信息，选择能力值高的邻居节点来转移请求，而当该邻居节点由于持续地接收负载使得自身的负载状态由L转向N时，又发起新一轮的负载类型更新。节点重新更新邻居节点的负载信息和能力值并重新排列，并选择新的节点来接收被转移的数据请求。若邻居节点中无轻载节点，则选择N状态的节点进行传输，而当该节点由N转到O状态后进行新一轮的数据更新时，则舍弃该节点选择其他节点进行请求的迁移。

2 实验结果与分析

为了评估LBRM算法的性能，将其与SQS算法[6]和SALB算法[5]做了对比实验。实验从播放流畅度，平均上行带宽利用率，超载节点比例3个方面对算法的性能进行对比和分析。

实验采用PeerSim工具评估LBRM算法，其参数设置为：1)在网络中放置3000个节点和500个共享视频，节点的上传带宽随机设置为70～200 kbit/s。2)设置Tracker服务器上传带宽为20 Mbit/s，延时为10 ms。

2.1 上传带宽利用率

由于超载节点将其负载转移给空闲的轻载节点，网络节点的带宽利用率相对提高。在实验中，采用CDF描绘3种算法在节点上传带宽利用率上的表现，如图1所示。

图1 节点上传带宽利用率Fig.1 Upload bandwidth utilization of nodes

从图1可看出，在使用LBRM算法的系统中，大约30%的节点的上传带宽利用率小于0.5，而在使用SQS和SALB算法中的比例却分别达到了95%和57%。这是因为SQS算法主要是优先向低负载的节点发送请求，所以网络中大部分节点的负载都处在一个比较低的均值。而SALB算法中用于接受负载的可选对象相对较少，所以低的带宽利用率的节点数量比LBRM算法多。通过观察图1中0.6～0.8内的节点总数，LBRM算法要比其他2种算法多。可见，LBRM算法优于SQS算法和SALB算法。

2.2 节点播放流畅度

播放流畅度是指节点在开始播放视频后，各时间段内节点所获得数据与应获得数据的比值[12]，它反映了用户播放视频的流畅程度。该值越高，表示视频播放越流畅。3种算法在播放流畅度方面的比较如图2所示。

图2 播放流畅度Fig.2 Playback fluency

从图2可看出，3种算法随着节点数量的增加，播放质量有所提升。原因是节点数量的增多使得可选的轻载节点数量变多，节点负载的转移更加方便。当节点的数量超过1000后，SQS算法的播放质量无太大的提升，这是因为它未考虑请求的紧急性和接收者的带宽，使得请求得到及时回应的几率不高。因此，使用LBRM算法能获得更高的播放流畅度。

2.3 超载节点比例

超载节点比例是指单位时间内网络中超载节点数量占节点总数的比例，它反映了系统中超载节点数量的变化情况以及不同算法在均衡节点负载上的效果。单位时间内系统中的超载节点数量减少得越多，说明该负载平衡算法越有效。3种算法在超载节点比例对比如图3所示。

实验中，当网络中超载节点数量占节点总数的10%时，开始记录3种算法的数据，在0～100 s，使用LBRM算法和SQS算法的网络中，超载节点的数量明显降低，SALB算法中超载节点数量减少的速度比前2种算法要慢。这是因为LBRM算法使用的是直接转移请求方法，SQS算法则是直接更改发送请求的方式向低负载的节点发送请求，所以改善速率较快。而SALB算法则需要根据待转移的请求建立后备节点，然后开始转移负载，效率较低。在300～500 s，由于SQS算法在请求发送的问题上不考虑接收者的带宽和承受能力，负载重的节点数量依然比LBRM算法多。因此，LBRM算法在降低网络超载节点的速度和效率上要优于其他2种算法。

图3 网络负载平衡度Fig.3 Network load balancing index

3 结束语

在P2P流媒体点播系统中，节点负载均衡算法能降低超载节点的负载，并提升轻载节点的带宽利用率。LBRM算法主要通过划分邻居节点簇和节点负载类型切换的方式管理网络中节点的负载信息，同时利用分布式节点层的优势，减轻服务器负载。此外，该算法还考虑了转移负载过程中请求的紧急性，避免了传统的负载均衡策略中由于转移负载造成的数据片的丢失。该算法利用节点的能力值选出合适的节点作为请求转移的接收者。通过这些措施，该算法解决了网络中节点负载不均的问题。仿真实验结果表明，该负载均衡算法能均衡网络中节点的负载。

[1] QIAO Y,BOCHMANN G.Load balancing in peer-to-peer systems using a diffusive approach[J].Computing,2012,94(8-10):649-678.

[2] GRAFFI K,KAUNE S,PUSSEP K,et al.Load balancing for multimedia streaming in heterogeneous peer-to-peer systems[C]//Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video,2008:99-104.

[3] YAO L,DAI G Z,ZHANG H X,et al.Load balancing algorithm for P2P systems based on partial network information[J].Journal of Computer Applications,2007,27(5):1080-1082.

[4] BHARAMBE A R,AGRAWAL M,SESHAN S.Mercury:supporting scalable multi-attribute range queries[J]//SIGCOMM Computer Communication Review,2004, 34(4):353-366.

[5] XIONG N,XU K,CHEN L,et al.An effective self-adaptive load balancing algorithm for peer-to-peer networks[C]//26th IEEE International Conference on Parallel and Distributed Processing Symposium Workshops & PhD Forum,2012:1425-1432.

[6] YANG S,SHEN Y,QU W,et al.A novel on-demand streaming service based on improved bittorrent[C]//Fifth IEEE International Conference on Frontier of Computer Science and Technology,2010:46-50.

[7] YANG Y,CHOW A L H,GOLUBCHIK L,et al. Improving QoS in bittorrent-like VoD systems[C]//Proceedings of INFOCOM,2010:1-9.

[8] TAKAYAMA K,FUJIMOTO T,ENDO R,et al.Neighbor selection based on transmission bandwidth on P2P live streaming service[C]// 26th IEEE International Conference on Advanced Information Networking and Applications Workshops,2012:105-110.

[9] GUPTA R,SOMANI A K.Game theory as a tool to strategize as well as predict nodes' behavior in peer-to-peer networks[C]//11th IEEE International Conference on Parallel and Distributed Systems,2005:244-249.

[10] YING H,ZHIGANG C.USMI:an ultra-node selection mechanism with incentive in P2P network[C]//13th IEEE International Conference on Multimedia Information Networking and Security,2010:131-135.

[11] WANG Y, FU T Z J, CHIU D M. Design and evaluation of load balancing algorithms in P2P streaming protocols[J].Computer Networks,2011,55(18):4043-4054.

[12] VLAVIANOS A,ILIOFOTOU M,FALOUTSOS M.BiToS:Enhancing BitTorrent for supporting streaming applications[C]//25th IEEE International Conference on Computer Communications,2006:1-6.

[13] VELOSO E,ALMEIDA V,MEIRA W,et al. A hierarchical characterization of a live streaming media workload[C]//Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment,2002:117-130.

编辑：曹寿平

A load balancing algorithm based on node information

LI Chengsen1, HUANG Guimin1, ZHOU Ya2, LIU Pingshan2

(1.School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China;2.School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China)

In P2P VoD systems, the nodes may receive too many data request and result in overload, this phenomenon leads to the imbalance of network load of nodes and affects performance of the system. In order to balance the load between nodes, a management list of the nodes information is established to manage the dynamic load information of nodes. Based on the load information, a load balancing algorithm based on request migration(LBRM) is proposed. Experimental result indicates that LBRM can solve load imbalance of nodes in network and improve play back quality.

load balance; peer to peer; request migration

2016-03-10

国家自然科学基金(61063038)

黄桂敏(1967-)，男，广西桂林人，教授，博士，研究方向为计算机网络、自然语言处理。E-mail:sen_5200@163.com

李成森，黄桂敏，周娅，等.一种基于节点信息的负载均衡算法[J].桂林电子科技大学学报，2016,36(6):449-453.

TN311

A

1673-808X(2016)06-0449-05