Wireless network scheduling methods and apparatus based on both waiting time and occupancy

• US 20070253425A1
• Filed: 05/01/2006
• Published: 11/01/2007
• Est. Priority Date: 05/01/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Li, Jinhui, Hamilton, Christopher, Severns-Williams, Christine, Kucuk, Noy
• Granted Patent: US 7,769,038 B2
• Time in Patent Office: Days
• US Class Current: 370/395.400
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

A scheduler is adapted to schedule packets or other data blocks for transmission from a plurality of transmission elements in timeslots in a communication system. The scheduler determines scaled capacity measures for respective ones of the transmission elements, with each of the scaled capacity measures being scaled by a combination of a waiting time and an occupancy for a corresponding one of the transmission elements. The scheduler selects one or more of the transmission elements for scheduling in a given one of the timeslots based on the scaled capacity measures. The scheduler in an illustrative embodiment may be implemented in a network processor integrated circuit or other processing device of the communication system.

Claims

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

determining for the transmission elements respective scaled capacity measures, each of said scaled capacity measures being scaled by a combination of a waiting time and an occupancy for a corresponding one of the transmission elements; and

selecting one or more of the transmission elements for scheduling in a given one of the timeslots based on the scaled capacity measures.

2. The method of claim 1 wherein the transmission elements comprise respective queues.

3. The method of claim 1 wherein the determining and selecting steps are repeated for one or more additional timeslots.

4. The method of claim 1 wherein the scaled capacity measures are given by (α

_iW_i+β

_iO_i)r_i, for values of i=1 to N, where N denotes the number of transmission elements, α

_i and β

_i are constants for transmission element i, W_i is the waiting time of a particular data block of transmission element i, O_i is the occupancy of the transmission element i, and r_i is channel capacity of transmission element i.

5. The method of claim 4 wherein transmission element i comprises a queue, and W_i is the waiting time of a head-of-line packet in queue i.

6. The method of claim 1 wherein the scaled capacity measures are given by (α

_iΔ

_i+β

_i)O_ir_i, for values of i=1 to N, where N denotes the number of transmission elements, α

_i and β

_i are constants for transmission element i, Δ

_i is the waiting time of transmission element i, O_i is the occupancy of the transmission element i, and r_i is channel capacity of transmission element i.

7. The method of claim 6 wherein Δ

_i is defined as T_c-T_last, where T_c is a current time and T_last is a latest time when transmission element i is scheduled.

8. The method of claim 1 wherein the scaled capacity measures are given by (α

_iΔ

_iO_ir_i), for values of i=1 to N, where N denotes the number of transmission elements, α

_i is a constant for transmission element i, Δ

_i is the waiting time of transmission element i, O_i is the occupancy of the transmission element i, and r_i is channel capacity of transmission element i.

9. The method of claim 8 wherein Δ

_i is defined as T_c-T_last, where T_c is a current time and T_last is a latest time when transmission element i is scheduled.

10. The method of claim 1 wherein the timeslots comprises HSDPA timeslots.

11. The method of claim 1 wherein two or more of the transmission elements are selected for scheduling in the given timeslot based on said selected transmission elements having substantially the same scaled capacity measures, said selected transmission elements all being scheduled in the given timeslot by assigning different subsets of a set of available codes to different ones of said selected transmission elements.

12. The method of claim 11 wherein the set of available codes comprises a set of HSDPA codes.

13. The method of claim 11 wherein the set of available codes comprises a set of codes assigned to an HS-DSCH channel of the system.

14. The method of claim 1 wherein the timeslots comprise timeslots of a frame.

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

a scheduler coupled to the transmission elements;

the scheduler being adapted to determine for the transmission elements respective scaled capacity measures, each of said scaled capacity measures being scaled by a combination of a waiting time and an occupancy for a corresponding one of the transmission elements, and to select one or more of the transmission elements for scheduling in a given one of the timeslots based on the scaled capacity measures.

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

17. The apparatus of claim 16 wherein the processing device comprises a network processor integrated circuit.

18. 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 in a communication system;

the scheduler being coupled to the transmission elements;

the scheduler being adapted to determine for the transmission elements respective scaled capacity measures, each of said scaled capacity measures being scaled by a combination of a waiting time and an occupancy for a corresponding one of the transmission elements, and to select one or more of the transmission elements for scheduling in a given one of the timeslots based on the scaled capacity measures.

19. The integrated circuit of claim 18 further comprising memory circuitry associated with said processing device and adapted for storage of one or more of said scaled capacity measures.

20. The integrated circuit of claim 18 wherein the scheduler is implemented at least in part in the form of software running on the processing device.