一种两阶段的虚拟网络功能转发图设计方法

摘要

本发明公开了一种两阶段的虚拟网络功能转发图设计方法，同时考虑到网络服务请求中的部分VNF之间存在依赖关系，且不同VNF工作特性引起的流量改变率存在差异，将VNF‑FG设计分为两个阶段。第一阶段设计单条SFC结构，最小化逻辑链路带宽总消耗；第二阶段整合多条SFC，减少VNF节点数目。在映射工作中，每个逻辑链路需要映射到一条或多条底层物理链路上，并分配带宽资源；VNF节点需要映射到底层物理服务器上，并且每个VNF节点需要运行在实例化的虚拟机中。因此在VNF‑FG设计中尽量减少链路带宽消耗以及VNF节点数目，可以在后续映射过程中减少链路映射成本和虚拟机实例化的成本。

权利要求

1.一种两阶段的虚拟网络功能转发图设计方法，其特征在于，包括以下步骤：S1、单条SFC设计：根据网络服务请求中的VNF依赖关系构造VNF依赖关系图，并对VNF依赖关系图进行拓扑排序，将VNF依赖关系图转换为VNF拓扑序列，将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC；

S2、多条SFC整合：对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组，在每组内对SFC进行整合，得到VNF-FG；

所述步骤S1包括以下分步骤：

S11、根据网络服务请求中的VNF依赖关系，构造有向无环的VNF依赖关系图；

S12、在VNF依赖关系图的所有入度为0的节点中选取流量改变率最小的节点放入VNF拓扑序列；

S13、将步骤S12中选择的节点的后继节点的入度减1；

S14、判断VNF依赖关系图中是否还有剩余节点，若是则返回步骤S12，否则进入步骤S15；

S15、将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC；

S16、判断是否还有未进行SFC设计的网络服务请求，若是则返回步骤S11，否则进入步骤S2；

所述步骤S11具体为：将网络服务请求中每个所需的VNF作为VNF依赖关系图中的一个节点，每个依赖关系作为VNF依赖关系图中的一条边，由被依赖项指向依赖项，从而构造有向无环的VNF依赖关系图；

所述步骤S2包括以下分步骤：

S21、对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组；

S22、判断是否还存在未进行SFC整合的组，若是则进入步骤S23，否则结束虚拟网络功能转发图设计；

S23、选取一组SFC，对组内的SFC进行整合，得到该组的VNF-FG，返回步骤S22；

所述步骤S23包括以下分步骤：

S231、选取一组SFC，取出其中VNF节点最多的一条SFC作为初始VNF-FG；

S232、判断该组SFC中是否还存在剩余SFC，若是则进入步骤S233，否则完成该组SFC的整合，返回步骤S22；

S233、取出该组SFC中VNF节点最多的一条SFC作为待整合SFC；

S234、遍历当前VNF-FG的所有路径，并计算各路径与待整合SFC的最长公共子序列Lcs；

S235、选取最长的Lcs记为Lcs_max，将Lcs_max与待整合SFC进行整合，形成新的VNF-FG，返回步骤S232；

所述步骤S235具体为：若待整合SFC中的VNF为Lcs_max中包含的VNF，则待整合SFC与当前VNF-FG共享该VNF；若待整合SFC中的VNF为Lcs_max中不包含的VNF，则在当前VNF-FG中新增该VNF节点并添加链路。

说明书

一种两阶段的虚拟网络功能转发图设计方法

技术领域

[0001] 本发明属于虚拟网络功能技术领域，具体涉及一种两阶段的虚拟网络功能转发图设计方法的设计。

背景技术

[0002] 伴随网络规模的快速膨胀和网络技术的迭代创新，旧有的网络架构日益冗杂僵化。为解决这一难题，人们试图重构现有网络架构，NFV(Network  Function Virtualization，网络功能虚拟化)作为其中的核心技术，受到了通信行业的密切关注。NFV技术将网络功能从专属硬件中抽离出来，解耦传统设备的硬件与软件，比如多媒体缓存、服务质量监控器、视频转码器、网关和各种代理等。NFV通过虚拟化技术把网元功能部署在虚拟机中，虚拟资源层将网元功能与底层资源分隔开，上层的网元功能是无法感知底层硬件物理资源的，而运营商只需管理和维护底层的硬件物理资源。

[0003] 现有的运营商网络中，端到端业务传递的报文需要按照某个特定的顺序，经历若干个功能模块节点，SFC(Service Function Chain，服务功能链)的概念就应运而生了。SFC是一个包含网络功能的有序集合，将数据流按照事先规定好的分类规则和策略进行一连串的网络功能处理。SFC作为一种网络服务的提供方式，在NFV环境下得到广泛应用，用软件编程的方式来实现以往用硬件来实现的网络功能，即VNF(Virtualized Network Function，虚拟网络功能)，具有动态创建与删除，灵活性高并且可扩展的特性。SFC在逻辑上表示了数据流所需经过的VNF种类以及次序。VNF-FG(VNF Forwarding Graph，虚拟网络功能转发图)也是用于表征VNF连接关系和流量流向的逻辑拓扑图，它可以包含多个SFC流，提供多个服务。

[0004] VNF-FG的结构决定了服务的具体提供方式(VNF处理的前后顺序，VNF的连接关系)。VNF-FG具有源目端系统，这里的端系统可能是一个功能实体，也可能是一个设备端口，比如隧道端点、虚拟网卡等，表明了网络流量在底层网络中的物理源目位置。

[0005] 在底层网络上部署用户的网络服务请求，进行资源分配，可以拆分为以下四个步骤：

[0006] (1)用户向服务提供商请求网络功能，该请求可以同时包含功能性的需求以及非功能性的需求，功能性的需求指具体的网络功能，比如深度报文检测(Deep Packet Inspection，DPI)、防火墙(Firewall，FW)等，而非功能性需求通常指的是服务质量(Quality of Service，QoS)。

[0007] (2)服务提供商根据用户的网络服务请求，设计出VNF-FG拓扑结构，其中很重要的一点是为每个功能性的需求计算其所需的资源，以满足非功能性的要求。

[0008] (3)服务提供商制定部署方案，将VNF-FG中的VNF和虚拟链路映射到NFVI(NFV Infrastructure，网络功能虚拟化基础设施)上，保证功能性需求与非功能性需求同时得到满足。

[0009] (4)根据部署方案，服务提供商在物理宿主机上分配资源，启动虚拟机并部署VNF软件，最后通过虚拟链路来连接这些虚拟机。

[0010] 在上述服务部署的四个步骤中，第二步的结果是作为第三步的输入，并且这两步很大程度上影响了整个服务的QoS以及总成本。目前网络服务部署中主要研究的是第三步的VNF-FG映射问题，而第二步的VNF-FG设计工作研究是比较缺失的。

[0011] VNF-FG包含了逻辑上的VNF节点及其连接关系，并指定了其中各个流历经VNF的次序。VNF-FG设计指的是根据用户的网络服务请求，设计出满足VNF种类需求，且满足VNF依赖关系的拓扑结构，VNF-FG是作为映射阶段的输入参数。

[0012] VNF依赖关系指的是，若VNF2依赖于VNF1，那么用户流量必须先经过VNF1的处理后才能接受VNF2的处理(比如解码器一定要处于编码器之后)。

[0013] VNF的流量改变率指的是，经过VNF处理后离开的流速率与进入该VNF的流速率之比。VNF会影响经过其处理的流量出速率(比如防火墙会减少数据量，而VPN代理会给数据报文新增IPsec头部开销引起数据量增加)，出边的链路带宽需求会发生变化，因此在VNF-FG设计中使逻辑链路的带宽需求小，可以减少链路映射瓶颈和节省链路映射成本。

[0014] VNF-FG中的VNF节点最终是要映射到物理节点，VNF软件运行在虚拟机上以提供服务，实例化虚拟机以及虚拟机运行本身存在一定成本，因此减少VNF-FG中节点数目可以减少实例化虚拟机的数目，以达到降低运营成本的目的。

发明内容

[0015] 本发明的目的提出一种两阶段的虚拟网络功能转发图设计方法，设计出在离线场景下最小化逻辑链路带宽总消耗和VNF节点数目的虚拟网络功能转发图。

[0016] 本发明的技术方案为：一种两阶段的虚拟网络功能转发图设计方法，包括以下步骤：

[0017] S1、单条SFC设计：根据网络服务请求中的VNF依赖关系构造VNF依赖关系图，并对VNF依赖关系图进行拓扑排序，将VNF依赖关系图转换为VNF拓扑序列，将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC。

[0018] 步骤S1包括以下分步骤：

[0019] S11、根据网络服务请求中的VNF依赖关系，构造有向无环的VNF依赖关系图。

[0020] 将网络服务请求中每个所需的VNF作为VNF依赖关系图中的一个节点，每个依赖关系作为VNF依赖关系图中的一条边，由被依赖项指向依赖项，从而构造有向无环的VNF依赖关系图。

[0021] S12、在VNF依赖关系图的所有入度为0的节点中选取流量改变率最小的节点放入VNF拓扑序列。

[0022] S13、将步骤S12中选择的节点的后继节点的入度减1。

[0023] S14、判断VNF依赖关系图中是否还有剩余节点，若是则返回步骤S12，否则进入步骤S15。

[0024] S15、将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC；

[0025] S16、判断是否还有未进行SFC设计的网络服务请求，若是则返回步骤S11，否则进入步骤S2。

[0026] S2、多条SFC整合：对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组，在每组内对SFC进行整合，得到VNF-FG。

[0027] 步骤S2包括以下分步骤：

[0028] S21、对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组。

[0029] S22、判断是否还存在未进行SFC整合的组，若是则进入步骤S23，否则结束虚拟网络功能转发图设计。

[0030] S23、选取一组SFC，对组内的SFC进行整合，得到该组的VNF-FG，返回步骤S22。

[0031] 步骤S23包括以下分步骤：

[0032] S231、选取一组SFC，取出其中VNF节点最多的一条SFC作为初始VNF-FG。

[0033] S232、判断该组SFC中是否还存在剩余SFC，若是则进入步骤S233，否则完成该组SFC的整合，返回步骤S22。

[0034] S233、取出该组SFC中VNF节点最多的一条SFC作为待整合SFC。

[0035] S234、遍历当前VNF-FG的所有路径，并计算各路径与待整合SFC的最长公共子序列Lcs。

[0036] S235、选取最长的Lcs记为Lcs_max，将Lcs_max与待整合SFC进行整合，形成新的VNF-FG，返回步骤S232。

[0037] 若待整合SFC中的VNF为Lcs_max中包含的VNF，则待整合SFC与当前VNF-FG共享该VNF；若待整合SFC中的VNF为Lcs_max中不包含的VNF，则在当前VNF-FG中新增该VNF节点并添加链路。

[0038] 本发明的有益效果是：

[0039] (1)本发明弥补了当前服务部署和资源分配工作中VNF-FG设计环节的缺失，提供了离线场景下根据用户的网络服务请求计算出VNF-FG结构(代表了网络服务的具体提供方式)的完整流程。

[0040] (2)考虑因素全面：本发明考虑了网络服务请求中的VNF存在依赖关系，且VNF的流量改变率存在差异，单条SFC设计阶段在保证依赖关系的前提下使SFC中逻辑链路带宽总消耗最小；考虑到SFC的端系统在底层物理位置确定，在SFC整合阶段，将拥有相同源目端系统的SFC分为一组，在组内进行整合，可以防止因不同源目端系统的SFC整合，导致后续映射工作中端系统相隔较远的多条SFC需要共用一个VNF实例而引起额外的链路消耗。同时保证SFC整合形成的VNF-FG中不存在环，也可以避免映射过程中的流量产生回路引起的链路消耗。

[0041] (3)可降低映射成本：本发明在对单条SFC设计时保证了逻辑链路带宽总消耗最小，并且在多条SFC整合阶段尽可能聚合相同VNF，可以降低链路映射成本与虚拟机实例化成本。

附图说明

[0042] 图1所示为本发明实施例提供的一种两阶段的虚拟网络功能转发图设计方法流程图。

[0043] 图2所示为本发明实施例提供的根据网络服务请求构造依赖关系图的示意图。

[0044] 图3所示为本发明实施例提供的步骤S23的分步骤流程图。

[0045] 图4所示为本发明实施例提供的VNF-FG路径示意图。

[0046] 图5所示为本发明实施例提供的待整合SFC示意图。

[0047] 图6所示为本发明实施例提供的SFC聚合后的新VNF-FG示意图。

具体实施方式

[0048] 现在将参考附图来详细描述本发明的示例性实施方式。应当理解，附图中示出和描述的实施方式仅仅是示例性的，意在阐释本发明的原理和精神，而并非限制本发明的范围。

[0049] 本发明实施例提供了一种两阶段的虚拟网络功能转发图设计方法，如图1所示，包括以下步骤S1-S2：

[0050] S1、单条SFC设计：考虑到部分VNF存在依赖关系以及VNF流量改变率这两个因素，本发明实施例中，根据网络服务请求中的VNF依赖关系构造VNF依赖关系图，并对VNF依赖关系图进行拓扑排序，将VNF依赖关系图转换为VNF拓扑序列，将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC。

[0051] 步骤S1包括以下分步骤S11-S16：

[0052] S11、根据网络服务请求中的VNF依赖关系，构造有向无环的VNF依赖关系图。

[0053] 网络服务请求中会包含此次请求所需的VNF种类，以及VNF之间存在的依赖关系，如图2所示给出了一个网络服务请求的示例，将网络服务请求中每个所需的VNF作为VNF依赖关系图中的一个节点，每个依赖关系作为VNF依赖关系图中的一条边，由被依赖项指向依赖项(例如图2中VNF3依赖于VNF1，则添加一条从VNF1指向VNF3的边)，从而构造VNF依赖关系图。由于网络服务请求不存在循环依赖，即不存在比如A依赖B，B依赖C，C依赖A这种情况，因此构造出的VNF依赖关系图必定是无环的。

[0054] S12、在VNF依赖关系图的所有入度为0的节点中选取流量改变率最小的节点放入VNF拓扑序列。

[0055] S13、将步骤S12中选择的节点的后继节点的入度减1。

[0056] S14、判断VNF依赖关系图中是否还有剩余节点，若是则返回步骤S12，否则进入步骤S15。

[0057] S15、将VNF拓扑序列作为SFC中VNF的次序，设计出单条SFC。

[0058] 步骤S12-S15即为对步骤S11构造的VNF依赖关系图进行拓扑排序操作。为了保证VNF的依赖关系，使被依赖项处于依赖项的前面，本发明采用拓扑排序的方式，对步骤S11构造的VNF依赖关系图进行拓扑排序，每次进入拓扑序列的是VNF依赖关系图中入度为0的点，弹出序列头部的元素后，后继节点的入度减1，若有新的入度为0的节点产生，则放入拓扑序列中，这样保证了被依赖项始终处于依赖项的前面。

[0059] 拓扑排序可能有多种满足依赖关系的序列结果，为了得到逻辑链路带宽总消耗Btotal最小的SFC结构，必须使流量改变率最小的VNF尽量放置在SFC中靠前的位置。本发明实施例中逻辑链路带宽总消耗Btotal定义如下：

[0060]

[0061] 其中Es表示SFC中逻辑链路集合，e为SFC中的逻辑链路，B(e)表示逻辑链路e的带宽需求。因此在对步骤S11构造的VNF依赖关系图进行拓扑排序时，每次从入度为0的节点队列里弹出流量改变率最小的VNF放入拓扑排序序列。这样在保证依赖关系满足的前提下，尽可能使流量改变率最小的VNF放置在SFC中靠前的位置。

[0062] S16、判断是否还有未进行SFC设计的网络服务请求，若是则返回步骤S11，对下一个网络服务请求进行SFC设计，否则说明已完成对所有网络服务请求进行SFC设计，进入步骤S2。

[0063] S2、多条SFC整合：对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组，在每组内对SFC进行整合，得到无环的VNF-FG，保证映射阶段不会产生回路，导致额外的链路消耗。

[0064] 步骤S2包括以下分步骤S21-S23：

[0065] S21、对所有SFC进行分组，将拥有相同源目端系统的SFC划分为一组。以相同源目端系统分组是为了避免因不同源目端系统的SFC整合，导致后续映射工作中端系统相隔较远的多条SFC需要共用一个VNF实例而引起额外的链路消耗。

[0066] S22、判断是否还存在未进行SFC整合的组，若是则进入步骤S23，否则结束虚拟网络功能转发图设计。

[0067] S23、选取一组SFC，对组内的SFC进行整合，得到该组的VNF-FG，返回步骤S22。

[0068] 将SFC整合至VNF-FG中，需要解决的问题是：待整合的SFC中哪几个VNF节点分别与VNF-FG中的哪几个VNF节点聚合。为了聚合更多数目的VNF节点，需要遍历VNF-FG中源节点到目的节点之间的所有路径，每条路径上的VNF依次构成一个序列L1，待整合的SFC中VNF依次构成一个序列L2，计算L1与L2的最长公共子序列Lcs。VNF-FG中每个路径都与待整合的SFC有一个Lcs，本发明实施例中，选取其中最长的Lcs作为整合方案Lcs_max。

[0069] 如图3所示，步骤S23包括以下分步骤S231-S235：

[0070] S231、选取一组SFC，取出其中VNF节点最多的一条SFC作为初始VNF-FG。

[0071] S232、判断该组SFC中是否还存在剩余SFC，若是则进入步骤S233，否则完成该组SFC的整合，返回步骤S22。

[0072] S233、取出该组SFC中VNF节点最多的一条SFC作为待整合SFC。

[0073] S234、遍历当前VNF-FG的所有路径，并计算各路径与待整合SFC的最长公共子序列Lcs。

[0074] VNF-FG中，从源节点到目的节点可能存在不止一条路径。本发明实施例中，如图4所示的VNF-FG中，存在3条路径，分别为L1：{VNF1，VNF2，VNF4，VNF7}，L2：{VNF1，VNF2，VNF5，VNF7}，L3:{VNF1，VNF3，VNF6，VNF7}。为了尽可能多的聚合相同VNF以减少节点数目，则需要遍历VNF-FG中所有的路径，计算待整合SFC的VNF序列与路径的VNF序列的最长公共子序列Lcs。如图5所示的SFC：{VNF1，VNF3，VNF6，VNF8}，它与图4中的VNF-FG中的三条路径的最长公共子序列分别为Lcs1：{VNF1}，Lcs2：{VNF1}，Lcs3：{VNF1，VNF3，VNF6}。

[0075] S235、选取最长的Lcs记为Lcs_max，将Lcs_max与待整合SFC进行整合，形成新的VNF-FG，返回步骤S232。

[0076] 从步骤S234中的各个Lcs中选出最长(即包含的节点数最多的)的Lcs，记为Lcs_max，将SFC按照Lcs_max中的元素整合至对应的路径中。比如，如图5所示的SFC与图4所示的VNF-FG的Lcs_max为Lcs3：{VNF1，VNF3，VNF6}，因此将SFC在路径L3上按照Lcs3中的节点进行整合。整合过程为，Lcs3中出现的VNF，则待整合的SFC与原VNF-FG共享该VNF；若待整合的SFC中有Lcs3不包含的VNF，则在VNF-FG中新增该VNF节点并添加链路。整合结果如图6所示，待整合的SFC共享原VNF-FG中L3上的VNF1，VNF3和VNF6，新增了VNF8节点，以及VNF6与VNF8之间、VNF8与目的节点之间的两条链路。

[0077] 对组内每条SFC按照步骤S233-S235的步骤进行整合，每次整合形成一个新的VNF-FG，并且作为下一个SFC整合时的VNF-FG。当所有SFC整合完成时，最终形成的VNF-FG即为按组划分设计的VNF-FG。

[0078] ETSI的NFV架构中，MANO(Management and Orchestration，管理和编排)由VIM(Virtualized Infrastructure Manager，虚拟化基础设施管理)、VNFM(VNF Manager，虚拟网络功能管理器)和NFVO(Network Function Virtualization Orchestration，网络功能虚拟化编排器)组成，VIM用于管理虚拟资源，VNFM用于管理网络功能，NFVO用于网络服务的生命周期管理和全局跨域资源调度。本发明实施例可以部署在NFV环境下MANO架构中的NFVO，通过VNF-FG设计来确定网络服务的具体提供方式(确定VNF个数，连接关系)。

[0079] 目前，业界的VIM多基于OpenStack进行产品化。因此可以使用OpenStack作为NFV云平台的VIM模块，Tacker项目作为VNFM，在此基础上进行NFVO模块的开发，网络服务提供商可以将本发明实施例所提出的两阶段的虚拟网络功能转发图设计方法部署在MANO架构里的NFVO中，NFVO在制定好VNF-FG后，将其保存为VNF-FG描述符(VNF-FG Descriptor，VNF-FGD)，用于后续网络服务编排及映射工作。

[0080] 针对离线场景下，当有多个网络服务请求到来时，NFVO调用部署在其中的虚拟网络功能转发图映射方法，分别为每个请求设计出相应的SFC结构，此为第一阶段的工作；然后以相同源目端系统对SFC分组后进行整合，每组构造一个VNF-FG，此为第二阶段的工作。最后将设计出的VNF-FG保存为VNF-FGD模板，供映射阶段使用。

[0081] 本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。