基于动态指数平滑预测的负载均衡算法

孟利民,徐　杨

(浙江工业大学 信息工程学院，浙江 杭州 310023)

基于动态指数平滑预测的负载均衡算法

孟利民,徐杨

(浙江工业大学 信息工程学院，浙江 杭州 310023)

摘要：负载均衡算法是决定计算机集群性能的关键.研究介绍了常见的负载均衡算法，讨论了这些算法的优缺点，并在此基础上提出了一种基于负载预测的均衡算法.该算法通过动态指数平滑模型，计算出适应于当前服务器节点负载时间序列的平滑系数，预测该节点下一时刻负载值，分发器再以负载预测值最小为依据调度用户服务请求.使用OPNET网络仿真软件进行测试，结果表明该算法能有效提高负载均衡效率，具有良好的负载均衡效果.

关键词：计算机集群；负载均衡；动态平滑法；OPNET

随着计算机网络的快速发展，人们对网络的访问量日益增加，各类服务器均面临巨大的访问压力，一些服务器因负载过大而造成如超时，甚至宕机等问题，无法满足用户的需求.计算机集群的出现，有效地解决了这个问题.计算机集群是指多台同构或者异构的计算机通过某种方式协同完成服务或者任务[1].集群通过分发器(Dispatcher)将请求分发到不同的计算机上，充分地利用服务器的资源[2].

负载均衡算法作为计算机集群的重要元素，很大程度上决定着集群的性能.目前对负载均衡算法的研究主要分为静态均衡算法和动态均衡算法[3].常见的静态均衡算法有轮询算法(Round robin)及加权的轮询算法(Weighted round robin)[4]等，轮询算法把用户请求依次分配给服务器节点，这种算法把所有服务器节点都看作是相同的；而加权轮询算法在轮询算法的基础上，考虑了服务器节点本身的性能差异，给每个节点赋予表明处理能力的权重系数，即加权的轮询算法(Weighted round robin).其他静态均衡算法还包括随机分配算法、目标地址或源地址散列算法等，这些算法相对简单，容易实现，但是没有考虑服务器当前的实际负载状态，均衡效果往往并不理想.因此，目前关于均衡算法的研究主要集中在动态均衡算法.经典的动态均衡算法有最小连接算法(Least connection)和最快响应速度算法(Fastest)等[5].最小连接算法将新的用户请求分配给当前连接数最少的服务器节点上，最快响应速度算法则是分配给响应时间最短的节点.文献[6-8]提出了一种动态反馈均衡算法，根据服务器节点的负载特征调整各项权值因子，通过权值来反应实时负载.动态均衡算法的均衡效果相较静态均衡算法而言，性能提高了30%，但是要求在较小的时间间隔内，甚至是实时地向分发器发送负载信息，消耗了大量的服务器资源.综合上述静态均衡算法和动态均衡算法的优缺点，利用主机负载随时间变化具有很强的关联性这一特性[9]，提出了一种基于负载预测的负载均衡算法.

1动态指数平滑预测模型

1.1服务器节点负载的计算

负载是服务器当前性能的体现，在计算机集群中，各个服务器节点往往是异构的，为了使分发器能更均衡地分配任务，充分利用各节点的资源，必须准确地表征服务器节点当前的性能.影响服务器负载的常用指标有CPU利用率、内存使用率、磁盘I/O占用率和网络带宽使用率等.设服务器节点的CPU利用率IC，内存使用率为IM，磁盘带宽占用率为ID，网络带宽使用率为IN，那么其负载为

L=(φ1IC+φ2IM+φ3ID+φ4IN)×100

(1)

式中φi为各项指标的权值参数，反应不同指标的重要程度，且Σφi=1.例如：对于使用RTP协议的流媒体服务器，应当提高带宽使用率的权值；对于FTP服务器，应当提高磁盘I/O使用率的权值等.在实际应用中，根据服务器节点的侧重对φ进行调整，以达到最优的效果.

1.2一次指数平滑模型

指数平滑法是一种简单易行的短期时间序列预测方法，被广泛应用在商业、金融和电力等各个行业[10].指数平滑法包括一次指数平滑、二次指数平滑等，考虑到高次的指数平滑算法给负载分发器带来较大的计算压力，影响计算机集群的性能，因此选取一次指数平滑法.

若服务器节点负载的时间序列为{Lt}，需要在t时刻得出t+1时刻的负载预测值，一次指数平滑预测模型为

St=αLt+(1-α)St-1

(2)

(3)

式中：Lt为服务器节点在t时刻的负载值；St-1为t-1时刻的平滑值；St为t时刻的平滑值，也即t+1时刻的预测值；α为平滑系数.

对式(2)进行递推展开，可得到

(4)

式中S0称为平滑初值.由式(4)可见：t时刻的预测值St用到了全部的历史数据{Lt}，并且对于某一个确定的负载时间序列{Lt}，t时刻的预测值是完全由平滑系数α和平滑初值S0决定的.

在传统的指数平滑模型中，α和S0是静态的.先不考虑平滑初值S0的影响，仅讨论平滑系数α.毫无疑问α对预测结果的精度是至关重要的，如何找到合适的平滑系数α一直是指数平滑法的关键.文献[11]针对静态平滑系数α提出一些改进方法，但是这种通过试探寻找最优的静态平滑系数方法仍然存在较大的盲目性，不能很好的适应负载时间序列{Lt}.对于服务器节点的负载预测，其时间序列{Lt}的长度是无限增长的，且其变化趋势是不可预测的，这就无法通过试探法找到最优的平滑系数α.为此，提出了一种动态平滑系数的预测模型.

1.3动态指数平滑模型

(5)

式中αt是在t时刻根据负载时间序列{Lt}得到的最优动态平滑系数，随着{Lt}地增长，αt也会不断地变化以适应负载时间序列{Lt}，呈现动态特性.

那么如何评价αt是负载时间序列{Lt}的最优平滑系数.文献[13]给出了一个以预测误差平方和SSE最小为目标的评价模型，即

将式(4)代入式(6)，则式(6)可展开为

(1-αt)iS0)2

(7)

求解式(7)即可得到最优的平滑系数αt，可采用收敛速度较快的最速下降法以解决类似的非线性优化模型，需要设置平滑系数初始值αt0，并设置ε>0作为控制条件：

1)对于给定的平滑系数αti(i=0,1,2,3,…)，计算SSE′(αti).若|SSE′(αti)|≤ε，则αti就是近似最优解.

2)若|SSE′(αti)|>ε，利用一维搜索中的黄金分割法计算最优步长λi(i=0,1,2,3,…)，并令αti+1=αti-λi×SSE′(αti)，返回步骤1.

根据式(7)得到最优动态平滑系数，并基于此建立的式(5)的动态平滑预测模型仍然无法直接应用在负载均衡算法当中.首先，负载时间序列{Lt}是无限增长的，因此随着式(5，7)的次数不断增高，使算法复杂度也不断增高，负载分发器不仅要保存大量的时间序列{Lt}，还要花费大量时间用于求解最优平滑系数，反而使计算机集群失去了原有的目的.其次，在动态平滑系数中，α不再像传统的静态平滑系数一样，存在0<α<1的约束.在快速增长或者快速下降的负载时间序列{Lt}中，是有可能使α>1；而在呈现凸型或者凹型的{Lt}中，平滑系数可能存在α<0.在这些情况下，指数平滑法就可能不再遵循“重近轻远”的思想，根据式(5)就有必要考虑平滑初值S0.但同时从式(1)对负载的定义，显然有0

(8)

式中t0为保留的负载时间序列的{Lt}长度.同时，求解最优平滑系数αt的评价模型也修改为

(9)

在此改进模型下，由于在时刻t-t0之前的负载时间序列被丢弃，因此随着负载时间序列{Lt}的增长，式(8，9)的次数也不会增长，维持在关于t0的常数次方，降低了算法的复杂度.另一方面，当负载时间序列{Lt}足够长时，平滑初值S0的影响也会逐渐减小，直至被丢弃.因此平滑初值可选用静态值，在这里定义为

(10)

接下来改进的动态平滑预测模型的关键就是选取合适的保留序列长度t0，使算法在预测精度与复杂度之间有一个合适的权衡.

图1显示了改进的动态指数平滑预测模型对负载的预测结果.实际负载值为某台服务器每隔1min采集一次得到的真实结果.分别取t0=5和t0=10，其中，当t0=5时，预测从第6个负载值开始；同理，t0=10时，预测从第11个负载值开始.对图1的分析看出：t0=5和t0=10时其预测结果与真实负载曲线都较为吻合.且当t0=10时，其预测的精度提升并不明显，但是其算法复杂度要比t0=5时要高出许多.因此对动态负载预测模型而言，取负载时间序列保留长度t0=5较为合适.

图1　动态指数平滑法对负载的预测结果Fig.1　The predictions of load through dynamic exponential smoothing method

图2显示了静态平滑系数的预测模型对负载的预测结果，由于负载时间序列变化多样，单一的平滑系数较难适应整个时间序列，因此预测精度并不高.从图1，2的对比中不难看出：动态指数平滑法的预测结果要优于静态指数平滑法.

图2　静态指数平滑法对负载的预测结果Fig.2　The predictions of load through static exponential smoothing method

2负载均衡算法

2.1负载预测函数描述

设有服务器节点{Svi}，n为计算机集群的服务器个数.当某个服务器启动时，每隔一分钟采集一次自己的负载信息，生成负载预测的初始时间序列{Lt0=5}Svi，并将此序列发送到分发器.分发器保存此初始时间序列{Lt0=5}Svi，由式(10)得到Svi的平滑初值SSvi.设预测值获取函数为SSvi=ExpPrediction(LSvi)，函数ExpPrediction(LSvi)的工作过程如下：

1) 分发器找到服务器节点Svi的负载时间序列{Lt0=5}Svi，丢弃此时间序列中最早的负载值Learly，并将最新的负载值LSvi加入到时间序列{Lt0=5}Svi的末尾.

2) 根据前一时刻的平滑值SSvi、新的负载时间序列{Lt0=5}Svi和式(9)的动态平滑系数评价模型，利用最速下降法得到适应此负载序列的最优平滑系数αt.

3) 将SSvi、负载时间序列{Lt0=5}Svi和动态平滑系数αt代入到式(8)的动态平滑预测模型，得到新的平滑值SSvi，替代掉原来的平滑值SSvi，而SSvi将作为服务器节点Svi下一时刻的预测值.

2.2负载均衡算法描述

分发器收到用户服务的请求后，根据负载均衡算法将请求发送到负载最优的服务器节点Svi处理，具体算法如下：

1) 分发器收到用户的请求，在分发器已有的服务器节点列表中{Svn}选择平滑值SSvi最小的服务器节点Svi.SSvi最小代表下一时刻节点Svi的负载最小.

2) 分发器将请求发送到服务器节点Svi处理.

3) 服务器节点Svi处理完请求后，在响应中携带自己当前时刻的负载数据，并将响应发回到分发器.

4) 分发器收到服务器节点Svi发回的响应，拿到Svi新时刻的负载LSvi，调用负载预测函数ExpPrediction(LSvi)得到下一时刻的负载预测值Svi，作为下一次分发器调度的依据.

3网络仿真结果与分析

为了检验算法的性能，用OPNET14.5进行了网络仿真.OPNET是一款应用与网络仿真软件，它支持大量的网络通信协议和模拟系统分发，通过对离散事件的仿真来分析系统的行为和性能[14].OPNET提供了三层建模机制，分别是进程层、节点层和网络层.负载均衡算法是在分发器的进程层当中.

计算机集群中，服务器组由3台Web服务器组成，其性能比为4︰7︰10，每台服务器通过100 M线路连接分发器；客户端组由6个子网组成客户端，其中5个子网组是内部子网，剩余一个是外部子网，每个子网都包含45个用户终端.在搭建环境完成后，选择仿真设置Application_Config中的HTTP应用，模拟客户端向服务器发送HTTP请求，仿真时间是5 h.为了验证笔者算法的性能，将笔者算法与动态均衡算法中的最小连接算法进行了对比，部分仿真结果如图3，4所示.

图3　最小连接算法下的CPU使用率Fig.3　CPUutilization under least connection algorithm

图4　笔者负载均衡算法下的CPU使用率Fig.4　CPUutilization under this paper algorithm

以CPU使用率为代表，图3显示了最小连接算法下，各服务器的CPU使用率，图4显示了笔者算法的CPU使用率.不难发现图3的CPU使用率稳定在10%，17%，25%，而图4的CPU使用率均稳定在20%.结果表明：最小连接算法下，分发器并没有按照服务器节点的负载能力分配任务，使得一些节点的CPU使用率过高，没有很好地实现负载均衡.而基于笔者均衡算法的服务器节点资源都得到了较为均衡地利用，比较好地实现了负载均衡.

综上所述，笔者的负载均衡算法与最少连接算法相比，均衡效果有了较为明显的改善.

4结论

改进的负载预测均衡算法通过建立动态平滑指数的预测模型，以较短的负载时间序列提高了负载预测精度，使分发器能够更准确地调度用户服务的请求，提高了服务器节点的资源使用率.该算法在OPNET网络仿真软件下与最少连接算法进行了比较，结果显示笔者算法具有更好的负载均衡效果.

参考文献：

[1]WU S X, BANZHAF W. The use of computational intelligence in intrusion detection systems: a review[J]. Applied soft computing,2010,10(1):1-35.

[2]张玉芳,魏钦磊,赵膺.基于负载权值的负载均衡算法[J].计算机应用研究,2012,29(12):4711-4713.

[3]BRYHNI H, KLOVNING E, KUREØ. A comparison of load balancing techniques for scalable web servers[J]. Network of IEEE,2000,14(4):58-64.

[4]魏钦磊.基于集群的动态反馈负载均衡算法的研究[D].重庆：重庆大学,2013.

[5]张前进,齐美彬,李莉.基于应用层负载均衡策略的分析与研究[J].计算机工程与应用,2007,43(32):138-142.

[6]孔令凡,吕丽民.基于B/S的网管负载平衡问题研究[J].浙江工业大学学报,2002,30(2):168-171.

[7]田绍亮,左明,吴绍伟.一种改进的基于动态反馈的负载均衡算法[J].计算机工程与设计,2007,28(3):572-573.

[8]孟利民,潘进学.视频监控系统中负载均衡算法的设计[J].浙江工业大学学报,2014,42(6):607-611.

[9]DINDA P A. The statistical properties of host load[J]. Scientific programming,1999,7(3/4):211-229.

[10]周炳飞.动态指数平滑模型预测及应用[J].哈尔滨师范大学自然科学学报,2013(4):25-27.

[11]唐炎森.指数平滑预测公式与平滑系数[J].统计与信息论坛,1998(1):39-44.

[12]黎锁平,刘坤会.动态指数平滑优化模型及其应用[J].系统工程学报,2003,18(2):163-167.

[13]吴德会.动态指数平滑预测方法及其应用[J].系统管理学报,2008,17(2):151-155.

[14]张铭.OPNET Modeler与网络仿真[M].北京：人民邮电出版社,2007.

(责任编辑：陈石平)

Load balancing algorithm based on dynamic exponential smoothing prediction

MENG Limin, XU Yang

(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The load balancing algorithm is the key to determine the performance of a server cluster. In this paper, we introduce some common load balancing algorithms and discuss their advantages and disadvantages. Then, we propose an improved load prediction based load balancing algorithm. It applies dynamic exponential smoothing model to calculate the dynamic smooth parameters which are adapted to the current server node load time sequence and predict the next load value. Dispatcher can use the minimum load predictive value to schedule customer requests. We use the OPNET simulation software to test the algorithm and the result shows that the proposed algorithm has a better load balancing effect.

Keywords:server cluster; load balancing; dynamic exponential smoothing; OPNET

收稿日期：2016-01-21

基金项目：国家自然科学基金资助项目(61372087)

作者简介：孟利民(1963—)，女，浙江金华人，教授，研究方向为无线通信与网络多媒体数字通信，E-mail:mlm@zjut.edu.cn．

中图分类号：TP393

文献标志码：A

文章编号：1006-4303(2016)04-0379-04