Iterative parsing and classification

• US 8,599,859 B2
• Filed: 11/16/2010
• Issued: 12/03/2013
• Est. Priority Date: 11/16/2009
• Status: Expired due to Fees

• Current Assignee: Marvell World Trade Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell World Trade Limited (Marvell Technology Group Limited)
• Inventors: Pais, Alon, Bishara, Nafea
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): MENSAH, PRINCE AKWASI
• Application Number:
  US12/947,678
• Publication Number:
  US 20110116507A1
• Time in Patent Office: 1,113 Days
• Field of Search: 370/374, 370/392, 370/395.7, 370/395.32, 370/409, 711/108, 711/128, 711/154, 711/217, 711/220
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

Some of the embodiments of the present disclosure provide a method comprising performing, by an iterative parser and classifier engine, a first parsing and classification cycle on a data packet, based at least in part on header information of the data packet; generating a first parsing and classification result based at least in part on performing the first parsing and classification cycle; and performing a second parsing and classification cycle on the data packet, based at least in part on header information of the data packet and the first parsing and classification result. Other embodiments are also described and claimed.

Claims

1. A method comprising:

performing, by an iterative parser and classifier engine, a first parsing and classification cycle on a data packet, based at least in part on header information of the data packet;

generating a first parsing and classification result based at least in part on performing the first parsing and classification cycle;

performing a second parsing and classification cycle on the data packet, based at least in part on header information of the data packet and the first parsing and classification result;

based at least in part on performing the second parsing and classification cycle, generating a second parsing and classification result such that the second parsing and classification result includes a parsing and classification complete flag indicating whether an additional parsing and classification cycle is needed to parse and classify the data packet;

if the parsing and classification complete flag indicates an additional parsing and classification cycle is needed to parse and classify the data packet, performing a third parsing and classification cycle on the data packet, based at least in part on header information of the data packet and the second parsing and classification result; and

if the parsing and classification complete flag indicates no additional parsing and classification cycle is needed to parse and classify the data packet, outputting a classification result for the data packet.

2. The method of claim 1, wherein said performing the first parsing and classification cycle further comprises:

performing, based at least in part on a header portion of the data packet, a first look-up at a content-addressable memory (CAM);

generating a first memory address based at least in part on said performing the first look-up; and

accessing a first content from the first memory address of a memory, the first content including the first parsing and classification result.

3. The method of claim 1, wherein said outputting the classification result further comprises:

outputting the classification result based at least in part on classification information included in the second parsing and classification result.

4. The method of claim 1, wherein said outputting the classification result further comprises:

outputting the classification result that comprises information associated with one or more of a queue, a priority, and a flow identification associated with the data packet.

5. The method of claim 1,

wherein performing the first parsing and classification cycle further comprises performing the first parsing and classification cycle based at least in part on a first header portion of a header of the data packet;

wherein performing the second parsing and classification cycle further comprises performing the second parsing and classification cycle based at least in part on a second header portion of the header of the data packet, wherein the second header portion is different from the first header portion.

6. The method of claim 1, wherein performing the second parsing and classification cycle further comprises:

performing the second parsing and classification cycle based at least in part on a header offset information that is included in the first parsing and classification result.

7. A system-on-chip (SOC) comprising:

a processing core; and

an iterative parser and classifier engine (IPAC) comprising;

a packet header offset unit configured to receive a data packet and to generate, (i) during a first iterative cycle, a first header portion from a header of the data packet, and (ii) during a second iterative cycle, a second header portion,

a ternary content-addressable memory (TCAM), wherein the IPAC is configured to perform, during the first iterative cycle, a first look-up at the TCAM using the first header portion, and to generate a first memory address in response to the first look-up,

a memory, wherein the IPAC is configured to access, (i) during the first iterative cycle, a first content from the first memory address in the memory, and (ii) during the second iterative cycle, a second content from a second memory address in the memory, and

a feedback processing unit configured to (i) receive the first content from the memory and generate a first feedback and (ii) receive the second content from the memory and generate a second feedback, wherein the second feedback includes a parsing and classification complete flag indicating whether an additional iterative cycle is needed to parse and classify the data packet.

8. The SOC of claim 7, wherein the packet header offset unit is further configured to generate, during the second iterative cycle, the second header portion from the header of the data packet, based at least in part on the first feedback.

9. The SOC of claim 7, wherein the IPAC is further configured to:

generate an effective portion of the TCAM by masking a plurality of entries of the TCAM, based at least in part on the first content; and

perform the second iterative cycle by performing a second look-up at the effective portion of the TCAM using the second header portion that is generated based on the first content.

10. The SOC of claim 8, wherein the IPAC is further configured to:

perform, during the second iterative cycle, a second look-up at the TCAM using the second header portion and the first feedback; and

generate the second memory address in response to the second look-up.

11. The SOC of claim 10, wherein:

the IPAC further includes a classification unit for generating classification information of the data packet;

if the parsing and classification complete flag indicates an additional parsing and classification cycle to parse and classify the data packet, the IPAC is further configured to perform a third parsing and classification cycle on the data packet, based at least in part on a third header portion of the data packet and the second feedback; and

if the parsing and classification complete flag indicates no additional parsing and classification cycle to parse and classify the data packet, the classification unit is configured to output a classification result for the data packet based at least in part on the second content.

12. The SOC of claim 7, wherein the memory is a static random access memory (SRAM).

13. The SOC of claim 7, wherein the packet header offset unit is configured to receive the data packet from a network controller.

14. A method comprising:

receiving a data packet;

performing, using a first header portion of a header of the data packet, a first look-up at a ternary content-addressable memory (TCAM) to generate a first content based on an output of the TCAM;

performing, using a second header portion of the header of the data packet and the first content, a second look-up at the TCAM to generate a second address;

accessing a second content from the second address of the memory, the second content including a parsing and classification complete flag indicating whether an additional look-up is needed to parse and classify the data packet;

if the parsing and classification complete flag indicates an additional parsing and classification cycle to parse and classify the data packet, performing, using a third header portion of the header of the data packet and the second content, a third look-up at the TCAM to generate a third address, wherein the third header portion is generated from the header based at least in part on the second content; and

if the parsing and classification complete flag indicates no additional parsing and classification cycle to parse and classify the data packet, outputting a classification result for the data packet based at least in part on the second content.

15. The method of claim 14, wherein said performing the first look-up further comprises:

performing the first look-up to generate a first memory address; and

generating the first content by accessing the first memory address of a memory.

16. The method of claim 14, wherein:

the second header portion is based at least in part on the first content; and

the second header portion is different from the first header portion.