Queueing Analysis of Computer Systems

Abstract

Heterogeneity and Performance Interference are two characteristics of modern large scale computer systems. The policies developed for simple homogeneous computer systems do not scale well when accounting for Heterogeneity and Performance Interference. In this thesis, we develop novel “power-of-d” policies that better address such systems. In the first part of this thesis, we approach the challenges of load balancing in large scale heterogeneous server systems. We sequentially develop effective load balancing models and introduce a framework to help characterize the different load balancing policies based on their querying and assignment rules. We compare the performance of these novel optimizable policies with the conventional policies present in literature for different parameter settings. Our policy framework allows us to develop complex load balancing policies --- i.e., allowing for probabilistic querying and/or job assignment not following simple rules such as Join-the-Idle-Queue, Join-the-Shortest-Queue, Join-the-Shortest-Expected-Wait-Queue and Join-the-Shortest-Expected-Delay-Queue--- which is a novel addition to the literature. Furthermore, our work makes it possible to do a comprehensive numerical study of policies that consider each queried server's queue length and speed information for job assignment. Prior to our work, conducting such a study required simulations which was computationally infeasible. Our performance comparisons for different mixes of querying and assignment rules allows us to identify the trade-off between policy simplicity and performance. In the last chapter of this thesis, we address a new area of interest which is load balancing models for systems where servers undergo performance interference. We first develop simple novel “power-of-d” policies for such systems that consider queried server's idleness and/or interference state information for job assignment. Using analytical proofs and numerical experiments we analyze the performance of these policies and identify system parameter regions that favors different heuristics. The analysis further motivates us to develop a more general and complex optimizable policy that has better performance under all parameter settings.