Optimal utility based multi-user throughput allocation subject to throughput constraints

Matthew Andrews, Lijun Qian, Alexander Stolyar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of scheduling multiple users sharing a time-varying wireless channel. (As an example, this is a model of scheduling in 3G wireless technologies, such as CDMA2000 3G1xEV-DO downlink scheduling.) We introduce an algorithm which seeks to optimize a concave utility function ∑ i. H i(R i] of the user throughputs R i, subject to certain lower and upper throughput bounds: R i min ≤ R i ≤ R i max. The algorithm, which we call the Gradient algorithm with Minimum/Maximum Rate constraints (GMR) uses a token counter mechanism, which modifies an algorithm solving the corresponding unconstrained problem, to produce the algorithm solving the problem with throughput constraints. Two important special cases of the utility functions are ∑ i log R i and ∑ i R i, corresponding to the common Proportional Fairness and Throughput Maximization objectives. We study the dynamics of user throughputs under GMR algorithm, and show that GMR is asymptotically optimal in the following sense. If, under an appropriate scaling, the throughput vector R(t) converges to a fixed vector R* as time t → ∞ then R* is an optimal solution to the optimization problem described above. We also present simulation results showing the algorithm performance.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Pages2415-2424
Number of pages10
DOIs
StatePublished - 2005
Externally publishedYes
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

NameProceedings - IEEE INFOCOM
Volume4
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2005
Country/TerritoryUnited States
CityMiami, FL
Period3/13/053/17/05

Keywords

  • 3G
  • CDMA
  • Gradient algorithm
  • Guaranteed rate
  • Maximum throughput
  • Proportional fair
  • QoS
  • Rate constraints
  • Scheduling
  • Time varying channel
  • Wireless

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimal utility based multi-user throughput allocation subject to throughput constraints'. Together they form a unique fingerprint.

Cite this