包分类算法研究综述

张杰鑫，张 铮

（数学工程与先进计算国家重点实验室，郑州450001）

1 概述

随着密集型光波复用技术和光纤技术的发展，链路的速率已经能够满足网络数据的持续增长。路由器是十分重要的网络设备，它对每一个数据包要进行很多种操作，包括复杂的分类操作，因此，网络的整体速度越来越受到路由器的处理速度的制约。随着计算机网络的飞速发展，传统网络尽力而为的服务模式已经不能满足用户的需求。互联网服务提供商（Internet Service Provider，ISP）希望网络能够提供更好的服务，特别是对新型业务流的检测与控制有着强烈需求。网络流量异常或者丢包，甚至整个网络的瘫痪，严重影响正常业务流量运行，也严重威胁系统和网络安全，对互联网和个人安全造成了威胁［1－2］。因此，通过有效的包分类技术，检测和控制网络中新型流量，提供不同的服务质量保障，是当前网络运营面临的主要挑战之一［3－4］。研究有效的包分类算法及其实现技术是目前网络技术领域的热门课题［5－6］。本文通过比较基于软件和基于硬件包分类算法，分析了不同算法设计的难点和不足。

2 包分类

2．1 包分类的概念

用一定的分类匹配规则，对数据包进行处理的算法，称为包分类技术。这些规则一般为数据包首部的某个字段或某些字段的组合。首先对数据包进行协议解析和字段抽取操作，然后依据协议类型和分类字段对数据包进行分类。目前，大多采用五元组，或者五元组的各种组合来对数据包进行分类，五元组包括目的地址IP（32bit）、源地址IP（32bit）、目的端口号（16bit）、源端口号（16bit）、和协议类型（8bit）。

图1是一个典型的基于IPV4的五维包分类系统的示意图，其中，宽箭头代表数据包的处理流程；细箭头代表规则集的应用场景。表1则描述了包分类系统存储的规则。首先系统根据输入包的五元组信息与规则进行匹配，然后系统再依据匹配规则的决策对输入包进行相应的处理，如转发、拒绝和丢弃等。

图1 包分类系统

表1 包分类规则示例

包分类规则的表示方式有2种，一种是前缀表示方式，如表1中的表示方式（其中，“＊”是通配符），另一种是范围表示方式。前缀表示方式容易被硬件接受，而且具有特殊的性质，如2个前缀仅有包含和不相交关系，但并不是所有IP段都能用一个前缀表示；范围表示方式虽然可以表示所有的IP段，但是难以被硬件实现［7］。

2．2 规则集特征概述和管理

文献［8］对大量实际的规则集进行了研究，结果表明，实际规则集的规则数目不会太多，规则的协议域通常只有很少的几个取值，端口号的取值范围很广等特征。实际统计结果是所有规则集的实际复杂度均远小于理论复杂度［9］。

通常采用通过简单的单向队列操作、集中管理的方式和分布式的并行方式对规则集进行管理。

2．3 包分类算法评价指标

包分类算法评价指标如下：

（1）时间复杂度：该指标用于定义在执行分类操作时，所需要的步骤数或者循环数的最大边界O（f）。f是一个以规则数目N，维度d和字段宽度W为自变量的函数。

（2）空间复杂度：该指标用于定义在执行包分类操作时，用于保存分类器和相关数据结构所需要存储空间的最大边界O（f）。此指标不仅包括存储规则集本身所占用的内存空间，还包括为实现快速查找所建立的数据结构，以及在查找计算过程中动态分配的空间［10－11］。

（3）更新复杂度：该指标用于定义对分类器进行更新规则集之后，修改数据结构所需要的步骤数或者循环数的最大边界O（f）。

（4）可扩展性：可扩展性不仅包括在纵向上对分类的规则数目上具有可扩展性，在横向上对分类的维数具有可扩展性，而且包括在分类的层次上还应具有可扩展性。

（5）最坏情况下的性能：不能只在平均情况下讨论一个算法的好坏，还应该在最坏情况下分析它的性能。因为有时候平均性能不能完整地反映分类算法的性能，极端情况下算法的性能对于综合评价算法是十分必要的。

3 基于软件的包分类算法

3．1 Grid－of－Tries算法

Grid－of－Tries算法［12］是基于决策树算法的包分类算法，主要解决涉及目的地址和源地址前缀的包分类问题。该算法在有向非循环图的基础上做了改进。虽然其可以消除多余子树，但是它没有彻底解决规则的复制问题。算法使用了一种有效消除规则复制的算法，主要思想是把一条规则仅存储在一个结点中，再用转移指针指向潜在匹配的规则或者规则子集，图2展示了依据表1的算法示意图，虚线指针为目的地址树到源地址树的指针，密集虚线指针为转移指针。

图2 Grid－of－Tries算法示意图

假设N是规则数目，W是目的地址或源地址的位宽，那么Grid－of－Tries算法的空间复杂度为O（NW），时间复杂度为O（W）。虽然Grid－of－Tries算法是地址前缀分类的有效技术，但是它不能延伸到规则的其他字段。

3．2 EGT算法

扩 展 的 树 型 网 格 （Extended Grid－of－Tries，EGT）算法［13］在 Grid－of－Tries算法的基础上进行了改进，通过改变Grid－of－Tries算法的数据结构，使得该算法能够支持多字段查找。EGT算法将Grid－of－Tries算法的转移指针改为跳转指针，跳转指针直接指向所有可能匹配的规则，而不是Grid－of－Tries算法中的最长前缀匹配规则。源地址树的结点指一个规则列表，列表由若干规则组成，规则包含了除地址域外的其他字段。在列表中进行线性查找进而找到最佳匹配。需要注意的是在源地址树中跳转指针直接指向所有可能的规则集。

图3展示了依据表1的算法示意图，密集虚线指针为跳转指针，虚线为源地址树的跳转指针，虚线指针为目的地址树到源地址树的指针。EGT算法的时空复杂度与Grid－of－Tries算法相同，最坏情况下访存次数是O（W2），其中，W是地址位宽。

图3 EGT算法示意图

3．3 HiCuts算法

HiCuts算法［10］采用了切割的算法，从几何角度解决包分类问题，该算法适合应用于范围类型的规则。HiCuts算法使用决策树作为数据结构进行快速搜索。决策树的内部结点存储的不是规则，而是适当的分类导向信息。决策树的外部结点（叶结点）包含一个相对较小的规则子集。一旦输入包到来，HiCuts算法将贯穿决策树，直到一个叶结点。然后在这个规则子集中通过线性查找来找到最佳匹配。在构造决策树时，需要对叶结点内所存储的规则数目进行限制，使其不超过一个常数——binth（即in－threshold）。

图4以表2的源地址（4bit）和目的地址（4bit）为例，当binth＝3时的HiCuts算法示意图，不同颜色的区域代表不同规则的在空间中所占的区域，R1～R9是表2中的9条规则。

图4 HiCuts算法示意图

表2 源地址和目的地址对应关系

HiCuts算法结合了线性查找算法与决策树算法，使得该算法不但具有较好的性能，而且具有也比较高的灵活性。当binth＝N时，算法将会退化为线性查找。当分类维度为d，规则数为N时，算法的时间复杂度为O（d），空间复杂度为O（Nd）。

3．4 Parallel BV 算 法

并行位向量（Parallel Bit－Vector）算法［11］假设所有规则已经按照优先级排序。假设有N条规则，对于规则的每一维最多可以划分出2N＋1个基本间隔，如图5所示。每一维的各个基本间隔都对应一个N位的位向量，向量的每一位对应一条规则。

图5 基本间隔原理

在初始化位向量时，首先将其所有位均被置为“0”，然后将该向量中那些与该基本间隔重合的规则所对应的位全部置为“1”。一旦计算出全部位向量和d个数据结构，那么查找也变得简单。在查找时，因为每一维都有一个数据结构，所以可以独立进行对各维的查找。首先在各维中找到一个位向量，待查找完毕，则一共找到d个位向量。然后，对d个位向量执行“与”操作，进而得到了一个最终的位向量。在此位向量中，所有位为“1”的位所对应的规则都是匹配规则，而最佳匹配规则是与其中最高一个“1”位对应的规则。

该算法的时间复杂度为O（lbN），空间复杂度为O（N2）。该算法也适合于硬件实现。假设内存接口宽度为W，那么访问一个N位向量需要次访存。

3．5 RFC算法

真实规则集包含了大量的结构和冗余，迭代流分类（Recursive Flow Classification，RFC）算法［14］很好解决了这一问题。RFC算法的基本思想是使用多阶段映射的算法，通过这种算法将一个较大的集合映射成多个较小的集合。RFC的映射是一个递归过程，通过映射实现包头中S比特串数据到T（T＜＜S）位eqID的映射（每个阶段映射称为缩减）。RFC算法包含Q个阶段，每一个阶段又包含一系列的并行查找。为了方便查找，RFC算法定义了合并表（Aggreation Table）和段表（Chunk Table）。算法又利用Index在2个表中查找，该Index就是前一阶段查找得到的eqID。经过多个阶段查找，得到一个最终的eqID，并由此eqID指明对输入包的决策动作。RFC算法执行过程如图6所示。当分类维度为d，规则数为N时，时间复杂度为O（d），空间复杂度为O（Nd）。RFC算法拥有较高的吞吐率，但其高效的查找是以内存为代价的，因此，RFC算法面临着内存膨胀的危险，而且RFC算法不支持增量更新，只能重建。

图6 RFC算法执行过程示意图

3．6 元组空间法

元组空间法是利用元组（Tuple）把规则集进行分割，进而到达快速缩短多维查找范围的目的。基本的元组空间法是穷尽查找，文献［15］提出若干利用元组空间法的查找算法。元组定义了规则的某个字段的若干位。

表3给出了一个五维规则集的例子，其中，源地址和目的地址为4bit，源端口号和目的端口号为4bit，协议为8bit，最后一列给出了元组的形式。

表3 五维规则集示例

对于所有使用了元组空间法的包分类算法，对涉及对元组空间或者其一个子集的查找是可以独立进行的，所以，元组空间法是能够并行实现的。然而，待查找的元组空间或者它的子集的大小是无法预测的，所以，采用并行实现是不容易的。采用元组空间法，能够有效地对规则集进行压缩，进而到达节省存储空间的目的。

元组空间法的时间复杂度和空间复杂度均为O（N），当规则集中有许多通配符时，与空间复杂度为的穷尽查找相比，元组空间法更能节省存储空间。

3．7 算法比较

表4列出线性查找（Linear Search）算法、HiCuts算法［10］、并行位向量算法［11］、Grid－of－Tries算法［12］、扩展的树型网格（Extended Grid－of－Tries）算 法［13］、迭代流分类（Recursive Flow Classification）算法［14］和元组空间（Tuple）算法［15］的时间复杂度和空间复杂度分析。假设N为规则数目，W为地址域关键字的长度，d为规则的维度。

表4 包分类算法性能比较

4 基于硬件的包分类算法

4．1 基于三态内容可寻址存储器的包分类算法

三态内容可寻址存储器（Ternary Content Addressable Memory，TCAM）是一种与传统的内容寻址内存（Content Addressable Memory，CAM）不同的三态内容查询的存储器。因其具有操作简单、匹配时间固定和查询速度快等优点而被应用于包分类和路由表查询等领域。TCAM的每一位具有3种状态：0，1和“＊”（通配符），正是因为它具有3种状态的特性使其既可以进行精确匹配，又可以进行模糊匹配。在存储时，TCAM是以表项作为基本的存储单位，表项的地址越低其优先级就越高，而且每一条表项只能被配置成固定位宽。在查询时，TCAM将关键字与所有的表项进行并行匹配，返回优先级最高的表项的地址。

TCAM的查询速度与表项的数目无关，其时间复杂度为O（1）。虽然TCAM具有良好的查询性能，但它也存在不足，TCAM的价格昂贵、集成度低 、能 耗 惊 人［16－17］，更 为 重 要 的 是 ，TCAM 不 能 直接进行非字段和范围字段匹配，并且其每次匹配只能输出一个结果。因此，在设计中必须考虑TCAM的成本、功耗和体积，并充分利用TCAM的每个比特［18］。

4．1．1 基于范围匹配的TCAM算法

前缀扩展算法［12］是传统的范围匹配算法，该算法将用范围表示的规则转化为一组前缀表示的形式。假设W 为范围的位宽，则算法的最差扩展系数为2（W－1）。对于目的端口号和源端口号而言，在最坏情况下，一条规则就需要900条TCAM表项。Taylor用前缀扩展法对多个实际的规则集进行转换实验，结果表明这种算法的平均扩展系数为6倍多，TCAM空间利用率仅为16．12%［19］。该算法的优点在于实现简单，且更新性能优秀，缺点是TCAM的空间利用率很低。

基于映射区间（Mapping Range，MR）算法［20］，来解决基于TCAM包分类算法中普遍存在的“区间膨胀”问题。MR算法的主要思想是对造成“区间膨胀”的源／目的端口进行重新编码，为每个源／目的端口分配特有的比特位进行表示。MR算法可以完全解决区间膨胀问题，不过该算法对源／目的端口域中的范围区间编码效果不理想，当范围区间的数目增多时，其所需的编码比特数目也将大幅增加。而且该算法的更新过程是十分复杂的，因为它需要维护整个规则集中不同范围之间的相互关系。

由于TCAM具有三态特性，其通配符可以出现在掩码的任意位置，因此范围不仅可以转化为前缀形式，也可以转化为任意掩码形式。另外，TCAM的位宽固定，规则的位宽小于表项的位宽，每一条表项会有部分剩余比特位，因此，可以利用这些剩余比特来存储一些附加信息。动态区间编码（Dynamic Range Encoding Scheme，DRES）算法［21］的主要思想是充分利用未使用的比特位来对区间进行选择性编码，达到提高TCAM空间存储效率的目的。这种选择性的区间编码方案可以有效缓解“区间膨胀”问题，同时也不会造成规则宽度大幅增加，可以达到提高TCAM空间的存储效率的目的。但该算法未能从根本上解决区间膨胀问题，不能对编码之后的规则位宽进行压缩，而且算法的更新性能不佳。

4．1．2 基于前缀匹配的TCAM算法

由于IP路由查找可以看成是一维的报文分类问题，而TCAM能够有效存储IP地址，因此利用TCAM可解决IP理由查找问题。最优路由表结构（Optimal IP Routing Tables Construction，ORTC）算法［22］是针对IP路由表的存储优化问题的一种空间压缩算法，该算法可使用最少的前缀来表示所需查找的IP路由表。该算法利用二叉树的算法，将IP地址存储于二叉树中，通过修改、合并、删除二叉树进而使得规则在纵向上压缩。虽然该算法支持批量更新，但其更新效果并不理想。

4．1．3 基于非匹配的TCAM算法

反向扩展法的基本思想是为每非字段的每一个匹配位对应一条表项。在存储时，将非字段的某些位取反，其余位用“＊”表示，如图7（a）所示。非规则一般被应用于排除指定的子网，所以，其非字段的匹配位较多，这就造成了反向扩展法的空间复杂度较高、更新性能较差，实际应用中一般不采用这种算法。因为TCAM只返回优先级最高的一条匹配结果，正向否定法［23］利用了这一特性，在存储时，每条非规则只占用2条TCAM表项，如图7（b）所示。首先在TCAM中存储一条正向非字段的表项，但是其SRAM中的匹配结果为空，即若命中此表项则表示不满足此非规则。然后在此表项的高地址上存储一条将非字段全置为“＊”的表项，若命中此表项则表示满足此非规则。

图7 反向扩展法、正向否定法示意图

4．1．4 基于改进硬件的TCAM算法

扩展的三态内容寻址存储器（Extended TCAM，E－TCAM）算法［24］针对 TCAM 硬件空间利用率低以及能耗大的问题。E－TCAM的主要思想是改变TCAM的硬件结构，使得硬件可以直接支持范围匹配，从而提高空间利用率。考虑到TCAM的并行查找模式能耗极大，因此，在实现时，E－TCAM将整个设备分为多个可以容纳数百条规则的区域。在查找时，设备的每个区域都能够正常查找，但ETCAM每次只激活部分区域，进而限制设备中每次查找的活跃区域的数目，从而达到降低能耗的目的。为了使查找关键字能够激活正确的区域，E－TCAM采用多阶段的分割算法。为了组织规则进入适当的区域，硬件体系结构严格限制了E－TCAM中“决策树”的高度，而且每次查找可能并行地在若干分支之间执行。

E－TCAM通过对原始TCAM硬件的改变，有效地解决了TCAM硬件空间利用率低和能耗大的问题。但是随着TCAM的大规模应用，修改TCAM硬件会造成巨大的成本开销，同时降低了TCAM硬件的灵活性。

4．2 基于Bloom过滤器的包分类算法

Bloom 过滤器（Bloom Filter）［25］是一种二进制向量的数据结构，可以用简洁的位数组表示大规模的数据集合，并快速对关键字进行查找，判断待查找元素是否属于集合中。假设数据集合S共有n个元素，Bloom Filter通过k个哈希函数将各个元素映射到长度为m位的向量V中，每一个哈希函数的取值范围为［0，m－1］，且函数之间相互独立。将每个元素代入k个哈希函数中进行计算，得到k个相应的哈希函数值，Bloom Filter根据k个函数值，将相应的V向量对应的位置设置为1。查找时将待匹配查找的关键字，通过k个哈希函数产生k个哈希函数值，只有发现所有的k个哈希值对应的V向量的比特都被置1时，Bloom Filter认为该关键字属于V向量代表的集合，否则不属于该集合。对于一个元素，如果判断不通过，那么该元素一定不属于该集合，然而若通过，也不能代表该元素一定属于集合，因为该元素哈希函数值的位置可能被其他元素置1。这种某元素不属于集合而被认定为该集合的可能性，称为假阳性误判。

Bloom Filter的优点是它的查询和插入时间都是常数。但它的缺点也是显而易见的，假阳性误判的概率随着插入元素的数目增大而增大。另外，在Bloom Filter结构中的某一位可能被多个元素的哈希值同时占用，所以，在Bloom Filter也不能随意删除一个元素，一旦删除了某一个比特位，就可能会影响多个元素的检测。基于Bloom Filter的硬件包分类算法耗费资源过多，并且影响匹配速度，另外，算法动态更新比较困难。

基于布鲁姆过滤的最长前缀匹配（Longest Prefix Matching Using Bloom Filters，LMP－Bloom）算 法［26］是运用Bloom Filter来实现最长前缀匹配的算法，即一维前缀匹配算法。首先将规则库中的规则按照规则前缀的长度分成子规则集，子规则集数目与规则库中前缀长度的个数相同，假设分成了W 个子规则集，那么算法需要W个Bloom Filter，分别存储在对应的W个子规则库。当数据包到达时，首先IP地址中各种不同长度的前缀被提取出来，再送入对应长度的Bloom Filter中进行查找，W 个Bloom Filter分别输出匹配结果，当发生有多个匹配结果时，按照最长前缀原则选择。该算法中W 个Bloom Filter可以并行查找，匹配速度相当快，但是消耗硬件资源较多。

分布式跨域符号生成（Distributed Crossproducting of Field Labels，DCFL）算 法［3］是 一 种 基 于 Bloom Filter的多维包分类算法，该算法将硬件设计与维度分解相结合。首先将多维匹配分解为多个一维匹配，分别在对应的一维规则库中进行匹配，然后对每二维的匹配结果做叉积，与二维均匹配的规则必在这些叉积中，但是有些叉积并不属于规则集。再将2个二维匹配结果再做叉积，再在四维叉积中匹配查找，以此类推进而得到多维匹配结果。DCFL算法运用Bloom Filter数组完成叉积的查找，降低内存访问次数和假阳性概率。

5 结束语

包分类算法是包分类技术的核心。本文从包分类算法背景、基本概念等方面介绍包分类算法的研究状况。总结和归纳经典的包分类算法，比较了它们的性能和特点，指出包分类算法设计的不足和缺点。随着互联网的高速发展，云计算、移动互联网、大规模物联网、软件定义网络（Software Defined Networking，SDN）的概念和OpenFlow等技术的兴起，包分类问题的研究将面临新的挑战［27］。在性能上，应支持超大规则集，满足骨干网络和数据中心网络的带宽。在业务上，应具备识别应用层包分类的能力，在网络业务的管理和服务质量上提供保障。同时，包分类技术将推动下一代互联网和相关设备的发展。

［1］陈正虎，蓝巨龙，黄万伟，等．一种基于Bloom－filter表项压缩的TCAM业务识别算法［J］．电子与信息学报，2011，33（9）：2212－2218．

［2］Lunterenvan J，Engbersen T．Fast and Scalable Packet Classification［J］．IEEE Journal on Selected Areas in Communications，2003，21（4）：560－571．

［3］Taylor D E，Turner J S．Scalable Packet Classification Using Distributed Crossproducing of Field Labels［C］／／Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies．Washington D．C．，USA：IEEE Press，2005：269－280．

［4］马 腾，陈庶樵，张校辉．改进的HyperSplit报文分类算法［J］．计算机工程，2014，40（1）：258－262．

［5］Yang Baohua，Jeffrey F，Jiang Weirong，et al．Practical Multi－tuple Packet Classification Using Dynamic Discrete Bit Selection［J］．IEEE Transactions on Computers，2014，63（2）：424－434．

［6］Kallath D．Trust in Trusted Computing——The End of Security as We Know It［J］．Computer Fraud and Security，2005，12（12）：4－7．

［7］Li Xiong，Liu Ling．PeerTrust：Supporting Reputation——Based Trust for Peer－to－peer Electronic Communities［J］．IEEE Transactions on Knowledge and Data Engineering，2004，16（7）：843－857．

［8］Gupta P，McKeown N．Packet Classification on Multiple Fields［C］／／Proceedings of ACM SIGCOMM’99．New York，USA：ACM Press，1999：147－160．

［9］亓亚炬，李 军．高性能网包分类理论与算法综述［J］．计算机学报，2013，36（2）：408－421．

［10］Gupya P，McKeown N．Packet Classification Using Hierarchical Intelligent Cuttings［C］／／Proceedings of the 7th IEEE Hot Interconnects Symposium．Washington D．C．，USA：IEEE Press，2000：34－41．

［11］Lakshman T V，Stiliadis D．High－speed Policy－based Packet Forwarding Using Efficient Multidimensional Range Matching［C］／／Proceedings of ACM Sigcomm．New York，USA：ACM Press，1998：203－214．

［12］Srinivvasan V，Suri S，Varghese G，et al．Fast and Scalable Layer Four Switching［C］／／Proceedings of ACM SIGCOMM’98．New York，USA：ACM Press，1998：191－202．

［13］Baboescu F，Singh S，Baboecu F，et al．Packet Classification for Core Router：Is There an Alternative to CAMs ［C］／／Proceedings of the 22nd IEEE Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2003：53－63．

［14］Gupta P，McKeown N．Packet Classification on Multiple Fields［C］／／Proceedings of SIGCOMM’99．New York，USA：ACM Press，1999：147－160．

［15］Srinivasan V，Suri S，Varghese G．Packet Classification Using Tuple Space Search［C］／／Proceedings of SIGCOMM’99．New York，USA：ACM Press，1999：135－146．

［16］Micron Technology．Micron 1Gb DDR SDRAM Data Sheet［EB／OL］．（2008－11－21）．http：／／www．micron．com／products／dram／ddr2／partlist．asp．

［17］Yu Fang，Lakshman T V．Effifient Multimatch Packet Classification for Network Security Applications［J］．IEEE Journal on Selected Areas in Communications，2006，24（10）：1805－1816．

［18］朱国胜，余少华．基于 TCAM 的范围匹配方法——C－TCAM［J］．通信学报，2012，33（1）：31－37．

［19］Taylor D E．Survey Taxonomy of Packet Classification Techniques［J］．ACM Computing Surveys，2005，37（3）：238－275．

［20］Liu Huan．Efficient Mapping of Range Classifier into Ternary－CAM［C］／／Proceedings of the 10th IEEE Symposium on High Performance Interconnects．Palo Alto，USA：IEEE Press，2002：95－100．

［21］Che Hao，Wang Zhijun，Zheng Kai，et al．DRES：Dynamic Range Encoding Scheme for TCAM Coprocessors［J］．IEEE Transactions on Computers，2008，57（7）：902－915．

［22］Draves R，King C，Venkatachary S，et al．Constructing Optimal IP Routing Tables［C］／／Proceedings of IEEE INFOCOM’99．Washington D．C．，USA：IEEE Press，1999：88－97．

［23］Yu F，Katz R H．Efficient Multi－match Packet Classification with TCAM［C］／／Proceedings of the 12th IEEE Symposium on High Perfor－mance Interconnects．Palo Alto，USA：IEEE Press，2004：28－34．

［24］Spitnagel E，Taylor D，Turner J．Packet Classification Using Extended TCAMs［C］／／Proceedings of IEEE International Conference on Network Protocols．Washington D．C．，USA：IEEE Press，2003：42－52．

［25］Bloom B H．Space／time Trade－offs in Hash Coding with Allowable Errors［J］．Communications of the ACM，1970，13（7）：422－426．

［26］Dharmapurikar S，Krishnamurthy P，Taylor D E．Longest Prefix Matching Using Bloom Filters［J］．IEEE／ACM Transactions on Networking，2006，14（2）：397－409．

［27］Ganegedara T，Jiang Weirong，Viktor K．A Scalable and Modular Architecture for High－performance Packet Classification［J］．IEEE Transactions on Parallel and Dis－tributed Systems，2014，25（5）：1135－1144．