Greedy primal-dual algorithm for dynamic resource allocation in complex networks

Research output: Contribution to journalArticle

Abstract

In Stolyar (Queueing Systems 50 (2005) 401-457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several "commodities.") Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401-457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples.

Original languageEnglish (US)
Pages (from-to)203-220
Number of pages18
JournalQueueing Systems
Volume54
Issue number3
DOIs
StatePublished - Nov 1 2006
Externally publishedYes

    Fingerprint

Keywords

  • Convex optimization
  • Dynamic scheduling
  • Greedy primal-dual algorithm
  • Non-linear constraints
  • Queueing networks
  • Resource allocation

ASJC Scopus subject areas

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

Cite this