规则的快速查找

本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。

msn:[email protected]

来源：http://yfydz.cublog.cn

1. 前言
 
防火墙的规则查找对防火墙的性能有很大影响，这是对通过防火墙的每个新连接数据包都要进行的操作，在防火墙的规则数很多的情况下，如果处理不好，防火墙的性能会急剧下跌，因此如何快速搜索与该包对应的规则也是提高防火墙性能的一个重要课题。
 
2. 规则分类
 
一般提高规则搜索速度的方法包括对规则进行分类，常用的分类方法通常是HASH和树结构。
 
2.1 HASH
 
HASH是把规则的匹配条件字段综合作为一个输入进行HASH，这样就可以把不同的规则分开。不过HASH有不少问题要进行处理，比如如何使一个网段内的不同地址都要HASH到同一个数值上。
 
2.2 树
树结构是用得更多的一个处理方式，就是将匹配条件按每个条件分层处理，有多少个条件就有多少层，每层的节点就是一个具体的条件值，这样可以使搜索次数从N1*N2...*Nm降低到N1+N2+...+Nm。
 
2.3 混合模式
 
混合模式就是HASH和数同时使用，因为某些条件参数的可能取值也会很多，全部查找也比较困难，就需要事先HASH一下进行处理。
 
2.4 优点和缺点
 
优点明显就是显著降低了搜索的规则数；缺点在于一是需要增加内存，这是以空间换时间的方法，不过以现在的内存的价钱看是非常值得的；二是HASH函数设计问题；三是规则执行顺序问题；四是匹配条件标准化问题，匹配条件的数量是固定的，会牺牲掉一些特殊匹配条件。

3. Linux/netfilter
 
linux下的防火墙netfilter使用规则是顺序执行的，因为其开放的匹配架构，可以设计各种各样的匹配条件，如POM中的各种匹配模块，因此很难使用上面说的方法来处理，不过有个开源项目nf-HiPAC(http://www.hipac.org)正在将netfilter规则处理树形话，也已经可以支持很多匹配。
 
虽然netfilter架构本身很难树化，但可以通过新链和新的匹配条件处理来提高规则效率。如类似checkpoint，其规则是加在各个网卡上的，从netfitler的角度看就是先根据数据的进出网卡建立新的规则链，每个网卡的数据就直接进入其中一条链处理，不用再转到其他链，实际是通过 iptables规则来构造树形结构而不是由netfilter内部来实现树；其次，由于可以定义新的匹配，就可以增加大地址、大端口的匹配条件，可以同时匹配很多地址或端口，这样就不用分成很多单一地址单一端口的“小”规则，也相当于把匹配空间从乘法降低为加法。
 
4. 结论
 
规则的快速查找主要还是要靠空间换时间的方式进行，netfilter内部虽然比不直接支持树型查找，但可以用外部处理来进行弥补。