学位论文 > 优秀研究生学位论文题录展示

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

相似论文

  1. 基于WinCE平台的故障分析仪应用程序设计与开发,TP311.52
  2. 汽车的电动助力转向系统,U463.4
  3. 面向软件的故障注入工具的研究与实现,TP311.52
  4. 基于ARM9的Windows CE系统移植,TP316.7
  5. 基于嵌入式图像处理单元的运动目标跟踪系统研究,TP391.41
  6. 面向嵌入式超声检测系统的图形接口设计与应用,TP274.53
  7. 多线阵CCD视觉测量系统的数据采集与处理,TP274.2
  8. LXI-VXI适配器研制,TP274
  9. 高性能恒温晶体振荡器温度控制系统的研究,TN752
  10. 扩招后全日制硕士研究生思想政治教育问题研究,G643.1
  11. 基于TCP/IP协议的嵌入式图像传输系统接收终端的设计,TP368.1
  12. 嵌入式中医经脉理疗仪的研究,R197.39
  13. 数字电视中间件中图形界面引擎的研究与应用,TP391.41
  14. 碳纳米管复合修饰物电极及其在电分析化学中的应用,O657.1
  15. 基于windows xp嵌入式系统的心电检测分析仪,R197.39
  16. 网络传输中的ROI图像编码算法研究,TN919.81
  17. 基于嵌入式系统钻孔成像装置的研究,P634.3
  18. 交叉杆型并联机床运动学及Kane动力学研究,TH113
  19. 基于嵌入式Web技术的动态应变仪研究与实现,TP368.1
  20. 基于ARM&Linux的嵌入式安防控制系统的研究,TP277
  21. 一体化能量回馈电梯驱动控制系统实现,TP273

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 微型计算机 > 各种微型计算机 > 微处理机
© 2012 www.xueweilunwen.com