Project 2 Adaptive Bitrate Streaming-Model Predictive Control

Author: Zhen Tong 120090694

Preface

This is a computer network course second project in CUHKSZ. We are asked to reproduce one algorithm for the Adaptive Bitrate problem. And this document is write for MPC(2015 SIGCOMM) reproduction.

Problem Definition

Video Streaming Model

$V \{1, 2, ..., K\}$ $L$ $R$ $k$ $R_k$ $d_k(R_k)$ $k$ $R_k$ $d_k(R_k) = L\times R_k$ .

$R_k$ $q(R_k)$ $B(t)\in[0, B_{max}]$ $t$ .

We can write the download process in the buffer formally:

t_{k + 1} = t_{k} + \frac{d_{k} (R_{k})}{C_{k}} + Δ t_{k}

$C_k$ $k$ $\Delta t$ is the time unrelated to the downloading (e.g. the parsing time, algorithm run time to choose bitrate, and overhead)

C_{k} = \frac{\int_{t_{k}}^{t_{k + 1} - Δ t_{k}} C_{t} d t}{t_{k + 1} - t_{k} - Δ t_{k}}

$C_t$ $t$ . Totally, we can model the buffer increase and decrease by this formula:

B_{k + 1} = ((B_{k} - \frac{d_{k} (R_{k})}{C_{k}})_{+} L - Δ t_{k})_{+}

$k$ $L$ $L$ $\frac{d_k(R_k)}{C_k}$ $(x)_+ = \max\{x, 0\}$ , ensures the buffer will never be negative.

video_model

QoE Maximization Problem

Another goal is improve the QoE of users. This project provides a flexible QoE.

Average video quality a measurement of the whole video, averaging the quality of all chunks.
Average Quality Variations is a measurement to consecutive variation of the quality, which cares about the sequential quality fluctuation.
Total rebuffering time is the sum of rebuffering for each chunk downloading. We want to minimize this measurement
$T_s$ is the time before the video gets to play

\begin{matrix} Average Video Quality = \frac{1}{K} \sum_{k = 1}^{K} q (R_{k}) \\ Average Quality Variations = \frac{1}{K - 1} \sum_{k = 1}^{K - 1} | q (R_{k + 1}) - q (R_{k}) | \\ Rebuffering = \sum_{k = 1}^{K} max {\frac{d_{k} (R_{k})}{C_{k}} - B_{k}, 0} \\ T_{s} << B_{m a x} \end{matrix}

$QoE$ is a weighted sum of the four measurement.

Q o E_{1}^{K} = \sum_{k = 1}^{K} q (R_{k}) - λ \sum_{k = 1}^{K - 1} | q (R_{k + 1}) - q (R_{k}) | - μ \sum_{k = 1}^{K} max {\frac{d_{k} (R_{k})}{C_{k}} - B_{k}, 0} - μ_{s} T_{s}

In the paper, researchers use 3 sets of weights:

$\lambda = 1, \mu = \mu_s = 3000$
$\lambda = 3, \mu = \mu_s = 3000$
$\lambda = 1, \mu = \mu_s = 6000$

MPC Algorithm

$f(\cdot)$ $R_k$ according to the previous information:

R_{k} = f (B_{k}, {{\hat{C}}_{t}, t > t_{k}}, {R_{i}, i < k})

$f(\{\hat{C}_t, t>t_k\}, \{R_i, i<k\})$ $f(B_k, \{R_i, i<k\})$ are all just sub-optimal in this context of question.

RBBB

$[t_k, t_{k+N}]$ $[t_{k+1}, t_{t+N+1}]$

2-alg1

Because this paper is not focus on the predictor function, they refer to the previous work(click to see paper), and use the harmonic mean of the observed throughput of the last 5 chunks because it is robust to outliers in per-chunk estimates

The core optimization in this algorithm is:

2-optimal

Change into dynamic programming

\begin{matrix} Q o E_{i}^{K} = \sum_{k = i}^{K} q (R_{k}) - λ \sum_{k = i}^{K - 1} | q (R_{k + 1}) - q (R_{k}) | - μ \sum_{k = i}^{K} max {\frac{d_{k} (R_{k})}{C_{k}} - B_{k}, 0} \\ = q (R_{i}) + \sum_{k = i + 1}^{K} q (R_{k}) - λ | q (R_{i + 1}) - q (R_{i}) | - λ \sum_{k = i + 1}^{K - 1} | q (R_{k + 1}) - q (R_{k}) | - μ max {\frac{d_{i} (R_{i})}{C_{i}} - B_{i}, 0} - μ \sum_{k = i + 1}^{K} max {\frac{d_{k} (R_{k})}{C_{k}} - B_{k}, 0} \\ = q (R_{i}) - λ | q (R_{i + 1}) - q (R_{i}) | - μ max {\frac{d_{i} (R_{i})}{C_{i}} - B_{i}, 0} + Q o E_{i + 1}^{K} \end{matrix}

$q(R_k)$

Performance

Because this algorithm has the benefit over simply buffer-based approach or simply rate-based approach, in the performance part, we test the average bitrate, buffer time, and switch stability between MPC and buffer-based (BB) algorithm. Apparently, when the trace is ALT, the MPC is better than BB.

2-rebuffer 2-switch

As for the rebuffer time, because the most of the time, MPC will offer a better bitrate, which means it will take more time to download the video. As for the HD and PQ trace, the rebuffering time is pretty the same. Because the MPC has one target to make the quality of video stable, from the switch times graph, we can see the MPC has less switch times than the BB algorithm

How to Run

There are a batch of simulation files list in the run_simulation.sh waiting for you to run. Only uncomment one line to test one case, don't test all! This is because the simulation need to communicate with the BBComm.py or mpComm.py


x
chmod +x scripts/run_simulation.sh
chmod +x scripts/run_BB.sh
chmod +x scripts/run_MPC.sh

Then first run the scripts/run_BB.sh or scripts/run_MPC.sh in one terminal, and run the scripts/run_simulation.sh in another terminal. You can also run the code without bash. But I recommend you do that because it can show you the detail performance in the log.txt.

2-run

Reference

Yin, Xiaoqi, et al. "A control-theoretic approach for dynamic adaptive video streaming over HTTP." Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 2015.
Jiang, Junchen, Vyas Sekar, and Hui Zhang. "Improving fairness, efficiency, and stability in http-based adaptive video streaming with festive." Proceedings of the 8th international conference on Emerging networking experiments and technologies. 2012.
Huang, Te-Yuan, et al. "A buffer-based approach to rate adaptation: Evidence from a large video streaming service." Proceedings of the 2014 ACM conference on SIGCOMM. 2014.
https://github.com/zpeats/50863_ABR_Lab/tree/master