一种基于软硬件协同的流分类技术研究

赵大胜 黄 馨 周 愚

（武汉船舶通信研究所 武汉 430205）

1 引言

某型万兆网络密码机采用红黑隔离架构，红黑区处理单元均基于通用处理器实现，红黑区之间以FPGA加密卡隔离。网络密码机内置ACL规则表，每行规则包含行号、五元组各字段范围（上限、下限）、优先级和动作（密传/明传/丢弃）等信息。CPU根据来包的五元组信息在规则表中进行分类匹配，决定后续处理，如密传/明传/丢弃等。

该项目流分类技术难点主要有三点，第一要支持万兆速率下线速流分类，当包长为64字节时每秒需进行14.88兆次流分类；第二要支持五元组各字段的范围匹配，不同于传统算法中IP地址字段仅支持掩码匹配或精确匹配；第三要支持ACL规则表实时更新，这使得基于规则表预生成二叉树的范围匹配算法难以适用。FPGA可实现范围匹配和规则表快速更新，但如每个数据包均由FPGA计算匹配的规则行号，再将行号返回CPU则总线通信开销极大［1～3］。

本文基于设备硬件架构，设计了一种软硬件协同的流分类算法。对于各数据流的首包，使用FP⁃GA进行范围匹配，并在CPU侧建立对应流表；该流的后续包在CPU侧基于流表进行哈希精确匹配，可大幅度降低计算开销和通信开销。此外，设计了基于计数器同步的规则表和流表的实时分布式更新机制，由入站流量触发动态更新，可降低更新流表的计算开销。

2 流分类技术研究现状

流分类的规则匹配分为精确匹配、掩码匹配和范围匹配，其中范围匹配实现难度最大。五元组范围匹配实现方式包括TCAM芯片匹配、CPU侧二叉树范围匹配和FPGA侧向量匹配方式［1～6］。

TCAM芯片常用于掩码匹配，将之用于范围匹配需要将规则展开成多行以进行掩码匹配，存在规则过度扩展问题，例如3bit范围［1，8）展开为3条掩码规则｛001，01*，1*｝。多个字段则展开项为幂次关系，TCAM存储空间有限且匹配条目过多时功耗显著增加，因此在采用大规则表时，规则表拆解为掩码造成的规则条目过度扩张将使得TCAM芯片难以满足要求［4～5］。

CPU侧范围匹配原理是基于规则表构建二叉树进行范围匹配，二叉树的构建方式不同影响搜索深度和搜索效率。学术界提出了不少优化算法，利用规则表统计特性提高效率，典型代表为Hyper⁃cut、Bitcut等算法［6～9］。但此类算法存在三个问题，第一，二叉树深度与规则表统计特性相关，不具普适性，使得流分类延时不固定；第二，当规则库修改后，二叉树需要重新构建，不能支持规则库实时更新；第三，其计算开销较大，目前常用的软件流分类算法处理10Gbps速率时，Bitcut等算法要使用四核Intel E3-1225志强处理器的三个核心。

FPGA侧基于向量匹配实现范围匹配，典型算法为StrideBV和QuYun多域分类算法［10～11］。其将五元组的各字段分别进行范围匹配，获得五个N行列向量（N为规则表行数），其中对应行为1则表示该字段在匹配范围内，否则为0；而后将五个列向量相与，结果为1的行为匹配行，当有多个匹配行时再进行优先级比较，选择最高优先级的行作为最终匹配成功行。向量匹配方式对规则表具有普适性，任何规则均能适配，其中StrideBV存储开销较大，本项目基于QuYun多域分类算法实现FPGA侧流分类处理。

3 算法描述

3.1 流分类处理流程

当数据流通过网卡进入CPU后，CPU首先根据五元组哈希值查询流表，如果查询不到则将五元组通过PCIe总线交FPGA处理。FPGA返回五元组信息及匹配到的行号，CPU收到匹配结果后建立对应的流表表项。CPU对该流后续包计算hash值，在哈希桶中获取流表index索引值，根据该值在流表中进行索引，获取对应的规则表行号，进而使用该行号索引规则表，根据规则表中规则进行对应处理。流分类示意图如图1所示。

图1 流分类流程

以下以1024行规则为例，介绍FPGA侧流分类引擎处理流程。流分类引擎由8个五元组匹配模块（PE）和8个优先级比较模块（PR）组成。每个PE包含128行五元组比较单元（LINE），每个PR处理128行规则的优先级比较。PE中每个LINE对应一行规则，包含5个比较器FE，每个FE处理五元组中的一个字段的范围比较，5个FE结果相与作为该行范围匹配的结果。PR中128行的比较器采用两两比较方式，横向多级比较后输出该128行匹配结果。

流分类引擎采用二维流水线方式，五元组沿PE纵向移动匹配，每个PE将匹配结果送入PR中进行优先级比较，PR优先级比较的结果（匹配与否、行号、优先级）沿各PR纵向移动匹配，本PR与上一个PR中结果比较后将结果送入下一个PR中。FPGA侧修改规则表参数相对容易，修改规则仅需修改BRAM或寄存器中对应值即可，删除规则将对应行无效即可。FPGA流分类引擎组成如图2所示。

图2 FPGA流分类引擎

CPU侧流表匹配使用DPDK自带的Cuckoo hash算法，又称布谷鸟哈希，由于其结构紧凑（CPU Cache友好），空间利用率高且访存性能确定，被In⁃tel公司用于DPDK数据转发平面查表操作。布谷鸟哈希查找首先利用主hash函数对五元组计算hash值，对hash值取余或移位作为主表哈希桶索引在该桶中查找，哈希桶中包含8个hash值高位字节（8×32bit）和8个index值（8×32bit）。如果hash值匹配则返回流表索引index，index用于指示流表行号。如果主表未查到，则利用副hash函数在副表中查找。布谷鸟哈希插入时采用hash桶方式，并使用主表、副表进一步降低冲突概率，如果发生冲突则将原位置数据移出，再进行插入操作。DPDK实现的hash库的最大优点，在于其一次查找到时间具有上限。官方试验结果表明，只有当哈希表节点使用率达到95%时才会出现插入失败，在50%以下时基本可以保证绝大部分节点都保存在主哈希桶中［12］。

流表匹配过程如图3所示，图中设置计数器目的是解决规则表修改后流表的分布式更新。

3.2 规则表更新处理流程

规则表仅千行量级，但流表数以百万计，为降低开销，本文通过对流表和规则行设置计数器实现由数据流触发的分布式同步更新。对于两行规则A、B而言，如果存在交集，则指有数据流同时满足A规则和B规则。对于交集中的流分类应选择优先级高的规则行作为匹配结果。因此，对某行规则的修改可能会影响与之有交集的对应行。规则更新包括删除行、插入行和修改行，各种操作对流表影响不同，以下分别分析。

在规则表中删除行操作：删除时把对应行号的使能值调整为0。则数据流进入时，CPU查阅规则表后发现该行已失效，会触发FPGA重新计算流分类值进而更新对应流表。

在规则表中插入行操作：将某行插入时需要计算与该行有交集的规则行，如果本行优先级高于与之有关联的行，则将相关关联行的计数值加一，在有相关数据流时触发关联行涉及流表的重新计算。

在规则表中修改行操作：规则表修改涉及范围修改和优先级修改，与插入行影响类似。此时需要计算与之有交集的规则行，如果待修改行的优先级高于交集中关联规则行，则相应关联规则行的计数值加一。

规则表修改流程如图4所示。

图4 规则表修改流程

4 效能分析

设计关注的指标包括流表插入速率、检索速率、规则更新速度和通信开销等，利用Intel Xeon E5-2699志强处理器和Xilinx公司的K7325T FPGA进行测试验证。流表插入方面，目前DPDK18.05使用的哈希算法为Sameh Gobriel等学者设计的RTE-Hash布谷鸟哈希算法，3200万条五元组流表可放入cache内。使用4个CPU核时流表插入速率可达20MPPS（Packet Per Second），使用8个核时插入速率超过35MPPS［12］。流表检索方面，使用单CPU核时100万条流表哈希查找速率超过16MPPS，3200万条流表查找速率超过15MPPS，使用4个CPU核进行流表查找时千万级流表查找速率超过50MPPS，FPGA侧进行范围匹配时在K7325T上时钟频率可达200MHz，流分类速度达到400MPPS，二者组合后远远超过万兆64字节小包的14.88MPPS线速流分类要求。规则更新方面，涉及FPGA侧规则更新和CPU侧规则更新。FPGA侧更新仅需更新BRAM或寄存器中参数值，更新速度可达一百万次/秒［11］。CPU侧处理规则更新时，删除规则仅需将规则表中对应行失效即可，修改规则时需要计算与之有交集的规则行，当程序在E5-2699CPU上运行时，对于1000条规则计算时延小于0.5ms，因此规则更新速度可达2000次/秒。通信开销方面，仅流的首包需要涉及CPU与FPGA间总线开销，后续包由CPU自行进行流分类，以一个流平均20包计算，相比FPGA流分类再将结果返还CPU方式，可以节约95%的总线通信开销。

5 结语

本文提出的软硬件协同流分类算法，可支持流分类范围匹配和流分类规则的快速更新。在FPGA上采用成熟的范围匹配算法，在CPU侧使用DPDK自带的布谷鸟哈希算法，降低了开发风险和难度。并通过在流表和规则表中设置计数器，实现了由流触发的流表自动更新机制，可以显著降低流表计算开销和规则更新时延。