A Hardware-Based PATRICIA Algorithm for Fixed-Length Match

PATRICIA algorithm has become a classic method for information retrieval. But PATRICIA insertion is time-consuming. By analyzing PATRICIA, it is discovered that not keeping the order of NBTs(next bit to test) in PATRICIA trie can improve the performance of PATRICIA insertion and decrease hardware design complexity. A new PATRICIA algorithm for fixed-length match is proposed. It is proved that this algorithm is an optimal binary trie-based algorithm. An ASIC (application specific integrated circuit) for this algorithm is implemented for the application of state table of stateful inspection. The theoretical and experimental results show that this algorithm can work very well for the application of state table in gigabit network.