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

戴紫彬; 劉航天

doi:10.11999/JEIT151264

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

doi: 10.11999/JEIT151264

戴紫彬¹,
劉航天¹

計量
- 文章訪問數(shù): 1396
- HTML全文瀏覽量: 118
- PDF下載量: 447
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2015-11-10
- 修回日期: 2016-03-21
- 刊出日期: 2016-08-19

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

DAI Zibin¹,
LIU Hangtian¹

摘要

摘要: 該文基于布魯姆過濾器算法和三態(tài)內(nèi)容尋址存儲器(Ternary Content Addressable Memory, TCAM)技術(shù)提出一種高效范圍匹配方法，解決了目前TCAM范圍匹配方案存在的存儲利用率低、功耗大的問題。設(shè)計基于最長共同前綴的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)將范圍匹配拆分為前綴匹配和特征區(qū)間比對兩步，TCAM空間利用率達(dá)到100%。根據(jù)SMLCP算法設(shè)計了BF-TCAM模型，使用布魯姆過濾器對關(guān)鍵字過濾，屏蔽無關(guān)項參與比較，大幅降低功耗。使用流水線縮短關(guān)鍵路徑長度，使查找操作在一個時鐘周期內(nèi)完成。研究結(jié)果表明，所提方法實現(xiàn)了零范圍擴(kuò)張，工作功耗較傳統(tǒng)TCAM降低50%以上。
- 范圍匹配 /
- 布魯姆過濾器 /
- 三態(tài)內(nèi)容尋址存儲器 /
- 零范圍擴(kuò)張 /
- 低功耗
Abstract: An efficient range matching method based on Bloom Filter algorithm and Ternary Content Addressable 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 range matching methods. An algorithm of Segmented Match on Longest Common Prefix (SMLCP) splits range matching into two stepsprefix matching and feature range comparation, resulting in 100% TCAM space using ratio. BF-TCAM is designed according to SMLCP algorithm, which filters searching key words by Bloom filter to avoid that unrelated items participate in comparation, so as to reduce greatly power dissipation. Critical paths are streamlined so that searching operation can be completed during one clock cycle. Research results demonstrate that BF-TCAM achieves zero range expansion, meanwhile power dissipation falls more than 50%.
- Range matching /
- Bloom Filter (BF) /
- Ternary Content Addressable Memory (TCAM) /
- Zero range expansion /
- Low power dissipation

HTML全文

參考文獻(xiàn)(21)

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

DONG Yongji, GUO Yunfei, HUANG Wanwei, et al. A new high-speed packet parsing architecture[J]. Journal of Electronics Information Technology, 2013, 35(5): 1083-1089.

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

LI Zhitao, XU Yajing, LIU Lihong, et al. An approach to available bandwidth measurement in IPv6 networks[J]. Journal of Electronics Information Technology, 2008, 30(9): 2283-2286. [3] Grammatikakis M D, Papadimitriou K, Petrakis P, et al. Security effectiveness and a hardware firewall for MPSoCs[C]. IEEE High Performance Computing and Communications, Paris, 2014: 1032-1039.

Grammatikakis M, Papadimitriou K, Petrakis P, et al. Security in MPSoCs: a NoC firewall and an evaluation framework[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(8): 1344-1357.

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

TIAN Le. Research on storage and power efficiency packet classification algorithm based on TCAM[D]. [Master dissertation], PLA Information Engineering University, 2013.

朱國勝, 余少華. 基于TCAM的范圍匹配方法C-TCAM [J]. 通信學(xué)報, 2012, 33(1): 31-37.

ZHU Guosheng and YU Shaohua. Range matching method based on TCAM: C-TCAM[J]. Journal on Communications, 2012, 33(1): 31-37.

BREMLERR-BARR A and HENDLER D. Space-efficient TCAM-based classification using gray coding[J]. IEEE Transactions on Computers, 2012, 61(1): 18-30.

RAY S S and BHATTACHARYA A. A fast range matching architecture with unit storage expansion ratio and high memory utilization using SBiCAM for packet classification[C]. IEEE India Conference, Pune, 2014: 1-6.

侯穎, 郭云飛, 黃海, 等. 基于同源組合布魯姆過濾器的早期流量抽樣算法[J]. 通信學(xué)報, 2014, 35(10): 117-126.

HOU Ying, GUO Yunfei, HUANG Hai, et al. Early traffic sampling algorithm based on SSCBF[J]. Journal on Communications, 2014, 35(10): 117-126.

侯穎, 黃海, 蘭巨龍, 等. 基于自適應(yīng)超時計數(shù)布魯姆過濾器的流量測量算法[J]. 電子與信息學(xué)報, 2015, 37(4): 887-894. doi: 10.11999/JEIT140820.

HOU Ying, HUANG Hai, LAN Julong, et al. An adaptive

timeout counter bloom filter algorithm for traffic

measurement[J]. Journal of Electronics Information Technology, 2015, 37(4): 887-894. doi: 10.11999/JEIT140820.

張士庚, 劉光亮, 劉璇, 等. 大規(guī)模RFID系統(tǒng)中一種能量有效的丟失標(biāo)簽快速檢測算法[J]. 計算機(jī)學(xué)報, 2014, 37(2): 434-444.

ZHANG Shigeng, LIU Guangliang, LIU Xuan, et al. An energy-efficient and fast missing tag detection algorithm in large scale RFID systems[J]. Chines Journal of Computers, 2014, 37(2): 434-444.

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

WANG Yizhuo, ZUO Qi, JI Weixing, et al. Memory-aware and user-aware mapping of applications to MPSoCS[J]. Acta Electronica Sinica, 2015, 43(4): 631-638.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計