High-throughput scheduler with guaranteed fairness for wireless networks and other applications

1. A method for scheduling data blocks for transmission from a plurality of transmission elements in timeslots of a given frame in a communication system, the method comprising:

designating each of the plurality of transmission elements as eligible to transmit one or more of the data blocks in the given frame;

selecting from those of the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame at least one of the plurality of transmission elements for scheduling in a next available timeslot;

adjusting eligibility status of the selected at least one of the plurality of transmission elements, wherein the adjusting step comprises designating the selected at least one of the plurality of transmission elements as ineligible to transmit one or more additional data blocks in the given frame; and

repeating the selecting and adjusting steps for one or more remaining timeslots of the given frame;

wherein the designating, selecting and adjusting steps are performed by a scheduler coupled to the plurality of transmission elements;

wherein selecting at least one of the plurality of transmission elements for scheduling in the next available timeslot further comprises selecting from those of the plurality of transmission elements designated as eligible at least one of the plurality of transmission elements having a highest channel capacity; and

wherein the highest channel capacity comprises a highest relative channel capacity, with the highest relative channel capacity being determined as a ratio of an absolute channel capacity and an average channel capacity.

2. The method of claim 1 wherein an eligibility status for a given selected transmission element comprises a binary eligibility indicator having an eligible state and an ineligible state.

3. The method of claim 2 wherein adjusting eligibility status of the selected transmission element(s) further comprises changing the binary eligibility indicator for the given selected transmission element from the eligible state to the ineligible state.

4. The method of claim 1 wherein an eligibility status for a given selected transmission element comprises an eligible number.

5. The method of claim 4 wherein designating each of the plurality of the transmission elements as eligible to transmit one or more data blocks in the given frame further comprises designating eligible numbers for respective ones of the plurality of the transmission elements.

6. The method of claim 5 wherein the designated eligible numbers for the respective transmission elements comprise weights assigned to the respective ones of the plurality of the transmission elements.

7. The method of claim 4 wherein adjusting eligibility status of the selected transmission element(s) further comprises altering the eligible number of the given selected transmission element.

8. The method of claim 7 wherein adjusting eligibility status of the selected transmission element(s) further comprises decrementing the eligible number of the given selected transmission element by one.

9. The method of claim 1 further comprising performing the designating, selecting, adjusting and repeating steps for at least one additional frame.

10. The method of claim 9 wherein the designating step as performed for each of the frames comprises initially designating each of the transmission elements as eligible to transmit one or more data blocks in that frame.

11. The method of claim 1 wherein the highest relative channel capacity is determined based on r i / r i , where r i is the absolute channel capacity of user i and r i is the average channel capacity of user i.

12. The method of claim 1 wherein the selecting step comprises:

selecting two or more of the plurality of transmission elements to be served simultaneously in the next available timeslot; and

assigning respective codes to the selected two or more of the plurality of transmission elements.

13. A method for scheduling data blocks for transmission from a plurality of transmission elements in timeslots of a given frame in a communication system, the method comprising:

designating each of the plurality of transmission elements as eligible to transmit one or more of the data blocks in the given frame;

selecting from those of the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame at least one of the plurality of transmission elements for scheduling in a next available timeslot;

adjusting eligibility status of the selected at least one of the plurality of transmission elements;

adding a new transmission element during the given frame to the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame;

repeating the selecting and adjusting steps for one or more remaining timeslots of the given frame;

wherein the designating, selecting and adjusting steps are performed by a scheduler coupled to the plurality of transmission elements, and

wherein the new transmission element is added during a t-th timeslot of the given frame and wherein an eligible number of the new transmission element in the given frame is determined based at least in part on t, and the eligible number indicates eligibility status of the new transmission element.

14. The method of claim 13 wherein the new transmission element has an assigned weight of w and the eligible number of the new transmission element in the given frame is determined based at least in part on w, t and F, where F is frame length in timeslots.

15. The method of claim 13 wherein the eligible number of the new transmission element in the given frame is determined at least in part as a function of a ratio between t and F, where F is frame length in timeslots.

16. The method of claim 13 wherein the new transmission element has an assigned weight of w and the eligible number of the new transmission element in the given frame is determined based at least in part on w*(F−t)/F, where F is frame length in timeslots.

17. A method for scheduling data blocks for transmission from a plurality of transmission elements in timeslots of a given frame in a communication system, the method comprising:

designating each of the plurality of transmission elements as eligible to transmit one or more of the data blocks in the given frame;

selecting from those of the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame at least one of the plurality of transmission elements for scheduling in a next available timeslot;

adjusting eligibility status of the selected at least one of the plurality of transmission elements;

repeating the selecting and adjusting steps for one or more remaining timeslots of the given frame; and

adding a new transmission element to the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame;

wherein the new transmission element has an assigned weight of w and is added in conjunction with a t-th timeslot of the given frame and an eligible number of the new transmission element is determined based on m+f=w*(F−t)/F, where F is frame length in timeslots, t is an integer, m is an integer and f is a fraction 0<=f<1;

wherein the designating, selecting and adjusting steps are performed by a scheduler coupled to the plurality of transmission elements.

18. An apparatus for scheduling data blocks for transmission from a plurality of transmission elements in timeslots of a given frame in a communication system, the apparatus comprising:

a scheduler coupled to the plurality of transmission elements;

the scheduler being adapted to designate each of the plurality of transmission elements as eligible to transmit one or more of the data blocks in the given frame; to select from those of the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame at least one of the plurality of transmission elements for scheduling in a next available timeslot; to adjust eligibility status of the selected at least one of the plurality of transmission elements; and to repeat the selection and adjustment for one or more remaining timeslots of the given frame;

wherein the scheduler adjusts the eligibility status of the selected at least one of the plurality of transmission elements by designating the selected at least one of the plurality of transmission elements as ineligible to transmit one or more additional data blocks in the given frame;

wherein the scheduler selects at least one of the plurality of transmission elements for scheduling in the next available timeslot by selecting from those of the plurality of transmission elements designated as eligible at least one of the plurality of transmission elements having a highest channel capacity; and

wherein the highest channel capacity comprises a highest relative channel capacity, with the highest relative channel capacity being determined as a ratio of an absolute channel capacity and an average channel capacity.

19. The apparatus of claim 18 wherein the scheduler comprises scheduling circuitry implemented in a processing device of the communication system.

20. The apparatus of claim 19 wherein the processing device comprises a network processor integrated circuit.

21. An integrated circuit comprising:

a processing device having a scheduler configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a given frame;

the scheduler being coupled to the plurality of transmission elements;

the scheduler being adapted to designate each of the plurality of transmission elements as eligible to transmit one or more of the data blocks in the given frame; to select from those of the plurality of transmission elements designated as eligible to transmit the one or more data blocks in the given frame at least one of the plurality of transmission elements for scheduling in a next available timeslot; to adjust eligibility status of the selected at least one of the plurality of transmission elements; and to repeat the selection and adjustment for one or more remaining timeslots of the given frame;

wherein the scheduler adjusts the eligibility status of the selected at least one of the plurality of transmission elements by designating the selected at least one of the plurality of transmission elements as ineligible to transmit one or more additional data blocks in the given frame;

wherein the scheduler selects at least one of the plurality of transmission elements for scheduling in the next available timeslot by selecting from those of the plurality of transmission elements designated as eligible at least one of the plurality of transmission elements having a highest channel capacity; and

wherein the highest channel capacity comprises a highest relative channel capacity, with the highest relative channel capacity being determined as a ratio of an absolute channel capacity and an average channel capacity.