Network Processors and Pipeline Optimization Methods

• US 20080112415A1
• Filed: 11/07/2007
• Published: 05/15/2008
• Est. Priority Date: 11/09/2006
• Status: Active Grant

• Current Assignee: Justin Mark Sobaje
• Original Assignee: Justin Mark Sobaje
• Inventors: Sobaje, Justin Mark
• Granted Patent: US 8,179,896 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A network processor of an embodiment includes a packet classification engine, a processing pipeline, and a controller. The packet classification engine allows for classifying each of a plurality of packets according to packet type. The processing pipeline has a plurality of stages for processing each of the plurality of packets in a pipelined manner, where each stage includes one or more processors. The controller allows for providing the plurality of packets to the processing pipeline in an order that is based at least partially on: (i) packet types of the plurality of packets as classified by the packet classification engine and (ii) estimates of processing times for processing packets of the packet types at each stage of the plurality of stages of the processing pipeline. A method in a network processor allows for prefetching instructions into a cache for processing a packet based on a packet type of the packet.

Claims

1. A network processor, comprising:

a packet classification engine for classifying each of a plurality of packets according to packet type;

a processing pipeline having a plurality of stages for processing each of the plurality of packets in a pipelined manner, each stage of the plurality of stages including one or more processors; and

a controller for providing the plurality of packets to the processing pipeline in an order that is based at least partially on (i) packet types of the plurality of packets as classified by the packet classification engine and (ii) estimates of processing times for processing packets of the packet types at each stage of the plurality of stages of the processing pipeline.

2. The network processor of claim 1,

wherein a processor of the one or more processors of a first stage of the plurality of stages is a different type of processor than a processor of the one or more processors of a second stage of the plurality of stages.

3. The network processor of claim 1, further comprising:

a plurality of queues, each queue of the plurality of queues for storing packets of a corresponding packet type, said plurality of queues configured to store said plurality of packets;

said controller configured to access said plurality of queues in accordance with said order to provide the plurality of packets to the processing pipeline.

4. The network processor of claim 1,

wherein each packet of the plurality of packets includes a packet header and payload data.

5. The network processor of claim 1,

said network processor located in at least one of a router and a switch.

6. The network processor of claim 1,

said packet classification engine configured to receive the plurality of packets from an Ethernet connection.

7. A method in a network processor, comprising:

classifying each packet of a plurality of packets into a corresponding packet type of a plurality of packet types;

determining an order of processing the plurality of packets in a processing pipeline based at least partially on (i) the corresponding packet type of each packet of the plurality of packets and (ii) estimates of processing times for processing packets of the plurality of packet types at each stage of a plurality of stages of the processing pipeline; and

providing the plurality of packets to the processing pipeline in said order.

8. The method of claim 7, said classifying comprising:

classifying each packet of the plurality of packets into the corresponding packet type of the plurality of packet types based on at least one of header data of the packet and payload data of the packet.

9. The method of claim 7, further comprising:

processing a packet of a packet type by a processor of a stage of the plurality of stages;

prefetching, into a particular cache, instructions for processing packets of said packet type while said processor is processing said packet; and

obtaining said instructions from said particular cache to process said packet by a particular processor of a particular stage of the plurality of stages, said particular stage located after said stage in said processing pipeline.

10. The method of claim 7, further comprising:

obtaining said estimates of processing times for processing packets of the plurality of packet types at each stage of the plurality of stages through experiments in which packets of the plurality of packet types are processed by the processing pipeline.

11. A method in a network processor, the network processor including a processing pipeline having a plurality of stages, the method comprising:

receiving a plurality of packets into the network processor in a first order;

classifying each packet of the plurality of packets into a corresponding packet type of a plurality of packet types;

determining a second order in which to provide the plurality of packets to the processing pipeline based at least partially on the corresponding packet type of each packet of the plurality of packets; and

providing the plurality of packets to the processing pipeline in said second order.

12. The method of claim 11, said determining comprising:

determining the second order in which to provide the plurality of packets to the processing pipeline based at least partially on (i) the corresponding packet type of each packet of the plurality of packets and (ii) estimates of processing times for processing packets of the plurality of packet types at each stage of the plurality of stages of the processing pipeline.

13. The method of claim 11, further comprising:

processing a packet of a packet type by a processor of a stage of the plurality of stages;

prefetching, into a particular cache, instructions for processing packets of said packet type while said processor is processing said packet; and

obtaining said instructions from said particular cache to process said packet by a particular processor of a particular stage of the plurality of stages, said particular stage located after said stage in said processing pipeline.

14. The method of claim 11, said receiving comprising:

receiving the plurality of packets from one or more Ethernet links.

15. A method in a network processor, said network processor including a processing pipeline having a plurality of stages, said method comprising:

processing a packet of a packet type by a processor of a stage of the plurality of stages;

prefetching, into a particular cache, instructions for processing packets of said packet type while said processor is processing said packet; and

obtaining said instructions from said particular cache to process said packet by a particular processor of a particular stage of the plurality of stages, said particular stage located after said stage in said processing pipeline.

16. The method of claim 15, said processing comprising:

performing table look-ups required for at least one of switching, routing, session switching, content switching, and policy enforcement related to the packet.

17. The method of claim 15, said processing comprising:

assigning the packet to an output port of a plurality of output ports.

18. The method of claim 15,

said prefetching occurring while said particular processor is idle.

19. A method in one or more computers, the method comprising:

obtaining information, for each packet type of a plurality of packet types and for each processor design of a plurality of processor designs for each stage of a plurality of stages of a processing pipeline, including a corresponding estimate of processing time for processing a packet of the packet type by a processor of the processor design;

specifying a linear program based on said information, said linear program including a corresponding binary variable for each processor design of the plurality of processor designs for each stage of the plurality of stages of the processing pipeline;

solving said linear program to assign a corresponding value to the corresponding binary variable for each processor design of the plurality of processor designs for each stage of the plurality of stages of the processing pipeline; and

outputting design information relating to processor designs of the plurality of processor designs to be used for a network processor based on the corresponding value of the corresponding binary variable for each processor design of the plurality of processor designs for each stage of the plurality of stages of the processing pipeline.

20. The method of claim 19, further comprising:

constructing a network processor in accordance with said design information.