Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A modeling framework for optimizing the flow-level scheduling with time-varying channels
AU - Ayesta, Urtzi
AU - Erausquin, Martin
AU - Jacko, Peter
PY - 2010/11/1
Y1 - 2010/11/1
N2 - 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μcμ-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μcμ-rule. Our results show that RB, PB, SB or the cμcμ-rule might outperform the others depending on the scenario, but regardless of this, the performance of PI is always superior or equivalent to the best of these opportunistic rules.
AB - 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μcμ-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μcμ-rule. Our results show that RB, PB, SB or the cμcμ-rule might outperform the others depending on the scenario, but regardless of this, the performance of PI is always superior or equivalent to the best of these opportunistic rules.
U2 - 10.1016/j.peva.2010.08.015
DO - 10.1016/j.peva.2010.08.015
M3 - Journal article
VL - 67
SP - 1014
EP - 1029
JO - Performance Evaluation
JF - Performance Evaluation
SN - 0166-5316
IS - 11
ER -