Multi-stage multi-core processing of network packets

• US 8,094,560 B2
• Filed: 05/19/2008
• Issued: 01/10/2012
• Est. Priority Date: 05/19/2008
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bagepalli, Nagaraj, Patra, Abhijit
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): SHIVERS, ASHLEY L
• Application Number:
  US12/123,223
• Publication Number:
  US 20090285228A1
• Time in Patent Office: 1,331 Days
• Field of Search: None
• US Class Current: 370/235
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

Techniques for multi-stage multi-core processing of network packets are described herein. In one embodiment, work units are received within a network element, each work unit representing a packet of different flows to be processed in multiple processing stages. Each work unit is identified by a work unit identifier that uniquely identifies a flow in which the associated packet belongs and a processing stage that the associated packet is to be processed. The work units are then dispatched to multiple core logic, such that packets of different flows can be processed concurrently by multiple core logic and packets of an identical flow in different processing stages can be processed concurrently by multiple core logic, in order to determine whether the packets should be transmitted to one or more application servers of a datacenter. Other methods and apparatuses are also described.

Claims

1. A method comprising:

receiving a plurality of network packets at a network element;

categorizing the network packets into a plurality of work units by a packet order work (POW) unit in the network element, each work unit representing a packet of different transport control protocol (TCP) flows to be processed in multiple processing stages in the network element, wherein each of the plurality of work units is identified by an identifier that uniquely identifies a flow in which the associated packet belongs and a processing stage that the associated packet is to be processed;

determining a group value for each of the plurality of work units, wherein the group value identifies one of a plurality of core logic in the network element for a specific processing event corresponding to a particular one of the multiple processing stages and allows the POW unit or a multi-core scheduling (MCS) unit in the network element to schedule processing of each of the work units to one of the plurality of core logic based on the specific processing event identified by the group value;

scheduling processing at the MCS unit of each of the plurality of work units based on a stage scheduling model and a flow scheduling model, wherein the stage scheduling model divides the work units into different processing stages and wherein the flow scheduling model divides the work units into different TCP flows; and

dispatching each of the work units to the one of the plurality of core logic of the network element for processing, such that work units of the network packets of different TCP flows are processed concurrently by multiple core logic and work units of the network packets of identical TCP flows in different processing stages are processed concurrently by multiple core logic, in order to determine whether the packets should be transmitted to one or more application servers of a datacenter.

2. The method of claim 1, wherein receiving comprises receiving the network packets with the network element operating as an application service gateway for the datacenter, and further comprising providing access for a client through the network element to a plurality of application servers of the datacenter that are configured to process the work units associated with the packets.

3. The method of claim 2, wherein and further comprising performing at least one of layer 5 to layer 7 services on the work units within the network element.

4. The method of claim 1, wherein categorizing comprises categorizing the network packets into work units such that the identifier for each of the work units is generated based on at least a portion of content of the packet.

5. The method of claim 4, further comprising generating the identifier for each of the work units that comprises a flow hash value representing the TCP flow associated with the packet and a stage identifier identifying a next processing stage that the packet should be processed.

6. The method of claim 5, further comprising performing a hash function on at least one of a source Internet Protocol (IP) address, destination IP address, source TCP port, destination TCP port, and protocol of the packet, in order to generate the flow hash value of the identifier.

7. The method of claim 1, further comprising for each processing stage, initializing a respective processing stage, including providing a callback function which is invoked when a work unit of the respective processing stage has been processed.

8. The method of claim 7, further comprising:

receiving a callback within a callback function of a current processing stage indicating that a particular work unit has been completely processed within the current processing stage;

modifying one or more data members of a tag data structure to indicate a next processing stage in which the particular work unit should be processed, wherein the tag data structure is passed from a caller of the callback; and

scheduling the work unit with the modified tag data structure such that the working unit can be processed in the next processing stage specified by the modified tag data structure.

9. The method of claim 1, further comprising storing any unprocessed work units in a work unit queue to be processed in a subsequent processing stage.

10. The method of claim 1, wherein categorizing the network packets into the plurality of work units comprises categorizing the network packets into the work units, wherein the work units identify processing events to be performed on the packets, and wherein determining the tag value comprises determining a multiple bit tag value that uniquely identifies a processing event.

11. The method of claim 10, further comprising:

determining a tag value and a tag type for each of the plurality of work units, wherein the tag value and tag type allow the POW unit or MCS unit to determine an order in which to process each of the plurality of work units, wherein the tag type of the work unit comprises one of an ordered tag type, atomic tag type or null tag type; and

determining a group value that represents one of the plurality of core logic which is configured to process the processing event indicated by the tag value of the work unit.

12. The method of claim 11, further comprising scheduling the processing events of the work units of the network packets in the order in which the network packets are received when the tag type is an ordered tag type and such that only one of the plurality of core logic processes only one work unit at a time when the tag type is an atomic tag type.

13. A non-transitory machine-readable storage medium having instructions stored therein which when executed by a processor, cause the processor to:

receive a plurality of network packets at a network element;

categorize the network packets into a plurality of work units in the network element, each work unit representing a packet of different transport control protocol (TCP) flows to be processed in multiple processing stages in the network element, wherein each of the plurality of work units is identified by an identifier that uniquely identifies a flow in which the associated packet belongs and a processing stage that the associated packet is to be processed;

determine a group value for each of the plurality of work units, wherein the group value identifies one of a plurality of core logic in the network element for a specific processing event corresponding to a particular one of the multiple processing stages and allows a packet order work (POW) unit or a multi-core scheduling (MCS) unit in the network element to schedule processing of each of the work units to the plurality of core logic based on the specific processing event identified by the group value;

schedule processing of each of the plurality of work units based on a stage scheduling model and a flow scheduling model, wherein the stage scheduling model divides the work units into different processing stages and wherein the flow scheduling model divides the work units into different TCP flows; and

dispatch each of the work units to one of the plurality of core logic of the network element for processing, such that work units of the network packets of different TCP flows are processed concurrently by multiple core logic and work units of the network packets of identical TCP flows with different processing stages are processed concurrently by multiple core logic, in order to determine whether the packets should be transmitted to one or more application servers of a datacenter.

14. The machine-readable storage medium of claim 13, wherein the instructions that cause the processor to receive the plurality of work units comprise instructions that cause the processor to receive the network packets with the network element operating as an application service gateway for the datacenter, and further comprises instructions that causes the processor to provide access for a client through the network element to a plurality of application servers of the datacenter that are configured to process the work units associated with the packets.

15. The machine-readable storage medium of claim 14, and further comprising instructions that cause the processor to perform at least one of layer 5 to layer 7 services on the work units within the network element.

16. The machine-readable storage medium of claim 13, wherein the instructions that cause the processor to categorize the network packets comprise instructions that cause the processor to categorize the network packets into work units such that the identifier for each of the work units is generated based on at least a portion of content of the packet.

17. The machine-readable storage medium of claim 16, further comprising instructions that cause the processor to generate the identifier for each of the work units that comprises a flow hash value representing the TCP flow associated with the packet and a stage identifier identifying a next processing stage that the packet should be processed.

18. The machine-readable storage medium of claim 17, further comprising instructions that cause the processor to perform a hash function on at least one of a source Internet Protocol (IP) address, destination IP address, source TCP port, destination TCP port, and protocol of the packet, in order to generate the flow hash value of the identifier.

19. The machine-readable storage medium of claim 13, further comprising instructions that cause the processor to initialize a respective processing stage, including providing a callback function which is invoked when a work unit of the respective processing stage has been processed.

20. The machine-readable storage medium of claim 19, further comprising instructions that cause the processor to:

receive a callback within a callback function of a current processing stage indicating that a particular work unit has been completely processed within the current processing stage;

modify one or more data members of a tag data structure to indicate a next processing stage in which the particular work unit should be processed, wherein the tag data structure is passed from a caller of the callback; and

schedule the work unit with the modified tag data structure such that the working unit can be processed in the next processing stage specified by the modified tag data structure.

21. A network device, comprising:

a plurality of core logic;

a packet order work (POW) unit that is configured to categorize network packets into a plurality of work units, each work unit representing a packet of different transport control protocol (TCP) flows to be processed in multiple processing stages in the network element, wherein each of the plurality of work units is identified by an identifier that uniquely identifies a flow in which the associated packet belongs and a processing stage that the associated packet is to be processed;

a work unit queue configured to receive and store the plurality of work units; and

a multi-core scheduling (MCS) unit coupled to the work unit queue that is configured to;

schedule processing of each of the plurality of work units based on a stage scheduling model and a flow scheduling model, wherein the stage scheduling model divides the work units into different processing stages and wherein the flow scheduling model divides the work units into different TCP flows, and

dispatch each of the work units to one of the plurality of core logic based on a specific processing event identified by a group value of each of the work units that identifies one of a plurality of core logic for the specific processing event corresponding to a particular one of the multiple processing stages for the work units, such that work units of the network packets of different TCP flows are processed concurrently by multiple core logic and work units of the network packets of identical TCP flows with different processing stages are processed concurrently by multiple core logic, in order to determine whether the packets should be transmitted to one or more application servers of a datacenter.

22. The network device of claim 21, wherein the network device operates as an application service gateway for the datacenter and is configured to provide access for a client to a plurality of application servers of the datacenter that are configured to process the work units.

23. The network device of claim 22, wherein the MCS unit is further configured to perform at least one of layer 5 to layer 7 services on the work units.

24. The network device of claim 21, wherein the POW unit is configured to generate the identifier for each of the work units of the network packets based on at least a portion of content of the packet.

25. The network device of claim 24, wherein the identifier for the work unit comprises a flow hash value representing the TCP flow associated with the packet and a stage identifier identifying a next processing stage that the packet should be processed.

26. The network device of claim 25, wherein the MCS unit is configured to perform a hash function on at least one of a source Internet Protocol (IP) address, destination IP address, source TCP port, destination TCP port, and protocol of the packet, in order to generate the flow hash value of the identifier.