第１７卷第６期 ２０１６年１２月 信息工程大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｖｏ１．１７ Ｎｏ．６ Ｄｅｃ．２０ｌ６ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７１ ６７３．２０１６．０６．０１７ 一种基于ＴＣＡＭ的报文分类算法 张杰鑫，邰 铭，杜 江，张 浩 （数学工程与先进计算国家重点实验室，河南郑州４５０００１） 摘要：基于ＴＣＡＭ的报文分类算法的关键问题在于如何高效地存储规则，而ＴＣＡＭ对范围形 式的规则存储效率不高。文章提出了一种基于ＴＣＡＭ的报文分类算法——ＧＤ—ＴＣＡＭ算法，该 算法基于格雷编码的纵向压缩，再利用ＴＣＡＭ的剩余位宽进行横向扩展，通过纵向压缩和横 向扩展实现降低扩展系数的目的。通过利用预留表项的顺序移动法，改进ＴＣＡＭ的储存方 式，保证分类的正确性、利于规则更新。经过理论证明和实验验证，ＧＤ．ＴＣＡＭ算法可以有效地 降低扩展系数、降低能耗、便于规则更新。 关键词：报文分类；规则集；ＴＣＡＭ技术；扩展系数 中图分类号：ＴＰ３９３．０２１ 文献标识码：Ａ 文章编号：１６７１＿０６７３（２０１６）０６￣７２４－０６ Ｐａｃｋｅｔ ＣＩａｓｓｉｎｃａｔｉＯｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ＴＣＡＭ ＺＨＡＮＧ Ｊｉｅｘｉｎ，ＴＡＩ Ｍｉｎｇ，ＤＵ Ｊｉａｎｇ，ＺＨＡＮＧ Ｈａｏ （Ｓｔａｔｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｄｖａｎｃｅｄ Ｃｏｍｐｕｔｉｎｇ，Ｚｈｅｎｇｚｈｏｕ ４５０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｃｋｅｔ ｃｌａｓｓｉｉｃａｔｉｏｎ ａｌｇｏｒｉｆｔｈｍｓ ｂａｓｅｄ ｏｎ ＴＣＡＭ ｆｏｃｕｓ ｏｎ ｅｆｉｃｉｅｎｔ ｓｔｏｒｉｎｇ ｒｕｌｅｓ．Ｈｏｗ— ｆｅｖｅｒ，ＴＣＡＭ ｃａｎ ｎｏｔ ｓｔｏｒｅ ｒｕｌｅｓ ｏｆ ｒａｎｇｅ ｆｏｒｍ ｉｎ ｈｉｇｈ ｅｆｉｃｉｅｎｃｙ．Ｔｈｉｆｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ＧＤ—ＴＣＡＭ ｐａｃｋｅｔ ｃｌａｓｓｉｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＴＣＡＭ．ＧＤ—ＴＣＡＭ ｃｏｎｄｕｃｔｓ ｖｅｒｔｉｃａｌｆ ｃｏｍｐｒｅｓｓｉｏｎ ｂａｓｅｄ ｏｎ ｇｒａｙ ｃｏｄｅ ａｎｄ ｈｏｒｉｚｏｎｔａｌ ｓｃａｌｉｎｇ—ｕｐ ｕｓｉｎｇ ｔｈｅ ｌｅｆｔ ｂｉｔｓ ｉｎ ＴＣＡＭ，ｔｈｕｓ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｃｏｅｆｉｃｉｆｅｎｔ ｏｆ ｓｃａｌｉｎｇ—ｕｐ．Ｂｙ ｍｏｖｉｎｇ ｔｈｅ ｒｅｓｅｒｖｅｄ ｔａｂｌｅ ｅｎｔｒｉｅｓ ｓｅｒｉａｌｌｙ，ｔｈｅ ｓｔｏｒｉｎｇ ｍｅｔｈｏｄ ｏｆ ＴＣＡＭ ｉｓ ｉｍｐｒｏｖｅｄ， ｔｈｅ ｒｕｌｅｓ ｕｐｄａｔｉｎｇ ｉｓ ｃｏｎｖｅｎｉｅｎｔ，ａｎｄ ｔｈｅ ｃｌａｓｓｉｆｙｉｎｇ ａｃｃｕｒａｃｙ ｉｓ ｇｕａｒａｎｔｅｅｄ ａｓ ｗｅｌ１．Ｂｏｔｈ ｔｈｅｏｒｅｔｉｃａｌ ｐｒｏｏｆ ａｎｄ ｅｘｐｅｒｉｍｅｎｔａｌ ｖｅｒｉｆｉｃａｔｉｏｎ ｓｈｏｗ ｔｈａｔ ＧＤ・－ＴＣＡＭ ｃａｎ ｒｅｄｕｃｅ ｔｈｅ ｃｏｅｆｉｃｉｆｅｎｔ ｏｆ ｓｃａｌｉｎｇ－－ｕｐ ａｎｄ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ ａｓ ｗｅｌｌ ａｓ ｕｐｄａｔｅ ｒｕｌｅｓ ｃｏｎｖｅｎｉｅｎｔｌｙ． Ｋｅｙ ｗｏｒｄｓ：ｐａｃｋｅｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｒｕｌｅ ｓｅｔ；ＴＣＡＭ；ｅｘｔｅｎｄｅｄ ｃｏｅｆｉｃｉｆｅｎｔ 对高速链路基于软件的报文分类算法显得越来越 ０ 引言 虽然有很多的基于软件的报文分类算法被提 出，但是随着规则集的越来越复杂和链路速度的不 断增长，报文分类算法也变得越来越复杂。最好的 软件分类算法在最好的计算机上仅能达到１Ｇｂｐｓ 的吞吐量，甚至使用最好的分类算法在多核网络处 理器上实现结果仅仅能达到１０Ｇｂｐｓ的吞吐量，面 力不从心。研究人员寻求从硬件上找到解决方案， 虽然已经提出了基于ＲＡＭ的路由查找算法和报 文分类算法 ，但是工业界中使用最多的硬件实 现路由查找的方法仍然是使用内容存储器（ｃｏｎｔｅｎｔ ａｄｄｒｅｓｓａｂｌｅ ｍｅｍｏｔｙ．ＣＡＭ）［２１来进行快速路由查找， 它能够快速对存储在ＣＡＭ中的大量数据进行并行 查找，ＣＡＭ的每一个存储位存储０或者１。目前， 使用最多的是三态内容地址存储器，简称ＴＣＡＭ 收稿日期：２０１５－０３—３１：修回日期：２０１５－０４－１８ 基金项目：国家８６３计划资助项目（２００９ＡＡ０１２２００）；上海市科研计划资助项目（０８ｄｚ１５０１６００；１３ｄｚｌ１０８８００） 作者简介：张杰鑫（１９８９一），男，硕士生，主要研究方向为包分类技术、计算机体系结构。 第６期 张杰鑫等：一种基于ＴＣＡＭ的报文分类算法 ７２５ （ｔｅｒｎａｒｙ ｃｏｎｔｅｎｔ ａｄｄｒｅｓｓａｂｌｅ ｍｅｍｏ￣），ＴＣＡＭ以表 项为单位存储分类规则，低地址的表项具有更高优 先级。 １ 基于ＴＣＡＭ的报文分类概述 １．１ ＴＣＡＭ简介 ＴＣＡＭ每条表项的宽度被配置为固定比特的 宽度，表项内容由关键字和掩码相“与”组成，因此 每位有３种状态：０、１和 。关键字查询时，ＴＣＡＭ 并行地将搜索关键字与所有表项进行并行匹配，并 返回最高优先级命中表项对应的地址，其查询速度 与表项的数目无关，为Ｏ（１）。虽然ＴＣＡＭ具有良 好的查询性能，但它也存在不足，ＴＣＡＭ实现每比 特的查询功能需要１０个～１２个晶体管，而ＳＲＡＭ 只需４个一６个 ，加之复杂的控制逻辑，导致 ＴＣＡＭ每比特的价格是ＤＤＲ ＳＲＡＭ的３０倍 ，功 耗则达到了１５０倍 。更为重要的是，ＴＣＡＭ不能 直接进行非字段和范围字段匹配，进而导致规则集 在纵向上膨胀，而且ＴＣＡＭ只能为每个表项分配 固定带宽，虽然很好地适应了不同的系统应用，但 是不可避免地在横向上产生了带宽浪费，并且其支 持硬件设计的优先级编码器每次匹配仅能输出一 个结果。因此，基于ＴＣＡＭ的报文分类算法最主 要解决的就是规则集膨胀问题和规则的优化储存 问题。 １．２基于ＴＣＡＭ的报文分类 基于ＴＣＡＭ的报文分类指系统通过配有 ＴＣＡＭ的分类引擎来实现报文分类，它可以分为规 则管理和报文分类处理两个方面。虽然实际统计 结果是所有规则集的实际复杂度均远小于理论复 杂度 ，但是规则集管理在分类系统中仍然至关 重要。基于ＴＣＡＭ的规则集管理，即系统将规则 转化成由掩码和关键字组成的三态比特串，并按照 一定的存放规则存人ＴＣＡＭ表项中。报文处理是 指系统处理器（ＮＰ、ＡＳＩＣ或ＦＰＧＡ等）从输入报文 中提取出关键字，然后将关键字送入ＴＣＡＭ中进 行匹配，最后根据匹配的结果对报文进行相应的处 理。由于报文处理的方式较为固定，因此，广义的 基于ＴＣＡＭ报文分类算法就是规则集管理，即如 何用ＴＣＡＭ表项表示和存储规则。 图１为基于ＴＣＡＭ的报文分类系统框图。规 则集管理算法运行在普通ＰＣ机或线卡ＣＰＵ的嵌 入式系统中，对规则进行相应的处理，之后通过报 文处理器把规则配置到ＴＣＡＭ表项中。处理报文 时，报文处理器提取进入报文首部各字段内容作为 搜索关键字，并输入ＴＣＡＭ进行查询，然后根据处 理结果对报文进行相应处理。 图１ 基于ＴＣＡＭ的报文分类系统框图 ＴＣＡＭ只适用于前缀匹配和精确匹配，无法直 接支持范围匹配和非匹配，为实现范围非匹配和非 匹配，需要用多条ＴＣＡＭ表项表示一条规则，即对 规则进行纵向扩展。平均扩展系数是平均一条规 则需要ＴＣＡＭ表项表示的条目数，如何降低扩展 系数也是研究重点之一。表１列出了规则集的统 计数据（其中１９９８年和２００４年的数据来自于文献 ［７］），可以看出范围规则越来越多，如何有效地支 持范围匹配对网络设备至关重要。 表１规则集范围统计 ２ 基于格雷编码的前缀扩展算 法——ＧＤ－ＴＣＡＭ算法 ２．１ 直接前缀扩展算法 ＴＣＡＭ只适用于前缀匹配和精确匹配，无法直 接支持范围匹配和非匹配。直接前缀扩展算法 是传统的范围匹配算法，该算法将用范围表示的规 则转化为一组前缀表示的形式。对于ＩＰ五元组而 言，端口号的表示方法通常是范围表示，如１— １０２３、１０２４—６５５３５。ＴＣＡＭ由于采用了并行查找 方式，所以若规则中出现范围匹配，首先要将范围 ７２６ 信息工程大学学报 转化为前缀形式，而且往往一个范围要表示成多条 ｃｏｄｅ），另外由于最大数与最小数之间也仅一位数 前缀。如区间［０００，１１１］，需转化为 ：ｉｔ （ 表示 不同，即“首尾相连”，因此又称循环码或反射码。 此位取值可为０也可为１），如果采用直接前缀扩 基于格雷码的前缀扩展算法用格雷编码表示 展算法，所消耗的空间极大，其在最坏情况下空间 范围字段的每个元素，并利用格雷码的对称性对范 ［１，２ 一２］转化为前缀表示为｛０１ ，００１ ，…０ 围进行分割，子范围各元素中满足遍历条件的位用 １，１０ ，１ １０ ，…，１ ０｝（１ ０ 表示ｍ个１后ｎ 代替，使这些带 的三态比特串能表示所有元 个０， 表示此位及其后的位为任意位），最坏情况 素，而这些三态比特串就是此范围字段用格雷编码 下需要用２ 一２条前缀匹配规则来表示一条范围 产生的ＴＣＡＭ表项。当输入范围中的元素作为搜 匹配规则。如果以端口号为例，端口号的位宽是 索关键字时，由于表项中有几位用 表示，而其它 １６位，则需要３０条规则来表示一条范围规则，在 都与元素相同，因此可以命中搜索。 实际应用中，一条规则包含源端口号和目的端口 算法首先利用对称性对范围进行分割，然后分 号，即存在两个范围区间，最坏情况下需要９００条 别得到各子范围带 的三态比特串。对范围［ａ， 规则来表示，空间消耗严重 。Ｔａｙｌｏｒ用直接前缀 ｂ］进行自然二进制编码，然后以其二进制编码的 扩展算法对多个实际的规则集进行转换实验，结果 公共前缀为界对范围［ａ，ｂ］进行分割，进而得到左 表明这种方法的平均扩展系数为６倍多，ＴＣＡＭ空 子树的最右叶子结点Ｎｏｄｅ 和右子树的最左叶子 间利用率仅为１６．１２％¨…。 结点Ｎｏｄｅ，。先依据（１）、（２）式得到ｇ ，然后再根 ２．２基于格雷编码的前缀扩展算法 据ｇ 范围［ｍ，ｎ］带 的三态比特串，并且以（Ｃ＋ 典型的二进制格雷码（ｂｉｎａｒｙ ｇｒａｙ ｃｏｄｅ）简称 ｄ）／２为中心、以２ 为长度对子范围向外再次进行 格雷码，因１９５３年公开的弗兰克・格雷（Ｆｒａｎｋ 分割，这样即可保证分割出来的元素可以用一条带 Ｇｒａｙ）专利“ｐｕｌｓｅ ｃｏｄｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ”而得名，现在 的三态比特串表示： 常用于模拟一数字转换和位置一数字转换中。在 ｇ０＝ｆｉｘ（１ｏｇ２（ｎ—ｍ＋１）） （１） 一组数的编码中，若任意两个相邻的代码只有一位 ｇ ＝ｆｉｘ（ｚ０ｇ：（ｎ一，ｎ＋１一∑； ２ ）） （２） 二进制数不同，则称这种编码为格雷码（ｇｒａｙ 图２ 基于格雷码的前缀扩展算法对范围编码过程示意图 图２展示了基于格雷码的前缀扩展算法对范 展算法时需要用００１ １和０１００两条表项，而使用基 围［５，１２］的编码过程，算法首先得到两个子范围 于格雷码的前缀扩展算法时只需要０ １０一条 ［５，ｌ０］和［１ １，１２］，再次切割出来的元素为｛６，７， 表项。 ８，９｝、｛５，１０｝和｛１１，１２｝，经过处理最终得到的带 的 基于格雷码的前缀扩展算法得到的扩展系数 三态比特串为：＊１０％、 ｌ１１和１＊１０，因此可以用３ 小于等于直接前缀扩展算法得到的扩展系数。 条ＴＣＡＭ表项来表示范围［５，１２］，而如果用直接 在纵向扩展方面，对于范围规则［ｍ，ｎ］，如果 前缀扩展算法进行编码的话，则需要０１０１、Ｏ１１ 、 可以由一条基于格雷码的ＴＣＡＭ表项表示则必须 １０ 和１１００等４条ＴＣＡＭ表项。 满足条件： 基于格雷码的前缀扩展算法对短范围编码时 ｎ—ｍ＋１＝２ｘ， ＝０，１，… （３） 可以获得较好的扩展系数，由于格雷编码具有相邻 ｍ＝（（ｎ—ｍ＋１）／２） Ｙ，Ｙ＝０，１，… （４） 数之间只差一位的特点，相邻数之间可以用一条 如果由一条基于直接前缀扩展算法的ＴＣＡＭ ＴＣＡＭ表项表示，例如范围［３，４］，用直接前缀扩 表项表示，则条件为 第６期 张杰鑫等：一种基于ＴＣＡＭ的报文分类算法 ７２７ ｎ—ｍ＋１：２ｘ， ＝０，１，… （５） 展后的规则源地址、目的地址和协议相同，而源端 口号和目的端口号不同，所以可将两条扩展后的规 ｍ＝（ｎ—ｍ＋１） Ｙ，Ｙ＝０，１，… （６） 由于（６）式成立的条件比（４）式苛刻，即可以 用一条基于直接前缀扩展算法的ＴＣＡＭ表项表示 则存储在一条ＴＣＡＭ表项中（如果一条规则扩张 后的规则数目是奇数，则在最后一个条目‘中存储相 同的端口号），达到减少ＴＣＡＭ存储空间、降低功 耗的目的。 的范围肯定可以被一条基于格雷码的前缀扩展算 法的表项表示，反之，则不成立。 可以得到一个结论：基于格雷码的前缀扩展算 法得到的扩展系数小于等于直接前缀扩展算法得到 的扩展系数。从格雷编码的特征可以直接看出，基 于格雷码的前缀扩展算法对短范围编码时比直接前 缀扩展算法获得更好的扩展系数。对于一个长度为 查找时，ＴＣＡＭ芯片支持分区掩码寄存器 （ｂｌｏｃｋ ｍａｓｋ ｒｅｇｉｓｔｅｒ，ＢＭＲ）和全局掩码寄存器 （ｇｌｏｂａｌ ｍａｓｋ ｒｅｇｉｓｔｅｒ，ＧＭＲ），分区掩码寄存器用于 在横向对ＴＣＡＭ表项进行区分，可以支持禁用部 分分区，全局掩码寄存器可以在纵向上确定那些 ＴＣＡＭ表项参与匹配。本方法利用了ＴＣＡＭ的此 项功能特性，在查找时通过对两个寄存器的动态配 置，确定参与匹配的ＴＣＡＭ表项和参与匹配的比 ２的范围，如果使用直接前缀扩展算法来表示需要 两条ＴＣＡＭ表项，而使用格雷编码只需要一条 ＴＣＡＭ表项，使用格雷编码可以使一般范围规则节 省５０％的ＴＣＡＭ的存储空间。当范围长度增加时， 特，在降低扩展系数的同时，也减少了参与匹配的 ＴＣＡＭ表项数目，进而降低功耗。如图３所示，查 找时，步骤如下： 基于格雷码的前缀扩展算法的优势开始下降。 可以归纳出，基于格雷码的前缀扩展算法比直 接前缀扩展算法更加优秀，其关注位不只是在表项 的末尾，可以在表项的任意位置，而且对于短范围 编码优势更加明显，该算法的灵活性更好。 ２．３基于ＴＣＡＭ优化存储结构 由于ＴＣＡＭ的表项必须被配置成固定位宽， ①设置ＴＣＡＭ的分区掩码寄存器为全部有 效，全局掩码寄存器设置为源地址、目的地址、源端 口号１、目的端口号１和协议有效； ②报文的五元组信息与所有ＴＣＡＭ表项进行 匹配，结果记为ｒｅｓｕｌｔ ，结果存储在判决器中； ③计算ｒｅｓｕｌｔ。所在的ｂｌｏｃｋ，结果记为ｂｌｏｃｋ ， ｉ≥０： 在存储ＩＰ五元组时，存在的位宽浪费的现象，如存 储ＩＰ五元组只需要使用１０４ｂｉｔ（源地址、目的地址 各需３２ｂｉｔ，源端口号、目的端口号各需１６ｂｉｔ，协议 需要８ｂｉｔ），而ＴＣＡＭ必须被配置成１４４ｂｉｔ，存在 ４０ｂｉｔ的位宽浪费。可以利用剩余的４０位再存储 一④重新设置分区掩码寄存器为ｂｌｏｃｋ。～ｂｌｏｃｋ 有效，全局掩码寄存器设置为源地址、目的地址、源 端口号２、目的端口号２和协议有效； 对端口号，一条规则存在纵向扩展的现象，即扩 全局掩码寄存器 Ｒ１ 源地址ｌ目的地址Ｉ源端口号ｌ 目的端口号１Ｉ协议ｌ源端口号２ 目的端口号２ｌ空闲 源地址ｌ目的地址Ｉ源端口号１旧的端口号１ｌ协议Ｉ源端口号２ 目的端口号２ｌ空闲 源地址Ｉ目的地址ｌ源端口号１ 目的端口号ｌｌ协议ｌ源端口号２ 目的端口号２Ｉ空闲 源地址ｌ目的地址Ｉ源端口号ｌ 目的端口号１ｌ协议ｌ源端口号２ 目的端口号２ｌ空闲 空闲ＴＣＡＭ表项 判 决 器 Ｒ２ ｂｌｏｃｋｏ Ｒ３ Ｒ４ 分 区 掩 码 寄 Ｒ５ 源地址ｌ目的地址ｌ源端口号ｌ 目的端口号１ｌ协议ｌ源端口号２ 目的端口号２ｌ空闲 存 器 Ｒ６ 源地址 目的地址ｌ源端口号ｌ旧的端口号１ 协议ｌ源端口号２ 目的端口号２ｌ空闲 源地址 目的地址ｌ源端口号ｌ 目的端口号ｌ 协议ｌ源端口号２ 目的端口号２Ｊ空闲 Ｒ７ Ｒ８ 源地址 目的地址Ｉ源端口号ｌ 目的端口号１ 协议Ｉ源端口号２ 目的端口号２ｌ空闲 空闲ＴｃＡＭ表项 图３ ＴＣＡＭ存储示意图 ７２８ 信息工程大学学报 ⑤对报文的五元组信息再进行匹配，结果记为 ｒｅｓｕｌｔ２； Ｐ２≤ＰＩ （８） 而采用ＧＤ－ＴＣＡＭ算法的能耗为 Ｐ３＝（１＋（Ｂ＋Ｂ１）／２Ｂ） （Ｐ２／２） （９） ⑥判决器，返回优先级高的表项地址，即若ｒｅ． ｓｕｌｔｌ≤ｒｅｓｕｌｔ２，返回ｒｅｓｕｌｔ】，若ｒｅｓｕｌｔ２≤ｒｅｓｕｌｔｌ，返回 ｒｅｓｕｌｔ２。 其中，Ｂ代表用到的所有ＴＣＡＭ的ｂｌｏｃｋ数目， 代表第２次匹配时用到的ＴＣＡＭ的ｂｌｏｃｋ数目，因 为有 （Ｂ＋Ｂ ）／２Ｂ≤１ （１０） 存储时，由于规则集中有规则存在交集的现 象，例如＠１９２．１５１．１１．１７／３２ １５．０．１２０．４／３２ ０： ６５５３５ １２２１：１２２１ ＯｘＯ６／Ｏｘｆｆ．＠１９２．１５１．１１．１７／３２ 在最坏情况下，ＧＤ．ＴＣＡＭ算法耗能比直接前 缀扩展算法和基于格雷码的前缀扩展算法要少。 在查找性能方面，虽然ＧＤ．ＴＣＡＭ算法需要２ １５．０．１２０．４／３２ ０：６５５３５ ０：１５９９ ＯｘＯ６／Ｏｘｆｆ，如果规 则存储不当会导致分类错误，如果将规则１存储在 高地址，而规则２存储在低地址，对于有一个报文 的头部为１９２．１５１．１１．１７ １５．０．１２０．４ １０２４ １２２１ 个时钟周期，若要到达每秒处理若要达到ＯＣ．１５３６ （８０ Ｇｂｐｓ）的线速转发速率，以最小的以太网分组 和帧间隙来计算，每秒必须处理１１９Ｍ个数据包， 从表２可以看出，现在很多ＴＣＡＭ芯片都支持该算 法。 表２几种ＴＣＡＭ芯片介绍 经过匹配后会返回规则２的结果，但是规则１更加 准确。在存储规则时，按照优先级排列，优先级高 的规则存储在低地址，优先级低的存储在高地址。 利用带预留表项的顺序移动法Ｈ。ｎ］，并且每个 ｂｌｏｃｋ的最后端存在一部分空余的ＴＣＡＭ表项，有 以下几种情况： ①当插入一条新的规则时，计算其优先级并规 则进入相应的ｂｌｏｃｋ，之后再确定其在ｂｌｏｃｋ中的位 置，顺序移动其后的表项。如图３所示，在Ｒ２后 面插入一条表项，首先移动Ｒ４到空余表项，再移 动Ｒ３到Ｒ４的位置。 ②当删除一条规则时，确定规则在ＴＣＡＭ中 的位置，删除该规则，并顺序移动其后的表项。如 图３所示，删除Ｒ６后，首先移动Ｒ７到Ｒ６的位置， 再移动Ｒ８到Ｒ７的位置。 ２．４ ＧＤ—ＴＣＡＭ算法 表３给出了３种算法的一些指标，包括最坏情 况下的扩张因子、最坏情况下功耗、更新性能和匹 配性能，其中规则的范围字段为源端口号和目的端 口号， 为范围字段长度，Ⅳ为规则的数目，曰代表 ＧＤ—ＴＣＡＭ算法用到的所有ＴＣＡＭ的ｂｌｏｃｋ数目， 曰．代表第２次匹配时用到的ＴＣＡＭ的ｂｌｏｃｋ数目。 综上所述，提出一种基于格雷编码的优化存储 的ＴＣＡＭ报文分类算法，即ＧＤ－ＴＣＡＭ算法。 在最坏情况下，ＧＤ—ＴＣＡＭ算法耗能比直接前 ３ 实验验证 由于分类规则很少公开，所以实验采用Ｃｌａｓｓ— 缀扩展算法和基于格雷码的前缀扩展算法要少。 设范围字段只是源端口和目的端口号时。 在最坏情况下，基于直接前缀扩展算法的能 耗为 Ｐ，＝Ｎ（２（Ｗ一１）） （７） Ｂｅｎｃｈ¨ 工具来产生分类规则库。本实验中所用 分类规则是防火墙的安全策略规则（ｆｗ—Ｂｕｍ），例 如，ｆｗ—ｌＯｋ表示由ＣｌａｓｓＢｅｎｃｈ在ｆＷ种子文件下产 生的１００００条规则，实验中采用了ｆｗ一１Ｏ０、ｆｗ一１ｋ、 ｆｗ＿５ｋ、ｆｗ一１Ｏｋ的４个规则集。经过直接前缀扩展 基于前面的证明，在最坏情况下，基于格雷码 的前缀扩展算法的能耗为 衰３ ３种算法指标对比 第６期 张杰鑫等：一种基于ＴＣＡＭ的报文分类算法 ７２９ 法、基于格雷码的前缀扩展法和ＧＤ－ＴＣＡＭ算法转 换后的规则条目如表４所示。 表４测试用规则库转换 从表４中可以看出，经过ＧＤ—ＴＣＡＭ算法转换 后，ＴＣＡＭ规则条目显著减少，存储效率大大增加。 为了便于比较，图４给出了基于表４的不同算法的 规则集扩张因子对比，可以看出，ＧＤ—ＴＣＡＭ算法的 扩张因子要比直接前缀扩展法和基于格雷码的前 缀扩展算法要低。因此ＧＤ—ＴＣＡＭ在节省空间、降 低能耗上具有优势。 ｆｗ １００ ｆｗ ｌｋ ｆｗ ５ｋ ｆｗ １０ｋ 图４ ３种算法规则扩张因子对比 ４ 总结 本文首先详细介绍了基于ＴＣＡＭ的报文分类 概念，分析了基于ＴＣＡＭ的报文分类算法的难点， 针对ＴＣＡＭ在存储规则时存在规则扩张的问题， 提出了基于格雷编码的纵向压缩，利用ＴＣＡＭ的 剩余位宽进行横向扩展，优化存储结构的报文分类 算法・ＧＤ—ＴＣＡＭ算法。在理论上证明了该算法比 直接前缀扩展算法和基于格雷码的前缀扩展算法 能更有效的解决规则扩张问题，通过实验检验了理 论的正确性。最坏情况下ＧＤ．ＴＣＡＭ的扩张因子 是Ｗ．１或Ｗ．２，提高了空间利用率，通过减少无效 表项参与匹配降低了功耗。该算法可以保证分类 的正确性，保证分类速度，提高ＴＣＡＭ的利用率， 减少能耗，方便规则更新。在现有ＴＣＡＭ的芯片 的情况下，即使在双周期完成查找依然可以支持 ８０Ｇｂｐｓ的线速查找。 参考文献６ ５ ４ ３ ２ ● Ｏ ： ［１］Ｇｕｐｔａ Ｖ，Ｌｉｎ Ｓ，Ｍｃｋｅｏｗｎ Ｎ．Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ ｉｎ Ｈａｒｄ・ ｗａｒｅ ａｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ Ｓｐｅｅｄｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｆｏｅｏｍ ９８．１９９８：８０１—８０９． ［２］Ｂａｂｏｅｓｃｕ Ｆ，Ｓｉｎｇｈ Ｓ，Ｂａｂｏｅｃｕ Ｆ，ａｔ ａ１．Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａ— ｔｉｏｎ ｆｏｒ Ｃｏｒｅ Ｒｏｕｔｅｒ：Ｉｓ ｔｈｅｒｅ ａｎ ａｌｔｅｒｎａｔｉｖｅ ｔｏ ＣＡＭｓ ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ・ ｐｕｒｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．２００３：５３－６３． ［３］Ｌｉ Ｘｉｏｎｇ，Ｌｉｎｇ Ｌｉｕ．ＰｅｅｒＴｒｕｓｔ：Ｓｕｐｐｏｒｔｉｎｇ ｒｅｐｕｔａｔｉｏｎ－ ｂａｓｅｄ ｔｒｕｓｔ ｆｏｒ ｐｅｅｒ－ｔｏ－ｐｅｅｒ ｅｌｅｃｔｒｏｎｉｃ ｃｏｍｍｕｎｉｔｉｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００４，１６（７）：８４３—８５７． ［４］Ｍｉｃｒｏｎ Ｔｅｃｈｎｏｌｏｇｙ．Ｍｉｃｒｏｎ １ ＧｂＤＤＲ ＳＤＲＡＭ．Ｄａｔａ Ｓｈｅｅｔ［ＥＢ／ＯＬ］．［２００８・１ １—２１］．ｈｔｔｐ：／／ｗｗｗ．ｍｉｃｒｏｎ． ｃｏｍ／ｐｒｏｄｕｃｔｓ／ｄｒａｍ／ｄｄｒ２／ｐａｒｔｌｉｓｔ．ａｓｐ． ［５］Ｆａｎｇ Ｙｕ，Ｌａｋｓｈｍａｎ Ｔ Ｖ，Ｍａｒｔｉｎ Ａｕｓｔｉｎ Ｍｏｔｏｙａｍａ．Ｅｆｆｉ— ｆｉｅｎｔ Ｍｕｌｔｉｍａｔｃｈ Ｐａｃｋｅｔ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｆｏｒ Ｎｅｔｗｏｒｋ Ｓｅｃｕｒｉ． ｔｙ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００６，２４（１０）：１８０５—１８１６． ［６］亓亚炬，李军．高性能网包分类理论与算法综述［Ｊ］． 计算机学报，２０１３，３６（２）：４０８－４２１． ［７］ Ｋａｒｔｈｉｋ Ｌａｋｓｈｍｉｎａｒａｙａｎａｎ， Ｓｒｉｎｉｖａｓａｎ Ｖｅｎｋａｔａｃｈａｒｙ， Ａｎａｎｄ Ｒａｎｇａｒａｊａｎ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ａｄｖａｎｃｅｄ ｐａｃｋｅｔ ｃｌａｓ— ｓｉｆｉｃａｔｉｏｎ ｗｉｔｈ ｔｅｒｎａｒｙ ｃａｍｓ［ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ＩＥＥＥ Ｓｉｇ— ｃｏｍｍ．２００５：１９３－２０４． ［８］Ｓｒｉｎｉｖａｓａｎ Ｖ，Ｖａｒｇｈｅｓｅ Ｇ，Ｓｕｒｉ Ｓ．Ｆａｓｔ ａｎｄ Ｓｃａｌａｂｌｅ Ｌａｙ— ｅｒ Ｆｏｕｒ Ｓｗｉｔｃｈｉｎｇ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ＡＣＭ Ｓｉｇｏｍｍ． １９９８：１９卜２０２． ［９］Ｓｕｎ Ｈａｉ，Ｓｕｎ Ｙａｎ，Ｖａｌｇｅｎｔｉ，Ｖ Ｃ，ｅｔ ａ１．ＴＣＡＭ—ｂａｓｅｄ ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｕｓｉｎｇ ｄｉｖｉｄｅ－・ａｎｄ・・ｃｏｎｑｕｅｒ ｆｏｒ ｒａｎｇｅ ｅｘｐａｎ・・ ｓｉｏｎ［ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｎｅｔ— ｗｏｒｋｓ（ＩＣＣＣＮ）．２０１４：１５４．１６１． ［１Ｏ］Ｔａｙｌｏｒ Ｄ Ｅ．Ｓｕｒｖｅｙ Ｔａｘｏｎｏｍｙ ｏｆ Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ Ｔｅｃｈｎｉｑｕｅｓ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２００５，３７ （３）：２３８・２７５． ［１１］周立力．基于ＴＣＡＭ技术的高速路由查找方案［Ｊ］． 计算机应用，２００３，２３（９）：１７一ｌ９． ［１２］王志强，王振兴，张定心．快速路由查找算法研究 ［Ｊ］．计算机应用研究，２００４，２１（２）：２３１—２３４． ［１ ３］Ｄａｖｉｄ Ｅ Ｔａｙｌｏｒ，Ｊｏｎａｔｈａｎ Ｓ Ｔｕｒｎｅｒ．ＣｌａｓｓＢｅｎｃｈ：Ａ Ｐａｃｋｅｔ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ Ｂｅｎｃｈｍａｒｋ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ｔｈ ＩＥＥＥ ＩＮＦＯＣ０Ｍ．２００５：６４８—６５６．
