面向多鏈路故障的生存性虛擬網(wǎng)絡(luò)映射算法

朱國暉,劉秀霞,張 茵

(西安郵電大學(xué) 通信與信息工程學(xué)院,西安 710121)

0 概述

隨著互聯(lián)網(wǎng)的快速發(fā)展,網(wǎng)絡(luò)僵化成為限制互聯(lián)網(wǎng)架構(gòu)創(chuàng)新與發(fā)展的關(guān)鍵因素,而網(wǎng)絡(luò)虛擬化的出現(xiàn)為解決網(wǎng)絡(luò)僵化問題提供了有效途徑[1-2]。網(wǎng)絡(luò)虛擬化解耦了網(wǎng)絡(luò)服務(wù)提供與基礎(chǔ)設(shè)施提供2個功能,并允許多個異構(gòu)虛擬網(wǎng)絡(luò)(Virtual Network,VN)在同一個物理網(wǎng)絡(luò)上共享資源[3],其核心問題是虛擬網(wǎng)絡(luò)映射(Virtual Network Embedding,VNE)[4],而VNE被證明是NP-Hard[5-6]問題。多數(shù)VNE算法都是假設(shè)在不出現(xiàn)物理故障的情況下[7]提出的,它們通過優(yōu)化網(wǎng)絡(luò)模型來提高資源利用率并增加收益。然而,如果在VNE過程中出現(xiàn)設(shè)備故障、大規(guī)模災(zāi)害或惡意攻擊等情況,將會導(dǎo)致VN請求服務(wù)失敗,降低服務(wù)性能和可用性,若服務(wù)中斷,則基礎(chǔ)設(shè)施提供商(Infrastructure Provider,InP)必須支付服務(wù)等級協(xié)議(Service Level Agreement,SLA)中指定的罰款。因此,需要對生存性虛擬網(wǎng)絡(luò)映射(Survivable Virtual Network Embedding,SVNE)算法進(jìn)行研究,從而保證網(wǎng)絡(luò)的正常運(yùn)行。

學(xué)者們針對現(xiàn)有SVNE算法進(jìn)行了研究,如文獻(xiàn)[8]提出數(shù)據(jù)中心鏈路發(fā)生故障的概率是節(jié)點發(fā)生故障概率的10倍。對于物理鏈路故障,文獻(xiàn)[9]提出一種主動鏈路備份生存性算法,該算法提前為虛擬鏈路分配好備份鏈路,當(dāng)物理鏈路發(fā)生故障時將其切換至備份鏈路,該方法雖然提高了故障恢復(fù)率,但是過多的冗余備份會造成資源浪費(fèi)。文獻(xiàn)[10-12]提出一種被動恢復(fù)的生存性算法,該算法不預(yù)留備份資源,當(dāng)鏈路發(fā)生故障時,利用剩余物理資源將受影響的虛擬鏈路進(jìn)行鏈路重映射,該方法雖然避免了冗余備份資源的浪費(fèi),但是增加了故障恢復(fù)時延,且不能保證具有良好的故障恢復(fù)率。文獻(xiàn)[13-15]研究了當(dāng)發(fā)生單個故障時,采用鏈路重映射和路徑分割的鏈路重映射方法進(jìn)行故障恢復(fù)。文獻(xiàn)[16]是在位置約束的條件下,對發(fā)生的鏈路故障進(jìn)行重映射處理。因此,上述提出的SVNE算法均是在僅發(fā)生單一鏈路故障的情況下提出的。對于多鏈路故障,文獻(xiàn)[17]從QoS角度提出了主動保護(hù)和被動恢復(fù)2種算法,但是這2種算法都沒有考慮映射開銷和物理資源碎片化問題。

針對以上問題,本文重點研究物理鏈路故障問題,并從多鏈路故障場景出發(fā),提出一種面向多鏈路故障的生存性虛擬網(wǎng)絡(luò)映射算法。利用多路徑選擇算法創(chuàng)建物理鏈路備份路由集,并根據(jù)目標(biāo)函數(shù)求解整數(shù)線性規(guī)劃,從故障鏈路備份路由集中選擇帶寬資源平衡度大的路徑,為受鏈路故障影響的虛擬鏈路逐個進(jìn)行重映射,從而減少物理資源碎片化概率,提高物理資源利用率。

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

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

物理網(wǎng)絡(luò)模型抽象為加權(quán)無向圖,記為Gs=(Ns,Ls),其中,Ns為物理節(jié)點集合,Ls為物理鏈路集合,對物理節(jié)點ns∈Ns的節(jié)點需求用c(ns)表示,對物理鏈路ls∈Ls的帶寬需求用b(ls)表示。在物理網(wǎng)絡(luò)中,將物理資源分為主、備用資源,其中,主鏈路帶寬資源為bp(ls)=αb(ls),備用鏈路帶寬資源為bb(ns)=(1-α)b(ls),α為調(diào)節(jié)系數(shù),用來調(diào)節(jié)主、備用帶寬資源比例[18]。

虛擬網(wǎng)絡(luò)模型抽象為加權(quán)無向圖,記為Gv=(Nv,Lv),其中,Nv為虛擬節(jié)點集合,Lv為虛擬鏈路集合,對虛擬節(jié)點nv∈Nv的節(jié)點需求用c(nv)表示,對虛擬鏈路lv∈Lv的帶寬需求用b(lv)表示。

虛擬網(wǎng)絡(luò)映射可分為2個階段[19]:

虛擬網(wǎng)絡(luò)映射示意圖如圖1所示。

圖1 虛擬網(wǎng)絡(luò)映射示意圖Fig.1 Schematic diagram of virtual network embedding

1.2 評價指標(biāo)

本文采用VN請求接受率、長期平均收益開銷比與平均故障恢復(fù)率對實驗結(jié)果進(jìn)行評價。

1)VN請求接受率的計算方法如式(1)所示:

(1)

其中,Nm(t)是t從0～T時刻映射成功的集合,N(t)是所有到達(dá)VN請求的集合,δ是趨于0的正數(shù),用來保證分母不為0。

2)對于虛擬請求Gv=(Nv,Lv),定義在t時刻Gv的映射收益R(Gv,t)為:

(2)

其中,β是節(jié)點和鏈路的收益均衡因子,在本文中設(shè)置為1。

定義在t時刻Gv的映射開銷C(Gv,t)為:

(3)

其中,γ是節(jié)點和鏈路的開銷均衡因子,在本文中設(shè)置為1,hop(lv)表示虛擬鏈路lv映射到物理路徑中的跳數(shù)。

定義長期平均收益開銷比為:

(4)

在VNE過程中,如果一條物理鏈路發(fā)生故障,并且故障恢復(fù)失敗,則InP需要承擔(dān)SLA中指定的罰款S(Gv)[20]:

S(Gv)=ωR(Gv,t)

(5)

其中,ω是懲罰因子,在本文中設(shè)置為2。

因此,將本文中的長期平均收益開銷比重新定義為:

(6)

3)平均故障恢復(fù)率的計算方法見式(7):

(7)

其中,F(lv)表示受物理鏈路故障影響而失效的虛擬鏈路總數(shù),Re(lv)表示受物理鏈路故障影響而失效,但采用故障恢復(fù)算法恢復(fù)成功的虛擬鏈路數(shù)量。

2 多鏈路故障的生存性虛擬網(wǎng)絡(luò)映射算法

2.1 備份路由集合構(gòu)建

在虛擬請求到達(dá)之前,采用路徑選擇算法為每個物理鏈路構(gòu)建備份路由集,縮短鏈路重映射時延。本文在最短路徑算法[20]的基礎(chǔ)上,提出一種多路徑選擇算法。它是在物理網(wǎng)絡(luò)中構(gòu)建多條可用路徑集合的算法,相比于最短路徑算法,該算法考慮了在規(guī)定路徑跳數(shù)和鏈路映射過程中多種資源約束的問題,通過搜索每條物理鏈路,找到滿足約束條件的多條路徑并構(gòu)成備份路由集合。

圖2 備份鏈路圖Fig.2 Backup link diagram

對物理鏈路定義2個變量:

(8)

ls∈x,x∈Cov(Gs,l,h)

(9)

其中,lv→l表示虛擬鏈路lv映射到物理鏈路l上,bp(lv)和bb(lv)分別表示在物理鏈路l上承載虛擬鏈路所需主用帶寬和用于鏈路重映射的備用帶寬,U(l)是兩者之和,Q(x)表示在路徑集合中每條路徑可用于鏈路重映射的最小瓶頸帶寬。

多路徑選擇算法的實現(xiàn)偽代碼為:

輸入Gs,h,h′=2,3,…,h

輸出可用備份路徑集合pathlist(l)

1.初始化,最大跳數(shù)h=max_hops,跳數(shù)h′=2

2.for 每條物理鏈路l∈Lsdo

3.使用最短路徑算法計算J(Gs,l,h′),將其結(jié)果存入集合Cov(Gs,l,h)中

4.跳數(shù)增加一跳,h′++

5.if 當(dāng)前跳數(shù)大于規(guī)定跳數(shù),即h′>h then

6.return 得到h跳之內(nèi)的所有鏈路集合Cov(Gs,l,h)

7.else 轉(zhuǎn)到步驟2

8.end if

9.end for

10.for Cov(Gs,l,h) do

11.根據(jù)式(8)計算U(l)

12.根據(jù)式(9)計算Cov(Gs,l,h)中每條路徑的最小瓶頸帶寬Q(x)

13.if U(l)≤Q(x) then

14.將該路徑存入可用路徑集合pathlist(l)中

15.else pathlist(l)集合為空

16.end if

17.end for

18.return pathlist(l)

2.2 虛擬網(wǎng)絡(luò)映射模型構(gòu)建

本文將虛擬網(wǎng)絡(luò)映射分為2個階段進(jìn)行,重點關(guān)注鏈路映射,將多鏈路故障建模為多條單一鏈路故障并進(jìn)行逐一優(yōu)化。在節(jié)點映射時,采用文獻(xiàn)[12]中的貪婪映射算法為虛擬節(jié)點選擇資源最大的物理節(jié)點,包括節(jié)點資源、鏈路帶寬和節(jié)點映射中相鄰鏈路的數(shù)量。虛擬鏈路映射采用整數(shù)線性規(guī)劃模型,具體過程如下:

1)目標(biāo)函數(shù)為最大化長期平均收益開銷比,表示為:

max(R′/C)

(10)

2)變量定義為:

(11)

3)約束條件為:

(12)

(13)

當(dāng)物理鏈路發(fā)生故障時,采用鏈路重映射算法,將受影響的虛擬鏈路重映射到故障鏈路的備份物理路徑上。由于一條物理鏈路發(fā)生故障會造成多條虛擬鏈路失效,若虛擬鏈路恢復(fù)失敗,VN請求服務(wù)中斷,InP會承擔(dān)SLA中規(guī)定的罰款。因此,優(yōu)先重映射產(chǎn)生罰款較多的虛擬鏈路,減少InP的罰款,增加收益。

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

(14)

2)約束條件為:

(15)

3)定義帶寬資源平衡度為[11]:

(16)

面向多鏈路故障恢復(fù)的虛擬網(wǎng)絡(luò)映射算法偽代碼為:

輸入輸入GS,G

輸出Embedding(Gv)

1.for 每個虛擬請求 do

2.for 虛擬請求的虛擬節(jié)點 do

3.采用文獻(xiàn)[12]中的貪婪算法進(jìn)行節(jié)點映射

4.end for

5.if 在進(jìn)行虛擬鏈路映射時,物理鏈路未發(fā)生故障 then

6.根據(jù)本文虛擬鏈路映射算法,求解線性規(guī)劃

7.end if

8.if 物理鏈路l發(fā)生故障 then

9.統(tǒng)計受鏈路l影響的虛擬鏈路的集合,并將虛擬鏈路帶寬值進(jìn)行降序排列,結(jié)果存入集合VL中

10.for 故障物理鏈路l do

11.根據(jù)多路徑選擇算法計算鏈路l的備份路由集pathlist(l)

12.for pathlist(l)集合中所有路徑 do

13.根據(jù)式(16)計算帶寬資源平衡度

14.根據(jù)式(14)求解線性規(guī)劃,將VL集合中虛擬鏈路在帶寬資源平衡度最大的路徑上,依次進(jìn)行鏈路重映射

15.end for

16.end for

17.end if

18.end for

19.return

3 實驗仿真

3.1 實驗環(huán)境配置

本文通過MATLAB進(jìn)行仿真實驗評估。使用GT-ITM[21]拓?fù)渖晒ぞ邉?chuàng)建實驗所需的虛擬網(wǎng)絡(luò)和物理網(wǎng)絡(luò)拓?fù)?具體參數(shù)如表1所示。物理鏈路故障的到達(dá)服從參數(shù)為0.05的泊松分布,候選集合跳數(shù)h為4。每次實驗運(yùn)行50 000個時間單元,約有5 000個VN請求到達(dá),每2 000個時間單元進(jìn)行一次數(shù)據(jù)統(tǒng)計,取10次實驗的平均值為最終結(jié)果。

表1 實驗參數(shù)配置Table 1 Experimental parameters configuration

3.2 對比方案與性能選取

將本文提出的M-SVNE算法與文獻(xiàn)[17]中的P-SVNE算法、文獻(xiàn)[22]中的N-SVNE算法進(jìn)行對比,從VN請求接受率、長期平均收益開銷比、平均故障恢復(fù)率和平均故障恢復(fù)時延4個方面驗證本文算法的性能,上述3種算法的具體描述如表2所示。

表2 3種SVNE算法描述Table 2 Description of three SVNE algorithms

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

3.3.1 VN請求接受率

3種算法的VN請求接受率隨時間的變化情況如圖3所示。從圖3可以看出,3種算法的VN請求接受率均隨著時間的推移呈現(xiàn)逐漸降低的趨勢,當(dāng)VN的到達(dá)與離開達(dá)到平衡時,VN請求接受率趨于穩(wěn)定。N-SVNE算法的VN請求接受率最高,這是因為它使用被動恢復(fù)策略,無任何資源備份,具有充足的物理資源用于虛擬網(wǎng)絡(luò)映射。而M-SVNE算法和P-SVNE算法雖然也使用了被動恢復(fù)策略,但是這2種算法都為物理鏈路預(yù)留了備份資源,VN請求接受率相對N-SVNE算法較低。其中,M-SVNE算法能夠動態(tài)感知物理網(wǎng)絡(luò)剩余資源,并根據(jù)鏈路發(fā)生故障的數(shù)量動態(tài)調(diào)整鏈路的主、備份資源比例,使得更多的物理資源用于VNE,與P-SVNE算法相比,M-SVNE算法的VN請求接受率較高。

圖3 VN請求接受率變化曲線Fig.3 Curves of VN request acceptance rate change

3.3.2 長期平均收益開銷比

3種算法在長期平均收益開銷比方面的性能比較如圖4所示。從圖4可以看出,M-SVNE算法的長期平均收益比最終穩(wěn)定在0.59左右,高于其他2種算法。這是因為當(dāng)物理鏈路發(fā)生故障時,M-SVNE算法優(yōu)先使用帶寬資源平衡度大的備份路徑,重映射罰款高的虛擬鏈路,在減少資源碎片化,優(yōu)化剩余備份資源的同時,減少了因故障恢復(fù)失敗而導(dǎo)致的罰款,提高了長期平均收益開銷比。

圖4 長期平均收益開銷比變化曲線Fig.4 Curves of long-term average revenue-to-expense ratio change

3.3.3 平均故障恢復(fù)率

圖5是3種算法的平均故障恢復(fù)率的性能比較。從圖5可以看出,N-SVNE算法的平均故障恢復(fù)率最低,因為它無任何備份資源,當(dāng)發(fā)生鏈路故障時,使用剩余物理資源進(jìn)行鏈路重映射,而當(dāng)VN請求數(shù)量逐漸增多,導(dǎo)致沒有足夠的物理資源用于鏈路重映射,平均故障恢復(fù)率會較低。而其他2種算法為物理鏈路預(yù)留了備份資源,有更多的資源用于鏈路重映射,其中,M-SVNE算法使用多路徑選擇算法創(chuàng)建備份路由集合,集合中的備份路徑均滿足資源約束條件,并且優(yōu)先使用帶寬資源平衡度大的備份路徑,在減少資源碎片化,優(yōu)化剩余備份資源的同時,提高了平均故障恢復(fù)率。

圖5 平均故障恢復(fù)率變化曲線Fig.5 Curves of average failure recovery rate change

3.3.4 平均故障恢復(fù)時延

圖6是3種算法的平均故障恢復(fù)時延性能比較。從圖6可以看出,N-SVNE算法的平均故障恢復(fù)時延最長,這是因為N-SVNE算法無任何備份,當(dāng)鏈路發(fā)生故障時,根據(jù)剩余物理資源進(jìn)行路由選擇,實現(xiàn)鏈路重映射,花費(fèi)時間較長。而M-SVNE算法和P-SVNE算法都為物理鏈路創(chuàng)建了備份路由集合,為鏈路重映射節(jié)省了時間。其中,M-SVNE算法使用帶寬資源平衡度大的備份路徑用于虛擬鏈路重映射,進(jìn)一步縮短了路徑選擇的時間。因此,M-SVNE算法的平均故障恢復(fù)時延最短。

圖6 平均故障恢復(fù)時延變化曲線Fig.6 Curves of average failure recovery delay change

4 結(jié)束語

本文對在多鏈路故障場景下的生存性虛擬網(wǎng)絡(luò)映射問題進(jìn)行研究,提出一種面向多鏈路故障的生存性虛擬網(wǎng)絡(luò)映射算法。通過使用多路徑選擇算法為物理鏈路創(chuàng)建備份路由集,并優(yōu)先選擇帶寬資源平衡度大的路徑用于鏈路重映射,降低了物理資源碎片化的可能性,且提升了物理資源利用率。仿真結(jié)果表明,該算法提高了長期平均收益開銷比和平均故障恢復(fù)率,縮短了故障恢復(fù)時延。此外,本文僅涉及的是單域VNE,而當(dāng)涉及多域VNE時將會產(chǎn)生域內(nèi)和域間的鏈路故障問題。因此,探索多域鏈路故障的SVNE算法將是下一步的研究方向。