CN115226044B - 一种nfv网络中的多播路由方法及系统 - Google Patents

Abstract

本发明属于通信技术领域，特别涉及一种NFV网络中的多播路由方法及系统；该方法主要包括混合整数线性规划的建立、虚拟网络功能节点复制路径选择图的建立、路径选择图中的节点分层、分层后目的节点的优化几个关键步骤；将目标函数及其服务质量约束建模为混合整数线性规划，接着寻找有效的启发式算法来代替具有高时间复杂度的混合整数线性规划直接求解，构造节点复制路径选择图用来为多播选择最佳服务功能链的路径和构造最短路径树，通过对最短路径树中的节点进行分类，利用优化算法对候选节点进行优化。本发明利用最短路径树中的节点能被分为不同的层级的特点，对目的节点进行优化，寻找到满足路径时延的最佳多播树，使得路由更加准确。

Description

一种NFV网络中的多播路由方法及系统

技术领域

本发明属于通信技术领域，涉及一种具有时延约束的最佳多播树路由策略，具体涉及一种NFV网络中的多播路由方法及系统。

背景技术

近年来，通信网络的设计和管理方式发生了根本性的变化，这种转变主要是由软件定义网络(Software Defined Networking，SDN)和网络功能虚拟化(Network FunctionVirtualization，NFV)这两种新兴的范式引起的。SDN和NFV被认为是未来通信网络的重要技术，代表着第五代(5G)移动通信的两个创新驱动平台。为了保证数据传输的可靠性和安全性，当前，数据中心和通信网络部署了各种各样的网络中间件，例如：防火墙、入侵检测系统和广域网优化器等传统网络的中间件通常是由专用硬件制造的，费用非常昂贵且扩展性差。基于NFV技术，传统网络的中间件可以由运行于虚拟机上的软件实现，即虚拟网络功能(Virtual Network Function，VNF)。软件定义网络(SDN)将控制层平面从数据平面中分离出来从而可以对网络进行集中的管理和监控。SDN结合NFV技术，可以对网络中运行的网络组件进行灵活的管理和调度。

随着用户业务类型需求的多样化，为了可靠、安全、可扩展地传输用户的流请求，网络数据通常要以先前预定好的顺序通过一系列的网络功能，称作服务功能链(ServiceFunction Chain，SFC)，NFV可以创建一个由一组有序的虚拟网络功能(Virtual NetworkFunctions，VNFs)组成的服务功能链来为网络请求流提供服务。近年，随着视频会议、多媒体数据分发、软件更新和系统监控等网络业务的增长，使得网络数据呈现爆炸式的增长，与单播通信相比，基于NFV的多播通信是将数据从一个源传输到多个目的地，比单播通信有更高的效率，能够节省大量的带宽和网络资源。当多播请求流通过SFC的VNFs时，需要综合考虑路由成本、服务功能链的顺序约束、VNF的分布、多播复制点分叉和服务质量(Quality ofService，QoS)如延迟等约束，以获得最优的多播路由方案。

目前，部分研究工作，如Alhussein的文献《A virtual network customizationframework for multicast services in NFV-enabled core networks》采用启发式算法对多播服务请求流的优先级进行排序调度，期望降低路由成本的同时获得较大的网络吞吐量，这种方法的多播复制点都在最后一个功能节点上，且不可以任意分叉，这样会增大最优多播树的路由成本。另一方面，Ma等的文献《Throughput maximization of NFV-enabledmulticasting in mobile edge cloud networks》采用成本最小化的近似算法来解决移动边缘云中基于NFV的多播请求的准入问题，该方法将多个VNF全部放在一个边缘云中，这样容易造成资源中心化，增大路由成本。除此以外，Ren等的文献《Embedding servicefunction tree with minimum cost for NFV-enabled multicast》运用两阶段算法来解决最优服务功能树(Service Function Tree，SFT)的嵌入问题，但是这种方法没有考虑服务质量(QoS)的约束。因此，目前的方案都没有实现多播复制点可以任意分叉的同时联合考虑服务质量如时延等QoS约束的多播服务路由树的构建。

发明内容

综上所述，本发明专利旨在基于NFV的网络中，在满足VNF服务链顺序约束、时延约束的条件下，考虑复制后的VNF可以放置在任意一个功能节点上，且可以任意分叉，多个VNF可以存在于一个数据中心上，从而设计出节点复制路径选择图；然后基于节点复制路径选择图，设计了一个启发式算法为多播请求流寻找一颗成本最优的多播树，以提高网络资源的利用率。本发明提出了一种NFV网络中的多播路由方法及系统，提供了节点复制路径选择图、最短路径树和主干路径选择、节点分层、节点优化、满足时延约束的最佳多播树的一整套完善的路由机制，这套路由机制能在满足多播路径时延、服务链顺序等约束的条件下，保证多播复制点可在任意功能节点上的同时找到最佳多播树。

在本发明的第一方面，提供了一种NFV网络中的多播路由方法，所述方法包括以下步骤：

对多播网络的服务功能链中的节点进行复制，按照预定义的顺序放置所有节点，并根据相对成本为节点之间构建有向链路，从而构造出节点复制路径选择图；

使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出目的节点个数最多的最短路径作为主干路径；

将最短路径树中的所有节点按照与距离主干路径的跳数进行分层，划分为多个层级；

根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；

将多播网络的最佳多播树对应的虚拟链路映射到多播网络的路由链路中，动态部署VNF实例。

在本发明的第二方面，提供了一种NFV网络中的多播路由系统，其应用于本发明第一方面所述的一种NFV网络中的多播路由方法中，所述多播路由系统包括：

节点复制路径选择图构造模块，用于对多播流请求的服务功能链中的节点进行复制，按照预定义的顺序放置所有节点，并根据相对成本为节点之间构建有向链路，从而构造出节点复制路径选择图；

主干路径获取模块，用于使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出目的节点个数最多的最短路径作为主干路径；

节点层级计算模块，用于将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级；

节点层级优化模块，用于根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；

链路时延约束模块，用于基于所述节点层级优化模块获得的多播网络的最佳多播树，计算所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新所述最佳多播树；

路由模块，用于将多播网络的最佳多播树对应的虚拟链路映射到多播网络的路由链路中，动态部署VNF实例。

本发明的优点及有益效果如下：

1.本发明提供一种NFV网络中的多播路由方法及系统，通过枚举所有可能部署的VNF，可以使得多播请求流利用冗余的VNF来选择成本较小的路径。

2.本发明提供一种NFV网络中的多播路由方法及系统，通过复制节点进行顺序排列的方式，将问题简化为在节点复制路径选择图中构造最佳多播树的问题，构造多播树不仅满足多播复制点和分叉可在任意功能节点处进行，且能让每个目的节点对应的服务功能链满足顺序约束要求，简化了问题的复杂度，能够有效降低路由成本。

3.本发明提供一种NFV网络中的多播路由方法及系统，将各个节点按照与主干路径的距离进行层级划分，并按照层级划分对目的节点进行优化，从而将高层级的目的节点降为低层级的目的节点，提高网络资源利用率，降低成本。

4.本发明提供一种NFV网络中的多播路由方法及系统，通过建立时延约束，保证最佳多播树的链路时延。

5.本发明提供一种NFV网络中的多播路由方法及系统，将虚拟链路映射到原链路中，再根据多播网络中功能节点的资源状况动态部署VNF实例，保证网络的负载均衡。

附图说明

图1为本发明实施例中整体方案流程图；

图2为本发明实施例中基于NFV网络的多播服务链拓扑图；

图3为本发明实施例中节点复制路径选择图的构造图；

图4为本发明实施例中每个目的节点的最短路径图；

图5为本发明实施例中主干路径选择图；

图6为本发明实施例中最小路径树图；

图7为本发明实施例中基于最小路径树的层级信息图；

图8为本发明实施例中资源高效多播树图；

图9为本发明实施例中简化的资源高效多播树图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一

图1为本发明实施例所述的一种NFV网络中的多播路由方法流程图，如图1所示，所述方法包括节点复制路径选择图构造、构造最短路径树和主干路径选择、节点分层、目的节点优化和部署路由五个部分。其中节点复制路径选择图构造部分主要用于为最佳多播树选择最佳服务功能链路径，构造最短路径树和主干路径选择、节点分层、目的节点优化则是对最佳多播树路由进行具体的操作过程，部署路由则是在多播网络中建立路由的具体过程。

具体包括如下步骤：

101、对多播请求流的服务功能链中的VNF节点进行复制，按照预定义的节点请求顺序放置所有节点，并根据相对成本构建节点之间有向链路，从而构造出节点复制路径选择图；

在本发明实施例中，构造出节点复制路径选择图的具体方法包括：

将每个节点进行复制，也即是将第一节点进行复制，得到第二节点，形成以第一节点和第二节点构成的两列节点，根据多播请求流中服务功能链中的节点请求顺序进行节点放置。

将源节点置于首列，各个目的节点分别置于尾列以及不同请求序列的两列节点之间，也即前一请求序列的第二节点与后一请求序列的第一节点之间；

分别对相邻列的节点之间，以及不同类型的节点之间构建出链路，并赋予相对成本，从而形成节点复制路径选择图；

其中，相邻列的节点之间即包括源节点与顺序最靠前的请求序列的第一节点之间，同一请求序列的第一节点与第二节点之间，每一请求序列的第二节点与对应的各个目的节点之间，以及各个目的节点与对应的每一请求序列的第一节点之间，所述第一节点和所述第二节点分别包括交换节点和功能节点即VNF节点。

可以理解的是，在本发明实施例中，多播网络由节点构成，所有节点都是物理节点，物理节点由交换节点和功能节点构成，而在本发明实施例中功能节点上部署有VNF实例，而在本发明实施例中将部署有VNF实例的功能节点称为VNF节点，因此VNF节点实际上与功能节点是一一对应的；其中，节点复制路径选择图中除了源节点和目的节点外，所有节点都是功能节点和交换节点；本发明通过对功能节点和交换节点进行复制，形成了节点复制路径选择图，而由于功能节点和交换节点的加入，所以复制前后节点之间的链路关系有所变化，本发明通过相对成本来衡量这个链路关系，能够准确刻画节点之间的路由关系。

102、使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出目的节点个数最多的最短路径作为主干路径；

在本发明实施例中，使用节点复制路径选择图生成对应多播网络的最短路径树包括利用最短路径算法，例如Dijkstra等算法在每个节点复制路径选择图上生成其对应的多播网络的最短路径树；所述最短路径树中的每个目的节点都有一条从源节点出发的最短路径，这种方式可以对每个多播网络都单独生成一个节点复制路径选择图，能够将复制后的VNF部署在任意一个功能节点上，且可以任意分叉。

103、将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级；

在本发明实施例中，所述将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级包括将位于主干路径上的节点设置为第一层级，与主干路径直接相连的节点设置为第二层级，与主干路径间接相连的节点设置为第三层级；第三层级的节点包括与主干路径通过一跳节点间接相连的第一节点，以及通过多跳节点间接相连的第N节点，N≥2，且为正整数。

104、根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；

在本发明实施例中，所述根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级包括将当前节点复制路径选择图中第三层级的目的节点与其他节点复制路径选择图中对应节点的分级进行对比，若该对应节点在其他节点复制路径选择图中属于第二层级的节点，则将当前节点复制路径选择图中第三层级的目的节点升级为第二层级的节点，这种分层更新方式能够在具有较小运算复杂度的前提下，快速优化当前节点复制路径选择图的路由链路。

105、计算所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新所述最佳多播树；

在本发明实施例中，当步骤104中获得当前节点复制路径选择图对应的多播网络的最佳多播树后，需要计算出获得的所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新获得的最佳多播树。

106、将多播网络的最佳多播树对应的虚拟链路映射到多播网络的物理链路中，动态部署VNF实例。

在本发明实施例中，将步骤105更新后的多播网络的最佳多播树对应的虚拟链路映射到多播网络的物理链路中，在真实的多播网络的路由链路环境中动态部署VNF实例，按照部署后的结果实现NFV网络中的路由。

为了简单起见，对本发明的前五个部分进行重点说明，整体方案流程图如图1所示，即：节点复制路径选择图构造、构成最短路径树和选择主干路径、节点分层、目的节点优化、时延约束建立等操作流程。综合考虑链路、节点资源容量约束和顺序约束。五个部分具体操作如下：

其一：节点复制路径选择图构造，网络中资源使用的一个重要特征是，资源的剩余率越小，使用该资源的相对成本就越大。比如，由于剩余流表资源越小的SDN交换机需要考虑更多的转发规则，与剩余流表资源较大的SDN交换机相比，它将花费更多的成本来处理传入网络的数据包。为了描述这一特性，我们利用相对成本来表示网络中资源的状况，并将其定义如下：

其中分别表示在路由服务功能链时带宽、流表和CPU的相对成本，表示链路uv上的带宽容量，/>表示当路由多播流f_i的SFC(服务功能链顺序)时，链路uv上带宽剩余率，/>表示多播流f_i的请求带宽，L表示辅助图即节点复制路径选择图构造前的物理链路集合；/>表示交换节点s上的流表容量，/>表示当路由多播流f_i的SFC(服务功能链顺序)时，交换节点s上的流表剩余率，θ_sn为交换节点的集合，L'表示节点复制后排序前的链路集合；/>表示功能节点m处的CPU容量，/>表示当路由多播流f_i的SFC(服务功能链顺序)时，功能节点m上CPU剩余率，/>表示多播流f_i的CPU消耗值。同时用阈值μ、θ和ω来区分多播的请求流，用/>表示节点复制后排序前的成本权值。

在第一个式子中，分子表示网络中的最大带宽容量，分母/>表示链路uv上剩余带宽与多播流请求带宽的差值，该式表名，一条链路上剩余的带宽越少，该链路的相对成本就越大，如果链路上的剩余带宽接近于零，相对成本会增长很快。第二个式子和第三个式子遵循同样的规律。因此，如果一条链路的相对成本较大，就可以确定为瓶颈链路。在相对成本也即相对代价的定义中考虑了流的特征，带宽消耗大于θ的流被设为大象流，带宽消耗小于μ的流被设为老鼠流(μ<θ)。如果带宽消耗在μ和θ之间，则流被设为狗流。如果CPU消耗大于ω，则设为密集流。将CPU消耗小于ω的流设为稀疏流。

由于大象流的带宽消耗量大且数量少，所以重点关注链路上的剩余带宽，而不是交换节点上剩余的流表。相反，由于老鼠流的带宽消耗可以忽略，但是老鼠流的数量很大，所以应该更多地关注交换节点上剩余的流表资源，而不是链路上剩余的带宽。因此，对于大象流，带宽的相对成本根据计算，流表的相对成本根据/>设为0。对于老鼠流，根据/>将带宽的相对代价设为0，根据/>计算流表的相对成本。对于狗流，由于带宽消耗和数量都是中等大小，因此需要同时考虑带宽和流表资源消耗，相应的成本分别根据/>和/>计算。由于计算密集型流的CPU消耗远远大于计算稀疏型流的CPU消耗。因此，根据/>计算密集型流的CPU消耗相对成本，对于计算稀疏型流，将其设为0。

首先复制节点，将每一个节点都复制一个同样的节点排成两列，并将这样的两个节点连接起来，为了便于展示，本实施例将交换节点省略，仅以功能节点进行说明，交换节点的复制排序过程与功能节点类似，其复制排序过程参考功能节点的过程；如图3所示，将节点Vnf11复制成两个节点Vnf11’、Vnf11”，多播流的服务功能链中包含多条请求序列，每一请求序列可以代表一个类型，根据原多播网络拓扑图的节点的分类情况，如图2所示，将同种类型的节点放在一列，依次排列成第2到第L+1列，同时将原网络多播拓扑图中源节点和目的节点分别放在第1和第L+2列，源节点将一对多地连接第2列的节点，第2列的节点将多对多地依次连接到第3列的节点，以同样的方法一直连接到第L+1列，第L+1列的节点将多对多地连接到第L+2列的各个目的节点。同时，在第L列和第L+1列之间可能放置不同的目的节点，满足不同用户的不同需求，第L列的所有节点多对一地连接到放置第L列和第L+1列的目的节点，这个目的节点一对多地连接到第L列的节点。

可以理解的是，参数没有上标时表示复制前的节点，实质上也是指的第一节点，为了便于区分，将复制前的节点不使用上标进行表示，将复制后的节点本身表示为第一节点，将复制后的多产生的节点表示为第二节点，也即是参数的上标'表示复制后的第一节点，参数的上标”表示复制后的第二节点。

复制后排序前的权值和时延设置，参考如下公式：

表示链路uv上的带宽容量，/>表示当路由多播流f_i的SFC即服务功能链顺序时，链路uv上带宽剩余率，/>表示多播流f_i的请求带宽，L表示辅助图即节点复制路径选择图构造前的物理节点链路集合；/>表示节点s上的流表容量，/>表示当路由多播流f_i的SFC即服务功能链顺序时，节点s上的流表剩余率，θ_sn为交换节点集合，L'表示节点复制后排序前的链路集合；/>表示类型为m的VNF节点处的CPU容量，/>表示当路由多播流f_i的SFC即服务功能链顺序时，类型为m的VNF节点上CPU剩余率，F_i ^cpu表示多播流f_i的CPU消耗值；/>和/>分别表示节点复制后排序前链路e'的成本权值和链路时延，/>表示多播流通过节点u与节点v构成的链路所经历的平均时延，/>表示数据包通过类型为m的VNF节点的链路时延；其中，e'＝<u',u”>表示同一类型的节点复制后排序前的第一交换节点u'和第二交换节点u”的链路，e'＝<u″,v'>表示不同类型的节点复制后排序前的第二节点u″与第一节点v'的链路，e'＝<m′,m″>表示同一类型的VNF节点复制后排序前的第一VNF节点m′和第二VNF节点m″的链路，u,v表示物理节点即复制前的第一节点，节点u'和VNF节点v'均为复制后排序前的第一节点，且属于复制后不同类型的第一节点，且均属于节点集合；u”表示节点u'复制后排序前的第二节点，m′表示类型m的VNF节点复制后排序前的第一节点，m″表示类型m的VNF节点复制后排序前的第二节点。

在本实施例中，当所求e'＝<u',u”>是同一类型的第一交换节点u'与第二交换节点u”的链路时，是通过遍历所有物理节点的带宽的相对成本而得，当所求e'＝<u″,v'>是不同类型的第二节点u″与第一节点v'的链路时，这里的第一节点和第二节点均包括对应的第一交换节点和第一功能节点，以及第二交换节点和第二功能节点，当然这里也可以包括源节点s与不同类型的第一节点v'的链路、不同类型的第二节点u″与目的节点d的链路，通过遍历所有交换节点的流表的相对成本而得，当所求e'＝<m′,m″>是同一类型m的第一VNF节点m′与第二VNF节点m″的链路时，是通过遍历所有功能节点的CPU消耗的相对成本而得。

基于上述分析，可以得出节点复制路径选择图的有向边的子相对成本权值和子时延权值分别表示为：

和/>分别表示复制排列后得到的节点复制路径选择图的成本权值和链路时延。/>表示类型为m的节点的CPU消耗，/>表示当路由多播流f_i的SFC服务功能链顺序时，类型为m的节点的CPU资源剩余率；F_i ^cpu表示当路由多播流f_i的SFC服务功能链顺序时，类型为m的VNF节点的CPU消耗；θ_fn表示功能节点集合，/>表示同一个节点复制排序后的第一节点/>和第二节点/>的链路，/>表示不同节点复制排序后的第一节点/>和第二节点/>的链路；/>表示节点复制排序后得到的节点复制路径选择图中的链路集合；/>表示节点复制后排序前链路e'的成本权值；p(u”v')表示复制后排序前的第二节点u”与第一节点v'之间的路径；δ^delay表示数据包通过节点时所经历的平均时延；/>表示节点复制后排序前链路e'的链路时延；/>表示节点u'复制排序后的第一节点，/>表示节点u'复制排序后的第二节点，u”表示节点u'复制后排序前的第二节点，/>表示节点v'复制排序后的第一节点，节点u'和节点v'属于复制后不同顺序的第一节点，且均属于节点集合。

可以理解的是，由于的权值跟m'm”在复制路径选择图中的权值相同。在复制路径选择图中，每条链路/>都相当于在原始路径图上由最短路径算法(如Dijkstra)生成的一条路径，用p(u”v')表示这条路径。/>在复制路径选择图的权重等于路径p(u”v')的权重之和。

其中，可以将成本权值和时延权值通过权重求和，求和后的权重能够反映链路的真实权重，这里的权重参数分别取α∈(0,1)和β∈(0,1)，且α+β＝1。。

其二：构成最短路径树和主干路径选择，根据已经构造好的节点复制选择路径作为拓扑图，利用Dijkstra算法求得网络拓扑图中每个目的节点所对应的最小成本路径，然后求得每条最小成本路径中目的节点的个数。如图4所示引入n(M)表示一条路径中目的节点的个数：

其中，n(u)表示节点u的个数；n(M)表示在路径M中节点的个数，u表示节点，M表示路径。则各条路径M中具有最多节点的公式表示为：

n(M)_max＝max{n(M₁),n(M₂),...n(M_n)}

如图5所示，根据上式得到这五条链路中包含目的节点的个数及最大值为：

n(M₁)＝n(M₂)＝n(M₃)＝n(M₅)＝1,n(M₄)＝2

n(m)_max＝2

由于四条路径M₁、M₂、M₃、M₅中包含目的节点的个数都为1，而路径M₄中包含的目的节点个数为2，因此选择路径M₄作为主干路径T。最短路径树构造如图6所示，其包含主干路径M₄。

其三：节点分层，将选择过的主干路径T上的所有节点层级设为0，最短路径树上的剩余各个节点的层级根据距离主干路径T的跳数决定，如果一节点s1直接连接到主干路径T，那么这个节点的层级就为1，如果另一节点s2通过节点s1连接到主干路径，那么这个节点的层级为2，其他节点的层级按照同样的方法得出。如图7所示，主干路径T上节点Vnf12、Vnf22、Vnf31和源节点S、目的节点d2和d4的层级为0，节点Vnf11、Vnf13和Vnf32的层级为1，节点Vnf21、Vnf23和目的节点d1的层级为2，节点Vnf33和目的节点d3的层级为3，目的节点d5和d3的层级为4，于是我们得到各个节点的层级如下公式所示：

Hc(v)＝(0,1,0,1,2,0,2,0,1,3,2,0,3,0,4)

以上层级公式H_c(v)中层级数据顺序为源S,Vnf11,Vnf12,Vnf13,Vnf21,Vnf22,Vnf23,Vnf31,Vnf32,Vnf33,d1,d2,d3,d4,d5。

即节点层级为：

Hc(v)＝Grade(v)

其四：目的节点优化，由前一步骤节点分层得到的各目的节点层级，假如层级为0和1级，则不进行任何处理对于目的节点的层级大于1级，需要与复制路径选择图对比，看是否能找到使其层级降低的路径，即降低其跳数使成本降低。如图7所示，d1、d2、d3、d4、d5的层级分别为2、0、3、0、4，对于层级大于1的目的节点d1、d3和d5,经过与复制路径选择图对比，可以发现在复制路径选择图2中，目的节点d1、d3和d5与主干路径T上的节点相连，在这种情况下，可以降低目的节点d1、d3和d5的层级，即跳数，这样目的节点d1的层级就由2降到了1，d3的层级由3降到了1，d5的层级由4降到了1。将最短路径树中的目的节点d1、d3和d5分别断开与节点Vnf11、节点Vnf23和节点Vnf33的连接，转而连接节点Vnf12、节点Vnf22和节点Vnf31,这样也就构成了最佳多播树，整个过程就是对最短路径树中的目的节点的优化，也是最佳多播树的构造过程。

其五：时延约束建立(流程如图1所示)，由目的节点优化这一步骤已经找到具有路径时延的最佳多播树，这里所说的路径时延是最佳多播树中所有链路的总时延，时延约束建立是寻求满足最佳多播树中链路总时延是否满足我们的要求，也就是时延阈值，如果链路总时延低于阈值，输出最佳多播树的成本，如果链路总时延高于阈值，就拒绝这个多播请求，重新进行路由，直到找到满足时延阈值的最佳多播树。

上述五个部分完成了节点复制路径选择图构造、最短路径树和主干路径选择、节点分层、目的节点优化、时延约束建立，形成了一套完整的带有时延约束的最佳多播树构造方法，确保不超过多播链路总时延阈值的情况下找到最佳多播树。

下面参照附图2～9，说明NFV网络中的多播路由方法的具体实施步骤：

将原始网络图，如图2所示的每个节点都复制一个同样的节点，相同类型的节点放在同一列，依次排列成2到L+1列，并将源节点和部分目的节点分别放在第1列和第L+2列，另外，在每两列的节点之间可能会有一些目的节点，如图2中的d1、d2和d3。

在节点与其对应的复制节点之间连接一条链路，以一对多的连接方式将源节点与第2列的各个节点连接起来，第二列的节点以多对多的方式将第三列的节点依次连接起来，一直到第L+1列，以同样的方式将各列的节点连接起来，第L+1列中的节点与第L+2列中的目的节点以多对一的方式连接起来，对于每两列之间的目的节点，前一列的节点多对一连接到这个目的节点，这个目的节点一对多地连接到后一列的节点，并赋予它们所对应的链路成本权值和链路延迟权值和/>这样就构造好节点复制路径选择图，如图3所示。

根据图3的节点复制路径选择图用Dijkstra算法为每个目的节点选择最低成本路径，在图4中，路径M₁、M₂、M₃、M₄、M₅分别表示对于目的节点d1、d2、d3、d4、d5的最低成本路径。可以观察到这四条路径M₁、M₂、M₃和M₅中包含的节点的个数都为1，而路径M₄中包含的目的节点的个数为2，选取M₄这条路径作为主干路径，如图5所示。

如图6所示，由上一步得到主干路径M₄和对于目的节点d1、d2、d3和d5的最低成本路径M₁、M₂、M₃和M₅，其它不在主干路径M₄上和最低成本路径M₁、M₂、M₃和M₅上的节点通过节点复制路径选择图上节点与路径的关系连接到主路径上，例如节点Vnf21和节点Vnf32不在这些路径上，但Vnf21通过节点Vnf11连接到主路径上，Vnf32通过节点Vnf22连接到主路径上，这样最短路径树就生成了。

如图7所示，将所选主干路径M₄上的节点的层级设为0，即节点S、Vnf12、Vnf22、d2、Vnf31和d4的层级为0；节点Vnf11、Vnf13和Vnf32与主干路径上的节点直接连接，所以将他们的层级设为1，节点Vnf21、Vnf23和d1分别通过节点Vnf11、Vnf13和Vnf11连接到主干路径上，将节点Vnf21、Vnf23和d1的层级设为2，同理将节点d3和Vnf33的层级设为3，目的节点d5的层级设为4。

如图8所示，目的节点d2、d4的层级为0，目的节点d1的层级为2，d3的层级为3，d5的层级为4，在节点复制路径选择图中目的节点d1与主干路径上的节点Vnf12相连，d3与主干路径的节点Vnf22相连，d5与主干路径上的节点Vnf31相连，对节点层级优化，将目的节点d1断开与Vnf11的连接转而连接到Vnf12，目的节点d3断开与Vnf23的连接转而连接到Vnf22，目的节点d5断开与Vnf33的连接转而连接到Vnf31，这样目的节点d1、d3和d5的层级分别由2、3、4都变为了1，降低了目的节点的跳数。这样就能够找到最佳多播树，如图8所示。为了便于观察，将最佳多播树的节点位置变换为图9，图8与图9是一致的，不同的目的节点所对应的服务功能链有所不同，其采用的终端不同，所需的功能也可以不同；参考图8，对于目的节点d1，它的服务功能链是s-Vnf12’-Vnf12”-d1，对于目的节点d2和目的节点d3，它们的服务功能链是s-Vnf12’-Vnf12”-Vnf22’-Vnf22”-d2(d3)，对于目的节点d4和目的节点d5，它们的服务功能链则是s-Vnf12’-Vnf12”-Vnf22’-Vnf22”-d2-Vnf31’-Vnf31”-d4(d5)。

对于已经找到的最佳多播树，如果它的总链路时延小于或等于阈值，则输出结果，如果它的总链路时延大于阈值，则拒绝这个多播请求，重新路由该多播流。

实施例二

本实施例公开了一种NFV网络中的多播路由系统，本实例是应用于如实施例一公开的一种网络中的多播路由方法中，所述多播路由系统包括：

节点复制路径选择图构造模块，用于对多播网络的服务功能链中的节点进行复制，按照预定义的顺序放置所有节点，并根据节点之间相对成本构建有向链路，从而构造出节点复制路径选择图；

主干路径获取模块，用于使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出目的节点个数最多的最短路径作为主干路径；

节点层级计算模块，用于将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级；

节点层级优化模块，用于根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；

链路时延约束模块，用于基于所述节点层级优化模块获得的多播网络的最佳多播树，计算所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新所述最佳多播树。

路由模块，用于将多播网络的最佳多播树对应的虚拟链路映射到多播网络的物理链路中，动态部署VNF实例。

可以理解的是，本发明的一种NFV网络中的多播路由方法和一种NFV网络中的多播路由系统属于同一发明构思，其对应特征可以相互引用，本发明不再一一赘述。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

Claims (2)

1.一种NFV网络中的多播路由方法，其特征在于，所述方法包括以下步骤：

对多播网络的服务功能链中的节点进行复制，按照预定义的节点请求顺序放置所有节点，并根据相对成本为节点之间构建有向链路，从而构造出节点复制路径选择图；构造出节点复制路径选择图的具体方法包括：

将第一节点进行复制，得到第二节点，形成以第一节点和第二节点构成的两列节点，根据多播网络的服务功能链中的节点请求的顺序，将所有节点按照顺序放置；

将源节点置于首列，各个目的节点分别置于尾列以及不同请求顺序的两列节点之间，也即前一请求顺序的第二节点与后一请求顺序的第一节点之间；

按照相对成本分别对相邻列的节点之间，以及不同类型的节点之间构建出有向链路，从而形成节点复制路径选择图；

其中，相邻列的节点之间即包括源节点与请求顺序最靠前的第一节点之间，同一请求顺序的第一节点与第二节点之间，每一请求顺序的第二节点与对应的各个目的节点之间，以及各个目的节点与对应的每一请求顺序的第一节点之间；

使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出目的节点个数最多的最短路径作为主干路径；所述最短路径树中的每个目的节点都有一条从源节点出发的最短路径；从最短路径树中找出包含目的节点个数最多的最短路径作为主干路径

将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级；将位于主干路径上的节点设置为第一层级，与主干路径直接相连的节点设置为第二层级，与主干路径间接相连的节点设置为第三层级；第三层级的节点包括与主干路径通过一跳节点间接相连的第一节点，以及通过多跳节点间接相连的第N节点，N≥2，且为正整数；

根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；将当前节点复制路径选择图中第三层级的目的节点与其他节点复制路径选择图中对应节点的层级进行对比，若该对应节点在其他节点复制路径选择图中属于第二层级，则将当前节点复制路径选择图中第三层级的目的节点升级为第二层级的节点；

计算所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新所述最佳多播树；

将最佳多播树对应的虚拟链路映射到物理网络中，动态部署VNF实例；

其中，节点复制路径选择图中有向边的相对成本权值和时延权值分别表示为：

表示节点复制排序后链路/>的成本权值，/>表示节点复制排序后链路/>的链路时延，/>表示类型为m的VNF节点的CPU资源容量，/>表示当路由多播流f_i时，类型为m的VNF节点上的CPU资源剩余率；/>表示多播流f_i的CPU资源请求值；θ_fn表示功能节点集合也即VNF节点集合，/>表示节点复制排序后的第一节点/>与第二节点/>之间的链路；/>表示节点复制排序后得到的节点复制路径选择图中的链路集合；/>表示节点复制后排序前链路e'的成本权值；p(u”v')表示复制后排序前的第二节点u”与第一节点v'之间的路径；δ^delay表示数据包通过节点时所经历的平均时延；/>表示节点复制后排序前链路e'的链路时延；其中，/>表示同一个节点复制排序后的第一节点/>和第二节点/>的链路，表示节点复制排序后两个不同节点之间的链路；所述第一节点包括第一交换节点和第一VNF节点，所述第二节点包括第二交换节点和第二VNF节点；

节点复制后排序前链路e'的成本权值和节点复制后排序前链路e'的链路时延/>所采用的公式分别表示为：

表示链路uv上的带宽容量，/>表示当路由多播流f_i时，链路uv上带宽剩余率，F_i ^bw表示多播流f_i的请求带宽，L表示辅助图即节点复制路径选择图构造前的物理节点链路集合；表示交换节点s上的流表容量，/>表示当路由多播流f_i时，交换节点s上的流表剩余率，θ_sn为交换节点集合，L'表示节点复制后排序前的链路集合；/>表示类型为m的VNF节点的CPU容量，/>表示当路由多播流f_i时，类型为m的VNF节点上CPU资源的剩余率，F_i ^cpu表示多播流f_i的CPU资源请求值；/>和/>分别表示节点复制后排序前链路e'的成本权值和链路时延，/>表示多播流通过节点u与节点v构成的链路所经历的时延，/>表示数据包通过类型为m的VNF节点的链路处理时延；其中，e'＝<u',u”>表示同一个节点的复制后排序前的第一交换节点u'和第二交换节点u”的链路，e'＝<u″,v'>表示不同节点复制后排序前的第二节点u″与第一节点v'的链路，e'＝<m′,m″>表示同一VNF节点复制后排序前的第一VNF节点m′和第二VNF节点m″的链路，u,v表示物理节点即复制前的第一节点。

2.一种NFV网络中的多播路由系统，其应用于如权利要求1所述的一种NFV网络中的多播路由方法，其特征在于，所述多播路由系统包括：

节点复制路径选择图构造模块，用于对多播网络的服务功能链中的节点进行复制，按照预定义的顺序放置所有节点，并根据相对成本为节点之间构建有向链路，从而构造出节点复制路径选择图；

主干路径获取模块，用于使用节点复制路径选择图生成对应多播网络的最短路径树，从最短路径树中找出包含目的节点个数最多的最短路径作为主干路径；

节点层级计算模块，用于将最短路径树中的所有节点按照与距离主干路径的跳数进行分级，划分为多个层级；

节点层级优化模块，用于根据其他节点复制路径选择图中的目的节点的层级，更新当前节点复制路径选择图中对应的目的节点的层级，并获得当前节点复制路径选择图对应的多播网络的最佳多播树；

链路时延约束模块，用于基于所述节点层级优化模块获得的多播网络的最佳多播树，计算所述最佳多播树上的链路时延，若链路时延不满足时延阈值则将不满足时延阈值的多播树剔除，并重新构建路由链路；若链路时延满足时延阈值则得到具有时延约束的最佳多播树，并更新所述最佳多播树；

路由模块，用于将最佳多播树对应的虚拟链路映射到物理网络中，动态部署VNF实例。