Stochastic processes are a very powerful tool for analyzing the performance of computer systems. However there are still some very fundamental computer systems problems which remain largely intractable. One example is the simple cycle stealing problem, where one server can steal another server's idle cycles under a switching cost overhead. Cycle stealing pervades applications ranging from Webserver farms, to networks of workstations, to disk arrays, to databaseserver clusters, and yet very simple questions like quantifying the benefit of cycle stealing, or understanding under what conditions cycle stealing is profitable are not yet understood. Another example is the long standing open problem of finding and analyzing the optimal policy for task assignment in a server farm. Interestingly, these problems and other open fundamental computer systems problems are difficult for the same reason: they all have a Markov chain representation which grows infinitely in two or more dimensions (2D). While a one-dimensional (1D) infinite Markov chain with repeating structure can be solved via computational approaches, these 2D infinite chains can not.
This project proposes a new approach for attacking problems such as those above, resulting in a 2D infinite Markov chain. The idea is to transform the 2D infinite chain into a 1D infinite chain which can be analyzed, without removing the relevant problem information. This is achieved by using Markov chain transitions to denote the durations of various types of busy periods. The project will entail a mathematical exploration of the general applicability of this technique, the application of the technique to specific problems, and the implementation of the analytical solutions within real systems.
Broader impacts resulting from the proposed activity include: a workshop on scheduling in server farms; online availability of all source code generated from the work along with documentation; a highly-accessible set of lecture notes on queueing theory applications which evolves yearly to reflect the current research aims of the author; collaborations with the Pittsburgh Supercomputer Center to implement ideas in this proposal; and undergraduate research opportunities in scheduling. The project involves 1 faculty member (1summer month only) and 0.5 graduate students over the course of 3years.
