基于决策树映射的低功耗TCAM包分类方案

Decision tree based pre-classifier for energy-efficient TCAM based packet classification

为了实现网络流的线速转发,高性能交换机普遍采用三态内容寻址存储器(TCAM)来构建其包分类引擎。针对TCAM功耗高的问题,近年来出现了许多低功耗索引方案,实现了TCAM存储块的选择性激活以降低功耗,但这些索引方案普遍采用自底向上的局部优化算法来构建,无法有效实现流表规则的均匀划分,严重影响了TCAM的存储效率及功耗降低效果。提出并实现了一种基于决策树映射的TCAM低功耗索引方案,在极大降低功耗的同时提升了TCAM的存储效率。利用规则普遍存在的小域特征,将原始规则集划分为若干个规则子集,然后针对各个子集的特征域,采用自顶向下的方式分别构建平衡决策树,最后通过对各个决策树进行贪心遍历,从而得到TCAM索引列表。实验表明,针对规模为十万条的规则集,算法在仅使用额外1.3%存储空间开销的同时实现了98.2%的功耗降低。

Due to the high-speed requirement of high-end network devices,hardware using TCAMs has been the dominant implementation of packet classification in industry.Despite its capability for line-speed queries,TCAM is not only power hungry but also capacity inefficient.By making use of a pre-classifier to activate TCAM blocks selectively,many research efforts significantly reduce the power consumption of TCAM.However,these bottom-up based pre-classifiers achieve power savings at the expense of poor utilization of TCAM capacity,and the potential of power reduction is not fully exploited in many cases.This paper proposed a power-saving pre-classifier for TCAM based packet classification,which constructed based on decision trees.By grouping rules with respect to their small fields,rules could be recursively mapped into decision trees without the trouble of rule replications,so that a top-down traversal algorithm could be well applied for obtaining index items.Experimental results show that for rule sets up to one hundred thousand entries,the proposed design achieves 98.2%power reduction with a TCAM storage overhead of 1.3%on average.