摘要: 1．本文的创新点
在现有分组分类算法中，搜索性能最高、搜索的时间复杂度最低的算法是递归流分类（RFC）算法。然而RFC 算法具有很高的空间复杂度和预处理时间复杂度，这限制了该算法在不同场景中的应用。本文的贡献在于：（1）提出了一种新型的增强RFC 算法（ERFC），该算法在保持RFC 算法极低的搜索复杂度O(1)的基础上，提出了一种新的算法预处理方案及一种新型的搜索数据结构，极大地降低算法的空间复杂度和预处理的时间复杂度。（2）在预处理阶段，本文提出一种基于散列的聚合比特向量（ABV）方案，提高了算法预处理的效率，加速预处理过程；（3）在搜索阶段，提出一种高效紧缩的、可缓存（cacheable）的搜索数据结构，大幅减少了算法所需的存贮空间，并进一步提高了算法的分类速度。

2．实现方法
　　（1）高效的算法预处理方案
　　在算法的预处理过程中，需要进行数量巨大的比特向量（BV）之间的“按位与”（Bitwise-AND）操作和搜索操作。为提高效率，本文提出了一种基于散列的聚合比特向量（ABV）的数据结构及算法，大大减少了长位数比特向量运算所需要的复杂计算操作的数量，提高了比特向量运算和搜索的效率，使算法预处理的总体时间复杂度降低了至少一个数量级。
　　（2）紧缩的、可缓存的搜索数据结构
　　本文对原有算法的搜索数据结构的内容和分布进行了统计分析，结果表明原有搜索数据结构存在大量冗余。对此本文提出了一种压缩的、且与原有结构等价的新搜索数据结构，可将算法所需的平均存贮空间可减少约一个数量级。同时，这种数据结构支持将频繁访问的内容载入高速缓存，以进一步提高算法的分类速度。该方案在最坏情况下具有与原有RFC 算法相同的分类性能（二者在最坏情况下，一次分类所需要的内存访问次数相同）；在平均情况下，本文提出的ERFC 算法一次分类所需要的平均内存访问次数下降了约50%。

3．结论及未来待解决的问题
在本文提出的 ERFC 算法中，采用了基于散列的聚合比特向量技术以降低算法预处理的时间复杂度；采用了高效紧缩的可缓存的搜索数据结构以减少算法所需的存贮空间，提高算法的分类速度。性能评估结果表明，与原有RFC 算法相比，当规则集中的规则数量N〉1000 时，ERFC 所需的存贮空间可减少约55~98%；算法预处理时间下降至少90%；算法的平均分类性能提高了约一倍。与其他分组分类算法如HiCuts 和HyperCuts 等相比，在N 较大时，本文提出的ERFC 同样具有更好的（或相当的）预处理性能和空间性能，但搜索性能大大优于HiCuts 和HyperCuts 算法。
未来的工作主要在于对 ERFC 算法的进一步改进，并将其应用到IPv6 网络环境中。

4．实用价值或应用前景
本文提出的算法可应用于高速网络设备中 QoS 控制、策略管理、安全管理等组件上的快速分组分类和识别机制。本文的工作也为高速IP 分组流分类领域的研究提供借鉴。