黃 睿 張紅旗 常德顯
(解放軍信息工程大學 鄭州 450001) (河南省信息安全重點實驗室 鄭州 450001) (xjhr1009@163.com)
隨著多樣化網(wǎng)絡業(yè)務的迅猛發(fā)展,傳統(tǒng)網(wǎng)絡安全服務模式在動態(tài)性、靈活性、可擴展性等方面的弊端愈發(fā)突顯[1].具體表現(xiàn)為[2]:1)安全功能實現(xiàn)方式的耦合性.現(xiàn)有安全功能,如防火墻、IDS等大都基于硬件中間盒子實現(xiàn),其在功能上具有專屬私有性,建設所需成本較高、可擴展性差、靈活性不足、運用中難以統(tǒng)一管理.2)安全功能部署位置的靜態(tài)性.現(xiàn)有安全功能大都以靜態(tài)方式部署在網(wǎng)絡的關鍵位置,拓撲依賴嚴重,這種僵化的部署方式使其難以根據(jù)業(yè)務請求的服務構(gòu)成進行重復使用或者動態(tài)重構(gòu).為此,探索新型網(wǎng)絡安全服務模式成為當下研究的熱點[3].
當前,軟件定義網(wǎng)絡[4](software defined networking, SDN)的發(fā)展和網(wǎng)絡功能虛擬化[5](network function virtualization, NFV)技術的興起為探尋新型網(wǎng)絡安全服務模式提供了支撐.SDN通過邏輯平面和物理平面的分離,將控制功能從傳統(tǒng)的分布式網(wǎng)絡設備遷移到集中化的控制平臺,進而實現(xiàn)網(wǎng)絡的集中管控和開放可編程.NFV將以專有硬件形式部署的網(wǎng)絡功能轉(zhuǎn)變?yōu)樵谕ㄓ梅掌魃线\行的虛擬網(wǎng)絡功能(virtual network function, VNF),將傳統(tǒng)網(wǎng)絡設備的軟件功能和硬件載體解耦開來,減少了在網(wǎng)絡特定位置部署專用中間盒子的開銷,增加了網(wǎng)絡設備部署的靈活性.二者結(jié)合,使得網(wǎng)絡架構(gòu)和網(wǎng)絡設備更加敏捷[6].由此,借助SDNNFV的安全服務鏈(security service chain, SSC)技術[7]應運而生.SSC在利用NFV技術將傳統(tǒng)安全服務功能虛擬化并部署在通用服務器(也稱服務節(jié)點)的基礎上,借助SDN的流量集中管控功能,根據(jù)用戶或業(yè)務的安全請求引導流量按序經(jīng)過服務節(jié)點上的安全功能實例(也稱VNF實例),從而為用戶或業(yè)務提供可配置的安全服務.
目前,SSC的研究尚處于起步階段.文獻[8]提出一種FRESCO架構(gòu),通過安全模塊組合的方式生成安全服務,但僅進行了功能上的驗證而并未給出具體的實現(xiàn)方案.為此,文獻[7]基于SDNNFV提出一種SSC的理論架構(gòu),但囿于網(wǎng)絡資源的限制,未對邏輯安全服務請求如何向具體的、優(yōu)化的VNF實例和VNF路徑映射做出說明.雖然文獻[9]在文獻[7]的基礎上進一步將SSC映射問題抽象為整數(shù)線性規(guī)劃(integer linear programming, ILP)問題,根據(jù)物理節(jié)點的服務能力和物理鏈路的容量約束選擇可映射的VNF實例和VNF路徑并設計高效的啟發(fā)式算法求解此問題,但未考慮到SSC模式下可能面臨的故障性問題.實際網(wǎng)絡中,受自然或人為因素影響,承載安全服務功能的物理網(wǎng)絡資源(物理節(jié)點物理鏈路)可能發(fā)生故障或性能劣化[10],這將影響SSC的可靠性,嚴重時還可能導致無法對后續(xù)安全服務請求做出及時有效的響應.因此,SDNNFV下SSC故障的備份恢復問題亟待解決.SSC故障的備份恢復旨在,當承載VNF實例VNF鏈路的服務節(jié)點物理鏈路發(fā)生故障時,采用一定方法及時有效地完成VNF實例的更替和流量路由路徑的切換,以最小化故障對用戶業(yè)務帶來的影響.
為此,本文提出一種SSC故障的備份恢復機制以應對SSC模式下難以避免的故障性問題.該機制能夠有效提高SSC在發(fā)生物理節(jié)點或物理鏈路故障時的故障修復率,在用戶業(yè)務容忍時間內(nèi)保證服務的連續(xù)性.本文貢獻主要包含3個方面:
2) 針對節(jié)點故障重映射問題,提出改進的離散粒子群(discrete particle swarm optimization, DPSO)算法求解該多目標優(yōu)化問題(multi-objective opti-mizing problem, MOP),在最大化成功恢復安全服務請求數(shù)目的同時最小化VNF實例和VNF路徑占用其重映射目標上備用資源的比例.
3) 針對鏈路故障重定向問題,設計動態(tài)路徑分割算法求解該混合整數(shù)規(guī)劃(mixed integer progra-mming, MIP)問題,最大化底層物理網(wǎng)絡資源剩余價值.
1) SSC優(yōu)化構(gòu)建.首先,需要依據(jù)用戶或業(yè)務的安全請求,在滿足網(wǎng)絡資源約束的條件下,確定VNF實例的部署數(shù)量、位置,并規(guī)劃流量路由路徑,達到最小化安全服務時延等優(yōu)化目標.現(xiàn)有研究大都從資源約束角度出發(fā),提出滿足約束條件的SSC優(yōu)化構(gòu)建策略.Dwaraki等人[14]將網(wǎng)絡拓撲轉(zhuǎn)換為分層圖,采用Dijkstra算法逐層選擇網(wǎng)絡功能實例和路由路徑,但未考慮對大規(guī)模物理網(wǎng)絡而言,分層圖可能帶來的存儲開銷.Xiong等人[15]采用兩階段映射方案,分別基于網(wǎng)絡功能的服務能力和網(wǎng)絡鏈路的容量約束選擇可映射的服務節(jié)點和路由路徑,但可能因為服務節(jié)點間距離過大而影響服務時延.為適應更大規(guī)模的網(wǎng)絡基礎設施,Luizelli等人[16]將SSC優(yōu)化構(gòu)建問題抽象為ILP問題,并設計啟發(fā)式算法高效求解此問題.
2) SSC執(zhí)行調(diào)度.構(gòu)建階段完成后,需考慮到SSC的執(zhí)行調(diào)度問題,即當網(wǎng)絡中存在多條SSC時,需要優(yōu)化服務節(jié)點中提供某一特定功能的虛擬節(jié)點上多個VNF實例請求的執(zhí)行順序,根據(jù)需要對VNF實例進行實時調(diào)度,以實現(xiàn)最小化安全服務請求的平均等待時間等目標.Riera等人[17]首次提出服務節(jié)點上VNF實例的執(zhí)行調(diào)度問題,并對其進行了形式化的定義.文獻[18]在文獻[17]基礎上,將最小化完成時間作為可行方案的優(yōu)化目標,但并未給出具體的解決方案.Mijumbi等人[19]在解決了VNF實例資源分配問題的基礎上,基于禁忌搜索算法解決VNF實例的執(zhí)行調(diào)度問題.
3) SSC故障的備份恢復.SSC優(yōu)化構(gòu)建和SSC執(zhí)行調(diào)度問題側(cè)重于SSC正常運行時的問題討論,而涉及到可靠性保證的SSC故障的備份恢復問題也不容忽視.作為本文研究的重點,SSC故障的備份恢復問題是指,當承載VNF實例VNF鏈路的服務節(jié)點物理鏈路出現(xiàn)故障時,需要在不影響SSC初始構(gòu)建資源的條件下,采用預留備用資源重建VNF實例和VNF鏈路,及時完成VNF實例的更替和流量路由路徑的切換,以保證安全服務的可靠性和連續(xù)性.在此問題中,物理平面的正常運行是為用戶提供安全服務的根本保障.然而,在可控或不可控因素影響下,物理網(wǎng)絡資源(物理節(jié)點物理鏈路)都可能發(fā)生一定程度的故障.鑒于SDNNFV下資源共享的特性,任何單一物理資源故障都會影響使用該資源的多條SSC,進而影響為用戶提供的安全服務.因此,除了為SSC提供有效的優(yōu)化構(gòu)建和執(zhí)行調(diào)度方案外,保證SSC故障發(fā)生時的生存性也至關重要.
為了增強SSC的生存抗毀性,Nguyen等人[20]提出了一種服務功能鏈的故障轉(zhuǎn)移機制,通過在線替換故障VNF實例并動態(tài)遷移受故障影響流量以減少故障恢復時延,但并未考慮替換VNF實例和遷移流量路徑對新到達SSC構(gòu)建請求的資源制約.Suh等人[21]提出的分布式故障恢復機制,在不介入控制平面的條件下利用寄存在每一個服務節(jié)點中的故障恢復代理快速檢測和恢復受影響的VNF實例,從而進行即時地故障恢復,但未考慮故障恢復代理帶來的額外資源開銷和性能損耗.Lee等人[22]提出了一種服務鏈的故障自恢復方案,通過數(shù)據(jù)平面的信令方式將受故障影響的服務節(jié)點自動地轉(zhuǎn)移到其他正常節(jié)點上,但未考慮轉(zhuǎn)移對象可能存在的潛在性故障可能.綜上,現(xiàn)有研究成果較少且著重關注于故障發(fā)生時受影響VNF實例的即時故障恢復和流量路由路徑變換,并未綜合考慮其可能帶來的資源約束、時延損耗和故障轉(zhuǎn)移目標的可靠性.此外,現(xiàn)有成果未對故障發(fā)生對象(節(jié)點鏈路)的類型進行分類討論,對SSC中的故障問題一概而論,具有一定的局限性.
通過梳理現(xiàn)有相關工作不難發(fā)現(xiàn),針對SSC故障的備份恢復問題,目前尚沒有一種機制能夠在既保證服務可靠性又不制約接受新請求資源的基礎上,為SSC中2類故障問題提供高效的備份恢復解決方案.因此,本文借助SDNNFV架構(gòu),提出一種SSC故障的備份恢復機制,綜合考慮節(jié)點故障重映射和鏈路故障重定向2個方面,為SSC的進一步推廣應用提供支撐.
Fig. 1 The mapping topology of SSC圖1 SSC映射拓撲圖
SSC故障一般分為物理節(jié)點故障和物理鏈路故障.實際網(wǎng)絡中,一個物理節(jié)點發(fā)生故障通常會導致一個區(qū)域的物理節(jié)點在相對集中的時間內(nèi)發(fā)生故障,即發(fā)生多節(jié)點故障.因此,將SSC中物理節(jié)點故障按時間順序建模為一系列單節(jié)點故障集合PNF={pnf1,pnf2,…},對于某單節(jié)點故障pnf1,用ts(pnfi)和te(pnfi)分別定義故障發(fā)生和結(jié)束的時刻,且ts(pnfi)
同樣地,將SSC中物理鏈路故障建模為PLF={plf1,plf2,…}.由于Gill等人[10]在分析鏈路故障相關性時發(fā)現(xiàn),超過50%的鏈路故障是由單鏈路故障引起的,并且超過90%的鏈路故障涉及不超過5條鏈路.因此,本文側(cè)重考慮物理鏈路故障中最常見的單鏈路故障問題.即在某時刻t,?i,j,物理鏈路故障plfi和plfj不同時發(fā)生.
節(jié)點故障重映射(node failure remapping, NFRM)是指,在發(fā)生物理節(jié)點故障后,依據(jù)當前物理平面狀態(tài),及時地為受影響的VNF實例節(jié)點和其關聯(lián)的VNF實例鏈路重新分配資源,使SSC恢復正常工作.
如圖2所示,當GS中的物理節(jié)點X發(fā)生故障時,SSRi中需要重映射的部分包含VNF實例節(jié)點b以及與之相連的VNF實例鏈路(b,a),(b,c)和(b,d).因此,LR(b)={(b,a),(b,c),(b,d)},NR(b)={a,c,d},NS(b)={A,D,E}.
Fig. 2 The instance of single-point fault圖2 單節(jié)點故障實例
對于NFRM問題,可抽象為以Max{Obj1,Obj2}(3.2.1節(jié)中詳細描述)為目標,滿足以下映射條件的優(yōu)化問題:
(1)
(2)
鏈路故障重定向(link failure redirect, LFRD)是指,在發(fā)生物理鏈路故障時,動態(tài)調(diào)整底層物理路徑流量分割比例,將受影響流量從故障物理鏈路遷移到正常物理鏈路當中,從而避免重映射方法帶來的服務中斷時間較長的影響,使得SSC在最短時間內(nèi)恢復正常工作.
如圖3所示,當GS中的物理鏈路l(B,E)發(fā)生故障時,映射在之上的VNF實例鏈路l(a,c)需要重定向.
Fig. 3 The instance of single-link fault圖3 單鏈路故障實例
對于LFRD方法,可以抽象為以Max{S(GS)}為目標(3.3.1節(jié)中詳細描述),滿足以下映射條件的優(yōu)化問題:
fredirect:li→l′(A,,B),l′(A,,B)∈Path(A,B),
l(A,B)≠l′(A,,B),
(3)
其中fredirect表示VNF實例鏈路重定向;Path(A,B)表示物理節(jié)點A,B間物理鏈路窮舉集合;l′(A,,B)表示集合中的某一條可用物理鏈路,即把VNF實例鏈路上的流量重定向到正常的物理鏈路上,以完成SSC物理鏈路故障恢復.
本文提出的NFV環(huán)境下SSC故障的備份恢復機制包含3個階段:1)物理平面初始化階段,即為每個物理資源(節(jié)點、鏈路)都按比例預留備份資源.對于物理節(jié)點,采用圖的連通性理論構(gòu)造可用節(jié)點候選集合;對于物理鏈路,采用路徑遍歷窮舉法構(gòu)造可用鏈路候選集合,盡可能多得為受故障影響對象提供重映射重定向目標.2)當有安全服務請求SSR到達時,采用已有的服務功能鏈構(gòu)建方法[7,9,10]為其分配物理資源并提供安全服務.3)當發(fā)生節(jié)點故障時,基于改進的DPSO算法求解NFRM,實現(xiàn)VNF實例節(jié)點的即時遷移;當發(fā)生鏈路故障時,基于動態(tài)路徑分割算法求解LFRD,實現(xiàn)VNF實例鏈路上流量的動態(tài)轉(zhuǎn)移.
物理平面初始化包括物理節(jié)點初始化和物理鏈路初始化2個方面,通過在初始化階段構(gòu)建候選集合,有利于減小故障發(fā)生時主備用資源間的制約,縮小重映射重定向問題的搜索空間,在提高故障恢復成功率的同時提升算法效率.
1) 物理節(jié)點初始化
在物理節(jié)點x發(fā)生故障后,其承載的VNF實例節(jié)點及與這些VNF實例節(jié)點相連的VNF實例鏈路都需要重新映射.文獻[23]中指出,一個物理節(jié)點故障可能會導致與它相鄰區(qū)域內(nèi)的物理節(jié)點故障發(fā)生率增加.因此,為了保證節(jié)點故障重映射方法的成功率,x的候選節(jié)點應該在一定范圍內(nèi)保持與故障節(jié)點x的不連通性.同時,為了降低地理范圍導致的資源開銷和傳輸時延,應限定候選節(jié)點與故障節(jié)點x間的相對距離.
首先,基于圖的連通性理論,構(gòu)造物理網(wǎng)絡GS的鄰接矩陣:
(4)
抽選出矩陣中故障節(jié)點x所對應的行列,判斷行列中元素的值,值為1則說明二者連通,為0不連通.選取值為0的節(jié)點構(gòu)成初始候選節(jié)點集合
(5)
該集合是由物理網(wǎng)絡GS中,初始候選節(jié)點集合IBN和故障節(jié)點x之間相對距離小于閾值D的節(jié)點元素構(gòu)成的集合,也是初始化階段構(gòu)造的最終物理節(jié)點候選集合.
圖2實例中,給定D=2,則初始候選節(jié)點集合為LBN(GS,x)={X,F,C},最終候選節(jié)點集合為BN(GS,x,2)={F,C}.
2) 物理鏈路初始化
當物理鏈路l(A,B)發(fā)生故障時,需要對其所承載的VNF實例鏈路li進行重定向.此處,采用路徑遍歷窮舉法構(gòu)造候選鏈路集合BL,集合中的元素需在保證VNF實例節(jié)點映射狀態(tài)不變的條件下,限定物理節(jié)點間跳數(shù)不超過閾值J.
首先,遍歷計算端節(jié)點A,B間的通路,構(gòu)造可達路徑集合RLA,B={l(node1),l(node2),…}.
然后,計算可達路徑集合RLA,B中候選路徑節(jié)點nodei的個數(shù)count(nodei),定義候選路徑集合BL如下:
BL(GS,l(A,B),J)=
{l(nodei)|count(nodei)-1≤J,
l(nodei)∈ES?ER,l(nodei)≠l(A,B)},
(6)
該集合是物理網(wǎng)絡GS的可達路徑集合RLA,B中,物理節(jié)點間跳數(shù)不超過閾值J且與原映射路徑不重疊的元素構(gòu)成的集合,即初始化階段構(gòu)造的物理鏈路候選集合.
圖3實例中,設定J=3,可達路徑集合為RLB,E={l(B,E),l(B,C,D,E),l(B,A,D,E),l(B,A,F,E)},候選鏈路集合為BL(GS,L(B,E),3)={l(B,A,D,E),l(B,A,F,E)}.
3.2.1 節(jié)點故障重映射的多目標優(yōu)化模型
物理平面節(jié)點故障問題可分為單節(jié)點故障和多節(jié)點故障問題,由于物理節(jié)點故障的發(fā)生具有一定的隨機性,無法預知未來可能發(fā)生故障的節(jié)點[24].因此,在節(jié)點故障重映射問題中,無法同時解決多節(jié)點故障問題,只能將其劃分為單節(jié)點故障問題逐一優(yōu)化.NFRM旨在最大化成功恢復安全服務請求數(shù)目的同時最小化VNF實例節(jié)點和VNF實例鏈路占用其重映射目標上備用資源的比例,而成功恢復數(shù)目的提高勢必會帶來資源消耗的增多,這2個目標函數(shù)相互沖突,不存在唯一的全局最優(yōu)解使得二者都達到最優(yōu).但是,存在一些解使得某個目標函數(shù)較優(yōu),同時其他目標函數(shù)不至于劣化,這樣的解稱為非劣有效解,又稱Pareto最優(yōu)解[25].為此,我們基于改進的DPSO算法來求解該MOP.首先,建立NFRM的MOP模型:
1) 變量定義
2) 約束條件
① 資源容量約束
(7)
(8)
式(7)和式(8)分別表示對任意候選節(jié)點或物理鏈路,用于重映射的節(jié)點資源容量和鏈路帶寬容量不得超過該節(jié)點或鏈路的實時剩余備用容量.
② 流量守恒約束
(9)
(10)
?j(1≤j≤|LR(ni)|),?x′∈BN(GS,x,D),
③ 變量取值約束
(11)
3) 目標函數(shù)
(12)
Obj2=
(13)
max(Obj1,Obj2).
(14)
NFRM進行故障節(jié)點重映射時,有2方面的優(yōu)化目標需重點考慮.一方面應盡可能最大化成功恢復安全服務請求的數(shù)目(式(12)),以確保用戶安全服務不受影響;另一方面應最小化VNF實例節(jié)點和VNF實例鏈路占用其重映射目標上備用資源的比例(式(13)中α,β為權重因子),優(yōu)先使用剩余備用資源容量大的物理節(jié)點和鏈路,有利于備用物理資源的負載均衡和物理平面整體抗毀能力的提升.式(14)為NFRM方法的Pareto目標函數(shù).
3.2.2 改進的離散粒子群算法
DPSO算法適合于對離散優(yōu)化問題的解空間進行多點隨機性搜索,其具有形式簡潔、收斂迅速、參數(shù)調(diào)節(jié)機制靈活等特點,目前已成功應用于MOP的求解當中.
DPSO算法中,每個粒子可以看作解空間中的一個點,如果粒子的群體規(guī)模為N,則第num=1,2,…,N個粒子可以用速度向量vnum和位置向量xnum表示,種群中的粒子num通過式(15)來更新自己進化過程中的速度和位置:
(15)
其中,w≥0代表慣性壓縮因子;c1,c2≥0代表加速因子;r1和r2是[0,1]內(nèi)均勻分布的隨機數(shù);xnum是粒子的當前位置;pBest[num]代表第num個粒子的個體最優(yōu)解;gBest代表整個群體的全局最優(yōu)解.式(15)中第1條為粒子速度更新公式,其中,第1部分為粒子依據(jù)自身速度進行慣性運動,表示粒子對當前自身運動的信任;第2部分為粒子的自我認知部分,表示粒子對自身歷史的思考;第3部分為粒子的社會認知部分,表示粒子在群體中的信息共享和相互協(xié)作.第2條采用sigmoid函數(shù)將粒子速度映射到[0,1]區(qū)間,作為下一步取值的概率.第3條為粒子的位置更新公式.
DPSO算法的參數(shù)中,慣性壓縮因子w對粒子的搜索能力有很大的影響,它決定搜索步伐的大小,較大的w有利于全局搜索,較小的w有利于局部搜索.通常在開始時搜索步伐大些,隨著迭代次數(shù)的增加,減小w值以防止錯過最優(yōu)解.本文所提故障恢復問題具有較高的時效性要求,因此,需要選擇一個合適的w值,在平衡全局和局部搜索能力的同時加快算法的收斂速度.式(16)為我們提出的一種慣性壓縮因子w的非線性自適應策略,使其值在每一輪迭代過程中動態(tài)變化.
(16)
本文參考文獻[27],提出改進的DPSO算法求解NFRM問題,偽代碼如算法1所示:
算法1.節(jié)點故障重映射算法.
輸入:物理網(wǎng)絡拓撲GS、故障物理節(jié)點ni;
輸出:Pareto最優(yōu)解.
Step1. 初始化,設定種群規(guī)模N、當前迭代次數(shù)t=0、隨機產(chǎn)生每個粒子的初始位置x0、初始速度v0;
Step2. 用目標函數(shù)Obj1,Obj2分別計算每個粒子的適應度值:
Fornum=1 toN
Fitness1[num]=Obj1(xnum);
Fitness2[num]=Obj2(xnum);
End For
Step3. 在2個目標函數(shù)Obj1和Obj2下分別對每個粒子求得個體極值:
Fornum=1 toN
pBest[1,num]←Obj1;
pBest[2,num]←Obj2;
End For
Step4. 對2個目標函數(shù)Obj1和Obj2,分別求2個全局極值:
gBest[1]←Obj1;
gBest[2]←Obj2;
Step5. 分別計算個體極值的均值和全局極值的均值:
pBest[num]=Average(pBest[1,num],pBest[2,num]);
gBest=Average(gBest[1],gBest[2]);
Step6. 用Step5計算所得的gBest和pBest[num]依據(jù)式(15)更新每個粒子的速度vi和位置xi,并依據(jù)式(16)更新慣性壓縮因子w的值;
Step7. 如滿足條件,則輸出最優(yōu)解,否則t++,轉(zhuǎn)Step2.結(jié)束條件為tmax>t或當前解已穩(wěn)定.
3.3.1 鏈路故障重定向的混合整數(shù)規(guī)劃模型
單鏈路故障問題在物理平面鏈路故障問題中最為常見,其發(fā)生具有瞬時性、不確定性,并且往往會給用戶安全服務請求造成較長時間的中斷.因此,本文將其建模為MIP問題并提出動態(tài)路徑分割算法,在發(fā)生物理鏈路故障時,動態(tài)調(diào)整底層物理路徑流量分割比例,重定向受影響流量至正常物理路徑.LFRD的目標在于最大化底層物理網(wǎng)絡資源剩余價值,使有限物理資源承載盡量多的安全服務請求.首先,進行算法條件準備:
1) 變量定義
2) 約束條件
① 鏈路帶寬約束
(17)
?l′(A,,B)∈BL(GS,l(A,B),J),
式(17)表示重定向VNF實例鏈路li中的φ份流量不能超過其宿主物理鏈路實時剩余帶寬容量.
② 流量守恒約束
(18)
?l′(A,,B)∈BL(GS,l(A,B),J),
式(18)表示當VNF實例鏈路li中的φ份流量重定向到物理鏈路l′(A,,B)上時,物理鏈路上的凈流量應該等于鏈路請求帶寬;否則,應滿足流量守恒定律.
③ 負載均衡約束
(19)
(20)
④ 變量取值約束
(21)
3) 目標函數(shù)
(22)
式(22)表示最大化底層物理資源剩余價值,是求解LFRD方法的目標函數(shù),其中ρ代表鏈路價值轉(zhuǎn)換權重.
3.3.2 動態(tài)路徑分割算法
動態(tài)路徑分割算法是指,在不改變VNF實例節(jié)點映射關系的前提下,將安全服務請求中VNF實例鏈路上的流量按比例分割并重定向在多條可用物理鏈路上.本文設計動態(tài)路徑分割算法用于求解LFRD問題的最優(yōu)解,偽代碼如算法2所示:
算法2.鏈路故障重定向算法.
輸入:物理網(wǎng)絡拓撲GS、故障物理鏈路l(A,B)、路徑分割率φ=(1+ε)|BL(GS,l(A,B),J)|;
輸出:底層物理資源剩余價值S(GS).
Step1.判斷VNF實例鏈路li是否具有路徑可分割性.如有,依據(jù)3.3.1節(jié)中算法條件準備2)中約束條件為其建立線性約束并初始化控制變量ε=0;S(GS)=0;否則,退出;
Step2.針對VNF實例鏈路li,按照路徑分割比例φ將其分別重定向在l′(A,,B)?BL(GS,l(A,B),J),并依據(jù)式(22)計算當前底層物理資源剩余價值T_S(GS);
Step3.比較T_S(GS)和S(GS).若T_S(GS)>S(GS),則S(GS)=T_S(GS);
Step4.控制變量ε++;
Step5.當ε<|BL(GS,l(A,B),J)|-1時,返回Step2;否則,退出;
實際中,對于安全服務請求中一些特殊的服務功能,路徑分割往往會導致其服務的中斷或者破壞其服務的連續(xù)性.因此,算法Step1階段,首先判斷VNF實例鏈路li是否可進行路徑分割.對于可分割的VNF實例鏈路,在滿足約束條件的情況下,依據(jù)“打擂”思想求解底層物理資源剩余價值的最大值;而對于不可分割的VNF實例鏈路,無法采用本文所提動態(tài)路徑分割算法求解,只能采用傳統(tǒng)方法對故障物理鏈路及相關節(jié)點重新進行資源映射或?qū)ξ锢砥矫鏀?shù)據(jù)包進行標記改造,這超出了本文的研究范圍.
本文開展仿真實驗的目的有3個方面:
1) 在不同物理網(wǎng)絡環(huán)境下,評估本文方法的適應性;通過設置不同資源容量載荷的物理網(wǎng)絡拓撲,比較本文方法性能差異.
2) 在不同故障模型下,評估本文方法的有效性;由于傳統(tǒng)服務鏈映射方法暫未考慮物理網(wǎng)絡故障問題,Lee等人也僅在文獻[22]中提出一種服務鏈的故障自恢復方案,故都不便與本文方法直接進行比較.因此,本文將經(jīng)典的服務鏈映射方法[16]和服務鏈故障自恢復方案[22]分別擴展為未采用故障恢復方法的NFRMLFRD算法(N_NFRMN_LFRD)和采用故障自恢復方法的NFRMLFRD算法(S_NFRMS_LFRD)與本文所提(P_NFRMP_LFRD)方法進行比較.
3) 在不同故障發(fā)生頻率下,測試資源主用比例λ對本文方法性能的影響;針對不同故障發(fā)生率,探索資源主用比例的最佳取值.
仿真實驗在配置Intel Core i7-6300HQ @3.40 GHz,8 GB內(nèi)存的PC機上進行,借助GT-ITM[28]工具生成底層物理網(wǎng)絡拓撲并利用Matlab工具對實驗結(jié)果進行分析.每次實驗運行50 000個時間單位.
實驗設置3種不同資源容量載荷的物理網(wǎng)絡拓撲對本文方法進行評估,拓撲中的每對節(jié)點以0.5概率相連,節(jié)點類型及個數(shù)如表1所示.假設物理網(wǎng)絡中的每個服務節(jié)點都能提供計算、存儲和帶寬3種資源,為了便于實驗分析,重點關注服務節(jié)點的存儲資源(限定每個服務節(jié)點的最大存儲容量為16 GB),而節(jié)點間的物理鏈路,重點關注其帶寬資源(限定每條物理鏈路的最大負載量為2 Gbps).針對在物理網(wǎng)絡Phy1中,節(jié)點資源總量(單位:M)和鏈路帶寬(單位:Mbps)分別服從[0,50]和[50,100]的均勻分布.物理網(wǎng)絡Phy2中,節(jié)點資源總量和鏈路帶寬分別服從[50,100]和[100,200]的均勻分布.物理網(wǎng)絡Phy3中,節(jié)點資源總量和鏈路帶寬分別服從[0,200]和[0,400]的均勻分布.物理節(jié)點故障的到達服從時間單位為100、強度為pn的泊松過程,故障持續(xù)時間服從均值為dn個時間單位的指數(shù)分布,物理節(jié)點候選集合相對距離D=3;物理鏈路故障的到達服從時間單位為100、強度為pl的泊松過程,故障持續(xù)時間服從均值為dl個時間單位的指數(shù)分布,物理鏈路候選集合跳數(shù)J=4.
Table 1 Number of Nodes in the Experimental Topology表1 實驗拓撲節(jié)點個數(shù)信息
假設網(wǎng)絡中有6種安全功能,每種安全功能有3種VNF實例.安全服務請求SSR中VNF實例節(jié)點的數(shù)目服從[3,5]的均勻分布,VNF實例節(jié)點間以0.5的概率相連.VNF實例節(jié)點資源需求和VNF實例鏈路帶寬需求分別服從[1,10]和[1,15]的均勻分布.安全服務請求SSR的到達服從時間單位為100、強度為4的泊松過程,請求的生命周期服從均值為40個時間單位的指數(shù)分布.
對于3.2節(jié)提出的基于改進的DPSO算法求解NFRM,將目標函數(shù)中節(jié)點資源權重α和鏈路資源權重β都設為1.DPSO算法中,設種群規(guī)模N=100,最大迭代次數(shù)tmax=50,初始權重winitial=1,最終權重wfinal=0.1,加速因子c1,c2均取2;對于3.3節(jié)提出的基于動態(tài)路徑分割算法求解LFRD,設鏈路價值轉(zhuǎn)換權重ρ=1.
安全服務請求故障修復率是指使用故障恢復方法后,能夠正常運行的安全服務請求數(shù)目與故障發(fā)生前正常運行的安全服務請求數(shù)目的比值,反映了故障修復算法的有效性.本文通過模擬物理節(jié)點故障和物理鏈路故障,從安全服務請求故障修復率角度對3.2和3.3節(jié)所提方法進行驗證,仿真結(jié)果如圖4~11所示.
圖4和圖5展現(xiàn)了在3種不同資源容量載荷的物理網(wǎng)絡上,NFRM和LFRD方法的故障修復率和故障修復時間.為便于比較,物理節(jié)點故障強度pn和物理鏈路故障強度pl均取3,故障持續(xù)時間dn和dl均取25,主用比例λ均取75%.
Fig. 4 The fault-recovery rate of NFRMLFRD in different substrate networks圖4 不同物理網(wǎng)絡下NFRMLFRD的故障修復率
Fig. 5 The fault-recovery time of NFRMLFRD in different substrate networks圖5 不同物理網(wǎng)絡下NFRMLFRD的故障修復時間
由圖4(a)可知,NFRM方法在3種不同資源容量載荷的物理網(wǎng)絡上,故障修復率較為接近.其中,物理網(wǎng)絡Phy1和Phy3下故障修復率分別為92%和86%;而在物理網(wǎng)絡Phy2下,安全服務請求故障修復率大概在96%,高于其他2種類型物理網(wǎng)絡,這主要是因為Phy2提供的節(jié)點資源總量和鏈路帶寬分別服從[50,100]和[100,200]的均勻分布,而VNF實例節(jié)點資源需求和VNF實例鏈路帶寬需求分別服從[1,10]和[1,15]的均勻分布,從資源配置角度來看,Phy2能夠在滿足請求資源的同時保證較高的故障修復率.觀察圖4(b)可知,LFRD方法在3種物理網(wǎng)絡上的故障修復率相差不大,但相比圖4(a)而言,物理網(wǎng)絡Phy1和Phy3下的故障修復率分別提高了1%和2%,可見LFRD方法即使在資源配置不合理的物理網(wǎng)絡環(huán)境下,仍能保證較高的故障修復率,對于多樣化物理網(wǎng)絡配置具有更好的適應性.
圖5(a)表示NFRM方法在3種不同資源容量載荷的物理網(wǎng)絡上的故障修復時間.可以看出,隨著SSC個數(shù)的增多,不同物理網(wǎng)絡下的NFRM故障修復時間不斷增長.這是因為隨著SSC個數(shù)的增多,可能發(fā)生故障的物理節(jié)點鏈路比例也隨之增大.其中,物理網(wǎng)絡Phy1和Phy3下故障修復時間波動性較大;而在物理網(wǎng)絡Phy2下,故障修復時間均勻增大并趨向于穩(wěn)定,這主要是因為Phy2提供的節(jié)點資源總量和鏈路帶寬總量能更好地滿足物理網(wǎng)絡資源配置需求.觀察圖5(b)可知,LFRD方法在3種物理網(wǎng)絡上的故障修復時間較為接近,但相比圖5(a)而言,在資源配置不盡合理的物理網(wǎng)絡環(huán)境下,Phy1和Phy3下的故障修復時間分別延長了0.9 s和0.5 s,即使在資源配置較為合理的Phy2下,仍存在近1s的延遲,可見對于未采用啟發(fā)式算法求解的LFRD方法,雖然能夠保證較高的故障修復率,但是當SSC個數(shù)增多時,存在故障修復時間較長的弊端.
Fig. 6 The fault-recovery rate of different NFRMs when dn=25圖6 dn=25時各NFRM的故障修復率
Fig. 7 The fault-recovery rate of different NFRMs when dn=50圖7 dn=50下各NFRM的故障修復率
Fig. 8 The fault-recovery rate of different LFRDs when dl=25圖8 dl=25下各LFRD的故障修復率
Fig. 9 The fault-recovery rate of different LFRDs when dl=50圖9 dl=50下各LFRD故障修復率
如圖6所示,當dn一定時,P_NFRM的平均故障修復率可達95%,分別高出S_NFRM和N_NFRM五個百分點和十個百分點.對比圖7還可看出,當dn增加時,P_NFRM性能受影響不大,而其他2種方法性能明顯下降.由此可見,當發(fā)生多節(jié)點故障概率增加時,本文方法具有更好的穩(wěn)定性,這是因為本文方法對可能發(fā)生的故障問題進行了前攝性的準備.此外,當dn較大時,S_NFRM和N_NFRM的曲線較為接近,主要是因為當節(jié)點故障概率增加時,2種方法恢復故障鏈的效率明顯降低.觀察圖8可知,當dl較小時,P_LFRD的平均故障修復率遠高于其他2種方法且性能發(fā)揮較為穩(wěn)定.對比圖9可以看出,當dl較大時,P_LFRD的曲線波動較為明顯,呈現(xiàn)出一定的不穩(wěn)定性,這是因為隨著鏈路故障持續(xù)時間的增長,物理網(wǎng)絡中發(fā)生區(qū)域性鏈路故障的概率增加,為鏈路故障修復帶來了一定的困難.
資源主用比例λ的取值直接影響本文方法的有效性,增大λ的取值,一方面可以提高SSC構(gòu)建的成功率;另一方面卻會減少故障備份的可用資源,為SSC的故障恢復增加難度.因此,本文通過仿真實驗探索不同故障發(fā)生頻率下最優(yōu)的λ取值.實驗在物理網(wǎng)絡Phy2上進行,故障持續(xù)時間dn和dl均取25.
由圖10(a)可知,NFRM在pn取1,2,3,4時的最優(yōu)節(jié)點資源主用比例分別為80%,70%,67%和60%,可見,λ的取值與故障發(fā)生強度pn呈現(xiàn)出一定的線性相關性,在故障強度增大時,主用比例逐漸減小,并且減小的趨勢逐漸平緩.觀察圖10(b)具有類似的曲線特性.可見,曲線結(jié)果與前述分析具有一致性.
Fig. 10 The impact of different link resourcemain-proportion on NFRMLFRD圖10 不同鏈路資源主用比例對NFRMLFRD的影響
本文主要圍繞NFV環(huán)境下SSC故障恢復問題展開討論,在已有無故障恢復服務鏈構(gòu)建方法基礎之上,創(chuàng)新性地提出了一種SSC故障的備份恢復機制.針對物理節(jié)點故障和物理鏈路故障2種不同的情形,通過預留備用資源和構(gòu)造初始化候選集合來提高故障發(fā)生時SSC的恢復能力,分別設計改進的DPSO算法和動態(tài)路徑分割算法求解此問題.實驗表明,本文方法可在不同物理網(wǎng)絡環(huán)境下和不同故障模型下有效提高安全服務請求的故障修復率,增強SSC的生存抗毀性.
未來工作主要從以下3個方面展開:1)求解MIP的動態(tài)路徑分割算法只適用于中小規(guī)模物理網(wǎng)絡,當面臨大規(guī)模物理網(wǎng)絡時,為保證故障恢復的時效性,應設計高效的啟發(fā)式算法近似求解;2)收集SSC故障歷史數(shù)據(jù)并進行統(tǒng)計分析,設計更具有針對性的故障恢復方案;3)進一步試驗探索主用比例對本文方法的影響,形式化定義并尋求最優(yōu)解.
[1]Paul S, Pan J L, Jain R. Architectures for the future networks and next generation Internet: A survey[J]. Computer Communications, 2011, 34(1): 2-42
[2]Quinn P, Guichard J, Yadav N. Network Service Chaining Problem Statement, RFC 7498[S]. Fremont, CA: IETF, 2015
[3]Huang Tao, Liu Jiang, Huo Ru, et al. Survey of research on future network architectures[J]. Journal on Communications, 2014, 35(8): 184-197 (in Chinese)(黃韜, 劉江, 霍如, 等. 未來網(wǎng)絡體系架構(gòu)研究綜述[J]. 通信學報, 2014, 35(8): 184-197)
[4]Lantz B, Heller B, Mckeown N. A network in a laptop: Rapid prototyping for software-defined networks[C]Proc of the 9th ACM SIGCOMM Workshop on Hot Topics. New York: ACM, 2010: 1-6
[5]Chiosi M, Clarke D, Willis P, et al. Network functions virtualization-introductory white paper[OL]. [2017-06-22]. https:portal.etsi.orgnfvnfv whitepaper.pdf
[6]Jeff W. Delivering Security Virtually Everywhere with SDN and NFV: IHS INFONETICS White Paper[OL]. [2017-04-28]. http:www.juniper.netassetsfrfrlocalpdfanalyst-reports2000602-en.pdf
[7]Lee W, Choi Y H, Kim N. Study on virtual service chain for secure software-defined networking[OL]. [2017-11-12]. http:onlinepresent.orgproceedingsvol29_201336.pdf
[8]Shin S, Porras P, Yegneswaran V, et al. FRESCO: Modular composable security services for software-defined networks[C]Proc of the 20th Annual Network and Distributed System Security Symp. San Diego: Internet Society, 2013: 32-48
[9]Ocampo A F, Gil-Herrera J, Isolani P H, et al. Optimal service function chain composition in network functions virtualization[C]Proc of the 11th Int Conf on Autonomous Infrastructure, Management and Security. Berlin: Springer, 2017: 62-76
[10]Gill P, Jain N, Nagappan N. Understanding network failures in data centers: Measurement, analysis, and implications[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 350-361
[11]Hwang J, Ramakrishnan K K, Wood T. NetVM: High performance and flexible networking using virtualization on commodity platforms[J]. IEEE Trans on Network and Service Management, 2015, 12(1): 34-47
[12]Martins J, Ahmed M, Raiciu C, et al. Enabling fast, dynamic network processing with clickOS[C]Proc of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 67-72
[13]Zhang Wei, Liu Guyue, Zhang Wenhui, et al. OpenNetVM: A platform for high performance network service chains[C]Proc of the 2016 Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2016: 26-31
[14]Dwaraki A, Wolf T. Adaptive service-chain routing for virtual network functions in software-defined networks[C]Proc of the 2016 Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2016: 32-37
[15]Xiong Gang, Hu Yuxiang, Lan Julong, et al. A mechanism for configurable network service chaining and its implementation[J]. KSII Trans on Internet & Information Systems, 2016, 10(8): 3701-3727
[16]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 12th Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2015: 98-106
[17]Riera J F, Hesselbach X, Escalona E, et al. On the complex scheduling formulation of virtual network functions over optical networks[C]Proc of Int Conf on Transparent Optical Networks. Piscataway, NJ: IEEE, 2014: 1-5
[18]Jordi F R, Eduard E, Josep B, et al. Virtual network function scheduling: Concept and challenges[C]Proc of the 2nd Int Conf on Smart Communications in Network Technologies. Piscataway, NJ: IEEE, 2014: 1-5
[19]Mijumbi R, Serrat J, Gorricho J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]Proc of the 2015 Int Conf on Network Softwarization. Piscataway, NJ: IEEE, 2015: 1-9
[20]Nguyen V C, Kim Y H. A failover mechanism for service function chain[C]Proc of the 2017 Symp of the Korean Institute of Communications and Information Sciences. Seoul, Korean: SoongSil University Press, 2017: 1145-1146
[21]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
[22]Lee S I, Shin M K. A self-recovery scheme for service function chaining[C]Proc of the 2015 Int Conf on Information and Communication Technology Convergence. Piscataway, NJ: IEEE, 2015: 108-112
[23]Sato Y. IECJIS standard-functional safety of electricalelectronicprogrammable electronic safety-related systems[C]Proc of the 1999 General Conf on Electronics, Information and Communication Engineers. London: Oxford University Press, 1999: 567-568
[24]Xiao Ailing, Wang Ying, Meng Luoming, et al. Virtual network embedding approach to survive multiple node failures[J]. Journal on Communications, 2015, 36(4): 81-88 (in Chinese)(肖藹玲, 王穎, 孟洛明, 等. 面向多節(jié)點故障的生存性虛擬網(wǎng)絡映射方法[J]. 通信學報, 2015, 36(4): 81-88)
[25]Zheng Jinhua, Jiang Hao, Kuang Da, et al. An approach of constructing multi-objective Pareto optimal solutions using arena’s principle[J]. Journal of Software, 2007, 18(6): 1287-1297 (in Chinese)(鄭金華, 蔣浩, 鄺達, 等. 用擂臺賽法則構(gòu)造多目標Pareto最優(yōu)解集的方法[J]. 軟件學報, 2007, 18(6): 1287-1297)
[26]Zhang Changsheng, Sun Jigui, OuYang Dantong. A self-adaptive discrete particle swarm optimization algorithm[J]. Acta Electronica Sinica, 2009, 37(2): 299-304 (in Chinese)(張長勝, 孫吉貴, 歐陽丹彤. 一種自適應離散粒子群算法及其應用研究[J]. 電子學報, 2009, 37(2): 299-304)
[27]Hu Wang, Yen G G, Zhang Xin. Multi-objective particle swarm optimization based on Pareto entropy[J]. Journal of Software, 2014, 25(5): 1025-1050 (in Chinese)(胡旺, Yen G G, 張鑫. 基于Pareto熵的多目標粒子群優(yōu)化算法[J]. 軟件學報, 2014, 25(5): 1025-1050)
[28]Calvert K L, Doar M B, Zegura E W. Modeling Internet topology[J]. IEEE Communications Magazine, 1997, 35(6): 160-163
HuangRui, born in 1993. Master candidate. Her main research interests include software defined network and network function virtualization.
ZhangHongqi, born in 1962. PhD, professor. His main research interests include network security and classification protection (zhq37922@126.com).
ChangDexian, born in 1977. PhD, associate professor. His main research interests include SDN security and trusted computing (changdexian@126.com).