A Parallel Packet Classification Algorithm with Real-Time Incremental Updates

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.