Content search mechanism that uses a deterministic finite automata (DFA) graph, a DFA state machine, and a walker process

• US 9,336,328 B2
• Filed: 07/22/2014
• Issued: 05/10/2016
• Est. Priority Date: 09/10/2004
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Hussain, Muhammad R., Carlson, David A., Bouchard, Gregg A., Parker, Trent
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US14/337,759
• Publication Number:
  US 20140337387A1
• Time in Patent Office: 658 Days
• Field of Search: 706/12, 706/45, 706/62
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

An improved content search mechanism uses a graph that includes intelligent nodes avoids the overhead of post processing and improves the overall performance of a content processing application. An intelligent node is similar to a node in a DFA graph but includes a command. The command in the intelligent node allows additional state for the node to be generated and checked. This additional state allows the content search mechanism to traverse the same node with two different interpretations. By generating state for the node, the graph of nodes does not become exponential. It also allows a user function to be called upon reaching a node, which can perform any desired user tasks, including modifying the input data or position.

Claims

1. A network services processor comprising:

at least one processor configured to process packets in an input stream of packets and match at least one pattern in the input stream by traversing a data structure generated from one or more regular expressions for a content processing application; and

at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and to perform at least one task based on traversing the at least one node, enabling the at least one processor to generate and check state information at the at least one node to obviate a post-processing overhead of the at least one pattern matched, to improve performance of the at least one processor relative to performing post-processing of results for the content processing application.

2. The network services processor of claim 1, wherein the at least one node having the intelligent node structure includes at least one outgoing arc associated with a depth from a root node of the generated data structure and the depth is either a total number of characters traversed from the root node of the graph or a value that represents an unknown depth.

3. The network services processor of claim 1, wherein the at least one task is determined based on whether a depth of the at least one node having the intelligent node structure from a root node of the generated data structure is known or unknown.

4. The network services processor of claim 1, wherein the data structure generated is a Deterministic Finite Automata (DFA) graph, the next node represents a next state of the DFA graph for a given character of the input stream, and the state generated is in addition to and different from state of the DFA graph.

5. The network services processor of claim 1, wherein the data structure generated is a DFA graph and the at least one task is determined during generation of the data structure obviating exponential growth of the DFA graph.

6. The network services processor of claim 1, wherein the intelligent node structure associates at least one command with the at least one node enabling the at least one processor to call a function to perform the at least one task.

7. The network services processor of claim 6, wherein the at least one command is based on whether or not a given regular expression of the one or more regular expressions is a fixed or non-fixed expression.

8. The network services processor of claim 6, wherein the intelligent node structure stores the at least one command directly or includes a reference to a location at which the at least one command is stored.

9. The network services processor of claim 6, wherein the at least one node having the intelligent node structure includes at least one outgoing arc associated with a set of commands and at least one command of the set of commands enables the at least one processor to call a function to perform the at least one task.

10. The network services processor of claim 1, wherein the intelligent node structure enables the at least one processor to report a match, of the at least one pattern matching in the input stream, at the at least one node, based on applying restrictions to qualify validity of the match, at the at least one node.

11. A method comprising:

generating a data structure from one or more regular expressions for a content processing application enabling at least one processor, configured to process packets in an input stream, to match at least one pattern in the input stream by traversing the data structure generated with characters from the packets;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and to perform at least one task based on traversing the at least one node, enabling the at least one processor to generate and check state information at the at least one node to obviate post-processing overhead of the at least one pattern matched, to improve performance of the at least one processor relative to performing post-processing of results for the content processing application; and

storing the data structure generated in at least one memory operatively coupled to the at least one processor.

12. The method of claim 11, wherein the at least one node having the intelligent node structure includes at least one outgoing arc associated with a depth from a root node of the generated data structure and the depth is either a total number of characters traversed from the root node of the graph or a value that represents an unknown depth.

13. The method of claim 11, wherein the at least one task is determined based on whether a depth of the at least one node having the intelligent node structure from a root node of the generated data structure is known or unknown.

14. The method of claim 11, wherein the data structure generated is a Deterministic Finite Automata (DFA) graph, the next node represents a next state of the DFA graph for a given character of the input stream, and the state generated is in addition to and different from state of the DFA graph.

15. The method of claim 11, wherein the data structure generated is a DFA graph and the at least one task is determined during generation of the data structure obviating exponential growth of the DFA graph.

16. The method of claim 11, wherein the intelligent node structure associates at least one command with the at least one node enabling the at least one processor to call a function to perform the at least one task.

17. The method of claim 16, wherein the at least one command is based on whether or not a given regular expression of the one or more regular expressions is a fixed or non-fixed expression.

18. The method of claim 16, wherein the at least one node having the intelligent node structure includes at least one outgoing arc associated with a set of commands and at least one command of the set of commands enables the at least one processor to call a function to perform the at least one task.

19. The method of claim 11, wherein the intelligent node structure enables the at least one processor to report a match, of the at least one pattern matching in the input stream, at the at least one node, based on applying restrictions to qualify validity of the match, at the at least one node.

20. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:

generate a data structure from one or more regular expressions for a content processing application enabling the processor, configured to process packets in an input stream, to match at least one pattern in the input stream by traversing the data structure generated with characters from the packets;

including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and to perform at least one task based on traversing the at least one node, enabling the processor to generate and check state information at the at least one node to obviate post-processing overhead of the at least one pattern matched, to improve performance of the at least one processor relative to performing post-processing of results for the content processing application; and

storing the data structure generated in at least one memory operatively coupled to the processor.