Method and apparatus for high-speed parsing of network messages

• US 6,892,237 B1
• Filed: 03/28/2000
• Issued: 05/10/2005
• Est. Priority Date: 03/28/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Gai, Silvano
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Assistant Examiner(s): NGUYEN, PHUOC H
• Application Number:
  US09/535,810
• Time in Patent Office: 1,869 Days
• Field of Search: 711/108, 711/120, 709223- 4, 709/231, 709/206, 709/207, 707/6
• US Class Current: 709/224
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/111 Switch interfaces, e.g. port details
• CPC Class Codes: H04L 49/112 Switch control, e.g. arbitration
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports

Abstract

A programmable pattern matching engine efficiently parses the contents of network messages for regular expressions and executes pre-defined actions or treatments on those messages that match the regular expressions. The pattern matching engine is preferably a logic circuit designed to perform its pattern matching and execution functions at high speed, e.g., at multi-gigabit per second rates. It includes, among other things, a message buffer for storing the message being evaluated, a decoder circuit for decoding and executing corresponding actions or treatments, and one or more content-addressable memories (CAMs) that are programmed to store the regular expressions used to search the message. The CAM may be associated with a second memory device, such as a random access memory (RAM), as necessary, that is programmed to contain the respective actions or treatments to be applied to messages matching the corresponding CAM entries. The RAM provides its output to the decoder circuit, which, in response, decodes and executes the specified action or treatment.

Claims

1. A pattern matching engine for use in searching network messages for pre-defined regular expressions and for determining matches thereto, the pattern matching engine comprising;

a regular expression storage device for storing the pre-defined regular expressions and one or more corresponding actions that are to be applied to network messages matching the respective regular expressions, the storage device including a content-addressable memory (CAM) having a plurality of entries containing at least the pre-defined regular expressions; and

a decoder circuit coupled to the regular expression storage device, the decoder circuit configured to control an input to the CAM that includes a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM, and to receive and decode an output returned from the regular expression storage device, the output identifying the action to be applied to the given network message or portion thereof,

whereby the CAM is configured such that each network message, or portion thereof input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.

2. The pattern matching engine of claim 1 wherein each CAM entry further contains a tag such that all CAM entries having the same tag define a single logical CAM within the CAM, and further wherein the decoder circuit is configured to constrain the matching of a given CAM input to the CAM entries corresponding to a selected logical CAM.

3. The pattern matching engine of claim 2 further comprising a barrel shifter operatively coupled to the decoder circuit, the barrel shifter configured to provide a selected portion of a network message to the CAM input as directed by the decoder circuit.

4. The pattern matching engine of claim 3 further comprising a second decoder circuit coupled to the regular expression storage device, and a second barrel shifter operatively coupled to the second decoder circuit, wherein the second decoder circuit and second barrel shifter apply a selected portion of a second network message to the regular expression storage device in parallel fashion with the decoder circuit and barrel shifter.

5. The pattern matching engine of claim 3 wherein the CAM input comprises a message data space for storing the network message or portion thereof provided by the barrel shifter, a tag space for storing the selected tag, and an end flag indicating whether the message data space contains a last segment of the respective network message.

6. The pattern matching engine of claim 5 wherein the output returned by the regular expression storage device comprises an operation code for identifying the action to be applied to the respective network message and, to the extent further searching is to be performed on the respective network message, an offset for use in directing the barrel shifter to select a new message portion for a subsequent CAM input and a tag to be appended to the subsequent CAM input.

7. The pattern matching engine of claim 6 wherein the output further returned by the regular expression storage device further comprises a done flag, which if asserted, indicates that processing of the respective message is complete.

8. The pattern matching engine of claim 7 further comprising a pre-parser logic circuit configured to extract one or more selected fields from network messages received at the pattern matching engine and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.

9. The pattern matching engine of claim 8 wherein a first action output by the regular expression storage device is a call action that comprises first and second tags, and the pattern matching engine further comprises a subroutine stack coupled to the decoder circuit for temporarily storing the second tag while the respective message is searched under the first tag.

10. The pattern matching engine of claim 8 wherein a second action output by the regular expression storage device is a counter action, and the pattern matching engine further comprises a counter memory coupled to the decoder circuit, the counter memory having one or more counters that may be selectively actuated by the decoder circuit in response to the counter action.

11. The pattern matching engine of claim 8 wherein a third action output by the regular expression storage device is a copy action, and the pattern matching engine further comprises a message field memory coupled to the decoder circuit for storing information in response to the copy action.

12. The pattern matching engine of claim 1 wherein the regular expression storage device further includes a second memory structure having a plurality of entries for storing the actions to be applied to the network messages, wherein each entry of the second memory structure is associated with a corresponding entry of the CAM and stores the action to be applied to network messages matching the regular expression of its corresponding CAM entry.

13. The pattern matching engine of claim 12 wherein the second memory structure is a random access memory (RAM).

14. The pattern matching engine of claim 13 wherein the CAM is a ternary content addressable memory (TCAM) that supports don'"'"'t care values.

15. A method for searching network messages for pre-defined regular expressions in order to apply a selected action to network messages matching a given regular expression, the method comprising the steps of:

storing the pre-defined regular expressions in a content-addressable memory (CAM) having a plurality of entries;

decoding a given network message, or selected portion thereof, for comparison with the regular expressions contained within the CAM;

inputting a decoded portion of the given network message to the CAM for comparison with all of the regular expressions stored therein;

decoding an output returned from the CAM; and

identifying, in response to the decoded output, the action that corresponds to a first CAM entry matching the inputted network message or selected portion thereof, whereby input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.

16. The method of claim 15 wherein the step of associating comprises the step of providing a second memory structure having a plurality of entries for storing the actions to be applied to the network messages, wherein each entry of the second memory structure is associated with a corresponding entry of the CAM and stores the action to be applied to network messages matching the regular expression of its corresponding CAM entry.

17. The method of claim 16 further comprising the step of appending a tag to the given network message or selected portion thereof that is input to the CAM, and further wherein each CAM entry contains a tag value such that all CAM entries having the same tag value define a single logical CAM within the CAM.

18. The method of claim 17 wherein the CAM is a ternary content addressable memory (TCAM) and the second memory structure is a random access memory (RAM).

19. An intermediate network device for use in processing and forwarding network messages in a computer network, the intermediate network device comprising:

a plurality of line cards, one or more of the line cards capable of being connected to portions of the computer network by respective communications media, each line card configured to receive and forward network messages;

a message processing card; and

a common bus that provides inter-communication between the plurality of line cards and the message processing card, wherein the message processing card comprises;

pattern matching engine far use in searching network messages for pre-defined regular expressions and for determining matches thereto, the pattern matching engine comprising;

a regular expression storage device for storing the pre-defined regular expressions and one or more corresponding actions that are to be applied to network messages matching the respective regular expressions, the storage device including a content-addressable memory (CAM) having a plurality of entries containing at least the pre-defined regular expressions; and

a decoder circuit coupled to the regular expression storage device, the decoder circuit configured to control an input to the CAM that includes a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM, and to receive and decode an output returned from the regular expression storage device, the output identifying the action to be applied to the given network message or portion thereof;

whereby the CAM is configured such that each network message or portion thereof input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.

20. The intermediate network device of claim 19 wherein each CAM entry of the CAM further contains a tag such that all CAM entries having the same tag define a single logical CAM within the CAM, and further wherein the decoder circuit is configured to constrain the matching of a given CAM input to the CAM entries corresponding to a selected logical CAM.

21. The intermediate network device of claim 20 wherein the pattern matching engine further comprises a barrel shifter operatively coupled to the decoder circuit, the barrel shifter configured to provide a selected portion of a network message to the CAM input as directed by the decoder circuit.

22. The intermediate network device of claim 21 wherein the pattern matching engine further comprises a second decoder circuit coupled to the regular expression storage device, and a second barrel shifter operatively coupled to the second decoder circuit, wherein the second decoder circuit and second barrel shifter apply a selected portion of a second network message to the regular expression storage device in parallel fashion with the decoder circuit and barrel shifter.

23. The intermediate network device of claim 22 wherein the CAM input comprises a message data space for storing the network message or portion thereof provided by the barrel shifter, a tag space for storing the selected tag, and an end flag indicating whether the message data space contains a last segment of the respective network message.

24. The intermediate network device of claim 23 wherein the output returned by the regular expression storage device comprises an operation code for identifying the action to be applied to the respective network message and, to the extent further searching is to be performed on the respective network message, an offset for use in directing the barrel shifter to select a new message portion for a subsequent CAM input and a tag to be appended to the subsequent CAM input.

25. A pattern matching engine for use in searching network messages for pre-defined regular expressions and for determining matches thereto, the pattern matching engine comprising:

means for storing the pre-defined regular expressions and one or more corresponding actions that are to be applied to network messages matching the respective regular expressions, the storage means including a content-addressable memory (CAM) having a plurality of entries containing at least the pre-defined regular expressions; and

means, coupled to the storage means, for decoding actions returned from the storage means, the decoding means configured to control an input to the CAM that includes a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM, and to receive and decode an output returned from the storage means, the output identifying the action to be applied to the given network message or portion thereof;

whereby the CAM is configured such that each network message or portion thereof input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.