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

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

doi:10.3969/j.issn.0372-2112.2020.06.013

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss
- Acta Electronica Sinica Vol. 48, Issue 6, Pages: 1132-1139(2020)
- 作者机构：
  
  陆军工程大学通信工程学院,江苏,南京,210000
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2020.06.013
  CLC： TP393.0
- Published Online：25 June 2020，
  
  Published：2020
- 稿件说明：
移动端阅览
SUN Ming-qian, QIAO Lu-feng, CHEN Qing-hua. Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss[J]. Acta Electronica Sinica, 2020, 48(6): 1132-1139.
DOI：

SUN Ming-qian, QIAO Lu-feng, CHEN Qing-hua. Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss[J]. Acta Electronica Sinica, 2020, 48(6): 1132-1139. DOI： 10.3969/j.issn.0372-2112.2020.06.013.

摘要

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

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.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Operator Fusion Method and Hardware Architecture Design Based on Non-Standard Operators

Multi-Hop Clock Synchronization Algorithm and System Implementation Based on IEEE 802.1AS

An Improved Attention Mechanism Algorithm Model and Hardware Aceleration Design Method

Verification of FPGA Encryption Protection Design Based on Laser Injection

Design and Optimization of Target Detection Accelerator Based on Winograd Algorithm

Related Author

WANG Ying

GAO Lan

ZHANG Zhe

LIU Xin

WU Yi-xiong

ZHANG Wei-gong

ZHAO Guo-feng

WEI Rui-peng

Related Institution

Faculty of Software Technologics, Shanxi Agricultural University

School of Mathematical Science, Capital Normal University

College of Information Engineering, Capital Normal University

School of Communications and Information Engineering， Chongqing University of Posts and Telecommunications

School of Mathematical Science， Capital Normal University

⁰