一种高性能包分类渐增式更新算法

摘要

包分类是第4层线速数据包输入处理的核心问题之一.当前包分类问题研究的重点是最差情况下,规则数达到百万、多维的动态算法.尝试格(grid of tries)算法的优点是查找时间复杂度与规则数无关,空间复杂度接近线性;缺点是没有支持渐增式更新的算法,即它是一种静态算法,并且仅支持二维.在此提出了一种尝试格的渐增式更新算法,使之成为动态算法.最终提高了尝试格算法的综合性能.