More info

This talk provides a overview of some basic and some not-so-basic results from scheduling and queueing and shows how they can be useful for system designers. The talk is meant to be light, interactive, and fun, but to still provide a feeling for the type of research questions I like to approach.

In recent years, the response times experienced by large job sizes have been the focus of a growing number of papers. Though results about many scheduling disciplines have appeared, to this point, results characterizing the response time of large job sizes have been limited to either mean value analysis or law of large numbers scalings. We will present a novel framework that unifies these results and provides new results characterizing the distributional behavior of large job sizes. Also, we will illustrate the impact these new results have (i) for the analysis of the response time tail, (ii) for the analysis of busy periods, and (iii) for predicting response times of customers upon arrival.

Scheduling is a fundamental technique for improving performance in computer systems. From web servers to routers to operating systems, how the bottleneck device is scheduled has an enormous impact on the performance of the system as a whole. Given the immense literature studying scheduling, it is easy to think that we already understand enough about scheduling. But, modern computer system designs have highlighted a number of disconnects between traditional analytic results and the needs of system designers. In particular, the idealized policies, metrics, and models used by analytic researchers do not match the policies, metrics, and scenarios that appear in real systems.

The goal of this thesis is to take a step towards modernizing the theory of scheduling in order to provide results that apply to tod s computer systems, and thus ease the burden on system designers. To accomplish this goal, we provide new results that help to bridge each of the disconnects mentioned above. We will move beyond the study of idealized policies by introducing a new analytic framework where the focus is on scheduling heuristics and techniques rather than individual policies. By moving beyond the study of individual policies, our results apply to the complex hybrid policies that are often used in practice. For example, our results enable designers to understand how the policies that favor small job sizes are affected by the fact that real systems only have estimates of job sizes. In addition, we move beyond the study of mean response time and provide results characterizing the distribution of response time and the fairness of scheduling policies. These results allow us to understand how scheduling affects QoS guarantees and whether favoring small job sizes results in large job sizes being treated unfairly. Finally, we move beyond the simplified models traditionally used in scheduling research and provide results characterizing the effectiveness of scheduling in multiserver systems and when users are interactive. These results allow us to answer questions about the how to design multiserver systems and how to choose a workload generator when evaluating new scheduling designs.

Shortest Remaining Processing Time (SRPT) scheduling has long been known to optimize mean response time. Motivated by the optimality of SRPT, in recent years many computer systems have used the heuristic of ``prioritizing small jobs'' in order to dramatically reduce user response times. However, rarely do computer systems have knowledge of exact remaining sizes. More frequently, computer systems must use estimates of job sizes when scheduling jobs, or even no job size information at all. In this talk, we will study the impact of the level of job size information on the achievable mean response times. In order to perform this comparison, we develop a new framework, motivated by the notion of "competitive analysis" used to study approximation algorithms in computer science, which highlights the effect of inexact job size information.

In this talk, we will introduce the class of SMART scheduling policies: policies that prioritize towards jobs with small original sizes, small remaining sizes, or both. The SMART class includes common policies, such as Shortest Remaining Processing Time and Preemptive Shortest Job First, in addition to a wide variety of hybrid policies. We will present recent results about the mean response time, the conditional response time, and the tail behavior of response time under policies in the SMART class.

The growing trend in computer systems towards using scheduling policies that prioritize jobs with small service requirements has resulted in a new focus on the fairness of such policies. In particular, researchers have been interested in whether biasing towards small job sizes results in large jobs being treated "unfairly." However, unfairness is an amorphous concept and thus difficult to define and study. In this talk, I will present some recent attempts to define and study the concept of fairness in single server queueing settings. Rather than providing the unique, correct definition of fairness for queues, my goal in this talk is to illustrate, compare, and contrast, the range of fairness measures that have been suggested and to summarize what interesting open questions remain for each.

Workload generators may be classified as based on a closed system model, where new job arrivals are only triggered by job completions (followed by think time), or an open system model, where new jobs arrive independently of job completions. In general, system designers pay little attention to whether a workload generator is closed or open.  In this talk, I will illustrate (using a combination of implementation and simulation experiments) that there is a vast difference in behavior between these open and closed models in real-world settings. Further,  I will synthesize  the differences in behavior between the models into a few  simple principles.

We present a general analytical framework for the modeling and analysis of TCP variations. The framework allows the modeling of multiple variations of TCP, including TCP-Vegas, TCP-SACK, and TCP-Reno, under general network situations. In particular, the framework allows us to propose the first analytical model of TCP-Vegas for arbitrary on-off traffic that is able to predict the operating point of the network. The analysis provided by our framework leads to many interesting observations with respect to both the behavior of bottleneck links that are shared by TCP sources and the effectiveness of the design decisions in TCP-SACK and TCP-Vegas.

We present an approach for solving 2 dimensionally infinite  Markov chains, which we refer to as dimensionality reduction.  The technique transforms a chain from a 2D-infinite chain into a 1D-infinite chain which can be analyzed. To do this, we introduce a new type of transition, which represents a busy period duration.  This transition is a phase type distribution which matches the first three moments of the busy period duration.   To illustrate the applicability of this technique, in this sequence of talks we apply the dimensionality reduction technique to solve several  variants of the cycle stealing problem as well as several variants of  multiserver priority systems.