曾友雯，李雙慶，鄒東升

(重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044)

隨著云計(jì)算的興起，云數(shù)據(jù)中心往往通過(guò)負(fù)載均衡手段協(xié)調(diào)服務(wù)器池中的服務(wù)器負(fù)載分配，以獲得優(yōu)化的響應(yīng)性能[1-2]。近年來(lái)，軟件定義網(wǎng)絡(luò)SDN(software defined network)在云數(shù)據(jù)中心廣泛應(yīng)用。SDN將控制平面與數(shù)據(jù)平面解耦合，由SDN控制器感知網(wǎng)絡(luò)狀態(tài)[3-4]。在SDN網(wǎng)絡(luò)中，控制器通過(guò)OpenFlow協(xié)議[5]動(dòng)態(tài)變換交換機(jī)中的流表規(guī)則，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)控制。一些研究利用這一特點(diǎn)，通過(guò)動(dòng)態(tài)變換用作負(fù)載均衡的交換機(jī)LBS(load balancing switch)中的流表規(guī)則來(lái)實(shí)現(xiàn)服務(wù)器間的負(fù)載均衡。負(fù)載均衡的策略集中在控制器端，其優(yōu)點(diǎn)是通過(guò)軟件定義的方式動(dòng)態(tài)部署不同的負(fù)載均衡策略，并且節(jié)省了傳統(tǒng)負(fù)載均衡器方式的部署成本[6]。

近年來(lái)對(duì)SDN環(huán)境下的服務(wù)器負(fù)載均衡領(lǐng)域的研究主要集中在服務(wù)器均衡策略[7-8]、流表資源優(yōu)化[9-11]等方面。Zhong等[7]將用戶請(qǐng)求定向到實(shí)時(shí)響應(yīng)時(shí)間最短的服務(wù)器處理，使服務(wù)器保持負(fù)載均衡的狀態(tài)。Handigol等[8]提出Plug-n-Server流量負(fù)載平衡方案，將控制器模塊化，通過(guò)控制器全局管理資源，使控制器高效有序地調(diào)度資源。Wang等[9]使用通配符規(guī)則轉(zhuǎn)發(fā)服務(wù)請(qǐng)求，將請(qǐng)求端按IP地址前綴劃分為多個(gè)區(qū)塊，根據(jù)負(fù)載動(dòng)態(tài)分解或合并各區(qū)，以期占用LBS較少的流表項(xiàng)資源。Lin等[10]提出通過(guò)給服務(wù)器分配優(yōu)先級(jí)設(shè)置不同的通配符規(guī)則，適用于大規(guī)模數(shù)據(jù)中心，以更少的流表項(xiàng)達(dá)到更高效率。Mao等[11]提出單流表和組流表結(jié)合的動(dòng)態(tài)流表設(shè)計(jì)算法，負(fù)載均衡時(shí)調(diào)整更少流表項(xiàng)，減少負(fù)載均衡流表變換。

文中提出一種采用OpenFlow交換機(jī)的服務(wù)器負(fù)載均衡策略，使用分區(qū)通配符規(guī)則均衡轉(zhuǎn)發(fā)服務(wù)請(qǐng)求，在LBS上預(yù)先部署多地址定向流表，SDN控制器周期性采集LBS活躍連接數(shù)，據(jù)此計(jì)算出服務(wù)器負(fù)載狀態(tài)。利用蟻群算法的信息正反饋和啟發(fā)式搜索特性，在服務(wù)器負(fù)載偏差超過(guò)閾值時(shí)求解負(fù)載調(diào)度方案，遷移負(fù)載以達(dá)到負(fù)載均衡的目的。

1 基于通配符的流表規(guī)則

采用負(fù)載均衡策略的服務(wù)器集群對(duì)外以單一IP地址形成單一映像(single image)。作為負(fù)載分配器(load dispatcher)的LBS按照SDN控制器部署的流表規(guī)則轉(zhuǎn)發(fā)請(qǐng)求到指定后端服務(wù)器。如果流表記錄每個(gè)請(qǐng)求的轉(zhuǎn)發(fā)規(guī)則，會(huì)產(chǎn)生流表溢出，影響轉(zhuǎn)發(fā)效率，增大控制器處理開(kāi)銷[12-13]。

將服務(wù)請(qǐng)求按源IP地址前綴劃分為多個(gè)區(qū)塊，分別用通配符表示每個(gè)區(qū)塊相同的地址前綴部分，將其映射到OpenFlow流表匹配字段中。在LBS轉(zhuǎn)發(fā)服務(wù)請(qǐng)求時(shí)，由于多個(gè)請(qǐng)求匹配同一轉(zhuǎn)發(fā)規(guī)則，因此稱之為多地址定向流表MDFT(multi-address directed flow table)，如圖1所示。MDFT能有效解決流表過(guò)多的問(wèn)題，主要用于流量轉(zhuǎn)發(fā)和流量數(shù)據(jù)監(jiān)控。

圖1 多地址定向流表表項(xiàng)Fig. 1 Multi-address directed flow entry

當(dāng)需要平衡負(fù)載，將原區(qū)域的負(fù)載重新分配時(shí)，引入單地址定向流表SDFT(single-address directed flow table)。在負(fù)載均衡調(diào)整期中同時(shí)存在調(diào)整前的TCP連接和調(diào)整啟動(dòng)后的新連接。SDFT登記每條新請(qǐng)求的TCP連接，而調(diào)整前的流量則繼續(xù)沿用原來(lái)的規(guī)則，從而保障TCP連接映射服務(wù)器的一致性。

在匹配規(guī)則上約定SDFT優(yōu)先級(jí)高于MDFT，當(dāng)請(qǐng)求同時(shí)滿足SDFT和MDFT匹配條件時(shí)，按照SDFT規(guī)則轉(zhuǎn)發(fā)流量。多個(gè)MDFT可以將服務(wù)請(qǐng)求轉(zhuǎn)發(fā)到同一服務(wù)器，但MDFT間IP通配符地址不能重疊，以保證服務(wù)請(qǐng)求轉(zhuǎn)發(fā)到唯一服務(wù)器。MDFT生存時(shí)間較長(zhǎng)，在不需要調(diào)整流表項(xiàng)時(shí)，服務(wù)請(qǐng)求按照MDFT轉(zhuǎn)發(fā)。SDFT生存時(shí)間較短，僅在負(fù)載均衡調(diào)整期使用。

2 基于OpenFlow交換機(jī)的負(fù)載均衡策略

如圖2所示，假設(shè)部署x臺(tái)服務(wù)器Si(i=1,2,…,x)，將請(qǐng)求端按源IP地址前綴初始劃分為m個(gè)區(qū)塊Bk(k=1,2,…,m)，每個(gè)區(qū)塊分別映射一個(gè)MDFT表項(xiàng)，其IP地址前綴為Ipre_k,每個(gè)區(qū)塊覆蓋n個(gè)請(qǐng)求端源IP地址，SDN控制器對(duì)應(yīng)生成并下發(fā)m個(gè)流表項(xiàng)Fk(Ipre_k,Si,p)到LBS，其中k=1,2,…,m，p為流表項(xiàng)的優(yōu)先級(jí)。地址前綴滿足Ipre_k的服務(wù)請(qǐng)求通過(guò)LBS匹配流表項(xiàng)Fk(Ipre_k,Si,p)后被轉(zhuǎn)發(fā)到服務(wù)器Si。當(dāng)不同服務(wù)器分配到的負(fù)載發(fā)生不均衡時(shí)，SDN控制器需要及時(shí)感知并做出負(fù)載再分配以均衡服務(wù)器負(fù)載。

圖2 負(fù)載均衡交換機(jī)轉(zhuǎn)發(fā)示意圖Fig. 2 Diagram of load balancing switch forwarding

2.1 服務(wù)器負(fù)載計(jì)算

在衡量服務(wù)器負(fù)載時(shí)，主要分為直接或間接方式獲取服務(wù)器的負(fù)載狀態(tài)。李艷冠等[14]和于天放等[15]通過(guò)控制器采用SNMP協(xié)議獲取服務(wù)器CPU利用率、內(nèi)存利用率等指標(biāo)來(lái)計(jì)算服務(wù)器負(fù)載。文獻(xiàn)[7]通過(guò)控制器發(fā)送Ping命令測(cè)試服務(wù)器實(shí)時(shí)響應(yīng)時(shí)間，根據(jù)實(shí)時(shí)響應(yīng)時(shí)間度量服務(wù)器負(fù)載。上述直接獲取服務(wù)器負(fù)載狀態(tài)的方法可以較準(zhǔn)確地衡量服務(wù)器的負(fù)載情況，但該方式對(duì)服務(wù)器缺乏透明性，對(duì)服務(wù)器的響應(yīng)方式有一定的要求，因此存在一定的局限性。另外，該方式需要控制器直接參與服務(wù)器數(shù)據(jù)采集，增加了控制器的開(kāi)銷。Boero等[16]提出通過(guò)交換機(jī)服務(wù)請(qǐng)求的入隊(duì)速率和處理速率衡量后端服務(wù)器負(fù)載不均衡程度，將交換機(jī)中入隊(duì)速率大于處理速率的流量重路由，從而達(dá)到后端服務(wù)器負(fù)載均衡的目的。該方法采用對(duì)服務(wù)器透明的機(jī)制，雖不能計(jì)算出服務(wù)器實(shí)際負(fù)載，但可以有效衡量后端服務(wù)器負(fù)載不均衡程度，減少控制器資源消耗，不限制服務(wù)器的響應(yīng)方式。

Li=θ*Ci，

(1)

式中，θ為活躍連接數(shù)對(duì)服務(wù)器負(fù)載的影響因子。當(dāng)服務(wù)請(qǐng)求到達(dá)LBS，LBS中匹配的流表項(xiàng)通過(guò)計(jì)數(shù)器對(duì)TCP的SYN位和FIN位計(jì)數(shù)，SDN控制器周期性采集LBS流表項(xiàng)中的該計(jì)數(shù)值，從而計(jì)算出活動(dòng)連接數(shù)。

考慮負(fù)載均衡出現(xiàn)抖動(dòng)，采取t次采樣數(shù)據(jù)計(jì)算平均數(shù)的方法來(lái)計(jì)算確定服務(wù)器平均負(fù)載

(2)

式中，Li[z]為在第z時(shí)刻服務(wù)器的總負(fù)載，t為采樣次數(shù)。

通過(guò)方差表示服務(wù)器間負(fù)載失衡度δ為

(3)

式中，δ(t)為t時(shí)刻服務(wù)器間負(fù)載失衡度。δ(t)越大，表示服務(wù)器間的不平衡程度越大。SDN控制器觸發(fā)負(fù)載均衡策略的條件為

δ(t)>ω，

(4)

式中，ω為負(fù)載失衡度閾值。

2.2 自適應(yīng)動(dòng)態(tài)負(fù)載均衡策略

文中提出一種自適應(yīng)動(dòng)態(tài)服務(wù)器負(fù)載均衡策略，利用SDN控制器向LBS部署MDFT和SDFT流表項(xiàng)重定向服務(wù)請(qǐng)求，SDN控制器采用基于蟻群算法的負(fù)載重定向算法ACO-LBSA(ACO-based load balance switching algorithm)來(lái)決策服務(wù)器間的負(fù)載遷移，以達(dá)到負(fù)載均衡。

2.2.1 負(fù)載重定向方案選擇

蟻群算法[18-20]是一種模擬螞蟻尋找食物過(guò)程中發(fā)現(xiàn)路徑的智能優(yōu)化算法，該算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特點(diǎn)。在研究場(chǎng)景中，負(fù)載均衡策略需要實(shí)時(shí)監(jiān)控全局負(fù)載變化，并自適應(yīng)均衡負(fù)載分配，因此采用蟻群算法以達(dá)到較快的收斂速度和較高的求解準(zhǔn)確度。將服務(wù)器負(fù)載情況作為蟻群算法的信息素，重定向活動(dòng)連接數(shù)的倒數(shù)作為啟發(fā)函數(shù)，服務(wù)器間負(fù)載失衡度作為路徑長(zhǎng)度，算法目標(biāo)是求解過(guò)載服務(wù)器負(fù)載重定向最優(yōu)方案。

假定在當(dāng)前時(shí)刻服務(wù)器Si過(guò)載。負(fù)載重定向算法過(guò)程描述如下：

1)初始化信息素濃度及每只螞蟻。在云數(shù)據(jù)中心初始化階段，考慮服務(wù)器之間的處理能力異構(gòu)性，用服務(wù)器的負(fù)載處理能力對(duì)信息素τki初始化：

τki=di，

(5)

式中，di表示為服務(wù)器Si處理負(fù)載的能力。創(chuàng)建包含m個(gè)MDFT表項(xiàng)、x個(gè)服務(wù)器的螞蟻對(duì)象，初始化服務(wù)器失衡度。螞蟻隨機(jī)選擇路徑(Fk,Si)，路徑表示為將流表項(xiàng)Fk重定向到服務(wù)器Si。并將分配過(guò)的MDFT從搜索列表gh中刪除，加入到禁忌表。

2)選擇重定向服務(wù)器。螞蟻按照概率與輪盤賭算法選擇服務(wù)器重定向MDFT，在t時(shí)刻第h只螞蟻選擇將流表項(xiàng)Fk重定向到副本服務(wù)器Si的概率

(6)

式中：τki(t)表示t時(shí)刻將流表項(xiàng)Fk重定向到服務(wù)器Si的路徑上的信息素濃度；α為信息素啟發(fā)因子，表示螞蟻在路徑上留下的信息素的重要性；β為期望啟發(fā)因子，反映了啟發(fā)函數(shù)的重要性。ηki(t)為啟發(fā)函數(shù)表示服務(wù)器Si處理流表項(xiàng)Fk轉(zhuǎn)發(fā)流量的可見(jiàn)度，本策略采用重定向活動(dòng)連接數(shù)定義啟發(fā)函數(shù)

(7)

3)更新任務(wù)禁忌表、搜索列表和服務(wù)器負(fù)載情況。根據(jù)步驟1中的方法更新禁忌表、搜索列表和服務(wù)器負(fù)載情況。

4)每只螞蟻形成一個(gè)局部最優(yōu)解。當(dāng)一次迭代結(jié)束后，每只螞蟻按照式(8)選擇最小失衡度的解為最優(yōu)解，最優(yōu)解加入到序列List<(Fk,Si)>中，其中a代表螞蟻的數(shù)量，h代表第h只螞蟻

(8)

5)更新信息素。為了防止信息素堆積，對(duì)每只螞蟻完成分配后，調(diào)整信息素：

(9)

(10)

6)重復(fù)進(jìn)行迭代，直到達(dá)到最大迭代次數(shù)，計(jì)算出最優(yōu)解，并給出最優(yōu)負(fù)載重定向矩陣

(11)

若eki的值不為空，則表示將流表項(xiàng)Fi的負(fù)載重定向到服務(wù)器Sj；若為空，則不重定向。

2.2.2 基于蟻群算法的負(fù)載重定向算法

根據(jù)前文求解到的最優(yōu)負(fù)載重定向矩陣E，SDN控制器向LBS下發(fā)流表項(xiàng)重定向服務(wù)請(qǐng)求，實(shí)現(xiàn)負(fù)載均衡。基本思路為：SDN控制器下發(fā)優(yōu)先級(jí)為p1(p1>p)的流表項(xiàng)Fnew(Ipre_k,Si,p1)和轉(zhuǎn)發(fā)到新服務(wù)器Sj流表項(xiàng)Fnew(Ipre_k,Sj,p)，當(dāng)服務(wù)請(qǐng)求到達(dá)Fnew(Ipre_k,Si,p1)時(shí)，流表項(xiàng)檢查TCP標(biāo)識(shí)SYN位。若SYN=1，視為新的TCP流，由SDN控制器下發(fā)優(yōu)先級(jí)為p2(p2>p1)的源IP地址為Ikj的SDFT表項(xiàng)fnew(Ikj,Sj,p2)定向到新的服務(wù)器Sj，并將流表項(xiàng)加入SDFT表項(xiàng)集合fj，將新的TCP請(qǐng)求重定向到新的服務(wù)器處理；若為原來(lái)持續(xù)的流，由SDN控制器下發(fā)流表項(xiàng)fnew(Iki,Si,p2)，設(shè)置空閑超時(shí)時(shí)間idle_time，從而保障TCP連接映射服務(wù)器的一致性，并將流表項(xiàng)加入集合fi。通常情況下[9]，若在60 s內(nèi)無(wú)數(shù)據(jù)傳輸，視為連接關(guān)閉，因此實(shí)驗(yàn)中設(shè)置idle_time 為60 s。超過(guò)idle_time后，刪除fj和Fnew(Ipre_k,Si,p1)，查看fi，若為空則刪除集合，實(shí)現(xiàn)無(wú)差錯(cuò)的負(fù)載重定向。該算法偽代碼如表1所示。

表1 ACO-LBSA算法

3 實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析

3.1 實(shí)驗(yàn)環(huán)境

研究在Ubuntu環(huán)境下使用Mininet搭建SDN網(wǎng)絡(luò)仿真實(shí)驗(yàn)環(huán)境，選擇Ryu作為SDN控制器，選擇OpenVSwitch作為負(fù)載均衡交換機(jī)，構(gòu)建實(shí)驗(yàn)網(wǎng)絡(luò)，該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)銯ig. 3 Experimental network topology

實(shí)驗(yàn)為服務(wù)器集群配置4臺(tái)服務(wù)器，服務(wù)請(qǐng)求端選擇整個(gè)IP地址空間的一個(gè)子集，將其劃為24個(gè)初始區(qū)塊，每個(gè)服務(wù)器初始按平均方式各分配6個(gè)區(qū)塊。

3.2 實(shí)驗(yàn)分析

以云數(shù)據(jù)中心為目標(biāo)，模擬4種場(chǎng)景下分別使用Random算法、Round Robin算法和ACO-LBSA算法進(jìn)行均衡負(fù)載的過(guò)程。4種場(chǎng)景分別為：①低負(fù)載運(yùn)行，服務(wù)器負(fù)載均在10%～20%；②負(fù)載失衡度較高，不同區(qū)塊的負(fù)載相差可達(dá)10倍；③服務(wù)請(qǐng)求突增，某些區(qū)塊的負(fù)載在某個(gè)時(shí)刻陡增一倍；④高負(fù)載運(yùn)行，服務(wù)器負(fù)載均在80%～90%。如圖4～圖7所示，為4種場(chǎng)景下發(fā)生一次負(fù)載均衡過(guò)程前后總共180 s內(nèi)服務(wù)器平均響應(yīng)時(shí)間，其中每隔5 s計(jì)算一次平均響應(yīng)時(shí)間。

圖4 場(chǎng)景(1)下服務(wù)器平均響應(yīng)時(shí)間變化趨勢(shì)Fig. 4 Trend of average server response time under scenario (1)

圖5 場(chǎng)景(2)下服務(wù)器平均響應(yīng)時(shí)間變化趨勢(shì)Fig. 5 Trend of average server response time under scenario (2)

圖6 場(chǎng)景(3)下服務(wù)器平均響應(yīng)時(shí)間變化趨勢(shì)Fig. 6 Trend of average server response time under scenario (3)

圖7 場(chǎng)景(4)下服務(wù)器平均響應(yīng)時(shí)間變化趨勢(shì)Fig. 7 Trend of average server response time under scenario (4)

如表2所示，為分別采用ACO-LBSA算法與Random算法、Round Robin算法在4種場(chǎng)景下服務(wù)器響應(yīng)性能對(duì)比。

表2 服務(wù)器響應(yīng)性能對(duì)比

從圖4～圖7和表2中可以看出，在場(chǎng)景(1)下，采用3種算法的服務(wù)器平均響應(yīng)時(shí)間相差不大，但采用ACO-LBSA算法的服務(wù)器平均響應(yīng)時(shí)間略有優(yōu)勢(shì)，且服務(wù)器平均響應(yīng)時(shí)間波動(dòng)更??；在場(chǎng)景(2)下，采用ACO-LBSA算法的服務(wù)器平均響應(yīng)時(shí)間明顯優(yōu)于其他2種算法，且服務(wù)器平均響應(yīng)時(shí)間波動(dòng)更??；在場(chǎng)景(3)下，采用ACO-LBSA算法的服務(wù)器平均響應(yīng)時(shí)間明顯優(yōu)于其他2種算法，且服務(wù)器平均響應(yīng)時(shí)間的波動(dòng)明顯降低；在場(chǎng)景(4)下，采用ACO-LBSA算法的服務(wù)器平均響應(yīng)時(shí)間優(yōu)化較場(chǎng)景(1)～場(chǎng)景(3)下程度更高，服務(wù)器平均響應(yīng)時(shí)間波動(dòng)較其他算法明顯降低。

根據(jù)以上實(shí)驗(yàn)可以看出，文中提出的ACO-LBSA算法較Random算法和Round Robin算法在服務(wù)器響應(yīng)性能方面有所改善，在云數(shù)據(jù)中心處于負(fù)載失衡度較高、服務(wù)請(qǐng)求突增和高負(fù)載運(yùn)行等典型場(chǎng)景下，較其他2種算法對(duì)服務(wù)器響應(yīng)性能改善更為明顯。

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

提出了一種采用OpenFlow交換機(jī)的負(fù)載均衡策略。通過(guò)通配符規(guī)則縮減流表項(xiàng)數(shù)量，分別采用MDFT和SDFT用于均衡的負(fù)載分配和負(fù)載調(diào)整期的負(fù)載過(guò)渡，以活躍連接數(shù)度量服務(wù)器負(fù)載，從而使負(fù)載均衡對(duì)服務(wù)器保持透明。當(dāng)服務(wù)器負(fù)載失衡度超過(guò)閾值，SDN控制器通過(guò)蟻群算法求解出最優(yōu)的負(fù)載調(diào)度方案，并向LBS下發(fā)MDFT流表項(xiàng)和SDFT流表項(xiàng)重定向服務(wù)請(qǐng)求，以達(dá)到負(fù)載均衡。通過(guò)仿真實(shí)驗(yàn)顯示文中的策略較隨機(jī)和輪轉(zhuǎn)策略性能更優(yōu)。后續(xù)研究工作將在此基礎(chǔ)上討論引入?yún)^(qū)分服務(wù)的負(fù)載均衡策略。