Scheduling of a generalized switch: Heavy traffic regime

Research output: Contribution to journalArticle

Abstract

We consider a generalized switch model, which is a natural model of scheduling multiple data flows over a shared time-varying wireless environment. It also includes as special cases the input-queued cross-bar switch model, and a discrete time version of a parallel server queuing system. Input flows, n = 1,..., N, are served in discrete time by a switch. Switch state follows a finite 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. We study the MaxWeight discipline which always chooses a decision where Qn'S are the queue lengths, and γn, are arbitrary positi ve parameters. It has been shown in previous work, that MaxWeight discipline is optimal in terms of system stability, i.e. it stabilizes queues if it is feasible to do all. We show that MaxWeight also has striking optimality and self-organizing properties in the heavy traffic limit regime. Namely, under a non-restrictive additional conditions, MaxWeight minimizes system equivalent workload Where some fixed vector with positive components; moreover, in the limit, vector (γ1Q1,... γNQN)is always proportional to ν*, These properties of MaxWeight discipline can be utilized in applications to optimize various system performance criteria.

Original languageEnglish (US)
Pages (from-to)143-164
Number of pages22
JournalOperations Research/ Computer Science Interfaces Series
Volume23
DOIs
StatePublished - Dec 1 2003
Externally publishedYes

    Fingerprint

Keywords

  • Generalized switch
  • Heavy traffic
  • Maxweight
  • Queueing
  • Scheduling
  • Wireless

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research

Cite this