一种改进的高可靠性虚拟网络映射算法研究

童绪军，钟 梁

(1. 安徽医学高等专科学校 基础部，中国 合肥 230601； 2. 武汉大学 计算机学院，中国 武汉 430072)

虚拟技术在云计算环境下扮演重要角色[1-3]，多个服务商(Service Providers, SPs)只需从一个或多个基础设施供应商(Infrastructure Providers, InPS)处租借共享资源即可创建异构虚拟网络(Virtual Networks, VNs)，进而向终端用户提供个性化端到端服务[4]。其中，虚拟网络映射主要负责将虚拟网络请求(虚拟节点的计算请求(虚拟机)和虚拟链路的带宽请求)映射到数据中心所位于的具体的物理节点以及具有有限资源的底层网络的路径上。如果数据中心或者底层物理网络链路发生物理故障，则受影响的虚拟网络无法为终端用户提供服务，导致服务提供商遭受重大经济损失。因此，我们希望将虚拟网络映射到可靠性最高的底层物理网络上，该问题称为高可靠性虚拟网络映射问题(Reliable Virtual Network Mapping, RVNM)[6]。

人们先前对RVNM问题的研究可分为3类：第1类，分布式云资源的分配。文献[7]将CPU和带宽等资源看成底层网络上的节点和链路的容量，资源分配过程负责通过多物品流通理论将各种请求映射到底层网络上的节点和路径上。文献[8]将分布式数据中心虚拟机的分配问题转化为分团问题，提出一种比率为2的近似算法，并可实现最大延时最小化。然而其算法对于虚拟器分配时的可靠性问题欠缺考虑。第2类，对虚拟星型网络的可靠性/可生存性资源分析问题进行研究。文献[9,10]的作者向不同的数据中心分配不同数量的虚拟机，以尽量提升可靠性。他们首先确定一个中央数据中心，然后增加更多数据中心以提供足够多的高可靠性虚拟机。文献[11]的作者首先通过提供超过请求数量的数据中心实现K度生存性。然后，根据不同参数(包括风险和延时)提出两种启发式算法，使虚拟星型网络的总体延时最小化。然而其算法只适用于星型拓扑结构，且只考虑了计算容量约束，局限性较大。第3类，利用双阶段博弈理论研究虚拟网络嵌入算法[12]。第1阶段的博弈将虚拟节点映射到物理节点上；第2阶段将虚拟链路映射到网络中的物理路径上。为了利用博弈理论获得近似解，他们的算法需要考察所有可能的虚拟节点映射，但忽略了链路容量约束。针对以上3类算法的不足，文中提出了一种改进的虚拟网络映射算法，可在满足计算容量和带宽容量约束的同时，提高虚拟网络映射的可靠性。

1 高可靠性虚拟网络映射

在本文研究中，采用如下的场景：(1)每次只考虑一个虚拟网络的映射请求；(2)每个虚拟节点请求的虚拟机数量不会多于一个或多个物理节点提供的可用虚拟机数量；(3)虚拟网络是连通型网络；(4)因为将一个虚拟节点映射到多个物理节点的能量消耗和网络成本可能更高，所以我们将一个虚拟节点只映射到一个物理节点上；(5)利用目前典型的虚拟机动态分配算法[13]来确定虚拟机的布局和建立物理路径；(6)因为发生故障时云服务的延时较高，所以重点是实现可靠性的最大化，而不是延时的最小化。

1.1 图模型和虚拟网络映射

图1 RVNM问题的图形示例：(a)GS；(b)GT

(1)服务图形：图1(a)给出了云计算场景下的虚拟网络示例。文中将虚拟网络表示为服务图形GS(V,E)，其中V表示负责处理计算任务的虚拟节点集合；E表示将虚拟节点连接起来的虚拟链路集合。每个顶点u的数值(mu)表示执行计算任务而请求的虚拟机数量；每条虚拟边e=(u,v)的数值(bu,v)表示两个虚拟节点之间的带宽请求。

(2)网络拓扑：图1(b)给出了将物理节点所在地的多个分布式数据中心连接起来的物理网络拓扑结构示例。文中将物理网络拓扑结构表示为图形GT(N,L)，其中N表示数据中心所在地的节点集合；L表示将这些节点连接起来的物理链路集合。对每个节点p∈N，括号中的首个数值(mp)表示数据中心内可用虚拟机的数量；第2个数值(fp)表示数据中心的可靠性。对每条链路l=(p,q)∈L，括号中的首个数值(bp,q)表示链路的可用带宽；第2个数值(fp,q)表示链路的可靠性。

(3)虚拟网络映射：虚拟网络映射问题是指将服务图形中的虚拟节点映射到网络拓扑结构中的物理节点(用h1:V→N′⊆N表示)，并将虚拟链路映射到网络拓扑结构中相应物理节点之间的路径上(用h2:E→L′⊆L表示)。图1(a)和图1(b)中的虚线表示虚拟节点映射(h1)，图1(b)中的实线(计算链路和节点可靠性)表示虚拟链路映射(h2)。

1.2 可靠性函数

根据图1所示，对于虚拟网络映射(h1,h2)而言，其可靠性可表示为

Pr(h1,h2)=∏u∈V,p=h1(u)fp×∏(p,q)∈U(u,v)∈Eh2(u,v)fp,q。

(1)

可靠性主要包括两个方面：(1)数据中心所在地物理节点的可靠性；(2)将被选物理节点连接起来的链路的可靠性。对于任意给定的一个实数a(0

R(h1,h2)=∑u∈V,p=h1(u)logafp+∑(p,q)∈U(u,v)∈Eh2(u,v)logafp,q=

∑u∈V,p=h1(u)rp+∑(p,q)∈U(u,v)∈Eh2(u,v)rp,q，

(2)

其中，rp=logafp表示物理节点p的可靠性；rp,q=logafp,q表示链路(p,q)的可靠性。因为a<1，为了实现最大可靠性(Pr)，需要找到可使可靠性函数R(h1,h2)最小化的映射(h1,h2)。

1.3 问题定义

定义1高可靠性虚拟网络映射问题(RVNM)可表述如下：

已知：服务图形GS(V,E)，每个节点u∈V请求(mu)个虚拟机，每条边e=(u,v)∈E请求带宽(bu,v)，网络拓扑结构GT(N,L)，每个节点p∈N的可靠性为(rp)，可用虚拟机数量为(mp)，每条链路l=(p,q)∈L的可靠性为(rp,q)，可用带宽为(bu,v)。

目标：寻找到映射(h1,h2)使可靠性函数R(h1,h2)最小。其中h1:V→N′⊆N将虚拟节点映射到数据中心所在地的物理节点，h2:E→L′⊆L将虚拟链路映射到网络拓扑结构中的路径上。在映射过程中满足如下约束：(1)计算容量约束：请求的虚拟机数量不得多于可用虚拟机数量(即对∀u∈V有mu≤mh1(u))；(2)带宽容量约束：对各条链路请求的总体带宽不得大于可用带宽(即对∀(p,q)∈L有∑(p,q)∈h2(u,v)bu,v≤bp,q)。

2 ILP模型

依据第1节给出的场景，当物理网络的拓扑结构为连通图且各条物理链路可靠性较高，可用/被请求的虚拟机的可靠性为1，可用/被请求的带宽的可靠性为1时，RVNM问题可以看作旅行推销员问题(TSP)，所以，RVNM问题是NP难题[14]。为此，本节首先给出基于整数线性规划(ILP)的RVNM问题描述和求解方法，然后在第3节对RVNM问题进行扩展求解。为了便于阐述，下面给出了基于ILP的RVNM问题描述中的各种参数定义：

(1) ILP的输入E:=[eu,v]|V|×|V|：GS的邻接矩阵；MS:=[mu]|V|：每个虚拟节点u请求的虚拟机；BS:=[bu,v]|V|×|V|：每条虚拟链路(u,v)要求的带宽；L:=[lp,q]|N|×|N|：GT的邻接矩阵；MT:=[mp]|N|：每个物理节点p的可用虚拟机；BT:=[bp,q]|N|×|N|：每条链路(p,q)的可用带宽；RN:=[rp]|N|：每个物理节点的可靠性p；RL:=[rp,q]|N|×|N|：每条链路(p,q)的可靠性；VL：大数。

从定义1可以看出，我们的目标是使下面的函数最小化。

(3)

本文采用匈牙利算法[15]获得基于ILP的RVNM问题的解。

3 基于双阶段博弈的启发式算法

由于RVNM问题是NP难题，以上的ILP模型只能解决小规模问题，应用局限性较大。为此，本节提出一种基于双阶段博弈的启发式算法来解决大规模RVNM问题。该算法涉及到两种映射：(1)虚拟链路映射(h2)；(2)虚拟节点映射(h1)。由于本文算法首先映射虚拟链路，所以将算法称为链路映射优先算法(LMF)。在描述博弈算法内容之前，首先给出另外4种符号标记。设I(u)={p∈N|mp≥mu}表示可满足虚拟节点u虚拟机请求数量的物理节点构成的集合；设J(u,p)={e∈E|u为e的端点&u映射到p}表示虚拟路径集合，集合中的各条路径均映射到物理节点p的虚拟节点u。因此，J(u)=∪p∈NJ(u,p)={e∈E|u为e的端点}。设K(l)={e∈E|l包含于e映射的物理路径上}表示各条物理路径l=(p,q)共有的路径。

3.1 第1阶段的博弈：虚拟链路映射

在第1阶段的博弈，我们松弛虚拟节点映射的约束，允许1个虚拟节点映射到1或多个物理节点。具体来说，式(4)松弛为：

(13)

第1阶段博弈表示为博弈方：各条虚拟链路e=(u,v)构成博弈方。策略/行动：对各个博弈方e=(u,v)，p1≠p2时从p1到p2的所有物理路径；因此，所有的行动集合可表示为∏e∈EAe。效用/成本函数：当博弈方从其行动集合ae∈Ae中选择从p1到p2的路径(表示为Pp1,p2)时，将成本函数计算为

C(e)=C(p1)+C(p2)+C(Pp1,p2),

(14)

其中

(15)

(16)

VL表示大数。与终端节点成本类似，如果满足带宽容量约束式(10)，则鼓励物理路径通过共享链路来提升可靠性。

综上所述，第1阶段博弈的算法内容如下所示。该算法的核心思路是最优响应。开始时，所有博弈方随机选择一条路径；然后，博弈方e根据其他博弈方的行动改选最短路径(C(e)方面)。当所有博弈方均满足各自选择的路径，本文算法终止。

算法1：虚拟链路映射算法

输入：虚拟机请求数量为(MS)、带宽请求数量为(BS)的GS(V,E)；可用虚拟机为(MT)、可用带宽为(BT)的GT(N,L)；节点可靠性(RN)，链路可靠性(RL)；

输出：每条虚拟链路映射到1条物理链路，否则驳回请求；

//初始阶段

1：for 各个博弈方e，随机选择1条物理路径，根据式(14-16)计算成本函数C(e)；

//博弈方可改变它们的选择

2：Done ← false //表明博弈方有没有更改其选择；

3：while (!Done)

4：Done ←true

5：for 从1至|E|的各条虚拟路径e

6： 删除被e映射的路径；

7： 如果虚拟链路e的某个终端节点映射到物理节点p上且物理路径遍历链路l，则创建虚拟链路e的图形G′，并根据式(15-16)计算出节点成本和链路成本；

8： 寻找出图G′中所有最短路径对，选择成本最低的成本对，将其存储为C′(e)；

9：ifC′(e)

10：End for

11：End while

12：if 存在虚拟链路e使C(e)=VL

13： return 请求被驳回；

14： else return 链路e∈E的物理路径及其成本C(e)；

3.2 第2阶段博弈：虚拟节点映射

在第2阶段，我们要求被相同虚拟节点映射的物理节点融合为1个物理节点，以便满足式(4)的约束。

第2阶段的博弈可表述为博弈方：映射到2个或2个以上物理节点的各个虚拟节点u构成1个博弈方。策略/行动：所有物理节点。效用/成本函数：当博弈方u选择节点p1时，计算p1∈I(u)的成本函数C(u)：

(17)

其中，C(e)根据式(14—16)计算而得。如果p1∉I(u)，则C(u)=VL。第1阶段的博弈结果作为第2阶段博弈的初始状态。根据对其他博弈做的最优响应，博弈方融合为1个物理节点。第2阶段博弈的算法内容如下所示。

算法2：虚拟节点的映射

输入：虚拟链路映射

输出：虚拟网络映射满足所有约束(式(12))

0：if 没有虚拟节点映射到多个物理节点；

Return虚拟网络的映射//完成虚拟网络的映射

1：对映射到多个物理节点的各个虚拟节点u，根据式(17)计算C(u)；

2：Done ← false //表明博弈方有没有改变行动；

3：while (!Done)

4：Done ← true

5：for 映射到多个节点的各个虚拟节点u

6：寻找I(u)中C′(u)最小的物理节点；

7：ifC′(u)

8： End for

9：End while

10：if 存在使C(u)=VL的虚拟节点u

11：return 驳回请求

12：else return 虚拟网络的映射

3.3 收敛性分析

定理1第1阶段的博弈具有收敛性。

证明本文博弈过程的势函数定义为

Φ=∑e∈EC(e)=∑e∈E1⊆EC(e)+VL·|E2|，

(18)

其中，E1表示成功映射到物理路径的所有虚拟链路集合，根据式(14-16)计算C(e)。剩余未成功映射的虚拟链路为E2=E-E1。现在证明，当博弈方e′更改想法映射到另一条物理路径时，势函数的变化量(ΔΦ)等价于ΔC(e′)的变化量。此时需要讨论两种情况：

情况1：开始时e′∈E2，改变主意后e′∈E1。有：

ΔΦ=[∑e∈E1∪{e′}⊆EC(e)+VL·(|E2|-1)]-[∑e∈E1⊆EC(e)+VL·|E2|]

=C(e′)-VL=ΔC(e′)。

情况2：改变物理路径之前和之后均有e′∈E1。通过考察受此变化影响的所有物理路径及终端节点，我们有ΔΦ=ΔC(e′)。如果虚拟节点u从映射p1变化到映射p2，则：

映射发生变化时ΔC(e′)也会变化，且

如果|J(u,p1)-1|或|J(u,p2)-1|等于0，则将该项删除后便可获得同样结论。类似地，链路变化时证明过程同上。所以，采用式(14-16)的成本函数时，本文第1阶段的博弈是具有收敛性的潜在博弈。得证。

当势函数为Φ=∑u∈VC(u)并根据式(17)计算C(u)时，同样可证明第2阶段的博弈具有收敛性。因此，可以得出结论：整个博弈过程具有收敛性。

4 仿真实验

本节给出定量结果，证明LMF在小规模和大规模场景下均具有优异性能。首先定义两个仿真参数：通信请求率和计算请求率。通信请求率α定义为

α=(‖BS·E‖/‖E‖)/(‖BT·L‖/‖L‖)，

其中，‖BS·E‖=∑(u,v)∈Ebu,v·eu,v，‖BT·L‖=∑(p,q)∈Lbp,q·lp,q。参数α的范围为0-1，用于衡量物理链路的共享概率。若α较大，则物理链路成为性能瓶颈，不利于链路映射时的路径共享，虚拟网络映射用到的物理链路数量上升，可靠性下降。

计算请求率β定义为β=(‖MS‖/|N|)/(‖MT‖/|V|)，其中，‖MS‖=∑u∈Vmu且‖MT‖=∑p∈Nmp>0。参数β范围0-1，用于衡量数据中心满足计算请求的程度。当其数值接近于0时，每个虚拟节点均可映射到任意物理节点上。当数值接近于1时，每个虚拟节点请求大量虚拟机，且只可映射到少量物理节点上。因此，参数β可间接衡量可被虚拟节点映射的物理节点的数量。

所有的仿真结果取算法1 000次运行后的均值。为便于比较，我们对文献[12]中的博弈算法进行修改，并增加了容量约束。修改后的博弈算法首先对虚拟节点进行映射，然后对虚拟链路进行映射，因此将该算法称为节点映射优先算法(NMF)。对于NMF，每个虚拟节点均是博弈方，并映射到某一物理节点上。所有虚拟节点映射到物理节点上时，NMF算法进行第2阶段的博弈，找到被虚拟节点映射的物理节点之间的路径，实现虚拟链路映射。博弈方为了降低成本可更换到其他物理节点。所有博弈方均不改变其映射策略时，博弈终止。

4.1 小规模条件下高可靠性虚拟网络映射

物理网络拓扑结构如图1(b)所示。随机生成物理拓扑结构中各条链路和各个节点的可靠性，范围在0.99～1.00之间。同时随机确定范围在50～150之间的可用虚拟机数量，及范围在2～10 Gbps之间的可用带宽。另外，我们还生成具有3～4个虚拟节点的服务图，虚拟节点之间的虚拟链路随机确定并保证服务图连通。随机确定范围在10～100之间的请求虚拟机数量，使β=40%；随机确定范围在1～3 Gbps之间的各条虚拟链路的请求带宽，满足不同α值的需要。表1给出了基于双阶段博弈的启发式算法的运行结果。

表1 ILP， IMF和NMF的性能比较

从表1可以看出，可靠性随着α值的下降而上升。原因在于：(1)有更多条虚拟链路共享高可靠性物理链路；(2)共享程度上升，使虚拟网络在映射后的物理链路总量下降。另外，虚拟节点和虚拟链路数量上升时，分配的虚拟链路和节点数量也在上升，满足了虚拟网络的需求，因此可靠性下降。当虚拟节点数量上升时，如果α值较大(α=0.5)，则链路共享的概率较低，导致可靠性从83.80%下降到69.04%。另一方面，α值较小时(当α≤0.3或|V|=3时差值低于9%)，链路共享的概率较高，所以可靠性只下降了6%左右。因此，通信请求率较低时有助于提升可靠性。最后，我们发现LMF可获得接近于最优解的结果，当α较小时尤其如此(当α≤0.3或|V|=3时差值低于9%)。同时，发现无论在哪种情况下，LMF的性能总是优于NMF。这是因为LMF在第1阶段博弈时通过松弛虚拟节点映射约束(式(4))来扩大解空间。于是，在高效分配网络带宽时，LMF将每条虚拟链路均看作独立的博弈方，从而获得了更好的性能。

4.2 大规模条件下高可靠性虚拟网络映射

从图2可以看出，当|V|增加时，由于虚拟网络具有更多个物理节点和链路，所以可靠性下降。其次，α=0.1时的可靠性下降速度要快于α=0.05时，原因是可以共享物理链路的虚拟链路数量下降。例如，当|V|=10时，|E|=27条虚拟链路需要映射。然而，每条物理链路平均来说只能与1/α=10条虚拟链路共享，导致虚拟网络对物理链路的需求量变大，可靠性下降，请求驳回概率上升。图3中结果也印证了上述结论。另外，LMF在可靠性和请求驳回概率方面的性能均优于NMF。原因在于：(1)LMF在第1阶段博弈时放松了虚拟节点映射约束(式(4))，增大了解空间，降低了请求驳回概率；(2) LMF在第2阶段的博弈采用第1阶段的博弈结果作为输入，而不是像NMF那样将虚拟节点随机映射到物理节点上，因此提升了可靠性。

此外，根据图2和3的仿真结果分析可知，通过如下方式可提升RVNM的可靠性，降低请求驳回概率：(1)将虚拟网络限定于少量分布式数据中心中，从虚拟链路数量方面减少数据中心间的通信；(2)增加可用网络带宽，使更多虚拟链路共享物理链路；(3)降低虚拟链路的带宽请求。

图2 可靠性 vs虚拟节点的数量

图3 请求驳回概率vs虚拟节点的数量

4.2.2 计算容量约束和带宽容量约束对高可靠性虚拟网络映射的影响 对于物理网络拓扑结构，所有参数的生成方法与4.2节相同。对于服务图，随机生成虚拟网络的虚拟链路且|V|=6，|E|=10。随机生成虚拟机请求数量，满足不同β值的需要；随机生成各条虚拟链路的带宽请求，满足不同α值的需要。图4～5比较了两种约束对虚拟网络映射的影响。从图4可以看出，当计算请求率(β)低于 0.8时可靠性较为稳定。原因在于：(1)每个虚拟节点映射到至少1个既满足计算容量约束且未被分配给其他虚拟节点的物理节点上；(2)网络带宽容容量约束在虚拟网络映射结果中占据主导地位。另一方面，如果β≥0.8，无论带宽容量约束如何，由于难以找到足够多的满足计算容量约束的物理节点，导致可靠性严重下降。最后，图5表明只有β≥0.8时计算容量约束才对请求驳回概率具有重大影响。因此，当β<0.8时，虚拟节点映射到物理节点的概率很大。

图4 可靠性vs计算请求率(β)

图5 请求驳回概率vs计算请求率(β)

5 结束语

本文在计算容量约束和带宽容量约束两种条件下研究了云请求的高可靠性虚拟网络映射(RVNM)问题。该问题被证明是NP难题，并提出ILP模型来获得小型网络的近似最优解。对于大型网络，进一步提出基于双阶段博弈的链路映射优先(LMF)算法来求解RVNM问题。定量结果表明，通过松弛第1阶段博弈过程的虚拟节点映射约束，LMF可在更大解空间搜索可行解，因此无论是对小型网络还是大型网络，LMF的可靠性和请于驳回概率性能均优于已有算法。在下一步工作中，除了可靠性之外，我们将继续研究具体底层网络(比如光纤网络)的各种故障类型，以及虚拟网络映射的生存性。