Hi, I'm Lavanya.
I'm a 4th-year PhD student at Stanford in Professor Nick
McKeown's group, and I'm going to talk
about why high speed networks need proactive congestion
control and how we can use-- how we can realize this using
programmable forwarding planes.
This is work done in collaboration
with people at Stanford, MIT, and Microsoft Research.
So in this talk I'm going to first describe
why at a 100 gigabit per second speeds
we need much faster congestion control
schemes than what we use today.
Then I'll try to convince you that letting
the network switches directly compute the rates in the data
plane is a fast and scalable scheme.
And then I'll describe how we can realize such a scheme 100G
networks using programmable forwarding planes.
So first, let me describe the congestion control problem
to you.
So here, I have a network with a set
of links with different capacities,
and I have flows that use different subsets
of these links.
And the congestion control problem
is defining rates for these flows
that are efficient, fair, and feasible so they
avoid congestion.
And so how do we solve this problem?
Well, we can ask an oracle.
We can give her the list of links, the list of flows
and the links they use, and the link capacities, and then
she magically gives us the flow rates.
Well, it's not quite magic, because given the link
capacities and the traffic matrix,
anyone can compute the flow rates.
On the other hand, here's what we do today.
In today's congestion control schemes
neither the end host nor the links
have any explicit information about the traffic matrix.
In fact, they are more like the control systems you
heard in this morning's talks.
They measure congestion signals, then
they react by adjusting the rates after some measurement
delay.
This is a gradual process.
They can't jump directly to the right rates,
but they know the direction in which to adjust.
So that's why I'll call them reactive algorithms.
And I'm going to show you an example of a specific reactive
algorithm called RCP, which was designed specifically
to converge very quickly to maximum fair rates, which
is the notion of fairness I'm looking at.
So this is the same network you saw before
and I'm going to show you how RCP tries to figure out
the rates for these flows.
On this graph on the y-axis, I have the transmission rate
in gigabits per second, and on the x-axis,
I have the time measured in RTTs, round trip times.
So first, let me plot the ideal rate for flow C, which
is the flow on your right, the red flow,
and it shares a link with another flow.
So the fair share rate for that would be half the link capacity
or 5 gigabits per second.
And-- Sorry, you can already see what RCP does,
but-- so here is what our RCP does.
You can see that initially it overshoots a bit, probably
because it di--
I should give you some context for how RCP works.
So in RCP, the switches basically
measure the input traffic rate and the queuing,
and then adjust the rate that they advertise to the end host,
and the end host will pick the minimum rate
that they hear from the switches to send it.
So here you can see the rate advertised by the switch,
by the link to the end host, and you can see that initially,
it kind of overshoots, because maybe it didn't
detect a lot of input traffic.
And then it undershoots, and gradually it
gets to the correct rate.
And let me plot the rates for the other flows.
You can see that they're similar.
They're basically all over the place,
and it takes 30 round trip times for these rates
to finally converge.
And this behavior is very typical
of all traditional congestion control schemes, but yet TCP,
XCP, or DCTCP.
While it's cool that they don't need any explicit information
to figure out these rates, if you step back,
you start to wonder why do they take 30 round trip times
to figure out just a few rates.
Why can't they be like the oracle, like maybe 1 RTT?
And as link speeds get faster, this problem
will only get worse.
Today's typical link speeds are 10 or 40 gigabits per second.
But if you move to 100 gigabits per second,
a typical flow in a search workload will only last 7 RTTs,
and in that case, we can't wait 30 round trip
times for the schemes to figure out the rates.
So yeah, at 100G speeds, this problem of convergence times
is even more important.
And a typical flow will finish in less than 7 round trip
times.
So here I have the flow size distribution for a search
workload, and if I get a typical flow from this,
like a 1 megabyte flow, at 100 gigabits per second,
it would finish in just 80 microseconds, which
is 7 to 8 round trip times in today's data centers.
So reactive schemes are slow for 100 gigabits per second.
And what we realize is perhaps these reactive
algorithms are trading off knowledge
of explicit flow information for long convergence times.
In this talk, I want to explore how
we can use this explicit flow information
and get shorter convergence times.
So where do we start?
Let's go back to the oracle and see how she used the traffic
matrix to compute rates.
A standard technique for computing maximum fair rates
is called the waterfilling algorithm.
Let me quickly walk you through it.
So here I have that network, and the gray boxes are the links.
The colored ones are the rates that the flows that getting,
and the height of the box is proportional to the link
capacity or the rates the flows are getting.
And basically in this scheme, I start
with 0 allocation for all the flows,
and then increase them at the same rate
until some link gets fully used up, like link 3 here.
And then the flows that go to the link, the red
and blue flows are bottlenecked at that link,
and I continue increasing the allocation for the other flows
until every link gets fully used.
And then I can simply read out the fair share
rates of the flows.
So we could try to implement-- so this is an explicit rate
calculation, and this could be much faster
than the reactive schemes.
If we try to implement this in a centralized controller,
though, the controller would have
to be involved in every flow event.
Every time a flow starts or ends,
it has to do this calculation again.
And moreover, it has to communicate these new rates
to all the affected flows.
So we think that a centralized water-filling scheme may not
scale.
And so in this talk I'm going to think
about how we can let the network figure out the rates
in a distributed fashion using programmable forwarding planes
or stateful data planes, as you'll see.
So luckily for me, there was quite a bit of research
done about finding maximum fair rates in a distributed way.
But in the context of ATM networks
in the late '90s and early 2000s.
And I wanted to describe a typical scheme from that era
just so you can see how these distributed schemes work.
So here I have 1 link and 2 flows using the link.
And the link is keeping track of what each flow has requested.
So basically, the flows will request a demand of infinity
because they'll send as much as the link will let them.
The links will look at the capacity available,
the number of flows, and then calculate the fair share
as just half the link capacity here, and then tell the flows.
And if we add a second link-- so here I've added link 2,
and I have flow B go through it.
You'll see it gets a little more complicated.
So here, clearly, flow B can't advertise
to link 1 that it can send at infinity, because it's
restricted to 10 gigabits per second at link 2.
So it gives a different demand, and when link 1 calculates
the rate, it looks at the capacity, the demand
of the flows that are bottlenecked elsewhere,
and the number of unrestricted flows
that are not bottlenecked elsewhere,
and then calculates the fair share rate.
So that's generally how the schemes look,
and when practically implement it--
so this is the first version of the scheme, practical scheme
that I implemented, called proactive explicit rate
control or PERC, basically the flows and links exchange
demands and fair shares using control packets.
So here you can see the control packet for flow B,
and it carries the demands for flow B at both the links
and placeholders for the links to fill in the fair shares.
And basically links on the way will look at the demand,
fill in the fair shares, and each flow
will be sending these control packets as long as it's active,
independently of the other flows in an asynchronous way.
So when we try to implement these schemes in today's
upcoming future, like programmable forwarding planes,
there are a lot of new constraints
that we have to look at.
Since these-- so input-- I was in particular
looking at the abstract switch model described
by the P4 paper, which is a pipeline of match action
tables with configurable match and action in every stage.
So there are quite a few constraints in switches.
For example, at 100 gigabits per second,
we really have a few nanoseconds to process,
to do the state update, do the updates and the switches.
We can only do a limited amount of computation.
For example, not only did the actions have
to complete in a few nanoseconds,
they have to be made up of the primitive actions that
are supported by the switch.
It might be something very simple,
like addition and compare, probably not division.
And there is only a limited amount of information
that we can modify for each packet update.
And then we have a limited amount of area
that we can use for the state and look-up tables
that our scheme will use.
And depending on the design of the switch,
the actual limits might be just enough for your use case
or it may not be enough.
But these are different things that you
have to keep in mind when designing
for programmable forwarding planes.
And so as a first step to realize this,
we wrote up a version of PERC using P4,
and then compiled it to a NetFPGA
using tools from Xilinx.
And note that this P4 program used
the most basic version of P4.
And so it reflects a very simple, programmable forwarding
plane.
I had to modify the original scheme
considerably to make it simple enough for P4.
For example, I didn't have any peripheral state
and basically didn't have division.
So I moved the division to the end host and the switches
just copied the raw inputs to the division on the packet.
And the switch is more flexible.
You can move the computer around between the switch and the end
host in different ways.
So that's the scheme that I'm working on right now,
and there's quite a few interesting schemes
and questions that I'm exploring.
One is what is the minimum time that
is needed for any distributed scheme to figure out
these maximum fair rates.
So for schemes like this like the one
I described which calculates explicit rates,
there is research that shows that the minimum time depends
on the dependencies that are there between different links.
And the longest dependency chain is basically
your bound for how long it will--
the minimum time it will take.
But I'm not sure how this would compare to something
like a scheduling scheme.
And second is what is the minimum amount of state
that we need to keep at the switch.
So for my P4 program, I simply got rid of this per flows
state that I had.
But it's not clear that I can prove that it converges,
so it's not clear whether we actually per flow state
to converge.
So that's something I'm looking into.
And a third very interesting question
is how many active flows are actually there in a network.
Like today in papers and all you'll see, oh yeah,
there's like hundreds of thousands of connections.
But if you look at RTT time scales,
at least what I've observed from my simulations
is that there's very few actually
like tens of flows even when the link is quite loaded.
So maybe we don't have to worry about keeping per flow state
if that's necessary.
So I'm trying to see if there's some theory that
can support this conjecture.
And finally, the end host may not
be sending precise demands, because they can't always
[INAUDIBLE] the links at the rates that you give them,
and so we might need some reactive component to actually
measure how much they're sending and how to adjust the rates.
So yeah, that's all.
[APPLAUSE]
Questions?
Yeah.
I have a somewhat naive question.
So what kind of distribution of flow sizes
do you think you actually get benefit from proactive side?
The reason I'm thinking of it is like if most fields are sharp,
[INAUDIBLE] doesn't really buy you much.
And if most fields are long, it's like OK, fine,
7 RTTs is not much in the grand scheme of things.
So it seems like-- so there's only
like a narrow range of distributions
where it actually benefits you.
It's like OK-- or you have to be like 10 RTT duration flows.
That's where you get the most benefit
of [INAUDIBLE] because those guys are coming from 7 to 1
or something like that, right?
Is that real?
Is that why people are expecting this on the deep networks?
I mean, I don't know.
I'm just asking.
Yeah, that's a question I've been thinking about too,
so basically while proactive schemes are-- reactive
schemes typically take tens of RTTs and at 100 gig links,
most of the flows are like very short.
So if you have a reactive scheme, if-- I mean,
they don't even have to be perfectly fair,
but if they're like getting far--
if there are some flows that are being starved
or getting like rates that are way off where
the reasonable rate would be, they will just stay on
in the network for a long time.
So you want rates-- well, you want schemes that can quickly
converge, and I feel like your active schemes converge
to some reasonable rates.
And so, practice scheme seem like a good candidate.
Reactive schemes, I don't think would ever work.
But at most [INAUDIBLE], it's like, oh, does it matter?
I mean, it's not even going to last for 30 RTTs, right?
Well, it can get very terrible.
So there is an example I used in the paper
where there is like just two flows, but one of them
gets the wrong rate and it lasts like
much longer than the few RTTs.
So yeah, much longer than like it
could be, maybe like at least four or five times slower
than what it would take if it had the [INAUDIBLE].
But the point you made is right, that you
don't need to find-- you just need
to have some reasonable rates.
They shouldn't be terrible.
All the flows need to get some reasonable rates
if they're very short.
You don't have to be perfect.
Can you compare your scheme to XCP?
[INAUDIBLE]
So in spirit, the scheme is similar to XCP in
that it wants to find-- it wants to speed up
traditional congestion control.
And the way it's different is that XCP is a reactive scheme,
like you measure cong-- it's like it measures condition
signals and then reacts to it.
On the other hand, here, the scheme
is using information about which flows
are active to just calculate the rates without-- it's
like an open loop system.
It's not even looking at the network congestion
to calculate the rates.
So in that way, it's very different from XCP.
[APPLAUSE]