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

【Abstract】 Binary Search On Levels(BSOL) is a fast algorithm for packet classification,which can be easily extended to multi-mention packet classification.For its core framework is hash Table which belongs to every layer of Trie Tree,the performance of BSOL will get lower when load factor of hash Table is big or hash collision is frequent.This paper presented a new algorithm using bloom filters.The new algorithm still performed well even the hash collision was frequent.Analyzing the experimental data from a virtual environment,the authors conclude that the new algorithm performs better when hit ratio of packets is lower than 90% while load factor is big.更多还原