0 概述

为满足云计算多样化业务需求, 云提供商运用网络虚拟化技术支持创建共享物理网络和运行多个异构虚拟网络^[1]。虚拟网络映射(Virtual Network Mapping, VNM)是网络虚拟化的一个关键技术之一, 由于虚拟网络请求中节点和链路的资源需求约束, 虚拟网络映射问题是NP-hard问题^[2]。随着网络虚拟化技术的快速发展和广泛应用, VNM作为其中急需解决的关键问题, 已成为当前热门的研究领域^[3]。

目前虚拟网络映射和优化问题已有一定的研究成果, 主要的映射算法可以分为基于图论、基于拓扑感知、基于数学规划模型3种^[4]。基于图论的算法是在映射过程中使用图论的方法, 如构子图搜索^[5-6]、子图分割^[7-8]方法等。基于拓扑感知的算法是通过拓扑感知分析网络中资源重要性的差异, 用以优化资源选取。文献[9]利用7个互补特征综合考虑虚拟网络的拓扑属性。文献[10]考虑节点和链路的属性, 提出基于接近中心度的映射算法。文献[11]引用加权相对熵的概念, 通过对虚拟网络和物理网络的拓扑感知适应物理资源的动态变化。基于数学规划模型^[12-13]的算法将映射问题建模为数学问题, 文献[14]基于线性规划理论, 通过预处理不同类型的请求以降低映射成本。

上述算法对先到达的虚拟网络请求优先分配资源, 使不同请求映射间缺少协同, 导致物理资源碎片化, 降低了后续到达请求的接受率。对此, 本文提出基于最优子图的虚拟网络映射算法。通过优化的重边匹配(Band Heavy Edge Matching, B-HEM)算法粗化虚拟网络拓扑, 并利用广度优先搜索(Breadth First Search, BFS)算法建立候选物理子网集合, 将虚拟网络请求映射至最合适的物理子网, 从而加强不同请求之间的协同, 降低物理资源碎片率。

1 虚拟网络映射问题描述 1.1 网络模型

虚拟网络映射模型如下:

1) 物理网络。可以抽象为加权无向图G_s=(N_s, L_s, A_s^N, A_s^L), 其中, N_s和L_s分别为物理网络的节点集合和链路集合, A_s^N和A_s^L分别表示物理节点n_s(n_s∈N_s)和物理链路l_s(l_s∈L_s)的属性集合。n_s的属性为剩余节点计算资源cpu(n_s)和节点位置loc(n_s), loc(n_s)=(x_s, y_s)为节点二维坐标, l_s的属性为剩余链路带宽资源bw(l_s)。

2) 虚拟网络请求。可以抽象为加权无向图G_v=(N_v, L_v, C_V^N, C_C^L, T_a, T_l), 其中, N_v和L_v分别为虚拟网络请求的节点集合和链路集合, C_v^N和C_v^L分别表示虚拟节点n_v(n_v∈N_v)和虚拟链路l_v(l_v∈L_v)的约束条件, T_a和T_l分别表示请求的到达时间和生存时间, n_v的约束条件为该节点的计算资源需求cpu(n_v)以及映射距离约束Dis(n_v), l_v的约束条件为该链路带宽资源需求bw(l_v)。

3) 虚拟网络映射。可以描述为G_v与满足约束条件的G_s子集的映射关系, M:G_v→G_sub=(N′_s, L′_s, R_Nsub^s, R_Lsub^s), 其中, G_sub∈G_s表示分配给G_v的物理资源, N′_s∈N_s, L′_s∈L_s, R_Nsub^s和R_Lsub^s分别表示分配给虚拟网络的节点资源和链路资源。

虚拟网络映射示意图如图 1所示。

1.2 评价指标

虚拟网络映射的一个主要挑战是找到带有约束条件的虚拟网络请求到物理网络的有效映射, 以便剩余物理资源可以承载更多的请求^[15]。本文以链路映射平均跳数、虚拟网络请求接收率及收益开销比评价算法性能。

链路映射平均跳数为:

$ \bar h\left( {{G_v}} \right) = \sum\limits_{{l_v} \in {L_v}} {h\left( {{M^L}\left( {{l_v}} \right)} \right)} /\left| {{L_v}} \right| $

(1)

其中, M^L(l_v)为承载虚拟链路l_v的物理路径, L_v为请求中虚拟链路的总数。

映射请求接受率为:

$ \mathop {\lim }\limits_{T \to \infty } \frac{{\sum\limits_{t = 0}^T V {N_m}(t)}}{{\sum\limits_{t = 0}^T V N(t) + \eta }} $

(2)

其中, VN_m(t)为映射成功的请求集合, VN(t)为所有到达的请求集合, η为趋近于0的正数, 防止分母为0。

t时刻G_v的映射收益开销比如下所示。

定义t时刻G_v的映射收益为:

$ R\left( {{G_v},t} \right) = \sum\limits_{{n_v} \in {N_v}} c \left( {{n_v}} \right) + \alpha \sum\limits_{{l_v} \in {L_v}} b w\left( {{l_v}} \right) $

(3)

其中, α为节点与链路的收益均衡因子, 本文中α=1。

定义t时刻G_v的映射开销为:

$ C\left( {{G_v},t} \right) = \sum\limits_{{n_v} \in {N_v}} c \left( {{n_v}} \right) + \beta \sum\limits_{{l_v} \in {L_v}} h \left( {{l_v}} \right)bw\left( {{l_v}} \right) $

(4)

其中, h(l_v)为虚拟链路l_v映射到物理链路的跳数, β为节点与链路的开销均衡因子, β=1。

定义网络的收益开销比为:

$ R/C = \mathop {\lim }\limits_{T \to \infty } \frac{{\sum\limits_{t = 0}^T {\sum\limits_{{G_v} \in V{N_m}(t)} {R\left( {{G_v},t} \right)} } }}{{\sum\limits_{t = 0}^T {\sum\limits_{{G_v} \in VN(t)} C } \left( {{G_v},t} \right)}} $

(5)

2 虚拟网络映射算法

现有虚拟网络映射算法可分为一阶段映射(协同映射)与两阶段映射算法^[16]。相较于一阶段映射^[17], 两阶段映射算法^[18]不仅复杂度较低, 而且可在计算资源开销较小情况下获得较好的映射结果, 因此, 本文选取两阶段映射算法。首先使用B-HEM算法粗化到达的虚拟网络请求, 并运行BFS算法为请求创建候选物理子网集合Ω(G_sub), 之后利用贪婪算法^[19]映射虚拟节点, K最短路径算法映射虚拟链路, 将请求映射至最优物理子网G_subⁱ。

2.1 虚拟网络的粗化请求

定义链路重要度为链路带宽资源与两端节点计算资源和的比值, 即:

$ VL\left( {{l_v}} \right) = band\left( {{l_v}} \right)/\sum\limits_{{n_i} \in {l_v}} c pu\left( {{n_i}} \right) $

(6)

根据VL(l_v)值对虚拟链路从大到小排序, 如果链路两端节点计算资源和小于物理网络剩余计算资源最大值cpu_max, 则将两节点整合, 每次整合后更新请求, 生成拥有更大带宽需求的虚拟网络拓扑, 如果新生成链路的带宽大于最大剩余物理带宽band_max, 且链路两端节点计算资源和大于cpu_max, 则放弃此次整合。具体粗化过程如算法1所示。

算法1  Coarsening(G_v)算法

输入  G_v, cpu_max, band_max

输出  G_v

1.for每一条虚拟链路  do

2.计算VL(l_v)

3.end for

4.将链路依据VL(l_v)值从大到小排序, 结果存入Linklist

5.for每一条虚拟链路l_v∈Linklist do

6.if band(l_v)>band_max$\& \sum\limits_{{\rm n_{v} \in l_{v}}} $cpu(n_v)>cpu_max

7.return G_v

8.else if $\sum\limits_{{\rm n_{v} \in l_{v}}} $ < cpu_max

9.合并2个虚拟节点, 更新虚拟网络请求

10.Coarsening(G_v)

11.return G_v

12.end for

13.return G_v

2.2 候选物理子网的创建

定义节点资源度和接近中心度如下:

1) 节点资源度为节点计算资源与所有相邻链路带宽资源的和:

$ R\left( {{n_i}} \right) = cpu \left( {{n_i}} \right) + \sum\limits_{{l_v} \in {L_v}} b w\left( {{l_i}} \right) $

(7)

2) 接近中心度为节点与全体可到达节点最短跳数之和的倒数:

$ D\left( {{n_i}} \right) = \frac{1}{{\sum\limits_{{n_i} \ne {n_j}} d \left( {{n_i},{n_j}} \right)}} $

(8)

定义节点重要度为:

$ VN\left( {{n_i}} \right) = R\left( {{n_i}} \right)D\left( {{n_i}} \right) $

(9)

定义网络资源度为:

$ \mathit{Re}\left( {{G_i}} \right) = \sum\limits_{{n_i} \in {G_i}} {cpu} \left( {{n_i}} \right) + \sum\limits_{{l_i} \in {G_i}} b w\left( {{l_i}} \right) $

(10)

为到达的虚拟网络请求建立物理子网G_sub^s=(N_sub^s, L_sub^s), 其中, N_sub^s∈N_s为满足计算资源约束和位置约束的物理节点集合, L_sub^s∈L_s为满足带宽资源约束的物理链路集合。将物理节点n_s∈N_sub^s按照VN(n_s)降序排序, 以VN(n_s)最大的n_s为根节点运行BFS算法生成候选物理子网G_subⁱ=(N_sⁱ, L_sⁱ), 其中, N_sⁱ∈N_s, L_sⁱ∈L_s。将G_subⁱ放入候选物理子网集合Ω(G_subⁱ), 删除N_sub^s和L_sub^s中相应的物理结点n_s∈N_sⁱ和物理链路l_s∈L_sⁱ。将Ω(G_subⁱ)中的候选物理子网按照Re(G_subⁱ)值从大到小排序, 删除Re(G_subⁱ)值小于虚拟网络请求的候选物理子网。候选物理子网创建过程如算法2所示。

算法2  Creating_subnet(G_subⁱ)算法

输入  G_v, G_s

输出  Ω(G_sub)

1.for每一个待映射的虚拟网络请求do

2.建立物理子网G_sub^s=(N_sub^s, L_sub^s), 其中, N_sub^s∈N_s为满足计算资源约束和位置约束的物理节点集合, L_sub^s∈L_s为满足带宽资源约束的物理链路集合。

3.if N_sub^s或L_sub^s为空

4.return false

5.else

6.for每一个n_s∈N_sub^s do

7.计算VN(n_s)

8.end for

9.do

10.以VN(n_s)值最大的物理节点为根节点运行BFS算法, 生成候选物理子网G_subⁱ

11.将G_subⁱ放入候选物理子网集合Ω(G_subⁱ), 删除N_sub^s和L_sub^s中相应物理结点n_s∈N_sⁱ和物理链路l_s∈L_sⁱ

12.while N_sub^s和L_sub^s不为空

13.end if

14.for每一个候选物理子网G_subⁱ∈Ω(G_subⁱ) do

15.计算Re(G_subⁱ)

16.end for

17.将候选物理子网按Re(G_subⁱ)值从大到小排序, 删除Re(G_subⁱ)值小于虚拟网络请求的候选物理子网

18.end for

19.return Ω(G_sub)

3 性能评估与分析

本文通过Matlab进行仿真实验评估。使用GT-ITM^[20]拓扑生成工具创建实验所需的虚拟网络和物理网络拓扑, 具体实验参数配置如表 1所示, 其中, 所有虚拟节点的位置约束为Dis(n_v)=200。

本文实验分为两部分, 验证所提算法性能和分析位置约束条件对算法性能的影响。每次实验需要30 000个时间单元, 约有1 500个虚拟网络请求到达, 以10次实验结果的平均值作为最终结果。

3.1 算法性能比较

将本文所提B-VNE算法与TA-VNE算法^[11]、DV-VNE算法^[14]、G-VNM算法^[19]进行对比, 从请求接受率、收益开销比两方面验证所提算法性能。

图 2为4种算法性能的变化情况。其中, B-VNE算法的请求接受率和收益开销比最大, 分别为0.68和0.58, G-VNM算法的请求接受率和收益开销比最小, 分别为0.64和0.53。仿真结果表明, B-VNE算法性能较好。

由图 2可知, 在当前实验参数下4种算法性能较为接近, 位置约束较小导致虚拟节点可映射的候选物理节点较少, 减小了算法解的多样性。为进一步研究位置约束条件对请求接受率和收益开销比的影响, 探索可提升算法性能的因素, 本文设计了不同位置约束下算法性能对比实验。

3.2 位置约束对算法性能的影响

其他实验参数不变, 所有节点的位置约束分别设为D(n_v)=500、D(n_v)=1 000, 根据链路映射平均跳数、虚拟网络请求接受率、收益开销比的变化情况分析位置约束对算法性能的影响。

表 2为3种位置约束下4种算法的平均跳数(h)变化情况, 可以看出, 随着D(n_v)的增大, B-VNE算法和TA-VNE算法的h明显减小, 而DV-VNE算法和G-VNM算法的h逐渐变大, 变大幅度较小。

图 3、图 4分别为D(n_v)=500、D(n_v)=1 000时4种算法请求接受率和收益开销比的变化情况。可以看出, B-VNE算法和TA-VNE算法的性能明显提高, 而DV-VNE算法和G-VNM算法性能变化较小。

结合表 2与图 2~图 4可以看出, 位置约束、链路映射平均跳数与算法性能具有相关性。4种算法的h在位置约束较小时比较接近, 且较大, 这与图 2中4种算法性能接近相符合。在表 2不同位置约束下, B-VNE算法的h最小, 这是因为B-VNE考虑了不同虚拟网络请求间的协同, 在映射前粗化请求的拓扑, 且考虑位置约束, 利用BFS算法为请求创建合适的子网, 进一步缩短了链路映射跳数, 减小了映射开销, 使相同的物理资源可以承载更多的请求, 因此它的请求接受率和收益开销比在4种算法中也是最优的。TA-VNE算法的h仅次于B-VNE, 这是因为其在映射时只考虑了节点的邻接关系与位置约束, 所以性能提升不如B-VNE明显。G-VNM算法和DV-VNE算法的h较大, 由于两者并未考虑虚拟网络请求映射前后拓扑的一致性, 无法有效减小链路映射长度, 因此性能较差。

4 结束语

本文通过分析云计算中的虚拟网络映射问题, 提出一种基于最优子网的虚拟网络映射算法。该算法通过创建候选物理子网映射虚拟网络请求, 以避免先到达的请求占用过多的关键资源, 从而提高物理资源利用率。仿真实验结果表明, 该算法能够减小虚拟链路的映射跳数, 提升虚拟网络请求接受率和收益开销比, 且算法性能在节点位置约束条件放宽后明显提升。