基于FPGA的报文分类技术
2015-05-04王敏,邰铭
计算机工程与设计 2015年4期
王 敏,邰 铭
(1.信息工程大学 网络空间安全学院,河南 郑州450001;2.信息工程大学数学工程与先进计算国家重点实验室,河南 郑州450001)
0 引 言
随着快速增长的网络链路速率与分类规则的增多,多维报文分类问题成为设计高速路由器的一个基本挑战。例如,当主干网链路速率达到80Gbps时,在报文长度为40字节时,需要每4ns内处理一个数据报,这个速度用现在的软件算法不可能实现。
为了满足以上网络速率的需要,研究人员寻求硬件上的解决方 案,三 态 内 容 存 储 器[1](ternary content addressable memory-TCAM)是一个不错的选择,它能够对输入的关键字进行并行查找,最大的优点是分类速度快,但也有如下一些缺点,如存储面积大、价格高,特别是TCAM不支持直接的范围匹配等。另一方面,由于FPGA具有可重构性和并行性,结合了软件的灵活性与硬件的高效性,使它成为实现实时网络处理引擎一个很好的选择。现在,研究人员已经开始在FPGA上实现一些现有分类算法[2-4],可以达到很高的吞吐量,由于存储需求过多,这些算法很少有能够支持大的规则集 (超过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相匹配。……
登录APP查看全文
