[报文,技术]基于FPGA的报文分类技术研究

《[报文,技术]基于FPGA的报文分类技术研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于FPGA的报文分类技术研究引言随着快速增长的网络链路速率与分类规则的增多，多维报文分类问题成为设计高速路由器的一个基本挑战。例如，当主干网链路速率达到80Gbps时，在报文长度为40字行时，需要每4ns内处理一个数据报，这个速度用现在的软件算法不可能实现。为了满足以上网络速率的需要，研究人员寻求硬件上的解决方案，三态内容存储器(ternarycontentaddressablememory-TCAM)是一个不错的选择，它能够对输入的关键字进行并行查找，最大的优点是分类速度快，但也有如下一些缺点，如存储面积大、价格高，特别是TCAM不支持直接的范围匹配等。另一方面，由于FPGA具

2、有可重构性和并行性，结合了软件的灵活性与硬件的高效性，使它成为实现实时网络处理引擎一个很好的选择,现在，研究人员已经开始在FPGA上实现一些现有分类算法，可以达到很高的吞吐量，由于存储需求过多，这些算法很少有能够支持大的规则集(超过10K)。本文主要针对基于决策树类的分类算法在FPGA中的实现做了深入研究，解决了在规则集较大的情况下对报文进行快速分类的问题。1分类算法的定义及评估方法1.1分类算法的定义报文分类问题有许多定义，它们基本上是等价的，描述如下：报文头部H包含K个域,分别表示成H[l]、一条过滤规则F相应地也具有K个域，其中F[i](F的第i部分)是H[i]的正则表达式，

3、如果对任意的H[i]满足正则表达式F[i],则称报文P与规则F相匹配°对具有N条过滤规则的分类器R来说，为了解决同一个报文与分类器R中多条规则相匹配的问题，在定义过滤规则F时，对每条规则指定了一个优先级，当有多条规则与报文头部匹配时，选择一个优先级最高的作为最终匹配规则。与每条规则相关联还有一个动作，它指出了当报文与此规则相匹配时，下一步所执行的操作，一个包含10规则的简单分类器。也可以从计算机几何中的点定位问题来看待多维报文分类问题，一个D维的分类规则相当于D维空间中的一个超矩形，D维空间中的N个规则至多可构成(2N-DD个互不重叠的超矩形，而一个报文则相当于D维空间中的一个点，

4、所以，多维报文分类转化为找到包含这个点的超矩形。由此可得到，多维报文分类的时间复杂度为0(logW，空间复杂度为0(ND),或是在时间度为0(logD-lN)的情况下，空间复杂度为0(2。从上面的分析可以看到，多维报文分类问题是一个非常复杂的问题，幸运的是，现实情况要比这好，真实的分类器没这么复杂，它们有一些自身特点，我们可以在实际中加以利用，可以使分类算法得到简化c1.2分类算法的评估方法由于IP分类问题可以抽象成一个查找表项巨大的多关键字查找问题，因此衡量一个算法好坏的关键是查询速度快，再就是用分类规则来构建查找表数据结构时所占内存要少。考虑到分类算法自身的特点，其它评估方法还

5、有过滤规则的插入与删除速度快，维数(查找中关键字个数)易扩展以及能够根据规则中各个域的不同表现形式，支持多种查询(匹配)方式等。总的来说，算法的关键是怎么找到时间与空间的平衡点。2现有的分类算法现有的分类算法很多，文献对各类算法进行了总结，并对每种类型的算法，列举出了相关的例子;文献根据分类算法对规则进行预处理情况，把它们分为基于分解、基于分割和基于决策树3种情况。基于分解算法的主要思想是对报文头部的每个域进行独立的搜索，最后把每个域查询结果结合起，就可得到最终匹配规则，该类型的算法适合于硬件实现，典型代表是平行位向量(parallelbitvector)(BV)算法。基于分割算法

6、的主要思想是把原来的规则集划分为若干个子集，每个子集中的规则在单个或多个域之间是没有重叠的，独立集合算法(independentsetsalgorithm))就属于这类。我们知道，对于有N条分类规则的D维分类器，算法所需要的空间复杂度为0(ND),现假设把规则集R均匀地划分为K组，每组有N/K个规则，划分后的空间复杂度为0(K(N/K)D),所以通过规则集划分后，空间复杂度减少为原来的LKA1。算法而临的主要挑战是独立规则集划分个数的不确定性和过多。决策树类的代表算法是HiCuts,它通过对分类器的预处理，建立决策树这种数据结构,树的根点代表整个搜索空间，它包含了规则集中的所有规则

7、，对决策树中的每个内部点，都递归地进行如下操作，根据预先定义的某种标准，选择在某一维方向上，相等地切割多少份，直到该结点所包含的规则数少于预先定义的某个定值为止，不再进行切割，该结点为叶子结点。每当有报文达到时，对决策树进行遍历，找到叶子结点，由于叶子结点中的规则数较少，可以进行线性搜索，找到最佳匹配规则。Hi-Cuts算法的主要缺点是由于对搜索空间进行了切割，带来了规则的复制，增加了存储空间。HyperCuts算法是Hi-Cuts的改进版本，HiCuts是通过局部优