(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

內(nèi)容分發(fā)網(wǎng)絡(luò)[1]的內(nèi)容路由技術(shù)一般由負(fù)載均衡系統(tǒng)來實(shí)現(xiàn)，是內(nèi)容分發(fā)網(wǎng)絡(luò)關(guān)鍵技術(shù)之一[2]。負(fù)載均衡的目的是運(yùn)用多評(píng)估機(jī)制選擇最佳節(jié)點(diǎn)并將用戶路由到節(jié)點(diǎn)內(nèi)合適的服務(wù)器上。內(nèi)容路由決定了就近服務(wù)的思想能否實(shí)現(xiàn)，決定了整個(gè)內(nèi)容分發(fā)網(wǎng)絡(luò)系統(tǒng)的運(yùn)行效率和性能，因此負(fù)載均衡是整個(gè)內(nèi)容分發(fā)網(wǎng)絡(luò)的基礎(chǔ)[4]。常用的負(fù)載平衡算法有靜態(tài)和動(dòng)態(tài)兩種。靜態(tài)負(fù)載中，代表算法是輪詢算法[5]和加權(quán)輪詢算法[6]。靜態(tài)負(fù)載平衡算法的優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是由于不考慮服務(wù)器節(jié)點(diǎn)的性能和當(dāng)前負(fù)載狀態(tài)，長時(shí)間運(yùn)行將導(dǎo)致負(fù)載不平衡。由于動(dòng)態(tài)負(fù)載均衡算法[5]無需先驗(yàn)知識(shí)進(jìn)行決策，可以根據(jù)實(shí)時(shí)服務(wù)器負(fù)載狀況，自適應(yīng)調(diào)整任務(wù)在各服務(wù)器中執(zhí)行順序，從而提高了系統(tǒng)整體性能，因此在系統(tǒng)中得到廣泛應(yīng)用。現(xiàn)有的動(dòng)態(tài)負(fù)載均衡算法主要有一致性哈希法[7]、最小連接算法(least connection, LC)[8]和加權(quán)最小連接算法(weighted least connection, WLC)[9]等。其中最小連接算法能動(dòng)態(tài)獲取服務(wù)器負(fù)載情況，但只關(guān)注連接數(shù)，沒有關(guān)注CPU和內(nèi)存使用率等問題，會(huì)出現(xiàn)連接數(shù)小但服務(wù)器資源消耗較高的情況[10-11]；文獻(xiàn)[12]提出一種異構(gòu)集群負(fù)載索引和負(fù)載均衡算法，但對(duì)服務(wù)器負(fù)載情況的衡量只以任務(wù)數(shù)量為參考；文獻(xiàn)[13]提出一種自適應(yīng)權(quán)值最小負(fù)載實(shí)現(xiàn)負(fù)載均衡的算法，但沒有考慮服務(wù)器所能承受的最大負(fù)載；文獻(xiàn)[14]提出一種基于可變因子α的加權(quán)最小鏈接算法，根據(jù)各服務(wù)器的負(fù)載情況，對(duì)α的值進(jìn)行調(diào)整并在一定程度上達(dá)到了負(fù)載均衡；文獻(xiàn)[15]提出一種將終端連接數(shù)作為影響因子和各服務(wù)器參數(shù)進(jìn)行綜合分析的算法，沒有考慮磁盤I/O且只應(yīng)用于特定的場(chǎng)景中。上述文獻(xiàn)對(duì)負(fù)載均衡算法都做了改進(jìn)，但都有其片面性。本研究對(duì)最小連接算法進(jìn)行改進(jìn)得到一種IWLC(improved weighted leastconnection)算法，提出了針對(duì)動(dòng)態(tài)權(quán)值的關(guān)鍵參數(shù)新的計(jì)算方法。IWLC算法通過動(dòng)態(tài)獲取服務(wù)器反饋性能指標(biāo)與負(fù)載指標(biāo)計(jì)算出當(dāng)前集群中最優(yōu)服務(wù)器進(jìn)行任務(wù)的調(diào)度分配，可更好達(dá)到負(fù)載均衡效果，更好地解決CDN系統(tǒng)中大規(guī)模用戶訪問請(qǐng)求下的負(fù)載均衡問題。

1 算法介紹

1.1 典型負(fù)載均衡算法

1.1.1 最小連接算法

最小連接算法思想是：假設(shè)系統(tǒng)內(nèi)各個(gè)服務(wù)器性能一致，當(dāng)有新的任務(wù)到來時(shí)，總是將該任務(wù)分配給連接數(shù)最少的服務(wù)器[4,7]，即對(duì)于現(xiàn)有服務(wù)器集群S={S1，S2，…，Sn}，每個(gè)服務(wù)器連接數(shù)為C(Si),1≤i

1.1.2 加權(quán)最小連接算法(IWLC)

加權(quán)最小連接算法算法[3]思想是在LC算法基礎(chǔ)上，考慮了不同服務(wù)器的性能差異，設(shè)置不同的權(quán)值來標(biāo)識(shí)服務(wù)器性能指標(biāo)，在任務(wù)調(diào)度時(shí)為權(quán)值較大的服務(wù)器分配較大比例的活動(dòng)連接[8,10]。IWLC算法充分考量服務(wù)器性能指標(biāo)及服務(wù)器動(dòng)態(tài)負(fù)載指標(biāo)，因此在負(fù)載均衡方面性能要優(yōu)于最小連接算法；然而，現(xiàn)有的IWLC算法對(duì)性能指標(biāo)的計(jì)算相對(duì)簡(jiǎn)單化，而系統(tǒng)實(shí)際運(yùn)行過程中性能指標(biāo)與負(fù)載指標(biāo)更加復(fù)雜，因此IWLC算法仍有優(yōu)化改進(jìn)的空間。

1.2 改進(jìn)加權(quán)最小連接算法(IWLC)

1.2.1 IWLC算法思路及流程

CDN應(yīng)用系統(tǒng)中，負(fù)載均衡服務(wù)器實(shí)時(shí)接收各服務(wù)器節(jié)點(diǎn)的負(fù)載情況及資源使用狀態(tài)，IWLC算法利用實(shí)時(shí)獲取的參數(shù)來計(jì)算各服務(wù)器節(jié)點(diǎn)的綜合性能指標(biāo)并以此作為任務(wù)調(diào)度的依據(jù)，選擇出最適合執(zhí)行任務(wù)的服務(wù)器，從而完成任務(wù)的動(dòng)態(tài)調(diào)度。

IWLC算法流程如下：

1) 集群中各真實(shí)服務(wù)器節(jié)點(diǎn)周期性計(jì)算各自的CPU空閑率、內(nèi)存空閑率、磁盤I/O空閑負(fù)荷、負(fù)載連接數(shù)，并反饋給負(fù)載均衡調(diào)度器；

2) 負(fù)載均衡調(diào)度器根據(jù)各服務(wù)器節(jié)點(diǎn)反饋的信息，計(jì)算服務(wù)器的綜合性能指標(biāo)P(Si)、綜合負(fù)載指標(biāo)C(Si)以及綜合評(píng)價(jià)指標(biāo)參數(shù)F(Si)，并計(jì)算出各個(gè)結(jié)點(diǎn)的權(quán)值wi；

3) 負(fù)載均衡調(diào)度器根據(jù)計(jì)算出的權(quán)值修改原先的權(quán)重，將更新后的權(quán)重寫入IPVS內(nèi)核；

4) Linux內(nèi)核啟用LVS編譯安裝IPVS內(nèi)核，IWLC算法根據(jù)新的權(quán)值選擇最合適的服務(wù)器進(jìn)行任務(wù)分配。

1.2.2 IWLC算法中關(guān)鍵參數(shù)計(jì)算

1) 集群S由n臺(tái)服務(wù)器組成，S={S1,S2,…,Sn}；

(1)

(2)

(3)

(4)

(5)

(6)

其中w1、w2、w3、w4分別代表各服務(wù)器性能指標(biāo)因素的權(quán)重?？紤]到CPU空閑率和內(nèi)存空閑率兩個(gè)指標(biāo)在描述服務(wù)器性能方面的重要性，因此對(duì)于4個(gè)權(quán)重的賦值分別是：w1=0.4、w2=0.4、w3=0.1、w4=0.1。若當(dāng)前的系數(shù)w1、w2、w3、w4不能很好反映應(yīng)用的負(fù)載，可以對(duì)系數(shù)進(jìn)行不斷的修改，直到找到一組貼近當(dāng)前應(yīng)用的系數(shù)。經(jīng)過多次試驗(yàn)，判定系數(shù)w1=0.4、w2=0.4、w3=0.1、w4=0.1是最優(yōu)的。

4) 為了更加有效預(yù)測(cè)每臺(tái)服務(wù)器節(jié)點(diǎn)所能承受的負(fù)載能力，引入服務(wù)器的綜合評(píng)價(jià)指標(biāo)參數(shù)F(Si)，其計(jì)算方法如下：

(7)

F(Si)的變化規(guī)則為：若要使F(Si)取值最小，其對(duì)應(yīng)的服務(wù)器Si要么滿足服務(wù)器性能指標(biāo)P(Si)最大，要么滿足服務(wù)器負(fù)載指標(biāo)C(Si)最小，或者同時(shí)滿足這兩個(gè)條件，此時(shí)Si便是集群中最合理的執(zhí)行新任務(wù)的服務(wù)器。

5) 設(shè)服務(wù)器的Si權(quán)重為wi，則令wi=1/F(Si)。F(Si)取值越小，服務(wù)器Si的動(dòng)態(tài)權(quán)重取值越大，負(fù)載指標(biāo)就越小，服務(wù)器Si的連接數(shù)就越小。

1.2.3 IWLC算法的代碼及分析

IWLC算法只做一次for循環(huán)，依次比較各服務(wù)器綜合指標(biāo)參數(shù)F(Si)，F(xiàn)(Si)取值大的被舍棄，繼續(xù)比較下一個(gè)，直到第n個(gè)服務(wù)器，選出F(Si)值最小的作為下一輪要執(zhí)行新任務(wù)的服務(wù)器，算法時(shí)間復(fù)雜度為O(n)，可見對(duì)參數(shù)的改進(jìn)并沒有造成更高的時(shí)間復(fù)雜度。

Algorithm:Improved Weighted Least ConnectionInput:CPU idle rate Ci,Memory idle rate Mi,I/O rate Di,Bandwidth Ni,Number of load connectionsLi Number of server n, Weight w1,w2,w3,w4Output:The most weighted serverSiInitialize an Array of n-dimensions arr with 0fori=1;i≤n;i++()do R(i)cpu=Ci/maxC1,C2,…,Cn() R(i)mem=Mi/maxM1,M2,…,Mn() R(i)disk=Di/maxD1,D2,…,Dn() R(i)net=Ni/maxN1,N2,…,Nn() R(i)con=LiL(i)max,CSi()=R(i)con PSi()=w1?R(i)cpu+w2?R(i)mem+w3?R(i)disk+w4?R(i)net FSi()=CSi()/PSi(),Wi=1/FSi() W=Wi arri[]=W Write the weightWi to the IPVS kernel and make install the IPVS kernelend doWmax=arri[]maxreturn the most weighted server Si

IWLC算法通過本研究提出的動(dòng)態(tài)權(quán)值計(jì)算方法得到服務(wù)器綜合評(píng)價(jià)指標(biāo)值，將新任務(wù)分配到F(Si)值最小的服務(wù)器Si上執(zhí)行，此時(shí)Si是當(dāng)前集群中最適合承擔(dān)負(fù)載的服務(wù)器。

2 實(shí)驗(yàn)與分析

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

實(shí)驗(yàn)?zāi)MCDN應(yīng)用系統(tǒng)中邊緣服務(wù)器節(jié)點(diǎn)應(yīng)對(duì)客戶訪問請(qǐng)求的負(fù)載均衡效果，本研究利用實(shí)驗(yàn)室現(xiàn)有設(shè)備，基于章文嵩博士[9]所提出的Linux虛擬服務(wù)器開源項(xiàng)目的集群體系結(jié)構(gòu)技術(shù)搭建了一套模擬CDN應(yīng)用系統(tǒng)邊緣服務(wù)器節(jié)點(diǎn)系統(tǒng)。

為驗(yàn)證提出的IWLC算法在解決CDN應(yīng)用系統(tǒng)中集群負(fù)載均衡問題方面的有效性，同時(shí)對(duì)比本算法與加權(quán)最小連接算法[5]在服務(wù)器響應(yīng)時(shí)間與吞吐量?jī)蓚€(gè)評(píng)價(jià)指標(biāo)上的實(shí)現(xiàn)效果，設(shè)計(jì)具體實(shí)驗(yàn)如下：

1) 在負(fù)載均衡服務(wù)器上通過IPVSADM管理軟件部署本研究提出的IWLC算法，而IPVSADM自身已經(jīng)配置了常用負(fù)載均衡算法，如加權(quán)輪詢算法加權(quán)最小連接算法等；

2) 在測(cè)試客戶機(jī)器上安裝部署LoadRunner系統(tǒng)負(fù)載測(cè)試工具，用來記錄模擬用戶訪問請(qǐng)求后臺(tái)服務(wù)器內(nèi)容過程中系統(tǒng)平均響應(yīng)時(shí)間與吞吐量；

3) 分10組模擬用戶訪問過程，請(qǐng)求任務(wù)數(shù)以每組遞增100的方式從100到1 000進(jìn)行實(shí)驗(yàn)，利用LoadRunner記錄系統(tǒng)平均響應(yīng)時(shí)間與吞吐量指標(biāo)，每組測(cè)三次，最終取平均值；

表1 10組平均響應(yīng)時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果表Tab.1 Experimental results of average response time

4)用MATLAB畫圖對(duì)比本研究所提IWLC算法與加權(quán)最小連接算法的系統(tǒng)平均響應(yīng)時(shí)間和系統(tǒng)吞吐量。

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

提出的IWLC算法與WLC算法的系統(tǒng)平均響應(yīng)時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果如表1和圖1所示?？梢钥闯觯寒?dāng)任務(wù)請(qǐng)求數(shù)低于300時(shí)，IWLC算法對(duì)應(yīng)的系統(tǒng)平均響應(yīng)時(shí)間要長于WLC算法，原因在于IWLC算法需要實(shí)時(shí)獲取各服務(wù)器傳送過來的性能指標(biāo)及負(fù)載指標(biāo)以計(jì)算各服務(wù)器的綜合性能指標(biāo)，引起額外的資源消耗，在任務(wù)請(qǐng)求數(shù)量較低的情況下造成了系統(tǒng)響應(yīng)時(shí)間延長；但是隨著系統(tǒng)用戶訪問請(qǐng)求任務(wù)數(shù)的增加，由于IWLC算法能夠充分利用系統(tǒng)資源，有效調(diào)度用戶任務(wù)請(qǐng)求，IWLC算法優(yōu)于WLC算法。

2) IWLC算法與WLC算法的系統(tǒng)吞吐量對(duì)比實(shí)驗(yàn)如圖 2所示。由圖可見：當(dāng)任務(wù)數(shù)小于500時(shí)，IWLC算法測(cè)試出的系統(tǒng)吞吐量小于加權(quán)最小連接算法；當(dāng)任務(wù)數(shù)為600～1 000時(shí)，IWLC算法測(cè)試出的系統(tǒng)吞吐量逐漸超過WLC算法測(cè)試出的系統(tǒng)吞吐量，大約提高了1 347 bytes/ms，隨著任務(wù)請(qǐng)求數(shù)的增多，IWLC算法對(duì)于合理使用各服務(wù)器更加有優(yōu)勢(shì)。

圖1 平均響應(yīng)時(shí)間實(shí)驗(yàn)結(jié)果對(duì)比圖Fig. 1 Comparison of Experimental Results of Average Response Time

圖2 系統(tǒng)吞吐量實(shí)驗(yàn)結(jié)果對(duì)比圖Fig. 2 Comparison of experimental results of throughput

綜上，IWLC算法有效提高了系統(tǒng)平均吞吐量，盡可能避免服務(wù)器過載，將任務(wù)分配到具有最佳性能的服務(wù)器，加強(qiáng)系統(tǒng)資源的有效利用。

3 結(jié)論

本研究從CDN應(yīng)用系統(tǒng)的本地負(fù)載均衡方面，針對(duì)邊緣服務(wù)器如何應(yīng)對(duì)大量用戶訪問請(qǐng)求而保障負(fù)載均衡的問題，基于加權(quán)最小連接算法，提出了一種改進(jìn)加權(quán)最小連接的CDN負(fù)載均衡算法。

相比于WLC算法，IWLC算法充分考慮了服務(wù)器自身資源使用情況以及負(fù)載情況等因素，通過動(dòng)態(tài)實(shí)時(shí)收集各服務(wù)器節(jié)點(diǎn)的資源性能指標(biāo)及負(fù)載指標(biāo)，綜合計(jì)算出當(dāng)前的最優(yōu)節(jié)點(diǎn)，完成訪問請(qǐng)求任務(wù)的分配，保證最大限度地利用系統(tǒng)資源，并對(duì)用戶的訪問請(qǐng)求更快地做出響應(yīng)。但I(xiàn)WLC算法也存在不足，如任務(wù)請(qǐng)求數(shù)較少時(shí)，負(fù)載均衡調(diào)節(jié)器定時(shí)發(fā)送請(qǐng)求報(bào)文獲取并處理真實(shí)服務(wù)器的各種信息帶來的額外開銷會(huì)影響整個(gè)系統(tǒng)的測(cè)試與評(píng)估。本工作沒有考慮到當(dāng)CPU空閑率、內(nèi)存空閑率、磁盤I/O空閑負(fù)荷、網(wǎng)絡(luò)帶寬四個(gè)參數(shù)都不大于90%的服務(wù)器時(shí)的算法情況，比較理想化，需要進(jìn)一步研究和細(xì)化算法來解決上述情況下的問題。