Parallel adaptive quantile wireless scheduler

• US 7,796,551 B1
• Filed: 07/11/2007
• Issued: 09/14/2010
• Est. Priority Date: 07/11/2007
• Status: Expired due to Fees

• Current Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Machiraju, Sridhar, Zang, Hui, Bali, Soshant
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): Hwang; Stamford
• Application Number:
  US11/776,113
• Time in Patent Office: 1,161 Days
• Field of Search: 370/330, 370/329, 370/348, 455450-453
• US Class Current: 370/330
• CPC Class Codes: H04L 5/003 Arrangements for allocating sub-channels of the transmission path

Abstract

A method, medium, and wireless system are provided for scheduling access terminals to prevent starvation of other access terminals connected to a communication network. The wireless system includes access terminals and base stations that are configured with a first wireless scheduler and a parallel wireless scheduler that select access terminals to communicate during specified time slots. The access terminals measure channel conditions associated with communications to the base station and transmit requests that specify a desired communication rate to the base station. The wireless schedulers on each base station receive the requests from each access terminal and select an access terminal to communicate during a subsequent time slot that may be based on, for example, the channel conditions and a combination of the probability estimates associated with the communication rate and a faction of unallocated slots or a second fraction—corresponding to the access terminal—generated by either the first wireless scheduler or the parallel wireless scheduler.

Claims

1. One or more non-transitory computer-readable media having computer-useable instructions embodied thereon for performing a method to schedule time slots for communication associated with an access terminal, the method comprising:

receiving a request for a communication rate with one or more access terminals at a specified interval;

generating an estimated probability based on the communication rate for each access terminal;

counting a number of previous time slots to generate a first fraction that is based on a number of unallocated time slots for each access terminal;

storing, for each access terminal, the estimated probability and the first fraction of unallocated time slots;

selecting an access terminal, having a maximum value when evaluating a combination of the estimated probability and the first fraction that is based on the number of unallocated time slots, to communicate during a subsequent time slot;

for each access terminal, generating a second fraction based on the estimated probability associated with each access terminal; and

increasing the second fraction of the access terminal having a maximum combined value of a quantile estimated probability and the second fraction.

2. The media of claim 1, wherein the first fraction based on the number of unallocated time slots decreases when the access terminal is allocated a time slot.

3. The media of claim 1, wherein the estimated probability and the first fraction of unallocated slots are generated by a first wireless scheduler.

4. The media of claim 3, wherein the selected access terminal is chosen based on evaluations performed by the first wireless scheduler.

5. A wireless base station configured with a processor to perform a method for scheduling access terminals, the method comprising:

receiving a request for a communication rate with one or more access terminals at a specified interval;

generating an estimated probability based on the communication rate for each access terminal via a first wireless scheduler;

counting a number of previous time slots to generate a first fraction that is based on a number of unallocated time slots for each access terminal via the first wireless scheduler;

storing, for each access terminal, the estimated probability and the first fraction of unallocated time slots;

selecting an access terminal, having a maximum value when evaluating a combination of the estimated probability and the first fraction that is based on the number of unallocated time slots, to communicate during a subsequent time slot;

for each access terminal, generating a second fraction based on the estimated probability associated with each access terminal and storing the second fraction, wherein the second fraction is generated by a parallel wireless scheduler; and

increasing the second fraction of the access terminal having a maximum combined value of a selected estimated probability and the second fraction, and decreasing the second fraction of all remaining access terminals.

6. The method of claim 5, wherein the selected access terminal is chosen based on evaluations performed by the first wireless scheduler.

7. The method of claim 5, wherein the first fraction of unallocated time slots is reassigned using the second fraction maintained by the parallel wireless scheduler.

8. The method of claim 7, where the second fraction is assigned to the first fraction when an access terminal moves from an off state to an on state.

9. A wireless system to schedule time slots for access terminals, the wireless system comprising:

one or more access terminals to communicate over a communication network;

one or more base stations, each base station comprises a first wireless scheduler and a parallel wireless scheduler configured to select an access terminal from the one or more access terminals to communicate over the communication network for each time slot based on estimated probabilities and a first fraction generated by the first wireless scheduler; and

a storage device to store, for each time slot, the estimated probabilities generated by the first wireless scheduler, the first fraction generated by the first wireless scheduler and a second fraction generated by a parallel wireless scheduler for each access terminal;

wherein the first fraction of the first wireless scheduler is re-assigned using the second fraction of the parallel wireless scheduler.

10. The wireless system of claim 9, wherein the one or more base stations are channel-aware.

11. The wireless system of claim 9, wherein the one or more access terminals send requests that specify a desired communication rate to the base station.

12. The wireless system of claim 9, wherein one or more of the access terminals includes one of a laptop, a personal computer, a mobile phone, a personal digital assistant, or a smart phone.

13. The wireless system of claim 9, wherein one or more of the access terminals generate or receive bursty traffic or experience good channel conditions after a period of bad channel conditions.

14. The wireless system of claim 13, wherein the bursty traffic is packet traffic.