Method for scheduling wireless downlink transmissions subject to rate constraints

TECHNICAL FIELD

P-0001[0001] This invention relates to the scheduling of communicative transactions between a central hub in a communication system, and remote terminals that are served by the hub. More particularly, the invention relates to scheduling downlink transmissions from a base station to mobile stations of a wireless communication system.

BACKGROUND OF THE INVENTION

P-0002[0002] Many communication networks include an arrangement in which a centralized node, or “hub,” communicates with a group of non-centralized terminals, which are here referred to as “remote terminals.” If the remote terminals communicate with the hub over a common channel, it is possible for the communications between one remote terminal and the hub to interfere with communications between other remote terminals and the hub. To prevent such interference, it is often desirable to employ the techniques of time-division multiplexing. According to such techniques, each remote terminal has an assigned timeslot during which it may communicate with the hub by sending or receiving transmissions without interference from competing remote terminals within the group.

P-0003[0003] In some fields, the process of determining which remote terminal should be assigned a given timeslot is referred to as “scheduling.” That terminology will be adopted here. Similarly, an entity, typically resident at the hub, that makes the scheduling determination for each timeslot will be referred to here as a “scheduler.” The simplest form of scheduling is “round robin” scheduling, in which the remote terminals are scheduled in a fixed order, and typically for equal durations. The scheduler repeatedly cycles through the remote terminals in the fixed order.

P-0004[0004] Although useful, round robin scheduling suffers from certain drawbacks. One such drawback is conveniently described with reference to the specific case of forward, or “downlink,” transmissions from a base station to mobile stations of a cellular network.

P-0005[0005] The maximum rate at which a mobile station can receive data from the base station, without exceeding a given error rate, is limited by interference and noise, and by the received signal strength at the current location of the mobile station. Typically, the ratio of signal strength to the combined noise and interference, often referred to as the “signal to interference plus noise ratio” SINR, is greatest near the center of a cell and lowest near the margins of the cell. The SINR also fluctuates over time.

P-0006[0006] At any given time, then, some mobile stations will be able to receive data at higher rates than others. By favoring those mobile stations having the highest SINR for receiving downlink transmissions, the scheduler can drive up the throughput of the system; i.e., the long-term average amount of downlink data transmitted per unit time.

P-0007[0007] If, for example, the revenue collected by the network operator depends upon throughput, it is desirable to drive the throughput as high as possible. However, a scheduler that always favors those mobiles having the highest SINR will tend to deny service to mobiles having low SINR. As a consequence, users will experience intolerable service interruptions, and will be dissatisfied.

P-0008[0008] Those skilled in the art have recognized the need to balance throughput against “fairness;” i.e., against the need to assure that service to each mobile station, or other remote terminal, is scheduled often enough to satisfy all of the users.

P-0009[0009] This necessity is discussed, for example, in U.S. Pat. No. 6,229,795, which issued on May 8, 2001 to R. Pankaj et al. (the '795 patent). The '795 patent describes a cellular system for high-rate packet-data transmission, in which the downlink has a variable rate of data transmission. The scheduling of individual remote terminals is based on a weight assigned to each remote terminal. At the base station, a scheduler uses these weights to make scheduling decisions. A scheduling algorithm is used that aims to balance the competing objectives of throughput and fairness.

P-0010[0010] According to that algorithm described in the '795 patent, a threshold is computed by averaging the instantaneous downlink data-transmission rates for all mobile stations that have queued data waiting at the base station. If the instantaneous transmission rate for a given mobile station exceeds the threshold, the weight for that mobile station is incremented by a step. If the instantaneous transmission rate for that mobile station falls below the threshold, the corresponding weight is incremented by a larger step.

P-0011[0011] Another algorithm, which also seeks to balance throughput against fairness, is the well-known Proportional Fair Scheduling algorithm. Proportional Fair scheduling is discussed, for example, in A. Jalali, et al., “Data Throughput of CDMA-HDR, a High Efficiency Data Rate Personal Communication Wireless System,” <i>Proc. Vehicular Technology Conference VTC </i>2000, IEEE (2000) 1854-1858.

P-0012[0012] In Proportional Fair scheduling, the scheduler keeps track of two values, in particular, for each remote terminal: DRC and R. On the downlink of a wireless network, for example, each remote terminal will estimate its SINR for the next timeslot, and on that basis will select a rate for transmission of downlink data from the base station. The selection will typically be the highest available rate consistent with a specified frame error rate, or other such error rate. The transmission rate requested by a given remote terminal in a given timeslot is DRC.

P-0013[0013] The second value, R, is the rate at which a given remote terminal has received data from the base station, or other hub, as averaged by an appropriate procedure such as exponentially weighted averaging using a desired time constant.

P-0014[0014] In each timeslot n, the Proportional Fair scheduler will serve that remote terminal for which the ratio <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mfrac><mi>DRC</mi><mi>R</mi></mfrac></math><img file="US20030193906A1-20031016-M00001.TIF" id="EMI-M00001" he="17.03835" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20030193906A1-20031016-M00001.NB" /></attachments></maths>

P-0015[0015] is greatest. Thus, each remote terminal tends to receive service in those timeslots where its requested rate is highest—not in an absolute sense, but, rather, highest relative to the average rate at which that particular remote terminal has been receiving data in the recent past. Because that average rate will be small for underserved remote terminals, even a remote terminal with a poor channel will eventually be served. That is, the average rates are dynamic quantities, and they will converge toward a condition in which each remote terminal is served reasonably often.

P-0016[0016] In addition to achieving a balance between throughput and fairness, the Proportional Fair algorithm is attractive because it can be mathematically demonstrated that the long-term throughput achieved using that algorithm, over all remote terminals, satisfies an optimality condition.

P-0017[0017] However, the Proportional Fair algorithm, among others, does not place any floor or ceiling on the amount of service that a given remote terminal will receive. There remains a need for algorithms that can impose such floors or ceilings, so that, for example, users can contract for different guaranteed levels of service. In particular, there is a need for an efficient scheduling algorithm that seeks to optimize performance according to some measure subject to the imposition of floors, or of floors and ceilings, on the average rates of service to individual terminals.

SUMMARY OF THE INVENTION

P-0018[0018] We have discovered a new approach to the scheduling problem that involves such algorithms. In our approach, the scheduler keeps track of a variable which we refer to as the “token count” T. The token count for a given remote terminal is incremented by a target amount in each pertinent timeslot, but is also decremented each time that the remote terminal is served. The amount of the decrement for one timeslot is the amount of data served, i.e., transmitted to or from the remote terminal, in that timeslot. “Service” in this regard may refer to either uplink or downlink transmission.

P-0019[0019] In exemplary embodiments of the invention, the target amount by which T is incremented depends on the current value of T. Whenever the token count is non-negative (i.e., whenever it has a positive or zero value), the target amount is a desired floor, or lower limit, on an average amount of data delivered to or from the given remote terminal in one timeslot. Whenever the token count is negative, the target amount is a desired ceiling, or upper limit, on the same average amount of data delivered. Moreover, whenever incrementing T would cause T to go from a negative to a positive value, we have found it advantageous in at least some cases to reset T to zero instead.

P-0020[0020] In each timeslot, a weight is assigned to each remote terminal. The weight is proportional to a product of at least two factors: a function relating the individual remote terminal to overall network performance, and at least one increasing function of the token count. As in the Proportional Fair algorithm, each time a scheduling decision is made, the scheduler selects for service that remote terminal having the highest weight.

P-0021[0021] In specific embodiments, our invention involves a modification of the Proportional Fair algorithm. To implement our modified algorithm, the scheduler must keep track of DRC and R for each remote terminal and each timeslot, as explained above, and must also keep track of the “token count” T. Although DRC and R have been illustrated above in terms of rates of downlink transmission, it should be noted that they can equally well represent rates of uplink transmission in appropriate communication networks. In each timeslot, the weight assigned to each remote terminal is proportional to the ratio <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mrow><mfrac><mi>DRC</mi><mi>R</mi></mfrac><mo>,</mo></mrow></math><img file="US20030193906A1-20031016-M00002.TIF" id="EMI-M00002" he="17.03835" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20030193906A1-20031016-M00002.NB" /></attachments></maths>

P-0022[0022] described above, multiplied by an increasing function of the token count. That is, <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mfrac><mi>DRC</mi><mi>R</mi></mfrac></math><img file="US20030193906A1-20031016-M00003.TIF" id="EMI-M00003" he="17.03835" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20030193906A1-20031016-M00003.NB" /></attachments></maths>

P-0023[0023] is one example of a function, referred to above, relating the individual remote terminal to overall network performance.

BRIEF DESCRIPTION OF THE DRAWING

P-0024[0024]FIG. 1 is a simplified schematic drawing of a cell of a wireless communication system, including mobile stations, a base station, and queues of buffered packets within the base station.

P-0025[0025]FIG. 2 is a flowchart of an illustrative sequence of steps performed by a scheduler during the n'th timeslot according to the invention in one embodiment.

P-0026[0026]FIG. 3 is a number line illustrating the effect of the token counter for a given remote terminal according to the invention in an illustrative embodiment. Each point on the number line represents a possible value for the token counter. The present value of the token counter, as represented by a point on the number line, is referred to here as the “operating point.”

DETAILED DESCRIPTION

P-0027[0027] Initially, it should be noted that it is convenient to adopt a convention in which transmission rates are expressed in bits per timeslot, because under such a convention, the amount of data delivered in a given timeslot is numerically equal to the rate over that timeslot. We will adopt that convention in the following discussion. Accordingly, it should be borne in mind that when the amount of data served or the token count is said to be incremented or decremented by a “rate,” what is actually meant is the amount of data delivered at that rate in one timeslot.

P-0028[0028] Our scheduling method has specific applications to the scheduling of packet transmissions from a base station to mobile stations of a CDMA network. Accordingly, the illustrative embodiment described below is implemented by a scheduler in such a network. However, our scheduling method is more general in its range of applicability, and we envisage other useful applications in communication networks of other kinds, including both wired and wireless networks. In particular, our method is applicable not only for scheduling downlink transmissions, but also for scheduling uplink transmissions in a CDMA or other wireless network.

P-0029[0029] In the case of uplink scheduling, the queues to be served will reside in the individual mobile stations rather than in the base station, and the mobile station will report both channel information and the queue length to the base station at prescribed times. In one approach, the mobile station reports channel information by sending pilot signals to the base station. From the pilot signals, the base station evaluates the channel conditions and selects an appropriate DRC accordingly. In one of various alternative approaches, the mobile station uses a downlink signal to estimate the quality of the uplink channel, and sends a corresponding DRC back to the base station.

P-0030[0030] With reference to FIG. 1, element <b>10</b> represents a base station serving mobile stations (more generally, “users”) <b>15</b>.<b>1</b>-<b>15</b>.<b>4</b> within its cell or local reception area. Incoming packets <b>20</b> destined for the mobile stations are queued, while awaiting service, in buffers <b>25</b>.<b>1</b>-<b>25</b>.<b>4</b>, each buffer corresponding to a respective mobile station. Separate buffers are shown for convenience; actual implementations may employ a single buffer, with appropriate logical demarcations of the respective queues. Scheduler <b>30</b> within base station <b>10</b>, or otherwise associated with it, schedules the respective queues for service, and serves the packets of each queue by transmitting them to the destined mobile station.

P-0031[0031] The queue associated with only one mobile station is served in each scheduling interval. However, a packet may extend over more than one timeslot. For example, a CDMA network might permit packets to occupy anywhere from one to sixteen timeslots, depending on the rate of data transmission. Typically, once a mobile station has been selected for service, a sequence of timeslots will be scheduled for the mobile station, and it will continue to be served in each scheduled timeslot until the entire packet has been transmitted. Thus, the scheduling decisions will typically be made only in timeslots that have not already been scheduled.

P-0032[0032] A typical base station will have available a discrete set of available rates for transmitting data to the mobile stations. Packets will typically be sent to the served mobile station at the maximum acceptable rate from the set of rates that are available. Each rate will have a minimum power requirement dictated, at least in part, by channel conditions, interference conditions, and noise. Thus, the maximum acceptable rate will be the greatest rate whose power requirement can be met in view of total transmit power available, the possible need to reduce interference in neighboring cells, concurrent demands for transmit power by, e.g., network management and control signals, and the specified rate of errors, such as frame errors, that is deemed acceptable.

P-0033[0033] It is typical in CDMA systems, among others, for the mobile stations to send periodic signals to the base station that contain indications of channel quality. Such signals generally include an indication of the current SINR for signals received at the mobile station from the base station. Additionally, or alternatively, these signals indicate the data rate achievable on the downlink at, e.g., maximum transmit power. In the following description, we will assume that each mobile station sends an indication of the current SINR to the base station in each timeslot.

P-0034[0034] Timeslots are advantageously made short enough that channel conditions can be assumed constant over the duration of one timeslot. Channel fluctuations are caused by fading effects, which tend to be manifested on both a short time scale having a characteristic interval of several milliseconds, and on a longer timescale, having a characteristic interval of seconds, or even tens of seconds. The rapidly fluctuating effects are often referred to as “fast fading,” and the slowly fluctuating effects, which may be due, inter alia, to user mobility, are often referred to as “shadow fading.”

P-0035[0035] An exemplary scheduling interval capable of substantially following fast fading effects is 1.67 ms, although intervals as small as 0.5 ms or less and as large as 5 ms or more, are also useful for such purpose.

P-0036[0036] An illustrative sequence of steps performed by the scheduler during the n'th timeslot will now be described with reference to FIG. 2. It should be noted that the particular sequence to be described is meant to be illustrative only, and not limiting as to the scope of the invention. The specific computational steps that are described will typically be carried out by a programmable digital signal processor (DSP), but provided that sufficient processing speed is available, they can equivalently be carried out by any general-purpose or special-purpose digital computing device operating under the control of an appropriate software, hardware, or firmware program. Those skilled in the art will appreciate that the specific computational results to be achieved may be reached by any of numerous combinations of mathematical steps. All such combinations of mathematical steps are deemed equivalents for purposes of the present invention.

P-0037[0037] At block <b>50</b>, the scheduler obtains a DRC, denoted DRC_i(n), from each remote terminal. Here, the integer n indexes the timeslots, and the interger i indexes the respective remote terminals. The DRC indicates to the base station which of the available discrete data transmission rates is requested by the remote terminal for the current timeslot. Typically, the DRC is a four-bit control sequence, the “Data Rate Control” sequence.

P-0038[0038] At block <b>60</b>, the scheduler obtains the parameters R_i(n) and T_i(n) from memory locations, which exemplarily reside at the base station. As noted above, R_i(n) is an average rate at which a given remote terminal has received data from the base station, and T_i(n) is a token count. Details of the computations that update R_i(n) and T_i(n) are discussed below. At startup, T_i(n) will typically be initialized to zero, and R_i(n) will typically be initialized to a fractionf of DRC_i(n); i.e., to f·DRC_i(n). The fraction f is, for example, 0.1. In another example, 1/f is an estimate of the current number of active users.

P-0039[0039] At block <b>70</b>, the weight W_i(n) is computed for each of the remote terminals. For the i'th remote terminal, in timeslot n, the weight is defined by: <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mrow><mrow><msub><mi>W</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><msub><mi>DRC</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mrow><msub><mi>R</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mfrac><mo></mo><mrow><msup><mi></mi><mrow><msub><mi>a</mi><mi>i</mi></msub><mo></mo><mrow><msub><mi>T</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow></msup><mo></mo><mstyle><mtext> </mtext></mstyle><mo>.</mo></mrow></mrow></mrow></math><img file="US20030193906A1-20031016-M00004.TIF" id="EMI-M00004" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00004" attachment-type="nb" file="US20030193906A1-20031016-M00004.NB" /></attachments></maths>

P-0040[0040] In the above expression, a_iis an adjustable parameter, which may be set differently for each remote terminal. The parameter a_iaffects the timescale over which the actual rate of service will tend to track the target rate or rates.

P-0041[0041] A typical value for <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mfrac><mn>1</mn><msub><mi>a</mi><mi>i</mi></msub></mfrac></math><img file="US20030193906A1-20031016-M00005.TIF" id="EMI-M00005" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00005" attachment-type="nb" file="US20030193906A1-20031016-M00005.NB" /></attachments></maths>

P-0042[0042] is given by the product of the target minimum average transmission rate, multiplied by the time constant τ for exponentially weighted averaging of the transmission rate. Exponentially weighted averaging is discussed below. A typical value for the target minimum rate in CDMA systems is 9.6 kbit per sec., or 16 bits per timeslot. An alternative, typical value is 28.8 kbit per sec., or 48 bits per timeslot.

P-0043[0043] The exponential function that multiples the DRC/R ratio is one example of an increasing function of the token count T_i(n). Other increasing functions of the token count may also be used to multiply the DRC/R ratio. Particularly desirable are functions that are convex because with such functions, the relative impact of the token count on the behavior of the system grows as the token count grows. The exponential function is advantageous because, among other things, it is conveniently implemented.

P-0044[0044] At block <b>80</b>, that remote terminal j is found for which the weight W_j(n) is greatest. In the event of a tie, any of various methods, such as random choice, can be used to make a definite selection. At block <b>90</b>, timeslot n is assigned to remote terminal j.

P-0045[0045] Advantageously, remote terminal j is scheduled for service only if it is active; that is, only if it has queued data. If scheduling is limited to active terminals only, then it may be advantageous to also limit the weight-function computation of block <b>70</b> to active terminals only.

P-0046[0046] At block <b>100</b>, the average rate R_i(n) for each remote terminal is updated to R_i(n+1). The timeslot index has been incremented because the updated value will be used to compute the weight for the next timeslot. As noted above, R_i(n) is an average computed over some appropriate length of time. One useful averaging method in this regard is exponentially weighted averaging with a time constant τ. An exemplary time constant is 1024 timeslots, which in typical CDMA networks is equivalent to 1.71 seconds.

P-0047[0047] According to the techniques of exponentially weighted averaging, R_i(n) is updated according to the following: <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mrow><mrow><msub><mi>R</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mfrac><mn>1</mn><mi>τ</mi></mfrac></mrow><mo>)</mo></mrow><mo></mo><mrow><msub><mi>R</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><mrow><msub><mi>r</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo>.</mo></mrow></mrow></mrow></mrow></math><img file="US20030193906A1-20031016-M00006.TIF" id="EMI-M00006" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00006" attachment-type="nb" file="US20030193906A1-20031016-M00006.NB" /></attachments></maths>

P-0048[0048] In the preceding expression, r_i(n) is the rate of transmission to remote terminal i in timeslot n. This rate r_i(n) will typically take the value DRC_i(n) if remote terminal i is being served, and otherwise will take the value zero.

P-0049[0049] It should be noted that the selection of a time constant depends on the maximum length of time during which an individual remote terminal can tolerably be denied service. That is, a sudden drop in the quality of the channel to a given remote terminal will elicit from that terminal a low DRC, which will result in a low weight for that remote terminal and concomitant denial of service, until a rise in the token count and a drop in R_iare sufficient to compensate for the drop in DRC. The larger the time constant, the longer it will take R_ito decay to a low value. On the other hand, throughput is benefited when R_idecays slowly, because in that case service will be withheld from remote terminal i for a relatively long period of time, during which the channel has a chance to recover.

P-0050[0050] At block <b>110</b>, the token count T_i(n) for each remote terminal is updated to T_i(n+1). The updating of the token count is described by the following:

<i>T</i>_i(<i>n+</i>1)=<i>T</i>_i(<i>n</i>)+<i>X</i>_i(<i>n</i>)−<i>r</i>_i(<i>n</i>).

P-0051[0051] The term X_i(n) in the preceding expression takes on different values, depending on the sign of T_i(n). If T_i(n) is positive or zero, X_i(n) takes on the value R_i^min, which is a desired floor, or lower limit, on the average transmission rate for user i. This floor may be set differently for each remote terminal i. If T_i(n) is negative, X_i(n) takes on the value R_i^max, which is a desired ceiling, or upper limit, on R_i. This ceiling may also be set differently for each remote terminal i. These settings may be made in accordance, e.g., with contracted levels of service for the users who correspond to the respective remote terminals.

P-0052[0052] Although it is not absolutely required, we have found through numerical simulations that the step represented by block <b>120</b> of FIG. 2 tends to improve the performance of the algorithm. At block <b>120</b>, if the token counter had a negative value at time n and a positive value at time n+1, then the counter is reset to zero in timeslot n+1.

P-0053[0053] For some or all of the remote terminals, it may be desirable to set a floor without setting a corresponding ceiling. This is readily achieved, in effect, simply by setting the ceiling to an extremely high value, and retaining the reset feature of block <b>120</b>. If that reset feature is omitted, then operation without a ceiling is readily achieved by immediately resetting the token counter to zero any time it goes negative.

P-0054[0054] The effect of the token counter for a given remote terminal is conveniently described with reference to FIG. 3. FIG. 3 is a number line, each point of which represents a possible value for the token counter. The present value of the token counter, as represented by a point on the number line, will be referred to here as the “operating point.” Displacement of the operating point to the right tends to increase the frequency of service to the remote terminal, whereas displacement to the left tends to decrease the frequency of service. In each timeslot, the net change in the operating point is the resultant of a shift to the right by one of the two possible values of X_i, and—only if the remote terminal has been served—a shift to the left by the pertinent rate, which for purposes of illustration is assumed to be the pertinent DRC.

P-0055[0055] Thus, if the operating point is to the right of zero and, on average, the remote terminal is being served at a rate less than R_i^min, the operating point will continue shifting to the right until the average rate of service equals R_i^min. At that point, a state of statistical equilibrium will be reached, and the operating point will remain approximately stationary on a timescale, typically, of seconds.

P-0056[0056] On the other hand, if the remote terminal is being served at an average rate greater than R_i^min, the operating point will shift leftward until either: (1) the average rate of service drops to R_i^min, thus achieving equilibrium, or (2) if the average service rate is also greater than R_i^max, the operating point crosses zero. If the operating point crosses zero, it will continue to shift leftward until the average rate of service drops to R_i^max, and equilibrium is achieved. If the average rate of service lies between R_i^minand R_i^max, then once the operating point reaches the vicinity of zero, it will go on oscillating about zero.

P-0057[0057] If no effective ceiling R_i^maxis to be imposed, then either of the approaches described above will have the effect that once the operating point reaches zero, it will stay close to zero so long as the average rate of service is at least R_i^min.

P-0058[0058] Those skilled in the art will appreciate that the boundary between the regime of incrementation by R_i^minand the regime of incrementation by R_i^maxcan be shifted from zero by including an additive constant in the token count. For purposes of defining the present invention, an embodiment of the invention resulting from any such modification is deemed equivalent to the described embodiment.

P-0059[0059] Those skilled in the art will also appreciate that our method may be practiced using various embodiments of a token counter alternative to that described here. For example, the token counter T_i(n) described above may be replaced by a pair of token counters G_i(n), H_i(n), and the weight function described above replaced by an expression such as <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>W</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><msub><mi>DRC</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mrow><msub><mi>R</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mfrac><mo></mo><msup><mi></mi><mrow><mrow><msub><mi>a</mi><mi>i</mi></msub><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo></mo><mrow><msub><mi>H</mi><mi>i</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow></mrow></msup></mrow></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo>,</mo></mrow></math><img file="US20030193906A1-20031016-M00007.TIF" id="EMI-M00007" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00007" attachment-type="nb" file="US20030193906A1-20031016-M00007.NB" /></attachments></maths>

P-0060[0060] where the argument of the increasing, e.g. exponential, function is now a weighted sum of the two token counters. In the preceding expression, G_i(n) is decremented by r_i(n), as above, and H_i(n) is incremented by r_i(n), whenever the pertinent remote terminal is served. In each timeslot, G_i(n) is incremented by the floor amount, and H_i(n) is decremented by the ceiling amount. Negative values of G_i(n) and H_i(n) are reset to zero.

P-0061[0061] It is well known that the Proportional Fair scheduling algorithm has the optimality property that it maximizes the quantity <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mrow><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo></mo><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><msub><mi>R</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>,</mo></mrow></math><img file="US20030193906A1-20031016-M00008.TIF" id="EMI-M00008" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00008" attachment-type="nb" file="US20030193906A1-20031016-M00008.NB" /></attachments></maths>

P-0062[0062] wherein the summation is taken over all remote terminals i. More precisely, in the asymptotic limit of infinite averaging time τ, the quantity <maths id="MATH-US-00009" num="9"><math overflow="scroll"><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo></mo><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><msub><mi>R</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></mrow></math><img file="US20030193906A1-20031016-M00009.TIF" id="EMI-M00009" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00009" attachment-type="nb" file="US20030193906A1-20031016-M00009.NB" /></attachments></maths>

P-0063[0063] resulting from Proportional Fair scheduling can be no less than that resulting from any other scheduling algorithm. In that sense, over the long term, when total throughput for all remote terminals is taken into account, no other scheduling algorithm can do better than Proportional Fair scheduling. We consider it likely that when the scheduling is constrained by floors R_i^minand ceilings R_i^maxon the average rates of service to the individual remote terminals, our new algorithm will have an optimality property of the same form; i.e., that it maximizes the quantity <maths id="MATH-US-00010" num="10"><math overflow="scroll"><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo></mo><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><msub><mi>R</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></mrow></math><img file="US20030193906A1-20031016-M00010.TIF" id="EMI-M00010" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00010" attachment-type="nb" file="US20030193906A1-20031016-M00010.NB" /></attachments></maths>

P-0064[0064] subject to the floor and ceiling constraints.

P-0065[0065] In an alternate embodiment of the invention, it is the throughput <maths id="MATH-US-00011" num="11"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mi>i</mi><mstyle><mtext> </mtext></mstyle></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><msub><mi>R</mi><mi>i</mi></msub></mrow></math><img file="US20030193906A1-20031016-M00011.TIF" id="EMI-M00011" he="22.08465" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00011" attachment-type="nb" file="US20030193906A1-20031016-M00011.NB" /></attachments></maths>

P-0066[0066] rather than <maths id="MATH-US-00012" num="12"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mi>i</mi><mstyle><mtext> </mtext></mstyle></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><msub><mi>R</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></mrow></math><img file="US20030193906A1-20031016-M00012.TIF" id="EMI-M00012" he="22.08465" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00012" attachment-type="nb" file="US20030193906A1-20031016-M00012.NB" /></attachments></maths>

P-0067[0067] that is optimized subject to the floor constraint or to the floor and ceiling constraints. In this alternate embodiment, the weight function for the i'th remote terminal is, e.g., DRC_i(n)e^a^_i^T^_i. (The argument n has been omitted here for brevity.)

P-0068[0068] In a broader aspect, the invention includes within its scope methods for optimizing various measures of network performance that all share the step of selecting the hightest-weighted remote terminal for service in each pertinent timeslot. If the performance measure is denoted F(R₁, . . . , R_N), then in each case the weight function for the i'th remote terminal is the product of <maths id="MATH-US-00013" num="13"><math overflow="scroll"><mfrac><mrow><mo>∂</mo><mi>F</mi></mrow><mrow><mo>∂</mo><msub><mi>R</mi><mi>i</mi></msub></mrow></mfrac></math><img file="US20030193906A1-20031016-M00013.TIF" id="EMI-M00013" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00013" attachment-type="nb" file="US20030193906A1-20031016-M00013.NB" /></attachments></maths>

P-0069[0069] times e^a^_i^T^_i, or else it is the product of <maths id="MATH-US-00014" num="14"><math overflow="scroll"><mfrac><mrow><mo>∂</mo><mi>F</mi></mrow><mrow><mo>∂</mo><msub><mi>R</mi><mi>i</mi></msub></mrow></mfrac></math><img file="US20030193906A1-20031016-M00014.TIF" id="EMI-M00014" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00014" attachment-type="nb" file="US20030193906A1-20031016-M00014.NB" /></attachments></maths>

P-0070[0070] times some other increasing, preferably convex, function of one or more token counters.

P-0071[0071] In each such instance, the i'th component <maths id="MATH-US-00015" num="15"><math overflow="scroll"><mfrac><mrow><mo>∂</mo><mi>F</mi></mrow><mrow><mo>∂</mo><msub><mi>R</mi><mi>i</mi></msub></mrow></mfrac></math><img file="US20030193906A1-20031016-M00015.TIF" id="EMI-M00015" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00015" attachment-type="nb" file="US20030193906A1-20031016-M00015.NB" /></attachments></maths>

P-0072[0072] of the gradient function <maths id="MATH-US-00016" num="16"><math overflow="scroll"><mrow><mo>(</mo><mrow><mfrac><mrow><mo>∂</mo><mi>F</mi></mrow><mrow><mo>∂</mo><msub><mi>R</mi><mn>1</mn></msub></mrow></mfrac><mo>,</mo><mi>…</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mfrac><mrow><mo>∂</mo><mi>F</mi></mrow><mrow><mo>∂</mo><msub><mi>R</mi><mi>N</mi></msub></mrow></mfrac></mrow><mo>)</mo></mrow></math><img file="US20030193906A1-20031016-M00016.TIF" id="EMI-M00016" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00016" attachment-type="nb" file="US20030193906A1-20031016-M00016.NB" /></attachments></maths>

P-0073[0073] relates the i'th remote terminal to overall network performance. In the examples given above <maths id="MATH-US-00017" num="17"><math overflow="scroll"><mfrac><mn>1</mn><msub><mi>R</mi><mi>i</mi></msub></mfrac></math><img file="US20030193906A1-20031016-M00017.TIF" id="EMI-M00017" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00017" attachment-type="nb" file="US20030193906A1-20031016-M00017.NB" /></attachments></maths>

P-0074[0074] and 1 are the i'th components of the gradient function for particular choices of the function F(R₁, . . . , R_N), namely, <maths id="MATH-US-00018" num="18"><math overflow="scroll"><mrow><mrow><mrow><mi>F</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>R</mi><mn>1</mn></msub><mo>,</mo><mi>…</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><msub><mi>R</mi><mi>N</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><msub><mi>R</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>and</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>F</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>R</mi><mn>1</mn></msub><mo>,</mo><mi>…</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><msub><mi>R</mi><mi>N</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><msub><mi>R</mi><mi>i</mi></msub></mrow></mrow></mrow><mo>,</mo></mrow></math><img file="US20030193906A1-20031016-M00018.TIF" id="EMI-M00018" he="24.97635" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00018" attachment-type="nb" file="US20030193906A1-20031016-M00018.NB" /></attachments></maths>

P-0075[0075] respectively.