包曉安，魏雪，陳磊，胡國(guó)亨，張娜

（浙江理工大學(xué)，浙江 杭州310018）

研究與開發(fā)

基于mean-variance的服務(wù)集群負(fù)載均衡方法

包曉安，魏雪，陳磊，胡國(guó)亨，張娜

（浙江理工大學(xué)，浙江 杭州310018）

大量并發(fā)請(qǐng)求任務(wù)進(jìn)行分配時(shí)，負(fù)載調(diào)度機(jī)制是通過最小化響應(yīng)時(shí)間及最大化節(jié)點(diǎn)利用率實(shí)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡，在基于遺傳算法的負(fù)載均衡算法中，適應(yīng)度函數(shù)設(shè)計(jì)對(duì)服務(wù)集群負(fù)載均衡效率產(chǎn)生重要的影響。對(duì)此提出了一種基于mean-variance的服務(wù)集群負(fù)載均衡方法對(duì)適應(yīng)度函數(shù)進(jìn)行優(yōu)化，采用投資組合選擇模型mean-variance進(jìn)行最小化響應(yīng)時(shí)間，以得到每個(gè)服務(wù)器資源利用率的權(quán)重，從而獲得最優(yōu)的分配組合，進(jìn)而提高適應(yīng)度函數(shù)的準(zhǔn)確性和有效性。在不同服務(wù)環(huán)境下與其他模型進(jìn)行比較，仿真結(jié)果表明，本文的負(fù)載均衡算法在節(jié)點(diǎn)利用率和響應(yīng)時(shí)間方面使服務(wù)集群得到了更好的均衡。

負(fù)載均衡；mean-variance模型；遺傳算法；負(fù)載調(diào)度

1 引言

在服務(wù)器集群中，用戶的請(qǐng)求需要經(jīng)過負(fù)載均衡器將請(qǐng)求任務(wù)分配到后臺(tái)的服務(wù)器進(jìn)行處理。由于同一時(shí)間會(huì)有大量任務(wù)等待被分配，為了解決請(qǐng)求分配的流量擁塞及控制問題，負(fù)載均衡器在接收到來(lái)自內(nèi)部或外部的資源請(qǐng)求時(shí)，根據(jù)服務(wù)器集群的負(fù)載情況通過均衡調(diào)度算法進(jìn)行合理分配。負(fù)載均衡機(jī)制[1,2]的目的是能夠高效地為服務(wù)集群分配任務(wù)提供好的解決方案。服務(wù)集群在實(shí)現(xiàn)負(fù)載均衡這一領(lǐng)域，已經(jīng)取得了很多研究成果[3-5]，但是這些傳統(tǒng)的調(diào)度算法操作簡(jiǎn)單，不適于工作復(fù)雜的現(xiàn)實(shí)環(huán)境，并且點(diǎn)到點(diǎn)式的算法在搜索過程中往往會(huì)產(chǎn)生大量錯(cuò)誤的峰值點(diǎn)，從而影響最佳結(jié)果的判定。Zomaya和Teh[6]提出將遺傳算法（genetic algorithm，GA）用到負(fù)載均衡策略上并且得到廣泛應(yīng)用。GA的本質(zhì)是一種求解問題的高度并行性全局搜索算法，能在搜索過程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并控制搜索過程以求得最優(yōu)解。當(dāng)服務(wù)集群有大量任務(wù)等待處理時(shí)負(fù)載均衡器會(huì)通過GA進(jìn)行調(diào)度，其目標(biāo)函數(shù)是最小化執(zhí)行時(shí)間，充分利用節(jié)點(diǎn)的利用率并均衡網(wǎng)絡(luò)負(fù)載。但簡(jiǎn)單遺傳作為一種啟發(fā)式搜索算法，尋優(yōu)理論還不完善。有各種類型的負(fù)載均衡算法[7,8]，其中服務(wù)器的性能和已使用情況不同，則當(dāng)前的節(jié)點(diǎn)利用率也將不同。但是，更多的負(fù)載均衡算法忽略了各個(gè)服務(wù)器應(yīng)有的差異權(quán)重，針對(duì)節(jié)點(diǎn)利用率的計(jì)算是采用簡(jiǎn)單的求和，降低了適應(yīng)值的準(zhǔn)確性和有效性。

為了實(shí)現(xiàn)高效的基于遺傳算法的負(fù)載均衡，特別是降低頻繁訪問節(jié)點(diǎn)的響應(yīng)時(shí)間還需要進(jìn)行研究。適應(yīng)度函數(shù)是GA進(jìn)行最優(yōu)選擇的關(guān)鍵步驟。如果提高了其有效性將在一定的資源利用率基礎(chǔ)上節(jié)約響應(yīng)時(shí)間。mean-variance投資組合選擇理論[9]主要研究如何使金融資產(chǎn)進(jìn)行合理配置與選擇，使用證券收益方差度量風(fēng)險(xiǎn)，從而實(shí)現(xiàn)收益率最大化與風(fēng)險(xiǎn)最小化間的均衡，為投資者進(jìn)行決策提供了指導(dǎo)。繼而mean-variance投資組合選擇理論還被用于應(yīng)用層路由中，路由的多路徑權(quán)值采用 mean-variance模型，在求解約束條件下求解最優(yōu)化問題而獲得的。本文是基于GA對(duì)負(fù)載任務(wù)進(jìn)行合理分配，在一定的資源利用率情況下最小化響應(yīng)時(shí)間，mean-variance模型適合適應(yīng)度函數(shù)中二者的特殊關(guān)系。通過mean-variance模型改進(jìn)傳統(tǒng)適應(yīng)度函數(shù)，以一定水平的資源利用率盡量縮短用戶請(qǐng)求的等待時(shí)延，從而獲得最優(yōu)的分配組合，提高用戶體驗(yàn)。

2 負(fù)載均衡機(jī)制

2.1 量化負(fù)載

當(dāng)大量用戶訪問網(wǎng)絡(luò)時(shí)，不同服務(wù)所需的時(shí)間和所消耗的計(jì)算資源是千差萬(wàn)別的。其中請(qǐng)求服務(wù)的類型不同，當(dāng)前網(wǎng)絡(luò)帶寬或服務(wù)器資源利用的情況不同等都是影響因素。例如，負(fù)載比較輕的請(qǐng)求或許只需要讀一個(gè)HTML頁(yè)面進(jìn)行比較簡(jiǎn)單的計(jì)算，然而一些負(fù)載比較重的請(qǐng)求則需要計(jì)算密集的查詢、數(shù)據(jù)庫(kù)訪問及很長(zhǎng)的響應(yīng)數(shù)據(jù)流，所以需要對(duì)不同的請(qǐng)求任務(wù)進(jìn)行合理量化。根據(jù)服務(wù)器的日志文件進(jìn)行分析，然后將其中涉及的請(qǐng)求文檔進(jìn)行分類[10]，通過不同文檔類型在日志文件中所占的比重及不同的服務(wù)請(qǐng)求類型形成的不同負(fù)載值，對(duì)用戶的請(qǐng)求任務(wù)進(jìn)行負(fù)載值量化。

2.2 mean-variance模型

投資組合優(yōu)化問題作為現(xiàn)代金融學(xué)的一個(gè)核心課題[11]，主要研究如何對(duì)金融資產(chǎn)進(jìn)行合理配置與選擇，從而實(shí)現(xiàn)收益率最大化與風(fēng)險(xiǎn)最小化。

負(fù)載均衡策略的主要目標(biāo)是在最小化響應(yīng)時(shí)間的情況下最大化節(jié)點(diǎn)利用率。負(fù)載均衡問題符合馬克維茨模型的幾個(gè)條件：在一定的平均資源利用率基礎(chǔ)上，期望的均衡時(shí)間最少；在一定的均衡時(shí)間上，期望的資源利用率最大；每一次的適應(yīng)度函數(shù)的取值與前一次的資源利用率分布情況相關(guān)聯(lián)；負(fù)載均衡的時(shí)間與平均資源利用率息息相關(guān)。因此，針對(duì)m個(gè)服務(wù)器的節(jié)點(diǎn)利用率及響應(yīng)時(shí)間問題，本文采用mean-variance模型[10,11]在約束條件下進(jìn)行設(shè)計(jì)，通過方差度量負(fù)載調(diào)度的響應(yīng)時(shí)間，在最小化響應(yīng)時(shí)間的狀態(tài)下得到期望利用率，從而增加了適應(yīng)度值計(jì)算的有效性，更好地實(shí)現(xiàn)服務(wù)集群的負(fù)載均衡。

2.3 自適應(yīng)閾值函數(shù)設(shè)計(jì)

自適應(yīng)的閾值策略中的閾值[12,13]表示處理器是重負(fù)載或輕負(fù)載。每一個(gè)處理器在達(dá)到或完成任務(wù)時(shí)會(huì)直接向中央調(diào)度程序報(bào)告，然后根據(jù)目前的系統(tǒng)負(fù)載和新調(diào)度任務(wù)的負(fù)載得到單個(gè)服務(wù)器的負(fù)載均值。系統(tǒng)設(shè)置了重閾值（Lmax）和輕閾值（Lmin）來(lái)判斷服務(wù)器當(dāng)前所處的負(fù)載環(huán)境，基于平均負(fù)載值可導(dǎo)出：

其中，CSL（current system load）定義為目前的節(jié)點(diǎn)負(fù)載量，表示負(fù)載均衡器中遺傳調(diào)度算法未給服務(wù)器集群分配任務(wù)，服務(wù)集群依舊在執(zhí)行前一次調(diào)度算法分配的任務(wù)量。

NTL（new tasks load）定義為即將分配的負(fù)載量，表示遺傳調(diào)度算法通過迭代操作已經(jīng)選擇出最優(yōu)分配組合，即將分配給服務(wù)集群的任務(wù)量。

Lave是根據(jù)目前的節(jié)點(diǎn)負(fù)載量（CSL）和即將分配的負(fù)載量（NTL）之和與總服務(wù)節(jié)點(diǎn)量N的比值求得。而R和D給負(fù)載平衡機(jī)制添加了靈活性和有效性，R是比1大的值，表明處理器的負(fù)載量大于平均負(fù)載值小于重閾值；同時(shí)D是比1小的值，表明處理器的負(fù)載量小于平均負(fù)載值，大于輕閾值。超負(fù)載的服務(wù)器將不再分配任務(wù)，否則會(huì)出現(xiàn)負(fù)載過重或過輕的不均衡問題。其中，R和D的值根據(jù)任務(wù)的數(shù)量及服務(wù)器的性能進(jìn)行設(shè)置。自適應(yīng)閾值策略可以靈活地調(diào)動(dòng)整個(gè)負(fù)載系統(tǒng)，是負(fù)載均衡系統(tǒng)的重要保障。

3 負(fù)載均衡優(yōu)化

根據(jù)當(dāng)前時(shí)刻t的系統(tǒng)狀態(tài)采集各服務(wù)節(jié)點(diǎn)的信息，當(dāng)有空閑出現(xiàn)時(shí)需要負(fù)載均衡器調(diào)用均衡算法進(jìn)行新一輪的任務(wù)分配。由于本文負(fù)載均衡調(diào)度是結(jié)合GA解最優(yōu)化問題，采用生存的優(yōu)勝劣汰技術(shù)交換信息進(jìn)行個(gè)體創(chuàng)新。其中遺傳方法需要根據(jù)歷史信息及預(yù)期對(duì)新搜索點(diǎn)進(jìn)行改善。這里的負(fù)載策略主要包括參數(shù)編碼和適應(yīng)度設(shè)計(jì)。

3.1 編碼

在編碼機(jī)制中，參數(shù)的編碼方式有多種[14]，其中二進(jìn)制編碼因?yàn)楹?jiǎn)單易行且處理模式數(shù)最多成為最常用的編碼方法，但是編碼串太長(zhǎng)使得空間搜索量變大且將一直占用內(nèi)存，導(dǎo)致計(jì)算機(jī)資源的使用率較底，因此提出采用三維十進(jìn)制對(duì)空間的候選解進(jìn)行參數(shù)編碼。其中每個(gè)組成數(shù)組的字符串具有固定大小，在搜索空間中的每個(gè)節(jié)點(diǎn)都有字符串代表，而且其代表的字符串是唯一的，從而三維十進(jìn)制編碼也將提高遺傳操作的準(zhǔn)確性。

在三維十進(jìn)制編碼中，每個(gè)解被編碼為一個(gè)由3個(gè)屬性表示的十進(jìn)制數(shù)組，記作＜Tα,Tβ,Pi＞，這里的Tα、Tβ分別表示任務(wù)的編號(hào)和任務(wù)的負(fù)載量，而Pi表示此任務(wù)被分配的服務(wù)器i，其中i=1,2,…,m。表1是將10個(gè)并發(fā)任務(wù)分配給4個(gè)服務(wù)器，其中第一組表示服務(wù)器1上的任務(wù)3的負(fù)載量為7，第二組表示服務(wù)器4上的任務(wù)5的負(fù)載量為3等。

表1 任務(wù)編碼

采用隨機(jī)函數(shù)產(chǎn)生Q個(gè)初始結(jié)構(gòu)數(shù)據(jù)，每個(gè)結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)字符串，也稱為一個(gè)個(gè)體，因此Q個(gè)字符串構(gòu)成了一個(gè)群體。在GA中將隨機(jī)產(chǎn)生的適量初始串結(jié)構(gòu)數(shù)據(jù)作為初始種群。

3.2 適應(yīng)度函數(shù)構(gòu)建

負(fù)載策略目的是使分配給服務(wù)集群的負(fù)載更均衡，而在GA中適應(yīng)度函數(shù)是評(píng)價(jià)字符串性能的唯一標(biāo)準(zhǔn)，所以有效地構(gòu)建適應(yīng)度函數(shù)就變得極其重要。將適應(yīng)度函數(shù)分為3部分，包括資源利用率、響應(yīng)時(shí)間和可接受分配服務(wù)器的概率。

3.2.1 負(fù)載指數(shù)

通過服務(wù)器運(yùn)行時(shí)各方面的參數(shù)得到負(fù)載指數(shù)，主要包括CPU使用量、內(nèi)存和帶寬利用率。變量中CPU、內(nèi)存及帶寬的利用情況可以通過負(fù)載平衡器監(jiān)測(cè)到。

其中，每個(gè)服務(wù)器的內(nèi)存利用率定義為：

其中，Vdi為服務(wù)器的已用內(nèi)存，Pdi為服務(wù)器i的總內(nèi)存。CPU、帶寬利用率的定義與內(nèi)存利用率具有相似形式，分別為：

其中，Vci、Vbi分別為服務(wù)器已被占用的CPU和帶寬，Pci、Pbi則是服務(wù)器的總資源。

對(duì)于負(fù)載指數(shù)的衡量，在不同類型的系統(tǒng)應(yīng)用中，各個(gè)參數(shù)的重要程度也有所不同。在典型的Web應(yīng)用環(huán)境下，可使用的內(nèi)存資源和響應(yīng)時(shí)間就非常重要，如果用戶以長(zhǎng)的數(shù)據(jù)庫(kù)事務(wù)為主[15-17]，則CPU使用率和可用內(nèi)存就相對(duì)重要一些。因而在資源利用率的問題上不可將以上因素同等看待，為了方便在系統(tǒng)運(yùn)行過程中針對(duì)不同的應(yīng)用對(duì)各個(gè)參數(shù)的比例進(jìn)行適當(dāng)調(diào)整，為每一個(gè)參數(shù)設(shè)定一個(gè)常量系數(shù)ki(i=1,2,3)，用來(lái)表示各個(gè)負(fù)載參數(shù)的權(quán)值。所以服務(wù)器的資源利用率表示如下：

其中，k1、k2、k3為常數(shù)，且k1+k2+k3=1。常量系數(shù)根據(jù)系統(tǒng)的應(yīng)用環(huán)境進(jìn)行設(shè)置。

3.2.2 資源利用率和響應(yīng)時(shí)間分析

由于不同的服務(wù)器的性能和使用的情況不同，引入了mean-variance模型計(jì)算服務(wù)集群的資源利用率及響應(yīng)時(shí)間[7]。假設(shè)對(duì)m個(gè)服務(wù)器進(jìn)行資源利用率的配置，對(duì)應(yīng)的資源利用率為隨機(jī)變量Rui（Ru1,Ru2,…,Rum），則系統(tǒng)中總的節(jié)點(diǎn)利用率為：

其中，wi(i=1,2,…,m)代表 m個(gè)服務(wù)器資源利用率的比例，即權(quán)重因子。系統(tǒng)中總的期望 up和響應(yīng)時(shí)間Makespan為：

其中，ui是服務(wù)器i資源利用率的期望，而cov(Rui,Ruj)表示任意兩個(gè)服務(wù)器資源使用情況的協(xié)方差，協(xié)方差也可表示為σi,j。mean-variance模型通過求解約束優(yōu)化問題來(lái)獲得最優(yōu)的權(quán)重向量：

根據(jù)期望及權(quán)重因子可以得到目標(biāo)函數(shù)的兩個(gè)約束條件：

在限制條件下求解Rui資源利用率組合時(shí)的最小負(fù)載執(zhí)行時(shí)間，關(guān)于最值問題，可通過拉格朗日目標(biāo)函數(shù)求得。構(gòu)建拉格朗日式如下：

其中，λ1和λ2是拉格朗日乘數(shù)，通過計(jì)算L相對(duì)于wi和拉格朗日乘子的導(dǎo)數(shù)為0的等式來(lái)獲得最優(yōu)的權(quán)重向量。分別對(duì)wi、λ1、λ2求偏導(dǎo)：

通過求偏導(dǎo)數(shù)得到權(quán)值因子wi，從而在式（8）和式（10）中可得到目標(biāo)函數(shù)的總資源利用率和響應(yīng)時(shí)間。

3.2.3 可接受分配的服務(wù)器

雖然服務(wù)器的資源利用率得到提高，執(zhí)行時(shí)間縮短但仍舊可能出現(xiàn)部分服務(wù)器超載運(yùn)行的狀況，所以負(fù)載均衡的下一個(gè)目標(biāo)是提高可接受分配服務(wù)器 （number of acceptable distribution server，ADS）的概率。

自適應(yīng)閾值策略得到重閾值（Lmax）和輕閾值（Lmin），每個(gè)服務(wù)器目前的負(fù)載與將要分配的負(fù)載之和不能超過重閾值或低于輕閾值：

可接受分配的服務(wù)器表示服務(wù)器目前的負(fù)載值符合以上條件，即式（18），且允許被調(diào)度算法再次分配任務(wù)。但是，服務(wù)器的負(fù)載值超過Lmax或低于Lmin則此服務(wù)器是不正常運(yùn)作，也將被定義為不可接受分配任務(wù)的服務(wù)器。在整個(gè)字符串中可接受分配任務(wù)的服務(wù)器的數(shù)量越多，表示調(diào)度任務(wù)的分配更均衡。

3.2.4 組合適應(yīng)度函數(shù)設(shè)計(jì)

通過3個(gè)目標(biāo)函數(shù)的計(jì)算可得到組合適應(yīng)度函數(shù)為：

這里的適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)負(fù)載調(diào)度任務(wù)的質(zhì)量。其中，式（14）構(gòu)建的拉格朗日式可以得到權(quán)值因子wi，從而通過式（8）和式（10）中可得到目標(biāo)函數(shù)的總資源利用率Rp和響應(yīng)時(shí)間Makespan。當(dāng)響應(yīng)時(shí)間縮短，資源利用率提高，且可接受分配服務(wù)器ADS的概率也較高時(shí)，適應(yīng)度值就會(huì)增大，這就表示負(fù)載均衡策略越好。

服務(wù)集群按照組合適應(yīng)度函數(shù)進(jìn)行評(píng)估操作，從而實(shí)現(xiàn)分配組合的優(yōu)勝劣汰。以下算法利用mean-variance模型計(jì)算分配組合的適應(yīng)度函數(shù)值，通過遺傳操作并行搜索得到最優(yōu)解。首先，按輪盤賭選擇方法對(duì)適應(yīng)性強(qiáng)的字符串進(jìn)行選擇復(fù)制，對(duì)選擇的優(yōu)秀字符串進(jìn)行交叉、變異運(yùn)算；再次，在完成變異操作后，字符串將產(chǎn)生新的適應(yīng)度值，所以需要被重新評(píng)估，然后產(chǎn)生新的幸存概率，這些值將被用來(lái)定義下一輪循環(huán)中輪盤的插槽值；最后，在需要判斷是否達(dá)到K次循環(huán)后，再?zèng)Q定是否將得到的最優(yōu)字符串解碼并用于任務(wù)分配或繼續(xù)迭代。對(duì)于新系統(tǒng)狀態(tài)t+1時(shí)刻，檢查是否有空閑處理器出現(xiàn)，若有空閑，將啟動(dòng)負(fù)載均衡進(jìn)行新任務(wù)的分配。

算法 負(fù)載均衡的最優(yōu)解設(shè)計(jì)

Load balance algorithm{

RequestQ in sliding-window//請(qǐng)求隊(duì)列

ServerList//服務(wù)節(jié)點(diǎn)負(fù)載信息

Do{

Requesti=RequestQ.Out_Q//請(qǐng)求出隊(duì)

Shedule IGA//通過遺傳算法分配請(qǐng)求

Initialize newPop//初始化種群

Evaluate fitness of P(t)based mean-variance//“適者生存”遺傳判斷

While(not Terminate-Condition)//不滿足終止條件時(shí)，循環(huán)

{

Select operation for P(t)//選擇操作

Crossover operation for P(t)//交叉操作

Mutation operation based Polynomial Mutation for P(t)//變異操作

P(t+1)=P(t) //得到下一代群體P（t+1）,循環(huán)

GA-operation//遺傳操作

Evaluate fitness of P(t)//適應(yīng)度判斷

}

End While

Output(Requesti)

}}

4 仿真實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

針對(duì)適應(yīng)度函數(shù)中響應(yīng)時(shí)間和資源利用率的有效性計(jì)算問題，引入投資組合選擇模型mean-variance來(lái)計(jì)算服務(wù)集群中節(jié)點(diǎn)利用率的權(quán)重，優(yōu)化遺傳算法中的適應(yīng)度函數(shù)，以獲得最優(yōu)的分配組合。

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文的優(yōu)化算法增加了適應(yīng)度函數(shù)的有效性，以提高服務(wù)集群的負(fù)載均衡表現(xiàn)。本文使用OPNET14.5仿真平臺(tái)進(jìn)行測(cè)試，其中服務(wù)集群的負(fù)載均衡策略遵循三層建模規(guī)則，包括網(wǎng)絡(luò)模型、節(jié)點(diǎn)模型和進(jìn)程處理模型。服務(wù)集群采用集中式負(fù)載均衡網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，100 Mbit/s帶寬的局域網(wǎng)架構(gòu)，集群的3個(gè)處理器分別為6MIPS、3MIPS、1MIPS。客戶端為4個(gè)以太子網(wǎng)，每個(gè)子網(wǎng)包括20個(gè)用戶，子網(wǎng)彼此通過64口以太網(wǎng)交換機(jī)連接，負(fù)載均衡單元與客戶端在10 Mbit/s線路上交流，而16口的Hub為服務(wù)集群與負(fù)載均衡單元的交流服務(wù)。

節(jié)點(diǎn)模型中負(fù)載均衡器的設(shè)計(jì)遵循OSI建模規(guī)則[18]，在IP處理層采用NET實(shí)現(xiàn)基于 mean-variance的負(fù)載均衡算法。該工作的實(shí)現(xiàn)在進(jìn)程模型中，首先，初始化負(fù)載均衡單元；然后，對(duì)獲得的數(shù)據(jù)分組進(jìn)行源、目的地址分析并根據(jù)其端口號(hào)進(jìn)行分類，根據(jù)用戶請(qǐng)求任務(wù)調(diào)用負(fù)載均衡算法分配給對(duì)應(yīng)的服務(wù)器；最后，把響應(yīng)的數(shù)據(jù)分組進(jìn)行NET地址轉(zhuǎn)換再反饋給客戶端。

完成網(wǎng)絡(luò)、節(jié)點(diǎn)及進(jìn)程建模后，通過圖1的負(fù)載均衡系統(tǒng)實(shí)現(xiàn)本文算法的性能表現(xiàn)，其中設(shè)計(jì)的負(fù)載均衡模型包含負(fù)載均衡調(diào)度模塊 （基于mean-variance的負(fù)載均衡算法、FCFS（first come first served）算法[4]、DGA（dynamic genetic load balancing）算法[3]）、數(shù)據(jù)分組分析模塊、負(fù)載信息采集模塊、請(qǐng)求轉(zhuǎn)發(fā)模塊及服務(wù)集群模塊。當(dāng)客戶端傳入數(shù)據(jù)分組后，根據(jù)網(wǎng)絡(luò)協(xié)議的端口判斷請(qǐng)求任務(wù)的類型[9]，將請(qǐng)求數(shù)據(jù)分組傳遞給負(fù)載均衡調(diào)度模塊。在 mean-variance模型的基礎(chǔ)上通過 GA并行搜索得到最優(yōu)分配組合 （其中負(fù)載采集模塊需要描述服務(wù)節(jié)點(diǎn)的CPU使用量），內(nèi)存和帶寬利用率等采集間隔時(shí)間設(shè)置為 10 s。改寫用戶的請(qǐng)求數(shù)據(jù)分組的目的地址為對(duì)應(yīng)服務(wù)器的內(nèi)部 IP地址，再將數(shù)據(jù)分組發(fā)送至服務(wù)集群中。

4.2 實(shí)驗(yàn)結(jié)果與分析

對(duì)于算法效果的驗(yàn)證，將本文提出的方法與FCFS及DGA進(jìn)行比較。實(shí)驗(yàn)運(yùn)行基于表2的默認(rèn)參數(shù)。

根據(jù)以上的參數(shù)設(shè)置，算法會(huì)有不同的性能表現(xiàn)。在負(fù)載均衡機(jī)制中迭代次數(shù)和并發(fā)請(qǐng)求量是影響節(jié)點(diǎn)利用率和響應(yīng)時(shí)間兩個(gè)目標(biāo)函數(shù)的關(guān)鍵因素，但隨機(jī)分配中部分參數(shù)只與GA相關(guān)。例如，迭代次數(shù)的變化在節(jié)點(diǎn)利用率和響應(yīng)時(shí)間方面對(duì)FCFS算法沒有影響。所以進(jìn)行實(shí)驗(yàn)時(shí)，在GA算法中改變迭代次數(shù)來(lái)觀察參數(shù)對(duì)算法性能的影響。

圖1 負(fù)載均衡系統(tǒng)模型設(shè)計(jì)

表2 實(shí)驗(yàn)參數(shù)

在圖2和圖3中可以看出迭代次數(shù)從5次增加到60次時(shí)，兩種算法的響應(yīng)時(shí)間的增幅逐漸減少，而節(jié)點(diǎn)利用率為增加的趨勢(shì)，最后趨于平緩。并且本文的負(fù)載均衡方法在響應(yīng)時(shí)間和節(jié)點(diǎn)利用率方面都優(yōu)于DGA算法。已知適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)負(fù)載調(diào)度的質(zhì)量，圖4的結(jié)果中，當(dāng)?shù)螖?shù)增加時(shí)本文算法的適應(yīng)度值逐漸增加，達(dá)到35次時(shí)目標(biāo)值最大。結(jié)合圖2、圖3觀察，隨著迭代的繼續(xù)進(jìn)行使得資源利用率有所提高，但在響應(yīng)時(shí)間上卻出現(xiàn)增幅較大的現(xiàn)象。因此對(duì)GA進(jìn)行過多的迭代是多余的并且會(huì)增加響應(yīng)時(shí)間，違背了負(fù)載調(diào)度的最初目的。所以將迭代次數(shù)設(shè)置為35次會(huì)使得本文算法得到最優(yōu)適應(yīng)度，并且本文的算法相對(duì)于DGA算法的適應(yīng)度值較高，這也表明了本文算法的優(yōu)越性。所示，任務(wù)數(shù)量從250個(gè)到3 000個(gè)進(jìn)行間隔250個(gè)的線性增加，3個(gè)算法總響應(yīng)時(shí)間也逐漸增加。在請(qǐng)求任務(wù)較少時(shí)，本文算法因引入拉格朗日乘數(shù)兩個(gè)約束條件求最優(yōu)權(quán)重因子，并對(duì)3個(gè)參數(shù)求偏導(dǎo)數(shù)導(dǎo)致響應(yīng)時(shí)間較長(zhǎng)。但隨機(jī)分配的任務(wù)數(shù)量大于1 250左右時(shí)，本文算法相對(duì)于DGA和FSFC算法的利用率產(chǎn)生一定差距。實(shí)驗(yàn)表明，通過增加的mean-variance模型對(duì)節(jié)點(diǎn)利用率權(quán)重的精確計(jì)算，使得適應(yīng)度函數(shù)的準(zhǔn)確性得到改善，從而節(jié)省了遺傳算法通過優(yōu)勝劣汰選擇最優(yōu)分配組合的時(shí)間，使得負(fù)載均衡算法分配任務(wù)到服務(wù)集群的響應(yīng)時(shí)間最小化。

圖2 Makespan:改變迭代次數(shù)

圖3 平均節(jié)點(diǎn)利用率:改變迭代次數(shù)

圖4 適應(yīng)度值：改變迭代次數(shù)

除了迭代次數(shù)外，并發(fā)請(qǐng)求量也是均衡算法的另一個(gè)關(guān)鍵因素，當(dāng)任務(wù)量增加時(shí)3種算法在響應(yīng)時(shí)間和節(jié)點(diǎn)利用率上的負(fù)載均衡表現(xiàn)如圖5、圖6所示。

本實(shí)驗(yàn)中除了任務(wù)數(shù)量外其他參數(shù)均為默認(rèn)值，如圖5

圖5 Makespan:改變?nèi)蝿?wù)數(shù)量

圖6 平均節(jié)點(diǎn)利用率：改變?nèi)蝿?wù)數(shù)量

如圖6所示，隨著任務(wù)的增加本文算法的服務(wù)集群節(jié)點(diǎn)利用率逐漸從90.5%增長(zhǎng)到96.8%，與DGA相比較增加了 0.9%。表明在不同負(fù)載比重的任務(wù)類型中，采用mean-variance模型有效地計(jì)算適應(yīng)度函數(shù)，然后通過拉格朗日乘數(shù)求得約束條件下節(jié)點(diǎn)利用率的權(quán)重因子，此方法是值得肯定的。本文提出的算法使得每個(gè)服務(wù)器資源利用率的權(quán)重因子得到更精確的評(píng)估和預(yù)測(cè)，從而提高了并發(fā)任務(wù)分配的效率。

5 結(jié)束語(yǔ)

有效的任務(wù)分配中負(fù)載均衡策略至關(guān)重要，大部分研究都集中關(guān)注這一問題并提出了一系列的解決方案。本文通過對(duì)服務(wù)集群均衡方法的研究，發(fā)現(xiàn)結(jié)合投資組合選擇理論中的mean-variance模型來(lái)設(shè)置服務(wù)集群中節(jié)點(diǎn)利用率的權(quán)重，以最小化任務(wù)完成時(shí)間為條件來(lái)獲得最優(yōu)的權(quán)值向量，為每個(gè)服務(wù)器的資源利用率分配權(quán)值從而得到更有效的組合適應(yīng)度函數(shù)。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在縮短響應(yīng)時(shí)間，提高節(jié)點(diǎn)利用率及負(fù)載均衡分配方面有很好的表現(xiàn)。但隨著應(yīng)用服務(wù)的逐漸升級(jí)，在大規(guī)模的應(yīng)用場(chǎng)景中用戶還需要一定的QoS保障[19]。為此，本文將在現(xiàn)有的基礎(chǔ)上，進(jìn)一步結(jié)合用戶QoS保障機(jī)制進(jìn)行深入研究。

[1]李文中,郭勝,許平,等.服務(wù)組合中一種自適應(yīng)的負(fù)載均衡算法[J].軟件學(xué)報(bào),2006,17(5):1068-1077. LI W Z,GUO S,XU P,et al.An adaptive load balancing algorithm for service composition[J].Journal of Software,2006, 17(5):1068-1077.

[2]DONG B,LI X,WU Q,et al.A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/Oservers[J].Journal of Parallel&Distributed Computing,2012, 72(10):1254-1268.

[3]RAMAKRISHNA M,KODATI V,GRATZ P,et al.GCA:global congestion awareness for load balance in networks-on-chip[J]. IEEE Transactions on Parallel&Distributed Systems,2016: 1-8.

[4]ZHANG Y,LIAO X,JIN H,et al.Inc-part:incremental partitioning for load balancing in large-scale behavioral simulations[J].IEEE Transactions on Parallel&Distributed Systems,2015,26(7):1900-1909.

[5]CHANDAKANNA V R,VATSAVAYIV K.A sliding window based self-learning and adaptive load balancer[J]. Journal of Network&Computer Applications,2015,56(C): 188-205.

[6]LI Y,YANG Y,MA M,et al.A hybrid load balancing strategy of sequential tasks for grid computing environments[J].Future Generation Computer Systems,2009,25(8):819-828.

[7]KORKHOV V V,MOSCICKI J T,KRZHIZHANOVSKAYA V V. Dynamic workload balancing ofparallelapplications with user-levelscheduling on the Grid [J].Future Generation Computer Systems,2009,25(1):28-34.

[8]BALASANGAMESHWARA J,RAJU N.A hybrid policy for fault tolerant load balancing in grid computing environments[J]. Journal of Network&Computer Applications,2012,35(1): 412-422.

[9]吳偉平,高建軍,李端.多階段均值-方差資產(chǎn)負(fù)債管理的隨機(jī)控制[J].控制理論與應(yīng)用,2015,32(9):1200-1207. WU W P,GAO J J,LI D.Stochastic control for multiperiod mean-variance asset-liability management[J].Control Theory& Applications,2015,32(9):1200-1207.

[10]FOSTERI,KESSELMAN C,TUECKES.The anatomy of the grid:enabling scalable virtual organizations[J].The International Journal Performance Computing Applications,2001,15(3): 200-222.

[11]WU Z W,SONG X F,XU Y Y,et al.A note on a minimax rule for portfolio selection and equilibrium price system[J]. Applied Mathematics&Computation,2009,208(1):49-57.

[12]韓東升,丁莎莎,余萍.一種基于閾值的無(wú)線異構(gòu)網(wǎng)絡(luò)基站分簇方法[J].電信科學(xué),2015,31(4):18-21. HAN D S,DING S S,YU P.A clustering method based on the thresholdinwireless heterogeneous network[J].Telecommunications Science,2015,31(4):18-21.

[13]MOHAMED N,AL-JAROODI J,EID A.A dual-direction technique for fast file downloads with dynamic load balancing in the cloud[J].Journal of Network&Computer Applications, 2013,36(4):1116-1130.

[14]鄧亮,趙進(jìn),王新.基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化[J].軟件學(xué)報(bào),2009,20(8):2269-2279. DENG L,ZHAO J,WANG X.Genetic algorithm solution of network coding optimization[J].Journal of Software,2009,20(8): 2269-2279.

[15]蘇金樹,郭文忠,余朝龍,等.負(fù)載均衡感知的無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法 [J].計(jì)算機(jī)學(xué)報(bào),2014,37(2): 445-456. SU J S,GUO W Z,YU C L,et al.Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers,2014,37(2):445-456.

[16]ANGRISANIL,CAPRIGLIONED,FERRIGNO L,etal. Locality-sensitive task allocation and load balancing in networked multiagent systems:talent versus centrality[J].Journal of Parallel&Distributed Computing,2011,71(6):822-836.

[17]DONG B,LI XQ,WU QM,et al.A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers[J].Journal of Parallel and Distributed Computing,2012, 72(10):1254-1268.

[18]CHENG D,RAO J,GUO Y,et al.Improving performance of heterogeneous mapreduce clusters with adaptive task tuning[J]. IEEE Transactions on Parallel&Distributed Systems,2016:1.

[19]郭濤,李有明,雷鵬,等.MIMO中繼系統(tǒng)中一種基于用戶QoS的資源分配方法[J].電信科學(xué),2015,31(4):115-120. GUO T,LI Y M,LEI P,et al.A resource allocation scheme based on user’s QoS in MIMO relay system[J].Telecommunications Science,2015,31(4):115-120.

Load balancing method of service cluster based on mean-variance

BAO Xiaoan,WEI Xue,CHEN Lei,HU Guoheng,ZHANG Na
Zhejiang Sci-Tech University,Hangzhou 310018,China

When a large number of concurrent requests are allocated,the load scheduling mechanism is to achieve the load balancing of nodes in the network by minimizing the response time and maximizing the utilization ratio of nodes.In the load balancing algorithm based on genetic algorithm,the fitness function is designed to have an important influence on the load balancing efficiency.A service cluster load balancing method based on mean-variance was proposed to optimize the fitness function.The investment portfolio selection model mean-variance was used to minimize the response time,which was used to get the weight of each server’s resource utilization,so as to obtain the optimal allocation combination.This method improves the accuracy and efficiency of the fitness function.Compared with other models in different service environment,the simulation results show that the load balancing algorithm makes the service cluster get a better balance performance in terms of node utilization and response time.

load balancing,mean-variance model,genetic algorithm,load scheduling

TP393

A

10.11959/j.issn.1000-0801.2017027

包曉安（1973-），男，浙江理工大學(xué)教授，主要研究方向?yàn)檐浖こ碳败浖y(cè)試、智能信息處理。

魏雪（1990-），女，浙江理工大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)關(guān)負(fù)載調(diào)度和智能優(yōu)化算法。

陳磊（1992-），男，浙江理工大學(xué)碩士生，主要研究方向?yàn)橹悄苄畔⑻幚砑扒度胧皆O(shè)備視頻采集。

胡國(guó)亨（1992-），男，浙江理工大學(xué)碩士生，主要研究方向?yàn)橹悄苄畔⑻幚砑拔锫?lián)網(wǎng)協(xié)議。

張娜（1977-），女，浙江理工大學(xué)副教授，主要研究方向?yàn)檐浖こ碳败浖阅芊治?、軟件測(cè)試技術(shù)。

2016-11-12；

2017-01-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379036，No.61502430）；國(guó)家自然科學(xué)基金委中丹合作項(xiàng)目（No.61361136002）；浙江省重大科技專項(xiàng)重點(diǎn)工業(yè)項(xiàng)目（No.2014C01047）；浙江理工大學(xué)“521人才培養(yǎng)計(jì)劃”基金資助項(xiàng)目

Foundation Items:The National Natural Science Foundation of China(No.61379036,No.61502430),China-Denmark Cooperation Program of the National Natural Science Foundation of China(No.61361136002),Major Science and Technology Projects of Zhejiang Province(No.2014C01047), 521 Talent Project of Zhejiang Sci-Tech University