Patent Document ID: 20100192215
Application ID: 12689842
Patent Flag: 0

Claim One:
1. A method for multi-core processor based packet classification on multiple fields, including the following steps: Block 101 , obtain the overall rule set R 0 , in which each rule includes priority, the range value of each filtering field, and the classification results; Block 102 , define S 0 as the initial search space, which contains all possible values of each filtering field in a packet header, and every field corresponds to a dimension of the initial search space; Block 103 , generate the root node V 0 corresponding to R 0 , S 0 , and a group of processing elements R′, S′ and V′, then copy R 0 , S 0 and V 0 to R′, S′ and V′ respectively; Block 104 , enqueue the group of processing elements R′, S′ and V′ into queue Q, which is a FIFO queue; Block 105 , dequeue a group of processing elements from the queue Q, and denote as R, S, V respectively; Block 106 , decide whether each rule in R includes S, if so, perform step s 116 , if not, perform step s 107 ; Block 107 , select field F as the partition field for S, along which there are maximum number of different endpoint values. Block 108 , sort different endpoint values of all rules in R along the partition field F in the ascending order, assume M endpoint values in total; Block 109 , select the endpoint numbered INT(M/2) along F as the partition point P, where INT(M/2) means the rounding operation; Block 110 , partition S into subspace S 1 and subspace S 2 through partition point P on F; Block 111 , label all rules in rule set R which overlap with subspace S 1 as rule set R 1 , and all rules in R which overlap with subspace 52 as rule set R 2 ; Block 112 , generate two sub-nodes V 1 and V 2 , store them in continuous memory space, and associate V 1 with R 1 , S 1 , V 2 with R 2 , S 2 ; Block 113 , set V as an internal node, and assign the following data structure to V: V.field=F, V.point=P, V.offset starting address of V 1 ; Block 114 , generate a group of processing elements R′, S′ and V′, copy R 1 , S 1 , and V 1 to R′, S′ and V′, and then enqueue the group into queue Q; Block 115 , generate a group of processing elements R′, S′ and V′, copy R 2 , S 2 , and V 2 to R′, S′ and V′, enqueue the group into queue Q, and then return to step s 105 ; Block 116 , obtain rule r with the highest priority in R, define V as a leaf node, and assign 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 rule r, r.pri is the priority of rule r; Block 117 , decide whether queue Q is empty, if so, perform Block 118 , if not, go to Block 105 ; Block 118 , return root node V 0 , which is the starting node to look up the decision tree data structure; Block 119 , receive a network packet, and according to the values of filtering fields, look up the decision tree from the root node V 0 until reach a leaf node, then classify the packet according to Wield stored in the leaf node.