Instability of MaxWeight scheduling algorithms

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

44 Citaten (Scopus)
107 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings 28th IEEE International Conference on Computer Communications (INFOCOM 2009, Rio de Janeiro, Brazil, April 19-25, 2009)
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's1701-1709
ISBN van geprinte versie978-1-4244-3512-8
DOI's
StatusGepubliceerd - 2009

Vingerafdruk Duik in de onderzoeksthema's van 'Instability of MaxWeight scheduling algorithms'. Samen vormen ze een unieke vingerafdruk.

Citeer dit