Task Assignment With Unknown Duration
Abstract
We consider a distributed server system and ask which policy should be used for assigning tasks to hosts. In our server, tasks are not preemptible. Also, the task's service demand is not known a priori. We are particularly concerned with the case where the workload is heavy tailed, as is characteristic of many empirically measured computer workloads. We analyze several natural task assignment policies and propose a new one TAGS (Task Assignment based on Guessing Size). The TAGS algorithm is counterintuitive in many respects, including load unbalancing, non-work-conserving, and fairness. We find that under heavy tailed workloads, TAGS can outperform all task assignment policies known to us by several orders of magnitude with respect to mean response time and mean slowdown, provided the system load is not too high. We also introduce a new practical performance metric for distributed servers called server expansion. Under the server expansion metric, TAGS significantly outperforms all other task assignment policies, regardless of system load.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1999
- Accession Number
- ADA368426
Entities
People
- Mor Harchol-balter
Organizations
- Carnegie Mellon University