支持快速增量更新的包分类算法

动态数据包分类是目前新兴网络服务的基础,但现有包分类算法的更新性能不能令人满意。基于递归空间分解和解释器方法,设计和实现了一个支持快速增量更新的两阶段多维包分类算法TICS,利用局部数据结构重建替换方法允许规则集增量更新,并通过适当的内存管理允许查找和更新的并行同步进行。实验表明,算法的更新速度比目前更新最快的BRPS算法至少提升了一个数量级,且内存消耗少,具有良好的并行扩放性。

A Packet Classification Algorithm with Fast Incremental Update Support

Dynamic packet classification is the basis of emerging network services, but the update performance of existing packet classification algorithms is unsatisfactory. Based on the Recursive Space Decomposition and Interpreter approach, this paper designs and implements a two-stage multi-dimensional algorithm TICS with fast incremental update support. It allows incremental update of rule set by reconstructing and replacing the local data structure, and allows parallel synchronous execution of search and update through appropriate memory management. The experimental results show that TICS is at least an order of magnitude faster than the current fastest algorithm BRPS, with less memory consumption and good parallel scalability.