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

DAI Zibin; LIU Hangtian

doi:10.11999/JEIT151264

Volume 38 Issue 8

Sep. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(8): 1872-1879

DAI Zibin, LIU Hangtian. Efficient Range Matching Method Based on Bloom Filter and Ternary Content Addressable Memory[J]. Journal of Electronics & Information Technology, 2016, 38(8): 1872-1879. doi: 10.11999/JEIT151264

Citation:

DAI Zibin, LIU Hangtian. Efficient Range Matching Method Based on Bloom Filter and Ternary Content Addressable Memory[J]. Journal of Electronics & Information Technology, 2016, 38(8): 1872-1879. doi: 10.11999/JEIT151264

Citation:

PDF( 779 KB)

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

doi: 10.11999/JEIT151264

DAI Zibin¹,
LIU Hangtian¹

Received Date: 2015-11-10
Rev Recd Date: 2016-03-21
Publish Date: 2016-08-19

Abstract

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

FullText(HTML)

References(21)

References

董永吉, 郭云飞, 黄万伟, 等. 一种新的高速报文解析结构研究[J]. 电子与信息学报, 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网络带宽测量方法[J]. 电子与信息学报, 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.

田乐. 面向存储和功耗优化的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.

朱国胜, 余少华. 基于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 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]. 通信学报, 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.

侯颖, 黄海, 兰巨龙, 等. 基于自适应超时计数布鲁姆过滤器的流量测量算法[J]. 电子与信息学报, 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.

张士庚, 刘光亮, 刘璇, 等. 大规模RFID系统中一种能量有效的丢失标签快速检测算法[J]. 计算机学报, 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.

王一拙, 左琦, 计卫星, 等. 访存与用户行为敏感的MPSoC应用映射[J]. 电子学报, 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.

Relative Articles

Supplements(0)

Cited By

Proportional views