Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm

Research output: Contribution to journalArticle

Abstract

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision "produces" a certain vector of "commodities"; it also has associated "traditional" queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable. We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.

Original languageEnglish (US)
Pages (from-to)401-457
Number of pages57
JournalQueueing Systems
Volume50
Issue number4
DOIs
StatePublished - Aug 1 2005
Externally publishedYes

    Fingerprint

Keywords

  • Congestion control
  • Convex optimization
  • Power and rate constraints
  • Primal-dual algorithm
  • Queueing networks
  • Resource allocation
  • Scheduling
  • Stability
  • Wireless

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Cite this