OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Scheduling in a random environment: stability and asymptotic optimality

Ayesta, Urtzi and Erausquin, Martin and Jonckheere, Matthieu and Verloop, Maaike Scheduling in a random environment: stability and asymptotic optimality. (2013) IEEE/ACM Transactions on Networking, vol. 21 (n° 1). pp. 258-271. ISSN 1063-6692

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1109/TNET.2012.2199764


We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted, and users arrive and depart upon service completion. This may model, for example, the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria, we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem, we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: 1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time-slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based, Proportionally Best, or Potential Improvement are stable under the maximum stability conditions, whereas the opportunistic scheduler Relative-Best or the cμ-rule are not. 2) We show that choosing the right tie-breaking rule is crucial for the performance (e.g., average delay) as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. We will refer to such tie-breaking rule as myopic. 3) We derive the growth rates of the number of users in the system in overload settings under various policies, which give additional insights on the performance. 4) We conclude that simple priority-index policies with the myopic tie-breaking rule are stable and asymptotically optimal. All our findings are validated with extensive numerical experiments.

Item Type:Article
Additional Information:Thanks to IEEE editor. The definitive version is available at http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6209453
HAL Id:hal-01121985
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > IKERBASQUE (SPAIN)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
Université de Toulouse > Université Paul Sabatier-Toulouse III - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université de Toulouse I-Sciences Sociales - UT1 (FRANCE)
Other partners > Universidad del País Vasco - Euskal Herriko Unibertsitatea - EHU (SPAIN)
Other partners > Consejo Nacional de Investigaciones Científicas y Técnicas - CONICET (ARGENTINA)
Laboratory name:
Deposited By: IRIT IRIT
Deposited On:03 Mar 2015 07:54

Repository Staff Only: item control page