MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic

• 成果类型: Article
• 署名作者: Stolyar, AL
• 署名单位: Alcatel-Lucent; Lucent Technologies; AT&T
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1075828046
• 发表日期: 2004
• 页码: 1-53
• 关键词: Asymptotic Optimality; parallel servers; queuing-networks; multiclass; queues; SYSTEM; LIMITS

摘要

We consider a generalized switch model, which includes as special cases the model of multiuser data scheduling over a wireless medium, the input-queued cross-bar switch model and a discrete time version of a parallel server queueing system. Input flows n = 1,...,N are served in discrete time by a switch. The switch state follows a finite state, discrete time Markov chain. In each state m, the switch chooses a scheduling decision k from a finite kset K(m), which has the associated service rate vector (mu(1)(m)(k),...,mu(N)(m)(k)). We consider a heavy traffic regime, and assume a Resource Pooling (RP) condition. Associated with this condition is a notion of workload X = Sigma(n)zeta(n)Q(n), where zeta = (zeta(1),...zeta(N)) is some fixed nonzero vector with nonnegative components, and Q(1),...,Q(N) are the queue lengths. We study the MaxWeight discipline which always chooses a decision k maximizing Sigma(n)gamma(n)[Q(n)](beta)mu(n)(m)(k), that is, k is an element of arg (1)max (n)Sigmagamman[Q(n)](beta)mu(n)(m)(i), where beta > 0, gamma(1) > 0,...,gamma(N) > 0 are arbitrary parameters. We prove that under MaxWeight scheduling and the RP condition, in the heavy traffic limit, the queue length process has the following properties: (a) The vector (gamma(1)Q(1)(beta),...,gamma(N)Q(N)(beta)) is always proportional to (this is State Space Collapse), (b) the workload process converges to a Reflected Brownian Motion, (c) MaxWeight minimizes the workload among all disciplines. As a corollary of these properties, MaxWeight asymptotically minimizes the holding cost rate (n)Sigmagamma(n)Q(n)(beta+1) at all times, and cumulative cost (with this rate) over finite intervals.