## 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γ _{n}Q _{n} ^{β+1} at all times, and cumulative cost (with this rate) over finite intervals.

Original language | English (US) |
---|---|

Pages (from-to) | 1-53 |

Number of pages | 53 |

Journal | Annals of Applied Probability |

Volume | 14 |

Issue number | 1 |

DOIs | |

State | Published - Feb 2004 |

Externally published | Yes |

## 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