Root scheduling algorithm in a network processor

A method of arbitrating between nodes of scheduling hierarchy of a hardware network processor having a plurality of processors and at least one shared memory with packet data, the method comprising:

• generating, by a traffic manager of the hardware network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduling levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy;
• queuing, by the traffic manager, one or more tasks in an associated queue of the scheduling hierarchy, wherein the tasks are associated with one or more data flows of the hardware network processor;
• performing, by a given scheduler in the scheduling hierarchy, a configurable arbitration between each child node of the given scheduler, wherein the configurable arbitration is one of (i) smooth deficit weighted round robin (SDWRR) arbitration, (ii) deficit weighted round robin (DWRR) arbitration, and (iii) strict priority arbitration, wherein the DWRR arbitration comprises:
• maintaining a linked list of active child nodes of each scheduler;
• scheduling a child node at a head end of the linked list;
• incrementing a task counter of the child node;
• determining, based on the task counter, whether the child node has reached an associated DWRR limit;
• if the child node has reached the DWRR limit:
• moving the child node to a tail end of the linked list and shift a subsequent child node to the head of the linked list.

A non-transitory machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of arbitrating between nodes of scheduling hierarchy of a hardware network processor having a plurality of processors and at least one shared memory with packet data, the method comprising:

• generating, by a traffic manager of the hardware network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduling levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy;
• queuing, by the traffic manager, one or more tasks in an associated queue of the scheduling hierarchy, wherein the tasks are associated with one or more data flows of the hardware network processor;
• performing, by a given scheduler in the scheduling hierarchy, a configurable arbitration between each child node of the given scheduler, wherein the configurable arbitration is one of (i) smooth deficit weighted round robin (SDWRR) arbitration, (ii) deficit weighted round robin (DWRR) arbitration, and (iii) strict priority arbitration, wherein the DWRR arbitration comprises:
• maintaining a linked list of active child nodes of each scheduler;
• scheduling a child node at a head end of the linked list;
• incrementing a task counter of the child node;
• determining, based on the task counter, whether the child node has reached an associated DWRR limit;
• if the child node has reached the DWRR limit:
• moving the child node to a tail end of the linked list and shift a subsequent child node to the head of the linked list.

A non-transitory machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of arbitrating between nodes of scheduling hierarchy of a hardware network processor having a plurality of processors and at least one shared memory with packet data, the method comprising:

• generating, by a traffic manager of the hardware network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduling levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy;
• queuing, by the traffic manager, one or more tasks in an associated queue of the scheduling hierarchy, wherein the tasks are associated with one or more data flows of the hardware network processor;
• performing, by a given scheduler in the scheduling hierarchy, smooth deficit weighted round robin (SDWRR) arbitration between each child node of the given scheduler, wherein the SDWRR arbitration comprises:
• checking one or more status indicators of each child node of the given scheduler;
• selecting, based on the one or more status indicators, a first active child node of the scheduler, whereby a task is scheduled for transmission by the traffic manager every cycle of the hardware network processor;
• and
• updating the one or more status indicators corresponding to the selected child node.