具有高可靠特征的無線虛擬網絡映射方法研究

高航航，趙尚弘，王 翔，彭 聰

空軍工程大學 信息與導航學院，西安710077

1 引言

網絡虛擬化[1-2]被認為是未來網絡中的一項關鍵技術，是一種應對當前互聯網僵化問題的重要方法，其有效地增強了網絡的靈活性，可以使不同的虛擬網絡請求（Virtual Network Request，VNR）共存于同一個底層物理網絡中，共享底層物理網絡資源，并且這些虛擬網絡請求之間相互隔離，在安全性方面也有一定的保證。網絡虛擬化改變了傳統的網絡服務與資源緊密耦合的特性，實現了網絡服務與資源靈活且有效的利用。虛擬網絡映射[3-5]作為網絡虛擬化當中的一項關鍵技術，是指將底層物理網絡資源分配給虛擬網絡中帶有約束條件的虛擬節點以及虛擬鏈路的過程，目前已被證明是NP難問題[6-7]。虛擬網絡映射目前主要面臨著資源約束、準入控制、在線請求和拓撲多樣等問題[8]，且由于VNR的到達時間、持續時間和服務需求不可預知，當底層網絡拓撲較大時，采用傳統方法求解將會產生龐大的搜索空間，難以在有限時間內滿足VNR的各種需求。

傳統虛擬網絡映射算法將節點映射階段與鏈路映射階段完全分離，忽略了鏈路映射結果對物理節點排序的影響，導致高映射成本和虛擬節點在底層物理網絡上的分布式分布，針對這些問題，文獻[9]提出了一種基于節點屬性和網絡單純形的雙層虛擬網絡映射算法Simplex-VNM，在節點映射層中采用一種考慮拓撲屬性、全局網絡資源和映射物理節點信息的新節點排序方法以此為鏈路映射層提供候選節點和節點映射成本，在鏈路映射階段中，通過引入與傳統最短路徑算法相比具有較小時間復雜度的網絡單純形算法，以在節點映射層的結果下找到最優鏈路映射解決方案，最后根據兩層結果以最小的總映射成本映射虛擬節點和相關鏈路，仿真表明本文算法在考慮節點屬性和使用最短路徑算法下的總映射成本和映射時間性能方面優于其他四種算法；當前大多數虛擬網絡映射算法主要面向底層網絡無故障環境下如何以提高網絡資源利用率、Vn請求接受率等指標，如文獻[10]在馬爾科夫隨機模型中采用K分解技術將VNR分割為核心網絡和邊緣網絡，并提出一種ViNEYard算法，算法通過協調節點映射和鏈路映射兩個過程并優先映射生存時間短的VNR，結果表明所提算法有效地提高了Vn接受率和網絡收益；針對物理節點負載不均衡問題，文獻[11]采用一種基于最小節點負載優先的映射算法進行求解，算法通過計算底層網絡中各節點的負載強度，得到具有剩余資源大和負載小的物理節點作為承載節點進行映射，并采用k最短路徑法完成鏈路映射，結果表明文中算法在資源利用率、鏈路均衡度方面均得到有效提升；文獻[12]為解決底層網絡在映射中所存在的能耗過高問題，提出一種基于鏈路可分割的鏈路休眠算法，在網絡低負載階段中由于部分鏈路資源不能得到充分利用，從而將低資源利用率的虛擬鏈路重映射到高資源利用率的鏈路上，并將資源利用率低的鏈路進行休眠操作，結果表明該算法在提升鏈路資源利用率的同時也增大了Vn映射成功率，但也帶來了通信延遲等問題；文獻[13]主要討論了分布式和混合云環境中的網絡資源映射問題，為解決數千個節點的大型虛擬和物理網絡的復雜性和可擴展性，文中提出了一種依靠拓撲模式和二分匹配的高效啟發式改進算法以獲得最優映射方案，通過將虛擬資源分離到不同的物理節點并在相同的物理節點中同定位，最終算法采用虛擬分解技術和物理模式圖的二分匹配法以在線性時間內解決該虛擬映射問題；在動態網絡拓撲中，由于節點的移動性導致無線鏈路易發生中斷，造成映射在該鏈路上的Vn失效，使得相應的網絡服務無法完成，此外，底層節點發生故障也會造成Vn失效，文獻[14]針對底層網絡單節點失效問題提出一種拓撲感知的節點映射策略和一種基于禁忌搜索算法的鏈路映射策略，仿真表明虛擬請求失效時所提算法在獲得較高映射成功率的同時也能達到較高的網絡收益和資源利用率；文獻[15]針對底層多節點故障問題提出一種基于拓撲感知的虛擬映射方法，文中首先在Vn到來之前為底層節點構建候選集，當Vn到來時利用可恢復性的映射策略對Vn的主要資源進行分配，將重要度較大的虛擬節點映射到可恢復性較好的物理節點上，當物理節點發生故障時采用利益驅動的重映射算法對受影響的Vn進行恢復；文獻[16]針對無線鏈路可靠性差提出一種基于鏈路可靠性的虛擬網絡分配算法，算法允許同一虛擬請求中不同節點映射到同一物理節點，并利用Q因子對稀疏拓撲分配時Vn映射成功率低進行改進，仿真表明該算法可獲得較高的Vn構建成功率和資源利用率；文獻[17]針對底層鏈路故障問題分別提出鏈路恢復和路徑恢復兩種方法，文中采用一種混合策略的啟發式算法用來解決可生存性虛擬網絡映射問題，算法預先計算每條物理鏈路的備份繞道路徑，并對到達的Vn執行節點映射和鏈路映射操作，當底層網絡出現故障時，直接在備份繞道路徑中為失效的鏈路重新路由，仿真表明該算法在Vn接受率、網絡收益和算法復雜度等方面要優于一般算法；針對可生存性的虛擬網絡映射問題，文獻[18]在文中將網絡鏈路資源分為主要流量資源和次要流量資源以滿足資源保護要求，并引入了全局資源容量這一指標，該指標可用于測量節點映射容量以改善網絡的負載平衡，最后提出一種基于全局資源容量的啟發式生存虛擬網絡映射算法GRC-SVNE，算法在節點映射階段通過計算所有節點的映射容量，并選擇部分節點作為虛擬網絡映射的候選節點以提高映射成功率，之后使用Dijkstra算法進行鏈路映射，結果表明文中算法與傳統GREEDY、R-ViNE和D-ViNE算法相比不僅實現了虛擬網絡的可生存性，在網絡負載均衡和收益方面也獲得了較優解；文獻[19]在計算容量約束和網絡容量約束下針對單個云請求的可生存性映射問題提出一種VSMF啟發式算法，文中算法共分為兩個階段，在第一階段中將虛擬網絡劃分為一組星類，每個星類都使用一個虛擬節點作為中心，第二階段中通過允許一個虛擬節點映射一個或多個物理節點以放寬虛擬節點映射約束，使得共享相同虛擬節點的虛擬鏈路可共享相同的物理節點，結果表明所提VSMF算法在小規模網絡和大規模網絡中均可獲得比傳統算法更低的成本和阻塞概率；文獻[20]針對無線網絡移動性提出一種近似算法BIRD-VNE，由于底層節點的移動性導致節點間的連接關系發生改變，使得已經被虛擬鏈路使用的物理路徑資源不足或發生故障，文中算法可以有效捕獲到節點移動和拓撲變化，并能夠減小由于底層節點的移動性所導致的Vn重映射所產生的開銷，結果表明該算法在獲得最佳虛擬映射收益的同時能夠減少由于節點移動所造成的Vn遷移個數，有效地減小了網絡拓撲移動性對虛擬網絡遷移的影響。

上述研究內容主要針對底層節點或鏈路發生故障時VNR的可生存性映射問題，主要以虛擬節點或虛擬鏈路重映射為主，而未考慮底層網絡中節點資源與鏈路資源間的關系。本文分別在節點映射和鏈路映射階段引入節點擴展資源和物理鏈路代價這一概念，建立一種高可靠性的虛擬網絡映射方案，并針對網絡故障設計一種可恢復的重映射方案，結果表明所提算法能夠獲得較優結果，其性能要優于一般算法。

2 模型分析

2.1 網絡模型描述

用加權無向圖GS=(NS,ES)表示底層物理網絡拓撲，其中ns∈NS表示物理節點，其屬性包括節點計算能力cpu(ns)、節點位置信息loc(ns)；ls∈ES表示物理鏈路，其屬性包括帶寬資源b(ls)，用P表示底層物理網絡無環路徑集合，對于路徑ps∈PS，其可用帶寬資源b(ps)大小由該路徑所經過的各鏈路最小帶寬資源所決定。底層物理網絡承載多個虛擬請求，在一段時間內，新虛擬請求到達的同時也存在某虛擬請求完成釋放物理網絡資源，故底層物理網絡中的資源是動態變化的，其數學表達式如下：

其中，式（1）表示物理節點資源能力，式（2）和式（3）分別表示物理鏈路帶寬和物理路徑帶寬能力，且路徑帶寬能力由該路徑所經過各鏈路的最小帶寬能力所決定。

用加權無向圖GV=(NV,EV,T)表示虛擬網絡請求VNR，其中nv∈NV為虛擬網絡節點，其屬性包括節點計算能力需求cpu(nv)、位置需求loc(nv)；lv∈EV為虛擬網絡鏈路，其屬性包括帶寬需求b(lv),T表示該虛擬網絡請求的生存時間。

2.2 虛擬映射約束條件

將節點間映射關系用矩陣FN表示，其中行向量表示虛擬節點，列向量表示物理節點，當虛擬節點i映射到物理節點m，即,FN(i,m)=1，否則為0，節點資源約束條件如下：

其中，式（4）表示物理節點資源能力大于VNR節點資源請求能力；式（5）表示同一個虛擬請求中的不同節點不能被映射到同一個物理節點上；式（6）表示若一個虛擬節點屬于不同虛擬網絡請求，則該節點只能被映射到同一物理節點上。

與節點映射矩陣類似，鏈路間的映射關系用矩陣FL表示，其中行向量代表虛擬鏈路，列向量代表物理鏈路，當虛擬節點i和j分別映射到物理節點m和n上，(i,j)間的鏈路映射到(m,n)間的路徑時，即,FL(ij,mn)=1，否則為0。此外，虛擬鏈路映射的所有物理鏈路組成了物理節點m,n之間的一條無環路徑p(m,n)，鏈路資源約束條件如下：

其中，式（7）表示物理路徑可用資源大小為該路徑所經過的物理鏈路中最小可用資源值；式（8）表示虛擬鏈路資源需求小于物理路徑所提供的可用帶寬資源。在考慮鏈路資源約束的同時也需要考慮鏈路的連通性約束，如式（9）所示：

若某物理鏈路包含虛擬鏈路的源節點，式（9）值為1時表示源節點流出流量為1、流入流量為0；若某物理鏈路包含虛擬鏈路的目的節點，式（9）值為-1時表示目的節點流出流量為0、流入流量為1；若某物理鏈路不包含虛擬鏈路的源節點和目的節點，則流入流量和流出流量平衡，且均為0。

2.3 物理節點故障分析

當某虛擬網絡請求VNR到達后，底層物理網絡判斷是否接受該VNR，若當前條件不允許，則拒絕該VNR，不提供物理資源進行映射；若當前條件允許接受，則物理網絡要從自身中選擇滿足虛擬網絡需求的物理節點和鏈路，映射問題定義為F:(GV→GS*,GS*?GS)，包括節點映射和鏈路映射兩方面。在節點映射中通常優先選擇可用資源較多的物理節點作為映射節點，但與該節點相連的物理鏈路資源不一定滿足虛擬鏈路映射所需求的資源，如圖（1）所示，圖1（a）中虛擬網絡請求包含兩個虛擬節點和一條虛擬鏈路，圖中數字表示節點和鏈路資源需求，圖1（b）所示為物理網絡，圖中數字為節點和鏈路可提供資源。一種節點映射方案為{a→C,b→A}，但此時物理鏈路(A,C)間帶寬資源不足以提供給虛擬鏈路(a,b)，導致該虛擬鏈路(a,b)推遲映射，當其余虛擬請求完成后，其占用的物理鏈路資源將被釋放掉，釋放的資源再用于對該鏈路進行映射。

圖1 鏈路映射請求推遲

在鏈路映射中，每條物理鏈路的帶寬資源可以被多個虛擬鏈路所共享，因而會存在多條虛擬鏈路被映射到同一條物理鏈路這種情況。假如此時某個物理節點發生故障，則會導致與該物理節點相連的周邊物理鏈路失效，使得這些物理鏈路所承載的虛擬鏈路隨之失效，進而導致該虛擬網絡不再連通。如圖2所示為一種虛擬網絡映射案例，圖2（a）表示某虛擬網絡請求VNR，圖2（b）代表一種虛擬網絡映射方案，其中節點映射方案為{a→A,b→D,c→C},鏈路映射方案為{(a,b)→(A,D),(b,c)→(D,C),(a,c)→(A,D,C)}，假如當物理節點D失效，則導致與其相連的物理鏈路(A,D),(D,C)均失效，進而使得映射在其上的虛擬鏈路(a,b),(a,c),(b,c)全部失效，造成虛擬網絡失去連通性；若使用圖2（c）所示的映射方案，將虛擬鏈路(a,c)映射到(A,B,E,C)，當物理節點D失效時，虛擬網絡中a,c之間仍保持連通；如果采用圖2（d）所示的映射方案將虛擬鏈路(a,c)映射到(A,E,C)，相比較方案2而言，虛擬網絡中a,c之間在保持連通的基礎上占用了較小的開銷，該方案可以取得較理想的結果。

圖2 虛擬網絡映射案例

2.4 節點與鏈路指標分析

（1）物理節點擴展資源

在虛擬網絡節點映射過程中通常優先選擇可用資源較多的物理節點作為承載節點，再進行鏈路映射，然而這種節點映射和鏈路映射相互獨立的方法，會出現與已映射節點相連的物理鏈路剩余資源小于虛擬鏈路請求資源的情況，進而造成某鏈路映射推遲甚至無法完成鏈路映射。針對這一問題，文中引入物理節點擴展資源，如式（10）所示：

其中，μ1和μ2為常數，表示節點和鏈路資源的重要度，ES⊕ns表示與節點ns相連的鏈路集。在映射節點時，選擇物理節點擴展資源較大的節點能夠很大程度上避免當虛擬節點映射成功后，由于與映射節點相連的物理鏈路資源不足而導致的鏈路映射請求被推遲問題。

（2）物理鏈路代價L(ls)

在無線網絡中鏈路存在頻繁失效，故需要重點考慮鏈路中斷這一因素，文中綜合考慮鏈路中斷概率、鏈路剩余帶寬和鏈路重要度，并定義如下物理鏈路代價：

式（11）中bmax(ls)為剩余鏈路中最大帶寬，pmin(ls)為剩余鏈路最小中斷概率，δ(ls)為鏈路ls重要度，λ1和λ2為系數。式（12）中定義為鏈路標識符，表示鏈路ls是否在已映射的物理路徑h中，若在則為1，否則為0。在映射路徑時，要選擇那些代價小的物理鏈路構成物理路徑，能夠最大程度上保證該路徑性能最佳。

（3）候選節點集合Ran(ms)

物理節點ms發生故障后，映射在其上的虛擬節點隨之失效，為保證虛擬請求的正常工作，需要對失效的虛擬節點重新映射。在重映射階段，對故障節點ms構建候選節點集合可以有效地減少映射時間，進而使虛擬請求得到及時響應，候選節點集合如式（13）所示，表示與節點ms間距離不超過δ跳的物理節點集合：（

4）節點備用系數Alter(ns)

虛擬節點重映射時，候選節點集合Ran(ms)中往往存在多個節點，而發生故障次數多、承載較多虛擬節點的物理節點很有可能再次發生故障，為避免重映射后的節點發生故障，文中使用節點備用系數Alter(ns)作為選取重映射節點的依據，其表達式如下所示：

式中，numfa(ns)表示節點發生故障次數，numem(ns)表示映射在該節點上的虛擬節點個數，ω1和ω2分別為二者的比例系數。在節點重映射時，應當選擇那些故障次數少、承載較少虛擬節點的備用節點進行映射。在實際映射過程中，由于節點故障次數和承載節點個數二者在映射過程中均會存在，且對于節點選擇的影響均不可忽略，其重要性程度相差較小。

2.5 評價指標

（1）虛網請求接受率

在虛擬網絡請求VNR到來時，底層網絡將為其提供物理網絡資源以供映射，同時也存在某節點或鏈路資源受限使得VNR推遲映射或映射失敗問題，文中用虛網請求接受率ξacc衡量VNR成功映射的情況，其表達式如下：

其中，VNRarr表示在一定時間內到達的VNR個數，VNRacc表示成功映射的VNR個數，T表示VNR的生存時間。

（2）虛擬網絡恢復成功率

當底層網絡節點發生故障時，映射在該節點上的VNR將會中斷，為了保證VNR服務的連續性，該請求需要重新映射至正常的物理節點和路徑上，文中用虛擬網絡恢復成功率ξres表示故障VNR成功恢復映射的情況：

其中，VNRerr表示因物理節點發生故障而失效的VNR個數，VNRres表示發生故障后成功重映射的VNR個數。

（3）物理網絡資源負載利用率

虛擬網絡請求映射成功后，底層網絡的資源被暫時分配出去從而造成剩余資源減少，若此時下一個VNR到達，則可能發生某節點或鏈路的物理剩余資源不足，進而導致該VNR映射的時間變長。文中定義節點資源負載利用率和帶寬資源負載利用率，若資源負載利用率越大則代表當前底層網絡資源大部分被占用，VNR映射需要等待的可能性越大。

3 算法設計

3.1 虛擬網絡映射方案

在無線網絡中，節點間利用激光或微波鏈路傳輸數據，當物理網絡拓撲在一定區域時，由于激光或微波的傳輸特性，一方面可忽略數據在鏈路中的傳輸時延，另一方面需要考慮鏈路中斷在鏈路映射中所帶來的影響[21]。因此文中在虛擬鏈路映射階段不考慮在網絡鏈路中所產生的時延，即路徑最短距離由該路徑中所包含的節點跳數決定，節點跳數越多，則認為該路徑距離越長；此外，無線網絡鏈路由于受外界干擾或節點間距離遠而發生鏈路中斷，若某鏈路中斷概率越小，則認為該鏈路越可靠。

由上述分析，本文提出一種高可靠性的無線虛擬網絡映射算法（WVNEA-HR），其中該算法包括基于擴展資源的節點映射階段和最小鏈路代價的鏈路映射階段。針對無線虛擬網絡映射問題中的節點映射和鏈路映射兩個階段，算法綜合考慮了節點擴展資源以及鏈路中斷概率，WVNEA-HR通過對虛擬網絡請求VNR和物理網絡資源進行預處理，使兩個映射階段時間減少，進而在一定時間內虛擬網絡映射的個數增多。該虛擬網絡映射算法主要包括3個模塊，分別為預處理模塊、節點映射模塊和鏈路映射模塊，具體WVNEA-HR算法偽代碼如下所示：

1. for all nv,lv∈VNR do

2.Sort{nv∈VnNodeList,lv∈VnLinkList}//根據虛擬資源排序

3.end for

4. for all ns,ls∈GSdo

5. if Resource(ns)＞Resourcemin(nv∈VnNodeList)then

6.UtilisablePhysicalNodeList←ns//節點加入該集合

7. Sort{ns∈UtilisablePhysicalNodeList}//按物理資源排序

8. else VNRList.Last←VNR //推遲映射

9. if Resource(ls)＞Resourcemin(lv∈VnLinkList)then

10. UtilisablePhysicalLinkList←ls

11. Sort{ls∈UtilisablePhysicalLinkList}

12.else VNRList.Last←VNR

13.end for

14.for all nv∈VnNodeListNode(Failure)do

15. if nv=then//最大資源需求的虛擬節點

16. k=0//設置虛擬節點個數變量

17. if k＜Num.VnNodeList then

18. for all ns∈UtilisablePhysicalNodeList do

19. if ns＞then//節點資源是否滿足映射條件

20. NodeSet←ns

21. if NodeSet≠? then

22. Compute cpuex(ns∈NodeSet)//節點擴展資源

23. if cpuex(ns)=cpuex(ns(max))then

24. ns→//節點映射成功

26. k=k+1

27. update//更新物理節點資源

28. end if

31. end if

32. end for

33. else Embedded NodeSet←Node(Success)//節 點映射完畢

34. end if

35. end for

36. for all lv∈VnLinkListLink(Failure)do

37. if lv=then

38. t=0

39. for all t＜Num.VnLinkList do

45. end if

46. if LinkSet≠? then

50. t=t+1

51. update//更新物理鏈路資源

54. end if

55. end if

56. end for

57.end if

58.end for

3.2 失效節點和鏈路恢復策略

當底層網絡節點發生故障時，映射在該節點上的虛擬節點失效，與其相連的虛擬鏈路也將失效，為了保證虛擬請求的正常工作，需要對失效節點以及相連鏈路進行重映射。在節點重映射時，考慮到虛擬請求的恢復時間，因此在故障節點的臨近范圍內選取備用節點進行映射，備用節點范圍如式（13）所示，其含義為節點m,n間距離不超過δ跳。節點恢復策略如下所示：

輸入：物理網絡拓撲GS,故障節點m,節點跳數δ輸出：備用節點n

（1）構造備用節點集合Ran(m)

（2）判斷集合Ran(m)中節點資源是否滿足虛擬節點資源需求，將不符合條件的節點刪除；若集合Ran(m)中的節點均不滿足，則轉向步驟（6）

（3）計算集合Ran(m)中節點的備用系數Alter(ns)，并將結果按照從小到大排列，選取節點備用系數最小的節點作為虛擬重映射節點

（4）更新節點資源

（5）虛擬節點映射成功

（6）虛擬節點映射請求被推遲

重映射的節點在備用節點集合Ran(m)中產生，這樣在恢復虛擬網絡請求的同時可以減少映射時間，構造備用節點集合Ran(m)可通過設置合適的跳數實現。虛擬鏈路重映射與鏈路映射方法類似，當失效節點重映射后，針對失效鏈路，同樣采取基于鏈路代價的方法對其進行映射，若當前資源不允許，則該虛擬鏈路重映射被推遲，等待有足夠資源時再進行修復。

可以看出，在虛擬節點初始映射階段對于節點的選取是基于節點擴展資源的，而在故障生存重映射階段對于節點的選取則是基于節點備用系數的，這是因為在初始階段底層網絡主要是以接受VNR為主，為提高VNR映射成功率，需要重點考慮底層網絡資源；而在重映射階段由于網絡故障使得需要重點考慮節點可靠性，以此確保映射的成功率。

4 仿真結果分析

4.1 實驗設置

本文中虛擬網絡拓撲和物理網絡拓撲均采用GT-ITM工具生成，其中物理網絡中包含100個節點和400條鏈路，每對節點之間相連的概率在區間[0.3，0.6]內，物理節點的計算資源和鏈路帶寬資源分別服從[30，70]和[30，100]之間的均勻分布。每個虛擬請求都是隨機生成的，本文假設虛擬請求的到達率滿足每100個時間單位到達4個的泊松分布，每個虛擬請求的生存時間滿足1 000個時間單位的指數分布。虛擬網絡請求中節點的計算資源需求和鏈路帶寬資源需求分別服從[1，10]和[1，20]之間的均勻分布，虛擬請求節點個數服從[2，6]之間的均勻分布，每一對虛擬節點之間以0.5的概率相連。在每次仿真實驗中運行50 000個時間單位，大約包含2 000個虛擬請求。節點的失效間隔設為20 000個單位，并假定在下一個節點失效到來之前上一個失效節點已經被修復。將物理節點擴展資源中μ1和μ2分別設置為0.4和0.6，物理鏈路代價中λ1和λ2均設置為0.5，候選節點集合中跳數δ設置為10，為簡化計算，節點備用系數中ω1和ω2設置為0.5。

4.2 實驗結果分析

本文以虛擬請求接受率、虛擬網絡恢復成功率、虛擬請求重映射接受率、節點和鏈路負載利用率作為算法性能的評價指標，分別與算法DP-VNE[22]、SVNE-Hybird[23]、VNM-SM[24]進行對比分析，表1所示為幾種算法對比。

圖3所示為虛擬映射接受率曲線，由于初始階段虛擬網絡請求少，因而幾種算法都獲得了較高的映射接受率，隨著時間的推移，幾種算法的性能逐漸趨于平穩?？梢钥闯?，SVNE-Hybird算法初始時性能略優于VNM-SM，這是由于VNM-SM針對不同服務采取不同策略，而初始時刻由于Vn個數較少，故性能略低于SVNE-Hybird，而隨著Vn個數的增多，SVNE-Hybird算法由于采用備份鏈路策略，因而一定程度上占用了剩余資源，導致其性能低于VNM-SM算法，本文算法WVNEA-HR性能總體上優于其余三種算法，是由于在虛擬節點映射過程中除節點資源外還考慮與之相連物理鏈路的資源，一定程度上確保了鏈路映射的可靠性，如當仿真時間為10 min時，DP-VNE算法的接受率降到56%左右，本文所提算法的接受率逐漸穩定在67%左右。

表1 算法比較

圖3 虛擬請求接受率

圖4 所示為虛擬網絡恢復成功率隨時間的變化情況，初始映射階段到達的Vn較少，發生故障后底層網絡有足夠多的資源供生存恢復使用，因而初始階段的恢復成功率較高，隨著時間的推移，底層網絡的資源逐漸被使用，能夠提供的資源減少，因而恢復成功率變小最終趨于穩定。DP-VNE算法的恢復成功率最低，VNM-SM和本文算法的恢復成功率相近，文中算法采取了節點候選集合，當物理節點發生故障后能夠快速找到其遷移的物理節點，因而使得發生失效的虛擬請求能夠迅速恢復，可以看出，本文算法的恢復成功率最終穩定在66%左右。

圖4 虛擬請求恢復成功率

圖5 所示為隨著候選集合節點跳數的變化虛擬請求重映射接受率的情況，可以看出，虛擬網絡重映射能否成功在很大程度上取決于網絡中節點跳數的選取。仿真顯示出隨著節點跳數的增加(h=5,8,11)，虛擬請求重映射接受率呈現出增大的趨勢，當節點跳數h分別為5、8、11時，對應的請求接受率依次在64%、59%和49%左右，這是由于候選集合中的節點個數增多，使得故障節點有更多候選節點資源使用，一定程度上提高了請求接受率。

圖5 虛擬請求重映射接受率

圖6 節點負載利用率

圖7 鏈路負載利用率

節點資源負載利用率和鏈路資源負載利用率仿真如圖6和圖7所示，可以看出，在三種算法的負載利用率曲線中，本文提出的算法具有較優的性能，由于WVNEAHR在節點映射方面綜合考慮節點資源和擴展資源，使得節點擴展資源較小的節點被排除，故節點資源負載利用率略小于VNM-SM算法，而在鏈路映射階段由于采用最小鏈路代價策略，有效地避免了底層某條鏈路被多次映射，故其鏈路負載利用率優于其余算法，SVNEHybird算法的負載利用率高于DP-VNE，DP-VNE算法簡單將每條虛擬鏈路映射到底層不交叉的鏈路上，沒有更進一步的約束條件，其效率最低?？傮w而言，本文算法具有較高的網絡資源利用率。

5 結束語

本文主要針對虛擬網絡映射過程中鏈路映射階段資源不足以及網絡故障問題進行研究，為確保鏈路映射的成功率，在節點映射階段采用基于節點擴展資源的映射策略，以此提高鏈路映射成功率，在鏈路映射階段則采用最小鏈路代價的映射方法。此外在底層網絡節點發生故障時，文中所提映射算法能夠最大程度保證虛擬請求的連通性，并能夠完成對虛擬請求失效部分的重映射，結果表明本文所提算法在滿足虛擬請求可靠映射的同時，能夠提高虛擬映射接受率和虛擬請求恢復成功率?，F階段關于虛擬網絡可靠性映射的研究主要圍繞單節點失效，關于多節點失效和多域映射的研究較少，今后將在現階段的基礎上進一步關于多節點失效和多域映射展開研究。