基于预测机制的分级负载均衡算法

连加典;刘宏立;谢海波;龚霞;胥小波

【摘 要】In order to solve the problem of uneven distribution of load in server cluster, considering the increasing load and performance of server nodes based on the type of users’history requests, a classified load balancing algorithm based on prediction mechanism is proposed. Load balancing node establishes single exponential smoothing model to forecast load based on the type of users’requests, and divides the predicted load with three classes:low load, normal load and heavy load. Load balancing node performs the scheduling and management based on the predicted load, and realizes load balancing of the system. Using the OPNET simulation software for testing, the result of simulation shows that the algo-rithm can effectively improve the efficiency of load balancing, and has a better load balancing result.%为解决服务器集群负载分配不均的问题，根据用户访问的请求类型，综合考虑用户历史请求引起的负载增量和服务器节点性能，提出了基于预测机制的分级负载均衡算法。负载均衡节点根据用户访问的请求类型建立一次指数平滑预测模型，对相应请求类型引起的负载进行预测，并将预测负载划分为低负载、正常负载、重负载等三个负载等级，根据负载等级对用户请求进行调度，从而实现负载均衡。使用OPNET仿真软件进行测试，结果表明该算法能有效提高负载均衡效率，有较好的负载均衡效果。 【期刊名称】《计算机工程与应用》 【年(卷),期】2015(000)011

【总页数】6页(P67-71,98)

【关键词】Web服务器集群;负载分级;负载预测;一次指数平滑;OPNET 【作 者】连加典;刘宏立;谢海波;龚霞;胥小波

【作者单位】湖南大学 电气与信息工程学院，长沙 410082;湖南大学 电气与信息工程学院，长沙 410082;长沙宏地科技开发有限公司，长沙 410004;湖南大学 电气与信息工程学院，长沙 410082;湖南大学 电气与信息工程学院，长沙 410082 【正文语种】中 文 【中图分类】TP393 1 引言

计算机集群是指多台同构或异构的计算机通过某种方式连接起来协同完成服务或任务[1]。Web集群服务器的典型结构是使用分发器（Dispatcher）将客户端请求转发给后端服务器，让整个集群表现得像一个服务于同一IP地址的虚拟服务器。 Web集群和负载均衡技术具有可靠性、可伸缩性和可管理性，Web集群通过负载均衡对Web请求分流至不同的服务器[2]。因此负载均衡是集群系统中最为关键的部分，它保证了集群系统拥有最大的处理速度和服务能力[3]。

传统的负载均衡算法有随机法、轮转法、最小连接法等[4]，还有在传统算法基础上进行改进的算法，如文献[5-8]。由于用户不同请求类型所消耗的服务器系统资源不同，其变化具有一定的规律[9-11]，抓住这些规律就可以对负载进行有针对的预测，基于此，本文提出基于预测机制的分级负载均衡算法。 2 指数平滑预测模型

指数平滑法又称指数加权平均法[12]，是1959年美国学者布朗（Robert

G..Brown）首先提出来的。这种方法是以时间为序揭示其历史资料的变化规律，克服了移动平均预测法没有充分利用时间序列全部数据的信息和对参与运算的数据等权看待的缺点，且过程清晰、计算便捷，因此在理论上倍受推崇，在工程、经济和管理等方面的预测中被广泛应用。常用的指数平滑法包括一次指数平滑、二次指数平滑和三次指数平滑。其中，一次指数平滑法适用于水平型历史数据的预测，而二次指数平滑法、三次指数平滑法适用于斜坡型线性趋势历史数据的预测。 考虑到算法复杂度过大引起的延时可能会影响到负载均衡器的调度，以及根据不同请求对服务器负载进行的预测没有趋势性变动，所以本文选择一次指数平滑模型进行负载预测。 2.1 一次指数平滑模型

一次指数平滑法，是指根据本期观察和上期一次指数平滑值，计算其加权平均值，并将其作为下期预测值的方法。它仅适用于各期数据大体呈水平趋势变动的时间序列的分析预测，并且仅能向下作一期预测。一次指数平滑法预测模型适用于平稳型数据的预测。设定时间序列为Y1，Y2，…，Yn，则一次指数平滑公式为：

其中，St为第t时刻的一次指数平滑值；α为平滑系数，且0＜α＜1；yt为t时刻的观察值。t+1时刻一次指数平滑公式如式（2）所示：

从而，t+i时刻一次指数平滑公式如式（3）所示：

式中i表示经过的时刻点，也表示超前预测时刻。

对平滑公式进行扩展，用基本的平滑公式代替St-1，如式（4）所示：

然后,接着替代 St-2，St-3， 如此递归，直到 S0，这样就可以得到式（5），如下

所示：

由于0＜α＜1，当t→∞时，(1-α)t→0，于是将式（5）改写为：

由于，各时间序列系数由近及远根据指数规律变化，且又具有平滑数据的功能。 2.2 指数平滑法中确定初始平滑值S0

一次指数平滑的起始平滑点是S0，一般有三种方法进行初始化S0：一种方法是S0=y1，这种方法较为常见；在时间序列较长，α值较大时，初始值的大小对预测值影响不大，可以取；还有一种是取S0=本文选取较常用的方法进行初始化，即S0=y1。

2.3 平滑系数α的选择

指数平滑法中，平滑系数的选择十分重要，它代表模型对时间序列变化的反应速度，又决定预测中修匀随机误差的能力。α选取得越大，表示近期数据所载的信息所占权重越大，修正的幅度也较大；α选取得越小，表示以前的数据所载信息占的权重相应较小，修正的幅度也就越小。从理论上说，取0～1之间的任意数值均可以。其选择的原则是使预测值与时间观测序列之间的均方差和平均绝对误差最小。α选择具体如下：

（1）当时间序列呈现较稳定的水平趋势时，应选较小的α值一般可在0.05～0.20之间取值，使观察值在现实的指数平滑中大小权数相当接近，从而使各期预测值对预测结果有相似的影响。

（2）当时间序列有波动，但长期趋势变化不大时，可选稍大的α值，常在0.1～0.4之间取值。

（3）当时间序列波动很大，长期趋势变化幅度较大,，呈现明显且迅速的上升或下降趋势时，宜选择较大的α值，如可在0.6～0.8间选值，以使预测模型灵敏度高

些，能迅速跟上数据的变化。

（4）当时间序列数据是上升（或下降）的发展趋势类型，应取较大的α值，在0.6～1之间。

2.4 节点性能和负载的计算

集群系统中的服务器节点往往是异构的，因此在任务分配时必须根据服务器节点的性能区别对待，以达到能者多劳、负载均衡的效果。服务器的负载状况与CPU利用率、内存使用率、磁盘I/O操作次数和服务器的当前活动连接数等多方面因素有关。根据需要，设服务器节点Si的CPU处理性能Ui，利用率为Ci；内存容量Vi，利用率为 Mi；网络带宽Wi，利用率 Bi，以这些参数作为指标，并为每个指标设定相应的系数来区分其影响服务器负载的重要程度。服务器节点Si的综合性能Pi可以用以下公式定义[13]：

服务器节点Si的综合负载Li可以用以下公式定义：

φi是各项指标的权值参数，反映不同类型的服务对各个指标的影响程度，其中，φ1+φ2+φ3=1，对于不同业务类型的网络应用，上述各个参数的重要程度也有所不同，如ftp服务主要对节点的网络吞吐量、硬盘I/O要求较大，http服务则侧重于节点CPU运算速度和内存，而数据库操作则侧重于网络吞吐量、硬盘I/O和CPU运算速度。 φ 在本文中设置为：φ=(0.2，0.3，0.5)，在实际的应用过程中，该参数可以根据实际情况进行调整，以达到更佳的效果。 3 基于预测机制的分级负载均衡算法

传统的负载均衡算法将服务器的综合性能负载作为任务请求分配的依据，该做法通常具有良好的通用性，然而在Web服务器集群系统中，处理不同类型的任务请求时所占用的系统资源不同，因此一定程度上了负载均衡的效果。因此，根据服

务器的收到的请求类型，将http操作请求、ftp操作请求、远程登录操作请求、email操作请求、打印操作请求以及数据库操作请求引起的负载增量作为任务请求分配的6项性能指标，分别建立一次指数平滑预测模型，根据Web用户请求的类型，结合负载预测的结果，实现对任务进行分配和调度。

Web服务器集群系统由一个负责请求分配的负载均衡节点和一个负责处理任务请求的服务器节点集合S=(S1，S2，…，Sn)组成。在负载均衡节点上保存6张负载信息表：Tab_http，Tab_ftp，Tab_in，Tab_email，Tab_pt和Tab_db，分别记录各个服务器节点的http操作、ftp操作、远程登录操作、电子邮件操作、打印操作以及数据库操作引起的负载增量。 3.1 服务请求的划分

基于互联网的技术日新月异，各种Web应用层出不穷，主要有http、ftp、远程登录、email、打印以及数据库操作等服务，根据Web请求的特点和机制，将用户服务请求分为六类，分别是： （1）http操作请求； （2）ftp操作请求； （3）远程登录操作请求； （4）email操作请求； （5）打印操作请求； （6）数据库操作请求。

服务器可以通过端口号来判断相应的服务请求。由于这些服务请求都对应不同的协议，所以不同的请求设置了不同的端口，服务器通过监听这些端口来实现对相应请求的各种操作。

服务器想要根据当前负载的情况就能对下个时刻的负载做出合理的预测，仅仅从当前服务器的总负载来预测缺乏针对性，即使有很好的算法也很难有好的预测结果。

针对这个问题，结合服务请求的划分，提出根据用户的服务请求类型对负载进行预测的策略。

由于服务器处理不同的服务请求所消耗的系统资源不同，各请求引起负载增量有各自不同的变化规律，利用一次指数平滑预测有利于更好地利用这些规律，对不同的服务可以请求设置不同的平滑系数α，更有针对性地实现负载的预测，从而得到更好的预测结果。 3.2 负载等级的划分

根据服务器的负载Li的情况可将负载分为3个等级，分别为： （1）低负载 Li＜Llow；

（2）正常负载 Llow≤Li≤Lheavy； （3）重负载 Li＞Lheavy。

其中Llow为服务器工作负载下限，Lheavy为服务器工作负载上限，可以根据具体情况设置。

低负载表明服务器处于低负荷工作状态，有多余的系统资源来继续接受并处理客户请求，具有较快的响应速度和处理效率。

正常负载表明服务器处于正常工作状态，能够充分利用系统资源来处理客户端请求，可以继续接受并处理客户端请求，但是空间没有低负载那么大，并且要考虑新增的负载是否超过服务器负载上限Lheavy成为重负载。

重负载表明服务器负载较重，响应速度和处理效率都受到了较大的影响，不能继续接受客户端请求，否则可能出现系统奔溃，是负载均衡过程中避免出现的状态。对负载进行等级划分可以方便负载均衡器对客户请求进行调度管理。

本文针对预测负载VL的情况进行等级划分，分为低负载、正常负载和重负载。 3.3 负载预测

服务器采集用户请求产生的负载信息，作为负载预测的历史数据，由前面介绍的一

次指数平滑算法对各请求生成的负载信息进行预测。

设VL为预测总负载，L为服务器当前负载，VLhttp为预测http操作引起的负载增量，VLftp为预测ftp操作引起的负载增量，VLdb为预测数据库操作引起的负载增量，VLin为预测远程登录引起的负载增量，VLemail为预测email操作引起的负载增量，VLpt为预测打印操作引起的负载增量，预测值获取函数如下：

从而得到预测总负载为：

VLreq为当服务请求到达负载均衡节点时，预测服务器对应该请求的预测负载增量（VLdb、VLftp、VLin、VLemail、VLpt或VLdb）。

在负载均衡节点上建立6个用于存放历史样本数据的空间 Shttp，Sftp，Sin，Semail，Spt和 Sdb，具体的负载预测过程如下：

（1）负载均衡节点初始化请求负载信息表Tab_http，Tab_ftp，Tab_in，

Tab_email，Tab_pt和 Tab_db，清空历史样本空间 Shttp，Sftp，Sin，Semail，Spt和 Sdb 。

（2）负载均衡节点等待用户发送服务请求。当t时刻请求到达负载均衡节点，调用server_load_update（）函数获取各个服务器的该时刻的总负载Lt。 （3）判断样本空间 Shttp，Sftp，Sin，Semail，Spt和 Sdb是否为空，为空则转到（5）。

（4）负载均衡节点以各个服务器的样本空间Shttp，Sftp，Sin，Semail，Spt和 Sdb 的历史数据为基础，根据用户的服务请求类型，预测每个服务器相应请求引起的负载增量，然后根据负载预测公式（15）得到预测总负载，为负载均衡调度提供依据。

（5）服务器等待负载均衡节点发送服务请求。当t+1时刻请求到达服务器，服务

器发送响应消息到负载均衡节点，负载均衡节点调用server_load_get（）函数获取该时刻的服务器总负载Lt+1。

（6）负载均衡节点计算服务请求到达服务器前后获取的总负载之差Lt+1-Lt，即为相应请求引起的负载增量 Lhttp，Lftp，Lin， Lemail，Lpt或 Ldb，负载均衡节点生成相应的 请 求 负 载 序 列 {Lhttp(t)}、{Lftp(t)}、{Lin(t)}、{Lemail(t)}、{Lpt(t)} 或 {Lpt(t)}， 放入样本空间 Shttp，Sftp， Sin，Semail，Spt或Sdb。 （7）返回（2）继续。

3.4 基于预测机制的分级负载均衡算法 3.4.1 算法总体设计思想

服务器均衡节点根据到达均衡节点的用户服务请求类型建立一次指数平滑模型对负载进行预测，然后根据预测值对服务器负载进行等级判定，最后依据负载等级对用户的服务请求进行负载调度。 3.4.2 具体算法描述

（1）合理地设置阈值工作负载下限值Llow，工作负载上限值Lheavy以及各请求类型对应的一次指数平滑系数α。

（2）服务器根据用户的服务请求（http、ftp、远程登录、email、打印或者数据库操作），由2.3节描述的过程可以得到各服务器相应请求的预测负载VLreq：

进而由式子VL=L+VLreq得到预测总负载。 （3）由2.2节所述，对预测负载VL进行等级判定： 当VL＜Llow时，预测负载为为低负载； 当Llow≤VL≤Lheavy时，预测负载为正常负载； 当VL＞Lheavy时，预测负载为重负载。

（4）负载均衡节点根据得到的负载等级调用find_best_server（）函数对该时刻

的服务请求进行调度。

遍历所有服务器节点，当只有一个服务器节点预测负载为低负载时，将服务请求发送到该服务器节点；若出现多个服务器节点预测负载都为低负载，则选择预测负载最低的服务器节点。

当遍历所有服务器节点没有低负载节点时，则查找正常负载节点，当只有一个服务器预测负载为正常负载时，则将服务请求发送到该服务器节点；若出现多个服务器预测负载都为正常负载，则选择预测负载最低的服务器节点。

若遍历所有服务器节点没有低负载节点，也没有正常负载节点，即只有重负载节点，则拒绝用户的操作请求，以防止系统奔溃。 4 算法仿真与结果分析

为了验证算法的性能，本文使用OPNET 14.5网络仿真软件构建仿真环境。OPNET提供了三层建模机制[14-15]，分别在进程层、节点层和网络层进行由下到上的建模，同时在仿真的过程中它采用了离散事件驱动的模拟机理，能够准确地分析复杂网络的性能和行为，进行数据采集和统计。负载均衡算法是在负载均衡节点的进程层里，可以通过C/C++语言来实现。

服务器组由3台Web服务器server1、server2和server3组成，客户端由5个子网组成，每个子网又由40个用户终端构成。服务器节点性能比为1∶1.5∶2，各自通过100 Mb/s的双工通信线与负载均衡节点相连接。在仿真设置 Application_Config里设置了 http、ftp、remote login、email、print、database等应用，模拟用户向服务器发送 http、ftp、remote login、email、print、database等请求，并设置仿真时间为10 h。选取服务器CPU利用率和数据包接收速率作为衡量服务器负载情况的统计量。

为了验证本文的算法的性能，本算法与最小连接算法进行了对比。实验网络仿真模型如图1所示。

图1 负载均衡网络仿真模型图 图2 最小连接算法CPU利用率 图3 本文算法CPU利用率 图4 最小连接算法包接收速率 图5 本文算法包接收速率

仿真结果如图 2～5（Server1、Server、Server3分别为图1中的三个服务器）。 由于系统是异构的，服务器节点的性能各不相同，这时，负载均衡要实现的目标是：让综合性能好的服务器处理更多的请求，让综合性能差的处理尽量少的请求，即让请求负载与服务器性能成正比；同时，尽量让每台服务器的CPU利用率大体保持一致。

由图2可以看出server1的CPU利用率大致稳定在30%，server2的CPU利用率大致稳定在23%，server3的CPU利用率大致稳定在15%，它们的利用率不尽相同，且相差较大，没有很好地实现负载均衡。

由图3可以看出，server1、server2、server3的CPU利用率均大致稳定在23%，各服务器系统资源都得到了较为均衡的利用，说明比较好地实现了负载均衡。 由图4可以看出，server1、server2、server3的数据包接收速率均大致稳定在31 000 packet/s，负载均衡节点并没有根据服务器的性能进行合理调度，适合在服务器性能相同的同构系统中，但在服务器性能差异较大的异构系统则均衡效果不理想。

由图5可以看出，server1的数据包接收速率稳定在20 000 packet/s，server2的数据包接收速率稳定在26 000 packet/s，server3的数据包接收速率稳定在40 000 packet/s，它们的比值为20∶26∶40，即1∶1.3∶2，比较接近服务器的性能比1∶1.5∶2，负载均衡效果较为理想。

综上可以看出本文算法较之最少连接算法负载均衡效果有了较明显的改善。

5 结束语

本文提出基于预测机制的分级负载均衡算法，根据用户发送到负载均衡节点的服务请求类型，利用一次指数平滑模型有针对性地对各请求类型进行负载预测，然后根据预测的结果对负载等级进行判定，最后对判定的结果做相应的负载调度和管理。该算法在OPNET网络仿真软件进行了仿真，并与最少连接算法仿真结果进行了比较，结果显示本文算法与最少连接法相比具有更好的负载均衡效果。

【相关文献】

[1]许海成，傅锦伟.服务器集群负载均衡的建模与仿真研究[J].计算机仿真，2012，29（3）：180-183.

[2]李双庆，古平.Web集群系统负载均衡策略分析与研究[J].计算机工程与应用，2002，38（19）：40-42.

[3]张普，王青，杨立光.网络计算机集群负载均衡机制的研究[J].计算机工程与设计，2006，27（16）：2914-2917.

[4]史鸿雁，李海生.基于OPNET的集群负载均衡仿真[J].北京工商大学学报：自然科学版，2010，28（1）：79-82.

[5]席静，褚兴军，徐志伟.一种提高Web服务器性能的方法[J].计算机研究与发展，2002，39（2）：133-136.

[6]Chen Zhenxiang，Yang Bo，Chen Yuehui，et al.Online hybrid traffic classifier for peer-to-peer systems based on network processors[J].Applied Soft Computing，2009，9（2）：685-694.

[7]Bryhni H.A comparison of load balancing techniques for scalable Web servers[J].IEEE Network，2000，14（4）：58-.

[8]刘振英，方滨兴，胡铭曾，等.一个有效的动态负载均衡方法[J].软件学报，2001，12（4）：563-569.

[9]杨伟，朱巧明，李培峰，等.基于时间序列的服务器负载预测[J].计算机工程，2006，32（19）：143-148.

[10]潘红羽.时间序列分析[M].北京：对外经济贸易大学出版社，2006：69-71.

[11]陈志刚，许伟，曾志文.一种基于预测的动态负载均衡模型及算法研究[J].计算机工程，2004，30（23）：87-.

[12]徐大江.预测模型参数的指数平滑估计法及其应用的进一步研究[J].系统工程理论与实践，1999，19（2）：25-30.

[13]张玉芳，魏钦磊.基于负载权值的负载均衡算法[J].计算机应用研究，2012，29（12）：4711-4713.

[14]陈敏.OPNET网络仿真[M].北京：清华大学出版社，2004：9-14.

[15]操惊雷，周建国，秦磊华.基于OPNET的网络压力仿真[J].计算机工程，2009，35（23）：115-117.