Method and system for scheduling requests in a non-first in first out (FIFO) order in a network

• US 7,908,396 B2
• Filed: 11/30/2005
• Issued: 03/15/2011
• Est. Priority Date: 11/30/2005
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola Mobility, Inc. (Lenovo Group Ltd.)
• Inventors: Jayapalan, Jay P., Agrawal, Rajeev, Kalyanasundaram, Suresh, Vukovic, Ivan N.
• Primary Examiner(s): Lin; Kenny S
• Assistant Examiner(s): Khajuria; Shripal K
• Application Number:
  US11/289,970
• Publication Number:
  US 20070124735A1
• Time in Patent Office: 1,931 Days
• Field of Search: 709/240, 709/238
• US Class Current: 709/240
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 88/12 Access point controller devices

Abstract

A method and a system for scheduling requests generated for a plurality of mobile devices in a communication network (100) has been disclosed. The requests are generated for a transmission opportunity. The method includes computing a sort metric (302) for each request, based on an information update. A lead-time is then computed (304) with respect to a drop-dead time for each request, based on the sort metric for a time slice. The drop-dead time for a given time slice is the time before which scheduling has to be done so that data can be transmitted during the given time slice. Each request may be considered (306) for allocation in the time slice before the beginning of a next time slice, based on the lead-time.

Claims

1. A method for scheduling requests generated for a plurality of mobile devices in a communication network, the requests being generated for a transmission opportunity, the method comprising:

computing a sort metric for each request based on an information update, wherein the sort metric represents a priority associated with each request;

computing a lead-time for each request based on the sort metric for a time slice wherein the lead-time is a time when each request is considered for allocation in the time slice before the beginning of a next time slice, the lead-time being computed with respect to a drop-dead time of the time slice, wherein the drop-dead time is a time before which scheduling has to be completed so that data can be transmitted during the time slice and wherein each request becomes eligible for processing after a unit of time determined by (T-S)/N where T is a duration of the time slice, S is the duration of a slack time during which a request is not eligible for processing and N is a number of requests; and

considering each request for allocation in the time slice before the beginning of a next time slice such that the request is considered for allocation within a time interval equal to a difference between the drop-dead time and the lead-time for the request.

2. The method according to claim 1, wherein each request is considered for allocation before the drop-dead time of the time slice.

3. The method according to claim 1 further comprising:

forwarding each request to a plurality of Base Transceiver Stations (BTSs) in the communication network, wherein the request is forwarded by at least one Base Station Controller (BSC) in the communication network; and

sending the information update to the plurality of BTSs.

4. The method according to claim 3, wherein the information update is sent by one of:

the BSC and the plurality of mobile devices.

5. The method according to claim 1, wherein considering each requests comprises allocating the transmission opportunity and, optionally, a data rate to the plurality of mobile devices, the allocation being done by the plurality of BTSs.

6. The method according to claim 5, wherein each request with a larger lead-time in the time slice is allocated the transmission opportunity ahead of each request with a lower lead-time in the time slice.

7. The method according to claim 5, wherein allocating the transmission opportunity comprises:

sending the allocations to the BSC, the allocations being sent by each BTS;

determining a final allocation for each mobile device, wherein the BSC determines the final allocation, the final allocation being least of each allocation sent by each BTS for each mobile device; and

sending the final allocation to each BTS.

8. The method according to claim 1, wherein computing the lead-time comprises:

determining a bottleneck resource; and

computing the lead-time based on the bottleneck resource.

9. The method according to claim 1, wherein the information update for computing the sort metric comprises:

the radio condition of channels of the plurality of mobile devices;

the quality of service requested by the plurality of mobile devices; and

an existing data rate received by the plurality of mobile devices.

10. The method according to claim 9, wherein the radio condition of channels comprises radio condition of channels in one or more Soft Handoff (SHO) legs of the plurality of mobile devices.

11. A method for scheduling requests generated for a plurality of mobile devices in a communication network, the request being generated for a transmission opportunity, the method comprising:

forwarding each request to a plurality of Base Transceiver Stations (BTSs) in the communication network;

sending an information update to the plurality of BTSs;

computing a sort metric for each request based on the information update, wherein the sort metric represents a priority associated with each request;

computing a lead-time for each request based on the sort metric for a time slice wherein the lead-time is a time when each request is considered for allocation in the time slice before the beginning of a next time slice, the lead-time being computed with respect to a drop-dead time of the time slice, wherein the drop-dead time is a time before which scheduling has to be completed so that data can be transmitted during the time slice and wherein each request becomes eligible for processing after a unit of time determined b¥

(T-S)/N where T is a duration of the time slice, S is the duration of a slack time during which a request is not eligible for processing and N is a number of requests; and

considering each request for allocation in the time slice before the beginning of a next time slice such that the request is considered for allocation within a time interval equal to a difference between the drop-dead time and the lead-time for the request.

12. The method according to claim 11, wherein the information update is sent by one of:

the BSC and the plurality of mobile devices.

13. The method according to claim 11, wherein each request is considered for allocation before the drop-dead time of the time slice.

14. The method according to claim 11, wherein considering each request comprises allocating the transmission opportunity and optionally, a data rate to the plurality of mobile devices, the allocation being done by the plurality of BTSs.

15. The method according to claim 14, wherein each request with a larger lead-time in the time slice is allocated the transmission opportunity ahead of each request with a lower lead-time in the time slice.

16. The method according to claim 14, wherein allocating the transmission opportunity comprises:

sending the allocations to the BSC, the allocations being sent by each BTS;

determining a final allocation for each mobile device, wherein the BSC determines the final allocation, the final allocation being least of each allocation sent by each BTS for each mobile device; and

sending the final allocation to each BTS.

17. The method according to claim 11, wherein computing the lead-time comprises:

determining a bottleneck resource; and

computing the lead-time based on the bottleneck resource.

18. The method according to claim 11, wherein the information update comprises:

the radio condition of channels of the plurality of mobile devices;

the quality of service requested by the plurality of mobile devices; and

an existing data rate received by the plurality of mobile devices.

19. The method according to claim 18, wherein the radio condition comprises radio condition of one or more Soft Handoff (SHO) legs of the plurality of mobile devices.

20. A system for scheduling requests generated for a plurality of mobile devices in a communication network, the system comprising:

a plurality of Base Transceiver Stations (BTSs) that are capable of receiving requests, the requests being generated for a transmission opportunity wherein the BTS comprise a time slice module that is capable of computing a lead-time for each request based on a sort metric and a scheduler capable of scheduling the requests based on the lead-time such that each request with a larger lead-time in a time slice is considered for allocation of a transmission opportunity ahead of each request with a lower lead-time in the time slice and within a time interval equal to a difference between a drop-dead time of the time slice and the lead-time of the requests such that the request is allocated before the drop-dead time and wherein the lead-time is a time when each request is considered for allocation in the time slice before the beginning of a next time slice and the drop-dead time is a time before which scheduling has to be completed so that data can be transmitted during the time slice, wherein a slack time is provided before processing the requests when at least one of the plurality of BTSs lacks required processing power, the plurality of BTSs further being capable of receiving an information update from the plurality of mobile devices and wherein each request becomes eligible for processing after a unit of time determined by (T-S)/N where T is a duration of the time slice, S is the duration of a slack time during which a request is not eligible for processing and N is a number of requests; and

a Base Station Controller (BSC) the BSC being capable of computing the sort metric based on the information update, wherein the sort metric represents a priority associated with each request, the information update being sent by the plurality of BTSs.

21. The system according to claim 20, wherein the information update for computing the sort metric comprises:

the radio condition of channels of the plurality of mobile devices;

the quality of service requested by the plurality of mobile devices; and

an existing data rate received by the plurality of mobile devices.

22. The system according to claim 20, wherein each of the plurality of BTSs comprises a bottleneck detector, the bottleneck detector determining a bottleneck resource, the bottleneck resource being used in computing the lead-time.

23. The system according to claim 20, wherein the time slice module is further capable of computing the sort metric for each request based on the information update.

24. The system according to claim 20, wherein each of the plurality of BTSs comprises a radio frequency load module that is capable of sending periodic updates to the BSC, the periodic updates being information about channel conditions of the each of the plurality of mobile devices.