论文部分内容阅读
依赖于正则表达式匹配的深度包检测技术因准确率高成为网络流分类广泛使用的技术.为了能在线性时间内对网络流进行快速分类,需采用时间高效的确定性有限自动机(DFA)匹配引擎,但DFA存在空间爆炸问题,无法满足实际需求.为了解决这个问题,本文从DFA中每个状态在不同的输入字符转换下到达的目的状态特性出发,提出了一种基于默认目的状态和位图技术的DFA压缩算法(对应的自动机模型称为DBDFA),该算法能够将有着相同目的状态的多条转移边压缩为只需一个默认目的状态或只需一个时空高效的位图.实验表明,DBDFA能达到平均99%的压缩效率,优于目前大多数的DFA压缩技术,且压缩后的总体匹配效率是原有DFA的3~5倍,这是目前大部分的压缩技术所不能达到的.
Deep packet inspection, which relies on regular expression matching, has become a widely used technique for network flow classification because of its high accuracy.In order to classify network flows quickly in linear time, a time-efficient deterministic finite automaton (DFA) Matching engine, but there is a space explosion problem in DFA, which can not meet the actual demand.In order to solve this problem, this dissertation starts from the state characteristics of each state in DFA that arrive under different input characters, Bitmap technology DFA compression algorithm (corresponding to the automaton model called DBDFA), the algorithm can be the same destination state of multiple transitions to only one default destination state or only a space-time efficient bitmap. Shows that DBDFA achieves an average compression efficiency of 99%, which is better than most of the current DFA compression techniques, and the overall compression efficiency is 3 to 5 times that of the original DFA, which is currently not achieved by most compression techniques of.