Accession Number:

ADA461871

Title:

Asymptotic Properties of Proportional-Fair Sharing Algorithms

Descriptive Note:

Conference paper

Corporate Author:

BROWN UNIV PROVIDENCE RI DIV OF APPLIED MATHEMATICS

Report Date:

2002-05-30

Pagination or Media Count:

10.0

Abstract:

We are concerned with the allocation of channel or transmitter resources for time varying mobile communications. There are many users who are competing to transmit data over the resource. Time is divided into small scheduling intervals, and information on the channel rates for the various users is available at the start of the intervals. Since the rates vary randomly, there is a conflict at any time between fully exploiting the channel by selecting the user with the highest current rate and being fair giving attention to users with poor rates, to assure a fair throughput for them. The Proportional Fair Scheduler PFS of the Qualcomm High Data Rate HDR system and related algorithms are designed to deal with such conflicts. There is little analysis available for such systems and our aim is to put them on a sure mathematical footing and analyze their behavior. Such algorithms are of the stochastic approximation type and results of stochastic approximation are used to analyze the long term properties of this class. The limiting behavior of the throughputs converges to the solution of an ordinary differential equation a mean ODE, which is akin to a mean flow. The ODE has a unique equilibrium and it is optimal in the sense that it optimizes a concave utility function. The results depend on the fact that the mean ODE has a special form that arises in problems with certain types of repeated stochastic games with competitive behavior. There are a large family of such algorithms, each member corresponding to a concave utility function. Thus, is not simply ad-hoc, but actually corresponds to a reasonable maximization problem. There are extensions to multiple antenna and frequency systems. Also, the infinite backlog assumption can be dropped and the data is allowed to arrive at random.

Subject Categories:

  • Operations Research
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE