本文選題：報文分類　切入點：三態(tài)內(nèi)容尋址存儲器　出處：《解放軍信息工程大學》2013年碩士論文

【摘要】：三態(tài)內(nèi)容尋址存儲器（TernaryContent-Addressable Memory，，TCAM）具有查詢速度快、匹配時間固定等優(yōu)點，目前廣泛應用于報文分類和路由查表領域。但是TCAM還存在以下問題（1）TCAM不直接支持范圍規(guī)則匹配，一條范圍規(guī)則必須轉(zhuǎn)換成多條TCAM表項，導致空間利用率較低；（2）TCAM的并行匹配機制導致高功耗，對系統(tǒng)設備的整體設計和布局提出了更高的要求。本文結(jié)合國家863計劃課題“面向三網(wǎng)融合的統(tǒng)一安全管控網(wǎng)絡”，對現(xiàn)有基于TCAM的報文分類算法進行分析總結(jié)，分別提出了一種基于域轉(zhuǎn)換的范圍匹配算法(DTRM)和一種基于三態(tài)位分割的低功耗算法(TSP-PR)，并在此基礎上設計了一種高效的報文分類引擎實現(xiàn)方案。本文主要工作如下： 1、針對TCAM不直接支持范圍規(guī)則匹配，導致空間利用率較低的問題，提出了一種基于域轉(zhuǎn)換的范圍匹配算法(Domain Transformation for Range Match，DTRM)。DTRM算法針對傳統(tǒng)算法未充分利用TCAM表項中冗余位的不足，在DIRPE編碼方法的基礎上設計了一種支持任意比特數(shù)目的編碼方法Smart-DIRPE，利用Smart-DIRPE對TCAM表項中的所有冗余位進行編碼，構(gòu)建新的范圍域；根據(jù)Smart-DIRPE的編碼特點和規(guī)則集中范圍規(guī)則的分布特征，設計域轉(zhuǎn)換函數(shù)，實現(xiàn)規(guī)則集原始范圍域到新構(gòu)建范圍域的轉(zhuǎn)換，使得規(guī)則集能夠壓縮為較少的TCAM表項。仿真結(jié)果表明，DTRM算法的擴張因子可達到1.21以下，TCAM空間利用率在82%以上，同時支持規(guī)則的增量更新。 2、針對TCAM采用并行匹配方式導致功耗較高的問題，提出了一種基于三態(tài)位分割的低功耗報文分類算法(Tri-State based Partition for Power Reduction，TSP-PR)。TSP-PR算法基于TCAM的分區(qū)匹配和三態(tài)位特性，提出了一種無規(guī)則復制的規(guī)則集劃分方法，設計標志位選取函數(shù)，選取少量能夠充分表達規(guī)則集內(nèi)部特征信息的比特位，據(jù)此將規(guī)則集劃分為多個具有不同特征的規(guī)則子集并存儲在相應的TCAM分區(qū)，通過對TCAM分區(qū)的選擇性查找降低功耗。仿真結(jié)果表明，TSP-PR算法在付出小于15%存儲代價的情況下，功耗減少了70%以上。 3、基于DTRM和TSP-PR算法，結(jié)合三網(wǎng)融合管控平臺，設計了一種基于TCAM的報文分類引擎實現(xiàn)方案。首先，給出了該引擎的總體框圖以及各子模塊的功能介紹；然后，詳細介紹了DTRM和TSP-PR算法在分類引擎中的具體實現(xiàn)；之后，通過實際測試驗證了本方案可獲得較高的空間利用率和較低的功耗；最后，給出了理論功耗減少量與實際測試值存在偏差的原因。
[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

【參考文獻】

相關碩士學位論文 前1條

1 趙地;嵌入式計算機系統(tǒng)功耗散熱分析及優(yōu)化設計[D];西安電子科技大學;2007年

本文編號：1655450