信任感知的安全虛擬網絡映射算法

龔水清，陳靖，黃聰會，朱清超

(1.空軍工程大學 信息與導航學院，陜西 西安 710077；2. 解放軍94543部隊，山東 濟寧 272500)

1 引言

網絡虛擬化[1,2]被認為是下一代互聯網的關鍵技術。它通過資源抽象、聚合、隔離等機制允許多個異構的虛擬網絡同時運行于底層物理網絡之上，共享底層基礎設施資源。且每個虛擬網絡可部署專用的協議和應用，為用戶提供個性化的端到端網絡服務，大大提高了底層網絡資源利用率，增強了網絡的靈活性和可控可管性，有效解決了互聯網發展過程中遇到的“僵化”問題[3]，并為新興的云計算的發展提供了技術保障，推動了云計算的發展[4]。目前，下一代互聯網研究項目如 GENI等[5]已廣泛使用了網絡虛擬化技術。然而，由于在網絡架構中引入了額外的虛擬化層，網絡虛擬化技術帶來了新的安全問題，如用戶攻擊虛擬網絡，虛擬網絡之間相互攻擊以及虛擬網絡與底層網絡之間的相互攻擊等[6]。這些安全風險會破壞網絡的機密性、完整性和隔離性，阻礙網絡虛擬化的大規模應用和發展。因此，亟需新的安全機制和技術來應對網絡虛擬化環境中新的安全威脅。

虛擬網絡映射[7]作為網絡虛擬化技術研究的關鍵問題，是指為虛擬網絡中帶有約束（如資源約束）的虛擬節點和鏈路分配底層物理網絡資源的過程，已引起了學術界的廣泛關注，并進行了大量研究。由于虛擬網絡映射是 NP難問題[8]，一般不能在多項式時間內找到問題的最優解，目前大部分的研究主要以提高虛擬網絡映射效率為目標，如提高物理網絡收益[9]、降低映射成本[10,11]和能耗[12,13]、保持物理網絡負載均衡[14]等，并設計啟發式算法[9,13]或采用元啟發式算法[10,14]獲得近似最優解。這些虛擬網絡映射算法按照不同標準[15]可分為靜態[10]和動態[16,17]、集中式[11～17]和分布式[18,19]、單域[11～17]和跨域[20,21]等類別。

為了使虛擬網絡免于潛在的網絡攻擊，確保信息的安全，用戶在虛擬網絡資源分配過程中往往有特定的安全需求，即需要將虛擬網絡映射在具有一定安全級別的物理網絡資源上。例如，虛擬網絡中的節點需要映射在具有一定數據加密級別和防火墻級別的物理節點上。然而，上述虛擬網絡映射算法在映射過程中均假設網絡中的所有節點都安全、可信，未考慮實際應用環境中的安全需求。虛擬節點可能會被映射至不可信的物理節點上，且當物理節點受到攻擊時，虛擬節點也會受到影響，進而可能導致虛擬網絡服務的中斷。

為此，本文將信任概念和信任度引入到虛擬網絡資源分配中，在虛擬網絡映射過程中除了資源約束，還考慮了虛擬節點與物理節點之間的信任關系，將節點間的信任度作為安全約束，并以此為基礎，提出一種基于信任感知的安全虛擬網絡映射算法（TA-SVNE, trust-aware secure virtual network embedding algorithm），可以快速高效地為有可信需求的虛擬網絡請求分配物理資源。TA-SVNE算法借鑒社會網絡分析方法中的度中心性、接近度中心性和節點自身的資源能力，采用逼近理想排序法[22]TOPSIS(technique for order preference by similarity to an ideal solution)，對節點進行多屬性重要度排序，并在映射過程中將較為重要的虛擬節點映射至較為重要的物理節點上，同時采用“k最短路徑法”進行鏈路映射，以降低虛擬網絡映射成本，提高映射效率。TA-SVNE算法通過將虛擬節點映射至滿足其可信要求的物理節點上，保證了虛擬網絡的安全性。

2 問題描述與網絡模型

2.1 問題描述

網絡虛擬化在傳統的網絡架構上引入了虛擬化層，允許在共享的底層物理網絡之上共存多個異構的虛擬網絡，大大提高了網絡的靈活性，但同時也帶來了新的安全風險。具體來說，網絡虛擬化環境中的安全問題可以分為以下3種[23]。

1) 物理主機攻擊虛擬機。底層網絡物理主機節點負責虛擬網絡虛擬機節點的管理，并在服務等級協定（SLA, service level agreement）下為其提供資源，虛擬機上運行的服務和應用最終通過物理主機上的軟硬件實現。因此，當物理主機遭受攻擊并被惡意用戶控制時，其可以通過虛擬機管理平臺修改虛擬機的信息（如網絡協議）、發動嗅探攻擊（sniffing attack）竊聽、攔截虛擬網絡上的數據分組，且虛擬機因完全由物理主機管理，無法進行防御。

2) 虛擬機攻擊物理主機。惡意虛擬機通過利用物理主機的漏洞，逃脫虛擬化過程中的約束，進而攻擊物理主機并獲取其控制權限。此時，虛擬機可發動DoS（denial of service）攻擊，以洪泛的方式不斷向物理主機注入大量的錯誤信息和冗余信息，占據物理主機上剩余的可用資源，導致物理網絡因資源匱乏而拒絕其他虛擬網服務請求。

3) 虛擬機之間相互攻擊。在網絡虛擬化環境中，不同虛擬網絡之間邏輯上相互隔離，但由于虛擬網絡上的虛擬機節點共享相同的底層硬件資源，惡意虛擬機可通過發動跨虛擬機旁路攻擊（side channel attack）來竊取同一物理主機上其他虛擬機的信息。

目前網絡基礎設施提供商通過不同層面為虛擬網絡提供安全保障來解決上述安全問題，如通過認證和入侵檢測技術防止惡意攻擊、通過加密等安全策略防止敏感信息被竊取。但這些技術措施一方面過于復雜，安全成本過高；另一方面由于虛擬化環境中資源具有動態性、異構性、開放性、分布性等特點，因此這些疊加式的“被動防御”措施無法確保用戶信息的安全。

信任概念源于社會科學中的人際關系網絡，它被引入計算機系統，用來解決當在分布、異構、自治的大規模網絡環境下跨組織之間發生的交互、共享與協作時，實體之間信任關系的建立問題[24]。在網絡虛擬化環境中，信任可定義為在某時刻網絡資源實體（虛擬節點或物理節點）可以可靠、安全、可信賴地提供其所宣稱服務的一種信念[25]，信任度是指網絡資源實體之間的信任程度。本文通過把信任度作為虛擬網絡映射的依據，可以使虛擬網絡資源的分配和調度更好地圍繞節點的信任關系展開，有利于將虛擬節點映射到信任度高的底層物理節點之上，滿足虛擬網絡請求的可信需求，從而增強網絡虛擬化環境的安全性，并在一定程度上減少后續的安全開銷。因此，針對上述3種安全問題，在虛擬網絡映射過程中需考慮如下3種約束。

1) 虛擬機節點需映射至其信任的物理主機上。

2) 物理主機只承載其信任的虛擬機節點。

3) 只有相互信任的虛擬機節點才能映射在同一物理主機上。

節點間的信任具有主觀性、非對稱性和傳遞性等特點。信任度的評估是一個復雜的過程，它主要基于節點的直接信任度、推薦信任度、信任的衰減因素等，通過信任度的估算算法得到。通常，節點A對節點B的信任度值在0～1之間。值越大，說明節點A對節點B越信任，將虛擬節點A映射至物理節點B上的安全性也越高。在虛擬網絡映射過程中，本文將節點間的信任關系抽象為節點的信任度需求和信任度等級。一個節點的信任度等級越高，表示網絡中其他節點對其更加信任，其安全性也越高。對于虛擬節點，信任度需求表示其對物理節點和共存于同一物理節點上的其他虛擬節點的可信度要求，信任度需求越高，表示虛擬節點對周圍環境的安全性要求越高。對于物理節點，信任度需求表示其對承載的虛擬節點的可信度要求，信任度需求越高，表示其對承載的虛擬節點的安全性要求越高。

基于上述討論，得出如下3條在虛擬網絡映射過程中需滿足的基于信任度的安全約束。

1) 物理節點的信任度等級不能低于映射在其上的虛擬節點的信任度需求。

2) 虛擬節點的信任度等級不能低于其映射物理節點的信任度需求。

3) 虛擬節點的信任度需求不能高于映射在同一物理節點上其他虛擬節點的信任度等級。

2.2 網絡模型

1) 物理網絡

物理網絡使用帶權無向圖Gs=(Ns,Ls)表示，其中Ns和Ls分別表示物理節點和鏈路的集合。對于物理節點ns∈Ns，用CPU資源、節點位置和信任度表示其屬性，cpu(ns)表示節點的可用 CPU資源，loc(ns)表示節點的地理位置，用二維坐標(xs,ys)表示，trd(ns)和trl(ns)分別表示節點的信任度需求和信任度等級。對于物理鏈路ls∈Ls，帶寬表示其屬性，b(ls)表示鏈路的可用帶寬資源。記所有物理網絡的無環路徑集合為Ps，且對任p∈Ps，其可用帶寬資源b(p)為路徑上各鏈路的最小可用帶寬。

2) 虛擬網絡請求

定義t時刻到達的虛擬網絡請求為VNR(t)=(Gv,t,td)，其中td表示虛擬網絡在物理網絡上的生存時間，帶權無向圖Gv=(Nv,Lv)表示虛擬網絡拓撲，Nv和Lv分別表示虛擬節點和虛擬鏈路的集合。cpu(nv)、trd(nv)和trl(nv)分別表示虛擬節點nv∈Nv的 CPU資源需求、信任度需求和信任度等級，loc(nv)表示虛擬節點的地理位置需求，D(nv)表示虛擬節點可以被映射到距離位置需求的最遠距離。b(lv)表示虛擬鏈路lv∈Lv的帶寬資源需求。

3) 安全虛擬網絡映射

安全虛擬網絡映射問題可以描述為在滿足虛擬網絡請求的資源需求和安全需求的條件下，從Gv到Gs的子圖Gsubs的映射關系，其可以進一步分為節點映射和鏈路映射2個階段。如圖1所示為一個安全虛擬網絡映射的示例，(x,y,z)分別代表節點（物理節點或虛擬節點）的 CPU資源需求、信任度等級和信任度需求，邊上的數字代表物理鏈路的可用帶寬資源或虛擬鏈路的帶寬需求。圖1(b)描述了安全虛擬網絡映射的一個可行方案，虛擬網絡請求的節點映射方案為{a→B,b→A,c→F}，鏈路映射方案為{(a,b)→(B,A), (a,c)→(B,F)}。

圖1 虛擬網絡映射示例

2.3 映射目標

在虛擬網絡映射過程中，底層物理網絡需在成本最小的前提下，映射盡量多的虛擬網絡請求，以提高物理網絡基礎設施提供商的資源利用率和收益。因此，本文將物理網絡映射收益、映射成本和虛擬網絡請求接受率作為映射目標。

1) 物理網絡映射收益和映射成本

虛擬網絡請求VNR(t)在某時刻的映射收益定義為

式(1)表明虛擬網絡請求的映射收益為其資源需求總和，且虛擬節點的信任度需求越高，安全收益越大，映射總收益也越大。

VNR(t)在某時刻的映射成本定義為

其中，xvs∈{0,1}表示虛擬節點nv與物理節點ns之間的映射關系，若虛擬節點nv映射到物理節點ns上，則xvs=1，否則xvs=0，f uvij∈{0,1}表示虛擬鏈路luv與物理鏈路lij之間的映射關系，若虛擬鏈路luv映射到物理鏈路lij上，則f uvij=1，否則f uvij=0。式(2)表明，虛擬網絡請求的映射成本為物理網絡分配給虛擬網絡的資源總和，且物理節點的信任度等級越高，安全成本越高，映射成本也越大。

2) 虛擬網絡請求接受率

虛擬網絡請求接受率定義為在一定時間內成功映射的虛擬網絡請求數與總到達的虛擬網絡請求數目之比，如式(3)所示。

其中，VNRsuccess和VNR分別表示從t=0時刻到t=T時刻映射成功的虛擬網絡請求個數和總到達的虛擬網絡請求的個數。式(3)表明，虛擬網絡請求接受率越高，在一定時間內映射成功的虛擬網絡請求個數越多，總映射收益也越高。

3 安全虛擬網絡映射問題的數學模型

本節以最小化虛擬網絡映射成本為目標，以滿足虛擬網絡請求的資源和安全需求為約束，將虛擬網絡映射問題建模為混合整數線性規劃模型（MILP, mixed integer linear program），具體過程如下。

目標函數

式(5)為節點的 CPU資源約束，表示虛擬節點的CPU資源需求不能大于物理節點的可用CPU資源，式(6)表示節點映射的位置約束，dis(loc(ni),loc(nj))表示虛擬節點ni和底層節點nj之間的歐式距離，式(7)和式(8)分別為鏈路的帶寬資源約束和連通性約束，式(9)表示基于節點信任度的3種安全約束，Ω(nj)表示物理節點nj上已承載的虛擬節點集合，式(10)確保同一虛擬網絡內的不同節點不能映射在相同的物理節點上，式(11)確保一個虛擬節點只能映射在一個物理節點上，式(12)和式(13)為變量域約束。

4 基于TOPSIS的多屬性節點重要性排序方法

目前，大部分虛擬網絡映射算法的節點重要性排序方法主要以節點的資源能力為標準，即主要考慮節點自身的可用 CPU資源需求和其鄰接鏈路可用帶寬資源需求或同時以這2種因素作為評價標準[7～9]。這類方法主要存在 2個問題：一是由于在節點重要性排序時未考慮其拓撲屬性，可能導致邏輯上相鄰的2個虛擬節點被映射至相距較遠的底層物理節點上，從而使后續鏈路的映射更加困難，且造成鏈路資源的浪費；二是這類方法僅以節點自身資源和鄰接鏈路資源為排序標準，只考慮了節點的局部重要性，而未考慮節點的全局重要性，不能全面衡量節點的重要程度。

社會網絡分析方法的主要思想是“節點的重要性等價于顯著性”。在社會網絡評價方法中，節點的重要性一般用其中心性指標來衡量，一個節點越接近網絡的中心，其越重要。常用的網絡中心性指標有度、接近度、介數、特征向量等，這些指標從不同角度刻畫了單個節點在網絡中的重要程度[26]。本文借鑒社會網絡節點中心度的定義，用來反映節點在物理網絡和虛擬網絡中的重要程度。

4.1 節點重要性分析

由于節點中心性指標的定義不同，節點重要性的評價結果也不同，本文針對虛擬網絡映射問題，對所使用的幾個節點中心性指標重新定義，并將節點的資源能力也作為節點的重要性評價指標。

定義1（度中心性）。與節點相連的所有鄰接鏈路的帶寬之和，如式(14)所示。

其中，L(ni)表示節點ni的鄰接鏈路集合，若ni為虛擬節點，則b(l)表示虛擬鏈路l的帶寬需求；若ni為物理節點，則b(l)表示物理鏈路l的可用帶寬。節點的度中心性反映了其局部重要性，度中心性越大，節點與其他節點的直接通信能力越強，在網絡中位置越重要。

定義2（接近度中心性）。節點ni到網絡中其他節點的距離之和的倒數，如式(15)所示。

其中，dij表示節點ni與nj之間的最短路徑的跳數，且當i=j時，dij=0。若ni為虛擬節點，則ψ(n)=Nv。若ni為物理節點，則ψ(n)表示已映射物理節點的集合，且當進行初始映射時，由于ψ(n)為空，此時令ψ(n)=Ns。節點的接近度中心性反映了其全局重要性。若ni為虛擬節點，則接近度中心性越大，節點就越接近虛擬網絡的中心位置，節點就越重要；若ni為物理節點，則接近度中心性越大，節點到已映射物理節點的距離越小，應越優先被選作映射物理節點，因為其使虛擬節點映射在相對集中的區域，縮短后續鏈路映射的距離，節省帶寬資源，降低虛擬網絡映射成本，所以節點也越重要。

定義3（資源能力）用節點的CPU資源表示，如式(16)所示。

其中，若ni為虛擬節點，則cpu(ni)表示節點的CPU資源需求；若ni為物理節點，則cpu(ni)表示節點的可用 CPU資源。節點的資源能力是其自身的能力因子。對于虛擬節點ni，節點的資源能力值越大，其映射就越困難，很可能因物理節點資源不足而導致映射失敗，因此這樣的節點更加重要，需優先進行映射；對于物理節點ni，節點的資源能力值越大，可用資源越多，可提高虛擬網絡映射成功率，節點也更加重要。

4.2 MNRTOP方法

上述3個節點重要性指標分別從局部或全局角度分析了節點在網絡中的重要程度，但在實際網絡中，僅依靠某個指標來判斷節點在網絡中的重要度較為片面。為此，本節綜合這些指標，提出一種基于TOPSIS的多屬性節點重要性排序方法(MNRTOP,multi-factor node ranking based on TOPSIS)。

TOPSIS是一種多屬性決策方法，它根據有限個評價對象的多個屬性與理想目標的接近程度進行排序。本文將虛擬網絡或物理網絡中的每一個節點作為一個方案，將節點重要性的多個評價指標看作各方案的屬性，那么節點重要性的評價就轉化為一個多屬性決策問題[26]。

MNRTOP共分為6個步驟。

步驟1考慮網絡中有N個節點，每個節點有M個重要性評價指標，記第i個節點的第j個評價指標值為xij，則重要性決策矩陣為

5 TA-SVNE算法設計

由于安全虛擬網絡映射的 MILP模型是 NP難問題，本節設計了 TA-SVNE啟發式算法對此問題進行求解。TA-SVNE算法分為基于MNRTOP的節點映射和基于k最短路徑法的鏈路映射2個階段。

5.1 節點映射

本文選用節點的度中心性、接近度中心性和資源能力作為其重要性評價屬性，采用 MNRTOP方法對虛擬網絡和物理網絡中的節點進行重要度排序，并基于此排序結果進行節點映射，使較為重要的虛擬節點能夠映射到物理網絡中較為重要的物理節點上。節點映射算法的主流程如算法1所示。

算法1TA-SVNE的節點映射

輸入：Gs,VNR(t)

輸出NodeMappingList

由式(2)可知，若物理節點的信任度等級越高，則映射成本越高。因此，在節點映射過程中，在滿足資源需求和安全需求的前提下，虛擬節點應映射至信任度等級較低的物理節點上，以降低安全成本。為此，對物理節點的資源能力做如下改進。

對于nv∈Nv，首先按照CPU資源約束式(5)、節點位置約束式(6)和安全約束式(9)選出其候選物理映射節點集合Θ(nv)。對于ns∈Θ(nv)，其資源能力定義如下

式(25)表明，若虛擬節點的信任度需求與候選物理映射節點的信任度等級差距越小，則該候選物理節點的資源能力越強，若將虛擬節點映射至此節點上，可降低映射安全成本。因此，該節點更加重要，應優先被選為映射物理節點。

5.2 鏈路映射

鏈路映射是指在滿足帶寬資源約束的條件下，將虛擬鏈路映射到物理網絡中的無環路徑上。由于不同虛擬鏈路映射至物理網絡中的不同路徑之間可能存在相同鏈路，這些路徑會同時競爭物理鏈路有限的帶寬資源，使帶寬資源需求高的虛擬鏈路映射更加困難，很可能由于物理網絡鏈路帶寬資源不足而導致映射失敗。因此，在鏈路映射階段，應優先選擇帶寬資源需求高的虛擬鏈路進行映射。在此基礎上，采用k最短路徑方法[27]，在物理網絡中尋找滿足帶寬需求的2個被映射虛擬節點之間的第k短路徑，并將虛擬鏈路映射至此路徑上。算法2為鏈路映射算法的主流程。

算法2TA-SVNE的鏈路映射

輸入：Gs,VNR(t),NodeMappingList

輸出：LinkMappingList

6 性能評估與分析

為了驗證算法的有效性，本節對TA-SVNE算法和之前研究中提出的算法進行對比仿真實驗，并從虛擬網絡請求接受率、物理網絡映射收益、映射成本、收益成本比和運行時間等方面討論TA-SVNE算法的性能。

6.1 仿真環境

實驗中物理網絡和虛擬網絡請求均使用GT-ITM拓撲生成器產生。物理網絡包含100個節點，節點間的鏈路連接概率為 0.5，相當于一個中等ISP的規模。物理節點的CPU資源和物理鏈路的帶寬資源均服從[50,100]的均勻分布，其位置x與y坐標均服從[0,100]的均勻分布。虛擬網絡請求隨機生成，其到達過程服從時間單元為 100，到達個數期望為5的泊松分布。每個虛擬網絡請求的生存時間服從期望為1 000個時間單元的指數分布，虛擬節點的數目服從[2,10]的均勻分布，節點間的連接概率為0.5。每個虛擬節點的CPU資源需求和鏈路帶寬資源需求均服從[0,50]的均勻分布，其位置x與y坐標均服從[0,50]的均勻分布，且假設所有虛擬節點的位置距離約束量D取常量50。此外，虛擬節點和物理節點的信任度需求和信任度等級均服從[0,1]的均勻分布，k最短路徑算法中的k設置為5，式(19)中3種節點重要性評價指標的權重均設置為整個仿真運行時間設定為50 000個時間單位，總共包含2 500個虛擬網絡請求，這樣能使實驗的運行進入比較穩定的狀態。由于虛擬網絡請求隨機生成，為避免隨機因素對實驗結果產生擾動，仿真實驗共進行 10次，并取實驗結果的平均值作為最終仿真結果。

本文進行了 4種算法的比較。TA-SVNE算法和 NTA-SVNE算法為本文提出的算法。TA-SVNE算法的物理節點資源能力重要度評價屬性采用式(25)計算。NTA-SVNE算法采用式(16)計算物理節點資源能力重要度評價屬性，節點映射過程中未考慮安全成本因素，以此測試TA-SVNE算法能否有效降低映射成本。BL1算法是基于D-ViNE映射算法[11]，并在節點映射過程中加入了安全約束式(9)，映射收益和成本依據式(1)和式(2)進行了相應修改。BL2[8]算法在節點映射階段采用貪婪策略，在節點排序時僅考慮自身 CPU資源和其鄰接鏈路帶寬資源，鏈路映射采用k最短路徑法。同時為便于比較，在節點映射時新增了安全約束。

6.2 仿真結果分析

本節以虛擬網絡請求接受率、物理網絡映射收益、映射成本、收益成本比和運行時間作為算法的性能評價指標，對TA-SVNE、NTA-SVNE、BL1和BL2算法進行性能分析。圖2～圖6和表1分別表示4種算法在上述5個性能評價指標下的實驗結果。

圖2 虛擬網絡請求接受率

圖3 物理網絡映射收益

圖4 物理網絡映射成本

圖5 物理網絡映射收益成本比

圖6 虛擬網絡請求接受率隨信任度需求和等級增大的變化

1) 虛擬網絡請求接受率

圖2為4種算法的虛擬網絡請求接受率隨時間的變化情況。從圖2中可以看出，由于初始時段物理網絡可用資源較為豐富，4種算法的虛擬網絡請求接受率都較高。隨著資源的逐步消耗，接受率逐漸下降，在7 500個時間單位后，接受率趨于穩定。TA-SVNE和NTA-SVNE算法的虛擬網絡請求接受率比較接近，分別穩定在83%和81%左右，比BL1算法（約70%）和BL2（約65%）提高了11%～18%。主要原因在于TA-SVNE和NTA-SVNE算法在節點映射過程中考慮了節點的局部和全局重要性，將虛擬節點集中映射到 CPU資源和鄰接鏈路帶寬資源較為豐富的底層物理節點上，使后續鏈路映射更容易成功，并縮短了鏈路映射距離，降低了映射成本，使物理網絡有更多的資源接受新的虛網請求，從而提高了虛網請求接受率。而在 BL1和BL2算法映射過程中未考慮節點拓撲屬性，使節點映射和鏈路映射的協調性較差，降低了虛擬網絡映射的成功率。

2) 物理網絡映射收益、成本和收益成本比

圖3為4種算法的物理網絡映射收益隨時間的變化情況，由圖3可知TA-SVNE和NTA-SVNE算法的映射收益比較接近，比算法BL1和BL2高出約19%～41%。圖4為4種算法的物理網絡映射成本隨時間的變化情況，由圖4可知NTA-SVNE算法的映射成本最高，TA-SVNE算法明顯降低了映射成本（約9%），BL2算法最低。圖5為4種算法的物理網絡映射收益成本比隨時間的變化情況，由圖5可知TA-SVNE算法的收益成本比最高（約85%），比算法 NTA-SVNE（約 75%）、BL1（約 73%）和BL2（約69%）高出10%～16%，可見TA-SVNE算法的映射效率最高。主要原因是在TA-SVNE算法的節點映射過程中，在滿足安全約束的前提下將虛擬節點優先映射在信任度等級較低的物理節點上，從而降低了映射安全成本，同時考慮了節點的全局拓撲屬性，使節點映射的區域較為集中，降低了后續鏈路映射的成本，提高了虛網請求接受率，使在相同時間內映射成功的虛擬網絡請求比其他 2種算法多，進而映射收益較高。而NTA-SVNE算法在節點映射過程中未考慮安全成本因素，使整體映射成本較高。BL1和BL2算法的虛擬網絡請求接受率較低，因而映射收益和成本較其他2個算法低，但由于這2種算法在節點映射過程中未考慮安全成本因素，且節點映射和鏈路映射的協調性較差，使鏈路映射成本較高，因此其映射收益成本比較低。

3) 運行時間

表1為4種算法虛擬網絡請求的平均映射求解時間。從表1可看出，與BL1相比，TA-SVNE、NTA-SVNE和 BL2的虛擬網絡映射所需時間降低了約40%～48%。主要原因是TA-SVNE、NTA-SVNE和 BL2采用啟發式算法求解，時間復雜度小，而BL1算法采用松弛技術求解虛擬網絡映射的MILP模型，時間復雜度高，且隨問題規模的增長而呈指數增加。

表1 算法運行時間

4) 不同類型虛擬網對虛擬網絡請求接受率的影響

上述研究側重在橫向上比較不同算法之間的性能指標，而未考慮不同類型的虛擬網請求對算法性能的影響。在實際中，不同類型虛擬網絡請求的安全需求存在很大的不同。有的網絡對安全性要求很高，如軍事網絡、電子商務、網上銀行等，而有的網絡對安全性要求較低。因此，本文研究了在不同信任度需求的虛擬網絡請求下4種算法的映射成功率的變化，以考察算法的執行效率。在實驗中，將虛擬網絡中節點的信任度需求和信任度等級均設置在[x,1]的均勻分布，x為虛擬節點的信任度需求和等級分布區間的下界，即圖6中的x坐標變量。隨著x的增大，虛擬網絡請求的安全需求逐漸增大。實驗中其他仿真環境參數保持不變。由圖6可知，隨著虛擬網絡節點的信任度需求和信任度等級逐漸增大，4種算法的虛擬網絡請求接受率都逐漸降低，且當x≥0.3時，接受率的下降速度明顯加快，但 TA-SVNE算法的映射接受率下降速度最慢，NTA-SVNE次之，BL1和BL2算法下降速度最快。這說明 TA-SVNE算法的執行效率較高，且當0.3≤x≤0.6時，TA-SVNE算法的優勢更為明顯。

7 結束語

網絡虛擬網技術由于在網絡架構中引入了虛擬化層，帶來了新的安全威脅。本文針對這一問題，將信任概念和信任度引入到虛擬網絡映射中，量化分析了虛擬網絡的安全問題，并以此為基礎，構建了安全虛擬網絡映射的 MILP模型，提出了TA-SVNE映射算法。為了提高映射效率，TA-SVNE算法在節點映射過程中借鑒社會網絡中心度理論，以度中心性、接近度中心性以及資源能力作為節點的重要度屬性，采用TOPSIS方法對節點進行多屬性重要度排序，并在映射過程中將重要的虛擬節點映射在較為重要的物理節點上，同時采用k最短路徑法進行鏈路映射。仿真結果表明，TA-SVNE算法在虛擬網絡請求接受率、映射收益和運行時間等方面具有一定優勢，并具備較高的映射效率。但該算法只考慮了節點間的信任關系，不足以應對網絡虛擬化環境中的多種安全威脅。下一步需在細粒度研究網絡虛擬化環境中安全問題的基礎上，擴展算法以考慮虛擬網絡映射過程中更多的安全約束條件。

[1] KHAN A, ZUGENMAIER A, JURCA D,et al. Network virtualization:a hypervisor for the Internet?[J]. IEEE Communications Magazine,2012, 50(1): 136-143.

[2] WANG A, IYER M, DUTTA R,et al. Network virtualization: technologies, perspectives, and frontiers[J]. Journal of Lightwave Technology, 2013, 31(4): 523-537.

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

[4] BARI M, BOUTABA R, ESTEVES R,et al. Data center network virtualization: a survey [J]. IEEE Communications Surveys and Tutorials, 2013, 15(2): 909-928.

[5] BERMAN M, CHASE J S, LANDWEBER L,et al. GENI: a federated testbed for innovative network experiments[J]. Computer Networks,2014, 61: 5-23.

[6] NATARAJAN S, WOLF T. Security issues in network virtualization for the future Internet[A]. Proceedings of the IEEE ICNC[C]. Maui,HI, 2012: 537-543.

[7] FISCHER A, BOTERO J F, BECK M T,et al. Virtual network embedding: a survey[J]. IEEE Communications Surveys & Tutorials, 2013,15(4): 1888-1906.

[8] YU M L, YI Y, REXFORD J,et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[9] HSU W H, SHIEH Y P. Virtual network mapping algorithm in the cloud infrastructure[J]. Journal of Network and Computer Applications,2013, 36(6): 1724-1734.

[10] FAJJARI I, AITSAADI N, PIóRO M,et al. A new virtual network static embedding strategy within the Cloud’s private backbone network[J]. Computer Networks, 2014, 62: 69-88.

[11] CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping[A]. Proceedings of the IEEE INFOCOM[C]. Rio de Janeiro, 2009. 783-791.

[12] SU S, ZHANG Z, LIU A X,et al. Energy-aware virtual network embedding[J]. IEEE/ACM Transactions on Networking, 2014, 22(5):1607-1620.

[13] BOTERO J F, HESSELBACH X. Greener networking in a network virtualization environment[J]. Computer Networks, 2013, 57(9):2021-2039.

[14] 黃彬彬, 林榮恒, 彭凱, 等. 基于粒子群優化的負載均衡的虛擬網絡映射[J]. 電子與信息學報, 2013, 35(7): 1753-1759.HUANG B B, LIN R H, PENG K,et al. Load-balancing based on particle swarm optimization in virtual network mapping[J]. Journal of Electronics & Information Technology, 2013, 35(7): 1753-1759.

[15] 程祥, 張忠寶, 蘇森, 等. 虛擬網絡映射問題研究綜述[J]. 通信學報, 2011, 32(10): 143-151.CHENG X, ZHANG Z B, SU S,et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10):143-151.

[16] 羅娟, 徐岳陽, 李仁發. 網絡虛擬化中動態資源分配算法研究[J].通信學報, 2011, 32(7): 64-70.LUO J, XU Y Y, LI R F. Dynamical resource allocation algorithm research in network virtualization[J]. Journal on Communications, 2011,32(7): 64-70.

[17] SUN G, YU H, ANAND V,et al. A cost efficient framework and algorithm for embedding dynamic virtual network requests[J]. Future Generation Computer Systems, 2013, 29(5): 1265-1277.

[18] HOUIDI I, LOUATI W, ZEGHLACHE D,et al. Adaptive virtual network provisioning[A]. Proceedings of the second ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures[C].New York, 2010. 41-48.

[19] 江逸茗, 蘭巨龍, 程東年, 等. 分布式環境中基于協商的虛擬網映射算法[J]. 通信學報, 2014, 35(12): 62-69.JIANG Y M, LAN J L, CHENG D N,et al. Virtual network embedding algorithm based on negotiation in distributed environment[J].Journal on Communications, 2014, 35(12): 62-69.

[20] HOUIDI I, LOUATI W, AMEUR W B,et al. Virtual network provisioning across multiple substrate networks[J]. Computer Networks,2011, 55(4): 1011-1023.

[21] SHEN M, XU K, YANG K,et al. Towards efficient virtual network embedding across multiple network domains[A]. Proceedings of the IEEE IWQoS[C]. Hong Kong, 2014. 61-70.

[22] LAI Y J, LIU T Y, HWANG C L. Topsis for MODM[J]. European Journal of Operational Research, 1994, 76(3): 486-500.

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

[24] 王勇, 代桂平, 侯亞榮. 信任感知的組合服務動態選擇方法[J]. 計算機學報, 2009, 32(8): 1668-1675.WANG Y, DAI G P, HOU Y R. Dynamic methods of trust-aware composite service selection[J]. Chinese Journal of Computer, 32(8): 1668-1675.

[25] 曹潔, 曾國蓀, 姜火文, 等. 云環境下服務信任感知的可信動態級調度方法[J]. 通信學報, 2014, 35(11): 39-49.CAO J, ZENG G S, JIANG H W,et al. Trust-aware dynamic level scheduling algorithm in cloud environment[J]. Journal on Communications, 2014, 35(11): 39-49.