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

NP-based Multi-dimensional Packet Classification Algorithm

作　　者：孙清[1,2] 张德运[1] 何晖[1] 李金库[1] 

机构地区：[1]西安交通大学网络研究所,陕西西安710049 [2]西安财经学院计算机科学与技术系,陕西西安710061

出　　处：《小型微型计算机系统》2009年第1期74-77,共4页Journal of Chinese Computer Systems

基　　金：中国下一代互联网示范工程项目(CNGI-04-11-1D)资助;国家高技术研究发展计划“八六三”项目(2006AA01Z210)资助

摘　　要：提出一种基于网络处理器并行处理能力的多维快速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.

关 键 词：包分类算法 网络处理器 TRIE树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]