蔡艳婧 孔苏鹏 程 实 王则林*

1(江苏商贸职业学院电子信息学院 江苏 南通 226001) 2(南通大学信息科学技术学院 江苏 南通 226019)

0 引 言

包匹配算法是对通过路由器的数据包进行识别，从而可以为互联网提供访问控制，提高网络服务质量以及针对不同客户要求提供差异式服务。包匹配算法本质上是一个多维范围匹配问题,根据预定义规则对进入网络或主机数据包的IP头部信息进行比较。IP头字段信息一般包括源IP地址、目的地IP地址、源端口、目的地端口和上层协议类型。每个规则还有一个行为字段，以便对符合匹配的数据包进行相应处理。一般每条规则还有一优先级。对于传入的数据包，如有多条规则与它匹配，数据包则匹配最高优先级的规则。包匹配的性能由内存消耗和内存访问的次数来衡量。

目前，不同的包匹配算法在算法的空间和时间性能之间采用不同的权衡策略。基于哈希表的算法有优越的空间性能，但其时间性能却无法得到保证[1-2]。基于决策树的算法使用决策树把规则库划分为多个线性搜索组[3-4]，此算法的速度和存储性能会根据规则数据库的特点有所不同。EffiCuts使用多个决策树控制内存消耗，但也降低了算法的时间性能[5]。三元内容可寻址存储器(TCAM)广泛用于查找规则。然而，TCAM不能直接处理范围类型的规则匹配，因此需要把范围的规则转换成前缀的规则类型，降低空间效率[6]。RFC[6]是著名的高性能算法之一，其高性能保障是有条件的，通常适用于维数低、规则库规模不大的情形，否则会引起维度灾难，产生规模爆炸问题。……