| 基于散列表的快速分组分类算法 |
| |
| 引用本文： | 李宾,刘淑媛,刘衍珩.基于散列表的快速分组分类算法[J].吉林大学学报(理学版),2005,43(6):787-793. |
| |
| 作者姓名： | 李宾 刘淑媛 刘衍珩 |
| |
| 作者单位： | (1. 吉林大学 数学教学中心, 长春 130012; 2. 吉林商业高等专科学校, 长春 130062；3. 吉林大学 计算机科学与技术学院, 长春 130012) |
| |
| 基金项目： | 吉林省自然科学基金(批准号:20030522-2) |
| |
| 摘 要： | 通过分析Internet网络主干路由器分组分类的关键问题和解决方案, 提出了基于散列表的快速分组分类算法, 该算法时间复杂度为O(1); 通过分析规则表的相关性将规则表分成相关子集和不相关子集, 对不相关子集采用哈希法构造散列表. 实验测试表明, 所给算法比顺序匹配算法的吞吐率提高近10%. 进一步分析了规则冲突, 并给出了冲突的理论证明和查找算法.
|
| 关 键 词： | 分组分类 散列表 规则表 相关规则 冲突检测 |
| 文章编号： | 1671-5489(2005)06-0787-07 |
| 收稿时间： | 2005-03-30 |
| 修稿时间： | 2005年3月30日 |
Fast Packet Classification Algorithm Based on Hash Table |
| |
| LI Bin,LIU Shu-yuan,LIU Yan-heng.Fast Packet Classification Algorithm Based on Hash Table[J].Journal of Jilin University: Sci Ed,2005,43(6):787-793. |
| |
| Authors: | LI Bin LIU Shu-yuan LIU Yan-heng |
| |
| Institution: | (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) |
| |
| 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.) |
| |
| Keywords: | packet classification hash table rule table related rules conflict detection |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《吉林大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《吉林大学学报(理学版)》下载免费的PDF全文 |
