|
Recent Talks
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.
[slides]
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.
[slides (short)]
[slides (long)]
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 theoretical
scheduling toolbox
Scheduling policies are fundamental components of a majority
of modern computer systems. However, despite a vast field of
research analyzing the performance of different scheduling
policies, the task of choosing a scheduling policy for a
particular application is still difficult. This difficulty is
a result of a disconnect between queueing researchers and
system designers. Typically, queueing research studies only
individual scheduling policies and individual metrics; whereas
practical issues force system designers to use complex hybrid
policies that perform well across a variety of metrics.
To bridge this divide, we propose a new style of scheduling
research where large groups of policies are classified with
respect to a wide range of metrics. In particular, we
propose to develop a theoretical scheduling toolbox consisting
of a range of classifications, each of which isolates a
different metric. The classifications we propose can be
divided into three types: classifications of efficiency
metrics, fairness metrics, and robustness metrics. Classical
queueing theory has focused entirely on measures of
efficiency; thus, in developing the toolbox, we will need to
develop novel metrics to measure the fairness and robustness
of scheduling policies. In addition, because classical
queueing research focuses on individual policies, we will need
to develop novel analytic techniques in order to analyze the
performance of large groups of policies.
[slides]
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.
[slides] 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.
[slides1] [slides2]
[slides3] [slides4]
|