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

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

0 引 言

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

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

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

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

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

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

1 問題描述

1.1 安全約束抽象

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

1.2 網(wǎng)絡模型

1.2.1 物理網(wǎng)絡

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

1.2.2 VNR

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

1.2.3 SVNE

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

圖1 虛擬網(wǎng)絡映射示例Fig.1 Example of virtual network embedding

1.3 評價指標

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

虛擬網(wǎng)絡請求接受率定義為

(1)

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

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

(2)

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

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

(3)

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

(4)

2 多目標優(yōu)化數(shù)學模型

2.1 目標函數(shù)

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

(5)

(6)

2.2 節(jié)點約束條件

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

(7)

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

(8)

(9)

(10)

2.3 鏈路約束條件

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

(11)

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

?ni∈Np,?est∈Ev

(12)

(13)

2.4 安全性約束條件

(14)

3 NP-SVNE算法設計

3.1 節(jié)點映射

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

(15)

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

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

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

(16)

(17)

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

(18)

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

Security(np)=

(19)

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

(20)

(21)

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

表1NP-SVNE的節(jié)點映射算法偽代碼

Table1Pseudo-codeofNP-SVNE’snodeembeddingalgorithm

3.2 鏈路映射

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

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

(22)

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

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

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

Table2Pseudo-codeofNP-SVNE’slinkembeddingalgorithm

4 實驗及結果分析

4.1 實驗環(huán)境設置

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

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

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

4.2 實驗結果分析

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

圖2 虛擬網(wǎng)絡請求接受率Fig.2 Acceptance ratio of virtual network request

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

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

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

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

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

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

由圖4可知，仿真初始階段到達的VNR數(shù)量較少,物理網(wǎng)絡的映射開銷較低。隨著仿真時間的持續(xù),到達的VNR數(shù)量逐漸增多,物理網(wǎng)絡的映射開銷也隨之增大,并在約5 000個時間單元后趨于穩(wěn)定。由于NP-SVNE算法在節(jié)點映射階段考慮了節(jié)點之間的鄰近關系和安全屬性的最優(yōu)匹配,因此其映射開銷最低,約為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增加,物理網(wǎng)絡的可用資源減少,虛擬鏈路映射的物理路徑長度增加,從而增加了映射開銷。穩(wěn)定后,NP-SVNE算法的收益開銷比最高,約為57%,分別較NR-SVNE、TA-SVNE和G-SVNE算法提高了約23.9%、50.0%和67.6%。

5 結束語

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

[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] 龔水清,陳靖,黃聰會,等. 信任感知的安全虛擬網(wǎng)絡映射算法[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.