基于多節點故障恢復的虛擬網絡映射算法

朱國暉，劉秀霞+，張 茵，陳 剛

(1.西安郵電大學 通信與信息工程學院，陜西 西安 710121；2.中國聯合網絡通信有限公司東營市分公司，山東 東營 257000)

0 引 言

網絡虛擬化[1]為傳統的互聯網提供了更大的靈活性和更好的可管理性，其關鍵在于虛擬網絡映射(virtual network embedding，VNE)[2]。在VNE過程中若出現設備故障、大規模災害或惡意攻擊等情況，導致虛擬網絡(virtual network，VN)請求服務失敗，基礎設施提供商(infrastructure provider，InP)[3]將會根據服務等級協議(service level agreement，SLA)的規定，為租戶提供賠償[4]。因此，保證VN請求的正常進行，變得尤為重要。

目前，相關學者針對物理網絡中出現節點和鏈路故障問題進行了研究，并采用主動保護和被動恢復兩種策略，來保證虛擬網絡的生存性，將這種恢復策略方法稱為生存性虛擬網絡映射(survivable virtual network embedding，SVNE)算法。對于主動保護策略：文獻[5-7]采用備份整個物理網絡拓撲的方案，雖然這保證了節點的恢復率，但是卻浪費了許多物理資源；文獻[8,9]提出一種主動的基于混合策略的啟發式鏈路備份算法。對于被動恢復策略,文獻[10,11]提出一種節點遷移與重映射方法，但在物理剩余資源較少時，恢復的成功率較低。

綜上，針對以上文獻中存在的不足，本文從多節點故障場景出發，為解決物理節點故障問題，提出一種基于多節點故障恢復的虛擬網絡映射算法。在虛擬請求到來之前，利用廣度優先搜索算法，為物理節點創建備份節點集合；在虛擬請求到達時，根據目標函數，求解線性規劃；當出現節點故障時，在節點備份集合中根據節點恢復度因子值，選擇最佳候選節點，并逐個進行VN重映射，從而增加了InP的長期業務利潤，縮短了故障恢復時延，提高了故障恢復率。

1 建立網絡模型

1.1 物理網絡和虛擬網絡模型

本文采用文獻[12]，建立網絡模型。

物理網絡：抽象為加權無向圖Gs=(Ns,Ls)， 其中，Ns和Ls分別為物理節點集合和物理鏈路集合。c(ns)表示物理節點ns∈Ns的節點計算能力。b(ls)表示物理鏈路ls∈Ls的鏈路帶寬。

在物理網絡中，將物理節點ns主用資源需求表示為cp(ns)=αc(ns)， 備用資源需求表示為cb(ns)=(1-α)c(ns)，α為主用比例。同樣，物理鏈路的帶寬資源也分為bp(ls) 和bb(ls) 兩部分。

虛擬網絡與物理網絡類似，詳細見文獻[13]，記為Gv=(Nv,Lv)。c(nv) 是虛擬節點nv∈Nv的節點資源大小。b(lv) 是虛擬鏈路lv∈Lv的帶寬大小。

1.2 虛擬網絡重映射

虛擬網絡重映射定義請詳見文獻[4]，此處不再贅述。VN重映射過程，如圖1所示，在VN映射過程中，節點A發生故障，虛擬節點a上的資源就要重映射(重新分配資源)到物理節點D上，將虛擬鏈路(a，b)和(a，c)分別重映射到物理鏈路(C，D)和(B，D)上。

圖1 虛擬網絡映射實例

1.3 評價指標

(1)InP的長期業務利潤

映射一個虛擬網絡請求獲得的收益R(Gv) 是在虛擬網絡Gv的生命周期內，將物理網絡資源成功分配到的虛擬節點和虛擬鏈路上的資源能力之和。故R(Gv) 可表示為

(1)

其中，β和γ設為1，分別是虛擬節點和虛擬鏈路的能力的單價。

在VNE過程中，一個物理節點出現故障，并且該物理節點上承載的VN請求無法恢復工作，即節點故障恢復失敗，則InP需要按照SLA中的規定支付罰款，定義為

(2)

其中，ω為懲罰因子，設為2，G′v為受節點x影響的任意一個VN

(3)

其中，D(x) 是受x節點影響而失效的VN的集合。

定義InP在時間T內的長期業務利潤profit(T)

(4)

其中，Nm(T) 映射成功的VN的集合，B(T) 是故障物理節點組成的集合。

(2)VN請求接受率

(5)

其中，Nm(t) 是t=0到T時刻映射成功的集合，N(t) 是所有到達的VN請求的集合。δ是趨于零的正數。

2 基于恢復度因子的生存性虛擬網絡映射算法

2.1 基于節點恢復度因子的候選節點選擇策略

2.1.1 構建物理節點候選集合

圖2 物理網絡資源配置

關于物理節點候選集合的構建算法，其偽代碼如下。

算法1： 物理節點候選集合的構建算法

輸入：Gs,x∈Ns，h′=1,2,…,h

輸出：Cov(Gs,x,h)

(1)初始化跳數h′=1

(2)for 物理節點x∈Nsdo

(3) 使用廣度優先搜索算法， 計算距離節點的最短路徑為h′ 跳的節點集合J(Gs,x,h′)

(4)h′++， 增加一跳

(5) if 當前跳數大于預定跳數即h′>hthen

(6) return 得到h跳之內的所有節點集合Cov(Gs,x,h)

(7) else 轉到步驟(4)

(8) end if

(9) end for

2.1.2 定義節點恢復度因子

(1)物理節點的生存性概率

當一個物理節點x發生故障時，若候選節點上實時剩余的備份資源較多，則重映射成功的概率較高，反之，則重映射成功的概率較低，在本文中定義節點生存概率為P(ri)， 表示當一個節點發生故障時，在它的候選節點ri進行重映射，并且使得VN請求正常工作的概率。

對于物理節點ns定義兩個變量

(6)

(7)

在物理節點x發生故障時，若節點x的一個候選節點ri∈Cov(Gs,x,h) 上的剩余可用資源Q(ri) 大于節點x已使用的資源A(ri) 時，在節點ri上進行重映射成功的概率就會較高，當Q(ri) 小于A(ri) 時在節點ri上進行重映射成功的概率就會較低。根據上述特點，定義一個歸一化的節點生存概率P(ri) 來表示這個關系

(8)

其中，δ為趨于零的正數。

(2)接近中心度：節點與物理網絡中可到達該節點最短跳數之和的倒數[14]

(9)

(3)節點資源度：節點計算資源與所有相鄰鏈路帶寬資源的和

(10)

(4)由式(9)和式(10)得到節點重要度

M(ri)=D(ri)U(ri)

(11)

(5)由式(11)和式(8)可得到節點恢復度因子

(12)

在圖2中，矩形框中的內容表示節點的資源需求，例如節點B旁邊的矩形框中“P∶5/7”表示節點主用資源共7個單位，目前已經使用了5個單位，而“B∶3/6”表示節點備份資源共6個單位，已經使用了3個單位，物理鏈路和節點表示類似。由此可以計算出物理節點A上的A(A)=23， 對于節點A在一跳范圍內的候選節點B、C、D，根據式(8)可得，P(B)=0.456，P(C)=0.432，P(D)=0.691， 由此可知當節點A發生故障時，節點D作為備份節點進行重映射成功概率較高。

但是，物理網絡的資源是有限的，在保證恢復率的同時，也必須考慮整個物理網絡資源的有效利用，故提出了節點重要度。節點重要度越大，則該節點在物理網絡拓撲中越重要，則它成為其它故障節點的備份節點的可能性就越大，因此若優先使用重要度小的候選節點，將重要度大的節點用于恢復那些重要的虛擬節點，則有利于優化剩余備份資源的連通性。

于是考慮到節點重映射成功的概率和剩余備份資源的連通性，提出了節點恢復度因子，它將兩種因素進行了折中處理，在故障節點x的候選集中，優先使用恢復度因子值最大的節點進行重映射。如圖2中節點A的3個候選節點的恢復度因子分別為ε(B)=0.064，ε(C)=0.042,ε(D)=0.038， 由此可得在節點A發生故障時，在節點B上進行節點重映射的綜合質量最佳。

2.2 虛擬網絡重映射的混合整數規劃

本文采用對單一節點故障恢復的逐一優化策略，來提高在多節點故障場景下，整體的長期業務利潤。

(1)目標函數

(13)

目標函數由兩部分組成，第一部分表示最小化由于物理節點故障，導致VN失效，所支付的罰款；第二部分表示最小化虛擬鏈路重映射占用的帶寬資源，ξ為權重因子，設為1。

(2)定義變量

myr：若虛擬節點y∈G′v∈D(x) 重映射到物理節點r∈Cov(Gs,x,h) 上時myr=1， 否則，myr=0。D(x)是受節點x影響而失效的VN組成的集合。

θnvr：若虛擬節點nv∈G′v映射到物理節點r∈Cov(Gs,x,h) 上時θnvr=1， 否則，θnvr=0。nv∈G′v表示節點nv和節點y在同一個虛擬請求中。

fuw：物理鏈路 (u,w) 用于鏈路重映射占用的帶寬資源。

(3)約束條件

備份資源約束

(14)

(15)

式(14)和式(15)表示任意用于重映射的節點，它的實際可用備份資源要大于等于被替代節點的計算資源；用于重映射的物理鏈路，它的實際可用備份帶寬也要大于或等于被替代鏈路的帶寬。

節點重映射約束

(16)

myr=0,θnvr=1,y∈N′v(x),
r∈Cov(Gs,x,h),nv∈G′v

(17)

式(16)表示一個物理節點發生故障，至多有一個候選節點進行重映射，式(17)表示在相同VN中的虛擬節點不能同時重映射在相同的物理節點上。

變量約束

myr∈{0,1}, ?y∈N′v(x),r∈Cov(Gs,x,h)

(18)

對于基于恢復度因子的生存性虛擬網絡映射算法(RE-SVNE)的偽代碼描述如下。

算法2： RE-SVNE算法

輸入：Gs，Gv

輸出：Embedding(Gv)

(1) forx∈Nsdo

(2) 根據算法1計算候選節點集Cov(Gs,x,h)

(3) end for

(4) forri∈Cov(Gs,x,h) do

(5) 根據式(8)計算Cov(Gs,x,h) 集合中每個節點生存概率

(6) 根據式(11)計算Cov(Gs,x,h) 集合中每個節點重要度

(7) 根據式(12)計算Cov(Gs,x,h) 集合中每個節點的恢復度因子值

(8) 將節點x的候選集合中的節點按恢復度因子值降序排列,并將結果存入Nodeslist

(9) end for

(10) for 每個VN請求 do

(11) if VN請求到達時， 未發生物理節點故障 then

(12) 采用文獻[15]的VN映射算法進行映射

(13) end if

(14) if 物理節點x發生故障 then

(15) 統計受x影響而失效的虛擬節點和虛擬鏈路構成的集合

(16) for 每個失效虛擬節點 do

(17) 根據式(13)目標函數求解線性規劃，在Nodeslist中ε(ri) 值最大的候選節點上，逐個進行虛擬節點重映射處理

(18) end for

(19) for 每個失效虛擬鏈路 do

(20) 使用K最短路徑算法進行鏈路重映射[17]

(21) end for

(22) end if

(23) forri∈Cov(Gs,x,h) do

(24) 更新ε(ri) 的值和結果集Nodeslist

(25) end for

(26) returnEmbedding(Gv)

3 實驗仿真

3.1 實驗環境

本文的實驗環境為：內存是4 GB，操作系統是64位的Win7系統，處理器是Intel i5。其中，采用MATLAB軟件進行實驗評估，在實驗中用到的網絡拓撲均由GT-ITM[17]生成，設置物理節點故障的到達服從參數為0.03的泊松分布，故障持續時間服從參數為d的指數分布,h的值為3，具體的參數見表1[18]。本實驗運行50 000個時間單元，為體現實驗結果的穩定性，結果均采用10次實驗的平均值。

表1 實驗參數配置

3.2 對比方案和性能選取

將文獻[19]中TA-SVNE算法和文獻[4]Blind-SVNE算法與本文所提RE-SVNE算法在長期業務利潤、VN接受率、VN恢復率、重映射平均計算時間和主用比例α對算法的影響程度進行算法性能比較。

3.3 仿真結果與分析

(1)長期業務利潤

圖3是發生多個物理節點故障時，使用InP的長期業務利潤來比較3種算法的性能，其中主用比例α為0.7。如圖3(a)和圖3(b)所示，RE-SVNE算法的長期業務利潤要都高于其它兩種算法，并且當節點故障平均持續時間從25增大到50時，RE-SVNE算法的長期業務利潤的影響并不大，而對于TA-SVNE算法和Blind-SVNE算法的性能顯著下降。這是因為隨著發生多節點故障概率增加，用于恢復故障的物理剩余備份資源會被過度占用，而RE-SVNE算法，在提高恢復率的同時還優化了備份資源的連通性，確保那些連通性好的節點不會被過度占用，將其用于恢復受其節點故障影響的VN中罰款較高的，減少InP必須支付的罰款，來提高長期業務利潤，由此驗證當發生多節點故障的概率增大時，RE-SVNE算法有更好的穩定性。

圖3 長期業務利潤

(2)VN請求接受率

圖4是關于3種算法的VN請求接受率的比較，RE-SVNE算法的請求接受率介于其它兩種算法之間。因為Blind-SVNE算法沒有任何的備份資源，將物理網絡資源全都用來進行VN映射，故接受率最高，RE-SVNE和TA-SVNE算法要將一定比例的物理資源用于VN重映射，故接受率稍低，但RE-SVNE算法重映射時采用的節點選擇策略，會使得剩余資源的連通性比較好，使其VN接受率相比TA-SVNE較高。

圖4 VN請求接受率

(3)VN恢復率

圖5中是關于3種算法的VN恢復率的比較，如圖5所示，文中所提算法RE-SVNE的恢復率都高于其它兩種算法。因為隨著到達VN的增多，物理資源不斷被占用，故障節點的個數增多，用于重映射資源被過度占用，因此VN恢復率會快速降低，而RE-SVNE算法優先選擇恢復度因子值最大的候選節點，使得剩余備份資源的連通性得到優化，隨著剩余備份資源的不斷減少，VN恢復率也會出現一定程度的降低，但較為緩慢，最終保持在0.826左右，優于其它3種對比算法。

圖5 VN恢復率

(4)重映射平均計算時間

圖6是3種算法重映射平均計算時間的對比，重映射平均計算時間即故障恢復時延是衡量被動恢復機制算法的有效性指標，重映射時間短，則故障恢復時延較小，可能造成的數據丟失情況較少。由圖6所示TA-SVNE算法和RE-SVNE算法兩種算法的重映射程序運行時間相比較Blind-SVNE算法較短，這是因為TA-SVNE算法和RE-SVNE算法兩種算法都采用了節點備份策略減少了節點選擇的時間，但是在重映射過程中TA-SVNE算法要在節點候選集中再找到合適的節點進行重映射，而RE-SVNE算法在重映射之前就為每一個節點計算好了最佳備份節點，更近一步縮短了重映射的時間。

圖6 重映射平均計算時間

(5)主用比例α對算法的影響程度

圖7是在節點故障平均持續時間d=25的情況下，主用比例α對TA-SVNE算法和RE-SVNE算法性能的影響，因為Blind-SVNE算法并沒有將物理資源進行主備用分配，故它的長期業務利潤不隨α的增大而改變。其它兩種算法在主用比例為0.7時長期業務利潤均達到最大值，當大于0.7時長期業務利潤又開始減少。因此在多節點故障場景下，應適當減小α， 來保障充足的資源進行故障恢復。

圖7 主用比例對算法的影響

4 結束語

本文主要分析了網絡虛擬化環境中VNE的生存性問題。對于發生多個物理節點故障時，使用節點恢復度因子的候選節點選擇策略，提出RE-SVNE算法。仿真實驗結果分析表明本文所提算法在故障恢復時延、InP的長期業務利潤和VN恢復率方面均有較好的性能，也有效提高了虛擬網絡的生存性。本文對節點故障的研究僅僅是在單域的VNE過程中進行的，對于多域的節點故障恢復可作為下一步的研究方向。