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

• US 20070124735A1
• Filed: 11/30/2005
• Published: 05/31/2007
• 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: Agrawal, Rajeev, Kalyanasundaram, Suresh, Jayapalan, Jay, Vukovic, Ivan
• Granted Patent: US 7,908,396 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• 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;

computing a lead-time for each request based on the sort metric for a time slice, the lead-time being computed with respect to a drop-dead time of the time slice; and

considering each request for allocation in the time slice before the beginning of a next time slice based on the lead-time.

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, wherein each request is considered for allocation, within a time interval equal to the difference between the drop-dead time and the lead-time for the request, such that the request is allocated before the drop-dead time.

4. 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.

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

the BSC and the plurality of mobile devices.

6. 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.

7. The method according to claim 6, 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.

8. The method according to claim 6, 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.

9. 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.

10. 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.

11. The method according to claim 10, 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.

12. 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;

computing a lead-time for each request for a time slice based on the sort metric, the lead-time being computed with respect to a drop-dead time of the time slice; and

considering each request for allocation in the time slice before the beginning of a next time slice based on the lead-time.

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

the BSC and the plurality of mobile devices.

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

15. The method according to claim 12, wherein each request is considered for allocation within a time interval equal to the difference between the drop-dead time and the lead-time for the request, such that the request is allocated before the drop-dead time.

16. The method according to claim 12, 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.

17. The method according to claim 16, 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.

18. The method according to claim 16, 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.

19. The method according to claim 12, wherein computing the lead-time comprises:

determining a bottleneck resource; and

computing the lead-time based on the bottleneck resource.

20. The method according to claim 12, 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.

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

22. 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, the plurality of BTSs further being capable of receiving an information update from the plurality of mobile devices; and

a Base Station Controller (BSC) the BSC being capable of computing a sort metric based on the information update, the information update being sent by the plurality of BTSs.

23. The system according to claim 22, 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.

24. The system according to claim 22, wherein each of the plurality of BTSs comprises a time slice module that is capable of computing a lead-time for each request based on the sort metric.

25. The system according to claim 24, 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.

26. The system according to claim 24, wherein the time slice module comprises 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.

27. The system according to claim 26, wherein the scheduler considers the requests for scheduling 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.

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

29. The system according to claim 22, 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.