Apparatus and method of ordering state transition rules for memory efficient, programmable, pattern matching finite state machine hardware

• US 7,301,792 B2
• Filed: 06/06/2006
• Issued: 11/27/2007
• Est. Priority Date: 03/12/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Sensory Networks, Inc. (Intel Corporation)
• Inventors: Gould, Stephen, Barrie, Robert Matthew, Williams, Darren, de Jong, Nicholas
• Primary Examiner(s): Nguyen, Viet Q.
• Application Number:
  US11/422,529
• Publication Number:
  US 20060221658A1
• Time in Patent Office: 539 Days
• Field of Search: 365/49, 711/108, 711/203, 370/392, 716/2, 716/5, 716/4
• US Class Current: 365/49.15
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: G06F 21/567 using dedicated hardware
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

A programmable finite state machine (FSM) includes, in part, first and second memories, and a selection circuit coupled to each of the memories. Upon receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state, the first memory supplies one ore more matching transition rules stored therein. The selection circuit selects the most specific of the supplied rules. The transition rules are stored in the first memory in a ranking order of generality. The second memory receives the selected transition rule and supplies the next state of the FSM. The first memory may be a ternary content addressable memory and the second memory may be a static random access memory. The contents of both the content addressable memory and the static random memory is determined by an algorithm which minimizes the number of terms required to represent the next-state transition functions.

Claims

1. A programmable finite state machine configured to transition to one of a plurality of next states from a current state in response to receipt of an input symbol, each of the current state and next states being represented by m bits and each input symbol being represented by k bits, the programmable finite state machine comprising:

a first memory configured to store a plurality of transition rules, said first memory further configured to receive a (k+m)-bit word representative of the input symbol and the current state and to supply one or more matching transition rules in response, wherein the one or more matching transition rules are stored in a ranking order of generality;

a logic block configured to derive a specific transition rule from the one or more matching transition rules and the current state; and

a second memory configured to receive the selected transition rule and to supply one of the plurality of next states in response.

2. The programmable finite state machine of claim 1 wherein the first memory is a ternary content addressable memory (TCAM).

3. The programmable finite state machine of claim 1 wherein the second memory is a static random access memory (SRAM).

4. The programmable finite state machine of claim 1 wherein the ranking order of generality is an increasing order of generality.

5. The programmable finite state machine of claim 1 wherein the ranking order of generality is a functionally derived order and which further dictates the configuration of the coupled logic block.

6. The programmable finite state machine of claim 1 wherein the ranking order of generality is an order derived to provide compatibility with the configuration of the coupled logic block.

7. The programmable finite state machine of claim 1 wherein the ranking order of generality is a decreasing order of generality.

8. The programmable finite state machine of claim 1 further comprising:

a register configured to receive the k-bit input symbol and the m-bit current state and to generate the (k+m)-bit word supplied to the TCAM.

9. The programmable finite state machine of claim 1 further comprising:

a look-up table configured to receive the m-bit next state from the second memory and to generate an associated output.

10. The programmable finite state machine of claim 9 wherein the LUT contains a bit configured to accept or reject a request.

11. The programmable finite state machine of claim 1 wherein the logic block is a priority encoder.

12. The programmable finite state machine of claim 1 wherein the logic block is a priority arbiter.

13. The programmable finite state machine of claim 2 further comprising:

cascading a second TCAM to the first TCAM to increase a depth of the programmable finite state machine.

14. The programmable finite state machine of claim 2 further comprising:

cascading a second TCAM to the first TCAM to increase a width of the programmable finite state machine.

15. The programmable finite state machine of claim 1 where the input symbol is received from a digital network, and the programmable finite state machine is configured to provide signature-based network security services selected from a group consisting of network intrusion detection, network monitoring and surveillance, virus protection, traffic filtering, content and copyright classification, storage area networks, policy and access control auditing, spam detection and prevention, fraud detection and network forensics, content-aware switching, and message classification.

16. A method for transitioning to one of a plurality of next states from a current state in response to receipt of an input symbol, each of the current and next states being represented by m bits and each input symbol being represented by k bits, method comprising:

receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state;

supplying one or more matching transition rules, wherein the one or more matching transition rules are stored in a ranking order of generality;

deriving a specific transition rule from the one or more supplied matching transition rules and the current state; and

supplying the one of the plurality of next states.

17. The method of claim 16 wherein the one or more matching transition rules is supplied by a ternary content addressable memory (TCAM).

18. The method of claim 16 wherein the one of the plurality of next states is supplied by a static random access memory (SRAM).

19. The method of claim 16 wherein the ranking order of generality is an increasing order of generality.

20. The method of claim 16 wherein the ranking order of generality is a functionally derived order and which further dictates the configuration of a coupled logic block.

21. The method of claim 16 wherein the ranking order of generality is an order derived to provide compatibility with the configuration of a coupled logic block.

22. The method of claim 16 wherein the ranking order of generality is a decreasing order of generality.

23. The method of claim 16 further comprising:

storing the k-bit input symbol and the m-bit current state.

24. The method of claim 16 further comprising:

generating an output for the one of the plurality of next states.

25. The method of claim 16 wherein most specific transition rule is selected by a priority encoder.

26. The method of claim 16 wherein most specific transition rule is selected by a priority arbiter.

27. The method of claim 17 further comprising cascading a second TCAM to the first TCAM to increase a depth of the plurality of next states.

28. The method of claim 17 further comprising cascading a second TCAM to the first TCAM to increase a width of the plurality of next states.

29. The method of claim 16 wherein transitioning to one of the plurality of next states from the current state is made in connection with a signature-based network security services selected from a group consisting of network intrusion detection, network monitoring and surveillance, virus protection, traffic filtering, content and copyright classification, storage area networks, policy and access control auditing, spam detection and prevention, fraud detection and network forensics, content-aware switching, and message classification.