楊 杰,趙成貴

(云南財(cái)經(jīng)大學(xué) 信息學(xué)院,云南 昆明 650221)

網(wǎng)絡(luò)虛擬化技術(shù)[1]作為未來互聯(lián)網(wǎng)最有前景的技術(shù)之一越來越受到重視.網(wǎng)絡(luò)虛擬化技術(shù)是對(duì)目前網(wǎng)絡(luò)改善的1個(gè)重要性工具,但是實(shí)現(xiàn)這個(gè)工具還面臨著1個(gè)重大的挑戰(zhàn)：即怎樣合理高效的把物理網(wǎng)絡(luò)中的資源分配給虛擬網(wǎng)絡(luò).把虛擬網(wǎng)絡(luò)嵌入到物理網(wǎng)絡(luò)的過程稱為虛擬網(wǎng)絡(luò)嵌入(virtual network embedding, VNE)問題[2].VNE問題被證明是NP-Hard問題[4],目前學(xué)術(shù)界的研究工作重點(diǎn)是啟發(fā)式或元啟發(fā)式方法.針對(duì)VNE問題,文獻(xiàn)[5-7]利用線性規(guī)劃的方法協(xié)調(diào)節(jié)點(diǎn)和鏈路進(jìn)行求解.Chowdhury等[5-6]通過放松整數(shù)約束獲得線性規(guī)劃方法來協(xié)調(diào)節(jié)點(diǎn)和鏈路映射,采用確定性和隨機(jī)舍入方法分別提出了D-VINE和R-VINE算法來達(dá)到在線的虛擬網(wǎng)絡(luò)嵌入過程.但是由于使用了一些其他的約束條件來進(jìn)行嵌入,增加了嵌入所需時(shí)間.Hu等[7]為了使得嵌入成本最低化,通過對(duì) P-VNE 模型的雙重表述的分析提出了一個(gè)列生成過程,通過逐步的更新新路徑來解決嵌入過程.但也正是由于不斷地更新路徑,從而導(dǎo)致了算法的靈活性受限導(dǎo)致嵌入時(shí)間不斷增加.文獻(xiàn)[8-9]把VNE問題解耦為節(jié)點(diǎn)映射和鏈路映射兩部分來進(jìn)行求解.Yao等[8]設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于強(qiáng)化學(xué)習(xí)的策略網(wǎng)絡(luò),利用貪婪策略做出節(jié)點(diǎn)映射決策,通過策略梯度來實(shí)現(xiàn)基于虛擬網(wǎng)絡(luò)請(qǐng)求的歷史數(shù)據(jù)的策略網(wǎng)絡(luò)自動(dòng)優(yōu)化.Nguyen等[9]提出云網(wǎng)絡(luò)狀態(tài)下的RT-VNE算法：在節(jié)點(diǎn)映射階段利用時(shí)間窗口技術(shù)集中處理每個(gè)時(shí)間窗口內(nèi)的虛擬網(wǎng)絡(luò)請(qǐng)求,鏈路映射階段通過k-最短路徑進(jìn)行貪婪映射過程.由于采用時(shí)間窗口過程不能及時(shí)處理最新的虛擬網(wǎng)絡(luò)嵌入過程,在一定程度上降低了用戶服務(wù)質(zhì)量.

上述算法在虛擬網(wǎng)絡(luò)嵌入的不同指標(biāo)上進(jìn)行了優(yōu)化,但是這些算法往往以犧牲算法運(yùn)行時(shí)間或者以犧牲用戶體驗(yàn)度為代價(jià).因此,提高VNE算法嵌入效率,同時(shí)縮短算法運(yùn)行時(shí)間,使得用戶在最短時(shí)間內(nèi)獲得服務(wù)則是本文研究的重點(diǎn).無論是在物理網(wǎng)絡(luò)中還是在虛擬網(wǎng)絡(luò)中,不難發(fā)現(xiàn)總是存在著一些非常重要的網(wǎng)絡(luò)節(jié)點(diǎn),如果從整個(gè)網(wǎng)絡(luò)中刪除這些節(jié)點(diǎn),那么此網(wǎng)絡(luò)的完整性就會(huì)遭到破壞.基于這些思想,本文提出了核心節(jié)點(diǎn)的查找方法,利用壽紀(jì)麟等[3]提出的重權(quán)集概念,同時(shí)引入割點(diǎn)來對(duì)物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)節(jié)點(diǎn)分別進(jìn)行核心節(jié)點(diǎn)的查找,設(shè)計(jì)出相應(yīng)的算法.在節(jié)點(diǎn)映射階段,利用核心節(jié)點(diǎn)來進(jìn)行節(jié)點(diǎn)映射,與大多數(shù)的節(jié)點(diǎn)映射算法不同的是在核心節(jié)點(diǎn)的基礎(chǔ)上,不僅僅考慮到節(jié)點(diǎn)CPU資源約束問題,本文引入了節(jié)點(diǎn)的平均鏈路資源概念,對(duì)節(jié)點(diǎn)的嵌入過程同時(shí)考慮節(jié)點(diǎn)CPU資源約束和鏈路帶寬資源的約束.實(shí)驗(yàn)表明,在保證了虛擬網(wǎng)絡(luò)請(qǐng)求嵌入成功率的同時(shí),嵌入所需的時(shí)間同時(shí)也明顯優(yōu)于已有的嵌入方法.

1 網(wǎng)絡(luò)模型和問題描述

1.1 底層物理網(wǎng)絡(luò)

把位于底層的物理網(wǎng)絡(luò)抽象成無向加權(quán)圖GS=(NS,ES),NS代表物理節(jié)點(diǎn)集,ES代表物理鏈路集.其中集合中每個(gè)物理節(jié)點(diǎn)nS∈NS具有的CPU資源權(quán)值定義為c(nS),連接任意節(jié)點(diǎn)i與j的物理鏈路eS∈ES的帶寬權(quán)值定義為wi,j(eS).同時(shí),定義節(jié)點(diǎn)的平均鏈路帶寬資源w(nS).

圖1(a)給出了1個(gè)底層物理網(wǎng)絡(luò)的實(shí)例,包含5個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)和7條物理鏈路.其中,鏈路旁邊的數(shù)字代表鏈路的帶寬資源約束,節(jié)點(diǎn)附近方框中數(shù)字表示節(jié)點(diǎn)的CPU資源約束.

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

虛擬網(wǎng)絡(luò)同樣可以抽象成無向加權(quán)圖GV=(NV,EV) ,NV為虛擬節(jié)點(diǎn)集,EV為虛擬鏈路集,每個(gè)虛擬節(jié)點(diǎn)和節(jié)點(diǎn)之間的虛擬鏈路都具有相應(yīng)的權(quán)值(即c(nV)和wi,j(eV))表示它所需要的資源.虛擬網(wǎng)絡(luò)節(jié)點(diǎn)n的平均鏈路帶寬資源用w(nV)表示.圖1(b)與圖1(c)分別列舉除了2個(gè)不同的虛擬網(wǎng)絡(luò).

1.3 VNE問題描述

當(dāng)有一個(gè)或者多個(gè)虛擬網(wǎng)絡(luò)發(fā)出請(qǐng)求服務(wù)時(shí),即虛擬網(wǎng)絡(luò)請(qǐng)求,網(wǎng)絡(luò)服務(wù)商需要利用已有的物理網(wǎng)絡(luò)來分配相應(yīng)的資源用以支持虛擬網(wǎng)絡(luò)的運(yùn)行.把虛擬網(wǎng)絡(luò)嵌入定義為GV=(NV,EV)→GS=(NS,ES),這個(gè)過程包括節(jié)點(diǎn)映射和鏈路映射兩部分.圖1(b)和圖1(c)給出了2個(gè)不同拓?fù)浣Y(jié)構(gòu)的虛擬網(wǎng)絡(luò),當(dāng)這2個(gè)虛擬網(wǎng)絡(luò)發(fā)出請(qǐng)求后，在物理節(jié)點(diǎn)CPU資源和物理鏈路帶寬資源滿足網(wǎng)絡(luò)請(qǐng)求所需要的資源的情況下：虛擬網(wǎng)絡(luò)1的3個(gè)虛擬節(jié)點(diǎn)a、b、c被映射到物理網(wǎng)絡(luò)中的節(jié)點(diǎn)C、D、A中,虛擬網(wǎng)絡(luò)鏈路(a,b)和(a,c)被映射到物理鏈路(C,D)和(C,A)中.虛擬網(wǎng)絡(luò)2中的3個(gè)虛擬節(jié)點(diǎn)d、e、f分別被映射到物理節(jié)點(diǎn)B、A、E中,虛擬鏈路(d,e),(d,f)以及(e,f)被映射到物理鏈路(B,A),(B,E)和(A,E)中.其中,節(jié)點(diǎn)c和e占用節(jié)點(diǎn)A的CPU資源為35 < 80.其它的物理節(jié)點(diǎn)CPU和鏈路帶寬資源在2個(gè)虛擬網(wǎng)絡(luò)嵌入后仍有剩余,所以2個(gè)虛擬網(wǎng)絡(luò)可以嵌入到物理網(wǎng)絡(luò)中并使用.

2 基于核心節(jié)點(diǎn)的VNE算法

基于核心節(jié)點(diǎn)的VNE算法以查找網(wǎng)絡(luò)圖中的重要節(jié)點(diǎn)為首要任務(wù),通過查找網(wǎng)絡(luò)圖的割點(diǎn)集以及重權(quán)節(jié)點(diǎn)集來構(gòu)建核心節(jié)點(diǎn)集；最后,通過考慮鏈路帶寬資源約束對(duì)于VNE的影響而引入核心節(jié)點(diǎn)的平均鏈路帶寬資源,以此來提高節(jié)點(diǎn)映射成功后的鏈路映射階段的成功率.

2.1 割點(diǎn)集

本文引入了割點(diǎn)集的概念,來對(duì)網(wǎng)絡(luò)形象化的抽象為無向圖,從而查找到網(wǎng)絡(luò)中至關(guān)重要的節(jié)點(diǎn)的集合并保存后續(xù)使用.如圖2(a)所示的1個(gè)簡(jiǎn)易網(wǎng)絡(luò)圖,我們可以觀察到.當(dāng)刪除a節(jié)點(diǎn)后,這個(gè)網(wǎng)絡(luò)會(huì)被分割成如圖2(b)所示的有2個(gè)連通分支({b,d,e}和{c})的情形,圖的連通性則被破壞.同樣的,如果刪除節(jié)點(diǎn)b,則網(wǎng)絡(luò)圖會(huì)被分割為如圖2(c)所示的{a,c}、syggg00和{e}3個(gè)部分,圖的連通性同樣被破壞.

在無向連通圖G= (V,E)中,V和E分別表示圖G的頂點(diǎn)集和邊集.定義ω(G)為圖G的連通分支數(shù),若?cn∈V(G),使得ω(G-cn)>1,則cn稱作圖G的1個(gè)割點(diǎn).本文設(shè)計(jì)的查找網(wǎng)絡(luò)的割點(diǎn)集的算法是在著名的Tarjan算法的基礎(chǔ)上進(jìn)行改進(jìn),并利用深度優(yōu)先搜索來對(duì)網(wǎng)絡(luò)圖中各個(gè)節(jié)點(diǎn)進(jìn)行割點(diǎn)判斷.查找核心節(jié)點(diǎn)集算法具體步驟如下.

Step 1 對(duì)每1個(gè)物理/虛擬網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行初始化標(biāo)記,從網(wǎng)絡(luò)中取出一個(gè)節(jié)點(diǎn)n.

Step 2 根據(jù)深度優(yōu)先搜索思想進(jìn)行深度優(yōu)先搜索,并記錄相應(yīng)的信息：如遍歷順序,可到達(dá)節(jié)點(diǎn)的最小遍歷順序值等.

Step 3 對(duì)于網(wǎng)絡(luò)圖中的每1條以n為起點(diǎn)的邊(n,v),如果v被訪問過,進(jìn)行Step 4.否則跳轉(zhuǎn)Step 2.

Step 4 若v節(jié)點(diǎn)可到達(dá)節(jié)點(diǎn)的最小遍歷順序值x1不小于n節(jié)點(diǎn)的遍歷順序值x2,核心節(jié)點(diǎn)集C=Cn.否則更新n的可到達(dá)節(jié)點(diǎn)的最小遍歷順序值為min(x1,x2).

割點(diǎn)是1個(gè)圖中起著至關(guān)重要的節(jié)點(diǎn).但是在實(shí)際情況中,大多數(shù)情況下1個(gè)圖割點(diǎn)的數(shù)量非常少,甚至可能為0.為了避免圖中割點(diǎn)為0情況下導(dǎo)致節(jié)點(diǎn)嵌入過程直接失敗,引入重權(quán)集來進(jìn)行核心節(jié)點(diǎn)的優(yōu)化.

2.2 重權(quán)集

把相應(yīng)的網(wǎng)絡(luò)抽象成無向加權(quán)圖G=(V(G),E(G)),其中V(G)={n1,n2,…,nm} .考慮到鏈路帶寬資源約束對(duì)于嵌入的影響,我們引入重權(quán)集[3]的概念來進(jìn)行對(duì)網(wǎng)絡(luò)中重權(quán)節(jié)點(diǎn)的查找.其中,網(wǎng)絡(luò)中節(jié)點(diǎn)ni的CPU資源約束表示為c(ni).

Step 1 根據(jù)公式計(jì)算物理/虛擬網(wǎng)絡(luò)圖的平均CPU權(quán)數(shù).對(duì)于網(wǎng)絡(luò)圖中的每1個(gè)節(jié)點(diǎn)進(jìn)行Step 2.

Step 2 對(duì)于節(jié)點(diǎn)n,判斷其CPU資源是否大于A,大于則重權(quán)集WeightSubset=WeightSubset∪n.

Step 3 核心節(jié)點(diǎn)集C=C∪WeightSubset.

2.3 核心節(jié)點(diǎn)優(yōu)化

核心節(jié)點(diǎn)進(jìn)行查找并統(tǒng)計(jì)后,單一的考慮節(jié)點(diǎn)CPU資源的映射算法并不能夠比較好的進(jìn)行虛擬網(wǎng)絡(luò)嵌入.在節(jié)點(diǎn)映射完成后,鏈路映射過程中鏈路的帶寬則是決定著虛擬網(wǎng)絡(luò)能否嵌入成功的關(guān)鍵因素.單一的考慮節(jié)點(diǎn)的CPU資源約束已經(jīng)不能適應(yīng)VNE的實(shí)際應(yīng)用需求,因此在節(jié)點(diǎn)映射階段加入對(duì)鏈路映射階段的預(yù)處理是必要的.

w(f)=k1*(wf,d+wf,e)/2+k2*wc,d+k3*(wa,c+wb,c)/2.

(1)

w(o)=k1*(wo,p+wo,r+wo,q)/3.

(2)

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)方案設(shè)置

文中實(shí)驗(yàn)算法依托慕尼黑大學(xué)Beck等提供的模擬框架Alevin[12]進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)中的物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)均在此框架下動(dòng)態(tài)隨機(jī)生成,其中物理網(wǎng)絡(luò)設(shè)置100個(gè)節(jié)點(diǎn),節(jié)點(diǎn)計(jì)算CPU資源和鏈路的帶寬資源均在[10,100]隨機(jī)分布.虛擬網(wǎng)絡(luò)設(shè)置為10個(gè),每個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)在[3,15]隨機(jī)分布,節(jié)點(diǎn)的CPU資源在[1,10]隨機(jī)分布,鏈路帶寬資源在[1,10]隨機(jī)分布.物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)相鄰節(jié)點(diǎn)之間生成鏈路的可能性均為0.5.在實(shí)驗(yàn)中將對(duì)比算法DViNE-SP,RW-MM-SP,GAR-SP 3個(gè)算法,如表1所示.為了避免實(shí)驗(yàn)結(jié)果的偶然性,將進(jìn)行50次循環(huán)實(shí)驗(yàn).

表1 實(shí)驗(yàn)對(duì)比的算法

3.2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證BC-VNE算法性能,本文使用虛擬網(wǎng)絡(luò)請(qǐng)求的接受率,運(yùn)行時(shí)間,嵌入成本與收益的比重,物理節(jié)點(diǎn)使用情況4個(gè)性能參數(shù)來對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià).根據(jù)實(shí)驗(yàn)數(shù)據(jù)結(jié)果分析如下所示.

1) BC-VNE相比于其他算法,提高了嵌入效率.圖4給出了每次對(duì)比算法實(shí)驗(yàn)的運(yùn)行時(shí)間,在圖中相比于其他2種算法,BC-VNE算法和GAR-SP算法明顯在運(yùn)行時(shí)間上很短.

同時(shí),結(jié)合表2給出的算法50次實(shí)驗(yàn)平均結(jié)果中實(shí)驗(yàn)的平均運(yùn)行時(shí)間,可以看出在同樣的條件下,DViNE-SP算法運(yùn)行時(shí)間為85.34 s, RW-MM-SP算法運(yùn)行時(shí)間為55.10 s,BC-VNE算法的運(yùn)行時(shí)間為0.15 s,相比于這2種算法BC-VNE運(yùn)行時(shí)間縮短了100倍以上.同時(shí),BC-VNE算法相比于GAR-SP算法,運(yùn)行時(shí)間也縮短了大約1倍.所以在相同條件下,BC-VNE算法運(yùn)行時(shí)間少于其他算法,極大的提高了VNE的運(yùn)行效率并且能夠減少用戶請(qǐng)求服務(wù)時(shí)間從而提供更高效的用戶服務(wù)質(zhì)量.

表2 對(duì)比算法50次實(shí)驗(yàn)平均結(jié)果

2) BC-VNE在提高嵌入效率的條件下,同時(shí)也提高了虛擬網(wǎng)絡(luò)請(qǐng)求的接受率.圖5給出了每次實(shí)驗(yàn)的虛擬網(wǎng)絡(luò)請(qǐng)求接受率的結(jié)果,圖中,BC-VNE算法的接受率明顯優(yōu)于GAR-SP算法和DVINE-SP算法接受率.從表2的中各個(gè)算法平均的接受率來看,BC-VNE算法的接受率為45.20%優(yōu)于RW-MM-SP算法接受率43.40%.

結(jié)合圖5和表2分析,而雖然在一定條件下BC-VNE算法的接受率不如RW-MM-SP算法的接受率,但是總體來說BC-VNE算法的虛擬網(wǎng)絡(luò)請(qǐng)求接受率要優(yōu)于后者.這是因?yàn)楸疚脑O(shè)計(jì)的BC-VNE算法是基于核心節(jié)點(diǎn)的嵌入算法,一旦核心節(jié)點(diǎn)的CPU資源全部被使用,則后續(xù)的虛擬網(wǎng)絡(luò)請(qǐng)求就不能利用核心節(jié)點(diǎn),則可能造成嵌入失敗.雖然會(huì)存在偶然條件下的嵌入失敗過程,但是整體來說,BC-VNE不僅提高了嵌入效率,而且使得嵌入質(zhì)量也取得了一定的提升.

3) BC-VNE算法相比于其他算法,具有更好的綜合效率.圖6給出了算法實(shí)驗(yàn)的成本與收益的比率,可以看出在BC-VNE的表現(xiàn)比GAR-SP和DViNE-SP要好.結(jié)合表2中平均實(shí)驗(yàn)結(jié)果數(shù)據(jù)可知,BC-VNE和RW-MM-SP算法的成本/收益比率相差不大,但是總體上BC-VNE表現(xiàn)更加出色.

圖7和圖8分別給出了VNE算法節(jié)點(diǎn)使用率和鏈路使用率情況,可以看出BC-VNE算法能夠極大化節(jié)點(diǎn)的使用率,但是在鏈路使用率上表現(xiàn)欠佳.這是由于BC-VNE算法時(shí)基于核心節(jié)點(diǎn)的啟發(fā)式嵌入算法,主要考慮節(jié)點(diǎn)的映射過程,從而在鏈路使用率方面表現(xiàn)不如DViNE-SP和RW-MM-SP算法.其中,在節(jié)點(diǎn)(鏈路)使用率比較上,GAR-SP算法由于多次實(shí)驗(yàn)的嵌入成功率為0無參考性而不作節(jié)點(diǎn)(鏈路)使用率比較.結(jié)合圖4～圖8分析,在虛擬網(wǎng)絡(luò)請(qǐng)求接受率上BC-VNE和RW-MM-SP算法比其他2種VNE算法更加符合網(wǎng)絡(luò)服務(wù)商利益需求.同時(shí), BC-VNE算法和RW-MM-SP算法兩者的成本/收益、節(jié)點(diǎn)利用率、接受率這些指標(biāo)相差不大,但是BC-VNE算法在算法的運(yùn)行時(shí)間上相比于RW-MM-SP更加高效,能夠使得用戶更快的得到所需要的網(wǎng)絡(luò)服務(wù).所以相比于其他3種算法,在不降低虛擬網(wǎng)絡(luò)請(qǐng)求接受率和其他評(píng)價(jià)指標(biāo)的情況下,BC-VNE算法能夠取得比較優(yōu)秀的虛擬網(wǎng)絡(luò)嵌入結(jié)果,具有更好的綜合性能.

4 結(jié)語

本文研究了基于核心節(jié)點(diǎn)的VNE算法,針對(duì)網(wǎng)絡(luò)中核心節(jié)點(diǎn)的查找做出相應(yīng)的算法設(shè)計(jì).實(shí)驗(yàn)表明,BC-VNE算法通過利用割點(diǎn)集和重權(quán)集的核心節(jié)點(diǎn)的嵌入,縮短了虛擬網(wǎng)絡(luò)嵌入所需要的時(shí)間,同時(shí)提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率.算法所涉及的核心節(jié)點(diǎn)利用割點(diǎn)和重權(quán)集查找具有一定的局限性,不能夠很好地代表整個(gè)網(wǎng)絡(luò)圖的重要節(jié)點(diǎn).為此,在后續(xù)工作中,將進(jìn)一步研究發(fā)現(xiàn)網(wǎng)絡(luò)中更重要的核心節(jié)點(diǎn)用來進(jìn)行虛擬網(wǎng)絡(luò)嵌入.