一种支持实时增量更新的并行包分类算法

A Parallel Packet Classification Algorithm with Real-Time Incremental Updates

UTM(unified threat management)技术的提出和应用要求多维包分类算法能够支持实时的增量更新.但由于以往的研究都侧重于加快算法的查找速度,这一需求已经成了目前包分类算法在实际应用中的一个瓶颈.提出一种二维trie树结构来组织分类规则,并给出了相应的查找及更新算法.利用trie结构的特性将各种长度的前缀组合进行分组,并依此将整个规则集分成多个子集.查找时将每一次查找过程分解成若干个可以独立运行的子任务,每个子任务处理一个子集.两级混合trie结构保持了规则之间的独立性,因此可以快速地对单条规则进行增量删除或添加.实验结果表明,本算法在保持高速查找的基础上,将单条规则的增量更新操作速度提高到了和单次查找操作同样的量级,同时并行查找使得算法对规则类型和规模的敏感度大大降低,具有较好的可扩展性.

UTM（unified threat management） technique requires that packet classification algorithms support incremental updates.However,Current approaches mainly focus on speeding up the classification,and rarely consider the requirement of incremental updates,which hinders UTM＇s practical applications.In this paper,a parallel classification algorithm is proposed to improve the performance of incremental updates.Firstly,a two dimension hybrid hierarchical trie is proposed to organize the classification rule-set.Kinds of the prefix-couples in rules can be formed into groups by mapping them into the trie because of the characteristics of the trie structure,and then the whole rule-set can be divided into a number of sub-sets.The processing procedure of each packet has been decomposed into several independent sub-missions,and each of them deals with a subset.Since the hybrid hierarchical trie maintaines the independence of each rule,each of them can be added or deleted from the trie incrementally.The experimental results show that the new algorithm can improve the speed of incremental updates to the same order of magnitude of classification.Additionally,using the parallel method in classification makes significant reduction in the algorithm＇s sensitivity to the scale and type of rule-sets,therefore the algorithm is more adaptive and scalable.