基于離散粒子群的SDN動態(tài)流調(diào)度算法

劉 威, 高新成, 王啟龍, 張 宣, 王莉利

(1. 東北石油大學(xué) 計算機(jī)與信息技術(shù)學(xué)院, 黑龍江 大慶 163318;2. 東北石油大學(xué) 現(xiàn)代教育技術(shù)中心, 黑龍江 大慶 163318)

隨著互聯(lián)網(wǎng)的迅速發(fā)展, 數(shù)據(jù)中心的流量負(fù)載能力不斷受到挑戰(zhàn)[1], 對數(shù)據(jù)中心流量承載能力的要求也不斷提高. 基于此, 研究人員提出了如Fat-Tree[2]和BCube[3]等網(wǎng)絡(luò)結(jié)構(gòu), 這些網(wǎng)絡(luò)結(jié)構(gòu)對提高網(wǎng)絡(luò)負(fù)載能力以及容災(zāi)能力效果很好. 目前, 數(shù)據(jù)中心使用較多的流量調(diào)度算法是等價多徑轉(zhuǎn)發(fā)(equal-cost multi-path, ECMP)算法[4]. ECMP通過將流量同時轉(zhuǎn)發(fā)到多條路徑上, 減少傳輸過程中單條路徑的負(fù)擔(dān)完成流量的負(fù)載均衡[5]. 傳統(tǒng)數(shù)據(jù)中心的ECMP對小流負(fù)載均衡較好, 但對于大流, ECMP可能會將其轉(zhuǎn)發(fā)至同一鏈路, 導(dǎo)致小流應(yīng)用的延遲、 丟包、 擁塞及大流的怠速, 從而使鏈路擁塞, 影響網(wǎng)絡(luò)質(zhì)量[6]. 因此如何對流量合理調(diào)度成為數(shù)據(jù)中心流量管理領(lǐng)域[7]的研究熱點.

針對傳統(tǒng)網(wǎng)絡(luò)在配置與管理方面的缺陷, 研究者們提出了軟件定義網(wǎng)絡(luò)(software defined network, SDN)[8]的新網(wǎng)絡(luò)架構(gòu). SDN的核心思想是將網(wǎng)絡(luò)進(jìn)行分層, 將控制功能與轉(zhuǎn)發(fā)功能分開進(jìn)行管理, 并賦予軟件控制數(shù)據(jù)轉(zhuǎn)發(fā)的能力, 使網(wǎng)絡(luò)集中控制化并且能從全局的網(wǎng)絡(luò)角度對流量進(jìn)行調(diào)度[9]. 雖然SDN的架構(gòu)比傳統(tǒng)網(wǎng)絡(luò)的靈活性、 可管理性更強(qiáng), 但其也面臨著數(shù)據(jù)流量負(fù)載不均衡、 無法充分利用網(wǎng)絡(luò)資源的問題. 針對大流調(diào)度問題, Al-fares等[10]提出了Hedera調(diào)度算法, Hedera算法采取全局首次適應(yīng)算法(global first fit, GFF)對大流進(jìn)行處理, 對小流的處理采取ECMP策略. 在Hedera算法中, 定義超過鏈路帶寬的10%就將該條數(shù)據(jù)流判定為大流, 但是隨著網(wǎng)絡(luò)負(fù)載的加重, 鏈路逐漸飽和, GFF很難保證調(diào)度所有大流; Xu等[11]提出了一種流量調(diào)度方法MTSS, MTSS通過定期監(jiān)控鏈路信息將負(fù)載較大的鏈路分擔(dān)到負(fù)載較小的鏈路, 但網(wǎng)絡(luò)狀況的多變導(dǎo)致頻繁調(diào)度, 其開銷較大; Wang等[12]提出了一種動態(tài)路徑規(guī)劃算法Freeway, 對于大流采取將其放入高吞吐量的路徑以滿足其帶寬需求; 對于小流使用ECMP策略將其調(diào)度到時延較低的路徑, 該算法同時滿足大流和小流的特征需求, 但Freeway算法采取VLAN標(biāo)記和鏈路隔離, 實現(xiàn)難度較大; Long等[13]建立了一種網(wǎng)絡(luò)閾值算法判斷網(wǎng)絡(luò)是否過載, 將整個網(wǎng)絡(luò)的鏈路負(fù)載方差作為判斷網(wǎng)絡(luò)是否擁塞的標(biāo)準(zhǔn), 將超過閾值的數(shù)據(jù)流進(jìn)行重路由, 這種網(wǎng)絡(luò)擁塞算法的計算過程復(fù)雜, 缺乏靈活性與準(zhǔn)確性; 黃馬馳[14]提出了一種BFlows算法, 其通過篩選若干條大流數(shù)目最少的路徑, 再選擇負(fù)載最小的路徑作為新路徑, 但其僅對大流數(shù)量進(jìn)行鏈路選擇, 因素過于單一.

針對目前數(shù)據(jù)中心流量特征以及負(fù)載均衡方案的不足, 本文提出一種基于離散粒子群優(yōu)化的動態(tài)流調(diào)度DFSDPSO(dynamic flow scheduling based discrete partical swarm optimization)算法, 結(jié)合離散粒子群算法和模擬退火算法(simulated annealing, SA)[15]中的Metropolis準(zhǔn)則, 以最大化網(wǎng)絡(luò)吞吐量為目標(biāo), 通過算法選擇對大流進(jìn)行調(diào)度完成流量均衡.

1 算法設(shè)計

1.1 設(shè)計思想

當(dāng)數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載較重時, 頻繁大流調(diào)度代價較大, 會導(dǎo)致原來暢通的鏈路擁塞、 流表缺失和控制器資源的浪費. 為減少網(wǎng)絡(luò)的整體負(fù)載, 增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性, 本文DFSDPSO算法的設(shè)計思想是通過收集網(wǎng)絡(luò)中大流, 分離出能滿足網(wǎng)絡(luò)吞吐量最大條件的大流集合, 滿足條件的大流傳輸路徑不變. 對不滿足條件的大流, 下發(fā)至策略集合處理模塊計算出最適合的路徑進(jìn)行傳輸. 算法流程如圖1所示.

圖1 算法設(shè)計流程Fig.1 Flow chart of algorithm design

1.2 流程設(shè)計

通過在SDN控制器中完成相關(guān)部署, DFSDPSO算法整體架構(gòu)如圖2所示, 由SDN控制器和拓?fù)錁永鼺at-Tree兩個模塊組成. 該架構(gòu)中最主要的模塊是SDN控制器模塊, SDN控制器模塊包括5個子模塊, 分別是拓?fù)涓兄K、 鏈路信息感知模塊、 大流采集模塊、 基于離散粒子群優(yōu)化算法的策略計算模塊和策略集合處理模塊.

圖2 DFSDPSO算法整體流程Fig.2 Overall process of DFSDPSO algorithm

1.3 控制器模塊設(shè)計

1.3.1 拓?fù)涓兄K

拓?fù)涓兄K由控制器通過鏈路發(fā)現(xiàn)協(xié)議LLDP實現(xiàn), 控制器通過構(gòu)造Packet_Out消息向其控制的邊緣交換機(jī)(OVS)下發(fā)LLDP數(shù)據(jù)包, 匯總LLDP響應(yīng)消息獲取相關(guān)連接信息.

1.3.2 鏈路信息感知模塊

SDN控制器通過下發(fā)的OFPPortStatsRequest和OFPFlowStatsRequest消息向OVS獲取其端口和流表狀態(tài)信息, 收到兩者Reply消息后, 解析消息得到鏈路信息.

1.3.3 大流采集模塊

根據(jù)Hedera檢測設(shè)置篩選大流閾值標(biāo)準(zhǔn), 如超過鏈路總帶寬10%為大流. 通過控制器收集邊緣交換機(jī)統(tǒng)計的流表信息, 將流表信息單位換算成流量信息, 篩選出所有大流記錄.

1.3.4 策略計算模塊

從大流采集模塊獲取輸入后, 利用DFSDPSO算法對大流進(jìn)行篩選, 通過篩選出滿足優(yōu)化目標(biāo)的大流, 返回相關(guān)調(diào)度策略, 告知后一層模塊, 提供策略輸入.

1.3.5 策略集合處理模塊

通過計算大流中所有路徑的負(fù)載, 選出滿足負(fù)載需求的路徑, 將所有大流及其相關(guān)滿足的路徑下發(fā)至后一模塊.

1.4 大流調(diào)度設(shè)計

1.4.1 數(shù)學(xué)模型建立

策略計算模塊在收集到大流集合后, 假設(shè)大流集合由n條大流f1,f2,…,fn組成, 其吞吐量分別為bi(i=1,2,…,n).在包含m條鏈路的網(wǎng)絡(luò)中, 其鏈路信息包含兩種屬性, 鏈路的可用帶寬rbj(j=1,2,…,m)及經(jīng)過該鏈路的大流n元組Ej(e1,e2,…,en), 其中ek(k=1,2,…,n)的取值為1或者0.ek=1表示第fk條大流經(jīng)過該鏈路;ek=0表示第fk條大流不經(jīng)過該鏈路.DFSDPSO算法的最終調(diào)取方案為X={x1,x2,…,xn}, 其中xi的取值為0或者1,xi=1表示在調(diào)度方案中選中fi大流進(jìn)行原路徑傳輸;xi=0表示不選該大流, 需要將大流fi輸入到策略集合模塊中進(jìn)行重調(diào)度.

DFSDPSO算法的優(yōu)化目標(biāo)為保證整體網(wǎng)絡(luò)吞吐量最大, 即挑選出滿足網(wǎng)絡(luò)吞吐量最大的流量, 并且挑選過程中要滿足每條鏈路的大流集合吞吐量之和不大于該鏈路的可用帶寬, 因此需要對優(yōu)化模型進(jìn)行如下限制:

1.4.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法(partical swarm optimization, PSO)[16]是一種智能優(yōu)化算法, 算法尋找待優(yōu)化問題最優(yōu)解的過程就是群體中個體之間通過信息共享協(xié)作、 不斷尋優(yōu)的過程. 算法優(yōu)點是參數(shù)較少、 實現(xiàn)簡單、 收斂快, 沒有相比于遺傳算法的交叉、 變異過程. PSO算法過程為: 設(shè)定群體的數(shù)量、 問題的維度、 粒子的屬性等參數(shù), 粒子即代表待優(yōu)化問題的潛在解, 在對n維問題進(jìn)行優(yōu)化時, 粒子i的位置表示為Pi=(p1,p2,…,pn), 速度表示為Vi=(v1,v2,…,vn); 設(shè)定初始條件后, 粒子進(jìn)入迭代更新過程, 粒子之間通過不斷信息共享, 調(diào)整自身參數(shù), 向個體最優(yōu)的位置Pbest和全體最優(yōu)位置Gbest靠攏.算法最終會因為粒子的這種行為得到一個問題的最優(yōu)解.其中粒子位置與速度的更新方式為

其中k表示第k代粒子,ω表示慣性因子,c1和c2分別表示個體向自身最優(yōu)和群體最優(yōu)學(xué)習(xí)程度的大小,r1和r2為獨立且均勻分布在0～1之間的數(shù).

1.4.3 DFSDPSO算法對粒子群的重定義

傳統(tǒng)PSO算法通常在連續(xù)空間上求解問題, 但對于SDN網(wǎng)絡(luò), 由于粒子是以離散形式分布的, 故為使PSO應(yīng)用到SDN網(wǎng)絡(luò)上, 需要將連續(xù)空間優(yōu)化問題映射到離散空間上.

首先, 初始粒子群體數(shù)量, 每個粒子的位置對應(yīng)一種大流調(diào)度方案, 將每個粒子的位置信息離散定義為Pk=(pk1,pk2,…,pkn).其中,pki只存在0,1兩種可能,pki=1表示第k次迭代中, 大流fi被選中從而不需要調(diào)度;pki=0表示需將大流fi加入到策略調(diào)度集合中.速度信息定義為Vk=(vk1,vk2,…,vkn),vki也只有0,1兩種可能,vki=1表示第k次迭代中, 同一維度的pki不更新;vki=0則表示同一維度的pki需要進(jìn)行更新.

其次, 定義適應(yīng)度函數(shù)計算方式.SDN網(wǎng)絡(luò)中粒子的適應(yīng)度評判直接影響最終調(diào)度結(jié)果. 本文重點解決離散優(yōu)化問題, 考慮對不超過約束的粒子, 將粒子位置信息中被選取的大流吞吐量總和作為粒子的適應(yīng)度, 對超過約束的粒子適應(yīng)度定義為-1. 因此, 選擇適應(yīng)度最高的, 即流調(diào)度策略中吞吐量最大的粒子作為最優(yōu)粒子. 粒子適應(yīng)度函數(shù)定義為

(7)

類似于連續(xù)空間的PSO算法, DFSDPSO算法分別重新規(guī)定了粒子的位置與位置之間、 速度與速度之間、 位置與速度之間3種更新操作.

1) 位置與位置之間的“同或”操作.

定義兩個粒子的位置分別為P1=(p11,p12,…,p1n)和P2=(p21,p22,…,p2n), 定義“·”為同或運算符, 將兩個位置進(jìn)行P1·P2運算, 比較兩個粒子在同一維度上的區(qū)別.如果p1i和p2i在i維度上的值相同, 即p1i=p2i, 則運算結(jié)果記為1, 反之記為0.

2) 速度與速度之間的“相加”操作.

定義兩個粒子的速度分別為V1=(v11,v12,…,v1n)和V2=(v21,v22,…,v2n), 定義“⊕”為相加運算符,α1,α2分別為速度V1,V2的調(diào)整參數(shù), 將兩個粒子速度進(jìn)行α1V1⊕α2V2運算計算下一時刻的速度Vk+1=(v(k+1)1,v(k+1)2,…,v(k+1)n), 將二者在同一維度上進(jìn)行加權(quán)求和, 其計算方法為

(8)

在式(8)中, 當(dāng)調(diào)整參數(shù)與相應(yīng)速度矢量的乘積和等于1時, 下一代粒子速度更新為1; 如果乘積和等于0, 則下一代粒子速度更新為0; 當(dāng)乘積和為[0,1]內(nèi)時, 例如, 0.2(1,0,1,0)⊕0.8[1,1,1,0], 結(jié)果為(1,“*”,1,0), 其中“*”的取值不確定, 則“*”取值就以0.2的概率取0, 0.8的概率取1.

3) 速度與位置之間的“相乘”操作.

定義粒子的當(dāng)前位置Pk=(pk1,pk2,…,pkn)和下一代的速度Vk+1=(v(k+1)1,v(k+1)2,…,v(k+1)n), 定義“?”為相乘運算符, 則粒子的下一代位置計算方式為Pk+1=Pk?Vk+1,

(9)

在式(9)中, 如果第i維度上的下一刻速度值為1, 則下一刻粒子的位置不發(fā)生改變; 如果下一刻速度值為0, 則下一刻粒子位置取其負(fù)值.

通過上述定義, 最終新的粒子更新過程可被解釋為

1.4.4 融合Metropolis準(zhǔn)則

本文引入SA算法中核心準(zhǔn)則Metropolis, 使其在計算最優(yōu)調(diào)度策略時能使粒子以一定的概率接受適應(yīng)度較差的位置, 使產(chǎn)生的調(diào)度策略更具有多樣性. Metropolis更新公式為

(12)

其中P為接受較差適應(yīng)度的概率,T表示當(dāng)前迭代次數(shù)的溫度,f(k),f(k+1)分別表示當(dāng)前代的適應(yīng)度和下一代的適應(yīng)度.如果下一代適應(yīng)度比當(dāng)前代高, 則以1的概率接受該適應(yīng)度; 如果下一代的適應(yīng)度比當(dāng)前代低, 則在[0,1]內(nèi)隨機(jī)選取一個數(shù)d, 當(dāng)d小于P中的exp項時, 則接受下一代的較差適應(yīng)度, 否則繼續(xù)使用當(dāng)前代的適應(yīng)度.為實現(xiàn)模擬退火算法中的降溫過程, 將溫度更新公式記為

Tnext=Tnow×λ,

(13)

其中:Tnext表示下一次迭代時使用的溫度;Tnow表示當(dāng)前迭代的溫度;λ表示降溫系數(shù),λ值通常在[0.95,0.99]內(nèi).

1.4.5 策略集合計算

通過DFSDPSO算法產(chǎn)生的選取方案, 確定需要重調(diào)度的大流f.實現(xiàn)過程為: 對大流f利用K條最短路徑(KSP)算法[17]計算f的K條路徑, 從f的K條最短路徑中找到一條路徑R, 路徑R滿足其最小可用帶寬與f吞吐量差值最大, 將R作為f的新傳輸路徑.

2 實驗與分析

2.1 實驗環(huán)境與參數(shù)

為驗證DFSDPSO算法的有效性, 實驗中SDN控制器采用Ryu控制器[18], 實驗拓?fù)浯罱ㄔ贛ininet仿真平臺[19]上.

網(wǎng)絡(luò)拓?fù)涞母鳁l鏈路帶寬均設(shè)為10 Mbit/s, 設(shè)置16臺服務(wù)器, OVS最大隊列長度設(shè)為1 000. 使用Iperf和hping3兩種工具生成UDP數(shù)據(jù)流模擬數(shù)據(jù)中心流量[20]. 利用hping3工具產(chǎn)生小流, 即小流速率為0～1 Mbit/s. 利用Iperf工具產(chǎn)生大流, 大流速率為1～9 Mbit/s, 數(shù)據(jù)中心通信模式采取隨機(jī)通信模式. 參數(shù)設(shè)置如下: 種群大小為50, 粒子維度為n, 迭代次數(shù)為100,α1=0.1,α2=0.2,α3=0.7, 初始溫度為100, 降溫系數(shù)為0.99, 最短路徑數(shù)為4.

2.2 實驗結(jié)果與分析

本文選取大流的平均時延抖動、 整體網(wǎng)絡(luò)吞吐量和平均鏈路利用率作為評價指標(biāo), 將DFSDPSO算法與BFlows,Hedera,ECMP算法進(jìn)行實驗對比.

2.2.1 大流時延抖動

向網(wǎng)絡(luò)中打入速率為1～9 Mbit/s的大流, 不同算法的時延抖動結(jié)果如圖3所示. 由圖3可見: ECMP算法的時延最大, 因為有多個大流被分配到相同路徑導(dǎo)致鏈路擁塞, 時延增大; 而Hedera算法因頻繁換路, 無法全面衡量各路徑的鏈路狀態(tài), 導(dǎo)致時延較大; BFlows算法對于路徑的選擇依靠鏈路的大流數(shù)量, 也可以較好地避免大流碰撞, 但其忽略了大流的流速, 產(chǎn)生一定的抖動; 而對于DFSDPSO算法, 部分大流調(diào)度策略較好地減少了時延抖動. DFSDPSO,ECMP,Hedera和BFlows四種算法的大流平均抖動時延分別為6.03,10.29,8.39,6.70 ms, DFSDPSO算法相比于ECMP,Hedera和BFlows算法的大流平均抖動時延分別減少了41.39%,28.13%和9.99%, 表明DFSDPSO算法對減少大流的平均抖動時延效果較好.

a. DFSDPSO算法; b. BFlows算法; c. Hedera算法; d. ECMP算法.圖3 不同算法大流平均時延抖動Fig.3 Average delay jitter for large streams of different algorithms

2.2.2 整體網(wǎng)絡(luò)吞吐量

向網(wǎng)絡(luò)中分別打入1～9 Mbit/s的大流, 實驗結(jié)果如圖4所示. 由圖4可見, 當(dāng)鏈路負(fù)載值為1～3 Mbit/s時, 4種算法的差別較小, 都能實現(xiàn)較大網(wǎng)絡(luò)吞吐量. 隨著鏈路負(fù)載的逐漸增大, DFSDPSO算法的整體網(wǎng)絡(luò)吞吐量明顯優(yōu)于ECMP,Hedera和BFlows算法, 這是因為ECMP算法在分配流量轉(zhuǎn)發(fā)時僅提供靜態(tài)流量分配從而導(dǎo)致鏈路擁擠, 后續(xù)的吞吐量減少; Hedera算法在路徑選擇上完全隨機(jī)化, 吞吐量無法達(dá)到最優(yōu); BFlows算法在路徑的選擇上只關(guān)注鏈路上的大流數(shù)目, 未關(guān)注大流的吞吐量從而導(dǎo)致大流碰撞, 降低了吞吐量; DFSDPSO算法通過得到的最優(yōu)調(diào)度策略對部分大流進(jìn)行調(diào)度, 但并不是對所有大流調(diào)度, 避免了大量調(diào)度引起的鏈路擁塞, 提高了整個網(wǎng)絡(luò)的吞吐量. DFSDPSO,ECMP,Hedera和BFlows 4種算法的平均吞吐率分別為287.29,236.75,272.22,277.15, DFSDPSO算法相比于ECMP,Hedera,BFlows算法的性能分別提升21.34%,5.5%,3.6%, 表明DFSDPSO算法對優(yōu)化吞吐量性能良好.

圖4 不同鏈路負(fù)載網(wǎng)絡(luò)吞吐量Fig.4 Network throughput for different link loads

2.2.3 平均鏈路利用率

平均鏈路利用率為整體網(wǎng)絡(luò)中所有鏈路利用率的和平均, 其計算公式為

(14)

其中:m為鏈路總數(shù);bi為第i個鏈路的已用帶寬;Bw為一條鏈路的總帶寬, 即10 Mbit/s. 不同鏈路負(fù)載下的平均鏈路利用率如圖5所示.

圖5 不同鏈路負(fù)載下的平均鏈路利用率Fig.5 Average link utilization under different link loads

由圖5可見, 剛開始4種算法的平均鏈路利用率沒有明顯區(qū)別, 但隨著流量負(fù)載的逐漸加大, 區(qū)別逐漸增大. 由于ECMP算法只是靜態(tài)轉(zhuǎn)發(fā), 所以其鏈路利用率最低, 曲線也較平緩. Hedera算法中調(diào)度的流和路徑具有不確定性, 導(dǎo)致鏈路擁塞. BFlows算法因為其在計算傳輸路徑時可能會計算迂回路徑, 表現(xiàn)與Hedera算法相差不大. 對于DFSDPSO算法僅需對少量的流進(jìn)行調(diào)度, 并且在滿足最大吞吐量的前提下對小流調(diào)度, 增大了鏈路的利用率. 所有負(fù)載的平均鏈路利用率列于表1. 由表1可見, 相比于ECMP,Hedera和BFlows算法49.32%,56.71%和57.59%的平均鏈路利用率, DFSDPSO算法為59.85%, 其算法效率更優(yōu), 說明DFSDPSO算法對于優(yōu)化鏈路利用率效果也較好.

表1 平均鏈路利用率Table 1 Average link utilization

上述實驗結(jié)果表明, 本文DFSDPSO算法在3個指標(biāo)上都優(yōu)于其他算法, 且隨著數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載逐漸增大, 其效果更優(yōu)越.

綜上所述, 針對數(shù)據(jù)中心網(wǎng)絡(luò)中流量路徑分配不合理、 易導(dǎo)致大流沖突的問題, 本文提出了一種基于離散粒子群的SDN動態(tài)流調(diào)度(DFSDPSO)算法. 算法對OpenFlow協(xié)議[21]下所支持的Ryu控制器實現(xiàn)對底層鏈路信息的感知, 以最大化吞吐率為離散粒子群優(yōu)化算法的優(yōu)化目標(biāo)重新定義離散模型, 將其應(yīng)用到底層大流調(diào)度優(yōu)化問題上. 與ECMP,Hedera和BFlows算法進(jìn)行對比, DFSDPSO算法取得了更優(yōu)的實驗效果, 能更好地實現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡.