Weighted fair queue having extended effective range

Abstract

A scheduler for a network processor includes a scheduling queue in which weighted fair queuing is applied to define a sequence in which flows are to be serviced. The scheduling queue includes at least a first subqueue and a second subqueue. The first subqueue has a first range and a first resolution, and the second subqueue has an extended range that is greater than the first range and a lower resolution that is less than the first resolution. Flows that are to be enqueued within the range of highest precision to the current pointer of the scheduling queue are attached to the first subqueue. Flows that are to be enqueued outside the range of highest precision from the current pointer of the scheduling queue are attached to the second subqueue. Numerous other aspects are provided.

1 . A scheduler for a network processor, the scheduler comprising: 
 one or more scheduling queues each adapted to define a sequence in which flows are to be serviced, at least one scheduling queue including at least a first subqueue and a second subqueue, the first subqueue having a first range and a first resolution, and the second subqueue having a second range that is greater than the first range and a second resolution that is less than the first resolution, wherein the first and second resolutions are an inverse of a distance increment that corresponds to at least one slot in each of the respective first and second subqueues.    
   
   
       2 . The scheduler of  claim 1 , wherein the first subqueue has a number of slots that is equal to a number of slots of the second subqueue.  
   
   
       3 . The scheduler of  claim 1 , wherein the first subqueue has a number of slots that is different than a number of slots of the second subqueue.  
   
   
       4 . The scheduler of  claim 1 , wherein the second range and the second resolution have a direct inverse relationship.  
   
   
       5 . The scheduler of  claim 1 , wherein the second range and the second resolution have other than a direct inverse relationship.  
   
   
       6 . The scheduler of  claim 1 , wherein the scheduling queue includes a third subqueue having a third range that is greater than the second range and a third resolution that is less than the second resolution.  
   
   
       7 . A scheduler for a network processor, the scheduler comprising a scheduling queue in which flows are enqueued according to the formula CP+((WF×FS)/SF) wherein: 
 CP is a pointer for indicating a current position in the scheduling queue;    WF is a weighting factor associated with a flow appointed for enqueuing;    FS is a frame size associated with the flow appointed for enqueuing; and    SF is a scaling factor;    wherein the scheduling queue includes at least a first subqueue and a second subqueue, and the flow appointed for enqueuing is enqueued to the first subqueue if the value of the expression ((WF×FS)/SF) is less than a range of the first subqueue and the flow appointed for enqueuing is enqueued to the second subqueue if the value of the expression ((WF×FS)/SF) is greater than a range of the first subqueue.    
   
   
       8 . The scheduler of  claim 7 , wherein the pointer CP is shared by the first and second subqueues, and least significant digits of the pointer are applied to the first subqueue and most significant digits of the pointer are applied to the second subqueue.  
   
   
       9 . The scheduler of  claim 7 , wherein the first subqueue has a number of slots that is equal to a number of slots of the second subqueue.  
   
   
       10 . The scheduler of  claim 7 , wherein the first subqueue has a number of slots that is different than a number of slots of the second subqueue.  
   
   
       11 . The scheduler of  claim 7 , wherein the second subqueue has a range that is larger than the range of the first subqueue and the second subqueue has a resolution that is less than a resolution of the first subqueue, wherein the first and second resolutions are an inverse of a distance increment that corresponds to at least one slot in each of the respective first and second subqueues.  
   
   
       12 . A scheduler for a network processor, the scheduler comprising: 
 one or more scheduling queues each adapted to define a sequence in which flows are to be serviced, at least one scheduling queue including a plurality of subqueues, wherein each successive one of the subqueues has a selected range that is greater than a range of a preceding subqueue and a selected resolution that is less than a resolution of the preceding subqueue, wherein the resolutions are an inverse of a distance increment that corresponds to at least one slot in each of the respective subqueues.    
   
   
       13 . A method of managing queuing of flows in a network processor, comprising: 
 enqueuing a flow to a first subqueue if the expression ((WF×FS)/SF) has a value that is less than a range of the first subqueue; and    enqueuing the flow to a second subqueue if the expression ((WF×FS)/SF) has a value that is greater than the range of the first subqueue, wherein:    WF is a weighting factor associated with the flow;    FS is a frame size associated with the flow; and    SF is a scaling factor.    
   
   
       14 . The method of  claim 13 , wherein the second subqueue has a range that is larger than the range of the first subqueue and the second subqueue has a resolution that is less than a resolution of the first subqueue.