基于散列表的快速分组分类算法  

Fast Packet Classification Algorithm Based on Hash Table

作　　者：李宾[1] 刘淑媛[2] 刘衍珩[3] 

机构地区：[1]吉林大学数学教学中心,长春130012 [2]吉林商业高等专科学校,长春130062 [3]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（理学版）》2005年第6期787-793,共7页Journal of Jilin University:Science Edition

基　　金：吉林省自然科学基金(批准号:20030522-2)

摘　　要：通过分析Internet网络主干路由器分组分类的关键问题和解决方案,提出了基于散列表的快速分组分类算法,该算法时间复杂度为O(1);通过分析规则表的相关性将规则表分成相关子集和不相关子集,对不相关子集采用哈希法构造散列表.实验测试表明,所给算法比顺序匹配算法的吞吐率提高近10%.进一步分析了规则冲突,并给出了冲突的理论证明和查找算法.The recent advance in the research of packet classification was surveyed, and a hash table based rule matching algorithm was given. The time complexity of the algorithm was O（ 1 ）. Through the analyses of the related problem of rule table, the rule table is separated into two sub groups. The unrelated group is constructed into a hash table which improves the matching speed. Experiments show that the throughput is improved about 10%. Another problem, the rule conflict, was proved and a conflict detection algorithm was given.

关 键 词：分组分类 散列表 规则表 相关规则 冲突检测 

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