CS244 ’13: Rising from the depths – Observing and implementing improvements in online video bitrate selection


Stephen Young (syoung0@stanford.edu)
Alex Trytko (atrytko@stanford.edu)
CS244 – Winter 2013
Stanford University

Introduction

With the rising popularity of services such as YouTube, Hulu, Netflix, and Vudu, video traffic comprises an increasingly large proportion of Internet traffic.  A recent report claimed that Netflix accounted for 33% of downstream traffic in North America, and that audio/video services in aggregate accounted for 65%.  As user demand and available video resolutions continue to grow, the share of aggregate video traffic will only rise.  Hence, it is important for video services to adopt practices that ensure enough throughput for good user experience while maintaining fairness to other traffic in the network.

In Confused, Timid, and Unstable: Picking a Video Streaming Rate is Hard, the authors studied the performance of various video streaming services (Netflix, Hulu, and Vudu) in the presence of a long-lived competing flow [1].  They found that, in all three services, the introduction of the competing flow caused video streaming rates to drop far below the video flow’s fair share of the bottleneck link.  For example, with a bottleneck rate of 5 Mb/s, the video client should be able to stream at a bitrate approximately half of that, or 2.5 Mb/s.  Instead, the bitrate falls quickly and dramatically to the lowest possible setting once the competing flow is introduced.

Fig. 1: This graph from the original paper illustrates the downward spiral effect in the Netflix video streaming client

The authors refer to this phenomenon as the “downward spiral effect”, which manifests as follows: when the competing flow starts, the video client perceives a drop in available bandwidth and consequently reduces the video bitrate.  The lower bitrate causes the client to underestimate available bandwidth even further, thereby reducing the video bitrate again and forming a vicious cycle. In the worst case, the client ends up streaming at the minimum possible bitrate – far below its fair share of the bottleneck link.  The authors identify TCP’s congestion control mechanism as the root cause of the downward spiral effect.  For brevity, we do not repeat that discussion here – please refer to sections 5.1-5.4 of the original paper.  Finally, they offer and evaluate several adjustments to the bitrate selection algorithm to reduce the severity of the downward spiral effect.

Although this paper is relatively recent (published 2012/11), Netflix was quite efficient in eliminating the downward spiral effect once it was brought to their attention.  Hence, we knew from the outset that reproducing the paper’s original result using the current production version of the Netflix client was infeasible.  Consequently, the objectives of this project are (1) to observe the behavior of the current Netflix client in the presence of a competing flow, (2) to reproduce the downward spiral effect using our own custom client that emulates the former Netflix client’s bitrate selection algorithm, and (3) to implement and evaluate each of the authors’ proposed solutions.  We feel that these objectives coincide with the main findings of the original paper and help to give some understanding of how the suggested improvements could have helped the client exhibit more favorable behavior.

When running the experiment against the current Netflix client, we found that the downward spiral effect is no longer present.  Instead, the client is able to stream at a level consistent with its fair share of the bottleneck link.  Against our emulated version of the former Netflix client, we were able to reproduce the downward spiral effect, albeit to a slightly less severe extent.  Of the four potential solutions that we implemented, three proved successful in mitigating the downward spiral effect, and two were able to eliminate it completely in our simulations.

Current Netflix client behavior

Since the publication of the original paper (and in part because of it), Netflix has directly addressed the issues raised therein by altering its client’s video bitrate selection algorithm.  To evaluate how successful the current client is in avoiding the downward spiral effect, we implemented and ran the original experiment against the Netflix client currently in production.  The experiment consisted of setting a bottleneck bandwidth rate of 5 Mb/s and streaming a video using the Netflix client, then introducing a long-lived competing flow from the same server.  We then dissected the packet trace to observe how video throughput [2] and video bitrate [3] adapt to the presence of the competing flow.

  Fig. 2: Current Netflix client, 5Mb/s bottleneck.  We see no downward spiral at all.

The Netflix client clearly no longer exhibits the downward spiral effect in the presence of a competing flow.  The video rate remains constant at 3000 Kb/s, even though video throughput is substantially below the competing flow’s throughput.  Note that the client is able to maintain a video bitrate of 3000 Kb/s even though the video throughput stabilizes around 2000 Kb/s.  This is due to the fact that video chunks are transmitted in compressed form, which enables the client to stream a video bitrate that is higher than the available network bandwidth.  We observed that the Netflix client’s playback buffer (of capacity 240 seconds) was full prior to the start of the competing flow and remained full thereafter.  Because the buffer does not begin to deplete, there is no need to downgrade the video bitrate.  This is a stark departure from Netflix’s former bitrate selection algorithm, which appeared to immediately downgrade video bitrate in response to a reduction in video throughput regardless of the current buffer occupancy.

Since the Netflix client seemed capable of sharing a 5Mb/s bottleneck link quite comfortably, we re-ran the experiment with the bottleneck rate set to 3Mb/s.

Fig. 3: Current Netflix client, 3Mb/s bottleneck.  Video bitrate decreases slightly in response to the competing flow, but nothing close to a downward spiral.

Prior to the introduction of the competing flow, video throughput and video bitrate both stabilize around 3000 Kb/s (note that because the incoming stream is compressed, the buffer is actually filling during this period).  Once we introduce the competing flow, video throughput drops to its fair share of 1500 Kb/s.  Since there is not enough available bandwidth in the network to maintain a 3000Kb/s requested bitrate (even accounting for compression), the client decreases the video bitrate, but only as far as necessary, often to around 1750Kb/s or 2350Kb/s – a perfectly respectable rate given a fair bandwidth share of 1500 Kb/s.  Thus, even when pressed for bandwidth, the Netflix client does not exhibit the downward spiral effect.  In summary, Netflix seems to have succeeded in adjusting its client’s bitrate selection algorithm to improve user experience while remaining fair to other flows in the network.

Reproducing the downward spiral effect against an emulated Netflix client

Since the downward spiral effect could not be reproduced in the current Netflix client, we implemented a custom client that emulates the behavior of the former Netflix client.  We also created our own server to serve the video chunks requested by the emulator.  This setup allows us to recreate conditions similar to those under which the original experiment was run and thereby observe the downward spiral effect in action.

The emulator requests video chunks from the server at varying bitrates and frequencies, depending on the state of its playback buffer and the bottleneck link.  While the playback buffer (which has a capacity of 240 seconds, like the actual Netflix client) is not full, the client requests video chunks at the highest bitrate that is below the client’s current estimate of available bandwidth.  This estimate consists of a moving average of download rates for the 10 most recent chunks, where the rate is simply the size of the chunk divided by the time it took to download.  Once the playback buffer is full, the client stops requesting chunks for 4 seconds, allowing 4 seconds of video to drain from the buffer.

A key aspect of the former Netflix client that we were careful to capture in our emulator is the existence of a “conservatism” factor that dictates how far below the current bandwidth estimate the client should request its video bitrate.  The higher the conservatism factor, the lower bitrate the client requests.  For example, with a current bandwidth estimate of 2000 Kb/s and 0.5 conservatism, the client requests the highest bitrate below 1000 Kb/s.  With 0.25 conservatism, it requests the highest bitrate below 1500 Kb/s.  We use a default value of 0.4 conservatism, which reflects the empirical estimate derived by the authors of the original paper for the then-version of the Netflix client.

Our emulator deviates from the actual Netflix client in one important way: it requests and receives video chunks in uncompressed form.  This is for several reasons: first, we know how (and to what extent) Netflix compresses video streams now, but not at the time the paper was written.  Second, the original paper did not mention compression at all in its analysis of the downward spiral effect.  Finally, attempting to account for compression would add a lot of complexity to our analysis, and based on the previous two points, there is little reason to believe that ignoring compression would sacrifice realism or relevance in any way.  Consequently, the size of each video chunk is always precisely equal to the video bitrate times the duration of the clip (i.e. four seconds).

While the original paper used 5Mb/s as the bottleneck rate for most of its analysis, here we use 7Mb/s to account for the fact that the maximum video bitrate offered by Netflix has since increased from 1750 Kb/s to 3000 Kb/s.  This way, a fair share of the bottleneck link (3500 Kb/s) should still allow the client to stream comfortably at the maximum bitrate.

Figure 4: Emulated Netflix client, 7Mb/s bottleneck and 0.4 conservatism.  Note that video bitrate stabilizes at 1050 Kb/s, even though a fair share of the bottleneck link is 3500 Kb/s.  This is clear evidence of a downward spiral.

The emulator successfully reproduces the downward spiral effect, as demonstrated in the above plot.  While the effect is not as pronounced as that in the original paper (i.e., video bitrate does not spiral down to the minimum of 235 Kb/s), the general idea is still present [4].  Once the competing flow is introduced, video throughput and video bitrate drop well below the fair bandwidth share.  Note that the playback buffer remains full throughout the duration of the competing flow, indicating that the client could have easily afforded to be more aggressive in its selection of video bitrate.  We explore this idea more concretely in the following section.

Fixing the downward spiral effect

The original paper proposed four solutions to the downward spiral effect, three of which they evaluated empirically using their own client emulator.  In this section, we conduct independent evaluations of all four solutions and compare our findings with those of the original paper.

Idea 1: Be less conservative in selecting video bitrates

As mentioned earlier, our emulator uses 0.4 conservatism when selecting which video bitrate to use.  Decreasing the conservatism factor could mitigate the downward spiral effect for two reasons.  First, note that the conservatism factor is proportional to the distance between the video throughput curve and the video bitrate curve.  Decreasing conservatism will reduce this distance, implying that bitrates will improve even if video throughput remains the same.  Second, higher bitrates means larger video chunks, so TCP cwnd has more time to ramp up before the file transfer is complete, thereby increasing the video throughput perceived by the client [5].

To test whether this idea works in practice, we reconducted the experiment against our emulator with conservatism factors of 0.0 and 0.2.  The resulting plots are displayed below, alongside the original fig. 4 for easy comparison.

Fig. 5: Emulated Netflix client, 7 Mb/s bottleneck, conservatism factors of 0.4, 0.2, and 0.0

Decreasing conservatism has exactly the effect that we predicted.  With 0.2 conservatism, we still observe a slight decline in video bitrate, but neither as steep nor as deep as for 0.4 conservatism.  With 0.0 conservatism, the client exhibits no decrease in video bitrate at all, and the two flows share the bottleneck link equally.  Therefore, using little or no conservatism seems to be very effective in eliminating the downward spiral effect.

Idea 2: Use better filtering for bandwidth estimates

The client emulator uses a moving average filter over the last 10 throughput measurements to obtain an estimate of available bandwidth.  This filtering method is not particularly robust against outliers – a single extreme throughput measurement could significantly affect the bandwidth estimate, and consequently the video bitrate.  Instead, the authors propose using an 80th-percentile filter, which returns the 80th percentile of the last 10 throughput measurements as the bandwidth estimate.  The results of our implementation of the 80th percentile (80p) filter are shown below.

Fig. 6: Emulated Netflix client with 7 Mb/s bottleneck, conservatism factors of 0.4 (top) and 0.2 (bottom), and 80p filtering

With the default conservatism factor of 0.4, 80p filtering noticeably reduces the severity of the downward spiral.  With a conservatism of 0.2, 80p filtering eliminates it entirely, resulting in both flows sharing the bottleneck link equally and video bitrate constant at 3000 Kb/s.  Therefore, 80p filtering seems to be effective on its own, and very effective when combined with lower conservatism.

Idea 3: Increase the video chunk size

Because the downward spiral effect is driven by chunk sizes that are too small, the original paper suggested requesting 5 chunks at a time – effectively increasing chunk size by a factor of 5.  This would ostensibly allow more time for the TCP cwnd to ramp up, thereby increasing the client’s perception of video throughput.  We implemented this idea and reran the experiment using the default conservatism factor of 0.4.  We decreased the size of the moving average window over which bandwidth estimates are derived from 10 to 2 to account for the fact that the intervals between throughput measurements are now 5 times longer.  The resulting plot is shown below.  Video throughput improves slightly, but overall there was no substantive change in the video bitrate curve.

Fig. 7: Emulated Netflix client with 7 Mb/s bottleneck, 0.4 conservatism, and chunk size of 20 seconds (instead of 4)

Idea 4: Aim to keep the buffer nonempty instead of full

The final idea proffered by the original paper was more of a conceptual re-approach to the problem of bitrate selection rather than an explicit algorithmic change.  The authors noted that the objective of the client should not be to keep the playback buffer full, but to keep it non-empty.  As long as the occupancy of the playback buffer is above a ‘comfortable’ threshold, the client can be a little more aggressive and set its video bitrate slightly higher than it normally would.  If the bitrate really is higher than the network can support, the playback buffer will eventually drain below the comfortable threshold and the client can return to its normal, non-aggressive bitrate selection algorithm.  Our implementation of this “non-empty” idea is as follows: if the playback buffer occupancy is above the comfortable threshold, the client requests new chunks at a bitrate one tier higher than it otherwise would have.  We re-ran the experiment with a comfortable threshold of 40 seconds, retaining the default conservatism factor of 0.4.

Fig. 8: Emulated Netflix client with 7 Mb/s bottleneck, 0.4 conservatism, and nonempty algorithm extension

There is noticeable improvement in both video bitrate and video throughput, although the fact that the buffer remains full indicates that the algorithm could have been even more aggressive than it was.  A pure implementation of the non-empty idea should show the buffer occupancy decreasing until it hits the comfortable threshold, then wavering around that threshold thereafter.  However, because this idea was almost an afterthought in the original paper, we leave this result as a proof of concept without delving into it further.

Implementation challenges

The overarching implementation challenge we faced throughout this project was how to obtain accurate throughput estimations.  Part of the reason for the difficulty of this task is that it needed to be implemented in multiple places.

  • We had to be able to estimate throughput of the video flow in real time, from the perspective of the client emulator.
  • We had to be able to estimate throughput of both the video flow and the competing flow in retrospect, from the perspective of the script that parses a trace file and generates a plot displaying the flows’ throughputs (and video bitrates) over time.

The first of these was simple enough.  Upon receipt of each video chunk, the client emulator simply divided the chunk size by the transfer time to obtain a point estimate for throughput of the video flow.

Estimating throughput from a packet trace, however, proved much hairier.  First, the structure of HTTP response flows is not conducive to intuitive estimations of transfer time.  Second, the competing flow results in an abundance of TCP retransmission packets, which are indistinguishable from valid TCP packets.  Thus, it proved infeasible to estimate throughput based on incoming traffic.  Instead, we use outgoing traffic – TCP acks, to be precise – to estimate how much data was successfully received by the client for each flow during a particular time period.  This approach results in slightly noisy estimates because acks aren’t always sent immediately, but overall it yields estimates that are accurate enough for our purposes.

Choice of platform

This project consists of two distinct components: reproducing the original paper’s experiment against the actual Netflix client, and against our own custom client that emulates the behavior of the former Netflix client.  Each component necessitated a very different approach from a platform perspective.

Because there is no easy way to automate a video stream against the actual Netflix client, a lot of the work had to be done manually.  Hence, for the first component of this project there is no real “platform” to speak of – we simply used Wireshark to capture a trace while manually streaming a Netflix video through a NIC throttled by a software rate-limiter called ipfw, then ran a script to extract the throughput and bitrate trendlines from the trace.  Notice that the bulk of the effort expended in reproducing these plots would be capturing the traces in the first place – given an existing pair of traces (which we provide), reproducing figures 2 and 3 is quite automatable.  Thorough instructions for capturing new traces against the actual Netflix client from scratch are provided in our README file.

For the second component of this project, we chose to use a simple client/server setup on a single EC2 instance instead of a virtual topology in Mininet (or some other network virtualization software).  Our primary rationale was that our desired topology – a client, a server, and a rate-limited link between them – is incredibly minimal.  Running both the client and the server on the same EC2 instance and using ipfw to set the bottleneck bandwidth provides an environment that is both controlled and isolated from other network activity.  Essentially, this setup provides the same benefits as a virtual topology without the complexity and implementation difficulty.

Acknowledgements

We would like to thank Te-Yuan Huang, the primary author of the original paper, and Aakanksha Chowdhery, our TA, for their support and guidance along the way.  In addition to very valuable general advice, Te-Yuan also provided a couple small scripts that we used in our implementation.

Result reproduction

  1. Follow the steps at http://www.stanford.edu/class/cs244/2013/ec2.html to create a new instance with the CS244-Win13-Mininet AMI (ami-7eab204e).
    • Important: be sure to modify the security group’s settings to allow requests to port 80 (the port on which our server runs).  Follow the instructions in the above link under “Modify Security Group Settings”, but use 80 instead of 8000.
    • We recommend also modifying the security group settings to allow requests to port 8000 in order to use SimpleHTTPServer for convenient viewing of plots.  Do not start SimpleHTTPServer on port 80, because this is the port used by our server.  To start SimpleHTTPServer on port 8000, run: sudo python -m SimpleHTTPServer 8000
    • We recommend using a c1.medium instance.
  2. Log into your new instance.
  3. git clone https://bitbucket.org/sjyoung12/cs244_pa3.git
    • This is a public repo, so you should not be required to authenticate.
  4. Follow the instructions in the README.

Footnotes

[1] In this project, we focus exclusively on Netflix both because of time constraints and because it was the most comprehensively studied of the three services in the original paper and seemed to form the basis of most of the analysis.

[2] As in the original paper, we use video throughput to refer to the network throughput of the video flow as perceived by the client.  This is estimated as the size of a video chunk divided by the time it took to download, averaged over the 10 most recent chunks.  The client uses video throughput to estimate available bandwidth (i.e., the two are related but not equivalent).

[3] Video bitrate refers to the playback rate chosen by the video client.  It is synonymous with video playback rate.  At the time of publication, Netflix offers video bitrates of 235, 375, 560, 750, 1050, 1750, 2350, and 3000 Kb/s.

[4] The original authors’ emulated client also failed to reproduce the worst-case downward spiral effect.

[5] Again, please refer to the original paper (5.1-5.4) for a complete discussion of the role of TCP congestion control in the downward spiral effect.

Advertisements

2 responses to “CS244 ’13: Rising from the depths – Observing and implementing improvements in online video bitrate selection

  1. We had some initial trouble configuring everything perfectly on our EC2 instance (the necessary instructions were all there, we just missed a step when we were going through them), but the experiment ran just fine once we resolved all of our instance configuration issues. We could tell this group was thorough with their process. I especially liked this group’s idea of making their original PCAP files available for analysis—it’s a major time-saver. Of course, they also include instructions for executing packet captures manually, if desired.

    Overall, it took some care to setup the EC2 instance correctly, but once we did, the experiment ran to completion and accurately reproduced the results in this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s