Method and apparatus for weighted fair queuing

1. A method of serving a plurality of input queues that store packets of data traffic to be transmitted, said data traffic stored in fixed-size units of storage in the input queues, said method comprising the steps of:

associating a credit count with each of said plurality of input queues;

maintaining a service queue containing a list of input queues that have a positive credit count and which have data traffic stored therein to be transmitted;

selecting one of the input queues from the service queue to be served;

transmitting data from one of the said fixed-size units of storage of the input queue selected to be served;

reducing, by a predetermined quantity, said credit count associated with the input queue selected to be served; and

determining whether further fixed-size units of storage are to be transmitted from the input queue selected to be served.

2. The method of claim 1 , wherein, if it is determined that further fixed-size units of storage are to be transmitted from the input queue selected to be served, the method further comprises the step of repeating the steps of transmitting, reducing and determining until it is determined that further fixed-size units of storage are not to be transmitted from the input queue selected to be served.

3. The method of claim 2 , wherein the step of determining comprises determining whether the fixed-size unit of storage that was most recently transmitted is the last fixed-size unit of storage associated with a variable length packet.

4. The method of claim 1 , wherein the step of determining results in a negative determination while the method is operating in an interleave mode.

5. The method of claim 1 , further comprising the steps of:

selecting at least one of the other input queues to receive credits that were reduced from the selected input queue; and

increasing, by said predetermined quantity, an associated credit count of the at least one other input queue selected to receive credits such that credits are not created or destroyed but rather moved between input queues as used.

6. The method of claim 1 , wherein the service queue contains an ordered list of identities of input queues that have a positive credit count and which have data traffic stored therein to be transmitted, and wherein the step of selecting one of the input queues from the service queue to be served comprises selecting an input queue that is at a head-end of the ordered list.

7. The method of claim 6 , the method further comprising the steps of determining whether the input queue selected to be serviced should be removed from the service queue after being served, or if the identity of the input queue selected to be serviced should be placed at a tail-end of the ordered list of identities of input queues contained in the service queue after being served.

8. The method of claim 7 , wherein the identity of the input queue selected to be serviced will be placed at a tail-end of the ordered list of identities of input queues contained in the service queue after being served if the input queue selected to be serviced continues to have data to be serviced and continues to have a positive credit count after the method has completed transmitting data from the fixed size units of storage and the step of determining has resulted in a determination that further fixed-size units of storage are not to be transmitted from the input queue selected to be served.

9. A scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted, said data traffic stored in fixed-size units of storage in the input queues, said scheduler adapted to:

associate a credit count with each of said plurality of input queues;

maintain a service queue containing a list of input queues that have a positive credit count and which have data traffic stored therein to be transmitted;

select one of the input queues from the service queue to be served;

transmit data from one of the said fixed-size units of storage of the input queue selected to be served;

reduce, by a predetermined quantity, said credit count associated with the input queue selected to be served; and

determine whether further fixed-size units of storage are to be transmitted from the input queue selected to be served.

10. A scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted, said data traffic stored in fixed-size units of storage in the input queues, said scheduler comprising:

means for associating a credit count with each of said plurality of input queues;

means for maintaining a service queue containing a list of input queues that have a positive credit count and which have data traffic stored therein to be transmitted;

means for selecting one of the input queues from the service queue to be served;

means for transmitting data from one of the said fixed-size units of storage of the input queue selected to be served;

means for reducing, by a predetermined quantity, said credit count associated with the input queue selected to be served; and

means for determining whether further fixed-size units of storage are to be transmitted from the input queue selected to be served.

11. A tangible computer readable medium containing computer-executable instructions which, when performed by a processor in a scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted and input queue schedulers associated with other queues of data to be transmitted, said data traffic stored in fixed-size units of storage, cause the processor to:

associate a credit count with each of said plurality of input queues and input queue schedulers;

maintain a service queue containing a list of input queues and input queue schedulers that have a positive credit count and which have data traffic stored therein or associated therewith to be transmitted;

select one of the input queues or input queue schedulers from the service queue to be served;

transmit data from one of the said fixed-size units of storage of the input queue selected to be served or from the input queue scheduler selected to be served;

reduce, by a predetermined quantity, said credit count associated with the input queue selected to be served or the input queue scheduler selected to be served; and

determine whether further fixed-size units of storage are to be transmitted from the input queue selected to be served or from the input queue scheduler selected to be served.

12. A method of distributing credits among a plurality of input queues that store packets of data traffic to be transmitted, said method comprising:

maintaining an active credit queue containing an ordered list of input queues that require credits and are eligible to receive credits during a current round of credit distribution;

maintaining a waiting credit queue containing an ordered list of input queues that require credits but are ineligible to receive credits until the next round of credit distribution;

obtaining a credit from a first of the input queues in connection with transmission of data from the first input queue;

selecting a second of the input queues from the active credit queue; and

increasing, by a predetermined quantity, a credit management count of the second of the input queues.

13. The method of claim 12 , wherein the active credit queue contains an ordered list of identifiers of the input queues, and wherein the second of the input queues is selected by selecting an identifier at a head end of the active credit queue.

14. The method of claim 12 , further comprising the step of determining if the credit management count of the second of the input queues is equal to or greater than a weight of the second input queue and, if so removing the second of the input queues from the active credit queue and placing the second input queue in the waiting credit queue.

15. The method of claim 12 , further comprising the step of determining if the credit management count of the second of the input queues is less than a weight of the second input queue and, if so, moving the second of the input queues to a tail end of the active credit queue.

16. The method of claim 14 , further comprising the step of, after the step of removing the second of the input queues from the active credit queue, determining whether the active credit queue is empty.

17. The method of claim 16 , further comprising the step of, if the active credit queue is empty, swapping the waiting credit queue for the active credit queue so that the waiting credit queue is considered to be the active credit queue.

18. A scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted, said data traffic stored in fixed-size units of storage, said scheduler adapted to:

maintain an active credit queue containing an ordered list of input queues that require credits and are eligible to receive credits during a current round of credit distribution;

maintain a waiting credit queue containing an ordered list of input queues that require credits but are ineligible to receive credits until the next round of credit distribution;

obtain a credit from a first of the input queues in connection with transmission of data from the first input queue;

select a second of the input queues from the active credit queue; and

increase, by a predetermined quantity, a credit management count of the second of the input queues.

19. A scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted, said data traffic stored in fixed-size units of storage, said scheduler comprising:

means for maintaining an active credit queue containing an ordered list of input queues that require credits and are eligible to receive credits during a current round of credit distribution;

means for maintaining a waiting credit queue containing an ordered list of input queues that require credits but are ineligible to receive credits until the next round of credit distribution;

means for obtaining a credit from a first of the input queues in connection with transmission of data from the first input queue;

means for selecting a second of the input queues from the active credit queue; and

means for increasing, by a predetermined quantity, a credit management count of the second of the input queues.

20. A tangible computer readable medium containing computer-executable instructions which, when performed by a processor in a scheduler adapted to serve a plurality of input queues that store packets of data traffic to be transmitted and input queue schedulers associated with other queues of data to be transmitted, said data traffic stored in fixed-size units of storage, cause the processor to:

maintaining an active credit queue containing an ordered list of input queues and input queue schedulers that require credits and are eligible to receive credits during a current round of credit distribution;

maintaining a waiting credit queue containing an ordered list of input queues and input queue schedulers that require credits but are ineligible to receive credits until the next round of credit distribution;

obtaining a credit from a first of the input queues or input queue schedulers in connection with transmission of data from the first input queue;

select a second of the input queues or input queue schedulers from the active credit queue; and

increase, by a predetermined quantity, a credit management count of the selected input queue or input queue schedulers.