Hi, everyone.
I'm Radhika Mittal.
I'm doing my PhD in UC Berkeley, but I
am advised by Sylvia Ratnasamy and Scott Shenker.
And I'm going to talk about the recent work
on universal packet scheduling, which
appeared in NSDI this year.
Now, there are some of you in the audience
who have already suffered through this talk before.
So I would like to apologize to you,
and I would also say there is good news for you.
It's not exactly the same as last time.
I've added two lines on SDNs to make
it a better fit for the venue.
So you have something new to watch out for.
OK.
Should we spot the difference?
If you want.
OK.
So as we all know, scheduling algorithms
play a key role in any packet switch networks.
And so, over the years, our community
has developed many different scheduling algorithms,
such as first in, first out factoring,
virtual clock scheduling, et cetera, et cetera.
And there has been this implicit assumption
that we need this many different algorithms to meet
many different goals in many different contexts.
And all of these scheduling algorithms
are implemented in the router hardware.
So how do we support these different scheduling algorithms
that are needed for different requirements?
One option is to go and change all of the router hardware
when our requirements change.
And one can imagine how difficult that would be,
given the scale of the network.
A second option is to implement all of the scheduling
algorithms in the hardware, but this can be very expensive.
And what if someone comes up with a new algorithms
for a new requirement?
Then you would likely need to go and change
all of the router hardware.
A third option is to have programmable scheduling,
as advocated in a recent proposal [INAUDIBLE].
But this requires a form of programmable hardware
in every router that does not exist yet.
And what is driving all of this is the underlying assumption
that we need different scheduling algorithms
for different requirements, which
leads us to ask this question.
With our work, we instead ask a different question.
Do we really need different scheduling algorithms
or different requirements, or can we instead
have a universal packed scheduling algorithm--
or what we call a UPS?
Now, by a UPS we mean a single scheduling algorithm
that can imitate the network-wide output
or the final end-to-end output produced
by any other algorithm.
But the first question that might occur to you
is, how can a single algorithm imitate all others and that too
at a network-wide level?
So to understand that, let us look at a network model.
There we have some input traffic,
coming in at the network ingress, which traverses
the core of the network.
Further out is running some scheduling
algorithm, many of which may rely
on some header state that can be initialized at the ingress.
And the resulting output is then seen at the network egress.
Now, according to the conventional mindset,
to output traffic characteristics at the egress
are tied to the scheduling algorithm
that is running in the routers.
So for different desired output, we
would go and run different scheduling algorithms
in the router.
For example, if our goal is to minimize the mean flow
completion time, we would emulate something
like shortest job first by running priority scheduling
in the routers, with the header scanning priority values
detecting the flow size.
Similarly, if our goal is fairness,
we would go and do fair queueing in the routers.
And for this, we do not need any specific core initialization.
But if our goal is weighted fairness,
we would do weighted fair queueing in the routers,
with the headers now guiding the flow weights, and so on.
However, in our quest for universality,
we envision tying the output traffic characteristics solely
to the header initialization process,
with the core running a scheduling algorithm that
is completely agnostic of the desired output,
and it simply makes uniform scheduling decision
using the packet header state.
So you can think of this header initialization
as being analogous to passing different parameter
values to a fixed function to get different desired outputs.
So the question that we ask now is, is it
possible to have a UPS here?
And can it actually just rely on your header initialization
to get any desired output?
Now, I'd like to point out here that our model assumes
that the network edge is capable of greater processing
complexity than the core of the network.
And this is in line with the edge/core spread
proposed in prior SDN-based architectures.
And basically, where the core focuses
on just delivering the packet from one
point to another, whereas the edge
is responsible for the rest of the things.
And similarly, our model-- the core
is running a fixed algorithm, and is just sort of
taking care of delivering the packets,
whereas the edge is responsible for making sure
that the headers are initialized appropriately
to meet the desired objective.
OK, so with this understanding of our model,
let us dive into how we formally define and evaluate a UPS.
We define a UPS using two viewpoints.
The first one is a theoretical viewpoint
that I informally mentioned about earlier.
And here we call a scheduling algorithm universal
if it can replay any given schedule.
I'll soon formalize what I mean by replay and schedule here.
And this theoretical viewpoint provides us
with a very clean definition of universality.
It allows us to understand its fundamental limitations, which
algorithms are flexible enough to be universal, and so on.
But as we'll see later, while it is theoretically useful,
it cannot be applied in practice.
So a second definition of UPS is from a practical viewpoint,
where a UPS is simply defined as an algorithm that
can achieve different network-wide objectives.
Now, in this talk I focus more on the theoretical viewpoint.
So for this, again, consider a network model
where we have some topology with some input load coming in,
given to us in the form of the packet [INAUDIBLE] the ingress.
And we have some arbitrary set of scheduling algorithms
running in the core routers-- many of which
may rely on some header initialisation, which
is done at the ingress.
And the resulting output is then seen at the network egress.
And so this output is what we represent
as o(p) for a packet p.
And this set of output times is what we call a schedule.
And the set o(p) gives us the original schedule.
I would like to point out that we
allow a very broad view of scheduling algorithms
when creating this original schedule.
For example, we can have two different routers running
two different algorithms.
They may learn an arbitrary state,
or they may even consult an [INAUDIBLE].
The only requirement we have from the original schedule
is that the final output times must be viable,
in the sense that there must be some way
to schedule the incoming packets in the routers, such
that we get the resulting output times.
We then try to replay this original schedule,
given to us in the form of the output times o(p)
by using the same topology and the same input load.
And we also assume that every packet follows the same path
in the original schedule and in the replay.
But we [INAUDIBLE] UPS in the core,
and we initialize the header for every packet at the ingress,
using the output times on the original schedule.
And this gives us a new set of output times
at the egress that we denote as o prime (p) for the packet p.
We say that the replay is successful
if, for every packet p, o prime (p) is
less than or equal to o(p).
However, we add some dramatic constraints
on what the header initialization
process and the UPS can use.
The first constraint is that when
initializing the header for the packet p,
the ingress router can only use the output time and the part
information for that packet p.
And it should remain completely oblivious to the rest
of the packets in the network.
And the second constraint is that in making its scheduling
decision, the UPS can only use some--
so the packet had a state and some stacking information
pertaining to the network topology.
By enabling these constrains, the key source
of impracticality that remains in our model
is the knowledge of the output times o(p) at the ingress.
And we get rid of this impracticality
with a practical viewpoint that I'll be discussing later.
And we term this constraint model as blackbox
initialization.
So with this understanding of our model,
let us look at some of our basic results.
We can show that we can always have a UPS under the Omniscient
Initialization condition, where we allow the header
initialization process to use extensive knowledge about when
every packet was scheduled at every hop
in the original schedule.
But it's not a very surprising result.
Interestingly, we can also produce a counter example
that shows that we can never have a perfect replay
under the blackbox initialization condition I
had mentioned before.
But only the final output times at the egress
are used to initialize the packet headers.
With these extreme results, we then
try to explore how close we can get to a UPS
in the blackbox model.
Through a theoretical analysis, we
find that the difficulty of replay
is determined by the number of congestion points
that a packet sees in the network, where a congestion
point is defined as a router where a packet can wait.
We can show that while there exists a scheduling
algorithm that can replay all schedules
with up to two congestion points per packet,
we can prove that no scheduling algorithm can replay
all schedules that have three congestion
points per packet or more.
So this gives us an upper bound, in terms
of the number of congestion points
that a scheduling algorithm can handle.
So the next question is, can we achieve this upper bound?
And the answer is yes.
The classical Least Slack Time First algorithm can, indeed,
achieve this upper bound.
So what is LSTF?
In LSTF, initialize the header of every packet
with a slack value that indicates
the maximum possible queuing delay that the packet is
willing to tolerate in the network.
So for the purpose [INAUDIBLE], the slack value
would be initialized as the [INAUDIBLE] packets
in the original schedule.
Then as the name suggests, the router
schedules the packet with the least slack time
first, and additionally, updates the slack of every packet
that it is scheduling by subtracting
the duration of time for which the packet waits at the router.
We can prove that LSTF can replay all schedules for two
congestion points per packet.
And like any other algorithm, it can
fill the replay schedule that have three or more congestion
points per packet.
And it's not like any other algorithm
is capable of achieving this upper bound.
For example, simple priority scheduling
can only replay schedules with one congestion
point per packet, and can fail beyond that.
OK, so this theoretically is established
that LSTF is as close to universal
as any algorithm can get.
But they do not give us any concrete measurement
of this closeness to universality.
So for this, we do some empirical experiments,
by doing LSTF replay using ns-2 simulations.
And we study how close LSTF is to being universal
under realistic settings.
And we find that for most cases, less than 3% packets
missed their target output times in an LSTF replay.
And more importantly, for most cases
less than 0.1% packets missed their targets
by more than one transmission time.
So this shows that even though LSTF is not
perfectly universal in the most theoretical sense,
it is indeed very, very close to universality
under realistic conditions.
Now, as I mentioned before, our theoretical viewpoint
is not practical, as it requires the knowledge of the output
times from an original schedule, which
is not available in practice.
And also, we don't care about replaying schedules
in practice.
What we care about is achieving different objectives.
So with a practical viewpoint, we
look at how LSTF can be used in practice to achieve
different objectives.
And the key difference between the two viewpoints
lies in how we assign the slacks.
Rather than using some original output times,
we now look at the network-wide objective
that we want to achieve, and we come up with certain heuristics
to assign the slack, to achieve that objective.
We look at three popular objective functions
for this purpose-- minimizing tail packet delays,
minimizing mean flow completion time, and fairness.
And our results show that LSTF performs
comparable to the state of the art for each of them.
And we also show how LSTF can facilitate active queue
management from the edge of the network.
I do not have time to go into the details of these results
today, but you can find these details in our NSDI paper.
So to summarize, in this work we discuss universality
of packet scheduling using two viewpoints--
theoretical and practical.
Our theoretical results show the while there
is no UPS under the pragmatic blackbox initialisation model,
the classic Least Slack Time First algorithm
comes as close to being a universal
as any algorithm can get.
And empirically, LSTF is very close
to universality under realistic conditions.
We then show how LSTF can be used
in practice to achieve a variety of network-wide objectives.
Our work, therefore, implies that we might not
need many different or new scheduling
and queue-management algorithms.
And we can instead just use LSTF with varying slack
initializations.
But there are still some interesting open questions
left.
So we showed that LSTF can-- we showed that we can always
achieve universality in the [INAUDIBLE]
initialisation model, and that we can never
achieve universality under the blackbox initialisation model.
So what is the least amount of information that is
needed to achieve universality?
Second, can we come up with any tractable bounds
on the degree of lateness with LSTF
when there are three or more congestion points?
And finally, can we formally define
the scope of using LSTF in practice.
In other words, is there a class of objectives
that can be achieved with LSTF, and what kind, etc.
So I'd like to conclude.
I'd like to thank you all, and happy to take questions.
Our code is available online.
[APPLAUSE]
Hopefully this is a simple one.
You said that you were going to restrict yourself
to looking at scheduling disciplines that had access
to information about the packet's path, the desired
output time, and certain static information.
What about the current queue size at the router?
Is that considered static information,
or are you not allowed to look at the queue size
at the router, in making a scheduling decision?
So LSTF does not really look at that.
And our non-existence proof would not be affected by that.
But if someone comes up with an algorithm that says that,
oh, we look at the current queue size and--
You'd be OK with that?
Yeah.
I should be OK with that.
I mean, that's not a very hard thing to do,
for routers, I think.
So another question I have is-- so
unlike the question of finding paths,
where oblivious routing has been shown
to be competitive theoretically and even better in practice,
there are examples where oblivious scheduling does
much worse than scheduling that can look at every packet
and make arbitrary decisions about how
packets are prioritized separately
at every individual switch.
I guess it would be interesting to know if there's
a spectrum of things you might consider or not consider,
between obliviousness and full global knowledge.
Yeah, that is the first open question I had.
And if you actually have any pointers on that,
I'll be happy to take a look.
Yeah, it would be interesting to find that out.
You're right.
Yes, please?
So actually, maybe this is open-ended.
So one question I have is, so why LSTF?
So why did you pick LSTF?
So what's the insight behind why LSTF works?
Is it just a question of putting arbitrary labels
on these packets, or is it something
about the slack semantics?
Yeah.
So one thing about LSTF that we realized along
the ways was-- it's this ability to remember
the history in some sense.
Like with LSTF, basically, if I have
spent some amount of queuing at one router,
I subtract that from the total amount I'm allowed to do that.
And then when I move-- when I pass that information along
to the second router, that helps.
So that is a key difference between simple priority
scheduling and LSTF.
So initially, I was trying to explore if priority scheduling
can get us far enough.
And then I realized that, no.
We need to have some notion of that history.
So there is this another-- earliest deadline first-based
approach that we can do, instead of
LSTF-- like I have [INAUDIBLE] equivalent to using LSTF.
But that uses some additional state in the routers.
But, yeah, I can discuss more about that offline
if you'd like, too.
Yeah.
Yes?
So you-- the one measure that you look at
is the number of congestion points.
Right.
But it's possible that there might
be some other metrics that might better
decide under what conditions you can have universality
and you can not?
Yeah, so this seemed like a very natural metric for us,
when we were comparing different schemes.
But yes, I'd be open to knowing more metrics
that we can look at.
And if you have any ideas, yeah.
I would be happy to chat around those lines.
Yeah.
[APPLAUSE]