CONFIGURING AND PERFORMING CHARACTER PATTERN RECOGNITION IN A DATA PLANE CIRCUIT

• US 20200134308A1
• Filed: 10/01/2019
• Published: 04/30/2020
• Est. Priority Date: 10/29/2018
• Status: Abandoned Application

• Current Assignee: Barefoot Networks, Incorporated (Intel Corporation)
• Original Assignee: Barefoot Networks, Incorporated (Intel Corporation)
• Inventors: Javadi, Masoud Moshref, Soule, Robert, Kim, Changhoon, Lee, Jeongkeun, Foster, John Nathan, Alvarez, Daniel A., Jepsen, Theodore
• Application Number:
  US16/590,338
• Publication Number:
  US 20200134308A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Some embodiments of the invention provide a data plane circuit for a network forwarding element that searches for one or more patterns of characters stored in data messages received by the data plane circuit. In some embodiments, the data plane circuit analyzes the data messages as it processes the data messages to forward the data messages to their destinations in a network. Because the data messages are already flowing through the network, it is optimal to search the data messages for the character patterns as the data messages pass through the network, instead of performing these operations on a separate set of servers that typically perform these searches at slower rates. In other embodiments, the data plane circuit does not perform its character pattern searches in conjunction with its forwarding operations, as it receives the data messages from a set of servers just for the purpose of performing its character pattern searches, in order to offload some or all of these searches from the server set.

Claims

1. A method of detecting a set of one or more character patterns stored in data messages passing through a network, the method comprising:

generating a state machine comprising (i) a plurality of states comprising partial-pattern states and at least one full-pattern state and (ii) a plurality of transitions between the states, each transition associated with a match of a set of characters in a data message and at least a portion of at least one pattern; and

providing configuration data to configure a data plane circuit of a forwarding element to implement the state machine, in order to search data messages to identify one or more character patterns in the data messages.

2. The method of claim 1, wherein the state machine transitions comprise at least one transition associated with a match of a plurality of characters in a data message with a multi-character portion of at least one pattern.

3. The method of claim 1, wherein

the data plane circuit comprises a plurality of match-action units,

the configuration data specifies a plurality of match-action pairs for the match-action units to implement,

each pair including (i) a match parameter set that includes a first state of the state machine and a set of characters, and (ii) an action parameter set that specifies a second state,

when a current state of the state machine and a processed character portion stored in a data message match the match parameter set of a particular match-action pair, the match-action unit that implements the particular match-action pair changes the current state of the state machine from the first state to the second state.

4. The method of claim 3, wherein the set of characters of each match parameter set in a group of match parameter sets of a group of match-action pairs comprises more than one character.

5. The method of claim 4, wherein for at least a subset of match parameter sets, each particular character set in at least a subset of the character sets with more than one character comprises at least one wildcard character that matches any potential character in a character portion that is being compared to the character set.

6. The method of claim 5, wherein the match-action units comprise TCAM match tables used to store match parameter sets with at least one wildcard character.

7. The method of claim 6, wherein the match-action units comprise SRAM match tables used to store match parameter sets that do not use wildcard characters.

8. The method of claim 5, wherein at least one match-action unit comprises

a TCAM match table to store match parameter sets with at least one wildcard character, and

an SRAM match table to store match parameter sets that do not use wildcard characters,

wherein when one set of characters in a data message matches match parameter sets in the TCAM and SRAM match tables, the SRAM match parameter set is identified as the matching match parameter set,

wherein when one set of characters in a data message matches a plurality of match parameter sets in the TCAM match table, the match parameter set with a highest priority in the TCAM match table is identified as the matching match parameter set.

9. The method of claim 1, wherein the data plane circuit is configured to recirculate a data message when the data plane circuit cannot check all the characters contained in the data message after having the data message traverse through one pass of the data plane circuits message processing stages.

10. The method of claim 3, wherein

each match parameter set stores its set of characters as hash values of the set of characters instead of storing the set of characters in order to reduce a size of the match parameter set;

the data plane circuit is configured to compare a plurality of characters in a data message with a set of characters of a match parameter set by generating a hash value of the plurality of characters and comparing the hash value with the hash of the set of characters that are stored in the match parameter set.

11. The method of claim 3, wherein each of a set of match-action units comprises multiple match-action unit (MAU) subsets, each of which implements a different state machine in parallel with the other MAU subsets of its match-action unit.

12. The method of claim 11 further comprising dividing the generating state machine into a plurality of state machines to be implemented by the data plane circuit in parallel.

13. The method of claim 1, wherein providing configuration data comprises providing the configuration data to a control plane circuit associated with the data plane circuit, in order for the control plane circuit to supply the configuration data to the data plane circuit.

14. The method of claim 1, wherein providing configuration data comprises forwarding he configuration data in-band to the data plane circuit.

15. A non-transitory machine readable medium storing a program for detecting a set of one or more character patterns stored in data messages passing through a network, the program for execution by at least one processing unit, the program comprising sets of instructions for:

generating a state machine comprising (i) a plurality of states comprising partial-pattern states and at least one full-pattern state and (ii) a plurality of transitions between the states, each transition associated with a match of a set of characters in a data message and at least a portion of at least one pattern; and

providing configuration data to configure a data plane circuit of a forwarding element to implement the state machine, in order to search data messages to identify one or more character patterns in the data messages.

16. The non-transitory machine readable medium of claim 15, wherein the state machine transitions comprise at least one transition associated with a match of a plurality of characters in a data message with a multi-character portion of at least one pattern.

17. The non-transitory machine readable medium of claim 15, wherein

the data plane circuit comprises a plurality of match-action units,

the configuration data specifies a plurality of match-action pairs for the match-action units to implement,

each pair including (i) a match parameter set that includes a first state of the state machine and a set of characters, and (ii) an action parameter set that specifies a second state,

when a current state of the state machine and a processed character portion stored in a data message match the match parameter set of a particular match-action pair, the match-action unit that implements the particular match-action pair changes the current state of the state machine from the first state to the second state.

18. The non-transitory machine readable medium of claim 17, wherein the set of characters of each match parameter set in a group of match parameter sets of a group of match-action pairs comprises more than one character.

19. The non-transitory machine readable medium of claim 18, wherein for at least a subset of match parameter sets, each particular character set in at least a subset of the character sets with more than one character comprises at least one wildcard character that matches any potential character in a character portion that is being compared to the character set.

20. The non-transitory machine readable medium of claim 15, wherein the data plane circuit is configured to recirculate a data message when the data plane circuit cannot check all the characters contained in the data message after having the data message traverse through one pass of the data plane circuits message processing stages.