一種區分等級的可生存服務功能鏈映射方法

劉 藝 張紅旗 楊英杰 常德顯

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 問題描述

本節首先給出了底層網絡、VNF和SFC的定義，之后在介紹基本SFC映射過程的基礎上引入可生存需求，對可生存SFC映射問題進行了描述.表1是主要符號列表.

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

2.1 基本定義

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

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

2.2 基本SFC映射過程

基于上述網絡模型，基本SFC映射過程分為節點映射和鏈路映射2部分.

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

2.3 可生存SFC映射問題描述

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

Fig. 1 Substrate network and SFC圖1 底層網絡和SFC

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

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

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

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

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

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

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

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

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

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

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

1) 決策變量

2) 優化目標

minQ,

(1)

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

3) 節點約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

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

4) 鏈路約束條件

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(21)表示若存在一條以底層節點q為終點的底層鏈路屬于主服務路徑，則必有一條以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 主備服務路徑構建算法

① 將與SFC端點對應的訪問節點加入到主服務節點集合Vpr和備用服務節點集合Vbk中；

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

④tn←0*標識是否找到滿足條件的候選主備服務節點*；

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

⑥l,CEpr,CEbk,CEbr←?

⑧ for allr∈Rdo

⑨x←路徑r的終點

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

then

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

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

3.3 算法的時間復雜度分析

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

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

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

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

1) 決策變量

2) 優化目標

(45)

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

3) 節點約束條件

(46)

(47)

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

(48)

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

(49)

(50)

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

(51)

(52)

(53)

(54)

4) 鏈路約束條件

(55)

(56)

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

(57)

(58)

(59)

(60)

(61)

(62)

4.2 失效服務路徑重建算法

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 算法的時間復雜度分析

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

5 實驗與結果分析

5.1 實驗環境

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

Table 4 Number of Nodes in the Experimental Topology

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

1) 算法運行時間.

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

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

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

5.2 實驗結果與分析

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

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

5.2.1 主備服務路徑構建算法有效性評估實驗

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

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

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

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

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

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

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

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

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

Fig. 7 Performance comparison under different substrate network size圖7 在不同底層網絡規模下有效性的對比

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

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

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

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

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

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

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

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

6 總 結

針對已有可生存SFC映射研究存在底層網絡資源開銷大、SFC服務時延長和映射時間開銷大等問題，本文提出了一種區分等級的可生存SFC映射方法.通過綜合保護和恢復策略，減少了備用資源消耗，從而降低了底層網絡資源開銷.通過將可生存SFC映射問題建模為以最小化服務時延為目標的優化模型，并提出啟發式算法進行求解，降低了服務時延，減小了直接求解模型的時間開銷.仿真實驗表明，在不同KSFC數目和不同底層網絡規模條件下，PBSP-Bld算法的KSFC映射成功率和KSFC最大時延分別比Opt-KSFC低0.99%～7.14%和高3.48%～58.31%，但前者的時間開銷比后者低95.31%～99.99%.在不同底層網絡規模和不同底層鏈路利用率條件下，FSP-Res算法的NSFC故障恢復率和已恢復NSFC最大時延分別比Opt-NSFC低1.05%～7.34%和高2.01%～18.44%，但前者的時間開銷比后者低99.74%～99.97%.此外，實驗模擬實際網絡環境，通過改變KSFC比例和底層單點故障發生頻率，從SFC故障恢復率、SFC成功運行率和額外帶寬消耗率3方面驗證了區分等級的可生存SFC映射方法的有效性.在未來研究中，需要在各類真實網絡中進一步評估和驗證所提方法，從優化網絡資源利用方面對其進行改進，并研究針對底層網絡多點、多鏈路和區域故障問題的可生存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)(程祥, 張忠寶, 蘇森, 等. 虛擬網絡映射問題研究綜述[J]. 通信學報, 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)(孫罡. 虛擬網絡的映射技術研究[D]. 成都: 電子科技大學, 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).