Hi, my name is Bruce and today I will be
presenting our work on running experiments in
congested networks.
This is joint work with some awesome
collaborators from Netflix and from Stanford.
So when we do networking research, we want to
know whether or not a new algorithm will work
well in practice.
And in order to do this, we want to run A/B tests
or randomized experiments where we run this new
algorithm on live traffic
and see if it actually works better or not when
it encounters all the weird stuff that goes on in
the actual internet.
These are just a few of the many papers published
over the last decade that use A/B tests.
There are many more unpublished tests.
For instance, Netflix runs an A/B test for almost
every single change it makes to its production
network.
So what is an A/B test?
In an A/B test, we have some new treatment
algorithm and we want to compare this treatment
algorithm to some existing control algorithm.
In order to do this, we split up the traffic into
two groups randomly, a treatment group and a
control group.
We apply the new algorithm to the treatment group.
We run it for a while to collect some data, and
then we look at what happens.
In this case, the treatment algorithm would get
better performance than the control algorithm.
And so we would say that the new algorithm
improves performance.
This statement that an algorithm improves
performance is a generalization.
We're using the results of a small A/B test to
decide what would happen if we were to go and we
were to deploy this algorithm everywhere.
This is a fine generalization to make, but it
requires assumptions.
And one of the big assumptions is that the
outcome of one unit in the test doesn't depend on
the outcome of the other units in the test.
This assumption is called interference.
If we think about it for a while, it's clear that
interference must exist in congested networks.
We have treatment algorithms and control
algorithms, and they use the same networks.
And they use the same queues, and they use the
same links inside these networks.
We know from decades of research on, for instance,
congestion control fairness, that there are
things the treatment algorithm can do to impact
the control algorithm.
For instance, if the treatment algorithm uses
more bandwidth, there will be less bandwidth
available for the control algorithm.
And if the treatment algorithm does something
that decreases queue lengths, then the control
algorithm will also experience improved queuing
delay.
This is clearly interference, but we still use A/B
tests to evaluate algorithms in congested
networks.
So this interference raises two questions.
One, does this interference matter?
Does it matter enough that it would affect the
decisions we make and the algorithms we deploy?
And two, if it does matter, what can we do about
it?
Our goal in this paper is to answer both of these
questions.
And we start with describing an A/B test we ran
that shows that interference can really make the
result of A/B tests very misleading.
The treatment for this experiment was bitrate capping.
In response to COVID-19, Netflix and most other
large video services worked with governments to
reduce load on the Internet and make the Internet
more stable when people started working from home.
Video is typically encoded at a number of
different quality levels, and with bitrate capping,
we took the highest qualities, the ones that also
tend to be the largest, and just stopped serving
them.
So let's imagine what would happen if we ran an A/B
test to measure the effects of bitrate capping.
And let's imagine that all of the traffic is
running on the same network over the same congested
link.
With bitrate capping, we would send less data
into the network, and because this link is
congested, maybe with bitrate capping the link
would become uncongested.
So there would be two effects of bitrate capping
here.
The first effect is that we're sending less data
into the network, and the second effect is that
this causes less congestion.
Now let's imagine what would happen if we ran an
A/B test.
We would cap some fraction of the traffic to this
link, and let's imagine that the control traffic
wouldn't be affected.
So if this were the case, we would correctly see
that the capped traffic uses less bandwidth in
our A/B test, because here the capped traffic is
using half of the traffic of the control traffic.
But what we would not see in an A/B test is this
effect on congestion, because both the capped and
the control traffic are using the same link,
which is not congested.
Another possibility is that the control traffic
would notice that there's now a little bit of
free space on this link, and it would start
sending faster, it would start sending higher
quality video, and it would fill up the link and
recongest it.
If this were to happen, we would again see that
the capped traffic uses less bandwidth than the
control traffic, but now it looks like it uses
way less bandwidth.
It uses like a third of the bandwidth instead of
half of the bandwidth.
And again, we would miss this impact on
congestion, because here both the capped and the
uncapped traffic are using the same link, which
is congested.
So in both of these A/B tests, we haven't really
figured out what happens when we do bit rate capping.
We've like totally missed the impact of
congestion, and this is because of the
interference between the treatment and control.
But we do want to measure what happens when we
cap traffic, so now let's introduce a bit of
formalism to help with this.
So let's imagine we're back in this setting where
the control traffic is going to use up whatever
free bandwidth is available from the capped
traffic.
This is what the bandwidth usage would look like.
On the x-axis, we have the fraction of traffic
which is capped.
On the y-axis, we have the bandwidth used. This
pink line is the bandwidth used by the control
traffic, and this purple line is the bandwidth
used by the capped traffic.
What we want to measure is the effect of capping,
which is the difference between when 100% of
traffic is capped and when 100% of traffic is
using the control.
This is called the total treatment effect in
causal inference, and it's the effect of
deploying bit rate capping.
When we run an A/B test, we don't measure this.
What we measure is one point on this graph.
We pick some point on the x-axis, and we compare
the treatment and control at that point.
This is not necessarily the same thing as the
total treatment effect, and this is why A/B test
results are biased when there's interference.
But if we do want to measure the total treatment
effect, we need multiple points on this graph.
If we were somehow able to run two simultaneous A/B
tests, for instance, an A/B test with 5% traffic
capped and 95% of traffic capped,
then we could compare these two points, compare
these two experiments, and use them to estimate
total treatment effects.
The problem is that typically this is hard.
Typically, we don't have isolation between A/B
tests, and so we can't run two A/B tests at the
same time without impacting each other.
However, we got very lucky, and we found a very
special location at Netflix which allowed us to
do this.
This location had a pair of very reliably congested
peering links, where every night during the peak
hours, these links would become congested.
The traffic between these two links was also very
well balanced, and we were able to run separate
experiments on each of these links.
What we did, we ran a 95% A/B test on one link, a
5% A/B test on the other link, and we compared
the two results.
We found that bit rate capping improves
throughput, and that A/B tests did not measure
this.
In each A/B test, bit rate capping appeared to
decrease throughput by about 5%.
But when we compared the two links, when we
calculated the total treatment effect, we saw
that bit rate capping actually improved
throughput overall.
We saw similar behavior for RTT. Capping
increased RTTs in both A/B tests, but when we
calculated the total treatment effect, we saw
that capping actually improved RTTs overall.
This experiment shows that A/B tests can be
biased when running congested networks.
And this should be really concerning. We make
really important decisions based on the results
of A/B tests all of the time.
We make decisions about whether or not an
algorithm works well, and whether or not it's
worthwhile to invest time and money in deploying
the algorithm,
and maybe invest time and money in doing follow-up
work on that algorithm.
If we had made a choice based on this bit rate capping
A/B test we just described, we might have been
totally misled by this test and made poor
decisions.
But another thing we just saw is that we can run
experiments which remove this bias.
In our paper, we talk more about this sort of
experiment.
One type of experiment we can run is an event
study.
In an event study, we switch from running 100% of
control to 100% of treatment, and compare before
and after.
We can also run switchback experiments, where we
switch back and forth between treatment and
control, and compare the treatment periods to the
control periods.
Both of these let us get better estimates of
total treatment effect, and we talk more about
them in the paper,
and we also talk about how to integrate them into
existing deployment workflows.
Any A/B test which we run in a congested network
has the possibility of being biased,
and we would encourage you to run more
experiments to see if this bias matters for your
A/B tests.
We would also encourage new proposals for new
algorithms to include the results of these
experiments,
and measure things like the total treatment
effect so we get a better sense of how the
algorithm will work when it is deployed.
We also think this paper really highlights the
need for better experiment methodology for
networks.
We've proposed a few new experiments, but we
haven't used that much information about networks
and how they work in order to design these
experiments.
We wanted to call this area to the attention of
the community in the hopes that we could improve
this methodology together.
In conclusion, there's a lot more work we can do
with designing experiments for networks,
and I'm really excited to see the sort of
experiments we can run, the sort of algorithms we
can build by using these experiments.
Thank you.