Weighted fair queue having adjustable scaling factor

Abstract

A scheduler for a network processor includes a scheduling queue in which weighted fair queuing is applied. The scheduling queue has a range R. Flows are attached to the scheduling queue at a distance D from a current pointer for the scheduling queue. The distance D is calculated for each flow according to the formula D=((WF×FS)/SF), where WF is a weighting factor applicable to a respective flow; FS is a frame size attributable to the respective flow; and SF is a scaling factor. The scaling factor SF is adjusted depending on a comparison of the distance D to the range R.

1 . A scheduler for a network processor, the scheduler including a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;    FS is a frame size attributable to the respective flow; and    SF is a scaling factor;    wherein the scaling factor SF is adjusted depending on a result of comparing the distance D to the range R.    
   
   
       2 . The scheduler of  claim 1 , wherein SF is increased if D>R.  
   
   
       3 . The scheduler of  claim 2 , wherein SF is increased if D exceeds R in regard to a predetermined number of calculations of D.  
   
   
       4 . The scheduler of  claim 1 , wherein SF is decreased if D<R/2.  
   
   
       5 . The scheduler of  claim 4 , wherein SF is decreased if D is less than one-half R in regard to a predetermined number of calculations of D.  
   
   
       6 . The scheduler of  claim 1 , wherein SF=2 n , n being a positive integer.  
   
   
       7 . A scheduler of  claim 6 , wherein n is incremented to adjust SF.  
   
   
       8 . The scheduler of  claim 6 , wherein n is decremented to adjust SF.  
   
   
       9 . A scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   wherein the scheduler is adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D>R; and  
 increase SF if the incremented counter exceeds a threshold.  
   
   
   
       10 . A scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   wherein the scheduler is adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented counter exceeds a threshold.  
   
   
   
       11 . A scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   wherein the scheduler is adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a first counter if the comparison of the distance D to the range R determines that D>R;  
 increase SF if the incremented first counter exceeds a first threshold;  
 increment a second counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented second counter exceeds a second threshold.  
   
   
   
       12 . A scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   wherein the scheduler is adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R; and  
 increase SF if the distance D exceeds the range R.  
   
   
   
       13 . A scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   wherein the scheduler is adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increase SF if the distance D exceeds the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented counter exceeds a threshold.  
   
   
   
       14 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
   the computer program product comprising:    a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D>R; and  
 increase SF if the incremented counter exceeds a threshold.  
   
   
   
       15 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
 the computer program product comprising:  
   a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented counter exceeds a threshold.  
   
   
   
       16 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
 the computer program product comprising:  
   a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increment a first counter if the comparison of the distance D to the range R determines that D>R;  
 increase SF if the incremented first counter exceeds a first threshold;  
 increment a second counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented second counter exceeds a second threshold.  
   
   
   
       17 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
 the computer program product comprising:  
   a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R; and  
 increase SF if the distance D exceeds the range R.  
   
   
   
       18 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
 the computer program product comprising:  
   a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R;  
 increase SF if the distance D exceeds the range R;  
 increment a counter if the comparison of the distance D to the range R determines that D<R/2; and  
 decrease SF if the incremented counter exceeds a threshold.  
   
   
   
       19 . A computer program product for use with a scheduler for a network processor, the scheduler including: 
 a scheduling queue in which weighted fair queuing is applied, the scheduling queue having a range R, flows being attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being calculated for each flow according to the formula D=((WF×FS)/SF), where: 
 WF is a weighting factor applicable to a respective flow;  
 FS is a frame size attributable to the respective flow; and  
 SF is a scaling factor;  
 the computer program product comprising:  
   a medium readable by a computer, the computer readable medium having computer program code adapted to: 
 calculate the distance D with respect to a particular flow to be enqueued;  
 compare the distance D to the range R; and  
 adjust the scaling factor SF based on a result of the comparison of the distance D to the range R.