电子学报 ›› 2020, Vol. 48 ›› Issue (6): 1132-1139.DOI: 10.3969/j.issn.0372-2112.2020.06.013

• 学术论文 • 上一篇    下一篇

一种无匹配时间损耗的DFA压缩算法的研究与实现

孙明乾, 乔庐峰, 陈庆华   

  1. 陆军工程大学通信工程学院, 江苏南京 210000
  • 收稿日期:2019-07-29 修回日期:2019-11-17 出版日期:2020-06-25
    • 通讯作者:
    • 乔庐峰
    • 作者简介:
    • 孙明乾 男,1995年出生于山东-城,现为陆军工程大学通信工程学院硕士研究生.主要研究方向为网络安全、高性能交换机和路由器相关技术. E-mail:sunmq1995@163.com
      陈庆华 男,1976年出生于湖北红安,现为陆军工程大学通信工程学院副教授.主要研究方向为交换技术和通信网络. E-mail:whitenny@126.com

Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss

SUN Ming-qian, QIAO Lu-feng, CHEN Qing-hua   

  1. Institute of Communication Engineering, Army Engineering University of PLA, Nanjing, Jiangsu 210000, China
  • Received:2019-07-29 Revised:2019-11-17 Online:2020-06-25 Published:2020-06-25

摘要: 高性能深度包检测系统使用确定型有穷自动机DFA(Deterministic Finite Automata)来执行数据包的检测过程.然而,DFA所带来的存储消耗问题使其难以适用于片内资源稀缺的FPGA.目前已存在多种算法着眼于解决DFA的空间爆炸问题,但是其在带来较好压缩率的同时,也在一定程度上影响到了系统的检测速度.本文提出了一种无匹配时间损耗的DFA压缩算法,并在此基础上,基于FPGA硬件平台,设计实现了单个DFA匹配引擎.实验测试结果表明,本文所设计的算法,在未影响整个系统匹配性能的前提下,可以实现10%~30%左右的压缩率.

关键词: 深度包检测, DFA, 存储压缩, FPGA

Abstract: Start-of-the-art deep packet inspection system uses deterministic finite automata (DFA) algorithms to perform regular expression matching.Nevertheless,the storage consumption problem caused by DFA make it difficult to apply to FPGA with scarce on-chip resources.At present,there are many algorithms aiming at solving the space explosion problem of DFA,but it affects the detection speed of the system to some extent while bringing better compression ratio.In this paper,a DFA compression algorithm without matching time loss is proposed.Based on the hardware platform of FPGA,a single DFA matching engine is designed and implemented.Experimental results show that the algorithm can achieve a compression rate of 10% to 30% without affecting the matching performance of the whole system.

Key words: deep packet inspection, DFA, storage compression, FPGA

中图分类号: