Optimizing Quality of Experience of Dynamic Video Streaming over Fading Wireless Networks

We address the problem of video streaming packets from an Access Point (AP) to multiple clients over a shared wireless channel with fading. In such systems, each client maintains a buffer of packets from which to play the video, and an outage occurs in the streaming whenever the buffer is empty. Clients can switch to a lower-quality of video packet, or request packet transmission at a higher energy level in order to minimize the number of outages plus the number of outage periods and the number of low quality video packets streamed, while there is an average power constraint on the AP. We pose the problem of choosing the video quality and transmission power as a Constrained Markov Decision Process (CMDP). We show that the problem involving $N$ clients decomposes into $N$ MDPs, each involving only a single client, and furthermore that the optimal policy has a threshold structure, in which the decision to choose the video-quality and power-level of transmission depends solely on the buffer-level.


I. INTRODUCTION
Scheduling packets for video streaming over a shared wireless downlink is of increasing attention [18]. Predominantly, this problem has been addressed with the goal of minimizing the average number of outages, i.e., time-slots during which a client has no packet to play [1], [2], [3], [4], [5], [6], [7], [8], [9]. However the models considered in these works do not incorporate the communication constraints imposed by the network over which the streaming occurs. Typically clients streaming video files will share a common wireless channel, which again typically has a constraint on the average power. The access point (AP) has to choose the power level at which to transmit individual packets to each client so as to maximize the total Quality of Experience (QoE) experienced by the clients. The system also has an additional degree of freedom in that the AP can transmit lower quality packets on occasion, leading to a softer loss of video quality than an abrupt outage. Another important aspect is that the quality of video streaming experienced by a client depends not only on the number of outages, but also on the number of "outage periods", i.e., number of interruption periods as well. Thus an outage lasting 10 time-slots is not the same as 10 outages each lasting 1 time-slot. The QoE experienced by a client thus has to take into account several metrics: the average number This material is based upon work partially supported by AFOSR Contract FA9550-13-1-0008, and NSF under Contract Nos. CNS-1302182 and Science & Technology Center Grant CCF-0939370. 1  of outages, the average number of outage-periods, and the quality of video-packets streamed. In this paper we address this overall problem. While we focus here on the single last-hop case for ease of exposition and brevity, our results can be generalized to multi-hop networks as well. In order to provide non-interruptive video streaming experience to the clients, the AP has to guarantee some sort of service regularity to the clients, i.e., it has to ensure that the packet deliveries to the clients are not in a bursty fashion. References [19], [20], [21], [22], [23] develop a framework to design policies which provide services to clients in a regular fashion, though not in a video streaming context.

II. SYSTEM DESCRIPTION
Consider a system where a wireless channel is shared by N clients for the purpose of streaming video packets. It is assumed that the system evolves over discrete timeslots, and one time-slot is taken by the access point (AP) for attempting one packet transmission.
Client n maintains a buffer of size B n packets and plays a packet for a duration of T n time-slots. Once it has finished playing a video packet, it looks for the next packet in the buffer. In case the buffer is empty, there is an "outage", meaning that the video streaming is interrupted, and the client has to wait for a packet to be delivered to its buffer before it can resume the video streaming.
The wireless channels connecting the clients to the AP are assumed to be random. For ease of exposition, we will derive the results for the case when the channel conditions are fixed. These results carry over to the case of fading channels in a straight-forward manner. Later, in Section VIII, we will outline the results for the case of fading channels.
There are Q n different video qualities {1, 2, . . . , Q n } of packets that can be transmitted for client n, with class 1 video quality providing the best viewing experience. Similarly there are {Ê 1 ,Ê 2 , . . . ,Ê n } different power levels at which the packets for client n can be transmitted. We letÊ 1 = 0, i.e., a user may choose to not request a packet in a time-slot. The probability that the packet for client n is successfully delivered upon a transmission attempt, P n (q, E), depends on the amount of power E used in the packet transmission and the quality of video packet q that was attempted. We also incorporate an average power constraint on the AP.
The basic problem considered is that of scheduling the AP's packet transmissions to clients so as to maximize the combined Quality of Experience (QoE) of the clients. The QoE of a single client depends on multiple factors 1) The average number of outages. 2) How "often" the video gets interrupted, i.e., the number of outage-periods, or the number of timeslots in which the transition from "non-outage" to outage occurs.
3) The number of packets of different quality types that are streamed.

III. PROBLEM FORMULATION
We denote by O n (s) the random variable that assumes the value 1 if the n-th client faces an outage at time s, and 0 otherwise, and by E n (s) the transmission power utilized by the n-th client at time-slot s. Also, let I n (q, s) be the random variable that takes the value 1 if a packet of quality q is delivered to client n in time-slot s.
The Constrained Markov Decision Process (CMDP) of interest is then to choose the quality of video packets and transmission power for each client, in order to Minimize lim sup lim sup Note that the term |O n (s) (O n (s − 1) − 1) | assumes the value 1 if time-slot s is the beginning of an outageperiod for client n, and is 0 otherwise. It thereby measures the number of outage periods incurred. The parameters {λ q,n } Qn q=1 , λ O,n n = 1, 2, . . . , N are employed for tuning the QoS to account for the relative importance placed on each of the objectives. We note that for i > j, λ i,n > λ j,n for all n, since we assumed that the video quality of a packet is less if the packet belongs to a higher valued class.
Thus the above problem is a CMDP in which the system state at time t is described by the N dimensional vector L(t) := (l 1 (t), l 2 (t), . . . , l N (t)), where l n (t) is the amount of play time remaining in the buffer of client n at time t.
The central difficulty which arises is that the cardinality of the state-space of the system increases exponentially with the number of clients N , and thus the problem is computationally infeasible as formulated above.
We show that the problem of serving N clients can be decomposed into N separate problems each involving only a single client. Thus the computational complexity of the problem grows linearly in the number of clients. Moreover, we show that the optimal policy is easily implementable since it has a simple threshold structure.

IV. THE DUAL MDP
The Lagrangian associated with a policy π for the system (1) is given by, where λ E is the Lagrangian multiplier associated with the average power constraint. The associated Lagrange dual is, Next we present a useful bound on the dual, the proof of which follows from the super-additivity of lim sup and sub-additivity of lim inf operations. Lemma 1:

V. SINGLE CLIENT PROBLEM
We consider minimizing the bound obtained in Lemma 1. Observing the bound, we find that we have decomposed the original problem (1) into N singleclient problems, i.e., the expression in the r.h.s. of (4) is the sum of the costs of N clients, in which the cost of a single client depends only on the action chosen for it in each time-slot.
The problem for the single client is described as follows. We omit the sub-script n in the following discussion. The channel connecting the client to the AP is random. The client maintains a buffer of capacity B time-slots of play-time video (this assumption is equivalent to the assumption of maintaining a buffer of B packets since a packet is played for T time-slots), and in each time-slot, the AP has to choose two quantities, which together comprise the control action chosen for the client: • The video quality q ∈ {1, 2, . . . , Q}.
The state of the client is thus described by l(t), the playtime duration of the packets present in the buffer at time t. If the client is scheduled a packet transmission of quality q at an power E at time t, and the remaining playtime at time t, l(t), is less than or equal to B −T +1, However if the value of remaining playtime l(t) is strictly greater than B − T + 1, then the system state at time t + 1 is l(t) − 1 with a probability 1.
We let be the transitions associated with the remaining playtimes associated for a successful and failed packet transmission respectively. The control action at time t will be denoted u(t) := (q(t), E(t)), where q(t), E(t) are the video quality and transmission power level chosen at time t.
The transmissions at power level E incur a cost of λ E × E. There is a penalty of 1 unit upon an outage at time t. A penalty of λ q units is imposed if a packet of quality q is delivered to it, while a penalty of λ O units is imposed at time t in case there was no outage at timeslot t − 1, and an outage occurs in time-slot t, i.e. if a new outage-period begins at time t.
Since the probability distribution of the system state at time t + 1 is completely determined by the system state at time t, and the action (q, E) chosen at time t, i.e., requested video quality and power level at which transmission occurs, the single client problem is a Markov Decision Process (MDP) involving only a finite number of actions and states, and is thus solved by a stationary Markov policy [12].
Denote by π n a policy for the client n. The single client problem is to solve, Denote by π n (λ E ), the optimal policy which solves the single client problem. We also let be the optimal cost, and V n (λ E , π) be the cost associated with a policy π.
VI. THRESHOLD STRUCTURE OF THE OPTIMAL POLICY FOR THE SINGLE CLIENT PROBLEM We will suppress the subscript n in the following discussion, and begin with a discussion of the β ∈ (0, 1) discounted infinite horizon cost problem for the single client. Let be the minimum β-discounted infinite horizon cost for the system starting in state x at time 0, where x can assume values in the set {0, 1, . . . , B}. The function V s β (x) is similarly defined to be the minimum β-discounted cost incurred in s time-slots for the system starting in state x, i.e., where π s is a policy for the s horizon β-discounted problem. The quantities V β (x), V s β (x) should not be confused with the quantities V n (λ E ) defined in the previous section. We have, where is the one-step cost associated with the action u = (q, E), and for s = 1, 2, . . ., We assume that a lower video quality packet, or a higher power packet transmission, leads to an increase in the success of packet transmission P (q, E), i.e., an increase in cost is associated with a higher transmission success probability. Definition 1: We say a policy is of threshold-type if it satisfies the following for each stage s: . . , B} are such that x > y, let u x , u y be the actions chosen by a threshold policy π in states x and y. Then it is easily verified that P (u x ) < P (u y ).
Next we present a useful lemma that is easily proved. In the following, (u, π) is the policy that follows the action u in the first slot, and then follows policy π, while V s,π β (x) is the cost achieved under the policy π in s timeslots for the system starting in state x.
Lemma 2: Let u 1 , u 2 be two actions where P (u 2 ) > P (u 1 ), or equivalently, P (u 2 ) > P (u 1 ). Then,  Proof: Within this proof, let π s be the optimal policy for the β-discounted s time-slots problem, and let (u, π s−1 ) be the policy for s time-slots which takes the action u at the first time-slot, and then follows the policy π s−1 . In order to prove the claim, we will use induction on s, the number of time-slots.
Let us assume that the statement is true for the functions D β z (x), for all z ≤ s. In particular the function, is decreasing for x ∈ {1, 2, . . . , B − T + 1}.
Fix an x ∈ {1, 2, . . . , B − T } and denote by u 1 , u 2 , u 3 , u 4 , the optimal actions at stage s for the states S(x), F(x), S(x + 1), F(x + 1) respectively. Note that the threshold nature of π s implies that, P (u 1 ) < P (u 2 ), P (u 3 ) < P (u 4 ) and , This is true because as the value of state decreases in the interval {1, 2, . . . , B}, a threshold policy switches to an action that has a higher transmission success probability. So it follows from Lemma 2 that where the first inequality follows since a sub-optimal action in the state F(x + 1) increases the cost-to-go for s time-slots, the second inequality is a consequence of the assumption that the functions V s−1 β (F(x)) − V s−1 β (S(x)) are decreasing in x, while the last inequality follows from the fact that a sub-optimal action in the state S(x) will increase the cost-to-go for s time-slots. Thus we have proved the decreasing property of D β s+1 (·) for x ∈ {2, 3, . . . , B − T + 1}, and it remains to show that D β s+1 (1) > D β s+1 (2). Once again, let u 1 , u 2 , u 3 , u 4 be the optimal actions at stage s for the states T, 0, T + 1, 1 respectively. Using the same argument as above (i.e., assuming that the actions taken in stage s at states T, T + 1 are the same, and the actions taken in the states 0, 1 are the same), it follows that However, then V s β (T ) − V s β (T + 1) ≤ 1 + λ O − βλ O (for s stages, apply the same actions for the system starting in state T , as that for a system starting in state T + 1, and note that the two systems couple at a stage t − 1, when the latter system hits the state 1 at any stage t; the hitting stage is of course random). This gives us, and thus we conclude that the function D s+1 (x) is decreasing for x ∈ {1, 2, . . . , B}. In order to complete the proof, we notice that for s = 1, we have, and thus the assertion of Lemma is true for s = 1. Theorem 1: Consider the single client problem discussed in Section V. There is a threshold policy that is Blackwell optimal [17], i.e., it is optimal for all values of β ∈ (β, 1) for someβ ∈ (0, 1), and is also optimal for the Average cost problem. Thus π n (λ E ) is of threshold-type and can be obtained in time O(B E×Q ) via comparing the costs of all threshold-type policies.
Proof: Fix a q and let E i , E j , i > j be two power levels. Without loss of generality, let u 1 = (q, E i ), u 2 = (q, E j ). Clearly C(u 1 ) > C(u 2 ) (11). In the Bellman equation (10), consider the term depending on u, i.e. the term C(u) − P (u)D β s (x). For x, y ∈ {1, 2, . . . , B − T + 1}, x > y, we have, where the last inequality follows from Lemma 3. Thus it follows that if action u 1 is preferred over action u 2 for any state x, then u 1 will also be preferred over action u 2 for any state y < x, y ∈ {1, 2, . . . , B −T +1}. Finally note that it follows from the Bellman equation (10) and (5), that the optimal action for states x > B − T + 1 is to let E = 0 (since any packet that is received will be lost due to buffer over flow). The proof for variations in power levels is similar. Thus it follows from the definition of a threshold policy that the optimal policy is of threshold type.
Finally note that the statement regarding Blackwell optimality follows from the result in the above paragraph, and because the state-space is finite.

VII. SOLUTION OF PRIMAL MDP
We now present the solution of the Primal Problem.
Proof: Let π (λ E ) := ⊗π n (λ E ) be the policy obtained by following the policy π n (λ E ) for each client n. Then from the definition of dual function, Lagrangian (2), cost associated with a policy π (8) and Lemma 1, we have However since the policy π (λ E ) is stationary, (all the lim inf and lim sup become lim in the definition of its Lagrangian, and associated rewards in the single-client problem change to lim), we have that which, along with (14) gives us D(λ E ) = n V n (λ E ) − λ EĒ .
Theorem 2: Consider the Primal MDP (1) and its associated dual problem defined in (3). There exists a price λ E such that (π (λ E ), λ E ) is an optimal primal-dual pair and thus the policy π (λ E ) solves the Primal MDP.
Proof: We observe that there is a one-to-one correspondence between any stationary randomized policy, and the measure it induces on the state-action space, and thus the Primal MDP can be posed as a linear program [13], [14]. Thus it follows from Slater's condition [15] that for the Primal MDP, strong duality holds if there exists a policy π that satisfies the constraints lim sup t→∞ 1 t E n s E n (s) <Ē. However the policy which never schedules any packets incurs a net power expenditure of 0, and thus Slater's condition is true for the Primal MDP ifĒ > 0. The claim of the Theorem then follows from Lemma 3. We note that the policy π (λ E ) is a decentralized policy. That is, the decision to choose the video-quality and power-level at each time t for client n, i.e., (q n (t), E n (t)) can be taken by client n itself, and doesn't require the AP to co-ordinate the clients. Thus a client n need not know the state values of other clients, l m (t) for m = n, nor does the AP need to know the values of l n (t). Thus the policy is easy to implement.

A. Obtaining λ E iteratively in a decentralized fashion
We note that in order to implement the optimal policy π (λ E ) as in Theorem 2, we need to find the optimal value of the price λ E . We iterate on the price λ E using the sub-gradient method [16], and since the problem is concave, the prices converge to the optimal value λ E . Moreover the iterations involving price-updates are decentralized, i.e., the clients need only the knowledge of the current price λ E for the iteration.
where E π (λ E ) n τ (n, π (λ E )) is the expected cost incurred on the power over all the users. This is the total "congestion" at the AP. The iteration for λ E is, where d k is the sub-gradient evaluated in (15).

VIII. FADING CHANNELS
The results in the previous sections can be extended in a straight forward manner to the case of fading channels. Let the channel conditions for client n be described by a Markov process evolving on finitely many states {1, 2, . . . , C n } having a transition matrix Π n . The state of client n is described by the vector x n (t) := (l n (t), c n (t)), where l n (t) is the play-time duration of the packets present in the buffer at time t, and c n (t) is the channel condition at time t. If the client n is scheduled a packet transmission of quality q at an power E at time t, then the system state at time t + 1 is (S(l(t)),c) with a probability P n,cn(t) (q, E)Π(c n (t),c), while it is (F(l(t)),c) with a probability P n,cn(t) (q, E)Π(c n (t),c).
However now the cost associated to an action u also depends on the channel condition, i.e., and a threshold policy will have a threshold structure for each value of channel condition (as defined in Section V).

IX. CONCLUDING REMARKS
We have formulated the problem of dynamically choosing the qualities and power levels for packet transmissions across unreliable wireless so as to maximize the Quality of Experience of video streaming channels as an MDP. Using Lagrangian techniques, we have shown that the problem exhibits a decentralized solution, wherein the clients can dynamically decide these quantities on their own using their local information, i.e., the channel state and the amount of playtime remaining in their buffers. Thus the optimal policy can be obtained in time linear in the number of users.
Furthermore we have shown that the optimal policy has a threshold structure, thus further reducing the complexity of searching for the optimal policy. Moreover due to the threshold nature of the policy, it is easy to implement.