Method and apparatus for high-speed parsing of network messages

• US 20050165966A1
• Filed: 03/21/2005
• Published: 07/28/2005
• Est. Priority Date: 03/28/2000
• Status: Active Grant

• Current Assignee: Silvano Gai, Thomas J. Edsall
• Original Assignee: Silvano Gai, Thomas J. Edsall
• Inventors: Edsall, Thomas J., Gai, Silvano
• Granted Patent: US 7,395,332 B2
• Time in Patent Office: Days
• US Class Current: 709/249
• 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 method for searching network messages for pre-defined regular expressions is disclosed. A plurality of pre-defined regular expressions are stored in a content-addressable memory (CAM). A network message or selected portion thereof is inputted to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time. An output is returned from the CAM. In response to the output from the CAM, identifying an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

Claims

1. A method for searching network messages for pre-defined regular expressions, the method comprising the steps of:

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

inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time;

returning an output from the CAM; and

identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

2. The method of claim 1, further comprising:

storing the pre-defined regular expressions in a memory storage device, and also storing one or more actions that are to be applied to network messages matching the respective regular expressions in the memory storage device; and

operating the memory storage device in interaction with the CAM.

3. The method of claim 1, further comprising:

appending a tag to the network message or selected portion thereof that is input to the CAM;

defining a single logical CAM within the CAM as all CAM entries having the same tag value; and

constraining the matching of a given CAM input having a tag value to the CAM entries corresponding to the tag value.

4. The method of claim 1, further comprising:

using as the CAM a ternary content addressable memory (TCAM);

storing the pre-defined regular expressions in a random access memory (RAM); and

storing one or more actions that are to be applied to network messages matching the respective regular expressions in the random access memory (RAM).

5. The method of claim 1, further comprising:

configuring a barrel shifter to provide a selected portion of a network message to the CAM input.

6. The method of claim 5, further comprising:

configuring a second barrel shifter to apply a selected portion of a second network message to a decoder circuit in parallel fashion with the network message, the decoder circuit using the CAM.

7. The method of claim 1, further comprising:

providing in an input to the CAM a message data space for storing the network message or portion thereof provided by a 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.

8. The method of claim 1, further comprising:

returning in the output from the CAM an identification of the action to be applied to the respective network message; and

in the event that further searching is to be performed on the respective network message, providing 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.

9. The method of claim 1, further comprising:

returning in the output from the CAM a done flag, which if asserted indicates that processing of the respective message is complete.

10. The method of claim 1, further comprising:

configuring a logic circuit to extract one or more selected fields from network messages and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.

11. The method of claim 1, further comprising:

receiving a network message having two tags; and

storing a second tag while the message is searched under a first tag.

12. The method of claim 1, further comprising:

actuating a counter in response to an action performed on a network message.

13. The method of claim 1, further comprising:

storing in a memory device the action to be applied to the network message in the event that the network message matches one of the CAM entries.

14. A pattern matching engine apparatus for use in searching network messages for pre-defined regular expressions, comprising:

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

a decoder circuit configured to control an input to the CAM, the input including a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM; and

an output from the CAM, and in response to the output from the CAM, identifying an action to be applied to the given network message or portion thereof, and the CAM 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.

15. The apparatus of claim 14, further comprising:

a memory storage device to store the pre-defined regular expressions, and also to store one or more actions that are to be applied to network messages matching the respective regular expressions; and

operating the memory storage device in interaction with the CAM.

16. The apparatus of claim 14, further comprising:

a tag to appended to the network message or selected portion thereof that is input to the CAM;

a single logical CAM within the CAM having all CAM entries that have the same tag value; and

means for constraining the matching of a given CAM input having a tag value to the CAM entries corresponding to the tag value.

17. The apparatus of claim 14, further comprising:

a ternary content addressable memory (TCAM) used as the CAM; and

a random access memory (RAM) to store the pre-defined regular expressions, and to store one or more actions that are to be applied to network messages matching the respective regular expressions.

18. The apparatus of claim 14, further comprising:

a barrel shifter to provide a selected portion of a network message to the CAM input.

19. The apparatus of claim 18, further comprising:

a second barrel shifter to apply a selected portion of a second network message to a decoder circuit in parallel fashion with the network message, the decoder circuit using the CAM.

20. The apparatus of claim 14, further comprising:

an input to the CAM having a message data space for storing the network message or portion thereof provided by a barrel shifter, a tag space for storing a selected tag, and an end flag indicating whether the message data space contains a last segment of the respective network message.

21. The apparatus of claim 14, further comprising:

an identification of the action to be applied to the given network message returned in the output from the CAM; and

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, in the event that further searching is to be performed on the given network message.

22. The apparatus of claim 14, further comprising:

a done flag returned in the output from the CAM, and the done flag indicating if asserted that processing of the respective message is complete.

23. The apparatus of claim 14, further comprising:

a logic circuit to extract one or more selected fields from network messages and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.

24. The apparatus of claim 14, further comprising:

two tags attached to a received network message; and

a memory to store a second tag while the message is searched under a first tag.

25. The apparatus of claim 14, further comprising:

a counter actuated in response to an action performed on a network message.

26. The apparatus of claim 14, further comprising:

a memory device to store the action to be applied to the network message in the event that the network message matches one of the CAM entries.

27. A pattern matching engine apparatus for use in searching network messages for pre-defined regular expressions, comprising:

means for storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM);

means for inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time;

returning an output from the CAM; and

means for identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

28. The apparatus of claim 27, further comprising:

means for storing the pre-defined regular expressions in a memory storage device, and also storing one or more actions that are to be applied to network messages matching the respective regular expressions in the memory storage device; and

means for operating the memory storage device in interaction with the CAM.

29. The apparatus of claim 27, further comprising:

means for appending a tag to the network message or selected portion thereof that is input to the CAM;

means for defining a single logical CAM within the CAM as all CAM entries having the same tag value; and

means for constraining the matching of a given CAM input having a tag value to the CAM entries corresponding to the tag value.

30. The apparatus of claim 27, further comprising:

means for using as the CAM a ternary content addressable memory (TCAM);

means for storing the pre-defined regular expressions in a random access memory (RAM); and

means for storing one or more actions that are to be applied to network messages matching the respective regular expressions in the random access memory (RAM).

31. The apparatus of claim 27, further comprising:

means for configuring a barrel shifter to provide a selected portion of a network message to the CAM input.

32. The apparatus of claim 27, further comprising:

means for configuring a second barrel shifter to apply a selected portion of a second network message to a decoder circuit in parallel fashion with the network message, the decoder circuit using the CAM.

33. The apparatus of claim 27, further comprising:

means for providing in an input to the CAM a message data space for storing the network message or portion thereof provided by a 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.

34. The apparatus of claim 27, further comprising:

means for returning in the output from the CAM an identification of the action to be applied to the respective network message; and

in the event that further searching is to be performed on the respective network message, means for providing 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.

35. The apparatus of claim 27, further comprising:

means for returning in the output from the CAM a done flag, which if asserted indicates that processing of the respective message is complete.

36. The apparatus of claim 27, further comprising:

means for configuring a logic circuit to extract one or more selected fields from network messages and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.

37. The apparatus of claim 27, further comprising:

means for receiving a network message having two tags; and

means for storing a second tag while the message is searched under a first tag.

38. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of,

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

inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time;

returning an output from the CAM; and

identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

39. Electromagnetic signals propagating on a computer network, comprising:

said electromagnetic signals carrying instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of,

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

inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time;

returning an output from the CAM; and

identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.