System and method for performing regular expression matching with high parallelism

An apparatus comprising:

• means for pattern matching having a plurality of information storage entries with two or more regular expressions, each regular expression including a plurality of characters and each regular expression associated with a corresponding action to be applied when matching strings are found;
• means for identifying one or more borders within each regular expression, the one or more borders separating the regular expression into a plurality of sub-expressions, each sub-expression having a plurality of sequential characters;
• means for loading each of the plurality of entries of the means for pattern matching with the plurality of the sequential characters from one of the sub-expressions of the plurality of sub-expressions, the entries stored in content addressable memory (CAM);
• means for applying a string from a network message to the entries of the pattern matching engine to search the string simultaneously in parallel for sub-expressions from each of the two or more regular expressions;
• means for determining that the sub-expressions of at least one regular expression match the string;
• and
• means for executing the corresponding action associated with that at least one regular expression on the network message.

A method for operating a pattern matching engine comprising the steps of:

• obtaining two or more regular expressions;
• identifying one or more borders within each regular expression using a deterministic finite state machine, the one or more borders separating the regular expression into a plurality of sub expressions, each sub expression including one or more characters, each border indicated by one or more predetermined metacharacters;
• loading separate portions of a memory of the pattern matching engine with the sequential characters from each of the plurality of sub expressions of the two or more regular expressions;
• applying a string from a network message to the memory to search the string in parallel for sub expressions from each of the two or more regular expression;
• and
• determining that at least one of the two or more regular expressions matches the string and executing in response thereto a corresponding action associated with that regular expression;
• wherein the memory is a content addressable memory (CAM).

An apparatus comprising:

• a pattern matching engine configured to obtain two or more regular expressions and to identify one or more borders within each regular expression using a deterministic finite state machine, the one or more borders separating the regular expression into a plurality of sub expressions, each sub expression including one or more characters, each border indicated by one or more predetermined metacharacters;
• a memory of the pattern matching engine configured to store the sequential characters from each of the plurality of sub expressions of the two or more regular expressions in separate portions of memory, the memory further configured to, in response to application of a string from a network message, search the string in parallel for sub expressions from each of the two or more regular expression, and to determine that at least one of the two or more regular expressions matches the string;
• and
• the pattern matching engine further configured to cause the execution of a corresponding action associated with that regular expression that matches;
• wherein the memory is a content addressable memory (CAM).