Convergence of proportional-fair sharing algorithms under general conditions

We are concerned with the allocation of the base station transmitter time in time varying mobile communications with many users who are transmitting data. Time is divided into small scheduling intervals, and the channel rates for the various users are available at the start of the intervals. Since the rates vary randomly, in selecting the current user there is a conflict between full use (by selecting the user with the highest current rate) and fairness (which entails consideration for users with poor throughput to date). The Proportional Fair Scheduler (PFS) of the Qualcomm High Data Rate (HDR) system and related algorithms are designed to deal with such conflicts. The aim here is to put such algorithms on a sure mathematical footing and analyze their behavior. The available analysis [6], while obtaining interesting information, does not address the actual convergence for arbitrarily many users under general conditions. Such algorithms are of the stochastic approximation type and results of stochastic approximation are used to analyze the long term properties. 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 mea