基于虛擬軟件的網(wǎng)絡(luò)流量調(diào)度數(shù)學(xué)模型仿真

孫曉磊,孔德志*,張煥生,趙男男

(1. 河北水利電力學(xué)院,河北 滄州 061000;2. 廣東海洋大學(xué)計算機(jī)科學(xué)與工程學(xué)院,廣東 陽江 529500)

1 引言

目前,網(wǎng)絡(luò)業(yè)務(wù)數(shù)量與帶寬需求隨著網(wǎng)絡(luò)應(yīng)用的高速發(fā)展呈不斷增長趨勢,無形中提高了對網(wǎng)絡(luò)業(yè)務(wù)承載力與轉(zhuǎn)發(fā)能力的要求,為防止發(fā)生網(wǎng)絡(luò)擁塞、提升網(wǎng)絡(luò)性能,網(wǎng)絡(luò)流量調(diào)度是網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵[1]。對于不同類型網(wǎng)絡(luò)的服務(wù)質(zhì)量,目前網(wǎng)絡(luò)流量調(diào)度方法還不能滿足其需求,原因是該方法的網(wǎng)絡(luò)服務(wù)能力路由具有局限性[2]。

如何提升網(wǎng)絡(luò)流量調(diào)度效果,提高網(wǎng)絡(luò)利用率,節(jié)省網(wǎng)絡(luò)能源消耗,使運(yùn)營成本降低,是中外學(xué)者一直研究的課題[3]。如吳博等人提出的基于動態(tài)DCVS的網(wǎng)絡(luò)流量調(diào)度模型[4],該模型可使網(wǎng)絡(luò)性能得到提高,但其計算復(fù)雜,導(dǎo)致流量調(diào)度實時性差;又如王耀民等人提出的基于斐波那契樹優(yōu)化算法的網(wǎng)絡(luò)流量調(diào)度模型[5],雖可使交換機(jī)的利用率得到提高,實現(xiàn)網(wǎng)絡(luò)節(jié)能,但其無法形成全局最優(yōu)的調(diào)度方案。

軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)是一種基于應(yīng)用、調(diào)控、轉(zhuǎn)發(fā)的新型網(wǎng)絡(luò)結(jié)構(gòu)體系[6],其作為虛擬機(jī)的一種嵌入式軟件的網(wǎng)架結(jié)構(gòu)體系,通過調(diào)控解藕設(shè)備與轉(zhuǎn)發(fā)功能集中網(wǎng)絡(luò)邏輯、開放可編程接口獲得。SDN的核心是調(diào)控器,可以調(diào)控網(wǎng)絡(luò)里的全部邏輯,整體管理網(wǎng)絡(luò),為確保不同網(wǎng)絡(luò)應(yīng)用的服務(wù)質(zhì)量需求,SDN網(wǎng)絡(luò)需找到數(shù)據(jù)轉(zhuǎn)發(fā)最佳的下一跳,找到數(shù)據(jù)的前提是需依據(jù)所有網(wǎng)絡(luò)拓?fù)渑c狀態(tài)信息搜索。本文利用SDN獲得節(jié)能網(wǎng)絡(luò)流量調(diào)度功能,研究基于虛擬軟件的網(wǎng)絡(luò)流量調(diào)度數(shù)學(xué)模型仿真,減少網(wǎng)絡(luò)擁塞,提高網(wǎng)絡(luò)流量調(diào)度效果。

2 網(wǎng)絡(luò)流量調(diào)度數(shù)學(xué)模型

本文采用以下符號構(gòu)建該數(shù)學(xué)模型:網(wǎng)絡(luò)用G(V,L)描述,其中,數(shù)據(jù)鏈路集合與鏈路分別用L與l描述,cl為l的容量。交換機(jī)的節(jié)點集合用V描述;隨意一個交換機(jī)的節(jié)點用v描述,鏈路集合用Lv描述,且該鏈路連接交換機(jī)v。

全部保持工作狀態(tài)的交換機(jī)與l在網(wǎng)絡(luò)里的能源消耗是網(wǎng)絡(luò)的總能源消耗[7],用COSTl描述隨意l兩個交換機(jī)端口的能源消耗,交換機(jī)機(jī)架與線卡的能源消耗用COSTv描述。

以符合數(shù)據(jù)流f∈F路由為基礎(chǔ),保證網(wǎng)絡(luò)能源消耗總量最低為目標(biāo),完成節(jié)能流量調(diào)度。

網(wǎng)絡(luò)流量調(diào)度的優(yōu)化數(shù)學(xué)模型是

(1)

s.t.

(2)

(3)

(4)

x(P)≥0?P

(5)

表示網(wǎng)絡(luò)總能源消耗的優(yōu)化目標(biāo)函數(shù)用式(1)表示;l容量限制約束條件為式(2),隨意活躍l的總?cè)萘啃璐笥谄涑休d的數(shù)據(jù)流總寬帶。流量守恒約束條件為式(3)。當(dāng)v分別僅有流出與流入數(shù)據(jù)流時,v分別是f的源節(jié)點與目的節(jié)點。否則,v的流入與流出數(shù)據(jù)流相同。用λ描述流量放大倍數(shù)。式(4)與式(5)為λ的約束條件,全部使用鏈路l傳輸流量的路徑為式(4),且傳輸流量總和≦鏈路容量cl。式(5)為路徑上的流量不能小于0。路徑P上的流量用x(P)描述;一條從源節(jié)點到目的節(jié)點路徑上的邊l滿足?l∈L,用l*描述SDN轉(zhuǎn)發(fā)設(shè)備之間的鏈路,且l*∈L區(qū)分原有鏈路l。

3 基于虛擬軟件的網(wǎng)絡(luò)流量調(diào)度算法EMV-SDN

EMV-SDN是基于SDN改進(jìn)的多層虛擬拓?fù)淞髁空{(diào)度算法,可采用EMV-SDN對上述數(shù)學(xué)模型進(jìn)行求解,切割網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為包含多層虛擬子拓?fù)涞奶摂M結(jié)構(gòu)。首先僅打開第一層虛擬拓?fù)?下一層虛擬拓?fù)鋯优c否受最大鏈路使用率影響[8],采用改進(jìn)貪婪算法在已打開的虛擬拓?fù)浣Y(jié)構(gòu)里通過路徑求解完成數(shù)據(jù)流調(diào)度。為達(dá)成節(jié)約網(wǎng)絡(luò)能耗的目標(biāo),結(jié)合實際情況,可將已經(jīng)打開的下一層虛擬拓?fù)溥M(jìn)行關(guān)閉[9]。

3.1 EMV-SDN算法描述

圖1為EMV-SDN流程,虛擬軟件的網(wǎng)絡(luò)拓?fù)渑cf作為輸入,f的路由與已打開的一層或多層虛擬拓?fù)錇檩敵?。對于f的調(diào)度,基于f路由產(chǎn)生流表項下發(fā)交換機(jī),由SDN調(diào)控器對其進(jìn)行調(diào)度。

圖1 節(jié)能網(wǎng)絡(luò)流量調(diào)度算法過程

該方法具體過程為:

過程1:原始化。

1)隨意選擇兩個服務(wù)器節(jié)點間K-最短路徑的運(yùn)算過程是通過設(shè)置虛擬軟件的網(wǎng)絡(luò)拓?fù)渫瓿伞?/p>

2)把虛擬軟件里的網(wǎng)絡(luò)拓?fù)渖啥鄬犹摂M拓?fù)洹?/p>

3)將虛擬軟件的第一層虛擬拓?fù)浯蜷_,其余層拓?fù)潢P(guān)閉。

用f描述新抵達(dá)的數(shù)據(jù)流,對f實施以下過程。

過程2:求解μ值,該值為最大鏈路使用率,求該值的前提是通過sflow軟件采集目前打開的虛擬拓?fù)滏溌肥褂脿顩r,且sflow軟件來自于SDN調(diào)控器。

過程3:預(yù)打開虛擬軟件的下一層虛擬拓?fù)涞那疤崾铅讨荡笥陂撝?[10],即將其中的交換機(jī)喚醒,但不改變該層的鏈路狀態(tài)[11]。該過程不僅能夠節(jié)能,還能對突發(fā)數(shù)據(jù)流進(jìn)行迅速地響應(yīng)及調(diào)度,使平均網(wǎng)絡(luò)時延的情況得到降低。若μ小于閾值1,轉(zhuǎn)至過程5。

過程4:打開并使用下一層虛擬拓?fù)涞那疤崾铅讨荡笥陂撝?,即使該層中里的鏈路喚醒并保持其活躍。若μ小于閾值2,轉(zhuǎn)至過程5。

過程5:運(yùn)算路由可采用改進(jìn)貪心算法實現(xiàn)。

過程6:路由數(shù)據(jù)流通過選中路徑完成。

過程7:求解μ值,求解該值的前提是將sflow收集鏈路狀態(tài)進(jìn)行調(diào)配使用[12]。

過程8:將下一層虛擬拓?fù)渲械慕粨Q機(jī)與鏈路進(jìn)行休眠,該操作的前提是已打開過下一層拓?fù)?且μ小于閾值1,持續(xù)時間大于T。該操作可防止交換機(jī)與鏈路產(chǎn)生網(wǎng)絡(luò)動蕩,其產(chǎn)生動蕩的原因是頻繁進(jìn)行打開/休眠操作,使數(shù)據(jù)中心網(wǎng)絡(luò)實現(xiàn)節(jié)能[13,14]。

過程9:若沒有完成網(wǎng)絡(luò)流量調(diào)度,則轉(zhuǎn)至過程2;反之,節(jié)能流量調(diào)度算法EMV-SDN結(jié)束。

3.2 基于優(yōu)先級隊列管理的流量調(diào)度控制

為防止流量調(diào)度擁塞,利用引入優(yōu)先級概念的隊列管理算法(Priority RED,PRED)進(jìn)行網(wǎng)絡(luò)流量調(diào)度控制。進(jìn)入/離開緩存區(qū)的順序問題不存在于網(wǎng)絡(luò)流量調(diào)度的單隊列中而是存在于多隊列中[15],該問題可通過網(wǎng)絡(luò)流量調(diào)度“實時優(yōu)先級”概念得到解決。

為使掉包率下降,需確保網(wǎng)絡(luò)流量調(diào)度的多個隊列的平均隊列長度在緩存區(qū)最小,獲得該最小長度的條件是到達(dá)分組中的隊列可在實時優(yōu)先級中優(yōu)先進(jìn)入。

設(shè)置有Qa,Qb,Qc三個網(wǎng)絡(luò)流量調(diào)度隊列在緩存區(qū),如圖2所示,Hin-a、Hin-b與Hin-c分別為網(wǎng)絡(luò)流量調(diào)度隊列進(jìn)入緩存區(qū)的優(yōu)先級,Hout-a、Hin-b與Hin-c分別為網(wǎng)絡(luò)流量調(diào)度隊列離開緩存區(qū)的優(yōu)先級,并假定在剛進(jìn)入網(wǎng)絡(luò)時,原始網(wǎng)絡(luò)流量調(diào)度隊列優(yōu)先級Hin-a

圖2 隊列長度變化

設(shè)置Qavga、Qavgb、Qavgc分別為Qa、Qb、Qc的平均隊列長度,常數(shù)為K。若有分組到達(dá)緩存區(qū),輸入及輸出網(wǎng)絡(luò)流量調(diào)度隊列的實時優(yōu)先級公式分別為

Hin-i=K/Qavgi,i=1,2,…n

(6)

由式(6)可看出,Hin-i和Qavgi成反比例,若Qavgi值越大,則代表此時刻該網(wǎng)絡(luò)流量調(diào)度隊列含有越多的分組數(shù)目,Hin-i值越小。

為確保Qavga、Qavgb、Qavgc值相對最短,需將到來的分組放進(jìn)網(wǎng)絡(luò)流量調(diào)度隊列長度最小的隊列里,該過程可依據(jù)運(yùn)算出的Hin-a、Hin-b與Hin-c值,重新排序進(jìn)入緩存區(qū)網(wǎng)絡(luò)流量調(diào)度隊列的優(yōu)先級。

Hout-i=A*Qavgi,i=1,2,…n

(7)

式中,A>1。Hout-i與Qavgi成反比例,Qavgi值越大,Hout-i值越大。為確保網(wǎng)絡(luò)流量調(diào)度隊列里較長的隊列數(shù)據(jù)先離開緩存區(qū),需重新排序Hout-a、Hin-b與Hin-c。

為防止網(wǎng)絡(luò)出現(xiàn)擁塞,需要對網(wǎng)絡(luò)流量進(jìn)行調(diào)度,該調(diào)度手段可依據(jù)優(yōu)先丟棄優(yōu)先級高的分組數(shù)據(jù),由網(wǎng)絡(luò)節(jié)點對其進(jìn)行調(diào)度。

丟棄優(yōu)先級的概念由TCRED(Three Color RED)算法提出,網(wǎng)絡(luò)里的業(yè)務(wù)流在優(yōu)先級的基礎(chǔ)上分為“Green,Yellow,Red”三種顏色,HRe d>HYellow>HGreen為該三種顏色的丟棄優(yōu)先級排列順序。運(yùn)算Green,Yellow,Red三種顏色隊列長度及掉包率,需采用同一組參數(shù)調(diào)控該三種顏色的分組,且其參數(shù)為maxth、minth、maxp、Wq。其中,式(8)、式(9)、式(10)為低優(yōu)先級分組平均隊長,且該隊長包含在高丟棄優(yōu)先級分組的平均隊列長度中。

用QGreen、QYellow、QRe d分別描述G、Y、R分組本身的瞬間隊列長度,求出QR、QY、QR的值,這些值分別描述G、Y、R基于優(yōu)先級分組的瞬時隊列長度。

4 實驗對象

為驗證本文模型的調(diào)度性能,采用mininet網(wǎng)絡(luò)仿真軟件進(jìn)行仿真,其中全部OpenFlow交換機(jī)均有50個端口,設(shè)置所有鏈路帶寬為120Mbit/s。

當(dāng)緩存區(qū)大小固定時,設(shè)從100至200為Green分組、Yellow分組、Red分組的三組隊列長度最大閾值(maxth)的變化區(qū)域,最大閾值的二分之一是其最小閾值(minth),驗證網(wǎng)絡(luò)流量調(diào)度過程中,調(diào)度隊列長度閾值對本文模型中三種分組隊列長度與掉包率的影響,結(jié)果如圖2與圖3所示。

圖3 掉包率變化

由圖2可看出,三組顏色的隊列長度隨著隊列長度閾值的增加而增高,當(dāng)閾值分別為100與200時,Red分組的隊列長度的最低值與最高值分別為110與170,Green分組的隊列長度的最低值與最高值分別為20與49。

由圖3可看出,三組顏色的掉包率隨著隊列長度閾值的增加而呈不斷上升趨勢,當(dāng)閾值為200時,Red與Green分組的掉包率的最高值分別為0.098與0.028,但其均小于0.10,在滿足網(wǎng)絡(luò)穩(wěn)定性范圍之內(nèi),。

由圖2及圖3的仿真可得出結(jié)論,當(dāng)緩存區(qū)大小固定時,隊列長度、掉包率隨著隊列長度閾值的增加而逐漸增大,使SDN調(diào)控器的可靠性與靈活性得到最大化的提高,同時使鏈路使用率也得到相應(yīng)的提高,本文模型可通過增大隊列長度閾值提升網(wǎng)絡(luò)流量的調(diào)度性能。

數(shù)據(jù)流的目的節(jié)點可通過隨機(jī)模式、間隔模式進(jìn)行確定。其中,隨機(jī)模式為主機(jī)j接收主機(jī)i隨機(jī)發(fā)送的數(shù)據(jù),且該數(shù)據(jù)以同一概率q發(fā)送;間隔模式為主機(jī)(i+x)mod n接收主機(jī)發(fā)送的數(shù)據(jù),網(wǎng)絡(luò)里主機(jī)的總數(shù)量用n描述。

實驗選擇300GB、600GB、900GB的網(wǎng)絡(luò)流量,驗證在該兩種模式下,不同網(wǎng)絡(luò)流量對本文模型網(wǎng)絡(luò)流量調(diào)度能源消耗的影響,結(jié)果如圖4與圖5所示。

圖4 隨機(jī)模式(0.5)下網(wǎng)絡(luò)流量調(diào)度能源消耗比例

圖5 交錯模式下的能源消耗比例

由圖4可以看出,在隨機(jī)模式下,隨著網(wǎng)絡(luò)流量的增加,本文模型的調(diào)度能源消耗比例呈小幅增長趨勢。當(dāng)網(wǎng)絡(luò)流量為300GB與600GB時,本文模型的調(diào)度能源最高消耗比例分別為54%與60%,其能源消耗比例僅差6%,三種網(wǎng)絡(luò)流量下的最低調(diào)度能源消耗比例為21%。

由圖5可以看出,在交錯模式下,本文模型的調(diào)度能源消耗比例依舊隨著網(wǎng)絡(luò)流量的增加而呈小幅增長趨勢。當(dāng)網(wǎng)絡(luò)流量為300GB與600GB時,本文模型的調(diào)度能源最高消耗比例分別為50%與53%,其能源消耗比例僅相差3%,三種網(wǎng)絡(luò)流量下的最低能源消耗比例只為19%。

結(jié)合圖4與圖5所得數(shù)據(jù)可知,本文模型的調(diào)度能源消耗受網(wǎng)絡(luò)流量的影響較小,調(diào)度所消耗能源少,本文模型具有很好的網(wǎng)絡(luò)流量調(diào)度節(jié)能效果。

5 結(jié)論

本文提出基于虛擬軟件的網(wǎng)絡(luò)流量調(diào)度數(shù)學(xué)模型仿真,經(jīng)實驗表明,當(dāng)緩存區(qū)大小固定時,隨著隊列長度閾值的增加,隊列長度、掉包率逐漸增大,最大化的提高SDN調(diào)控器的可靠性與靈活性,同時提高鏈路使用率,增大隊列長度閾值可提升本文模型網(wǎng)絡(luò)流量的調(diào)度性能;在隨機(jī)與交錯模式下,當(dāng)網(wǎng)絡(luò)流量為300GB與600GB時,其調(diào)度能源消耗比例相差值分別為6%與3%,且三種網(wǎng)絡(luò)流量下的最低調(diào)度能源消耗比例僅為19%,說明本文模型的調(diào)度能源消耗幾乎不受網(wǎng)絡(luò)流量的影響,且消耗能源少,本文模型節(jié)能效果好。