一種5G網(wǎng)絡(luò)低時(shí)延資源調(diào)度算法

王琛, 湯紅波, 游偉, 王曉雷, 袁泉

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心, 450002, 鄭州; 2.移動(dòng)互聯(lián)網(wǎng)安全技術(shù)國家工程實(shí)驗(yàn)室, 100876, 北京)

5G移動(dòng)通信網(wǎng)將是一個(gè)全方位服務(wù)、多技術(shù)融合的網(wǎng)絡(luò),通過信息通信技術(shù)的演進(jìn)和創(chuàng)新,來滿足未來用戶多樣化的業(yè)務(wù)需求[1]。以軟件定義網(wǎng)絡(luò)(software defined network,SDN)和網(wǎng)絡(luò)功能虛擬化(network function virtualization,NFV)為代表的網(wǎng)絡(luò)新技術(shù)將成為5G網(wǎng)絡(luò)的關(guān)鍵技術(shù)[2]。NFV技術(shù)使網(wǎng)絡(luò)資源分配更加靈活,實(shí)現(xiàn)了異構(gòu)的網(wǎng)絡(luò)架構(gòu)和服務(wù)的聚合[3]。在傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)中,網(wǎng)絡(luò)功能通過昂貴的硬件中間件來實(shí)現(xiàn),當(dāng)移動(dòng)網(wǎng)絡(luò)運(yùn)營商部署新業(yè)務(wù)時(shí),需要大量的資本支出和運(yùn)營支出。而在NFV環(huán)境下,網(wǎng)絡(luò)功能通過實(shí)例化在商用服務(wù)器上的虛擬機(jī)(virtual machine,VM)中的軟件化的虛擬網(wǎng)絡(luò)功能(virtual network function,VNF)來實(shí)現(xiàn),網(wǎng)絡(luò)服務(wù)則是由多個(gè)虛擬網(wǎng)絡(luò)功能以一定的依賴關(guān)系構(gòu)成服務(wù)功能鏈(service function chaining,SFC)來完成。移動(dòng)網(wǎng)絡(luò)運(yùn)營商通過NFV技術(shù)能夠有效地減少資本支出和運(yùn)營支出,為用戶提供先進(jìn)和靈活的網(wǎng)絡(luò)服務(wù)[4],而SDN作為一種新型的網(wǎng)絡(luò)架構(gòu),能夠控制數(shù)據(jù)流通過相應(yīng)的網(wǎng)絡(luò)功能以執(zhí)行相應(yīng)的策略,實(shí)現(xiàn)靈活的網(wǎng)絡(luò)管理[5]。SDN和NFV的結(jié)合為虛擬網(wǎng)絡(luò)功能的協(xié)調(diào)控制和調(diào)度提供了有效的架構(gòu),促進(jìn)了網(wǎng)絡(luò)的創(chuàng)新[6]。在網(wǎng)絡(luò)虛擬化下,資源分配分為服務(wù)功能鏈的構(gòu)建、服務(wù)功能鏈的映射和虛擬網(wǎng)絡(luò)功能調(diào)度這3個(gè)階段。虛擬網(wǎng)絡(luò)功能調(diào)度作為NFV環(huán)境下資源分配的第3個(gè)階段,主要解決在給定相應(yīng)的計(jì)算資源約束和虛擬網(wǎng)絡(luò)功能執(zhí)行順序的基礎(chǔ)上,為多個(gè)服務(wù)功能鏈中的每個(gè)虛擬網(wǎng)絡(luò)功能在虛擬機(jī)中選擇相應(yīng)的實(shí)例化時(shí)間,從而達(dá)到最小化完成所有網(wǎng)絡(luò)服務(wù)總時(shí)間的目的[7]。

IMT-2020將增強(qiáng)移動(dòng)寬帶、海量機(jī)器通信和高可靠低時(shí)延通信作為5G的主要應(yīng)用場景[8]。為了使移動(dòng)終端完美支持交互式游戲、3D虛擬現(xiàn)實(shí)等在線交互應(yīng)用,5G提出了毫秒級時(shí)延和10 Gbit/s峰值速率的要求[9]。因此,設(shè)計(jì)高效的虛擬網(wǎng)絡(luò)功能調(diào)度方法是將NFV應(yīng)用在5G當(dāng)中的關(guān)鍵問題之一。目前僅有少量的文獻(xiàn)研究了虛擬網(wǎng)絡(luò)功能調(diào)度問題。文獻(xiàn)[10]將虛擬網(wǎng)絡(luò)功能調(diào)度問題定義為柔性車間調(diào)度問題(flexible job shop problem,FJSP),然而未提出多項(xiàng)式時(shí)間內(nèi)的解決方案,而且在其調(diào)度模型里僅考慮了虛擬網(wǎng)絡(luò)功能的處理時(shí)延。文獻(xiàn)[11]提出了NFV環(huán)境下具有較低復(fù)雜度的多資源數(shù)據(jù)包調(diào)度算法,該算法考慮了數(shù)據(jù)包隊(duì)列的特性,然而未考慮服務(wù)功能鏈的特性。文獻(xiàn)[12]對服務(wù)功能鏈的端到端時(shí)延進(jìn)行了分析,然而其假定時(shí)延具有固定的值,這在實(shí)際中并不適用,不能應(yīng)用在動(dòng)態(tài)的網(wǎng)絡(luò)服務(wù)中。文獻(xiàn)[13]在FJSP模型的基礎(chǔ)上引入數(shù)據(jù)流量在虛擬鏈路上的傳輸時(shí)延,建立了虛擬網(wǎng)絡(luò)功能調(diào)度問題的混合整數(shù)線性規(guī)劃模型,并設(shè)計(jì)了基于遺傳算法的虛擬網(wǎng)絡(luò)功能調(diào)度方法,但其提出的遺傳算法容易早熟,陷入局部最優(yōu),無法獲得更好的調(diào)度方案。虛擬化技術(shù)將物理服務(wù)器虛擬化為多個(gè)虛擬機(jī)節(jié)點(diǎn),這些虛擬機(jī)節(jié)點(diǎn)之間由虛擬鏈路相互連接[14],流入服務(wù)功能鏈中的數(shù)據(jù)流量在具有有限帶寬的虛擬鏈路中傳輸時(shí)會(huì)帶來不可忽視的傳輸時(shí)延,而完成一個(gè)服務(wù)功能鏈需要利用多個(gè)虛擬機(jī),這些虛擬機(jī)可以放置在位于一個(gè)數(shù)據(jù)中心或多個(gè)數(shù)據(jù)中心的物理實(shí)體上,瓶頸傳輸鏈路帶來的時(shí)延將會(huì)降低整個(gè)網(wǎng)絡(luò)服務(wù)的用戶體驗(yàn),因此虛擬網(wǎng)絡(luò)功能調(diào)度問題需要考慮高效的帶寬資源分配策略。文獻(xiàn)[15]闡明了因?yàn)槿鄙賹μ摂M機(jī)的帶寬保證,傳統(tǒng)的傳輸層協(xié)議是不公平的,其將帶寬分配建模為協(xié)作博弈模型,設(shè)計(jì)了相應(yīng)帶寬分配策略。文獻(xiàn)[16]針對現(xiàn)有的帶寬分配方案不能有效應(yīng)對高動(dòng)態(tài)的流量變化狀況,通過考慮大量短流和突發(fā)流的影響,在控制論框架下基于符號邏輯模型設(shè)計(jì)了一種分布式速率分配算法。

針對以上研究的不足,本文通過考慮虛擬網(wǎng)絡(luò)功能實(shí)例化在虛擬機(jī)上的處理時(shí)延和數(shù)據(jù)流量在虛擬鏈路上的傳輸時(shí)延,建立了相應(yīng)的虛擬網(wǎng)絡(luò)功能調(diào)度模型,并設(shè)計(jì)了動(dòng)態(tài)鏈路帶寬分配策略,提出了基于聯(lián)合遺傳和禁忌搜索(GATS)的虛擬網(wǎng)絡(luò)功能調(diào)度方法。該算法在帶寬分配上具有更高的細(xì)粒度,充分利用了遺傳算法的全局搜索能力和禁忌搜索的局部搜索能力,有效的避免了早熟問題,具有更快的收斂速度,可以得到更優(yōu)的調(diào)度方案。

1　網(wǎng)絡(luò)模型與問題建模

1.1　網(wǎng)絡(luò)模型

定義服務(wù)功能鏈集合S,對于每個(gè)服務(wù)功能鏈si(i∈[1,S]),具有一組數(shù)據(jù)流量需要以固定順序通過的虛擬網(wǎng)絡(luò)功能;Fi(i∈[1,S])為服務(wù)功能鏈si中虛擬網(wǎng)絡(luò)功能的集合;fij表示服務(wù)功能鏈si中的第j個(gè)虛擬網(wǎng)絡(luò)功能;N為虛擬網(wǎng)絡(luò)中虛擬機(jī)的集合;L為虛擬網(wǎng)絡(luò)中虛擬鏈路的集合。假設(shè)每個(gè)虛擬機(jī)節(jié)點(diǎn)具有實(shí)例化不同虛擬網(wǎng)絡(luò)功能的能力,且在同一時(shí)間段內(nèi)至多實(shí)例化一個(gè)虛擬網(wǎng)絡(luò)功能,Mfij(i∈[1,S],j∈[1,Fi])為具有實(shí)例化虛擬網(wǎng)絡(luò)功能fij能力的虛擬機(jī)節(jié)點(diǎn)集合,即計(jì)算資源約束。本文考慮了2種類型的時(shí)延,即服務(wù)功能鏈的數(shù)據(jù)流通過虛擬機(jī)之間的虛擬鏈路的傳輸時(shí)延和虛擬網(wǎng)絡(luò)功能實(shí)例化在虛擬機(jī)中的處理時(shí)延。假定每個(gè)服務(wù)功能鏈從流入端點(diǎn)到流出端點(diǎn)具有固定的流量需求,定義為Di(i∈[1,S]),2個(gè)虛擬機(jī)之間的虛擬鏈路的帶寬為Bk1,k2(k1,k2∈[1,N]),因此,服務(wù)功能鏈si在虛擬機(jī)節(jié)點(diǎn)k1和k2之間虛擬鏈路的傳輸時(shí)延為Di/Bk1,k2。τk,fij(k∈[1,N])為虛擬網(wǎng)絡(luò)功能fij實(shí)例化在虛擬機(jī)節(jié)點(diǎn)k上的處理時(shí)延。

1.2　問題建模

(1)

式(1)的約束條件為

(2)

(3)

(4)

式中:δ是所有服務(wù)功能鏈中最后一個(gè)虛擬網(wǎng)絡(luò)功能的處理完成時(shí)間,即多個(gè)網(wǎng)絡(luò)服務(wù)的完成時(shí)間。式(1)表示虛擬網(wǎng)絡(luò)功能調(diào)度的目標(biāo),即最小化所有服務(wù)功能鏈請求的最大完成時(shí)間;式(2)確保了當(dāng)服務(wù)功能鏈中的數(shù)據(jù)流量在虛擬網(wǎng)絡(luò)功能處理完成后,相應(yīng)的虛擬網(wǎng)絡(luò)功能才能開始轉(zhuǎn)發(fā)數(shù)據(jù)流;式(3)確保了只有從上行虛擬機(jī)中接收到數(shù)據(jù)流后,下行虛擬機(jī)才能開始處理相應(yīng)的數(shù)據(jù)流;式(4)確保了有且僅有一個(gè)虛擬機(jī)實(shí)例化虛擬網(wǎng)絡(luò)功能fij。

1.3　帶寬分配策略

合理的帶寬分配策略能夠有效的降低數(shù)據(jù)流在虛擬鏈路上的傳輸時(shí)延。定義Cin(k)/Cout(k)為虛擬機(jī)節(jié)點(diǎn)k的流入/流出帶寬。根據(jù)流經(jīng)虛擬機(jī)的數(shù)據(jù)流量動(dòng)態(tài)的分配帶寬資源,將帶寬分配建模為整數(shù)線性規(guī)劃模型,其優(yōu)化目標(biāo)表示為

minη

(5)

式(5)的約束條件為

(6)

(7)

式中:η表示虛擬鏈路總的傳輸時(shí)延。式(5)表示帶寬動(dòng)態(tài)分配的目標(biāo),即最小化總傳輸時(shí)延;式(6)確保從一個(gè)虛擬機(jī)流出的所有鏈路帶寬之和不大于該虛擬機(jī)的流出帶寬;式(7)確保流入一個(gè)虛擬機(jī)的所有鏈路帶寬之和不大于該虛擬機(jī)的流入帶寬。

2　聯(lián)合遺傳和禁忌搜索算法(GATS)

根據(jù)上述虛擬網(wǎng)絡(luò)功能調(diào)度模型,虛擬網(wǎng)絡(luò)功能調(diào)度問題可看做是柔性車間調(diào)度問題的擴(kuò)展,該問題是NP難問題,引入動(dòng)態(tài)的鏈路帶寬分配后,進(jìn)一步增加了其復(fù)雜性,因此在多項(xiàng)式時(shí)間內(nèi)無法利用傳統(tǒng)方法求得精確解[7]。為了有效地解決虛擬網(wǎng)絡(luò)功能調(diào)度問題,本文設(shè)計(jì)了一種聯(lián)合遺傳算法(genetic algorithm,GA)和禁忌搜索(tabu search,TS)的啟發(fā)式算法(GATS),通過利用遺傳算法的全局搜索能力和禁忌搜索的局部搜索能力,能夠得到更優(yōu)的調(diào)度方案。

2.1　染色體編碼和解碼

ci=[322131231231421324]

(8)

ci染色體中包含3條服務(wù)功能鏈,每條服務(wù)功能鏈由3個(gè)虛擬網(wǎng)絡(luò)功能構(gòu)成,共有4個(gè)虛擬機(jī)實(shí)例化所有虛擬網(wǎng)絡(luò)功能。前9位基因表示虛擬網(wǎng)絡(luò)功能的調(diào)度順序,可被解碼為f31→f21→f22→f11→f32→f12→f23→f33→f13,后9位基因表示實(shí)例化前9位虛擬網(wǎng)絡(luò)功能的虛擬機(jī)序號,可解碼為Mf31(2)→Mf21(3)→Mf22(1)→Mf11(4)→Mf22(2)→Mf12(1)→Mf23(3)→Mf33(2)→Mf13(4),其中Mf31(2)為可實(shí)例化虛擬網(wǎng)絡(luò)功能f31的虛擬機(jī)節(jié)點(diǎn)集合Mf31中的第2個(gè)元素。當(dāng)完成染色體編碼后,需要將其解碼,以生成可行的調(diào)度方案。下列偽代碼表示相應(yīng)的解碼算法:

1輸入:染色體c

4根據(jù)c計(jì)算每個(gè)虛擬機(jī)的路由

5根據(jù)動(dòng)態(tài)鏈路帶寬分配模型,執(zhí)行整數(shù)規(guī)劃算法進(jìn)行鏈路帶寬分配

6for從前往后選擇c中的基因odo

7i=get_service(c(o))

8j=get_function(c(o))

9k=get_VM_node(c(o))

10xijk=1

11ifj=1 then

12tij=starting_time_VM(T,T′,Z,k)

13else

15tij=starting_time_VM(T,T′,Z,k)

16end if

17end for

2.2　適應(yīng)度計(jì)算和選擇

染色體的適應(yīng)度值為所有服務(wù)功能鏈請求完成時(shí)間δ的倒數(shù),如式(9)所示。

(9)

對于任意染色體,計(jì)算其適應(yīng)度值,然后采用輪盤賭法進(jìn)行排序,個(gè)體的選擇概率如式(10)所示,其中NNIND表示種群個(gè)數(shù)。

(10)

2.3　交叉

圖1　染色體交叉過程

2.4　變異

首先從種群中隨機(jī)選擇變異個(gè)體,然后在個(gè)體隨機(jī)選擇2個(gè)虛擬網(wǎng)絡(luò)功能,最后交換這2個(gè)虛擬網(wǎng)絡(luò)功能及實(shí)例化虛擬網(wǎng)絡(luò)功能的虛擬機(jī)基因位置。染色體變異過程如圖2所示,首先,隨機(jī)選擇第2和第3位基因,然后交換該位置基因和相應(yīng)虛擬機(jī)分配基因(第11和第12位基因)的順序,完成變異。

圖2染色體變異過程

2.5　禁忌搜索

禁忌搜索的思想是標(biāo)記已搜索的局部最優(yōu)解的一些對象,并在進(jìn)一步的迭代搜索中盡量避開這些對象,從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到鄰域、禁忌表、禁忌長度、候選解、藐視準(zhǔn)則等概念。禁忌搜索是解決調(diào)度問題的一種有效的局部搜索策略,本文采用了文獻(xiàn)[17]提出的鄰域結(jié)構(gòu),提出的禁忌搜索算法的流程如圖3所示。

圖3　禁忌搜索算法流程圖

本文提出的GATS算法充分利用了遺傳算法的全局搜索能力和禁忌搜索的局部搜索能力,其算法流程如圖4所示。

圖4　GATS算法流程圖

在提出的GATS算法中,選擇個(gè)體執(zhí)行禁忌搜索時(shí),首先需要將其解碼為一個(gè)可行的調(diào)度解,然后將這個(gè)解作為禁忌搜索的初始解,算法執(zhí)行完后,將輸出的最優(yōu)解編碼為染色體,繼續(xù)執(zhí)行遺傳操作,當(dāng)達(dá)到最大進(jìn)化代數(shù)Gmax時(shí),終止GATS算法,當(dāng)達(dá)到最大迭代次數(shù)Tmax時(shí),終止禁忌搜索算法。設(shè)置Tmax=80×(G/Gmax)。在GATS算法的早期階段,因?yàn)檫z傳算法不能為禁忌搜索提供較好的個(gè)體,禁忌搜索算法很難找到更優(yōu)的解,所以禁忌搜索算法的最大迭代次數(shù)此時(shí)較小,可以節(jié)省GATS算法的計(jì)算時(shí)間。在GATS算法的后期階段,遺傳算法可以為禁忌搜索算法提供較好的個(gè)體,因此增大禁忌搜索算法的最大迭代次數(shù)可以幫助其找到更優(yōu)的解。因此,將禁忌搜索算法的最大迭代次數(shù)隨著GATS算法的進(jìn)化過程動(dòng)態(tài)調(diào)節(jié),可以有效的降低算法時(shí)間復(fù)雜度。

3　實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

未來5G系統(tǒng)將采用基于SDN/NFV的網(wǎng)絡(luò)架構(gòu),可以實(shí)時(shí)的掌握全局網(wǎng)絡(luò)視圖,得到算法所需的輸入數(shù)據(jù)。為了評估模型的可行性及算法有效性,本文將提出的聯(lián)合算法(GATS)與文獻(xiàn)[13]中均勻鏈路帶寬分配的遺傳算法(GA-NBA)和動(dòng)態(tài)帶寬分配的遺傳算法(GA-BA)在統(tǒng)一的實(shí)驗(yàn)平臺(tái)上進(jìn)行了比較。

3.1　實(shí)驗(yàn)設(shè)置

5G系統(tǒng)將采用云數(shù)據(jù)中心架構(gòu),具有強(qiáng)大的并行處理能力。本文為了方便算法比較,使用了配置為Intel Core i7-4790 3.60 GHz CPU、8 GB內(nèi)存的個(gè)人電腦,并利用CPLEX 12.4工具求解動(dòng)態(tài)帶寬分配整數(shù)規(guī)劃模型,編寫了算法的Matlab仿真程序。網(wǎng)絡(luò)參數(shù)方面,設(shè)置最大服務(wù)功能鏈數(shù)量S=100,最大虛擬機(jī)數(shù)量N=20。虛擬網(wǎng)絡(luò)功能在虛擬機(jī)中的處理時(shí)延在[2,10]ms內(nèi)隨機(jī)生成。虛擬網(wǎng)絡(luò)為全連通網(wǎng)絡(luò),虛擬機(jī)之間的鏈路帶寬初始化為2 Mb/s,虛擬機(jī)的流入/流出帶寬可以由此得出。考慮移動(dòng)核心網(wǎng)數(shù)據(jù)和控制平面服務(wù)功能鏈的數(shù)據(jù)流量需求,設(shè)置流經(jīng)控制面服務(wù)功能鏈的數(shù)據(jù)流量在(0,2]kb之間隨機(jī)取值,而針對數(shù)據(jù)平面服務(wù)功能鏈請求,流經(jīng)數(shù)據(jù)平面服務(wù)功能鏈的數(shù)據(jù)流量則在[10,20]kb之間隨機(jī)取值。可實(shí)例化虛擬網(wǎng)絡(luò)功能的虛擬機(jī)節(jié)點(diǎn)集合隨機(jī)生成,其中每個(gè)虛擬機(jī)節(jié)點(diǎn)實(shí)例化虛擬網(wǎng)絡(luò)功能的數(shù)量不大于3,任意虛擬網(wǎng)絡(luò)功能至少可由1個(gè)虛擬機(jī)節(jié)點(diǎn)實(shí)例化。3種算法參數(shù)統(tǒng)一設(shè)置為:種群數(shù)量NNIND=40,遺傳代數(shù)maxGen=50,交叉概率為80%,變異概率為60%。

3.2　實(shí)驗(yàn)結(jié)果分析

圖6　控制面流量GATS算法(GA-BA算法)調(diào)度結(jié)果

圖7　控制面流量GA-NBA算法調(diào)度結(jié)果

首先,設(shè)置網(wǎng)絡(luò)為全連通的具有5個(gè)虛擬機(jī)的底層網(wǎng)絡(luò)和2條控制面服務(wù)功能鏈(VNF4→VNF2→VNF1→VNF3→VNF5)和(VNF3→VNF2→VNF4→VNF5→VNF1),對3種算法進(jìn)行了仿真實(shí)驗(yàn)。圖6和圖7分別給出了在控制面流量下GATS算法(本例中GA-BA的仿真結(jié)果與其相同)和GA-NBA算法的仿真結(jié)果。圖中,Y軸表示不同的虛擬機(jī),X軸表示時(shí)間。不同顏色表示不同的服務(wù)功能鏈,色塊中上方的數(shù)字表示虛擬網(wǎng)絡(luò)功能所在的服務(wù)功能鏈的序號和在服務(wù)功能鏈中的位置,下方的文字表示虛擬網(wǎng)絡(luò)功能的類型?？梢钥闯?2種具有帶寬分配策略的方法獲得了相同的仿真結(jié)果,這是因?yàn)榭刂泼媪髁枯^小,傳輸時(shí)延對調(diào)度結(jié)果的影響較小。表1給出了3種算法在算法時(shí)間復(fù)雜度和服務(wù)完成時(shí)間上的對比。GA-NBA算法的服務(wù)完成時(shí)間最長為17 s。引入帶寬分配策略后其他2種算法將服務(wù)完成時(shí)間減少了7%。對比GA-BA算法和GATS算法的時(shí)間復(fù)雜度,由于GATS算法在遺傳算法中加入了禁忌搜索算法,增加了算法的時(shí)間復(fù)雜度。

表1　控制平面流量結(jié)果比較

圖8　數(shù)據(jù)面流量GA-NBA算法調(diào)度結(jié)果

圖9　數(shù)據(jù)面流量GABA算法調(diào)度結(jié)果

圖10　數(shù)據(jù)面流量GATS算法調(diào)度結(jié)果

使用相同的虛擬機(jī)網(wǎng)絡(luò)拓?fù)?針對2條數(shù)據(jù)平面服務(wù)功能鏈請求運(yùn)行3種算法,運(yùn)行結(jié)果如圖8～圖10所示。從圖8～圖10可見,由于數(shù)據(jù)流量較大,傳輸時(shí)延對服務(wù)完成時(shí)間的影響更加顯著。表2給出了3種算法在算法時(shí)間復(fù)雜度和服務(wù)完成時(shí)間上的對比。實(shí)驗(yàn)結(jié)果表明,引入鏈路帶寬分配后,服務(wù)完成時(shí)間明顯減少,GA-BA算法和GATS算法分別在帶寬平均分配的GA-NBA方法的基礎(chǔ)上將服務(wù)完成時(shí)間降低了24.3%和37.1%。因?yàn)楸疚腉ATS算法對帶寬分配的細(xì)粒度更小,能夠獲得更好地帶寬分配策略,因此,GATS算法比GA-BA算法獲得了更小的服務(wù)完成時(shí)間。通過比較表1和表2可以看出,算法的時(shí)間復(fù)雜度僅與虛擬網(wǎng)絡(luò)的拓?fù)浜头?wù)功能鏈的數(shù)量有關(guān)。

表2　數(shù)據(jù)平面流量結(jié)果比較

圖11表示了在數(shù)據(jù)平面流量下,不同進(jìn)化代數(shù)下服務(wù)完成時(shí)間的收斂過程。由圖11可以看出,GATS算法具有更優(yōu)的收斂效率,而GA-BA算法則經(jīng)常陷入局部最優(yōu)解,這是因?yàn)?GATS算法采用了禁忌搜索對染色體的解進(jìn)行了進(jìn)一步優(yōu)化,具有較好的局部搜索能力,表現(xiàn)出較快的收斂速度,避免了早熟問題,同時(shí)采用了細(xì)粒度更高的帶寬分配策略能夠獲得更短的服務(wù)完成時(shí)間。

圖11　2種算法的收斂過程

圖12　不同服務(wù)功能鏈請求強(qiáng)度下的服務(wù)完成時(shí)間

圖12表示不同的服務(wù)功能鏈請求強(qiáng)度下的2種算法的服務(wù)完成時(shí)間,其中,網(wǎng)絡(luò)參數(shù)設(shè)置為具有20節(jié)點(diǎn)的全聯(lián)通網(wǎng)絡(luò),設(shè)置種群數(shù)量NNIND設(shè)置為40,最大遺傳代數(shù)maxGen為50,服務(wù)功能鏈數(shù)據(jù)流量在0～20 kb均勻生成?？梢钥闯?GATS算法獲得的服務(wù)完成時(shí)間更少,而且隨著流量的上升,本文方法的優(yōu)勢更加明顯,這是因?yàn)橛捎诹髁康脑黾?傳輸時(shí)延將成為影響服務(wù)完成時(shí)間的關(guān)鍵因素,GATS算法在鏈路帶寬分配上具有更高的細(xì)粒度,而且GATS算法將遺傳算法和禁忌搜索算法有效的結(jié)合,能夠搜索到更優(yōu)的調(diào)度方案,在更短的時(shí)間內(nèi)完成網(wǎng)絡(luò)服務(wù)。

4　結(jié)　論

本文基于柔性車間調(diào)度問題提出了結(jié)合虛擬鏈路動(dòng)態(tài)帶寬分配的虛擬網(wǎng)絡(luò)功能調(diào)度模型,并設(shè)計(jì)了聯(lián)合遺傳和禁忌搜索的啟發(fā)式算法(GATS)進(jìn)行求解。GATS算法通過混合整數(shù)規(guī)劃的方法準(zhǔn)確求出鏈路帶寬分配的閉式最優(yōu)解,提高了帶寬分配的細(xì)粒度,同時(shí)利用禁忌搜索算法的局部搜索能力,有效避免了遺傳算法的早熟問題。實(shí)驗(yàn)結(jié)果表明,GATS算法在收斂速度上具有較高優(yōu)勢,而且獲得了更好的調(diào)度方案,能夠滿足5G低時(shí)延場景的需求,增加了用戶的服務(wù)體驗(yàn)和運(yùn)營商的收益。但是,本文提出的算法由于融合了2種算法,增加了算法的時(shí)間復(fù)雜度。下一步,將在保證求得更優(yōu)調(diào)度方案的前提下,研究算法時(shí)間復(fù)雜度更低的算法。

參考文獻(xiàn):

[1]張平, 陶運(yùn)錚, 張治. 5G若干關(guān)鍵技術(shù)評述 [J]. 通信學(xué)報(bào), 2016, 37(7): 15-29.

ZHANG Ping, TAO Yunzheng, ZHANG Zhi. Survey of several key technologies for 5G [J]. Journal on Communications, 2016, 37(7): 15-29.

[2]MARTINI B, PAGANELLI F, CAPPANERA P, et al. Latency-aware composition of virtual functions in 5G [C]∥IEEE Conference on Network Softwarization: Software-Defined Infrastructures for Networks, Clouds, IoT and Services, NETSOFT 2015. Piscataway, NJ, USA: IEEE, 2015: 1-6.

[3]ABDELWAHAB S, HAMDAOUI B, GUIZANI M, et al. Network function virtualization in 5G [J]. IEEE Communications Magazine, 2016, 54(4): 84-91.

[4]劉彩霞, 盧干強(qiáng), 湯紅波, 等. 一種基于Viterbi算法的虛擬網(wǎng)絡(luò)功能自適應(yīng)部署方法 [J]. 電子與信息學(xué)報(bào), 2016, 38(11): 2922-2930.

LIU Caixia, LU Ganqiang, TANG Hongbo, et al. Adaptive deployment method for virtualized network function based on Viterbi algorithm [J]. Journal of Electronics & Information Technology, 2016, 38(11): 2922-2930.

[5]KREUTZ D, RAMOS F M V, ESTEVES P, et al. Software-defined networking: A comprehensive survey [J]. Proceedings of the IEEE, 2014, 103(1): 10-13.

[6]CHENG G, CHEN H, HU H, et al. Enabling network function combination via service chain instantiation [J]. Computer Networks, 2015, 92: 396-407.

[7]HERRERA J G, BOTERO J F. Resource allocation in NFV: A comprehensive survey [J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 518-532.

[8]OSSEIRAN A, BOCCARDI F, BRAUN V, et al. Scenarios for 5G mobile and wireless communications: the vision of the METIS project [J]. IEEE Communications Magazine, 2014, 52(5): 26-35.

[9]袁泉, 湯紅波, 黃開枝, 等. 基于Q-learning算法的vEPC虛擬網(wǎng)絡(luò)功能部署方法 [J]. 通信學(xué)報(bào), 2017, 38(8): 172-182

YUAN Quan, TANG Hongbo, HUANG Kaizhi, et al. Deployment method for vEPC virtualized network function via Q-learning [J]. Journal on Communications, 2017, 38(8): 172-182.

[10] RIERA J F, ESCALONA E, BATALLE J, et al. Virtual network function scheduling: Concept and challenges [C]∥2014 International Conference on Smart Communications in Network Technologies. Piscataway, NJ, USA: IEEE, 2014: 6867768.

[11] LI X, QIAN C. Low-complexity multi-resource packet scheduling for network function virtualization [C]∥Proceedings of 2015 IEEE Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2015: 1400-1408.

[12] LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions [C]∥Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway, NJ, USA: IEEE, 2015: 98-106.

[13] QU L, ASSI C, SHABAN K. Delay-aware scheduling and resource optimization with network function virtualization [J]. IEEE Transactions on Communications, 2016, 64(9): 3746-3758.

[14] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: State-of-the-art and research challenges [J]. IEEE Communications on Surveys & Tutorials, 2016, 18(1): 236-262.

[15] GUO J, LIU F, LUI J, et al. Fair network bandwidth allocation in IaaS datacenters via a cooperative game approach [J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 873-886.

[16] GUO J, LIU F, HUANG X, et al. On efficient bandwidth allocation for traffic variability in datacenters [C]∥ Proceedings of IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2014: 1572-1580.

[17] GAMBARDELLA L M, MASTROLILLI M. Effective neighborhood functions for the flexible job shop problem [J]. Journal of Scheduling, 1996, 3(3): 3-20.

[本刊相關(guān)文獻(xiàn)鏈接]

王琳,錢德沛,王銳,等.高效支持負(fù)載聚合的程序資源敏感度獲取及分析方法.2017,51(4):79-84.[doi:10.7652/xjtuxb201704012]

朱正倉,趙季紅,唐睿,等.移動(dòng)中繼協(xié)助下終端直通中的模式選擇和資源分配方案.2016,50(10):111-117.[doi:10.7652/xjtuxb201610017]

趙輝,鄭慶華,張未展,等.多版本視頻點(diǎn)播流媒體服務(wù)器集群資源分配方法.2016,50(6):30-35.[doi:10.7652/xjtuxb 201606005]

周墨頌,朱正東,董小社,等.采用資源劃分的云環(huán)境下Hadoop資源許可調(diào)度方法.2015,49(8):69-74.[doi:10.7652/xjtuxb201508012]