安全虛擬網絡映射的啟發式算法

劉新波, 王布宏, 劉帥琦, 楊智顯, 趙志遠

(空軍工程大學信息與導航學院, 陜西 西安 710077)

0 引 言

目前,網絡虛擬化技術受到了學術界和工業界的高度重視,它不僅是解決當前互聯網面臨的僵化問題的關鍵技術[1],也是云計算中的核心技術。虛擬網絡映射是網絡虛擬化需要著重解決的問題之一,已有的研究成果證明該問題屬于非確定性多項式時間(non-deterministic polynomial-time，NP)難問題[2]。現有的虛擬網絡映射算法主要以提高底層物理網絡的映射收益[3-5]或降低能耗[6-8]為目標,并采用啟發式算法[9-10]或者元啟發式算法[11-12]進行求解。然而,網絡虛擬化在為網絡架構帶來靈活性的同時,也帶來了一些新的安全問題[13]。

針對網絡虛擬化所帶來的安全威脅,文獻[13]首次提出了安全虛擬網絡映射(secure virtual network embedding, SVNE)概念,并給出了SVNE應滿足的安全約束條件。在此基礎上,文獻[14]根據加密方式不同將虛擬網絡請求(virtual network request,VNR)和底層物理網絡節點設置為不同的安全等級,建立了SVNE模型,并對離線虛擬網絡映射進行了仿真計算,結果表明部分情況下完成虛擬網絡映射所需的時間過長。文獻[15-16]將虛擬節點和物理節點的安全屬性抽象為安全需求等級和安全等級,建立了SVNE混合整數線性規劃模型,并采用啟發式算法對在線虛擬網絡映射進行了仿真計算,提高了虛擬網絡映射的運算速度,但沒有著重考慮虛擬節點的安全屬性對映射成功率的影響。文獻[17]提出了針對隱蔽信道攻擊的SVNE算法,提高了虛擬節點的安全性,但該算法針對特定安全問題,其應用范圍受限。

在現有研究基礎上,本文主要工作包括以下幾點:

(1) 對SVNE模型進行優化,以最小化物理網絡的映射開銷和最小化物理節點的安全屬性改變量為目標函數,構建了多目標優化的SVNE混合整數線性規劃模型;

(2) 針對改進的SVNE模型,提出了基于節點多屬性綜合評估與路徑優化的SVNE算法(SVNE algorithm based on node attributes comprehensive assessment and path optimization,NP-SVNE);

(3) 編寫仿真程序,對NP-SVNE算法進行仿真計算,驗證了該算法在虛擬網絡請求接受率和收益開銷比等方面較現有算法具有較大的優越性。

1 問題描述

1.1 安全約束抽象

在網絡虛擬化環境中,有些VNR對安全性要求較高,如與金錢密切相關的網上支付和網上購物等,而有的VNR對安全性要求相對較低,如在線游戲和在線視頻等。因此,本文將VNR的安全屬性設置為不同的安全需求等級和安全等級,而不是將虛擬網絡中的每個虛擬節點都設置為不同的安全需求等級和安全等級[15-16]。同時,虛擬網絡映射過程中需要滿足與文獻[13,15-16]相同的安全約束條件。

1.2 網絡模型

1.2.1 物理網絡

物理網絡拓撲使用加權無向圖Gp=(Np,Ep)表示,其中Np為物理節點集合;Ep為物理鏈路集合。物理節點np∈Np的屬性取可用CPU資源cpu(np)、安全需求等級sd(np)和安全等級sl(np)。物理鏈鏈路ep∈Ep的屬性取剩余帶寬b(ep)。

1.2.2 VNR

使用VNRi=(Gv,ta,td)來表示第i個到達的VNR,其中Gv為虛擬網絡拓撲;ta為VNR到達時間;td為VNR結束時間。虛擬網絡拓撲也使用加權無向圖Gv=(Nv,Ev)表示,其中Nv為虛擬節點集合;Ev為虛擬鏈路集合。虛擬節點nv∈Nv的屬性取CPU資源需求cpu(nv)、安全需求等級sd(nv)和安全等級sl(nv),虛擬節點的安全需求等級和安全等級與相應的VNR的安全需求等級和安全等級相同。虛擬鏈路ev∈Ev的屬性取鏈路帶寬需求b(ev)。

1.2.3 SVNE

SVNE是一類特殊虛擬網絡映射,在映射過程中除了需要滿足節點資源和鏈路資源的約束條件外,還需要滿足安全性約束條件。根據安全性約束條件限制,當虛擬節點映射至物理節點后,物理節點的安全屬性可能會發生改變,從而影響其承載后續到達的虛擬網絡映射請求的能力。圖1為2個按時間序列到達的虛擬網絡映射請求,任一節點n旁邊圓括號內的數字依次代表節點的屬性cpu(n)、sd(n)和sl(n),任一鏈路e旁邊的數字代表鏈路的屬性b(e)。如果VNR1按照方案1進行映射,則映射完成后,物理節點B、C和A的安全需求等級會升高,均變為3,使后續到達的VNR2由于無法滿足安全性約束而不能成功映射。如果VNR1按照方案2進行映射,則映射完成后,物理網絡中所有節點的安全屬性均不發生變化,使后續到達的VNR2可以順利完成映射,其一種可行的節點映射方案為{d→B,e→C,f→A},相應的鏈路映射方案為{(d,e)→(B,C),(d,f)→(B,A),(e,f)→(C,A)}。因此,在面向安全的虛擬網絡映射過程中,不僅要以盡量降低物理網的絡映射開銷為目標,還要以盡量不改變物理節點的安全屬性為目標。

圖1 虛擬網絡映射示例Fig.1 Example of virtual network embedding

1.3 評價指標

與文獻[3-4,15-16]類似,以虛擬網絡請求接受率、物理網絡映射收益、物理網絡映射開銷和收益開銷比作為SVNE算法的評價指標,并根據SVNE需要,對其進行適量修改。

虛擬網絡請求接受率定義為

(1)

式中,VNRs表示映射成功的VNR;VNRa表示到達的VNR。

定義VNRi=(Gv,ta,td)在t時刻的映射收益為

(2)

式中,α(ns)=1+0.1·sd(ns)表示虛擬節點ns的單位CPU資源映射收益,其大小與虛擬節點的安全需求等級有關。

定義VNRi=(Gv,ta,td)在t時刻的映射開銷為

(3)

物理網絡收益開銷比定義為物理網絡的長時間平均收益與長時間平均開銷的比值,表示為

(4)

2 多目標優化數學模型

2.1 目標函數

在SVNE過程中,不僅要盡量降低虛擬網絡的映射開銷,還要盡量不改變物理節點的安全屬性,以便使其能夠更好地承載后續到達的虛擬網絡映射請求。因此,在文獻[15-16]的基礎上,將SVNE問題建模為多目標混合整數線性規劃模型,以最小化物理網絡映射開銷和最小化物理節點安全屬性改變量為目標函數,表示為

(5)

(6)

2.2 節點約束條件

首先,物理節點ni的剩余可用資源應不小于映射在其上的虛擬節點ns的資源需求為

(7)

其次,若虛擬節點與物理節點之間存在映射關系,則虛擬節點和物理節點的映射關系應該是一對一映射關系,需滿足的約束條件為

(8)

(9)

(10)

2.3 鏈路約束條件

首先,任一條物理鏈路eij的剩余帶寬應該不小于映射到其上的虛擬鏈路的帶寬和,即

(11)

其次,需要考慮鏈路的連通性約束,確保將虛擬鏈路映射至一條無環路的物理路徑上,即

?ni∈Np,?est∈Ev

(12)

(13)

2.4 安全性約束條件

(14)

3 NP-SVNE算法設計

3.1 節點映射

步驟1計算虛擬節點資源能力。在節點映射階段,節點資源需求大的節點更難映射成功,應優先映射這類節點。因此,本文定義的虛擬節點資源能力屬性為

(15)

式中,E(nv)是nv的鄰邊集合。

步驟2對虛擬節點進行排序。為了盡量使虛擬網絡中相鄰的節點在映射至物理網絡后仍然保持鄰近性,減少虛擬鏈路映射至物理路徑的跳數,本文采用廣度優先搜索算法通過構造虛擬節點的映射樹來對虛擬節點進行排序,即以H(nv)最大的虛擬節點為根節點,運行廣度優先搜索算法,將剩余虛擬節點按照距根節點的距離進行排序,若距根節點距離相同,則按照H(nv)值從大到小的順序排列。

k≤sl(np)&&sd(np)≤l,np∈Np}

(16)

(17)

式中,H(np)為物理節點np的資源能力屬性;Security(np)為物理節點np的安全性屬性;Distance(np)為物理節點np的距離屬性;ε是一個非常小的正數,避免分母為零。

(18)

式中，E(np)為np的鄰接鏈路集合。

Security(np)=

(19)

式中,σ(0<σ<1)和λ(0<λ<1)是權重因子。

(20)

(21)

在虛擬節點映射過程中,選擇NEF作為映射標準,主要基于以下3點考慮:①優先考慮可用資源大的物理節點,有利于抑制網絡碎片的產生,從而可以提高虛擬網絡請求接受率;②優先選擇安全等級與VNR的安全需求等級相近的物理節點,可以降低映射開銷;當VNR的安全需求等級大于物理節點的安全需求等級時,優先選擇安全需求等級與VNR的安全需求等級相近的物理節點,可以較少地改變物理節點的安全需求等級,有利于完成后續到達的虛擬網絡映射請求;③優先選擇到已映射節點距離和較小的節點,可以降低鏈路資源消耗,提高物理網絡的資源利用率。NP-SVNE的節點映射算法主要流程的偽代碼如表1所示。

表1NP-SVNE的節點映射算法偽代碼

Table1Pseudo-codeofNP-SVNE’snodeembeddingalgorithm

3.2 鏈路映射

步驟1對虛擬鏈路進行排序。根據虛擬鏈路對帶寬需求的大小,將虛擬鏈路按降序進行排列。優先映射帶寬需求大的虛擬鏈路。

步驟3計算候選物理路徑的路徑映射函數(path embedding function,PEF)值,并將虛擬鏈路映射至PEF值最大的物理路徑。PEF的定義為

(22)

式中,b(pk)為路徑pk的可用帶寬；hops(pk)為路徑pk的跳數。

將虛擬鏈路映射至PEF值最大的物理路徑,可以協調物理鏈路資源消耗并降低映射開銷。NP-SVNE的鏈路映射算法主要流程的偽代碼如表2所示。

表2NP-SVNE的鏈路映射算法偽代碼

Table2Pseudo-codeofNP-SVNE’slinkembeddingalgorithm

4 實驗及結果分析

4.1 實驗環境設置

當前,在進行虛擬網絡映射算法研究時,常用的網絡拓撲生成工具有佐治亞理工學院的網絡拓撲模型(georgia tech internetmork topology models, GT-ITM)和Waxman網絡拓撲生成器。在本文中,與文獻[15-16]類似,使用GT-ITM來生成物理網絡和虛擬網絡的網絡拓撲結構,通過控制其參數α和β來改變所生成網絡中的邊數和長邊相對短邊的比例。物理網絡拓撲由100個節點和500條鏈路組成。另外,cpu(np)和b(ep)均服從50～100的整數均勻分布;sd(np)和sl(np)服從0～4的整數均勻分布,且每個物理節點的安全需求等級不能高于其安全等級。

VNR的到達過程和生存時間與文獻[15]相同。對每個VNR來說,其節點個數服從4～10的整數均勻分布,每對節點間以0.5的概率相互連接。另外,cpu(nv)和b(ev)均服從0～50的整數均勻分布;sd(nv)和sl(nv)服從0～4的整數均勻分布,且每個虛擬節點的安全需求等級不能高于其安全等級。

本文進行了4種算法的比較。NP-SVNE是本文提出的基于節點多屬性綜合評估與路徑優化的安全虛擬網絡映射算法。NR-SVNE是文獻[15]提出的基于節點排序的安全虛擬網絡映射算法。TA-SVNE是文獻[16]提出的基于TOPSIS多屬性節點重要性排序的安全虛擬網絡映射算法。G-SVNE是文獻[16]提出的基于貪婪策略的安全虛擬網絡映射算法。

4.2 實驗結果分析

本文所對比的4種算法的虛擬網絡請求接受率隨時間的變化關系如圖2所示。

圖2 虛擬網絡請求接受率Fig.2 Acceptance ratio of virtual network request

由圖2可知，初始時間段4種算法的虛擬網絡請求接受率都比較高,這是因為剛開始時物理網絡的可用資源比較豐富。隨著時間的推進和VNR的不斷到來,物理網絡的可用資源逐漸減少,請求接受率逐漸下降,并在約5 000個時間單元后趨于穩定。虛擬網絡請求接受率穩定后,NP-SVNE算法的接受率約為90%,分別較NR-SVNE、TA-SVAE和G-SVNE算法提高了約6.4%、26.6%和37.0%。與其他算法相比,NP-SVNE算法在節點映射階段更多的考慮了節點的安全屬性和拓撲鄰近性,在鏈路映射階段綜合考慮了路徑帶寬和跳數,這些措施使節點匹配更加合理,使鏈路映射更加優化,因此提高了虛擬網絡請求接受率。

本文所對比的4種算法的平均收益隨時間的變化關系如圖3所示。

圖3 物理網絡平均映射收益Fig.3 Average embedding revenue of physical network

由圖3可知，初始時間段到達的VNR數量較少,4種算法的物理網絡平均收益均比較低。隨著仿真時間的持續,到達的VNR數量逐漸增加,物理網絡的平均收益逐漸增加,并在約5 000個時間單元后趨于穩定。由于NP-SVNE算法的虛擬網絡請求接受率最高,因此在相同時間內映射成功的虛擬網絡數量也最多,物理網絡的平均收益也最高,約為9 983,分別較NR-SVNE、TA-SVNE和G-SVNE算法提高了約9.9%、38.5%和46.0%。

本文所對比的4種算法的平均開銷隨時間的變化關系如圖4所示。

圖4 物理網絡平均映射開銷Fig.4 Average embedding cost of physical network

由圖4可知，仿真初始階段到達的VNR數量較少,物理網絡的映射開銷較低。隨著仿真時間的持續,到達的VNR數量逐漸增多,物理網絡的映射開銷也隨之增大,并在約5 000個時間單元后趨于穩定。由于NP-SVNE算法在節點映射階段考慮了節點之間的鄰近關系和安全屬性的最優匹配,因此其映射開銷最低,約為17 412,分別較NR-SVNE、TA-SVNE和G-SVNE算法降低了約12.6%、8.9%和14.6%。

本文所對比的4種算法的收益開銷比隨時間的變化關系如圖5所示。

圖5 收益開銷比Fig.5 Revenue/cost ratio

由圖5可知，初始時間段,隨時間的增加,4種算法的收益開銷比均有所降低,這是因為隨著VNR增加,物理網絡的可用資源減少,虛擬鏈路映射的物理路徑長度增加,從而增加了映射開銷。穩定后,NP-SVNE算法的收益開銷比最高,約為57%,分別較NR-SVNE、TA-SVNE和G-SVNE算法提高了約23.9%、50.0%和67.6%。

5 結束語

虛擬網絡映射問題屬于NP難問題,加入安全約束條件后會進一步增加虛擬網絡映射的復雜程度,導致現有SVNE算法的性能不夠理想。針對該問題,構建了多目標優化的SVNE混合整數線性規劃模型,提出了啟發式的SVNE算法NP-SVNE。該算法在節點映射階段綜合評估了節點的資源能力、拓撲鄰近性和安全屬性,在鏈路映射階段考慮了物理路徑的長度和可用帶寬。仿真結果表明,NP-SVNE算法的多項評價指標(如,η和R/C等)均優于現有的SVNE算法。但該算法沒有考慮映射過程中物理網絡的可靠性。下一步需結合物理網絡的安全等級發生改變或突然失效等情況,將可靠性引入SVNE過程,研究安全可靠的虛擬網絡映射算法。

[1] ANDERSON T, PETERSON L, SHENKER S, et al. Overcoming the internet impasse through virtualization[J]. Computer, 2005, 38(4): 34-41.

[2] AMALDI E. On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52:213-220.

[3] BIANCHI F, PRESTI F L. A markov reward model based greedy heuristic for the virtual network embedding problem[C]∥Proc.of the IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2016: 373-378.

[4] CUI H Y, GAO W J, LIU J,et al. A virtual network embedding algorithm based on virtual topology connection feature[C]∥Proc.of the IEEE 16th International Symposium on Wireless Personal Multimedia Communications, 2013: 1-5.

[5] LIU X, ZHANG Z B, LI X M, et al. Optimal virtual network embedding based on artificial bee colony[J]. Eurasip Journal on Wireless Communications & Networking, 2016, 2016(1): 273.

[6] ZHANG Z B, SU S, ZHANG J C, et al. Energy aware virtual network embedding with dynamic demands:online and offline[J]. Computer Networks, 2015, 93: 448-459.

[7] TRIKI N, KARA N, BARACHI M E, et al. A green energy-aware hybrid virtual network embedding approach[J]. Computer Networks, 2015, 91: 712-737.

[8] HAN X, HAN P C, LIU Y J, et al. Green virtual network embedding with periodical sleep mechanism for fiber-wireless access network[C]∥Proc.of the Asia Communications and Photonics Conference, 2016, paper AF3E.3.

[9] LEKHA P, TRAM T H, MOHAN G. Time and bandwidth-aware virtual network embedding and migration in hybrid optical-electrical data centers[C]∥Proc.of the IEEE 31st International Conference on Advanced Information Networking and Applications, 2017: 947-954.

[10] SHAHRIAR N, AHMED R, KHAN A, et al. ReNoVatE: recovery from node failure in virtual network embedding[C]∥Proc.of the 12th International Conference on Network and Service Management (CNSM), 2016: 19-27.

[11] ZHANG Z B, SU S, LIN Y K, et al. Adaptive multi-objective artificial immune system based virtual network embedding[J]. Journal of Network and Computer Applications,2015,53:140-155.

[12] WANG C, SU Y, ZHOU L X, et al. A virtual network embedding algorithm based on hybrid particle swarm optimization[C]∥Proc.of the International Conference on Smart Computing & Communication, 2016: 568-576.

[13] FISCHER A, DE MEER H. Position paper: secure virtual network embedding[J]. Praxis der Information Sverarbeitung und Kommunikation, 2011, 34(4): 190-193.

[14] BAYS L R, OLIVEIRA R R, BURIOL L S, et al. Security-aware optimal resource allocation for virtual network embedding[C]∥Proc.of the 8th International Conference on Network and Service and Service Management, 2012: 378-384.

[15] LIU S H, CAI Z P, XU H, et al. Towards security-aware virtual network embedding[J].Computer Networks,2015,91:151-163.

[16] 龔水清,陳靖,黃聰會,等. 信任感知的安全虛擬網絡映射算法[J]. 通信學報, 2015, 36(11): 180-189.

GONG S Q, CHEN J, HUANG C H, et al. Trust-aware secure virtual network embedding algorithm[J]. Journal on Communications, 2015, 36(11): 180-189.

[17] WANG Z M, WU J X, GUO Z H, et al. Secure virtual network embedding to mitigate the risk of covert channel attacks[C]∥Proc.of the IEEE Conference on Computer Communications Workshops, 2016: 144-145.