孟利民,徐　楊

(浙江工業(yè)大學 信息工程學院，浙江 杭州 310023)

基于動態(tài)指數(shù)平滑預測的負載均衡算法

孟利民,徐楊

(浙江工業(yè)大學 信息工程學院，浙江 杭州 310023)

摘要：負載均衡算法是決定計算機集群性能的關鍵.研究介紹了常見的負載均衡算法，討論了這些算法的優(yōu)缺點，并在此基礎上提出了一種基于負載預測的均衡算法.該算法通過動態(tài)指數(shù)平滑模型，計算出適應于當前服務器節(jié)點負載時間序列的平滑系數(shù)，預測該節(jié)點下一時刻負載值，分發(fā)器再以負載預測值最小為依據(jù)調(diào)度用戶服務請求.使用OPNET網(wǎng)絡仿真軟件進行測試，結果表明該算法能有效提高負載均衡效率，具有良好的負載均衡效果.

關鍵詞：計算機集群；負載均衡；動態(tài)平滑法；OPNET

隨著計算機網(wǎng)絡的快速發(fā)展，人們對網(wǎng)絡的訪問量日益增加，各類服務器均面臨巨大的訪問壓力，一些服務器因負載過大而造成如超時，甚至宕機等問題，無法滿足用戶的需求.計算機集群的出現(xiàn)，有效地解決了這個問題.計算機集群是指多臺同構或者異構的計算機通過某種方式協(xié)同完成服務或者任務[1].集群通過分發(fā)器(Dispatcher)將請求分發(fā)到不同的計算機上，充分地利用服務器的資源[2].

負載均衡算法作為計算機集群的重要元素，很大程度上決定著集群的性能.目前對負載均衡算法的研究主要分為靜態(tài)均衡算法和動態(tài)均衡算法[3].常見的靜態(tài)均衡算法有輪詢算法(Round robin)及加權的輪詢算法(Weighted round robin)[4]等，輪詢算法把用戶請求依次分配給服務器節(jié)點，這種算法把所有服務器節(jié)點都看作是相同的；而加權輪詢算法在輪詢算法的基礎上，考慮了服務器節(jié)點本身的性能差異，給每個節(jié)點賦予表明處理能力的權重系數(shù)，即加權的輪詢算法(Weighted round robin).其他靜態(tài)均衡算法還包括隨機分配算法、目標地址或源地址散列算法等，這些算法相對簡單，容易實現(xiàn)，但是沒有考慮服務器當前的實際負載狀態(tài)，均衡效果往往并不理想.因此，目前關于均衡算法的研究主要集中在動態(tài)均衡算法.經(jīng)典的動態(tài)均衡算法有最小連接算法(Least connection)和最快響應速度算法(Fastest)等[5].最小連接算法將新的用戶請求分配給當前連接數(shù)最少的服務器節(jié)點上，最快響應速度算法則是分配給響應時間最短的節(jié)點.文獻[6-8]提出了一種動態(tài)反饋均衡算法，根據(jù)服務器節(jié)點的負載特征調(diào)整各項權值因子，通過權值來反應實時負載.動態(tài)均衡算法的均衡效果相較靜態(tài)均衡算法而言，性能提高了30%，但是要求在較小的時間間隔內(nèi)，甚至是實時地向分發(fā)器發(fā)送負載信息，消耗了大量的服務器資源.綜合上述靜態(tài)均衡算法和動態(tài)均衡算法的優(yōu)缺點，利用主機負載隨時間變化具有很強的關聯(lián)性這一特性[9]，提出了一種基于負載預測的負載均衡算法.

1動態(tài)指數(shù)平滑預測模型

1.1服務器節(jié)點負載的計算

負載是服務器當前性能的體現(xiàn)，在計算機集群中，各個服務器節(jié)點往往是異構的，為了使分發(fā)器能更均衡地分配任務，充分利用各節(jié)點的資源，必須準確地表征服務器節(jié)點當前的性能.影響服務器負載的常用指標有CPU利用率、內(nèi)存使用率、磁盤I/O占用率和網(wǎng)絡帶寬使用率等.設服務器節(jié)點的CPU利用率IC，內(nèi)存使用率為IM，磁盤帶寬占用率為ID，網(wǎng)絡帶寬使用率為IN，那么其負載為

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

(1)

式中φi為各項指標的權值參數(shù)，反應不同指標的重要程度，且Σφi=1.例如：對于使用RTP協(xié)議的流媒體服務器，應當提高帶寬使用率的權值；對于FTP服務器，應當提高磁盤I/O使用率的權值等.在實際應用中，根據(jù)服務器節(jié)點的側(cè)重對φ進行調(diào)整，以達到最優(yōu)的效果.

1.2一次指數(shù)平滑模型

指數(shù)平滑法是一種簡單易行的短期時間序列預測方法，被廣泛應用在商業(yè)、金融和電力等各個行業(yè)[10].指數(shù)平滑法包括一次指數(shù)平滑、二次指數(shù)平滑等，考慮到高次的指數(shù)平滑算法給負載分發(fā)器帶來較大的計算壓力，影響計算機集群的性能，因此選取一次指數(shù)平滑法.

若服務器節(jié)點負載的時間序列為{Lt}，需要在t時刻得出t+1時刻的負載預測值，一次指數(shù)平滑預測模型為

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

(2)

(3)

式中：Lt為服務器節(jié)點在t時刻的負載值；St-1為t-1時刻的平滑值；St為t時刻的平滑值，也即t+1時刻的預測值；α為平滑系數(shù).

對式(2)進行遞推展開，可得到

(4)

式中S0稱為平滑初值.由式(4)可見：t時刻的預測值St用到了全部的歷史數(shù)據(jù){Lt}，并且對于某一個確定的負載時間序列{Lt}，t時刻的預測值是完全由平滑系數(shù)α和平滑初值S0決定的.

在傳統(tǒng)的指數(shù)平滑模型中，α和S0是靜態(tài)的.先不考慮平滑初值S0的影響，僅討論平滑系數(shù)α.毫無疑問α對預測結果的精度是至關重要的，如何找到合適的平滑系數(shù)α一直是指數(shù)平滑法的關鍵.文獻[11]針對靜態(tài)平滑系數(shù)α提出一些改進方法，但是這種通過試探尋找最優(yōu)的靜態(tài)平滑系數(shù)方法仍然存在較大的盲目性，不能很好的適應負載時間序列{Lt}.對于服務器節(jié)點的負載預測，其時間序列{Lt}的長度是無限增長的，且其變化趨勢是不可預測的，這就無法通過試探法找到最優(yōu)的平滑系數(shù)α.為此，提出了一種動態(tài)平滑系數(shù)的預測模型.

1.3動態(tài)指數(shù)平滑模型

(5)

式中αt是在t時刻根據(jù)負載時間序列{Lt}得到的最優(yōu)動態(tài)平滑系數(shù)，隨著{Lt}地增長，αt也會不斷地變化以適應負載時間序列{Lt}，呈現(xiàn)動態(tài)特性.

那么如何評價αt是負載時間序列{Lt}的最優(yōu)平滑系數(shù).文獻[13]給出了一個以預測誤差平方和SSE最小為目標的評價模型，即

將式(4)代入式(6)，則式(6)可展開為

(1-αt)iS0)2

(7)

求解式(7)即可得到最優(yōu)的平滑系數(shù)αt，可采用收斂速度較快的最速下降法以解決類似的非線性優(yōu)化模型，需要設置平滑系數(shù)初始值αt0，并設置ε>0作為控制條件：

1)對于給定的平滑系數(shù)αti(i=0,1,2,3,…)，計算SSE′(αti).若|SSE′(αti)|≤ε，則αti就是近似最優(yōu)解.

2)若|SSE′(αti)|>ε，利用一維搜索中的黃金分割法計算最優(yōu)步長λi(i=0,1,2,3,…)，并令αti+1=αti-λi×SSE′(αti)，返回步驟1.

根據(jù)式(7)得到最優(yōu)動態(tài)平滑系數(shù)，并基于此建立的式(5)的動態(tài)平滑預測模型仍然無法直接應用在負載均衡算法當中.首先，負載時間序列{Lt}是無限增長的，因此隨著式(5，7)的次數(shù)不斷增高，使算法復雜度也不斷增高，負載分發(fā)器不僅要保存大量的時間序列{Lt}，還要花費大量時間用于求解最優(yōu)平滑系數(shù)，反而使計算機集群失去了原有的目的.其次，在動態(tài)平滑系數(shù)中，α不再像傳統(tǒng)的靜態(tài)平滑系數(shù)一樣，存在0<α<1的約束.在快速增長或者快速下降的負載時間序列{Lt}中，是有可能使α>1；而在呈現(xiàn)凸型或者凹型的{Lt}中，平滑系數(shù)可能存在α<0.在這些情況下，指數(shù)平滑法就可能不再遵循“重近輕遠”的思想，根據(jù)式(5)就有必要考慮平滑初值S0.但同時從式(1)對負載的定義，顯然有0

(8)

式中t0為保留的負載時間序列的{Lt}長度.同時，求解最優(yōu)平滑系數(shù)αt的評價模型也修改為

(9)

在此改進模型下，由于在時刻t-t0之前的負載時間序列被丟棄，因此隨著負載時間序列{Lt}的增長，式(8，9)的次數(shù)也不會增長，維持在關于t0的常數(shù)次方，降低了算法的復雜度.另一方面，當負載時間序列{Lt}足夠長時，平滑初值S0的影響也會逐漸減小，直至被丟棄.因此平滑初值可選用靜態(tài)值，在這里定義為

(10)

接下來改進的動態(tài)平滑預測模型的關鍵就是選取合適的保留序列長度t0，使算法在預測精度與復雜度之間有一個合適的權衡.

圖1顯示了改進的動態(tài)指數(shù)平滑預測模型對負載的預測結果.實際負載值為某臺服務器每隔1min采集一次得到的真實結果.分別取t0=5和t0=10，其中，當t0=5時，預測從第6個負載值開始；同理，t0=10時，預測從第11個負載值開始.對圖1的分析看出：t0=5和t0=10時其預測結果與真實負載曲線都較為吻合.且當t0=10時，其預測的精度提升并不明顯，但是其算法復雜度要比t0=5時要高出許多.因此對動態(tài)負載預測模型而言，取負載時間序列保留長度t0=5較為合適.

圖1　動態(tài)指數(shù)平滑法對負載的預測結果Fig.1　The predictions of load through dynamic exponential smoothing method

圖2顯示了靜態(tài)平滑系數(shù)的預測模型對負載的預測結果，由于負載時間序列變化多樣，單一的平滑系數(shù)較難適應整個時間序列，因此預測精度并不高.從圖1，2的對比中不難看出：動態(tài)指數(shù)平滑法的預測結果要優(yōu)于靜態(tài)指數(shù)平滑法.

圖2　靜態(tài)指數(shù)平滑法對負載的預測結果Fig.2　The predictions of load through static exponential smoothing method

2負載均衡算法

2.1負載預測函數(shù)描述

設有服務器節(jié)點{Svi}，n為計算機集群的服務器個數(shù).當某個服務器啟動時，每隔一分鐘采集一次自己的負載信息，生成負載預測的初始時間序列{Lt0=5}Svi，并將此序列發(fā)送到分發(fā)器.分發(fā)器保存此初始時間序列{Lt0=5}Svi，由式(10)得到Svi的平滑初值SSvi.設預測值獲取函數(shù)為SSvi=ExpPrediction(LSvi)，函數(shù)ExpPrediction(LSvi)的工作過程如下：

1) 分發(fā)器找到服務器節(jié)點Svi的負載時間序列{Lt0=5}Svi，丟棄此時間序列中最早的負載值Learly，并將最新的負載值LSvi加入到時間序列{Lt0=5}Svi的末尾.

2) 根據(jù)前一時刻的平滑值SSvi、新的負載時間序列{Lt0=5}Svi和式(9)的動態(tài)平滑系數(shù)評價模型，利用最速下降法得到適應此負載序列的最優(yōu)平滑系數(shù)αt.

3) 將SSvi、負載時間序列{Lt0=5}Svi和動態(tài)平滑系數(shù)αt代入到式(8)的動態(tài)平滑預測模型，得到新的平滑值SSvi，替代掉原來的平滑值SSvi，而SSvi將作為服務器節(jié)點Svi下一時刻的預測值.

2.2負載均衡算法描述

分發(fā)器收到用戶服務的請求后，根據(jù)負載均衡算法將請求發(fā)送到負載最優(yōu)的服務器節(jié)點Svi處理，具體算法如下：

1) 分發(fā)器收到用戶的請求，在分發(fā)器已有的服務器節(jié)點列表中{Svn}選擇平滑值SSvi最小的服務器節(jié)點Svi.SSvi最小代表下一時刻節(jié)點Svi的負載最小.

2) 分發(fā)器將請求發(fā)送到服務器節(jié)點Svi處理.

3) 服務器節(jié)點Svi處理完請求后，在響應中攜帶自己當前時刻的負載數(shù)據(jù)，并將響應發(fā)回到分發(fā)器.

4) 分發(fā)器收到服務器節(jié)點Svi發(fā)回的響應，拿到Svi新時刻的負載LSvi，調(diào)用負載預測函數(shù)ExpPrediction(LSvi)得到下一時刻的負載預測值Svi，作為下一次分發(fā)器調(diào)度的依據(jù).

3網(wǎng)絡仿真結果與分析

為了檢驗算法的性能，用OPNET14.5進行了網(wǎng)絡仿真.OPNET是一款應用與網(wǎng)絡仿真軟件，它支持大量的網(wǎng)絡通信協(xié)議和模擬系統(tǒng)分發(fā)，通過對離散事件的仿真來分析系統(tǒng)的行為和性能[14].OPNET提供了三層建模機制，分別是進程層、節(jié)點層和網(wǎng)絡層.負載均衡算法是在分發(fā)器的進程層當中.

計算機集群中，服務器組由3臺Web服務器組成，其性能比為4︰7︰10，每臺服務器通過100 M線路連接分發(fā)器；客戶端組由6個子網(wǎng)組成客戶端，其中5個子網(wǎng)組是內(nèi)部子網(wǎng)，剩余一個是外部子網(wǎng)，每個子網(wǎng)都包含45個用戶終端.在搭建環(huán)境完成后，選擇仿真設置Application_Config中的HTTP應用，模擬客戶端向服務器發(fā)送HTTP請求，仿真時間是5 h.為了驗證筆者算法的性能，將筆者算法與動態(tài)均衡算法中的最小連接算法進行了對比，部分仿真結果如圖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使用率.不難發(fā)現(xiàn)圖3的CPU使用率穩(wěn)定在10%，17%，25%，而圖4的CPU使用率均穩(wěn)定在20%.結果表明：最小連接算法下，分發(fā)器并沒有按照服務器節(jié)點的負載能力分配任務，使得一些節(jié)點的CPU使用率過高，沒有很好地實現(xiàn)負載均衡.而基于筆者均衡算法的服務器節(jié)點資源都得到了較為均衡地利用，比較好地實現(xiàn)了負載均衡.

綜上所述，筆者的負載均衡算法與最少連接算法相比，均衡效果有了較為明顯的改善.

4結論

改進的負載預測均衡算法通過建立動態(tài)平滑指數(shù)的預測模型，以較短的負載時間序列提高了負載預測精度，使分發(fā)器能夠更準確地調(diào)度用戶服務的請求，提高了服務器節(jié)點的資源使用率.該算法在OPNET網(wǎng)絡仿真軟件下與最少連接算法進行了比較，結果顯示筆者算法具有更好的負載均衡效果.

參考文獻：

[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]魏欽磊.基于集群的動態(tài)反饋負載均衡算法的研究[D].重慶：重慶大學,2013.

[5]張前進,齊美彬,李莉.基于應用層負載均衡策略的分析與研究[J].計算機工程與應用,2007,43(32):138-142.

[6]孔令凡,呂麗民.基于B/S的網(wǎng)管負載平衡問題研究[J].浙江工業(yè)大學學報,2002,30(2):168-171.

[7]田紹亮,左明,吳紹偉.一種改進的基于動態(tài)反饋的負載均衡算法[J].計算機工程與設計,2007,28(3):572-573.

[8]孟利民,潘進學.視頻監(jiān)控系統(tǒng)中負載均衡算法的設計[J].浙江工業(yè)大學學報,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]周炳飛.動態(tài)指數(shù)平滑模型預測及應用[J].哈爾濱師范大學自然科學學報,2013(4):25-27.

[11]唐炎森.指數(shù)平滑預測公式與平滑系數(shù)[J].統(tǒng)計與信息論壇,1998(1):39-44.

[12]黎鎖平,劉坤會.動態(tài)指數(shù)平滑優(yōu)化模型及其應用[J].系統(tǒng)工程學報,2003,18(2):163-167.

[13]吳德會.動態(tài)指數(shù)平滑預測方法及其應用[J].系統(tǒng)管理學報,2008,17(2):151-155.

[14]張銘.OPNET Modeler與網(wǎng)絡仿真[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—)，女，浙江金華人，教授，研究方向為無線通信與網(wǎng)絡多媒體數(shù)字通信，E-mail:mlm@zjut.edu.cn．

中圖分類號：TP393

文獻標志碼：A

文章編號：1006-4303(2016)04-0379-04