Assignment 2: Basic Simulations of a HTTP-based Adaptive Streaming (HAS) Player

 

By Vengatanathan Krishnamoorthi and Niklas Carlsson, August 2017

Before starting this assignment it is important that you carefully read the entire assignment and provide answers in the desired format (see deliverables).

Goals

Overview of the Assignment

For this assignment, imagine that you are working at a company that is developing new media streaming players for mobile clients. As part of your work you have been asked to determine the best possible rate adaption policy for a popular HTTP-based Adaptive Streaming (HAS) system. However, development cost of implementing and testing on a real system is very expensive (both in terms of money and time). You have therefore been asked to first implement a customized simulator that allow you to easily modify the default policies used by the player and quickly (faster than you could with real experiments) evaluate the expected performance of these policies. To your help you have also been given a trace file which shows the achieved download rate in a mobile device as the user moves through a city.

Goal: In this assignment you are expected to build a simple trace-driven simulator for a HAS system and evaluate two different ways of estimating the current network conditions. Based on these simulations you should make a recommendation of which of the two policies should be used in practice, as well as answer a number of questions. You may also chose to test and evaluate additional rate adaption policies than the one described here.

Bandwidth trace

This assignment requires you to work with a log file, available here, which contains information about the observed bandwidth during a mobile commuter's 3G session on his/her way to work. This trace was collected by Riiser et al. [1].

The file is in plain ASCII text, with each line providing information about a measurement point, and the number of bits received since the previous measurement point. The format of each line is as follows:

If you carefully observe columns 1 and 2 the difference in time stamps ranges from 1000-1100 ms. For simplicity, for the purpose of this assignment, please feel free to assume that these values are separated by 1 second.

HAS background

HTTP-based Adaptive Streaming (HAS) is the most popular method of delivering high quality streaming video. Today, HAS is used for almost all video streaming over the Internet, including by YouTube, Netflix, Apple HLS, Microsoft Smooth Streaming, Hulu, Vudu, .... Contrary to classical streaming, where the video quality remains the same throughout the video, a HAS player dynamically adapts the playback quality based on the current buffer and bandwidth conditions of the client. In order to support this, the HAS server hosts the same video encoded at multiple bitrates or qualities.

While there are many different HAS protocols (some chunk-based and other range-based), in the following we will describe a basic chunk-based protocol in which the file is split into many smaller chunks called fragments.

Figure 1
Figure 1: Visualizing multiple encodings at the server

Fragments and quality encodings: Figure 1 illustrates how the content might look at the server. The base video is first encoded at different bit-rates to create multiple copies, the only difference between copies is that each has a different encoding rate. The different versions of the video are now divided into smaller chunks/fragments. The playtime of each of these fragments is maintained as a constant throughout the video. Furthermore, each of these fragments can be identified by a unique URL. For example,

may be the URL used to fetch fragment 1 at 1300 kbps, while may be used to fetch the same fragment at 500 kbps.

For the purpose of this assignment you can consider a 2 minute long video file, that is available at the server in four different encodings: 250 kbps, 500 kbps, 850 kpbs and 1300 kbps. Let us number these qualities from zero to three, such that quality zero corresponds to the 250 kbps encoding and quality three to the 1300 kbps encoding. Also, assume that each fragment has a 4 second playback duration (the time it takes to play the fragment).

To simplify switching between qualities, the playback points of the fragment boundaries are aligned (in playtime), regardless of the encoding quality. For example, if the player plays fragment 2 at 250Kb/s, fragment 3 can be downloaded at any encoding rate (250, 500, 850 or 1300Kb/s) and the player can playback these fragments back-to-back without any skip in the content shown on the screen. Leveraging these properties and taking advantage of the chunking, it is possible to easily change the quality at which the video is played on a per-fragment basis without any visual artifacts.

Some measures and parameters: To understand how the player dynamically chooses the quality at which the next fragment would be downloaded, we next consider a few measures and parameters that the player keeps track of and that help determine the actions of the player. Of course, your simulator also must keep track of all these measures and parameters.

For the purpose of this assignment, the above parameters will be sufficient to simulate some simple policies used by an HAS player. However, it should be noted that commercial players typically keep track of a long list of additional parameters and event statistics that they use in their adaption algorithms and when making download decisions. This includes statistics regarding dropped frames, weighted rate estimations, past tradeoffs between buffer fullness and playback quality, the success of past quality selections, the reliability of the link conditions, etc. (Please see the work by Akhshabi et al. [2] for a comparison and discussion of different HAS players and the parameters they use.)

Player operation

We now move to the player's working.

Timing of requests: During normal operation, the player should try to maintain a buffer of at least minBuf (in seconds) and at most maxBuf (in seconds). First, the player begins playback only when there is at least minBuf seconds of data in the buffer. Second, the player keeps making new requests at the completion of the previous download as long as less than maxBuf of video (in seconds) is buffered. When more than maxBuf is buffered, the player stops downloading new fragments until the buffer occupancy is less than minBuf. At this time, downloading is resumed. (Note that under normal operation and conditions, this protocol results in the buffer occupancy oscillating between minBuf and maxBuf.)

Bandwidth estimation: After download of a fragment, the player calculates the average download rate for that fragment and updates its estimated current available bandwidth (i.e., download rate). For the case of this assignment, let us consider two ways of estimating the available bandwidth:

Rate adaptation: Using the estimated available bandwidth, the player can calculate the highest quality that it can choose without causing the buffer to go empty (i.e., for the buffer size to decrease to zero) before or by the download completion of the next fragment. The quality at which the next fragment is requested, is selected as the highest quality that satisfies the condition above, but also satisfies the additional restriction that the player is not allowed to switch up by more than one quality level when compared to the previous request. Furthermore, in case of a quality reduction, the player should not reduce its quality by more than two levels from the current quality level.

Example: At (the normalized) time t=0, when the client request the file, the player initiates download of the first fragment. For simplicity, you can assume that this fragment is downloaded at quality zero. At completion of this download the buffer will have 4 seconds of data. With minBuf=4, we can begin playback. Furthermore, the measured download rate is used to estimate the quality with which to download the next fragment. Note that this can either be quality zero or one (due to the above restrictions in the maximum steps with which the quality can be changed). For each download completion, update the estimated available bandwidth and check if the buffer occupancy is greater than maxBuf. If it is, suspend download of the next fragment until the buffer occupancy is down to minBuf again. If it is not, make the next request immediately, with the quality at which a new fragment is requested depending on the estimate bandwidth as per the above adaption policy.

Figure 2 shows a detailed example log of a player in action. Here, the request time, buffer occupancy, and request quality are all plotted in the same graph, with quality 0 representing the lowest encoding and 3 the highest encoding. One can observe that the player begins with the lowest quality and slowly ramps up to the highest. The variation in buffer occupancy shows how buffer occupancy triggers fresh requests.

Figure 1
Figure 1: Example player: Request timing and quality selection.

Building your Simulator

Building the simulator: For this assignment you are expected to write a trace-driven simulator (program) in C or Java, which reads the above trace file (and maybe take some input parameters; e.g., minBuf, maxBuf, etc.) and calculates the time and quality at which new fragment requests will be placed, when the player switches to a different quality, as well as the buffer occupancy at every iteration of the algorithm. Each group has to implement the player logic, the instantaneous available bandwidth is read from the trace file and this is used to calculate the estimated available bandwidth.

Hint 1: We recommend that your simulator is event-based and that you always keep track of the current event and its time. For example, is it a download completion, a buffer run-out, or is it a change in the available bandwidth. Your simulator must "simulate" events one after another using the "simulated" time. Note that the run time of the simulator depend on the number of events and the complexity of your code, not the "simulated" playtime of the video. (You should not try to "emulate" events at the rate of a player.) For example, the simulation of a 2-minute video playback session should complete almost instantaneously (if you write a reasonable program and run the code on a good machine). This way, simulations allow you to run many tests during a short amount of time.

Hint 2: When designing your algorithms, you need to identify the states that the player can be in and the actions (or state transitions) that can take place at the next event. Also, to save time, try to break the problem into smaller tasks that you quickly can complete one at a time (e.g., identify states/events, write high-level algorithm, identify sub-functions X, Y, Z, etc., including a function that read the log file, for example, identify test cases and sanity tests for these functions, and write the function X, Y, Z, etc.).

Simulation scenarios: For this assignment you can consider a single client connecting directly to the server, which has the available bandwidth (to the server) as specified in the trace file. The player downloads a video file (with encodings described above) with our simplified player policies (described above). You should consider two cases; one for each way of estimating the available bandwidth (options 1 and 2, described above).

Deliverables: Demonstration and Report

Short report: In addition to creating the above simulator, you should write a short report that has (at least) five parts. First, it should clearly list (in the form of summarizing bullets) all assumptions made for your player simulations. This involves identifying the simplified assumptions spread throughout this descriptions, as well as any additional assumptions that you made to make the simulator work. Second, it should summarize your results using figures and brief explanations of what are shown. Please use the following file to generate output graphs. (Updated file for the university machines: updated.) Necessary instructions have been included in the file. Third, you should discuss the impact of the bandwidth estimations (e.g., does the value of α matter?) and what other changes to the player (that you do not have to implement or test) you expect would be most beneficial for a mobile client, such as the one you simulated the performance of. Fourth, please discuss what impact the simplifying assumptions may have had relative to what would have been observed with a "real" implementation. Fifth, related to assignment 1, please briefly discuss how you would modify the player policies to act intelligently, if you had knowledge (or good predictions) about potential future bandwidth conditions (based on your location and your future path when commuting to school/work, for example).

Demonstrations and reporting: Before (i) handing in a hard copy of your written report and (ii) emailing your code to the TA, it is important that you demonstrate your assignment and discuss your (already printed) report with the TA.

To assess your understanding of the lab, during the demonstration, the TA may ask similar questions as those in the report. As the assignments are done in groups of two, both members of the group will be asked to answer questions. You are expected to clearly explain and motivate your answers both verbally AND in the written report.

Additional instructions and information about the reports can be found here. Please take this chance to read the guidelines carefully.

Optional Bonus Task

By providing a good solution to one of the two optional tasks below, you can earn yourself up-to two (2) additional bonus marks for the exam.

References

[1] H. Riiser, P. Vigmostad, P. Halvorsen, and C. Griwodz. "Commute Path Bandwidth Traces from 3G Networks: Analysis and Applications", In Proc. ACM Multimedia Systems Conference (MMSys), February/March 2013, pp. 114--118.

[2] S. Akhshabi, A. C. Begen, and C. Dovrolis. "An experimental evaluation of rate-adaptation algorithms in adaptive streaming over HTTP", In Proc. ACM Multimedia Systems Conference (MMSys), San Jose, CA, Feb. 2011.

[3] V. Krishnamoorthi, N. Carlsson, D. Eager, A. Mahanti, and N. Shahmehri, "Quality-adaptive Prefetching for Interactive Branched Video using HTTP-based Adaptive Streaming", In Proc. ACM Multimedia (MM), Orlando, FL, Nov. 2014, pp. 317--326.

[4] N. Carlsson, D. Eager, V. Krishnamoorthi, and T. Polishchuk, "Optimized Adaptive Streaming of Multi-video Stream Bundles", IEEE Transactions on Multimedia (IEEE TMM), volume 19, issues 7, July 2017, pp. 1637--1653.