基于全局资源容量的虚拟网络嵌入算法
2019-06-11孙新丽
孙新丽
摘要：采用全局资源容量（CRC）度量方法来量化每个底层物理节点的嵌入潜力，并提出了一种启发式虚拟网络嵌入算法（CRC-VNE），最大限度地提高基础设施提供商（InP）的收益。该算法采用贪婪的负载均衡方式依次嵌入每个虚拟节点，并结合基于Dijkstra算法的最短路径路由嵌入每个虚拟链路。仿真结果表明：与考虑整个底层物理网络资源的RW-MM-SP算法和TA算法相比，所提出的GRC-VNE算法能够实现更低的请求阻塞概率和更高的收益。
关键词：网络虚拟化;全局资源容量;虚拟网络嵌入;虚拟网络请求
中图分类号：TP393
文献标识码：A
近年来网络虚拟化受到了研究界的高度关注[1-3]，网络虚拟化可在底层物理网络上提供多个虚拟网络（VN），以此共享计算和网络资源。VN是由一组虚拟节点（如虚拟路由器）组成的逻辑拓扑结构，这些虚拟节点通过底层物理网络上的相应虚拟链路相互连接[4]。在这种情况下，传统的互联网服务提供商（ISP）可以分为基础设施提供商（lnP）（如云提供商）和服务提供商（SP）（如云用户）。多个SP可动态构建VN，并从InP租赁基础设施来聚合最终用户的需求。如果给定一组在节点和链路上具有某些资源需求的VN请求（VNR），则在底层物理网络中找到满足每个VNR的节点和链路的特定子集的问题称为虚拟网络嵌入（VNE）问题[5-6]。在解决VNE问题时，InP通常在底层建立网络来最大化其收益。
然而，VNE问题是NP问题[6]。文献[7]对VNE问题的研究依赖启发式算法来平衡性能和计算复杂性之间的权衡。通常现有算法只适用于两种情况：（1）在没有节点或链路要求的情况;（2）底层物理网络中的节点和链路上具有无限的资源。文献[8]通过分别求解节点映射和链路映射来降低计算复杂性。文献[9]通过联合优化两个子问题（即节点映射和链路映射）来提高计算性能。文献[10]提出了协调VNE（ CO-VNE）算法来确定性能和计算复杂度之间的最佳权衡，即在节点映射阶段考虑了链路映射约束，从而了减轻由于分离处理而导致的性能下降。
提出了一种有效的CO -VNE算法来最大化InP的收益，通过建立了全局资源容量（GRC）度量来量化所有节点在底层物理网络中的嵌入潜力。每个节点的GRC计算都考虑了整个网络的资源。利用随机游走形式表示GRC并揭示了其物理意义。设计了一种基于GRC的CO-VNE算法，即基于全局资源容量的虚拟网络嵌入（GRC-VNE）。该算法采用负载均衡的方式将虚拟节点嵌入到底层物理网络中GRC最高的节点上，并利用最短路径的路由方法进行链路映射。
1 模型建立
1.1 VNE模型
在VNE问题中，从底层物理网络分配资源（用于节点的计算资源和链路的带宽資源）来满足VNR的需求。当InP得到一个VNR时，InP应该决定是否接受它。如果VNR被接受，则应该在相应的物理节点上分配计算资源，并在相应的物理链路上分配带宽来满足VNR的需求，当VNR返回时，所分配的资源将被释放。底层物理网络和VNR的模型如下所示：
1.3 VNE收益模型
对于每个VNR，本文都采用基于Amazon WebServices（ AWS）中“按需”云服务价格方案的“按用户付费”收益模式[11]。对于VNR的ω为InP创造的收益为：
该上界可以通过以下假设情况来确定：
（1）每个VNR等同于底层物理网络;
（2）当前的VNR过期时，后续的VNR到达。
在这种情况下，每个VNR都满足于最小的底层物理资源量，并且底层物理网络被完全占用。因此，时间积累的收益将最大化，从而收益将最大化。
2.2 收益惩罚因素
实际上，观察到的InP收益远低于底层物理网络提供的上界。这种差距是由于与VNR到达相关的不规则性而导致。对于一组非理想的VNR，以下两种情况将增加InP对收益的惩罚：
（1）情况1：由于资源不足，底层物理网络无法容纳VNR，因此拒绝VNR。资源不足可能是由于基础资源限制或不适当的VNE算法浪费了资源。
（2）情况2：即使接受VNR，虚拟边缘的子集映射到跨越多个边缘的底层物理网络中的路径上。对于情况1，本文可以将阻塞概率降到最低，使底层物理网络以其有限的资源接受大多数的VNR。对于情况2，本文可以最大限度地提高每个VNR的收益一成本比，从而在单个VNR上尽可能减少资源成本。
3 基于全局资源容量的VNE算法
3.1 全局资源容量（GRC）
作为节点映射阶段考虑链路映射约束的尝试之一，文献[12]在节点映射阶段考虑了链路映射约束，制定了局部资源容量（IRC），并定义为节点计算资源和链路带宽资源总和的乘积。但是，LRC有以下缺点：
①局部性问题：如文献[13]所述，节点的LRC仅考虑节点本身的资源及其事件链路，这并不能揭示节点的实际嵌入潜力。例如，如图2（a）所示，节点A和D的LRC值与50x（ 20+20） =2000个单位相同的LRC值。当节点A的相邻节点可用资源大于节点D的相邻节点可用资源时，节点A的嵌入潜力应大于节点D的嵌入潜力。
②“孤岛”问题：当网络中的负载分配不平衡时，仍然有大量可用资源的节点将成为网络中的“孤岛”，并且基于LRC无法正常利用这些资源节点。例如，如图2（b）所示，节点A仍然有相当大量的计算资源，因此即使其事件链路的带宽资源非常有限，其LRC值仍然与节点B相同。
3.2 贪婪节点映射
在节点映射阶段，采用贪婪映射算法。其工作原理如下：在计算了底层物理网络和VNR的GRC向量后，分别根据GRC对两种拓扑的节点进行降序排序。从底层物理网络的负载平衡角度来看，贪婪节点映射是通过对两个节点进行自上而下的处理，并逐个映射节点来实现，类似于Mergesort算法，只要满足计算要求，VNR中GRC最大虚拟节点总可以映射到底层物理。如果使用任何底层物理节点都不能满足计算资源需求，那么VNR将会被阻塞。并且该贪婪映射算法的时间复杂度为O（|Vs‖Vr|）。
3.3 基于最短路径的链路映射
在链路映射阶段，采用基于最短路径的链路映射算法。对于VN请求中的每一条边，使用Dijkstra算法来计算底层物理网络中相应节点之间的最短路径。该算法通过对底层物理中没有足够可用带宽资源的所有链路进行预分割来提高效率。如果链路映射失败（即无法成功嵌入任何虚拟链路），则将恢复底层物理网络状态，并将VNR标记为阻塞。基于最短路径的链路映射算法的时间复杂度为O（|Er‖Es|log|Vs|）。
4 数值模拟
利用数值模拟来比较GRC-VNE与RW-MM-SP算法[16]和TA算法[17]的性能。考虑两个性能指标：等式（6）的收益和等式（7）的VNR阻塞概率。
4.1 模型模拟
采用了与文献[18]相似的模型模拟，底层物理网络和VNR的拓扑结构由GT-ITM工具随机生成。对于底层物理网络，采用均匀分布随机选择初始可用计算资源和带宽资源。在每个VNR中，随机选择每个虚拟节点的计算资源需求和每个虚拟链路的带宽需求。VNR中的虚拟节点数根据均匀分布从2到20进行选择。虚拟链路连通率（VNR中任意两个节点连接的概率）设为η。因此，VNR中的平均链路数为η[n（n-l）]/2，其中n是虚拟节点的数量。VNR逐个到达形成泊松过程，平均到达率为A个请求，每个请求的存在期遵循负指数分布，平均为I/μ=500 s。因此，VNR的负载可以用λ/μ在Erlangs中进行量化。实验模拟的参数如表1所示。
4.2 性能比较
使用固定流量负载评估上述三种VNE算法的性能，固定鏈路连通率为0.5 MB/s，并模拟运行50000 s来查看其长期运行结果。在模拟中，设定α=β=1，σ=0.00001，d=0.85，。RW-MM-SP和TA的所有参数分别取选自文献[16]和[17]。三种算法的长期平均收益如图3所示。
由图3可以看出，所提出的GRC-VNE优于其他两种算法。这是由于GRC可以通过克服LRC的局部性问题和“孤岛”问题来更有效地量化嵌入潜力。因此，在提供的负载下，GRC-VNE只有VNR的较小阻塞概率。在我们假设的随机流量模型下，收益可以近似为：
其中，R0（ω）和τω分别是指每个请求的平均收益和每个请求的平均存在期。三种算法的阻塞概率如图4所示。由图4可见，本文所提出的算法具有最低的长期阻塞概率，从而收益最高。
4.3 敏感性分析
比较了三种算法在VNR的不同的流量负载和链路连通率下的性能。三种算法在不同流量负载下的收益和阻塞概率分别如图5和图6所示。
由图5和图6可以看出，所提出的GRC-VNE算法在所有流量负载中都获得了最高收益。收益随着流量负载的增加而增加。随着流量负载的增加，底层物理网络的性能越来越接近其容量。因此，如果接受额外的VNR可能会消耗更多的资源，从而降低收益一成本比。随着流量负载的进一步增加，收益将趋于平缓。通过观测所有三种算法的阻塞概率，这些算法将随着流量负载的增加而合并。
通过改变VNR的链路连通率来进行相同的灵敏度分析。静止状态下不同链路连通率下长期平均收益的比较和阻塞概率的比较分别如图7和图8所示。
由图7和图8可以看出，所提出的算法产生的收益最高，阻塞概率最低。此外，当链路连通率为固定值时，收益首先增加然后降低，当链路连通率是固定值时，导致收益达到峰值。如等式（18）所示，由阻塞概率和每个请求的收益之间的基本权衡来实现。随着链路连通率的提高，阻塞概率将单调增加;而每个请求的平均收益也随着需要更多资源而增加。由于阻塞概率增加而导致的边际惩罚完全由每个请求增加收益的边际收益补偿。
4.4 时间复杂性
比较了在同一底层物理网络上嵌入VNR每种算法的平均运行时间，该度量可作为三种算法时间复杂度的指标。本文的仿真环境为Matlab R2012A，在3.10 GHz Intel Core i3 -2100 CPU和2.00 GBRAM的计算机上运行。三种算法在不同链路连通率下的平均运行时间如表2所示。
由表2所示，所提出的算法对于所有情况下的运行时间最短，其运行时间约为其他两种算法运行时间的20-30%。该运行时间增益的一部分来源于算法中的优化步骤，即在嵌入虚拟链路之前预分割了所有不可行的链路，并且对于每个虚拟链路只需要执行一次最短路径算法。而对于其它两种VNE算法中的最短路径方案，在路径计算中仍然考虑了不可行链路，从而增加了运行时间。
5 结论
建立了GRC来量化节点在底层物理网络中的嵌入潜力，并提出了一种新型的VNE算法。该算法使用GRC平衡负载的方式将虚拟节点映射到底层物理节点上，采用基于最短路径的链路映射。仿真结果表明，所提出的算法优于其他两种VNE算法。
参考文献
[1]范宏伟，胡宇翔，兰巨龙，基于FPGA的虚拟网络功能数据包处理加速架构[J].计算机工程，2018，44（08）：112-119+126.
[2]方子璐，杨俊杰，刘娟.基于虚拟局域网的智能变电站通信网络实时性仿真[J]电测与仪表，2017，54（24）：62-67+93.
[3]高兴海，计算机网络信息安全中虚拟专用网络技术的运用[J].通讯世界，2017（24）：134-135.
[4]周非，高建军，范馨月，等.无线传感网络中基于虚拟力的节点动态覆盖算法[J].系统仿真学报，2018，30（08）：2908-2917.
[5]邹裕，覃中平，混合网络的资源分配与虚拟机部署优化算法[J].控制工程，2018，25（ 03）：509-515.
[6]李芳，高翔.局部线性嵌入和深度自编码网络的降维方法的比较[J]中国海洋大学学报：自然科学版，2018，48（2）：215- 222.
