Greedy primal-dual algorithm for dynamic resource allocation in complex networks |
| |
Authors: | Alexander L Stolyar |
| |
Institution: | (1) Bell Labs, Lucent Technologies, 600 Mountain Ave., 2C-322, Murray Hill, NJ, 07974 |
| |
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.
AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12 |
| |
Keywords: | Queueing networks Dynamic scheduling Resource allocation Convex optimization Non-linear constraints Greedy primal-dual algorithm |
本文献已被 SpringerLink 等数据库收录! |
|