Scheduling for Server Farms: Approaches and Open Problems

Server farms are ubiquitous in applications ranging from Web server farms to high-performance supercomputing systems to call centers. The popularity of the server farm architecture is understandable, as it allows for increased performance, while being cost-effective and easily scalable. Given the prevalence of server farms, it is surprising that even at this late date so little is understood regarding their performance as compared with their single-server counterpart. In this talk, we review existing results and present new results on the stochastic analysis of server farms. We will be particularly interested in the routing/dispatching policies used for assigning jobs to servers, and in the scheduling policies employed at the servers. We will assume that job service requirements are highly-variable, as is common in computing workloads today.

We consider three different server farm models. The first model, representative of supercomputing and manufacturing applications, involves non-preemptive, First-Come-First-Serve (FCFS) scheduling at the individual servers. We will see that the mean response time of such FCFS server farms can vary by orders of magnitude depending on the routing policy used, and that routing policies that reduce workload variability are most effective. The second model, representative of Web server farms, employs Processor-Sharing (PS) service order at the servers. We show that the best routing policied for PS server farms are very different from those for FCFS server farms. In particular, the Join-the-Shortest-Queue routing policy will prove to be very useful in the PS server farm setting. Finally, we turn to the question of what server farm architectures are optimal for minimizing mean response time. Here we consider a third model for server farms, where the individual servers employ Shortest-Remaining-Processing-Time (SRPT) scheduling. Such models are very difficult to analyze stochastically, but we discuss some beautiful competitive ratio analyses, that shed light on future research directions for stochastic modeling.