吳宇彤, 周金和
(北京信息科技大學(xué) 信息與通信工程學(xué)院, 北京 100101)
在傳統(tǒng)網(wǎng)絡(luò)中,網(wǎng)絡(luò)功能由不同的硬件設(shè)備提供,網(wǎng)絡(luò)服務(wù)提供商(Network Service Provider,NSP) 需要在用戶請(qǐng)求新服務(wù)時(shí)部署大量新設(shè)備,價(jià)格昂貴且靈活性差,加大了資本支出和運(yùn)營(yíng)費(fèi)用。為解決上述問題,軟件定義網(wǎng)絡(luò)/網(wǎng)絡(luò)功能虛擬化技術(shù)應(yīng)運(yùn)而生。軟件定義網(wǎng)絡(luò)(Software Defined Networking,SDN) 技術(shù)通過解耦控制平面和用戶平面以實(shí)現(xiàn)集中控制,加強(qiáng)網(wǎng)絡(luò)的靈活性。網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization,NFV) 架構(gòu)使網(wǎng)絡(luò)功能從硬件中抽象出來并能在虛擬機(jī)上運(yùn)行。NSP提供的服務(wù)通常是通過服務(wù)功能鏈(Service Function Chaining,SFC) 來實(shí)現(xiàn)的。SFC是指引導(dǎo)流量按序通過一組虛擬網(wǎng)絡(luò)功能(Virtual Network Function,VNF)以提供端到端服務(wù)的過程。
近年來,關(guān)于SFC部署的研究已成為一個(gè)熱門話題。但現(xiàn)有研究?jī)H關(guān)注靜態(tài)SFC編排,未考慮服務(wù)請(qǐng)求的動(dòng)態(tài)變化[1-2];或者未考慮SFC與新型網(wǎng)絡(luò)技術(shù)的結(jié)合[3-5],如SRv6技術(shù);或者僅考慮一個(gè)或兩個(gè)優(yōu)化目標(biāo),沒有考慮動(dòng)態(tài)SFC部署的多目標(biāo)優(yōu)化[5-6]。
目前部署 SFC 的一個(gè)關(guān)鍵問題是如何在保證提供服務(wù)的同時(shí)降低端到端時(shí)延、資源消耗和負(fù)載壓力。為應(yīng)對(duì)以上挑戰(zhàn),本文首先引入在 NFV架構(gòu)下的SFC動(dòng)態(tài)部署問題,然后將SFC部署與SRv6機(jī)制相結(jié)合,設(shè)計(jì)SFC動(dòng)態(tài)編排(SFC Dynamic Orchestration,SFCDO) 算法。算法包括兩步:第一步選用廣度優(yōu)先搜索(Breadth-first Search,BFS) 算法遍歷物理網(wǎng)絡(luò)并找到可部署SFC的最短路徑;第二步選擇啟發(fā)式的蟻群優(yōu)化算法(Ant Colony Optimization,ACO) 得到最佳且可動(dòng)態(tài)調(diào)整的SFC部署方案。
與現(xiàn)有文獻(xiàn)相比,本文考慮的SFC部署是動(dòng)態(tài)的,同時(shí)采用SRv6技術(shù),結(jié)合NFV架構(gòu)對(duì)SFC進(jìn)行編排和部署。并且本文提出的SFCDO算法在考慮網(wǎng)絡(luò)負(fù)載均衡的同時(shí),可以有效降低用戶到NSP的延遲和服務(wù)傳輸?shù)膸捹Y源消耗,是對(duì)SFC部署的多目標(biāo)聯(lián)合優(yōu)化。該方案可以應(yīng)用于網(wǎng)絡(luò)功能的編排,為用戶提供高效及時(shí)的各類服務(wù)。
本文采用的NFV架構(gòu)如圖1所示。
圖1 ETSI NFV架構(gòu)圖
NFV編排器(NFV Orchestration,NFVO) 用于管理 VNF 操作,例如實(shí)例化、刪除和擴(kuò)展VIM。VNF管理器(VNF Manager,VNFM) 負(fù)責(zé)管理VNF實(shí)例。在傳統(tǒng)NFV架構(gòu)中,網(wǎng)絡(luò)全局視圖中流量的轉(zhuǎn)發(fā)規(guī)則由SDN控制器提供。在這個(gè)架構(gòu)中,由于結(jié)合SRv6技術(shù),所以使用SR控制器來發(fā)送段標(biāo)簽。根據(jù)源路由機(jī)制,控制器只需將所有信息統(tǒng)一發(fā)送到源節(jié)點(diǎn)即可。這一操作可減輕控制器負(fù)載,其他節(jié)點(diǎn)不需要維護(hù)每個(gè)流的狀態(tài)。3GPP中對(duì)網(wǎng)絡(luò)功能進(jìn)行了定義,每個(gè)網(wǎng)絡(luò)功能(Network Function,NF)可提供不同服務(wù)。本文中假設(shè)一個(gè)NF提供一個(gè)特定服務(wù),架構(gòu)中可用VNF來表示NF。
接下來將說明基于 NFV架構(gòu)的SFC編排,如圖2所示。在域中,一個(gè)NFV節(jié)點(diǎn)托管多個(gè)VNF。與VNF相關(guān)的數(shù)據(jù)包在入口節(jié)點(diǎn)中被分類。根據(jù)一個(gè)SFC的指示,流將依次通過不同VNF。
圖2 基于NFV的SFC編排示意圖
圖3描述了數(shù)據(jù)包在SRv6機(jī)制下的傳輸過程和過程中報(bào)文的變化。數(shù)據(jù)包首先通過分類器Head,再在段標(biāo)簽指引下依次通過SFC中的每個(gè)VNF(VNF1→VNF4→VNF6) 。數(shù)據(jù)包中封裝有 IPv6 標(biāo)頭和包含分段列表的 SRH。
圖3 SRH工作流示意圖
首先,本文采用一個(gè)無向圖G=(V,E)來表示底層物理網(wǎng)絡(luò),其中,V={v1,v2,v3,…,v|M|}表示物理節(jié)點(diǎn)集合,E={e1,e2,e3,…,e|N|}表示物理鏈接集合,物理節(jié)點(diǎn)和物理鏈接的總數(shù)分別為|M|和|N|。節(jié)點(diǎn)負(fù)載率L(vi)由公式(1)進(jìn)行計(jì)算:
(1)
式中:vi表示一個(gè)物理節(jié)點(diǎn),其具有一定的計(jì)算資源,可用c(vi)表示;r(vi)表示剩余計(jì)算資源。
一個(gè)物理鏈接ei也可表示為一個(gè)節(jié)點(diǎn)對(duì),如公式(2)所示,其中eiva和eivb代表鏈接ei兩端的節(jié)點(diǎn)。
ei=(eiva,eivb),?ei∈E。
(2)
b(ei)表示物理鏈路上的帶寬資源,剩余帶寬資源用r(ei)表示,鏈路負(fù)載率L(ei)用公式(3)進(jìn)行計(jì)算:
(3)
p(vi,vj)表示從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的一條路徑,由公式(4)可知,p(vi,vj)中包含該路徑上所有物理鏈接。
p(vi,vj)={em,…,en}?E,?vi,vj∈V。
(4)
D[p(vi,vj)]表示路徑p(vi,vj)的端到端時(shí)延,這一參數(shù)包括dprop、dproc和dtrans三個(gè)部分,如公式(5)所示。其中,dprop指的是傳播時(shí)延,因?yàn)楸疚牟豢紤]跨域部署SFC,因此設(shè)dprop為0;dproc表示數(shù)據(jù)包處理時(shí)延,為固定值,可不予考慮,故端到端時(shí)延等同于傳輸時(shí)延dtrans,由公式(6)進(jìn)行計(jì)算。
D[p(vi,vj)]=dprop+dproc+dtrans,
(5)
D[p(vi,vj)]=∑ek∈p(vi,vj)d(ek),?vi,vj∈V。
(6)
以上是對(duì)物理網(wǎng)絡(luò)的參數(shù)建模,接下來對(duì)SFC請(qǐng)求中的參數(shù)進(jìn)行定義。
一個(gè)SFC請(qǐng)求可定義為SFC=(VS,ES,S,D,F)。其中,VS={vnf1,vnf2,vnf3,…,vnf|VS|}表示SFC中所有VNF的集合,ES={vl1,vl2,vl3,…,vl|ES|}表示SFC中所有虛擬鏈接的集合,|VS|和|ES|分別表示VNF和虛擬鏈接的數(shù)量,S和D分別是SFC的起始節(jié)點(diǎn)和目的節(jié)點(diǎn),F(xiàn)是經(jīng)過該SFC的有序流。
一個(gè)VNF所需的計(jì)算資源為c(vnfi),V(vnfi)表示部署vnfi的物理節(jié)點(diǎn)。假設(shè)一個(gè)二元變量M(vnfi,vj),若vnfi成功部署在節(jié)點(diǎn)vj上,則M(vnfi,vj)=1;反之,M(vnfi,vj)=0。以上過程由公式(7)定義:
M(vnfi,vj)∈{0,1},?vnfi∈VS,?vj∈V。
(7)
b(vli)表示部署一個(gè)虛擬鏈接vli所需的帶寬資源。一個(gè)虛擬鏈接可表示為一對(duì)VNF,由公式(8)可知,vlivnfa和vlivnfb分別是虛擬鏈接vli兩端的VNF。
vli=(vlivnfa,vlivnfb),?vli∈ES。
(8)
同樣地,定義另一個(gè)二元變量N(vli,ej)來描述虛擬鏈接的部署情況。如果N(vli,ej)=1,說明虛擬鏈接vli成功部署在物理鏈接ej上;反之,則N(vli,ej)=0。以上過程由公式(9)表示:
N(vli,ej)∈{0,1},?vli∈ES,?ej∈E。
(9)
p(vli)表示部署虛擬鏈接vli的物理鏈接,E(vli)表示vli部署的路徑,D(vli)表示vli的延時(shí),B(vli)表示vli部署路徑的帶寬資源消耗。公式(10)~(12)分別定義以上變量,其中NUM[E(vli)]是指路徑E(vli)上的鏈接數(shù)量。
E(vli)=p[V(vlivnfa),V(vlivnfb)],?vli∈ES,
(10)
D(vli)=d[E(vli)]=∑ek∈E(vli)d(ek),?vli∈ES,
(11)
B(vli)=b[E(vli)]=b(vli)×NUM[E(vli)]。
(12)
SFC中的源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D分別代表網(wǎng)絡(luò)服務(wù)提供商和用戶的位置。除此之外,標(biāo)準(zhǔn)文件RFC7665中定義SFC是有序的, 因此在公式(13)中用F表示這種有序的流。
(13)
在部署過程中,Ta(SFCi)代表當(dāng)前SFC和上一個(gè)SFC之間的到達(dá)時(shí)間間隔,F(xiàn)s(SFCi)代表當(dāng)前SFC的服務(wù)時(shí)間,TR(SFCi)代表響應(yīng)一個(gè)SFC所需的時(shí)間。DL(SFCi)代表一個(gè)SFC的端到端時(shí)延,BW(SFCi)代表部署它所需的帶寬資源,分別由公式(14)和(15)計(jì)算。
DL(SFCi)=∑vlk∈ESD(vlk),?SFCi∈SSFC,
(14)
BW(SFCi)=∑vlk∈ESB(vlk),?SFCi∈SSFC。
(15)
SFC部署情況可用二元變量P(SFCi)來描述:如果SFC部署成功,則P(SFCi)=1;反之,P(SFCi)=0。以上過程由公式(16)表示:
P(SFCi)∈{0,1},?SFCi∈SSFC。
(16)
在一個(gè)完整的SFC部署過程中,所有的SFC請(qǐng)求用SSFC={SFC1,SFC2,SFC3,…,SFC|SSFC|}代表,其中|SSFC|是請(qǐng)求總數(shù)。NUMsuss(SSFC)代表SFC成功部署的數(shù)量,DLall(SSFC)代表總延時(shí),BWall(SSFC)代表總帶寬消耗,TR(SFCi)代表響應(yīng)一個(gè)SFC所需的時(shí)間,TRall(SSFC)代表SSFC總響應(yīng)時(shí)間,分別由公式(17)~(20)計(jì)算,本文僅考慮成功部署的情況。
NUMsuss(SSFC)=∑SFCk∈SSFCP(SFCk),
(17)
DLall(SSFC)=∑SFCk∈SSFCDL(SFCk)×P(SFCk),
(18)
BWall(SSFC)=∑SFCk∈SSFCBW(SFCk)×P(SFCk),
(19)
TRall(SSFC)=∑SFCk∈SSFCTR(SFCk)×P(SFCk)。
(20)
SFC的動(dòng)態(tài)編排需考慮服務(wù)請(qǐng)求的到達(dá)和離開。部署過程中,Ta(SFCi)代表當(dāng)前SFC和上一個(gè)SFC之間的到達(dá)時(shí)間間隔,F(xiàn)s(SFCi)代表當(dāng)前SFC的服務(wù)時(shí)間。一個(gè)服務(wù)請(qǐng)求的動(dòng)態(tài)到達(dá)和離開都遵循泊松分布,因此,SFC到達(dá)時(shí)間間隔和服務(wù)時(shí)間這兩個(gè)參數(shù)獨(dú)立同分布,均遵循指數(shù)分布,計(jì)算公式如(21)和(22)所示。
(21)
(22)
同時(shí)在部署過程中,LB(SFCi)表示物理網(wǎng)絡(luò)的負(fù)載率,由公式(23)可知,它由節(jié)點(diǎn)負(fù)載率和鏈路負(fù)載率共同決定,其中α是權(quán)重因子。
LB(SFCi)=α×L(vi)+(1-α)×L(ei)。
(23)
當(dāng)虛擬網(wǎng)絡(luò)功能vnfi部署到物理網(wǎng)絡(luò)節(jié)點(diǎn)V(vnfi)上時(shí),需要確保vnfi所需計(jì)算資源應(yīng)小于物理節(jié)點(diǎn)剩余計(jì)算資源r[V(vnfi)],且物理節(jié)點(diǎn)消耗的總計(jì)算資源應(yīng)小于其自身固有計(jì)算資源。以上約束由公式(24)和(25)定義:
r[V(vnfi)]≥c(vnfi),?vnfi∈V;
(24)
c(vj)≥∑SFCk∈SSFC∑vnfi∈VSM(vnfi,vj)×c(vnfi),?vj∈V。
(25)
在SFC部署過程中,每個(gè)VNF只能映射到一個(gè)物理節(jié)點(diǎn)上,兩者是一對(duì)一映射的關(guān)系。這樣可以簡(jiǎn)化SFC部署方案,避免出現(xiàn)VNF集中部署在某個(gè)節(jié)點(diǎn)的情況,更好實(shí)現(xiàn)負(fù)載平衡。以上過程約束由公式(26)、(27)給出:
0≤∑vj∈VM(vnfi,vj)≤1,?vnfi∈VS;
(26)
0≤∑vnfi∈VSM(vnfi,vj)≤1,?vj∈V。
(27)
對(duì)于一個(gè)虛擬鏈接vli和它所在的物理部署路徑E(vli),需確保vli的帶寬消耗小于物理路徑E(vli)的剩余帶寬r[E(vli)]。物理鏈接ej消耗的總帶寬需小于自身固有帶寬資源,同時(shí),一個(gè)物理鏈接ej僅能部署一個(gè)虛擬鏈接vli。以上約束由公式(28)~(30)表示:
r[E(vli)]≥b(vli),?vli∈ES;
(28)
b(ej)≥∑SFCk∈SSFC∑vli∈ESN(vli,ej)×b(vli),?ej∈E;
(29)
0≤∑vli∈ESN(vli,ej)≤1,?ej∈E。
(30)
首先使用BFS算法(算法1)尋找源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D間的最短物理路徑。NSP和用戶分別位于源點(diǎn)和目的節(jié)點(diǎn)上,BFS利用序列遍歷查找最短路徑的長(zhǎng)度,執(zhí)行步驟如下:
輸入:物理網(wǎng)絡(luò)G=(V,E);源節(jié)點(diǎn)S;目的節(jié)點(diǎn)D。
輸出:最短路徑的長(zhǎng)度;最短路徑的拓?fù)湫畔ⅰ?/p>
初始化:queue=?,
將節(jié)點(diǎn)S加入隊(duì)列queue;
while queue≠?,do
將下一個(gè)節(jié)點(diǎn)加入list1;
標(biāo)記S為已查詢;
將S加入list2;
hop=hop+1;
ifD在隊(duì)列queue中,do
將所有節(jié)點(diǎn)加入list2;
清空list1;
length=hop
return length 和 path
end if
end while
算法1的輸入是物理網(wǎng)絡(luò)拓?fù)湫畔?。鄰接表用于存?chǔ)網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈接的位置信息。SFC請(qǐng)求的起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)已知,該算法輸出起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間最短路徑的長(zhǎng)度。
首先執(zhí)行初始化操作。變量queue用于進(jìn)行網(wǎng)絡(luò)遍歷和路徑查找。queue遵循先進(jìn)先出原則,在開始時(shí)置為空。此外設(shè)置一些用于記錄的參數(shù)。queue是當(dāng)前到達(dá)節(jié)點(diǎn),list1記錄待檢查節(jié)點(diǎn),list2記錄已檢查節(jié)點(diǎn),hop記錄到達(dá)該節(jié)點(diǎn)時(shí)的路徑長(zhǎng)度,path記錄當(dāng)前節(jié)點(diǎn)的路徑拓?fù)湫畔?,length是節(jié)點(diǎn)S和D之間的最短路徑長(zhǎng)度。
BFS的輸出結(jié)果將作為SFC 部署的基礎(chǔ)信息。VNF 和虛擬鏈路會(huì)分別部署在物理網(wǎng)絡(luò)最短路徑的節(jié)點(diǎn)和鏈接上。
本文使用ACO算法來得到最佳的SFC動(dòng)態(tài)部署方案。
ACO依賴于信息素濃度初值,這會(huì)導(dǎo)致局部最優(yōu)解。因此,本文采用遺傳算法(Genetic Algorithm,GA)獲取信息素濃度初值?;贕A的交叉變異因子,可改進(jìn)信息素濃度設(shè)置,增強(qiáng)傳統(tǒng)ACO的全局搜索能力。
具體做法是:在算法的早期階段,使用 GA 來初始化種群,因?yàn)樗哂休^快的初始收斂速度,所以很容易得到更好的解。接下來,將這個(gè)較好的解作為ACO的初始信息素輸入,然后運(yùn)行ACO算法。因?yàn)椴捎肎A進(jìn)行預(yù)處理,不易陷入局部最優(yōu),得到的最優(yōu)解更接近實(shí)際的最優(yōu)解。
蟻群優(yōu)化算法(算法2)中,螞蟻數(shù)量用m表示,所有節(jié)點(diǎn)之間的信息素用矩陣P表示,Bestlength表示最短路徑,Bestscheme表示最佳部署路徑;Tabu是一張存放所有已訪問節(jié)點(diǎn)的表,Allowed是存儲(chǔ)未訪問節(jié)點(diǎn)的表;Matrix Delta存儲(chǔ)一個(gè)循環(huán)中的信息素信息;整個(gè)路徑的開銷用 Tourlength表示。假設(shè)算法運(yùn)行次數(shù)為 NUM,總運(yùn)行次數(shù)為MAX_GEN,運(yùn)行時(shí)間為t。算法流程如下:
輸入:物理網(wǎng)絡(luò)G=(V,E);源節(jié)點(diǎn)S;目的節(jié)點(diǎn)D。
輸出:最佳部署路徑Bestscheme。
初始化:t=0,Bestlength→∞,Besttour=0,Delta=0,Tabu=0,Allowed=0
for 每一條鏈路 do
設(shè)置從遺傳算法中得到的信息素初值p;
end for
將所有節(jié)點(diǎn)添加到表 Allowed中;
for 每只螞蟻kdo
隨機(jī)選擇初始起點(diǎn);
將源節(jié)點(diǎn)S加入表Tabu;
在表 Allowed中刪除節(jié)點(diǎn)S;
由公式(31)尋找下一節(jié)點(diǎn)T;
將T加入表Tabu;
在表 Allowed中刪除節(jié)點(diǎn)T;
end for
由公式(32)計(jì)算啟發(fā)式因子Delta;
計(jì)算Tourlength的值;
if Tourlength < Bestlength then
Bestlength = Tourlength;
Besttour = Tabu;
else
continue;
end if
NUM=NUM+1;
t=t+nt;
由公式(33)更新矩陣P;
if NUM=MAX_GEN then
return Besttour;
else
再次初始化;
end
螞蟻從起點(diǎn)S出發(fā),下一個(gè)節(jié)點(diǎn)的選擇概率由公式(31)計(jì)算,啟發(fā)式因子由式(32)計(jì)算。
(31)
(32)
公式(31)中,τij(t)代表節(jié)點(diǎn)i和j在時(shí)間t的信息素濃度,α和β分別代表信息素濃度和啟發(fā)因子的權(quán)重;ηij代表從節(jié)點(diǎn)i到j(luò)的可見度,是兩節(jié)點(diǎn)距離dij的倒數(shù),由公式(32)可知,dij越小,ηij越大。信息素矩陣由公式(33)進(jìn)行計(jì)算和更新,τij(t+n)代表時(shí)間t+n時(shí)節(jié)點(diǎn)i和j的信息素濃度。公式(34)中Δτijk代表螞蟻k在節(jié)點(diǎn)i和j間留下的信息素。公式(35)中Q表示一個(gè)正常數(shù),Lk代表螞蟻在一次迭代中遍歷的路徑距離,即Tourlength。
τij(t+n)=(1-ρ)·τij(t)+Δτij,
(33)
(34)
(35)
本文提出的算法分為兩步,下面分別分析其復(fù)雜度。
在廣度優(yōu)先算法中,假設(shè)底層物理網(wǎng)絡(luò)有m個(gè)節(jié)點(diǎn)和n個(gè)鏈接。每個(gè)節(jié)點(diǎn)最多只能進(jìn)出一個(gè)隊(duì)列一次,因此操作隊(duì)列的總時(shí)間為O(m)。網(wǎng)絡(luò)拓?fù)湫畔⒋鎯?chǔ)在鄰接表中,BFS只在節(jié)點(diǎn)彈出隊(duì)列時(shí)掃描鄰接表,每個(gè)頂點(diǎn)的鄰接表最多掃描一次,因此掃描鄰接表的總時(shí)間是O(n)。故算法1的時(shí)間復(fù)雜度為O(m+n)。
在蟻群優(yōu)化算法中,假設(shè)螞蟻數(shù)量有k只,底層物理網(wǎng)絡(luò)的節(jié)點(diǎn)有m個(gè),則通過對(duì)算法各步驟的分析可得到算法2的復(fù)雜度為O(m2+m)[7]。
因此,本文所提SFCDO算法的復(fù)雜度為O(m2)。本文算法與可靠性保證算法(Ensure Reliability,ER)[8]、基于負(fù)載均衡的可靠性保證算法(Ensure Reliability Cost Saving, ER_CS)[8]和貪婪-模擬退火算法(Greedy-Simulated Annealing, G-SA)[6]的復(fù)雜度對(duì)比如表1所示。
表1 復(fù)雜度對(duì)比
本節(jié)通過模擬仿真試驗(yàn)驗(yàn)證本文算法的性能,并將其與現(xiàn)有ER[8]、ER-CS[8]和G-SA[6]三種算法進(jìn)行對(duì)比。
本文使用Java搭建仿真環(huán)境,仿真網(wǎng)絡(luò)使用Intel i7 4.0 GHz CPU、9.8 GB RAM的主機(jī),采用GT-ITM的Waxman 2 拓?fù)淠P停?隨機(jī)生成不同尺寸的網(wǎng)絡(luò)實(shí)例用于SFC部署。在實(shí)驗(yàn)所用物理網(wǎng)絡(luò)中,設(shè)定小拓?fù)渚W(wǎng)絡(luò)含有50個(gè)節(jié)點(diǎn),大拓?fù)渚W(wǎng)絡(luò)有200 個(gè)節(jié)點(diǎn)。綜合考慮SFC的部署成本和時(shí)間,使用Intel i7 CPU實(shí)現(xiàn)兩種拓?fù)渚W(wǎng)絡(luò)。
參照文獻(xiàn)[9]中的實(shí)驗(yàn)參數(shù)設(shè)置,本文設(shè)置的實(shí)驗(yàn)參數(shù)見表2。
表2 仿真參數(shù)
本文選擇的優(yōu)化目標(biāo)包括平均端到端時(shí)延、平均帶寬資源消耗、最大節(jié)點(diǎn)負(fù)載率、最大鏈路負(fù)載率和部署成功率。
4.2.1 平均端到端時(shí)延
如圖4和圖5所示,隨著SFC長(zhǎng)度增加,四種算法產(chǎn)生的平均端到端時(shí)延隨之增加。一般來說,對(duì)于SFCDO和其他三種對(duì)比算法,時(shí)延的增長(zhǎng)速度與底層物理鏈路的增長(zhǎng)速度幾乎相同。
圖4 小拓?fù)渲械钠骄说蕉藭r(shí)延
圖5 大拓?fù)渲械钠骄说蕉藭r(shí)延
在兩種拓?fù)渲?,SFCDO 的端到端延遲均小于對(duì)比算法, 原因是本文所提算法傾向于跳數(shù)更少的最短路徑,因此可以有效減少鏈路傳輸時(shí)延。仿真結(jié)果表明,與對(duì)比算法相比,SFCDO算法在小拓?fù)浜痛笸負(fù)渲械亩说蕉藭r(shí)延分別平均減少了24%和20%。
4.2.2 平均帶寬資源消耗
平均帶寬資源消耗的仿真結(jié)果如圖6和圖7所示。在兩種拓?fù)浣Y(jié)構(gòu)中,隨著SFC長(zhǎng)度增加,帶寬消耗相應(yīng)增加。SFCDO的帶寬消耗總是小于其他算法,這是由于在選擇部署虛擬鏈接的物理鏈路時(shí),本文所用BFS算法會(huì)選擇鏈接更少的路徑,因此部署消耗帶寬相應(yīng)減少。在小拓?fù)浜痛笸負(fù)渲?,這一參數(shù)分別平均優(yōu)化21%和15%。
圖6 小拓?fù)渲械钠骄鶐捹Y源消耗
圖7 大拓?fù)渲械钠骄鶐捹Y源消耗
4.2.3 最大節(jié)點(diǎn)負(fù)載率
圖8和圖9展示了兩種拓?fù)渲械淖畲蠊?jié)點(diǎn)負(fù)載率。最大節(jié)點(diǎn)負(fù)載率隨SFC長(zhǎng)度增加而增長(zhǎng),但SFCDO中的節(jié)點(diǎn)負(fù)載率總是低于其他三種算法。兩種拓?fù)渲械那€走勢(shì)有所不同:在圖8小拓?fù)渚W(wǎng)絡(luò)中,四條曲線相距很近,但當(dāng)SFC長(zhǎng)度大于6時(shí),三種對(duì)比算法的節(jié)點(diǎn)負(fù)載率都有下降,因?yàn)镾FC長(zhǎng)度大于6時(shí),對(duì)比算法的部署成功率下降,它們的節(jié)點(diǎn)負(fù)載率也相應(yīng)受到影響。同時(shí),SFCDO節(jié)點(diǎn)負(fù)載率始終低于對(duì)比算法,說明該算法可以有效避免節(jié)點(diǎn)擁塞。在圖9中,SFCDO的曲線始終低于對(duì)比算法。當(dāng)SFC長(zhǎng)度增加時(shí),對(duì)比算法的最大節(jié)點(diǎn)負(fù)載率幾乎達(dá)到1,但SFCDO這一參數(shù)的值總是低于0.6,說明在大拓?fù)渲?,啟發(fā)式蟻群算法可以根據(jù)之前的部署情況調(diào)整部署方案,所以節(jié)點(diǎn)負(fù)載率始終保持在較低水平。
圖8 小拓?fù)渲械淖畲蠊?jié)點(diǎn)負(fù)載率
圖9 大拓?fù)渲械淖畲蠊?jié)點(diǎn)負(fù)載率
4.2.4 最大鏈路負(fù)載率
圖10和圖11展示了兩種拓?fù)渲凶畲箧溌坟?fù)載率的仿真結(jié)果。最大鏈路負(fù)載率會(huì)隨著SFC長(zhǎng)度增加而增長(zhǎng), 總體上其他三種算法的曲線總是高于本文算法,大拓?fù)渲薪Y(jié)果更加明顯。因?yàn)樵诒疚乃惴ㄖ校褂孟伻核惴ú渴餠NF時(shí)會(huì)傾向于部署在負(fù)載率更低的節(jié)點(diǎn)上,相應(yīng)地,經(jīng)過這些節(jié)點(diǎn)的鏈路負(fù)載率也就更低。對(duì)比算法中,VNF總是部署在中心節(jié)點(diǎn)上,經(jīng)過的鏈路負(fù)載也高,因此它們的節(jié)點(diǎn)負(fù)載率和鏈路負(fù)載率均大于SFCDO算法。
圖10 小拓?fù)渲械淖畲箧溌坟?fù)載率
圖11 大拓?fù)渲械淖畲箧溌坟?fù)載率
4.2.5 部署成功率
圖12和圖13展示了在兩種不同拓?fù)渲蠸FC的部署成功率。在兩種拓?fù)渚W(wǎng)絡(luò)中,SFCDO算法的成功率均保持在95%以上,并且不會(huì)隨著SFC長(zhǎng)度的增加而降低。由前文可知,本算法較好地提升了網(wǎng)絡(luò)負(fù)載,極少出現(xiàn)部署過載的中心節(jié)點(diǎn),因此部署成功率相對(duì)較高且穩(wěn)定。然而在對(duì)比算法中,隨著SFC長(zhǎng)度的增加,部署成功率會(huì)逐漸下降。在兩種拓?fù)浣Y(jié)構(gòu)中,SFCDO算法平均優(yōu)化部署成功率23%。
圖12 小拓?fù)涞牟渴鸪晒β?/p>
圖13 大拓?fù)涞牟渴鸪晒β?/p>
本文考慮基于NFV的SFC動(dòng)態(tài)編排和部署問題,首先提出可用于SFC編排的NFV架構(gòu),然后描述結(jié)合SRv6機(jī)制的SFC編排原理和工作流程,提出SFCDO算法用于提升部署過程的性能,包括端到端時(shí)延、帶寬資源消耗和負(fù)載均衡。仿真結(jié)果表明,本文算法在端到端時(shí)延、帶寬資源消耗和負(fù)載均衡方面均有所優(yōu)化,本文部署方案具有一定優(yōu)化效果。
在未來SFC部署問題的研究中,由于5G、6G、基于意圖的網(wǎng)絡(luò)等新型網(wǎng)絡(luò)通信架構(gòu)的出現(xiàn)和應(yīng)用,可進(jìn)一步考慮將機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等先進(jìn)技術(shù)融入到SFC部署問題中。同時(shí),5G異構(gòu)網(wǎng)絡(luò)中的資源調(diào)度也值得深入研究,高效的異構(gòu)網(wǎng)絡(luò)切換方案對(duì)于用戶QoS的提升和SFC服務(wù)提供也具有啟發(fā)意義。未來,我們將嘗試?yán)蒙疃葟?qiáng)化學(xué)習(xí)技術(shù)實(shí)現(xiàn)用戶意圖的轉(zhuǎn)化,并將其與SFC部署問題相結(jié)合,優(yōu)化其在新網(wǎng)絡(luò)架構(gòu)下的整體性能。