基于网络处理器的多维包分类算法

NP-based Multi-dimensional Packet Classification Algorithm

提出一种基于网络处理器并行处理能力的多维快速IP数据包分类算法.首先对包过滤规则库进行有效的预处理,以使对规则的分组能够最大限度地发挥并行算法的优势;在合理分组之后对每一组规则实施相关的三值TRIE树最优编码,这种最优编码形式从根本上消除了在对规则库进行压缩编码时产生的规则扩展问题.算法的最终实现,仅需要对数据包进行一次索引表的哈希查询和一次规则匹配,因此有效提高了包分类运算的效率.

A fast multifields packet classification algorithm base on the parallel process ability of network processor is presented in this paper. In order to let the parallel algorithm provide high performance, this paper pretreat the packet filter rules in library in a meaningful way. Then divide rules into several clusters according to the corresponding feature of one kind of network processor. After that, an optimized three value trie tree method is emploied to encode each rule into shorter bit string. By the help of this method, the problem of rule expansion while rule encoding had been successfully solved. Only need one hash search and one time rule match in this algorithm, so it provide an efficient way to handle multi-dimensional packet classification.