軟件定義網(wǎng)絡(luò)下大象流擁塞路由調(diào)度算法

劉向舉，徐楊洋，方賢進(jìn)，趙 犇

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

隨著當(dāng)今網(wǎng)絡(luò)的飛速發(fā)展，網(wǎng)絡(luò)中業(yè)務(wù)的承載量也在逐漸增加，互聯(lián)網(wǎng)應(yīng)面向業(yè)務(wù)做出快速的應(yīng)用請求來滿足業(yè)務(wù)需要，促使業(yè)務(wù)產(chǎn)生多方向、多層度的網(wǎng)絡(luò)需求變化.傳統(tǒng)網(wǎng)絡(luò)存在網(wǎng)絡(luò)部署困難、管理復(fù)雜、流量難以控制、難以可視化、分布式架構(gòu)出現(xiàn)瓶頸、設(shè)備不可編程等缺陷.在這樣的背景下，產(chǎn)生一種新型網(wǎng)絡(luò)架構(gòu)——軟件定義網(wǎng)絡(luò)(software defined network,SDN).SDN的出現(xiàn)促使研究人員可以在不斷增長的網(wǎng)絡(luò)規(guī)模中進(jìn)行集中式自動化的管理，在大型數(shù)據(jù)中心中部署大量的新興業(yè)務(wù)，同時(shí)使一些新型的數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)淙缗謽鋄1]、Bcube、VL2(virtual layer-2)、Helios等得以實(shí)現(xiàn).在數(shù)據(jù)中心網(wǎng)絡(luò)(data center network,DCN)[2-3]中同時(shí)存在著兩種不同類型的流量，分別為數(shù)據(jù)占比小而承載數(shù)據(jù)量大的大象流[4-5]與數(shù)據(jù)占比大而承載數(shù)據(jù)量小的老鼠流，通過流分類區(qū)分出大象流是解決DCN中流量調(diào)度的首要工作.SDN在解決DCN中大象流擁塞路由調(diào)度時(shí)，利用SDN控制器，根據(jù)業(yè)務(wù)需求對轉(zhuǎn)發(fā)設(shè)備進(jìn)行轉(zhuǎn)發(fā)策略的定義，同時(shí)在控制器內(nèi)進(jìn)行全局網(wǎng)絡(luò)鏈路狀態(tài)的實(shí)時(shí)監(jiān)測，依據(jù)網(wǎng)絡(luò)狀態(tài)變化，通過轉(zhuǎn)發(fā)策略選擇空閑鏈路完成對DCN中流量的調(diào)度，從而提高網(wǎng)絡(luò)質(zhì)量.在DCN中任意主機(jī)間通過多條路徑選擇最優(yōu)下發(fā)路徑避免鏈路擁塞，進(jìn)行高效的流調(diào)度來提高帶寬和網(wǎng)絡(luò)吞吐量是一個(gè)具有挑戰(zhàn)性的問題[6-7].

目前，研究者將SDN與DCN結(jié)合來解決傳統(tǒng)網(wǎng)絡(luò)中靜態(tài)路由的問題.等價(jià)多路徑(equal-cost multi-path,ECMP)[8]算法是解決DCN中路由問題的傳統(tǒng)算法，使用ECMP算法進(jìn)行路由下發(fā)時(shí)，將產(chǎn)生多條相同開銷的路由項(xiàng).當(dāng)某路徑出現(xiàn)問題時(shí)，通過其余相同開銷的路由項(xiàng)替換實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，但由于各路徑間存在帶寬、時(shí)延等開銷不一致，產(chǎn)生網(wǎng)路負(fù)載不唯一，且ECMP算法無法進(jìn)行擁塞感知與大小流分類等問題，容易將流分散到剩余帶寬較小的鏈路上，加劇鏈路的擁塞.郝建華等[9]提出基于路徑關(guān)鍵度的重路由(rerouting based on path criticality,RPC)算法，根據(jù)啟發(fā)式算法將鏈路負(fù)載與時(shí)延作為評價(jià)指標(biāo)解決鏈路擁塞問題，算法對時(shí)延以及吞吐量有一定的改善，但主機(jī)間通信模式的選擇及路徑中評價(jià)參數(shù)的選取不完善.Al-fares等[10]利用全局首次適應(yīng)(global fit first,GFF)算法運(yùn)用在大象流調(diào)度中，通過對鏈路負(fù)載計(jì)算，將大象流動態(tài)調(diào)度到鏈路負(fù)載較低的路徑上避免擁塞，但由于路徑選擇上的隨機(jī)性以及控制器和交換機(jī)之間的頻繁交互，指令開銷加大.付應(yīng)輝等[11]為避免鏈路擁塞的情況，通過對鏈路進(jìn)行評估，充分利用網(wǎng)絡(luò)剩余帶寬，根據(jù)鏈路剩余帶寬來選擇最優(yōu)的轉(zhuǎn)發(fā)路徑，算法的穩(wěn)定性得到一定地提升，但僅局限于數(shù)據(jù)流的帶寬，未多方面考慮傳輸性質(zhì)以及評價(jià)指標(biāo)對網(wǎng)絡(luò)路徑選擇的影響.張偉東等[12]提出在DCN下進(jìn)行流分類后對擁塞控制算法的研究，主要選擇鏈路利用率以及時(shí)延作為路由權(quán)值的計(jì)算，通過選擇權(quán)值小的路徑作為最優(yōu)路徑進(jìn)行數(shù)據(jù)流地轉(zhuǎn)發(fā)提高網(wǎng)絡(luò)質(zhì)量，但未考慮主機(jī)間的通信模式.Lan等[13]根據(jù)單鏈路的動態(tài)負(fù)載均衡路徑優(yōu)化(dynamic load-balanced path optimization,DLPO)算法與多鏈路DLPO算法結(jié)合成動態(tài)負(fù)載平衡優(yōu)化算法，在流的傳輸過程中改變流的路徑來避免網(wǎng)絡(luò)擁塞，有效地提高了鏈路利用率和吞吐量.Cui等[14]提出一種本地的、輕量級的在DCN中用于自適應(yīng)分組交換的分布式流調(diào)度(distributed flow scheduling,DiFS)協(xié)議.通過交換機(jī)間的控制命令來實(shí)現(xiàn)DiFS交換機(jī)間的相互協(xié)作，減少流量沖突，避免本地和遠(yuǎn)程碰撞，實(shí)現(xiàn)流到鏈路的平衡.彭大芹等[15]通過對鏈路實(shí)時(shí)狀態(tài)的收集，根據(jù)鏈路特征，將大象流依據(jù)路徑權(quán)重來進(jìn)行路徑選擇，對于老鼠流則根據(jù)剩余帶寬進(jìn)行路由來提高網(wǎng)絡(luò)質(zhì)量，算法本身考慮性能不充分，沒從多角度進(jìn)行性能分析.農(nóng)黃武等[16]在SDN架構(gòu)下提出實(shí)用性算法，通過控制器進(jìn)行狀態(tài)信息監(jiān)控來實(shí)現(xiàn)最優(yōu)路徑下發(fā).何東澤等[17]提出一種基于SDN的數(shù)據(jù)中心多路徑負(fù)載均衡算法，該算法通過鏈路狀態(tài)信息的收集，以蟻群算法作為尋路算法選擇最優(yōu)路徑.但兩者未考慮大小流分類問題以及鏈路是否出現(xiàn)擁塞和擁塞處理.馬樞清等[18]采用粒子群優(yōu)化算法，通過對粒子聚合度的判斷，避免產(chǎn)生局部最優(yōu)問題，減輕網(wǎng)絡(luò)負(fù)載.Zhang等[19]在研究DCN中流調(diào)度問題，通過穩(wěn)定匹配理論為流調(diào)度問題建模，證明了該問題為非確定性多項(xiàng)式難問題，通過尋找大象流與交換機(jī)之間穩(wěn)定匹配項(xiàng)，使得該方法在流的完成時(shí)間上有所降低，提高網(wǎng)絡(luò)質(zhì)量，但未考慮網(wǎng)絡(luò)中的鏈路問題.劉振鵬等[20]提出的動態(tài)流量調(diào)度策略(dynamic traffic scheduling of network load,DTSNL)根據(jù)帶寬占比為大象流進(jìn)行路由調(diào)度，提高網(wǎng)絡(luò)質(zhì)量.黃冰[21]提出的面向服務(wù)質(zhì)量的動態(tài)流量調(diào)度策略(dynamic scheduling flows,DSFlows)，綜合考慮路徑可用帶寬、路徑時(shí)延、路徑帶寬均衡制定路由策略，但未考慮鏈路擁塞的處理狀況.

針對上述研究中未考慮大象流流量下鏈路擁塞以及主機(jī)間通信模式選擇的問題，本文提出在SDN架構(gòu)下大象流的擁塞路由調(diào)度算法.將路徑帶寬最優(yōu)與路徑時(shí)延的歸一化作為多目標(biāo)評價(jià)指標(biāo)模型，采用改進(jìn)的帶精英策略的非支配排序遺傳(bandwidth delay-non-dominated sorting genetic algorithm-II,BD-NSGA2)算法保證全局搜索以及增加個(gè)體間遺傳機(jī)會，通過最佳路徑的計(jì)算將大象流下發(fā)到空閑鏈路上，以此避免鏈路擁塞.

1 模型構(gòu)建

擁塞路由調(diào)度問題的解決是建立在網(wǎng)絡(luò)拓?fù)浼熬W(wǎng)絡(luò)實(shí)時(shí)狀態(tài)約束下，通過控制器與交換機(jī)之間的交互，再根據(jù)擁塞路由調(diào)度功能，構(gòu)建出大象流擁塞路由調(diào)度模型.所選擇的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為典型的胖樹拓?fù)浣Y(jié)構(gòu)，將網(wǎng)絡(luò)拓?fù)錁?gòu)造成有向圖G=(N,L)結(jié)構(gòu)，N表示網(wǎng)絡(luò)中交換機(jī)節(jié)點(diǎn)的集合，N={n1,n2,…,nz}，其中z=|N|表示交換機(jī)個(gè)數(shù)；L表示網(wǎng)路中鏈路的集合，L={l1,l2,…,le}，其中e=|L|表示鏈路個(gè)數(shù).基于BD-NSGA2算法的擁塞路由調(diào)度主要包括五大模塊：網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)、流量監(jiān)控、鏈路時(shí)延監(jiān)測、流分類以及鏈路擁塞判斷，模塊架構(gòu)如圖1所示.

圖1 BD-NSGA2模塊架構(gòu)Fig.1 Module architecture of BD-NSGA2

1.1 功能模塊

1.1.1 網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn) 用于網(wǎng)絡(luò)初始化，通過周期性向網(wǎng)絡(luò)拓?fù)渲懈鹘粨Q機(jī)發(fā)送鏈路層發(fā)現(xiàn)協(xié)議(link layer discovery protocol,LLDP)數(shù)據(jù)包獲取交換機(jī)間的網(wǎng)絡(luò)連接信息，進(jìn)而獲取全局網(wǎng)絡(luò)拓?fù)湫畔?

1.1.2 流量監(jiān)控 首先通過Ryu控制器進(jìn)行SimpleMonitor對象的初始化，然后以周期t運(yùn)轉(zhuǎn)_monitor方法，并向OpenFlow交換機(jī)發(fā)送OFPFlowStatsRequest請求與OFPPortStatsRequest請求，OpenFlow交換機(jī)收到請求后向控制器回復(fù)相應(yīng)的統(tǒng)計(jì)消息回復(fù)報(bào)文.控制器解析消息得到流量統(tǒng)計(jì)信息txpkts、txbytes、txerror，運(yùn)用流量統(tǒng)計(jì)信息計(jì)算鏈路速率、丟包率以及鏈路可用帶寬等.

定義1鏈路i速率計(jì)算公式：

(1)

定義2鏈路i丟包率計(jì)算公式：

(2)

定義3鏈路i可用帶寬：

Bi=Bmax-sri(Δt).

(3)

定義4路徑p可用帶寬：

Bp=min{B1,B2,B3,…,Bn}.

(4)

式(1)～(4)中i滿足條件i∈[1,n]；txbytes(t+Δt)與txbytes(t)分別表示t+Δt時(shí)刻與t時(shí)刻傳輸?shù)淖止?jié)數(shù)；txerror(t+Δt)與txerror(t)分別表示t+Δt時(shí)刻與t時(shí)刻的丟包數(shù)；txpkts(t+Δt)與txpkts(t)分別表示t+Δt時(shí)刻與t時(shí)刻數(shù)據(jù)包的傳輸數(shù)量；Bmax為鏈路端口最大帶寬.

1.1.3 鏈路時(shí)延監(jiān)測 通過Ryu控制器在網(wǎng)絡(luò)鏈路中的LLDP數(shù)據(jù)包，產(chǎn)生LLDP時(shí)延，其中Tlldp1(k)與Tlldp2(k+1)為交換機(jī)與控制器間的LLDP時(shí)延，Techoa與Techob為ECHO報(bào)文測試的控制器到交換機(jī)的往返時(shí)延.

定義5鏈路平均時(shí)延：

(5)

定義6路徑時(shí)延：

(6)

1.1.4 流分類 在DCN中存在兩類流量，其中一類為由數(shù)據(jù)備份產(chǎn)生對帶寬需求和時(shí)延敏感的大象流，另一類由Web服務(wù)以及分布式計(jì)算等進(jìn)程產(chǎn)生對網(wǎng)絡(luò)中時(shí)延較為敏感的老鼠流.本文主要根據(jù)流量監(jiān)控，以Δt時(shí)間內(nèi)流量大小與鏈路可用帶寬的比值w進(jìn)行大小流劃分，并將w>0.1時(shí)的數(shù)據(jù)流定為大象流.

(7)

式中txbytes(t+△t)-txbytes(t)為交換機(jī)在時(shí)間Δt內(nèi)的數(shù)據(jù)流的字節(jié)數(shù)，且w∈(0,1).

1.1.5 鏈路擁塞判斷 檢測DCN中鏈路是否發(fā)生鏈路擁塞情況，在獲取網(wǎng)絡(luò)狀態(tài)信息后，通過SDN控制器與匯聚層交換機(jī)進(jìn)行信息交互，獲取鏈路負(fù)載信息，根據(jù)鏈路最小帶寬與最大帶寬的比值進(jìn)行鏈路擁塞判斷.鏈路負(fù)載評判標(biāo)準(zhǔn)l為

(8)

當(dāng)l<0.3時(shí)，鏈路處于擁塞狀態(tài)，并將擁塞鏈路記錄保存.

1.2 路徑評價(jià)指標(biāo)模型

在大象流進(jìn)行流量調(diào)度過程中，對時(shí)延和帶寬較為敏感，因此鏈路擁塞情況需根據(jù)路徑帶寬最優(yōu)以及路徑時(shí)延進(jìn)行綜合考慮，由于指標(biāo)單位的不同，為了構(gòu)成更好的路徑評價(jià)指標(biāo)，需對兩者進(jìn)行歸一化處理.

定義7路徑帶寬最優(yōu)歸一化：

(9)

定義8路徑時(shí)延歸一化：

(10)

當(dāng)f1與f2越大，鏈路可用帶寬越大，路徑時(shí)延越小，對路徑選擇的能力越強(qiáng).

目標(biāo)函數(shù)：最大化f1∪f2.

約束條件：

(11)

(12)

(13)

(14)

式(11)表示鏈路流量小于或等于鏈路容量；式(12)滿足鏈路中流量守恒定律；式(13)表示從sk流出的流量與dk流入的流量相等；式(14)表示除sk、dk外，在交換機(jī)節(jié)點(diǎn)流入的流量值等于流出的流量值.

2 BD-NSAG2算法設(shè)計(jì)

帶精英策略的非支配排序遺傳(non-dominated sorting genetic algorithm-II,NSGA2)算法[22]是解決多目標(biāo)優(yōu)化的基準(zhǔn)算法，該算法將種群中優(yōu)秀個(gè)體大概率保留，提高種群中個(gè)體的優(yōu)質(zhì)性，同時(shí)減少收斂時(shí)間.BD-NSGA2算法是建立在NSGA2算法基礎(chǔ)之上，對NSGA2算法中存在的全局性搜索無法保證以及個(gè)體遺傳機(jī)會不足等缺點(diǎn)，BD-NSGA2算法通過標(biāo)準(zhǔn)差擁擠度計(jì)算、非支配個(gè)體層制約的精英策略以及算數(shù)交叉算子的交叉方式三方面進(jìn)行改進(jìn)，避免算法陷入局部最優(yōu).將DCN中Δt時(shí)間內(nèi)流量大小與鏈路可用帶寬比值形成閾值對大小流進(jìn)行分類，區(qū)分出大象流.在大象流的流量調(diào)度中，通過鏈路負(fù)載評判標(biāo)準(zhǔn)對鏈路進(jìn)行擁塞判斷.鏈路發(fā)生擁塞時(shí)，首先采用K最短路徑計(jì)算出k條初始路徑，然后采用BD-NSGA2算法解決大象流擁塞路由調(diào)度問題.BD-NSGA2算法流程如圖2所示.

圖2 BD-NSGA2算法流程Fig.2 Flow diagram of BD-NSGA2 algorithm

2.1 初始化路由

表1 KSP算法Tab.1 KSP algorithm

2.2 BD-NSGA2算法

在大象流進(jìn)行流量下發(fā)的過程中，當(dāng)鏈路發(fā)生擁塞問題時(shí)，BD-NSGA2算法可以對資源進(jìn)行重新分配，選擇網(wǎng)絡(luò)中空閑鏈路進(jìn)行下發(fā)，解決鏈路擁塞的問題.該算法核心在于快速非支配排序、擁擠度計(jì)算、精英策略和交叉變異.

2.2.1 快速非支配排序 設(shè)種群大小為P，每個(gè)個(gè)體為p、解個(gè)體數(shù)np以及個(gè)體支配的解的集合Sp.通過對種群的遍歷，找到當(dāng)np=0時(shí)，放入未被其余解所支配的集合fro[1]中.再去遍歷fro[1]中每個(gè)個(gè)體q對應(yīng)Sq集合中的解，將Sq中解的個(gè)體數(shù)nq減1，遍歷完一次進(jìn)行fro[i+1]，其中若有解對應(yīng)nq值為0，則保存至fro[i+1]，并賦予非支配序irank.重復(fù)步驟，直至所有解被劃分.

2.2.2 擁擠度改進(jìn) 對于每個(gè)點(diǎn)的初始擁擠度設(shè)置為0，令邊界上的兩個(gè)個(gè)體擁擠度為無窮大.

f[0]distance=f[i-1]distance=∞.

(15)

NSGA2算法僅考慮相鄰個(gè)體間的距離，但解集的分布度關(guān)乎不同子群間的擁擠距離，當(dāng)解集分布均勻時(shí)，個(gè)體間遺傳機(jī)會增加，有利于保持分布度.因此提出考慮標(biāo)準(zhǔn)差的擁擠距離公式，對種群其余個(gè)體利用標(biāo)準(zhǔn)差計(jì)算:

(16)

2.2.3 精英策略 傳統(tǒng)的精英策略為精英保留策略，在Pareto最優(yōu)層個(gè)體進(jìn)行大量的交叉變異，而非支配層中的個(gè)體數(shù)量較少，導(dǎo)致目標(biāo)偏移產(chǎn)生局部收斂，因此通過對非支配層個(gè)體數(shù)進(jìn)行制約來解決Pareto最優(yōu)層個(gè)體數(shù)過多所產(chǎn)生的局部收斂問題，具體解決方法如下：

(17)

式中El為第l非支配層個(gè)體數(shù)，γ∈[0,1]為衰減率，σ為迭代次數(shù).

2.2.4 隨機(jī)排序選擇 BD-NSGA2算法根據(jù)快速非支配排序以及擁擠度的計(jì)算，對種群中個(gè)體含有非支配序irank和擁擠度f[i]Distance進(jìn)行排序，從而選擇種群中個(gè)體數(shù).通過隨機(jī)選擇，設(shè)每次迭代時(shí)種群中個(gè)體的數(shù)量為固定N，每次從中選出最優(yōu)解，如Rank0的解，同時(shí)滿足：

(18)

2.2.5 交叉改進(jìn) NSGA2算法是采用模擬的二進(jìn)制交叉方式(simulated binary crossover,SBX)交叉產(chǎn)生新個(gè)體，這種交叉方式無法保證種群的多樣性計(jì)算以及全局性搜索，通過算數(shù)交叉算子進(jìn)行交叉換位產(chǎn)生新個(gè)體.進(jìn)入交叉操作時(shí)，隨機(jī)從父種群中選擇兩個(gè)父本進(jìn)行位置信息的交換來產(chǎn)生子代個(gè)體，對第k+1代個(gè)體的位置計(jì)算為

(19)

式中Qc1,k+1和Qc2,k+1為父本交叉生成的第k+1代個(gè)體的位置信息；Qc,k為當(dāng)前位置；Qbest,k為當(dāng)前最優(yōu)位置；μ1∈[0,1],μ2∈[0,1]且μ1+μ2=1.

2.2.6 多項(xiàng)式變異 變異操作基于自然界染色體變異產(chǎn)生新個(gè)體，本文的變異為多項(xiàng)式變異，從父種群中選擇一個(gè)父本Pk產(chǎn)生第k+1代個(gè)體的計(jì)算為

(20)

(21)

式中?∈[0,1]，ηm為變異分布指數(shù).

2.3 BD-NSGA2算法流程及算法復(fù)雜度分析

BD-NSGA2算法在解決大象流鏈路擁塞調(diào)度中，采用KSP算法進(jìn)行初始化路由，根據(jù)式(8)進(jìn)行鏈路擁塞判斷，當(dāng)鏈路發(fā)生擁塞時(shí)，根據(jù)式(9)(10)作為多目標(biāo)評價(jià)指標(biāo)模型，同時(shí)應(yīng)滿足式(11)～(14)的約束條件，再根據(jù)2.2節(jié)的內(nèi)容進(jìn)行路由部署，得到最優(yōu)路徑.BD-NSGA2算法流程如表2所示.

表2 BD-NSGA2算法Tab.2 BD-NSGA2 algorithm

BD-NSGA2算法首先通過步驟1的KSP算法計(jì)算k條初始路由路徑，算法的時(shí)間復(fù)雜度為O(kN2)，由于k路徑數(shù)遠(yuǎn)小于拓?fù)鋱D的節(jié)點(diǎn)數(shù)，因此可認(rèn)為KSP初始化算法的時(shí)間復(fù)雜度為O(N2)；步驟2的時(shí)間復(fù)雜度主要與鏈路個(gè)數(shù)e與種群規(guī)模N有關(guān)，非支配排序的時(shí)間復(fù)雜度為O(N2)，擁擠度的時(shí)間復(fù)雜度為O(eNlogN)；步驟3的時(shí)間復(fù)雜度取決于迭代次數(shù)σ與種群規(guī)模N，精英策略的時(shí)間復(fù)雜度為O(σNlogN).因此BD-NSGA2算法的最大時(shí)間復(fù)雜度為O(N2).BD-NSGA2算法經(jīng)過有限次迭代后收斂，具有實(shí)時(shí)性與有效性.

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)平臺

采用仿真平臺為Mininet，控制器的選擇為Ryu 4.34，編程語言為Python 2.7.實(shí)驗(yàn)機(jī)器配置為Intel(R) Core(TM) i7-10710U CPU @1.10 GHz,16.0 GB RAM，操作系統(tǒng)為Ubuntu16.0.4-desktop-64 4.0 GB.實(shí)驗(yàn)拓?fù)洳捎萌鐖D3所示的胖樹(k=4)數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌撏負(fù)涔灿?個(gè)Pod，任意兩個(gè)Pod之間存在4條路徑.

3.2 參數(shù)設(shè)置

實(shí)驗(yàn)中KSP算法設(shè)置初始路徑為13條，網(wǎng)絡(luò)性能測試時(shí)長為60 s，數(shù)據(jù)流的發(fā)送速率以10 Mbit/s為步長，Ryu控制器的監(jiān)督時(shí)間設(shè)置為5 s，拓?fù)浒l(fā)現(xiàn)周期設(shè)置為2 s，鏈路時(shí)延監(jiān)測周期設(shè)置為2 s，網(wǎng)絡(luò)擁塞狀態(tài)設(shè)置為鏈路容量的70%，鏈路帶寬設(shè)置為100 Mbit/s.BD-NSGA2算法參數(shù)配置：種群個(gè)數(shù)N為70,迭代次數(shù)σ為30,突變率mr為10%,交叉率cr為100%.利用iperf產(chǎn)生數(shù)據(jù)流模擬大象流，利用ping產(chǎn)生數(shù)據(jù)流來模擬老鼠流，其虛擬主機(jī)間通信模式為如下兩種方式.

1) 隨機(jī)方式(Random).主機(jī)之間以等概率進(jìn)行隨機(jī)通信.

2) 交錯(cuò)方式(Staggered(pEdge,pPod)).在網(wǎng)絡(luò)中，pEdge為同一Pod內(nèi)相同子網(wǎng)的流量占比，pPod為不同子網(wǎng)間的流量占比，對于不同Pod內(nèi)的流量占比為1-pEdge-pPod.

3.3 結(jié)果分析

實(shí)驗(yàn)中，通過平均吞吐量、平均丟包率、鏈路利用率評估指標(biāo)對網(wǎng)絡(luò)性能以及服務(wù)質(zhì)量進(jìn)行評估.為了確保實(shí)驗(yàn)的真實(shí)性以及準(zhǔn)確性，本文在不同模式下進(jìn)行仿真實(shí)驗(yàn)20次，取20次實(shí)驗(yàn)結(jié)果的平均值為最終實(shí)驗(yàn)結(jié)果.

3.3.1 平均吞吐量比較 在流發(fā)送速率下，BD-NSGA2算法與ECMP算法[8]、GFF算法[10]、RPC算法[9]、DSFlows算法[21]、NSGA2算法[22]的平均吞吐量比較如圖4所示.當(dāng)流發(fā)送速率在10～20 Mbit/s時(shí)，由于發(fā)送速率較小，網(wǎng)絡(luò)能容納這些數(shù)據(jù)流，幾種算法的平均吞吐量接近相等.當(dāng)數(shù)據(jù)流不斷增長時(shí)，網(wǎng)絡(luò)吞吐量緩慢上升，ECMP算法易于將多條流轉(zhuǎn)發(fā)到同一條路徑上，導(dǎo)致鏈路擁塞，因此吞吐量最低.GFF算法由于其低網(wǎng)絡(luò)地址易于劃分，導(dǎo)致留下很多難以利用的小空間，因此GFF算法的平均吞吐量相比RPC算法要低.RPC算法根據(jù)鏈路負(fù)載和時(shí)延作為關(guān)鍵度指標(biāo)進(jìn)行重路由，因?yàn)榇笙罅鲗W(wǎng)絡(luò)中帶寬較為敏感，在模型建立中，未考慮網(wǎng)絡(luò)帶寬，會產(chǎn)生一定程度的偏差.DSFlows算法通過對鏈路帶寬狀態(tài)的考慮，將大象流轉(zhuǎn)發(fā)到負(fù)載較低的鏈路中，平均吞吐量比ECMP算法與GFF算法相比明顯上升.NSGA2算法由于可能存在局部最優(yōu)的情況因此吞吐量低于BD-NSG2算法.BD-NSGA2算法在發(fā)送速率上升，數(shù)據(jù)流不斷增長時(shí)，當(dāng)鏈路發(fā)生擁塞時(shí)，以路徑帶寬最優(yōu)以及路徑時(shí)延多目標(biāo)評價(jià)模型下，同時(shí)避免局部最優(yōu)的產(chǎn)生，更好地將多條大象流向空閑鏈路進(jìn)行轉(zhuǎn)發(fā)，因此吞吐量高于RPC算法.當(dāng)流發(fā)送速率為40 Mbit/s時(shí)，BD-NSGA2算法與ECMP、GFF、RPC、DSFlows、NSGA2算法相比分別增了36.4%、26.9%、6.1%、18.3%、8.8%；當(dāng)流發(fā)送速率為50 Mbit/s時(shí)，相比于ECMP、GFF、RPC、DSFlows、NSGA2算法增加了47.0%、37.4%和10.8%、12.5%、8.1%，可以有效地提高吞吐量.

3.3.2 平均丟包率比較 在網(wǎng)絡(luò)負(fù)載下，BD-NSGA2算法與ECMP、GFF、RPC、DSFlows、NSGA2算法的平均丟包率比較如圖5所示.在網(wǎng)絡(luò)負(fù)載較低的情況下，鏈路出現(xiàn)擁塞的可能性較低，在網(wǎng)絡(luò)負(fù)載為0.1～0.2時(shí)，幾種算法的平均丟包率接近.在網(wǎng)絡(luò)負(fù)載達(dá)到0.3時(shí)，RPC算法與DSFlows算法在網(wǎng)絡(luò)負(fù)載較小時(shí)比BD-NSGA2算法收斂快，因此BD-NSGA2算法在網(wǎng)絡(luò)負(fù)載0.3時(shí)比RPC算法與DSFlows算法平均丟包率多.但隨著網(wǎng)絡(luò)負(fù)載的增加，BD-NSGA2算法會避免快速收斂產(chǎn)生的局部最優(yōu)的情況，因此在網(wǎng)絡(luò)負(fù)載達(dá)到0.5時(shí)，BD-NSGA2算法平均丟包率比ECMP、GFF、RPC、DSFlows、NSGA2算法減少73.8%、64.7%、10.0%、21.7%、30.8%.

圖5 平均丟包率比較Fig.5 Comparison of the average packet loss rate

3.3.3 平均時(shí)延抖動比較 在網(wǎng)絡(luò)負(fù)載下，BD-NSGA2算法與ECMP、GFF、RPC、DSFlows、NSGA2算法的平均時(shí)延抖動比較如圖6所示.在網(wǎng)絡(luò)負(fù)載在0.1時(shí)，Ryu控制器在與OpenFlow交換機(jī)間進(jìn)行信息交互，包括控制器中的路由調(diào)度算法的計(jì)算轉(zhuǎn)發(fā)以及流表的安裝，導(dǎo)致時(shí)延明顯上升.隨著網(wǎng)絡(luò)負(fù)載的增加,鏈路帶寬的資源更加緊張，因此在鏈路負(fù)載達(dá)0.3以后的時(shí)延抖動緩慢上升.在網(wǎng)絡(luò)負(fù)載為0.5時(shí)，BD-NSGA2算法平均時(shí)延抖動比ECMP、GFF、RPC、DSFlows算法與NSGA2算法減少35.9%、22.6%、6.8%、8.9%、14.6%.

圖6 平均時(shí)延抖動比較Fig.6 Comparison of the average delay variation

3.3.4 鏈路利用率比較 在不同通信模式下，BD-NSGA2算法與ECMP、GFF、DTSNL[20]、NSGA2算法的鏈路利用率比較如圖7所示.在Random、Stag(0.1,0.2)、Stag(0.2,0.3) 3種通信模式下，由于網(wǎng)絡(luò)中主機(jī)在不同Pod內(nèi)通信概率較大，存在的流量較多導(dǎo)致鏈路使用數(shù)量增加，因此5種算法的鏈路利用率都較高.在Stag(0.5,0.3)通信模式下，流量在Pod間通信，鏈路使用數(shù)量減少，鏈路利用率低于Random、Stag(0.1,0.2)、Stag(0.2,0.3)通信模式下的鏈路利用率.本文在對大象流進(jìn)行鏈路擁塞流量調(diào)度中，通過BD-NSGA2算法進(jìn)行流量調(diào)度，在Pod間以及Pod內(nèi)流進(jìn)行優(yōu)化，提高其鏈路利用率.在Random通信模式下，BD-NSGA2算法的鏈路利用率比ECMP、GFF算法與NSGA2算法相比增加26.4%、3.4%、3.4%，與DTSNL算法持平；在Stag(0.5,0.3)模式下，BD-NSGA2算法的鏈路利用率比ECMP、GFF、DTSNL、NSGA2算法增加13.6%、8.1%、6.3%、9.8%.

圖7 鏈路利用率比較Fig.7 Comparison of the link utilization

4 結(jié)語

研究了DCN中大象流在鏈路擁塞問題下的調(diào)度問題，在SDN架構(gòu)下大象流調(diào)度的BD-NSGA2算法，該算法在對大象流進(jìn)行流量調(diào)度時(shí)，能有效地將大象流調(diào)度到空閑鏈路中，避免鏈路擁塞的情況發(fā)生，提高網(wǎng)絡(luò)質(zhì)量.通過對比實(shí)驗(yàn)表明，該算法可以更好地提高鏈路利用率和網(wǎng)絡(luò)吞吐量、降低在傳輸過程中的丟包率和時(shí)延抖動.通過仿真實(shí)驗(yàn)進(jìn)行測試，選取的拓?fù)渚W(wǎng)絡(luò)也是具有規(guī)則的數(shù)據(jù)中心拓?fù)?，因此在真?shí)環(huán)境中以及其他規(guī)格拓?fù)渲杏写M(jìn)一步探索與研究.