一种IP数据包快速分类算法  

IP packet fast classification algorithm

作　　者：尚凤军[1] 

机构地区：[1]重庆邮电大学计算机科学与技术学院,重庆400065

出　　处：《东南大学学报（自然科学版）》2006年第S1期86-89,共4页Journal of Southeast University：Natural Science Edition

基　　金：重庆大学博士启动基金资助项目(A2006-08)

摘　　要：为了提高查找效率,在无冲突哈希查找算法和Grid of Tries算法的基础上提出了一种基于无冲突哈希和多比特Trie树(NHMT)的IP分类算法.该算法的核心有3部分:哈希函数的构造,主要是采用基于目的端口和协议两域构造哈希函数,使得在最坏情况下完全避免了空间爆炸问题;在Grid of Tries算法的基础上,对Grid of Tries算法改造成修剪的Trie树和多比特Trie树,以减少空间复杂度;在无冲突哈希查找算法的基础上扩展一层用于存放源端口号(或范围),扩展后一般要提高算法的时间复杂度,要通过引入多比特Trie树的方法进行解决.对于空间复杂度方面与无冲突哈希查找算法比较,一般情况下不增加空间复杂度.通过仿真,当对10 000条规则进行包分类时,该算法的分类速度可以达到1 Mbit/s,所消耗的最大内存为8.2 MB.In order to improve lookup efficiency,a novel IP classification,NHMT(non-collision Hash and nultibit-trie tree) is proposed, which is based on non-collision Hash trie-tree algorithm and grid of tries algorithm.The core of this algorithm has three parts: constructing Hash function mainly based on destination port and protocol type field so that the hash function can avoid space explosion problem;transforming Grid of tries for the trie-tree pruned and multibit-trie tree in order to reduce space complexity;add...

关 键 词：IP分类 查找算法 TRIE树 无冲突哈希 GridofTries 

分 类 号：TN915.01[电子电信—通信与信息系统]