Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler

Abstract

In a first aspect, a network processor includes a scheduler in which a scheduling queue is maintained. A last frame is dispatched from a flow queue maintained in the network processor, thereby emptying the flow queue. Data indicative of the size of the dispatched last frame is stored in association with the scheduler. A new frame corresponding to the emptied flow queue is received, and the flow corresponding to the emptied flow queue is attached to the scheduling queue. The flow is attached to the scheduling queue at a distance D from a current pointer for the scheduling queue. The distance D is determined based at least in part on the stored data indicative of the size of the dispatched last frame.

1. A method of operating a network processor, comprising:
 dispatching a last frame from a flow queue maintained in the network processor, thereby emptying the flow queue; 
 storing data indicative of a size of the dispatched last frame; 
 receiving a new frame corresponding to the emptied flow queue; and 
 attaching to a scheduling queue a flow corresponding to the emptied flow queue; 
 wherein the flow is attached to the scheduling queue a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the dispatched last frame. 
 
   
   
     2. The method of  claim 1 , wherein the distance D is determined based in part on a Quality of Service to which the flow is entitled. 
   
   
     3. The method of  claim 1 , wherein the data indicative of the size of the dispatched last frame is stored in a flow queue control block which corresponds to the emptied flow queue. 
   
   
     4. The method of  claim 3 , wherein the flow queue control block is stored in a random access memory associated with a scheduler. 
   
   
     5. A network processor, comprising:
 a scheduler which includes a scheduling queue having flows attached thereto and defining a sequence in which the attached flows are to be serviced; and 
 storage means, associated with the scheduler, for maintaining a flow queue corresponding to each flow attached to the scheduling queue; 
 wherein the storage means stores, for each flow queue that has been emptied, data indicative of a last frame dispatched from the respective flow queue, and 
 wherein when a new frame is received that corresponds to a flow queue that has been emptied, a flow corresponding to the new frame is attached to the scheduling queue at a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the last frame dispatched from the flow queue that has been emptied. 
 
   
   
     6. The network processor of  claim 5 , wherein the distance D is determined based in part on a Quality of Service to which the flow is entitled. 
   
   
     7. The network processor of  claim 5 , wherein the data indicative of the size of the last frame dispatched from the respective flow queue is stored in a flow queue control block which corresponds to the respective flow queue. 
   
   
     8. The network processor of  claim 5 , wherein the storage means includes a random access memory. 
   
   
     9. A computer program product for use with a network processor, the computer program product comprising:
 a computer storage device readable by a computer, the computer storage device having program code adapted to: 
 dispatch a last frame from a flow queue to empty the flow queue; 
 store in a flow queue control block which corresponds to the emptied flow queue data indicative of a size of the dispatched last frame; 
 receive a new frame corresponding to the emptied flow queue; and attach to a scheduling queue a flow corresponding to the emptied flow queue; wherein the flow is attached to the scheduling queue a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the dispatched last frame. 
 
   
   
     10. A method of operating a network processor, comprising:
 dispatching a last frame from a flow queue maintained in the network processor, thereby emptying the flow queue; 
 storing in a flow queue control block which corresponds to the emptied flow queue data indicative of a size of the dispatched last frame; 
 receiving a new frame corresponding to the emptied flow queue; and 
 attaching to a scheduling queue a flow corresponding to the emptied flow queue; 
 wherein the flow is attached to the scheduling queue a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the dispatched last frame. 
 
   
   
     11. A network processor, comprising: a scheduler which includes a scheduling queue having flows attached thereto and defining a sequence in which the attached flows are to be serviced;
 storage means, associated with the scheduler, for maintaining a flow queue corresponding to each flow attached to the scheduling queue; 
 means for dispatching a last frame from a flow queue maintained in the storage means, thereby emptying the flow queue; 
 means for storing, in a flow queue control block which corresponds to the emptied flow queue, data indicative of a size of the dispatched last frame; 
 means for receiving a new frame corresponding to the emptied flow queue; and 
 means for attaching to the scheduling queue a flow corresponding to the emptied flow queue; 
 wherein the flow is attached to the scheduling queue a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the dispatched last frame. 
 
   
   
     12. A computer program product for use with a network processor, the computer program product comprising:
 a medium readable by a computer, the computer readable medium having program code adapted to:
 dispatch a last frame from a flow queue maintained in a network processor, thereby emptying the flow queue; 
 store in a flow queue control block which corresponds to the emptied flow queue data indicative of a size of the dispatched last frame; 
 receive a new frame corresponding to the emptied flow queue; and 
 attach to a scheduling queue a flow corresponding to the emptied flow queue; 
 
 wherein the flow is attached to the scheduling queue a distance D from a current pointer for the scheduling queue, the distance D being determined based at least in part on the stored data indicative of the size of the dispatched last frame.