《计算机应用研究》|Application Research of Computers

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

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

免费全文下载 (已被下载 次)  
获取PDF全文
作者 李文军,刘馨蔚,邢凯轩,乐文霞,李挥
机构 1.北京大学深圳研究生院,广东 深圳 518055;2.鹏城实验室,广东 深圳 518055;3.北京大学 信息科学技术学院,北京 100871
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2021)01-047-0237-04
DOI 10.19734/j.issn.1001-3695.2019.09.0625
摘要 为了实现网络流的线速转发,高性能交换机普遍采用三态内容寻址存储器(TCAM)来构建其包分类引擎。针对TCAM功耗高的问题,近年来出现了许多低功耗索引方案,实现了TCAM存储块的选择性激活以降低功耗,但这些索引方案普遍采用自底向上的局部优化算法来构建,无法有效实现流表规则的均匀划分,严重影响了TCAM的存储效率及功耗降低效果。提出并实现了一种基于决策树映射的TCAM低功耗索引方案,在极大降低功耗的同时提升了TCAM的存储效率。利用规则普遍存在的小域特征,将原始规则集划分为若干个规则子集,然后针对各个子集的特征域,采用自顶向下的方式分别构建平衡决策树,最后通过对各个决策树进行贪心遍历,从而得到TCAM索引列表。实验表明,针对规模为十万条的规则集,算法在仅使用额外1.3%存储空间开销的同时实现了98.2%的功耗降低。
关键词 软件定义网络; OpenFlow; 包分类; 三态内容寻址存储器; 低功耗
基金项目 国家自然科学基金资助项目(61671001)
国家重点研发计划资助项目(2016YFB0800101,2017YFB0803204)
鹏城实验室资助项目(PCL2018KP001)
广东省重点领域研发计划资助项目(2019B010137001)
深圳市基础研究课题(JCYJ20170306092030521)
中国博士后科学基金资助项目(2020TQ0158,2020M682825)
本文URL http://www.arocmag.com/article/01-2021-01-047.html
英文标题 Decision tree based pre-classifier for energy-efficient TCAM based packet classification
作者英文名 Li Wenjun, Liu Xinwei, Xing Kaixuan, Le Wenxia, Li Hui
机构英文名 1.Peking University Shenzhen Graduate School,Shenzhen Guangdong 518055,China;2.Peng Cheng Laboratory,Shenzhen Guangdong 518055,China;3.School of Electronic Engineering & Computer Science,Peking University,Beijing 100871,China
英文摘要 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.
英文关键词 SDN; OpenFlow; packet classification; TCAM(ternary content addressable memory); energy-efficient
参考文献 查看稿件参考文献
 
收稿日期 2019/11/19
修回日期 2020/1/8
页码 237-240,255
中图分类号 TP393.07
文献标志码 A