Patent Document ID: 8375433
Application ID: 12689842
Patent Flag: 1

Claim One:
1. A method for multi-core processor based packet classification on multiple fields comprising the following steps: a) obtaining an overall rule set (R 0 ), in which each rule includes a priority, a range value of each filtering field, and classification results; b) defining an initial search space (S 0 ), which contains all possible values of each filtering field in a packet header in which each filtering field corresponds to a dimension of the initial search space; c) generating a root node (V 0 ) corresponding to R 0 , S 0 , and a group of processing elements (R′, S′ and V′); d) copying R 0 , S 0 and V 0 to R′, S′ and V′ respectively; e) enqueueing the group of processing elements (R′, S′ and V′) into a first in first out queue (Q); f) dequeueing another group of processing elements (R, S and V) from the queue Q; g) determining if each rule in R includes S; h) selecting a field (F) as a partition field for S, along which there are a maximum number of different endpoint values, if each rule in R does not include S; i) sorting the different endpoint values of all rules in R along the partition field F in ascending order, assuming there are M endpoint values in total; j) selecting an endpoint numbered INT(M/2) along F as a partition point P, where INT(M/2) is a rounding operation; k) partitioning S into a first subspace (S 1 ) and a second subspace (S 2 ) through the partition point P on F; l) labeling all rules in the rule set R which overlap with the subspace S 1 as a rule set (R 1 ); m) labeling all rules in the rule set R which overlap with the subspace S 2 as a rule set (R 2 ); n) generating two sub-nodes (V 1 and V 2 ); o) storing the sub-nodes V 1 and V 2 in a continuous memory space; p) associating V 1 with R 1 and S 1 ; q) associating V 2 with R 2 and S 2 ; r) setting an internal node (V); s) assigning the following data structure to V: V.field=F, V.point=P, V.offset=starting address of V 1 ; t) generating another group of processing elements (R′, S′ and V′); u) copying R 1 , S 1 and V 1 to R′, S′ and V′; v) enqueueing the another group into the queue Q; w) generating another group of processing elements (R′, S′ and V′); x) copying R 2 , S 2 and V 2 to R′, S′ and V′; y) enqueueing the another group into the queue Q, and then returning to step (f); z) repeating steps (f)-(y) until each rule in R includes S; aa) obtaining a rule (r) with the highest priority in R; ab) defining a leaf node (V); ac) assigning the following data structure to V: V.field=r.action, V.point=r.pri, V.offset=0; Where r.action is the classification result of the rule r and r.pri is the priority of rule r; ad) determining if the queue Q is empty; ae) repeating steps (f), (g), and (z) until the queue Q is empty; af) returning the root node V 0 if the queue Q is empty, which is a starting node used to map a decision tree data structure; ag) receiving a network packet; ah) mapping the decision tree from the root node V 0 until a leaf node is reached, according to the values of the filtering fields; and ai) classifying the network packet according to V.field stored in the leaf node.