基于FPGA的精确查找研究与设计
发布时间：2021-10-29 01:51
随着经济社会的发展,网络变得越来越普及,互联网已经成为这个社会不可缺少的一部分。而随着网络的普及与发展,也凸显出一系列的问题和矛盾。主要有网络流量的快速增长与现有网络设备的转发处理速度之间的矛盾,还有人们日益增长的对一个安全的网络环境的需求与现有网络环境存在诸多安全隐患之间的矛盾。不管是数据转发的现实需求,还是网络安全的现实需求,对于数据流量关键字段的精确查找都是实现其功能的基础,所以快速的、准确的、低成本的精确查找的实现就显得尤为重要。基于此,本文设计了一种基于可编程逻辑门阵列的精确查找结构。通过借鉴学习基于布隆过滤器的匹配查找,基于正则表达式的匹配查找,和基于已有内容可寻址芯片的查找匹配方法。通过对以上三种实现方式进行理论分析,比较这三种方法实现的难易程度、复杂程度、开发成本、价格成本以及实现效果分析,并通过模拟仿真比较,最终提出了基于布隆过滤器的查找匹配方法。在布隆过滤器的基础上,改造了原先的普通的布隆过滤器,设计了一种适用于硬件维护的并且可删除元素的布隆过滤器,使布隆过滤器经过改造可以适用于查找表设计,并理论计算和实验仿真分析其可删除率;并且设计了一种两级流水的布隆过滤器的实现...
【文章来源】：中国电子科技集团公司电子科学研究院北京市
【文章页数】：79 页
【学位级别】：硕士
【部分图文】：
正则表达式仿真结果
图 2.6 布隆过滤器误检率分析通过公式(2.1)和(2.2)能得出结论，在最好的状况时，可以由 1<来表示误检率的最小值，那么就可以得出有如下的公式：In2nmk （2.3）这时的误检率如下公式： kf 12（2.4）由此得出结论，若误检率的值一定的时候，所需要的 m（二进制向量的长度）与 n（元素的数量）互为比例的增加或减少。工程实现时，在误捡率小至一定的值时，可以近似的认为布隆过滤器可以准确的判定一个元素是否属于某个集合。2.2.2.3 布隆过滤器仿真分析由于布隆过滤器需要进行哈希计算，对于纯软件平台来说，这会大大降低其实现的性能，由于纯软件平台本身的性能相对较低，所以这里对于纯软件实现布隆过滤器不做讨论。
的字段按同样的方法进行计算，然后依次和这个布隆过滤器的比特位进行比较，由此来判断该字段是否属于该集合。并维持一个 hit 信号，当其为 1 时代表其匹配成功，反之则匹配失败。datain 缓存fifo dataout关键字提取64bitCRC（1）CRC（5）..Bloom Filter hit 丢弃图 2.7 一个简单布隆过滤器的实现布隆过滤器查找匹配字段的时序图如下所示，布隆过滤器完成待匹配字段的“编程”写入。对于一个输入的数据 datain（在 datain_val 有效），在等待一定的延时后可以看到，hit 值变为 1，则说明该 datain 匹配于该布隆过滤器，那么则将该数据包放行，而第二个输入 datain 则没有出现 hit 信号为 1 的情况，则说明该datain 不匹配于该布隆过滤器，那么则将该数据包丢弃。
【参考文献】：
期刊论文
[1]一种基于FPGA压缩DFA的高速正则表达式匹配算法[J]. 谭用秋,唐球,谭建龙. 电子技术. 2014(08)
[2]基于FPGA的高速低资源消耗字符串匹配算法[J]. 黄建,徐晶. 微电子学与计算机. 2007(11)
[3]一种将NFA到最小化DFA的方法[J]. 毛红梅,聂承启. 计算机与现代化. 2004(10)
[4]构造正则表达式的简化 DFA 算法[J]. 檀凤琴. 北京航空航天大学学报. 1998(04)
博士论文
[1]下一代互联网的报文标识与查找技术的研究[D]. 孙琼.北京邮电大学 2010
硕士论文
[1]基于FPGA的正则表达式匹配引擎的设计[D]. 温源.哈尔滨工程大学 2009
[2]正则表达式在电信业务处理中的应用研究[D]. 李哲夫.暨南大学 2008
[3]基于正则表达式的深度包检测研究[D]. 张娜.华东师范大学 2007
[4]基于正则表达式技术的信息搜集引擎应用研究[D]. 马俊.电子科技大学 2006
[5]集成化防火墙防护系统[D]. 王皎.电子科技大学 2003
本文编号：3463729
【文章来源】：中国电子科技集团公司电子科学研究院北京市
【文章页数】：79 页
【学位级别】：硕士
【部分图文】：
正则表达式仿真结果
图 2.6 布隆过滤器误检率分析通过公式(2.1)和(2.2)能得出结论，在最好的状况时，可以由 1<来表示误检率的最小值，那么就可以得出有如下的公式：In2nmk （2.3）这时的误检率如下公式： kf 12（2.4）由此得出结论，若误检率的值一定的时候，所需要的 m（二进制向量的长度）与 n（元素的数量）互为比例的增加或减少。工程实现时，在误捡率小至一定的值时，可以近似的认为布隆过滤器可以准确的判定一个元素是否属于某个集合。2.2.2.3 布隆过滤器仿真分析由于布隆过滤器需要进行哈希计算，对于纯软件平台来说，这会大大降低其实现的性能，由于纯软件平台本身的性能相对较低，所以这里对于纯软件实现布隆过滤器不做讨论。
的字段按同样的方法进行计算，然后依次和这个布隆过滤器的比特位进行比较，由此来判断该字段是否属于该集合。并维持一个 hit 信号，当其为 1 时代表其匹配成功，反之则匹配失败。datain 缓存fifo dataout关键字提取64bitCRC（1）CRC（5）..Bloom Filter hit 丢弃图 2.7 一个简单布隆过滤器的实现布隆过滤器查找匹配字段的时序图如下所示，布隆过滤器完成待匹配字段的“编程”写入。对于一个输入的数据 datain（在 datain_val 有效），在等待一定的延时后可以看到，hit 值变为 1，则说明该 datain 匹配于该布隆过滤器，那么则将该数据包放行，而第二个输入 datain 则没有出现 hit 信号为 1 的情况，则说明该datain 不匹配于该布隆过滤器，那么则将该数据包丢弃。
【参考文献】：
期刊论文
[1]一种基于FPGA压缩DFA的高速正则表达式匹配算法[J]. 谭用秋,唐球,谭建龙. 电子技术. 2014(08)
[2]基于FPGA的高速低资源消耗字符串匹配算法[J]. 黄建,徐晶. 微电子学与计算机. 2007(11)
[3]一种将NFA到最小化DFA的方法[J]. 毛红梅,聂承启. 计算机与现代化. 2004(10)
[4]构造正则表达式的简化 DFA 算法[J]. 檀凤琴. 北京航空航天大学学报. 1998(04)
博士论文
[1]下一代互联网的报文标识与查找技术的研究[D]. 孙琼.北京邮电大学 2010
硕士论文
[1]基于FPGA的正则表达式匹配引擎的设计[D]. 温源.哈尔滨工程大学 2009
[2]正则表达式在电信业务处理中的应用研究[D]. 李哲夫.暨南大学 2008
[3]基于正则表达式的深度包检测研究[D]. 张娜.华东师范大学 2007
[4]基于正则表达式技术的信息搜集引擎应用研究[D]. 马俊.电子科技大学 2006
[5]集成化防火墙防护系统[D]. 王皎.电子科技大学 2003
本文编号：3463729
本文链接：https://www.wllwen.com/kejilunwen/dianzigongchenglunwen/3463729.html
