Abstract:In order to solve the problems of long classification time and large storage space incurrent packet classification algorithms, a fast packet classification approach (Uscuts) based on unit space partition was proposed. The method mainly includes rule preprocessing, rule space partition and decision tree construction stage. First, based on the multidimensional matrix design model, the original rules were mapped in reverse order to the multidimensional matrix, and the target rules which have the same semantics with the original rules and mutually independent rule spaces were obtained. Then, the corresponding space of the target rules was divided and a classification decision tree was constructed. Each branch of the decision tree corresponds to an independent multidimensional rule subspace, which means each leaf node of the decision tree just relates only one rule. Therefore, when the packet was matched to the leaf node, the classification decision of the packet can be directly determined to be accept. Unlike the traditional packet classification methods, the sequence matching should be continued within the rule group associated with the leaf nodes, which significantly raised the speed of packet classification. In addition, when dividing the rules space, Uscuts used the division method based on the unit space boundary. Compared with the current classification algorithms, the number of the rule subspace was effectively reduced and the storage space was saved. To further validate the efficiency and effectiveness of the proposed algorithm, different sizes of rules and packets were generated to test the time required for packet classification. The test results showed that the time complexity of Uscuts could reach O(0.75k·lb(n)), even in the worst case, it was not more than O(k·lb(n)), here n and k were the number and dimension of the rules, respectively. Theoretical analysis and experimental results demonstrated that, compared with existing classification methods based on decision tree, Uscuts method has higher classification efficiency and smaller storage space.