Spatial inefficiency of MaxWeight scheduling

P.M. Ven, van de, S.C. Borst, L. Ying

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)
77 Downloads (Pure)


MaxWeight scheduling has gained enormous popularity as a powerful paradigm for achieving queue stability and 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 flows with stationary ergodic traffic processes. In the present paper we examine networks where the population of active flows varies over time, as flows eventually end while new flows occasionally start. We show that MaxWeight policies may fail to provide maximum stability due to persistent inefficient spatial reuse. The intuitive explanation is that these policies tend to serve flows with large backlogs, even when the resulting spatial reuse is not particularly efficient, and fail to exploit maximum spatial reuse patterns involving flows with smaller backlogs. These results indicate that instability of MaxWeight scheduling can occur due to spatial inefficiency in networks with fixed transmission rates, which is fundamentally different from the inability to fully exploit time-varying rates shown in prior work. We discuss how the potential instability effects can be countered by spatial traffic aggregation, and describe some of the associated challenges and performance trade-offs.
Originele taal-2Engels
TitelProceedings 9th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'11, Princeton NJ, USA, France, May 9-13, 2011)
UitgeverijInstitute of Electrical and Electronics Engineers
ISBN van geprinte versie978-1-61284-822-8
StatusGepubliceerd - 2011

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

Citeer dit