Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion

A matching method and range technology, which is applied in the field of high-efficiency range matching based on BF_TCAM to realize zero range expansion, can solve the problems of low storage utilization and high power consumption, and achieve the goals of reducing power consumption, improving update performance, and reducing circuit resource overhead Effect

Inactive Publication Date: 2016-04-20
刘航天 +1
View PDF4 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] The technical problem to be solved by the present invention is to provide a high-efficiency range matching algorithm based on Bloomfilter algorithm and TCAM to realize zero-range expansion, so as to solve the problems of low storage utilization and high power consumption in the range matching method based on TCAM. Performance is reflected in: high-efficiency storage, high-speed search and low power consumption

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion
  • BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion
  • BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion

Examples

Experimental program
Comparison scheme
Effect test

Embodiment

[0035] Bloomfilter algorithm introduction: BloomFilter is a random data structure with high space efficiency. It uses a bit array to succinctly represent a set, and can determine whether an element belongs to the set. BloomFilter contains an m-bit array, and each bit is set to 0 in the initial state. In order to express a set S={s1,s2,...,sn} containing n elements, BloomFilter uses k mutually independent hash functions hash_i (i=1,2...,k) to map each element in the set into the range {1,...,m}. For any element x, the position hash_i(x) of the i-th hash function mapping will be set to 1 (1≤i≤k), such as figure 1 shown.

[0036] When judging whether s belongs to a set, apply the hash function k times to s, if all the positions of hash_i(s) are 1 (1≤i≤k), then s hits this set with a high probability, otherwise it can be determined s does not belong to this set. Such as figure 2 As shown, it can be determined that y1 is not an element in the set, and it is a high probability...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion. The method is used for solving the problems of low storage utilization ratio and high power consumption of existing TCAM-based range matching methods and is mainly applied to the port range matching in packet classification, the storage access address examining in storage protection and the like. The high efficiency of the method provided by the invention is embodied in the aspects of high-efficiency storage, high-speed lookup and low power consumption. The method is characterized in that the range matching process is segmented into the two steps of prefix matching and characteristic interval comparison by utilizing a SMLCP (Segmented Match on Longest Common Prefix) algorithm to ensure that the TCAM technique is conveniently used and the storage utilization ratio of the TCAM is up to 100%; a BF_TCAM module is designed according to the SMLCP algorithm, the range is classified according to the prefix length, keywords are filtered and irrelevant items are shielded from participating in the comparison by using a bloom filter, so that the power consumption is reduced by a large margin; and the circuit critical path length is reduced by using a pipeline technique, so that the lookup operation is completed in one clock period.

Description

technical field [0001] The invention relates to an efficient range matching method based on Bloomfilter algorithm and TCAM (TernaryContentAddressableMemory, ternary content addressable memory) to realize zero range expansion, mainly used to solve port range matching in message classification and review of memory access addresses in storage protection Etc., to achieve access control, security filtering, bandwidth control and other functions, widely used in firewalls, routers, switches, distributed storage networks, trusted computing security platforms and other equipment. These applications have high requirements on search performance, and high-speed range matching is the technical support for their realization. Background technique [0002] At present, the industry generally uses TCAM to realize high-speed look-up tables. Unlike ordinary memory, which uses addresses to find content, TCAM locates addresses through content. It compares the input keyword with all table entries...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): H04L12/743
CPCH04L45/7453Y02D30/50
Inventor 刘航天方开莎
Owner 刘航天
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com