Computer Science Department
School of Computer Science, Carnegie Mellon University


Stochastic Models and Analysis for
Resource Management in Server Farms

Varun Gupta

May 2011

Ph.D. Thesis


Keywords: Queueing theory, Multi-server systems, Load balancing, Scheduling, M/G/k, Time-varying load, Energy management, Stochastic modeling, Heavy-traffic analysis

Server farms are popular architectures for computing infrastructures such as supercomputing centers, data centers and web server farms. As server farms become larger and their workloads more complex, designing efficient policies for managing the resources in server farms via trial-anderror becomes intractable. In this thesis, we employ stochastic modeling and analysis techniques to understand the performance of such complex systems and to guide design of policies to optimize the performance.

There is a rich literature on applying stochastic modeling to diverse application areas such as telecommunication networks, inventory management, production systems, and call centers, but there are numerous disconnects between the workloads and architectures of these traditional applications of stochastic modeling and how compute server farms operate, necessitating new analytical tools. To cite a few:
(i) Unlike call durations, supercomputing jobs and file sizes have high variance in service requirements and this critically affects the optimality and performance of scheduling policies.
(ii) Most existing analysis of server farms focuses on the First-Come- First-Served (FCFS) scheduling discipline, while time sharing servers (e.g., web and database servers) are better modeled by the Processor- Sharing (PS) scheduling discipline.
(iii) Time sharing systems typically exhibit thrashing (resource contention) which limits the achievable concurrency level, but traditional models of time sharing systems ignore this fundamental phenomenon.
(iv) Recently, minimizing energy consumption has become an important metric in managing server farms. State-of-the-art servers come with multiple knobs to control energy consumption, but traditional queueing models donāt take the metric of energy consumption into account.

In this thesis we attempt to bridge some of these disconnects by bringing the stochastic modeling and analysis literature closer to the realities of today's compute server farms. We introduce new queueing models for computing server farms, develop new stochastic analysis techniques to evaluate and understand these queueing models, and use the analysis to propose resource management algorithms to optimize their performance. iv

159 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by