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

(1.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121；2.中國聯(lián)合網(wǎng)絡(luò)通信有限公司東營市分公司，山東 東營 257000)

0 引 言

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

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

綜上，針對以上文獻(xiàn)中存在的不足，本文從多節(jié)點故障場景出發(fā)，為解決物理節(jié)點故障問題，提出一種基于多節(jié)點故障恢復(fù)的虛擬網(wǎng)絡(luò)映射算法。在虛擬請求到來之前，利用廣度優(yōu)先搜索算法，為物理節(jié)點創(chuàng)建備份節(jié)點集合；在虛擬請求到達(dá)時，根據(jù)目標(biāo)函數(shù)，求解線性規(guī)劃；當(dāng)出現(xiàn)節(jié)點故障時，在節(jié)點備份集合中根據(jù)節(jié)點恢復(fù)度因子值，選擇最佳候選節(jié)點，并逐個進(jìn)行VN重映射，從而增加了InP的長期業(yè)務(wù)利潤，縮短了故障恢復(fù)時延，提高了故障恢復(fù)率。

1 建立網(wǎng)絡(luò)模型

1.1 物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)模型

本文采用文獻(xiàn)[12]，建立網(wǎng)絡(luò)模型。

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

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

虛擬網(wǎng)絡(luò)與物理網(wǎng)絡(luò)類似，詳細(xì)見文獻(xiàn)[13]，記為Gv=(Nv,Lv)。c(nv) 是虛擬節(jié)點nv∈Nv的節(jié)點資源大小。b(lv) 是虛擬鏈路lv∈Lv的帶寬大小。

1.2 虛擬網(wǎng)絡(luò)重映射

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

圖1 虛擬網(wǎng)絡(luò)映射實例

1.3 評價指標(biāo)

(1)InP的長期業(yè)務(wù)利潤

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

(1)

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

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

(2)

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

(3)

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

定義InP在時間T內(nèi)的長期業(yè)務(wù)利潤profit(T)

(4)

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

(2)VN請求接受率

(5)

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

2 基于恢復(fù)度因子的生存性虛擬網(wǎng)絡(luò)映射算法

2.1 基于節(jié)點恢復(fù)度因子的候選節(jié)點選擇策略

2.1.1 構(gòu)建物理節(jié)點候選集合

圖2 物理網(wǎng)絡(luò)資源配置

關(guān)于物理節(jié)點候選集合的構(gòu)建算法，其偽代碼如下。

算法1： 物理節(jié)點候選集合的構(gòu)建算法

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

輸出：Cov(Gs,x,h)

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

(2)for 物理節(jié)點x∈Nsdo

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

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

(5) if 當(dāng)前跳數(shù)大于預(yù)定跳數(shù)即h′>hthen

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

(7) else 轉(zhuǎn)到步驟(4)

(8) end if

(9) end for

2.1.2 定義節(jié)點恢復(fù)度因子

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

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

對于物理節(jié)點ns定義兩個變量

(6)

(7)

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

(8)

其中，δ為趨于零的正數(shù)。

(2)接近中心度：節(jié)點與物理網(wǎng)絡(luò)中可到達(dá)該節(jié)點最短跳數(shù)之和的倒數(shù)[14]

(9)

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

(10)

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

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

(11)

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

(12)

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

但是，物理網(wǎng)絡(luò)的資源是有限的，在保證恢復(fù)率的同時，也必須考慮整個物理網(wǎng)絡(luò)資源的有效利用，故提出了節(jié)點重要度。節(jié)點重要度越大，則該節(jié)點在物理網(wǎng)絡(luò)拓?fù)渲性街匾?，則它成為其它故障節(jié)點的備份節(jié)點的可能性就越大，因此若優(yōu)先使用重要度小的候選節(jié)點，將重要度大的節(jié)點用于恢復(fù)那些重要的虛擬節(jié)點，則有利于優(yōu)化剩余備份資源的連通性。

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

2.2 虛擬網(wǎng)絡(luò)重映射的混合整數(shù)規(guī)劃

本文采用對單一節(jié)點故障恢復(fù)的逐一優(yōu)化策略，來提高在多節(jié)點故障場景下，整體的長期業(yè)務(wù)利潤。

(1)目標(biāo)函數(shù)

(13)

目標(biāo)函數(shù)由兩部分組成，第一部分表示最小化由于物理節(jié)點故障，導(dǎo)致VN失效，所支付的罰款；第二部分表示最小化虛擬鏈路重映射占用的帶寬資源，ξ為權(quán)重因子，設(shè)為1。

(2)定義變量

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

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

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

(3)約束條件

備份資源約束

(14)

(15)

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

節(jié)點重映射約束

(16)

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

(17)

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

變量約束

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

(18)

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

算法2： RE-SVNE算法

輸入：Gs，Gv

輸出：Embedding(Gv)

(1) forx∈Nsdo

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

(3) end for

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

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

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

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

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

(9) end for

(10) for 每個VN請求 do

(11) if VN請求到達(dá)時， 未發(fā)生物理節(jié)點故障 then

(12) 采用文獻(xiàn)[15]的VN映射算法進(jìn)行映射

(13) end if

(14) if 物理節(jié)點x發(fā)生故障 then

(15) 統(tǒng)計受x影響而失效的虛擬節(jié)點和虛擬鏈路構(gòu)成的集合

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

(17) 根據(jù)式(13)目標(biāo)函數(shù)求解線性規(guī)劃，在Nodeslist中ε(ri) 值最大的候選節(jié)點上，逐個進(jìn)行虛擬節(jié)點重映射處理

(18) end for

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

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

(21) end for

(22) end if

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

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

(25) end for

(26) returnEmbedding(Gv)

3 實驗仿真

3.1 實驗環(huán)境

本文的實驗環(huán)境為：內(nèi)存是4 GB，操作系統(tǒng)是64位的Win7系統(tǒng)，處理器是Intel i5。其中，采用MATLAB軟件進(jìn)行實驗評估，在實驗中用到的網(wǎng)絡(luò)拓?fù)渚蒅T-ITM[17]生成，設(shè)置物理節(jié)點故障的到達(dá)服從參數(shù)為0.03的泊松分布，故障持續(xù)時間服從參數(shù)為d的指數(shù)分布,h的值為3，具體的參數(shù)見表1[18]。本實驗運(yùn)行50 000個時間單元，為體現(xiàn)實驗結(jié)果的穩(wěn)定性，結(jié)果均采用10次實驗的平均值。

表1 實驗參數(shù)配置

3.2 對比方案和性能選取

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

3.3 仿真結(jié)果與分析

(1)長期業(yè)務(wù)利潤

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

圖3 長期業(yè)務(wù)利潤

(2)VN請求接受率

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

圖4 VN請求接受率

(3)VN恢復(fù)率

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

圖5 VN恢復(fù)率

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

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

圖6 重映射平均計算時間

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

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

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

4 結(jié)束語

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