A study of *A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP*

Helen Hastings and Sloane Sturzenegger {hhas77, sloanes} @stanford.edu

**The Thrill of Victory and the Agony of Defeat**

Over the last few weeks, we attempted to integrate an advanced video streaming scheduler into VLC, a widely used open source video client. The scheduling algorithm we investigated was introduced at SIGCOMM 2015 in the paper *A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP*. The algorithm advertises a 10-15% improvement over the existing state of the art schedulers in terms of quality of user experience. With streaming video becoming more and more prevalent in devices with low-quality bandwidth, picking the correct video encoding is essential to balance video quality and rebuffer time.

Recreating the original authors’ work was incredibly challenging and we were not able to accomplish it. The paper is predicated on being able to solve a complex nonlinear discrete optimization problem. Over the last few weeks, we attempted to leverage several open source optimizers but were unable to efficiently locate solutions to the formula presented in the paper. We present here the challenges faced and an argument as to why we believe that the algorithm offered is unlikely to be used broadly.

**The Promise of FastMPC**

Yin et. al begin their paper by formulating a precise “quality-of-experience” (QoE) function that measures the strength of a streaming session. High quality video, infrequent rebuffering pauses, and a low startup delay time result in a very high QoE value. The paper uses CPLEX, an IBM closed-source software package that can optimize both the bitrate choices and initial startup time to maximize the QoE value. In order to pick bitrate choices that will produce global optimum QoE, the optimizer requires full knowledge of future download throughput.

Solving such an optimization requires a tremendous amount of computational power. In fact, the authors argue (and we confirmed!) that it takes much longer to solve the optimization than to actually download the biggest chunk over low-quality internet and allow the stream to re-buffer. Instead, the authors provide a system where for each video, they pre-compute a table of values. The tables are binned such that given any tuple of (PredictedThroughput, CurrentBufferSize, PreviousBitratesSelected, the streaming scheduler can select a NextBitrate for the video chunk about to be downloaded.

To prove the value of this algorithm, called FastMPC, the authors implemented it in dash.js, a reference client implementation for the playback of MPEG DASH content and tested the performance under different network simulations. They evaluated their implementation of *FastMPC* by comparing its performance to alternative, state of the art bitrate adaption algorithms and the naive, default scheduler in dash.js*.*

**A Bold Goal for CS 244**

Our goal was to recreate Figure 8 (below), which demonstrates the success of FastMPC (in blue) against the default dash.js (in black) and various other scheduler algorithms. We hoped to show that FastMPC would continue to perform well under our measurements and compare it to the default streaming algorithm from another popular video player. This graph shows that FastMPC exceeds the QoE offered by other systems under broadband throughput traces from the FCC, mobile traces from HSPDA in Sweden, and a random synthetic trace drawn from a Gaussian distribution.

**A Strong Start**

We chose to use open source software to complete this task and settled on the VLC media player, a cross-platform program written C++. We extended VLC to output measurements for each downloaded chunk and wrote scripts to extract this data into a QoE score for each streaming session. The VLC source code which chooses the representation for the next chunk to download is fairly isolated, and introducing a new streaming algorithm can be accomplished by implementing a new adaptation logic class which inherits from a default class and passing a different runtime flag. We identified where the necessary data for the QoE optimization was represented in the source code to analyze QoE for the default VLC logic and to prepare to write FastMPC logic.

We found all of the raw data used by the Yin and his team. We use the same video as the one tested in the original paper and ran a webserver to serve all of the chunks that could be requested by VLC. We also found the broadband and mobile trace datasets and converted the raw CSV files into the file format expected by Mahi Mahi. Using the command mm-trace, we could run VLC as if it were under any of the network conditions we needed. Additionally, we created a set of synthetic traces by drawing from a Gaussian distribution, as described by the authors.

**The Valley of Optimization Despair**

Unfortunately, the next step of reproducing Yin et al.’s work, calculating the necessary optimization of the QoE expression, QOE_OPT, was significantly harder than we expected. At first, we attempted to use a package called PyOpt, which contains Python interfaces to standard optimization algorithms. Despite our best efforts, none of those optimizers can maximize even a small subset of the QoE, let alone the full expression, which needs to select 130 values for the 65-chunk video. Even in our attempts to run the easiest version of the optimization problem, throughout prediction, the program would not terminate. We could not find any examples of PyOpt which used discrete variables, or needed to choose nearly as many variables as QOE_OPT, so we are doubtful that solving QOE_OPT was in the scope of PyOpt.

Pursuing a more-conventional open source optimizer, GLPK (the Gnu Linear Programming Kit), was also incredibly challenging — its low ratings on performance, and our inability to represent our problem in its obtuse domain-specific language led us to abandon it as a solution. GLPK may actually be unable to optimize the QoE expression because the program is not designed to allow variables to be restricted to one of a discrete set and only allows linear operations of the variables.

At the last moment, we realized that Stanford has IBM’s proprietary optimizer CPLEX installed, which is the same program the original authors used as the optimizer. CPLEX, we believe, can perform a mixed integer nonlinear programming optimization (MINLP), but learning its APIs or custom DSL was extremely complicated. However, from our research on CPLEX, MINLP is one of the hardest problems in optimization, and we could not find any MINLP examples of CPLEX.

Essentially, *FastMPC* relies on a very large set of pre-computed discrete optimization problems which seem to be too complex for an open source optimizer, and take a very large time for industry-standard optimizers to solve. Predicating the entire success of their system on having access to a product like CPLEX is an unfortunate design system and, as we learned, prevents others from adopting it.

**Establishing Baseline Results**

Our goal was to verify the value of FastMPC when applied to another video player, as Yin et al’s data depended on the underlying implementation of dash.js. Unfortunately, we were only able to graph the baseline QoE values extracted from VLC without any of our attempted additions. The only data we were able to produce was the QoE of the baseline VLC bitrate adaptation algorithm run on all the traces used in the paper. The default adaptation logic in VLC is rate-based, and it is good that we are able to provide another comparison of a rate-based adaptation algorithm. Figure 8 displays the QoEs from each trace set normalized by dividing them by the ‘optimum’ run of the video on that trace: before streaming the video, the algorithm looked into the future to know all throughputs and choose the best bitrates. Because we never made a working optimizer, we could not normalize by the optimal QoE for each trace, and producing a graph with the cumulative distribution of QoEs normalized by some other value would be meaningless. Instead, we plotted the raw QoE values for each trace. Our data adds little value to our goal of evaluating FastMPC, but demonstrates the distribution of QoE from a different DASH video player with rate-based adaptation logic.

**Unanswered Questions**

As the project winded down and the likelihood we would be able to maximize the QoE for any throughput inputs dwindled, we investigated the FastMPC demo Javascript implementation hosted on Vyas Shekar’s homepage at CMU and cited in the paper. Our intent was to use the table of values generated by Yin et al. for their tests — since we used the same video encoded at the same bitrates, the tables we generated would have been identical. If we could have found that table, we would have not needed to calculate the optimization problem ourselves, removing the roadblock from our research.

For some reason, the demo running on the website does not perform the online version of FastMPC, meaning that it never downloads the large table of values and dynamically picks bitrate values based on an estimate of future throughput. The code that distinguishes between the “offline demo” (which calculates optimal values based on knowledge of future throughput) and “online demo” (which runs the FastMPC algorithm from the paper) has been commented out in the source Javascript of the player. The commented out code refers to a method setAbrAlgorithm that does not exist in the version of the dash.js client linked into the page. We are not sure why the authors’ demo page does not reflect the work presented in their paper, and it is unfortunate that the SIGCOMM paper points readers to a demo that does not demonstrate the heart of the paper’s contributions.

**Reproducing the Reproducers**

If you’d like to reproduce our graph of the baseline VLC QoE, please follow the instructions in https://github.com/sloanesturz/experiments.

**References**

DASH Industry Forum. *Dash.js Sample Videos*. http://dashif.org/reference/players/javascript/1.4.0/samples/

GLPK (GNU Linear Programming Kit). http://www.gnu.org/software/glpk/

CPLEX Optimizer. IBM. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

Müller, Christopher and Christian Timmerer.* A VLC Media Player Plugin enabling Dynamic Adaptive Streaming over HTTP*. ACMMM 2011. http://www-itec.uni-klu.ac.at/bib/files/p723-muller.pdf

PyOpt. http://www.pyopt.org/

*VideoLAN Documentation*. 3 December 2015. Web. https://wiki.videolan.org/Documentation:Documentation

Vyas Sekar. *A Control Theoretic Approach for Bitrate Adaptation over HTTP. *Web. https://users.ece.cmu.edu/~vsekar/mpcdash.html

Yin, Xiaoqi, Abhishek Jindal, Vyas Sekar, and Bruno Sinopoli. *A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP*. SIGCOMM 2015. https://users.ece.cmu.edu/~vsekar/papers/sigcomm15_mpcdash.pdf

Very commendable attempt at replicating the results of this paper. Unfortunately, setting up based on the github instructions proved to be very difficult, and I appreciated you working with me to at least get the executable going these past few nights. In the future, if a project is going to have this many dependencies, it would be worth creating your own AMI image so that others don’t have to run more commands to install/update before actually making the executable for vlc.

The baseline experiment ran for over 7 hours and was still not completed. Unfortunately, somewhere between the 8-9th hour, my computer lost connection to the EC2 Instance and I was unable to plot the results after logging back in.

Even if I was able to get results up before the deadline, based on how much trial and error this took, I’d have to give 2/5. Hopefully the course staff has better luck with reproduction than I did.