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. Finite number N of input flows are served in discrete time by a switch. Switch state m follows a finite discrete time Markov chain. In each state m, the switch can choose a scheduling decision k from a finite set K(m); each scheduling decision has the associated vector of service rates at which queues are served. We consider a heavy traffic regime, and assume a (very non-restrictive in applications) resource pooling (RP) condition. Associated with the RP condition is a notion of workload, which is a linear combination of queue length with some fixed non-negative coefficients. We study the WaxWeight discipline which always chooses a decision maximizing the sum of service rates weighted by a power law function of the corresponding queue lengths. MAIN RESULT: Under MaxWeight scheduling and CRP condition, in the heavy traffic limit, the queue length process has the following properties: (a) State Space Collapse - vector of queue lengths is always proportional to some fixed vector, (b) the workload process converges to a Reflected Brownian Motion, and (c) MaxWeight minimizes the workload among all disciplines. As a corollary, MaxWeight asymptotically minimizes the (power law) holding cost rate at all times, and cumulative cost over finite intervals. (This paper is a generalized version of the report ITD-01-41671V. )