Multi-field classification using enhanced masked matching

A system for matching a target bit pattern with a plurality of filter bit patterns, said a system comprising:

• a field register containing said target bit sequence;
• a plurality of classifier elements, each classifier element being associated with a group of filter bit patterns, each classifier element receiving said target bit pattern from said field register, and each classifier element outputting a filter identifier identifying which filter bit pattern from the group of filter bit patterns associated with said classifier element matches said target bit pattern, each classifier element comprising:
• an input stage receiving said target bit pattern and having a plurality of stage outputs, each stage output being a portion of said target bit pattern
• a multiplexer stage receiving said stage outputs, said multiplexer stage selecting one of said stage outputs as a multiplexer output based on a sequencer output;
• a memory stage unit receiving said multiplexer output and said sequencer output, said storage unit having a storage unit output determined by said multiplexer output and said sequencer output, said memory stage unit storing intermediate arrays generated from said filter bit patterns;
• AND gate means for performing an AND operation between successive storage unit outputs and a match vector to produce a new match vector, said match vector indicating which filter bit pattern matches said target bit pattern;
• and
• match vector storage means for storing said match vector, said match vector storage means receiving said new match vector to overwrite an old match vector, said match vector storage means outputting said match vector
• a priority multiplexer receiving outputs from said classifier elements said priority multiplexer determining which of said outputs of said classifier elements has a highest priority;
• a launch first in-first out (FIFO) buffer receiving a sequence of target bit patterns and transmitting in sequence said target bit patterns to said field register;
• a result first in-first out (FIFO) buffer receiving an output of said multiplexer and transmitting in sequence saids,previous cutouts of said multiplexer;
• and
• a sequencer communicating with each classifier element, said multiplexer, said field register, and each of said buffers, said sequencer determining which target bit pattern is being matched.

A classifier element for matching a target bit pattern with a plurality of filter bit patterns, the classifier element comprising:

• an input stage receiving said target bit pattern and having a plurality of stage outputs, each stage output being a portion of said target bit pattern;
• a multiplexer stage receiving said stage outputs, said multiplexer stage selecting one of said stage outputs as a multiplexer output based on a sequencer output;
• a memory stage unit receiving said multiplexer output and said sequencer output, said storage unit having a storage unit output determined by said multiplexer output and said sequencer output, said memory stage unit storing intermediate arrays generated from said filter bit patterns;
• gate means for performing an AND operation between successive storage unit outputs and a match vector to produce a new match vector, said match vector indicating which filter bit pattern matches said target bit pattern;
• and
• match vector storage means for storing said match vector, said match vector storage means receiving said new match vector to overwrite an old match vector, said match vector storage means outputting said match vector.

A method of determining whether a target bit pattern matches at least one of a plurality of filter bit patters, each bit pattern being composed of a specific sequence of element bits, each element bit in said target bit pattern having a value of either 1 or 0 and each element bit in said filter bit pattern having a value of 1, 0, or x where x can be matched by any value of an element bit, the method comprising:

• a) generating a target vector from said target bit patted;
• b) generating a filter array from said plurality of filter bit patterns, each filter bit pattern corresponding to a row in said filter array;
• c) generating at least one intermediate array based on said filter array;
• d) selecting specific columns from said at least one intermediate array based on bit values of said target vector;
• e) generating a final array from columns selected in step d);
• and
• f) generating a match vector from said final array, each vector element of said match vector being a result of a bitwise AND operation on a row of said final array,
• wherein each vector element in said match vector having a value of 1 indicates a match between said target bit pattern and a filter bit pattern corresponding to a row in said filter array having the same row number as said vector element.