一种支持TCAM规则更新与压缩方法＊

蔡立军，李 杜，池 鹏，李 睿

（1.国家超级计算长沙中心，湖南 长沙 410082；2.湖南大学 信息科学与工程学院，湖南 长沙 410082）

一种支持TCAM规则更新与压缩方法＊

蔡立军1，2，李 杜2，池 鹏1†，李 睿2

（1.国家超级计算长沙中心，湖南 长沙 410082；2.湖南大学 信息科学与工程学院，湖南 长沙 410082）

提出了一种TCAM空间划分和规则压缩相结合的方法，使得OpenFlow网络在支持实时更新的同时能采用小容量的TCAM芯片来存储网络中的规则.所提方法将TCAM芯片空间划分为实时更新区和压缩存储区，实时更新区处在TCAM芯片的前部，用于存放中央控制器发送过来的实时更新规则.后台服务器以一定的时间周期将TCAM芯片中的实时更新区的规则以及压缩存储区中的规则进行压缩，并将压缩后的规则存入TCAM的压缩区，保持实时更新区具有空间接收实时更新规则.分析了区间划分的比率问题，并利用ClassBench工具产生原始规则集进行了仿真实验，实验结果验证了本文方法的有效性.

网络协议；OpenFlow；TCAM；规则压缩；实时更新；空间划分

OpenFlow［1］是一种新型网络交换模型，主要由OpenFlow交换机、FlowVisor和Controller三部分组成.OpenFlow交换机进行数据层的转发，FlowVisor对网络进行虚拟化，Controller对网络进行集中控制，实现控制层的功能.OpenFlow技术采用集中式的控制方法，由一个或多个包含整个网络拓扑的中心控制器通过一个开放的协议对不同交换机和路由器中的流表直接进行编程，从而实现对网络中数据流的控制.

为了实现数据包的高速转发，采用TCAM［2］芯片来存储与匹配路由规则已经成为OpenFlow网络中事实上的工业标准.TCAM是一种三态内容寻址存储器，查询时采用全并行的方式对所有单元的数据进行搜索，因此可以在一个时钟周期内完成数据的匹配.TCAM芯片在具有快速查询处理优点的同时，也存在如下不足［3］：1）存储空间小.TCAM 存储空间相当有限，目前比较流行的TCAM芯片的内存为2Mb或1Mb，最大的也只有18Mb.2）能耗高、散热大.在进行数据查询时，由于TCAM采用全并行方式对整个存储空间进行搜索，因此消耗的电能大，同时散发的热量也多.一个1Mb的TCAM芯片的功率可以达到15～30W，大功率消耗对于核心路由以及其他网络设备来说是一个非常严重的问题，因为在机箱内需要占用更大的面积.3）价格昂贵.TCAM芯片价格相当昂贵，特别是随着容量的增加，价格增加迅速.因此，采用小容量的TCAM芯片是解决TCAM芯片面临问题的有效途径.针对小容量的存储空间，国内外研究者在规则压缩方面开展了大量的研究工作［4－5］，但这些研究工作都是针对TCAM中规则相对稳定或者更新速度慢的情况.在OpenFlow网络中，规则更新频繁［6］.就我们所知，目前还没有研究工作研究如何在小容量的TCAM芯片中实现规则的实时更新.

为此，本文针对OpenFlow中规则更新频繁的特点，提出了一种支持规则实时更新和压缩的方法，在保证规则快速更新的同时，能够采用小容量的TCAM芯片来存储规则.为了同时支持快速更新以及规则压缩，本文提出了一种对TCAM芯片存储空间进行划分的方法，将TCAM芯片空间划分为实时更新规则区和压缩规则存储区，如图1所示.实时更新规则区处在TCAM芯片的前部，用于存储由中央控制器发来的最新更新规则集，压缩规则存储区存储压缩后的规则集.中央控制器持续向交换机下发规则，每隔一定的时间片段，将交换机中的规则集复制到规则处理服务器，由规则处理服务器负责对规则集采用规则压缩算法对其进行压缩处理，压缩算法处理结束后服务器向TCAM芯片发出规则更新来替换TCAM更新区和压缩区的规则.该结构一方面能够满足OpenFlow中的实时更新要求，另外一方面又防止控制器不断产生的更新规则导致规则集过大而无法用容量较小的TCAM芯片来存储的问题.

图1 实时更新与压缩Fig.1 Real-time updates and compression

1 相关工作

与本文工作最为相关的研究工作是数据包的分类以及防火墙领域的规则压缩.文献［5］提出了一种对一维包分类器的动态规划算法，其一维前缀压缩实验数据显示41 455条前缀的压缩比为58%，运行时间为2.73s.文献［6］提出的压缩算法总压缩比为54%，较以往的压缩算法在压缩效果上已经有了部分改进，但在该文中未公布其算法运行时间.在此基础上，文献［3］提出了一种多维规则的压缩算法，总的压缩比为3.9%，压缩效果有了大幅度的提高，但是缺点在于算法运行速度比较慢，661条规则压缩运行时间为31.9s.这些研究工作都是针对静态规则集的压缩，没有考虑规则的实时更新问题.

OpenFlow网络具有规则更新快的特点，仅仅考虑规则的压缩而忽略规则的更新是没有意义的，而目前规则压缩的研究还未延伸到OpenFlow领域，因此本文的主要难点在于如何科学分配TCAM芯片中的实时更新区和压缩存储区，使得TCAM芯片既能持续不断地接收中央控制器发出的最新规则，又能将已有规则集进行有效压缩.

2 基本概念

本节给出相关概念的定义.一个域Fi的一个区间变量，记作D（Fi），是一个非负整数的有限区间，比如［0，100］.TCAM 规则形式为 〈predicate〉→〈decision〉，其中predicate的形式为F1∈S1∧ …∧Fd∈Sd，其中每一个Si都是D（Fi）的非空子集当且仅当p1∈S1∧ …pd∈Sd，一个数据包（p1，…，pd）和一条predicate匹配［7］.decision指满足匹配之后执行的指令，典型的decision包括accept，disgard，accept with logging，disgard with logging.

在一个规则序列f中可能存在这种情况，其中的两条或者多条规则的区间部分重叠或其中一个区间包含于另一个区间，甚至两条规则不但重叠而且具有不同的decision.为了解决这个矛盾，TCAM采用首匹配原则，也就是说一个包p的decision是p在f中匹配到的第一个规则的decision，数据包p在f中匹配的decision用f（p）表示［8］.两个规则序列f1，f2等价，当且仅当对于任意包p都有f1（p）＝f2（p），记作f1≡f2.对于任意规则序列f，我们用 ｛f｝表示所有与f等价的规则集合.

规则的压缩：对于一个规定的规则序列f，找到另一个语义与f等价的规则序列g，其中g拥有尽可能少的规则数量.

压缩比：压缩比＝压缩后规则数／原始规则数.

3 空间划分

为了实现压缩与更新的平衡，将TCAM芯片的存储空间分为两个区域：实时更新区和压缩规则存储区.实时更新区中存储了由中央控制器发来的最新更新规则.TCAM芯片采用的是首匹配方式进行规则匹配，因此，实时更新区处在TCAM的前部.压缩规则区存储压缩后的规则.引入规则处理服务器负责对TCAM中的规则进行处理规则集的压缩.规则处理服务器定期向TCAM芯片发出规则更新来替换TCAM压缩区的规则.采用该结构，一方面能满足OpenFlow中的实时更新要求，另外一方面又防止控制器不断产生的更新规则导致规则集过大而无法用容量较小的TCAM芯片来存储的问题.

中央控制器持续向TCAM芯片传输最新的规则集，每隔一定的时间周期，将其中的规则集复制到规则压缩处理器中进行压缩算法处理，在算法处理过程中由中央控制器传输的最新规则保存在实时规则更新区，压缩算法处理结束之后，将压缩后的规则集替换压缩规则存储区中的规则集，然后将实时规则更新区中的规则集转移至压缩规则存储区，如此循环进行算法处理，以达到规则实时更新以及压缩的目的.

TCAM中规则的实时更新以及压缩过程如图2所示.假设TCAM芯片容量总共可以存储S条规则，进行空间划分之后实时更新区可以存储α条规则，压缩存储区可以存储β条规则，其中有：

图2 TCAM芯片状态Fig.2 TCAM chip status

假设后台服务器对规则进行压缩的时间周期为T，网络中规则的更新速度为v条／s，算法运行时间为t，规则压缩算法的压缩比为r，r＜1.因此每一个时间周期内在实时更新区内更新的规则数为vT.上文已经提到，TCAM芯片采用的是首匹配原则，因此新的规则总是存放在规则集的顶端.在状态1，实时更新区处于相对空白状态，此时将TCAM中的规则复制到压缩服务器，在服务器中进行压缩算法处理.在状态2，算法结束经过一个时间周期之后将已压缩的规则集存放在TCAM的底部，此时实时更新区内已积累v T条规则.在状态3，将压缩之后的规则集与最新的更新规则组成新的规则集存放在TCAM中，重新返回状态1，进入下一个循环.

定理1 规则的更新与压缩机制中所运用的规则压缩算法运行时间t须满足：

定理2 更新与压缩过程中一个时间周期T的取值范围为：

证 因为规则压缩算法运行时间为t，所以必须等待t时间之后才能将压缩后的规则集导入TCAM芯片.因为规则持续更新的速度为v，在S／v的时间段内TCAM芯片内存将占用完毕而导致没有更多的空间存放即将接受的新规则.

证毕.

定理3 当时间周期一定时，同时实现规则的更新与压缩的必要条件为TCAM芯片的空间不小于v T （2－r）／（1－r）.

证 如图2所示，规则的更新与压缩是一个动态的循环过程，在每一次循环中都要对β条规则进行一次压缩处理，为了保证压缩过程中实时更新区的规则不溢出，实时更新区所分配的空间必须满足：

α≥vT.

压缩算法结束之后，将已压缩的规则集替换压缩存储区内的旧规则集，压缩之后的规则集存放在压缩存储区的底部，同时压缩存储区腾出的空间为β－rβ.此时将实时更新区内的最新规则转移至压缩存储区的顶部，为了保证压缩之后的规则集不占用实时更新区的空间而导致规则溢出，那么压缩存储区所占空间必须满足：

证毕.

在压缩算法、时间周期以及TCAM芯片空间容量等条件得到满足的前提下，对TCAM区间进行划分，分析一定容量TCAM芯片内实时更新区以及压缩存储区所占空间的比例.

性质1 当其他参数一定时，实时更新区在TCAM芯片中所需空间随规则更新速度的增大而增大.

性质2 当其他参数一定时，压缩存储区在TCAM芯片中所需空间随规则压缩比的增大而增大.

例如，当时间周期T以及规则更新速度v一定时，选择不同的规则压缩算法，则压缩存储区所占空间也会有差别.当r＝0.5时，β的最小取值为2vT，当r＝0.9时，β的最小取值为10 vT.

当实时更新区所占空间取最小值v T时，压缩存储区分配的空间为S－v T，当压缩存储区所占空间取最小值v T／（1－r）时，实时更新区的空间为S－v T／（1－r），由此可得TCAM芯片中实时更新区和压缩存储区所占空间比例的取值范围.

新媒体信息传播的量更大，在新闻中可以涵盖图片、音频、视频等多种信息资源。同时，新媒体时代相关的信息链接可以随意打开，这是传统的报纸行业无法做到的。最后，信息互动性更强。互动性是新媒体时代信息传播的典型特点。在这种形势下，信息传播主体和客体之间的界限不再明显，人们不仅是新闻内容的传播者，同时也是信息的发布和评论者，在互动交流的共同影响下形成了新的信息传播模式。新媒体时代人们对新闻的阅读兴趣大大提高，可以根据自身需要选择个性化的信息服务。不仅如此，新闻信息更加生活化和平民化，这势必会对传统报纸行业产生非常重大的影响。

引理1 TCAM芯片中实时更新区和压缩存储区所占空间比例取值范围为：

4 规则压缩算法

本文设计一种适用于快速更新的动态规则压缩算法，主要思想为在不改变规则集语义的前提下将规则集转换为一个等价的BDD［9］，再将实时更新的规则集嵌入改变缩减之后的BDD，最后将BDD转换为等价的规则集以减少规则集中的规则数量从而达到压缩规则的目的.将更新与压缩两种操作结合在一起，不仅能够满足网络中快速更新规则的需要，而且可以提高规则集的压缩效率.

一个二叉决策图Binary Dicesion Diagram（BDD）是有限个节点的有向无环图G＝（V，E），其中，V是G中所有节点的集合，E是G中所有边的集合.其中一个BDD满足如下4个条件：

1）存在一个decision集合DS；

2）存在一个根节点，其不存在父节点，存在若干叶子节点，其不存在子节点；

3）每一个叶子节点对应一个decision，记为D（v）；

4）一条从根节点到decision的路径对应规则集中的一条或多条规则.

图3 BDD示意图Fig.3 A binary decision digram

对于一个已转换的BDD进行改编缩减.在这里提出BDD规则压缩算法.

算法1 BDDCompress（node）.

图4为改编缩减后的BDD，其语义与图3等价.

图4 压缩后的BDDFig.4 A reduced binary decision diagram

本文的压缩策略是在规则快速更新的Open－Flow网络中，将实时的更新规则嵌入已有的压缩BDD，嵌入的过程完成冗余规则的去除以及特定规则的合并，最后将BDD转换为等价的规则集.

对于一个网络中实时更新的规则集f，本文的动态规则压缩算法分为如下3个步骤：

转换后的BDD如图5所示.

BDD中的每一个decision都对应一条规则，该规则由一条或多条路径合并而成.从decision开始寻找其父节点直到根节点，若某个decision所对应的叶子节点只存在一个父节点，那么从其到根节点的路径唯一，且对应一条或多条压缩后的规则；若某个decision存在多个父节点，那么从其到跟节点的路径中必然存在可以合并的两条或多条路径，此时对其各路径进行判断并对满足条件的边进行合并.图4所示BDD中dicesion1只有一个父节点，因此从其到根节点的路径唯一，对应的规则为：r1：F1∈［0，7］∧F2∈ ［8，15］→disgard.dicesion2存在2个父节点node2，node3，将node1至node2的边和node1至node3的边所对应的区间合并得到规则：r2：F1∈ ［0，15］∧F2∈ ［0，7］→accept.图4所示BDD转换为规则集如下：

假设压缩服务器中规则集的规则数目为n，实时更新的规则数目为k，由于算法需要先将规则集转换为等价的BDD，且BDD中的每一个叶子节点对应一条规则，而调用BDD动态规则压缩算法时需要将更新BDD中的每一条从根节点到叶子节点的路径与压缩BDD中的每一条从根节点到叶子节点的路径匹配，因此BDD动态规则压缩算法的时间复杂度为O（kn）.这种动态更新与压缩的算法避免了每一次规则更新之后都将压缩服务器中的规则集与更新的规则集重新进行一次压缩算法处理，节约了运行时间，提高了规则压缩的效率.

图5 转换后的BDDFig.5 Converted BDD

将图5中的BDD嵌入图4的BDD中，得到新的BDD如图6所示.

图6 规则压缩算法实验结果Fig.6 Rules compression algorithm results

5 实 验

网络中的实际规则集由于安全保密等原因很难获得，因此本文中实验用的规则集利用华盛顿大学圣路易斯分校Taylor和Turner开发的工具Class－Bench产生.ClassBench产生的规则集中的每条规则包含了6个域：源IP地址、目的IP地址、源端口、目的端口、协议类型和标志域.其中源IP地址和目的IP地址以前缀表示，源端口和目的端口以范围表示，协议类型和标志域以某种精确数据类型表示.实验过程首先利用ClassBench生成若干条规则，然后利用正则表达式从规则集中截取源端口和目的端口作为实验源数据生成二维规则集，最后对二维规则集进行仿真实验，其中每条规则域的区间为［0，65 535］.因为ClassBench工具产生的规则不包含decision项，所以在仿真实验时每一条规则都随机产生一个decision，其中设置decision仅包含accept和disgard.图7为ClassBench生成的5条规则组成的规则集.

图7 ClassBench工具生成的规则Fig.7 Rules producesd by ClassBench

图8为算法1对20组从50～1 000条不同数量的规则所组成的规则集进行压缩处理的实验数据图，从图8可以看出，压缩算法具有较高的压缩比，1 000条规则的压缩比接近30%.

实验过程中利用ClassBench工具产生100 000条规则作为原始规则集，以不同的更新速度向仿真TCAM容器内传输规则集，利用上述规则压缩算法对规则进行周期性压缩，对规则更新速度v、仿真容器容量S、时间周期T等参数进行设置，并以上文的理论为依据对仿真TCAM容器进行区间划分，采用BDD动态规则压缩算法对压缩处理器中的实时更新规则进行压缩并实时记录容器规则数量的变化.实验采用java在PC机上（Inter Core2双核CPU，2.53GHz，2GB内存）实现.

图8 规则压缩算法实验结果Fig.8 Rules compression algorithm results

图9和图10分别为仿真容器容量S取值800和1 500时对于不同的规则更新速度选取不同的压缩周期并对其进行区间划分后仿真容器内规则数目变化的情况展示.以图9为例，当S＝800，v＝10时，规则平均压缩比约为r＝0.5，压缩算法运行时间t＜5，根据不等式（3）可得时间周期T的取值范围为5≤T≤80，因此可取时间周期T为20，又因为.

图9 S＝800时规则数量变化Fig.9 Number of rules changes when S＝800

图10 S＝1 500时规则数量变化Fig.10 Number of rules changes when S＝1 500

因此仿真容器容量的大小满足所需条件，根据不等式（4）可得仿真TCAM芯片中实时更新区和压缩存储区所占空间比例取值范围为：

在实验中取α∶β＝3∶5，从实验结果可以看出，在一个时间周期内，仿真容器中的规则呈线性增长，而每隔一个时间周期，仿真容器中的规则就会被压缩一次，最终容器内的规则在一定范围内波动.

6 结束语

本文针对OpenFlow网络中规则需要进行实时更新以及TCAM芯片容量受限等问题，提出了一种对TCAM区间进行划分和规则压缩的方法.为了验证规则压缩算法的效果和效率，采用ClassBench工具产生原始规则集，并对不同的规则更新速度根据论文的理论基础对仿真TCAM容器进行区间划分，实验采用java在PC机上实现.实验结果证明本文提出的压缩与更新的平衡机制能够很好的对快速更新的规则进行实时动态压缩.

［1］ KEMPF J，BELLAGAMBA E，JOCHA D.Scalable fault management for OpenFlow［C］／／Communications（ICC），2012IEEE International Conference on.Ottawa，ON：IEEE，2012：6606－6610.

［2］ BREMLER-BARR A，HENDLER D.Space-efficient TCAM-based classification using gray coding［J］.Computers，IEEE Transactions on，2012：18－30.

［3］ CHAD R M，ALEX X L，ERIC T.TCAM razor：a systematic approach towards minimizing packet classifiers in TCAMS［C］／／Network Protocols，ICNP 2007，IEEE International Conference on.Beijing：IEEE，2007：266－275.

［4］ TAYLOR D E，TURNER J S.Class bench：apacket classification benchmark［C］／／Association for Computing Machinery，Networking，IEEE／ACM Transactions on.Miami：IEEE，2005：2068－2079.

［5］ DONG Qun-feng，BANERJEE S，WANG Jia.Packet classifiers in ternary CAMs can be smaller［C］／／SIGMETRICS＇06／Performance＇06 Proceedings of the Joint International Conference on.New York：ACM，2006：311－322.

［6］ DELY P，KASSLER A，BAYER N.OpenFlow for wireless mesh networks［C］／／Computer Communications and Networks（ICCCN），2011Proceedings of 20th International Conference on.Maui：IEEE，2011：1－6.

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

ZHU Guo-sheng，YU Shao-hua.Range matching method based on TCAM：C-TCAM［J］.Journal on Communications，2012，33（1）：31－37.（In Chinese）

［8］ YAN S，KIM M S.Tree-based minimization of TCAM entries for packet classificaion［C］／／Consumer Communications and Networking Conference（CCNC），2010 7th IEEE.Las Vegas：IEEE，2010：1－5.

［9］ CHAD R M，LIU A X，TORNG E.Topological transformation approaches to optimizing TCAM－based classification systems［C］／／SIGMETRICS＇09Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems.New York：ACM，2009：73－84.

A New Method for Rule Real-time Updates and Compression in TCAM

CAI Li-jun1，2，LI Du2，CHI Peng1†，LI Rui2
（1.National Supercomputing Center in Changsha，Changsha，Hunan 410082，China；2.College of Computer Science and Electronic Engineering，Hunan Univ，Changsha，Hunan 410082，China）

This paper presented an approach which combines space division and rules compression in an effort to allow the real-time updates and TCAM chips storage happening at the same time.In the approach，the TCAM chip was divided into two partitions，a real-time update area and a compression storage area.The former was assigned in the front of the chip for storing real-time updating rules sent by the controller，and the latter had the function of compressing and storing rules generated by the server within certain time period.We made a comprehensive analysis of the space division ratio and conducted simulation experiments on the rules generated by the ClassBench tool.The experiment results have demonstrated the effectiveness of the approach.

network protocols；OpenFlow；ternary content addressable memory（TCAM）；rules compression；real-time update；space division

TP393.2

A

1674-2974（2014）08-0094-07

2014-01-13

国家科技支撑计划资助项目（2012BAH09B02）；长沙市重点科技计划资助项目（K1204006-11-1）

蔡立军（1964－），男，湖南常德人，湖南大学教授，博士

†通讯联系人，E-mail：chipeng＠189.cn