A modeling framework for optimizing the flow-level scheduling with time-varying channels

作者：Ayesta Urtzi; Erausqum Martin; Jacko Peter^*

来源：Performance Evaluation, 2010, 67(11): 1014-1029.

DOI：10.1016/j.peva.2010.08.015

• Multi-armed restless bandit problem
• Markov Decision Process
• Stochastic dynamic programming
• Opportunistic scheduling
• Optimal scheduling
• c mu-rule
• Index policy

We introduce a comprehensive modeling framework for the problem of scheduling a finite number of finite-length jobs where the available service rate is time-varying The main motivation comes from wireless data networks where the service rate of each user varies randomly due to fading We employ recent advances on the restless bandit problem that allow us to obtain an opportunistic scheduling rule for the system without arrivals When the objective is to minimize the mean number of users in the system or to minimize the mean waiting time, we obtain a priority-based policy which we call the Potential Improvement (PI) rule, since the priority index equals the ratio between the current available service rate and the expected potential improvement of the service rate We also show that for certain objective functions the index rule takes the form of known opportunistic scheduling rules like Relatively Best (RB) or Proportionally Best" (PB) Thus our model provides a formal justification for the deployment of opportunistic scheduling rules in order to improve the flow-level performance in the presence of time-varying capacities We further analyze the performance of the PI rule in the presence of randomly arriving users When the service rates are constant PI is equivalent to the c mu-rule which is known to be optimal with any distribution of arrivals Using a recent characterization for the stability region of flow-level scheduling rules under random arrivals we show that PI achieves the maximum stability region We perform numerical experiments in a wide range of scenarios and compare the performance of PI with other popular disciplines like RB PB Score-Based (SB) and the c mu-rule Our results show that RB PB SB or the c mu-rule might outperfor

• 出版日期2010-11