CN113965616B - 一种基于vnf资源改变矩阵的sfc映射方法 - Google Patents

Abstract

本发明公开了一种基于VNF资源改变矩阵的SFC映射方法，包括：获取物理网络信息和多个用户业务请求信息；对所述物理网络信息进行第一预处理，以得到最短路径；对所有所述用户业务请求信息进行第二预处理，以对所有所述用户业务请求信息进行排序；确定待处理业务对应的业务部署路径；根据所述业务部署路径，对所述业务部署路径对应的依赖性VNF对进行第一映射，以得到第一映射策略集合；根据所述业务部署路径，对所述业务部署路径对应的无依赖性VNF进行第二映射，以得到第二映射策略集合；根据所述第一映射策略集合和第二映射策略集合，确定每个所述用户业务请求信息对应的每条虚拟链路，以实现SFC映射。本发明能够更准确地反映网络资源使用量。

Description

一种基于VNF资源改变矩阵的SFC映射方法

技术领域

本发明属于通信技术领域，具体涉及一种基于VNF资源改变矩阵的SFC映射方法。

背景技术

数据报文在网络中传递时，往往需要经过各种各样的业务节点，才能保证网络能够按照设计要求，提供给用户安全、快速、稳定的网络服务。通常，网络流量需要按照业务逻辑所要求的既定顺序穿过这些业务点，才能实现所需要的业务。

随着网络功能虚拟化(Network Function Virtualization，NFV)和网络虚拟化的发展，可将网络服务与具体的硬件分开，使网络服务能够以软件的形式交付，并部署在通用的硬件平台上；软件定义网络(Software Define Networking，SDN)可以通过集中控制，使得控制器生成能够自动形成业务功能链的流表。在SDN和NFV两者基础上建立的功能链就被称为服务功能链(Service Function Chain，SFC)，这就为网络服务的设计、部署和管理带来了很大灵活性和弹性。

但是，现有技术中的SFC映射方法只能对服务器资源进行平均分配，无法对客户需求执行针对性的操作，从而导致服务的效率较低，成本高昂，另外，现有技术中仅考虑虚拟网络功能(Virtual Network Function，VNF)带宽改变因子，而实际应用中该VNF的资源使用，可能会对同一个SFC中该VNF后续VNF的资源和虚拟链路带宽需求产生影响，现有技术与实际情况相差较远。

发明内容

为了解决现有技术中存在的上述问题，本发明提供了一种基于VNF资源改变矩阵的SFC映射方法。本发明要解决的技术问题通过以下技术方案实现：

一种基于VNF资源改变矩阵的SFC映射方法，应用于包括VNF及VNF管理设备的NFV网络中，包括：步骤1：获取物理网络信息和多个用户业务请求信息，其中，所述用户业务请求信息中包括用户业务请求的VNF集合，所述用户业务请求的VNF集合中包括依赖性VNF对和无依赖性VNF；步骤2：对所述物理网络信息进行第一预处理，以得到最短路径；步骤3：对所有所述用户业务请求信息进行第二预处理，以对所有所述用户业务请求信息进行排序；步骤4：根据所述用户业务请求信息确定待处理业务，以及确定所述待处理业务对应的业务部署路径；步骤5：根据所述业务部署路径，对所述业务部署路径对应的所述依赖性VNF对进行第一映射，以得到第一映射策略集合；步骤6：根据所述业务部署路径，对所述业务部署路径对应的所述无依赖性VNF进行第二映射，以得到第二映射策略集合；步骤7：根据所述第一映射策略集合和第二映射策略集合，确定每个所述用户业务请求信息对应的每条虚拟链路，以实现SFC映射。

在本发明的一个实施例中，所述物理网络信息包括所述NFV网络中的物理网络节点，所述步骤2包括：步骤2-1：检测所述物理网络节点中连接有预设服务器的所有节点，确定所述NFV网络中已有的VNF集合；步骤2-2：计算所述物理网络节点中每两节点之间的前k条最短路径，其中，0<k≤K，K为大于0的整数。

在本发明的一个实施例中，所述物理网络节点中包括源节点和目的节点，所述步骤2-2包括：步骤2-201：在物理网络节点中随机选取一个源节点和一个目的节点，其中，将选取的所述源节点确定为起始节点，将选取的所述目的节点确定为终止节点，将当前选取的起始节点和终止节点确定为一组待处理节点对；步骤2-202：按照第一跳数计算规则，计算所述待处理节点对之间所有路径的跳数，将跳数最少的路径确定为第一路径；步骤2-203：将所述第一路径中途径的物理网络节点，确定为偏离节点；步骤2-204：按照第二跳数计算规则，计算每个偏离节点与终止节点之间所有路径的跳数，将每个偏离节点与终止节点之间跳数最少的路径确定为第二路径；步骤2-205：将所述第一路径分别与每个所述第二路径拼接，以得到第一候选路径集合，其中，所述第一候选路径集合中包括第一候选路径；步骤2-206：按照跳数由少到多的顺序，对所述第一候选路径集合中的路径进行排序；步骤2-207：将所述第一路径和排序后的第一候选路径集合中的前k-1条路径，确定为当前选取的待处理节点对对应的前k条最短路径；步骤2-208：判断是否已获得所述当前选取的待处理节点对对应的所述前k条最短路径；步骤2-209：当已获得当前选取的待处理节点对对应的所述前k条最短路径时，继续执行步骤2-210；或者，当未获得当前选取的待处理节点对对应的前k条最短路径时，重复执行步骤2-203至步骤2-209；步骤2-210：判断是否已获得所述物理网络节点中所有待处理节点对应的前k条最短路径；步骤2-211：当已获得所有待处理节点对对应的前k条最短路径时，继续执行步骤3；或者，当未获得所有待处理节点对应的前k条最短路径时，在所述物理网络节点的未处理节点对中，继续随机选取一个节点对，其中，将选取的所述节点对中的一个节点确定为新的起始节点，将选取的所述节点对中的另一个节点确定为新的终止节点，将当前选取的新的起始节点和新的终止节点确定为新的一组待处理节点，重复执行步骤2-202至步骤2-211。

本发明的有益效果：

本发明首次提出了基于VNF资源改变矩阵的概念，重点研究基于VNF资源改变矩阵的SFC映射问题，既考虑到VNF对链路带宽资源的影响，也考虑其对网络中节点资源如计算资源与存储资源等的影响，即考虑当前VNF对同一个SFC中后续VNF的影响。与已有算法相比，能够真实地反映网络中节点资源与链路资源的使用量，可以更真实地反映网络拓扑中资源的使用情况，从而能够针对性地进行资源分配。

以下将结合附图及实施例对本发明做进一步详细说明。

附图说明

图1是本发明实施例提供的一种基于VNF资源改变矩阵的SFC映射方法流程示意图；

图2是本发明实施例提供的一种VNF对网络中节点资源的影响示意图；

图3是本发明实施例提供的一种VNF映射前的网络状态示意图；

图4是本发明实施例提供的一种VNF映射后的网络状态示意图；

图5是本发明实施例提供的一种虚拟链路映射示意图；

图6是本发明仿真采用的NSFNET网络拓扑示意图；

图7是本发明仿真采用的US Backbone网络拓扑示意图；

图8是本发明仿真中基于NSFNET得到的不同资源改变矩阵均值下的网络中计算资源使用量随业务请求数变化的对比示意图；

图9是本发明仿真中基于US Backbone得到的不同资源改变矩阵均值下的网络中计算资源使用量随业务请求数变化的对比示意图；

图10是本发明仿真中基于NSFNET得到的不同资源改变矩阵均值下的网络中最大频隙号随业务请求数变化的对比示意图；

图11是本发明仿真中基于US Backbone得到的不同资源改变矩阵均值下的网络中最大频隙号随业务请求数变化的对比示意图；

图12是本发明仿真中基于NSFNET得到的不同资源改变矩阵均值下的归一化的网络资源使用量随业务请求数变化的对比示意图；

图13是本发明仿真中基于US Backbone得到的不同资源改变矩阵均值下的归一化的网络资源使用量随业务请求数变化的对比示意图。

具体实施方式

下面结合具体实施例对本发明做进一步详细的描述，但本发明的实施方式不限于此。

实施例一

请参见图1，图1是本发明实施例提供的一种基于VNF资源改变矩阵的SFC映射方法流程示意图，应用于包括VNF及VNF管理设备的NFV网络中，所述方法包括：

步骤1：获取物理网络信息和多个用户业务请求信息，其中，所述用户业务请求信息中包括用户业务请求的VNF集合，所述用户业务请求的VNF集合中包括依赖性VNF对和无依赖性VNF。

本发明所述的基于VNF资源改变矩阵的SFC映射方法，是基于节点重要性与用户需求双感知的SFC映射方法。

其中，VNF和SFC是指，NFV技术将处理数据包的网络功能从硬件中间盒子映射到运行在预设服务器中的软件中间盒子上，所述预设服务器如x86架构服务器，运行在软件中间盒子上的网络功能称为VNF，多个VNF通常按照一个特定的顺序连接构成SFC来提供网络业务。本发明物理网络信息包括已有VNF集合，用户业务请求信息包括业务请求VNF集合，业务请求VNF集合包括依赖性VNF对、无依赖性VNF。其中，用户业务请求信息除了包括业务请求VNF集合，还包括业务请求的源节点与目的节点，以及各VNF资源改变矩阵，其包含VNF的带宽改变因子与节点改变因子。

步骤2：对所述物理网络信息进行第一预处理，以得到最短路径。

可选的，所述物理网络信息包括所述NFV网络中的物理网络节点。

可选的，所述步骤2包括：

步骤2-1：检测所述物理网络节点中连接有预设服务器的所有节点，确定所述NFV网络中已有的VNF集合；

所述预设服务器如x86架构服务器。

步骤2-2：计算所述物理网络节点中每两节点之间的前k条最短路径，其中，0<k≤K，K为大于0的整数。

本发明以k取值为3进行举例说明。

可选的，所述物理网络节点中包括源节点和目的节点。

可选的，所述步骤2-2包括：

步骤2-201：在物理网络节点中随机选取一个源节点和一个目的节点，其中，将选取的所述源节点确定为起始节点，将选取的所述目的节点确定为终止节点，将当前选取的起始节点和终止节点确定为一组待处理节点对；

步骤2-202：按照第一跳数计算规则，计算所述待处理节点对之间所有路径的跳数，将跳数最少的路径确定为第一路径；

所述第一跳数计算规则如迪杰斯特拉Dijkstra算法。所述第一路径又称基准路径。

步骤2-203：将所述第一路径中途径的物理网络节点，确定为偏离节点；

步骤2-204：按照第二跳数计算规则，计算每个偏离节点与终止节点之间所有路径的跳数，将每个偏离节点与终止节点之间跳数最少的路径确定为第二路径；

所述第二跳数计算规则，如迪杰斯特拉Dijkstra算法以及预设条件，所述预设条件如满足路径无环条件和路径非重复条件的跳数最少路径。其中，路径无环条件是指，跳数最少路径不能通过基准路径上从源节点到偏离节点之间的任何一个节点；路径非重复条件是指从跳数最少路径上偏离节点出发的边不能与已找到的任何一条最短路径上从此偏离节点出发的边相同。

步骤2-205：将所述第一路径分别与每个所述第二路径拼接，以得到第一候选路径集合，其中，所述第一候选路径集合中包括第一候选路径；

步骤2-206：按照跳数由少到多的顺序，对所述第一候选路径集合中的路径进行排序；

步骤2-207：将所述第一路径和排序后的第一候选路径集合中的前k-1条路径，确定为当前选取的待处理节点对应的前k条最短路径；

步骤2-208：判断是否已获得所述当前选取的待处理节点对对应的所述前k条最短路径；

步骤2-209：当已获得当前选取的待处理节点对对应的所述前k条最短路径时，继续执行步骤2-210；或者，当未获得当前选取的待处理节点对对应的前k条最短路径时，重复执行步骤2-203至步骤2-209；

步骤2-210：判断是否已获得所述物理网络节点中所有待处理节点对对应的前k条最短路径；

步骤2-211：当已获得所有待处理节点对对应的前k条最短路径时，继续执行步骤3；

或者，当未获得所有待处理节点对对应的前k条最短路径时，在所述物理网络节点的未处理节点对中，继续随机选取一个节点对，其中，将选取的所述节点对中的一个节点确定为新的起始节点，将选取的所述节点对中的另一个节点确定为新的终止节点，将当前选取的新的起始节点和新的终止节点确定为新的一组待处理节点，重复执行步骤2-202至步骤2-211。

步骤3：对所有所述用户业务请求信息进行第二预处理，以对所有所述用户业务请求信息进行排序。

可选的，所述步骤3包括：

步骤3-1：遍历所有用户业务请求信息，分析所述用户业务请求信息中每个用户业务请求的VNF对应的依赖性信息；

可选的，所述步骤3-1之后，所述方法还包括：记录每个用户业务请求的VNF对应的依赖性信息。

步骤3-2：根据所述依赖性信息，对所有用户业务请求信息进行排序，其中，所述依赖性越高，排序越靠前。

本发明能够将含有依赖性VNF的业务请求信息放在前面，并优先部署在物理网络中。

步骤4：根据所述用户业务请求信息确定待处理业务，以及确定所述待处理业务对应的业务部署路径。

本发明能够在业务请求信息中获取一待处理业务。

可选的，所述用户业务请求信息中包括业务请求节点，所述业务请求节点包括业务请求源节点和业务请求目的节点。

可选的，所述步骤4包括：

步骤4-1：在物理网络节点中每两节点之间的前k条最短路径中，确定所述业务请求源节点和业务请求目的节点之间的前k条最短路径。

步骤4-2：将所述业务请求源节点和所述业务请求目的节点之间的前k条最短路径，确定为第二候选路径集合；

步骤4-3：分别计算第二候选路径集合中的路径上，所述已有的VNF集合与所述用户业务请求的VNF集合的交集；

步骤4-4：在所有所述交集中，确定最大的交集；

步骤4-5：将所述最大交集对应的路径确定为目标最短路径；

步骤4-6：将所述目标最短路径确定为所述待处理业务对应的业务部署路径。

可选的，当候选路径上的节点集中的某一节点的服务器中资源不足以部署业务请求的VNF，则更换业务部署路径，使其能够成功部署。

步骤5：根据所述业务部署路径，对所述业务部署路径对应的所述依赖性VNF对进行第一映射，以得到第一映射策略集合。

可选的，所述步骤5包括：

步骤5-1：从所述用户业务请求的VNF集合中随机选取一个依赖性VNF对，将选取的依赖性VNF对从所述用户业务请求的VNF集合中删除；

步骤5-2：将所述选取的依赖性VNF对标记为两个无依赖性VNF；

本发明能够将选取的依赖性VNF对视为两个不具有依赖性的VNF。

步骤5-3：根据预设映射规则，对标记后的两个无依赖性VNF进行映射，以得到第一映射结果；其中，所述映射结果中包括无依赖性VNF映射到的节点位置；

所述预设映射规则如下：按照贪心策略的原则进行部署，在跳数最少的候选路径与最大交集候选路径上分别计算其部署时的网络资源消耗，包括初次部署VNF实例所需额外计算资源和VNF提供服务所需计算资源与带宽资源。一般来说，初次部署时消耗的额外资源量少于其提供服务时的资源消耗。然后基于贪心策略，选择网络资源消耗最小的方案部署VNF。在计算带宽资源或计算资源消耗时，采用LFGL的规则，即，将VNF资源改变矩阵(Resource Change Matrix，RCM)中对应的影响较小的VNF放置在距离源节点更近的服务器节点上，而影响较大的VNF则部署在距离目的节点更近处，该方法能够有效减小网络资源的消耗。

步骤5-4：判断第一映射结果是否符合所述选取的依赖性VNF对的依赖信息；

步骤5-5：当第一映射结果符合所述选取的依赖性VNF对的依赖信息时，则将该第一映射结果作为一个第一映射策略；

或者，当第一映射结果不符合所述选取的依赖性VNF对的依赖信息时，将标记后的两个无依赖性VNF映射在同一个节点上，以得到多个第二映射结果，从得到的多个第二映射结果中选取网络资源消耗最少的一个作为一个第一映射策略；

步骤5-6：在所述用户业务请求的VNF集合中，分析依赖性VNF对的数量；其中，当该数量大于0时，则重复执行步骤5-1至步骤5-6；或者，当该数量等于0时，则继续执行步骤5-7；

即，判断所述业务请求VNF集合中是否仍存在至少一个依赖性VNF对，若是，则重复执行步骤5-1至步骤5-6，否则，完成业务请求VNF集合中所有依赖性VNF对的映射，并执行步骤5-7。

步骤5-7：将基于所有依赖性VNF对得到的第一映射策略，确定为第一映射策略集合。

步骤6：根据所述业务部署路径，对所述业务部署路径对应的所述无依赖性VNF进行第二映射，以得到第二映射策略集合。

可选的，所述步骤6包括：

步骤6-1：从所述用户业务请求的VNF集合中随机选取一个无依赖性VNF；

步骤6-2：根据预设映射规则，对选取的无依赖性VNF进行第二映射，以得到第三映射结果，以及将所述第三映射结果确定为一个第二映射策略；

步骤6-4：在所述用户业务请求的VNF集合中，分析无依赖性VNF的数量；其中，当该数量大于0时，则重复执行步骤6-1至步骤6-4；或者，当该数量等于0时，则执行步骤6-5；

即，判断所述业务请求VNF集合是否为空，若是，则所有的无依赖性VNF映射完成，执行步骤6-5，否则，重复执行步骤6-1至步骤6-4。

步骤6-5：将基于所有无依赖性VNF得到的第二映射策略，确定为第二映射策略集合。

步骤7：根据所述第一映射策略集合和第二映射策略集合，确定每个所述用户业务请求信息对应的每条虚拟链路，以实现SFC映射。

可选的，所述用户业务请求信息中包括待映射的虚拟链路集合。

可选的，所述步骤7包括：

步骤7-1：从所述待映射的虚拟链路集合中随机选取一条虚拟链路；

步骤7-2：基于所述第一映射策略集合和所述第二映射策略集合，分析当前选取的虚拟链路两端的用户业务请求的VNF的映射位置；其中，当所述映射位置在同一个节点上时，确定当前选取的虚拟链路不需要映射，执行步骤7-8；或者，当所述映射位置不在同一节点上时，确定当前选取的虚拟链路需要映射，执行步骤7-3至步骤7-8；

步骤7-3：分析当前选取的虚拟链路的次序；其中，在当前选取的虚拟链路为第一条虚拟链路时，则从所述用户业务请求信息中获取当前选取的虚拟链路所需的频隙数；或者，在当前选取的虚拟链路不是第一条虚拟链路时，按照预设频隙数计算规则，计算得到当前选取的虚拟链路所需的频隙数。

所述预设频隙数计算规则，如前一条选取的虚拟链路所需的频隙数乘以当前选取的虚拟链路起始端业务请求信息中的VNF的带宽改变因子，得到当前选取的虚拟链路所需的频隙数。

步骤7-4：当前选取的虚拟链路两端的业务请求VNF映射在的两节点间的前k条最短路径作为第二候选路径集合；

步骤7-5：按照预设命中规则，分别在所述第二候选路径集合中的每条候选路径上为当前选取的虚拟链路分配频隙，得到k个路由和频谱分配方案；

所述预设命中规则，如首次命中算法。

步骤7-6：在所述k个路由和频谱分配方案中，选取使最大频隙号增加量最少的一个目标路由和频谱分配方案；

步骤7-7：根据所述目标路由和频谱分配方案，映射当前选取的虚拟链路；

步骤7-8：判断所述待映射的虚拟链路集合中所有待映射的虚拟链路是否映射完成；其中，当映射全部完成时，确定SFC映射完成；或者，当映射未全部完成时，重复执行步骤7-1至步骤7-8。

可选的，所述用户业务请求信息中还包括每个用户业务请求的VNF对应的资源改变矩阵，所述资源改变矩阵中包括带宽改变因子和节点改变因子。

可选的，所述按照预设频隙数计算规则，计算当前选取的虚拟链路所需的频隙数，包括：

步骤S11：在当前选取的虚拟链路起始端的用户业务请求信息中，确定带宽改变因子；

步骤S12：将上一条选取的虚拟链路所需的频隙数与所述带宽改变因子相乘，以计算得到当前选取的虚拟链路所需的频隙数。

可选的，所述步骤7之后，所述方法还包括：

步骤S21：判断多个用户业务请求信息中是否还有未处理的用户业务请求信息；

步骤S22：当多个用户业务请求信息中还有未处理的用户业务请求信息时，重复步骤1至步骤7；或者，当多个用户业务请求信息中没有未处理的用户业务请求信息时，确定SFC映射完毕。

本实施例采用了基于前K条最短路径算法和最大交集算法的选取业务部署路径方法，以及基于VNF间依赖性关系、VNF带宽改变因子、网络中节点的重要性和用户业务请求的VNF映射方法，并且结合了基于前K条最短路径算法和首次命中(First Fit)算法的路由和频谱分配方法。在业务源节点与目的节点间的前K条最短路径中选取VNF可重用数最多的路径与跳数最少的路径作为业务部署路径，接着在所选路径上映射SFC，并使用路由和频谱分配方法优化虚拟链路的映射，完成业务请求的部署。由于在对网络中的服务器分配资源时考虑到了网络中节点的重要性与用户的业务请求，使得网络拓扑中的服务器资源是有针对性地分配而不是平均分配的，能够最大化地为用户请求较密集的区域提供数目更多而且质量更佳的服务，同时能够避免在用户请求较少的区域使用过多的资源，有效提高资源的利用率。由于构建和映射SFC时，在满足VNF间的依赖性关系的前提下，根据VNF的带宽改变因子，根据最小最先最大最后(LFGL)的原则，将减小带宽占用的VNF尽可能映射到所选路径前端，将增大带宽占用的VNF尽可能映射到所选路径末端。故本实施例方法能够在满足VNF间依赖性关系的同时，尽可能减少业务请求VNF的部署数目和底层弹性光网络中所有光纤链路的最大频隙号，从而减少业务部署成本，可以解决在NFV场景下部署存在依赖性的VNF对业务请求的问题。

综上所述，本发明首次提出了VNF资源改变矩阵的概念，重点研究基于VNF资源改变矩阵的SFC映射问题，能够考虑到VNF对链路带宽资源的影响，也能够考虑到其对网络中节点资源如计算资源与存储资源等的影响，能够真实地反映网络中节点资源的使用量，能够更真实地反映网络拓扑中资源的使用情况，从而能够针对性地进行资源分配。

下面结合实施例对本发明的SFC构建和映射过程进行详细说明。

实施例图参照附图2、附图3、附图4，附图2中，物理网络中有8个节点，其中节点1、节点3、节点4和节点6分别连接有一个服务器。当前网络中已存在的VNF由矩形框表示，它们是节点1上的VNF1、节点3上的VNF2、节点4上的VNF4和VNF5、节点6上的VNF8。

以初始频隙数需求为1，需求的VNF集合为{VNF2，VNF4，VNF8}，源节点与目的节点分别为节点3和节点6的业务请求为例，来说明本发明方法部署存在依赖性VNF对的业务请求的过程。其中VNF4和VNF8是一个依赖性VNF对，VNF8必须在VNF4之前执行。此外，VNF2，VNF4，VNF8的带宽改变因子分别为r2＝1.3，r4＝0.6，r8＝1.4。

步骤1，预处理物理网络信息。

筛选出连接有x86架构服务器的所有节点：节点1、节点3、节点4和节点6，作为部署VNF的物理节点集合。计算物理网络中任意两节点间的前3条最短路径，其中业务请求源宿节点间的前3条最短路径由图2中的虚线箭头表示，它们分别为：节点3->节点1->节点2->节点6、节点3->节点4->节点2->节点6和节点3->节点5->节点7->节点6。

步骤2，选取业务部署路径。

第1条路径(节点3->节点1->节点2->节点6)上已有的VNF集合为{VNF1,VNF2,VNF8}，与服务需求的VNF集合的交集为{VNF2}；第2条路径(节点3->节点4->节点2->节点6)上已有的VNF集合为{VNF2,VNF4,VNF5,VNF8}，与服务需求的VNF集合的交集为{VNF2,VNF4,VNF8}；第3条路径(节点3->节点5->节点7->节点6)上已有的VNF集合为{VNF2,VNF8}，与服务需求的VNF集合的交集为{VNF2}。第2条路径(节点3->节点4->节点2->节点6)所得交集最大，在此路径上能够尽可能多地重用VNF，所以选择第2条路径(节点3->节点4->节点2->节点6)作为业务部署路径，由附图3中的实线箭头表示。

步骤3，映射依赖性VNF对。

映射依赖性VNF对：VNF4和VNF8。在所选业务部署路径上，已有的VNF8在节点6上，已有的VNF4在节点4上。由于VNF8在业务部署路径上的位置处于VNF4之后，如果为了重用VNF4和VNF8，将业务需求的VNF4映射在节点6上，将VNF8映射在节点4上，则会导致VNF8在VNF4之后执行，无法满足VNF间的依赖性关系。因为r8＝1.4>1，r4＝0.6≤1，所以应将减小带宽占用的VNF4尽可能映射到路径的前端，将增大带宽占用的VNF8尽可能映射到路径的末端，以减少虚拟链路消耗的带宽频谱资源，又由于VNF8必须在VNF4之前执行，所以应将VNF8和VNF4映射到业务部署路径上同一个服务器节点中。为了重用业务部署路径上已存在的VNF，应将VNF4和VNF8同时映射到节点4或节点6上，又由于r4*r8＝0.84≤1，所以选取靠近路径前端的节点4作为映射节点。最终将VNF4和VNF8同时映射到节点4上，此时能够重用VNF4。

步骤4，映射剩余的VNF。

映射剩余的VNF：VNF2。由于业务部署路径上服务器节点3中已存在VNF2，故直接将业务需求的VNF2映射到节点3上，以重用已存在的VNF2。

此时，业务需求的VNF全部映射完成，同时构建完成的SFC为：VNF2->VNF8->VNF4。VNF映射结果用附图3中椭圆框表示，带阴影的椭圆框表示可以重用这个VNF。

步骤5，映射虚拟链路。

为了减小弹性光网络中的最大频隙号，在虚拟链路两端VNF所在的物理节点间的前3条最短路径上，分别使用首次命中(First Fit)算法尝试为虚拟链路分配频隙，并选取使最大频隙号增加最少的一条作为虚拟链路映射的路径，而不是简单地把虚拟链路映射到业务部署路径上。

以附图4中的SFC(VNF2->VNF8->VNF4)中VNF2到VNF8间虚拟链路为例说明虚拟链路的映射过程。当前虚拟链路需求的频隙数可以由业务需求的初始频隙数1乘以VNF1的带宽改变因子r1＝1.3得出，为1*1.3＝1.3个频隙，所以应为此条虚拟链路分配2个频隙。VNF2和VNF8所在物理节点分别为节点3和节点4，如附图4所示，两节点间的前3条最短路径分别为：节点3->节点4、节点3->节点5->节点4、节点3->节点1->节点2->节点4。如附图5，其中每条物理链路上的频隙数占用情况由矩形框表示，灰色矩形框表示已占用的频隙，白色矩形框表示空闲频隙。根据First Fit算法得到每条路径上为虚拟链路分配的频隙，并用黑色圆点标出。其中在路径节点3->节点4上为虚拟链路分配第8个和第9个频隙，分配结束后最大频隙号是9；在路径节点3->节点5->节点4上为虚拟链路分配第4个和第5个频隙，分配结束后最大频隙号是7；在路径节点3->节点1->节点2->节点4上为虚拟链路分配第8个和第9个频隙，分配结束后最大频隙号是9。故选取使网络中最大频隙号增加最少的方案：将VNF2到VNF8间的虚拟链路映射到路径节点3->节点5->节点4上，并为其分配第4个和第5个频隙。

虚拟链路全部映射完成后，业务部署完成。

进一步地，基于仿真实验验证本发明所述方法的技术效果：

1.仿真条件

使用图6所示的14个节点的NSFNET拓扑和附图7所示的28个节点的US Backbone拓扑进行仿真。仿真参数设置如下：共有8种类型的VNF，类型1～4的VNF的带宽改变因子在区间[0.5,1]随机选取，其余类型VNF的带宽改变因子在区间[1,2]中随机选取。业务初始频隙数请求在区间[4，8]中随机选取。每条光纤链路容纳358个频隙。另外，选取2对依赖性VNF对，分别为VNF7和VNF3、VNF4和VNF8，其中VNF7必须在VNF3之前执行，VNF4必须在VNF8之前执行。在每次实验中，业务请求的数量从100变化到600，每个业务请求最多需要3种类型的VNF。对比VNF的带宽改变因子与节点资源改变因子在不同大小下对网络资源用量的影响，将其均值用符号表示为M_ravg，其值分别为0.8、1和1.2，将优化目标的权重系数设为α＝β＝0.5，为避免单次实验的偶然性，本文进行20次实验取平均值作为最终结果。

2.仿真内容：

实验目标为对比NSFNET与US Backbone两种拓扑下，VNF资源改变矩阵在不同均值下对网络资源产生的影响，优化目标为最小化网络中的总资源使用量，包括计算资源使用量与带宽资源使用量。其中计算资源使用量还包括初次部署VNF实例时所产生的额外花销，带宽资源使用量用最大频隙号来表示，这是因为实验场景是在弹性光网络中，其带宽由频谱资源来提供。优化目标可用公式表示为：

该式第1项为归一化的最大频隙号，第2项为归一化的计算资源消耗，又可分为放置在节点上的VNF实例使用的计算资源与初次部署时额外使用的计算资源，α和β为权重系数，其中α+β＝1，α≥0且β≥0。

3.仿真结果分析：

由于在业务请求数量较少时出现了大量的重复数据，因此仿真结果图的横坐标业务请求数的范围是300个到600个之间。

图8和图9分别给出了不同的M_ravg在两个拓扑中的计算资源消耗随业务请求数的变化，从图中可以明显看出VNF对计算资源消耗的影响。在NSFNET中，VNF的RCM均值的增加使计算资源消耗增加了9％～17％，而在US Backbone中，VNF的RCM的影响约为12％～17％。对比图8和图9，可以发现同样的业务请求数在两个拓扑中消耗的计算资源数基本一致，其分别在M_ravg为1～1.2(NSFNET)与0.8～1(US Backbone)区间资源增长较多的原因为受节点服务器资源容量的限制，有较多的VNF不能重用已有实例而需要部署在其他节点服务器上，因此增加了VNF实例的部署资源消耗。在两个拓扑波动较大的区间不同的原因是NSFNET中只有7个服务器节点，其服务器资源相比US Backbone多，因此在RCM较大时才会受到资源容量的限制。此外，产生该现象的另一个原因可能是网络总资源有限，使用平均分配的方式将资源分配到各个节点上，使个别服务请求较多的节点无法完成对应服务，对应的VNF部署在其他节点时产生了额外的部署成本。

图10和图11分别给出了不同的M_ravg在两个拓扑中的最大频隙号随业务请求数的变化，从图中可知随M_ravg的增长，网络中的最大频隙号有明显增加。在NSFNET中，M_ravg使最大频隙号增加24％～40％，而在US Backbone中，其增幅为29％～40％。对比两图可以发现，USBackbone中的最大频隙号要小于NSFNET，其原因在于US Backbone拓扑较大，其中VNF的分布范围较为广泛，能够利用的链路较多，因此流量在每条链路上占用的频隙数就相对较少。此外，可以通过公式估算链路中的频隙数，频隙数＝(虚拟链路数*虚拟链路平均占用频隙*节点间平均跳数)/物理链路数。在两个拓扑中，业务请求数相同，因此虚拟链路与其占用频隙基本相同，US Backbone的物理链路数目为90条，是NSFNET的两倍之多，而US Backbone的网络节点间平均跳数为3.2跳，是NSFNET的1.7倍，图示结果基本符合计算结果。

图12和图13分别展示在两种拓扑下归一化网络资源消耗的对比，如图所示，随着M_ravg的增加，归一化的网络资源消耗呈增长趋势。在NSFNET中，增长率约为13％～25％，而在US Backbone中，增长率约为19％～24％，分别对比两个拓扑中的数值，可以发现其数值很接近，说明VNF的RCM对网络资源产生的影响不受网络拓扑的限制。

由图10可知，在NSFNET中M_ravg为1.2时网络资源的消耗增加较快，说明较小的拓扑相比于较大的拓扑对于资源的消耗的变动体现更加明显，这是因为在小型拓扑中业务部署比较密集，尤其是因为有VNF实例重用的发生，一些链路的频隙使用较多，导致网络中最大频隙号较高。而在US Backbone中，其服务器节点的资源量相比于NSFNET少，因此VNF被更加广泛地部署在整个拓扑中，使链路的使用较平均，客观上降低了最大频隙号，也使得归一化的网络资源消耗更偏向线性增长。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。此外，本领域的技术人员可以将本说明书中描述的不同实施例或示例进行接合和组合。

本领域技术人员应明白，本申请的实施例可提供为方法、装置(设备)、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式，这里将它们都统称为“模块”或“系统”。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。计算机程序存储/分布在合适的介质中，与其它硬件一起提供或作为硬件的一部分，也可以采用其他分布形式，如通过Internet或其它有线或无线电信系统。

本申请是参照本申请实施例的方法、装置(设备)和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。

Claims (8)

1.一种基于VNF资源改变矩阵的SFC映射方法，应用于包括VNF及VNF管理设备的NFV网络中，其特征在于，包括：

步骤1：获取物理网络信息和多个用户业务请求信息，其中，所述用户业务请求信息中包括用户业务请求的VNF集合，所述用户业务请求的VNF集合中包括依赖性VNF对和无依赖性VNF；

步骤2：对所述物理网络信息进行第一预处理，以得到最短路径；

步骤3：对所有所述用户业务请求信息进行第二预处理，以对所有所述用户业务请求信息进行排序；

步骤4：根据所述用户业务请求信息确定待处理业务，以及确定所述待处理业务对应的业务部署路径；

步骤5：根据所述业务部署路径，对所述业务部署路径对应的所述依赖性VNF对进行第一映射，以得到第一映射策略集合；

步骤6：根据所述业务部署路径，对所述业务部署路径对应的所述无依赖性VNF进行第二映射，以得到第二映射策略集合；

步骤7：根据所述第一映射策略集合和第二映射策略集合，确定每个所述用户业务请求信息对应的每条虚拟链路，以实现SFC映射；

所述步骤5包括：

步骤5-1：从所述用户业务请求的VNF集合中随机选取一个依赖性VNF对，将选取的依赖性VNF对从所述用户业务请求的VNF集合中删除；

步骤5-2：将所述选取的依赖性VNF对标记为两个无依赖性VNF；

步骤5-3：根据预设映射规则，对标记后的两个无依赖性VNF进行映射，以得到第一映射结果；其中，所述映射结果中包括无依赖性VNF映射到的节点位置；

步骤5-4：判断第一映射结果是否符合所述选取的依赖性VNF对的依赖信息；

步骤5-5：当第一映射结果符合所述选取的依赖性VNF对的依赖信息时，则将该第一映射结果作为一个第一映射策略；

或者，当第一映射结果不符合所述选取的依赖性VNF对的依赖信息时，将标记后的两个无依赖性VNF映射在同一个节点上，以得到多个第二映射结果，从得到的多个第二映射结果中选取网络资源消耗最少的一个第二映射结果作为一个第一映射策略；

步骤5-6：在所述用户业务请求的VNF集合中，分析依赖性VNF对的数量；其中，当该数量大于0时，则重复执行步骤5-1至步骤5-6；或者，当该数量等于0时，则继续执行步骤5-7；

步骤5-7：将基于所有依赖性VNF对得到的第一映射策略，确定为第一映射策略集合。

2.根据权利要求1所述的方法，其特征在于，所述物理网络信息包括所述NFV网络中的物理网络节点，所述步骤2包括：

步骤2-1：检测所述物理网络节点中连接有预设服务器的所有节点，确定所述NFV网络中已有的VNF集合；

步骤2-2：计算所述物理网络节点中每两节点之间的前k条最短路径，其中，0<k≤K，K为大于0的整数。

3.根据权利要求2所述的方法，其特征在于，所述物理网络节点中包括源节点和目的节点，所述步骤2-2包括：

步骤2-201：在物理网络节点中随机选取一个源节点和一个目的节点，其中，将选取的所述源节点确定为起始节点，将选取的所述目的节点确定为终止节点，将当前选取的起始节点和终止节点确定为一组待处理节点对；

步骤2-202：按照第一跳数计算规则，计算所述待处理节点对之间所有路径的跳数，将跳数最少的路径确定为第一路径；

步骤2-203：将所述第一路径中途径的物理网络节点，确定为偏离节点；

步骤2-204：按照第二跳数计算规则，计算每个偏离节点与终止节点之间所有路径的跳数，将每个偏离节点与终止节点之间跳数最少的路径确定为第二路径；

步骤2-205：将所述第一路径分别与每个所述第二路径拼接，以得到第一候选路径集合，其中，所述第一候选路径集合中包括第一候选路径；

步骤2-206：按照跳数由少到多的顺序，对所述第一候选路径集合中的路径进行排序；

步骤2-207：将所述第一路径和排序后的第一候选路径集合中的前k-1条路径，确定为当前选取的待处理节点对对应的前k条最短路径；

步骤2-208：判断是否已获得所述当前选取的待处理节点对对应的所述前k条最短路径；

步骤2-209：当已获得当前选取的待处理节点对对应的所述前k条最短路径时，继续执行步骤2-210；或者，当未获得当前选取的待处理节点对对应的前k条最短路径时，重复执行步骤2-203至步骤2-209；

步骤2-210：判断是否已获得所述物理网络节点中所有待处理节点对对应的前k条最短路径；

步骤2-211：当已获得所有待处理节点对对应的前k条最短路径时，继续执行步骤3；

或者，当未获得所有待处理节点对对应的前k条最短路径时，在所述物理网络节点的未处理节点对中，继续随机选取一个节点对，其中，将选取的所述节点对中的一个节点确定为新的起始节点，将选取的所述节点对中的另一个节点确定为新的终止节点，将当前选取的新的起始节点和新的终止节点确定为新的一组待处理节点，重复执行步骤2-202至步骤2-211。

4.根据权利要求1所述的方法，其特征在于，所述步骤3包括：

步骤3-1：遍历所有用户业务请求信息，分析所述用户业务请求信息中每个用户业务请求的VNF对应的依赖性信息；

步骤3-2：根据所述依赖性信息，对所有用户业务请求信息进行排序，其中，所述依赖性越高，排序越靠前。

5.根据权利要求2所述的方法，其特征在于，所述用户业务请求信息中包括业务请求节点，所述业务请求节点包括业务请求源节点和业务请求目的节点，所述步骤4包括：

步骤4-1：在物理网络节点中每两节点之间的前k条最短路径中，确定所述业务请求源节点和业务请求目的节点之间的前k条最短路径；

步骤4-2：将所述业务请求源节点和所述业务请求目的节点之间的前k条最短路径，确定为第二候选路径集合；

步骤4-3：分别计算第二候选路径集合中的路径上，所述已有的VNF集合与所述用户业务请求的VNF集合的交集；

步骤4-4：在所有所述交集中，确定最大的交集；

步骤4-5：将所述最大交集对应的路径确定为目标最短路径；

步骤4-6：将所述目标最短路径确定为所述待处理业务对应的业务部署路径。

6.根据权利要求1所述的方法，其特征在于，所述步骤6包括：

步骤6-1：从所述用户业务请求的VNF集合中随机选取一个无依赖性VNF；

步骤6-2：根据预设映射规则，对选取的无依赖性VNF进行第二映射，以得到第三映射结果，将所述第三映射结果确定为一个第二映射策略；

步骤6-4：在所述用户业务请求的VNF集合中，分析无依赖性VNF的数量；其中，当该数量大于0时，则重复执行步骤6-1至步骤6-4；或者，当该数量等于0时，则执行步骤6-5；

步骤6-5：将基于所有无依赖性VNF得到的第二映射策略，确定为第二映射策略集合。

7.根据权利要求1所述的方法，其特征在于，所述用户业务请求信息中包括待映射的虚拟链路集合，所述步骤7包括：

步骤7-1：从所述待映射的虚拟链路集合中随机选取一条虚拟链路；

步骤7-2：基于所述第一映射策略集合和所述第二映射策略集合，分析当前选取的虚拟链路两端的用户业务请求的VNF的映射位置；其中，当所述映射位置在同一个节点上时，确定当前选取的虚拟链路不需要映射，执行步骤7-8；或者，当所述映射位置不在同一节点上时，确定当前选取的虚拟链路需要映射，执行步骤7-3至步骤7-8；

步骤7-3：分析当前选取的虚拟链路的次序；其中，在当前选取的虚拟链路为第一条虚拟链路时，则从所述用户业务请求信息中获取当前选取的虚拟链路所需的频隙数；或者，在当前选取的虚拟链路不是第一条虚拟链路时，按照预设频隙数计算规则，计算得到当前选取的虚拟链路所需的频隙数；

步骤7-4：当前选取的虚拟链路两端的业务请求VNF映射在的两节点间的前k条最短路径作为第二候选路径集合；

步骤7-5：按照预设命中规则，分别在所述第二候选路径集合中的每条候选路径上为当前选取的虚拟链路分配频隙，得到k个路由和频谱分配方案；

步骤7-6：在所述k个路由和频谱分配方案中，选取使最大频隙号增加量最少的一个目标路由和频谱分配方案；

步骤7-7：根据所述目标路由和频谱分配方案，映射当前选取的虚拟链路；

步骤7-8：判断所述待映射的虚拟链路集合中所有待映射的虚拟链路是否映射完成；其中，当映射全部完成时，确定SFC映射完成；或者，当映射未全部完成时，重复执行步骤7-1至步骤7-8。

8.根据权利要求7所述的方法，其特征在于，所述用户业务请求信息中还包括每个用户业务请求的VNF对应的资源改变矩阵，所述资源改变矩阵中包括带宽改变因子和节点改变因子，所述按照预设频隙数计算规则，计算当前选取的虚拟链路所需的频隙数，包括：

步骤S11：在当前选取的虚拟链路起始端的用户业务请求信息中，确定带宽改变因子；

步骤S12：将上一条选取的虚拟链路所需的频隙数与所述带宽改变因子相乘，以计算得到当前选取的虚拟链路所需的频隙数。

Images