# Convergence of Proportional-Fair Sharing Algorithms Under General Conditions

##
Harold J. Kushner

### Brown University, USA

### Résumé:

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.