计算机应用 ›› 2012, Vol. 32 ›› Issue (04): 999-1002.DOI: 10.3724/SP.J.1087.2012.00999

• 先进计算 • 上一篇    下一篇

基于中间点划分无冲突哈希的高速包处理

张墨华1,李戈2   

  1. 1. 河南财经政法大学 计算机与信息工程学院,郑州 450000
    2. 华北水利水电学院水利职业学院 信息工程系,郑州 450000
  • 收稿日期:2011-10-31 修回日期:2011-12-02 发布日期:2012-04-20 出版日期:2012-04-01
  • 通讯作者: 张墨华
  • 作者简介:张墨华 (1979-),男,河南固始人,讲师,硕士,主要研究方向:网络信息安全、智能信息处理;
    李戈(1979-),女,河南内乡人,讲师,硕士,主要研究方向:网络信息安全。

High-speed packet processing by non-collision hash functions based on

ZHANG Mo-hua1,LI Ge2   

  1. 1. School of Computer and Information Engineering, Henan University of Economics and Laws, Zhengzhou Henan 450000, China
    2. Department of Information Engineer, Conservancy Vocational Institute of North China Institute of Water Conservancy and Hydroelectric Power, Zhengzhou Henan 450000, China
  • Received:2011-10-31 Revised:2011-12-02 Online:2012-04-20 Published:2012-04-01
  • Contact: ZHANG Mo-hua

摘要: 通过在高速片上存储器上存储所有的攻击特征,实现对数据包的高速检测。针对有限的片上存储器空间,提出一种新的基于中间点划分无冲突哈希函数的trie树结构,将攻击特征串平均分配到trie树每层的多个组中,实现对片上存储器有效的控制。通过在同一个芯片中采用流水并行方式执行查询操作,获得更高的吞吐量。存储中间点的空间复杂度为O(n),哈希表的构建时间随攻击特征数量线性增长。实验结果表明:该方法降低了片上存储空间需求,在片上存储器只需执行一次即可完成特征匹配操作。

关键词: 高速包处理, 无冲突哈希, 中间点划分, trie树, 片上存储

Abstract: High-speed packet inspection can be achieved through storing attack signatures on the high-speed on-chip memory. Concerning the limited on-chip memory, this paper proposed a new trie structure with non-collision hash functions based on middle-point partition. The algorithm evenly partitioned attack signatures into multiple groups at each layer in trie tree to achieve the effective control of memory. The trie-tree structure can be implemented on a single chip and perform query operations by pipelining and parallelism, thus achieving higher throughput. The space complex of storing middle-point is O(n) and the construction time of hash table is linearly growing with the number of attack signatures. The experimental results show that the new structure decreases the demand of on-chip memory and can facilitate access to the attack signature on the on-chip memory while allowing to perform the signatures matching operations only once.

Key words: high-speed packet processing, non-collision hash, middle-point partition, trie tree , on-chip memory