Task Assignment in Server Farms under Realistic Workload Conditions
Venue: 10.08.03 (Building 10, Floor 8, Room 3)
Abstract:
Server farms have become very popular in recent years since they effectively address the problem of large delays, a common problem faced by many organisations whose systems receive high volumes of traffic. Recently, there has been a wide use of these server farms in two main areas, namely, Web hosting and scientific computing. The performance of such server farms is highly reliant on the underlying task assignment policy, a specific set of rules that defines how the incoming tasks are assigned to and processed at hosts. The aim of a task assignment policy is to optimise certain performance criteria such as the expected waiting time and slowdown. One of the key factors that affect the performance of these policies is the service time distribution of tasks. There is extensive evidence indicating that the service times (processing times) of modern computer workloads closely follow heavy-tailed distributions that possess high variance. However, in certain environments, the service time distributions of tasks are unknown. Imposing parametric assumptions (e.g. heavy-tailed, exponential, etc.) in such cases can lead to inaccurate and unreliable inferences. Considerable efforts have been made in recent years to devise more efficient policies. These policies use special techniques (such as unbalancing the load among hosts and reducing the task size variability in hosts queues, etc.) to improve the performance. Although these policies perform well in certain environments under specific workload conditions, they have several major limitations. These include the assumption of known service times, inability to efficiently assign tasks in time sharing server farms, poor performance under changing workload conditions and poor performance under multiple server farms.
We aim at proposing novel task assignment policies for assigning tasks in server farms under two main classes of realistic workload conditions, namely, the heavy-tailed and arbitrary service time distributions. Arbitrary service time distributions are assumed, for cases where the underlying service time distribution of tasks is unknown. First we investigate ways to optimise the performance in a time-sharing server. We concentrate on a particular scheduling policy called multi-level time sharing policy (MLTP). We derive a performance model for MLTP under finite levels and positive quanta and then provide a comprehensive performance analysis of MLTP under a range of scenarios. This analysis shows that MTLP with optimal quanta can result in significant performance improvements over other policies under a range of workload conditions (e.g. high system loads and task size variabilities). Second we investigate how to improve the performance in time sharing server farms. Three task assignment policies (MLMS, MLMS-M and MLMS-PM) are proposed for time sharing server farms. The core features of these policies include the global and local reduction of task size variance, provision of preferential treatment to small tasks and task migration between hosts. These policies outperform existing policies under a range of conditions. For example, MLMS-M with five levels outperforms TAGS by a factor of 6.75 under high system loads and high task size variabilities. Third we investigate how to design efficient task assignment policies to assign tasks in multiple server farms (i.e. a set of server farms). We propose MCTPM policy for a multiple server farm, which is based on a flexible multi-tier host architecture. MCTPM supports preemptive task migration and it controls the traffic flow into server farms via a global dispatching device so as to optimise the performance. Performance analysis of MCTPM shows that it outperforms MC-TAGSPM by a factor of 5 under moderate system loads and low task size variabilities. Finally, we investigate ways to design adaptive task assignment policies that make no assumptions regarding the underlying service time distribution of tasks. We propose a novel task assignment policy, called ADAPT-POLICY, which is based on a set of static-based task assignment policies. ADAPT-POLICY defines a set of policies for the server farm and it adaptively changes the task assignment policy to suit with the most recent traffic conditions. The experimental performance analysis of ADAPT-POLICY shows that ADAPT-POLICY outperforms other policies under a range of evolving traffic conditions.
Please see Malith's home page at here.
Seminar Organisation
Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Sebastian Sardina, the seminar co-ordinator.