Hello, everyone.
I'm Victor.
And I'll be talking to you about simplifying network
optimization for SDN deployment doing
the work with my advisors, Mike Reiter and Vyas Sekar.
Let's talk quickly about SDN, overview of it.
I think a lot of us have become familiar with this picture.
You've got your data plane.
You've got your control plane.
Everything is great.
There are a lot of SDN applications
that are running on top of your controller.
There could be a whole lot of them, of different kinds,
and you've got this nice engineer or a guy who's
typing everything up and everything is great.
Well, this is kind of an oversimplification and not
even because I'm ignoring all of the complicated stuff that
happens between the control platform and the data plane,
mostly by what happens between the application and the control
platform.
What we have is not an engineer but a scientists,
much like one of us, who's got a whole bunch of tool
boxes sitting next to him, whether it's
in the optimization tool kit, it's
a book of all the fancy algorithms we learned,
or even their colleagues.
And so it is not a trivial process
to write in SDN application, especially
the one that does something with optimisations.
So network optimizations are very common, even
something as simple as max flow or traffic engineering,
all these classic applications we've learned,
optimizations creep up in recent literature.
We've seen a lot of papers published in networking
conferences we all love.
And they all, at some point, try to provision
the network using a network optimization.
And to write one of these papers is actually
not an easy process, either.
Here's how I approximate it.
And it's illustrated with various stages
of anger you might experience while you go through it.
So you try to learn your theory and your optimization trying
to become a theory expert, much like some of you guys.
Then you formulate your problem using a linear program,
integer linear program, any other fancy techniques
you know.
You solve it with a solver.
And at this point, you start getting irritated.
This is taking up your time.
It's not just, oh, I'll code up something in a week.
And then you realize, oh, I'm actually solving an [INAUDIBLE]
higher problem.
So you have to go and go, OK, well how do
I develop a heuristic for this?
You code that up.
You still have to parse what your solver gives you
and then go, OK, how do I translate that
to your SDN controller.
All right, so what we would like to do in our work
is our vision is to take the scientists guy, with all
of his fancy tool boxes, and replace him
with an engineer, essentially, who can actually
write things much quicker using some sort of simplified
interface.
And maybe we'll replace him with management.
I know, that's kind of taking a little too far.
So how do we do this?
We would like to introduce an optimization layer.
It's a layer that runs on top of your control platform
and kind of hides all this theory stuff.
All the theory and fancy stuff is
sandwiched in the optimization layer, which
exposes a much simpler API to the engineer who's
writing the application.
So what are we aiming for?
We are aiming for no custom heuristics.
We don't have to reinvent the wheel
and come up with a heuristic each time you
have a new problem.
We would like to give the engineer the ability
to specify high level goals or high level
intents about what should happen in a network
and not muck around with little variables
and all the other stuff that would normally
go into an optimization.
We would like to be able to give developers the ability
to rapidly prototype an application.
And that also kind of ties into the last point,
which is, an application should be
something fairly quick and easy, like 20 lines of code.
And you've got yourself a traffic engineering
or a service training application
that you can play with.
So OK, why hasn't this been done before?
What's really the trick here?
What's the challenge?
Well, the challenge is achieving two properties
that we, as computer scientists, really love.
We love generality and we love efficiency.
So what we've seen before in previous work
is a lot of frameworks that cover generality really well
but they're not efficient.
They can't generate the solution really fast.
Or we've seen custom solutions, and this goes back
to heuristics and all these papers
you publish in networking conferences, where they solve
one problem very specifically and very well, very fast,
but it's not sort of re-usable.
The solution you've come up with isn't
reusable to other problems.
Now in our work, SOL, we try to achieve both.
So let me tell you how we actually do that.
So SOL stands for SDN optimization layers.
This is the sort of framework we're proposing.
This is what we're designing.
And it is the optimization layer that
sits on top of the controller platform and talks
to a solver, such as CPLEX or Gurobi or whatever.
It's a general linear program solver.
It exposes a set of interfaces, or APIs
as we call it, to the developer or the SDN applications,
the developer who writes these applications.
The good thing about this, the optimization layer
and the control platform are logically centralized.
So it's a good fit for SDN.
That's what we knew for a while, now.
Optimizations are great when they're centralized.
The problem is, this set of applications
is incredibly diverse.
So a number of things you might want
to express in your application is very large.
So how do we model all of them?
Well, let's talk about it.
The first insight we have is the path abstraction.
So all of these optimization problems
are recast to be path-based.
And the second thing is we apply policies to your network
by applying predicates to the paths.
So let me talk about these in a little more details.
First of all, path-based recasting.
If you think about your classic networking
problems, such as max flow, you can write a lot of them
as integer linear programs or linear programs.
If you wanted to do max flow, what you would see
is something like on the left.
You have your network.
You have your source.
You have your destination or sync, SNT.
And you have all these variables that talk about how much
flow you're sending on each link in the network, fairly similar.
Now, there is an alternative way of writing that same problem
that you kind of see on the right, is
instead of thinking about these variables being for each link,
you think of variables being per each path.
Now, you have to enumerate all of the paths.
And you have to assign them all of these variables
and that's kind of the problem.
So what happens is, you have a lot of these.
And I'll touch on that in just a little bit.
Second thing I would like to say is,
policies as path predicates.
We as networking people love policies.
That's what we do.
We route traffic according to a policy.
Now, encoding that in the optimization is very difficult,
or can be very difficult. So what we do is we
separate that out.
We generate the paths first and then
we go, OK, paths can be valid or invalid according
to a predicate.
So in this particular example, if you would like to say,
oh, my traffic must hit a firewall and a proxy.
And it must go from node 1 to node 5,
you will end up enumerating your paths and saying,
OK, we have 2 valid paths and 1 invalid path
because it doesn't hit an IPS-- or sorry, a firewall.
So why do we do this?
What this buys us is generality.
So because a predicate is an arbitrary piece of code,
essentially, you could make your paths
to be whatever you want them to be.
You could say firewall followed by proxy.
You could say path is only valid in Wednesdays.
So that's the good thing.
However, to achieve this we do have
to enumerate all of the paths and then filter them.
That presents a problem.
Because exponential number of paths in a network,
large optimisation size, long running time, bad efficiency.
We just kind of sacrificed one of our goals.
We have to get back at that efficiency
once we've got this much generality.
How do we do it?
SOL process.
We do generate all the paths in a network first.
So yes, there are a lot of them.
We enumerate them, all simple paths.
And we keep the ones that match the predicate.
There are still a large set of them,
so that's why this is an offline step.
This is the first thing we need to do before we even
get to the actual optimization part.
Number two is we do path selection or path pruning.
This works as a general heuristic
step that lets us throw away a bunch of the paths
we consider not to be important in the optimization.
This is the step that lets us get back
some of that efficiency.
SO out of the millions of paths you could have in a network,
we pick a few that we think are going to be good.
Then using those paths, we can create the optimization.
So we construct these sort of linear program
or ILP that we then solve.
And we finally use the output of that solution
to actually deploy the rules or the configurations
of the network.
While this step might be kind of dismissed as trivial,
this is one of the things that allows
us to sort of do that substitution from the scientist
to engineer.
It just says, I give you the high level goals of the network
and you do the rest.
So given all of this, let me just quickly talk
about an implementation.
We've actually done this.
This is implemented as a Python library and interfaces
with a CPLEX solver and even on this controller.
We did end up prototyping bunch of applications
just to show you that both the classic problems and the sort
of problems from recent literature
can be expressed in our framework.
So we've taken max flow and traffic engineering.
We also have taken Elastic Tree and Panopticon SIMPLE
as examples of work from the literature that could be
expressed using our framework.
Now, just to give you a flavor of what
this would look like for a few systems people in the crowd,
if you wanted to do something like max flow,
I'm ignoring a little bit of a set up here,
but in 6 lines of code you essentially
have yourself a max flow formulation.
And so what you're doing is you're saying,
yes, we'd like to initialize an optimization.
This is your topology and your source destination pairs.
Then you give a few parameters for path generation
and selection.
And then you proceed to create, essentially, your problem.
You're saying, I'd like to allocate
some flow from my source nodes to my destination nodes.
Then you actually create a little function
that dictates how resources are being consumed in a network.
In this case, this is just a bandwidth.
And then you proceed to say, OK, we would like to cap our links.
Who likes overloading their links?
After this, we just go global objective, which is max flow.
And then we solve the optimization.
Six lines, you've got yourself a max flow problem.
Now, let's say you want to do traffic engineering.
It's no longer max flow, it's your load balancing your links.
Everything is pretty much the same except these two lines.
Now you would like to route all traffic that you have.
So for all your demands you'd like to not drop anything.
And you'd like to minimize bandwidth load on your links.
And just like that, you actually have yourself
two applications, what used to take a lot of time
now it takes, hopefully, less.
So a few quick key questions we'd
like to ask before we sort of go on to the evaluation.
So does it reduce the development effort?
Are we actually making anybody's life easier?
Is it faster than the original and is it
any worse than optimal?
Because as I mentioned, we do have a heuristic step
that kind of throws a lot of things away.
Let's take a look at development effort.
The short answer is, yes, we believe we
do reduce development effort.
So we have prototyped these three applications
from the literature.
In all of these, the optimization
that used to take half a page to write just mathematically
can be now done in about 20 lines of code.
Now, I admit that lines of code isn't
the best metric in some cases but it's a good place to start.
And we do think that it's an important metric
to take a look at.
Second question we had is run time,
is it any faster than the original?
And the answer is, yes.
So here you see two graphs, two prototype applications,
Panopticon and SIMPLE, taken from the literature.
On the x-axis you see different topologies
with their sizes in brackets.
And on the y-axis you see time in seconds
to actually solve the optimization.
I'd like you to note the log scale
and I'd like you to note the shaded regions.
The shaded regions mean that the were original did not
complete within half an hour.
So we just decided to cut it off.
We didn't think it was worth it to run it longer than that.
And so the take away here is that the SOL implementation
is actually orders of magnitude faster
than the original integer linear program that
was formulated in this paper.
And in all of these cases we are less than 1%
from being optimal.
I don't have a lot of time, so let
me just go straight to the potential future directions.
There is some work left to do here, especially
from the theoretical side.
We would like to analytically show why
path selection is effective.
At this point we've said, OK, let's throw away a lot of paths
and just keep some.
And I didn't even tell you how we keep some.
There are two strategies.
They're very, very complicated, shortest path and random path.
Why does it work?
There is a good intuition for it.
For example, random paths work because if you
want to load balance, randomness just kind of
lets you load balance naturally through the network.
But can we prove any sort of theoretical bounds on it?
Perhaps.
And the second thing is kind of flipping the problem upside
down a little bit and saying, can we
create path selection that honors bounds and optimality?
So I said that we've done some path selection
and we are less than a percent away from optimal.
Can we do it the other way around where
I say, I want percent away from optimal,
give me the paths that I need to put into my optimization.
So just a quick summary, getting SDN benefits
requires a lot of expertise at this point.
SOL lowers these sort of barrier of entry for developers
and helps you write the applications
in a much easier way.
It leverages the path abstraction for a plus--
this general heuristic that is path selection.
It is very efficient.
We can deploy a network in about 15 seconds for a basic traffic
engineering application.
And we do believe it creates new opportunities for future work.
So if you have any questions, happy to take them or shoot me
an email.
Our code is public on Github if you'd
like to see the internals.
And there is a paper that appeared in NSDI 2016
if you'd like to read a little more.
Thank you.
[APPLAUSE]
Yes?
So great work.
My question is like, so this simplifies a lot of stuff.
But by doing that is it losing some flexibilities
or freedom of doing stuff?
Because for example, using your language or framework, can
you say, OK, you want to do some waypoints or things like that.
Can you do that?
Yes.
So generating a path, using the path predicate,
you can just filter out the paths that you don't like.
So that we can do.
There are certainly some things we can't do right now,
or maybe we'll never be able to do.
I don't know.
[INAUDIBLE]
I mean, right, there is limitation on the generality
to almost everything.
Did you get a chance to evaluate the quality of [INAUDIBLE].
By quality you mean?
So how good your solution is.
Yeah.
Yeah, we did.
So in most cases, we are less than a percent away
from the actual optimal solution.
Any other questions?
Thank you.
[APPLAUSE]