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 method of processing a data packet comprising:
comparing the data packet with a list of regular expressions or rules stored in a content addressable memory (CAM) array to determine if the data packet matches any of the regular expressions or rules;
wherein comparing the data packet comprises:
(a) comparing the data packet with the regular expressions and rules stored in the CAM array;
(b) shifting the data packet by one symbol, thereby providing a shifted pattern;
(c) comparing the shifted pattern with the regular expressions and rules stored in the CAM array; and
(d) repeating steps (b) and (c) until the entire data packet has been shifted and compared with the regular expressions and rules stored in the CAM array;
upon detecting a match between the data packet and a regular expression or rule, switching the data packet to a server designated for processing data packets exhibiting the regular expression or rule;
asserting a first match signal when the data packet or shifted pattern matches a first entry of the CAM array having a length of N symbols; and
preventing a second entry of the CAM array from asserting a second match signal until after the data packet or shifted pattern has been shifted N times after the first match signal is asserted.
2. The method of claim 1 , further comprising asserting a second match signal when the shifted pattern matches the second entry of the CAM array after the data packet or shifted pattern has been shifted N times after the first match signal is asserted.
3. The method of claim 2 , wherein the first entry and second entry of the CAM array comprise the regular expressions or rules.
4. The method of claim 2 , further comprising:
generating an index signal in response to the asserted second match signal; and
rerouting the data packet in response to the index signal.
5. The method of claim 1 , further comprising:
storing the count N in a location associated with the first entry; and
loading the count N from the location into a counter when the first match signal is asserted.
6. The method of claim 1 , further comprising using a state machine to implement the step of preventing.
7. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet includes an image request.
8. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet includes a CGI script transaction.
9. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet includes a cookie.
10. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet includes an FTP transaction.
11. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet is sent by a paying customer.
12. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet is SPAM.
13. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet is an advertisement.
14. The method of claim 1 , wherein one of the regular expressions or rules determines whether the data packet is a banner.
15. The method of claim 1 , wherein one of the regular expressions or rules comprises: a first predetermined string, followed by any symbol, followed by a second predetermines string, followed by any symbol, followed by a third or fourth predetermined string.
16. The method of claim 15 , wherein the data packet is an internet protocol (IP) packet, and wherein the first, second, third, and fourth predetermined strings are located in Layer 7 of the IP packet.
17. The method of claim 1 , wherein one of the regular expressions comprise strings, wild cards, and character subsets.
18. The method of claim 1 , further comprising revising the regular expressions and rules stored in the CAM array on the fly.
19. The method of claim 1 , further comprising processing the data packet at 2.4 giga-bits per second, or faster.
20. A method of processing a data packet comprising:
comparing the data packet with a list of regular expressions or rules stored in a plurality of parallel content addressable memory (CAM) arrays to determine if the data packet matches any of the regular expressions or rules;
wherein comparing the data packet comprises:
(a) comparing the data packet with the regular expressions and rules stored in the CAM array;
(b) shifting the data packet by one symbol, thereby providing a shifted pattern;
(c) comparing the shifted pattern with the regular expressions and rules stored in the CAM array; and
(d) repeating steps (b) and (c) until the entire data packet has been shifted and compared with the regular expressions and rules stored in the CAM array;
upon detecting a match between the data packet and a regular expression or rule, switching the data packet to a server designated for processing data packets exhibiting the regular expression or rule;
asserting a first match signal when the data packet or shifted pattern matches a first entry of the CAM array having a length of N symbols; and
preventing a second entry of the CAM array from asserting a second match signal until after the data packet or shifted pattern has been shifted N times after the first match signal is asserted.
21. The method of claim 20 , further comprising processing the data packet at 10 giga-bits per second, or faster.