朱國暉,史思潮,翟鵬宇
(西安郵電大學 通信與信息工程學院,陜西 西安 710121)
在互聯(lián)網(wǎng)發(fā)展初期,主要通過傳統(tǒng)的負載均衡技術(shù)改善網(wǎng)絡流量擁塞問題。當網(wǎng)絡中的用戶產(chǎn)生了流量,負載均衡設備根據(jù)流量的目的IP,通過服務器將流量分配到相應的鏈路中去。隨著大數(shù)據(jù)等技術(shù)飛速發(fā)展,網(wǎng)絡的規(guī)模也越來越大,尤其在數(shù)據(jù)中心網(wǎng)絡中,需要提供的業(yè)務也越來越多,因此會產(chǎn)生大量的流量。傳統(tǒng)的負載均衡技術(shù)不能滿足網(wǎng)絡中多業(yè)務對流量的需求,從而會引發(fā)網(wǎng)絡擁塞問題。并且傳統(tǒng)的數(shù)據(jù)中心網(wǎng)絡拓撲簡單,很難解決鏈路擁塞問題,從而導致網(wǎng)絡傳輸速率較低。因此,研究人員提出了胖樹[1](Fat-Tree)、BCube[2]等多種網(wǎng)絡拓撲結(jié)構(gòu),可以為網(wǎng)絡提供更多的鏈路,便于實現(xiàn)數(shù)據(jù)中心網(wǎng)絡的負載均衡。
在數(shù)據(jù)中心網(wǎng)絡中,使用最為廣泛的是等價多路徑[3](Equal Cost Multi Path, ECMP)算法,由于其為靜態(tài)路由算法,不能適應網(wǎng)絡流量的實時變化,因此當網(wǎng)絡的流量急劇增加會使網(wǎng)絡產(chǎn)生擁塞現(xiàn)象。隨著網(wǎng)絡中業(yè)務種類的不同,產(chǎn)生的流量大小也不同。為了可以更好地調(diào)度網(wǎng)絡中的流量,充分利用網(wǎng)絡資源,將數(shù)據(jù)中心網(wǎng)絡中的流量按照大小劃分為大象流和老鼠流[4-5]。傳統(tǒng)的ECMP算法會將網(wǎng)絡中的大象流調(diào)度到同一路徑中,使得鏈路產(chǎn)生擁塞現(xiàn)象,導致網(wǎng)絡負載不均衡現(xiàn)象。文獻[6]中提出了Hedera策略,可以隨著網(wǎng)絡中實時變化的動態(tài)流量而調(diào)整策略,將占用鏈路容量的10%作為大象流,通過全局優(yōu)先匹配流量調(diào)度(Global First Fit, GFF)算法在網(wǎng)絡中搜索,將得到的第一條滿足大象流分配的路徑作為大象流路由。隨著網(wǎng)絡中流量不斷擴大,大象流可調(diào)度的路徑將會不斷減少。因此,Hedera策略不能保證所有數(shù)據(jù)流都能合理的調(diào)度,易使得網(wǎng)絡產(chǎn)生擁塞現(xiàn)象,并且導致網(wǎng)絡資源不能充分的利用。文獻[7]提出一種差異化調(diào)度算法,將網(wǎng)絡中的流量劃分為老鼠流和大象流,并且分別提出不同的算法進行調(diào)度。大象流通過封鎖島路徑設置算法,老鼠流則使用多路徑算法,通過分配合理的加權(quán)值將老鼠流分配到多路徑中,并且隨著網(wǎng)絡流量變化動態(tài)地調(diào)整策略。文獻[8]中提出粒子群優(yōu)化算法,主要針對網(wǎng)絡中的大象流進行調(diào)度。在網(wǎng)絡中設定一個閾值,當負載超過設定的閾值時,通過調(diào)度優(yōu)化的粒子群算法重新路由網(wǎng)絡中的大象流,避免鏈路產(chǎn)生擁塞現(xiàn)象。文獻[9]同樣設定閾值,當網(wǎng)絡中的負載超過設定的閾值,大象流負載均衡機制通過將大象流劃分為多個老鼠流,并且在選擇下一跳交換機時,將負載最小作為選擇條件。最終將大象流分配到其他路徑中,避免產(chǎn)生擁塞現(xiàn)象。文獻[10]針對大象流易導致?lián)砣麊栴},對可調(diào)度的路徑進行加權(quán)值計算,將大象流合理地分配到多條路徑中,從而實現(xiàn)網(wǎng)絡負載均衡。文獻[11]以最小化最大鏈路利用率為目標,提出了基于蟻群算法的軟件定義網(wǎng)絡(Ant Colony Optimization-Software Defined Network,ACO-SDN)機制。通過建立整型線性規(guī)劃(Integral Linear Programing,ILP)模型,將擁堵的鏈路通過調(diào)度蟻群算法重新路由,實現(xiàn)負載均衡的效果。但是,該蟻群算法收斂速度變慢,對網(wǎng)絡整體性能都有影響。
針對ECMP算法調(diào)度大象流易產(chǎn)生鏈路擁塞導致網(wǎng)絡負載不均衡現(xiàn)象,在Fat-Tree拓撲結(jié)構(gòu)下,擬提出基于蟻群優(yōu)化的動態(tài)鏈路負載均衡(Dynamic Load Balancing based on Ant Colony Optimization,DLB-ACO)算法。該算法首先計算一個周期內(nèi)的鏈路負載方差,降低瞬時負載極值對負載均衡度的影響,避免資源的浪費。其次,對蟻群算法的路徑選擇概率引入混沌策略和分段調(diào)節(jié)揮發(fā)因子,增強算法的全局搜索能力,可以較大概率地計算出全局最優(yōu)路徑,實現(xiàn)網(wǎng)絡的負載均衡。最后,通過與ECMP算法和GFF算法對比,驗證所提DLB-ACO算法的有效性。
在數(shù)據(jù)中心網(wǎng)絡中,ECMP算法調(diào)度大象流會導致鏈路產(chǎn)生擁塞現(xiàn)象,使得網(wǎng)絡負載不均衡。因此,所提DLB-ACO算法通過在SDN控制器中部署相關(guān)模塊功能實現(xiàn)數(shù)據(jù)中心負載均衡,總體實現(xiàn)的框架如圖1所示,其由控制器與Fat-tree網(wǎng)絡拓撲兩個部分組成。
圖1 DLB-ACO總體框架
由圖1可以看出,SDN控制器包括流量監(jiān)控、大象流檢測、負載均衡度計算、DLB-ACO調(diào)度路徑計算和流量管理等5個模塊。Fat-tree網(wǎng)絡主要由主機和交換機組成,在數(shù)據(jù)中心網(wǎng)絡對于大象流的整體調(diào)度的具體步驟如下。
步驟1流量監(jiān)控模塊主要功能是監(jiān)控整個數(shù)據(jù)中心網(wǎng)絡的數(shù)據(jù)流,并將數(shù)據(jù)流信息傳遞給大象流檢測模塊。
步驟2大象流檢測模塊主要檢測是否有大象流,如果有,將信息傳遞給負載均衡度計算模塊。
步驟3負載均衡度計算模塊主要計算網(wǎng)絡鏈路的帶寬方差,判斷整個網(wǎng)絡的負載均衡度,當網(wǎng)絡中大象流超過設定的閾值,就調(diào)度DLB-ACO算法模塊。
步驟4DLB-ACO算法模塊主要為大象流的調(diào)度重新計算轉(zhuǎn)發(fā)路徑,并將計算出的轉(zhuǎn)發(fā)路徑下發(fā)給流量管理模塊。
步驟5流量管理模塊把計算出的轉(zhuǎn)發(fā)路徑下發(fā)到數(shù)據(jù)中心網(wǎng)絡中的流表項中,并由其完成大象流的重路由。
介紹針對大象流易導致數(shù)據(jù)中心網(wǎng)絡擁塞現(xiàn)象提出的DLB-ACO算法實現(xiàn)整體過程,描述針對負載方差易受短時間內(nèi)鏈路已用帶寬極值的影響,并進行部分改進。最后,詳述蟻群優(yōu)化算法過程。
所提DLB-ACO算法首先設定閾值,以鏈路的負載方差作為網(wǎng)絡的負載均衡度。當鏈路的負載方差大于設定的閾值時,觸發(fā)網(wǎng)絡中的負載均衡算法,控制器根據(jù)當前的網(wǎng)絡情況通過優(yōu)化的蟻群算法對大象流進行調(diào)度,從而計算出最佳路徑,最終實現(xiàn)網(wǎng)絡的負載均衡。DLB-ACO負載均衡算法的流程如圖2所示。
圖2 DLB-ACO負載均衡算法流程
由圖2可以看出,DLB-ACO算法包括以下5個具體實現(xiàn)步驟。
步驟1當網(wǎng)絡中的主機產(chǎn)生流量,并發(fā)送到數(shù)據(jù)中心網(wǎng)絡中時,網(wǎng)絡首先會調(diào)用ECMP靜態(tài)路由算法對流量進行調(diào)度。物理層中的交換機會周期性地收集鏈路中的數(shù)據(jù)流信息,并傳遞給控制器。
步驟2控制器中sflow收集器會處理收集來的信息,并根據(jù)數(shù)據(jù)流的大小分類。將超過鏈路容量的10%劃分為大象流,并且計算鏈路利用率。
步驟3控制器判斷計算出大象流經(jīng)過的鏈路利用率是否大于閾值60%[11]。如果大于該閾值,轉(zhuǎn)到步驟4,否則轉(zhuǎn)到步驟1。
步驟4根據(jù)鏈路的實時信息,控制器調(diào)用改進的蟻群算法重新路由大象流。將計算出的流表項轉(zhuǎn)發(fā)給交換機。
步驟5交換機根據(jù)流表項重新路由大象流。之后,轉(zhuǎn)到步驟2。
在所提DLB-ACO算法中,控制器可以獲取到全網(wǎng)絡的鏈路信息,并且計算出網(wǎng)絡的負載均衡度。通過計算全局鏈路已用帶寬方差[12]作為網(wǎng)絡的負載均衡度。t時刻的網(wǎng)絡鏈路負載方差表達式為
(1)
在目前網(wǎng)絡中,鏈路已用帶寬隨時間波動較大,易造成網(wǎng)絡資源浪費。為降低此影響,在鏈路負載方差中引入平滑機制,某一時刻的鏈路負載不均衡狀態(tài)會觸發(fā)不必要的負載均衡算法。因此,需要忽略網(wǎng)絡中某一時刻鏈路負載的極值。
通過計算一段時間內(nèi)鏈路使用帶寬變化情況,可以降低網(wǎng)絡中某時刻產(chǎn)生的極值影響,使得計算出的方差值更加接近數(shù)據(jù)中心網(wǎng)絡實際的波動情況。一個周期內(nèi)網(wǎng)絡鏈路負載方差計算的表達式為
(2)
式中:P表示周期時間;T表示當前時刻。
2.3.1 選擇策略
混沌現(xiàn)象是一種隨機的現(xiàn)象,與大自然生物、物理及地理都有一定的聯(lián)系,并且被廣泛地應用在計算機技術(shù)的加密和圖像處理中。為了增加路徑選擇的多樣性,在選擇下一節(jié)點的概率中引入混沌現(xiàn)象,可以使得選擇下一節(jié)點的路徑數(shù)增加。
Logistic映射產(chǎn)生混沌序列[13]的計算表達式為
Xi+1=μXi(1-Xi)
(3)
i∈{1,2…,n},μ∈(0,4],Xi∈(0,1)
式中,μ表示控制參數(shù)。
蟻群算法融合混沌策略之后的轉(zhuǎn)移概率為螞蟻從i到j之間的選擇路徑概率,其表達式為
(4)
式中:Xij表示節(jié)點i到節(jié)點j產(chǎn)生的混沌變量;τij(t)表示t時刻節(jié)點i與節(jié)點j路徑上的信息素;τiu(t)表示t時刻節(jié)點i與節(jié)點u路徑上的信息素;ηiu(t)表示節(jié)點i到節(jié)點u的啟發(fā)式因子;ηij(t)為節(jié)點i到節(jié)點j的啟發(fā)式因子,表示信息素τ的重要程度;β為啟發(fā)式η的相對重要程度;Sk為螞蟻k在t時刻可以選擇的下一節(jié)點集合。
信息素更新的表達式為
τij(t+1)=(1-ρ)τij(t)+Δτij(t)
(5)
(6)
信息素初始化表達式為
(7)
2.3.2 分段調(diào)節(jié)信息素揮發(fā)因子
考慮蟻群算法在后期階段容易陷入局部最優(yōu)解,并且收斂速度也會隨之降低。其中,揮發(fā)因子ρ對收斂速度和搜索能力都會產(chǎn)生一定的影響。ρ過大,會降低算法的收斂速度;ρ過小,會降低全局搜索能力,得到的路徑不一定是全局最優(yōu)路徑。因此,所提算法將揮發(fā)因子引入分段調(diào)節(jié),在不降低收斂速度的同時,提高算法的全局搜索能力,可以較大概率地得到全局最優(yōu)解,其調(diào)節(jié)的表達式為
(8)
式中:M表示最大迭代次數(shù);N表示算法當前執(zhí)行的迭代次數(shù)。將算法分為前期、中期、后期和末期等4個階段,每個階段對信息素揮發(fā)因子都有對應的取值。
在經(jīng)典的蟻群算法上做出改進,通過在路徑選擇概率中引入混沌策略,增加可能選擇路徑的數(shù)量,可以較大概率上得到全局最優(yōu)解。同時,對揮發(fā)因子進行分段調(diào)節(jié),增加蟻群算法的全局搜索能力和收斂速度。具體步驟如下。
步驟1將算法中所有參數(shù)初始化,螞蟻的總數(shù)為m,最大的迭代次數(shù)為M,數(shù)據(jù)中心的鏈路總數(shù)初始化為L。
步驟2根據(jù)式(7)初始化鏈路的信息素濃度。
步驟3當為第k只螞蟻時,根據(jù)式(4)選擇選擇下一跳節(jié)點(交換機)。
步驟4如果沒有達到目的節(jié)點,繼續(xù)重復步驟3,直達目的節(jié)點。
步驟5根據(jù)迭代的次數(shù)選擇式(8)、式(6)和式(5)更新鏈路上的信息素。
步驟6當k≠m時,重復執(zhí)行步驟3,直到k=m。
針對蟻群算法在后期存在收斂速度較低的問題,對蟻群算法做出了改進。通過分段調(diào)節(jié)揮發(fā)因子使得算法具有較強的全局搜索能力的同時還可以有較高的收斂速度,并且對路徑選擇概率引入混沌策略,增加路徑選擇的數(shù)目,可以更大概率上獲得全局最優(yōu)路徑。
為驗證所提的DLB-ACO算法的性能,在Mininet仿真平臺搭建的Fat-Tree數(shù)據(jù)中心網(wǎng)路拓撲中,與其他兩種算法比較,分別將最大鏈路利用率、吞吐量和網(wǎng)絡時延作為最終的性能評價指標。
3.1.1 網(wǎng)絡拓撲結(jié)構(gòu)
在Mininet[14]仿真平臺上,搭建k=4的網(wǎng)絡架構(gòu),SDN下的Fat-tree拓撲圖如圖3所示,每個鏈路的容量均為100 Mbit·s-1。
圖3 SDN下的Fat-tree拓撲圖
3.1.2 參數(shù)設置
蟻群參數(shù)設置對蟻群算法影響較大,通過文獻[11]研究和綜合多次試驗結(jié)果進行設置,迭代次數(shù)設置為75,流量統(tǒng)計周期為1 s,大流監(jiān)控周期為5 s,負載監(jiān)控周期為5 s。兩節(jié)點之間為11跳,其他主要參數(shù)值如表1所示。
表1 蟻群算法主要參數(shù)值
通過以上參數(shù)設置,將所提算法與ECMP算法和GFF算法相比較。
為了驗證ECMP算法、GFF算法與所提DLB-ACO算法的性能,設定在交錯通信模式下Staggered(0,0.3),將第一個數(shù)據(jù)中心基本物理設計單元(Point of Delivery,Pod)中的主機作為數(shù)據(jù)源產(chǎn)生數(shù)據(jù)流并發(fā)送,使得鏈路中有較高的負載,達到可以檢測算法的性能。
3.2.1 平均吞吐量
吞吐量可以清楚地反映出算法對網(wǎng)絡實時的影響情況,表示在單位時間內(nèi)網(wǎng)絡可以傳輸?shù)臄?shù)據(jù)量,并且還能反映出網(wǎng)絡狀態(tài)的優(yōu)劣情況。ECMP算法、GFF算法和DLB-ACO這3種算法在不同流量負載下的吞吐量對比情況如圖4所示。
圖4 不同流量負載下的平均吞吐量
由圖4可以看出,ECMP算法和GFF算法的吞吐量分別在負載80 Mbit·s-1、85 Mbit·s-1時達到最大值,之后呈下降趨勢。通過不同的負載情況對比3種算法,可以看出所提的DLB-ACO算法吞吐量一直高于其他兩種算法。
3.2.2 平均時延
算法的性能影響網(wǎng)絡狀態(tài)和數(shù)據(jù)流的傳輸時間,計算數(shù)據(jù)流的平均傳輸時延可以有效地反映出算法對網(wǎng)絡系統(tǒng)的影響。ECMP算法、GFF算法和DLB-ACO等3種算法在不同流量負載下的平均傳輸時延情況如圖5所示。
圖5 不同流量負載下的平均時延
由圖5可以看出,ECMP算法、GFF算法及所提DLB-ACO算法的平均延遲時間:在負載30 Mbit·s-1之前,3種算法的延遲基本相差不大;在負載60 Mbit·s-1后,GFF算法和DLB-ACO算法與ECMP算法相差較大,GFF算法相對于DLB-ACO算法平均延遲時間逐漸變大;當負載到達最高100 Mbit·s-1時,DLB-ACO算法相較于ECMP算法和GFF算法分別降低了延遲時間的38%和22%。
3.2.3 最大鏈路利用率
鏈路利用率可以反映出鏈路的使用情況,不同負載下ECMP算法、GFF算法和DLB-ACO這3種算法鏈路利用率如圖6所示。
圖6 不同負載下的鏈路利用率
由圖6可以看出,DLB-ACO算法的性能最好,因為當網(wǎng)絡中的信息有變化時,該算法會對網(wǎng)絡鏈路信息實時更改。當有鏈路的負載均衡度超過閾值時,則啟動DLB-ACO算法,對檢測出的大象流重路由,避免了網(wǎng)絡的擁塞機率。ECMP算法不能根據(jù)網(wǎng)絡的當前信息及時作出調(diào)整,因此鏈路擁塞的機率和最大鏈路利用率會變大。GFF算法是根據(jù)大象流達到的先后順序進行重路由,有一定的局限性。因此,所提DLB-ACO算法最大鏈路利用率最高。
針對數(shù)據(jù)中心網(wǎng)絡中傳統(tǒng)路由算法調(diào)度大象流容易造成網(wǎng)絡負載不均衡現(xiàn)象,提出了基于蟻群優(yōu)化的動態(tài)負載均衡DLB-ACO算法。所提算法首先計算出一個周期內(nèi)的鏈路負載方差,降低瞬時負載極值對負載均衡度的影響,然后對蟻群算法的路徑選擇概率引入混沌策略,增強蟻群算法的全局搜索能力。同時,分段調(diào)節(jié)揮發(fā)因子,增強算法的收斂速度,并且可以較大概率地計算出全局最優(yōu)路徑,實現(xiàn)網(wǎng)絡的負載均衡。最后,為了驗證所提DLB-ACO算法的有效性,將其與ECMP算法和GFF算法對比。在網(wǎng)絡負載為90 Mbit·s-1時,所提算法的平均吞吐量明顯高于其他兩種算法。當負載最高時,DLB-ACO算法與ECMP算法和GFF算法相比,時延分別降低了38%和22%。實驗結(jié)果表明,ECMP和GFF算法整體性能低于所提DLB-ACO算法,所提算法對網(wǎng)絡整體性能有所改進,分別在平均吞吐量和時延和最大鏈路利用率有所改善。