基于规则集划分多决策树报文分类算法.doc

基于规则集划分多决策树报文分类算法 　　摘要： 　　为克服决策树算法处理高速网络、大容量规则集下的报文分类问题时内存使用量大的弊端，提出一种基于规则集划分的多决策树报文分类算法。在保证规则子集数量可控的前提下，采用启发式算法将规则集划分为有限个规则子集，最大限度分离交叠规则；提出两级级联决策树结构，降低决策树深度以减少规则查找时间。理论分析表明，该算法空间复杂度较传统单决策树算法大幅降低。仿真结果表明，该算法的内存使用量比目前空间性能最好的EffiCuts算法减少了30%，且维度可扩展性更好。 　　关键词：报文分类；规则集划分；多决策树；内存使用量；大容量规则集 　　中图分类号：TP393.0 　　文献标志码：A 　　0引言 　　报文分类是网络应用领域的关键技术之一。目前业界的解决方案主要有两种：基于硬件的三态内容可寻址寄存器（Ternary Content Addressable Memory，TCAM）和基于随机存取存储器（Random Access Memory，RAM），它们均可以线速处理报文。随着链路带宽不断增加、网络应用日益多元化，分类规则集呈现出新的特点：容量增大、规则维数增多、范围规则大量出现，使得基于TCAM的多域报文分类算法举步维艰（TCAM不宜处理范围规则）[1-3]，而运行于可编程门阵列（Field Programmable Gate Array，FPGA）+RAM架构的决策树算法在规则集容量、规则维数方面扩展性强，且适合处理范围规则，成为研究热点。 　　规则集中的规则在某些域相互交叠，使得这类算法在预处理阶段构建立决策树时，不可避免出现规则复制，带来严重的存储空间消耗。受限于高速存储器的容量，高速网络、大容量规则集下的报文分类算法必须解决内存消耗量大的问题。为此在预处理阶段需要对规则集进行合适的划分，使得规则子集内部的规则相互交叠的概率大幅降低，从而达到抑制规则复制、减少算法内存使用量的目的。划分规则集、建立多决策树结构的报文分类算法是本文研究的内容。 　　2相关工作 　　早期基于决策树的多域报文分类算法包括HiCuts算法[5]和HyperCuts算法[6]，均折中考虑了分类速率与内存使用量，但它们采用均匀切分规则空间的启发式算法不可避免带来规则复制（见图2左图，R2在左侧子节点出现复制）。近年出现的HyperSplit算法[7]提出了沿投影端点非均匀切分规则空间的思路，减小了规则复制的概率，算法内存使用量大幅降低（见图2右图，没有规则复制），但HyperSplit对规则空间的二分处理导致决策树深度过大，算法基于FPGA实现的逻辑复杂度极高，使得系统无法提供满足需求的吞吐率。 　　3算法描述 　　本文算法包含两个部分：规则集划分算法和决策树构建算法。首先通过规则集划分算法将原始规则集划分为多个规则子集，然后对每个规则子集建立决策树，形成多决策树并行查找的系统架构。 　　3.3基于多决策树的报文分类算法 　　基于多决策树的报文分类算法包括3个部分：决策树构建、规则查找和规则更新。 　　3.3.1决策树构建 　　规则集划分完成后，对每个规则子集分别建立决策树。传统的决策树算法从根节点开始，利用选择切分维度和切分点的启发式算法，连续切分多维规则空间，直至节点对应规则子集包含的规则数量不大于预先设定的门限，该节点为决策树的一个叶节点。 　　本文对传统决策树结构进行改进，提出两级决策树级联算法[11]：1）对每棵决策树的根节点，由于其对应规则集中的规则在维度x上互不交叠，为降低决策树高度，保持规则数量在子节点分布均衡，采取沿x维度对规则等数量多点切分的方法；2）对每棵决策树根节点的子节点，以其作为根节点，按照HyperSplit算法建立第二级决策树，原因在于HyperSplit沿规则投影点切分规则空间的方法大大减少了算法内存使用量。决策树结构见图4。 　　3.3.2规则查找 　　基于决策树的报文分类算法按如下过程完成规则查找：报文到来后，提取头部关键字，逐层遍历决策树，直至找到叶节点，再线性查找叶节点对应的少量规则，输出匹配规则索引。在多决策树的报文分类系统中，上述过程在所有决策树中并行执行，最后通过优先级判决器，输出优先级最高的规则索引，见图5。 　　3.3.3规则更新 　　为提供足够吞吐率，一般基于决策树的报文分类算法通过将树形结构在FPGA上映射为多级深度流水线实现，而规则的增量更新通过在流水线中插入Write Bubble实现[12-13]。首先离线计算每级流水线待更新的节点内容，然后启动更新过程，插入wtite bubble。每一个write bubble分配一个标识符，当写使能位被置位后，write bubble用新的节点内容更新FPGA片上相应的双端口