劉 藝 張紅旗 楊英杰 常德顯

(解放軍信息工程大學(xué) 鄭州 450001) (河南省信息安全重點實驗室 鄭州 450001) (liuyi9582@126.com)

當(dāng)前，網(wǎng)絡(luò)中部署著大量的專用硬件設(shè)備(如防火墻和負(fù)載均衡器等)，為用戶及業(yè)務(wù)提供了種類繁多的服務(wù)功能[1]，并且網(wǎng)絡(luò)往往需要引導(dǎo)用戶或業(yè)務(wù)流按序經(jīng)過多個服務(wù)功能的處理，即以服務(wù)功能鏈[1](service function chain, SFC)的形式提供服務(wù).但是，現(xiàn)有的SFC實現(xiàn)方式依賴于路由器等轉(zhuǎn)發(fā)設(shè)備和防火墻等專用硬件設(shè)備[2]，不僅需要人工配置路由表項，過程繁瑣且易出錯[3]，而且專用硬件設(shè)備位置與網(wǎng)絡(luò)拓?fù)渚o耦合[4]，難以實現(xiàn)SFC的動態(tài)調(diào)整，如增加、移除服務(wù)功能或者改變服務(wù)功能的順序.

軟件定義網(wǎng)絡(luò)[5](software defined networking, SDN)和網(wǎng)絡(luò)功能虛擬化[6-7](network function virtualization, NFV)為靈活高效地實現(xiàn)SFC提供了新途徑.在利用NFV技術(shù)將SFC中的服務(wù)功能軟件化、并以虛擬網(wǎng)絡(luò)功能(virtual network function, VNF)的形式部署在通用服務(wù)器的基礎(chǔ)上，依照SFC的服務(wù)功能順序要求，借助SDN的流量管控能力引導(dǎo)流量按序經(jīng)過若干VNF，從而在網(wǎng)絡(luò)中實例化SFC，為用戶及業(yè)務(wù)提供服務(wù).由此，基于“SDN+NFV”實現(xiàn)SFC的關(guān)鍵在于解決SFC映射問題，即規(guī)劃服務(wù)功能的部署位置和服務(wù)功能間的流量路由路徑.然而，在底層網(wǎng)絡(luò)中，受軟件錯誤、硬件失效和黑客攻擊等事件的影響，節(jié)點和鏈路故障頻現(xiàn)，這會導(dǎo)致VNF失效或VNF間的連接路徑失效，進(jìn)而造成SFC不可用、網(wǎng)絡(luò)服務(wù)中斷，而且由于SFC共享底層網(wǎng)絡(luò)資源，即便是單點或單鏈路故障，也可能導(dǎo)致多個SFC無法正常提供服務(wù).因此，如何在底層網(wǎng)絡(luò)出現(xiàn)故障時保證SFC的正常運行成為亟待解決的問題，本文稱之為可生存SFC映射問題.

目前，底層網(wǎng)絡(luò)的單點和單鏈路故障出現(xiàn)頻率較高[8]，預(yù)留備用資源成為解決可生存SFC映射問題的通用方法，但該方法在提高SFC可生存能力的同時會增大底層網(wǎng)絡(luò)資源開銷[9]，進(jìn)而降低SFC映射的成功率.實際上，SFC的可生存能力需求與其所提供的服務(wù)的重要程度密切相關(guān)，比如為銀行提供加密通信服務(wù)的SFC必須24 h正常運行，而為普通網(wǎng)站提供審計或備份服務(wù)的SFC即使在短時間內(nèi)失效，也不會帶來嚴(yán)重?fù)p失.因此，為應(yīng)對底層網(wǎng)絡(luò)的單點和單鏈路故障，本文提出一種區(qū)分等級的可生存SFC映射方法.該方法根據(jù)SFC提供服務(wù)的重要程度，將SFC劃分為2個等級，即提供重要服務(wù)的關(guān)鍵SFC(key service function chain, KSFC)和提供普通服務(wù)的普通SFC(normal service function chain, NSFC)，分別采用保護(hù)和恢復(fù)策略解決可生存映射問題，從而兼顧提高SFC可生存能力和降低底層網(wǎng)絡(luò)資源開銷.此外，由于服務(wù)時延是評價服務(wù)質(zhì)量的重要指標(biāo)[10-11]，該方法將最小化服務(wù)時延作為映射SFC的重要考慮因素.本文的主要工作包括2個方面：

1) 采用混合整數(shù)線性規(guī)劃(MILP)為基于保護(hù)策略的KSFC可生存映射建模，并提出了面向KSFC的主備服務(wù)路徑構(gòu)建算法(primary-backup service path building, PBSP-Bld)求解該模型，從而在KSFC映射時預(yù)分配備用VNF和備用鏈路，并最小化KSFC的服務(wù)時延；

2) 采用MILP為基于恢復(fù)策略的NSFC可生存映射建模，并提出了面向NSFC的失效服務(wù)路徑重建算法(failed service path restoring, FSP-Res)求解該模型，從而在底層網(wǎng)絡(luò)出現(xiàn)故障后為失效NSFC重新分配節(jié)點和鏈路資源，并在盡可能多地恢復(fù)失效NSFC的同時最小化已恢復(fù)NSFC的服務(wù)時延.

1 相關(guān)工作

隨著SDN網(wǎng)絡(luò)架構(gòu)的逐步推廣與NFV技術(shù)的日益成熟，SFC映射問題成為研究熱點.已有研究大多將SFC映射建模為帶資源約束的優(yōu)化模型，并采用Gurobi優(yōu)化器等現(xiàn)有工具[12]或設(shè)計啟發(fā)式算法[13-14]進(jìn)行求解，但它們未考慮底層網(wǎng)絡(luò)發(fā)生故障的情況.

可生存SFC映射問題與可生存虛擬網(wǎng)絡(luò)映射問題(survivable virtual network embedding, SVNE)[9]類似，均是在不可靠的、共享的底層網(wǎng)絡(luò)中為帶有資源約束的邏輯拓?fù)浞峙湎鄳?yīng)資源，保證在網(wǎng)絡(luò)故障發(fā)生時能有效恢復(fù)受影響的邏輯拓?fù)?但二者存在諸多不同，如SFC中各服務(wù)功能有嚴(yán)格的順序約束，而虛擬網(wǎng)絡(luò)(virtual network, VN)只要求虛擬節(jié)點之間連通；在SFC映射時需要考慮服務(wù)功能類型和底層節(jié)點類型，而VN映射只涉及一種物理設(shè)備[15](即路由器)；只有全部服務(wù)功能正常運行，且服務(wù)功能間的流量路由路徑完整，SFC才能正常提供服務(wù)[16]，而只要VN是一個連通圖，虛擬網(wǎng)絡(luò)服務(wù)就可以保持連續(xù)性[17].由此可見，解決可生存SFC映射問題可借鑒SVNE研究成果，如SVNE主要采用保護(hù)和恢復(fù)2種策略[18].保護(hù)指事先預(yù)留備用資源以應(yīng)對可能的故障；恢復(fù)指在故障發(fā)生后實時地為失效部分重分配資源，但是仍需要根據(jù)SFC的特性提出針對性的解決方法.

目前，關(guān)于可生存SFC映射問題的研究剛剛起步，根據(jù)底層故障類型大致分為2類：

1) 面向單故障的可生存SFC映射.單故障指在一個時刻至多只有一個底層節(jié)點和或鏈路發(fā)生故障.文獻(xiàn)[19]通過快速啟用備用VNF和更新流量引導(dǎo)策略來恢復(fù)失效SFC，但未提出具體的VNF備份方法.文獻(xiàn)[20]在與同一交換機相連的2個服務(wù)器上分別部署主備VNF，但無法應(yīng)對交換機出現(xiàn)故障的情況.文獻(xiàn)[21]針對單點故障、單鏈路故障和單點-單鏈路故障3種情況，分別提出了基于保護(hù)策略的SFC映射方法，并將面向單點-單鏈路故障的SFC映射建模為ILP問題，采用CPLEX求解，但在SFC數(shù)量多或網(wǎng)絡(luò)規(guī)模大的情況下求解速度慢.

2) 面向多故障的可生存SFC映射.多故障指在一個時刻可能有多個底層節(jié)點和鏈路發(fā)生故障.文獻(xiàn)[22]提出了基于回溯機制的SFC備用資源分配方法，但回溯機制耗時長，且未考慮降低底層網(wǎng)絡(luò)資源開銷.文獻(xiàn)[16]以服務(wù)器失效時SFC中所有VNF仍正常運行的概率衡量SFC的可靠性，提出了基于聯(lián)合備份的SFC映射算法，但未考慮多條SFC共享備用資源.文獻(xiàn)[23]利用負(fù)載均衡器實現(xiàn)SFC備份，但它假設(shè)底層鏈路絕對可靠.

綜上，已有研究主要存在3點不足：1)大多通過大量預(yù)分配備用資源來增強SFC的可生存能力，導(dǎo)致底層網(wǎng)絡(luò)資源開銷大；2)大多關(guān)注如何在底層網(wǎng)絡(luò)資源有限的情況下為SFC分配足夠的運行資源，而對其自身的運行性能(如服務(wù)時延)缺乏考慮；3)基于優(yōu)化模型的映射方法的時間開銷大.

2 問題描述

本節(jié)首先給出了底層網(wǎng)絡(luò)、VNF和SFC的定義，之后在介紹基本SFC映射過程的基礎(chǔ)上引入可生存需求，對可生存SFC映射問題進(jìn)行了描述.表1是主要符號列表.

Table 1 Key Symbols Lists表1 主要符號列表

2.1 基本定義

定義1. 底層網(wǎng)絡(luò).底層網(wǎng)絡(luò)G=(V,E)，其中，v∈V和(u,v)∈E分別是底層節(jié)點和底層鏈路.根據(jù)SFC參考架構(gòu)[24]，底層節(jié)點分為3類：1)訪問節(jié)點vA∈VA，表示流量進(jìn)出網(wǎng)絡(luò)的交換機；2)服務(wù)節(jié)點vS∈VS，表示服務(wù)功能轉(zhuǎn)發(fā)器(service function forwarder, SFF)及與其相連的通用服務(wù)器(假設(shè)它們之間的鏈路可靠)，這些通用服務(wù)器上可運行VNF；3)轉(zhuǎn)發(fā)節(jié)點vR∈VR，表示僅用于在訪問節(jié)點和服務(wù)節(jié)點之間轉(zhuǎn)發(fā)數(shù)據(jù)包的交換機.記服務(wù)節(jié)點vS具有屬性{(id,ω(id))}，其中id∈IDS是與vS相連的服務(wù)器標(biāo)識，具有全網(wǎng)唯一性，IDS是所有與SFF相連的服務(wù)器的標(biāo)識集合；ω(id)表示服務(wù)器id的資源容量，本文以其可用的CPU核數(shù)衡量.為便于后文描述節(jié)點映射關(guān)系，假設(shè)每個訪問節(jié)點上也有一個唯一性標(biāo)識為id∈ID-IDS的服務(wù)器，且ω(id)=∞，其中ID是全網(wǎng)服務(wù)器標(biāo)識集合.底層鏈路(u,v)的可用帶寬和時延分別記為λ(u,v)和η(u,v).

定義2. VNF.假設(shè)網(wǎng)絡(luò)中有m種VNF，構(gòu)成VNF類型集合T={f1,f2,…,fm}.本文將類型為fj的VNF的服務(wù)能力定義為其實例最多可同時為Nser(fj)條SFC提供服務(wù)[21]，并且fj實例化所需的資源以CPU核數(shù)衡量，為避免非一致性內(nèi)存訪問帶來的開銷[13]，假定各類型VNF實例均需要1個CPU核.

2.2 基本SFC映射過程

基于上述網(wǎng)絡(luò)模型，基本SFC映射過程分為節(jié)點映射和鏈路映射2部分.

圖1是示例底層網(wǎng)絡(luò)和SFC，其中底層網(wǎng)絡(luò)節(jié)點旁的方框中標(biāo)明了相應(yīng)的服務(wù)器標(biāo)識及可用CPU核數(shù)，鏈路上標(biāo)明了可用帶寬時延；SFC各虛擬鏈路的帶寬需求均為5.由此，VNF1映射到節(jié)點C，VNF2和VNF3映射到節(jié)點E，示例SFC的服務(wù)路徑是{(A,C),(C,E),(E,I),(I,K),(K,L)}，服務(wù)時延是14.

2.3 可生存SFC映射問題描述

可生存SFC映射是指在滿足SFC基本映射約束的前提下，通過在SFC映射時預(yù)分配備用資源，或在SFC失效后重映射失效節(jié)點和鏈路，降低底層網(wǎng)絡(luò)故障對SFC提供服務(wù)的影響.而且，可生存SFC映射需要考慮最小化SFC服務(wù)時延，以提高服務(wù)質(zhì)量.下面分別描述面向KSFC和面向NSFC的可生存映射問題.

Fig. 1 Substrate network and SFC圖1 底層網(wǎng)絡(luò)和SFC

2.3.1 面向KSFC的可生存映射問題描述

依據(jù)上述映射規(guī)則，以圖1中的底層網(wǎng)絡(luò)和SFC為例，主服務(wù)路徑是{(A,C),(C,E),(E,I),(I,K),(K,L)}，其中C、E和K分別是VNF1，VNF2和VNF3的主服務(wù)節(jié)點.備用服務(wù)路徑是{(A,B),(B,D),(D,G),(G,J),(J,L)}，其中D是VNF1和VNF2的備用服務(wù)節(jié)點，G是VNF3的備用服務(wù)節(jié)點.橋接路徑是{(C,B),(B,D)}和{(E,H),(H,G)}.

2.3.2 面向NSFC的可生存映射問題描述

3) 不重映射未失效虛擬節(jié)點和鏈路.

依據(jù)上述映射規(guī)則，對于圖1中底層網(wǎng)絡(luò)和SFC的映射關(guān)系，若節(jié)點E發(fā)生故障，則將VNF2和VNF3分別重映射至D和G，并將以VNF2或VNF3為端點的失效虛擬鏈路重映射至路徑{(C,B),(B,D)}，{(D,G)}和{(G,K),(K,L)}.

3 面向KSFC的可生存映射建模與求解

基于上述問題描述，本節(jié)為面向KSFC的可生存映射建立了模型，提出了啟發(fā)式算法進(jìn)行求解，并分析了算法的時間復(fù)雜度.

3.1 面向KSFC的可生存映射模型

以最小化最大的KSFC時延為優(yōu)化目標(biāo)，以節(jié)點約束、鏈路約束和可生存約束為約束條件，采用MILP為面向KSFC的可生存映射建立模型，記為Pro-KSFC.表2是該模型中的主要符號說明.

Table 2 Key Symbol Descriptions for Pro-KSFC表2 Pro-KSFC的主要符號說明

① 由于SFC端節(jié)點和訪問節(jié)點的映射關(guān)系已知，后文如無特別說明，僅討論VNF和服務(wù)器之間的映射關(guān)系.

1) 決策變量

2) 優(yōu)化目標(biāo)

minQ,

(1)

式(1)表示最小化最大的KSFC時延.

3) 節(jié)點約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(2)表示KSFC端節(jié)點的位置已唯一確定；式(3)表示虛擬節(jié)點被唯一地映射到一個主(備用)服務(wù)器上；式(4)表示VNF節(jié)點不能被映射到訪問節(jié)點中的服務(wù)器上：式(5)表示同一KSFC的VNF節(jié)點不能被映射到同一主服務(wù)節(jié)點上；式(6)和式(7)不僅保證一個VNF節(jié)點被映射到不同的主備服務(wù)節(jié)點上，而且允許同一KSFC的VNF節(jié)點被映射到同一備用服務(wù)節(jié)點上；式(8)和式(9)保證VNFfj在服務(wù)器id上部署，當(dāng)且僅當(dāng)存在類型為fj的VNF節(jié)點映射到id所在的主服務(wù)節(jié)點或備用服務(wù)節(jié)點上；式(10)和式(11)分別是服務(wù)器可用CPU核數(shù)約束和VNF服務(wù)能力約束.

4) 鏈路約束條件

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(21)表示若存在一條以底層節(jié)點q為終點的底層鏈路屬于主服務(wù)路徑，則必有一條以q為起點的底層鏈路也屬于該路徑，式(22)和式(23)的含義類似.

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

(36)

(37)

(38)

5) 可生存性約束條件

(39)

(40)

(41)

(42)

(43)

(44)

3.2 主備服務(wù)路徑構(gòu)建算法

① 將與SFC端點對應(yīng)的訪問節(jié)點加入到主服務(wù)節(jié)點集合Vpr和備用服務(wù)節(jié)點集合Vbk中；

② 初始化主服務(wù)路徑Epr、備用服務(wù)路徑Ebk、橋接節(jié)點集合Vbr和橋接路徑集合Ebr；

④tn←0*標(biāo)識是否找到滿足條件的候選主備服務(wù)節(jié)點*；

⑤id,id′,CVpr,CVbk,CSpr,CSbk←null

⑥l,CEpr,CEbk,CEbr←?

⑧ for allr∈Rdo

⑨x←路徑r的終點

VS-(Vpr∪{x}),MaxHops,

then

算法1按序迭代映射VNF節(jié)點及相關(guān)虛擬鏈路，在每次迭代過程中，首先，確定候選主服務(wù)節(jié)點x(行⑦～)，具體是以訪問節(jié)點或前驅(qū)VNF節(jié)點的主服務(wù)節(jié)點為起點，搜索與備用服務(wù)路徑僅可能在訪問節(jié)點處相交，且路徑跳數(shù)不大于跳數(shù)閾值MaxHops的候選路徑，并將它們按時延大小升序排列(行⑦)，依次對各候選路徑的終點進(jìn)行可用資源容量檢驗(行⑩)和連通性檢驗(行)；之后，按照前述類似過程確定候選備用服務(wù)節(jié)點x′(行～)；最后，確定從前驅(qū)VNF節(jié)點的主服務(wù)節(jié)點到x′的橋接路徑(行～)，它和最新建立的主服務(wù)子路徑僅在x處相交.此外，為提高主備服務(wù)路徑構(gòu)建成功率，只有在搜索候選主備服務(wù)節(jié)點和構(gòu)建橋接路徑均失敗的情況下，才重新映射前驅(qū)VNF節(jié)點(行～).

在算法1中，函數(shù)Can_Path(u,V,σ,Λ,τ)用于搜索候選路徑集合，并按時延大小升序排列，每條候選路徑滿足：1)以節(jié)點u為起點，以V中的某個節(jié)點為終點；2)路徑跳數(shù)不大于σ；3)與路徑集合Λ中的路徑僅可能在τ處相交.函數(shù)Res_Check(x,f)用于在底層節(jié)點x中搜索可部署VNFf的服務(wù)器id，id滿足任一條件：1)id上已部署f的實例，且它能再為至少一條SFC提供服務(wù)；2)id能滿足f的CPU核數(shù)需求.函數(shù)Cnt_Check(x)返回False，當(dāng)且僅當(dāng)將x置為主(備用)服務(wù)節(jié)點后剩余節(jié)點無法連通，即無法構(gòu)建備用(主)服務(wù)路徑.

3.3 算法的時間復(fù)雜度分析

4 面向NSFC的可生存映射建模與求解

基于上述問題描述，本節(jié)為面向NSFC的可生存映射建立了模型，提出了啟發(fā)式算法進(jìn)行求解，并分析了算法的時間復(fù)雜度.

4.1 面向NSFC的可生存映射模型

以最大化成功恢復(fù)的失效NSFC數(shù)目和最小化最大的已恢復(fù)NSFC時延為優(yōu)化目標(biāo)，以節(jié)點約束和鏈路約束為約束條件，采用MILP為面向NSFC的可生存映射建立模型，記為Res-NSFC.表3是該模型中的主要符號說明.

1) 決策變量

2) 優(yōu)化目標(biāo)

(45)

式(45)分為2部分：①最小化未恢復(fù)的失效NSFC的數(shù)目；②最小化最大的已恢復(fù)NSFC時延.其中α用于調(diào)節(jié)這2部分的相對重要性.

3) 節(jié)點約束條件

(46)

(47)

式(46)表示不重映射未失效的虛擬節(jié)點；式(47)表示失效VNF節(jié)點不映射到底層故障服務(wù)器或訪問節(jié)點中的服務(wù)器上.

(48)

Table 3 Key Symbol Descriptions for Res-NSFC表3 Res-NSFC的主要符號說明

(49)

(50)

式(48)和式(49)表示VNFfj在服務(wù)器id上部署，當(dāng)且僅當(dāng)存在類型為fj的VNF節(jié)點映射到id所在的服務(wù)節(jié)點上；式(50)表示VNFfj至多有一個實例在id上運行.

(51)

(52)

(53)

(54)

4) 鏈路約束條件

(55)

(56)

式(55)表示不重映射未失效的虛擬鏈路；式(56)表示失效虛擬鏈路不映射到底層故障鏈路上.

(57)

(58)

(59)

(60)

(61)

(62)

4.2 失效服務(wù)路徑重建算法

4.2.1 雙重重映射子算法

⑤ else

⑥H←0；

⑨ if |Ωl|>Hor (|Ωl|=Hand

MDly(Ωl)

BST←Ωl；

⑧ end if

⑨ end for

⑩ for all (u,v)∈Edo

② for allP∈Φdo

⑧ end if

⑨ end for

⑩ end for

4.2.2 替代路徑選擇子算法

⑦ end if

⑧ end for

4.3 算法的時間復(fù)雜度分析

在算法2的主函數(shù)中最耗時的操作是調(diào)用函數(shù)MPaths()，以獲得重映射路徑集合.由于MPaths()的關(guān)鍵步驟是利用Dinic算法，故時間復(fù)雜度為O(d2×l).由此，若失效共享節(jié)點的數(shù)目是p，候選服務(wù)節(jié)點集合大小為q，則算法2在最壞情況下的時間復(fù)雜度為O(p×q×l×d2).

5 實驗與結(jié)果分析

5.1 實驗環(huán)境

底層網(wǎng)絡(luò)拓?fù)溆蒅T-ITM工具隨機產(chǎn)生，每對節(jié)點以0.5的概率互連，各類型節(jié)點的個數(shù)如表4所示.在底層網(wǎng)絡(luò)中，每個服務(wù)節(jié)點具有2個服務(wù)器，每個服務(wù)器具有2個CPU核，底層鏈路時延服從取值區(qū)間為[5,20](單位：ms)的均勻分布，帶寬值均為1 Gbps.假設(shè)網(wǎng)絡(luò)中有6種VNF，每種VNF至多可被4條SFC共享.SFC由隨機選取的訪問節(jié)點對和3種VNF構(gòu)成，其帶寬需求服從取值區(qū)間為[50,150](單位：Mbps)的均勻分布.

Table 4 Number of Nodes in the Experimental Topology

實驗在配置2個Intel Xeon E5-2650 8 x 2 GHz處理器和128 GB RAM的服務(wù)器上進(jìn)行，2種對比算法采用CPLEX 12.6.0.1分別對Pro-KSFC和Res-NSFC進(jìn)行求解，記為Opt-KSFC和Opt-NSFC.評估指標(biāo)包括：

1) 算法運行時間.

2) KSFC映射成功率.即成功映射的KSFC數(shù)目與KSFC映射請求數(shù)目之間的比值.

5) SFC成功運行率.即在SFC請求不斷到來和底層網(wǎng)絡(luò)間歇性出現(xiàn)單點故障的情況下，成功運行的SFC數(shù)目與SFC映射請求數(shù)目之間的比值，其中，成功運行的SFC既包括成功映射的新到的KSFC和NSFC映射請求，也包括成功恢復(fù)的已部署的KSFC和NSFC，該指標(biāo)反映了SFC映射的有效性和對節(jié)點故障的SFC恢復(fù)能力.

6) 額外帶寬消耗率.即SFC消耗的額外帶寬與底層鏈路帶寬總量之間的比值，其中，SFC消耗的額外帶寬包括為KSFC的備用路徑和橋接路徑分配的帶寬，以及為恢復(fù)NSFC分配的帶寬.

5.2 實驗結(jié)果與分析

實驗分為3部分：1)針對PBSP-Bld算法，研究參數(shù)MaxHops對KSFC映射成功率和算法運行時間的影響，并從KSFC最大時延、KSFC映射成功率和算法運行時間3方面評估算法有效性；2)針對FSP-Res算法，從NSFC故障恢復(fù)率、已恢復(fù)NSFC最大時延和算法運行時間3方面評估算法有效性；3)模擬實際網(wǎng)絡(luò)環(huán)境，從SFC故障恢復(fù)率、SFC成功運行率和工作鏈路資源利用率3方面評估所提SFC可生存性映射方法的有效性.

Fig. 2 Influence of the value of MaxHops圖2 MaxHops取值的影響

5.2.1 主備服務(wù)路徑構(gòu)建算法有效性評估實驗

實驗隨機生成10條KSFC，采用具有不同Max-Hops值的PBSP-Bld將它們映射到底層網(wǎng)絡(luò)T3中，測算KSFC映射成功率和算法運行時間.實驗重復(fù)50次取均值，結(jié)果如圖2所示.當(dāng)MaxHops≤4時，KSFC映射成功率隨MaxHops的增大而增大；當(dāng)MaxHops>4時，成功率幾乎維持不變，而算法運行時間隨著MaxHops的增大而增加.因此，MaxHops=4是相對最佳取值，后續(xù)實驗中均采用該值.

實驗在不同KSFC數(shù)目和不同底層網(wǎng)絡(luò)規(guī)模條件下，分別采用PBSP-Bld和Opt-KSFC將隨機生成的若干條KSFC映射至底層網(wǎng)絡(luò)，測算KSFC最大時延、KSFC映射成功率和算法運行時間.實驗重復(fù)50次取均值，結(jié)果如圖3～5所示：

Fig. 4 Success ratio of KSFC mapping圖4 KSFC映射成功率

Fig. 5 Running time圖5 算法運行時間

由圖3和4可知，Opt-KSFC在KSFC最大時延和映射成功率方面的表現(xiàn)優(yōu)于PBSP-Bld，這是因為前者搜索了更多種映射方案以尋求最優(yōu)解.在KSFC數(shù)目一定的情況下，隨著底層網(wǎng)絡(luò)規(guī)模的增大，可利用的網(wǎng)絡(luò)資源增多，二者的映射成功率增大，然而它們的KSFC最大時延未明顯降低，這是因為雖然網(wǎng)絡(luò)規(guī)模越大意味著KSFC映射的優(yōu)化空間越大，但是KSFC時延會受到訪問節(jié)點和服務(wù)節(jié)點位置的影響.此外，在底層網(wǎng)絡(luò)規(guī)模一定的情況下，由于底層網(wǎng)絡(luò)資源有限，隨著KSFC數(shù)目的增大，二者的映射成功率下降，KSFC最大時延增大.

此外，由圖5可知，PBSP-Bld的運行時間小于Opt-KSFC，這是因為后者的搜索空間更大.而且，結(jié)合圖3～5可知，隨著底層網(wǎng)絡(luò)規(guī)模的增大和KSFC數(shù)目的增多，PBSP-Bld和Opt-KSFC在映射成功率和KSFC最大時延方面間的差距未顯著增加，但前者的算法運行時間愈發(fā)優(yōu)于后者，比如當(dāng)?shù)讓泳W(wǎng)絡(luò)具有45個節(jié)點(T4)且KSFC數(shù)目為10時，Opt-KSFC的KSFC最大時延比PBSP-Bld減小約16.4%，映射成功率提高1.85%，但算法運行時間增大了約84.4倍.

5.2.2 失效服務(wù)路徑重建算法有效性評估實驗

實驗借鑒文獻(xiàn)[9]中的方法，在網(wǎng)絡(luò)T3中隨機部署若干條NSFC，并保證底層鏈路負(fù)載均衡，由此，通過改變已部署的NSFC數(shù)目可以改變網(wǎng)絡(luò)的底層鏈路利用率.在不同底層鏈路利用率情況下，從網(wǎng)絡(luò)中隨機選取一個轉(zhuǎn)發(fā)節(jié)點或服務(wù)節(jié)點或服務(wù)器作為故障節(jié)點，并將相關(guān)鏈路和服務(wù)器置為失效，分別采用FSP-Res和Opt-NSFC(權(quán)重α=1 000，即以最大化成功恢復(fù)的NSFC數(shù)目為主要目標(biāo))恢復(fù)失效NSFC，測算NSFC故障恢復(fù)率，已恢復(fù)NSFC最大時延和算法運行時間，實驗重復(fù)50次取均值，結(jié)果如圖6所示.此外，實驗采用不同規(guī)模的底層網(wǎng)絡(luò)，在保證它們的鏈路利用率相同的情況下重復(fù)上述實驗，結(jié)果如圖7所示.

Fig. 6 Performance comparison under different substrate link utilization圖6 在不同底層鏈路利用率下有效性的對比

Fig. 7 Performance comparison under different substrate network size圖7 在不同底層網(wǎng)絡(luò)規(guī)模下有效性的對比

由圖6(a)和7(a)可知，Opt-NSFC的故障恢復(fù)率均高于FSP-Res，這是因為前者在更大的節(jié)點和鏈路空間中進(jìn)行搜索以重映射失效VNF節(jié)點和虛擬鏈路.由圖6(a)可知，它們隨底層鏈路利用率的增大而降低，這是因為底層鏈路利用率越大意味著單點故障可能導(dǎo)致更多的NSFC失效，而且可用于恢復(fù)失效虛擬鏈路的帶寬也越少.進(jìn)一步地，當(dāng)?shù)讓渔溌防寐蚀笥?0%時，2種算法的故障恢復(fù)率顯著下降，原因在于:為達(dá)到較高的底層鏈路利用率，文獻(xiàn)[9]的NSFC映射方法降低了對鏈路負(fù)載均衡的要求，使得部分鏈路的剩余帶寬難以滿足NSFC需求，進(jìn)而導(dǎo)致失效虛擬鏈路無法重映射到所有經(jīng)過這些“擁塞”鏈路的底層路徑上，并且底層鏈路利用率越高，“擁塞”鏈路越多.此外，由圖7(a)可知，2種算法的故障恢復(fù)率隨底層網(wǎng)絡(luò)規(guī)模的增大而增加，這是因為底層鏈路越多意味著有更多條不同的底層路徑可作為重映射失效虛擬鏈路的選擇.

由圖6(b)和7(b)可知，Opt-NSFC的已恢復(fù)NSFC最大時延均小于FSP-Res.由圖6(b)可知，它們隨底層鏈路利用率的增大而增大，這是因為更多的底層鏈路難以為NSFC提供足夠的帶寬，致使失效虛擬鏈路不得不重映射到更長的路徑上.此外，由圖7(b)可知，隨著底層網(wǎng)絡(luò)規(guī)模增大，2種算法的已恢復(fù)NSFC最大時延小幅增大，原因在于：在規(guī)模較大的網(wǎng)絡(luò)中訪問節(jié)點可能相距較遠(yuǎn)，導(dǎo)致NSFC對應(yīng)的服務(wù)路徑較長.

由圖6(c)和7(c)可知，F(xiàn)SP-Res比Opt-NSFC至少約快384倍.此外，隨著底層鏈路利用率和底層網(wǎng)絡(luò)規(guī)模的增大，由于失效NSFC增多和待搜索的節(jié)點、鏈路空間擴大，2種算法的運行時間均增大，但是單點故障恢復(fù)算法的運行時間增幅小于Opt-NSFC.

5.2.3 SFC可生存性映射方法有效性評估實驗

Fig. 8 Average recovery ratio of SFC圖8 平均SFC故障恢復(fù)率

Fig. 9 Average successful running ratio of SFC圖9 平均SFC成功運行率

Fig. 10 Average additional bandwidth consumption ratio圖10 平均額外帶寬消耗率

綜上所述，PBSP-Bld算法和FSP-Res算法能夠在較短的時間內(nèi)獲得接近最優(yōu)的性能表現(xiàn)，并且隨著底層網(wǎng)絡(luò)規(guī)模的增大，二者在時間開銷上的優(yōu)勢愈加顯著.可生存SFC映射方法在底層單點故障頻繁發(fā)生時能有效保證SFC的正常運行，但是其性能表現(xiàn)受KSFC和NSFC之間的數(shù)量比例的影響，并且在KSFC數(shù)量比例大時，該方法消耗的額外帶寬資源也較大，需要從減小備用帶寬資源開銷方面對該方法進(jìn)行改進(jìn).

6 總 結(jié)

針對已有可生存SFC映射研究存在底層網(wǎng)絡(luò)資源開銷大、SFC服務(wù)時延長和映射時間開銷大等問題，本文提出了一種區(qū)分等級的可生存SFC映射方法.通過綜合保護(hù)和恢復(fù)策略，減少了備用資源消耗，從而降低了底層網(wǎng)絡(luò)資源開銷.通過將可生存SFC映射問題建模為以最小化服務(wù)時延為目標(biāo)的優(yōu)化模型，并提出啟發(fā)式算法進(jìn)行求解，降低了服務(wù)時延，減小了直接求解模型的時間開銷.仿真實驗表明，在不同KSFC數(shù)目和不同底層網(wǎng)絡(luò)規(guī)模條件下，PBSP-Bld算法的KSFC映射成功率和KSFC最大時延分別比Opt-KSFC低0.99%～7.14%和高3.48%～58.31%，但前者的時間開銷比后者低95.31%～99.99%.在不同底層網(wǎng)絡(luò)規(guī)模和不同底層鏈路利用率條件下，F(xiàn)SP-Res算法的NSFC故障恢復(fù)率和已恢復(fù)NSFC最大時延分別比Opt-NSFC低1.05%～7.34%和高2.01%～18.44%，但前者的時間開銷比后者低99.74%～99.97%.此外，實驗?zāi)M實際網(wǎng)絡(luò)環(huán)境，通過改變KSFC比例和底層單點故障發(fā)生頻率，從SFC故障恢復(fù)率、SFC成功運行率和額外帶寬消耗率3方面驗證了區(qū)分等級的可生存SFC映射方法的有效性.在未來研究中，需要在各類真實網(wǎng)絡(luò)中進(jìn)一步評估和驗證所提方法，從優(yōu)化網(wǎng)絡(luò)資源利用方面對其進(jìn)行改進(jìn)，并研究針對底層網(wǎng)絡(luò)多點、多鏈路和區(qū)域故障問題的可生存SFC映射方法.

[1]Quinn P, Nadeau T, Yadav N. Problem statement for service function chaining, RFC 7498[EBOL]. (2015-04) [2017-10-10]. https:www. rfc-editor. orginforfc7498

[2]Ding Wanfu, Qi Wen, Wang Jianping, et al. OpenSCaaS: An open service chain as a service platform toward the integration of SDN and NFV[J]. IEEE Network, 2015, 29(3): 30-35

[3]Bari M F, Chowdhury S R, Ahmed R, et al. On orchestrating virtual network functions[C]Proc of the 11th Int Conf on Network and Service Management. Piscataway, NJ: IEEE, 2015: 50-56

[4]Gupta A, Habib M F, Mandal U, et al. On service-chaining strategies using virtual network functions in operator networks[J]. Computer Network, 2018, 133: 1-16

[5]McKeown N. Software-defined networking[C]Proc of the 28th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 30-32

[6]Chiosi M, Clarke D, Willis P, et al. Network functions virtualisation-introductory white paper[R]. Darmstadt, Germany: AT&T, 2012

[7]European Telecommunications Standards Institute. Network functions virtualization (NFV): Architectural framework[R]. Nice, France: ETSI, 2014

[8]Guo Tao, Wang Ning, Moessner K, et al. Shared backup network provision for virtual network embedding[C]Proc of the 2011 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2011: 1-5

[9]Rahman M R, Boutaba R. SVNE: Survivable virtual network embedding algorithms for network virtualization[J]. IEEE Trans on Network & Service Management, 2013, 10(2): 105-118

[10]Nagarajan R, Kurose J F. On defining, computing and guaranteeing quality-of-service in high-speed networks[C]Proc of the 11th Annual Joint Conf of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 1992: 2016-2025

[11]Aurrecoechea C, Campbell A T, Hauw L. A survey of QoS architectures[J]. Multimedia Systems, 1998, 6(3): 138-151

[12]Mehraghdam S, Keller M, Karl H. Specifying and placing chains of virtual network functions[C]Proc of the 3rd IEEE Int Conf on Cloud Networking. Piscataway, NJ: IEEE, 2014: 7-13

[13]Mohammadkhan A, Ghapani S, Liu Guyue, et al. Virtual function placement and traffic steering in fiexible and dynamic software defined networks[C]Proc of the 21st IEEE Int Workshop on Local and Metropolitan Area Networks. Piscataway, NJ: IEEE, 2015: 1-6

[14]Ghaznavi M, Shahriar N, Kamali S, et al. Distributed service function chaining[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2479-2489

[15]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]Proc of the 14th IFIPIEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2015: 98-106

[16]Fan Jingyuan, Ye Zilong, Guan Chaowen, et al. GREP: Guaranteeing reliability with enhanced protection in NFV[C]Proc of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2015: 13-18

[17]Cheng Xiang, Zhang Zhongbao, Su Sen, et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10): 143-151 (in Chinese)(程祥, 張忠寶, 蘇森, 等. 虛擬網(wǎng)絡(luò)映射問題研究綜述[J]. 通信學(xué)報, 2011, 32(10): 143-151)

[18]Sun Gang. Research on virtual network mapping technologiesp[D]. Chengdu: University of Electronic Science and Technology of China, 2012(in Chinese)(孫罡. 虛擬網(wǎng)絡(luò)的映射技術(shù)研究[D]. 成都: 電子科技大學(xué), 2012)

[19]Medhat A M, Carella G A, Pauls M, et al. Resilient orchestration of service functions chains in a NFV environment[C]Proc of the 3rd IEEE Conf on Network Function Virtualization and Software Defined Networks. Piscataway, NJ: IEEE, 2017: 7-12

[20]Suh D, Baek H, Jang S, et al. Distributed service function failover mechanism in service function chaining[C]Proc of the 2017 Int Conf on Information Networking. Piscataway, NJ: IEEE, 2017: 148-150

[21]Hmaity A, Savi M, Musumeci F, et al. Virtual network function placement for resilient service chain provisioning[C]Proc of the 8th Int Workshop on Resilient Networks Design and Modeling. Piscataway, NJ: IEEE, 2016: 245-252

[22]Beck M T, Botero J F, Kai S. Resilient allocation of service function chains[C]Proc of the 3rd IEEE Conf on Network Function Virtualization and Software Defined Networks. Piscataway, NJ: IEEE, 2017: 128-133

[23]Herker S, An X, Kiess W, et al. Data-center architecture impacts on virtualized network functions service chain embedding with high availability requirements[C]Proc of the 2015 IEEE GLOBECOM Workshops. Piscataway, NJ: IEEE, 2015: 1-7

[24]Halpern J, Pignataro C. Service function chaining (SFC) architecture, RFC 7665[EBOL]. (2015-10) [2017-11-10]. https:www.rfc-editor.orginforfc7665

[25]Martins E Q V. An algorithm for ranking paths that may contain cycles[J]. European Journal of Operational Research, 1984, 18(1): 123-130

[26]Beck M T, Botero J F. Scalable and coordinated allocation of service function chains[J]. Computer Communications, 2017, 102: 78-88

[27]Dinitz E A. Algorithm for solution of a problem of maximum flow in networks with power estimation[J]. Soviet Mathematics-Doklady, 1970, 11: 1277-1280

[28]Fredman M L, Tarjan R E. Fibonacci heaps and their uses in improved network optimization algorithms[C]Proc of the 25th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1987: 338-346

LiuYi, born in 1991. PhD candidate. Her main research interests include SDN security and SFC technology.

ZhangHongqi, born in 1962. PhD, professor. His main research interests include network security and classification protection (zhq37922@126.com).

YangYingjie, born in 1971. PhD, professor. His main research interests include security management and situation awareness (yangyj-2010@qq.com).

ChangDexian, born in 1977. PhD, associate professor. His main research interests include SDN security and trusted computing (changdexian@126.com).