引 言
随着快速增长的网络链路速率与分类规则的增多，多维报文分类问题成为设计高速路由器的一个基本挑战。例如，当主干网链路速率达到80Gbps时，在报文长度为40字节时，需要每4ns内处理一个数据报，这个速度用现在的软件算法不可能实现。
为了满足以上网络速率的需要，研究人员寻求硬件上的解决方案，三态内容存储器(ternary content addressable memory-TCAM)是一个不错的选择，它能够对输入的关键字进行并行查找，最大的优点是分类速度快，但也有如下一些缺点，如存储面积大、价格高，特别是TCAM不支持直接的范围匹配等。另一方面，由于FPGA具有可重构性和并行性，结合了软件的灵活性与硬件的高效性，使它成为实现实时网络处理引擎一个很好的选择。现在，研究人员已经开始在FPGA上实现一些现有分类算法，可以达到很高的吞吐量，由于存储需求过多，这些算法很少有能够支持大的规则集(超过10K)。本文主要针对基于决策树类的分类算法在FPGA中的实现做了深入研究，解决了在规则集较大的情况下对报文进行快速分类的问题。
1 分类算法的定义及评估方法
1.1 分类算法的定义
报文分类问题有许多定义，它们基本上是等价的，描述如下：报文头部H 包含K个域，分别表示成H[1]、H[2]H[K]，一条过滤规则F相应地也具有K 个域，其中F[i](F的第i部分)是H[i]的正则表达式，如果对任意的H [i]满足正则表达式F [i]，则称报文P与规则F相匹配。
对具有N条过滤规则的分类器R来说，为了解决同一个报文与分类器R中多条规则相匹配的问题，在定义过滤规则F时，对每条规则指定了一个优先级，当有多条规则与报文头部匹配时，选择一个优先级最高的作为最终匹配规则。与每条规则相关联还有一个动作，它指出了当报文与此规则相匹配时，下一步所执行的操作，一个包含10规则的简单分类器。
也可以从计算机几何中的点定位问题来看待多维报文分类问题，一个D维的分类规则相当于D维空间中的一个超矩形，D维空间中的N个规则至多可构成(2N-1)D 个互不重叠的超矩形，而一个报文则相当于D维空间中的一个点，所以，多维报文分类转化为找到包含这个点的超矩形。由此可得到，多维报文分类的时间复杂度为O(logN)，空间复杂度为O(ND)，或是在时间度为O(logD-1 N)的情况下，空间复杂度为O(N)。从上面的分析可以看到，多维报文分类问题是一个非常复杂的问题，幸运的是，现实情况要比这好，真实的分类器没这么复杂，它们有一些自身特点，我们可以在实际中加以利用，可以使分类算法得到简化。
1.2 分类算法的评估方法
由于IP分类问题可以抽象成一个查找表项巨大的多关键字查找问题，因此衡量一个算法好坏的关键是查询速度快，再就是用分类规则来构建查找表数据结构时所占内存要少。考虑到分类算法自身的特点，其它评估方法还有过滤规则的插入与删除速度快，维数(查找中关键字个数)易扩展以及能够根据规则中各个域的不同表现形式，支持多种查询(匹配)方式等。总的来说，算法的关键是怎么找到时间与空间的平衡点。
2 现有的分类算法
现有的分类算法很多，文献对各类算法进行了总结，并对每种类型的算法，列举出了相关的例子;文献根据分类算法对规则进行预处理情况，把它们分为基于分解、基于分割和基于决策树3种情况。
基于分解算法的主要思想是对报文头部的每个域进行独立的搜索，最后把每个域查询结果结合起，就可得到最终匹配规则，该类型的算法适合于硬件实现，典型代表是平行位向量(parallel bit vector)(BV)算法。基于分割算法的主要思想是把原来的规则集划分为若干个子集，每个子集中的规则在单个或多个域之间是没有重叠的，独立集合算法(independent sets algorithm))就属于这类。我们知道，对于有N 条分类规则的D维分类器，算法所需要的空间复杂度为O(ND)，现假设把规则集R均匀地划分为K组，每组有N/K个规则，划分后的空间复杂度为O(K*(N/K)D)，所以通过规则集划分后，空间复杂度减少为原来的1/KD-1。算法面临的主要挑战是独立规则集划分个数的不确定性和过多。
决策树类的代表算法是HiCuts，它通过对分类器的预处理，建立决策树这种数据结构，树的根点代表整个搜索空间，它包含了规则集中的所有规则，对决策树中的每个内部点，都递归地进行如下操作，根据预先定义的某种标准，选择在某一维方向上，相等地切割多少份，直到该结点所包含的规则数少于预先定义的某个定值为止，不再进行切割，该结点为叶子结点。每当有报文达到时，对决策树进行遍历，找到叶子结点，由于叶子结点中的规则数较少，可以进行线性搜索，找到最佳匹配规则。Hi-Cuts算法的主要缺点是由于对搜索空间进行了切割，带来了规则的复制，增加了存储空间。HyperCuts算法是Hi-Cuts的改进版本，HiCuts是通过局部优化的方法在每个结点选择哪一维和切割多少份来建立决策树，而Hyper-Cuts算法允许每一步选择多个维度进行切割，其结果是树的宽度变大，深度减少。例如对表1中前5个规则所建立的决策树如图1所示(只选择源/目的端口)，可以看到对规则集端口域采用HyperCuts算法切割后，决策树的深度从3变成2了。
((a)X轴与Y轴分别表示表1中规则R1至R5所代表的源端口域与目的端口域，(b)(c)圆矩形框表示树的内部结点，长方形框表示树的叶子结点)现在，这几类算法都能在FPGA中实现，文献是基于分割算法在FPGA中的实现，为了避免分割的子集过多，该文献对Independent Sets algorithm 进行改进，提出了coarse-grained独立集合算法，该算法把原始规则集划分为若干个coarse-grained独立集合，进行并行搜索，剩下的规则建立cross-producting表进行查询。由于对独立集合算法进行了改进，可以在coarse-grained中存放更多的规则，这样规则子集数就减少了，在Xilinx Virtex-5FPGA上实现结果表明，在消耗较少片内资源情况下，在单个FPGA芯片中能够存储10K的实时规则，在最小报文长度为40字节时，可以维持80Gbps的吞吐量。
文献把基于分割算法与决策树算法结合起来，即先把规则集分割成若干个子集，再对各个子集分别建立决策树，当报文达到时，可以对各个决策树进行并行搜索。为了使对规则的划分达到最优，作者采用范围到点转换(range-point conversion)的思想，也就是F维空间中的一个超矩形能够在2F空间中转换成一个点。从计算几何的角度来看，每个D维分类规则可以看作是D维空间中的一个超矩形，也就是2D空间中的一个点，再用组合优化的方法把这些点划分成不同的集合，为了使划分达到近似最优，使用模拟退伙的方法，在各个集合之间进行相应的规则调整。当近似优化划分完成后，对每个子集用Hyper-Split算法分别建立决策树，再把每棵决策树映射到专有的流水线上，由于这个设计消耗的资源较少，多个这样的机制能够在单个FPGA中实现，达到更高的吞吐量。
3 改进的HyperCuts算法在FPGA中的实现虽然HyperCuts算法对HiCuts有很多改进，但是在建立决策树时，虽然能减少树的深度，但并没有消除规则复制，从图2中我们可以看到，在两棵决策树中，规则R1、R2和R4都得复制到它们多个孩子结点中。通过观察可以发现，规则复制有两个来源，一是不同的规则之间相互重叠，上例中R1与R3、R5都重叠，无论怎么切割，R1都要复制到包含R3与R5的结点中去;二是在每个维度上进行均匀切割，如R2与R4都要复制一次，虽然它们没有与任何规则相重叠。需要说明的是第二点对用前缀表示的IP地址来说并不存在，因为IP地址查找是从最高有效位到最低有效位，等同于均匀切割。针对上面的问题，我们提出了两个优化的方法(图2)，一是把需要复制到多个孩子结点的规则，存储到附加在内部结点的一条链中，这个链叫做内部规则链，例如上面的R1，就可以把它选出来放在附加在根结点中的规则链中;第二种方法叫做精确范围切割，当我们对端口域进行切割时，选择能导致最小复制的切割点，重新选择切割点后，R2与R4就不用复制了。
3.1 决策树的建立
结合上面两种优化思想，用以下步骤来建立决策树，首先，从根结点开始，根结点包含了规则集中的所有规则，对决策树结点进行递归地切割，直到叶子，叶子结点包含规则小于等于预先定义的参数binth。在每个内部结点，需要计算出对哪些维进行切割，每一维切割多少份，规则切割次数的上限为64，所以每个内部结点有2、4、8、16、32或64个孩子。对于端口域需要寻找精确的切割点，而不是切割多少份，可以限定端口域最大的切割数为2。因此没有对协议域进行切割，因为在实时规则集中，前四维就可以满足分类要求了。当选择哪些维进行切割和在源、目的IP地址上切割多少份时，标准与HiCuts和Hyper-Cuts算法一样，不同之处在于，当选择端口域进行切割时，选择的切割点能导致最少规则复制;当切割方法决定下来后，把在当前结点中复制次数最多的规则挑选出来，加到当前结点的内部规则链中，直到链中规则数达到上界binth为止。
3.2 决策树映射到流水线
为了把决策树映射到流水线去，流水线每一阶段需要的存储大小都需要在FPGA实现之前确定，一般采用的方法是，把决策树相同层次上的结点映射到单独的阶段中去，由于存储分布在每个阶段变化很大，如果在每个阶段分配最大的存储量，将造成浪费。可以考虑把决策树映射到线性流水线中去，达到在每个阶段平衡存储分布的目的，同时还可以维持每个时钟周期处理一个报文的吞吐量。由于在这种体系中存在着两种流水线组织，因此，不仅在树流水线中，而且也要规则流水线中考虑各个阶段的存储分布情况，规则流水线中每个阶段需要的存储量取决于树的结点数，所以树到流水线映射的方式中，既要平衡存储分配情况，也要平衡各个阶段的结点分布情况。在把决策树映射到线性流水线的过程中，可以考虑把同一层的结点映射到流水线的不同阶段上去，这就为树结点映射提供了更多的灵活性，这样在每个阶段中能平衡存储和结点分布，需要的一个约束是，如果在决策树中结点A 是结点B的祖先，则A映射到的阶段要先于B的映射。
3.3 搜索过程
当报文达到树流水线的某个阶段进行存储访问时，它同时也得到了与当前树结点相联系的规则链指针，报文利用这个指针与该规则链中的所有规则进行匹配，由于FP-GA提供了足够的字宽，每条规则作为一个字存储在规则流水线的某个阶段上。在规则流水线的某个阶段上，报文利用指针找到一个规则，并用报文头部与该规则进行比较，对不同的域，可采用不同的比较方法，如范围、前缀、定值比较。当它在当前规则流水线阶段找到匹配的规则后，遍历过程并没有结束，它需要记下当前规则优先级，以便与下一个匹配规则相比较。
3.4 规则更新
当有规则需要添加或删除时，也就是规则更新，一般采用增量更新的方法，这种方法消耗存储空间较少，但是频繁的添加与删除操作将导致决策树的不稳定，最终得对决策树进行重建。这里用文献中的write-bubbles方法，即通过插入write-bubbles到各自的流水线上，可以在硬件中实现即时更新(即在更新过程中，分类操作并没有停止)。然而，大规模的改变数据结构需要更有效方法，即缓存备份，这个方法需要建立额外的流水线来存放需要更新的数据，当这个流水线准备好了以后，与需要更新的流水线进行交换，这种方法牺牲了FPGA中的逻辑与RAM，但是带来了更有效的即时更新。
4 实验结果
实验所用分类规则是访问控制链规则(aclnum)，规则个数从100 到50000， 可以从网站：http：//www.arl.wustl.edu/～hs1/PClassEval.html中下载得到。
例如，acl10K表示是由classbench在acl种子文件下产生的10000条件规则，实验中用到了num 数为100、1K、5K、10K的4种规则集。由于这个算法主要是在Hyper-Cuts算法中做了相应的改进，所以对这两种算法在两个参数上进行了比较，一是每个规则消耗的存储大小，主要用来说明算法的可扩展性;二是决策树的高度，用来指出树流水线的阶段数。比较结果从中可以看到，随着规则数的增加，每个规则所需要的存储空间基本上保持不变，这说明了整个存储空间需求与存储规则数呈线性增长关系，易于扩展;同时，由于优化了切割方法，决策树的深度也降低了，减少了报文遍历决策树的延迟。FPGA器件采用当前比较先进的Xilinx Virtex-6，型号是XC6VSX475T，它包含7640Kb分布式RAM 和38304Kb的块RAM，时钟频率可达到115.4MHZ，其资源消耗，两种算法实现结果，其中效率这一项表示为吞吐量除以每个规则消耗的存储空间，主要用来说明时间与空间的平衡度问题。
5 结束语
随着网络带宽的快速发展，线速多维报文分类问题成为了设计下一代网络处理设备的主要挑战，传统的软件算法已经无法满足需要。本文针对HyperCuts算法中规则复制的两个来源进行了相应改进，解决了该算法存储需求过多的缺点，基于FPGA的实验结果表明，改进后的算法能够在单个芯片上能够支持10K的规则，同时在报文长度为40字节的情况下能维持100Gbps的吞吐量。
