2. 中国科学院大学 深圳先进技术学院, 深圳 518055;
3. 中国科学院大学, 北京 100049;
4. 中国科学院 计算技术研究所, 北京 100190
为了优化基于网络功能虚拟化（NFV）的安全服务功能链（NS-SFC）的性能，提出了基于TCP Offloading的虚拟网络安全服务功能链（SFC）—TOChain，解决了重复收发网络包的问题；提出了面向吞吐率保证的强同步周期性CPU调度算法，在虚拟网络功能（VNF）与用户虚拟机混合部署的场景下实现网络吞吐率性能保证与调度公平性.基于KVM虚拟化平台实现了原型系统，并对由防火墙、入侵防御系统和应用层防火墙3种VNF构成的NS-SFC进行了不同负载下的性能测试.结果显示，与传统SFC相比，TOChain能够以较低的CPU资源占用率达到更高、更稳定的网络性能；在轻度和中度网络流量负载下，采用强同步周期性调度算法都能够达到与所设定的吞吐率极为接近的网络性能，即便是在重度负载下，也能实现用户虚拟机间的调度公平性.
2. Shenzhen College of Advanced Technology, University of Chinese Academy of Sciences, Shenzhen 518055, China;
3. University of Chinese Academy of Sciences, Beijing 100049, China;
4. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
Performance problem is a big challenge for network function virtualization (NFV) based security service function chain (NS-SFC). To solve this problem, a TCP offloading based SFC for virtual network security, called TOChain was proposed, which avoids reduplicative packet processing over TCP/IP stack and virtual network interfaces. And furthermore, a throughput guarantee oriented strongly synchronized periodical CPU scheduling algorithm for TOChain was presented. Finally, the prototype based on KVM and the performance of the prototype with three types of virtualized network function (VNF), including iptables, Snort and FreeWAF was developed and evaluated. It is shown that TOChain achieves a significantly higher performance with a lower CPU utilization compared to the NFV based traditional SFC architecture. With strongly synchronized periodical algorithm, the network performance achieved is very close to the configured throughput under the light and medium traffic load. Moreover, even under the heavy load, it also ensure fairness between virtual machines.
网络功能虚拟化(NFV, network function virtualization)是虚拟网络安全的发展方向[1].近年来，一些研究工作围绕着网络安全设备的虚拟化展开，如防火墙虚拟化[2-4]、DDoS攻击防御系统虚拟化[5-7]等，验证了网络安全服务虚拟化的可行性和架构灵活性.目前，性能问题是NFV面临的重要挑战[8-10]，尤其是在由多种虚拟网络功能(VNF, virtualized network function)串接构成的服务功能链(SFC, service function chain)[11]的情况下，网络性能下降更加明显[1].当前NFV性能优化工作大多围绕着提升虚拟机性能而展开，虽然取得了一定的效果，但由于主流虚拟化平台已较为充分地利用硬件虚拟化支持，虚拟机性能提升空间有限.
事实上，从网络安全服务功能链(NS-SFC, network security service function chain)整体的视角来看，在传输每一个网络包时，所有的VNF都要执行如下流程：虚拟网卡收包→网卡驱动收包处理→TCP/IP协议栈解封装→数据处理→TCP/IP协议栈封装→网卡驱动发包处理→虚拟网卡发包.在这个流程中，除了在不同的VNF上进行不同的“数据处理”外，其他处理环节都是重复的，而这些环节往往造成了不可忽视的性能开销.以Snort入侵检测系统为例，42%的处理时间消耗在了网络包捕获和解封装环节[12].此外，这些重复环节会消耗大量的CPU资源，如虚拟网卡功能逻辑完全由宿主机CPU模拟，运行TCP/IP协议栈也会消耗大量的CPU时间片.
基于上述观察，笔者提出了一种基于TCP Offloading的虚拟网络安全SFC—TOChain，旨在消除传统SFC架构下重复的网络包收发处理环节，优化网络性能.
1 相关工作目前，与NFV性能问题相关的研究工作主要包括2个方面：一个是NFV/SFC性能评价与优化；另一个是NFV/SFC调度算法.下面将从这2个方面分别进行介绍.
1.1 NFV/SFC性能评价与优化Hu等[13]对运行在非一致性存储访问(NUMA, non-uniform memory access)架构服务器上VNF的性能开销进行了微体系结构级评测，指出非对称性的Socket间通信开销和Socket内部的多线程资源竞争是导致NFV性能下降的主要原因，为此提出了针对端到端性能保证的、基于动态规划算法的线程与处理器核映射框架. Stezenbach等[14]提出了一种基于inter-event time对比分析的NFV性能评价方法，该方法旨在评价不同虚拟化平台下以及物理机环境下的NFV性能差异.在虚拟机本身的性能优化方面，主要包括CPU调度、内存分配、I/O优化等方面的细粒度调优技术[15].例如，通过将虚拟机CPU核与物理CPU核做“一对一”静态绑定，避免动态调度虚拟CPU过程中产生的上下文切换开销，避免Cache污染和转换检测缓冲区动态刷新开销；通过NUMA感知的内存分配策略避免虚拟机中跨NUMA节点访问内存，降低访存开销；使用支持单根虚拟化的网卡通过VMM Bypass的方式允许虚拟机直接访问硬件网卡，减少虚拟化开销等. Jardin[16]利用数据平面开发套件技术简化网卡驱动程序处理逻辑，采用轮询模式替代中断模式，缩短网络包处理延迟；采用用户态运行的网络协议栈，减少上下文切换开销，提高网络收发性能. Roseboro[17]利用网卡的卸载叠加网络能力，提高虚拟网络的性能，减少物理机的CPU消耗.
1.2 VNF/SFC调度针对网络SFC构建过程中的VNF选择问题，Kim等[18]提出了一种面向服务质量(QoS, quality of service)保证的VNF调度算法，该算法将问题建模为多约束路径选择问题，并通过遗传算法来寻找最优解. Riera等[19]将VNF调度问题建模为柔性作业车间调度问题，以SFC上VNF的总体运行时间最短为目标寻找最优调度方案.该算法仅考虑了VNF的运行时间而没有考虑网络包在链路上的传输时间，此外，对于柔性作业车间调度这一经典组合优化问题，相关研究已证明没有多项式时间的算法，因此，在这种模型下很难满足在线调度的实时性需求. Long等[20]提出了一种基于遗传算法的延迟感知流量调度算法，考虑了VNF的处理时延和链路上的传输延迟，为流量选择延迟最低的VNF转发路径. Zhang等[21]分别针对SFC中的VNF在物理节点中的分布调度和网络请求在VNF服务实例中的调度2个问题进行形式化定义，前者被抽象为装箱问题，后者基于Jackson排队网络进行建模，并针对前者提出了优先级驱动的加权算法来最大化物理节点的资源利用率，针对后者提出了启发式算法以实现网络请求响应延迟的最小化.
1.3 相关研究小结现有的研究工作大多从虚拟机本身进行细粒度的性能调优，性能虽有提升但效果并不十分显著.在VNF/SFC调度方面，目前的算法尚未从SFC的整体角度考虑VNF之间的细粒度协同调度，也没有考虑到VNF与虚拟机混合部署的场景.因此，笔者从NS-SFC的整体结构出发，开展面向网络性能优化的研究.
2 TOChain系统设计与实现 2.1 基于TCP Offloading的网络虚拟化基于TCP Offloading的网络虚拟化架构如图 1所示.将虚拟机的TCP/IP协议栈卸载到宿主机上运行，在宿主机上为每个虚拟机分配一个运行协议栈卸载引擎(TOE, TCP offload engine)的容器，该容器具有独立的网络命名空间和IP地址(即虚拟机的IP地址)，并以桥接模式与物理网卡连接，从而可以与外部通信.虚拟机通过远程过程调用(RPC, remote procedure call)的方式调用TOE以收、发网络包.在虚拟机和TOE之间基于虚拟机间共享内存传递传输层数据包，NS-SFC部署在TOE容器和虚拟机之间，直接对虚拟机间共享内存区中的传输层数据包实施安全检查.为了保持对虚拟机中应用程序的透明性，在虚拟机中以运行时库的形式提供BSD Socket兼容的应用程序编程接口.此外，为了保证数据隔离性，VMM为每对“虚拟机-TOE容器”组合分配独立的虚拟机间共享内存区，并动态授予相应NS-SFC上的VNF以访问权限.
|
图 1 基于TCP Offloading的网络虚拟化示意图 |
TOChain由控制面和数据面两部分组成，如图 2所示.控制面由SFC编排与管理模块和资源调度模块组成，数据面由VNF、虚拟机以及包调度器组成. VNF与被保护的用户虚拟机运行在同一台宿主机上，由SFC编排与管理模块按需动态地构建出NS-SFC.NS-SFC由转发表描述，转发表记录网络包在VNF之间的处理和转发顺序，由SFC编排与管理模块下发和维护.每当VNF完成网络包的处理时，就会向包调度器发送完成“通知”和处理结果(“Allow”或“Deny”).对于“Allow”结果，包调度器则根据转发表通知下一跳VNF或虚拟机/TOE处理该网络包；对于“Deny”结果，包调度器则阻止该网络包向下游传递.此外，一个VNF可以同时属于多个NS-SFC，为不同的用户虚拟机提供服务.
|
图 2 TOChain系统结构 |
在虚拟机间共享内存区中的网络包由2个队列进行管理，分别是输入队列和输出队列.输入队列是指等待或正在被VNF处理的网络包队列，按照到达时间从先到后的顺序进行组织；输出队列是指已由NS-SFC处理完成、等待或正在被虚拟机或TOE接收的网络包，同样地，输出队列中的网络包也是按照到达的先后顺序进行排列.
TOChain中典型的网络包收发流程如下：假设为虚拟机配置了2个NS-SFC(in-sfc与out-sfc)，分别针对输入流量和输出流量进行安全检查.当宿主机物理网卡接收到网络包后，将根据目标IP地址分发到相应的TOE容器.在容器中，经过TCP/IP协议栈处理、逐层解除协议头部封装后，TOE将各层协议头部信息和传输层载荷存储在相应的输入队列中，并通知包调度器进行调度.接下来，在包调度器的调度下由in-sfc上各个VNF依次进行处理后，该网络包被放入输出队列中，由虚拟机接收.类似地，当用户虚拟机发出应用层数据时，先将数据存储在虚拟机间共享内存区中，再由包调度器调度out-sfc上各个VNF按序处理数据，最后提交给TOE完成各层协议头部的封装，并通过物理网卡将网络包发送出去.由上述流程可见，虚拟机与外部网络之间传输的网络包仅需经过一次物理网卡收/发包和协议栈解包/封包处理.
2.3 三级并行设计TOChain采用了三级并行设计，以充分利用宿主机多处理器架构，以提升NS-SFC的性能，具体包括串行部署VNF间的流水线并行、并行部署VNF间的数据并行和同一个VNF的多线程并行.
1) VNF间流水线并行
NS-SFC上串行部署的VNF之间天然地具有流水线并行性，每个VNF可以看作是网络包处理的一个“流水段”，VNF之间通过共享内存访问的方式实现“零拷贝、零延迟”数据转发.进一步地，通过同步调度“流水线”上的VNF到物理CPU上运行，提高网络包的处理效率.
2) VNF间数据并行
典型的网络安全服务大多不会改变网络包①，而是以只读的方式对网络包进行检查，因此，不同的VNF之间往往不存在数据依赖关系. TOChain支持多个VNF，同时对同一个网络包进行处理，即数据并行性.具体而言，当转发表中记录的本跳中存在多个并行的VNF时，包调度器将汇总本跳上各个VNF的处理结果(“Allow”或“Deny”).只有在得到本跳上全部VNF的“Allow”结果后，才通知下一跳的各个VNF开始处理网络包.当收到某个VNF的“Deny”结果时，包调度器立即阻断该网络包的转发，不再向下一跳传递，阻止非法包传输.当转发表中记录的下一跳中存在多个并行的VNF时，包调度器则通知下一跳中所有的VNF同步开始处理网络包.
① 带有网络地址转换功能的防火墙服务会改变网络包的协议头部，因此会与其他网络安全服务间存在数据依赖关系，不适合于并行.
3) VNF多线程并行
在VNF中，网络安全服务以多线程的形式运行，服务线程与虚拟CPU以“一对一”的方式绑定，以便于在宿主机中以虚拟CPU为单位进行资源调度.如前所述，一个VNF可以属于多个NS-SFC，通过将服务线程(虚拟CPU)以独占方式分配给NS-SFC，从而便于实现以NS-SFC为单位进行资源调度和性能隔离.为了提高NS-SFC中特定VNF的处理能力，可以分配多个服务线程，并且服务线程可以来自于同一个VNF的一个或多个不同的虚拟实例，从而实现灵活的扩展性.在这种情况下，包调度器采用轮转方式在同一个VNF的不同服务线程之间分配网络包，以实现服务线程间负载均衡.
3 TOChain CPU资源调度算法以吞吐率作为衡量NS-SFC的QoS指标，为便于表述，将NS-SFC吞吐率定义为在输入队列中网络包充足的情况下，每秒能够从NS-SFC中转出网络包的数量，单位是packet/s.本研究面向NS-SFC吞吐率保证的CPU资源调度算法.
3.1 面向NS-SFC吞吐率保证的强同步周期性调度在TOChain中NS-SFC具有三级并行性，而实现这些并行性的前提是要将同一个NS-SFC上的VNF同步调度到物理CPU上运行.为此，本算法的核心思想是“强同步”调度，即将物理CPU按照以时间线划分的、连续、固定的周期进行调度，并在每个周期内对NS-SFC上的VNF服务线程采取步调一致的组调度.具体策略如下所述.
首先，将物理CPU以处理器核心为单位划分为2个分区，一个称为同步调度分区，运行VNF和虚拟机的虚拟CPU；另一个称为服务分区，运行TOE容器进程和TOChain控制面服务进程以及各种硬件设备的中断处理服务等.本节介绍的强同步调度是针对同步调度分区而言的，因此，下文中的“物理CPU”如无特殊说明均是指同步调度分区的物理CPU.接下来，为每个物理CPU设置2个运行队列，一个是VNF虚拟CPU(以下用VCPUvnf表示)队列—VCPURQvnf；另一个是用户虚拟机虚拟CPU(以下用VCPUvm表示)队列—VCPURQvm.其中，VCPUvnf采用组调度机制，即同一个NS-SFC上的VCPUvnf被同步调度到不同的物理CPU上运行，以发挥并行处理能力. VCPUvnf在调度过程中被动态分配到VCPURQvnf队列上，运行结束后便从该队列中移除.相反，VCPUvm一经调度到某个VCPURQvm队列后，便一直在该队列中，直至出现了负载不均衡的情况才可能被调度到其他物理CPU上.最后，物理CPU以固定的、相同的周期进行调度，周期为若干个tick(2次时钟中断之间的时间间隔).在每个调度周期中都会先按照NS-SFC的优先级依次调度VCPURQvnf队列中的VCPUvnf，再调度VCPURQvm队列中的VCPUvm.第i个NS-SFC的优先级Hi计算公式为
| $ {H_i} = \frac{{{I_i} + {T_i}{R_i}}}{{{F_i} + {T_i}{T_i}}} $ | (1) |
其中：Ii为上一个调度周期内到达NS-SFC输入队列的网络包的数量，Fi为上一个调度周期内第i个NS-SFC完成处理和转发的网络包的数量，Ri为上一个调度周期结束时输入队列中剩余的待处理网络包数量，Ti为该NS-SFC设定的吞吐率.在调度周期开始时，将根据式(1)计算每一个NS-SFC的优先级，Hi值越大，优先级越高.特别地，当上一个调度周期输入队列中剩余的待处理网络包数量为0(Ri=0)时，该NS-SFC在本调度周期优先级为0，在本周期将不予调度.
在一个调度周期中，对VCPUvnf和VCPUvm分别采取不同的策略分配物理CPU份额(份额是指在一个调度周期内虚拟CPU的运行时间，以tick为单位).对于VCPUvnf，将为其分配足够的物理CPU份额以使相应的VNF能够达到所设定的吞吐率，即满足式(2)中的条件，称为面向吞吐率保证的分配策略.
| $ {q_{ik}} = \left\{ \begin{array}{l} {\rm{ceil}}\left( {\frac{{{t_i}C}}{{{f_{ik}}}}} \right){\rm{, }}\;\;\;\;{t_i} < {f_{ik}}\\ {\rm{ceil}}\left( {\frac{{{t_i}C}}{{{f_{ik}}R}}} \right){\rm{, }}{f_{ik}} < {t_i} < {f_{ik}}R \end{array} \right. $ | (2) |
其中：ti为用户对第i个NS-SFC的吞吐率要求；C为物理CPU调度周期；fik为第i个NS-SFC的第k个VNF中单个服务线程在独占物理CPU的情况下能够达到的最大吞吐率，该值可以预先通过测算得出.由于不同VNF的数据处理复杂度不尽相同，相应的最大吞吐率也往往不同.当ti < fik时，即单个服务线程的处理能力能够满足吞吐率要求的情况下，只需要在VNF中为该NS-SFC分配1个服务线程即可；而当ti>fik时，即单个服务线程的处理能力无法满足吞吐率要求时，则可以通过增加服务线程并将网络流量均分到R个服务线程上并行处理来满足吞吐率要求.
对于VCPUvm，则采用面向公平性原则的时间片轮转分配策略.在一个调度周期中，VCPURQvnf队列调度完成后剩余的份额将平均分配给VCPURQvm队列中的VCPUvm.在调度周期结束后，重新计算各个VCPURQvm队列的长度，在出现不均等的情况时，对较长队列队尾的若干个VCPURQvm进行重新调度，以达到负载均衡.
3.2 VCPUvnf调度算法VCPUvnf调度算法由TOChain控制面资源调度模块执行，在调度周期开始时调用，如算法1所示.算法的前提是分配给VCPURQvnf中各个VCPUvnf的调度份额的总和小于等于一个调度周期的tick数量，即为各个NS-SFC所设定的吞吐率保证不能超出宿主机能够达到的最大吞吐率.
在为VCPUvnf选择物理CPU时，调度目标为尽可能地使调度后每个物理CPU的负载达到均衡水平.因此，该调度问题为寻找NS-SFC上VCPUvnf的集合到物理CPU集合的一个映射关系，使得按照该映射关系将VCPUvnf调度到物理CPU上后每个物理CPU的负载与总体平均负载的方差最小化.算法采用贪心策略解决这一组合优化问题.
算法1 VCPUvnf贪心组调度算法
输入:Ii, Fi, Ti, Ri, qik, P, pj, i=1, 2, …, n, k=1, 2, …, li, j=1, 2, …, m /* P为宿主机上CPU的集合，pj为该集合中第j个CPU，m为宿主机上CPU的个数，n为宿主机上NS-SFC的数量，li为第i个NS-SFC中VNF的个数. */
输出: None
初始化:
1 根据式(2)计算每个NS-SFC的优先级，并采用插入排序算法对所有NS-SFC按照优先级降序排列
2 for i=1, 2, …, n and Hi!=0 do
3 /* 计算CPU平均利用率 */
4 for j=1, 2, …, m do
5 u + = uj /* uj为当前从pj分配的配额 */
6 end for
7 for k=1, 2, …, li do
8 u+=qik
9 end for
10 u=u/m /* 计算从每个CPU分配的配额的平均值 */
11 for k=1, 2, …, li do
12 P’ = P
13 for j=1, 2, …, m and pj∈P′ do
14 if ((qik+uj)－u2＜umin then
15 umin=((qik+uj)－u)2
16 s=j
17 end if
18 end for
19 Schedule kth VNF/VCPU to ps
20 us+=qik /* 更新从ps分配的配额 */
21 Delete ps from P′
22 end for
23 end for
24 end
在VCPUvnf运行过程中当满足以下2个条件之一时，服务线程主动通知资源调度模块以提前结束运行，从而将物理CPU资源尽可能多地调度给用户虚拟机使用.
条件a NS-SFC的输入队列中没有待处理的网络包.
条件b 当输出队列中累积的网络包数量达到或超过输出接收端(虚拟机或TOE)在一个调度周期内的平均处理能力时，即满足
| $ {O_i} \ge {E_i} = \frac{{\sum\limits_{x = 1, 2, \ldots, w} {{r_x}} }}{w} $ | (3) |
其中：Oi为第i个NS-SFC的输出队列中待接收的网络包数量；Ei为在最近w个调度周期内，输出接收端(虚拟机或TOE)在每个周期接收网络包数量的数学期望；rx为最近第x个调度周期中接收端所接收的网络包的数量.
3.3 VCPUvm调度算法VCPUvm采用简单公平调度算法，如算法2所示.算法独立地运行在每个物理CPU上，当物理CPU完成了本周期内VCPUvnf的调度后，执行算法计算每个VCPUvm能够获得的调度份额，并进行调度.首先，算法对VCPURQvm队列中的VCPUvm进行优先级排序，排序的规则是VCPUvm对应的NS-SFC输出队列中队首网络包的到达时间越早则优先级越高.在算法伪代码中以数组RQ表示VCPURQvm队列，数组的长度即为运行队列的长度，记为l，数组的索引是VCPUvm在队列中的序号，数组中存储VCPUvm的指针和对应的NS-SFC的编号；数组OQ记录VCPUvm对应的NS-SFC输出队列队首网络包的到达时间，该数组以NS-SFC的编号为索引，长度是宿主机上NS-SFC的个数，用n表示.因此，以VCPUvm在队列中的序号为索引能够通过数组RQ和OQ查找到相应NS-SFC输出队列中最早的网络包的到达时间，进而依据其对RQ进行优先级排序.其次，计算分配到每个VCPUvm的调度份额，并存储到数组TK中.在算法伪代码中，g是一个调度周期中tick的数量，gvnf是本调度周期中已经分配给VCPUvnf的tick数量.通常，剩余可供分配给VCPUvm的tick数量不一定为队列中VCPUvm个数(l)的整数倍，这种情况下，在公平性原则的基础上优先将份额分配给队列中靠前的VCPUvm.最后，按照VCPUvm在排序后RQ数组中的顺序，依次调度VCPUvm到物理CPU上运行数组TK中所指定的份额.
算法2 VCPUvm简单公平调度算法
输入: RQ, OQ, gvnf, g, l, n
输出: None
初始化:
1 InsertSort(RQ, OQ, l, n)
2 /* 计算分配给VCPUvm的tick数量 */
3 for d=1, 2, …, l do
4 if d < =(g-gvnf) mod l then
5 TK[d]= floor((g-gvnf)/l)+1
6 else
7 TK[d]=floor((g-gvnf) /l)
8 end if
9 end for
10 for d=1, 2, …, l do
11 Schedule dth VCPUvm for TK[d] ticks
12 end for
13 end
3.4 算法1的时间复杂度分析首先，算法对宿主机上的NS-SFC逐个计算调度优先级，并依据优先级进行排序，在排序过程中采用插入排序算法.因此，计算优先级操作的执行次数为n，插入排序的时间复杂度为O(lgn)，其中n为宿主机上NS-SFC的数量.
其次，在调度每个NS-SFC时，先计算物理CPU上的平均负载(已分配的调度份额)，所进行的加法操作次数为m+li，其中m为宿主机上物理CPU的个数，li为第i个NS-SFC上VNF的个数.因此，对于全部NS-SFC来说，所需要的加法操作次数为
| $ mn + \sum\limits_{i = 1, 2, \ldots, n} {{l_i}} $ | (4) |
接下来，对NS-SFC上的每个VCPUvnf通过贪心算法找到能够使得与调度后总体平均负载偏差最小的物理CPU.这一过程需要进行的方差计算和比较次数为
| $ \begin{array}{l} {G_i} = m + \left( {m{\rm{-}}1} \right) + \left( {m{\rm{-}}2} \right) + \cdots + (m{\rm{-}}{l_i} + 1) = \\ \;\;\;\;\;\;m{l_i}{\rm{ - }}\frac{{({l_i}{\rm{ - }}1 + 1)({l_i}{\rm{ - }}1)}}{2} = m{l_i}{\rm{ - }}\frac{{l_i^2{\rm{ - }}{l_i}}}{2}=\\ \;\;\;\;\;\; \left( {m + \frac{1}{2}} \right){l_i}{\rm{ - }}\frac{{l_i^2}}{2} \end{array} $ | (5) |
因此，全部NS-SFC的方差计算和比较次数之和为
| $ \begin{array}{l} {G_{{\rm{total}}}} = \sum\limits_{i = 1, 2, \ldots, n} {{G_i} = } \\ \sum\limits_{i = 1, 2, \ldots, n} {\left[{\left( {m + \frac{1}{2}} \right){l_i}{\rm{-}}\frac{{l_i^2}}{2}} \right]} = \\ \left( {m + \frac{1}{2}} \right)\sum\limits_{i = 1, 2, \ldots, n} {{l_i}{\rm{ -}}\frac{1}{2}\sum\limits_{i = 1, 2, \ldots, n} {l_i^2} } \end{array} $ | (6) |
综上，算法1的时间复杂度为
| $ \begin{array}{l} \;\;\;\;\;\;{Y_{{\rm{Alg1}}}} = n + O({\rm{lg}}n) + mn + \\ \sum\limits_{i = 1, 2, \ldots, n} {{l_i} + \left( {m + \frac{1}{2}} \right)} \sum\limits_{i = 1, 2, \ldots, n} {{l_i}{\rm{-}}\frac{1}{2}} \sum\limits_{i = 1, 2, \ldots, n} {l_i^2 = } \\ O(mn + m\sum\limits_{i = 1, 2, \ldots, n} {{l_i}-\sum\limits_{i = 1, 2, \ldots, n} {l_i^2} }) \end{array} $ | (7) |
下面为算法2的时间复杂度分析.
首先，算法对VCPURQvm队列中的VCPUvm进行排序，采用插入排序算法，时间复杂度为O(lgl)，其中l为VCPURQvm队列的长度；其次，为队列中的每个VCPUvm计算调度份额，该操作的执行次数为l.因此，算法2的总的时间复杂度为
| $ {Y_{{\rm{Alg\;2}}}} = O({\rm{lg}}l) + l = O\left( l \right) $ | (8) |
对TOChain原型系统进行了性能评测，以验证：① TOChain相对于传统SFC的性能优化效果；②强同步周期性CPU调度算法在吞吐率保证方面的效果.
4.1 实验环境配置实验采用2台曙光I620-G20 2U机架式服务器，每台服务器配置有2颗十核Intel Xeon E5-2650 V3处理器(主频为2.3 GHz)、128 GB内存和一块Intel I210千兆以太网卡. TOChain原型系统基于KVM虚拟化平台实现，宿主机和虚拟机操作系统均采用CentOS 7.1.1503，Linux内核版本为3.10.0.在网络安全服务方面，采用iptables防火墙、Snort(v2.9)入侵监测系统和FreeWAF(v1.4.1)应用防火墙系统.
4.2 实验设计实验对以下3种NS-SFC进行了性能测试.
1) 基于NFV的传统网络安全SFC，以下简称TraditionalChain；
2) 采用KVM原生的完全公平调度算法的TOChain，以下简称TOChain-CFS；
3) 采用强同步周期性调度算法的TOChain，以下简称TOChain-SYNC.
测试环境由2台物理机组成，其中一台运行HTTP请求负载生成器，另一台作为宿主机运行NS-SFC和HTTP请求接收端虚拟机. HTTP请求接收端虚拟机中运行Apache HTTP Server(v2.2.32)服务程序，配置为4个VCPU、4 GB内存，并与NS-SFC一一对应.在TraditionalChain中，iptables、Snort和FreeWAF分别部署在3个虚拟机上，构成3种不同的VNF.在TOChain中，将iptables与卸载的TCP/IP协议栈一起部署在宿主机上，Snort和FreeWAF分别部署在虚拟机上，并且二者采用数据并行架构部署.在TOChain中，Snort和FreeWAF中单个服务线程在独占物理CPU的情况下能够达到的吞吐率上限，如表 1所示.
|
表 1 单个VNF服务线程吞吐率上限 |
在每种测试环境下都部署3种吞吐率的NS-SFC，如表 2所示，并针对不同吞吐率的NS-SFC施加不同的输入流量，以测试在混合场景下的网络性能和吞吐率保证能力.基于表 1中单个VNF服务线程的最大吞吐率，可以计算出为了达到设定的吞吐率，每个调度周期内需要分配给Snort和FreeWAF的CPU份额百分比.进一步地，对CPU份额较大的VNF采用多线程并行的方式进行部署.
|
|
表 2 不同吞吐率下VNF所需CPU份额和线程数 |
实验设计了3种测试负载，分别为轻度负载、中度负载和重度负载，如表 3所示.此外，在TOChain-SYNC中，按照3.1小节中介绍的调度算法设计，划定6个物理CPU核为服务分区，其余14个物理CPU核作为同步调度分区.因此，一个周期内同步调度分区物理CPU的总调度份额为1 400%.在实验中，tick设置为10 ms，调度周期设置为50 tick.
|
|
表 3 3种不同负载 |
在测试过程中，HTTP请求负载生成器同时分别以与设定的吞吐率相同的速率向接收端虚拟机持续发送稳定的流量，以接收端虚拟机接收到的HTTP请求速率作为端到端的性能指标.
4.3.1 轻度负载轻度负载下的测试结果如图 3所示.其中，图 3(a)给出了QoS为1 kpacket/s的3种NS-SFC(TraditionalChain、TOChain-CFS和TOChain-SYNC)达到的吞吐率的对比情况，图 3(b)和图 3(c)分别是QoS为2 kpacket/s和5 kpacket/s的NS-SFC的测试结果.由图中数据对比可见，TOChain-SYNC能够达到最好的吞吐率保证，而在TraditionalChain下，虚拟机接收到的请求速率远低于发送速率.这是因为在TraditionalChain中，每个HTTP请求要反复经过3个VNF(iptables、Snort和FreeWAF)和1个虚拟机上的共4次虚拟网卡和TCP/IP协议栈的解包、封包流程，显著增加了HTTP请求的传输延迟和处理开销.此外，在轻度负载的情况下，VNF和虚拟机能够分配到充足的物理CPU资源，因此，TOChain-CFS也得到了接近于发送速率的测试结果.
|
图 3 轻度负载下的吞吐率测试结果 |
在测试过程中，宿主机的CPU占用率情况如图 4所示.其中，在TraditionalChain下，分别统计了用户态和核心态下的CPU利用率；在TOChain-CFS和TOChain-SYNC下，分别统计了服务分区和同步调度分区的CPU利用率(以全部CPU占用率上限为100%计，服务分区占用率上限为6/20=30%，同步调度分区占用率上限为14/20=70%).由图可见，TraditionalChain相对于TOChain消耗了更多的CPU资源.特别是TraditionalChain的核心态CPU占用率较高，这主要是运行核心态的虚拟网卡驱动程序和TCP/IP协议栈导致的.
|
图 4 轻度负载下宿主机CPU占用率情况 |
中度负载下的测试结果如图 5所示.由图中数据可见，TOChain-SYNC能够达到与NS-SFC设定的吞吐率接近的性能，而TraditionalChain和TOChain-CFS与发送速率的差距十分明显.此外，从具有相同输入速率的3个NS-SFC之间的横向对比还可以看出，TOChain-SYNC能够保证NS-SFC之间以及用户虚拟机之间的调度公平性.测试过程中的宿主机CPU占用率情况如图 6所示.其中，TraditionalChain消耗了最多的CPU资源，约为79%；TOChain-CFS与TOChain-SYNC较为接近，分别为58%和61%. TOChain-SYNC服务分区的CPU占用率较TOChain-CFS略高(约为2%)，这主要是由控制面资源调度模块的周期性运行开销所导致的.
|
图 5 中度负载下的吞吐率测试结果 |
|
图 6 中度负载下宿主机CPU占用率情况 |
重度负载下的测试结果如图 7所示.从总体上看，TOChain-SYNC能够达到最高的性能，但与NS-SFC设定吞吐率仍然存在明显的差距.这主要是因为，在重度负载下物理CPU资源竞争激烈，虽然NS-SFC上的VNF能够获得足够的CPU份额，但HTTP接收端虚拟机能够获得的CPU份额较少，不能及时接收HTTP请求，从而导致接收速率降低.此外，从测试数据中还可以看出，在TOChain-SYNC下每个接收端虚拟机的接收速率较为接近，这意味着即使在重度负载下仍然能够达到较好的调度公平性. 图 8给出了重度负载下宿主机的CPU占用率情况.从整体上来看，宿主机CPU都达到了饱和状态，分别是100%、96%和99%.在TraditionalChain中，有55%的CPU资源用于核心态的虚拟网络收发包流程处理，由于用户态处理不及时，导致大量的丢包.在TOChain-CFS和TOChain-SYNC下，同步调度分区中每个CPU都满负荷运行，达到了该分区的上限(70%).
|
图 7 重度负载下的吞吐率测试结果 |
|
图 8 重度负载下宿主机CPU占用率情况 |
笔者提出了一种虚拟网络安全SFC的优化设计—TOChain及其CPU资源调度算法. TOChain可以有效避免VNF和用户虚拟机重复地执行虚拟网卡收/发包和协议栈解/封包处理流程，避免了跨宿主机转发网络包，支持VNF流水线并行、数据并行和多线程并行三级并行处理.针对NS-SFC的QoS保障问题，进一步提出了面向吞吐率保证的强同步周期性CPU资源调度算法.在由防火墙、入侵检测和应用防火墙3种网络安全服务构成的NS-SFC测试环境中进行了不同网络流量负载下的性能与吞吐率保证能力测试.测试数据表明，与传统SFC相比，采用强同步周期性调度算法的TOChain能够以较低的CPU占用率达到更高、更稳定的网络性能，能够在轻度和中度负载下达到与设定的吞吐率极为接近的网络性能，即使在重度负载下，也能较好地保证虚拟机之间的调度公平性.
下一步将研究TOChain下自适应的VNF多线程并行优化技术，以进一步优化CPU资源调度的均衡性，提升QoS保障能力.为此，一方面需要研究轻量化的VNF动态快速部署技术，使得能够在可接受的调度开销内完成从VNF部署到服务线程构建，再到SFC重新编排等一系列准备工作；另一方面，需要改进CPU调度算法，以适应VNF多线程并行度的可变性和CPU调度份额的动态性.
| [1] | Bonafiglia R, Cerrato I, Ciaccia F, et al. Assessing the performance of virtualization technologies for NFV: a preliminary benchmarking[C]//Proc of 4th European Workshop on Software Defined Networks. Bilbao: IEEE, 2015: 67-72. |
| [2] | Mauricio L A F, Rubinstein M G, Duarte O C M B. Proposing and evaluating the performance of a firewall implemented as a virtualized network function[C]//Proc of 7th Int Conf on the Network of the Future (NOF). Buzios: IEEE, 2016: 1-3. |
| [3] | Deng Juan, Hu Hongxin, Li Hongda, et al. VNGuard: an NFV/SDN combination framework for provisioning and managing virtual firewalls[C]//Proc of Network Function Virtualization and Software Defined Network. San Francisco: IEEE, 2015: 107-114. |
| [4] | Li Hongda, Deng Juan, Hu Hongxin, et al. On the safety and efficiency of virtual firewall elasticity control[C]//Proc of the 22nd ACM Symp on Access Control Models and Technologies. Indianapolis: Association for Computing Machinery, 2017: 129-131. |
| [5] | Jakaria A H M, Yang Wei, Rashidi B, et al. VFence: a defense against distributed denial of service attacks using network function virtualization[C]//Proc of Computer Software and Applications Conf. Atlanta: IEEE, 2016: 431-436. |
| [6] | Rashidi B, Fung C. CoFence: a collaborative DDoS defence using network function virtualization[C]//Proc of Int Conf on Network and Service Management. Montreal: IEEE, 2016: 160-166. |
| [7] | Fung C J, Mccormick B. VGuard: a distributed denial of service attack mitigation method using network function virtualization[C]//Proc of Int Conf on Network and Service Management. Barcelona: IEEE, 2015: 64-70. |
| [8] | Cao Lianjie, Sharma P, Fahmy S, et al. NFV-VITAL: a framework for characterizing the performance of virtual network functions[C]//Proc of Network Function Virtualization and Software Defined Network. San Francisco: IEEE, 2015: 93-99. |
| [9] | Asawa M. NFV: a dynamic, multi-layer resource optimization challenge[EB/OL]. Ann Arbor: University of Michigan, 2016[2017-03-24]. http://eecs.umich.edu/eecs/about/articles/2016/Celebrating-a-Leader-In-Control-Systems/presentations/asawa.pdf. |
| [10] | Ge Xiongzi, Liu Yi, Du D H C, et al. OpenANFV: accelerating network function virtualization with a consolidated framework in OpenStack[C]//Proc of ACM Conf on SIGCOMM. Chicago: ACM, 2015: 353-354. |
| [11] | Blendin J, Ruckert J, Leymann N, et al. Software-defined network service chaining[C]//Proc of Third European Workshop on Software Defined Networks. London: IEEE, 2014: 139-140. |
| [12] | 楼亮. 基于snort的入侵检测系统的分析和改进[D]. 上海: 上海交通大学, 2007. |
| [13] | Hu Yang, Song Mingcong, Chen Huixiang, et al. Towards efficient server architecture for virtualized network function deployment: implications and implementations[C]//Proc of IEEE/ACM 49th Int Symp on Microarchitecture. Taipei: IEEE, 2016: 1-12. |
| [14] | Stezenbach D, Tutschku K, Fiedler M. A performance evaluation metric for NFV elements on multiple timescales[C]//Proc of the 2013 Global Communications Conference. Atlanta: IEEE, 2013. |
| [15] | Hoban A, Czesnowicz P, Mooney S, et al. A path to line-rate-capable NFV deployments with Intel architecture and the OpenStack Kilo release[EB/OL]. USA: Intel Corporation, 2015[2017-02-21]. https://networkbuilders.intel.com/docs/kilo-a-path-to-line-rate-capable-nfv-deployments-with-intel-architecture-and-the-openstack-kilo-release.pdf. |
| [16] | Jardin V. High performance NFV infrastructure (NFVI): DPDK host applications with neutron/OpenStack and VNF acceleration[EB/OL]. Dusselforf: ELC Europe, 2014[2017-02-22]. http://events.linuxfoundation.jp/sites/events/files/slides/Openstack-v4_0.pdf. |
| [17] | Roseboro R. Using hardware to improve NFV performance[EB/OL]. Sunnyvale: Mellanox Technologies, 2015[2017-03-10]. http://www.mellanox.com/related-docs/whitepapers/WP_heavyreading-NFV-performance.pdf. |
| [18] | Kim T, Kim S, Lee K, et al. A QoS assured network service chaining algorithm in network function virtualization architecture[C]//Proc of IEEE/ACM Int Symp on Cluster, Cloud and Grid Computing. Shenzhen: IEEE, 2015: 1221-1224. |
| [19] | Riera J F, Escalona E, Batalle J, et al. Virtual network function scheduling: concept and challenges[C]//Proc of Int Conf on Smart Communications in Network Technologies. Vilanova i la Geltru: IEEE, 2014: 1-5. |
| [20] | Long Q, Assi C, Shaban K. Delay-aware scheduling and resource optimization with network function virtualization[J]. IEEE Transactions on Communications, 2016, 64(9): 3746–3758. doi: 10.1109/TCOMM.2016.2580150 |
| [21] | Zhang Qixia, Xiao Yikai, Liu Fangming, et al. Joint optimization of chain placement and request scheduling for network function virtualization[C]//Proc of 37th IEEE Int Conf on Distributed Computing Systems. Atlanta: IEEE, 2017: 731-741. |