面向動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬網(wǎng)絡(luò)映射算法

苑 迎，王 聰，王翠榮，宋 欣，呂艷霞

(1.東北大學(xué)秦皇島分校 計(jì)算中心，河北 秦皇島 066004； 2.東北大學(xué)秦皇島分校 計(jì)算機(jī)與通信工程學(xué)院，河北 秦皇島 066004)

(*通信作者電子郵箱yuanying1121@gmail.com)

面向動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬網(wǎng)絡(luò)映射算法

苑 迎1*，王 聰2，王翠榮2，宋 欣1，呂艷霞2

(1.東北大學(xué)秦皇島分校 計(jì)算中心，河北 秦皇島 066004； 2.東北大學(xué)秦皇島分校 計(jì)算機(jī)與通信工程學(xué)院，河北 秦皇島 066004)

(*通信作者電子郵箱yuanying1121@gmail.com)

針對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求資源動(dòng)態(tài)變化的實(shí)際情況，提出了面向動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬網(wǎng)絡(luò)映射(DVNR-VNE)算法。以混合線性規(guī)劃理論為基礎(chǔ)，采用多隊(duì)列的方式分別對(duì)不同類型的虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行預(yù)處理，建立了以最小化映射代價(jià)和最小遷移代價(jià)為優(yōu)化目標(biāo)的映射模型，優(yōu)先映射需要釋放資源的請(qǐng)求以獲得更多的資源支持其他的虛擬網(wǎng)絡(luò)，對(duì)新到來的虛擬網(wǎng)絡(luò)請(qǐng)求采用優(yōu)化后的虛擬網(wǎng)絡(luò)映射(WD-VNE)算法進(jìn)行映射。仿真實(shí)驗(yàn)表明，該算法降低了鏈路映射成本和遷移成本并獲得了較高的虛擬網(wǎng)絡(luò)請(qǐng)求接受率。

網(wǎng)絡(luò)虛擬化；虛擬網(wǎng)絡(luò)；虛擬網(wǎng)絡(luò)映射；動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，互聯(lián)網(wǎng)上新型應(yīng)用層出不窮，現(xiàn)有的網(wǎng)絡(luò)架構(gòu)很難跟上互聯(lián)網(wǎng)新型應(yīng)用的發(fā)展，在某種程度上出現(xiàn)了僵化的現(xiàn)象。網(wǎng)絡(luò)虛擬化是解決網(wǎng)絡(luò)結(jié)構(gòu)僵化的一項(xiàng)重要技術(shù)，網(wǎng)絡(luò)虛擬化技術(shù)允許多個(gè)異構(gòu)的虛擬網(wǎng)絡(luò)共享同一個(gè)物理網(wǎng)絡(luò)資源[1]。它將傳統(tǒng)意義上的互聯(lián)網(wǎng)提供商分成了基礎(chǔ)設(shè)施提供商(Infrastructure Provider, INP)和服務(wù)提供商(Service Provider, SP)兩個(gè)部分[2]。在網(wǎng)絡(luò)虛擬化環(huán)境下，基礎(chǔ)設(shè)施提供商部署和管理底層網(wǎng)絡(luò)資源，通過可編程接口為不同的服務(wù)提供商提供資源。服務(wù)提供商租用基礎(chǔ)設(shè)施提供商的底層網(wǎng)絡(luò)資源并創(chuàng)建虛擬網(wǎng)絡(luò)，獲得個(gè)性化的端到端的網(wǎng)絡(luò)服務(wù)[3]。虛擬網(wǎng)絡(luò)映射(Virtual Network Embedding, VNE)技術(shù)能有效地利用共享的物理網(wǎng)絡(luò)資源，最大化物理網(wǎng)絡(luò)資源的利用率，提高服務(wù)質(zhì)量，降低網(wǎng)絡(luò)運(yùn)營(yíng)成本[4]。在虛擬化環(huán)境下，大多數(shù)研究?jī)H針對(duì)虛擬網(wǎng)請(qǐng)求是固定不變的情況設(shè)計(jì)有效的虛擬網(wǎng)絡(luò)映射算法，但是有時(shí)虛擬網(wǎng)絡(luò)的資源請(qǐng)求數(shù)量甚至拓?fù)浣Y(jié)構(gòu)會(huì)隨著時(shí)間的變化而發(fā)生變化(如：在線游戲、分布式計(jì)算等)，需要底層的物理網(wǎng)絡(luò)動(dòng)態(tài)地調(diào)整資源分配的方案及時(shí)應(yīng)對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求的變化。底層的物理網(wǎng)絡(luò)也會(huì)因?yàn)槟承┨厥馇闆r(如：網(wǎng)絡(luò)部件故障、自然災(zāi)害、黑客攻擊等)的發(fā)生而影響到正在運(yùn)行的虛擬網(wǎng)絡(luò)，服務(wù)提供商需根據(jù)物理網(wǎng)絡(luò)資源的變化情況及時(shí)地調(diào)整映射方案以滿足虛擬網(wǎng)絡(luò)的正常運(yùn)行。

虛擬網(wǎng)絡(luò)映射問題是一個(gè)NP-hard問題。即便已經(jīng)確定了虛擬節(jié)點(diǎn)的位置，基于帶寬約束的虛擬鏈路映射問題也是NP-hard問題[5]。目前大多數(shù)研究?jī)H針對(duì)虛擬網(wǎng)請(qǐng)求是固定不變的情況設(shè)計(jì)有效的虛擬網(wǎng)絡(luò)映射算法，針對(duì)動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的映射算法還較少。

文獻(xiàn)[6]提出了一種分布式的自治虛擬資源分配算法，在該算法中物理節(jié)點(diǎn)能夠識(shí)別某條物理鏈路的過載流量，并通過虛擬節(jié)點(diǎn)遷移盡可能地減少物理鏈路的跳數(shù)；但該機(jī)制沒有給出遷移虛擬節(jié)點(diǎn)的方法。文獻(xiàn)[7]提出了一種根據(jù)物理節(jié)點(diǎn)平均負(fù)載差異度來遷移虛擬節(jié)點(diǎn)的方法，通過綜合影響因子來選擇虛擬節(jié)點(diǎn)適合的遷移節(jié)點(diǎn)以減少虛擬節(jié)點(diǎn)遷移對(duì)物理鏈路帶寬和時(shí)延的影響；但該算法只是動(dòng)態(tài)地調(diào)整了物理節(jié)點(diǎn)間的負(fù)載沒有考慮物理鏈路的負(fù)載平衡。文獻(xiàn)[8]提出了一種針對(duì)動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的重配置方法；但是該算法僅考慮了當(dāng)一個(gè)運(yùn)行中的VN(Virtual Network)請(qǐng)求發(fā)生變化時(shí)，如何以最小的成本實(shí)現(xiàn)對(duì)該VN的重配置。文獻(xiàn)[9]從工作負(fù)載概率角度考慮虛擬網(wǎng)絡(luò)映射中的動(dòng)態(tài)資源分配問題，為每個(gè)虛擬網(wǎng)絡(luò)設(shè)定一個(gè)容忍閾值，建立了一個(gè)兩階段的虛擬網(wǎng)絡(luò)映射算法，然后以共享方式映射虛擬網(wǎng)絡(luò)節(jié)點(diǎn)，物理節(jié)點(diǎn)/鏈路上的空閑資源塊由所有虛擬節(jié)點(diǎn)/鏈路按需共享使用，當(dāng)資源飽和時(shí)，利用貪心算法為不滿足需求的虛擬節(jié)點(diǎn)鏈路尋找候選映射目標(biāo)。文獻(xiàn)[10]針對(duì)光電混合數(shù)據(jù)中心網(wǎng)絡(luò)的特點(diǎn)，針對(duì)動(dòng)態(tài)到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求，利用非線性優(yōu)化理論對(duì)混合數(shù)據(jù)中心的虛擬網(wǎng)絡(luò)映射問題進(jìn)行建模，然后使用改進(jìn)的貪心算法對(duì)模型進(jìn)行求解，獲得了更好的求解速度；但沒有考慮已映射虛擬網(wǎng)絡(luò)的資源變化問題。

本文提出了面向動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬網(wǎng)絡(luò)映射(Virtual Network Embedding based on Dynamic Virtual Network Requests, DVNR-VNE)算法，將虛擬網(wǎng)絡(luò)請(qǐng)求分為三類：一類是已經(jīng)映射的虛擬網(wǎng)絡(luò)請(qǐng)求，它所請(qǐng)求的節(jié)點(diǎn)或鏈路資源因?yàn)椴恍枰蝗∠?；第二類是已?jīng)映射的虛擬網(wǎng)絡(luò)請(qǐng)求，它的部分虛擬網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路所請(qǐng)求的資源增加；第三類是新到來的虛擬網(wǎng)絡(luò)請(qǐng)求。以最小化映射代價(jià)和最小遷移代價(jià)為優(yōu)化目標(biāo)，采用多隊(duì)列的方式分別對(duì)不同類型的虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行預(yù)處理，優(yōu)先映射需要釋放資源的請(qǐng)求以獲得更多的資源支持其他的虛擬網(wǎng)絡(luò)，對(duì)新到來的虛擬網(wǎng)絡(luò)請(qǐng)求采用優(yōu)化后的WD-VNE(WinDow-Virtual Network Embedding)算法[11]進(jìn)行映射。實(shí)驗(yàn)表明，該算法可以降低映射成本和遷移成本并且提高虛擬網(wǎng)絡(luò)請(qǐng)求的接受率。

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

首先建立了物理網(wǎng)絡(luò)模型、動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求模型以及相應(yīng)的虛擬網(wǎng)絡(luò)映射問題的模型，進(jìn)而定義了節(jié)點(diǎn)綜合能力和影響因子，然后給出了系統(tǒng)模型和優(yōu)化目標(biāo)。

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

1.2 虛擬網(wǎng)絡(luò)請(qǐng)求

1.3 虛擬網(wǎng)絡(luò)映射問題模型

虛擬網(wǎng)絡(luò)映射問題可以被看作一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求(Virtual Network Request, VNR)到底層物理網(wǎng)絡(luò)S的映射Γ，通過下式進(jìn)行描述：

(1)

其中NS*?NS,PS*?PS，虛擬網(wǎng)絡(luò)請(qǐng)求中的每個(gè)虛擬節(jié)點(diǎn)到物理網(wǎng)絡(luò)節(jié)點(diǎn)的映射由ΓN表示：

(2)

進(jìn)一步，對(duì)于ΓN(nv)∈NS*,?nv∈NV，加入資源約束條件后的映射可以被描述為：

RCPU(nv)≤CCPU(ΓN(nv))

(3)

(4)

其中：RCPU(nv)表示虛擬節(jié)點(diǎn)nv請(qǐng)求的CPU資源的約束，CCPU(ΓN(nv))表示目標(biāo)物理節(jié)點(diǎn)空閑的CPU資源。CPU(ΓN(nv))表示物理節(jié)點(diǎn)總的CPU資源。對(duì)于物理節(jié)點(diǎn)來說，空閑CPU資源等于總資源減去所有已分配資源。

對(duì)于虛擬邊的映射，根據(jù)其兩端虛擬節(jié)點(diǎn)被映射的位置，在物理網(wǎng)絡(luò)中可通過不分流的路徑映射或者基于多商品流的路徑分割映射，其數(shù)學(xué)描述為：

(5)

對(duì)于?lv(i,j)∈LV，PS是物理網(wǎng)絡(luò)S上的任意路徑，即ΓL(lv)?PS(ΓN(i),ΓN(j))，并且虛擬鏈路的映射要滿足帶寬約束：

Rbw(lv)≤Cbw(p); ?p∈ΓL(lv)

(6)

(7)

(8)

DIS(nv,ΓN(nv))≤γ

(9)

其中：Rbw(lv)是虛擬鏈路lv請(qǐng)求的帶寬資源額度；Cbw(p)表示底層物理網(wǎng)絡(luò)鏈路的空閑資源，取路徑P上空閑帶寬資源最小的鏈路的值；P(q,r)表示物理鏈路中，節(jié)點(diǎn)q和r之間的路徑的集合；bw(ls)表示物理網(wǎng)絡(luò)鏈路總的帶寬容量。

1.4 節(jié)點(diǎn)綜合能力

為了衡量節(jié)點(diǎn)優(yōu)劣從而判斷映射目標(biāo)，本文引入了節(jié)點(diǎn)綜合能力作為判定依據(jù)，其數(shù)學(xué)描述為：

(10)

其中：nnb是節(jié)點(diǎn)n的鄰居節(jié)點(diǎn)，DIS(n,nnb)是節(jié)點(diǎn)n到nnb的路徑跳數(shù)。

1.5 影響因子

鑒于動(dòng)態(tài)虛擬網(wǎng)絡(luò)的映射需要重配置機(jī)制支持，因此涉及虛擬節(jié)點(diǎn)的遷移，那么也就需要判斷物理節(jié)點(diǎn)上已駐留的虛擬節(jié)點(diǎn)遷移代價(jià)，因此本文引入了虛擬節(jié)點(diǎn)的影響因子，其表達(dá)式為：

ζ=Z(ns)?φ(ns)/Z(nv)

(11)

影響因子表示物理節(jié)點(diǎn)上駐留的虛擬節(jié)點(diǎn)對(duì)該物理節(jié)點(diǎn)的重要程度，其中φ(ns)是底層物理節(jié)點(diǎn)ns的利用率，影響因子ζ的值越大其越重要。

1.6 映射成本和接受率

本文節(jié)點(diǎn)資源用CPU能力表示，鏈路資源用帶寬表示。與文獻(xiàn)[4,12]類似，首先給出成本和接受率的定義。

定義1 成本。底層物理網(wǎng)絡(luò)分配給一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的CPU資源和帶寬資源之和。用C(GV)表示，形式化為：

(12)

定義2 接受率。虛擬網(wǎng)絡(luò)請(qǐng)求的接受率表示到t時(shí)刻虛擬網(wǎng)絡(luò)請(qǐng)求被接受的概率，形式化為：

(13)

其中：VNRA表示被物理網(wǎng)絡(luò)成功映射的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量；VNR表示到t時(shí)刻到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求的總數(shù)量。

2 系統(tǒng)模型和優(yōu)化目標(biāo)

對(duì)于動(dòng)態(tài)虛擬網(wǎng)絡(luò)映射問題，本文利用混合線性規(guī)劃(MixedLinearProgramming,MLP)理論，建立以最小開銷為優(yōu)化目標(biāo)的模型。需要注意的是，在模型及后續(xù)算法的設(shè)計(jì)中利用了可重用特性，即允許同一虛擬網(wǎng)絡(luò)的不同虛擬節(jié)點(diǎn)可以被映射到同一物理網(wǎng)絡(luò)節(jié)點(diǎn)上，這樣可以節(jié)省分配的帶寬資源[13]。

映射開銷指為了承載虛擬網(wǎng)絡(luò)，物理網(wǎng)絡(luò)所分配的所有資源，包括節(jié)點(diǎn)計(jì)算資源和鏈路帶寬資源以及由于映射方案調(diào)整所需要的遷移虛擬節(jié)點(diǎn)及鏈路的開銷，即：

COST(V)=cost(nv)+cost(lv)+costmig

(14)

虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)映射開銷為其計(jì)算資源，即所占用CPU資源的總和：

cost(nv)=RCPU(nv)

(15)

虛擬網(wǎng)絡(luò)的鏈路映射開銷為所有物理路徑上所占用的帶寬資源的總和：

(16)

當(dāng)i=j時(shí)，表示虛擬鏈路w利用可重用機(jī)制被映射到內(nèi)存中，即虛擬鏈路ij并沒有占用實(shí)際物理鏈路帶寬；i≠j時(shí)該虛擬鏈路才被映射到實(shí)際物理鏈路上并被分配了相應(yīng)帶寬資源。

對(duì)于虛擬網(wǎng)絡(luò)來說，遷移開銷表示為：

costmig=MCPU(nv)+Mbw(lt)

(17)

其中MCPU(nv)和Mbw(lw)分別表示遷移節(jié)點(diǎn)和遷移鏈路的代價(jià)。對(duì)于物理網(wǎng)絡(luò)來說，無論虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)被映射到哪個(gè)物理節(jié)點(diǎn)，其計(jì)算資源即CPU資源是必須分配且額度不變的，因此在考慮最小映射開銷時(shí)，CPU資源的開銷可以被省略，那么動(dòng)態(tài)虛擬網(wǎng)絡(luò)映射問題的優(yōu)化目標(biāo)可以被定義為：

min (cost(lv)+costmig)

(18)

即系統(tǒng)的總體目標(biāo)為最小化映射該虛擬網(wǎng)絡(luò)的鏈路開銷與為了映射該虛擬網(wǎng)絡(luò)產(chǎn)生的虛擬節(jié)點(diǎn)和虛擬鏈路的遷移代價(jià)之和。

3 DVNR-VNE算法

針對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求是動(dòng)態(tài)的這一特點(diǎn)，首先建立請(qǐng)求提交的等待隊(duì)列模型。在請(qǐng)求到達(dá)執(zhí)行映射算法尋找可行的資源分配方案前明確虛擬網(wǎng)絡(luò)請(qǐng)求的分類并加入相應(yīng)的隊(duì)列。本文提出的DVNR-VNE算法使用了三個(gè)隊(duì)列：r_new、r_increase和r_decrease。根據(jù)1.2節(jié)中參數(shù)η和R設(shè)置，本文將動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求分為三類，分別對(duì)應(yīng)算法中的三個(gè)隊(duì)列。當(dāng)η=1時(shí)，說明虛擬網(wǎng)絡(luò)請(qǐng)求是新的隊(duì)列，將被加入隊(duì)列r_new。當(dāng)η=0時(shí)，進(jìn)一步判斷R的值，如果該虛擬網(wǎng)絡(luò)請(qǐng)求增加節(jié)點(diǎn)或者資源，則將其加入隊(duì)列r_increase；如果該虛擬網(wǎng)絡(luò)請(qǐng)求減少節(jié)點(diǎn)或者資源時(shí)，將其加入隊(duì)列r_decrease。

在三個(gè)隊(duì)列的處理順序上，為了盡可能充分地利用資源，應(yīng)當(dāng)首先處理隊(duì)列r_decrease中的請(qǐng)求，使其釋放不需要的資源。然后處理r_increase中的請(qǐng)求，因?yàn)橐M可能地響應(yīng)已運(yùn)行的虛擬網(wǎng)絡(luò)請(qǐng)求對(duì)于資源增加或節(jié)點(diǎn)增加的需求，以盡量縮短其生命周期并保證用戶的服務(wù)質(zhì)量(Quality of Service, QoS)需求。最后才嘗試處理隊(duì)列r_new中的新增虛擬網(wǎng)絡(luò)請(qǐng)求，因?yàn)樽屛幢挥成涞奶摂M網(wǎng)絡(luò)請(qǐng)求繼續(xù)等待要強(qiáng)于拒絕已運(yùn)行虛擬網(wǎng)絡(luò)請(qǐng)求的資源增加請(qǐng)求。

具體的DVNR-VNE算法的詳細(xì)描述如算法1所示。

算法1DVNR-VNE算法。

輸入：物理網(wǎng)絡(luò)GS=(NS,ASN,LS,ASL);虛擬網(wǎng)絡(luò)請(qǐng)求VNR=(GV,Ta,t,η,R,κ)。

1)

根據(jù)虛擬網(wǎng)絡(luò)請(qǐng)求參數(shù)將其加入到請(qǐng)求提交的等待隊(duì)列中；

2)

for每個(gè)r_decrease中的虛擬網(wǎng)絡(luò)請(qǐng)求 do

3)

釋放其請(qǐng)求釋放的節(jié)點(diǎn)和鏈路資源；

4)

endfor

5)

for每個(gè)r_increase中的虛擬網(wǎng)絡(luò)請(qǐng)求do

6)

if如果該VNR請(qǐng)求增加資源then

7)

if如果需要增加節(jié)點(diǎn)資源then

8)

for每個(gè)要增加資源的節(jié)點(diǎn)do

9)

if目標(biāo)物理節(jié)點(diǎn)滿足RCPU(nv)≤CCPU(ΓN(nv))then

10)

為該節(jié)點(diǎn)資源增加請(qǐng)求的資源；

11)

else調(diào)用vnmig1()函數(shù)找到可遷移節(jié)點(diǎn)，釋放需遷移節(jié)點(diǎn)已占用的資源并對(duì)其進(jìn)行重新映射；

12)

endif

13)

endfor

14)

endif

15)

if需要增加鏈路資源then

16)

for每個(gè)需要增加資源的虛擬鏈路do

17)

if目標(biāo)物理鏈路滿足Rbw(lv)≤Cbw(p)then

18)

為該虛擬鏈路分配增加請(qǐng)求的資源；

19)

else嘗試路徑分割映射，即利用其他物理路徑滿足該資源增加請(qǐng)求并使得cost(lv)最?。?/p>

20)

end if

21)

end for

22)

end if

23)

end if

24)

if 該虛擬網(wǎng)絡(luò)請(qǐng)求申請(qǐng)?jiān)黾庸?jié)點(diǎn) then

25)

for 每個(gè)需要被增加的虛擬節(jié)點(diǎn) do

26)

從物理網(wǎng)絡(luò)節(jié)點(diǎn)中找到空閑資源大于該虛擬節(jié)點(diǎn)請(qǐng)求的資源綜合能力Z(n)最大，并且與相應(yīng)虛擬節(jié)點(diǎn)的距離滿足式(9)的約束的物理網(wǎng)絡(luò)節(jié)點(diǎn)加入集合F；

27)

ifF非空 then

28)

找到cost(lv)最小的映射方案并映射該節(jié)點(diǎn)使用k-shortest path 算法對(duì)相應(yīng)的虛擬鏈路進(jìn)行路徑分割映射；

29)

else 調(diào)用vnmig2()重新映射節(jié)點(diǎn)，嘗試對(duì)虛擬鏈路進(jìn)行遷移并釋放其所占資源；

30)

end if

31)

end for

32)

end if

33)

end for

34)

ifr_increase已經(jīng)為空或隊(duì)列中所有的虛擬網(wǎng)絡(luò)請(qǐng)求已被嘗試分配5次 then

35)

for 隊(duì)列r_new中的前processcount個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求do

36)

利用文獻(xiàn)[11]中WD-VNE映射算法映射虛擬網(wǎng)絡(luò)請(qǐng)求；

37)

if映射成功then

38)

將其從r_new中移除；

39)

endif

40)

endfor

41)

endif

在算法1中，參數(shù)processcount是WD-VNE映射算法中的滑動(dòng)窗口值，即先處理若干個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，目的是將滑動(dòng)窗口中虛擬網(wǎng)絡(luò)請(qǐng)求收益較大的優(yōu)先處理。另外需要注意的是，r_increase隊(duì)列中的虛擬網(wǎng)絡(luò)請(qǐng)求根據(jù)類型不同被區(qū)別對(duì)待，當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求增加某個(gè)或某些虛擬節(jié)點(diǎn)的計(jì)算資源或者鏈路資源時(shí)，只需要考慮該節(jié)點(diǎn)或者鏈路的映射目標(biāo)對(duì)應(yīng)的物理節(jié)點(diǎn)或者物理路徑上是否有滿足需求的空閑資源，如果有則簡(jiǎn)單增加即可；當(dāng)空閑資源不滿足條件時(shí)，如果是增加節(jié)點(diǎn)資源，則需要對(duì)目標(biāo)物理節(jié)點(diǎn)上的其他虛擬節(jié)點(diǎn)進(jìn)行遷移以獲得更多的資源，即調(diào)用vnmig1()函數(shù)進(jìn)行遷移；如果是增加虛擬鏈路資源，則需要利用其他物理網(wǎng)絡(luò)路徑，對(duì)增加資源的虛擬鏈路作多路徑分割映射，即將該虛擬鏈路映射到多條底層物理網(wǎng)絡(luò)路徑之上，在算法中直接采用k-shortest path算法進(jìn)行多路徑映射。

當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求增加虛擬節(jié)點(diǎn)時(shí)，必然涉及到虛擬鏈路的增加，因此需要同時(shí)對(duì)虛擬節(jié)點(diǎn)和虛擬鏈路進(jìn)行調(diào)整，如果能夠在物理網(wǎng)絡(luò)中找到符合資源約束的目標(biāo)物理節(jié)點(diǎn)和物理鏈路，則進(jìn)行直接映射；否則意味著當(dāng)前物理網(wǎng)絡(luò)的資源狀態(tài)無法直接滿足要求，因此需要對(duì)部分已運(yùn)行虛擬節(jié)點(diǎn)及其相關(guān)鏈路進(jìn)行適當(dāng)遷移，本文使用vnmig2()函數(shù)對(duì)這種情況進(jìn)行處理。下面是對(duì)兩個(gè)函數(shù)的具體算法說明。

算法2 vnmig1()。

輸入：物理網(wǎng)絡(luò)GS=(NS,ASN,LS,ASL);目前的虛擬網(wǎng)絡(luò)映射方案和需要調(diào)整的節(jié)點(diǎn)編號(hào)。

1)

找到需增加資源的虛擬節(jié)點(diǎn)nv駐留的物理節(jié)點(diǎn)ns；

2)

讀取ns上映射的其他虛擬節(jié)點(diǎn)集合A；

3)

foreach節(jié)點(diǎn)inAdo

4)

if 該虛擬節(jié)點(diǎn)請(qǐng)求的資源大于nv需要增加的資源then

5)

計(jì)算該虛擬節(jié)點(diǎn)的ζ值；

6)

endif

7)

取最小的ζ值對(duì)應(yīng)的虛擬節(jié)點(diǎn)nv′；

8)

找到ns的能滿足式(9)的距離約束γ且空閑資源能力大于nv′占用資源的鄰居節(jié)點(diǎn)集合B；

9)

ifB非空then

10)

依次遍歷B中的所有節(jié)點(diǎn)，找到nv′的遷移目標(biāo)物理節(jié)點(diǎn)，且滿足以下要求：根據(jù)式(18)使得遷移nv′代價(jià)最小的目標(biāo)節(jié)點(diǎn)ns′；

11)

遷移nv′到ns′并遷移相應(yīng)的虛擬鏈路；

12)

else將整個(gè)nv看成需要被新映射的節(jié)點(diǎn)，調(diào)用vnmig2()函數(shù)映射；

13)

If 映射成功then

14)

釋放nv在ns上占用的資源；

15)

endif

16)

endif

算法2的思路是，盡量遷移待調(diào)整虛擬節(jié)點(diǎn)的宿主主機(jī)上的能空閑足夠資源且影響力最小的其他虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)，將其遷移到宿主主機(jī)鄰居節(jié)點(diǎn)上，并使得遷移代價(jià)最小。如果遷移某一個(gè)虛擬節(jié)點(diǎn)無法滿足要求，那意味著要遷移兩個(gè)或兩個(gè)以上節(jié)點(diǎn)才能滿足該虛擬節(jié)點(diǎn)的增加資源需求，那么與其進(jìn)行多個(gè)節(jié)點(diǎn)的遷移，不如直接將該虛擬節(jié)點(diǎn)作為新的虛擬節(jié)點(diǎn)重映射到其他物理節(jié)點(diǎn)之上，因此調(diào)用了vnmig2()函數(shù)，如果成功，則釋放原來宿主主機(jī)上的資源，這樣的好處是使被遷移虛擬節(jié)點(diǎn)的個(gè)數(shù)盡量少，從而減少遷移代價(jià)。vnmig2()函數(shù)的具體描述如下：

算法3vnmig2()。

輸入：物理網(wǎng)絡(luò)GS=(NS,ASN,LS,ASL);目前的虛擬網(wǎng)絡(luò)映射方案和重映射的虛擬節(jié)點(diǎn)編號(hào)。

1)

找到與需重映射虛擬節(jié)點(diǎn)nv連接的鄰接節(jié)點(diǎn)集合C；

2)

foreach節(jié)點(diǎn)inCdo

3)

找到與nv相連的鏈路所需帶寬最大的節(jié)點(diǎn)nva；

4)

endfor

5)

找到nva所映射的物理節(jié)點(diǎn)nsa；

6)

fornsa節(jié)點(diǎn)do

7)

找到與nsa節(jié)點(diǎn)滿足距離約束γ且剩余節(jié)點(diǎn)資源大于nv節(jié)點(diǎn)所需總資源的節(jié)點(diǎn)集合D；

8)

將D中的所有節(jié)點(diǎn)降序排序，取具有最大空閑資源的物理節(jié)點(diǎn)nsb；

9)

endfor

10)

for節(jié)點(diǎn)nsbdo

11)

將nv映射到nsb，并利用k-shortest path算法映射相應(yīng)的虛擬邊；

12)

endfor

算法3是節(jié)點(diǎn)的重新映射算法，主要思路是首先找到與需要重映射節(jié)點(diǎn)直接相連的虛擬節(jié)點(diǎn)中所需虛擬鏈路資源最大的節(jié)點(diǎn)并找到該節(jié)點(diǎn)映射的物理節(jié)點(diǎn)。通過此物理節(jié)點(diǎn)找到滿足距離約束和資源請(qǐng)求約束的候選集合，選擇剩余節(jié)點(diǎn)資源最大的節(jié)點(diǎn)作為遷移節(jié)點(diǎn)進(jìn)行映射，并采用k-shortest path算法遷移相應(yīng)的虛擬鏈路。

4 仿真與分析

4.1 仿真環(huán)境和參數(shù)設(shè)置

在CloudSim 3.0.1上測(cè)試了本文所提出的DVNR-VNE算法，硬件平臺(tái)為配備Intel Core i7-3770 CPU和20 GB內(nèi)存的PC。在CloudSim中用Java為底層物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)編寫了一個(gè)拓?fù)渖善?，以連通概率、資源需求邊界、節(jié)點(diǎn)數(shù)量范圍作為輸入?yún)?shù)生成隨機(jī)物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)拓?fù)?。算?中的processcount設(shè)置為8，三類虛擬網(wǎng)絡(luò)請(qǐng)求隨機(jī)分布，實(shí)驗(yàn)中涉及到的具體參數(shù)如表1所示。虛擬網(wǎng)絡(luò)請(qǐng)求增加請(qǐng)求、增加節(jié)點(diǎn)資源和新到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求服從隨機(jī)均勻分布。

表1 仿真實(shí)驗(yàn)參數(shù)

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

在實(shí)驗(yàn)一中，假設(shè)虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)服從泊松分布，平均每100個(gè)時(shí)間單位有4個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)設(shè)為100。虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)數(shù)分別設(shè)為4，8，12，16和20。運(yùn)行100個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，每種情況運(yùn)行20次取平均值實(shí)驗(yàn)結(jié)果如圖1所示。分別將DVNR-VNE算法與文獻(xiàn)[8]中算法的鏈路映射代價(jià)和遷移代價(jià)進(jìn)行比較。從圖1中可以看出DVNR-VNE算法鏈路映射代價(jià)和遷移代價(jià)均低于DVNMA(Dynamic Virtual Network Mapping Algorithm)，這是因?yàn)镈VNR-VNE算法使用了多隊(duì)列來存儲(chǔ)不同類型的虛擬網(wǎng)絡(luò)請(qǐng)求。如果r_decrease隊(duì)列中有虛擬網(wǎng)絡(luò)請(qǐng)求對(duì)其進(jìn)行優(yōu)先處理，這樣能預(yù)留出更多的資源為后續(xù)的虛擬網(wǎng)絡(luò)請(qǐng)求服務(wù)。隨著虛擬網(wǎng)絡(luò)請(qǐng)求節(jié)點(diǎn)個(gè)數(shù)的增多，鏈路映射代價(jià)和遷移代價(jià)逐漸增大，且鏈路映射代價(jià)的差距增大。這是因?yàn)楸疚牡乃惴ú捎昧丝芍赜脵C(jī)制，隨著虛擬網(wǎng)絡(luò)請(qǐng)求節(jié)點(diǎn)個(gè)數(shù)的增多，可重用機(jī)制的優(yōu)勢(shì)越來越明顯。

圖1 映射鏈路和遷移的成本

在實(shí)驗(yàn)二中，假設(shè)虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)服從泊松分布，平均每100個(gè)時(shí)間單位有4個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)分別設(shè)為60，70，80，90和100。運(yùn)行200個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，每種情況運(yùn)行20次取平均值，實(shí)驗(yàn)結(jié)果如圖2所示。從圖中可以看出DVNR-VNE算法的成本低于DVNMA，這是因?yàn)镈VNR-VNE算法采用了可重用技術(shù)且優(yōu)先處理減少資源的虛擬網(wǎng)絡(luò)請(qǐng)求，這樣后續(xù)的虛擬網(wǎng)絡(luò)請(qǐng)求映射的可選資源更充足。隨著物理網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)數(shù)的增加，在處理相同虛擬網(wǎng)絡(luò)請(qǐng)求的情況下，DVNMA的成本減少比DVNR-VNE算法明顯，這是因?yàn)樵谖锢砉?jié)點(diǎn)增多的請(qǐng)求下，采用DVNMA映射虛擬網(wǎng)絡(luò)請(qǐng)求可選擇資源增多，且DVNR-VNE算法因采用了節(jié)點(diǎn)可重用技術(shù)，而使新增節(jié)點(diǎn)對(duì)采用DVNR-VNE算法的映射結(jié)果影響不大。

圖2 不同物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的虛擬網(wǎng)絡(luò)映射成本

在實(shí)驗(yàn)三中，物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)設(shè)定為80。運(yùn)行1 000個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，運(yùn)行20次取平均值，實(shí)驗(yàn)結(jié)果如圖3所示。從圖3可以看出在前2 000 s內(nèi)兩種算法的接受率都急劇下降，這是由于隨著虛擬網(wǎng)絡(luò)請(qǐng)求的不斷到來物理網(wǎng)絡(luò)逐漸趨于飽和狀態(tài)，能承載的新到來的虛擬網(wǎng)絡(luò)請(qǐng)求能力減弱。隨著時(shí)間增長(zhǎng)，算法的接受率趨于穩(wěn)定且DVNR-VNE算法的接受率比DVNMA的接受率高大約5%，原因在于算法采用了可重用技術(shù)，這樣可以節(jié)約部分鏈路的映射開銷，能使物理網(wǎng)絡(luò)承載更多的虛擬網(wǎng)絡(luò)請(qǐng)求，算法采用的多隊(duì)列和滑動(dòng)窗口技術(shù)首先映射的是已運(yùn)行著的虛擬網(wǎng)絡(luò)請(qǐng)求，使占用資源的虛擬網(wǎng)絡(luò)請(qǐng)求能盡早地滿足變化的請(qǐng)求完成任務(wù)，且并不是映射不成功就直接加入到隊(duì)列后面而是在滑動(dòng)窗口內(nèi)等待一段時(shí)間再重新映射，這樣提高了虛擬網(wǎng)絡(luò)完成工作的效率，使得已運(yùn)行的虛擬網(wǎng)絡(luò)請(qǐng)求的運(yùn)行時(shí)間縮短從而能接受新的請(qǐng)求任務(wù)。在映射調(diào)整的過程中是映射到滿足要求的且剩余資源最多的節(jié)點(diǎn)上，這樣雖然在一定程度上增加了映射成本，但是負(fù)載趨于均衡，為后續(xù)到來的虛擬網(wǎng)絡(luò)請(qǐng)求提供了更多的映射成功機(jī)會(huì)。

圖3 虛擬網(wǎng)絡(luò)請(qǐng)求的接受率

5 結(jié)語(yǔ)

本文針對(duì)多租賃模式下的動(dòng)態(tài)虛擬網(wǎng)絡(luò)請(qǐng)求映射問題，提出了一種物理節(jié)點(diǎn)可重用多隊(duì)列存儲(chǔ)虛擬網(wǎng)絡(luò)請(qǐng)求的DVNR-VNE算法，該算法首先對(duì)到來的虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行分類，并建立虛擬網(wǎng)絡(luò)請(qǐng)求存儲(chǔ)隊(duì)列模型，優(yōu)先映射需要釋放資源和已運(yùn)行的虛擬網(wǎng)絡(luò)請(qǐng)求，使得被占用資源盡早完成任務(wù)；采用了節(jié)點(diǎn)可重用的方法，以內(nèi)存交換代替虛擬鏈路從而減少了物理鏈路資源的使用。仿真實(shí)驗(yàn)表明，該算法降低了鏈路映射成本和遷移成本并提高了虛擬網(wǎng)絡(luò)請(qǐng)求接受率。此外DVNR-VNE算法僅用了最短路徑算法來作路徑的遷移，因此在路徑遷移的優(yōu)化方面還有一定的改進(jìn)和發(fā)展空間。

References)

[1] CHOWDHURY N, BOUTABA R.A survey of network virtualization [J].Computer Networks, 2010, 54(5): 862-876.

[2] MUNTASIR R R, ISSAM A, RAOUF B.Survivable virtual network embedding [C]// Proceedings of the 9th International IFIP TC 6 Networking Conference.Berlin: Springer, 2010: 40-52.

[3] BAVIER A, FEAMSTER N, HUANG M, et al.In VINI veritas: realistic and controlled network experimentation [C]// SIGCOMM’ 06: Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications.New York: ACM, 2006: 3-14.

[4] YU M, YI Y, REXFORD J, et al.Rethinking virtual network embedding: substrate support for path splitting and migration [J].ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[5] RAHMAN M R, BOUTABA R.SVNE: survivable virtual network embedding algorithms for network virtualization [J].IEEE Transactions on Network and Service Management, 2013, 10(2): 105-118.

[6] MARQUEZAN C, NOBRE J, GRANVILLE L, et al.Distributed reallocation scheme for virtual network resources [C]// ICC2009: Proceedings of 2009 IEEE International Conference on Communications.Piscataway, NJ: IEEE, 2009: 1-5.

[7] 羅娟,徐岳陽(yáng),李仁發(fā).網(wǎng)絡(luò)虛擬化中動(dòng)態(tài)資源分配算法研究[J].通信學(xué)報(bào),2011,32(7):64-70.(LUO J, XU Y Y, LI R F.Dynamical resource allocation algorithm research in network virtualization [J].Journal on Communications, 2011, 32(7): 64-70.)

[8] SUN G, ANAND V, YU H, et al.A cost efficient framework and algorithm for embedding dynamic virtual network requests [J].Future Generation Computer Systems, 2013, 29(5): 1265-1277.

[9] MAO Y, GUO F, HU C.Sharing based virtual network embedding algorithm with dynamic resource block generation [J].IEEE Communications Letters, 2015， 19(12): 2126-2129.

[10] DIVAKARAN D M, HEGDE S, SRINIVAS R, et al.Dynamic resource allocation in hybrid optical-electrical datacenter [J].Computer Communications, 2015, 69: 40-49.

[11] YUAN Y, WANG C R, ZHU N, et al.Virtual network embedding algorithm based connective degree and comprehensive capacity [C]// ICIC’13: Proceedings of the 9th International Conference on Intelligent Computing Theories, LNCS 7995.Berlin: Springer, 2013: 250-258.

[12] CHOWDLIURY N M M K, RAHMAN M R, BOUTABA R.Virtual network embedding with coordinated node and link mapping [C]// INFOCOM 2009: Proceedings of the 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2009: 783-791.

[13] 苑迎,王翠榮,王聰,等.基于DPSO負(fù)載可控的虛擬網(wǎng)絡(luò)映射算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(1):10-14.(YUAN Y, WANG C R, WANG C, et al.Load controllable virtual network embedding algorithm based on discrete particle swarm optimization [J].Journal of Northeastern University (Natural Science), 2014, 35(1): 10-14.)

This work is partially supported by the National Natural Science Foundation of China (61300195, 61402094), the Natural Science Foundation of Heibei Province (F2014501078， F2016501079), the Science and Technology Research Project of the Colleges and Universities of Hebei Province (ZD20132003), the Science and Technology Research Project of Qinhuangdao (201401A028), the School Foundation of Northeastern University at Qinhuangdao (XNB201607).

YUAN Ying, born in 1981, Ph.D., lecturer.Her research interests include cloud computing, data centre, virtual network embedding.

WANG Cong, born in 1981, Ph.D., lecturer.His research interests include cloud computing, virtual network embedding, resource allocation in data center.

WANG Cuirong, born in 1963, Ph.D., professor.Her research interests include cloud computing, routing protocol, resource allocation in data center.

SONG Xin, born in 1978, Ph.D., associate professor.Her research interests include wireless sensor networks, distributed computing, intelligent information processing.

LYU Yanxia, born in 1982, Ph.D.candidate, lecturer.Her research interests include big data analysis, distributed computing, data stream classification.

Virtual network embedding algorithm for dynamic virtual network requests

YAUN Ying1*, WANG Cong2, WANG Cuirong2, SONG Xin1, LYU Yanxia2

(1.ComputerCenter,NortheasternUniversityatQinhuangdao,QinhuangdaoHebei066004,China;2.SchoolofComputerandCommunicationEngineering,NortheasternUniversityatQinhuangdao,QinhuangdaoHebei066004,China)

Due to the dynamic characteristic of Virtual Network Request (VNR) resources, a Virtual Network Embedding algorithm based on Dynamic Virtual Network Requests (DVNR-VNE) was proposed.On the basis of mixed linear programming theory, we adopted multi-queue to pre-process different types of VNRs and established a multi-object embedding model with minimum mapping and migration cost.Those requests which need to release resource would be accepted firstly to support more VNRs, and the new arrived VNR would be embedded by an optimized WinDow-Virtual Network Embedding (WD-VNE) algorithm.The simulation results show that the proposed algorithm can reduce link cost, migration cost and can also obtain higher accept ratio.

network virtualization; virtual network; Virtual Network Embedding (VNE); dynamic virtual network request

2016-07-25;

2016-08-10。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300195, 61402094)；河北省自然科學(xué)基金資助項(xiàng)目(F2014501078，F(xiàn)2016501079)；河北省高等學(xué)?？茖W(xué)技術(shù)研究項(xiàng)目(ZD20132003)；秦皇島市科技計(jì)劃項(xiàng)目(201401A028)；東北大學(xué)秦皇島分校校內(nèi)基金資助項(xiàng)目(XNB201607)。

苑迎(1981—)，女(滿族)，遼寧本溪人，講師，博士，CCF會(huì)員，主要研究方向：云計(jì)算、數(shù)據(jù)中心、虛擬網(wǎng)絡(luò)映射； 王聰(1981—)，男，河北秦皇島人，講師，博士，CCF會(huì)員，主要研究方向：云計(jì)算、虛擬網(wǎng)絡(luò)映射、數(shù)據(jù)中心資源分配； 王翠榮(1963—)，女，河北遷安人，教授，博士，CCF會(huì)員，主要研究方向：云計(jì)算、路由協(xié)議、數(shù)據(jù)中心資源分配； 宋欣(1978—)，女，山東鄆城人，副教授，博士，CCF會(huì)員，主要研究方向：無線傳感器網(wǎng)絡(luò)、分布式計(jì)算、智能信息處理； 呂艷霞(1982—)，女，河北黃驊人，講師，博士研究生，CCF會(huì)員，主要研究方向：大數(shù)據(jù)分析、分布式計(jì)算、數(shù)據(jù)流分類。

1001-9081(2017)01-0006-06

10.11772/j.issn.1001-9081.2017.01.0006

TP393.2

A