一种基于规则分解映射的防火墙规则匹配算法

Rule matching mapping algorithm for firewall based on rule decomposion mapping

并行树搜索(PTS)算法是报文分类领域中较为优秀的算法之一,但它需要构建大量的external nodes,且只支持以前缀形式表示的规则,因此其匹配效率及适用范围都受到了很大的影响。针对这一问题,提出一种基于规则分解映射的规则匹配算法RMBRDM。RMBRDM算法首先按照启发式方法选取标准维;然后根据规则分解映射和标准维对相关规则进行分解;最后建立一棵二叉决策树。理论分析和仿真实验均表明,RMBRDM算法不仅支持以范围形式表示的规则,且时空性能优于PTS算法。

Parallel Tree Search （PTS） is one of the best algorithms among the existing algorithms for rule matching. However, PTS needs to construct so many external nodes and only supports rules with prefixes. The authors proposed an algorithm named RMBRDM for rule matching based on rule decomposing. At first, RMBRDM employed heuristic methods to choose a standard dimension. And then rules could be decomposed according to rule decomposing mapping and the standard dimension. At last, a binary decision tree could be buih. Algorithm analysis and simulation results show that RMBRDM can support rules with ranges and the performance of RMBRDM is better than that of PTS.