Bloom filter Extern

Home || Extern Function Library

Bloom Filter Extern

Description - Query or set an entry of a Bloom filter.

Instantiation:

#define BLOOM_OP_READ 2w0
#define BLOOM_OP_SET 2w1
#define BLOOM_OP_CLEAR 2w2
@BloomFilterHashWidth(hash_width)
@BloomFilterHashCount(hash_count)
@Xilinx_ControlWidth(0)
@Xilinx_MaxLatency(hash_width+3)
extern void <filter_name>_bloom_filter<T>(in bit<2> opcode, in T key, out bit<1> result);

• BloomFilterHashWidth: The log2 of the desired size of the Bloom filter. Note that if hash_width >= 22, you are trying to allocate more than 4 Mbits of BRAM, and will likely encounter timing issues and/or BRAM depletion issues.
• BloomFilterHashCount: The number of hash functions to be applied to each key. This parameter controls the latency and throughput of the extern, as the memory must be probed hash_count times in series for each read or set operation.
• index: The key to query the bloom filter (which will be fed to the hash functions).
• result: The result of the query (1 if the element was present, 0 otherwise). In case of a SET operation, the result will indicate presence of the element in the filter prior to insertion -- the SET operation is essentially an atomic read&set.
• opcode: Either BLOOM_OP_READ, to query the filter for presence of the key specified in index; or BLOOM_OP_SET, to insert the key specified in index into the filter while querying the filter for previous presence of the element; or BLOOM_OP_CLEAR, for resetting the filter (removing all elements). The later operation will block the filter during 2^hash_width cycles, during which any query will return 0.

Remarks: The extern has a throughput of 1 read or set operation every hash_count+3 cycles, i.e. it can handle 200/(hash_count+3) Mpps, with a maximum throughput of 50 Mpps if hash_count==1. Therefore, the filter will drop packets if run at 4*10 Gbit/s line-rate (~60 Mpps). It can, however, handle packets at 10 Gbit/s line-rate from a single interface provided that hash_count <= 10.