论文部分内容阅读
数据包分类是按照一定的规则集和数据包的域信息，找出与数据包匹配的规则条目的过程。数据包分类技术在防火墙、入侵检测、负载均衡系统、VPN等各类网络设备中都得到了广泛的应用。作为网络设备数据平面的关键技术之一，高性能的数据包分类方法在过去的20年中得到了广泛和深入的研究。传统的数据包分类技术，一般基于特定硬件。然而随着数据中心网络、软件定义网络、业务感知网络等新型网络技术的发展，基于多/众核平台的高效灵活的数据包分类技术开始逐渐成为研究热点。本文主要从算法设计框架、规则集特性分析和算法实现优化三个层面对数据包分类技术进行了研究。 在算法设计框架方面，本文在分析多种典型包分类算法的基础上提出多域决策树包分类算法框架。该框架将决策树算法过程分解成由域选择-域划分-优化方法三类“元”方法所构成，揭示了不同算法内在的联系和区别，为设计更高效的算法提供依据。本文通过混合不同算法的“元方法”，提出HiCuts-op和HyperSplit-op数据包分类算法，实验结果表明，HiCuts-op比HiCuts算法内存占用降低2～20倍，访存次数降低约10％。HyperSplit-op算法比HyperSplit算法内存占用降低2～200倍，访存次数有10％～30％的下降。 在规则集特性分析方面，本文挖掘规则集特性和算法性能之间的联系，发现规则集的“覆盖均匀性”对不同算法的访存次数具有直接影响，规则集内“正交结构”规则的数量将直接决定算法的内存占用。结合所提出的“覆盖均匀性”量化方法和内存估算模型，本文设计了SmartSplit多决策树算法和AutoPC算法策略框架。对比EffiCuts算法，SmartSplit算法的访存次数平均减少1.9倍，内存占用最多下降10倍。对于给定一个规则集，AutoPC框架能够根据规则特性自适应选择合适的算法。与仅使用一种算法相比，AutoPC框架通过为不同规则集推荐不同算法，取得了平均3.8倍的性能提升。 本文还分析了IP转发表中的前缀长度和更新开销之间的联系。本文发现，前缀长度越长，前缀树算法Tree Bitmap访存次数则越多;前缀长度越短，DIR-24-8算法的更新开销则越大。本文通过结合这两类典型的IP查找算法的优势，提出了一种混合算法SplitLookup，改进了已有算法的更新开销。实验结果表明，在更新短前缀时，和DIR-24-8算法相比，SplitLookup更新所需要的访存次数有2个数量级的下降，其分类速率和DIR-24-8接近。 在算法实现优化上，本文在多/众核上实现并优化多种算法，包括IP查找中的DIR-24-8和Tree Bitmap算法、多域包分类中的HyperCuts/HiCuts算法的多种实现变体、Adaptive Binary Cuttings算法、EffiCuts算法、HiCuts-op和HyperSplit-op算法。其中SplitLookup算法在众核处理器TILEPro64上能够达到40Gbps的分类速率，多域包分类算法HiCuts-op和HyperSplit-op算法在通用CPU上能够获得10～20Gbps的吞吐率。