Task assignment with work-conserving migration

In this paper we a present a task assignment policy suited to environments (such as high-volume web serving clusters) where local centralised dispatchers are utilised to distribute tasks amongst back-end hosts offering mirrored services, with negligible cost work-conserving migration available between hosts. The TAPTF-WC (Task Assignment based on Prioritising Traffic Flows with Work-Conserving Migration) policy was specifically created to exploit such environments. As such, TAPTF-WC exhibits consistently good performance over a wide range of task distribution scenarios due to its flexible nature, spreading the work over multiple hosts when prudent, and separating short task flows from large task flows via the use of dual queues. Tasks are migrated in a work-conserving manner, reducing the penalty associated with task migration found in many existing policies such as TAGS and TAPTF which restart tasks upon migration. We find that the TAPTF-WC policy is well suited for load distribution under a wide range of different workloads in environments where task sizes are not known a priori and negligible cost work-conserving migration is available. (c) 2006 Elsevier B.V. All rights reserved.