METHOD AND SYSTEM FOR SCHEDULING REQUESTS IN A NON-FIRST IN FIRST OUT

(FIFO) ORDER IN A NETWORK

Field of the Invention

The present invention relates generally to the field of communication networks. More specifically, the present invention relates to serving requests generated by a plurality of mobile devices in a communication network.

Background

A communication network includes a plurality of mobile devices, a plurality of Base Transceiver Stations (BTSs), and at least one Base Station Controller (BSC). Examples of mobile devices include cell phones, Personal Digital Assistants (PDAs), etc. In the downlink, the BSC generates requests for resources to transmit data to the mobile, and, in the uplink, the mobile devices generate the requests for resources to transmit data. The requests are sent to the BTSs, which may schedule the requests.

The request may be scheduled using a variety of methods including the weighted fair queuing method, the earliest-due-date method, the priority-queuing method and the shortest fair queuing method. In the shortest fair queuing method, each request is stamped with a start tag based on a pre-determined criteria. The requests are then served in an increasing order of the start tags associated with each request. The BTSs may schedule the requests from the mobile devices in a First In

First Out (FIFO) order. A request received first by the BTS may be given a higher priority for allocation of the resource than a request received later.

Alternately, the BTSs may schedule the requests in a non-FIFO order, such as based on a priority of the request. The priority of the request is determined by using one or more predetermined criteria. The BTSs receive the requests at different times and have to wait for a predetermined period so as to receive all requests for a time slice before scheduling these requests for the time slice. Thereafter, sorting is performed and the requests are scheduled and served in the next time slice.

One or more of the methods described above may suffer from one or more of the following limitations. Firstly, they do not operate in a distributed soft handoff

environment. Secondly, the requests served in the FIFO order do not take into account the priorities associated with the requests. Thirdly, for serving requests in the non- FIFO order the BTSs have to wait till a predetermined period of time to receive each request. Moreover, in a Soft Hand Off (SHO) environment, resources that have been allocated cannot be reallocated if they are greater than the final allocation for a mobile device. Lastly, the requests served in a non-FIFO order require high processing on the communication network.

Brief Description of the Figures

The accompanying figures, where like reference numerals refer to identical or functionally similar elements throughout the separate views and which together with the detailed description below are incorporated in and form part of the specification, serve to further illustrate various embodiments and to explain various principles and advantages all in accordance with the present invention.

FIG. 1 is a block diagram illustrating a communication network, in accordance with an exemplary embodiment of the present invention;

FIG. 2 is a block diagram illustrating the components of a Base Transceiver Station (BTS), in accordance with an embodiment of the present invention;

FIG. 3 is a flowchart illustrating a method for scheduling requests, in accordance with an embodiment of the present invention; FIG. 4 is a flowchart illustrating a method for determining the final allocation for a request in an SHO environment, in accordance with an embodiment of the present invention; and

FIG. 5 is a flowchart illustrating a method for allocating the transmission opportunity to a request, in accordance with another embodiment of the present invention.

Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.

Docket CE12658R 2

Detailed Description

Before describing in detail embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps and apparatus components related to scheduling requests in a non First In First Out (FIFO) order in a communication network. Accordingly, the apparatus components and method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.

The terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element proceeded by "comprises ...a" does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that comprises the element.

It will be appreciated that embodiments of the invention described herein may be comprised of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the functions of scheduling requests in a non first in first out order in a communication network described herein. The non-processor circuits may include, but are not limited to, a radio receiver, a radio transmitter, signal drivers, clock circuits, power source circuits, and user input devices. As such, these functions may be interpreted as steps of a method to perform scheduling requests in a non-first in first out order in a network. Alternatively, some or all functions could be implemented by a state machine that has no stored program instructions, or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic. Of course, a combination of the two approaches could

Docket CE12658R 3

be used. Thus, methods and means for these functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.

A method and system for scheduling requests generated for a plurality of mobile devices in a communication network is disclosed. The requests are generated by a Base Station Controller (BSC) for downlink transmission and by the plurality of mobile devices for uplink transmission. These requests are generated for a transmission opportunity at a determined data rate for the plurality of mobile devices. The method involves computing a sort metric for each request based on an information update. The sort metric associated with a request represents a priority associated with the request. The sort metric is used by a plurality of Base Transceiver Stations (BTSs) to compute a lead-time for each request in a time slice. Based on the lead-time, each request is considered for allocation in the time slice before the beginning of the next time slice.

FIG. 1 is a block diagram illustrating a communication network 100, in accordance with an exemplary embodiment of the present invention. The communication network 100 includes a Base Station Controller (BSC) 102, a mobile device 104, a mobile device 106, a Base Transceiver Stations (BTS) 108 and a BTS 110. As understood by those skilled in the art, the network 100 may include multiple BTSs, BSCs, and a plurality of mobile devices. Examples of the mobile devices 104 and 106 include cell phones, Personal Digital Assistants (PDAs), and the like. The mobile devices 104 and 106 are capable of communicating with the BTSs 108 and 110, which then communicates with the BSC 102. During a Down Link (DL) transmission of data, which is the transmission of data from the BSC to a mobile device, the BSC 102 monitors the current buffer occupancy of the data buffered at the BSC 102, where the data is meant for the mobile devices 104 and 106, and determines whether a request for additional network resources has to be generated or not. The mobile devices 104 and 106 may need the additional network resources for a

Docket CE12658R 4

transmission opportunity. A mobile device requires the transmission opportunity to transmit data to or receive data from other mobile devices or electronic devices in the communication network 100 at a predetermined data rate. The predetermined data rate may be measured in megabits per second (mbps) or kilobits per second (kbps). A BSC monitors the buffer occupancy for downlink data, and mobile devices monitor buffer occupancy for an Up Link (UL) transmission, which is the transmission of data from the mobile devices 104 and 106 to the BSC 102. For the UL transmission of data, one or more of the mobile devices 104 and 106 may generate a request for the additional network resources. The BSC 102 also performs one or more of a radio channel allocation, a frequency administration, and a handover for the BTSs 108 and 110. Handover between BTSs within the communication network 100 occurs when a mobile device moves within the communication network 100 so that the BTS, which is providing services to the mobile device, no longer can provide such services.

Each of the BTSs 108 and 110 has an associated coverage area in which it can transmit signals to or receive signals from the mobile devices. For example, the BTS 108 can transmit to or receive signals from the mobile device 104, which lies in a coverage area 112. Similarly, the BTS 110 can transmit to or receive signals from the mobile device 106, which lies in a coverage area 114.

Each mobile device may undergo a Soft Handoff (SHO) when it moves from one coverage area to another. For example, when the mobile device 104 moves from the coverage area 112 to the coverage area 114, it may undergo an SHO. Each mobile device undergoing an SHO has one or more active SHO leg associated with it. Each active SHO leg represents each of the BTSs 108 and 110 in the coverage area of the communication network 100 to which the mobile devices 104 and 106 may transmit and receive signals.

FIG. 2 is a block diagram illustrating the components of the BTS 108, in accordance with an embodiment of the present invention. It should be appreciated that though the components are shown for the BTS 108, the same is applicable for other BTSs present in the communication network 100. The BTS 108 includes a time slice module 202, a radio frequency load module 204, and a bottleneck detector 206. The time slice module 202 receives requests for a channel, including during SHO, from

Docket CE12658R 5

the BSC 102. The time slice module 102 may also receive current buffer occupancy of a mobile device's buffer at the BSC 102. The request for channel from the BSC 102 to the BTS 108 can be converted into an information update. The information update may include, but is not limited to, the radio conditions of the 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. In an embodiment of the invention, the BSC 102 sends multiple information updates to the BTS 108.

The time slice module 202 computes a lead-time for each request, based on a sort metric. The sort metric is a metric that lets one compare the priority to schedule one mobile device's transmission over that of another. The sort metric represents the assigned priorities associated with the requests for allocation made by the plurality of mobile devices and tells the network how early it can make a decision on scheduling. The sort metric helps the time slice module 202 to schedule a request for transmission. In an embodiment of the present invention, the time slice module 202 includes information required to compute the sort metric. The information includes, but not limited to, a past history of scheduling decision and radio condition of the channel to/from the mobile device. The sort metric for each request is computed by the BSC 102 based on the information update. The radio conditions of the channels of the plurality of mobile devices included in the information update are sent to the BSC 102 by the radio frequency load module 204. The BSC 102 then forwards the sort metric to the BTS 108, so as to enable the BTS 108 to compute a lead-time using the information in the sort metric.

In another embodiment of the present invention, the sort metric is computed by the time slice module 202, which computes the sort metric based on the information update. Here, the information such as the quality of service requested by the plurality of mobile devices requesting resources and an existing data rate received by the plurality of mobile devices is sent by the BSC 102 or the plurality of mobile devices to the time slice module 202. The radio frequency load module 204 may also send periodic updates on the radio conditions of the channels of the plurality of mobile devices to the time slice module 202.

Docket CE12658R 6

The time slice module 202 computes the lead-time from the sort metric based on a bottleneck resource. The bottleneck resource is detected by the bottleneck detector 206. Examples of the bottleneck resource include, but are not limited to, a BTS processing resource, a BSC processing resource, a Down Link (DL) backhaul, and an Up Link (UL) backhaul. For example, if the bottleneck resource is a BTS processing power, then the lead-time will be such that a request becomes eligible after every "delta" units of time. Delta in the above case may be defined by the following equation: delta = T/N; where,

T = time slice duration; and

N = number of requests.

If the BTS processing power is not enough to process a request within a drop- dead time for a given time slice, then a slack time is provided, after which the BTS starts processing requests. During the slack time a request is not eligible for processing. After the slack time, the requests become eligible for processing after every "delta" units of time. Delta in the above case may be defined by the following equation:

Delta = (T-S)ZN where,

T = time slice duration;

S = slack time duration; and

N = number of requests.

A scheduler 208, which can be included in the time slice module 202, considers the requests received from the BSC 102 for downlink transmission, and from the plurality of mobile devices, for example, mobile devices 104 and 106 for uplink traffic for channel resource allocation. The requests are considered for resource allocation based on the lead-time computed by the time slice module 202. In an embodiment of the invention, if a request received for the mobile device 104 has a

Docket CE12658R 7

higher lead-time than a request received for the mobile device 106, then the scheduler 208 considers the request received for the mobile device 104 for resource allocation ahead of the request received for the mobile device 106 in the time slice. The method for scheduling the request is explained in detail in conjunction with FIG. 3. FIG. 3 is a flowchart illustrating a method for scheduling requests, in accordance with an embodiment of the present invention. At step 302, a sort metric is computed for requests generated for the plurality of mobile devices in the communication network 100. The requests may be generated either by the plurality of mobile devices for uplink transmission and by the BSC 102 for downlink transmission. The sort metric, which may represent a priority associated with the request for resource allocation, is computed based on an information update. The information update may include one or more of radio conditions of the channels of the plurality of mobile devices, a quality of service requested by the plurality of mobile devices, or an existing data rate received by the plurality of mobile devices. In accordance with an embodiment of the present invention, the BSC 102 computes the sort metric for each request and forwards the sort metric to the plurality of BTSs. If a mobile device from the plurality of mobile devices is in an SHO, then the BSC 102 forwards the sort metric for the requests to each BTS with which the mobile device has an active SHO leg. In another embodiment of the present invention, the BSC 102 forwards the information update to the plurality of BTSs so as to enable the plurality of BTSs to compute the sort metric for each request. If a mobile device from the plurality of mobile device is in an SHO, then the BSC 102 forwards the information update to each BTS with which the mobile device has an active SHO leg.

The radio condition of the channels being used by the plurality of mobile devices is the quality of a communication channel between the plurality of mobile devices and the plurality of BTSs. The quality of the channel determines the amount of resource that would be required by the plurality of BTSs to transmit data to the plurality of the mobile devices. The quality of channel depends on a number of factors, which may include, but are not limited to, the distance of a mobile device from a BTS and the location of the mobile device. For example, if the mobile device is behind a building or in the basement of a building, it may not have a good channel. A mobile

Docket CE12658R 8

device with a good radio condition as compared to the remaining mobile devices in the communication network 100, including the mobile device behind the building, may have a higher priority to receive the transmission opportunity.

In an embodiment of the present invention, the quality of service requested by the plurality of mobile devices has a bearing on the magnitude of the data rate demanded by each mobile device. For example, users of each mobile device may be categorized as a first priority user and a second priority user based on the data rate required by them. The first priority users require a higher data rate than the second priority users. Therefore, the first priority users may have a higher priority than the second priority users. This priority information is considered while computing the sort metric. In various embodiments of the present invention, the sort metric maybe computed based on one or more of the radio condition of the channels being used by 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 the mobile devices.

In another embodiment of the present invention, a sort metric depicts a priority associated with the request. A request with a small sort metric has a large lead-time and hence a higher priority as compared to a request with a large sort metric, to ensure that the request with a high priority is scheduled well before the drop-dead time associated with the time slice. The requests that could not be considered for allocation within the drop-dead time are served in another time slice.

At step 304, a lead-time is computed for each request. The lead-time is based on the sort metric associated with it. The lead-time for each mobile device is calculated by the BTSs within a time slice and with respect to a drop-dead time. The drop-dead time for a given time slice is the time before which the scheduler 208 has to complete the scheduling so that data can be transmitted during the given time slice. If a mobile device is in an SHO, then each BTS with which the mobile device has an active SHO leg, computes the lead-time for the request.

The method used for computing the lead-time is based on a bottleneck resource, which is determined by the bottleneck detector 206. Examples of the bottleneck resource include, but are not limited to, a BSC processing resource, a DL

Docket CE12658R 9

backhaul, and a UL backhaul. If the bottleneck resource is a BTS processing resource, the BTS 108 determines the number of active users in a previous time slice. The time slice is then divided into equal intervals by the time slice module 202 wherein each interval depends on the number of active users. For example, if the BTS 108 determines that there were three active users in the previous time slice, then the time slice module 202 divides the time slice into three equal intervals. Thereafter, requests generated for the plurality of mobile devices are scheduled, so that a request with a least sort metric is scheduled at the end of the first interval of the three intervals, and a request with the second-lowest sort metric is scheduled at the end of the second interval, and so on. Therefore, the lead-time for the request with the least sort metric is higher than the lead-time for the request with the second-lowest sort metric.

At step 306, each request is considered for allocation in the time slice based on the lead-time. The requests are considered for allocation before the drop- dead time in the time slice. Otherwise, the requests cannot be processed and will need to be processed for another time slice. In an embodiment of the invention, a request is considered for allocation at a time equal to the difference between the drop-dead time and the lead-time of the request or later. If a mobile device is in an SHO, the request for the mobile device is considered for allocation by each BTS with which the mobile device has an active SHO leg. In various embodiments of the invention, the requests are considered for allocation by the scheduler 208.

After scheduling the request, the transmission opportunity at the determined data rate is allocated to the plurality of mobile devices by a BTS from the plurality of BTSs in coverage area of which the mobile devices lie. In an embodiment of the invention, a request with a larger lead-time in the time slice is allocated a transmission opportunity ahead of a request with a smaller lead-time. In another embodiment of the invention, a request with a small lead-time in the time slice may be allocated a transmission opportunity in the subsequent time slices if the amount of resource required by the request is not available in the time slice. The method for allocating the transmission opportunity is explained in detail in conjunction with FIGs. 4 and 5.

Docket CE12658R 10

FIG. 4 is a flowchart illustrating a method for determining the final allocation for a request in an SHO environment, in accordance with an embodiment of the present invention. The request is generated for a mobile device in an SHO environment in the communication network 100. At step 402, a transmission opportunity allocated to the request at a determined data rate is sent to the BSC 102 within the time slice. The request is initially allocated using the method described in conjunction with FIG. 3. In various embodiments of the present invention, step 402 is performed by each BTS with which a mobile device has an active SHO leg. For example, if the BTSs 108 and 110 are the active SHO legs for the mobile device 104, then the BTSs 108 and 110 will send the allocation for the request generated for the mobile device 104 to the BSC 102.

At step 404, a check is performed to determine if each BTS with which the mobile device has an active SHO leg has sent an allocation for the request. In various embodiments of the present invention, step 404 is performed by the BSC 102. For example, if the BTSs 108 and 110 act as active SHO legs for the mobile device 104, then the BSC 102 will check if they have sent an allocation for a request generated for the mobile device 104 within a time slice. If each BTS with which the mobile device has an active SHO leg has not sent an allocation for the request within the time slice, then step 404 is repeated. If each BTS with which the mobile device has an active SHO leg has sent an allocation for the request within a time slice, step 406 is performed. At step 406, a final allocation for the request is determined. The final allocation for the request is the minimum of all allocations received for the request. For example, if an allocation made by the BTS 108 for a request generated for the mobile device 104 is less than an allocation made by the BTS 110, then the final allocation will be the allocation made by the BTS 108. In various embodiments of the present invention, step 406 is performed by the BSC 102.

Thereafter, at step 408, the final allocation for the request is sent to each BTS with which the mobile device has an active SHO leg, within the time slice. This enables each BTS that had made an allocation that was larger than the final allocation to reallocate the additional resources that have now become free to a request made by

Docket CE12658R 11

another mobile device from the plurality of mobile devices. For example, for a request generated for the mobile device 104, resources have been allocated by the BTSs 108 and 110 with which the mobile device 104 has an active SHO leg. The allocation made by the BTS 108 is less, as compared to the allocation made by the BTS 110. In this case, the allocation made by the BTS 108 is assigned to the mobile device 104. Hence, the additional resource needed for the higher allocation made at the BTS 110 becomes free. This additional resource is used to make an allocation to a request generated for another mobile device, for example, the mobile device 106. In various embodiments of the invention, step 408 is performed by the BSC 102. FIG. 5 is a flowchart illustrating a method for allocating the transmission opportunity to a request in accordance with another embodiment of the present invention. The request is generated for a mobile device in an SHO environment in the communication network 100. At step 502, a transmission opportunity allocated to the request at a determined data rate is sent to the BSC 102 from the BTSs having an active SHO leg for a mobile device. Step 502 is performed by each BTS with which a mobile device, for which the request has been generated, has an active SHO leg for a mobile device.

At step 504, an intermediate allocation for the request is determined from the allocations received before a predefined time within the time slice. The predefined time is a fraction of the time slice. The intermediate allocation for the request is the minimum of each allocation received for the request till the predefined time within the time slice. In various embodiments of the present invention, step 504 is performed by the BSC 102.

At step 506, the intermediate allocation for the request is sent to each BTS with which the mobile device has an active SHO leg within the time slice. At step 508, a check is performed to determine if one or more allocations made within the time slice by the BTSs with which the mobile device has an active SHO leg are received after the predefined time and are less than the intermediate allocation. In various embodiments of the present invention, step 508 is performed by the BSC 102. If the allocation made by the BTS for a request generated for the mobile device is received by BSC, and is larger than the intermediate allocation, then step

Docket CE12658R 12

510 is performed. At step 510, the BSC sends the intermediate allocation as the final allocation to the BTS. Step 510 is performed by the BSC 102. For example, if an allocation made by the BTS 108 for a request generated for the mobile device 104 is received by the BSC 102 after the predefined time and the allocation is larger than the intermediate allocation, then the BSC 102 sends the intermediate allocation as a final allocation to the BTS 108.

If one or more allocations made within the time slice by the BTSs with which the mobile device has an active SHO leg are received after the predefined time and are less than the intermediate allocation, then step 504 is performed. For example, if an allocation made by the BTS 108 for a request generated for the mobile device 104 is received by the BSC 102 after the selected time, and the allocation is less than the intermediate allocation, then the allocation made by the BTS 108 becomes the intermediate allocation, and is thereafter sent to both the BTSs. This enables BTS 108 to free an allocated transmission opportunity as soon as the BSC 102 determines that the allocation made by the BTS 108 is larger than the intermediate allocation for the request.

In an embodiment of the invention, a combination of methods, explained in FIGs. 4 and 5, can be used for allocating the transmission opportunity.

In another embodiment of the present invention, a speculative scheduling of the requests may be performed in each BTS by the scheduler 208. The speculative scheduling is achieved by initially making a conservative allocation to a request and sending the conservative allocation to the BSC 102. The conservative allocation is then updated by each BTS, based on the remaining resources and new allocations.

Various embodiments of the present invention, as described above, provide a method and a system for scheduling requests generated for a plurality of mobile devices in a non-FIFO order. The requests for the plurality of mobile devices are considered for allocation, based on a lead-time computed by the BSC 102 or by the BTSs 108 and 110, and where processing of requests by the BTSs 108 and 110 is distributed across time instead of waiting for all requests to arrive and processing them all at once, and therefore reduces the processing power required for scheduling the requests in a non-FIFO order.

Docket CE12658R 13

In the foregoing specification, specific embodiments of the present invention have been described. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention. The benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential features or elements of any or all the claims. The invention is defined solely by the appended claims including any amendments made during the pendency of this application and all equivalents of those claims as issued.

Docket CE12658R 14