学位论文 > 优秀研究生学位论文题录展示
BGP协议中正则表达式匹配系统的研究与软硬件实现
作 者: 蓝维洲
导 师: 朱杰
学 校: 上海交通大学
专 业: 电路与系统
关键词: 正则表达式 路由应用 嵌入式 硬件加速
分类号: TP368.1
类 型: 硕士论文
年 份: 2010年
下 载: 39次
引 用: 0次
阅 读: 论文下载
内容摘要
正则表达式是一种热门的字符匹配技术,在BGP路由协议中得到了重要的应用,本文的研究内容的是如何提高正则表达式的匹配速度。在BGP路由协议中,正则表达式通过软件实现的方式用于路由信息过滤,但大量的过滤事务和自身效率问题在一定程度上影响了BGP的性能,如何提高正则表达式的匹配速度是解决问题的关键。在这样的项目需求下,本研究课题应运而生。经过对国内外关于正则表达式的实现技术进行了调研,本文提出了一种新的正则表达式实现技术,它以BGP网络路由协议的应用为背景,以嵌入式平台为运行环境,采用了POSIX正则表达式库的软件算法,结合软件平台的灵活和硬件平台的高效,使得嵌入式Linux软件系统和FPGA硬件协同工作,通过硬件加速的方式完成了对正则表达式的匹配。具体实施中,系统被划分成了软件系统模块、硬件系统模块和负责软硬件通信的接口等三个组成部分。输入的正则表达式和字符串首先进入软件系统模块,它基于嵌入式Linux软件系统实现,结合堆栈技术,把正则表达式编译成为机器能识别并执行的执行码指令,并生成fastmap数据。因为软件系统模块和硬件系统模块的实现平台不同,运行速度级别也有差异,故通信接口负责它们之间的数据传输。硬件系统模块基于FPGA实现,结合堆栈技术,根据得到的执行码、字符串和fastmap数据来完成正则表达式的匹配计算,得到最终是否匹配的结果。在整体设计中,系统具有“硬件加速”、“默认使用最短匹配原则”和“放弃计算匹配细节”等独到的设计特点,系统内部高效运作,很好地完成了设计任务。文章在最后给出的逻辑测试和性能测试证明,系统不仅很好地完成了设计逻辑,并且拥有良好的加速效果,表明了本次科研设计是成功的。本文的创新和贡献在于:(1)总结了当前各种正则表达式的实现技术,结合了软件解决方案和硬件解决方案的优点,创新出软硬件协同工作的解决方案。(2)在嵌入式领域上提高了正则表达式的匹配速度,有力地支持了路由器等设备,拓展了正则表达式在嵌入式平台上的应用领域。
|
全文目录
摘要 5-7 ABSTRACT 7-13 第一章 绪论 13-17 1.1 课题研究背景 13 1.2 正则表达式的发展 13-14 1.3 嵌入式系统的发展 14-15 1.4 选题意义与研究方法 15-16 1.5 论文组织 16-17 第二章 正则表达式现状研究 17-22 2.1 正则表达式语法规则 17-19 2.2 正则表达式实现的基本原理 19-20 2.3 正则表达式软件实现的相关研究 20-21 2.4 正则表达式硬件实现的相关研究 21 2.5 本章小结 21-22 第三章 系统整体设计 22-33 3.1 系统应用背景和方案选择 22-23 3.2 系统设计与实现构架 23-25 3.3 执行码 25-32 3.4 本章小结 32-33 第四章 软件系统模块设计 33-53 4.1 软件系统模块概述 33-34 4.2 正则表达式编译 34-47 4.2.1 各执行码操作流程 35-45 4.2.2 maybe_pop_jump 执行码修正 45-46 4.2.3 正则表达式编译小结 46-47 4.3 fastmap 生成算法 47-51 4.4 同内核驱动的数据传输 51-52 4.5 本章小结 52-53 第五章 软硬件交互接口设计 53-61 5.1 交互接口设计 53 5.2 同软件系统模块通信 53-54 5.3 同硬件系统模块通信 54-55 5.4 数据传输时序 55-60 5.5 本章小结 60-61 第六章 硬件系统模块设计 61-76 6.1 硬件系统模块构架 61-62 6.2 数据传输和初始化 62 6.3 匹配计算 62-75 6.3.1 子串管理 63-64 6.3.2 堆栈技术 64-68 6.3.3 总体算法 68-75 6.4 本章小结 75-76 第七章 系统测试 76-89 7.1 测试概述 76-77 7.2 逻辑测试 77-85 7.3 性能测试 85-87 7.4 本章小结 87-89 第八章 全文总结 89-91 8.1 主要结论 89-90 8.2 研究展望 90-91 参考文献 91-93 致谢 93-94 攻读硕士学位期间的研究成果 94
|
相似论文
- 基于WinCE平台的故障分析仪应用程序设计与开发,TP311.52
- 汽车的电动助力转向系统,U463.4
- 面向软件的故障注入工具的研究与实现,TP311.52
- 基于ARM9的Windows CE系统移植,TP316.7
- 基于嵌入式图像处理单元的运动目标跟踪系统研究,TP391.41
- 面向嵌入式超声检测系统的图形接口设计与应用,TP274.53
- 多线阵CCD视觉测量系统的数据采集与处理,TP274.2
- LXI-VXI适配器研制,TP274
- 高性能恒温晶体振荡器温度控制系统的研究,TN752
- 扩招后全日制硕士研究生思想政治教育问题研究,G643.1
- 基于TCP/IP协议的嵌入式图像传输系统接收终端的设计,TP368.1
- 嵌入式中医经脉理疗仪的研究,R197.39
- 数字电视中间件中图形界面引擎的研究与应用,TP391.41
- 碳纳米管复合修饰物电极及其在电分析化学中的应用,O657.1
- 基于windows xp嵌入式系统的心电检测分析仪,R197.39
- 网络传输中的ROI图像编码算法研究,TN919.81
- 基于嵌入式系统钻孔成像装置的研究,P634.3
- 交叉杆型并联机床运动学及Kane动力学研究,TH113
- 基于嵌入式Web技术的动态应变仪研究与实现,TP368.1
- 基于ARM&Linux的嵌入式安防控制系统的研究,TP277
- 一体化能量回馈电梯驱动控制系统实现,TP273
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 微型计算机 > 各种微型计算机 > 微处理机
© 2012 www.xueweilunwen.com
|