Asymptotic Properties of Proportional-Fair Sharing Algorithms

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 30, 2002
Accession Number
ADA461871

Entities

People

  • Harold J. Kushner
  • Philip A. Whiting

Organizations

  • Brown University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Convergence
  • Equations
  • Information Operations
  • Intervals
  • Mathematics
  • Packet Loss
  • Scheduling (Production)
  • Sequences
  • Simulations
  • Standards
  • Stationary
  • Statistics
  • Throughput

Readers

  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Calculus or Mathematical Analysis