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

Research output: Contribution to journalArticle

Abstract

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 set K(m), which has the associated service rate vector (μ 1 m(k),..., μ 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 = Σ n ζ n Q n, where ζ = (ζ 1,..., ζ 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 Σ nγ n[Q n] β μ n m(k), that is, k ∈ arg maxi Σn γ n[Q n] β μ n m (i), where β > 0, γ 1 > 0,..., γ 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 (γ 1 Q 1 β,..., γ N Q N β) 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γ nQ n β+1 at all times, and cumulative cost (with this rate) over finite intervals.

Original languageEnglish (US)
Pages (from-to)1-53
Number of pages53
JournalAnnals of Applied Probability
Volume14
Issue number1
DOIs
StatePublished - Feb 1 2004

Keywords

  • Asymptotic optimality
  • Equivalent workload formulation
  • Generalized switch
  • Heavy traffic limit
  • MaxWeight scheduling
  • Queueing networks
  • Resource pooling
  • State space collapse

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic'. Together they form a unique fingerprint.

  • Cite this