Recent Talks
Some lessons scheduling and queueing can teach us about system design
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.
Revisiting the performance of large jobs
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 for today's systems: Bridging theory and practice
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.
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.
Levels of information: How much do policies need to know about job sizes?
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.
A class of policies that prioritize small jobs
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.
Fairness in queues
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.
Open versus closed: A cautionary tale
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.
A unified framework for modeling TCP Vegas, TCP SACK, and TCP Reno
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.
Dimensionality reduction: 4 example applications
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.