基于FPGA的报文分类技术

2015-05-04 08:08:10王敏,邰铭
计算机工程与设计 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查看全文

猜你喜欢
规则分类方法
撑竿跳规则的制定
数独的规则和演变
分类算一算
让规则不规则
Coco薇(2017年11期)2018-01-03 20:59:57
教你一招:数的分类
TPP反腐败规则对我国的启示
用对方法才能瘦
Coco薇(2016年2期)2016-03-22 02:42:52
四大方法 教你不再“坐以待病”!
Coco薇(2015年1期)2015-08-13 02:47:34
捕鱼