Patent ID: 6778984
Filing Date: 2004-08-17
Classification: H04L,Y10S

Abstract:
A packet classification method, comprising:converting an original rule database into a rule mapping table format for storage, wherein the method of producing the rule mapping table includes: dividing an input key value into a plurality of sub-key values; sequentially comparing various combination of each sub-key value with the same sub-key field of each rule; and storing the result of comparison in the rule mapping table by a bit-map method, wherein a size (S) of the rule mapping table is given by a formula: S=(W/G)Ã—NÃ—2G(bits); and, the amount of memory read (A) for each search is given by a formula:A=(W/G)Ã—N(bits), where W is the width of the input key in bits, G is the number of bits in each sub-key and N is the number of rules in the rule database,wherein a smallest size of the rule mapping table is given by a formula: S=(WÃ—N)Ã—2(bits), and a minimum amount of memory reading (A) in each search corresponding to the smallest size of the rule mapping table is given by a formula:â€ƒA=(WÃ—N)/2(bits),when each sub-key has a grouping state with a width of two (G=2).