划分位无冲突哈希在trie树分组中的研究

Research on trie-tree partition processing using non-collision Hash functions based on partition bit

随着网络带宽的不断增长,迫切需要时空高效的数据包处理技术,满足线速处理和低存储需求。在高速片上存储器上存储所有的攻击特征,可以实现对数据包的高速检测,但受限于有限的片上存储器空间。通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一次就执行完复杂的完全匹配操作,显著地降低片上存储空间需求。

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.