（计算机软件与理论专业论文）高性能包分类算法研究.pdf

摘要 摘要 i n t e r n e t 发展到今天，连接到i n t e r n e t 的主机数量正在以前所未有的速度增长 从而使得网络的流量逐年成倍地增长。这无疑对i n t e r n e t 服务质量提出了新的挑 战，随着光纤技术和密集波分复用技术( d w d m ) 的发展，网络链路传输速率问 题已基本解决，此时，作为网络核心器件路由器的性能已成为网络性能的新 瓶颈。而路由器所具有的包括路由选择、区分服务、q o s 、流量费等在内的多项 功能都是以数据包分类技术为支撑地。 本文首先对目前常见的十余种典型的基于软件实现的包分类算法进行了系 统、详细的研究，并对各种算法的查找时间和空间需求进行了比较，分析总结出 当前数据包分类领域面临的问题。研究发现现有的包分类算法均只对特定形式的 分类规则表现出良好的性能。目前还没有一种算法能在所有方面都较理想地满足 高速( 大于l o o g b p s ) 应用的需要。 随后本文针对多维包分类问题，提出了一种能灵活的适应各种多维规则的包 分类算法，本文称之为域分多维包分类算法。研究过程中取得的主要研究成果有： 1 根据多维规则的各个域的表现形式不同将其分段处理。具体的做法是：将 规则分为最长前缀表示段、精确值表示段、剩余部分段三部分，分别加以处理。 如此处理显然能使算法更很好地适应各种形式的规则集； 2 通过对规则表示形式的研究，本文统一将规则中除前缀式和精确值形式之 外的部分转化为任意位掩码形式予以处理，并针对任意位掩码形式表示的规则， 提出了一种新的分类算法状态转移树算法( 时间复杂度o ( m ) ，空间复杂度 o ( m ) ，m 为规则长度) ； 3 对t u p l es p a c es e a r c h 算法作了改进，将查找速度由0 ( n ) 提高到0 ( 1 0 9 n ) ，1 1 为不同前缀的个数； 4 针对本文提出的分段策略，设计出并行执行方案，进一步提高了速度； 文章分析得出本算法的时间复杂度为0 ( 1 0 9n ) 空间复杂度为0 ( n ) ， n 为不同前缀个数，n 为规则数。 关键字：包分类多模式匹配元组t r i e 摘要三 a b s t r a c t n o w a d a y s ，m o r ea n dm o r ep c s l i n kt ot h ei n t e r n e ta n dt h i sm a k e si n t e r n e td a t a f l o wg r o w i n gm u c hf a s t e rt h a na n yt i m eb e f o r e c o n s e q u e n t l y , g o o dq u a l i t yo fi n t e r n e t s e r v i c e sm u c hm o r ed i f f i c u l t yt oo b t a i n w i t ht h er a p i dd e v e l o p m e n to ff i b e ra n d d w d mt e c h n o l o g y , t h en e t w o r k st r a n s m i s s i o nr a t ei ss a t i s f y i n gb a s i c a l l y a sab a s i c e q u i p m e n to fn e t w o r k s ，r o u t e rb e c o m e s ab o t t l en e c ko ft h ei n t e r n e tn o wa n dt h eb a s i c t e c h n o l o g yo fr o u t e ri sp a c k e tc l a s s i f i c a t i o n i nt h i sp a p e r , w ef i r s td oas y s t e m i c ，d e t a i lr e s e a r c ho na l m o s ta l lt h ec l a s s i c a l p a c k e tc l a s s i f i c a t i o na l g o r i t h m sa n da n a l y z et h et i m ea n ds p a c er e q u e s to fa l l t h e a l g o r i t h m sa n dc o m p a r eo nt i m e s p a c ec o n s u m p t i o nb e t w e e nt h e m o u rr e s e a r c h s h o w s ：t h em o s to ft h ec l a s s i c a lp a c k e tc l a s s i f i c a t i o na l g o r i t h m so n l ys u i tf o ro n eo rt o t y p eo fm a t c h i n g n o w a d a y s ，t h ep a c k e t f i l t e rb e c o m e st ob em o r ea n dm o r e c o m p l e x i 啦o n ef i l t e ru s u a l l yc o m p r i s e sl o n g e s tp r e f i xm a t c h i n g ，a c c u r a t em a t c h i n g ， r a n gm a t c h i n ga n ds oo n t h a to n ea l g o r i t h mf i t s a l lt h et y p eo fm a t c h i n gr e m a i n sa p r o b l e m a st ot h ep r o b l e ma b o v e ，w ei n t r o d u c ean e wa l g o r i t h mn a m e dm u l t i d i m e n s i o n a l s u b s e c t i o no nf i e l da l g o r i t h ma n dt h i sa l g o r i t h mu s e ss t r a t e g yo ff i l t e r - d i v i s i o no n m a t c h i n gt y p e c o n c r e t e l ys a y s ，t h i sa l g o r i t h md e a l sd i f f e r e n tm a t c h i n gf i e l di i l o n e r u l ew i t hd i f f e r e n ts t r a t e g y i no u rn e wa l g o r i t h m ，w eu s et u p l es p a c es e a r c h a l g o r i t h mf o rt h el o n g e s tp r e f i xm a t c h i n gp a r t s ，h a s h i n gt a b l ef o ra c c u r a t em a t c h i n g p a r t sa n dd e v e l o ps t a t et r a n s m i s s i o nt r e ea l g o r i t h mf o rt h el a s tp a r t so ft h er u l e w e i n t r o d u c e dt h ep a r a l l e la l g o r i t h ms o o n f i n a l l yw ec o d e di i lcl a n g u a g ef o ro u r a l g o r i t h mf o rv e r i f y i n g i ti so b v i o u st h a t0 1 1 1 a l g o r i t h mc a nf i tv a r i o u sf i l t e r sw e l l w ea n a l y z e dt h et i m e a n ds p a c er e q u i r e m e n to ft h ea l g o r i t h m t h er e s u l ts h o w st h a tt i m ec o m p l e x i t yi s o ( t o g 砂a n ds p a c ec o m p l e x i t yi sd 仰，t h e ni st h en u m b e ro ft h et u p l e ，t h eni st h e n u m b e ro f r u l ea n d 咒 3 ) 维分类，包分类算法很难在时空两方面都取得较高的性能，要么用线性 空间o ( n ) 获得o ( 1 0 9 d 1 n ) 的时间复杂度，要么用o ( n d ) 的空间获得o ( 1 0 9 n ) 的时间复 杂度。因此，一个分类效率高而空间消耗又比较合理的算法依然是个设计难题。 但是数据流的分布和特定规则集中规则的分布都有一定的规律性，或者说有 内在的结构。所以很多好的包分类算法的解决思想是考察它们分布的某一点规律 性提出的。此外，二维的包分类问题( 即针对目的口地址和源i p 地址) 相对简单，而 高性能包升类算法研究 且二维的包分类在多播和、，p n 中都有广泛应用，具有实际的意义，并且有一些优 秀的算法作为基础，因此解决包分类算法的一个重要思想就是降维，即将高维问 题转化为二维乃至一维的问题。 目3 1 表3 1 的图形表示 近年米虽然新的算法不断涌现，但很多算法通常采用相似的数据结构和杳找 模式，或多或少地取材于经典的包分类算法。本章主要就几种典型的包分类算法 加以介绍，并对它们的性能做以比较。 32 基于t r i e 算法 t r i e 【2 7 义称为数字查找树，最简单的t 订e 就是一个二叉查找树，分支分别标 记为0 和1 。树上节点对应的前缀是从根节点到该节点的路径上所有比特组成的比 特向量。这种结构有利丁进行二维的目的源地址分类，广泛应用于v p n 和多播转 发中。基于t n e 树的算法主要有h i e r a t c h i c a lt r i e 、s e t - p r u n i n gt i l e 、以及它 们的改进算法g r i d o f - t r i e s 。接下来将对它们进行一一介绍。 3 21h i e r a r c h i c a lt i l e 算法 h i e r a r c h i c a lt r i e 是一种基于t i l e 树的二维前缀匹配算法，它使用两个混台 的t n e 树，每一个对应规则集中的一维空间。如果是对目的源i p 地址进行分类，相 圜 一。 一曩 一 第三章典型包分类算法描述 应的t i l e 树分别称为目的地址t r i e 树和源地址t r i e 树。根据表3 1 的规则集构建的目 的源地址t r i e 树如图3 2 所示。对于目的地址t r i e 树中的每个节点，如果在规则集中 图3 2h i e r a r c h i c a lt r i e 算法查找示意 t i r e 存在着对应的目的地址前缀，则会指向一棵源地址t r i e 树，否则相应的指针为空。 对于每个到达的数据包，算法的查找过程分为两步：第一步是在目的地址t i l e 树中对包头的目的m 地址做最长前缀匹配，找到匹配节点：第二步再对这个节点及 其父节点所指向的所有源地址t h e 树进行源地址匹配查找，得到优先级最高的过滤 规则。 以包头为h ( 0 0 0 ，0 1 0 ) 的数据包为例，其目的地址为0 0 0 ，按最长前缀匹配原则 找到点c ( 0 0 宰) ；再根据c 点所指向的源地址t r i e 树，由其源地址( 0 1 0 ) 找到r 4 ；然后再在 目的地址比特树中回溯，查找b 点和a 点的源地址比特，找到i 也。按最长前缀匹配 的原则，r 2 的优先级高，因此r 2 是其匹配规则。 进行多维分类时，算法与二维分类类似，使用递归算法，先建立第d 维的t i l e 树，再在第d 维的t i l e 树下面建立( d 一1 ) 维的t r i e 树。 h i e r a r c h i c a lt r i e 算法简单、直接、便于硬件实现，但是由于回溯查找时间较长， 算法对规则维数的扩展性较差，不能直接支持范围匹配。算法的空间复杂度为 o f n d w ) ，时间复杂度是。卯) ，w 为域宽。 3 2 2s e t p r u n i n gt r i e 算法 由于经常要进行回溯查找，h i e r a r c h i c a lt r i e 算法会耗费大量的时间，使得查找 1 6 高性能包分类算法研究 效率很低。s e t p r u n i n gt r i e 算法提出，将目的地址t r i e 树中每个节点的所有父节点 的源地址比特在这个节点的源地址t r i e 树下复制一份，这样就避免了回溯，只需要 查找一遍目的地址t r i e 树，一遍源地址t r i e 树就可以完成规则匹配。算法构建的树 结构如图3 3 所示，它在图3 2 的基础上增加了某些节点的拷贝。 该算法由于复制了叶节点，不再需要回溯操作，所以减少了查寻时间，时间 复杂度降为o ( d w ) 。但这是以增加空间复杂度为代价的，最坏情况下空间复杂度达 到。o m d d w ) 。而且该算法不易更新，只适用于静态规则库。 图3 3 s e t - p r i m i n gt i l e 算法查找示意 3 2 3g r i d o f - t r i e s 算法 不难看出，s e t p r u n i n gt r i e 算法要消耗大量的内存，每个目的地址t r i e 树中的 节点不但存储它自身的源地址前缀，还要存储其祖先的源地址前缀。在最坏情况 下，其空间复杂度可达到。o ( n d d w ) 。一种改进的办法就是去掉这些多余的拷贝， 每个目的地址前缀只包含规则集中与该目的地址相配的源地址前缀。这样得到的 就是以上介绍的h i e r a r c h i c a lt i l e 算法，但时间复杂度却增加了。 v s r i n i v a s a n 等人提出的g r i d o f - t r i e s 算法巧妙地引入转向指针，即通过预处理 将源地址t r i e 树中的空指针指向其目的地址t r i e 树的某个祖先对应的源地址t r i e 树 中的节点，使得在查找过程中沿着最长匹配路径能够尽可能地前进。此外，为了 确保算法的正确性，还必须保证目的源地址前缀对中前缀长的节点对应的优先级 高( u 0 地址前缀匹配越精确优先级越高) ，这些都是通过预处理完成的。 在图2 4 所示的g r i d 0 f - t r i e s 算法示意图中，对一个待分类的数据包的查找过程 第三章典型包分类算法描述 1 7 如下：先对目的地址做最长前缀匹配，然后沿着目的地址最长匹配前缀所指向的源 地址“e 树，根据包头的源地址沿着o ，1 指针( 或者转向指针) 尽可能地前进，直到无 法继续前进为止。存储沿途经过的结点，在其中寻找优先级最高的规则，这个即 是它的最佳匹配。 以查找包头h ( 0 0 0 ，o l o ) 为例，先根据其目的地址0 0 0 按最长前缀匹配原则找到 节点c ( o o 水) ，再根据节点c 所指向的源地址t r i e 树，由其源地址第一个比特“0 ”找到 r 、点，然后再根据其第二个比特“1 ”找到节点r 2 。按最长前缀匹配的原则，r 2 的 优先级高，因此r 2 是其匹配规则。 此算法的时间复杂度为o ( w ) ，空间复杂度为o ( n w ) 。但空指针的使用增加了 更新的难度，在需要更新时最好要重建这棵树。另外，这种算法要求目的地址及 源地址都是前缀形式，这就限制了它的适用范围。当然，非前缀形式可以转换为 若干前缀形式之和。 图3 4 g r i d o f - t r i e s 算法查找示意图 3 32 d 分类算法 在2 0 0 1 年l a k s h m a n 与s t i l i a d i s 发表了一个2 d 的分类演算法【2 8 1 ，它的数据结构是 首先建立一个t r i e 在第一维里，第二维是建立在t r i e 之下的节点。 一个2 d 的分类演算法的是基于二维的的分类规则库，并且第一维必须具有前 高性能包分类算法研究 缀形式，它的第二维可以是任意的形式。用它第一维的数据首先建立一个比特树， 然后，在每个结点下，将第一维与这个结点相匹配的规则的第二维数据组织起来， 构成一个数据结构( 如数组或二叉树) 建立在这个结点下，使用一个范围查找的方法 来搜索符合条件的规则。以图表2 1 的分类规则为例，用它建立的数据结构如图3 5 所示。 2 d 分类的搜索算法描述如下： 1 ) 从根结点开始，用输入的每一个d 包的目的地址，沿着比特树向下搜索，直 到找到一个最长前缀匹配的结点。 2 ) 对搜索路径上所遇到的每一个结点，在其指的数据结构中查找匹配源地址的 规则。这次的搜索是允许任意范围的数据查找。 3 ) 在所有找到的匹配规则中选出具有最高优先级的规则。 我们举例来说明，如图表2 7 所示，当有一个包h ( 0 1 1 ，1 1 0 ) 到达时，先用目的 地址( 0 1 1 ) 搜索比特树，寻找最长前缀匹配的节点。找到b 点。然后在a 点及b 点所 指的数据结构中查找与( 11 0 ) 相匹配的规则，此时会找n r 5 。 如 图3 5 2 d 分类算法图示 2 d 分类算法的复杂度可从时间复杂度与空间复杂度来分析，址的宽度，n 为 规则的数量。因为数据查找使用二叉树来做搜寻，其中w 为目的地其时间为 0 0 0 9 n ) ，故其时间复杂度为o ( w l o g n ) 。因旖有n 个规则，每个规则只存储一次， 故其空间复杂度为o ( n w ) 。 第三章典型包分类算法描述 3 4b i tv e c t o r 算法 b i tv e c t o r ( 又称之为b i tm a p ) 算法的基本思想是把包分类的问题分解成d 个小 问题，然后再把得到的结果组合起来。比如，为规则集的每一个域构建一棵一维 t r i e 树，在t i l e 树中每一个具有有效前缀的树节点都用一个n 比特的比特向量表示。 图3 7 所示的t r i e 树是根据表3 1 的规则集创建的。很显然，与f 1 对应的t r i e 树包 含了该域具有有效前缀的所有节点，如o 宰、0 0 、1 幸。t r i e 树中的每一个节点都由 一个n 比特的比特向量来表示。如果某一个节点的前缀和规则r i 匹配，则该节点对 应比特向量中第j 个比特就置为1 ( 按从左到右的顺序) 。当一个具有d 个域的包头到 达时，在每一个域上做最长前缀匹配查找，找到相应的节点，读取对应的比特向 量，然后将所有域的比特向量按位相“与”( 即执行a n d 操作) ，就可以找到交集中代 价最小的匹配规则。假设规则在数据库中是以代价的增序排列的，则所要做的只 是查找相“与”之后第一个置“1 ”的比特所在的位置( 按从左到右的顺序) ，该位置序 号即表示了规则集中相匹配的规则的序号。这些n 比特比特向量之间“与”操作 的时间复杂度为o f n ) ，如果内存中一个字长是w 比特，那么最坏情况下这些操作 需要d ) w 次内存访问。由此可见，算法运行时间是随着n 的增大而线性增长 的，这种线性关联使之很难应用于大规模规则集。比如，当一个规则集中包含上 万条规则时，算法的性能将会很低。其次，算法经常会遇到最坏情况，因为通常 一个数据包头不会仅匹配规则集中的一条规则，所以b i t v e c t o r 算法的扩展性很低。 另外，当n 增大时，需要有足够宽的内存总线来传输计算出的比特向量，因而采用 a s i c 实现是比较合适的。而网络处理器的s r a m 总线宽度只有3 2 比特，如果要按 照一个大规模规则集来进行包分类，则需要对比特向量分段提取，造成多次内存 访问，从而降低了分类性能。 2 0 - _ 一 高性能包分类算法研究 图3 7b i tv e c t o r 算法示意图 3 5h i c u t s 算法 f l h i c u t s ( h i e r a r c h i c a li n t e l l i g e n tc u t t i n g s ) t 2 7 】法的基本出发点是，根据规则集本 身的特征自动调节包分类算法使用的数据结构，最大限度地利用优化的数据结构 来减少冗余，降低算法的存储容量需求，提高包分类的速度。在预处理过程中， 算法采用一棵基于规则集的决策树，决策树的根结点包含整个d 维空间，树中每个 结点的所有子结点将父结点包含的d 维空间按某一维平均划分，子结点的个数和维 数的选择均根据用户事先给定的约束参数b i n t h ( 叶结点包含的规则最大数) 和s p f a c ( 根据实验结果确定的常数) ，按用户选定的某种最优化原则进行选取。每个结点包 含的规则定义为与该结点包含的d 维空间相交的规则的集合，只要某结点包含的规 则数量超过预先定义的b i n t h ，该结点就会被划分为若干个子结点。在决策树生成 过程中还要考虑如何最大限度地重复利用结点信息、删除由于空间划分产生的冗 余规则。 第三章典犁包分类算泣描述 i 第二次分割： 、 、 ， ：第一次! 一7 7 _ 一1 7 7 j ； 粪一| 一j ： o h ； r ； ：， 、 ，j m 二 ， 二壤l 高性能包分类算法研究 到一个包含规则的节点，获取切割信息，沿着该节点的右孩子查找，最终到达一 个仅包含r 5 的叶节点，可知r 5 便为匹配规则。 h i c u t s 算法对内存空间需求量较低，规则集的更新也比较容易，可直接支持范 围匹配，并且可以通过改变约束参数b i n t h 和s p f a c 来调节分类时间和内存空间需求， 对一些小型的规则集来说是一种较好的选择。其缺点是预处理时间较长，和一些 快速包分类算法相比处理速度有限，而和r f c 算法相比需要较多的访存次数。 h i c u t s 的时间复杂度为o ( d ) ，空间复杂度为o f n d ) 。 3 6r f c 算法 r f c 算法利用实际应用中规则的结构特性和冗余，将整个头域分为若干个段， 通过计算分段中等价类和递归操作，实现空间的分步压缩映射。 假设数据包分类规则为d 维，s 表示包头中d 个域所形成的比特串的总长度。包 分类的实质是将数据包中头域s i g h 特的关键字信息映射成t 比特( t = l o g n ，t s ， n 为规则条数) 的等价类标识( e q l d ) 。 若要通过一次内存访问便可得出查找结果。则需预先建3 f f _ 2 s 个数到t 个e q l o z 间的对应关系。如此至少需要2 s + 2 1 个内存空间来保存这些对应关系。然而在实际 的多维包分类问题中，s 通常很大( 在1 0 0 左右) ，比如当d 为( 目的源地址域、目 的源端口域、协议域) 时s 为1 0 4 b i t ，如此便需要至少约2 1 i t 内存，这显然是不现 实的。 r f c 算法的基本思想如图3 1 0 所示：将原来的一次映射转变为多阶段映射，其 作用是将一个较大的集合映射成若干个较小的集合。每一阶段映射称为一次缩减， 最终实现包头中s 比特串数据到t ( t s ) 位e x t i d 的映射。由多阶段映射所构建的数 据结构称为缩减树。 图3 1 1 是根据表3 2 的规则集构建的一棵二阶段r f c 缩减树，其中每条规则包含 3 个域，每个域为3 比特。r f c 算法构建缩减树的过程如下： 1 ) p h a s e0 阶段，将规则集的3 个域( f 1 f 3 ) 分别映射到3 个预处理表( c h u n k 0 2 ) 中。预处理表的表项序号表示域的一种取值，例j t i c h u n k0 的表项o 表示f l 取值为 “0 0 0 ”，表项内容则为一个e q i d 。每个预处理表有一张相关联的e q l d 表，其中c b m 位串的长度与规则数相同，每一位对应一条规则( 第一条规则对应最高位，依次类 推1 ，每个不同的c b m 位 第三章典型包分类算法描述 i ， i i i l i i l一步映射r f c 所采用的多步递归步映射 l l i i l i l ：图3 1 0 ： t i f l l l p h a s e 0p h a s e1 r ，。，。e a i dc b m n0 0 0 1 1 预处理挚表l 0 0 0 0 阿j 、- j ：7 ，。7 。j 。 11 1 0 l 0 0 1 1 20 0 1 1 0 1 0 2 0 1 1 2 爻7 夕 + 一 1 0 0 0 1 1 l ，0 ， 1 m ，牡1 忆， 0 0 0 0 0 0 j 刨，于厩j 段 ， l 0 0 0 0 。 0 0 0 0 1 0 0 0 1 0 c q i d c b m 0 1 0 0 0 0 n 0 0 n 1 l 0 1 0 1 ， 0 1 0 0 1 1 11 0 n 1 0 1 1 0 i dc b m f l 0 1 0 1 0 0 ，f ) 1 n 1 f 2 - 1 0 0 2 n0 0 0 1 0 1 0 1 1 2 30 0 1 1 11 0 0 1 b | 1 1 1 o 20 1 1 1 0 1 1 1 0 0 夕 0 1 11 1 0 0 0 0 0 1 0 0 0 0 3 1 0 0 0 l 。3 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 i dc b m n 0 0 1 1 1l l l l l l l ，o 图3 1 1 阶r f c 缩减树示意图 高性能包分类算法研究 表3 2r f c 算法规则集 规则f 】f 2f 3 a c t i o n r i 0 0 10 1 00 1 1p e r m i t r 2 0 0 11 0 0 0 1 1 d e n y r 3 0 1 1 0 0 p e r m i t 搴木+木奎幸木事 p e r m i t 串被赋予一个不同的e q i d 。确定预处理表中e q i d 的方法如下：从预处理表的第一个 表项开始，计算每个表项对应的c b m 位串，方法是检查每一条规则的对应域，如 果该域的取值与表项序号相同，则c b m 中与该规则对应的位置1 ( 表示匹配该取值) ， 否则置o ；检查e q i d 表中是否己存在该位串，若存在则将其对应的e q i d 填入预处理表 的表项，若不存在则分配一个新的e q l d ，并在e q i d 表中添加一条记录。例如c h u n k o 的表项o 对应的f 1 取值为“0 0 0 ”，只有r 4 的f 1 域与它匹配，则该表项对应的c b m 位串为“0 0 0 1 ”。该位串第一次出现，因而分配e q i d 为o 。 2 ) p h a s e1 阶段，计算由p h a s e 0 阶段得到的各e q i d 表的交叉乘积表 ( c r o s s p r o d u c t i n gt a b l e ，c p t ) 。交叉乘积表的每个表项代表7 e q i d o e g i d 2 的一种 组合，例如a 的表项0 代表( e q i d 0 e q i d l e q i d 2 ) 的组合0 0 0 ，表项内容为一个新的e q l d 。 交叉乘积表也有一个对应的e q l d 表。交叉乘积表中的e q l d 通过以下方法获得：对于 每一个表项，将该表项所代表的e q l d 组合中各e q l d 对应的c b m 位串做交叉乘积运 算( 位串按位相与) ，得到一个新的c b m ；若该c b m 在e q l d 表中己出现过，则将其对 应的e q l d 填入表项，否则分配一个新的e q l d 。比如，a 的表项o 代表( e q l d o e q i d l e q i d 2 ) = 0 0 0 ，对应的3 个c b m 位串分别为“0 0 0 1 ”，“0 0 0 1 ”和“0 0 1 1 ”，按位相“与”得到新的 c b m 位串为“0 0 0 1 ”，分配e q l d 为0 。 r f c 算法对表3 2 中待分类的样例数据包头h ( 0 1 0 ，l o o ，0 1 1 ) 的查找过程如下： 1 ) p h a s e 0 阶段，用h i = 0 1 0 ，h 2 = 1 0 0 和h 3 = 0 1 1 分别索引c h u n k 0 。2 ，得到 ( e q l d o e q i dle q l d 2 ) = 2 2 1 。 2 ) p h a s e l 阶段，按昭, , i n d e x = e q l d o * 3 * 2 + e q l d l * 2 + e q l d 2 得到查找交叉乘积表a 的 索引表，查表a 得至t j e g l d 等于3 ，其对应的c b m 位串为0 0 1 l ，表示规n r 。和r ，均 匹配，但按照最佳匹配原则，数据包匹配规则r 3 。 以上是经过简化的例子，当r f c 算法应用于实际的i p v 4 包分类时，可以根据需 要进行多维的包分类，并根据情况选择阶段数。 由图3 1 1 可以看出，预处理表和交叉乘积表中的e q i d 数量与规则集规模成正 比，交叉乘积表的长度等于各预处理表中e q i d 数量的乘积，其中总是存在相同的 e q l d 连续重复存储的问题。下文将每个不同的e q i d 定义为一个独立元素 ( i n d e p e n d e n te l e m e n t