TY - GEN
T1 - To migrate or to wait
T2 - IEEE Conference on Computer Communications, INFOCOM 2012
AU - He, Ting
AU - Chen, Shiyao
AU - Kim, Hyoil
AU - Tong, Lang
AU - Lee, Kang Won
PY - 2012
Y1 - 2012
N2 - We consider the problem of scheduling low-priority tasks onto resources already assigned to high-priority tasks. Due to burstiness of the high-priority workloads, the resources can be temporarily underutilized and made available to the low-priority tasks. The increased level of utilization comes at a cost to the low-priority tasks due to intermittent resource availability. Focusing on two major costs, bandwidth cost associated with migrating tasks and latency cost associated with suspending tasks, we aim at developing online scheduling policies achieving the optimal bandwidth-latency tradeoff for parallel low-priority tasks with synchronization requirements. Under Markovian resource availability models, we formulate the problem as a Markov Decision Process (MDP) whose solution gives the optimal scheduling policy. Furthermore, we discover structures of the problem in the special case of homogeneous availability patterns that enable a simple threshold-based policy that is provably optimal. We validate the efficacy of the proposed policies by trace-driven simulations.
AB - We consider the problem of scheduling low-priority tasks onto resources already assigned to high-priority tasks. Due to burstiness of the high-priority workloads, the resources can be temporarily underutilized and made available to the low-priority tasks. The increased level of utilization comes at a cost to the low-priority tasks due to intermittent resource availability. Focusing on two major costs, bandwidth cost associated with migrating tasks and latency cost associated with suspending tasks, we aim at developing online scheduling policies achieving the optimal bandwidth-latency tradeoff for parallel low-priority tasks with synchronization requirements. Under Markovian resource availability models, we formulate the problem as a Markov Decision Process (MDP) whose solution gives the optimal scheduling policy. Furthermore, we discover structures of the problem in the special case of homogeneous availability patterns that enable a simple threshold-based policy that is provably optimal. We validate the efficacy of the proposed policies by trace-driven simulations.
UR - http://www.scopus.com/inward/record.url?scp=84861621114&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861621114&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2012.6195718
DO - 10.1109/INFCOM.2012.6195718
M3 - Conference contribution
AN - SCOPUS:84861621114
SN - 9781467307758
T3 - Proceedings - IEEE INFOCOM
SP - 2871
EP - 2875
BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Y2 - 25 March 2012 through 30 March 2012
ER -