一种基于折半层次搜索的包分类算法

？折半层次搜索(bsol)算法是一种高效的包分类算法，容易拓展至多维包分类，并支持range类型的规则。但由于其核心结构是在特里树（trie）的每一层创建hash表，因此当hash装载因子较大或hash冲突较大时，会影响其效率。分析折半层次搜索算法的优缺点，引入布鲁姆过滤器，提出了一种新的改进算法，为trie树的每一层建立了一个布鲁姆过滤器，在进行hash查找之前先进行一次布鲁姆查询运算，能够在hash冲突较大的情况下依然具有良好的性能。仿真实验结果表明，在数据包的命中率低于90%并且hash装载因子较大的情况下，新算法在运行时间上要优于以前的算法。