Bloomier filter

Report
1
Chisel: A Storage-efficient,
Collision-free Hash-based Network
Processing Architecture
Author: Jahangir Hasan, Srihari Cadambi, Venkatta Jakkula Srimat Chakradhar
Publisher: ISCA 2006
Presenter: Yuen-Shuo Li
Date: 2012/10/03
Outline

Introduction

Bloomier Filter

Issue – False Positive

Issue - Wildcard

Issue - Update

Performance
2
Introduction(1/2)
There are three major families of techniques for performing LPM

TCAM


Trie-Based


Large cost and power dissipation
Large memory requirements and long lookup latencies
Hash-Based

lower power, small memory requirement, and short lookup latencies

can’t handle wildcard and have collision problem
3
Introduction(2/2)

Chisel(Collision-free Hashing-Scheme for LPM)

use collision-free hashing scheme called Bloomier filter

solve two key problem


false positive

wildcard
support incremental updates
4
Bloomier Filter(1/5)

recall Bloom Filter

a bit vector

multiple hash function

false-positive problem
5
Bloomier Filter(2/5)

an extension of Bloom filter

collision-free hashing scheme

support storage and retrieval of arbitrary per-key information

support static sets of keys and not dynamic update

inherit Bloom filter’s false-positive problem
6
Bloomier Filter(3/5)

Idea
7
HN: The set of k hash values of a key

find a T(t) among HN(t) such that there is a one-to-one mapping
between all t and T(t)

setup the Index Table, so that a lookup for t return location T(t)

and store value in a separate Result Table at address T(t)
Bloomier Filter(4/5)
It is possible that this setup process can fail
• use more hash function or expand the table
• and use a little TCAM
8
Bloomier Filter(5/5)

9
In order to retrieve T(t), the solution is to store some value in T(t)

use XOR
  ∶ the value of the i’th hash function
D[  ] ∶ the data value in the   ‘th location
Issue – False Positive(1/2)

can occur when lookup involves some key t which was not in the set
of original keys used for setup

two way

add a checksum field to each hash bucket


still has false positives
use chisel architecture

eliminating false positives
10
Issue – False Positive(2/2)

encode a pointer p(t) for each t instead of  

use two separate tables to store f(t) and t
11
Issue – Wildcard(1/3)

Because hash functions cannot operate on wildcard bits

the way to support wildcard bits

large number of tables


CPE


results in considerable hardware complexity and cost
resulting in huge amounts of memory
prefix collapsing
12
Issue – Wildcard(2/3)
13
Issue – Wildcard(3/3)
14
Issue - Update

update for existing prefix is easy


just change the entry in the Result Table
remove: temporarily mark the prefix dirty


15
a large fraction of updates are actually route-flaps
maintain shadow copy of the date structures in software

first incrementally update the shadow copy

then transfer the data structure to the hardware engine
route-flaps: a prefix is added back after being recently removed
Performance(1/3)
16
Performance(2/3)
17
Performance(3/3)
18

similar documents