用于多播虚拟网络的资源分配方法及抗毁资源分配方法

摘要

本发明公开了一种用于多播虚拟网络的资源分配方法，属于MVN技术领域。本发明首先采集当前物理网络信息，从MVN的跟节点开始，依次为各虚拟节点分配对应的物理节点，每映射完成一对虚拟节点和物理节点，则将其从对应的待映射节点集合中剔除，在完成每个虚拟节点的映射配置后，基于设定的时延窗口对其对应的映射物理路径进行调整，使得得到的映射物理路径满足MVN的业务传输需求，完成对应工作资源的配置。同时为了实现单失效区域下多播虚拟网络的抗毁资源分配方法，本发明在上述映射资源的配置基础上，分别从物理网络中剔除各失效区域所对应的物理节点和链路，配置关于各失效区域的冗余备份资源。本发明用于MVN的映射配置，其效率高，具备抗毁性。

说明书

技术领域

本发明涉及多播虚拟网络(Multicast Virtual Network，MVN)技术，具体涉及一种用于多 播虚拟网络的资源分配方法及抗毁资源分配方法。

背景技术

互联网在定义当今世界中获取并交换信息方式的模型上取得了巨大的成功。在过去的三 十年中，互联网通过支持大批分散的应用以及大量不同的网络技术，证实了自身结构的价值。 然而，互联网的广泛使用也成为了其进一步发展的最大阻碍，由于其多供应商的特性，在互 联网的现有结构中加入新的结构或调整需要获得所有运营商的共同认可，从而使得现今的网 络结构受到限制只能够进行迟缓简单的更新，而无法进行迅速的变革。网络虚拟化作为解决 当前互联网僵化问题的技术手段，近年来受到了国内外未来网络领域研究的广泛关注。网络 虚拟化的优势之一是支持多个异构的网络架构共享物理基础设施。网络虚拟化技术其本质是 通过抽象、分配、隔离机制在一个公共物理网络上独立地运营多个虚拟网，从而能够有选择 性地进行最佳的资源分配与调度。

络虚拟化的目的就是实现分布式虚拟资源的广泛共享，因此虚拟资源映射是网络虚拟化 技术需要实现的重要功能。虚拟资源映射算法作为网络虚拟化技术的关键问题之一，它实现 了将用户的虚拟网络请求合理地映射至底层物理网络的物理资源上的过程，其中如何高效分 配物理网络资源以满足各虚拟网络的链路带宽和节点性能要求，是虚拟资源映射问题的关键。

众所周知网络间的通信有单播、多播、广播等形式，其中多播已在许多需要高QoS的实 时性应用中被广泛使用，多播情况下的虚拟网络映射问题可以先转化成在下层网络中寻找多 播子网。启发式算法是解决虚拟资源映射问题的常用方法，其在网络节点上定义函数h(n)， 用于评估从此节点到目标节点最便宜的路径。算法中包含节点资源分配和链路资源分配两部 分。节点资源分配是指：根据虚拟节点的约束条件，将底层节点的资源分配给虚拟节点。链 路资源分配是指：根据虚拟链路的源节点和宿节点被映射的底层节点、以及虚拟链路的约束 条件，将底层网络的一条底层链路或者多条底层链路的资源分配给虚拟链路。

针对MVN问题，VMNDDVCM(Virtual multicast network with delay and delay variation  constraints mapping)算法是一种常见的解决多播虚拟网络的映射方法，该方法综合考虑了多 播虚拟网络的特殊性，引入了多播网络的时延和时延抖动的特性，通过引入窗口滑动机制解 决了映射过程中的时延抖动约束，采用枚举策略寻找满足约束的最优多播树以完成映射，保 证了最优的映射成本。虽然上述方法能够实现多播虚拟网络映射，但是在完成映射时采用了 枚举的机制，虽然保证了映射结果的最优，但是算法复杂度较高、收敛速度太慢，尤其不能 适用于较大规模的虚拟网络映射问题；并且，该方法并未考虑到底层网络的突发失效的状况， 不能够对底层网络中节点和链路的失效做出相应的处理，即无法实现多播虚拟网络的抗毁映 射，无法解决多播虚拟网络映射的生存性问题。

在关于虚拟网络映射方法的研究中，CPP(Cluster Protecting Provision)和VNP(Virtual  Network Protecting)算法是比较常见的考虑抗毁性的虚拟网络映射的方法，能够同时允许一 个虚拟节点的映射服务器和一条底层数据中心网络链路的失效，并及时的从失效中进行恢复。 该方法是通过1：1的方式对节点和链路进行保护，以最小化映射成本为目标，将虚拟网络 映射到底层网络上。在映射完成后，以相同的资源代价为映射完成的工作中的虚拟网络提供 保护。虽然上述方法能够实现虚拟网络的抗毁映射，但是其仅仅针对单播虚拟网络映射问题 而提出的。在实际应用中，存在大量的多播虚拟网络映射需求，而已有的能够实现虚拟网络 的抗毁映射的方法因无法兼顾多播虚拟网络映射的各种特殊性约束，特殊性约束主要是指时 延和时延抖动，即各虚拟节点的网络资源需求(比如网络容量、时延开销，时延抖动或者说 时延差等)，因而不能适用于多播虚拟网络映射问题；另外，在1：1的冗余备份资源分配 机制(即每份工作资源对应于一份等量的保护资源)方式下的抗毁虚拟网络映射方案中，因 其未引入资源共享策略，这将导致在虚拟网络映射过程中会消耗较高的资源成本。

发明内容

本发明的发明目的在于：针对上述存在的问题，提供一种高效且能适用于大规模多播虚 拟网络映射的底层网络资源的优化配置方法。

本发明的用于多播虚拟网络的资源分配方法，包括下列步骤：

步骤1：获取初始化信息：

获取当前物理网络的网络资源信息，初始化未映射物理节点集合UMN^S为当前物理网络的 所有物理节点n_k；未映射虚拟节点集合UMN_V为当前多播虚拟网络MVN请求的所涉及的所有虚 拟节点v_i；

步骤2：基于当前MVN请求的网络拓扑结构，构建关于各虚拟节点v_i的二层生成树，并为 所述二层生成树的虚拟根节点v分配对应的物理节点：

根据公式Cost(v→n_k)＝(p'(n_k)+(MC-Con(n_k)))*ε(v)分别计算所述虚拟根节点v映射到各物 理节点n_k的资源开销估计值Cost(v→n_k)，其中p'(n_k)＝p(n_k)+α*AF(n_k)为物理节点n_k的节点资 源的虚拟单位成本，所述p(n_k)表示物理节点n_k的节点资源的单位成本，AF(n_k)表示影响物理 节点n_k的失效区域的数量，可调因子α为任意实数；所述MC是当前物理网络的网络拓扑结 图中节点度最大的值，Con(n_k)＝|Adj(n_k)|表示物理节点n_k的节点度，ε(v)表示虚拟根节点v的 资源需求容量；

取最小资源开销估计值Cost(v→n_k)所对应的物理节点n_k为虚拟根节点v的映射节点，并 记为n_s；

步骤3：将虚拟根节点v与物理n_s的映射关系v→n_s存储到资源分配表M中；并从未映射 物理节点集合UMN^S中删除物理节点n_s，从未映射虚拟节点集合UMN_V中删除虚拟节点v；

步骤4：对未映射虚拟节点集合UMN_V进行更新处理：

根据公式分别计算各虚拟节点v_i的权值DR(v_i)，其中ε(v_i)表示虚拟节点 v_i的资源需求容量，表示虚拟根节点v与虚拟节点v_i的相连的虚拟链路e_i的带宽资源需求值， 可调因子λ为任意实数；

基于各虚拟节点v_i的权值DR(v_i)，按降序排序得到更新后的未映射虚拟节点集合UMN_V；

步骤5：基于当前未映射物理节点集合UMN^S，对当前未映射虚拟节点集合UMN_V中的各 虚拟节点v_i，从左到右依次进行资源分配：

步骤501：对虚拟节点v_i，基于当前未映射物理节点集合UMN^S，查找出满足虚拟节点v_i的 网络资源需求的从物理节点n_s到候选物理节点n_k的最短路径，所述候选物理节点n_k属于当前 集合UMN^S，并根据公式Cost(v_i→n_k)＝CNn_k+CPn_k计算各物理节点n_k作为虚拟节点v_i的候选映 射节点时的资源开销估计值Cost(v_i→n_k)；

记录资源开销估计值Cost(v_i→n_k)，以及物理节点n_s到物理节点n_k的最短路径为虚拟链路 e_i的映射物理路径若不存在从物理节点n_s到候选物理节点n_k的最短路径，则令对应的资 源开销估计值Cost(v_i→n_k)为预设极大值；

其中CNn_k＝p'(n_k)*ε(v_i)为虚拟节点v_i映射到物理节点n_k上的资源虚拟开销；

所述为虚拟链路e_i的映射物理路径的资源虚拟开销，其中 p'(e)＝p(e)+α*AF(e)，所述p(e)表示物理链路e的链路资源的单位成本，AF(e)表示影响物理 链路e的失效区域的数量，所述链路e属于映射物理路径

步骤502：取最小资源开销估计值Cost(v_i→n_k)所对应的物理节点n_k为当前虚拟节v_i的映射 节点，并将映射关系v_i→n_k、映射物理路径存储到资源分配表M中；同时从未映射物理节 点集合UMN^S中删除当前物理节点n_k，未映射虚拟节点集合UMN_V中删除当前虚拟节点v_i；

步骤503：重复执行步骤501、502，直到映射虚拟节点集合UMN_V为空；

步骤6：根据当前MVN请求设置时延窗口W＝[D_max-C_DV,D_max]，调整资源分配表M中的 映射物理路径：判断资源分配表M中的各映射物理路径的时延是否在所述时延窗口W内， 若否，则调整当前映射物理路径更新资源分配表M：基于当前映射物理路径所对应的映 射关系v_i→n_k，在物理网络拓扑图中查找出从物理n_s到物理节点n_k的前K条最短路径，并从 所述K条最短路径中选择时延在所述时延窗口W内的最短路径替换当前映射物理路径其中所述D_max表示资源分配表M中的所有映射物理路径中，最大的路径时延；C_DV表示当前 MVN请求的链路最大时延差约束值。

基于本发明的资源分配方法，本发明还提出了一种针对单失效区域下的多播虚拟网络的 抗毁资源分配方法，以解决多播虚拟网络映射的生存性问题，即以给定的所有可能的失效区 域为基础，并且在允许底层网络最多同时出现一个区域失效的情况下，实现多播虚拟网络映 射，并引入一定的容错机制，使得多播虚拟网络映射成功后，能在底层物理网络出现任何一 个区域失效的情况下正常工作。

本发明的单失效区域下多播虚拟网络的抗毁资源分配方法，包括下列步骤：

步骤S1：基于权利要求1所述的资源分配方法为当前MVN请求分配工作资源分配表M；

步骤S2：为当前MVN请求分配备用资源分配表：

步骤S201：在当前物理网络中确定各个失效区域r_i，由各失效区域r_i构成失效区域集合R；

步骤S202：分别为每个失效区域r_i分配备用资源分配表M_i：将失效区域r_i所涉及的物理 节点和链路从当前物理网络的网络拓扑中剔除；再基于剔除处理后的物理网络拓扑所对应的 网络资源信息，根据权利要求1所述的资源分配方法所述MVN请求分配对应失效区域r_i的备 用资源分配表M_i；

步骤S3：存储所述工作资源分配表M和各个失效区域r_i的备用资源分配表M_i，并发送至 各物理节点。

综上所述，由于采用了上述技术方案，本发明的有益效果是：本发明能高效实现大规模 多播虚拟网络映射的资源优化配置，同时为多播虚拟网映射预留了备份资源，使多播虚拟网 络在任意给定的一个区域失效的情况下能继续正常工作。

附图说明

图1是单区域失效时的MUV映射实例，其中图(a)中的节点a、b、c表示MVN请求所涉 及的虚拟节点，对应各虚拟节点的矩形框中的数字(数字“4”、“5”)表示MVN请求中各虚拟 节点资源的要求，两个虚拟节点间连线上的3个数字分别表示对链路资源、时延和时延抖动 的需求信息；图(b)的节点A、B、C、D、E、F表示物理节点，对应各物理节点中矩形框 中的数字(数字“20|3”、“20|4”)左边是物理节点的可用资源总量，右边是单位节点资源的 成本，各物理链路上的数字(数字“30|5|3”、“30|3|1”、“30|4|2”等)左边是物理链路的可用 物理链路资源总量，中间数字是单位物理链路资源的成本，右边数字是物理链路时延；

图2是最小开销集合覆盖示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合实施方式和附图，对本发明作 进一步地详细描述。

为了便于本发明的实现，本发明中将MVN的请求构建为无向加权图 G_V＝(N_V,E_V,C_N,C_L,C_D,C_DV)模型，具体来说，面向服务的MVN请求可以表示为一个两层的 树，如图1中的(a)图，其中，N_V＝{v₁,v₂,...,v_i,...v_T}表示MVN的虚拟节点集合，T为虚拟节 点的总个数，E_V＝{e₁,e₂,....,e_i,...,e_T}表示MVN的虚拟链路集合，e_i表示连接虚拟根节点v到 叶子节点v_i的虚拟链路，C_N表示个虚拟节点的节点资源约束信息，表示 各虚拟链路带宽约束信息，C_DV表示虚拟链路最大时延差约束信息，G_V所涉及的上述信息均 可以基于MVN的请求获取到。

类似地，本发明中将物理网络(底层网络)构建为无向加权图G^S＝(N^S,E^S,C^N,C^L)模型，其 中N^S物理网络的所有物理节点的集合(例如图1中途(b)所示的节点A、B、C、D、E、F)， E^S物理网络的所有物理链路的集合，对于每一个物理节点n_k∈N^S都可以为MVN节点提供 资源，C^N表示物理节点资源属性，如节点的资源容量，C^L表示各物理链路属性，包括带宽和 时延等信息；

类似地，定义MVN虚拟链路集合E_V到底层物理网络路径的映射集合为 表示对应虚拟链路e_i在物理网络中的映射物理路径，因此每一条 映射物理路径是E^S的子集。所以端到端的映射物理路径的时延和可用带宽资源可以表 示为和和可以按照下面的公式计算：

$D\left(p_{e_i}\right)=\underset{e\in p_{e_i}}{\Sigma }d\left(e\right),\forall p_{e_i}\in P$

$B\left(p_{e_i}\right)=\underset{e\in p_{e_i}}{\min }\left\{b\left(e\right)\right\},\forall p_{e_i}\in P$

其中d(e)表示物理链路e的时延，b(e)表示物理链路e的可用带宽资源。

以上述定义为基础，在将虚拟节点集合和虚拟节点资源需求集合(N_V,C_N)映射到底层物理 网络节点集合和节点资源集合(N^S,C^N)上可表示为：即对任意虚拟 节点使得M_N(v_i)＝n_k。

在将虚拟节点v_i映射在物理节点n_k上，意味着在物理节点n_k分配给了虚拟节点v_i的资源 需求容量ε(v_i)，因此n_k上的可用资源容量R_n(M_N(v_i))必须不小于ε(v_i)，即约束如下：

$R_n\left(M_N\left(v_i\right)\right)\ge ϵ\left(v_i\right),\forall v_i\in N_V---\left(1\right)$

同上，虚拟链路集合和物理链路资源需求集合(E_V,C_L)映射在底层网络链路集合和链路资 源集合上可表示为：$M_E:(E_V,C_L)\stackrel{M}{\to }(P,C^L),$即对任意使得$M_E\left(e_i\right)=p_{e_i},$虚拟链 路e_i映射在底层物理网络路径上，意味着底层物理网络路径分配给了虚拟链路e_i所需的 链路带宽资源因此底层物理网络路径的可用带宽资源B(M_E(e_i))必须不小于即约束 如下：

$B\left(M_E\left(e_i\right)\right)\ge x_{e_i},\forall e_i\in E_V---\left(2\right)$

同时总的时延和时延抖动也必须满足下面的约束条件：

$D\left(M_E\left(e_i\right)\right)\le C_D,\forall e_i\in E_V---\left(3\right)$

$\left(\begin{array}{cccc}|D\left(M_E\left(e_i\right)\right)-D\left(M_E\left(e_j\right)\right)|\le C_{\mathrm{DV}},& \forall e_i,e_j\in E_V& \mathrm{and}& e_i\ne e_j---\left(4\right)\end{array}\right)$

约束式(3)确保：映射物理路径的时延D(M_E(e_i))不超过MVN请求的时延上限C_D。 约束式(4)确保：任意两条映射物理路径间的时延差不超过MVN请求的时延差上限C_DV。

上述4个约束条件为多播虚拟网络映射的固有约束条件，即MVN请求中所涉及的各虚 拟节点所对应的网络资源需求信息，本发明在满足上述4各约束条件的前提下了，实现了将 各虚拟节点映射到不同的物理节点的资源分配，具体执行步骤如下：

步骤1：

初始化处理

获取当前物理网络的网络资源信息，得到G^S＝(N^S,E^S,C^N,C^L)；

基于当前MVN的请求获取G_V＝(N_V,E_V,C_N,C_L,C_D,C_DV)；

初始化未映射物理节点集合UMN^S＝N^S,未映射虚拟节点集合UMN_V＝N_V,资源分配表

步骤2：

基于当前MVN请求的网络拓扑结构，基于当前MVN请求的网络拓扑结构，构建关于各虚 拟节点v_i的二层生成树，并为所述二层生成树的虚拟根节点v分配对应的物理节点：

对每个n_k∈UMN^S，分别根据公式(5)计算计算和记录虚拟根节点v映射到各物理节点n_k的资源开销估计值Cost(v→n_k)；

取最小资源开销估计值Cost(v→n_k)所对应的物理节点n_k为虚拟根节点v的映射节点，并 记为n_s，如果存在多个最小Cost(v→n_k)，则任意选择其中一个作为映射节点即可。

公式(5)为：Cost(v→n_k)＝(p'(n_k)+(MC-Con(n_k)))*ε(v)，

其中，p'(n_k)＝p(n_k)+α*AF(n_k)为物理节点n_k的节点资源的虚拟单位成本，p(n_k)表示物 理节点n_k的节点资源的单位成本，AF(n_k)表示影响物理节点n_k的失效区域的数量，可调因子α 为任意实数，α在这里起引导映射避开失效区域的作用；MC是当前物理网络的网络拓扑结 图中节点度最大的值，Con(n_k)＝|Adj(n_k)|表示物理节点n_k的节点度(即MC为所有Con(n_k)中的 最大项所对应的值)，ε(v)表示虚拟根节点的资源需求容量。这样单位虚拟成本越低，度越大的 物理节点更容易成虚拟根节点的映射节点。配置度越大的物理节点成为MVN虚拟根节点对 应的映射节点，则其它叶子节点到虚拟根节点v的链路映射就有更多的选择。

步骤3：

更新资源分配表M：将虚拟网络的虚拟根节点v与物理n_s的映射关系v→n_s存储到资源分 配表M中；

更新集合UMN^S和UMN_V：令UMN^S＝UMN^S-n_s，UMN_V＝UMN_V-v；

本次更新后的UMN_V是所有多播虚拟网络叶子节点的集合，更新的目的是让不同的虚拟节 点映射到不同的物理节点；

步骤4：

对未映射虚拟节点集合UMN_V中的各元素重新进排序处理：

根据公式(6)计算集合UMN_V中各虚拟节点的权重值，并按降序排序，对集合UMN_V中的 各元素重新排序后，就将资源需求大的虚拟节点排在了前面，于是资源需求大的节点就能优 先得到映射配置处理，从而可以降低阻塞率，提高映射成功的可能性。

公式(6)为：其物理意义是将虚拟节点所需的节点资源和虚拟根节 点与该节点相连的链路带宽资源按比例λ相加，其中可调因子λ为任意实数，这样就将节点资 源需求和链路资源需求综合考虑起来。

步骤5：基于当前未映射物理节点集合UMN^S，对当前未映射虚拟节点集合UMN_V中的各 虚拟节点v_i，从左到右依次进行资源分配：

步骤501：对每个虚拟节点v_i∈UMN_V，在满足约束条件(1)、(2)、(3)的前提下，在有 向图G^S中查找出物理节点n_s到候选物理节点n_k的最短路径，其中n_k∈UMN^S；若存在满足约束 条件(1)、(2)、(3)的物理节点n_s到物理节点n_k的最短路径，则根据公式(7)计算虚拟节 点v_i映射到候选物理节点n_k的资源开销估计值Cost(v_i→n_k)；若不存在，则令资源开销值 Cost(v_i→n_k)为预设极大值，例如配置Cost(v_i→n_k)＝∞；

记录当前虚拟节点v_i与各个物理节点n_k的资源开销值Cost(v_i→n_k)，和对应的映射物理路 径该映射物理路径即为从物理节点n_s到物理节点n_k的最短路径；

公式(7)为Cost(v_i→n_k)＝CNn_k+CPn_k，其中CNn_k＝p'(n_k)*ε(v_i)为虚拟节点v_i映射到物理节 点n_k上的资源虚拟开销；为虚拟链路e_i的映射物理路径资源虚拟开销，其中 p'(e)＝p(e)+α*AF(e)，p(e)表示物理链路e的链路资源的单位成本，AF(e)表示影响物理链路e 的失效区域的数量；

步骤502：基于步骤501所计算的各资源开销估计值Cost(v_i→n_k)，取最小项所对应的物 理节点n_k为当前虚拟节v_i的映射节点，并将映射关系v_i→n_k、映射物理路径存储到资源分 配表M中；若同时存在多个最小项，则任意选择其中一个最小项所对应的物理节点为当前虚 拟节v_i的映射节点；

同时从集合UMN^S和UMN^S剔除以完成映射的两个节点，即令UMN^S＝UMN^S-n_k， UMN_V＝UMN_V-v_i；

步骤503：重复执行步骤501、502，直到映射虚拟节点集合UMN_V为空。

步骤6：基于约束公式(4)，对资源分配表M中的对应映射物理路径进行调整，即当存 在于最小时延的路径之间不能满足约束条件(4)的映射物理路径时，则需要重新找一条可行 的替换路径，为了显著降低约束条件(4)中对两两路径之间进行比较所带来的计算复杂度， 本发明根据时延窗口W＝[D_max-C_DV,D_max]来判断对资源分配表M中所有映射物理路径是 否存在不满足时延窗口W的映射物理路径，若存在，则重新查找可行的替换路径，具体处理 为：

判断资源分配表M中的各映射物理路径的时延是否在所述时延窗口W内，若否，则调 整当前映射物理路径更新资源分配表M：基于当前映射物理路径所对应的映射关系 v_i→n_k，在物理网络拓扑图中查找出从物理n_s到物理节点n_k的前K(预设值，基于实际应用 场景进行取值)条最短路径，例如可通过常用的K-shortestpaths(前K条最短路径)算法来 获取K条最短路径，并从该K条最短路径中选择时延在所述时延窗口W内的最短路径替换 当前映射物理路径

其中D_max表示资源分配表M中的所有映射物理路径中，最大的路径时延；C_DV表示当前 MVN请求的链路最大时延差约束值。

为了实现对单失效区域下多播虚拟网络的物理网络资源配置的冗余备份，在任意单区域 失效时，多播虚拟网能够得到恢复，从而保证多播虚拟网的生存性；

首先基于物理网络的应用场景、确定可能失效的失效区域r_i，由系统获知的各个失效区 域r_i构成失效区域集合R。所谓失效区域是指停电、地震等原因，所造成的底层物理网络的区 域性故障，通常可能会同时出现多个物理节点设备和多条链路设备失效。对于每一个失效区 域r_i∈R会同时摧毁一到多个物理节点和与这些物理节点相连的所有物理链路，为了便于描 述，本发明将对应失效区域r_i的失效区域描述为其中和如图 1(b)所示例的两个失效区域，从图中可以看出其中和$E_{r_1}=\{A-F,$$B-F,E-F,A-E,D-E\};G\left(r_2\right)=(N_{r_2},E_{r_2}),$其中$N_{r_2}=\{C,D\}$和$E_{r_2}=\{A-C,B-C,A-D,C-D,$$D-E\}.$

其次，为当前MVN请求分配备用资源分配表，即当多播虚拟网络的虚拟节点或者链路映 射到失效区域r_i内时，为了保证多播虚拟网络的生存性，就必须从不包含r_i的区域预留资源， 当区域r_i发生失效时，多播虚拟网的请求可以从预留资源中恢复，从而保证多播虚拟网的生 存性，也就是为多播虚拟网映射预留备份资源来保证生存性：

对每一个r_i∈R，将失效区域r_i所涉及的物理节点和链路从当前物理网络的网络拓扑中剔 除，即更新G^S＝G^S-G(r_i)；基于更新后的G^S，根据权利要求1所述的资源分配方法所述MVN 请求分配对应失效区域r_i的备用资源分配表M_i；

最后，存储工作资源分配表M和各个失效区域r_i的备用资源分配表M_i，并发送至各物理 节点。

虽然上述步骤得到的资源分配表M和各备用资源分配表M_i，能够保证在单区域失效情况 下多播虚拟网的正常工作，但是有多少个失效区域就有多少个备用资源分配表M_i，而对于某 些备用资源分配表M_i，可能有多个失效区域能从映射M_i中恢复出来，于是资源分配表M中 就有大量的冗余，为了消除冗余，使资源得到更充分的利用，对资源分配表M进行优化处理， 具体为：

步骤(1)：基于当前获取的备用资源分配表M_i，分别计算各备用资源分配表M_i关于所 有虚拟节点和链路的最小映射开销和c(M_i)；

步骤(2)根据公式min{c(M_i)/|U(M_i)|}选择对应的M_i，并将当前最小项所对应的备用资 源表M_i存储到最小备用资源分配表M*中，并更新工作资源分配表M＝M-M_i，同时更新失 效区域集合R：在失效区域集合R中删除能从备用资源分配表M_i中恢复的失效区域；

步骤(3)：基于步骤(4)更新后的失效区域集合R包含的各失效区域r_i所对应的最小映 射开销和c(M_i)，继续执行步骤(2)，直到失效区域集合R为空；

最后，存储当前分配工作资源分配表M(消除冗余后的)和最小备用资源分配表M*， 并发送至各物理节点。

上述公式min{c(M_i)/|U(M_i)|}中，|U(M_i)|表示能从备用资源分配表M_i中恢复的失效区域个 数，能从映射M_i中恢复出来的失效区域的个数可能不止一个，如图2所示，能从备用资源分 配表M₂中恢复出来的失效区域包括r₁和r₂两个。显然|U(M_i)|值越大，M_i就更有可能被加入到 M^*中，而且M^*也可能越小。同理在|U(M_i)|固定的情况下，c(M_i)越小，M_i就更有可能被加 入到M^*中。

实施例1

将本发明的一种单失效区域下多播虚拟网络的抗毁资源分配方法部署在SDN网络中，以 实现多播虚拟网络业务的映射。

首先通过SDN控制路由器调度自身带有的控制管理功能采集底层物理网络拓扑和相应的 资源信息，包含底层物理网络中所有物理节点资源情况，以及物理链路资源，时延等资源信 息；

当接收到MVN请求时，SDN控制路由器基于当前所采集的物理网络拓扑和相应的资源信 息，基于本发明的一种单失效区域下多播虚拟网络的抗毁资源分配方法，计算出对应的虚拟 节点和物理节点的映射信息，将相应虚拟多播业务的虚拟节点的任务分配给映射的物理节点， 并发送相应的工作路由和备份路由信息(即工作资源分配表M和最小备用资源分配表M*)， 完成多播虚拟网络的实际映射。

综上，本发明所带来的有益效果体现在：

(1)优化性。解决了CPP，VNP算法无法解决的多播虚拟网络映射问题和各种约束问题， 同时引入了最小集合覆盖算法优化映射结果，消除冗余资源，降低了多播虚拟网络的映射成 本；

(2)兼容性。不仅能够解决如VMNDDVCM算法所针对一般的多播虚拟网络的映射，而 且还解决了单区域失效情况下的多播虚拟网络映射的生存性问题，使多播虚拟网络在任意给 定的一个区域失效的情况下正常工作；

(3)预测性。在计算最小资源开销估计值Cost(v→n_k)时，使用了虚拟单位成本和引导因 子α，在一定程度上引导映射避开失效区域，从而达到失效感知的效果，减少失效区域的不 利影响。

以上所述，仅为本发明的具体实施方式，本说明书中所公开的任一特征，除非特别叙述， 均可被其他等效或具有类似目的的替代特征加以替换；所公开的所有特征、或所有方法或过 程中的步骤，除了互相排斥的特征和/或步骤以外，均可以任何方式组合。