Deficit round robin scheduling using multiplication factors

Some of the embodiments of the present disclosure provide a method for scheduling processing of packets received from a network, comprising assigning a corresponding queue weight to each of a plurality of queues that are configured to enqueue the packets for processing; for each of the plurality of queues, determining a corresponding multiplication factor (MF) as a function of a number of cycles until a next packet is available from the corresponding queue for processing; and incrementing a plurality of counters, associated with the corresponding plurality of queues, based at least in part on the multiplication factors. Other embodiments are also described and claimed.

TECHNICAL FIELD

Embodiments of the present disclosure relate to deficit round robin scheduling in general, and more specifically, to deficit round robin scheduling of data packets using multiplication factors.

BACKGROUND

Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in the present disclosure and are not admitted to be prior art by inclusion in this section.

In a conventional deficit round robin (DRR) scheduling, a packet processor processes data packets from a plurality of traffic flows or queues. Each queue is assigned a corresponding weight based on, for example, a priority of the queue. In each DRR cycle, a counter associated with a queue is incremented by the assigned weight of the queue. During a DRR cycle, a size of a packet to be processed from a queue is compared with the associated counter. If the size of the packet in the queue is greater than the associated counter, the packet is not processed in that DRR cycle (e.g., the processing of the packet is carried forward for a future DRR cycle). However, if the counter is at least as high as the size of the packet, the packet is processed during the DRR cycle and the counter is updated by subtracting the packet size from the previous counter value.

If the sizes of the packets in the queues are relatively large compared to the respective weights of the queues, in a conventional DRR scheduling, no packets may be processed during several DRR cycles. That is, several DRR cycles are wasted (e.g., wasted as no packet processing occurs during these DRR cycles), as the counters are not high enough to allow processing of the data packets. These wasted DRR cycles in a conventional packet processing system generally results in performance degradation of the system.

SUMMARY

In various embodiments, the present disclosure provides a method for scheduling processing of packets received from a network, comprising assigning a corresponding queue weight to each of a plurality of queues that are configured to enqueue the packets for processing; for each of the plurality of queues, determining a corresponding multiplication factor (MF) as a function of a number of cycles until a next packet is available from the corresponding queue for processing; and incrementing a plurality of counters, associated with the corresponding plurality of queues, based at least in part on the multiplication factors. There is also provided a system-on-chip (SOC) comprising a plurality of client devices associated with a corresponding plurality of queues, wherein the plurality of queues is assigned a corresponding plurality of counters; and a packet processor comprising a weight assignment module configured to assign, to the plurality of queues, a corresponding plurality of queue weights; a queue multiplication factor module configured to determine, for the plurality of queues, a corresponding plurality of multiplication factors (MFs), wherein a MF of a queue is a function of a number of cycles until a next packet is available from the corresponding queue for processing; a queue counter module configured to increment each of the plurality of counters based at least in part on the plurality of MFs. There is also provided a method comprising determining a first multiplication factor (MF) associated with a first queue, wherein the first MF represents a minimum number of deficit round robin (DRR) cycles required by the first counter to reach a first threshold value if the first counter is incremented by a first queue weight during a DRR cycle; determining a second MF associated with a second queue, wherein the second MF represents a minimum number of DRR cycles required by the second counter to reach a second threshold value if the second counter is incremented by the second queue weight during a DRR cycle; determining a third MF that is a minimum of the first MF and the second MF; incrementing a first counter, associated with the first queue, by a product of the first queue weight and the third MF; and incrementing a second counter, associated with the second queue, by a product of the second queue weight and the third MF.

DETAILED DESCRIPTION

FIG. 1schematically illustrates a packet processing system100(also referred to herein as system100) that includes a system-on-chip (SOC)10comprising a queue multiplication factor module32, in accordance with an embodiment of the present disclosure. The SOC10includes a packet processor20comprising the queue multiplication factor module32. The SOC10also includes one or more processing cores, e.g. processing core12aand processing core12b. The SOC10further includes one or more network interfaces, e.g., network interfaces12c, . . . ,12e. In an embodiment, network interfaces12c, . . . ,12eare network devices, e.g., a network switch, a network router, a network port, an Ethernet port (e.g., a Gigabyte or other suitable sized Ethernet port), a network controller, any appropriate device that has a network connectivity, and/or the like.

Although not illustrated inFIG. 1, in an embodiment, one or more of the processing cores12aand12band network interfaces12b, . . . ,12eare external to the SOC10, although such architecture is optional. Although the SOC10includes several other components (e.g., one or more peripherals, one or more serializer and/or deserializer (SerDes) devices, interfaces, communication bus, cache, and/or the like), these components are not illustrated inFIG. 1for the purpose of illustrative clarity. Although two processing cores and three network interfaces are illustrated inFIG. 1, the SOC10may include any other suitable number of processing cores and/or network interfaces.

In an embodiment, the processing cores12aand12band the network interfaces12c, . . . ,12etransmit data packets to the packet processor20. Data packets (also referred to herein as “packets”) herein refer to packets that include user data, control data, management data, and/or any other appropriate information. As the packet processor20provides service to the processing cores12aand12band the network interfaces12c, . . . ,12e, the processing cores12aand12band the network interfaces12c, . . . ,12eare also referred to herein as client devices of the packet processor20. The packet processor20receives data packets from one or more of the processing cores12aand12band the network interfaces12c, . . . ,12e, and processes the received data packets. In a simple example, the packet processor20sequentially receives data packets from one or more client devices (the sequence in which the data packets are received from one or more client devices will be discussed in more detail herein later), and re-transmits the received data packets (illustrated as outgoing data packets inFIG. 1) to one or more components that are either external to, or included in the SOC10. In an embodiment, the packet processor20processes the data packets received from the client devices, before transmitting the processed data packets as outgoing data packets.

In an embodiment, data packets from a client device are queued before being transmitted to the packet processor20. A queue associated with a client device may form within the client device, and/or may form in any appropriate memory or buffer (e.g., a first-in first-out buffer, not illustrated inFIG. 1) associated with the client device. For example, data packets to be transmitted from the processing core12ato the packet processor20are queued as queue A, data packets to be transmitted from the processing core12bto the packet processor20are queued as queue B, data packets to be transmitted from the network interface12cto the packet processor20are queued as queue C, data packets to be transmitted from the network interface12dto the packet processor20are queued as queue D, and data packets to be transmitted from the network interface12eto the packet processor20are queued as queue E, as illustrated inFIG. 1.

AlthoughFIG. 1illustrates only one queue from a client device to the packet processor20, this does not in any way limit the teachings of this disclosure. Although not illustrated inFIG. 1, in an embodiment, more than one queue is formed from a client device to the packet processor20. For example, relatively high priority data packets of a client device are queued in a queue, whereas relatively low priority data packets of the client device are queued in another queue. Although not illustrated inFIG. 1, in an embodiment, a queue receives data packets from more than one client devices. As an example, although not illustrated inFIG. 1, a queue receives data packets from processing core12aand network interface12c.

FIG. 1also illustrates example data packets in the queues A, . . . , E at a given time. For example, queue A includes data packets Da1, Da2and Da3, queue B includes data packets Db1and Db2, queue C includes data packets Dc1, Dc2, Dc3and Dc4, queue D includes only one data packet (e.g., data packet Dd1), and queue E does not include any data packet.

In an embodiment, data packets from various queues are processed by the packet processor20using deficit round robin (DRR) scheduling. In an embodiment, during a DRR cycle, a scheduling module30included in the packet processor20schedules a data packet, from a queue of the queues A, . . . , E, for processing by the packet processor20, as will be discussed in more detail herein later.

In an embodiment, individual queues operate on a first-in first-out basis. For example, for queue A, data packet Da1is processed by the packet processor20, followed by data packets Da2and Da3(although one or more other data packets from other queues may be processed in between processing the data packets of the queue A).

Referring again toFIG. 1, the packet processor20comprises a weight assignment module22. In an embodiment, the weight assignment module22is configured to assign queue weights to a queue based, for example, on a priority of the data packets associated with the queue, an originating address of the queue, a destination address of the queue, etc. For example, a queue weight of a queue is a number that represents a relative priority of the queue compared to priorities of other queues. As an example, if the priority of the data packets of queue A is relatively higher than that of queue B, the queue weight assigned to queue A is relatively higher than that of queue B. As an example, if packets in queue A have a higher processing priority than packets in queue B, then queue A is assigned a queue weight of Wa, queue B is assigned a queue weight of Wb, where Wa>Wb, and so on.

Although the weight assignment module22is illustrated to be included in the packet processor20, in an embodiment, the weight assignment module22is external to the SOC10. In an embodiment, the assigned queue weights Wa, . . . , We are configurable and/or are assigned by a user of the SOC10.

For the purpose of this disclosure and unless otherwise mentioned, a data packet at a head of a queue is referred to herein as a head data packet of the queue. Thus, the head data packet of the queue is the first data packet of the queue that is to be processed by the packet processor20. For example, data packet Da1is the head data packet of the queue A, data packet Db1is the head data packet of the queue B, and so on. InFIG. 1, the queue E is empty. Accordingly, queue E does not have any head data packet.

The packet processor20also comprises a head data packet size determination module24, which is configured to determine packet sizes of head data packets of various queues. In an embodiment, a packet size is expressed using any appropriate packet size measurement units, e.g., bits, bytes, etc. For example, the size of the head data packet Da1of the queue A is PSa (e.g., which is a function of a number of bytes included in the head data packet Da1), the size of the head data packet Db1of the queue B is PSb, and so on. In an embodiment, the head data packet size determination module24determines the size of the head data packet of a queue based on one or more parameters received from the queue (e.g., from a header portion of the head data packet received from the queue).

In an embodiment, the queues A, . . . , E are assigned queue counters Ca, . . . , Ce, respectively. For example, queue A is assigned a queue counter Ca, queue B is assigned a queue counter Cb, and so on. The packet processor20also comprises a queue counter module28, which keeps track of the queue counters Ca, . . . , Ce, and periodically updates the queue counters.

In an embodiment, the packet processor20schedules processing of data packets from one or more of the queues A, . . . , E using DRR scheduling. The DRR scheduling comprises a plurality of DRR cycles. During each DRR cycle, the scheduling module30schedules a data packet (e.g., a head data packet from a selected queue of the queues A, . . . , E) for processing by the packet processor20(e.g., by a data processing module36included in the packet processor20).

The packet processor20also comprises a queue increment factor (IF) module34configured to determine increment factors IFa, . . . , IFe for queues A, . . . E, respectively, as will be discussed in more detail herein later. In an embodiment, in each DRR cycle, the queue counters Ca, . . . , Ce are incremented (e.g., by the queue counter module28) by corresponding increment factors IFa, . . . , IFe, respectively. For example, during a DRR cycle, the queue counter Ca is incremented by increment factor IFa, the queue counter Cb is incremented by increment factor IFb, and so on.

During each DRR cycle, in an embodiment, after incrementing the queue counters Ca, . . . , Ce, the queue counter of a queue is compared to the size of the head data packet of the queue. If the size of the head data packet of the queue is greater than the associated queue counter, the packet is not scheduled (e.g., by the scheduling module30) for processing in that DRR cycle (e.g., the processing of the packet is carried forward for a future DRR cycle). However, if the queue counter value is at least as high as the size of the head data packet, the head data packet is scheduled (e.g., by the scheduling module30) for processing (e.g., by the data processing module36) during the DRR cycle and the queue counter is updated by subtracting the size of the head data packet from the queue counter.

In a conventional packet processing system implementing a conventional DRR scheduling, if the sizes of the head data packets of the queues are relatively large compared to the respective queue weights of the queues, during several DRR cycles no data packets may be processed at all (e.g., the queue counters of each queue may be lower than the size of the corresponding head packets during these DRR cycles). That is, several DRR cycles are wasted (e.g., wasted as no data packet processing occurs during these DRR cycles), as the queue counters of the conventional packet processing system are not high enough to allow transmission of head data packets. To overcome these issues of the conventional packet processing system, in an embodiment, the packet processor20ofFIG. 1increments, during one or more DRR cycles, the queue counters by increment factors that are greater than the corresponding queue weights, as will be discussed in more detail herein later.

In an embodiment, the packet processor20also comprises a queue multiplication factor module32, which is configured to determine, for each DRR cycle, a plurality of multiplication factors (MFs) for the corresponding plurality of queues. For example, during a DRR cycle, the queue multiplication factor module32determines MFa associated with queue A, MFb associated with queue B, and so on. In an embodiment, an MF of a queue (e.g., MFa of queue A) represents a minimum number of DRR cycles required to increment the queue counter by the corresponding queue weight such that the queue counter value is high enough to allow transmission of the head data packet in the queue. For example, if the queue counter Ca is incremented by queue weight Wa in each DRR cycle, then MFa represents the minimum number of DRR cycles required to increment the queue counter Ca by the queue weight Wa such that the queue counter Ca is at least as high as PSa (i.e., is at least as high as the size of the head data packet Da1in the queue A). For an itqueue (where i=A, . . . , E) with queue counter Ci, queue weight Wi and head data packet size PSi, MFi is determined as
MFi=Ceiling((PSi−Ci)/Wi),  Equation (1)
where the function Ceiling(M) of a number M represents the smallest integer that is not smaller than M. For example, if M=3.2, then ceiling(M) is 4. In a simple example, if PSa is 1000, queue weight Wa is 150 and the queue counter Ca is 350, then MFa is 5. In an embodiment, multiplication factor for empty queues (i.e., those queues which do not currently include any data packet, e.g., queue E) is undefined.

For each DRR cycle, the queue multiplication factor module32also determines a minimum multiplication factor (MMF), which is a minimum of the MFs of all the queues. For example, for each DRR cycle,
MMF=minimum(MFa, . . . , MFe).  Equation (2)
In an embodiment, multiplication factor for empty queues are not taken into account while determining the MMF (e.g., in such a case, MMF=minimum(MFa, . . . , MFd), as queue E is empty).

As previously discussed, at the beginning of each DRR cycle, the queue counter module28increments the queue counters Ca, . . . , Ce by increment factors IFa, . . . , IFe, respectively. In an embodiment, the increment factors IFa, . . . , IFe are products of respective queue weights and the MMF. For example, IFa is a product of Wa and MMF (i.e., IFa=Wa×MMF), IFb is a product of Wb and MMF (i.e., IFb=Wb×MMF), and so on. Thus, for the ithqueue,
IFi=Wi×MMF.  Equation (3)
As previously discussed, once the queue counters are updated using the respective increment factors, the queue counter of a queue is compared to the packet size of the head data packet of the queue. If the packet size of the head data packet of the queue is greater than the associated queue counter, the packet is not scheduled for processing (e.g., by the scheduling module30) in that DRR cycle. However, if the queue counter value is at least as high as the size of the head data packet, the head data packet is scheduled (e.g., by the scheduling module30) for processing by the packet processor20during the DRR cycle and the queue counter is updated (e.g., by the queue counter module28) by subtracting the size of the head data packet from the queue counter. The head data packet, scheduled for processing, is subsequently processed by the data processing module36included in the packet processor20.

In a conventional packet processing system implementing a conventional DRR scheduling, during each DRR cycle the queue counters are generally incremented by the assigned queue weights. For example, if a queue weight assigned to a queue is 100, then the associated queue counter of the conventional packet processing system is incremented by 100 during each DRR cycle. Subsequently, the queue counter is compared to the packet size of the head data packet of the queue to determine if the head data packet is to be processed during the current DRR cycle. If the sizes of the head data packets of the queues are relatively large compared to the respective queue weights of the queues, in a conventional DRR scheduling, during several DRR cycles no data packets may be processed at all. That is, several DRR cycles are wasted (e.g., wasted as no data packet processing occurs during these DRR cycles), as the queue counters are not high enough to allow transmission of head data packets. These wasted DRR cycles in a conventional packet processing system generally results in performance degradation (e.g., results in relatively higher latency) of the conventional packet processing system.

In contrast, in the packet processing system10ofFIG. 1, due to the introduction of the MFs and the MMF, the queue counters Ca, . . . , Ce are updated by the corresponding increment factors such that no DRR cycles are wasted (i.e., processing of head data packets occur in each DRR cycle when such head data packets are available for processing in one or more queues). For example, the MFs and MMF ensure that the queue counters are updated using the increment factors IFa, . . . , IFe such that for at least one queue of the queues A, . . . , E, the queue counter is high enough to allow transmission of a head data packet in each DRR cycle. Accordingly, the packet processing system ofFIG. 1has better performance (e.g., due to less or no wastage of DRR cycles) compared to the previously discussed conventional packet processing system.

FIGS. 2aand2bschematically illustrate operations of the packet processing system10ofFIG. 1, in accordance with an embodiment of the present disclosure. InFIGS. 2aand2b, as an example, the operation of the packet processing system10is illustrated using only three queues (queues A, B and E), although the teachings of this disclosure is not limited by such a number of queues.

As illustrated inFIGS. 1 and 2a, at the end of a DRR cycle (i−1), queue A has three data packets Da1, Da2and Da3, with Da1being the head data packet. Also, data packets Da1, Da2and Da3are equal to example sizes 1500, 1000, and 1000, respectively. Thus, the size of the head data packet of queue A is 1500 (i.e., PSa=1500). Similarly, queue B has two data packets Db1and Db2at the end of the DRR cycle (i−1), with Db1being the head data packet. Also, data packets Db1and Db2are equal to example sizes of 1500 and 1100, respectively (i.e., PSb=1500). Queue E has no data packet at the end of the DRR cycle (i−1) (i.e., size of the head data packet PSe=0). Queue weights Wa, Wb and We are assumed to be equal to example values 100, 150 and 250, respectively. Also, at the end of the DRR cycle (i−1), the queue counters Ca, Cb and Ce are all equal to examples value of 0.

At DRR cycle (i) (which occurs immediately subsequent to the DRR cycle (i−1)), MFa, MFb and MFc are determined using equation 1. For example, MFa=Ceiling ((PSa−Ca)/Wa)=Ceiling ((1500−0)/100)=15. MFb is similarly determined to be equal to 10. As the queue E is empty, MF for queue E (i.e., MFe) is undefined. The MMF for the DRR cycle (i) is determined using equation 2, and the MMF is equal to the minimum of MFa and MFb. That is, the MMF for the DRR cycle (i) is equal to 10.

Increment factors IFa, IFb and IFe are subsequently determined using equation 3. For example, IFa=MMF×Wa=10×100=1000. Similarly, IFb is equal to 1500 and IFe is equal to zero, as illustrated inFIG. 2a.

Based on the determined increment factors IFa, IFb and IFe, the queue counters Ca, Cb and Ce are respectively updated. For example, the new value of the queue counter Ca is equal to (0+1000)=1000. Similarly, the new value of the queue counter Cb is equal to 1500, and the new value of the queue counter Ce is equal to zero.

Subsequent to updating the queue counters Ca, Cb and Ce, during the DRR cycle (i), the queue counter Cb is at least as high as the head data packet size Pb. That is, the queue counter Cb is high enough to transmit head data packet Db1from the queue B, whereas the queue counter Ca is still less than the head data packet size PSa. Accordingly, in the DRR cycle (i), the head data packet Db1from the queue B is processed by the data processing module36of the packet processor20. In response to processing the head data packet Db1, the queue counter Cb is updated by decrementing the queue counter Cb by the size of the head data packet Db1. Accordingly, the new value of the queue counter Cb is 0.

FIG. 2billustrates the operation of the packet processing system10ofFIG. 1during DRR cycle (i−1)), where the DRR cycle (i+1)) occurs immediately subsequent to DRR cycle (i) ofFIG. 2a. As previously discussed, during the DRR cycle (i), the head data packet Db1is processed. Accordingly, in the DRR cycle (i+1), queue B includes data packet Db2only, which is also the head data packet of the queue B. Furthermore, the size of the head data packet Db2is 1100 (i.e., PSb=1100). Also, similar toFIG. 2a, for the DRR cycle (i+1), PSa=1500 and PSe=0.

Referring again toFIG. 2a, at the end of the DRR cycle (i), the queue counters Ca, Cb and Ce were equal to 1000, 0 and 0, respectively. At DRR cycle (i+1), MFa, MFb and MFe are determined using equation 1. For example, MFa=Ceiling ((PSa−Ca)/Wa)=Ceiling ((1500−1000)/100)=5. Also, MFb=Ceiling ((1100−0)/150)=8. As the queue E is empty, MF for queue E (i.e., MFe) is undefined. The MMF for the DRR cycle (i+1) is determined using equation 2, and the MMF is equal to the minimum of MFa and MFb. That is, for the DRR cycle (i+1), the MMF is equal to 5.

The increment factors IFa, IFb and IFe for the DRR cycle (i+1) are subsequently determined using equation 3. For example, for the DRR cycle (i+1), IFa=MMF×Wa=5×100=500. Similarly, IFb is equal to 750 and IFe is equal to zero, as illustrated inFIG. 2b.

Based on the determined increment factors IFa, IFb and IFc, the queue counters Ca, Cb and Ce are respectively updated. For example, during the DRR cycle (i+1), the new value of the queue counter Ca is equal to (1000+500)=1500. Similarly, the new value of the queue counter Cb is equal to (0+750)=750, and the new value of the queue counter Ce is equal to zero.

Subsequent to updating the queue counters Ca, Cb and Ce during the DRR cycle (i−1), the queue counter Ca is at least as high as the head data packet size PSa (e.g., as illustrated inFIG. 2b, Ca is equal to PSa). That is, the queue counter Ca is high enough to transmit the head data packet Da1from the queue A, whereas the queue counter Cb is still less than the head data packet size PSb. Accordingly, in the DRR cycle (i+1), the head data packet Da1from the queue A is processed by the data processing module36of the packet processor20. In response to processing the head data packet Da1, the queue counter Ca is updated by decrementing the queue counter Ca by the size of the head data packet Da1. Accordingly, the new value of the queue counter Ca is 0. Also, the queue counter Cb and Ce are 750 and 0, respectively, at the end of the DRR cycle (i+1).

Although inFIGS. 2aand2b, no new data packets are illustrated to be queued in the queues A, B and E during the DRR cycles (i) and (i+1), in various other embodiments, one or more new data packets join one or more of the queues during, for example, DRR cycle (i+1). Furthermore, the various numbers (e.g., PSa, Ca, IFa, etc) associated withFIGS. 2aand2bhave appropriate units. The unit for these numbers is, for example, bytes. The MFs and the MMF are, for example, dimensionless numbers.

In a conventional deficit round robin packet processing system scheduler, the queue counters are incremented by queue weights only. Accordingly, in the conventional packet processing system, subsequent to DRR cycle (i−1), in the example above, at least fifteen more conventional DRR cycles would be required before the queue counter for the queue B reaches 1500. That is, at least fifteen conventional DRR cycles would be required before the queue counter Cb for the queue B is high enough for transmitting the head data packet Db1, thereby resulting in a waste of at least fourteen DRR cycles. In contrast, in the embodiments ofFIG. 2a, by incrementing the queue counter Cb with the increment factor IFb, no DRR cycle is wasted in processing the head data packet Db1(as there are no DRR cycles between the DRR cycle (i−1) and DRR cycle (i) inFIG. 2a). Also, as the minimum of all the MFs are taken into account (e.g., by calculating the MMF) while scheduling the processing of the head data packets, the order in which the head packets of various queues are to be processed are always maintained.

Similarly, in the conventional DRR packet processing scheduling system, subsequent to DRR cycle (i), at least five more conventional DRR cycles are required before the queue counter for the queue A reaches 1500. That is, at least five more conventional DRR cycles are required before the queue counter for the queue A is high enough for transmitting the head data packet Da1, thereby resulting in a waste of at least four DRR cycles. In contrast, in the embodiments ofFIG. 2b, by incrementing the queue counter Ca with the increment factor IFa, no DRR cycle is wasted in processing the head data packet Da1(as there are no DRR cycles between the DRR cycle (i) and DRR cycle (i+1) inFIG. 2b).

Accordingly, in various embodiments, the data processing system10ofFIG. 1is more efficient (e.g., results is relatively less latency, less processing time, no wasted DRR cycles, etc.) compared to a conventional data processing system.

FIG. 3illustrates an example method300for operating the packet processing system10ofFIG. 1, in accordance with an embodiment of the present disclosure. At304, the packet processor20(e.g., the weight assignment module22) assigns, to a plurality of queues (e.g., queues A, . . . , E), a corresponding plurality of queue weights (e.g., queue weights Wa, . . . , We). In an embodiment, a queue weight of a queue is assigned based at least in part on a priority of the queue.

At308, the packet processor20(e.g., queue multiplication factor module32) determines (e.g., using equation 1), for the plurality of queues, a corresponding plurality of multiplication factors (e.g., MFa, . . . , MFe). In an embodiment, the MF of a queue represents a minimum number of DRR cycles required by the corresponding queue counter to reach a threshold value if the corresponding queue counter is incremented by the corresponding queue weight during each DRR cycle, where the threshold value of a queue is a size of a head data packet in the queue.

At312, the packet processor20(e.g., queue multiplication factor module32) determines (e.g., using equation 2) a minimum MF (MMF) that is a minimum of the plurality of MFs. At316, the packet processor20(e.g., the queue counter module28) increments each of the plurality of queue counters by a corresponding plurality of increment factors based at least in part on the MMF. In an embodiment, for each queue of the plurality of queues, the increment factor is a product of the MMF and the corresponding queue weight, and is determined using equation 3.

At320, the packet processor20(e.g., the data processing module36) compares, for each of the queue, the corresponding queue counter with the corresponding threshold value. At324, for each queue of the plurality of queues, if the queue counter is at least as high as the corresponding threshold value, the packet processor20(e.g., the data processing module36) processes a head data packet of the queue.

Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art and others, that a wide variety of alternate and/or equivalent implementations may be substituted for the specific embodiment shown and described without departing from the scope of the present disclosure. The present disclosure covers all methods, apparatus, and articles of manufacture fairly falling within the scope of the appended claims either literally or under the doctrine of equivalents. This application is intended to cover any adaptations or variations of the embodiment disclosed herein. Therefore, it is manifested and intended that the present disclosure be limited only by the claims and the equivalents thereof.