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

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,\ldots,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 $(\mu_1^m(k),\ldots,\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=\sum_n \zen Q_n$, where $\ze=(\ze_1,\ldots,\ze_N)$ is some fixed nonzero vector with nonnegative components, and $Q_1,\ldots,Q_N$ are the queue lengths. We study the MaxWeight discipline which always chooses a decision $k$ maximizing $\sum_n \gamma_n [Q_n]^{\beta} \mu_n^m(k)$, that is, \[ k \in \mathop{\arg\max}_{i} \sum_n \gamma_n [Q_n]^{\beta} \mu_n^m(i), \] where $\beta>0$, $\gamma_1>0,\ldots,\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},\ldots,\gamma_N Q_N^{\beta})$ is always proportional to $\ze$ (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 \[ \sum_n \gamma_n Q_{n}^{\beta+1} \] at all times, and cumulative cost (with this rate) over finite intervals.