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

摘要

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