Past Awards
- "Maxweight Scheduling in a Generalized Switch: State Space Collapse and Workload Minimization in Heavy Traffic," The Annals of Applied Probability, 14:1-53, 2004.
MaxWeight scheduling algorithms have been studied intensively in recent years, first as a means of allocating capacity in communication switches, and then in other, similar contexts involving dynamic capacity allocation. MaxWeight rules are attractive because of their meager data requirements (only buffer contents are used), but are also known is to be “throughput optimal,” meaning that MaxWeight stabilizes a system whenever stability is achievable.
This paper considers an abstract model of a discrete-time processing system that the author calls a “generalized switch.” It includes the classical crossbar switch as a particular case, and discrete-time versions of various standard queuing models fit within its framework as well. In this very general setting, the following efficiency property is proved: in the heavy traffic parameter regime (properly defined), MaxWeight minimizes “system workload” under diffusion scaling, given an additional hypothesis which ensures that “workload” is unambiguously defined.
This is a surprising result, especially given that MaxWeight uses no explicit information about the demand environment. It complements the known stability result cited above with a strikingly positive characterization of delay performance. The paper has been frequently cited in the years since its appearance in preliminary form, and has already had a strong influence on the work of other researchers.
J. Michael Harrison, Chair
Richard R. Weber
Sean Meyn