TY  - JOUR
T1  - A Packet Classification Algorithm Using Bloom Filter Pre-Searching on Area-based Quad-Trie
AU  - Byun, Hayoung 
AU  - Lim, Hyesook 
JO  - Journal of KIISE, JOK
PY  - 2015
DA  - 2015/1/14
DO  - 
KW  - packet classification
KW  - Bloom filter
KW  - area-based quad-trie
KW  - leaf-pushing
AB  - As a representative area-decomposed algorithm, an area-based quad-trie (AQT) has an issue of search performance. The search procedure must continue to follow the path to its end, due to the possibility of the higher priority-matching rule, even though a matching rule is encountered in a node. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to further improve the search performance of the leaf-pushing AQT. The proposed algorithm implements a leaf-pushing AQT using a hash table and an on-chip Bloom filter. In the proposed algorithm, by sequentially querying the Bloom filter, the level of the rule node in the leaf-pushing AQT is identified first. After this procedure, the rule database, which is usually stored in an off-chip memory, is accessed. Simulation results show that packet classification can be performed through a single hash table access using a reasonable sized Bloom filter. The proposed algorithm is compared with existing algorithms in terms of the memory requirement and the search performance.