HK1077690A1 - Scheduler and method for allocating resources in a communication system - Google Patents

Description

Resource scheduler and resource scheduling method in communication system

The present application is a divisional application filed on 12/1/2000 under the name of 00802803.6 entitled "resource scheduler and resource scheduling method in communication system".

Technical Field

Embodiments disclosed herein relate to communication systems. In particular, the embodiments are directed to a resource scheduler and a resource scheduling method for communication resource allocation among a plurality of users in a communication system.

Background

Several solutions have been proposed to the problem of allocating limited communication resources provided by a node in a communication system among a plurality of users. The purpose of the system is to provide sufficient resources at the node to meet the needs of all users, and to minimize costs. Therefore, these systems are generally designed for the purpose of efficiently allocating resources among users.

Various systems have implemented Frequency Division Multiple Access (FDMA) schemes that allocate resources to each user in parallel. The communication nodes of the system typically have a limited bandwidth for receiving or transmitting information to each user in the network at any one time. This scheme typically involves allocating different portions of the total bandwidth to each user, and while this scheme is effective for systems in which users require uninterrupted communication with the communication node, better utilization of the total bandwidth can be achieved without the need for this constant interruption.

Other schemes for allocating communication resources among multiple users in a single communication node include Time Division Multiple Access (TDMA) schemes. This is particularly effective for distributing among a plurality of users that do not require constant uninterrupted communication with a single communication node. TDMA schemes typically dedicate the entire bandwidth of a single communication node to each user at specified time intervals. In a wireless communication system utilizing a Code Division Multiple Access (CDMA) scheme, this can be accomplished by assigning all code channels to each subscriber unit at specified time intervals in accordance with time division multiplexing. The unique carrier frequency or channel code associated with the user is implemented by the node so as to enable communication exclusively with the user. TDMA schemes may also be implemented in landline systems using actual contact relay switching or packet switching.

TDMA systems typically allocate users equal time intervals in a round robin fashion. This may result in some users underutilizing some time intervals. Similarly, other users may have communication resource requirements that exceed the allocated time interval, leaving those users unserviceable. The system operator may then choose to accept the cost of increased bandwidth to ensure that no users are rendered unserviceable, or to allow unserviceable users to continue to remain,

accordingly, there is a need for a system and method for efficiently and openly allocating communication resources among users of a communication system based on network policies for allocating communication resources among users.

Disclosure of Invention

An object of the present invention is to provide a resource scheduler for use in a communication system, the resource scheduler comprising: means for maintaining a weight associated with each client node, the weight associated with an instantaneous rate at which the client node consumes the resource; means for selecting one or more client nodes to allocate resources based on the weights associated with the client nodes.

In addition, the resource scheduler of the present invention may also vary the weighting associated with a client node based on the instantaneous rate at which the client node consumes resources.

Briefly, one embodiment of the present invention is directed to a resource scheduler in a communication system including a common node and a plurality of client nodes coupled to the common node. The common node can provide limited resources exclusively used by one or more occupied customer nodes regardless of the remaining customer nodes during any particular service interval. The resource scheduler includes logic to maintain a weight or score associated with each client node, logic to select one or more remaining client nodes to occupy the limited resource for a subsequent service interval based on comparing the weight associated with each selected client node to the weights associated with the remaining client nodes, and logic to change the weights associated with the client nodes to facilitate optimal allocation of the limited resource in accordance with a public criterion.

The resource scheduler may maintain a weight associated with each client node based on an instantaneous rate at which the client node can receive data from the common node. The resource scheduler may then support the reception of client nodes having higher data reception rates. By maintaining the weights associated with each client node and selecting individual client nodes to occupy a common node, the scheduler can optimally allocate resources to client nodes according to fairness criteria.

In embodiments where the common node provides data transmission resources to the client nodes, for example, the scheduler may weight individual client nodes to support client nodes capable of receiving data at a higher rate. This weighting helps to increase the throughput of the total data of the common node. In another embodiment, the weighting is done in a way that the scheduler also complies with the public guidelines.

Although the embodiments disclosed herein are directed to allocating transmission resources to users via a forward channel in a data service network, the underlying principles are also generally used extensively to allocate resources among components in a communication system. The disclosed embodiments are therefore to be considered in all respects as illustrative and not restrictive, the scope of the claims. For example, the principles described herein may be applied to communication networks in which client nodes are able to transmit data to a common node through limited reverse transmission channel contention.

Brief Description of Drawings

Fig. 1 illustrates a communication network according to an embodiment of the present invention.

Fig. 2 shows a schematic diagram detailing an embodiment of a base station controller in the communication network shown in fig. 1.

Fig. 3 shows a flow chart of the scheduling algorithm performed in the embodiment of the channel scheduler shown in fig. 2.

Fig. 4 shows a diagram illustrating the timing of the execution of an embodiment of the scheduling algorithm shown in fig. 3.

FIG. 5 shows a flow chart illustrating an embodiment of a process for weighting updates of selected queues in the embodiment identified in FIG. 3.

Fig. 6a to 6c show a flowchart illustrating embodiment 1 of the data transmission reception queue selection process in the discriminated service interval of fig. 3.

Fig. 7a to 7d show a flowchart illustrating embodiment 2 of the data transmission reception queue selection process in the discriminated service interval of fig. 3.

Fig. 8a to 8b show a flowchart illustrating embodiment 3 of the data transmission reception queue selection process in the discriminated service interval of fig. 3.

Best mode for carrying out the invention

Embodiments of the present invention are directed to systems and apparatus for allocating resources among a plurality of users of a communication network served by a single communication node. In each discrete transmission interval (or "service interval"), each user occupies the limited resources of the communication node, regardless of all other users. And selecting each user to occupy the limited resources according to the weighting or the grading associated with each user. The weighting of the individual user associations is preferably varied based on the instantaneous rate at which the individual users can consume the limited resources.

Referring to the drawings, FIG. 1 illustrates an exemplary variable rate communication system. One such system is set forth in U.S. patent application serial No. 08/963386. This patent, entitled "method and apparatus for high rate packet data transmission," was filed on 3.11.1997, assigned to Qualcomm, inc. The variable rate communication system includes a plurality of cells 2 a-2 g. Each cell 2 is served by a respective base station 4. A number of remote stations 6 are dispersed throughout the communication system. In the exemplary embodiment, each remote station 6 communicates with a maximum of 1 base station 4 along the forward link at any data transmission interval. For example, along the forward link at time slot n, base station 4a transmits data exclusively to remote station 6a, base station 4b transmits data exclusively to remote station 6b, and base station 4c transmits data exclusively to remote station 6 c. As shown in fig. 1, each base station 4 preferably transmits data to one remote station 6 at any given time. In other embodiments, base station 4 may communicate with more than one remote station 6 at a particular data transmission interval regardless of all other remote stations 6 with which base station 4 is associated. In addition, the data rate is variable and depends on the carrier frequency to interference ratio (C/I) measured by the receiving remote station 6 and the required energy to noise ratio per bit (Eb/No). The reverse link from remote station 6 to base station 4 is not shown in fig. 1 for simplicity. According to one embodiment remote station 6 is a mobile unit having a wireless transceiver operated by a wireless data service user.

A block diagram illustrating the basic subsystems of an exemplary variable rate communication system is shown in fig. 2. The base station controller 10 is connected to a packet communication network interface 24, a Public Switched Telephone Network (PSTN) and all base stations 4 in the communication system (only one base station 4 is shown in fig. 2 for simplicity). Base station controller 10 facilitates communication between remote station 6 and other users connected to packet communication network interface 24 and PSTN30 in a communication system. PSTN30 connects users through a standard telephone network (not shown in fig. 2).

The base station controller 10 comprises a number of selector units 14, although only one is shown in fig. 2 for simplicity. Each selector element 14 is assigned to control communication between one or more base stations 4 and one remote 6. If selector element 14 is not assigned to remote station 6, call control processor 16 is notified that a page to remote station 6 is required. Call control processor 16 then directs base station 4 to page remote station 6.

Data source 20 contains some data to be transmitted to remote station 6. The data source 20 provides data to the packet communication network interface 24. The packet communication network interface 24 receives the data and passes the data to the selector unit 14. Selector element 14, in turn, sends the data to each base station in communication with remote station 6. In the exemplary embodiment, each base station 4 maintains a data queue 40 for storing data to be transmitted to remote station 6.

Data is sent from data queue 40 to channel element 42 in data packets. In the exemplary embodiment, on the forward link, a "data packet" refers to some data of up to 1420 bits and some data to be transmitted to remote station 6 on the other hand in a "slot" (such as ≈ 1.667 msec). The channel element 42 inserts the required control segment for the first data packet. In the exemplary embodiment, channel element 42 CRC encodes the data packet and control end and inserts a set of code tail bits. The data packet, control segment, CRC parity bits, and code tail bits comprise a formatted data packet. In the exemplary embodiment, channel element 42 encodes the formatted data packets and interleaves (or reorders) the symbols in the encoded data packets. In the exemplary embodiment, the interleaved data packet is masked with a walsh code and spread with short PNI and PNQ codes. The spread data is provided to the RF unit 44 for quadrature modulation, filtering and amplification of the signal. The forward link signal is transmitted over the air on a forward link 50 via an antenna 46.

At remote station 6, the forward link signal is received by antenna 60 and passed to the receiver at front end 62. The receiver filters, amplifies, quadrature demodulates, and quantizes the signal. The digitized signal is provided to a demodulator (DEMOD)64, despread with the short PNI and PNQ codes, and de-masked with walsh codes. The demodulated data is supplied to a decoder 66, which performs inverse processing to that performed by the base station 4, specifically, de-identification, decoding, and CRC check of the signal. The decoded data is provided to a data sink 68.

The hardware indicated above supports variable rate data transmission, messaging, voice, image and other communications over the forward link. The rate of data transmitted from data queue 40 varies to accommodate changes in the signal strength and noise environment of remote station 6. Each remote station 6 preferably transmits a Data Rate Control (DRC) signal to the associated base station 4 in each slot. The information provided by the DRC signal to base station 4 includes the identity of remote station 6 and the rate at which remote station 6 receives data from its associated data queue. Thus, the circuitry of remote station 6 measures the signal strength and estimates the noise environment of remote station 6 to determine the rate at which information is to be transmitted in the DRC signal.

Embodiments of the present invention may be used in other hardware architectures capable of supporting variable rate transmission. The reverse link is not shown or described for simplicity. The present invention can advantageously delay variable rate transmissions to include the reverse link. For example, instead of base station 4 determining the rate at which data is received based on the DRC signal from remote station 6, base station 4 measures the strength of the signal received from remote station 6 and estimates the noise environment to determine the rate at which data is received from remote station 6. Base station 4 then transmits to each associated remote station 6 the rate at which data can be transmitted on the reverse link from remote station 6. However, base station 4 may schedule transmission of the reverse link based on the different data rates on the reverse link in the same manner as described above for the forward link.

The base station 4 of the embodiment discussed above also transmits to a selected one or ones of the remote stations 6 using a Code Division Multiple Access (CDMA) scheme regardless of the remaining remote stations with which the base station 4 is associated. At any particular time, base station 4 transmits to a selected one or ones of remote stations 6 by employing the code assigned to the receiving base station 4. However, the invention can also be used in other systems that use different Time Division Multiple Access (TDMA) methods to optimally allocate transmission resources, irrespective of which other base station 4 provides data specifically to the selected base station 4.

The channel scheduler 12 is connected to all selector elements 14 in the base station controller 10. The channel scheduler 12 schedules variable rate transmissions on the forward link. Channel scheduler 12 receives the queue size, which refers to the amount of data inventively sent to remote station 6, and the message from remote station 6. The channel scheduler 12 preferably schedules data transmission to achieve the system goal, i.e., data throughput is maximized and fairness constraints are met.

As shown in fig. 1, remote stations 6 are dispersed throughout the communication system and may or may not communicate with one base station 4 on the forward link. In the exemplary embodiment, channel scheduler 12 coordinates forward link data transmissions throughout the communication system. The high speed data transmission scheduling method and apparatus is detailed in U.S. patent application serial No. 08/798951. This patent, entitled "Forward Link Rate scheduling method and apparatus", was filed on year 1997, month 2, day 11, assigned to the assignee of the present invention and is incorporated herein by reference.

The channel scheduler 12 is implemented in a computer system according to one embodiment, which includes a processor, a Random Access Memory (RAM), and a program memory (not shown) that stores instructions to be executed by the processor. The processor, RAM and program memory may be dedicated to the various functions of the channel scheduler 12. In other embodiments, the processor, RAM and program memory may be part of a common computing resource for performing additional functions at the base station controller 10. In the present embodiment, each base station 4 is assigned a separate channel scheduler 12. In other embodiments, a single channel scheduler may be used collectively to schedule transmissions for all base stations 4.

Fig. 3 illustrates a scheduling algorithm for control channel scheduler 12 to schedule transmissions from base station 4 to remote station 6. As described above, a data queue 40 is associated with each remote station 6. The channel scheduler 12 associates each data queue 40 with a "weight" that is evaluated at step 110 to select the particular remote station 6 associated with the base station 4 to receive data in the subsequent service interval. The channel scheduler 12 selects a single remote station to receive transmissions at discrete service intervals. The channel scheduler initializes the weights for each queue associated with the base station 4 at step 102.

The channel scheduler 12 loops through steps 104 to 112 during the transmission interval (or service interval). In step 104, the channel scheduler 12 decides whether to add additional queues due to the detection of another remote station 6 associated with base station 4 in the previous service interval. The channel scheduler 12 also initializes the weights associated with the new queue in step 104. As described above, the base station 4 receives DRC signals from its associated remote stations 6 at regular intervals, such as time slots.

The DRC signal also provides information for the channel scheduler to use in determining the instantaneous rate at which each remote station associated with each queue consumes information (or receives transmitted data) at step 106. According to one embodiment, a DRC signal transmitted from any remote station 6 indicates that the remote station 6 can receive data at any of the 11 effective data rates shown in table 1. The above-incorporated reference U.S. patent No. 6,064,678 entitled "method for Assigning Optimal Packet Lengths in a Variable Rate communication system" details the Variable Rate transmission system.

TABLE 1

Is provided withEffective data Rate (Ri)	Data (Data _ size (li)) (bits) transmitted in service intervals	Length of service interval/transmission time (time slot ═ 1.667msec)
			38.4kbps	1024	16
76.8kbps	1024	8
			102.4kbps	1024	6
153.6kbps	1024	4

204.8kbps	1024	3
			307.2kbps	1024	2
614.4kbps	1024	1
			921.6kbps	1536	1
1228.8kbps	2048	1
			1843.2kbps	3072	1
2457.6kbps	4096	1

The channel scheduler 12 determines the length of the service interval for transmitting data to any particular remote station based on the remote station's associated instantaneous rate of received data (indicated in the newly received DRC signal) at step 108. According to one embodiment, the instantaneous rate of receiving data Ri determines the length of the service interval Li associated with a particular data queue at step 106. Table 1 summarizes the Li values for each of the 11 received data rates in remote station 6.

In step 110, the channel scheduler 12 selects a particular data queue for transmission. The associated amount of data to be transmitted is then retrieved from the data queue 40 and provided to the channel element 42 for transmission to the remote station 6 with which the data queue 40 is associated. As will be discussed below, the channel scheduler 12 selects a queue at step 110 with information including the weight associated with each queue for providing data for transmission in the next service interval. The weights of the transmitted queue associations are then updated at step 110.

Fig. 4 shows a timing diagram of the channel scheduler 12 and data transmission in the service interval. Fig. 4 shows 3 discrete service intervals when transmitting at time intervals δ -1, δ 0 and δ 1. When the scheduling algorithm of steps 104 through 112 of fig. 3 is executed during service interval 202, the scheduling algorithm executed during interval δ 0 preferably determines which queue to send during interval δ 1. Further, as described above, the execution of steps 104 through 112 is dependent on information in the DRC signal received from the remote station 6. This information is preferably extracted from the most recently received DRC signal. Therefore, steps 104 through 110 are preferably performed and completed during the last slot of the service interval. This ensures that the allocation of the subsequent service interval is decided based on the latest DRC signal, i.e. the DRC signal in the slot immediately before the execution of step 104 to step 110.

Steps 104 and 110 are preferably completed within one time slot while providing the channel scheduler 12 with sufficient time to schedule the transmission of a subsequent service interval. Therefore, the processor and RAM utilized by the channel scheduler 12 are preferably capable of performing steps 104 through 112 within the time constraints illustrated in FIG. 4. That is, the processor and RAM are sufficient to perform steps 104 through 110 for a sufficient amount of time, beginning at the beginning of a time slot and completing steps 104 through 110 before the end of the time slot, for the channel scheduler 12 to schedule transmission of a subsequent service interval.

FIG. 5 illustrates one embodiment of the weighted update process in step 112 (FIG. 3). Step 302 calculates a rate threshold "C" equal to the average of all instantaneous rates associated with a queue having data. The calculation preferably removes the instantaneous rate associated with queues that do not contain data. Step 304 compares the instantaneous rates associated with the selected Sselected-Queue selected in step 110. If the instantaneous rate of the selected queue association exceeds the threshold C, step 306 increments the weight of the selected queue association by a lower value, preferably representing the amount of data, in units such as bits, bytes or megabytes, transmitted from the selected queue during the subsequent service interval. If the instantaneous rate associated with the select queue does not exceed the threshold calculated in step 302, step 308 increments the weight of the select queue by a large value, preferably "G" times the amount of data to be transmitted from the select queue during the subsequent service interval, in bits, bytes, or megabytes.

G is preferably selected based on fairness criteria that supports allocation of service intervals to remote stations 6 having capacity to receive data at a relatively high rate. The size of G is selected by the system designer based on the degree of support provided by remote station 6 for receiving data at a higher rate than for receiving remote stations 6 at a lower rate. The larger the value of G, the more fully utilized the forward link of the base station. However, this efficiency is achieved at the cost of the user of the slower rate receiving remote station 6 losing the transmission resources of the forward link. Therefore, the system designer preferably balances the competing goals of (1) increasing the overall forward link efficiency and (2) avoiding the severe loss of the slower rate receiving remote station 6 by selecting the value of G in this manner.

Steps 304, 306 and 308 illustrate that select queues with faster associated instantaneous data rates (i.e., exceeding the threshold C) will have only a small increase in associated weights, while select queues with lower data rates (i.e., not exceeding the threshold C) will have a significantly larger increase in associated weights. This measure helps to support the remote station receiving data at a faster rate than the remote station receiving data at a lower data rate, as will be discussed below in connection with the algorithm executed in step 110 of fig. 3.

This tendency increases the throughput efficiency of the base station 4 when transmitting data in the forward link. However, since the weights of the frequently selected queues associated with remote stations of higher data reception rates (G exceeding the threshold C) continue to be incremented, these weights eventually approach the weights of the less frequently selected queues associated with remote stations of lower data reception rates (G not exceeding the threshold). Selection processing then begins at step 110 to support the slower rate receiving remote station when the weighting of the faster rate receiving remote station begins to exceed the weighting of the slower rate receiving remote station. This imposes a public constraint on the selection process of step 110 to avoid the faster-rate-receiving remote station dominating the forward link transmission resources of the base station despite the lower-rate-receiving remote station.

It is an object of the invention to ensure that queues that do not have data to transmit get unfair priority transmission over queues that have data. In steps 102 and 104, all new queues are initialized with zero weighting. Assuming that a queue is not selected, the queue will continue to maintain a zero weighting in the case of non-selection. Thus, step 310 of FIG. 5 decrements the total queue weight by any minimum weight for the queue with data (determined in step 309) to a value no less than zero. This is explained in detail in the example shown in table 2 below.

TABLE 2

Service interval	Weighting of service interval ends			Remote station selected in service interval	Remote station operating in service interval	Weighted incremental amount of decrease
							Remote station 1	Remote station 2	Remote station 3
	0	0	0							0	Is free of	Is free of	Is free of
1				0	0	0	1	Is free of	0
	2	1	1							0	2	1	0
3				0	0	7	3	2	1
	4	1	0							7	1	3	0
5				0	0	6	2	1	1
	6	1	0							6	1	2	0
7				0	0	5	2	1	1

This example has 3 remote stations each associated with a data queue to be transmitted from the base station. This example assumes that remote station 1 has the highest data rate, remote station 2 has the 2 nd highest data rate, and remote station 3 has the lowest data rate. For simplicity, it is assumed that these data rates do not change during service interval 1 through service interval 7. Assume again that remote station 1 and remote station 2, respectively, exceed threshold C at step 304 and that the data rate at remote station 3 does not exceed this threshold. Assume again that step 306 increments the Selected-Queue weight by 1, provided that the Selected Queue is associated with remote station 1 or remote station 2; if the selection queue is associated with the remote station 3, step 308 increments the weight of the selection queue by 8.

In service interval 1, channel scheduler 12 selects remote station 1 to receive data in the subsequent service interval because remote station 1 has a higher data reception rate despite the lowest weighting of remote station 1 with remote stations 2 and 3. Thus, during service interval 2, data is transmitted to remote station 1 and the weight associated with remote station 1 is incremented by 1 at the end of service interval 1. Channel scheduler 12 then selects remote station 2 to receive data in service interval 3 (since remote station 2 has the lowest weighted sum and faster data reception rate than remote station 3). As shown in table 2, the weight of remote station 2 is incremented by 1 before service interval 2 ends.

At the beginning of the service interval 3, the remote station 3 has the lowest weight. The channel scheduler 12 selects the remote station 3 to receive data during the service interval 4. The status of the end of interval 3 reflects an increment of the weighting of the remote station 3 from zero to 8 to reflect the selection of the remote station 3. The weights for remote stations 1, 2 and 3 are then incremented by 1 as shown in table 2. This point is consistent with step 310 of fig. 5. In service interval 4, channel scheduler 12 selects remote station 1 to receive data for service interval 4 because the queue associated with remote station 1 has the lowest weighting and the highest data reception rate.

Channel scheduler 12 selects a remote station 2 in service interval 5 to receive data during service interval 6. In step 306, the remote station 2 associated weights are first incremented and the weights for all remote stations are decremented as reflected by the weights at the end of service interval 5 shown in table 2. The remote station 1 with the lowest weight is then selected again in service interval 6 for receiving data in service interval 7.

As shown in the embodiment of fig. 1, remote station 6 is mobile and can change associations with different base stations 4. For example, remote station 6f first receives a data transmission from base station 4 f. The remote station 6f may then move out of the cell of base station 4f and into the cell of base station 4 g. The remote station 6f may then begin sending its DRC signal alerting the base station 4c instead of the base station 4 f. Since no DRC signal is received from remote station 6f, the logic of base station 4f concludes that remote station 6f is not engaged and thus no longer receives data transmissions. The data queue associated with remote station 6f may then be transmitted to base station 4g via a landline or radio frequency communication link.

In accordance with an embodiment of the present invention, base station 4 can assign weights to the queues of remote stations 6 that are not camped and that re-camp on base station 4, and base station 4 can assign weights that allow the re-camped remote stations to receive data transmissions from base station 4 with the benefit of fairness, as opposed to simply assigning zero weights to the re-camped remote stations 6. In one embodiment, channel scheduler 12 may assign weights to queues re-occupying remote station 6 over phases, e.g., based on a uniform distribution between zero and the highest weight of any queue currently being serviced by the scheduler. In another embodiment, base station 4 receives the weight to re-engage remote station 6 via landline transmission from the last base station with which remote station 6 is associated.

In another embodiment, channel scheduler 12 provides "partial credit" to re-occupying remote station 6 in order to have past association with base station 4. The channel scheduler 12 determines the number of slots "n" spanned by the previous service interval and keeps a history of the number of slots m during the previous service interval in which the base station receives the DRC signal from the remote station I. Thus, in step 310, the weighting for the queue associated with remote station I is decremented as follows:

W_i＝W_i-m_i/n×W_min

in the formula

W_iWeighting of queue i

W_minMinimum weighting for any queue with data sent to remote station

m_iThe number of time slots during the previous service interval in which the base station received the DRC signal from the remote station 1

n is the number of slots spanned by the previous service interval

Fig. 6 a-6 c show a flowchart illustrating the logic performed by step 110 (fig. 3), according to one embodiment. Step 402 initializes an identification of Selected _ Queue as the 1 st data Queue with data to be sent to the associated remote station 6. Channel scheduler 12 determines whether the initial queue or a different data queue has data to select for transmission to its associated remote station 6 in steps 404 through 422. Then, in step 406 and step 408, Next _ Queue is retrieved and it is determined whether the Next Queue has data. If the next queue has no data, execution of the flow returns to step 406 to select a subsequent data queue. In addition, if the next Queue has data, the next Queue is assigned the identification of Current _ Queue. If the weight of the current queue is greater than the weight of the selected queue, step 412 returns execution of the process to step 406 to retrieve the next queue in the sequence. Otherwise, step 414 determines whether the weight of the current queue is less than the weight of the selected queue. If the weight of the current queue is less than the weight of the selected queue, execution of step 414 proceeds to step 420 where the identity of the current queue is assigned to the selected queue.

Otherwise, in steps 412 and 414, if the logic instruction executes to hcib416, the weighting of the current queue and the weighting of the select queue are equal. If either of the following conditions is met, then step 424 allocates the current queue as the select queue:

(1) the instantaneous rate of data reception associated with the current queue is greater than the instantaneous rate of data reception associated with the selected queue (step 416);

(2) if the service interval allocated to the current queue runs out of all the data stored in the current queue, only a portion of the remaining data is left in the service interval allocated to the current queue, which is no more than the portion of the remaining data in the selected queue in the service interval allocated to the selected queue (steps 418 to 422).

Otherwise, execution returns to step 406 to select the next queue.

Fig. 7A-7 d show a flow chart illustrating embodiment 2 of the logic performed in step 110 for selecting a queue to send to the associated remote station 6. It is assumed in this embodiment that each base station 4 periodically transmits control signals to all associated remote terminals 6 having a fixed duration, such as 8 to 16 time slots. According to one embodiment, the base station 4 transmits a control signal every 400 msec. No data from either data queue (fig. 2) is transmitted to the associated remote station 6 during the transmission of this control signal. The purpose of the embodiment shown in fig. 7A and 7b is to select only the data queue that can be completely transmitted for the service interval of the length specified in step 108 before the next control signal transmission is started.

Steps 499 through 503 screen the entire queue to determine which queues are candidate queues to complete before the next control signal transmission begins. Step 499 determines a time "T" before transmission of a control signal by, for example, subtracting the next scheduled service interval start time from the scheduled time at which transmission of the control signal begins. Step 501 determines whether the length of the service interval associated with each queue determined in step 108 can be transmitted within time T based on the instantaneous transmission rate of the remote station 6 associated with the queue determined in step 106. According to an embodiment, step 501 compares the service interval length to T. Step 502 then determines whether Next _ Queue contains data. If the next queue meets the conditions of steps 501 and 502, an identification of the next queue is assigned to the selected queue.

Steps 504 to 508 examine the remaining data queues to determine which data queues can all be transmitted before the next control signal transmission begins and have an associated service interval determined in step 108. When the criteria set in step 507 and step 508 are satisfied, Current _ Queue is allocated as the next Queue. Steps 512 through 526 then perform a selection process based on the queue weights in the same manner as discussed above in connection with steps 412 through 426 of fig. 6a through 6 c. However, in the embodiments of fig. 7a to 7d, only data queues whose allocated data packet lengths can be completed before the next control signal transmission starts can be used as candidate queues based on the associated queue weights.

Fig. 8a and 8b show a flow chart illustrating an embodiment 3 of the logic performed in step 110 of fig. 3 for selecting a transmit queue. In this embodiment, the user selected for remote unit 6 is guaranteed to have the minimum average rate for data transmission. For each of the aforementioned preferential remote units, the channel scheduler 12 maintains a timer that provides the channel scheduler 12 with scheduling transmission for its preferential queue regardless of the weights associated with the remaining queues. The time interval for the particular timer is determined based on the average data rate guaranteed to the client, the service interval allocated to the data queue in step 108 (see the central column of table 1), and any instantaneous data rate of the received data determined in step 106. The time interval associated with the offer queue timer thus varies dynamically with these values. According to one embodiment, each time the timer is reset, the timer interval is determined as follows;

img id="idf0001" file="C20051000689300151.GIF" wi="147" he="46" img-content="drawing" img-format="GIF"/

in the formula

T_jTimer interval for preferential queue j

Data_Size(L_j) The amount of data to be transmitted in the service interval allocated to the preference queue j.

r_jAverage data transmission rate guaranteed for preferential user associated with preferential queue j

The timer is reset upon the occurrence of any of the 2 events. The 1 st event that initiates timer reset is the expiration of a timer interval. Event 2, which initiates timer reset, is the selection of the associated data offer queue according to the associated weights, in the manner discussed above with reference to fig. 6 a-6 c.

Step 606 to step 610 determine whether Next Queue grants a preferential Queue with minimum average data receiving rate characteristic, if yes, determine whether the timer associated with the preferential Queue expires. In the event that the timer expires, step 612 assigns the selected queue an identification of the next queue, thereby completing the process performed in step 110. The weighting of the selected queue is then updated at step 112, as described above. If there is no coupon queue for which the timer expires, step 614 initiates selection of a subsequent service interval transmission queue in step 616, the selection being based on the weighting of the queue, in the manner discussed above with reference to FIGS. 6 a-6 c. If the queue selected at step 616 is a premium queue having an associated timer, step 618 is initiated and the timer associated with the selected queue is reset at step 620.

As described above, the associated timer for any particular offer data queue is restored at step 620 after the queue is selected based on the associated weights. The associated timer is also reset upon expiration prior to data queue selection. Thus, the timer alerts the channel scheduler 12 to override the logic for selecting data queues by weight to ensure that the user is associated with a preferential data queue, resulting in a guaranteed minimum average rate of data reception.

While there has been illustrated and described what are presently considered to be the preferred embodiments of the present invention, it will be understood by those skilled in the art that various other modifications may be made, and equivalents may be substituted, without departing from the true scope of the invention. In addition, many modifications may be made to adapt a particular situation to the teachings of the present invention without departing from the central inventive concept described herein. Therefore, it is intended that the invention not be limited to the particular embodiment disclosed, but that the invention and all embodiments thereof are within the scope of the appended claims.

Claims (15)

1. A resource scheduler for use in a communication system comprising a common node and a plurality of client nodes associated with the common node, the resource scheduler comprising;

means for maintaining a weight associated with each client node, the weight associated with an instantaneous rate at which the client node consumes the resource;

means for selecting one or more client nodes to allocate resources based on the weights associated with the client nodes.

2. The resource scheduler of claim 1, further comprising:

the means for selecting one or more client nodes is further configured to vary the weighting associated with the client node based on the instantaneous rate at which the client node consumes the resource.

3. The resource scheduler of claim 2, wherein the means for selecting one or more client nodes is further configured to increase the weight associated with a client node by a value associated with an instantaneous rate at which the client node consumes the resource.

4. The resource scheduler of claim 3, wherein the instantaneous rate at which the client node consumes the resource is dynamic.

5. The resource scheduler of claim 1, further comprising:

means for causing the selected one or more client nodes to occupy the common node and to occupy the resource after the expiration of the current service interval.

6. The resource scheduler of claim 1, wherein the means for selecting one or more client nodes selects one or more client nodes having one of the associated minimum weights.

7. The resource scheduler of claim 1, wherein the resources comprise an instantaneous capacity to send information to the selected one or more guest nodes.

8. The resource scheduler of claim 7, wherein the common node sends information to the selected one or more client nodes based on a rate at which the selected one or more client nodes can receive the information.

9. The resource scheduler of claim 8, wherein the means for maintaining the weight associated with the client node modifies the weight associated with the at least one client node when the amount of information to be sent to the at least one client node falls below the amount of information threshold for a specified period of time such that the means for selecting one or more client nodes selects from the remaining client nodes associated with the amount of information that exceeds the amount of information threshold.

10. The resource scheduler of claim 1, wherein the common node starts sending control information to the at least one client node for a control channel duration at fixed intervals using the resource; the means for selecting one or more client nodes is further configured to select one or more client nodes before starting during the next control channel.

11. The resource scheduler of claim 1, wherein the communication system comprises a plurality of common nodes, each client node being associated with exactly one common node at any particular point in time, and at least one client node being able to change its association between a 1 st common node and a 2 nd common node.

12. The resource scheduler of claim 1, wherein the resource scheduler independently maintains a weight associated with each client node associated with at least the 1 st common node; the means for selecting one or more customer nodes is further configured to modify a weighting associated with at least one customer node based on a duration of time that the at least one customer node is associated with the 1 st common node at a particular past stage.

13. The resource scheduler of claim 1, further comprising:

means for determining a duration of a time interval having a beginning and an end associated with the at least one client node based on the minimum average rate of consuming resources associated with the at least one client node and the instantaneous rate of consuming resources associated with the at least one client node.

14. The resource scheduler of claim 13, further comprising:

the means for determining a time interval duration is further configured to initialize a time interval each time at least one client node occupies resources and each time the time interval ends.

15. The resource scheduler of claim 13, wherein at the end of each time interval, the means for selecting schedules the at least one client node to occupy the resource in a subsequent service interval, independent of the weight associated with the client node.