Varun Gupta

Stochastic Models and Analysis for Resource Management in Server Farms Degree Type: Ph.D. in Computer Science
Advisor(s): Mor Harchol-Balter
Graduated: May 2011

Abstract:

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-and-error 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.

Thesis Committee:
Mor Harchol-Balter (Chair)
David G. Andersen
Anupam Gupta
Alan Scheller-Wolf
Devavrat Shah (MIT)
Don Towsley (UMass. Amherst)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

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

CMU-CS-11-114.pdf (2.2 MB) ( 159 pages)
Copyright Notice