吳宇彤， 周金和

(北京信息科技大學(xué) 信息與通信工程學(xué)院， 北京 100101)

0 引 言

在傳統(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ù)通過(guò)解耦控制平面和用戶平面以實(shí)現(xiàn)集中控制，加強(qiáng)網(wǎng)絡(luò)的靈活性。網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization,NFV) 架構(gòu)使網(wǎng)絡(luò)功能從硬件中抽象出來(lái)并能在虛擬機(jī)上運(yùn)行。NSP提供的服務(wù)通常是通過(guò)服務(wù)功能鏈(Service Function Chaining,SFC) 來(lái)實(shí)現(xiàn)的。SFC是指引導(dǎo)流量按序通過(guò)一組虛擬網(wǎng)絡(luò)功能(Virtual Network Function,VNF)以提供端到端服務(wù)的過(guò)程。

近年來(lái)，關(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ù)。

1 系統(tǒng)架構(gòu)

本文采用的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控制器來(lái)發(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來(lái)表示NF。

接下來(lái)將說(shuō)明基于 NFV架構(gòu)的SFC編排，如圖2所示。在域中，一個(gè)NFV節(jié)點(diǎn)托管多個(gè)VNF。與VNF相關(guān)的數(shù)據(jù)包在入口節(jié)點(diǎn)中被分類。根據(jù)一個(gè)SFC的指示，流將依次通過(guò)不同VNF。

圖2 基于NFV的SFC編排示意圖

圖3描述了數(shù)據(jù)包在SRv6機(jī)制下的傳輸過(guò)程和過(guò)程中報(bào)文的變化。數(shù)據(jù)包首先通過(guò)分類器Head，再在段標(biāo)簽指引下依次通過(guò)SFC中的每個(gè)VNF(VNF1→VNF4→VNF6) 。數(shù)據(jù)包中封裝有 IPv6 標(biāo)頭和包含分段列表的 SRH。

圖3 SRH工作流示意圖

2 問題描述與建模

2.1 物理網(wǎng)絡(luò)

首先，本文采用一個(gè)無(wú)向圖G=(V,E)來(lái)表示底層物理網(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ù)建模，接下來(lái)對(duì)SFC請(qǐng)求中的參數(shù)進(jìn)行定義。

2.2 SFC請(qǐng)求

一個(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)過(guò)該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。以上過(guò)程由公式(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)來(lái)描述虛擬鏈接的部署情況。如果N(vli,ej)=1，說(shuō)明虛擬鏈接vli成功部署在物理鏈接ej上；反之，則N(vli,ej)=0。以上過(guò)程由公式(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)

2.3 動(dòng)態(tài)SFC部署

SFC中的源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D分別代表網(wǎng)絡(luò)服務(wù)提供商和用戶的位置。除此之外，標(biāo)準(zhǔn)文件RFC7665中定義SFC是有序的， 因此在公式(13)中用F表示這種有序的流。

(13)

在部署過(guò)程中，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)來(lái)描述：如果SFC部署成功，則P(SFCi)=1；反之，P(SFCi)=0。以上過(guò)程由公式(16)表示：

P(SFCi)∈{0,1},?SFCi∈SSFC。

(16)

在一個(gè)完整的SFC部署過(guò)程中，所有的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á)和離開。部署過(guò)程中，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í)在部署過(guò)程中，LB(SFCi)表示物理網(wǎng)絡(luò)的負(fù)載率，由公式(23)可知，它由節(jié)點(diǎn)負(fù)載率和鏈路負(fù)載率共同決定，其中α是權(quán)重因子。

LB(SFCi)=α×L(vi)+(1-α)×L(ei)。

(23)

2.4 網(wǎng)絡(luò)資源約束

當(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部署過(guò)程中，每個(gè)VNF只能映射到一個(gè)物理節(jié)點(diǎn)上，兩者是一對(duì)一映射的關(guān)系。這樣可以簡(jiǎn)化SFC部署方案，避免出現(xiàn)VNF集中部署在某個(gè)節(jié)點(diǎn)的情況，更好實(shí)現(xiàn)負(fù)載平衡。以上過(guò)程約束由公式(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)

3 算法設(shè)計(jì)

3.1 廣度優(yōu)先搜索算法

首先使用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;

清空l(shuí)ist1;

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)和鏈接上。

3.2 蟻群優(yōu)化算法

本文使用ACO算法來(lái)得到最佳的SFC動(dòng)態(tài)部署方案。

ACO依賴于信息素濃度初值，這會(huì)導(dǎo)致局部最優(yōu)解。因此，本文采用遺傳算法(Genetic Algorithm,GA)獲取信息素濃度初值?；贕A的交叉變異因子，可改進(jìn)信息素濃度設(shè)置，增強(qiáng)傳統(tǒng)ACO的全局搜索能力。

具體做法是：在算法的早期階段，使用 GA 來(lái)初始化種群，因?yàn)樗哂休^快的初始收斂速度，所以很容易得到更好的解。接下來(lái)，將這個(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)

3.3 算法復(fù)雜度分析與對(duì)比

本文提出的算法分為兩步，下面分別分析其復(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è)，則通過(guò)對(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ì)比

4 仿真與結(jié)果分析

本節(jié)通過(guò)模擬仿真試驗(yàn)驗(yàn)證本文算法的性能,并將其與現(xiàn)有ER[8]、ER-CS[8]和G-SA[6]三種算法進(jìn)行對(duì)比。

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文使用Java搭建仿真環(huán)境，仿真網(wǎng)絡(luò)使用Intel i7 4.0 GHz CPU、9.8 GB RAM的主機(jī)，采用GT-ITM的Waxman 2 拓?fù)淠Ｐ停?隨機(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 實(shí)驗(yàn)結(jié)果分析

4.2.1 平均端到端時(shí)延

如圖4和圖5所示，隨著SFC長(zhǎng)度增加，四種算法產(chǎn)生的平均端到端時(shí)延隨之增加。一般來(lái)說(shuō)，對(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ì)比算法，說(shuō)明該算法可以有效避免節(jié)點(diǎn)擁塞。在圖9中，SFCDO的曲線始終低于對(duì)比算法。當(dāng)SFC長(zhǎng)度增加時(shí)，對(duì)比算法的最大節(jié)點(diǎn)負(fù)載率幾乎達(dá)到1，但SFCDO這一參數(shù)的值總是低于0.6，說(shuō)明在大拓?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)樵诒疚乃惴ㄖ?，使用蟻群算法部署VNF時(shí)會(huì)傾向于部署在負(fù)載率更低的節(jié)點(diǎn)上，相應(yīng)地，經(jīng)過(guò)這些節(jié)點(diǎn)的鏈路負(fù)載率也就更低。對(duì)比算法中，VNF總是部署在中心節(jié)點(diǎn)上，經(jīng)過(guò)的鏈路負(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)部署過(guò)載的中心節(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>

5 結(jié)束語(yǔ)

本文考慮基于NFV的SFC動(dòng)態(tài)編排和部署問題，首先提出可用于SFC編排的NFV架構(gòu)，然后描述結(jié)合SRv6機(jī)制的SFC編排原理和工作流程，提出SFCDO算法用于提升部署過(guò)程的性能，包括端到端時(shí)延、帶寬資源消耗和負(fù)載均衡。仿真結(jié)果表明，本文算法在端到端時(shí)延、帶寬資源消耗和負(fù)載均衡方面均有所優(yōu)化，本文部署方案具有一定優(yōu)化效果。

在未來(lái)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ā)意義。未來(lái)，我們將嘗試?yán)蒙疃葟?qiáng)化學(xué)習(xí)技術(shù)實(shí)現(xiàn)用戶意圖的轉(zhuǎn)化，并將其與SFC部署問題相結(jié)合，優(yōu)化其在新網(wǎng)絡(luò)架構(gòu)下的整體性能。