Switching circuit implementing variable string matching
View Patent ↗A content matching engine (CME) uses a content addressable memory (CAM) array that stores a plurality of strings in separate entries. The strings define one or more rules to be matched. The strings of each rule are linked, thereby providing a required order. The strings of each rule can be linked by per-entry counters associated with each string, or by a state machine. The strings in the CAM array are compared with a packet, which is shifted one symbol at a time (because the strings can start on any boundary). When the CAM detects a match, the CAM skips over the string that resulted in the match, thereby preventing erroneous matches. The CAM allows parallel matching to be performed for multiple rules. If the contents of a packet match all of the strings of a rule, in order, then the CME asserts a match/index signal that identifies the matched rule.
1. A content matching engine comprising:
a shift register configured to receive and shift a packet in a byte-wise manner, thereby providing a pattern;
a content addressable memory (CAM) array having a plurality of entries configured to store a corresponding plurality of strings that identify a first rule, wherein each of the entries is coupled to receive the pattern in parallel from the shift register, and assert a match output signal if the string stored in the entry matches the pattern;
a plurality of entry counters, each being coupled to receive a match output signal from a corresponding entry of the CAM array, and each storing a count value associated with the length of the string stored in the corresponding entry of the CAM array;
connections between output terminals of a first set of the entry counters and enable terminals of a set of the entries; and
a priority encoder coupled to output terminals of a second set of the entry counters.
2. The content matching engine of claim 1 , wherein each of the entry counters is configured to count down toward a zero count upon detecting an asserted match output signal.
3. The content matching engine of claim 2 , wherein each of the entry counters is configured to assert an output signal in response to reaching a zero count.
4. The content matching engine of claim 1 , wherein the shift register is configured to shift the packet at a frequency of one byte per clock cycle.
5. The content matching engine of claim 1 , wherein the CAM array is a ternary CAM array capable of storing “don't care” values.
6. The content matching engine of claim 1 , wherein the CAM array further comprises a plurality of entries configured to store a corresponding plurality of strings that identify a second rule.
7. The content matching engine of claim 1 , wherein at least one of the connections connects the output terminal of one of the entry counters to the enable terminals of a plurality of entries.
8. The content matching engine of claim 1 , wherein the CAM array comprises a plurality of CAM blocks connected in parallel.