Packet scheduling in a network processor

• US 9,397,938 B2
• Filed: 02/28/2014
• Issued: 07/19/2016
• Est. Priority Date: 02/28/2014
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Folsom, Brian Robert, Tompkins, Joseph B., Snyder, Wilson P. II, Kessler, Richard E., Langevin, Edwin, Jones, Andrew J., Robbins, Ethan F.
• Primary Examiner(s): SWEET, LONNIE V
• Application Number:
  US14/193,933
• Publication Number:
  US 20150249604A1
• Time in Patent Office: 872 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A circuit operates to manage transmittal of packets in a network packet processor. The circuit includes a packet descriptor manager (PDM), a packet scheduling engine (PSE), and a packet engines and buffering module (PEB). The PDM generates a metapacket and a descriptor from a command signal, where the command signal identifies a packet to be transmitted by the circuit. The PSE models the packet through a model of the network topology, determining an order in which to transmit the packet among a number of packets based on the modeling. Once the packet is scheduled for transmission, the PEB performs processing operations on the packet to produce a processed packet based on instructions indicated in the descriptor. The PEB then causes the processed packet to be transmitted toward the destination.

Claims

1. A circuit for managing transmittal of packets, the circuit comprising:

a packet descriptor manager (PDM) circuit module configured to generate a metapacket from a command signal, the metapacket indicating a size and a destination of a packet to be transmitted by the circuit;

a packet scheduling engine (PSE) circuit module configured to model transmission of the packet through a model of a network topology from the destination to the circuit, the model of the network topology including simulated instances of a plurality of nodes in the network topology between the destination and the circuit and connections between the plurality of nodes, the modeling being based on information indicated by the metapacket, the PSE determining an order in which to transmit the packet among a plurality of packets based on the model transmission; and

a packet engines and buffering (PEB) circuit module configured to process the packet and cause the processed packet to be transmitted toward the destination according to the order determined by the PSE.

2. The circuit of claim 1, wherein the PSE is further configured to model the plurality of nodes in the network topology between the destination and the circuit.

3. The circuit of claim 2, wherein the PSE is further configured to model a network shaper at each of the nodes, each of the network shapers defining at least one of a peak rate and a committed rate.

4. The circuit of claim 3, wherein the PSE is further configured to apply a model of the packet to each of the network shapers in a path between the circuit and the destination, the PSE determining the order based on the application.

5. The circuit of claim 1, wherein the PSE is further configured to determine the order based on arrival of the packet relative to other packets at the circuit in the model transmission.

6. The circuit of claim 5, wherein the PSE is further configured to model transmission of the plurality of packets from a plurality of respective destinations to the circuit, the PSE determining the order based arrival of the packet among the plurality of packets in the model transmission.

7. The circuit of claim 6, wherein the PSE is further configured to model a plurality of nodes in the network topology between the plurality of destinations and the circuit.

8. The circuit of claim 7, wherein the PSE is further configured to assign relative priority to each of the inputs of the model plurality of nodes.

9. The circuit of claim 7, wherein the PSE is further configured to model transmission of the plurality of packets through the model plurality of nodes based on a deficit-weighted round robin calculation.

10. The circuit of claim 1, wherein the PSE is further configured to determine the order based on a credit count associated with the packet, the credit count indicating a capacity of a transmission buffer to receive the packet.

11. A method of managing transmittal of packets, the method comprising:

receiving a command signal identifying a packet to be processed and transmitted;

generating a metapacket from the command signal, the metapacket including an indication of a size of the packet and a destination of the packet;

modeling, at a packet scheduling engine (PSE) circuit module, transmission of the packet through a model of a network topology from the destination to the circuit, the model of the network topology including simulated instances of a plurality of nodes in the network topology between the destination and the circuit and connections between the plurality of nodes, the modeling being based on information indicated by the metapacket;

determining an order in which to transmit the packet among a plurality of packets based on the model transmission;

processing operations on the packet to produce a processed packet; and

causing the processed packet to be transmitted toward the destination according to the order.

12. The method of claim 11, further comprising modeling the plurality of nodes in the network topology between the destination and the circuit.

13. The method of claim 12, further comprising modeling a network shaper at each of the nodes, each of the network shapers defining at least one of a peak rate and a committed rate.

14. The method of claim 13, further comprising applying a model of the packet to each of the network shapers in a path between the circuit and the destination, the PSE determining the order based on the application.

15. The method of claim 11, further comprising determine the order based on arrival of the packet relative to other packets at the circuit in the model transmission.

16. The method of claim 15, further comprising modeling transmission of the plurality of packets from a plurality of respective destinations to the circuit, the determining the order being based arrival of the packet among the plurality of packets in the model transmission.

17. The method of claim 16, further comprising modeling a plurality of nodes in the network topology between the plurality of destinations and the circuit.

18. The method of claim 17, further comprising assigning relative priority to each of the inputs of the model plurality of nodes.

19. The method of claim 17, further comprising modeling transmission of the plurality of packets through the model plurality of nodes based on a deficit-weighted round robin calculation.

20. The method of claim 11, further comprising determining the order based on a credit count associated with the packet, the credit count indicating a capacity of a transmission buffer to receive the packet.