OK.
So today, I want to talk about Flowtune in a few minutes.
This is joint work with Hari Balakrishnan
and Devavrat Shah from MIT.
So what is Flowtune?
We tried to create an architecture for data center
networks, where we can allocate network resources
with extremely fast convergence time
to the optimal location, where we have
a very explicit notion of what the optimal occasion is,
and a system that has a very flexible deployment story-- so
basically, in software only.
So we start with a very similar motivation to [? Levanya's ?]
talk, the previous talk, where we looked at these existing
schemes.
We looked at-- just to drop some names-- DCTCP, P Fabric, CoDel
with SFQ, XCP, and others.
[? Levanya ?] showed RCP, but we saw similar results.
And we think the problem is that these schemes are
packet-centric.
So what I mean by that is these schemes
specify what to do at the switches per packet.
So how do you cue packets?
For example, drop tail stochastic fair queuing
priorities.
And how do you mark or modify packets?
And at the end hosts, these schemes
specify when the next packet should be sent
and how to react to these per packet congestion signals.
And this has three major disadvantages.
So first, in the data center, we mostly
care about per flow objectives.
And translating those into per packet mechanisms is hard
and sometimes we don't get it right in every situation.
A second issue is these schemes take several round trip
times to converge.
And [? Levanya ?] mentioned that in the previous talk.
And lastly, if you want to change the policy,
frequently you have to switch algorithms, which we all
know is very painful to get into hardware,
and many times the sort of algorithms,
which is hard to do as well.
So we tried to overcome these.
So what we do with Flowtune, we take a somewhat different
approach.
And if you take just one thing out of this talk
is that maybe, as a community, we
shouldn't allocate resources on a per packet
basis with per packet mechanisms,
but rather allocate them per flowlet.
And here we have a specific definition of flowlet.
Here we mean a batch of packets that are queued at a sender.
So if the application wants to send a one megabyte buffer,
all of the packets for this one megabyte buffer
are the same flowlet.
And we argue, like we heard previously today,
that allocations should only change
when the set of flowlets alive in the network should change.
So for example, if you have this network with these two flows,
you either want to prioritize one over the other or you want
to allocate resources 50/50, or 10%/90%.
But this should remain constant as the set of flowlets
remains constant.
And the time you want to change allocations usually
with these per flow objectives is when flowlets arrive
and when flowlets terminate.
A second part of our approach, which is a design choice,
is we want to centralize the allocation.
So here I'm arguing for the Oracle approach.
And we think that the Oracle is feasible
in medium-sized networks.
I'll show some results later.
And here we wanted to overcome the multiple RTTs
that it takes to converge.
So let me run through an example.
Let's say A has a flowlet for B. A
opens a TCP connection, starts transmitting.
And in parallel, it tells the allocator
here this process, Hadoop on A, has
some packets for B. The allocator looks at this flowlet
and assigns rate.
It tells A, here you can blast its line rate.
So at the time that A gets this allocation from the allocator,
it can just blast away at line rate.
So it very quickly opens the window.
Now another flow enters the network.
C has some packets for B. And C opens
its connection, in parallel contacts the allocator,
tells it I have some data from this ad service for B.
The allocator looks at these flows again and says,
ads is more important in our network
than Hadoop, so I'm going to allocate one
gigabit to A and nine gigabits to B,
tells the endpoints the rates, and the endpoints enforce this.
So you might say, hey, this doesn't
seem like a hard problem.
You phrased it this way.
You just allocate rate.
You have a set of flowlets live in the network.
Just assign the rates.
Well, this is actually harder than it seems.
So even if you have an optimal location,
now you're trying to add a flowlet.
The problem is that the updates to rates
cascade in the network, making the whole approach very
expensive.
So let me show this example.
So look at this link over there.
The new flow shares this link with an existing flow.
So the rate for the existing flow
might need to be lowered to accommodate the new flow.
Now, on a few links, there's spare capacity
that you would want to allocate to different flows.
So the rates of these flows change, and so on, and so on.
So in general, just an update too
is a small part of the network, one part of the network
very quickly cascades across the network,
making it really expensive.
The second problem is we don't even
know what we're trying to optimize.
Are we trying to get just a variant of TCP
that converges faster?
Are we trying to get the same thing as TCP?
Can we get something better?
How can we make this more explicit?
So to address this, we leverage the NUM framework, the Network
Utility Maximization framework, proposed
by Kelly and his co-authors in the late '90s.
So I'll show the economic intuition
for the NUM framework.
So what we do is we assign a price p for every link.
And we adjust p based on supply and demand,
where supply is the link capacity and demand
is the sum of the rate of all the flows
that traverse that link.
And we adjust prices.
If flows want to send over the link capacity,
then the price increases.
If flows want to send below the link capacity, price decreases.
And now, given prices, each flow can optimize its own rate.
So each flow knows its utility.
So this is what it gains from each allocation--
so what it gets at one gigabit, at two gigabit,
at three gigabit, and so on.
And it also knows the price it pays per gigabit per second.
So it can subtract the two and get its profit.
So kind of revenue minus cost equals profit.
And each flow can selfishly optimize its rate.
So it's going to choose the point where
it gets the most profit, the rate where
it gets the most profit.
So here it would choose 2.2 gigabits per second.
And the magic of NUM is each flow
optimizes its own profit selfishly,
but the prices drive the entire system to a global optimum.
So it maximizes the sum of utility from all the flows.
And the secret sauce in any such NUM framework-based scheme
is how to exactly update the prices.
There's supply and demand.
How do you change the prices?
What is the delta when you have a difference in supply
from demand?
And we have some innovation there,
but I don't have time to explain.
But I'm happy to talk about it offline.
So this is an iterative scheme.
So you adjust prices based on rates,
then rates based on prices.
Prices based on rates, rates based on prices.
So you need several iterations for a system to converge.
And usually we've found that it takes around 100 iterations
to converge.
Unfortunately, this is way too slow to run in practice.
We wanted something much, much faster.
So our first attempt at trying to solve this is saying let's
run want iteration.
So we update the network state, run one iteration.
Then maybe some other flowlets arrive or leave,
run another iteration.
So update, run an iteration.
The problem is that this doesn't behave very well.
So what happens is that links are over-allocated.
So let's say a new flowlet arrives in the system.
There is extra demand on some links.
So the prices for these links should increase.
But for a few iterations, the prices are too low,
and flowlets over-send on these links.
So this causes congestion, buffering, packet
drops that we want to avoid.
So what we did with Flowtune is we introduced
another step, a normalization step,
after the optimization iteration.
So what this does is for every link that is over-allocated,
it scales down its flows that traverse that link,
so that the link is not over-allocated anymore.
And what this gets is-- if you look
at the top line-- we're able to get
99.7% of the optimal throughput, while completely
avoiding these over-allocations, like packet loss, buffering,
and so on.
So just to review what the architecture looks
like-- endpoints send these notifications of flowlet
arrival and termination to the allocator.
The optimizer continuously runs these iterations of NUM
and kind of updates its flow state,
runs an iteration, updates flow state, runs an iteration.
And after every iteration, it copies the rates
to the normalizer, which normalizes the rates
and sends updates to the endpoints.
So I have-- yeah?
So the iterations are taking place quickly,
though they're just [? happening ?] in computation.
There's no round trips for the prices to be--
Exactly.
You don't need to propagate--
--assimilated in the controller.
Yes, everything runs on the same CPU on the controller.
Yeah, so a couple of results.
So we ran this experiment to find out
how quickly Flowtune converges to the right allocation
in a network.
So what we did is-- a similar experiment
was run in the DCTP paper.
So what we did is we had five senders and one receiver.
And every 10 milliseconds we started a new sender sending
to the receiver.
And then after five senders started up,
after every 10 milliseconds, we stopped one of the senders.
So what you would want to see is in the second graph,
what Flowtune achieves, that with n senders
each flow gets-- sorry.
So what this is a function of time.
So x is time.
y is the rate for each flow.
So there should be five lines there on every graph.
So in Flowtune all the lines overlap.
And when there are n senders, every sender gets exactly 1/n--
of [INAUDIBLE]-- of the link capacity.
What you can see is DCTCP oscillates
around the fair allocation.
P Fabric minimizes flow completion time.
So it just chooses the one flow and goes with it
until it finishes.
So CoDel with SFQ has a lot of packet drops,
so the rates that the applications see
are very bursty.
And XCP is very slow to hand out traffic,
because it needs to measure the network.
It takes a long time for it to react.
We've been able to scale Flowtune.
You can see the last line of the graph there.
With 64 cores, we can allocate 4,600 servers,
49,000 flows in 31 microseconds.
So it's around two to three round trip times.
So your network can allocate resources very quickly.
So I've talked a bit about Flowtune.
We've used flowlet-based control and used the NUM framework
with a normalization step to get these three goals very
quickly converge to the optimal allocation,
have an explicit kind of notion of what is optimal
and do this entirely in software.
And even if you disagree with the design decisions--
obviously, this doesn't scale to the world's largest data
centers-- but if you think these are exciting goals to have,
then please come talk to me later,
and we can do something together.
So I'm happy to take questions.
[APPLAUSE]
You can ask about fault tolerance, about--
[LAUGHTER]
[INAUDIBLE]
I'm just curious.
Maybe you have a feel for this or maybe somebody else does.
But in your example, where you had 4,600 servers and 47,000
flowlets, is that a high or low number of flowlets?
Like would a normal server have thousands
though simultaneously?
You've got 10 there.
Right.
And I don't have a gut feel for that.
And of course, it depends on the application.
So I think the VL2 paper published results at Microsoft
from-- they're pretty old by now.
It's 2010, I think.
So they had this distribution of number
of flows active per server over very coarse granularity.
This, you would only account for the actual live flows
and they took 10 milliseconds, or something.
And it shows, if you look at the distribution,
the median is around 10.
I'm actually looking for [INAUDIBLE].
I thought [INAUDIBLE].
And the card's saying don't use that CDF for anything.
There are others.
So actually, I had a different question.
So you guys did this Fastpass stuff, right?
So it seemed like the key difference
is you are doing more kinds of utility functions.
Is that what it is?
Yes, so here you have an explicit utility function
that you can have per flow.
So Fastpass is a framework where you
can prioritize different flows when you allocate, and you
can prioritize them differently between time slot to time slot.
But it's still a packet-based scheme.
It was really hard to express a lot of these in Fastpass-- hard
or sometimes impossible.
And also, we tried to scale.
Then we realized that you have this cascading
problem in the network.
Right?
We said, if we just scheduled flows instead of packets,
we'd do a lot less work.
But then we found out that it's not as easy as it seems.
But we were still able to scale 10 times more.
So it's more expressive and more scalable.
Is that what?
Yes.
OK, good.
And the nice thing is that, in some sense,
Fastpass you have to do per packet work.
So if you go from 10 gigabit to 40 gigabits to 100 gigabits,
you automatically scale down.
It hinders your scaling.
Whereas here, if you allocate rates, then maybe
you're not as sensitive to the technology you're using.
So since you asked for open-ended questions,
do you have ideas about how you would make this less
centralized?
Would you have to worry about things
like-- I guess, either the resources get charted
or you have some kind of control.
[INAUDIBLE] issues, like stability.
So first, you said, if you have any notion of how
to make this less centralized.
I'm not sure that that is a goal.
We kind of know, as a community, how
to build centralized systems now, more than before.
And we have failover.
We have quorums that decide on what is the primary replica.
We have a lot of tools at our disposal.
And Flowtune is not as sensitive to faults as Fastpass is.
But that said, scaling is an issue.
So how do you use multiple computation resources
spread across a lot of servers that use the system.
Yeah, that is a concern.
We have this schema that I hadn't had time
to talk about-- it's in the bottom-- of how
to distribute this resource allocation
and network to many cores.
And we believe this can generalize to many servers.
So many of these allocators working in tandem
with this pattern of communication between them
that has good properties.
We haven't tested it out yet, so it's still an open question
whether we can scale up using multiple machines.
Aren't they going to make change?
Are you going through everything or just make a [INAUDIBLE]?
We make an incremental computation.
So the optimizer runs one iteration at a time
and keeps the rates from the old iteration.
So it computes prices based on rates and then rates
based on prices, and so on.
So what we do is we just do one iteration of this,
then maybe add some flowlets and remove some flowlets.
So the prices are around what they are supposed to be.
Then we run another iteration, and so on.
So we reuse.
We update state.
Do you have a sense of how far now from the [INAUDIBLE]
you are, because you can stop before the thing actually
can do this?
Yeah.
So if you have long-running flows that are more than 100
RTTs or 100 iterations of the algorithm,--
so you have a new flow-- that part of the network is going
to be in disruption.
So it's not going to converge for a few iterations.
Maybe not 100-- 5 or 10 iterations.
After 10 iterations, you're fine, because you've converged.
The problem with normalization is you trade off optimality.
You just want to cramp all your flows
on to the links, just kind of extinguish fires.
So for maybe a few iterations of the algorithms,
you're not optimal.
But we found that you're-- this graph shows that,
at least in this example, it converges very quickly.
[APPLAUSE]