Multi-threaded packet processing architecture with global packet memory, packet recirculation, and coprocessor

• US 7,551,617 B2
• Filed: 02/08/2005
• Issued: 06/23/2009
• Est. Priority Date: 02/08/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Williams, John, Fingerhut, John Andrew, Eatherton, Will, Cohen, Earl T., Steiss, Donald E.
• Primary Examiner(s): LY, ANH VU H
• Application Number:
  US11/054,076
• Publication Number:
  US 20060179156A1
• Time in Patent Office: 1,596 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling

Abstract

A network processor has numerous novel features including a multi-threaded processor array, a multi-pass processing model, and Global Packet Memory (GPM) with hardware managed packet storage. These unique features allow the network processor to perform high-touch packet processing at high data rates. The packet processor can also be coded using a stack-based high-level programming language, such as C or C++. This allows quicker and higher quality porting of software features into the network processor.

Processor performance also does not severely drop off when additional processing features are added. For example, packets can be more intelligently processed by assigning processing elements to different bounded duration arrival processing tasks and variable duration main processing tasks. A recirculation path moves packets between the different arrival and main processing tasks. Other novel hardware features include a hardware architecture that efficiently intermixes co-processor operations with multi-threaded processing operations and improved cache affinity.

Claims

1. A packet processor, comprising:

an external interface to receive external packets from a network;

a recirculation interface to receive recirculated packets;

a plurality of packet processor elements each operating one or more threads;

a packet memory coupled to the external interface to store the external packets, coupled to the recirculation interface to store the recirculated packets, and coupled to the packet processing elements to enable the packet processor elements to process both the external packets and the recirculated packets;

a distributor distributing ones of the external packets in the packet memory to free ones of the threads according to a bounded time arrival processing required for the external packets, and distributing ones of the recirculated packets in the packet memory to free ones of the threads according to a variable time main processing required for the recirculated packets; and

wherein the arrival processing of the external packets by the packet processor elements is used, at least in part, to produce the recirculated packets.

2. The packet processor according to claim 1 further comprising a queuing system that receives the packets after completing each of the arrival processing and the main processing, the queuing system enabled to store the arrival-processed external packets and the main-processed recirculated packets in a plurality of sets of queues, each of the sets of queues having a respective root.

3. The packet processor according to claim 2 further comprising a recirculation path that re-circulates at least some of the packets in the queuing system back to the packet memory via the recirculation interface.

4. The packet processor according to claim 3 wherein the recirculation path re-circulates packets in the queuing system back to the packet memory for one or more additional passes through the main processing.

5. The packet processor according to claim 3 wherein the main processing partially completes packet replications for a multicast packet, and then sends the multicast packet pack through the recirculation path for another pass through the main processing to continue the packet replications.

6. The packet processor according to claim 2 wherein some of the roots are configured as recycle roots that send the packets in the associated queues back to the packet memory for the main processing by the threads.

7. The packet processor according to claim 6 further comprising, for each of the recycle roots, a respective primary distribution group associated with respective primary ones of the threads, the distributor preferentially using the primary distribution groups to distribute the recirculated packets from the recycle roots to the associated respective primary threads.

8. The packet processor according to claim 7 further comprising, for each of the recycle roots, a respective secondary distribution group associated with respective secondary ones of the threads, the distributor using the secondary distribution groups to distribute the recirculated packets from the recycle roots to the associated respective secondary threads when the associated respective primary threads are not available.

9. The packet processor according to claim 8 wherein the secondary threads overlap into more than one of the secondary distribution groups.

10. The packet processor according to claim 2 further comprising a gather mechanism enabled to gather processed ones of the packets in the packet memory to send to the queuing system while the threads that previously processed the packets are processing new packets.

11. A packet processor, comprising:

an array of packet processing elements, each enabled to operate one or more threads;

a memory system including packet memory to store packets and a packet handle data structure having a plurality of entries, each of the packets in the packet memory associated with a respective one of the packet handle data structure entries;

a distributor coupled to the memory system, the distributor enabled to assign to the threads ones of the packets in the memory system to be processed;

a gather mechanism coupled to the memory system and enabled to use the respective packet handle data structure entries of processed ones of the packets to independently gather and assemble the processed packets to output from the packet memory; and

wherein a first one of the packets associated with a first one of the packet handle data structure entries is assigned to a particular one of the threads by the distributor, the particular thread completes the processing of the first packet, and a second one of the packets associated with a second one of the packet handle data structure entries is assigned to the particular thread by the distributor prior to the gather mechanism using the first packet handle data structure entry to gather the first packet.

12. The packet processor according to claim 11 wherein the distributor assigns the packets to the threads according to a respective type of relatively bounded arrival processing time or variable main processing time required for the packets.

13. The packet processor according to claim 11 wherein the gather mechanism gathers and assembles the processed packets to output to a queuing system.

14. The packet processor according to claim 11 further comprising a queuing system that comprises queues to store the processed packets and a recirculation path that re-circulates queued ones of the processed packets back to the memory system for additional processing by the threads.

15. The packet processor according to claim 14 wherein the queuing system further comprises associated roots of the queues, some of the roots configured to send the queued processed packets back to the memory system over the recirculation path.

16. A packet processor, comprising:

a plurality of packet processing elements to process packets;

a queuing system to store the packets after being processed by the packet processing elements;

a distributor enabled to allocate packets to free ones of the packet processing elements received both from one or more external ports and recirculated via the queuing system;

wherein each of the packet processing elements is enabled to be notified by the distributor after the distributor has allocated one of the packets to the packet processing element;

wherein a particular one of the packet processing elements is enabled to process both ones of the packets received from the external ports and ones of the packets recirculated via the queuing system; and

wherein the queuing system comprises roots and associated queues that store the packets, some of the roots configured as recycle roots that send the packets in the associated queues back to the distributor for reallocation to the packet processing systems.

17. The packet processor according to claim 16 wherein the distributor allocates the packets received from the external ports to ones of the packet processing elements providing arrival processing, and allocates the packets recirculated via the queuing system to ones of the packet processing elements providing main processing.

18. The packet processor according to claim 17 further comprising a recirculation path that recirculates packets in the queuing system back to the distributor to be reallocated to the packet processing elements after completing the arrival processing or the main processing.

19. The packet processor according to claim 17 wherein the arrival processing has a relatively bounded processing time in the packet processing elements, and the main processing has a variable processing time in the packet processing elements.