Instability of MaxWeight scheduling algorithms

P.M. Ven, van de, S.C. Borst, V. Shneer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

50 Citations (SciVal)
174 Downloads (Pure)


MaxWeight scheduling algorithms provide an effective mechanism for achieving queue stability and guaranteeing maximum throughput in a wide variety of scenarios. The maximum-stability guarantees however rely on the fundamental premise that the system consists of a fixed set of sessions with stationary ergodic traffic processes. In the present paper we examine a scenario where the population of active sessions varies over time, as sessions eventually end while new sessions occasionally start. We identify a simple necessary and sufficient condition for stability, and show that MaxWeight policies may fail to provide maximum stability. The intuitive explanation is that these policies tend to give preferential treatment to flows with large backlogs, so that the rate variations of flows with smaller backlogs are not fully exploited. In the usual framework with a fixed collection of flows, the latter phenomenon cannot persist since the flows with smaller backlogs will build larger queues and gradually start receiving more service. With a dynamic population of flows, however, MaxWeight policies may constantly get diverted to arriving flows, while neglecting the rate variations of a persistently growing number of flows in progress with relatively small remaining backlogs. We also perform extensive simulation experiments to corroborate the analytical findings.
Original languageEnglish
Title of host publicationProceedings 28th IEEE International Conference on Computer Communications (INFOCOM 2009, Rio de Janeiro, Brazil, April 19-25, 2009)
PublisherInstitute of Electrical and Electronics Engineers
ISBN (Print)978-1-4244-3512-8
Publication statusPublished - 2009


Dive into the research topics of 'Instability of MaxWeight scheduling algorithms'. Together they form a unique fingerprint.

Cite this