面向动态虚拟网络请求的虚拟网络映射算法

苑 迎，王 聪，王翠荣，宋 欣，吕艳霞

(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