2.2 服务功能链并行化加速

2.2.1 传统串行组链模式的弊端

在传统的SFC研究中，每个NF需严格按照顺序部署和执行，且必须按照预定义的顺序引导流量通过每个NF，这种模式也叫SFC串行处理模式。然而，传统的SFC串行处理模式使得服务的端到端时延随着SFC长度的增加而线性增加，这将对未来时延敏感型应用有重大影响。5G的一个关键应用场景是降低通信时延，从而提供如远程手术、车辆对车辆通信或触觉互联网等低时延甚至超低时延服务 ^[21] 。为了应对这种趋势，研究者提出了SFC并行处理的思想 ^[22，23] ，NF并行处理的基本前提是保证NF并行处理后SFC处理结果的正确性，通过分析NF的操作类型，可将互不影响的两个NF并行处理，如将两个只读取数据的NF并行处理并不影响最终的服务结果，以此减少SFC的长度并降低SFC的时延。

2.2.2 网络功能操作类型识别

在一条SFC中，存在执行时互不影响的VNF。因此，考虑VNF之间的依赖性是寻求并行处理的关键。VNF之间的依赖性可基于NF的操作类型进行分析，为了确定VNF之间是否存在依赖关系，首先要研究NF的操作类型。NF常见的操作类型有读、写数据包头或有效负载，添加或删除包头域，丢弃数据包等。前、后有两个网络功能NF ₁ 和NF ₂ 。如果两个NF都只对数据进行读操作，则可将这两个NF并行处理；但是如果NF ₁ 改写数据，NF ₂ 再读取该数据，为了保证NF ₂ 读取结果的准确性 ^[7] ，这两个NF必须以串行的方式组链。因此，NF操作类型是判断NF是否可以并行处理的重要依据。常见的网络功能对数据包的操作类型如表2-1所示。

表2-2为两个不同操作类型的NF是否可以并行处理对照表。本节基于NF的操作类型及依赖性对照表分析两个VNF是否可以并行处理，将串行SFC并行处理后形成具有串行和并行处理的混合服务图（PSG），如图2-1所示，在PSG构建完成后，为了统一描述，可以将其看作不同的子图相连，每个子图中具有不同数量的VNF，将单个串行的VNF看成并行子图的特殊情况（PN=1）。VNF的并行性具有传递性，如果两两相邻的 y 个VNF都可并行处理，则可将 y 个VNF放置到同一个子图，即PN= y 。

2.2.3 网络功能并行化组链

为了最大限度地降低SFC的时延，本节提出了一种最小化总时延的PSFC部署方案。在本节的方案中，如果物理节点有足够的容量，则将整条PSFC部署在同一个物理节点中。当服务节点资源有限而不能将所有VNF放在同一服务节点中时，则将VNF放置在尽可能少的服务节点中。

在SFC并行处理架构中，为了并行化处理数据包，需要引入两个额外的功能：①数据包复制功能；②数据包合并功能，如图2-1所示。为了进行高效的并行处理，这些功能必须嵌入交换节点中，当数据包到达时，数据包复制功能复制数据包并将其发送到两个并行处理的VNF，VNF完成数据包处理后，通过合并功能将数据包智能地合并到一起。尽管VNF并行处理可以降低时延，但是数据包复制和合并操作将产生额外的资源开销与时延开销。

网络中TCP数据包大小为64～1500 B。研究发现，数据包复制和合并带来的额外资源开销与数据包大小和并行度存在一定的关系 ^[24] ，额外资源开销 r =64 × （ d -1）/ s ，其中， d 为并行度（并行支链的个数）， s 为数据包大小。在额外的时延方面，在并行度为2～5的情况下，数据包复制和合并将带来平均15μs的时延。在更长的链和更复杂的NF中（如VPN），复制和合并带来的时延开销将进一步降低。

为了支持SFC并行化处理，本节提出了一个VNF并行化处理的架构，如图2-2所示。其中，NF依赖性分析模块可用于分析NF之间的依赖关系，并将SFC转为并行服务图；编排器负责将VNF部署在拥有不同资源的物理节点中，并通过SDN控制器实现智能的流量路由策略。数据包复制和合并功能将嵌入在VNF之前与之后的交换机中，以实现流量的分发和合并。

2.2.4 服务功能链并行度优化

1.PSFC并行度优化

SFC中VNF并行处理的之前应先判断NF的操作类型，给定一对VNF，如果两个VNF之间不存在依赖关系，则可以并行执行它们。例如，如果两个VNF都简单地执行读操作，则可以将它们并行处理。如果其中一个VNF执行读操作而另一个执行写操作，那么当且仅当它们不对同一字段进行操作时，才可以并行处理它们。同样地，如果两者都执行写操作（包括在数据包中插入/删除标头/位），那么无法并行执行它们，因为修改的数据部分（标头或有效负载）可能重叠。鉴于依赖性分析已经得到了较充分研究 ^[28-30] ，这部分内容将不作为本节研究重点。

在SFC并行处理中，不同并行支链之间可能存在巨大的时延差异，从而导致等待时延和数据包堆积现象，而且尽可能多地并行VNF可能不会获得更大的收益，反而浪费可用的资源。在图2-3中，经过依赖性分析后，可以并行执行VNF ₂ 、VNF ₃ 和VNF ₄ 。由于这些VNF的处理时延不同，因此总处理时延取决于最长的VNF处理时延加上并行的时延开销。在图2-3（a）中，VNF ₂ 和VNF ₃ 的处理时延明显比VNF ₄ 短，当VNF ₄ 处理完到达合并节点时，VNF ₂ 和VNF ₃ 可能已经处理了几个数据包了，这将造成数据包堆积现象；另外，在并行处理之前需要将数据包复制后并行发送到各个并行支链，数据包的复制和合并将带来不可忽略的资源消耗与时延。所以，在优化SFC的处理机制时，不仅要探索VNF之间并行的可能性，还需要联合VNF执行时延优化PSFC并行度，协同设计并行支链的路由规则，最大限度地降低网络时延和减少资源消耗。相反，如图2-3（b）所示，由于VNF ₂ 、VNF ₃ 与VNF ₄ 处理时延相差较大，因此可以将VNF ₂ 与VNF ₃ 串行处理，将VNF ₄ 单独并行处理，以缩减两条并行支链的时延差异，减少链路的占用和额外资源消耗，同时降低时延，其处理结果与图2-3（a）一样。

给定VNF之间的依赖关系，可将串行SFC转换为PSG。如图2-3所示，图2-3（a）为并行度为3的PSG，图2-3（b）为并行度为2的PSG，其中，并行度定义为PSG中并行支链的个数。研究发现，并行度优化问题可以转化为在PSG中将关键路径（Critical Path）大小作为容器容量（ V ）的装箱（Bin Packing，BP） ^[25] 问题，关键路径定义为处理时延最长的支链，直观地说，两个可并行VNF支链处理时延要尽可能接近关键路径的处理时延。为了构建一个满足优化目标的PSG，其优化方法可分为两个步骤。

第一步：找出PSG中决定总时延大小的关键路径及其时延，如图2-3（a）中VNF ₁ -VNF ₄ -VNF ₅ 。

第二步：根据关键路径的时延和并行支链处理时延的差异，消除不必要的并行性，如图2-3（b）所示。

2.数学描述

假设 S 表示网络服务集，| S |表示服务集 S 的数量，[1，| S |]表示1～| S |的整数集合， S _i 表示对应网络服务集中第 i 条SFC，其中 i∈ [1，| S |]。每条 S _i 对应着一系列需要按规定顺序执行的VNF，假设 S _i 中含有| F |个VNF， F 表示VNF的集合， f _ij 表示 S _i 所对应的第 j 个VNF， i∈ [1，| S |]， j∈ [1，| F |]。网络拓扑由 G =（ N ， L ）表示， N 和 L 分别表示节点集和链路集，此外，不论处理VNF虚拟机是位于服务器还是交换机，都称其为物理节点。假设 f _ij 部署到物理节点 k∈N ，则 X _ijk =1，否则为0。VNF f _ij 的处理时延表示为 φ _ij ，经过并行化分析后生成PSG，如果并行支链 P _x 存在，则 P _x =1，否则为0，PSG一共含有Pe= ∑P _x 条并行支链，每条并行支链 P _x 中含有 M 个VNF，如果 f _ij 属于支链 P _x ，则 ，否则为0。假设VNF f _ij 和 f _ij′ 在物理拓扑之间的路由路径为 l （ k ， k′ ），则 f _ij 和 f _ij′ 之间的链路时延为 D _{l （ k ， k′ ）} ， f _ij 的资源需求为 r _ij ，物理节点 n∈N 的资源容量为 C _n 。如果并行支链之间的时延相差太大，将导致数据包堆积并产生等待时延，PSFC中不同的并行支链之间的时延差异表示为：

假设SFC的数据传输速率为 υ _i ，则数据包堆积量为 E = υ _i ×Δ t 。根据Sun ^[7] 等人的研究，由并行处理的数据包复制和合并带来的额外资源消耗为 C =64 × （Pe-1）/ b ，其中，Pe为并行度， b 为数据包大小。数据包复制和合并带来的额外时延大约为30 ms/Gbit/s，因此，总的额外时延可以表示为 Δd =30 υ _i 。SFC的总时延可以表示为：

本节的目标是最小化总的SFC时延、由数据包复制和合并带来的额外资源消耗，以及数据包堆积量。因此，目标函数 O 可表示为：

约束条件（2-4）使每个VNF只能属于一条并行支链，约束条件（2-5）使每个VNF只能部署在一个物理节点上，约束条件（2-6）限制了VNF必须部署在满足其资源需求的物理节点上。

如前文所述，并行度优化问题可以转化为装箱（BP） ^[25] 问题求解。BP问题的定义为：给定一组bin={ b ₁ ， b ₂ ，…}，bin大小为 υ ，给定容积为 V 的容器，要求找出整数个bin使得填充箱子后剩余的体积最小，该问题是NP-hard问题。并行支链的时延协同问题就是并行VNF（bins）不存在先后关系的BP问题，因此该问题可以转化为bin的大小与VNF的处理时延匹配、容积 V 与PSG中关键路径时延大小匹配的问题，其中，决定PSG总时延大小的路径定义为关键路径。为了解决该问题，本节提出了基于BP问题的并行度优化算法，通过两个步骤实现时延感知的PSFC优化。

3.基于BP问题的并行度优化算法

为解决由不必要的并行度引起的一系列问题，本节提出了一种时延平衡的并行度优化策略。考虑SFC创建后每个VNF的处理时延是固定的，研究发现将处理时延相对较短的几个VNF适当地链接到相同的支链中可以带来更好的性能。这不仅改善了数据包堆积现象和等待时延问题，而且降低了PSFC并行度，降低了不必要数据包复制和合并带来的额外开销，同时保证了PSFC性能。

假设经过并行性分析后生成并行服务图PSG={ f ₁ ，…（ f _i … f _j ），…}，其中，小括号内（ f _i … f _j ）表示可并行的VNF，其余为串行的VNF。定义并行的VNF集合为 M _ij ，即 M _ij =（ f _i … f _j ），定义接近变量 ρ 。首先找出 M _ij 中决定并行支链时延的VNF f _c （算法2-1中第4行）， M _ij 中如果存在 y 个VNF处理时延之和与 f _c 相近（＜ ρ ）（算法2-1中第5行），则将这 y 个VNF放置在同一条并行支链中（算法2-1中第6行）。PSFC优化前并行度Pe= j-i +1，如果 y 个VNF被放在同一条并行支链中，则Pe= j-i +1 -y 。本节对BP算法进行适当改进，使其适应本节提到的场景，具体如算法2-1所示。 PrHdyUBxhqC4LQ+ZttckHYmXgyUUK6zQkTjsIOC3aXGaNJnfi1zCKZHe5N4MJiLq