Publication 2004-002

We are concerned with the scheduling decisions (allocation of transmitter time and power) for multi-access mobile communications for data communications in a randomly time varying environment. Time is divided into small scheduling intervals, called slots, and information on the channel rates for the various users is available at the start of the slot, when the user selections are made. There is a conflict between selecting the user that can get the most immediate data through and helping users with poor average throughputs. The Proportional Fair Sharing method (PFS) deals with such conflicts. In [4], [6] the convergence and basic qualitative properties were analyzed via stochastic approximation methods. The paths of the (suitably interpolated) throughputs converge to the solution of an ODE, akin to a mean flow. The behavior of the ODE completely describes the behavior of PFS. It has a unique equilibrium point that is asymptotically stable and optimal for PFS in that it is the maximizer of a concave utility function. There is a large family of such algorithms, each member corresponding to a concave utility function. Most past work assumed an infinite backlog of data. In many applications, the data arrival process for some users is bursty and data is queued until transmission, there might be minimal throughput constraints, or a balance between queue length (or delay) and throughput sought. The fact that some queues might be empty at times raises new issues. Natural modifications of PFS for these cases are shown to have the same properties. Simulations illustrate many of the unique features and the tradeoffs that are possible, Keywords: Proportional fair sharing, throughput constraints, delay constraints, multi-access control, time varying channels