Methods and apparatus for packet classification with multi-level data structure

Claim 3

The method of claim 1 wherein, in at least one of the tables, the conditions include a first condition which is matched by any of a plurality of specific parameter values.

Claim 4

The method of claim 2 wherein, in at least one of the tables, the first condition is matched by any parameter value in a range of parameter values.

Claim 5

The method of claim 3 wherein, for at least one of the parameter values, searching the lookup table comprises finding a table entry having a condition which provides a longest prefix match to the parameter value.

Claim 6

The method of claim 1 wherein searching at least one of the tables comprises searching for a best match to the parameter value.

Claim 7

The method of claim 5 wherein, whenever a table contains two or more different conditions which could be simultaneously matched by a parameter value and a first one of the two or more conditions has a higher precedence than a second one of the two or more conditions, a next level one of the tables corresponding to the first one of the two or more conditions duplicates one or more entries of a next level one of the tables corresponding to the second one of the two or more conditions.

Claim 8

The method of claim 6 wherein every next level one of the tables corresponding to the first one of the two or more conditions duplicates all entries of a next level one of the tables corresponding to the second one of the two or more conditions.

Claim 9

The method of claim 1 wherein providing a set of packet classification rules embodied in a plurality of lookup tables comprises: a) obtaining a set of classification rules, each of said classification rules specifying a set of conditions to be met by each of a plurality of parameter values in a packet signature, the parameter values comprising a first parameter value, a last parameter value and one or more intermediate parameter values; and, b) creating in an electronically readable memory a data structure providing a plurality of chains of linked conditions, the data structure comprising a first level lookup table associated with a first one of the parameter values, a plurality of intermediate lookup tables associated with each of the intermediate parameter values and a plurality of last level lookup tables associated with a last one of the parameter values; c) in the first level lookup table creating a plurality of entries each associating a distinct condition specified by the rules on the first one of the parameter values with a pointer to one of the intermediate lookup tables; d) in each intermediate lookup table creating one or more entries, each entry associating a distinct condition specified by the rules on an intermediate parameter value with a pointer to a subsequent lookup table; e) in the final level lookup table creating a plurality of entries each entry associating a distinct condition specified by the rules on the final one of the parameter values with a class identifier; wherein each possible path which follows the pointers from an entry in the first level table to an entry in a final level table provides a chain of linked conditions and each chain of linked conditions includes every condition in the set of conditions specified by one of the rules.

Claim 10

The method of claim 8 wherein providing a set of packet classification rules embodied in a plurality of lookup tables further comprises: a) identifying two or more entries in either the first level table or any one of the intermediate level tables, the two or more entries containing distinct conditions which could be simultaneously matched by a parameter value; b) identifying a group of two or more subsequent level tables pointed to by such entries; and, c) in one of the two or more subsequent level tables which corresponds to a higher priority one of the distinct conditions, duplicating entries from another of the two or more subsequent level tables which corresponds to a lower priority one of the distinct conditions.

Claim 11

The method of claim 9 wherein the higher priority condition and the lower priority conditions each specify a match to a prefix and the prefix for the higher priority condition is longer than the prefix for the lower priority condition.

Claim 12

The method of claim 10 wherein providing a set of packet classification rules embodied in a plurality of lookup tables comprises: a) identifying all cases in the first level table and the intermediate level tables wherein two or more entries contain distinct conditions which could be simultaneously matched by a parameter value; b) for each case identifying a group of two or more subsequent level tables pointed to by such entries; and, c) for each case selecting each of the two or more subsequent level tables which corresponds to a higher priority one of the distinct conditions and in each such subsequent level table duplicating entries from each of the two or more subsequent level tables which corresponds to a lower priority one of the distinct conditions.

Claim 13

The method of claim 1 wherein the signature comprises three or more parameter values selected from the group consisting of: input port on which packet arrived; source IP address; destination IP address; source UDP or TCP port number; destination UDP or TCP port number; layer 3 packet type; Type of Service (“TOS”) value; layer 4 packet type; TCP acknowledgement flag; and, time of packet arrival.

Claim 14

The method of claim 1 where the signature comprises at least a time parameter and one or more address parameters and wherein the condition on at least one of the one or more address parameters is a best matching condition.

Claim 15

The method of claim 1 wherein one of a plurality of search engines is associated with each table and wherein searching a table comprises searching using the search engine corresponding to the table.

Claim 16

The method of claim 1 wherein backtracking is reduced by providing a set of packet classification rules embodied in a plurality of lookup tables by: a) for each group of conditions in the first level table or in an intermediate level table, identifying every case wherein two or more distinct conditions in the same group could be simultaneously matched by a parameter value; b) for each case, identifying a group of two or more subsequent level tables which correspond to the distinct conditions; and, c) for each case, selecting each of the two or more subsequent level tables which does not correspond to a lowest priority one of the distinct conditions and in each such subsequent level table duplicating all entries from each of the two or more subsequent level tables which correspond to lower priority ones of the distinct conditions.

Claim 19

Apparatus for classifying data packets, the apparatus comprising: (a) a processor capable of obtaining a signature comprising N parameter values for the packet to be classified, where N is an integer with N>=3; (b) a memory accessible to the processor; (c) a data structure in the memory, the data structure comprising N levels of tables, the tables including a first level lookup table associated with a first one of the parameter values, a plurality of intermediate lookup tables associated with each of one or more intermediate parameter values and a plurality of final level lookup tables associated with an N th one of the parameter values, each of the tables containing entries which include a condition on a parameter value which corresponds to the table, wherein a condition is duplicated in two different tables at a same level; wherein the processor is adapted to, beginning with the first level table, iteratively, search a table for a condition which matches the parameter value in the signature which corresponds to the level to obtain a pointer to a subsequent table to search for a condition matching a subsequent parameter value in the signature of the packet until the processor identifies a final level table and wherein the processor is adapted to obtain the class identifier applicable to the packet by searching the final level table for a condition which matches the N th parameter value in the signature.

Claim 20

Apparatus for classifying data packets, the apparatus comprising: (a) a processor capable of obtaining a signature comprising N parameter values for the packet to be classified, where N is an integer with N>=3; (b) a memory accessible to the processor; (c) a data structure in the memory, the data structure comprising N levels of tables, the tables including a first level lookup table associated with a first one of the parameter values, a plurality of intermediate lookup tables associated with each of one or more intermediate parameter values and a plurality of final level lookup tables associated with an N th one of the parameter values, each of the tables containing entries which include a condition on a parameter value which corresponds to the table, wherein a condition is duplicated in two different tables at a same level; wherein the processor is adapted to, beginning with the first level table, iteratively, search a table for a condition which matches the parameter value in the signature which corresponds to the level to obtain a pointer to a subsequent table to search for a condition matching a subsequent parameter value in the signature of the packet until the processor identifies a final level table and wherein the processor is adapted to obtain the class identifier applicable to the packet by searching the final level table for a condition which matches the N th parameter value in the signature.

Claim 21

The apparatus of claim 16 wherein the processor provides at least two search engines, each level being associated to one of the at least two search engines, the search engine associated with each level adapted to search a table of that level for a condition which matches the parameter value in the signature which corresponds to that level.