|
|
|
|
|
|
|
In mobile communications with many users and randomly time varying channels, at any time the scheduler has a conflict between selecting the user with the highest current rate (assuring maximum utilization of the resource) and fairness (giving attention to users with a past record of poor rates, to assure fair throughput). The Proportional Fair Sharing scheduler (PFS) of the Qualcomm High Data Rate (HDR) system and related algorithms are designed to deal with such conflicts. Our aim is to put such algorithms on a sure mathematical footing and analyze their behavior. The algorithms are of the stochastic approximation type. It is shown that the limiting behavior of the sample paths of the throughputs converges to the solution of an intuitively reasonable ordinary differential equation, which is akin to a mean flow. We show that the ODE has a unique equilibrium and that it is characterized as optimizing a concave utility function, which shows that PFS is not ad-hoc, but actually corresponds to a reasonable maximization problem. The ODE can be used to get qualitative information that would not otherwise be available. The results depend on the fact that the mean ODE has a special form that arises in problems with certain types of competitive behavior. There is a large set of such algorithms, each one corresponding to a concave utility function. This set allows a choice of tradeoffs between the current rate and throughout. Extensions to multiple antenna and frequency systems are given. Finally, the infinite backlog assumption is dropped and the data is allowed to arrive at random. This complicates the analysis, but the same results hold. Many forms of the systems can be dealt with.
This is a joint work with Philip A. Whiting from Bell Labs.
|
|
|
|
|
|
|
|