一种虚拟网络中基于灰色预测的自适应动态资源分配方法

摘要

本发明针对现有核心虚拟网络中资源分配方法算法不能快速降低分配误差，没有考虑全局虚拟资源分配是否合理，并且没有将资源利用率与资源分配过程相联系从而无法有效的调节资源利用率等问题，提出一种全新的面向虚拟网络的资源分配方法。该方法首先提出了资源使用预测的概念，通过灰色模型来预测各虚拟节点的资源使用量，然后通过自适应反馈算法进行虚拟资源的分配，最后进行检测再分配以确保资源分配的合理性，完成虚拟网络的资源分配过程。该方法不仅能够满足与多个虚拟平面的资源分配，迅速降低了资源动态分配值与实际资源使用值之间的误差，还能够分别控制各虚拟平面节点的资源利用率，并保证资源分配结果的合理有效性。

说明书

技术领域：

本发明主要针对虚拟网络环境下的资源分配技术，特别是应用于虚拟网络的一种基 于预测的自适应动态资源分配提供了技术方案。

背景技术：

互联网从最初只考虑“尽力而为”的数据业务，发展到现在互联网的应用已经无所不 包，新型业务层出不穷，日常生活中常见的VoIP业务、IPTV业务、3G业务等等，都是 在IP技术的基础上建立的。然而，因为互联网是由多种服务提供商提供服务，使得采纳 一种新的架构或者在现有架构上进行一些修改变得十分困难，导致现有的互联网技术不利 于支持移动性，影响了核心路由的扩展性，降低了现有安全方法的效能，阻碍了网络新技 术的发展。

网络虚拟化是解决网络僵化问题的一个重要方法。通过允许网络共享相同的物理链路 和路由器等物理资源，针对不同的业务类型，构建不同的虚拟业务平面。在健壮的、可信 的、易于管理的虚拟环境下，为各个虚拟平面中的每个虚拟节点请求分配合适的虚拟资源， 从而实现资源共享，并提高网络生存性，提升自身的服务质量和用户的满意度。

在网络虚拟化环境下，现有网络被划分为底层网络(SN,substrate network)和虚拟网络 (VN,virtual network)。底层网络中的节点是物理层的核心路由节点(CN,core node)，通过 节点虚拟化技术，可将该节点虚拟化为几个虚拟节点(VN,virtual node)，从而构建不同业 务类型的虚拟业务平面，如图1所示。如何将有限的底层网络资源分配给尽可能多的虚拟 网络，即如何将有限的核心路由节点资源合理分配给每个对应的虚拟节点，提高基础设施 资源利用率，是网络虚拟化中一个关键问题。

当前针对虚拟网络的动态资源分配问题，国内外主要有基于效用函数，基于控制理论 和基于预测自适应理论等方法。例如：

(1)将系统被分为两层，上层是资源决定者，对全局的资源分配负责，从而实现全局效 用的最大化。下层则是应用管理者，它通过调整给定资源的局部参数，实现本地效用的最 大化。效用函数进行效用的转化和计算，对各个应用管理者之间的行为进行编排。应用管 理者转化效用函数的状态，将下层效用函数转化为上层所使用的资源级效用函数，资源定 者运用计算系统级的效用得到全局的资源分配方案，并以此来调整下层应用管理者的行 为。

(2)使用一个两层的资源管理系统，通过虚拟层的本地控制和资源池层的全局控制之间 的交互行为来动态分配资源，由于负载变化的不确定性和复杂性，在本地控制中采用了基 于模糊逻辑的方法。

(3)采用一种基于动态资源分配的虚拟机群负载均衡方法，这种方法可以实时地监控虚 拟机和物理机的资源利用率，然后通过调用资源重分配算法，在同一个物理机上，获得虚 拟机的局部负载平衡；同时在多个物理机之间，通过虚拟机的实时迁移(1ive migration)获 得虚拟机群全局的负载平衡。

(4)根据物理节点平均负载差异度，动态的为虚拟节点分配资源，从而使物理节点的 负载更加均衡，提高物理资源的使用效率；同时结合当前物理网络容忍的节点负载差异动 态地进行虚拟节点迁移，并通过综合影响因子为虚拟节点选择合适的目标宿主，减少虚拟 节点迁移对物理链路带宽和虚拟链路时延的影响。

然而，上述几种故障检测方法存在着如下的不足：a.需要大量监控后再计算或者大量 信息的交互，每次动态资源分配需要时间过长，不能满足快速的资源分配；b.没有考虑如 何减少资源分配值与资源实际使用值的误差，使分配结果更加合理准确；c.没有考虑虚拟 节点上资源利用率的变化过程，从而也没有考虑到如何提高虚拟网络的资源利用率并控制 资源利用率的变化范围；d.没有考虑初次初始分配失败的情况，该如何调整才能迅速完成 资源分配的再调整，从而满足网络要求。

发明内容：

本发明的目的是克服上述中所提到的不足，针对虚拟网络环境下的资源分配问题，提 供一种基于灰色预测的自适应动态分配的方法，对虚拟平面上的虚拟节点进行合理的资源 分配，满足虚拟平面的资源需求。

为了达到上述目的，本发明的具体技术方案如下：

一种虚拟网络中基于灰色预测的自适应动态资源分配方法，包括以下步骤：

1）建立虚拟业务平面后，由物理层核心节点负责给虚拟平面上各虚拟节点实时分配资 源，并在下一时刻的资源分配时，回收多余资源或者继续分配新的资源；

2）上述核心节点在每个固定时间间隔内根据前n个时间间隔虚拟节点资源使用量，通过 灰色预测模型预测出该虚拟节点n+1时刻的资源使用量；

3）上述核心节点依据预测的资源使用量，提出一种基于误差反传调整的自适应分配算 法，对各虚拟节点进行资源的初始分配；

4）上述分配结果通过判断函数的验证，如果满足则完成虚拟资源的分配过程；

5）上述判断函数条件如果不成立，修改分配过程参数，进行虚拟资源重分配，完成虚拟 资源分配过程。

本发明的有益效果是：该方法不仅能够满足多个虚拟平面的资源分配，并在分配过程 中迅速降低了资源动态分配值与实际资源使用值之间的误差，还能够分别控制各虚拟平面 节点的资源利用率，并保证资源分配结果的合理有效性。

附图说明：

图1为虚拟网络的平面结构示意图；

图2为虚拟网络环境下虚拟节点的资源分配方法流程图；

图3分别为20个样本时间间隔内三个虚拟节点的资源分配情况及资源利用率的变化 过程；

图4为未引用分配误差比率进行资源重分配时20个样本时间间隔的三个虚拟节点的 资源分配情况；

图5为引用分配误差比率后进行资源重分配时20个样本时间间隔的三个虚拟节点的 资源分配情况；

图6为20个样本时间间隔内三个虚拟节点的资源分配均方误差值。

具体实施方式：

为了使本发明的内容、效果以及优点更加清楚明白，下面结合附图和具体实施例子对 本发明进一步地详细阐述。

图1为某虚拟网络的平面结构示意图。如图1所示，经过虚拟化后，物理层平面分为 m个虚拟业务平面，相应的，每个物理层核心节点虚拟化成m个虚拟节点。本发明就是 要实现每个核心节点对应的m个虚拟节点的资源分配过程。

本发明具体的实施步骤如下所述：

【301】本方案对各虚拟节点采用相同的方法进行资源分配。对于一个物理层核心节 点对应的m个虚拟节点，在某一时刻同时启用该自适应资源分配方法，然后由物理层核 心节点完成资源的分配和回收，这一功能由虚拟化的核心路由节点的控制模块完成。

对于该分配方法的启动时间，其由网络状况决定，一般情况下周期间隔可取为60s， 在每个周期开始时，由虚拟化的核心路由节点控制模块对m个虚拟节点同时启用该分配 方法，待分配方法计算出各虚拟节点的资源分配值，再由虚拟化核心路由节点的分配模块 进行虚拟资源的分配及回收过程。本方案重点关注各虚拟节点资源分配值的计算过程。

【302】由于每个虚拟节点的资源预测和资源分配过程原理都是一样的，虚拟节点的 资源预测和分配计算过程均只针对一个虚拟节点讨论。

对于某一个虚拟节点来说，设其前n个间隔资源使用量为时间序列 X⁽⁰⁾={x⁽⁰⁾(1),x⁽⁰⁾(2),...,x⁽⁰⁾(n)}。

为了使其成为有规律的时间序列数据，对其作一次累加生成运算，即令 从而得到新的生成数列X⁽¹⁾，X⁽¹⁾={x⁽¹⁾(1),x⁽¹⁾(2),...,x⁽¹⁾(n)}。

则生成的离散形式的微分方程具体的形式为

$\frac{\mathrm{dx}}{\mathrm{dt}}+\mathrm{ax}=u---\left(3.1\right)$

将代入（3.1）式得

$x^{\left(0\right)}(t+1)=-\frac{1}{2}a[x^{\left(1\right)}\left(t\right)+x^{\left(1\right)}(t+1)]+u$

由其离散形式可得到如下矩阵：

$\left(\begin{array}{c}{x}^{\left(0\right)}\left(2\right)\\ x^{\left(0\right)}\left(3\right)\\ .\\ .\\ .\\ x^{\left(0\right)}\left(n\right)\end{array}\right)=a\left(\begin{array}{c}-\frac{1}{2}[x^{\left(1\right)}\left(1\right)+x^{\left(1\right)}\left(2\right)]\\ -\frac{1}{2}[x^{\left(1\right)}\left(2\right)+x^{\left(1\right)}\left(3\right)]\\ ...\\ -\frac{1}{2}[x^{\left(1\right)}(n-1)+x^{\left(1\right)}\left(n\right)]\end{array}\right)+u$

令Y＝[x⁽⁰⁾(2),x⁽⁰⁾(3),……,x⁽⁰⁾(n)]^T

$B=\left(\begin{array}{cc}-\frac{1}{2}[x^{\left(1\right)}\left(1\right)+x^{\left(1\right)}\left(2\right)]& 1\\ -\frac{1}{2}[x^{\left(1\right)}\left(2\right)+x^{\left(1\right)}\left(3\right)]& 1\\ .& \\ .& \\ .& \\ -\frac{1}{2}[x^{\left(1\right)}(n-1)+x^{\left(1\right)}]& 1\end{array}\right)$

α=(au)^T

由最小二乘估计方法得

$\alpha =\left(\begin{array}{c}a\\ u\end{array}\right)={\left(B^{T}B\right)}^{-1}{B}^{T}Y$

求解微分方程（3.1），其解为

$x\left(t\right)={\mathrm{ce}}^{-a(t-1)}+\frac{u}{a}---\left(3.2\right)$

当t=1时，x(t)=x(1)，即则可根据上述公式得到离散形式微分方程的具 体形式为

$x\left(t\right)=x\left(1\right)-\frac{u}{a}{e}^{-a(t-1)}+\frac{u}{a}---\left(3.3\right)$

将求得的a，u值代入式（3.3）即得微分方程的解式为

${\hat{x}}^{\left(1\right)}\left(t\right)=(x\left(1\right)-\frac{u}{a})e^{-a(t-1)}+\frac{u}{a}$

将它离散化得

${\hat{x}}^{\left(1\right)}\left(t\right)=(x^{\left(0\right)}\left(1\right)-\frac{u}{a})e^{-a(t-1)}+\frac{u}{a}$

对序列再作累减生成即可得出最终的预测结果如下：

${\hat{x}}^{\left(0\right)}\left(t\right)=(x^{\left(0\right)}\left(1\right)-\frac{u}{a})(1-e^a)e^{-a(t-1)},t=\mathrm{2,3},...,n+1---\left(3.4\right)$

将t=n+1带入式（3.4）即可得出该虚拟节点在n+1时间间隔的预测资源使用值。

【303】上述推导已经根据某虚拟节点前n个时刻的资源使用值得到该虚拟节点下一 时刻的资源预测使用值，此后只要设定一个分配因子γ，用资源预测值除以该分配因子即 可得出下一时刻的资源分配值。在此，将分配因子γ等同于上一时刻实际资源利用率。这 样资源利用率，资源预测值及资源分配值三个参数之间就建立了数学关系，使该方法能够 有效的将资源利用率与资源分配过程紧密结合。这样，三个参数之间的数学关系表示如下：

$U(n+1)=\hat{x}(n+1)/R\left(n\right)---\left(3.5\right)$

其中R(n)是指虚拟节点的上一时刻的资源利用率，指经过灰色预测得出的 n+1时刻的虚拟节点的资源预测使用值，U(n+1)即为计算出的n+1时刻该虚拟节点的资源 分配值。式（3.5）用预测值和资源利用率得出资源分配值。然而，如果仅简单设定分配 因子γ=R，这样无法有效调节实际资源利用率，也无法迅速的减少分配值与使用值之间 的误差，因而仅通过式（3.5）的分配将无法有效提高实际资源利用率。为了方便读者阅 读，本发明在以下的推导过程中用R代替分配因子γ。

本发明认为R应该由上一时刻资源分配值反馈控制，它应随着网络负载变化动态调 整，并且维持在一个最优值附近。故此，引用自适应控制调节资源利用率R。故对式（3.5） 中的R做如下调整：

$R(n+1)=(1+p(n+1)*\frac{U\left(n\right)-x\left(n\right)}{U\left(n\right)+x\left(n\right)}*R\left(n\right))---\left(3.6\right)$

p是资源利用率调整步长，通过式（3.6），下一时刻的资源利用率与上一时刻的资源 利用率建立了严密的数学关系，然后反馈给式（3.5），以此来实时调整R的值，并且R 的调整幅度与上一时刻的资源分配值与资源使用值的差比率相关，从而使资源利用率的调 整步伐与负载的变化幅度相一致。

然而，不同的虚拟网络，对于QoS的要求也不尽相同。因而，对于不同的虚拟网络， 有些要求资源利用率尽可能的提高（此时可设），有些则要求资源利用率保持在一个 合理的值附近。为此，我们再引入以下公式：

$p(n+1)=\partial *(\hat{R}-R\left(n\right))---\left(3.7\right)$

其中，是个常数，由网络资源使用量决定，是理想的资源利用率。通过式（3.7）， 可以使资源利用率R自动往调整，并保持在其附近。至此，通过灰色预测模型和资源 利用率的自适应调节方法，我们得出该虚拟节点n+1时刻的初始资源分配值。

【304】此时，对于该物理核心节点所对应的m个虚拟节点，均已完成资源的初始分 配。然而，由于该方法是分别对m个虚拟节点完成的资源分配，因而有可能出现给虚拟 节点分配的资源和超出对应的物理核心节点的资源总和的情况，故引用判断函数进行判定 上述分配结果是否合理。

判断函数如下：

${\Sigma }_{n=1}^m{U}_i(n+1)\le C---\left(3.8\right)$

其中，C是指该物理层核心节点对应的实际资源总量。若式（3.8）条件满足，则就 按【304】的结果对每个虚拟节点进行资源分配，该方法的虚拟资源资源结束；若上式条 件不满足，则需要跳至【305】，对【303】中的参数进行适当的修改，以对全局网络实现 合理的资源分配。

【305】由于各虚拟节点资源初始分配结果和超出对应的物理层核心节点资源总量， 故需要对以上结果进行修正。对于虚拟节点来说，由于其资源分配值与修正资源利用率 R(n+1)以及资源预测值相关，而资源预测值由灰色模型直接得来，无法修改，故我们只能 通过进一步调整(3.6)式中的R(n+1)来改变资源分配值，进而使修正后资源分配值符合要 求。

定义为分配结果超出误差比率。为使修改后的资源分配值满足 【304】中判断公式，对式(3.6)做以下修改：

$R(n+1)=(1+p*\frac{U\left(n\right)-x\left(n\right)}{U\left(n\right)+x\left(n\right)}*R\left(n\right)*(1+\Delta ))---\left(3.9\right)$

跳至【303】，按照重新修正后R(n+1)计算新的资源分配值，这样得出的结果会在分 配结果超出误差比率的基础上缩小虚拟节点资源分配值，从而使分配结果满足【304】中 判断公式，完成虚拟资源的分配过程。

为了更好地理解本发明，以下根据上述步骤选取指定参数进行说明：

由于每个物理核心节点的资源分配过程都一样，为能更简洁的了解本发明的步骤，只 针对一个核心节点来说明本发明的内容。对于本实施例，设定m=3，即每个核心物理节 点划分成三个虚拟节点，以便能够清楚的看到本发明每一步骤的计算结果。

图2所示为虚拟网络环境下虚拟节点的资源分配方法流程图，包括：

步骤【201】在周期固定时刻启动资源分配方法；

启用资源分配方法的周期由网络状况及规模决定，本实施例设定周期为60s。此时， 物理层核心节点的控制模块将要调出各虚拟节点前n个时刻的资源使用值，为后续资源分 配的计算过程做好准备。

n值代表灰色预测的原始输入样本数。灰色预测不需要太多的初始样本即可做到较为 准确的预测。在本实施例中，设定n=5。当然，n值越大，预测结果会更为精确，但是算 法复杂度也会相应增加（n值的增大意味着算法循环次数的增加）。

表1是该核心节点对应的三个虚拟节点前五个时刻的资源使用量。该数据通过某核心 网的网络节点资源使用量归一化而来。

表1各虚拟节点点前五个时刻的资源使用量

步骤【202】运用灰色预测模型，预测出各虚拟节点下一时刻的资源预测使用量；

核心节点的控制模块存储着各虚拟节点前n个时刻的资源使用量，如表1所示。表1 中的数据可作为GM（1,1）灰色预测模型的原始出入。对于本实施例，三个虚拟节点的 输入时间序列分别为：

$X_1^{\left(0\right)}=\left(\mathrm{0.260,0.265,0.270,0.275,0.288}\right),$

$X_2^{\left(0\right)}=\left(\mathrm{0.348,0.337,0.328,0.319,0.309}\right),$

$X_3^{\left(0\right)}=\left(\mathrm{0.405,0.394,0.385,0.374,0.362}\right).$

运用灰色模型，经过公式计算后，得出各虚拟节点n+1时刻的资源预测使用量。在 此实施例中，分别为：x₁⁽⁰⁾(n+1)=0.294，x₂⁽⁰⁾(n+1)=0.301，x₃⁽⁰⁾(n+1)=0.353。

通过步骤【202】的计算，得出三个虚拟节点下一时刻的资源预测使用量，从而触发 虚拟资源的分配方法。

步骤【203】运用自适应反馈模型对各虚拟节点进行虚拟资源分配；

在资源分配的过程中，需要用到上一时刻的资源利用率。对于本实施例，设定初始 时刻的资源利用率为0.8。而对于理想资源利用率三个虚拟节点可以设为相同的值， 也可以设为不同的值。在本实施例中，三个虚拟节点的目标资源利用率分别设为0.9，0.95， 0.95。步长常数设为2。

将上述设定值分别代入公式（3.5）~（3.7），可以得出n+1时刻三个虚拟节点的资源 分配值，分别为：U₁(n+1)=0.367，U₂(n+1)=0.376，U₃(n+1)=0.440。此后，每一个 设定时间间隔后，都会重新对虚拟节点进行资源分配，并且随着样本的进行，自适应反馈 方法将不断校正虚拟资源的实际分配值，使分配值与真值之间的误差越来越小。

步骤【204】判定上一步的虚拟资源分配是否符合实际要求；

由【203】的结果可以看出，由于在本实施例中，初始资源利用率设置的不够高，加之 第一次资源分配时反馈调节方法还未能发挥作用，三个虚拟节点的分配的资源总和已经超 过对应核心节点的资源总量，即U₁(n+1)+U₂(n+1)+U₃(n+1)>1因而这次初始分配是不符 合实际需求的。

本发明充分考虑到初始分配失败的解决方案，只需要修改【203】中适当参数即可在 满足可行性的前提下尽可能合理的完成虚拟资源的分配。此时，已判断出初始分配失败， 故跳至【205】进行资源的再分配过程。

步骤【205】对虚拟资源进行再分配，完成虚拟资源的分配过程。

对于初始分配失败的情况，首先计算其分配结果超出误差比率Δ。对于本实施例，经 过计算可得Δ=0.183。代入公式（3.9）以修改R(n+1)的值，这样即可以使资源分配值相应 合理的的缩小。

经上述调整后，得出最终的分配结果为：U₁(n+1)=0.311，U₂(n+1)=0.317， U₃(n+1)=0.371。经验证，符合U₁(n+1)+U₂(n+1)+U₃(n+1)≤1的条件。至此，一次完整 的虚拟网络环境下虚拟节点的资源分配过程全部结束。

由于网络业务量随着时间会不断波动，因而虚拟节点的资源分配也要随着时间不断重 新分配。由于本发明的计算过程均要用到最新的数据进行反馈调节，因而当一次资源分配 过程结束后，要及时更新核心节点中所存的前n个时刻的数据。

对于表1来说，当完成第一次分配过程后，而后会获得n+1时刻实际资源使用量， 因为在下一次资源分配过程启动时，表1的数据将会修改成如下表2所示：

表2更新后各虚拟节点前五个时刻的资源使用量

其中，表2中最后一列是n+1时刻三个虚拟节点的实际资源使用量，其作为输入样 本预测三个虚拟节点下一时刻（即n+2时刻）的资源使用值。

在本实施例中，通过观察20个时间间隔的资源分配过程来验证本发明的可行性和有 效性。

图3(a)、(b)、(c)给出了应用本发明在20个时间间隔内三个虚拟节点的资源分配情况 及其实际资源利用率。由图3可以看出，应用本发明发明能够同时满足三个虚拟节点的资 源分配，资源分配值能很好的追踪到实际资源使用值的变化曲线，并且经过数十个样本时 间的调整，虚拟节点上的资源利用率便可以达到预订目标值（图3(a)预设目标资源利用率 为0.9，图3(b)、(c)为0.95）。

为了说明本发明提出的判断函数和资源重分配方法对于资源分配过程的合理性的改 善，给出图4和图5分别为为引用判断函数和资源重分配方法和引用后的虚拟节点资源分 配结果。从图4和图5的对比可以看出，如果没有判断函数，只是一次分配，那么分配结 果不能保证极其合理性，即三个虚拟节点的资源分配总量超出核心节点的资源总量。从图 5可以看到，引用本发明的资源重分配方法可以有效的改善资源过度分配的情况，并且使 核心节点的物理资源尽可能的得到充分的利用。

图6给出了三个虚拟节点的平均均方误差值（Mean Squared Error，MSE）。 由图6可以看出，采用本发明进行虚拟资源分配后，能使资源分配误差迅速减小。

至此，虚拟网络环境下虚拟节点的资源分配方法已经建立。该方法充分考虑到虚拟网 络环境下多个虚拟节点资源协调分配的问题，通过预测，分配，检测再分配过程，确保每 个虚拟节点能够快速准确的分配到所需资源，从而实现了虚拟网络的资源动态分配。