关键词: 无冲突哈希, 划分位, trie树分组, 片上存储

Abstract: With the fast progress of Internet broadband, time and space efficient packet processing technology is urgently needed. One way to achieve high-speed packet processing is to store all the attack signatures on high-speed on-chip memory. Due to the limited on-chip memory, this paper proposes a new algorithm to create the non-collision functions based on middle-point partition. The algorithm evenly partitions attack signatures into multiple groups at each layer in trie tree. The data structure can be implemented on a single chip to perform pipelining and parallelism simultaneously, thus achieve high throughput. The theory and experimental results show that the algorithm can facilitate access to the signature string in the on-chip memory while allowing to perform the expensive exact match operations only once, and decreases the requirement of on-chip memory.

Key words: non-collision Hash, partition bit, trie-tree partition, on-chip memory