Pattern matching in a multiprocessor environment with finite state automaton transitions based on an order of vectors in a state transition table

• US 7,805,392 B1
• Filed: 11/29/2006
• Issued: 09/28/2010
• Est. Priority Date: 11/29/2005
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Tilera Corporation (NVIDIA Corporation)
• Inventors: Agarwal, Anant, Steele, Kenneth M.
• Primary Examiner(s): Holmes; Michael B.
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US11/564,694
• Time in Patent Office: 1,399 Days
• Field of Search: 706/48
• US Class Current: 706/48
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Pattern matching in a plurality of interconnected processing engines includes: accepting a stream of input sequences over an interface and storing the input sequences; storing instructions for matching an input sequence to one or more patterns in memory accessible by a first set of one or more processing engines, and storing instructions for matching an input sequence to one or more patterns in memory accessible by a second set of one or more processing engines; distributing information identifying selected input sequences to the first and second sets of processing engines; and retrieving the identified input sequences to perform pattern matching in the first and second sets of processing engines.

Claims

1. A method for pattern matching in a plurality of interconnected processing engines, comprising:

accepting at least one input sequence of symbols over an interface;

accepting a specification of transitions among states associated with a finite state automaton for matching an input sequence to one or more patterns, the specification comprising a state transition table having a first dimension corresponding to states and a second dimension corresponding to input symbols, with each transition being associated with at least one symbol, with multiple subsets of transitions comprising vectors in the first dimension each associated with a respective input symbol and specifying next state transitions for each current state, and with the input symbol associated with a given vector in the first dimension of the state transition table being determined by the position of the given vector in the table;

selecting an order associated with the vectors that is different from the order of the vectors in the state transition table;

storing data that specifies the transitions according to the selected order; and

performing pattern matching in a plurality of interconnected processing engines including determining whether the accepted input sequence matches a pattern based on the stored data, with the determining including, for at least one input symbol in the accepted input sequence;

translating the input symbol in the accepted input sequence to a different symbol according to the change in position of a given vector between the order defined by the state transition table and the order defined by the stored data,

determining one of the vectors that corresponds to the translated input symbol, and

determining a transition from a current state to a next state based on the determined vector and the stored data.

2. The method of claim 1, wherein the order associated with the vectors is selected based on reducing the size of the stored data that specifies the transitions.

3. The method of claim 1, wherein the data that specifies the transitions according to the selected order comprises:

a subset of consecutive components of a vector in the second dimension of the state transition table associated with a current state and specifying next state transitions for each input symbol that excludes transitions to an initial state of the finite state automaton before and after the subset, and

data that indicates a relative position of the subset of consecutive components within the vector.

4. The method of claim 1, wherein the data that indicates the relative position includes the smallest of the relative positions of the consecutive components.

5. The method of claim 4, wherein the data that indicates the relative position further includes the largest of the relative positions of the consecutive components.

6. The method of claim 4, wherein the data that indicates the relative position further includes data based on the number of consecutive components in the subset.

7. The method of claim 1, wherein translating the input symbol in the accepted input sequence further comprises translating uppercase and lowercase versions of letters into a single case.

8. The method of claim 1, wherein translating the input symbol in the accepted input sequence further comprises translating each of multiple symbols not appearing in the patterns into a single symbol not appearing in the patterns.

9. The method of claim 8, wherein translating the input symbol in the accepted input sequence further comprises translating two symbols not appearing in the patterns and all the symbols between them into a single symbol not appearing in the pattern if the number of symbols between them are fewer than the minimum number of symbols in any of the patterns.

10. The method of claim 1, wherein the order associated with the vectors is selected based on placing a first portion of the stored data that specifies transitions from a first state close to a second portion of the stored data that specifies transitions from a second state, wherein there is at least one transition from the first state to the second state.

11. The method of claim 10, wherein the first portion and the second portion are stored close enough to be mapped to the same cache line.

12. The method of claim 1, in which:

accepting at least one input sequence of symbols over the interface includes accepting a stream of input sequences over the interface and storing the input sequences;

storing the data includes storing instructions for matching an input sequence to one or more patterns in memory accessible by a first set of one or more processing engines, and storing instructions for matching an input sequence to one or more patterns in memory accessible by a second set of one or more processing engines; and

performing pattern matching includes

distributing information identifying selected input sequences to the first and second sets of processing engines, and

retrieving the identified input sequences to perform pattern matching in the first and second sets of processing engines.

13. The method of claim 12, further comprising assigning input sequences to the first and second sets of processing engines based on status information from the sets of processing engines.

14. The method of claim 13, wherein the status information comprises an indication of a work load on a set of processing engines.

15. The method of claim 14, wherein information identifying an accepted input sequence is distributed to a set of processing engines that have the lowest work load.

16. The method of claim 14, wherein the indication of the work load comprises at least one of a number of input sequences currently being processed and a number of input sequences in an input queue.

17. The method of claim 12, further comprising assigning input sequences to the first and second sets of processing engines based on an identified class of a packet that includes the input sequence.

18. The method of claim 17, wherein at least one of the sets of processing engines is dedicated to performing pattern matching for input sequences in packets of a corresponding class.

19. The method of claim 12, further comprising gathering results of the pattern matching performed by the first set of one or more processing engines and the second set of one or more processing engines.

20. The method of claim 12, wherein the instructions stored in the memory accessible to the first set of processing engines comprise a program corresponding to a finite state automaton.

21. The method of claim 20, wherein the finite state automaton includes states corresponding to a keyword tree of a Aho-Corasick pattern matching technique.

22. The method of claim 20, wherein the memory accessible to the first set of processing engines stores data specifying transitions among states associated with the finite state automaton.

23. The method of claim 20, wherein the first set of processing engines performs a first of the following functions in a first subset of the processing engines and a second of the following functions in a second subset of the processing engines that does not overlap with the first subset:

translating symbols within an input sequence based on an order associated with subsets of the specified transitions;

determining a transition from a current state to a next state based on a translated symbol and the stored data; and

determining an output rule in response to determining that an input sequence matches a pattern.

24. The method of claim 23, wherein the first set of processing engines performs all three of the functions in different non-overlapping subsets of processing engines.

25. The method of claim 23, wherein translating symbols within an input sequence further comprises translating uppercase and lowercase versions of letters to a single case.

26. The method of claim 20, wherein the finite state automaton includes one or more states associated with transitions corresponding to a deterministic finite automaton and one or more states associated with transitions corresponding to a non-deterministic finite automaton.

27. The method of claim 12, wherein the memory accessible by the first set of processing engines and the memory accessible by the second set of processing engines comprise memory caches within the respective processing engines.

28. The method of claim 27, wherein the instructions stored in the memory accessible by the first set of processing engines comprise an active portion of a program corresponding to a finite state automaton.

29. The method of claim 27, wherein the instructions stored in the memory accessible by the first set of processing engines comprise at least a portion of a program corresponding to a finite state automaton for matching a first set of patterns, and the instructions stored in the memory accessible by the second set of processing engines comprise at least a portion of a program corresponding to a finite state automaton for matching a second set of patterns different from the first set of patterns.

30. The method of claim 27, further comprising processing a specification of transitions among states associated with a finite state automaton for matching an input sequence to one or more patterns to generate data specifying the transitions based on storage constraints of the memory caches of the first set of processing engines.

31. The method of claim 30, wherein the data is small enough to fit in the memory caches of the first set of processing engines.

32. The method of claim 30, wherein processing the specification of transitions to generate the data based on the storage constraints comprises selecting an order associated with subsets of the transitions.

33. The method of claim 30, wherein processing the specification to generate the data based on the storage constraints comprises generating a representation of the finite state automaton in which one or more of the states are associated with transitions corresponding to a deterministic finite automaton and one or more states are associated with transitions corresponding to a non-deterministic finite automaton.

34. The method of claim 12, wherein the instructions stored in the memory accessible by the first set of processing engines comprise at least a portion of a first program corresponding to a first finite state automaton, and the instructions stored in the memory accessible by the second set of processing engines comprise at least a portion of a second program corresponding to a second finite state automaton different from the first finite state automaton.

35. The method of claim 34, wherein the instructions stored in the memory accessible by the first set of processing engines are stored before the stream of input sequences are accepted over the interface.

36. The method of claim 35, wherein the instructions stored in the memory accessible by the second set of processing engines are stored after at least some of the input sequences have been accepted over the interface.

37. The method of claim 34, wherein the instructions stored in the memory accessible by the first set of processing engines are stored after at least some of the input sequences have been accepted over the interface.

38. The method of claim 34, wherein the instructions stored in the memory accessible by the first set of processing engines are stored while the second set of processing engines are processing input sequences.

39. The method of claim 38, wherein the first set of processing engines starts processing input sequences according to its stored instructions after the second set of processing engines finishes processing input sequences according to its stored instructions.

40. The method of claim 34, wherein the first finite state automaton matches an input sequence to one or more case-sensitive patterns.

41. The method of claim 40, wherein the second finite state automaton matches an input sequence to one or more case-insensitive patterns.

42. The method of claim 12, wherein the input sequences comprise segments of a character stream.

43. The method of claim 42, wherein the first and second sets of processing engines perform pattern matching to the same patterns.

44. The method of claim 43, wherein at least some of the segments include the same portion of the character stream.

45. The method of claim 44, wherein each set of processing engines processes a given segment starting from an initial state.

46. The method of claim 44, wherein at least some of the segments processed by the first set of processing engines include the same portion of the character stream as a segment processed by the second set of processing engines.

47. The method of claim 46, wherein the portion of the character stream that is the same in a first segment and a second segment is one character shorter than a maximum length of the patterns being matched in the first and second sets of processing engines.

48. The method of claim 44, further comprising gathering results of the pattern matching performed by the first set of one or more processing engines and the second set of one or more processing engines.

49. The method of claim 48, wherein gathering results of the pattern matching includes filtering the results to identify a portion of the character stream matched in more than one input sequence.

50. The method of claim 43, wherein each set of processing engines processes a given segment starting from a state determined after processing a previous segment.

51. The method of claim 12, wherein at least some of the input sequences each comprise at least a portion of a packet.

52. The method of claim 51, wherein at least some of the input sequences each comprise a payload of a packet.

53. The method of claim 1,

wherein one or more of the states are associated with transitions corresponding to a deterministic finite automaton and one or more states are associated with transitions corresponding to a non-deterministic finite automaton.

54. The method of claim 53, wherein at least some of the transitions corresponding to a non-deterministic finite automaton fail to a state associated with transitions corresponding to a deterministic finite automaton.

55. The method of claim 54, wherein all of the transitions corresponding to a non-deterministic finite automaton fail to a state associated with transitions corresponding to a deterministic finite automaton.

56. The method of claim 53, wherein all of the transitions corresponding to a non-deterministic finite automaton fail to the same failure state.

57. The method of claim 56, wherein the failure state comprises an initial state of the finite state automaton.

58. The method of claim 56, wherein the failure state comprises a state to which the largest number of transitions terminate.

59. The method of claim 56, wherein the finite state automaton does not include any direct transitions to children of the failure state from a state other than the failure state.

60. The method of claim 53, wherein determining whether the accepted input sequence matches the pattern comprises, for a given symbol in the input sequence, accessing a first portion of the stored data that determines a transition from a current state in parallel with accessing a second portion of the stored data that determines a transition from a state to which the current state transitions if the given symbol fails to match a specified transition from the current state.

61. The method of claim 60, wherein accessing the first and second portions of the stored data in parallel comprises accessing the first and second portions in different execution units of a processing engine.

62. The method of claim 60, wherein accessing the first and second portions of the stored data in parallel comprises accessing the first and second portions in different processing engines of an interconnected network of processing engines.

63. The method of claim 60, wherein accessing the first and second portions of the stored data in parallel comprises overlapping execution of instructions associated with accessing the first and second portions in a pipeline.

64. A system for pattern matching, comprising:

a plurality of interconnected processing engines;

an interface to at least one of the processing engines configured to accept at least one input sequence of symbols; and

memory accessible by one or more of the processing engines that stores data that specifies transitions among states associated with a finite state automaton for matching an input sequence to one or more patterns, based on an accepted specification comprising a state transition table having a first dimension corresponding to states and a second dimension corresponding to input symbols, with each transition being associated with at least one symbol, with multiple subsets of transitions comprising vectors in the first dimension each associated with a respective input symbol and specifying next state transitions for each current state, and with the input symbol associated with a given vector in the first dimension of the state transition table being determined by the position of the given vector in the table;

at least one of the processing engines being configured to translate input symbols in the input sequence according to a selected order associated with the vectors that is different from the order of the vectors in the state transition table; and

at least one of the processing engines being configured to determine whether the accepted input sequence matches a pattern based on the stored data that specifies the transitions, with the determining including, for at least one input symbol in the accepted input sequence;

translating the input symbol in the accepted input sequence to a different symbol according to the change in position of a given vector between the order defined by the state transition table and the order defined by the stored data,

determining one of the vectors that corresponds to the translated input symbol, and

determining a transition from a current state to a next state based on the determined vector and the stored data.

65. The system of claim 64, wherein translating the input symbol in the accepted input sequence further comprises translating uppercase and lowercase versions of letters into a single case.

66. The system of claim 64, wherein translating the input symbol in the accepted input sequence further comprises translating each of multiple symbols not appearing in the patterns into a single symbol not appearing in the patterns.

67. The system of claim 64, in which:

the interface is configured to accept a stream of input sequences;

the memory accessible by one or more of the processing engines includes

memory accessible by a first set of one or more processing engines that stores instructions for matching an input sequence to one or more patterns, and

memory accessible by a second set of one or more processing engines that stores instructions for matching an input sequence to one or more patterns;

at least one processing engine is configured to distribute information identifying selected input sequences to the first and second sets of processing engines; and

the first and second sets of processing engines are configured to retrieve the identified input sequences to perform pattern matching.

68. The system of claim 67, wherein at least one processing engine is configured to assign input sequences to the first and second sets of processing engines based on status information from the sets of processing engines.

69. The system of claim 68, wherein the status information comprises an indication of a work load on a set of processing engines.

70. The system of claim 67, wherein at least one processing engine is configured to assign input sequences to the first and second sets of processing engines based on an identified class of a packet that includes the input sequence.

71. The system of claim 67, wherein at least one processing engine is configured to gather results of the pattern matching performed by the first set of one or more processing engines and the second set of one or more processing engines.

72. The system of claim 67, wherein the instructions stored in the memory accessible to the first set of processing engines comprise a program corresponding to a finite state automaton.

73. The system of claim 72, wherein the finite state automaton includes states corresponding to a keyword tree of a Aho-Corasick pattern matching technique.

74. The system of claim 64,

wherein one or more of the states are associated with transitions corresponding to a deterministic finite automaton and one or more states are associated with transitions corresponding to a non-deterministic finite automaton.

75. The system of claim 74, wherein at least some of the transitions corresponding to a non-deterministic finite automaton fail to a state associated with transitions corresponding to a deterministic finite automaton.

76. The system of claim 75, wherein all of the transitions corresponding to a non-deterministic finite automaton fail to a state associated with transitions corresponding to a deterministic finite automaton.

77. The system of claim 74, wherein all of the transitions corresponding to a non-deterministic finite automaton fail to the same failure state.