Online Bitrate Selection for Viewport Adaptive 360-Degree Video Streaming

The video is temporally partitioned into segments (i.e., small video pieces), each corresponding to a playback time of $\beta$ seconds. Let $\mathcal{I}=\{1,2,\ldots,I\}$ denote the set of segments. Each segment is further spatially divided into $K$ tiles with $M$ rows and $N$ columns, i.e., $K=MN$. Let $\mathcal{K}=\{1,2,\ldots,K\}$ denote the set of tiles of each segment.

We introduce a reference FoV for each segment, where the idea is inspired by the recommended FoV in [25]. In practice, the reference FoV can be either the FoV showing the main object (determined by object detection methods, e.g., [12]) of the video scene or the recommended FoV marked by video producers (e.g., [25]). The reference FoV is used to characterize user-specific FoV preference, i.e., the relative position of a user’s FoV to the reference FoV. Fig. 3 shows an example of a 360-degree video streaming of car riding experience. The reference FoV can be looking ahead in the car (e.g., the four shaded tiles in the center) in Fig. 3, while a user may prefer to look toward his right-hand side (e.g., the FoV represented by the solid rectangle) in Fig. 3.

The reference FoV can be different in different segments. Hence, in order to characterize the user’s FoV preference (i.e., the relative position of the user’s FoV to the reference FoV), we define the indices of the tiles based on their relative positions to the reference FoV.¹¹1If using a fixed tile indexing (irrelevant to the reference FoV) as in most of the existing works in VA360 (e.g., [6, 5]), we cannot characterize user’s FoV preference because the reference FoV can vary across segments. This is one approach of tile indexing, while it does not affect either the video encoding or the video streaming process. The indices of the tiles are defined as follows. Suppose the top-left corner of the reference FoV is at the tile on row $m_{0}$ and column $n_{0}$. The tile on row $m$ and column $n$ is indexed with $N\text{mod}(m-m_{0},M)+(\text{mod}(n-n_{0},N)+1)$, where $\text{mod}(x,y)$ is equal to $x$ modulo $y$, and $M$ and $N$ is the total number of rows and columns of the tiles, respectively. For example, in Fig. 4, the reference FoV is represented by the shaded area, which can be different for different segments. In segment $1$, the top-left corner of the reference FoV is located at the tile on row $m_{0}=2$ and column $n_{0}=2$, so the tile on row $m=2$ and column $n=4$ is indexed by $4\text{mod}(2-2,4)+(\text{mod}(4-2,4)+1)=3$. Note that the 360-degree video has no boundary, e.g., in segment $1$, tile $4$ is adjacent to the right-hand side of tile $3$.

In the following, we use tile $(i,k)$ to denote tile $k$ of segment $i$. Each tile is encoded at $|\mathcal{R}|$ bitrate levels, where each level is selected from bitrate set $\mathcal{R}=\{R_{1},R_{2},...,R_{|\mathcal{R}|}\}$. The value of the bitrate represents the number of bits required to encode a tile corresponding to a playback time period of one second. Hence, the size (i.e., the total number of bits) of a tile of a $\beta$-second segment selecting bitrate $r\in\mathcal{R}$ is $r\beta$. Without loss of generality, we assume that $R_{1}<R_{2}<\cdots<R_{|\mathcal{R}|}$.

During video streaming, the user’s downloading capacity and his FoV are time-varying. The user’s downloading capacity varies across time. We consider a continuous time interval $\mathcal{T}=[0,T)$. Let $d(t)$ denote the user’s downloading capacity at time $t\in\mathcal{T}$, i.e., the user’s maximum achievable downloading rate at time $t$. We assume that $d(t)$ is upper- and lower-bounded, i.e., $d(t)\in[d^{\text{min}},d^{\text{max}}]$ for all $t\in\mathcal{T}$. On the other hand, the user’s FoV varies across playback time (instead of the real time),²²2For example, a user starts playing the video at time $t=0$ sec, and the video rebuffers for one second during time interval $[1,2]$ (sec). Then, at real time $t=3$ sec, the playback time is at $3-(2-1)=2$ sec. because the user changes his FoV to watch his interested contents in the video, which is playback time-associated. We assume that when the user watches a segment, the user’s FoV is unchanged. This is reasonable because in practice, a segment always corresponds to a video piece of several seconds.

The user makes decisions on the bitrates of the tiles. Let $r_{i,k}\in\mathcal{R}$ denote the bitrate decision of tile $(i,k)$. Let $\tau_{i,k}\in\mathcal{T}$ and $\hat{\tau}_{i,k}\in\mathcal{T}$ denote the time that the downloading of tile $(i,k)$ is started and finished, respectively. The user downloads the video tiles in a particular sequence: tile $(i,k)$ is downloaded earlier than tile $(i^{\prime},k^{\prime})$ if and only if either (a) $i<i^{\prime}$ or (b) $i=i^{\prime}$ and $k<k^{\prime}$. When one tile has been downloaded, the downloading of the next tile will start immediately, i.e.,

Let $b_{i}$ denote the buffer occupancy when all the tiles of segment $i$ have been downloaded. We define the buffer occupancy with respect to the segment index for the presentation simplicity of buffer update (i.e., the buffer is being updated when a segment has been received). The buffer occupancy is in the unit of playback time, which is commonly used in the existing literature on dynamic adaptive streaming over HTTP (DASH), e.g., [26]. Receiving one segment will lead to a buffer occupancy increased by $\beta$ seconds.

Without loss of generality, we set $b_{0}={b}^{\textsc{ini}}$ as the initial buffer occupancy, and $\hat{\tau}_{0,K}={\tau}_{1,1}=0$ as the initial starting time. We denote the following decision vectors: $\bm{r}=(r_{i,k},i\in\mathcal{I},k\in\mathcal{K})$, $\bm{r}_{i}=(r_{i,k},k\in\mathcal{K})$, $\bm{\tau}=(\tau_{i,k},i\in\mathcal{I},k\in\mathcal{K})$, $\hat{\bm{\tau}}=(\hat{\tau}_{i,k},i\in\mathcal{I},k\in\mathcal{K})$, and $\bm{b}=(b_{i},i\in\mathcal{I})$.

Within the downloading period of tile $(i,k)$, the capacity constraint ensures that the total size of the downloaded tile should be no larger than the downloading capacity within the downloading period, i.e.,

When all the tiles of segment $i$ have been received, the buffer is updated as follows:

where the operator $[x]^{+}=\max\{x,0\}$. In (3), if the buffer occupancy $b_{i-1}$ is no smaller than the downloading period, then buffer occupancy $b_{i}$ is the sum of the buffer occupancy immediately before receiving segment $i$ and the received segment length $\beta$. If the buffer becomes empty before receiving segment $i$, then buffer occupancy $b_{i}$ is equal to $\beta$.

For the definition of the user’s QoE, let $\omega_{i,k}$ denote the fraction of tile $(i,k)$ that is overlapped with the user’s FoV. We define a function $\mu_{i}(\bm{r}_{i})$ for any segment decision vector $\bm{r}_{i}$, indicating the viewing bitrate when the user views segment $i$ under the bitrate decision, i.e.,

Note that this is the bitrate that the user actually views, taking into account the user’s FoV.

Similar to some of the existing works [6, 15], the user’s QoE consists of three terms, which are the user’s viewing utility $U(\bm{r})$, the rebuffering loss $L^{\textsc{rb}}(\bm{\tau},\hat{\bm{\tau}},\bm{b})$, and the bitrate degradation loss $L^{\textsc{bd}}(\bm{r})$, i.e.,

The user’s viewing utility of each segment is a function of the user’s viewing bitrate of the segment, i.e., a larger viewing bitrate leads to a higher utility. The user’s viewing utility $U(\bm{r})$ is the summation of the user’s viewing utilities of all segments:

where $u_{i}(\cdot)$ for segment $i$ is a nondecreasing concave function. This is a generalization of those works considering linear viewing utility, e.g., [6, 5, 15].

If the tiles of a segment have not been completely received by the video player when the segment is to be played, then rebuffering will occur, and the video will freeze until the tiles of the segment are received. The rebuffering loss is the user’s loss resulting from the video freeze. This loss is proportional to the rebuffering time. Hence, the rebuffering loss is defined as follows:

where $l^{\textsc{rb}}$ is the unit loss if the user experiences a one-second rebuffering. In (7), if the downloading duration of segment $i$ is larger than the buffer occupancy $b_{i-1}$, then rebuffering will happen, leading to a rebuffering time of $\left[\hat{\tau}_{i,K}-\tau_{i,1}-b_{i-1}\right]^{+}$.

The bitrate degradation loss consists of two parts: an inter-segment bitrate degradation loss $L^{\textsc{bd-e}}(\bm{r})$ and an intra-segment bitrate degradation loss $L^{\textsc{bd-a}}(\bm{r})$. That is,

The inter-segment bitrate degradation loss is the loss resulting from the bitrate degradation among segments, i.e.,

where $l^{\textsc{bd-e}}$ is the loss if the viewing bitrate is degraded by one unit. In (9), if $\mu_{i-1}(\bm{r}_{i-1})$ is larger than $\mu_{i}(\bm{r}_{i})$, then the inter-segment bitrate degradation occurs, leading to a degradation loss which is proportional to the size of the degradation. The intra-segment bitrate degradation loss is the loss resulting from the bitrate difference among the tiles of each segment, i.e.,

where $l^{\textsc{bd-a}}$ is the loss if the bitrate is degraded by one unit. In (10), if $\omega_{i,k}$ is positive (i.e., the tile is being viewed), and the bitrate $r_{i,k}$ is smaller than the normalized viewing bitrate $\mu_{i}(\bm{r}_{i})/(\sum_{k^{\prime}\in\mathcal{K}}\omega_{i,k^{\prime}})$, then the intra-segment bitrate degradation happens, inducing a degradation loss proportional to the size of the degradation.

We aim to determine the decision vectors $\bm{r}$, $\bm{\tau}$, $\hat{\bm{\tau}}$, $\bm{b}$ to maximize the user’s QoE subject to the capacity and buffer update constraints. The problem is formulated as follows:

Problem (11) is a mixed-integer nonconvex programming problem with nonlinear constraints (2) and (3). This problem is challenging to solve, even in an offline case when all the parameters (i.e., the user’s FoV and downloading capacity) are known beforehand.

In this work, we focus on the online algorithm design, which addresses the realistic scenario where the user’s FoV of a segment and the capacity for downloading the segment are unknown when the bitrate decision of the segment needs to be made.

For segment $i\in\mathcal{I}$, we define a function $\widetilde{Q}_{i}(\bm{r}_{i}~{}|~{}\bm{r}_{i-1},b_{i-1})$, which indicates the user’s QoE of segment $i$ under bitrate decision vector $\bm{r}_{i}$, given the bitrate decision vector of segment $i-1$ (i.e., $\bm{r}_{i-1}$) and the buffer occupancy before downloading segment $i$ (i.e., $b_{i-1}$). The function $\widetilde{Q}_{i}(\bm{r}_{i}~{}|~{}\bm{r}_{i-1},b_{i-1})$ is given as follows:

where $\bar{d}_{i}$ is the average downloading capacity when segment $i$ is being downloaded. For simplification, we will use $\widetilde{Q}_{i}(\bm{r}_{i})$ to denote $\widetilde{Q}_{i}(\bm{r}_{i}~{}|~{}\bm{r}_{i-1},b_{i-1})$ in the rest of this paper.

In contrast to the user’s QoE for segment $i$ (as in Section 2.2.3), equation (12) has two major differences. First, the downloading time of segment $i$ in (12), i.e., ${\sum_{k\in\mathcal{K}}r_{i,k}\beta}/\bar{d}_{i}$, is an approximation of the actual downloading time (as it is computed in (2)). This approximation is introduced to simplify the algorithm design, and is close to the actual downloading time, because the change of the downloading capacity within the downloading period of a segment is small in practice.³³3For example, downloading a two-second 4K segment (which has a bitrate of around $2\times 50$ Mbps on YouTube) using a 62 Mbps downlink (as the average mobile download speed in Canada in 2019 [27]) leads to a downloading period of $2\times 50/62\approx 1.6$ seconds. Second, in (12), we relax the operators $[\cdot]^{+}$ involved in the rebuffering loss and the inter-segment bitrate degradation loss. Intuitively, as we focus on per-segment problems, this relaxation can help with characterizing the impact of the bitrate decision of a segment on the user’s QoE of the subsequent segments. For example, the rebuffering loss may fail to capture the difference between downloading a segment (with smaller bitrates) for one second and downloading a segment (with larger bitrates) for five seconds, if neither downloading process induces rebuffering. The two downloading processes, however, may lead to different likelihood of having a rebuffering later due to the resulting different buffer occupancies after the downloading has been accomplished. This difference can be characterized if the operator $[\cdot]^{+}$ is relaxed. A similar reason applies for the inter-segment bitrate degradation loss.

Given $\bm{r}_{i-1}$ and $b_{i-1}$, the per-segment problem for segment $i$ is to determine the bitrate decision $\bm{r}_{i}$ by maximizing $\widetilde{Q}_{i}(\bm{r}_{i})$, i.e.,

Problem (OPT-SEGMENT-i) does not include constraints (1), (2), and (3) (as in problem (11)) for the following reasons. Constraint (1) is eliminated, because under the per-segment problem, the relationship between the downloading time of different segments does not need to be considered. Constraint (2) is eliminated due to the downloading time approximation. In addition, with the set of per-segment problems, at the time that the bitrate decision of segment $i$ is optimized, the buffer occupancy $b_{i-1}$ is directly observed, so the buffer update constraint (3) is not required.

Let $\tilde{I}_{i}$ denote the segment index such that segment $i$ has been viewed by the user during the time period when the bitrate decisions of segments $\tilde{I}_{i}$ and $\tilde{I}_{i}+1$ are made. Since a segment should be downloaded before it is being viewed, the FoV and downloading capacity information of segment $i$ has been observed by the video player when the bitrate decision of segment $\tilde{I}_{i}+1$ is to be made. The auxiliary set $\mathcal{I}_{i}\subset\mathcal{I}$ for segment $i\in\mathcal{I}\cup\{I+1\}$ is defined as follows:

which is the set of segments which have been viewed by the user during the time period when the bitrate decisions of segments $i-1$ and $i$ are made. The consideration of $i=I+1$ is used to include the segments whose parameter realizations are observed after the bitrate decision of segment $I$ is made.⁴⁴4Note that given the bitrate decisions and the parameter realizations of all segments in $\mathcal{I}$, the vectors $\mathcal{I}_{I+1}$ and $\bm{r}^{o}_{I+1}$ can be determined.

The OBS360 algorithm is given in Algorithm 1. The algorithm first initializes the following parameters: an initial bitrate vector $\bm{r}_{0}$, which can be any bitrate in set $\mathcal{R}^{K}$; a parameter $\alpha>0$, which corresponds to the positive stepsize in the existing OGD algorithms [19, 20, 21].

For any segment $i$, the video player first obtains the auxiliary set $\mathcal{I}_{i}$, which contains the indices of the segments whose FoV and downloading capacity information is newly observed as defined in (15). If the set $\mathcal{I}_{i}$ is non-empty, then the bitrate decision of segment $i$ will be made based on the bitrate decisions of the segments referred in set $\mathcal{I}_{i}$ and the corresponding downloading capacity and FoV information when each of those segments is downloaded and viewed, respectively. Specifically, the bitrate decision of segment $i$ is updated as follows:

where $\nabla\widetilde{Q}_{J_{i}}(\bm{r}_{J_{i}}^{o})$ is the subgradient of $\widetilde{Q}_{J_{i}}(\bm{r}_{J_{i}}^{o})$, and $J_{i}$ is defined as

Specifically, $J_{i}$ is the segment index in set $\mathcal{I}_{i}$ such that the dot product of the negative value of the subgradient $\nabla\widetilde{Q}_{j}(\bm{r}_{j}^{o})$ and the difference between the optimal decision of segment $J_{i}$ (obtained by solving the corresponding per-segment problem) and the actual decision of segment $J_{i}$ (obtained according to the algorithm) is the smallest, comparing with other segments in set $\mathcal{I}_{i}$. If the set $\mathcal{I}_{i}$ is empty, then the bitrate decision of segment $i$ is the same as the bitrate decision of segment $i-1$:

In the special case when set $\mathcal{I}_{i}=\{i-1\}$ for all $i\in\mathcal{I}\cup\{I+1\}$, i.e., the information of segment $i-1$ can always be observed during the time period when the decisions of segments $i-1$ and $i$ are made, Algorithm 1 is equivalent to the existing OGD algorithms in [19, 20, 21].

In online convex optimization techniques considering time-varying parameters, without restricting the varying of the parameters, obtaining a bound on dynamic regret is not possible [23]. Here, we impose a condition on the varying of the parameters as follows:

In Condition 1, inequality (19) implies that the number of the bitrate decisions that are not updated based on (16) is bounded. Inequality (20) ensures that the variations of the parameters are relatively small, such that the changes among the optimal solutions to the per-segment problems are bounded. In the special case when $\mathcal{I}_{i}=\{i-1\}$ for all $i\in\mathcal{I}\cup\{I+1\}$, Condition 1 is equivalent to each of the parameter variation conditions in the existing works [20, 19] on OGD algorithms.

In the following, we first show the bound of the regret of each segment under Algorithm 1. We then show the bound of the dynamic regret.

The bound of the regret of each segment is given in Lemma 1. Note that in this lemma, we use two different subscripts $s$ and $i$ to refer to the indices of different segments in order to make the presentation clear.

Based on Lemma 1, we show that the dynamic regret of Algorithm 1 is upper-bounded in Theorem 1.

Based on Theorem 1, the dynamic regret of Algorithm 1 is sublinear under particular setting of $\alpha$.

Corollary 1 implies that as the number of segments increases, the performance of the proposed online algorithm approaches the performance under the optimal solutions to the per-segment problems (OPT-SEGMENT-i) for $i\in\mathcal{I}$.