Hi, everyone.
I'm Harry Liu from Microsoft Research.
And today, I will tell you a beautiful story
of the marriage between theory and software defined network.
And today, I will talk about how can we
achieve efficient and robust traffic engineering
with a concept called forward fault correction.
So nowadays, cloud services are rapidly
growing, which gives a cloud network a very huge pressure.
So on one hand, the traffic demands ramping up very fast.
On the other hand, it's really expensive
to build and maintain new networks.
So to handle this tension-- and it's
more and more important to consider,
what [INAUDIBLE] says, the efficiency of the network.
And this is why people are motivated
to study how to use traffic engineering, which
is centralized and SDN-based, to boost the network efficiency.
And they already showed that they are effective and have
huge potential.
And let's use a simple example to show you
what is traffic engineering and why centralized TE is
the key to network efficiency.
So this is a very simple network where
there's four nodes, four links, with link
capacity with bandwidth 10.
And one flow reach this network--
and for example, if the source is 1,
node 1 needs to make two basic traffic engineering
decisions-- the first, how much traffic to administer
the network; and the second, how to route to the destination.
And in this case, let's assume it
admits the fully 10 bandwidth and use two paths for the flow.
And each path has 5.
And then later, there is another flow-- comes from 2 to 4.
And then 2 makes the same decision, but at this time,
2 only sees 5 capacity from 2 to 4.
So it only admits 5.
So in total, the throughput is 15.
And obviously, this is suboptimal,
because optimal throughput should be 20.
And the suboptimal is caused by the local decision
between 1 and 2.
And if we have centralized TE controller
and it knows what's going on globally in the network
to configure multiple devices, it
can achieve optimal throughput.
So overall, the centralized TE's architecture is like this.
So we have a conceptually centralised controller.
And it keep monitoring and the controller in the network.
It has the network view, including the topology,
capacity, and traffic.
And it's making a TE decision and translating the TE decision
into network configurations.
And it push it all the network devices.
And because the traffic is changing all the time,
it also needs to frequently update
the network configuration to achieve high utilization.
And this architecture also have a weakness.
It's because the TE controller, it's monitoring and controlling
the network remotely.
So it's very vulnerable to the faults
that can happen in the network.
And today, we will focus on two kinds of faults-- data plane
faults and the control plane faults.
So data plane faults means the device and the link failure.
So when this happens, basically, the topology has been changed.
And the capacity has been changed.
And it will cause severe congestion.
For example, given this network, suppose
there are two flows going through.
Each flow is using two paths from the source
to the destination.
And if the link from s2 to s4 goes down,
what happens next is that the s2 route very quickly does
a local reaction.
The local reaction is called rescaling,
which means it will stop sending any traffic on this failed
path.
Instead, it will proportionally send all the traffic
to the residual path.
So in this case, there's only one residual path.
So after the rescaling, the traffic distribution
would be like this.
And there will be link congestion.
And then the other kind of fault is control plane faults.
That means the failures or long delays
to configure a network device.
So it's caused sometimes by the TE controller's communication.
And the communication channel can break.
But also, in the switch side, there
are bunch of a problems that's prevented
the switch from responding in the configuration.
So you can see if you want to reconfigure
a bunch of switches, and some are not responding to you,
and still use the old one, this mismatching
will also cause severe congestion.
So for more examples, you can refer to our paper.
And let's get back.
So now, let's understand why exactly
the data plane faults and the control plane faults
are causing problems.
Because basically, the data plane faults
make the topology and the capacity of the network
keep changing.
And there's quite inaccuracy in the network view
to the network controller.
And on the other hand, the control plane faults
create incompleteness of the natural configuration.
And this seems to be a very fundamental problem
when we use this centralized control architecture.
And now, the problem is whether these faults are very common.
And unfortunately, yes.
So we did a study on Microsoft WAN, which
is the largest scale network.
We found that these two kinds of faults are very common.
And from time to time, they are causing severe problems.
For example, we found that every 5 minutes,
you have a one quarter chance to have at least one link go down.
And each time you want to configure a switch,
there is 0.1% and 1% chance that you cannot configure it.
And in a fully utilized network, even a single failure
will cause severe congestion.
This shows the link over-subscription
when we introduce a single link failure.
So because this is so common and so important,
we want to see how to handle it.
And let's first look at what's the state of art.
So currently, there are only two methodology, mainly.
The first one is have a over-subscription,
which means blindly leave spare capacity everywhere
in every link.
Hopefully, that can work.
But actually, this usually does not work.
But the one thing is for sure that we
will have a big loss in the network throughput.
And that the other methodology is to react to faults.
We don't do anything until the faults happen.
But remember that in the real network, a logistical network,
reaction is really slow.
And when you react slow, it means that you cannot prevent
any connection from happening.
And reaction means another round of network configuration.
And this round of confirmation can still
be blocked by the control plane faults.
So the network will be messed up.
And instead, what we want to do is to consider a new angle.
So how about handling the faults proactively?
And it means that, if the network we cannot assume is
100% robust, can we build any robustness into the TE
algorithm?
So that when the TE algorithm figures out a network
configuration and when it configures the network,
the configuration is not only valid in the current situation
of the network, but also can handle the dynamics
and uncertainties that can happen in the near future
of the network.
So when some problems happen, the configuration
can fix itself and without the reaction of the TE controller
until next 5 minutes.
It just configures a new configuration.
So if we go along this way, we are facing a challenge
that no one is knowing what exactly will happen in next 5
minutes because individual faults are
really unpredictable.
But we also have some good news.
Because in next 5 minutes, the simultaneous number of faults
should be small.
And this reminded us of very similar case in communication
when the sender sends some receivers some packets
over a lossed channel.
And it's almost for sure that some packets will get lost.
But you never know beforehand which packet will get lost.
So people created the concept called forward
error correction.
That means, I want to encode the data in the case
that if only the number of lost packets is up to k,
I can recover all the information.
So given the similar situation, we
create a similar concept, which is called forward
fault correction.
This means we want to find a network configuration
of traffic engineering that can guarantee
no congestion if only the number of faults is under k.
So we all know that FEC receives this concept with a carefully
designed data encoding.
And the way you achieve this concept, with a carefully
designed traffic distribution.
So before showing you how we systematically
achieve FFC concept, let's look at an example
to show you this kind of robust TE does exist.
So this network has two flows.
And the traffic demand is 9.
And they are using two paths.
And they split with 1 and 8.
And I will say this is FFC 1 for the link.
So it is resilient to any single link
failure on this technology.
For example, when this link goes down and after the rescaling,
the traffic is like this.
And when this link goes down, no congestion, no congestion.
And because the traffic and the topology are symmetric,
so you can verify the lasso tool.
So there is no congestion, and there is single link failure.
And what's more interesting is to put non-FFC and FFC traffic
engineering together.
And the first one is non-FFC.
The third one is also non-FFC.
But if we can pair the first one and the second one,
we can see the trade-off between throughput and robustness.
And if the throughput requirement is 30,
we have no way to find any FFC traffic engineering.
Because for the robustness, we have
to leave some spare capacity on some critical links.
And it will have some overhead on the throughput.
But what's more interesting is to look
at the second one and the third one
knowing that they have the same throughput.
The only difference is how you spread out
the traffic distribution.
And it means that FFC sometimes is frail.
It's just a matter whether you're
smart enough to find a good traffic distribution.
And based on the trade-off between efficiency
and robustness, we want to find out
a sweet spot in this trade-off.
What we want to find is a kind of FFC guarantee.
We want to find the traffic engineering that's
achieved optimal throughput.
By optimal, I mean that I can fully satisfy all the traffic
demands, or I can satisfy them as much as possible.
So now, let's systemically consider how to achieve FFC.
And we have two questions to answer-- first,
how to model this concept; second, how to find FFC TE.
And currently, people typically use linear programming
to find the traffic engineering distribution.
And basically, they make the TE decision as variables.
And they have some objective to achieve-- for example,
maximizing the network throughput.
And they have some basic TE constraints.
And if you translate English into linear programming,
it will be straightforward.
And because FFC is the further requirement
for the final traffic engineering we want to find,
so it's natural to think whether we can just
plug in some FFC constraint that can guarantee
that the final traffic engineering decision we find
achieves the FFC requirement.
We call this FFC constraint.
And now, the question is, what does it look like?
So first, we use a simple example
to show you what does it look like.
And suppose there is one flow.
And the source is s.
Destination is d.
And from source to destination, there are three paths.
And we assume that the paths are link-disjoint.
So a single link failure can at most turn down one path.
And what do we need to decide is the flow size f
and the bandwidth allocation on the 3 paths.
So if we have the FFC case of k, that we
wanted to [INAUDIBLE] to any single link failure,
it means that when path 1 goes down, path 2 and path 3
has sufficient capacity to deliver the flow.
And similarly, when path 2 or path 3 goes down,
so the other two will have sufficient capacity
to deliver it.
So overall, it's 3 choose 2.
And you can easily see that this is the necessary condition
for the FFC.
But in the paper, we have [INAUDIBLE] that finally, you
set the path wave like this.
And it will become a sufficient condition.
So when it's achieved, it's guaranteed
that FFC is achieved.
So let's generalize it.
If we generalize it, and you follow
this flow, if we have n paths and the we want
to decide the bandwidth allocation along these n paths,
and we want to be resilient to k link failure, that
means the arbitrary n minus k-- that is residual tunnel--
should be enough to support the flow size.
And if we write this requirement down,
we will have n choose k constraints.
And we called this group of constraints
as k-sum constraint [INAUDIBLE] naming.
And then, let's go back to look at the structure of the FFC TE
formulation.
So we have normally objective, basic constraints.
But we have a lot of FFC constraints.
And the FFC constraints consider many, many groups of k-sums.
And this is just for data plane faults.
For control plane faults, you can also formulate it--
finally, the k-sum problem.
So now, the challenge is, in the largest scale network,
we have too many constraints.
We cannot solve it directly.
And what do we want to do is to achieve a lossless compression
of this k-sum constraint format, which
means we want to find a small number of constraints that
can sufficiently represent the original constraint
and still achieve the optimal objective.
So there's no loss in the [INAUDIBLE] of the objective.
So [INAUDIBLE] paper, we found a way
based on bubble sorting network.
We reduced it from n choose k to kn.
And recently, we have progress.
We found a way to reduce it to On.
And because these are short talks,
I won't show the details, but you can visit to my home page
for details.
And in the project, we also find that in traffic engineering
domain, there are many, many extensions that-- we found
FFC is just like a plug-in.
You can easily plug in the existing system
and just add some more constraints,
and survey it, and find a more robust TE.
And it can extend to support different traffic priorities.
And even if there's no traffic limiters,
we can still use FFC to minimize the congestion.
So now, I give highlights of the implementation
and the evaluation.
So I only have two points to stand.
The first one is FFC can fully be implemented in the commodity
hardwares.
And the second point is that with real network topology,
real traffic, real event, we find
that actually, FFC's throughput loss is negligible,
but it can reduce the data loss significantly.
So here is the conclusion.
You will find that we go back to this figure-- by the way,
changed [INAUDIBLE] to SDN controller.
I believe a lot of SDN systems will
have architecture like this.
And it will suffer from the same problem
that the TE controller suffers from.
Basically, with SDN with centralized control,
we want to achieve a lot of and keep
a lot of network properties, but a lot of network faults
prevent us from achieving that, and FFC is just
to solve a sub-problem of this whole domain.
And by presenting this, I hope I can arouse more discussion
and research on this topic.
Thank you.
[APPLAUSE]
[INAUDIBLE]
So do I understand correctly that you use FC [INAUDIBLE]?
You want the data itself to be forward.
I think that's independent.
So using FFC, you're guaranteed that there's no congestion.
Yeah.
So at the end, you mentioned that you can do it with other n
constraints independent of k?
Independent of k, yeah.
Well, this should not work for large k, right?
It should work.
So we can discuss offline.
Actually, I have a technical report.
Yeah.
Thank you.
[APPLAUSE]