US 8,619,787 B2 · Byte-accurate scheduling in a network processor

Abstract

Described embodiments provide for scheduling packets for transmission by a network processor. A traffic manager generates a tree scheduling hierarchy having a root scheduler and N scheduler levels. The network processor generates tasks corresponding to received packets. The traffic manager enqueues the received task in the associated queue, the queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler. Each scheduler determines one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task. The corresponding packet data is read from a shared memory, and, at each corresponding parent scheduler up to the root scheduler, an actual size of the packet data is updated. Scheduling weights of each corresponding parent scheduler are updated based on the actual size of the packet data.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims23

Dependent claims

A method of scheduling packets for transmission by a network processor having a plurality of processing modules and at least one shared memory with packet data, the method comprising:

generating, by a traffic manager of the network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N is a positive integer;
generating, by the network processor, one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows of the network processor;
enqueuing, by the traffic manager, a task provided by one of the plurality of processing modules of the network processor to an associated queue of the scheduling hierarchy, the queue associated with a data flow of the received task, each queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler;
determining, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
reading the corresponding packet data from the at least one shared memory;
updating, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
updating one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein the one or more corresponding scheduling weights comprise (i) an arbitration bucket value, wherein the arbitration bucket value corresponds to a weight of the corresponding node of the scheduling hierarchy, and (ii) a traffic shaping value, wherein the traffic shaping value corresponds to a desired data rate of the corresponding node of the scheduling hierarchy;
determining, based on the arbitration bucket value, a frequency of selecting the corresponding node for scheduling;
and
temporarily removing, based on the traffic shaping value, the corresponding node from the scheduling hierarchy, thereby making the node unavailable for scheduling and enforcing a data rate limit on the corresponding node.

7 more elements

A non-transitory machine-readable storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of scheduling packets for transmission by a network processor having a plurality of processing modules and at least one shared memory with packet data, the method comprising:

generating, by a traffic manager of the network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N is a positive integer;
generating, by the network processor, one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows of the network processor;
enqueuing, by the traffic manager, a task provided by one of the plurality of processing modules of the network processor to an associated queue of the scheduling hierarchy, the queue associated with a data flow of the received task, each queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler;
determining, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
reading the corresponding packet data from the at least one shared memory;
updating, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
updating one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein the one or more corresponding scheduling weights comprise (i) an arbitration bucket value, wherein the arbitration bucket value corresponds to a weight of the corresponding node of the scheduling hierarchy, and (ii) a traffic shaping value, wherein the traffic shaping value corresponds to a desired data rate of the corresponding node of the scheduling hierarchy;
determining, based on the arbitration bucket value, a frequency of selecting the corresponding node for scheduling;
and
temporarily removing, based on the traffic shaping value, the corresponding node from the scheduling hierarchy, thereby making the node unavailable for scheduling and enforcing a data rate limn on the corresponding node.

7 more elements

A network processor comprising:

a plurality of processing modules and at least one shared memory with packet data, wherein one of the plurality of processing modules is configured to generate one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows;
a traffic manager of the network processor configured to:
receive a task corresponding to a data flow, the task provided by one of the plurality of processing modules of the network processor;
generate a scheduling hierarchy comprising of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N a positive integer;
enqueue each received task in a queue of the scheduling hierarchy associated with the received task, the queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to a root scheduler of the scheduling hierarchy, wherein the queue and one or more corresponding parent schedulers at each level of the scheduling hierarchy form a branch of the scheduling hierarchy;
determine, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
read the corresponding packet data from the at least one shared memory;
update, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
update one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein the one or more corresponding scheduling weights comprise (i) an arbitration bucket value, wherein the arbitration bucket value corresponds to a weight of the corresponding node of the scheduling hierarchy, and (ii) a traffic shaping value, wherein the traffic shaping value corresponds to a desired data rate of the corresponding node of the scheduling hierarchy;
determine, based on the arbitration bucket value, a frequency of selecting the corresponding node for scheduling;
and
temporarily remove, based on the traffic shaping value, the corresponding node from the scheduling hierarchy, thereby making the node unavailable for scheduling and enforcing a data rate limit on the corresponding node.

9 more elements

A method of scheduling packets thy transmission by a network processor having a plurality of processing modules and at least one shared memory with packet data, the method comprising:

generating, by a traffic manager of the network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N is a positive integer;
generating, by the network processor, one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows of the network processor;
enqueuing, by the traffic manager, as task provided by one of the plurality of processing modules of the network processor to an associated queue of the scheduling hierarchy, the queue associated with a data flow of the received task, each queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler;
determining, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
reading the corresponding packet data from the at least one shared memory;
updating, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
updating one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein the step of updating comprises:
sending a task update message from the corresponding queue to the corresponding parent scheduler at the next level of the hierarchy;
and
iteratively, for each scheduling level up to the root scheduler, sending a task update message from each corresponding parent scheduler at each level of the scheduling hierarchy, wherein the task update message comprises a first packet size correction field and a second packet size correction field;
updating, based on the first packet size correction field, the packet size at each level of the scheduling hierarchy;
and
indicating, based on the second packet size correction field, a protocol of the given packet.

10 more elements

generating, by a traffic manager of the network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N a positive integer;
generating, by the network processor, one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows of the network processor;
enqueuing, by the traffic manager, a task provided by one of the plurality of processing modules of the network processor to an associated queue of the scheduling hierarchy, the queue associated with a data flow of the received task, each queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler;
determining, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
reading the corresponding packet data from the at least one shared memory;
updating, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
updating one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein the step of updating comprises:
sending a task update message from the corresponding queue to the corresponding parent scheduler at the next level of the hierarchy;
and
iteratively, for each scheduling level up to the root scheduler, sending a task update message from each corresponding parent scheduler at each level of the scheduling hierarchy, wherein the task update message comprises a first packet size correction field and a second packet size correction field;
updating, based on the first packet size correction field, the packet size at each level of the scheduling hierarchy;
and
indicating, based on the second packet size correction field, a protocol of the given packet.

10 more elements

A network processor comprising:

a plurality of processing modules and at least one shared memory with packet data, wherein one of the plurality of processing modules is configured to generate one or more tasks corresponding to each of a plurality of received packets associated with one or more data flows;
a traffic manager of the network processor configured to:
receive a task corresponding to a data flow, the task provided by one of the plurality of processing modules of the network processor;
generate a scheduling hierarchy comprising of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N a positive integer;
enqueue each received task in a queue of the scheduling hierarchy associated with the received task, the queue having a corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to a root scheduler of the scheduling hierarchy, wherein the queue and one or more corresponding parent schedulers at each level of the scheduling hierarchy form a branch of the scheduling hierarchy;
determine, by each of the one or more corresponding parent schedulers and root scheduler, one or more tasks to schedule from a given queue based on a default packet size of the packet corresponding to the task;
read the corresponding packet data from the at least one shared memory;
update, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, an actual size of the packet data;
update one or more corresponding scheduling weights of each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler based on the actual size of the packet data, wherein, at each corresponding parent scheduler at each of one or more next levels of the scheduling hierarchy up to the root scheduler, the traffic manager is configured to:
send a task update message from the corresponding queue to the corresponding parent scheduler at the next level of the hierarchy;
and
iteratively, for each scheduling level up to the root scheduler, send a task update message from each corresponding parent scheduler at each level of the scheduling hierarchy, wherein the task update message comprises a first packet size correction field and a second packet size correction field, the traffic manager configured to:
update, based on the first packet size correction field, the packet size at each level of the scheduling hierarchy;
and
indicate, based on the second, packet size correction field, a protocol of the given packet.

12 more elements

Dependencies are inferred from the claim text.

Description23,828 words

Summary646 words

#1. Field of the Invention

#The present invention relates to communication systems, in particular, to data caching and coherency maintenance for an accelerated processor architecture for packet networks.

#2. Description of the Related Art

Brief description of the drawings21 figures

#Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which like reference numerals identify similar or identical elements.

#FIG. 1 shows a block diagram of a network processor operating in accordance with exemplary embodiments of the present invention;

#FIG. 2 shows a block diagram of a system cache of the network processor of FIG. 1;

Detailed description22,596 words

#Described embodiments of the present invention provide a Modular Traffic Manager (MTM) for a multi-core, multi-threaded network processor.

#Table 1 defines a list of acronyms employed throughout this specification as an aid to understanding the described embodiments of the present invention:

#TABLE 1 USB Universal Serial Bus FIFO First-In, First-Out SATA Serial Advanced I/O Input/Output Technology Attachment SCSI Small Computer System DDR Double Data Rate Interface SAS Serial Attached SCSI DRAM Dynamic Random Access Memory PCI-E Peripheral Component MMB Memory Manager Interconnect Express Block SRIO Serial RapidIO CPU Central Processing Unit SoC System-on-Chip μP Microprocessor AXI Advanced eXtensible PLB Processor Local Bus Interface AMBA Advanced Micro- MPP Modular Packet controller Bus Processor Architecture PAB Packet Assembly Block AAL5 ATM Adaptation Layer 5 MTM Modular Traffic Manager SED Stream Editor DBC Data Buffer Controller THID Thread Identifier HE Hash Engine PQM Pre-Queue Modifier SENG State Engine FBI Function Bus Interface TID Task Identifier CCL Classification Com- pletion List SCH Scheduler SEM Semaphore Engine SPP Security Protocol PCM Per Context Memory Processor TIL Task Input Logic PDU Protocol Data Unit TCP Transmission Control PIC Packet Integrity Checker Protocol TS Traffic Shaper FSM Finite State Machine PCR Peak Cell Rate MCR Minimum Cell Rate EF Expedited Forwarding AF Assured Forwarding BE Best Effort Forwarding SDWRR Smooth Deficit Weighted Round Robin mutex MUtually EXclusive CRC Cyclic Redundancy Check IP Internet Protocol

Facts

Application

13/250,927Filed 30 Sep 2011 · continuation in part

Priority

18 May 2010

Published

US 2012/0020210 A126 Jan 2012

Granted

31 Dec 2013

Term ends

1 Feb 2031

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 259 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification10 codes

H04L 49/254
Using establishment or release of connections between ports: centralised controller, i.e. arbitration or scheduling
H04L 47/621
Characterised by scheduling criteria: individual queue per connection or flow, e.g. per VC
H04L 47/623
Queue service order: weighted service order
H04L 47/628
For service slots or service orders: based on packet size, e.g. shortest packet first

Family

Application12/782,379Parent of this continuation-in-part · filed 18 May 2010

Application12/782,393Parent of this continuation-in-part · filed 18 May 2010

Application12/782,411Parent of this continuation-in-part · filed 18 May 2010

Application61/388,962Us provisional application · filed 1 Oct 2010

US 2012/0020210 A1Pre-grant publication · published 26 Jan 2012

US 8,255,644 B2Parent of this continuation-in-part

US 8,407,707 B2Parent of this continuation-in-part

US 2010/0293312 A1Published application

US 2010/0293345 A1Published application

US 2010/0293353 A1Published application

US 9,081,742 B2Related patent

US 8,619,787 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

18 May 2010Priority claimedParent application 12/782,379
30 Sep 2011Application filedUS 13/250,927
3 Oct 2011Assigned to Lsi Corporationassignment of assignor's interest
26 Jan 2012PublishedUS 2012/0020210 A1
31 Dec 2013GrantedUS 8,619,787 B2
8 May 2014Assigned to Deutsche Bank AG New York Branch, AS Collateral Agentpatent security agreement
18 Nov 2014Assigned to Lsi Corporation, Agere Systems LLCtermination and release of security interest in patents at reel/frame no. 32856/0031
24 Feb 2015Assigned to Intel Corporationassignment of assignor's interest
2 Feb 2016Assigned to Lsi Corporation, Agere Systems LLCtermination and release of security interest in patent rights (releases rf 032856-0031)
12 Oct 2026TodayWithin its term
1 Feb 2031Term endsEstimated, includes 259 days of adjustment

Byte-accurate scheduling in a network processor

Life of this patent

Byte-accurate scheduling in a network processor

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims23

Description23,828 words

Drawings

Classification10 codes

Life of this patent

Description23,828 words