Instability of MaxWeight scheduling algorithms

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

Research output: Book/ReportReportAcademic

81 Downloads (Pure)

Abstract

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
Place of PublicationEindhoven
PublisherEurandom
Number of pages15
Publication statusPublished - 2011

Publication series

NameReport Eurandom
Volume2011021
ISSN (Print)1389-2355

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

Cite this