面向動態虛擬網絡請求的虛擬網絡映射算法

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

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

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

面向動態虛擬網絡請求的虛擬網絡映射算法

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

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

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

針對虛擬網絡請求資源動態變化的實際情況，提出了面向動態虛擬網絡請求的虛擬網絡映射(DVNR-VNE)算法。以混合線性規劃理論為基礎，采用多隊列的方式分別對不同類型的虛擬網絡請求進行預處理，建立了以最小化映射代價和最小遷移代價為優化目標的映射模型，優先映射需要釋放資源的請求以獲得更多的資源支持其他的虛擬網絡，對新到來的虛擬網絡請求采用優化后的虛擬網絡映射(WD-VNE)算法進行映射。仿真實驗表明，該算法降低了鏈路映射成本和遷移成本并獲得了較高的虛擬網絡請求接受率。

網絡虛擬化；虛擬網絡；虛擬網絡映射；動態虛擬網絡請求

0 引言

隨著互聯網技術的快速發展，互聯網上新型應用層出不窮，現有的網絡架構很難跟上互聯網新型應用的發展，在某種程度上出現了僵化的現象。網絡虛擬化是解決網絡結構僵化的一項重要技術，網絡虛擬化技術允許多個異構的虛擬網絡共享同一個物理網絡資源[1]。它將傳統意義上的互聯網提供商分成了基礎設施提供商(Infrastructure Provider, INP)和服務提供商(Service Provider, SP)兩個部分[2]。在網絡虛擬化環境下，基礎設施提供商部署和管理底層網絡資源，通過可編程接口為不同的服務提供商提供資源。服務提供商租用基礎設施提供商的底層網絡資源并創建虛擬網絡，獲得個性化的端到端的網絡服務[3]。虛擬網絡映射(Virtual Network Embedding, VNE)技術能有效地利用共享的物理網絡資源，最大化物理網絡資源的利用率，提高服務質量，降低網絡運營成本[4]。在虛擬化環境下，大多數研究僅針對虛擬網請求是固定不變的情況設計有效的虛擬網絡映射算法，但是有時虛擬網絡的資源請求數量甚至拓撲結構會隨著時間的變化而發生變化(如：在線游戲、分布式計算等)，需要底層的物理網絡動態地調整資源分配的方案及時應對虛擬網絡請求的變化。底層的物理網絡也會因為某些特殊情況(如：網絡部件故障、自然災害、黑客攻擊等)的發生而影響到正在運行的虛擬網絡，服務提供商需根據物理網絡資源的變化情況及時地調整映射方案以滿足虛擬網絡的正常運行。

虛擬網絡映射問題是一個NP-hard問題。即便已經確定了虛擬節點的位置，基于帶寬約束的虛擬鏈路映射問題也是NP-hard問題[5]。目前大多數研究僅針對虛擬網請求是固定不變的情況設計有效的虛擬網絡映射算法，針對動態虛擬網絡請求的映射算法還較少。

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

本文提出了面向動態虛擬網絡請求的虛擬網絡映射(Virtual Network Embedding based on Dynamic Virtual Network Requests, DVNR-VNE)算法，將虛擬網絡請求分為三類：一類是已經映射的虛擬網絡請求，它所請求的節點或鏈路資源因為不需要被取消；第二類是已經映射的虛擬網絡請求，它的部分虛擬網絡節點或鏈路所請求的資源增加；第三類是新到來的虛擬網絡請求。以最小化映射代價和最小遷移代價為優化目標，采用多隊列的方式分別對不同類型的虛擬網絡請求進行預處理，優先映射需要釋放資源的請求以獲得更多的資源支持其他的虛擬網絡，對新到來的虛擬網絡請求采用優化后的WD-VNE(WinDow-Virtual Network Embedding)算法[11]進行映射。實驗表明，該算法可以降低映射成本和遷移成本并且提高虛擬網絡請求的接受率。

1 問題描述與網絡模型

首先建立了物理網絡模型、動態虛擬網絡請求模型以及相應的虛擬網絡映射問題的模型，進而定義了節點綜合能力和影響因子，然后給出了系統模型和優化目標。

1.1 物理網絡

1.2 虛擬網絡請求

1.3 虛擬網絡映射問題模型

虛擬網絡映射問題可以被看作一個虛擬網絡請求(Virtual Network Request, VNR)到底層物理網絡S的映射Γ，通過下式進行描述：

(1)

其中NS*?NS,PS*?PS，虛擬網絡請求中的每個虛擬節點到物理網絡節點的映射由ΓN表示：

(2)

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

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

(3)

(4)

其中：RCPU(nv)表示虛擬節點nv請求的CPU資源的約束，CCPU(ΓN(nv))表示目標物理節點空閑的CPU資源。CPU(ΓN(nv))表示物理節點總的CPU資源。對于物理節點來說，空閑CPU資源等于總資源減去所有已分配資源。

對于虛擬邊的映射，根據其兩端虛擬節點被映射的位置，在物理網絡中可通過不分流的路徑映射或者基于多商品流的路徑分割映射，其數學描述為：

(5)

對于?lv(i,j)∈LV，PS是物理網絡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請求的帶寬資源額度；Cbw(p)表示底層物理網絡鏈路的空閑資源，取路徑P上空閑帶寬資源最小的鏈路的值；P(q,r)表示物理鏈路中，節點q和r之間的路徑的集合；bw(ls)表示物理網絡鏈路總的帶寬容量。

1.4 節點綜合能力

為了衡量節點優劣從而判斷映射目標，本文引入了節點綜合能力作為判定依據，其數學描述為：

(10)

其中：nnb是節點n的鄰居節點，DIS(n,nnb)是節點n到nnb的路徑跳數。

1.5 影響因子

鑒于動態虛擬網絡的映射需要重配置機制支持，因此涉及虛擬節點的遷移，那么也就需要判斷物理節點上已駐留的虛擬節點遷移代價，因此本文引入了虛擬節點的影響因子，其表達式為：

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

(11)

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

1.6 映射成本和接受率

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

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

(12)

定義2 接受率。虛擬網絡請求的接受率表示到t時刻虛擬網絡請求被接受的概率，形式化為：

(13)

其中：VNRA表示被物理網絡成功映射的虛擬網絡請求數量；VNR表示到t時刻到達的虛擬網絡請求的總數量。

2 系統模型和優化目標

對于動態虛擬網絡映射問題，本文利用混合線性規劃(MixedLinearProgramming,MLP)理論，建立以最小開銷為優化目標的模型。需要注意的是，在模型及后續算法的設計中利用了可重用特性，即允許同一虛擬網絡的不同虛擬節點可以被映射到同一物理網絡節點上，這樣可以節省分配的帶寬資源[13]。

映射開銷指為了承載虛擬網絡，物理網絡所分配的所有資源，包括節點計算資源和鏈路帶寬資源以及由于映射方案調整所需要的遷移虛擬節點及鏈路的開銷，即：

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

(14)

虛擬網絡的節點映射開銷為其計算資源，即所占用CPU資源的總和：

cost(nv)=RCPU(nv)

(15)

虛擬網絡的鏈路映射開銷為所有物理路徑上所占用的帶寬資源的總和：

(16)

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

對于虛擬網絡來說，遷移開銷表示為：

costmig=MCPU(nv)+Mbw(lt)

(17)

其中MCPU(nv)和Mbw(lw)分別表示遷移節點和遷移鏈路的代價。對于物理網絡來說，無論虛擬網絡的節點被映射到哪個物理節點，其計算資源即CPU資源是必須分配且額度不變的，因此在考慮最小映射開銷時，CPU資源的開銷可以被省略，那么動態虛擬網絡映射問題的優化目標可以被定義為：

min (cost(lv)+costmig)

(18)

即系統的總體目標為最小化映射該虛擬網絡的鏈路開銷與為了映射該虛擬網絡產生的虛擬節點和虛擬鏈路的遷移代價之和。

3 DVNR-VNE算法

針對虛擬網絡請求是動態的這一特點，首先建立請求提交的等待隊列模型。在請求到達執行映射算法尋找可行的資源分配方案前明確虛擬網絡請求的分類并加入相應的隊列。本文提出的DVNR-VNE算法使用了三個隊列：r_new、r_increase和r_decrease。根據1.2節中參數η和R設置，本文將動態虛擬網絡請求分為三類，分別對應算法中的三個隊列。當η=1時，說明虛擬網絡請求是新的隊列，將被加入隊列r_new。當η=0時，進一步判斷R的值，如果該虛擬網絡請求增加節點或者資源，則將其加入隊列r_increase；如果該虛擬網絡請求減少節點或者資源時，將其加入隊列r_decrease。

在三個隊列的處理順序上，為了盡可能充分地利用資源，應當首先處理隊列r_decrease中的請求，使其釋放不需要的資源。然后處理r_increase中的請求，因為要盡可能地響應已運行的虛擬網絡請求對于資源增加或節點增加的需求，以盡量縮短其生命周期并保證用戶的服務質量(Quality of Service, QoS)需求。最后才嘗試處理隊列r_new中的新增虛擬網絡請求，因為讓未被映射的虛擬網絡請求繼續等待要強于拒絕已運行虛擬網絡請求的資源增加請求。

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

算法1DVNR-VNE算法。

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

1)

根據虛擬網絡請求參數將其加入到請求提交的等待隊列中；

2)

for每個r_decrease中的虛擬網絡請求 do

3)

釋放其請求釋放的節點和鏈路資源；

4)

endfor

5)

for每個r_increase中的虛擬網絡請求do

6)

if如果該VNR請求增加資源then

7)

if如果需要增加節點資源then

8)

for每個要增加資源的節點do

9)

if目標物理節點滿足RCPU(nv)≤CCPU(ΓN(nv))then

10)

為該節點資源增加請求的資源；

11)

else調用vnmig1()函數找到可遷移節點，釋放需遷移節點已占用的資源并對其進行重新映射；

12)

endif

13)

endfor

14)

endif

15)

if需要增加鏈路資源then

16)

for每個需要增加資源的虛擬鏈路do

17)

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

18)

為該虛擬鏈路分配增加請求的資源；

19)

else嘗試路徑分割映射，即利用其他物理路徑滿足該資源增加請求并使得cost(lv)最小；

20)

end if

21)

end for

22)

end if

23)

end if

24)

if 該虛擬網絡請求申請增加節點 then

25)

for 每個需要被增加的虛擬節點 do

26)

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

27)

ifF非空 then

28)

找到cost(lv)最小的映射方案并映射該節點使用k-shortest path 算法對相應的虛擬鏈路進行路徑分割映射；

29)

else 調用vnmig2()重新映射節點，嘗試對虛擬鏈路進行遷移并釋放其所占資源；

30)

end if

31)

end for

32)

end if

33)

end for

34)

ifr_increase已經為空或隊列中所有的虛擬網絡請求已被嘗試分配5次 then

35)

for 隊列r_new中的前processcount個虛擬網絡請求do

36)

利用文獻[11]中WD-VNE映射算法映射虛擬網絡請求；

37)

if映射成功then

38)

將其從r_new中移除；

39)

endif

40)

endfor

41)

endif

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

當虛擬網絡請求增加虛擬節點時，必然涉及到虛擬鏈路的增加，因此需要同時對虛擬節點和虛擬鏈路進行調整，如果能夠在物理網絡中找到符合資源約束的目標物理節點和物理鏈路，則進行直接映射；否則意味著當前物理網絡的資源狀態無法直接滿足要求，因此需要對部分已運行虛擬節點及其相關鏈路進行適當遷移，本文使用vnmig2()函數對這種情況進行處理。下面是對兩個函數的具體算法說明。

算法2 vnmig1()。

輸入：物理網絡GS=(NS,ASN,LS,ASL);目前的虛擬網絡映射方案和需要調整的節點編號。

1)

找到需增加資源的虛擬節點nv駐留的物理節點ns；

2)

讀取ns上映射的其他虛擬節點集合A；

3)

foreach節點inAdo

4)

if 該虛擬節點請求的資源大于nv需要增加的資源then

5)

計算該虛擬節點的ζ值；

6)

endif

7)

取最小的ζ值對應的虛擬節點nv′；

8)

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

9)

ifB非空then

10)

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

11)

遷移nv′到ns′并遷移相應的虛擬鏈路；

12)

else將整個nv看成需要被新映射的節點，調用vnmig2()函數映射；

13)

If 映射成功then

14)

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

15)

endif

16)

endif

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

算法3vnmig2()。

輸入：物理網絡GS=(NS,ASN,LS,ASL);目前的虛擬網絡映射方案和重映射的虛擬節點編號。

1)

找到與需重映射虛擬節點nv連接的鄰接節點集合C；

2)

foreach節點inCdo

3)

找到與nv相連的鏈路所需帶寬最大的節點nva；

4)

endfor

5)

找到nva所映射的物理節點nsa；

6)

fornsa節點do

7)

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

8)

將D中的所有節點降序排序，取具有最大空閑資源的物理節點nsb；

9)

endfor

10)

for節點nsbdo

11)

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

12)

endfor

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

4 仿真與分析

4.1 仿真環境和參數設置

在CloudSim 3.0.1上測試了本文所提出的DVNR-VNE算法，硬件平臺為配備Intel Core i7-3770 CPU和20 GB內存的PC。在CloudSim中用Java為底層物理網絡和虛擬網絡編寫了一個拓撲生成器，以連通概率、資源需求邊界、節點數量范圍作為輸入參數生成隨機物理網絡和虛擬網絡拓撲。算法1中的processcount設置為8，三類虛擬網絡請求隨機分布，實驗中涉及到的具體參數如表1所示。虛擬網絡請求增加請求、增加節點資源和新到達的虛擬網絡請求服從隨機均勻分布。

表1 仿真實驗參數

4.2 仿真結果與分析

在實驗一中，假設虛擬網絡請求的到達服從泊松分布，平均每100個時間單位有4個虛擬網絡請求，物理網絡節點數設為100。虛擬網絡請求的節點數分別設為4，8，12，16和20。運行100個虛擬網絡請求，每種情況運行20次取平均值實驗結果如圖1所示。分別將DVNR-VNE算法與文獻[8]中算法的鏈路映射代價和遷移代價進行比較。從圖1中可以看出DVNR-VNE算法鏈路映射代價和遷移代價均低于DVNMA(Dynamic Virtual Network Mapping Algorithm)，這是因為DVNR-VNE算法使用了多隊列來存儲不同類型的虛擬網絡請求。如果r_decrease隊列中有虛擬網絡請求對其進行優先處理，這樣能預留出更多的資源為后續的虛擬網絡請求服務。隨著虛擬網絡請求節點個數的增多，鏈路映射代價和遷移代價逐漸增大，且鏈路映射代價的差距增大。這是因為本文的算法采用了可重用機制，隨著虛擬網絡請求節點個數的增多，可重用機制的優勢越來越明顯。

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

在實驗二中，假設虛擬網絡請求的到達服從泊松分布，平均每100個時間單位有4個虛擬網絡請求，物理網絡節點數分別設為60，70，80，90和100。運行200個虛擬網絡請求，每種情況運行20次取平均值，實驗結果如圖2所示。從圖中可以看出DVNR-VNE算法的成本低于DVNMA，這是因為DVNR-VNE算法采用了可重用技術且優先處理減少資源的虛擬網絡請求，這樣后續的虛擬網絡請求映射的可選資源更充足。隨著物理網絡節點的個數的增加，在處理相同虛擬網絡請求的情況下，DVNMA的成本減少比DVNR-VNE算法明顯，這是因為在物理節點增多的請求下，采用DVNMA映射虛擬網絡請求可選擇資源增多，且DVNR-VNE算法因采用了節點可重用技術，而使新增節點對采用DVNR-VNE算法的映射結果影響不大。

圖2 不同物理網絡節點數的虛擬網絡映射成本

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

圖3 虛擬網絡請求的接受率

5 結語

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

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] 羅娟,徐岳陽,李仁發.網絡虛擬化中動態資源分配算法研究[J].通信學報,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負載可控的虛擬網絡映射算法[J].東北大學學報(自然科學版),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。

國家自然科學基金資助項目(61300195, 61402094)；河北省自然科學基金資助項目(F2014501078，F2016501079)；河北省高等學校科學技術研究項目(ZD20132003)；秦皇島市科技計劃項目(201401A028)；東北大學秦皇島分校校內基金資助項目(XNB201607)。

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

1001-9081(2017)01-0006-06

10.11772/j.issn.1001-9081.2017.01.0006

TP393.2

A