METHOD FOR PROVIDING A PARSER TO EXTRACT INFORMATION FROM FIELDS OF A DATA PACKET HEADER

• US 20140307736A1
• Filed: 04/16/2013
• Published: 10/16/2014
• Est. Priority Date: 04/16/2013
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Geoffrey Lefebvre, Suresh Krishnan
• Inventors: KRISHNAN, Suresh, LEFEBVRE, Geoffrey
• Granted Patent: US 9,848,068 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method for providing a parser by a network node, which includes a table defining a plurality of rules and a plurality of match fields required for extraction from an incoming data packet header in order to apply each of the respective rules is described. The method comprises determining at least one occurrence in the table of a first match field that requires extraction; and determining a parser for use in accordance with the at least one determined occurrence of the first match field. Furthermore, the step of determining at least one occurrence of the first match field comprises initializing a counter associated with the first match field and incrementing the counter for each of the plurality of rules that requires extraction of the first match field. And the step of determining a parser comprises determining the parser for use in accordance with the counter. A network node for carrying this method is also described.

Claims

1. A method for providing a parser by a network node that includes a table defining a plurality of rules and a plurality of match fields required for extraction from an incoming data packet header in order to apply each of the respective rules, the method comprising:

determining at least one occurrence in the table of a first match field that requires extraction; and

determining a parser for use in accordance with the at least one determined occurrence of the first match field.

2. The method of claim 1, wherein determining at least one occurrence of a first match field comprises:

initializing a counter associated with the first match field; and

incrementing the counter for each of the plurality of rules that requires extraction of the first match field.

3. The method of claim 2, wherein determining a parser for use in accordance with the at least one determined occurrence of the first match field comprises determining the parser for use in accordance with the counter.

4. The method of claim 3, further comprising:

initializing a plurality of counters, each counter associated with a respective one of the plurality of match fields;

incrementing each of the plurality of counters for each of the plurality of rules that requires extraction of each of the respective match fields; and

determining the parser for use in accordance with the plurality of counters.

5. The method of claim 4, further comprising building a reference table associated with the table, the reference table having a first row corresponding to the plurality of match fields and a second row corresponding to the plurality of counters.

6. The method of claim 4, wherein the determined parser only extracts, from the incoming data packet header, match fields whose associated counters have a count different than an initial value.

7. The method of claim 4, wherein determining the parser comprises generating the parser.

8. The method of claim 4, wherein determining the parser comprises selecting the parser among a set of predefined parsers.

9. The method of claim 7, wherein generating the parser comprises:

using a register of bits, each bit corresponding to a match field;

setting each of the bits for a corresponding match field whose associated counter has a count different than an initial value; and

generating the parser according to the set bits of the register.

10. The method of claim 8, wherein selecting the parser among a set of predefined parsers comprises:

using a register of bits, each bit corresponding to a match field;

setting each of the bits for a corresponding match field whose associated counter has a count different than an initial value; and

selecting the parser corresponding to the set bits among the set of predefined parsers, wherein the set of predefined parser is given by a plurality of possibilities of configuration of bit setting of the register of bits.

11. The method of claim 10, wherein selecting the parser among the set of predefined parsers comprises using a table, which includes the plurality of possibilities of configuration of bit setting of the register of bits and a key to point to the configuration of bit setting corresponding to the selected parser.

12. The method of claim 4, further comprising updating the plurality of counters in response to one of an addition of a new rule to the table and a removal of a rule from the table.

13. The method of claim 12, wherein updating the plurality of counters in response to an addition of the new rule comprises incrementing each of the plurality of counters associated with the match fields that require extraction based on the new rule.

14. The method of claim 12, wherein updating the plurality of counters in response to a removal of the rule comprises decrementing each of the plurality of counters associated with the match fields that require extraction based on the removed rule.

15. The method of claim 12, further comprising determining a new parser based on the plurality of updated counters.

16. The method of claim 15, wherein determining a new parser comprises determining a change in states of at least one counter.

17. The method of claim 16, wherein determining a change in states comprises one of a count of the at least one counter going from an initial value to a value different than the initial value and a count of the at least one counter going from a value different than an initial value to the initial value.

18. The method of claim 16, wherein determining a new parser comprises:

using a register of bits, each bit corresponding to a match field;

updating the register of bits by performing one of setting and clearing a bit for a corresponding match field whose associated count has changed in states; and

determining the new parser in accordance with the updated register of bits.

34. The method of claim 1, further comprising, responsive to the determination of the at least one occurrence of the first match field, using the determined parser to read the first match field from the incoming data packet.

19. A network node for providing a parser, the network node including a table defining a plurality of rules and a plurality of match fields required for extraction from an incoming data packet header in order to apply each of the respective rules, the network node comprising:

a detector for determining at least one occurrence in the table of a first match field that requires extraction; and

a processor associated with the detector for determining a parser for use in accordance with the at least one determined occurrence of the first match field.

20. The network node of claim 19, wherein the detector comprises an initialized counter associated with the first match field;

and wherein the processor is further associated with the counter for incrementing the counter for each of the plurality of rules that requires extraction of the first match field and for determining a parser for use in accordance with the counter.

21. The network node of claim 20, wherein the detector further comprises a plurality of initialized counters, each counter associated with a respective one of the plurality of match fields, wherein the first processor is further associated with the plurality of counters for incrementing each of the plurality of counters for each of the plurality of rules that requires extraction of each of the respective match fields, and for determining the parser for use in accordance with the plurality of counters.

22. The network node of claim 21, wherein the processor further builds a reference table associated with the table, the reference table having a first row corresponding to the plurality of match fields and a second row corresponding to the plurality of counters.

23. The network node of claim 20, wherein the determined parser only extracts, from the incoming data packet header, match fields whose associated counters have a count different than an initial value.

24. The network node of claim 22, further comprising a register of bits, each bit corresponding to a match field and wherein the processor is further configured to set each of the bits for a corresponding match field whose associated counter has a count different than an initial value and to generate the parser for use in accordance with the set bits of the register.

25. The network node of claim 22, further comprising:

a register of bits, each bit corresponding to a match field; and

a set of predefined parsers, corresponding to a plurality of possibilities of configuration of bit setting of the register of bits;

wherein the processor is further configured to set each of the bits for a corresponding match field whose associated counter has a count different than an initial value and to select the parser for use corresponding to the set bits among the set of predefined parsers.

26. The network node of claim 25, wherein the processor selects the parser for use among the set of predefined parsers using a table and a key to point to the parser corresponding to the selected parser.

27. The network node of claim 22, wherein the processor updates the plurality of counters in response to one of an addition of a new rule to the table and a removal of a rule from the table.

28. The network node of claim 27, wherein the processor updates the plurality of counters in response to an addition of the new rule by incrementing each of the plurality of counters associated with the match fields that require extraction based on the new rule.

29. The network node of claim 27, wherein the processor updates the plurality of counters in response to a removal of the rule by decrementing each of the plurality of counters associated with the match fields that require extraction based on the removed rule.

30. The network node of claim 27, wherein the processor determines a new parser based on the plurality of updated counters.

31. The network node of claim 30, wherein the processor further determines a change in states of at least one counter.

32. The network node of claim 31, wherein the processor determines a change in states by determining one of a count of the at least one counter going from an initial value to a value different than the initial value and a count of the at least one counter going from a value different than an initial value to the initial value.

33. The network node of claim 32, wherein the processor further updates a register of bits, each bit corresponding to a match field, by performing one of setting and clearing a bit for a corresponding match field whose associated count has changed in states and determines the new parser in accordance with the updated register of bits.