Hello everyone, I'm Francis from Microsoft
Research.
My research has focused on practical machine
learning algorithms for networked systems.
It's my pleasure today to talk about Puffer, a
video streaming platform we built to run a
randomized experiment on real users
and a learning-based adaptive bit rate algorithm
that works on the wild Internet.
This work was completed back at Stanford, advised
by my former PhD advisors Keith Weinstein and
Phil Levis.
Now let's get started.
The problem we're tackling here is adaptive bit
rate streaming, or ABR,
which is a critical algorithm used to carry a
large portion of the video traffic on today's
Internet.
At a high level, ABR aims to improve the user's
quality of experience, or QoE,
that basically consists of two primary goals,
higher video quality and fewer rebuffering events.
Although it seems to have been well studied in
the past,
ABR still remains a challenge because its two
primary goals naturally conflict with each other.
Let me show you how ABR works.
An ABR server divides the video into chunks.
Each chunk is usually 2 to 6 seconds.
Then each of those chunks is pre-encoded into a
couple of compressed versions at different sizes
and video qualities.
The objective of ABR is to react to the varying
network conditions over time
and decide which version of each chunk to send,
so as to optimize the total QoE of the client.
This problem is non-trivial because, let's say, ABR
believes it's okay to send 1080p all the time,
which gives the highest video quality.
But what if the network capacity suddenly drops
to a level that's unable to deliver 1080p anymore?
From that moment on, the playback buffer in a
client's player will be drained slowly,
eventually resulting in video freezes.
This talk will be in three parts.
First, I'll describe Puffer, a live streaming
platform for video streaming research.
Then I'll show a surprising finding from a
randomized experiment we performed on Puffer.
That is, the confidence intervals on the
performance of ABR algorithms are much bigger
than we realized.
Lastly, I'll introduce Fugu, a machine-learning-based
ABR algorithm that was learned in situ,
meaning in place on the actual deployment
environment Puffer.
Okay, let's move on to Puffer.
To study video streaming and test ABR schemes in
real life, ideally on real users,
we built our own video streaming platform called
Puffer.
It's a live TV streaming website, open to public
in late 2018,
allowing users to watch six TV channels for free.
Our goal was to create a realistic testbed and a
learning environment for the community
to investigate video streaming algorithms.
We operate Puffer also as a randomized experiment
of ABR schemes.
So each time you visit our website, puffer.stanford.edu,
you'll be randomly assigned to one of the ABR
schemes being tested,
including those in a prior work and our own
algorithm that I'm going to introduce later.
But you won't be aware of this assignment.
While you are watching TV on Puffer, our server
will record which ABR algorithm is used,
along with some other client telemetry on video
quality and a playback buffer for analysis
purposes.
To recruit users, we purchased ads on Google and
Reddit for keywords like "live TV."
The other users we attracted came from the press
articles covering Puffer.
For example, New York Times recommended Puffer to
those who need free TV to watch at home during
the pandemic.
As of today, we've had more than 130,000 real
users across the US.
Puffer's web page may look simple, but you can
think of it as a small YouTube TV built from
scratch.
It's actually a lot more challenging to support
130,000 users than building a research prototype.
This picture shows Puffer's architecture.
We receive TV signals with an antenna at Stanford,
decode the signals and encode video into multiple
versions,
and then serve them using different ABR
algorithms to our users.
We've also built a monitoring system to monitor
the system state and send an alert to my phone if
anything goes wrong.
We wrote more than 30,000 lines of code for Puffer
and have used it to stream 60 years of video to
130,000 real users.
Not only are our results in the paper reproducible,
all the user data collected on Puffer is being
automatically posted to the website every day
after anonymization.
You could select any data and view the algorithm
performance we plotted in figures,
but you could also download the data and do the
analysis using our scripts by yourself.
Additionally, we're opening Puffer to the
research community to train and test novel ABR
algorithms,
and more generally speaking, also congestion
control and bandwidth prediction algorithms.
And after building Puffer, we then run a long
randomized experiment on video streaming in real
life on real users.
It's worth noting that the existing ABR
algorithms did real experiments as well,
but those experiments often ran between a few
network nodes and lasted for only hours or days.
What we have found is measuring ABR performance
on a wild internet is much harder than we
realized before.
You may need two years of data per scheme to
reliably measure a difference like 20%.
I'll demonstrate the surprising finding using the
experimental results comparing five ABR
algorithms.
This figure shows the algorithm performance using
the data collected on a single day in January
2019.
Puffer streamed more than 17 days of video to
about 600 users watching TV on that day.
Since I'm going to present this type of figure
several times, let's take a closer look first.
On the y-axis, it shows the video quality
measured by a standard metric as seen. Higher is
better.
On the x-axis, it displays the re-buffering ratio,
but we have reversed the axis, so the better is
to the right.
Overall, the better QE is up and to the right.
For now, let's ignore the individual performance
of each scheme and focus on those 95% confidence
intervals around each point.
You see, even after streaming 17 days of video,
the confidence intervals are still huge and
overlapping with each other.
As a result, most schemes are still indistinguishable
from each other.
This tells us if you perform an experiment that
only streams 17 days of video, you can't really
measure any benefits reliably.
Any improvements you found could just be
statistical noise if you don't collect enough
data or consider the confidence intervals.
So, we left the experiment running for a week and
collected 42 days of video.
Now the confidence intervals became smaller, but
not actually enough.
For instance, let's look at the scheme MPC-HM.
Its mean style ratio is about 0.4%, but the
confidence interval ranges from 0.1% to 0.9%,
twice as large as the mean value.
So we continue the experiment.
After a month, about half a year of video were
streamed and now the confidence intervals became
much smaller.
However, we are still unable to distinguish some
schemes.
For example, MPC-HM and BBA have almost identical
performance.
But is that a reliable result?
After running the experiment for 8 months, we
ended up streaming more than 13 years of video to
about 55,000 user IPs.
And finally, let's zoom in on this figure.
We are now able to narrow the confidence
intervals down to 20% of the mean value.
But remember, this is only possible after
streaming at least 2 years of video per scheme.
The reason for such large uncertainty is because
the internet is way more noisy and heavy-tailed
than without.
Among the 600,000 streams, only 4% of them had
any stalls, meaning the other 96% never stalled.
Stall events are so rare in practice, which is
why you need a huge amount of data to measure
them.
Additionally, we have results in the paper to
show that the distributions of watch time and
throughput are also super-skilled.
In the final part, I'll describe how we leverage
machine learning to train an ABR algorithm in
situ, meaning in place on Puffer.
The first step we took was to understand the
system dynamics better.
We can plot how the playback buffer changes over
time.
For instance, it drains 1 second per second while
waiting for the next chunk.
And once the chunk is received and appended to
the buffer, its buffer size increases by the
chunk length.
You'll see the only uncertainty in ABR is the
transmission time of a video chunk.
That is simply how long it takes for a client to
receive a video chunk since the chunk leaves the
sender.
The algorithm we proposed is called Fugue.
At its core, it uses a neural network to predict
the transmission time of each chunk.
The transmission time predictor, TTP, takes as
input the sizes and transmission times of past
chunks, and also the size of the chunk to send.
I'd like to emphasize that we don't predict
throughput, because a throughput predictor wouldn't
consider the size of the chunk to send,
and would have ignored a well-known fact in
networking that the observed throughput actually
varies with the file size to send.
Another uncommon feature of the input is low-level
TCP statistics from the kernel, such as RTT and
congestion window size.
This is weakly crossing layers, with information
flowing from transport layer to application layer.
The output of TTP is unusual too.
Instead of a point estimate, it outputs a
probability distribution over transmission times,
and we found it to be useful when maximizing the
expected QoE.
In sum, TTP has several uncommon features in the
design, and our ablation study found each of
these features to be necessary to Fugue's
performance.
TTP's design enables it to be trained in situ,
meaning in place on real data from the deployment
environment buffer.
The training data are sampled and fed into TTP as
individual user streams.
Each user stream contains a chunk-by-chunk series,
including the size and actual transmission time
of each chunk, and the required TCP statistics on
the server.
We use standard supervised learning to train TTP
to minimize the difference between its
predictions and the actual transmission times of
chunks.
Note that learning in situ does not require any
network simulators or replay any recorded
throughput traces.
Because if an algorithm is learned in simulation
and evaluated in the real world, the gap between
simulation and reality may cause generalization
issues, which we'd like to avoid.
Once the only system uncertainty is approximated
by TTP, the remaining question is how to actually
select the version for each video chunk.
What Fugue does is to look five chunks ahead and
optimize the total QoE in a look-ahead horizon.
Roughly speaking, the QoE function includes
higher video quality, lower quality variation,
and less rebuffering time.
Given TTP, this optimization problem of maximizing
QoE can be solved with a well-known technique in
Markov decision process, called value iteration.
We don't need to look into the formula because it's
basically dynamic programming, which can be
computed in real time.
Its behavior is also interpretable because we
know exactly what's going on.
After the optimal plan is computed, Fugue only
takes the first step and then replans for the
next five chunks.
This is also a classical technique in control
theory, called model predictive control, which
proves to mitigate the accumulation of errors.
Putting everything together, including the Puffer
video server, the model-based controller, and TTP,
Fugue falls into a class of reinforcement
learning, or RL, algorithms called model-based RL.
We first deploy a version of Fugue on Puffer's
video server, and Fugue's model-based controller
will plan ahead and select a bit rate when it
receives necessary information from the video
server.
The optimal plan of chunk qualities is computed
in real time with dynamic programming, during
which TTP is queried to predict transmission
times repeatedly for the chunks of our interest.
After new data is collected and aggregated, we
retrain TTP offline using supervised learning,
and deploy the new version of Fugue on the next
day.
This paradigm I just described is model-based
reinforcement learning, but its core component is
really the TTP, which is learned in situ.
Once again, let's come back to this figure that
shows average video quality on the y-axis and
style reissue on the reversed x-axis. The better
QE is up and to the right.
These results are obtained by analyzing 13 years
of video data, sent in more than 600,000 video
streams from Puffer.
Here are four state-of-the-art ABR algorithms.
BBA is a simple buffer-based ABR algorithm
published at SIGCOMM 2014. It selects video bit
rate based only on users' playback buffer level.
MPC-HM and robust MPC-HM are two variants of an ABR
scheme from SIGCOMM 2015. It leverages the
classical model predictive model, same as in Fugue's
model-based controller.
However, it tries to predict the future
throughput using the harmonic mean of some past
throughput measurements.
The last ABR in this figure is PAN-SIEV from SIGCOMM
2017, which is also based on reinforcement
learning.
Different from learning in situ, PAN-SIEV
requires training in network simulators. Although
their paper reports near optimal performance in
simulation, unfortunately its performance did not
generalize from simulation to the real Internet.
For instance, although its re-buffering ratio is
lower than BBA and MPC-HM, its average video
quality is worse than them.
In this figure, Fugue is here. It achieves the
highest video quality and lowest style ratio,
except robust MPC has a lower style ratio than Fugue,
but that comes at a great cost of video quality.
This table contains the raw performance numbers
of the same experiment, where the first row is Fugue.
We can see Fugue's mean style ratio in the first
column is only 0.01% higher than the lowest
scheme.
And Fugue is the best on the other dimensions,
including the mean SM we saw in the last slide.
In the third column, we see Fugue's quality
variation is also the lowest, meaning that the
video delivered by Fugue is more smooth than the
other schemes.
The last column shows an interesting performance
metric, time on site, or session durations.
Recall that Puffer users are blinded to the
assignment of ABR algorithms.
Under this randomized setting, users whose
sessions were assigned to Fugue chose to remain
on the Puffer video player about 1-3 minutes
longer than those assigned to other schemes.
Let's now move on to their cold start performance,
that is, how well they perform in new sessions
which they hadn't streamed any video to.
We plot the average video quality of the first
chunk served in such new sessions on the y-axis,
and the startup delay on the reversed x-axis.
On a cold start to a new session, Firework argues
that since the ABR algorithm knows nothing about
the network conditions of the new session,
it needs some session clustering algorithm to
determine the initial chunk quality based on
other similar sessions.
Otherwise, ABR algorithms will have to choose the
first chunk blindly, which could be too
conservative or aggressive.
By contrast, Fugue provides an alternative option.
Recall that one of the input features of Fugue's
TTP is TCP statistics, such as RTT measurements,
which are actually available as soon as the
underlying HTTP/TLS/TCP connection is established.
And knowing this information turns out to allow Fugue
to begin safely at a higher first chunk quality
than the other schemes, while maintaining roughly
the same level of startup delay.
To conclude today's presentation, I introduce Puffer,
a video streaming platform that we built for the
research community to train and test novel
algorithms.
It has 130,000 real users now and has streamed
more than 60 years of video.
Using the data, we had a surprising finding that
the internet is way more noisy than expected.
You may need as much as two years of data per
scheme to reliably measure a 20% precision.
We outperformed existing ABR algorithms
consistently in the real world through the design
of Fugue.
And Fugue's core component is a neural network TTP
that predicts the transmission time of each chunk.
TTP is trained in situ, meaning on real data from
the deployment environment Puffer.
That's all for today and I'm happy to take
questions. Thank you.
Thank you.