BGP协议中正则表达式匹配系统的研究与软硬件实现

发布时间：2020-09-16 15:06

　　正则表达式是一种热门的字符匹配技术,在BGP路由协议中得到了重要的应用,本文的研究内容的是如何提高正则表达式的匹配速度。在BGP路由协议中,正则表达式通过软件实现的方式用于路由信息过滤,但大量的过滤事务和自身效率问题在一定程度上影响了BGP的性能,如何提高正则表达式的匹配速度是解决问题的关键。在这样的项目需求下,本研究课题应运而生。经过对国内外关于正则表达式的实现技术进行了调研,本文提出了一种新的正则表达式实现技术,它以BGP网络路由协议的应用为背景,以嵌入式平台为运行环境,采用了POSIX正则表达式库的软件算法,结合软件平台的灵活和硬件平台的高效,使得嵌入式Linux软件系统和FPGA硬件协同工作,通过硬件加速的方式完成了对正则表达式的匹配。具体实施中,系统被划分成了软件系统模块、硬件系统模块和负责软硬件通信的接口等三个组成部分。输入的正则表达式和字符串首先进入软件系统模块,它基于嵌入式Linux软件系统实现,结合堆栈技术,把正则表达式编译成为机器能识别并执行的执行码指令,并生成fastmap数据。因为软件系统模块和硬件系统模块的实现平台不同,运行速度级别也有差异,故通信接口负责它们之间的数据传输。硬件系统模块基于FPGA实现,结合堆栈技术,根据得到的执行码、字符串和fastmap数据来完成正则表达式的匹配计算,得到最终是否匹配的结果。在整体设计中,系统具有“硬件加速”、“默认使用最短匹配原则”和“放弃计算匹配细节”等独到的设计特点,系统内部高效运作,很好地完成了设计任务。文章在最后给出的逻辑测试和性能测试证明,系统不仅很好地完成了设计逻辑,并且拥有良好的加速效果,表明了本次科研设计是成功的。本文的创新和贡献在于:(1)总结了当前各种正则表达式的实现技术,结合了软件解决方案和硬件解决方案的优点,创新出软硬件协同工作的解决方案。(2)在嵌入式领域上提高了正则表达式的匹配速度,有力地支持了路由器等设备,拓展了正则表达式在嵌入式平台上的应用领域。
【学位单位】：上海交通大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP368.1
【部分图文】：

原理图,自动机,原理图,正则表达式

图 2-1 构造自动机原理图Fig. 2-1 principle graph of making automaton由正则表达式构造出自动机的过程，如图 2-1 所示。首先，正则表达式被解树，然后再转换成非确定有限自动机。目前，从解析树构造非确定有限自用方法有汤姆逊（Thompson）构造法[9]和格拉施科夫（Glushkov）构造法[9非确定有限自动机后，可以直接用它进行文本匹配，也可以将它确定化和构造出相应的确定有限自动机，然后用确定有限自动机进行文本匹配。3 正则表达式软件实现的相关研究目前的软件平台上，C、C++、Java 等编程语言都有支持正则表达式的语法，各有优缺点，在这些实现方法中，不少方法用到了自动机理论的知识，实现正则表达式的算法，都是可以值得借鉴的。以下是支持正则表达式的和软件库：

框架图,框架图,系统设计,正则表达式

通大学工程硕士学位论文第三章程中，只要发现有部分字符串符合正则表达式的规则，即宣告匹配成功，而不寻找符合要求的、长度更长的字符串；“放弃计算匹配细节”指的是放弃匹配细计算，诸如不计算出“字符串中共有多少部分的字符信息符合要求”等。以上设计特点，都是结合课题应用背景需求，减少计算，为了更好地实现加速匹配。系统设计与实现构架在本次设计中，采用软件和硬件相结合的方式来实现系统功能，软件平台采用嵌 Linux 系统，它能提供很好的软件开发平台，而硬件平台采用 FPGA 芯片，它程的特点，提供了硬件开发过程中能不断调试的机会，并且自身优良的性能可速实现正则表达式的匹配计算。

工作流程图,软件系统,工作流程图,系统模块

工程硕士学位论文第四章软件系统模块设计系统模块概述上一章节介绍，我们得知整体系统设计划分为三个组成部分，本章节件系统模块进行介绍。系统模块是基于 Linux 操作系统实现的，属于 Linux 操作系统的应用程其被封装成 regcomp 函数模块，所实现的功能是提供调用接口给用户的编译和 fastmap 数据生成、同硬件系统模块通信。

【参考文献】