计算机应用 ›› 2010, Vol. 30 ›› Issue (2): 306-308.

• 网络与通信 • 上一篇    下一篇

基于网络处理器的并行包分类方法

刘震宇1,李卫军2,赖粤2   

  1. 1. 华南理工大学
    2.
  • 收稿日期:2009-08-03 修回日期:2009-09-09 发布日期:2010-02-10 出版日期:2010-02-01
  • 通讯作者: 刘震宇
  • 基金资助:
    教育部高等学校科技创新工程重大项目培育资金项目

Paralleled packet classification based on network processor

  • Received:2009-08-03 Revised:2009-09-09 Online:2010-02-10 Published:2010-02-01
  • Contact: Liu ZhenYu
  • Supported by:
    Science and Technology Ministry of Education, colleges and universities foster innovation fund projects

摘要: 在大型网络中大量的规则数量会导致位向量(BV)算法的位向量过长和稀疏,要在网络处理器中实现BV算法需要大量的存储资源,而且多次存储读取也降低了算法匹配效率。针对BV算法位向量的问题,将Tuple空间分割思想与BV算法相结合缩短了位向量长度,充分利用网络处理器的并行处理机制和硬件加速单元,提出了一种适用于网络处理器的改进算法——Tuple-BV算法。该算法的元组分割缩短了位向量的长度,减少了位向量的存储空间和读取次数。通过对数据包处理延时的实验比较,当较多规则时,Tuple-BV算法在最大延时和平均延时指标上优于BV算法。

关键词: 网络处理器, 位向量, 元组空间, 哈希表, Trie

Abstract: There are a large number of rules in large networks. This feature leads to overlong and sparse bit vectors of BV algorithm, which requires a large amount of storage resources and too many read cycles in network processor. An improved method, Tuple-BV algorithm, was put forward, which combined tuple space partition with the BV algorithm to reduce the length of bit vector and take advantage of parallel processing mechanism and hardware acceleration units in network processor. The improved algorithm shortens the length of bit vector and reduces storage space. The experiments prove that Tuple-BV algorithm is better than BV algorithm in terms of maximum delay and average delay when the number of rules is over one thousand.

Key words: network processor, Bit Vector (BV), tuple space, Hash table, Trie