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

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

李宾¹, 刘淑媛², 刘衍珩³

(1. 吉林大学数学教学中心, 长春 130012; 2. 吉林商业高等专科学校, 长春 130062；3. 吉林大学计算机科学与技术学院, 长春 130012)

收稿日期:2005-03-30 修回日期:1900-01-01 出版日期:2005-11-26 发布日期:2005-11-26
通讯作者: 刘衍珩

Fast Packet Classification Algorithm Based on Hash Table

LI Bin¹, LIU Shu-yuan², LIU Yan-heng³

(1. Centre of Mathematics Teaching, Jilin University, Changchun 130012, China; 2. Jilin Commercial College, Changchun 130062, China;3. College of Computer Science and Technology, Jilin University, Changchun 130012, China)

Received:2005-03-30 Revised:1900-01-01 Online:2005-11-26 Published:2005-11-26
Contact: LIU Yan-heng

摘要/Abstract

摘要： 通过分析Internet网络主干路由器分组分类的关键问题和解决方案, 提出了基于散列表的快速分组分类算法, 该算法时间复杂度为O(1); 通过分析规则表的相关性将规则表分成相关子集和不相关子集, 对不相关子集采用哈希法构造散列表. 实验测试表明, 所给算法比顺序匹配算法的吞吐率提高近10%. 进一步分析了规则冲突, 并给出了冲突的理论证明和查找算法.

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

Abstract: 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.

Key words: packet classification, hash table, rule table, related rules, conflict detection

中图分类号:

TP393

李宾, 刘淑媛, 刘衍珩. 基于散列表的快速分组分类算法[J]. J4, 2005, 43(06): 787-793.

LI Bin, LIU Shu-yuan, LIU Yan-heng. Fast Packet Classification Algorithm Based on Hash Table[J]. J4, 2005, 43(06): 787-793.

[1]	刘洁群. 基于谓词推理的冲突检测算法[J]. 吉林大学学报(理学版), 2016, 54(01): 112-115.
[2]	张长利, 赫枫龄, 左万利. 一种基于后缀数组的无词典分词方法[J]. J4, 2004, 42(04): 548-553.