电子技术
電子技術
전자기술
ELECTRONIC TECHNOLOGY
2014年
9期
24-27
,共4页
正则表达式%游程编码%有穷确定型自动机%现场可编程阵列
正則錶達式%遊程編碼%有窮確定型自動機%現場可編程陣列
정칙표체식%유정편마%유궁학정형자동궤%현장가편정진렬
regular expression%run length encoding (RLE)%DFA%FPGA
目前，面向网络流实时处理的正则表达式匹配技术面临两方面的挑战：一方面，复杂或大规模规则集会导致DFA存储空间爆炸的问题；另一方面，传统计算机的串行DFA匹配技术很难满足对高速主干网的线速深度包检测。本文提出了一个基于改进游程编码的DFA压缩算法，并在FPGA上高效实现了该压缩DFA的匹配引擎。测试结果表明规则集的单个DFA的吞吐率均大于800Mbps，在FPGA块内存最大利用率情况下的理论最大吞吐率达到49.5Gbps。
目前，麵嚮網絡流實時處理的正則錶達式匹配技術麵臨兩方麵的挑戰：一方麵，複雜或大規模規則集會導緻DFA存儲空間爆炸的問題；另一方麵，傳統計算機的串行DFA匹配技術很難滿足對高速主榦網的線速深度包檢測。本文提齣瞭一箇基于改進遊程編碼的DFA壓縮算法，併在FPGA上高效實現瞭該壓縮DFA的匹配引擎。測試結果錶明規則集的單箇DFA的吞吐率均大于800Mbps，在FPGA塊內存最大利用率情況下的理論最大吞吐率達到49.5Gbps。
목전，면향망락류실시처리적정칙표체식필배기술면림량방면적도전：일방면，복잡혹대규모규칙집회도치DFA존저공간폭작적문제；령일방면，전통계산궤적천행DFA필배기술흔난만족대고속주간망적선속심도포검측。본문제출료일개기우개진유정편마적DFA압축산법，병재FPGA상고효실현료해압축DFA적필배인경。측시결과표명규칙집적단개DFA적탄토솔균대우800Mbps，재FPGA괴내존최대이용솔정황하적이론최대탄토솔체도49.5Gbps。
DFA for regular expression matching has the advantage of speed, however, it has the disadvantage of space explosion caused by the complex semanteme of rule or the large-scale rule set. This disadvantage seriously constrains the application of regular expression matching based on network flow which requires wire-speed matching packages. This paper proposes a new algorithm using an improved run length encoding (iRLE) to compress the DFA memory space and efficiently implement a matching engine for the compressed DFA on FPGA. The experimental results show that the throughput of one DFA is larger than 800Mbps and the theoretical maximum throughput reaches 49.5Gbps in the case of maximum utilization of FPGA block memory.
