基于離散粒子群的SDN動態流調度算法

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

(1. 東北石油大學 計算機與信息技術學院, 黑龍江 大慶 163318;2. 東北石油大學 現代教育技術中心, 黑龍江 大慶 163318)

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

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

針對目前數據中心流量特征以及負載均衡方案的不足, 本文提出一種基于離散粒子群優化的動態流調度DFSDPSO(dynamic flow scheduling based discrete partical swarm optimization)算法, 結合離散粒子群算法和模擬退火算法(simulated annealing, SA)[15]中的Metropolis準則, 以最大化網絡吞吐量為目標, 通過算法選擇對大流進行調度完成流量均衡.

1 算法設計

1.1 設計思想

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

圖1 算法設計流程Fig.1 Flow chart of algorithm design

1.2 流程設計

通過在SDN控制器中完成相關部署, DFSDPSO算法整體架構如圖2所示, 由SDN控制器和拓撲樣例Fat-Tree兩個模塊組成. 該架構中最主要的模塊是SDN控制器模塊, SDN控制器模塊包括5個子模塊, 分別是拓撲感知模塊、 鏈路信息感知模塊、 大流采集模塊、 基于離散粒子群優化算法的策略計算模塊和策略集合處理模塊.

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

1.3 控制器模塊設計

1.3.1 拓撲感知模塊

拓撲感知模塊由控制器通過鏈路發現協議LLDP實現, 控制器通過構造Packet_Out消息向其控制的邊緣交換機(OVS)下發LLDP數據包, 匯總LLDP響應消息獲取相關連接信息.

1.3.2 鏈路信息感知模塊

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

1.3.3 大流采集模塊

根據Hedera檢測設置篩選大流閾值標準, 如超過鏈路總帶寬10%為大流. 通過控制器收集邊緣交換機統計的流表信息, 將流表信息單位換算成流量信息, 篩選出所有大流記錄.

1.3.4 策略計算模塊

從大流采集模塊獲取輸入后, 利用DFSDPSO算法對大流進行篩選, 通過篩選出滿足優化目標的大流, 返回相關調度策略, 告知后一層模塊, 提供策略輸入.

1.3.5 策略集合處理模塊

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

1.4 大流調度設計

1.4.1 數學模型建立

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

DFSDPSO算法的優化目標為保證整體網絡吞吐量最大, 即挑選出滿足網絡吞吐量最大的流量, 并且挑選過程中要滿足每條鏈路的大流集合吞吐量之和不大于該鏈路的可用帶寬, 因此需要對優化模型進行如下限制:

1.4.2 粒子群優化算法

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

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

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

傳統PSO算法通常在連續空間上求解問題, 但對于SDN網絡, 由于粒子是以離散形式分布的, 故為使PSO應用到SDN網絡上, 需要將連續空間優化問題映射到離散空間上.

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

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

(7)

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

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

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

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

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

(8)

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

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

定義粒子的當前位置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, 則下一刻粒子的位置不發生改變; 如果下一刻速度值為0, 則下一刻粒子位置取其負值.

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

1.4.4 融合Metropolis準則

本文引入SA算法中核心準則Metropolis, 使其在計算最優調度策略時能使粒子以一定的概率接受適應度較差的位置, 使產生的調度策略更具有多樣性. Metropolis更新公式為

(12)

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

Tnext=Tnow×λ,

(13)

其中:Tnext表示下一次迭代時使用的溫度;Tnow表示當前迭代的溫度;λ表示降溫系數,λ值通常在[0.95,0.99]內.

1.4.5 策略集合計算

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

2 實驗與分析

2.1 實驗環境與參數

為驗證DFSDPSO算法的有效性, 實驗中SDN控制器采用Ryu控制器[18], 實驗拓撲搭建在Mininet仿真平臺[19]上.

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

2.2 實驗結果與分析

本文選取大流的平均時延抖動、 整體網絡吞吐量和平均鏈路利用率作為評價指標, 將DFSDPSO算法與BFlows,Hedera,ECMP算法進行實驗對比.

2.2.1 大流時延抖動

向網絡中打入速率為1～9 Mbit/s的大流, 不同算法的時延抖動結果如圖3所示. 由圖3可見: ECMP算法的時延最大, 因為有多個大流被分配到相同路徑導致鏈路擁塞, 時延增大; 而Hedera算法因頻繁換路, 無法全面衡量各路徑的鏈路狀態, 導致時延較大; BFlows算法對于路徑的選擇依靠鏈路的大流數量, 也可以較好地避免大流碰撞, 但其忽略了大流的流速, 產生一定的抖動; 而對于DFSDPSO算法, 部分大流調度策略較好地減少了時延抖動. 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 整體網絡吞吐量

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

圖4 不同鏈路負載網絡吞吐量Fig.4 Network throughput for different link loads

2.2.3 平均鏈路利用率

平均鏈路利用率為整體網絡中所有鏈路利用率的和平均, 其計算公式為

(14)

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

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

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

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

上述實驗結果表明, 本文DFSDPSO算法在3個指標上都優于其他算法, 且隨著數據中心網絡負載逐漸增大, 其效果更優越.

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