戴紫彬　劉航天

（信息工程大學密碼工程學院鄭州450004）

?

基于布魯姆過濾器算法和三態(tài)內(nèi)容尋址存儲器的高效范圍匹配方法

戴紫彬劉航天*

（信息工程大學密碼工程學院鄭州450004）

該文基于布魯姆過濾器算法和三態(tài)內(nèi)容尋址存儲器（Ternary Content Add ressable Memory，TCAM）技術(shù)提出一種高效范圍匹配方法，解決了目前TCAM范圍匹配方案存在的存儲利用率低、功耗大的問題。設(shè)計基于最長共同前綴的分段匹配算法（Segmented Match on Longest Common Prefix，SMLCP）將范圍匹配拆分為前綴匹配和特征區(qū)間比對兩步，TCAM空間利用率達到100%。根據(jù)SM LCP算法設(shè)計了BF-TCAM模型，使用布魯姆過濾器對關(guān)鍵字過濾，屏蔽無關(guān)項參與比較，大幅降低功耗。使用流水線縮短關(guān)鍵路徑長度，使查找操作在一個時鐘周期內(nèi)完成。研究結(jié)果表明，所提方法實現(xiàn)了零范圍擴張，工作功耗較傳統(tǒng)TCAM降低50%以上。

范圍匹配；布魯姆過濾器；三態(tài)內(nèi)容尋址存儲器；零范圍擴張；低功耗

1　引言

范圍匹配廣泛應(yīng)用于網(wǎng)絡(luò)3到4層的報文分類，根據(jù)源端口和目的端口字段匹配端口范圍，實現(xiàn)訪問控制、安全過濾、帶寬控制等功能［1，2］。在存儲保護方面也有較多應(yīng)用，比如審查進程發(fā)起的訪存操作地址是否匹配其權(quán)限內(nèi)的存儲空間實現(xiàn)安全訪問控制［3，4］。這些實時應(yīng)用對查找性能要求很高，高速的范圍匹配是實現(xiàn)實時應(yīng)用的技術(shù)支撐。

目前業(yè)界普遍使用三態(tài)內(nèi)容尋址存儲器（Ternary Content Addressable Memory，TCAM）實現(xiàn)高速查找表。TCAM突出的問題在于它不適用于范圍匹配，只能實現(xiàn)精確匹配和前綴匹配。比如TCAM可以方便地表達報文分類中的協(xié)議字段和IP地址字段，但端口范圍無法直接實現(xiàn)。目前已有方案是將范圍匹配轉(zhuǎn)換成前綴匹配和精確匹配，一個范圍字段往往映射出多條匹配表項，稱為范圍擴張（rangeexpansion）。范圍擴張降低了TCAM空間使用效率，造成了較大的配置負載，提高了更新代價，同時使TCAM的功耗問題雪上加霜。

文獻［5］提出一種基于域轉(zhuǎn)換的范圍匹配算法DTRM（Domain Transformation for Range Match），充分利用TCAM表項中的冗余位壓縮規(guī)則集，理想情況下可使范圍擴張因子達到1.21以下，TCAM空間利用率提高到82%以上。文獻［6］提出一種基于TCAM的范圍匹配方法C-TCAM（Com pressed TCAM），通過二級壓縮將2個擴展后的表項壓縮成一個，最壞情況下范圍擴張因子為W-1或W-2（W為關(guān)鍵字二進制編碼位寬，如端口號位寬為16），同時減少查找過程中無效表項參與比較來降低功耗。文獻［7］提出了基于格雷碼的范圍編碼方法SRGE（Short Range Gray Encoding），利用格雷碼相鄰編碼之間只有一位不同的特點對規(guī)則集進行壓縮，但隨著范圍長度增加格雷編碼效率大打折扣，只適用于較小范圍，最壞情況下擴展因子達到了2W-2。文獻［8］提出一種用于范圍查找的新型存儲器結(jié)構(gòu)SBiCAM（Smart Binary Content Addressable Mem ory），無需規(guī)則擴展，直接實現(xiàn)關(guān)鍵字與表項并行比較大小，打破了傳統(tǒng)的TCAM位比較結(jié)構(gòu)，因而可實現(xiàn)高效的范圍匹配。但SBiCAM是一種新型電路，投入實際應(yīng)用尚需時日，從TCAM的發(fā)展歷程可以判斷SBiCAM即使投入生產(chǎn)也要經(jīng)歷一段漫長歷程才能達到較理想的性能以滿足應(yīng)用需求。

本文為解決基于TCAM的范圍匹配問題提供了高效解決方案，在實現(xiàn)零范圍擴張的同時大幅降低TCAM功耗。提出基于最長共同前綴的分段匹配算法（Segmented Match on Longest Common Prefix，SMLCP），將范圍匹配轉(zhuǎn)化為前綴匹配和特征區(qū)間比對兩個步驟，實現(xiàn)了零范圍擴張，使TCAM空間利用率達到100%。根據(jù)SM LCP算法設(shè)計了BFTCAM模型，結(jié)合B loom filter的前綴分類處理優(yōu)勢和TCAM的高速查找特性，在保持高性能的同時大幅降低了TCAM功耗。

2　 SM LCP算法

2.1問題描述

首先對范圍匹配問題進行形式化描述，以準確無誤地表達問題實質(zhì)，為SMLCP算法提供理論基礎(chǔ)。

范圍匹配問題等價描述為：給定一整數(shù)x，在S中定位包含x的元素即］使如圖1所示。同時S集支持元素的動態(tài)插入與刪除。

下面給出算法涉及的幾個名詞解釋：

（1）最長共同前綴（Longest Comm on Prefix，LCP）：范圍是一系列連續(xù)整數(shù)，位于數(shù)軸上的一段閉區(qū)間。最小的整數(shù)稱為起點，最大的整數(shù)稱為終點，構(gòu)成范圍的兩個端點。起點與終點的二進制編碼從第1個不同的比特位到最低位用*替代（*表示不關(guān)注），構(gòu)成三態(tài)表示，這樣的一個包含*的W位二進制編碼稱為范圍的最長共同前綴（W為二進制編碼位寬）。如8位范圍［22:38］，起點22的二進制編碼為0001_0110，終點38的二進制編碼為0010_0110，則

圖1　范圍匹配的形式化描述

（2）特征區(qū)間（feature range）：范圍起點與終點去除最長共同前綴后組成的新區(qū)間，它不改變范圍的規(guī)模，標識了范圍內(nèi)所有整數(shù)的上限與下限，位寬為W-length（LCP）。如范圍［22，38］的特征區(qū)間為［01_0110:10_0110］，位寬由8減為6。

（3）偏移量（offset）：范圍內(nèi)的一個整數(shù)，其二進制編碼去除最長共同前綴后的數(shù)值，標明了它在特征區(qū)間內(nèi)的偏移量，位寬與特征區(qū)間一致。如范圍［22:38］內(nèi)的整數(shù)31，偏移量為O ffset（31）=01_ 1111。

2.2算法設(shè)計與證明

范圍［s，t］內(nèi)任意一整數(shù)點x，其二進制編碼分為LCP和O ffset兩段，SMLCP算法利用這種特性，將匹配過程分段進行：首先查找與關(guān)鍵字x任意長度前綴相匹配的范圍，至多有W個范圍的LCP與x相匹配，然后再根據(jù)x的O ffset精確篩選出匹配的范圍。算法的關(guān)鍵在于第1步將搜索范圍減少至W個以下，大幅縮小了匹配范圍。

定理1范圍［s，t］兩端點s，t的LCP是范圍內(nèi)所有整數(shù)點的最長共同前綴且這種對應(yīng)關(guān)系是唯一的。

定理1要從LCP前綴值和前綴長度兩個維度予以證明，包括：

（2）所有范圍的LCP構(gòu)成的集合稱為標識集，P=LCP（s，t）是［s，t］內(nèi)所有整數(shù)點共同前綴中最長的，即在標識集中不存在比P更長的LCP與范圍內(nèi)所有整數(shù)點相匹配。

范圍為一個整數(shù)點時其前綴長度最長，容易處理，為方便證明，首先設(shè)定范圍［s，t］至少包含兩個整數(shù)點。定理1證明如下：

首先證明（1），分為兩種情況：

（a）當h=g=x即范圍［h，g］為一整數(shù)點時，

LCP為其自身，即LCP（h，g）=x。

∵P=LCP（s，t）的前綴長度小于x，

∴P≠x，得證。

（b）當h≠g時，使用反證法，

假設(shè)LCP（h，g）=LCP（s，t）=P，

令［h，g］在數(shù)軸上位于［s，t］的左邊，即g＜s。

則h，g，s，t可以表示為

h=P 0*，g=P 1*，s=P 0*，t=P 1*。

∵g＜s，

∴有P1*＜P0*，

假設(shè)產(chǎn)生矛盾，得證。

下面證明（2），P=LCP（s，t），LCP（S）為標識集。使用反證法，假設(shè)?PQ∈LCP（S），對于?x∈［s，t］，LCP（x）=PQ，其中PQ表示覆蓋P的前綴，只需在［s，t］中找出與PQ不匹配的整數(shù)即可證明假設(shè)錯誤，從而得證。

為方便證明，設(shè)定Q=0。分兩種情況：

（a）當［s，t］包含3個及3個以上的整數(shù)點，則有u=P10..0∈［s，t］（0..0表示1個或若干個0），

但LCP（u）≠P0。

假設(shè)產(chǎn)生矛盾，得證。

（b）當［s，t］僅包含兩個整數(shù)點，

則s=P0，t=P1，

顯然LCP（t）≠P0，即得證。

綜上所述，定理1得證。

LCP適于TCAM存儲，無需范圍擴張就可以唯一表示范圍，實現(xiàn)了TCAM的高效存儲，使存儲利用率達到100%。對于關(guān)鍵字x，其任意長度的前綴可能與標識集中多個LCP相匹配，但其中至多只有一個LCP對應(yīng)的范圍包含x。例如R1為［37，57］，R2為［32，36］，P1=LCP（R1）=001*_****，P2=LCP（R2）= 0010_0***，關(guān)鍵字x=0010_0101（37）同時與P1，P2相匹配，但只有R1命中x。要實現(xiàn)精確查找，還要對與關(guān)鍵字前綴相匹配的所有范圍進行篩選。需要指出，并非一定是與關(guān)鍵字前綴相匹配的最長LCP包含x，上例中雖然P2覆蓋了P1，但其對應(yīng)范圍R2并不真正包含x。易得知，如果存在多個范圍的LCP與關(guān)鍵字前綴匹配，則這些LCP之間存在覆蓋關(guān)系，且數(shù)量不會超過關(guān)鍵字的位寬。

定理2對關(guān)鍵字進行分段匹配：當關(guān)鍵字某一長度前綴與范圍LCP相匹配且偏移量位于特征區(qū)間內(nèi)，則與該范圍匹配，否則不匹配。定理2易于證明，不再予以詳細論證。

SM LCP算法具體實現(xiàn)時，由TCAM和RAM分別存儲范圍LCP和特征區(qū)間，使用TCAM完成第1步關(guān)鍵字前綴與LCP的比較，縮小查找范圍，然后以TCAM匹配表項的位置作為地址索引RAM，查看關(guān)鍵字偏移量是否位于特征區(qū)間，完成第2步精確匹配。SMLCP算法將范圍匹配問題轉(zhuǎn)化為前綴匹配和偏移比對兩個步驟，在沒有擴展規(guī)則集的情況下實現(xiàn)了精確查找，因而其擴張因子僅為1.0。因為SM LCP算法存在離散范圍的前提條件，所以在規(guī)則制定中要注意各個范圍不能重疊，相互之間不可存在交集。

3　 BF-TCAM模型

3.1模型設(shè)計

布魯姆過濾器（B loom filter）是一種空間效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，利用位數(shù)組簡潔地表示一個集合，能判斷一個元素是否屬于該集合。B loom filter包含一個m位的位數(shù)組，初始狀態(tài)每一位都置為0。為了表達含有n個元素的集合B loom filter使用k個相互獨立的哈希函數(shù)Hash_i分別將集合中每個元素映射到｛1，2，，｝m…的范圍中［911］-。

按前綴長度將范圍分為不同集合，比如IP報文端口號有16位，將端口范圍按LCP長度劃分為16個子集，每個子集單獨存儲于TCAM中的一塊區(qū)域。為降低TCAM的功耗，生產(chǎn)廠家在設(shè)計時將TCAM進行了分塊，通過配置寄存器實現(xiàn)片選，只有選中的塊參與運算。在查找時首先通過Bloom filter篩選出關(guān)鍵字可能所在的集合，然后驅(qū)動相應(yīng)的TCAM塊完成查找，這樣僅被選中的TCAM塊參與查找，功耗大幅降低。為進一步優(yōu)化存儲空間，可根據(jù)前綴長度的分布規(guī)律分配各個子集的存儲空間。

BF-TCAM模型由4類單元構(gòu)成：基于B loom filter的前綴預(yù)處理BFPP（Prefix Prep rocessing unit on Bloom Filter）單元，TCAM_RAM單元，更新單元（Updata Unit）和狀態(tài)單元（State Unit），如圖2所示。

BFPP單元對關(guān)鍵字進行判斷，篩選出關(guān)鍵字可能所在的前綴子集。為每個長度的前綴子集設(shè)置B loom filter，分別為判斷關(guān)鍵字是否屬于長度為i的前綴子集。所有B loom filter對關(guān)鍵字相應(yīng)長度的前綴并行運算，判斷結(jié)果組成匹配向量，表明關(guān)鍵字命中的前綴子集。匹配向量作為TCAM的塊區(qū)域片選信號，被選中的塊區(qū)域參與關(guān)鍵字的前綴匹配運算。如果關(guān)鍵字沒有命中任何B loom filter，則可判斷關(guān)鍵字無效，通知狀態(tài)單元。

圖2　 BF-TCAM模型電路結(jié)構(gòu)解析

TCAM_RAM單元存儲了所有范圍的LCP、特征區(qū)間及附屬信息，每個前綴子集對應(yīng)一組TCAM_RAM，由片選信號進行選擇。其中TCAM中存儲范圍的LCP，在BFPP單元選中的塊區(qū)域中搜索與關(guān)鍵字匹配的表項，以匹配表項的地址索引RAM。RAM中存儲了范圍的特征區(qū)間及附屬信息，如端口范圍和控制信息。每個子集（除長為w的子集）設(shè)置比較器判斷關(guān)鍵字偏移量是否位于特征區(qū)間內(nèi)，w長子集為精確匹配，不存在特征區(qū)間，無需進行比較。特征區(qū)間端點最高位為固定值（起點為0，終點為1），利用此特點優(yōu)化比較器減小電路資源開銷：使用1個比較電路實現(xiàn)區(qū)間判斷（通常設(shè)置2個，一個判斷大于起點，另一個判斷小于終點）。對于長度為j（1 j w≤<）的比較器，僅關(guān)鍵字的低w j-比特參與比較，比較電路輸入位寬為1w j--。若所有參與運算的比較器判斷關(guān)鍵字不在特征區(qū)間內(nèi)，可判斷關(guān)鍵字無效，通過零匹配信號通知狀態(tài)單元。匹配特征區(qū)間的比較器輸出相關(guān)附屬信息。

Bloom filter位數(shù)組中每一位可能被多個元素共享，因而某元素的刪除操作可能影響到其它元素，造成BFPP單元無法執(zhí)行刪除操作。為解決該問題，將B loom filter位數(shù)組的每一位擴展為BF計數(shù)器，每執(zhí)行一次插入/刪除操作相應(yīng)位加/減1。進一步分析發(fā)現(xiàn)，更新操作較查找操作發(fā)生頻率很低，為降低開銷設(shè)置更新單元維護BF計數(shù)器，BFPP單元中的B loom filter依然保持位數(shù)組結(jié)構(gòu)。當BF計數(shù)器跳變?yōu)?或由0變?yōu)檎龜?shù)時更新BFPP單元的B loom filter。TCAM_RAM單元同步更新。

Bloom filter的高效是以較低的錯誤率換取的，存在正誤差，即Bloom filter判斷通過的關(guān)鍵字以較小概率是無效的。這種誤差并非隨機的，對于特定關(guān)鍵字出現(xiàn)誤判則該關(guān)鍵字永遠出錯。具體在模型中由BFPP和比較器的判斷結(jié)果表現(xiàn)：當BFPP匹配向量不為0而比較器出現(xiàn)零匹配時，表明關(guān)鍵字通過Bloom filter判斷卻沒有匹配的范圍表項，誤差出現(xiàn)。然而這種誤差不影響匹配結(jié)果，最終將被比較器過濾掉，但較高的錯誤率會使更多TCAM塊區(qū)域參與比較，從而增加了工作功耗。狀態(tài)單元記錄查找狀態(tài)，通過無效信號指示關(guān)鍵字是否有效。

使用B loom filter進行預(yù)處理，可快速判斷關(guān)鍵字可能存在的前綴子集，過濾無關(guān)子集參與運算，但同時增加了電路關(guān)鍵路徑長度，為了不降低時鐘頻率引入二級流水線，將前綴預(yù)處理和TCAM_ RAM查找分為兩級進行。

3.2算法流程

配置算法（BF-TCAM Configuration A lgorithm）流程如表1所示。

首先獲取范圍集，計算每一個范圍的LCP，然后對LCP進行K次哈希計算，由BF計數(shù)器記錄計算結(jié)果，根據(jù)計數(shù)值配置BFPP單元中的B loom filter，同時將LCP存入TCAM相應(yīng)位置，特征區(qū)間和附屬信息存入RAM相應(yīng)位置。整個配置算法分為4個階段：（1）獲取范圍集，如1～5行所示，共有N個范圍（range），saddr表示起始地址，eaddr表示結(jié)束地址，acs_infor表示附屬信息；（2）計算范圍LCP，如6～7行所示，plen表示LCP的前綴長度；（3）訓練B loom filter，如8～18行所示，其中8～11行是更新單元中BF計數(shù)器的學習過程，根據(jù)前綴長度plen找到對應(yīng)的BF計數(shù)器，對LCP進行K次哈希計算，Hash_j表示BF計數(shù)器的第j個哈希函數(shù)，將哈希映射的位置加1；12～18行是BFPP單元B loom filter的配置過程，對應(yīng)BF計數(shù)器不為0的位被置1，m為Bloom filter數(shù)組的位寬；（4）配置TCAM和RAM，如19～20行所示，根據(jù)前綴長度（p len）找到相應(yīng)TCAM塊存入LCP值，范圍的特征區(qū)間saddr［w-plen-2:0］，eaddr［w-plen-2:0］和附屬信息（acs_infor）存入RAM相應(yīng)位置。3，4階段可并行運行。

表1　配置算法流程

查找算法（BF-TCAM Lookup A lgorithm）流程如表2所示。

首先通過B loom filter過濾關(guān)鍵字任意長度前綴，如果沒有前綴匹配，判定關(guān)鍵字無效。若通過過濾，然后在匹配的TCAM塊區(qū)域中查找相應(yīng)長度前綴，將匹配表項的位置作為地址索引RAM，最后由比較器判斷關(guān)鍵字是否位于特征區(qū)間，如果匹配成功，輸出附屬信息，否則判定關(guān)鍵字無效。整個查找算法分為兩個階段：（1）前綴預(yù)處理，如1～19行所示，其中1～15行完成B loom filter運算，分別對關(guān)鍵字各個長度的前綴進行哈希計算和判斷，將命中的前綴子集標記在匹配向量（match_vector）中，這個階段如果沒有發(fā)現(xiàn)匹配前綴即匹配向量為0可判斷關(guān)鍵字無效，如16～19行所示；（2）在命中的TCAM_RAM中查找關(guān)鍵字，如20～34行所示，TCAM若存在匹配表項，以其位置作為地址（ram_ addr）索引RAM，比較器判斷關(guān)鍵字偏移量是否位于特征區(qū)間，若存在匹配的特征區(qū)間，將對應(yīng)的附屬信息輸出，完成范圍匹配，否則判定關(guān)鍵字無效。

BF-TCAM支持增量更新，包括插入和刪除操作。插入算法與配置算法的2，3，4階段相同，完成BF訓練和TCAM_RAM表項的插入。刪除與插入算法相似，BF訓練階段對BF計數(shù)器進行減1操作，如果某位歸零，則相應(yīng)更新BFPP中的B loom filter，同時刪除TCAM_RAM中的表項。各個長度的前綴子集分區(qū)存放，支持隨機插入與刪除，無需移動無關(guān)表項，因而BF-TCAM模型能夠高效完成更新操作。

4　性能分析

表3為不同算法的關(guān)鍵性能指標對比，其中F為范圍匹配包含的字段個數(shù)，對于報文分類來說為2，包括源端口和目的端口，W為范圍字段位寬，DTRM算法將W位寬的范圍字段劃分為M個較短的比特串編碼，N為表項數(shù)目。DTRM，SRGE和C-TCAM最壞情況下都會造成嚴重范圍擴張，以報文分類中的端口查詢?yōu)槔?，DTRM造成2（2 4 1）×-倍擴張，倍擴張。DTRM和C-TCAM平均擴張因子優(yōu)化到了較理想的水平，但每條表項需要額外使用2W個比特。范圍擴張直接引發(fā)了高昂的更新代價，增加或刪除一個范圍需要對多條表項進行操作，同時加重了TCAM功耗。BF-TCAM通過SMLCP算法實現(xiàn)了高效的范圍匹配轉(zhuǎn)化，不增加任何冗余信息，擴張因子達到1.0，使TCAM空間利用率達到100%。SMLCP算法將范圍匹配拆分為兩個步驟，較其它算法增加了一個比較過程，為不降低查找速度，使用流水線縮小關(guān)鍵路徑長度，但不可避免地增加了電路資源消耗，由此可見SMLCP的高效存儲是以犧牲一定電路資源為代價的。TCAM功耗與參與并行比較的表項數(shù)目成正相關(guān)，BF-TCAM引入分類存儲思想，僅通過B loom filter過濾的子集參與比較，能夠大大降低TCAM功耗，極端惡劣情況下所有子集同時參與比較，此時功耗達到峰值。BF-TCAM支持增量更新，實現(xiàn)了表項的隨機插入與刪除，較其它算法大幅提高了更新性能。查找操作一個時鐘周期即可完成，特殊情況下流水線停頓造成一個時鐘周期延時，但目前TCAM時鐘頻率已達500 MHz以上，意味著查找操作可在4 ns內(nèi)完成，能夠滿足性能需求。

表2　查找算法流程

以多處理器片上系統(tǒng)［12］（Mu lti-Processor System-on-Chips，MPSoC）的存儲保護為背景評估BF_TCAM的實際功耗：MPSoC上可并行運行多個任務(wù)，每個任務(wù)分配有獨享的內(nèi)存區(qū)域，對共享數(shù)據(jù)存儲區(qū)有特定的訪問權(quán)限，引入BF-TCAM監(jiān)控任務(wù)的訪存地址可以實現(xiàn)對存儲資源的訪問控制，進而保護系統(tǒng)不受非法入侵。實驗中并行執(zhí)行4個應(yīng)用，共有551條規(guī)則表項，通過監(jiān)測TCAM_ RAM的片選信號即匹配向量可以計算實時參與比較的表項數(shù)目，進而評估實時功耗。如圖3所示，每個應(yīng)用采集2000次訪存操作，統(tǒng)計每次訪存參與比較的表項數(shù)目，圖中橫軸表示訪存次序，縱軸表示實時參與比較的表項數(shù)目，可以發(fā)現(xiàn)應(yīng)用1平均每次訪存有181.4條表項參與比較，占總規(guī)則數(shù)目的32.9%；應(yīng)用2為232.9條，占42.3%；應(yīng)用3為213.9條，占38.8%；應(yīng)用4為253.5條，占46.0%。BF-TCAM使用Bloom filter過濾無關(guān)項參與比較，將實際參與比較的規(guī)則數(shù)目大幅減少，實驗表明，BF-TCAM較傳統(tǒng)TCAM實際功耗降低50%以上。

表3　不同算法的關(guān)鍵性能指標對比

圖3　不同應(yīng)用下BF_TCAM的實際功耗水平

5　總結(jié)

目前基于TCAM的范圍匹配方案通過擴展規(guī)則集方式表達范圍，存儲空間利用率低，尤其對于報文分類中的端口匹配，范圍擴張因子達數(shù)百倍，同時大幅提高了工作功耗和更新代價。針對這個問題，本文提出了基于BF-TCAM的高效范圍匹配方法，利用范圍區(qū)間兩端點二進制編碼最長共同前綴的唯一性設(shè)計了SMLCP算法，將范圍匹配過程分解為前綴匹配和特征區(qū)間比對兩個步驟，從而便于應(yīng)用TCAM技術(shù)，使TCAM空間利用率達到100%。進而設(shè)計BF-TCAM模型，按前綴長度對范圍進行分類處理，支持增量更新，提高了更新性能。使用B loom filter對關(guān)鍵字過濾，屏蔽無關(guān)項參與比較，從而大幅降低功耗。使用流水線技術(shù)縮短電路關(guān)鍵路徑長度，使查找操作在一個時鐘周期內(nèi)完成。BF-TCAM模型在保持高速查找性能的同時，使用B loom filter過濾無關(guān)項，大幅減少參與比較的規(guī)則數(shù)目，實際功耗較傳統(tǒng)TCAM降低50%以上。

［1］董永吉，郭云飛，黃萬偉，等.一種新的高速報文解析結(jié)構(gòu)研究［J］.電子與信息學報，2013，35（5）:1083-1089.

DONG Yongji，GUO Yunfei，HUANG W anwei，et al.A new high-speed packet parsing architecture［J］.Journal of Electronics&Information Technology，2013，35（5）: 1083-1089.

［2］李智濤，徐雅靜，劉利宏，等.一種新的IPv6網(wǎng)絡(luò)帶寬測量方法［J］.電子與信息學報，2008，30（9）:2283-2286.

LI Zh itao，XU Yajing，LIU Lihong，et al.An approach to available bandw idth m easurem ent in IPv6 networks［J］. JournalofElectronics&Information Technology，2008，30（9）: 2283-2286.

［3］Grammatikakis M D，Papadim itriou K，Petrakis P，et al. Security effectiveness and a hardware firewall for MPSoCs［C］. IEEE High Perform ance Com puting and Comm un ications，Paris，2014:1032-1039.

［4］Grammatikakis M，Papadim itriou K，Petrakis P，et al. Security in MPSoCs:a NoC firewall and an evaluation framework［J］.IEEE Transactions on Computer-Aided Design of In tegrated Circuits and System s，2015，34（8）:1344-1357.

［5］田樂.面向存儲和功耗優(yōu)化的TCAM報文分類算法研究［D］.［碩士論文］，解放軍信息工程大學，2013.

TIAN Le.Research on storage and power efficiency packet classification algorithm based on TCAM［D］.［Master dissertation］，PLA Information Engineering University，2013.

［6］朱國勝，余少華.基于TCAM的范圍匹配方法C-TCAM［J］.通信學報，2012，33（1）:31-37.

ZHU Guosheng and YU Shaohua.Range matching method based on TCAM:C-TCAM［J］.Journal on Comm unications，2012，33（1）:31-37.

［7］BREMLERR-BARR A and HENDLER D.Space-efficient TCAM-based classification using gray coding［J］.IEEE Transactions on Computers，2012，61（1）:18-30.

［8］RAY S S and BHATTACHARYA A.A fast rangematching architecture w ith un it storage expansion ratio and h igh m em ory utilization using SBiCAM for packet classification［C］. IEEE India Conference，Pune，2014:1-6.

［9］侯穎，郭云飛，黃海，等.基于同源組合布魯姆過濾器的早期流量抽樣算法［J］.通信學報，2014，35（10）:117-126.

HOU Ying，GUO Yunfei，HUANG Hai，et al.Early traffic sam p ling algorithm based on SSCBF［J］.Journal on Communications，2014，35（10）:117-126.

［10］侯穎，黃海，蘭巨龍，等.基于自適應(yīng)超時計數(shù)布魯姆過濾器的流量測量算法［J］.電子與信息學報，2015，37（4）:887-894. doi:10.11999/JEIT 140820.

HOU Ying，HUANG Hai，LAN Ju long，et al.An adap tive tim eou t counter b loom filter a lgorithm for tra ffic measurement［J］.Journal of Electronics&Information Technology，2015，37（4）:887-894.doi:10.11999/JEIT 140820.

［11］張士庚，劉光亮，劉璇，等.大規(guī)模RFID系統(tǒng)中一種能量有效的丟失標簽快速檢測算法［J］.計算機學報，2014，37（2）: 434-444.

ZHANG Sh igeng，LIU Guangliang，LIU Xuan，et al.An energy-efficient and fast m issing tag detection algorithm in large scale RFID system s［J］.Chines Journal of Computers，2014，37（2）:434-444.

［12］王一拙，左琦，計衛(wèi)星，等.訪存與用戶行為敏感的MPSoC應(yīng)用映射［J］.電子學報，2015，43（4）:631-638.

WANG Yizhuo，ZUO Qi，JIWeixing，et al.Memory-aware and user-awaremapping of applications to MPSoCS［J］.Acta Electronica Sinica，2015，43（4）:631-638.

戴紫彬：男，1966年生，博士，教授，研究方向為安全專用芯片設(shè)計.

劉航天：男，1991年生，碩士生，研究方向為安全SoC設(shè)計與驗證.

Efficient Range Matching M ethod Based on Bloom Filter and Ternary Content Addressable Memory

DAIZibin LIU Hangtian
（Cryptography Engeering College，Information Engeering University，Zhengzhou 450004，China）

An efficient rangematchingmethod based on Bloom Filter algorithm and Ternary Content Add ressab le Memory（BF-TCAM）technology is proposed to resolve the problem that there generally exit low memory using ratio and high power dissipation in current TCAM rangematchingmethods.An algorithm of Segmented Match on Longest Common Prefix（SM LCP）sp lits range m atching into two steps prefix m atching and featu re range comparation，resulting in 100%TCAM space using ratio.BF-TCAM is designed according to SM LCP algorithm，which filters searching key wordsby Bloom filter to avoid that unrelated item s participate in comparation，so as to reduce greatly power dissipation.Critical paths are stream lined so that searching operation can be comp leted during one clock cycle.Research resu lts demonstrate that BF-TCAM achieves zero range expansion，meanwhile power dissipation fallsmore than 50%.

Range m atching；B loom Filter（BF）；Ternary Content Addressab le M em ory（TCAM）；Zero range expansion；Low power dissipation

TP393.08

A

1009-5896（2016）08-1872-08

10.11999/JEIT 151264

2015-11-10；改回日期：2016-03-21；網(wǎng)絡(luò)出版：2016-05-09

劉航天13703928360@163.com