劉 藝 張紅旗 楊英杰 常德顯

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 問(wèn)題描述

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

Table 1 Key Symbols Lists表1 主要符號(hào)列表

2.1 基本定義

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

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

2.2 基本SFC映射過(guò)程

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

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

2.3 可生存SFC映射問(wèn)題描述

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

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

2.3.1 面向KSFC的可生存映射問(wèn)題描述

依據(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é)點(diǎn).備用服務(wù)路徑是{(A,B),(B,D),(D,G),(G,J),(J,L)}，其中D是VNF1和VNF2的備用服務(wù)節(jié)點(diǎn)，G是VNF3的備用服務(wù)節(jié)點(diǎn).橋接路徑是{(C,B),(B,D)}和{(E,H),(H,G)}.

2.3.2 面向NSFC的可生存映射問(wèn)題描述

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

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

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

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

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

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

Table 2 Key Symbol Descriptions for Pro-KSFC表2 Pro-KSFC的主要符號(hào)說(shuō)明

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

1) 決策變量

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

minQ,

(1)

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

3) 節(jié)點(diǎn)約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

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

4) 鏈路約束條件

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(21)表示若存在一條以底層節(jié)點(diǎn)q為終點(diǎn)的底層鏈路屬于主服務(wù)路徑，則必有一條以q為起點(diǎn)的底層鏈路也屬于該路徑，式(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端點(diǎn)對(duì)應(yīng)的訪問(wèn)節(jié)點(diǎn)加入到主服務(wù)節(jié)點(diǎn)集合Vpr和備用服務(wù)節(jié)點(diǎn)集合Vbk中；

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

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

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

⑥l,CEpr,CEbk,CEbr←?

⑧ for allr∈Rdo

⑨x←路徑r的終點(diǎn)

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

then

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

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

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

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

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

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

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

1) 決策變量

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

(45)

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

3) 節(jié)點(diǎn)約束條件

(46)

(47)

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

(48)

Table 3 Key Symbol Descriptions for Res-NSFC表3 Res-NSFC的主要符號(hào)說(shuō)明

(49)

(50)

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

(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 算法的時(shí)間復(fù)雜度分析

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

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

5.1 實(shí)驗(yàn)環(huán)境

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

Table 4 Number of Nodes in the Experimental Topology

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

1) 算法運(yùn)行時(shí)間.

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

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

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

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

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

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

5.2.1 主備服務(wù)路徑構(gòu)建算法有效性評(píng)估實(shí)驗(yàn)

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

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

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

Fig. 5 Running time圖5 算法運(yùn)行時(shí)間

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

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

5.2.2 失效服務(wù)路徑重建算法有效性評(píng)估實(shí)驗(yàn)

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

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

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

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

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

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

5.2.3 SFC可生存性映射方法有效性評(píng)估實(shí)驗(yàn)

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

Fig. 9 Average successful running ratio of SFC圖9 平均SFC成功運(yùn)行率

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

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

6 總 結(jié)

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