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

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 (.m1(k),.,.mN(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\zenQn , where \ze=(\ze1,.,\zeN) is some fixed nonzero vector with nonnegative components, and Q1,.,QN are the queue lengths. We study the MaxWeight discipline which always chooses a decision k maximizing .n.n[Qn]..mn(k), that is, k.argmaxi.n.n[Qn]..mn(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 (.1Q.1,.,.NQ.N) 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 .n.nQ.+1n at all times, and cumulative cost (with this rate) over finite intervals.