一种基于切割映射的规则冲突消除算法

A Filter Conflicts Resolving Algorithm Based on Cutting Mapping

防火墙规则冲突不仅使规则集变得难于管理,而且会影响报文分类的效率.现有的规则冲突消除算法不能完全消除冲突.针对这一情况,从计算几何角度对规则冲突进行了分析,提出了一种基于切割映射的冲突消除算法.该算法对规则冲突进行了详细的分类,并根据不同的类型消除冲突.算法以两条冲突规则为基本处理对象,在其冲突消除过程中,顺序切割优先级较低的规则的每一维分量.理论分析和测试表明,算法达到了只需增加少量规则即能彻底消除冲突的目的.

Filter conflicts resolving is an important issue for packet classification and network management. On the one hand, to reduce the time spent on packet classlfication, a certain algorithm for resolving filter conflicts should be applied to eliminate all filter conflicts during the preprocessing phase. On the other hand,because of the complexity of firewall filters, when firewall administrators add a filter, the newly added filter may conflict with existing ones. This not only makes filter datahases difficult to manage, but also may lead to security vuluerabilities. Thus a certain algorithm for resolving filter conflicts should also be applied to eliminate all filter conflicts. Several algorithms for resolving filter conflicts have already been proposed but most of them cannot eliminate filter conflicts completely and set restrictions on filters. This paper analyses filter conflicts from the perspective of computational geometry and presents a filter conflicts resolving algorithm based on cutting mapping. The algorithm resolves filter conflicts according to the classification of conflicts. It treats two filters as the basic processed object and sequentially cuts every dimension of the filters that have lower priority. This paper proves the algorithm and experiments verify its good performance.