面向存储和功耗优化的TCAM报文分类算法研究

发布时间：2018-03-23 22:20

本文选题：报文分类　切入点：三态内容寻址存储器　出处：《解放军信息工程大学》2013年硕士论文

【摘要】：三态内容寻址存储器（TernaryContent-Addressable Memory，，TCAM）具有查询速度快、匹配时间固定等优点，目前广泛应用于报文分类和路由查表领域。但是TCAM还存在以下问题（1）TCAM不直接支持范围规则匹配，一条范围规则必须转换成多条TCAM表项，导致空间利用率较低；（2）TCAM的并行匹配机制导致高功耗，对系统设备的整体设计和布局提出了更高的要求。本文结合国家863计划课题“面向三网融合的统一安全管控网络”，对现有基于TCAM的报文分类算法进行分析总结，分别提出了一种基于域转换的范围匹配算法(DTRM)和一种基于三态位分割的低功耗算法(TSP-PR)，并在此基础上设计了一种高效的报文分类引擎实现方案。本文主要工作如下： 1、针对TCAM不直接支持范围规则匹配，导致空间利用率较低的问题，提出了一种基于域转换的范围匹配算法(Domain Transformation for Range Match，DTRM)。DTRM算法针对传统算法未充分利用TCAM表项中冗余位的不足，在DIRPE编码方法的基础上设计了一种支持任意比特数目的编码方法Smart-DIRPE，利用Smart-DIRPE对TCAM表项中的所有冗余位进行编码，构建新的范围域；根据Smart-DIRPE的编码特点和规则集中范围规则的分布特征，设计域转换函数，实现规则集原始范围域到新构建范围域的转换，使得规则集能够压缩为较少的TCAM表项。仿真结果表明，DTRM算法的扩张因子可达到1.21以下，TCAM空间利用率在82%以上，同时支持规则的增量更新。 2、针对TCAM采用并行匹配方式导致功耗较高的问题，提出了一种基于三态位分割的低功耗报文分类算法(Tri-State based Partition for Power Reduction，TSP-PR)。TSP-PR算法基于TCAM的分区匹配和三态位特性，提出了一种无规则复制的规则集划分方法，设计标志位选取函数，选取少量能够充分表达规则集内部特征信息的比特位，据此将规则集划分为多个具有不同特征的规则子集并存储在相应的TCAM分区，通过对TCAM分区的选择性查找降低功耗。仿真结果表明，TSP-PR算法在付出小于15%存储代价的情况下，功耗减少了70%以上。 3、基于DTRM和TSP-PR算法，结合三网融合管控平台，设计了一种基于TCAM的报文分类引擎实现方案。首先，给出了该引擎的总体框图以及各子模块的功能介绍；然后，详细介绍了DTRM和TSP-PR算法在分类引擎中的具体实现；之后，通过实际测试验证了本方案可获得较高的空间利用率和较低的功耗；最后，给出了理论功耗减少量与实际测试值存在偏差的原因。
[Abstract]:TernaryContent-Addressable memory (TCAM) is widely used in the field of packet classification and routing table lookup because of its advantages of fast query speed and fixed matching time. However, TCAM also has the following problems: it does not directly support range rule matching. A range rule must be converted into multiple TCAM table entries, resulting in a parallel matching mechanism with low space utilization, resulting in high power consumption. This paper analyzes and summarizes the existing packet classification algorithms based on TCAM, combined with the national 863 project, "the unified security control and control network oriented to three networks", which is the overall design and layout of the system equipment. A range matching algorithm based on domain transformation (DTRM) and a low power algorithm (TSP-PRN) based on tri-state bit segmentation are proposed, respectively. On this basis, an efficient packet classification engine is designed. The main work of this paper is as follows:. 1. Aiming at the problem that TCAM does not directly support range rule matching, which leads to low space utilization, a domain transform based range matching algorithm is proposed to solve the problem that the traditional algorithm does not make full use of the redundant bits in TCAM table items. Based on the DIRPE coding method, a new coding method, Smart-DIRPEE, which supports any number of bits, is designed. All redundant bits in the TCAM table are encoded by Smart-DIRPE, and a new range is constructed. According to the coding characteristics of Smart-DIRPE and the distribution of the rules in the rule set, the domain transformation function is designed to transform the original range of the rule set to the newly constructed scope domain. The result of simulation shows that the expansion factor of the algorithm can reach more than 82%, and the incremental updating of the rules can be supported at the same time. 2. In order to solve the problem of high power consumption caused by parallel matching in TCAM, a low power packet classification algorithm based on tri-state bit segmentation is proposed, which is based on the partitioned matching and tristate characteristics of TCAM, which is based on the algorithm of Tri-State based Partition for Power reduction and TSP-PRPPR. In this paper, a rule set partition method is proposed, in which the function of flag bit selection is designed, and a small number of bits which can fully express the feature information inside the rule set are selected. Based on this, the rule set is divided into several rule subsets with different characteristics and stored in the corresponding TCAM partition. The power consumption is reduced by selective lookup of the TCAM partition. The simulation results show that the TCAM PR algorithm pays less than 15% storage cost. Power consumption is reduced by more than 70%. 3. Based on DTRM and TSP-PR algorithm, a message classification engine based on TCAM is designed. Firstly, the overall block diagram of the engine and the function of each sub-module are introduced. The implementation of DTRM and TSP-PR algorithms in the classification engine is introduced in detail. After the actual test, it is proved that the scheme can achieve higher space utilization and lower power consumption. The reason of the deviation between the theoretical power consumption reduction and the actual test value is given.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP333

【参考文献】