基于非对称规则的模糊匹配算法的硬件设计

作     者：程心昱 

作者单位：东南大学 

学位级别：硕士

导师姓名：徐平平;李冰;吕耀安

授予年度：2019年

学科分类：0810[工学-信息与通信工程] 08[工学] 081001[工学-通信与信息系统] 

主      题：模糊匹配 非对称规则 内容寻址存储器 流水线结构 UVM 

摘      要：随着互联网的快速发展,网络链路上数据传输速率不断提升,网络链路层对路由器数据报文分发速率的要求也越来越高。路由器数据报文分发的核心是模糊匹配算法,高效实现模糊匹配算法成为提升路由器数据转发速率的关键。因此,本课题提出一种基于非对称规则的模糊匹配算法并完成硬件电路设计来提升路由报文分发速率。本文首先阐述模糊匹配算法在网络数据报文中的作用,对模糊匹配算法及其硬件设计的研究现状和发展趋势进行了分析总结。相较于哈希匹配算法,本文提出的基于双样本空间的多级查找算法不存在地址冲突问题,相较于基于二进制树的匹配查找,查找速度提升了32.4%,具有查找速度快,算法复杂度低的特点。论文提出基于双样本空间的多级查找电路结构,采用并行流水线技术进行优化。本文所提出模糊匹配算法的硬件设计经过UVM验证平台的验证表明,可实现对88比特、88×2比特、88×4三种长度的数据进行模糊匹配操作,当索引数据为88×4比特长度,时钟频率为250MHz的情况下,可实现每秒钟62.5M次搜索,满足所搭载路由器芯片查找匹配速率不低于每秒钟59.52M次查找的要求,当索引为88比特,时钟频率为250MHz时,查找速率可达到每秒钟250M次。经过前端Design Compiler综合实现表明,采用GlobalFoundries的45nm工艺文件下,所设计的硬件电路无时序违例情况,不对存储单元进行综合的情况下,综合面积约为235332μm。最终实验结果表明,所设计的模糊匹配算法的硬件实现能够满足高速网络对匹配速度的要求。本文所提出的模糊匹配算法及其硬件设计可应用于对索引进行模糊匹配的场合,如网络路由器中的查找转发模块,网络防火墙,虚拟专用网络过滤等高级网络应用,具有极大的使用价值。