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

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

【參考文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

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

本文編號(hào)：1655450