BOLA: Near-Optimal Bitrate Adaptation for Online Videos Kevin Spiteri1∗, Rahul Urgaonkar2†, Ramesh K. Sitaraman1,3 1University of Massachusetts Amherst, 2Amazon Inc, 3Akamai Technologies Inc {kspiteri,ramesh}@cs.umass.edu, [email protected] Abstract—Modern video players employ complex algorithms Providingahigh-qualityexperienceforvideousersrequires to adapt the bitrate of the video that is shown to the user. balancing two contrasting requirements. The user would like Bitrate adaptation requires a tradeoff between reducing the to watch the highest-quality version of the video possible, probability that the video freezes and enhancing the quality of where video quality can be quantified by the bitrate at which the video shown to the user. A bitrate that is too high leads 6 to frequent video freezes (i.e., rebuffering), while a bitrate that the video is encoded. For instance, watching a movie in high 1 is too low leads to poor video quality. Video providers segment definition (HD) encoded at 2 Mbps arguably provides a better 0 the video into short chunks and encode each chunk at multiple user experience than watching the same movie in standard 2 bitrates. The video player adaptively chooses the bitrate of each definition (SD) encoded at a bitrate of 800 kbps. In fact, chunk that is downloaded, possibly choosing different bitrates r there is empirical evidence that the user is more engaged p for successive chunks. While bitrate adaptation holds the key to A a good quality of experience for the user, current video players and watches longer when the video is presented at a higher usead-hocalgorithmsthatarepoorlyunderstood.Weformulate bitrate. However, it is not always possible for users to watch 2 bitrate adaptation as a utility maximization problem and devise videos at the highest encoded bitrate, since the bandwidth 1 an online control algorithm called BOLA that uses Lyapunov available on the network connection between the video player optimization techniques to minimize rebuffering and maximize on the user’s device and the video server constrains what ] videoquality.WeprovethatBOLAachievesatime-averageutility I that is within an additive term O(1/V) of the optimal value, for bitrates can be watched. In fact, choosing a bitrate that is N a control parameter V related to the video buffer size. Further, higher than the available network bandwidth1 will lead to . unlikepriorwork,ouralgorithmdoesnotrequireanyprediction video freezes in the middle of the playback, since the rate s c of available network bandwidth. We empirically validate our at which the video is being played exceeds the rate at which [ algorithminasimulatednetworkenvironmentusinganextensive collectionofnetworktraces.Weshowthatouralgorithmachieves the video can be downloaded. Such video freezes are called 2 near-optimalutilityandinmanycasessignificantlyhigherutility rebuffersandplayingthevideocontinuouslywithoutrebuffers v thancurrentstate-of-the-artalgorithms.Ourworkhasimmediate is a key factor in the QoE perceived by the user [3]. Thus, 8 impact on real-world video players and for the evolving DASH balancing the contrasting requirements of playing videos at a 4 standard for video transmission. highbitratewhileatthesametimeavoidingrebuffersiscentral 7 Index Terms—Internet Video, Video Quality, Adaptive Bitrate to providing a high-quality video watching experience. 6 Streaming, Lyapunov Optimization, Optimal Control 0 . A. Adaptive Bitrate (ABR) Streaming 1 I. INTRODUCTION 0 Achieving a high QoE for video streaming is a major Online videos are the “killer” application of the Internet 6 challenge due to the sheer diversity of video-capable devices 1 with videos currently accounting for more than half of the that include smartphones, tablets, desktops, and televisions. : Internet traffic. Video viewership is growing at a torrid pace v Further, the devices themselves can be connected to the i and videos are expected to account for more than 85% of all X Internet in a multitude of ways, including cable, fiber, DSL, Internet traffic within a few years [1]. As all forms of tradi- WiFiandmobilewireless,eachprovidingdifferentbandwidth r tional media migrate to the Internet, video providers face the a characteristics. The need to adjust the video playback to the daunting challenge of providing a good quality of experience characteristics of the device and the network has led to the (QoE) for users watching their videos. Video providers are evolution of adaptive bitrate (ABR) streaming that is now the diverseandincludemajormediacompanies(e.g.,NBC,CBS), de facto standard for delivering videos on the Internet. news outlets (e.g., CNN), sports organizations (e.g., NFL, ABR streaming requires that each video is partitioned into MLB), and video subscription services (e.g., Netflix, Hulu). chunks, where each chunk corresponds to a few seconds of Recent research has shown that low-performing videos that play. Each chunk is then encoded in a number of different start slowly, play at lower bitrates, and freeze frequently can bitrates to accommodate a range of device types and network cause viewers to abandon the videos or watch fewer minutes connectivities. When the user plays a video, the video player ofthevideos,significantlydecreasingtheopportunityforgen- can download each chunk at a bitrate that is appropriate for erating revenue for the video providers [2]–[4], underscoring the available bandwidth of the network connection. Thus, the need for a high-quality user experience. the player can switch to a chunk with a lower bitrate when ApreliminaryversionofthispaperappearedatINFOCOM2016. ∗SupportedinpartbyNSFgrantCNS-1413998. 1 Throughout this paper, we say bandwidth when talking about network †ThisworkwasperformedwhenRahulUrgaonkarwasatIBMResearch. throughputandbitratewhentalkingaboutencodingquality. the available bandwidth is low to avoid rebuffering. If more but only uses the amount of data that is currently stored bandwidth becomes available at a future time, the player can in the buffer of the video player. Recently, there has been switch back to a higher bitrate to provide a richer experience. empirical evidence that a buffer-based approach has desirable The video player has a buffer that allows it to fetch and propertiesthatbandwidth-basedapproacheslackandhasbeen store chunks before they need to be rendered on the screen. adopted by Netflix [11]. An intriguing outcome of our work Thus, the video player can tolerate brief network disruptions is that the optimal algorithm within our utility maximization without interrupting the playback of the user by using the framework requires only knowledge of the amount of data in buffered chunks. A large disruption, however, will empty the buffer and no estimate of the available bandwidth. Thus, the buffer, resulting in rebuffering. The decision of which our work provides the first theoretical justification for why chunks to download at what bitrates is made by a bitrate buffer-basedalgorithmsperformwellinpracticeandaddsnew adaptation algorithm within the video player, the design of insightstotheongoingdebate[12]withinthevideostreaming such algorithms being the primary focus of our work. and DASH standards communities of relative efficacy of the Several popular implementations of ABR streaming exist, two approaches. Further, since our algorithm BOLA is buffer- including Apple’s HTTP Live Streaming (HLS) [5], Mi- based, it avoids the overheads of more complex bandwidth crosoft’s Live Smooth Streaming (Smooth) [6] and Adobe’s prediction present in current video player implementations Adaptive Streaming (HDS) [7]. Each has its own proprietary and is more stable under bandwidth fluctuations. Note that implementation and slight modifications to the basic ABR our results imply that the buffer level is a sufficient statistic technique described above. A key recent development is that indirectly provides all information about past bandwidth a unifying open-source standard for ABR streaming called variations required for choosing the next bitrate. MPEG-DASH[8].DASHisbroadlysimilartotheotherABR We also empirically evaluate BOLA on a wide set of protocolsandisaparticularfocusinourempiricalevaluation. network traces that include 12 test cases provided by the DASH industry forum [13] and 85 publicly-available 3G B. Our Contributions mobilebandwidthtraces[14].Asabenchmarkforcomparison, Our primary contribution is a principled approach to the we develop an optimal offline algorithm that uses dynamic design of bitrate adaptation algorithms for ABR streaming. programming and is guaranteed to produce the maximum In particular, we formulate bitrate adaptation as a utility achievable time-average utility for any given set of network maximization problem that incorporates both key components traces. Unlike BOLA that works in an online fashion, the of QoE: the average bitrate of the video experienced by the offline optimal algorithm makes decision based on perfect user and the duration of the rebuffer events. An increase knowledge of future bandwidth variations. Remarkably, the in the average bitrate increases utility, whereas rebuffering utilityachievedbyBOLAiswithin84–95%ofofflineoptimal decreasesit.Astrengthofourframeworkisthatutilitycanbe utility for all the tested traces. definedinarbitraryways,say,dependingonthecontent,video Besides comparing BOLA with the offline optimal, we also provider, or user device. This contrasts with bitrate adaptation empirically compared our algorithm with two state-of-the-art algorithms currently in use that provide no such flexibility. algorithms proposed in the literature. In all test cases, BOLA Using Lyapunov optimization, we derive an online bitrate achievedautilitythatisasgoodasorbetterthanthebeststate- adaptation algorithm called BOLA (Buffer Occupancy based of-the-artalgorithm.Inhalfofthetestedscenarios,BOLAdid Lyapunov Algorithm) that provably achieves utility that is even better by achieving a utility that is nearly 1.75 times the within an additive factor of the maximum possible utility. utility of the best state-of-the-art algorithm. While numerous bitrate adaptation algorithms have been pro- We are also implementing BOLA as the default ABR algo- posed [9]–[12] and implemented within video players, our rithmindash.js,theopen-sourceDASHreferenceplayer[15]. algorithm is the first to provide a theoretical guarantee on the achieved utility. Further, BOLA provides an explicit knob II. SYSTEMMODEL for video providers to set the relative importance of a high Our system model closely captures how ABR streaming video quality in relation to the probability of rebuffering. works on the Internet today. We consider a video player While not an explicit part of the Lyapunov optimization that downloads a video file from a server over the Internet framework, we also show how BOLA can be adapted to and plays it back to the user. The video file is segmented avoid frequent bitrate switches during video playback. Bitrate into chunks that are downloaded in succession. The available switches are arguably less annoying than rebuffering, but it bandwidthbetweentheserverandtheplayervariesovertime. is still of some concern to video providers and users alike if This can be due to reasons such as network congestion and such switches occur too frequently. wireless fading among others. The viewing experience of the Most algorithms implemented in practice use a bandwidth- user is determined by both the video quality as quantified based approach where the available bandwidth between the by the bitrates of the chunks that are played back and the server and the video player is predicted and the predicted playback characteristics such as rebuffering. The objective value is used to determine the bitrate of the next chunk of the player is to maximize a utility associated with the that is to be downloaded. A complementary approach is a user’sviewingexperiencewhileadaptingtotime-varying(and buffer-based approach that does not predict the bandwidth, possibly unpredictable) changes in the available bandwidth. 2 Video Model: The video file is segmented into N chunks III. PROBLEMFORMULATION indexed as {1,2,...,N} where each chunk represents p We consider two primary performance metrics4 that affect secondsofthevideo.Ontheserver,eachchunkisavailablein theoverallQoEoftheuser:(1)time-averageplaybackquality M differentbitrateswhereachunkencodedatahigherbitrate which is a function of the bitrates of the chunks viewed by hasalargersizeinbitsanditsplaybackprovidesabetteruser the user and (2) fraction of time spent not rebuffering. To experience and higher utility. Suppose the size (in bits) of a formalize these metrics, we consider a time-slotted represen- chunk encoded at bitrate index m is S bits2 and suppose m tation of our system model. The timeline is divided into non- the utility derived by the user from viewing it is given by υ m overlapping consecutive slots of variable length and indexed where m ∈ {1,2,...,M}. WLOG, let the chunk bitrates be byk ∈{1,2,...}.Slotkstartsattimet andisT =t −t non-increasing in index m. Then, the following holds. k k k+1 k secondslong.Weassumethatt =0.Atthebeginningofeach 1 υ ≥υ ≥...≥υ ⇐⇒S ≥S ≥...≥S . (1) slot, the video player makes a control decision on whether it 1 2 M 1 2 M should start downloading a new chunk, and if yes, its bitrate. Note that the actual encoding bitrate for bitrate index m is If a download decision is made, then a request is sent to the given by S /p bits/second. m server and the download starts immediately5. This download Video Player: The video player downloads successive takes T seconds and is completed at the end of slot k. Note k chunks of the video file from the server and plays back that T is a random variable whose actual value depends on k the downloaded chunks to the user. Each chunk must be the realization of the ω(t) process as well as the choice of downloaded in its entirety before it can be played back. We chunk bitrate. If the player decides not to download a new assumethattheplayersendsrequeststotheservertodownload chunk in slot k (for example, when the buffer is full), then one chunk at a time. Also, the chunks are downloaded in the this slot lasts for a fixed duration of ∆ seconds. same order as they are played back. The video player has a We define the following indicator variable for each slot k: finite buffer of size Q chunks3 to store the downloaded max  1 if the player downloads a chunk but yet-to-be-played-back chunks. Measuring the buffer in  a (t )= of bitrate index m in slot k, and (3) chunksisequivalenttomeasuringitinsecondssincethechunk m k duration p is fixed. If the buffer is full the player cannot  0 otherwise. download any new chunks and waits for a fixed period of Then, for all k, we must have (cid:80)M a (t )≤1. Moreover, time given by ∆ seconds before attempting to download a when (cid:80)M a (t ) = 0, then nmo=1chumnkskare downloaded. new chunk. The chunks that are fully downloaded are played m=1 m k Let K denote the index of the slot in which the Nth (i.e., back at a fixed rate of 1/p chunks/second without any idling. N last) chunk is downloaded. Also, denote the time at which When sending a download request for a new chunk, the the player finishes playing back the last chunk by T . Then end player also specifies the desired bitrate for that chunk. This the first performance metric of interest is the time-average enables the player to tradeoff the overall video quality with expected playback utility υ which is defined as N the likelihood of rebuffering that occurs when there are no (cid:110) (cid:111) chunksinthebufferforplayback.Notethatwhileeachchunk E (cid:80)KN (cid:80)M a (t )υ (cid:77) k=1 m=1 m k m has a fixed playback time of p seconds, the size of the chunk υN = E{T } (4) (in bits) can be different depending on its bitrate. Thus, the end choice of bitrate for a chunk impacts its download time. where the numerator denotes the expected total utility across Network Model: The available bandwidth (in bits/second) allN chunks.Notethatachunkcanonlybeplayedbackafter ithasbeendownloadedentirely.Thus,T isgreaterthanthe betweentheserverandplayerisassumedtovarycontinuously end in time according to a stationary random process ω(t). We last chunk’s download finish time, i.e., Tend >tKN +TKN. do not make any assumptions about knowing the statistical The second performance metric of interest is the expected properties or probability distribution of ω(t) except that it has fraction of time sN that is spent not rebuffering and can be finite first and second moments as well as a finite inverse interpreted as a measure of the average playback “smooth- secondmoment.Supposetheplayerstartstodownloadachunk ness”. This can be calculated by observing that the actual of bitrate index m at time t. Then the time t(cid:48) when the playback time for all N chunks is Np seconds. Thus, the download finishes satisfies the following: expected playback smoothness sN is given by (cid:110) (cid:111) (cid:90) t(cid:48) E (cid:80)KN (cid:80)M a (t )p Sm = t ω(τ)dτ (2) sN =(cid:77) E{NTepnd} = k=1E{Tme=nd1}m k (5) Let E{ω(t)}=ωavg. Then, E{t(cid:48)−t}=Sm/ωavg. where in the last step we use the relation that Np = (cid:80)KN (cid:80)M a (t )p. Note that T ≥ Np (since at most k=1 m=1 m k end 2Forsimplicity,weassumethatthechunksize(inbits)isSmforallchunks ofagivenbitrateindexm.However,ourframeworkcanbeeasilyextended 4We do not include the secondary objective of avoiding frequent bitrate tothecasewherethechunksizeforthesamebitratecanvaryacrosschunks. switchesinourformulation,butwedealwithitempiricallyinSectionV-E. 3Itiscommonpracticeforvideoplayerstomeasurethebufferinseconds 5Anydelaysassociatedwithsendingtherequestcanbeaddedtotheoverall ofplaybacktimeratherthaninbits. downloadtime. 3 one chunk can be played back at any time), so that s ≤1. besmallerthanυ∗ ands∗ respectivelysincetheoptimalpolicy N Performance Objective: We want to design a control algo- forthefinitebufferconstrainedmodelisratestable.Moreover, rithm that maximizes the joint utility υ +γs subject to the the following can be shown under this relaxation. N N constraints of the model. γ >0 is an input weight parameter Lemma 1: In the large N regime, there exists a buffer- forprioritizingplaybackutilitywiththeplaybacksmoothness. state-independent stationary policy that makes i.i.d. control Thisproblemcanbeformulatedasastochasticoptimization decisionsineveryslotandsatisfiestheratestabilityconstraint problem with a time-average objective over a finite horizon whileachievingtime-averageutilitynosmallerthanυ∗+γs∗. anddynamicprogramming(DP)basedapproachescanbeused Proof: This follows from Theorem 4.5 in [17] and is to solve it [16]. However, traditional DP-based methods have omitted for brevity. two major disadvantages. First, they require knowledge of the Note that such a buffer-state-independent stationary policy distribution of the ω(t) process which may be hard to obtain. is not necessarily feasible for our finite buffer system. Fur- Second, even when such knowledge is available, the resulting ther, calculating it explicitly would require knowledge of DP can have a very large state space. This is because the the distribution of ω(t). However, instead of calculating this state space for this problem under a DP formulation would policyexplicitly,wewilluseitsexistenceandcharacterization consist of not only the timeslot index k and value t , but also k per Lemma 1 to design an online control algorithm using the buffer occupancy and the quality types of the chunks in Lyapunov optimization [17]. We will show that this online the buffer. Further, an appropriate discretization of the ω(t) algorithm is feasible for our finite buffer system and achieves process would be required to obtain a tractable solution. a time-average utility that is within O(1/Q ) of υ∗+γs∗ max A. Problem Relaxation without requiring any knowledge of the distribution of ω(t). In order to overcome the above mentioned challenges associated with traditional DP based methods, we take the following approach. We consider this problem in the limiting IV. BOLA:ANONLINECONTROLALGORITHM regime when the video size becomes large, i.e., N → ∞. In this regime, we can get the following two simplifications. First, the optimal control policy becomes independent of the Our online control algorithm for bitrate adaptation makes slot index k. That is, it is sufficient to consider the class of useofthecurrentbufferlevel(measuredinnumberofchunks) stationary (and potentially randomized) algorithms that make that we denote by Q(t ). This is updated at the start of each k control decisions only as a function of the buffer occupancy. slot using the following equation: Second, instead of considering the total playback finish time M Tend, we can consider total download finish time in the Q(t )=max[Q(t )− Tk,0]+ (cid:88) a (t ) (8) objective. Specifically, in the limit N → ∞, the metrics υ k+1 k p m k N m=1 and s can be expressed as N Here, the arrival value into this queue in slot k is given by υ=(cid:77) lim υN = Nl→im∞E(cid:110)K1N (cid:80)(cid:110)Kk=N1(cid:80)Mm=1am(cid:111)(tk)υm(cid:111) (6) (cid:80)sloMmt =k1aanmd(t0k)otwhehriwchisies.1ThifeadedpoawrtnulroeadvadleuceisiisonTkis/pmawdheicihn N→∞ Nl→im∞E K1N (cid:80)Kk=N1Tk represents the total number of chunks (including fractional (cid:110) (cid:111) chunks) that could have departed the buffer in slot k. Note lim E 1 (cid:80)KN (cid:80)M a (t )p s=(cid:77) Nl→im∞sN = N→∞ limKNE(cid:110)k=11(cid:80)KmN=1Tm(cid:111) k (7) athsasutmtheetahcattuathlevabluufefeorfleTvkelisisreivneitailaeldizeadt tthoe0e,nid.eo.,fQsl(ott1)k.=W0e. N→∞ KN k=1 k The Lyapunov optimization-over-renewal-frames method This follows by noting that the difference between the ex- [17] can be used to derive an algorithm that optimizes the pected total playback finish time E{T } and the expected metricsin(6)–(8).Themethodgreedilyminimizestheratioof end (cid:110) (cid:111) totaldownloadfinishtimeE (cid:80)KN T isupperboundedby driftpluspenaltytoframelengthovereachslot.Wenowgive k=1 k a high-level intuition of how to derive the algorithm. In slot a finite value due to the finite buffer size Q . Specifically, max k, the buffer is kept stable by minimizing the drift defined as this upper bound is given by Q p. max E(cid:8)(Q(t )2−Q(t )2)/2|Q(t )(cid:9). Using (8), we achieve Let us denote the optimal time-average values of these k+1 k k metrics in the large N regime under an optimal policy by bufferstabilitybyminimizingQ(tk)((cid:80)Mm=1am−Tk/p).Us- υ∗ and s∗ respectively. Note that while the optimal policy ing (6)–(7), the performance objective to maximize υ+γs in the large N regime does not depend on the slot index, it is achieved by maximizing ((cid:80)Mm=1am(tk)(υm + γp)). can still depend on the buffer occupancy state. To address The expected frame (slot) length has a linear relation to this, we temporarily replace the finite buffer constraint of our (cid:80)Mm=1am(tk)Sm. We use a control parameter V >0 related modelwitharatestabilityconstraint[17].Thisconstraintonly to the maximum buffer size to allow a tradeoff between the requires that the time-average arrival rate into the buffer is buffer size and the distance from the optimal utility. equaltothetime-averageplaybackrate.Itisclearthatoptimal In every slot k, given the buffer level Q(t ) at the start of k time-averagevaluesofthemetricsunderthisrelaxationcannot the slot, our algorithm makes a control decision by solving 4 the following deterministic optimization problem: 1x10-6 6.0 Mbps (cid:80)M a (t )(cid:0)Vυ +Vγp−Q(t )(cid:1) 3.0 Mbps Maximize m=1 m k m k 8x10-7 1.4 Mbps subject to (cid:88)M am(tk(cid:80))≤Mm=11,aamm((ttkk))S∈m{0,1} (9) γVp - Q) / S 6x10-7 th00r..e73s hMMobbldppsss m=1 + 4x10-7 υ V Theconstraintsofthisproblemresultinaverysimplesolution ( 2x10-7 structure. Specifically, the optimal solution is given by: 1) If Q(tk)>V(υm+γp) for all m∈{1,2,...,M}, then 0 the no-download option is chosen, i.e., a (t ) = 0 for 0 5 10 15 20 25 m k all m. Note that in this case T =∆. buffer level (s) k 2) Else, the optimal solution is to download the next chunk Fig.1. Thevalueof(Vυm+Vγp−Q)/Sm fordifferentbitratesdepends atbitrateindexm∗ wherem∗ istheindexthatmaximizes on buffer level. (γp = 5 and V = 0.93.) Note that the buffer level is Qp the ratio (cid:0)Vυ +Vγp−Q(t )(cid:1)/S among all m for seconds. m k m which this ratio is positive. Notice that solving this problem does not require any knowledge of the ω(t) process. Further, the optimal solution bitrate 6 thresholds depends only on the buffer level Q(t ). That’s why we call k ouralgorithmBOLA:BufferOccupancybasedLyapunovAlgo- s) 5 p rithm.ThesepropertiesofBOLAshouldbecontrastedwiththe Mb 4 bpthareonpdaowvsaieiddltahbfloperrebtdhainicsdtiwporniodbtbhlaesfmeodrtchstoarntattrreeogqliuedsieretchisaeixtophnlasicv.ietbpereendicreticoenntolyf bitrate ( 23 The following theorem characterizes the theoretical perfor- 1 mance guarantees provided by BOLA. 0 Theorem 2: Suppose BOLA as defined by (9) is imple- 0 5 10 15 20 25 mented in every slot using a control parameter 0 < V ≤ buffer level (s) Qmax−1. Assume Q(0)=0. Then, the following hold. υ1+γp Fig. 2. BOLA’s bitrate choice as function of buffer level. (γp = 5,V = 1) The queue backlog satisfies Q(tk)≤V(υ1+γp)+1 for 0.93.)NotethatthebufferlevelisQpseconds. all slots k. Further, the buffer occupancy in chunks never exceeds Q . max 2) The time-average utility achieved by BOLA satisfies bitrate likely provides a larger utility gain for the user when p2+Ψ that increase is from 0.5 Mbps to 1.5 Mbps than when it is υBOLA+γsBOLA ≥υ∗+γs∗− (10) 2p2V from 5 Mbps to 6 Mbps. A natural choice for our example is whereΨisanupperboundonE(cid:8)T2(cid:9)underanycontrol the logarithmic utility function: let υm = ln(Sm/SM). Pick k γ =5.0/p and V =0.93. The bitrates and utilities are below. algorithm and is assumed to be finite. Proof: See the Appendix. bitrate(Mbps) 6.000 2.962 1.427 0.688 0.331 Remarks: The performance bounds in Theorem 2 show a S(Mb) 18.00 8.886 4.281 2.064 0.993 υ 2.897 2.192 1.461 0.732 0.000 O(1/V,V) utility and backlog tradeoff that is typical of Lyapunov based control algorithms for similar utility max- For any slot we choose the chunk bitrate to maximize imization problems. Specifically, the time-average utility of (Vυm +Vγp−Q)/Sm for 1 ≤ m ≤ M. Fig. 1 shows the BOLAiswithinanO(1/V)additivetermoftheoptimalutility relationship between the expression and the buffer level Q for and this gap may be made smaller by choosing a larger value different m. The line intersections mark the buffer levels that of V. However, the largest feasible value of V is constrained correspondtodecisionthresholds.Fig.2summarizesBOLA’s by the buffer size and there is a linear relation between them. bitrate choices as a function of the buffer level. Fig.3showshowBOLAworks.Weuseasyntheticnetwork A. Understanding BOLA With an Example bandwidth profile as shown in Fig. 3(a). We can see the We now present a sample run to illustrate how BOLA feedback loop involving the bitrate in (a) and the buffer level works. We slice a 99-second video using 3-second chunks in (b). BOLA chooses the bitrate based directly on the buffer and encode it at five different bitrates. While BOLA only level using Fig. 2. The bitrate affects the download time, thus requires the utilities to be a non-decreasing function of the it indirectly affects the buffer level at the beginning of the chunkbitrate,itisnaturaltoconsiderconcaveutilityfunctions following slot. Finally, when all the chunks are downloaded, with diminishing returns, e.g., a 1 Mbps increase in chunk the video player plays out the chunks remaining in the buffer. 5 TABLEI BITRATESUSEDFORBIGBUCKBUNNYTESTVIDEO 9 download bitrate network bandwidth 8 encoded bitrates Bitrate Bitrate(Mbps) ChunkSizeS(Mb) Utility )bps 7 Inmdex Mean DSetavniadtairodn Mean DSetavniadtairodn =ln(υS/SM) btrate (Mi 456 1234 6522....009002650726 1000....085379698144 118685..81..00860868 3211....266137982312 3322....205168591460 a) 3 5 1.427 0.275 4.281 0.825 1.825 ( 2 6 0.991 0.182 2.973 0.545 1.461 7 0.688 0.120 2.064 0.360 1.096 1 8 0.477 0.096 1.431 0.287 0.729 0 9 0.331 0.054 0.993 0.162 0.364 0 20 40 60 80 100 M =10 0.230 0.038 0.690 0.113 0.000 time (s) TABLEII 25 NETWORKPROFILESFORTHEDASHBENCHMARKS 20 1 3 5 7 9 11 )s Mbps(ms) Mbps(ms) Mbps(ms) Mbps(ms) Mbps(ms) Mbps(ms) el ( 5.0( 38) 5.0( 13) 5.0(11) ev 15 4.0( 50) 4.0( 18) 4.0(13) 9.0( 25) 9.0( 10) 9.0( 6) buffer l 10 321...005(((1780580))) 321...005(((2250880))) 321...005(((122505))) 421...000(((1570050))) 421...000(((12550000))) 421...000(((122305))) (b) 5 23..00(( 8785)) 23..00(( 5288)) 23..00((2105)) 24..00(( 7550)) 24..00((15500)) 24..00((2103)) buffer level 4.0( 50) 4.0( 18) 4.0(13) decision thresholds 0 0 20 40 60 80 100 ∆ seconds. Rather than picking an arbitrary value for ∆, time (s) we use a dynamic wait until Q(t ) ≤ V(υ + γp). This k 1 Fig. 3. Sample video download and playback using BOLA. (a) The video has the same effect as picking a fixed but very small ∆, isencodedat5differentbitrates.Thenetworkbandwidthvariesfromhighto so the theoretical analysis still holds. We also implemented low and back to high. The downloaded chunk bitrate adapts to the network bandwidth. (b) The buffer level variation triggers bitrate changes when it other versions of BOLA, namely BOLA-FINITE, BOLA-O, crossesthethresholds. and BOLA-U, that we describe later in this section. A. Test Methodology B. Choosing Utility and Parameters γ and V We simulated all versions of BOLA using the Big Buck Whilewechosealogarithmicutilityfunctionfortheexam- Bunny movie [18]. The 10-minute movie was encoded at 10 ple,avideoprovidercanuseanyutilityfunctionsatisfying(1). differentbitratesandslicedin3-secondchunks.Althougheach The utility function might also take into account system qualityindexhasaspecifiedaveragebitrate,chunksmayhave characteristics such as the type of device a viewer is using. variable bitrate (VBR) because of the varying nature of the γ correspondstohowstronglywewanttoavoidrebuffering. movie. We simulate playback times longer than 10 minutes Increasingγ translatesthegraphsinFigs.1and2totheright, byrepeatingthemovie.Againwechoosealogarithmicutility effectively shifting the thresholds higher without changing function: υ = ln(S /S ). Table I shows the mean and m m M their relative distance. BOLA will thus download more low- standard deviation of the bitrate and chunk size for each bitrate chunks to maintain a larger (and safer) buffer level. quality index and the respective utility values. Increasing V expands the graphs in Figs. 1 and 2 horizon- TheDASHIndustryForumprovidesbenchmarksforvarious tallyabouttheorigin.IfwehaveamaximumbufferlevelQmax aspects of the DASH standard [13]. The benchmarks include we want to avoid downloading unless there is enough space twelve different network profiles. Profiles 1–6 have network for one full chunk on the buffer, that is unless Q≤Qmax−1. bandwidths ranging from 1.5 to 5 Mbps while profiles 7–12 For a given Qmax we can set V =(Qmax−1)/(υ1+γp). havebandwidthsrangingfrom1to9Mbps.Differentlatencies After choosing a utility function, a video provider might are provided for each bandwidth, where the latency is half wanttospecifyasafebufferlevelsuchthatBOLAwillalways the round-trip time (RTT). Table II shows the odd-numbered choosethelowestbitratewhenthebufferfallsbelowthelevel. bandwidth characteristics. Profile 1 spends 30s at each of 5, γ and V can be calculated to satisfy the safe buffer level 4, 3, 2, 1.5, 2, 3 and 4 Mbps respectively, then starts back at constraint and a maximum buffer level constraint. the top. Even-numbered profiles are similar to the preceding odd-numbered profiles but start at the low bandwidth stage. V. IMPLEMENTATIONANDEMPIRICALEVALUATION For example, profile 2 starts at 1.5 Mbps. We first implemented a basic version of BOLA, named In addition, we also tested our algorithms using a set of 86 BOLA-BASIC, directly from (9). Recall that when the buffer 3G mobile bandwidth traces that are publicly available [14]. level is full BOLA does not download a chunk but waits for One trace was excluded because it had an average bandwidth 6 1: r(0,t,b)←{0fort=b=0,−∞otherwise} 2: fornin[1,N]do 3 3: initializer(n,t,b)←−∞forallt,b 4: forall(t(cid:48),b(cid:48))suchthatr(n−1,t(cid:48),b(cid:48))>−∞do 2.5 y 56:: forxm←in[d1o,wMnl]oaddotime(n,t(cid:48),m) utilit 2 7: xδ ←(cid:98)x/δ(cid:99)·δ ge 8: x(cid:48)δ ←max[xδ,b(cid:48)+p−bmax] era 1.5 9: y←max[x(cid:48) −b(cid:48),0] v δ a 10: t←t(cid:48)+x(cid:48) e- 1 1112:: br(cid:48)←←br(cid:48)(−nx−δ(cid:48)δ1+,ty(cid:48),b(cid:48))+υm−γy tim 0.5 1312000 mmmiiinnnuuuttteeesss BBBOOOLLLAAA---BBBAAASSSIIICCC 13: r(n,t,b)←max[r(n,t,b),r(cid:48)] offline optimal bound 14: endfor 0 15: endfor 0 10 20 30 40 50 60 70 16: endfor maximum buffer size (s) r(N,t,b) 17: r∗←max (t,b) (t+b) Fig.5. Time-averageutilityforγp=5usingprofile1forBOLA-BASIC. Fig.4. CalculatingtheOfflineOptimalUtilityUpperBound 1: fornin[1,N]do 2: t←min[playtimefrombegin,playtimetoend] 3: t(cid:48)←max[t/2,3p] of 80 kbps; our lowest video bitrate is 230 kbps. Since the 4: QDmax←min[Qmax,t(cid:48)/p] traces do not include latency measurements, we used 50 ms 5: VD←(QDmax−1)/(υ1+γp) latencygivingaRTTof100msthroughout.Thisisthemedian 6: m∗[n]←argmax(VDυm+VDγp−Q)/Sm m RTT measured empirically in [19]. 7: ifm∗[n]<m∗[n−1]then 8: r←bandwidthmeasuredwhendownloadingchunk(n−1) B. Computing an Upper Bound on the Maximum Utility 9: m(cid:48)←minmsuchthatSm/p≤max[r,SM/p] 10: ifm(cid:48)≤m∗[n]then InordertoevaluatehowwellBOLAperformsonthetraces, 11: m(cid:48)←m∗[n] it is important to derive an upper bound on the maximum 12: elseifm(cid:48)>m∗[n−1]then 13: m(cid:48)←m∗[n−1] utilitythatisobtainablebyanyalgorithmonagiventrace.We 14: elseifsomeutilitysacrificedforfeweroscillationsthen deriveanofflineoptimalalgorithmthatprovidesthemaximum 15: pauseuntil(VDυm(cid:48)+VDγp−Q)/Sm(cid:48) ≥ (cid:46)BOLA-O achievable utility using dynamic programming. We define a (VDυm(cid:48)−1+VDγp−Q)/Sm(cid:48)−1 16: else table r(n,t,b) that contains the maximum utility possible 17: m(cid:48)←m(cid:48)−1 (cid:46)BOLA-U when we download the nth chunk and finish at time t with 18: endif buffer level b. We initialize the table with r(0,0,0) = 0. Let 19: m∗[n]←m(cid:48) 20: endif x(n,t,m) be the time to download the nth chunk at bitrate 21: pauseformax[p·(Q−QD +1),0] max index m starting at time t. Note that the dependency of x on 22: downloadchunknatbitrateindexm∗[n],possiblyabandoning n is due to VBR. We quantize the time with granularity δ. 23: endfor While some accuracy is lost, we ensure the final result will Fig.6. TheBOLAAlgorithm. still be an upper bound by rounding the download time down. xδ(n,t,m)=(cid:98)x(n,t,m)/δ(cid:99)·δ Section V-B. The offline optimal gave nearly the same utility for the different video lengths. BOLA-BASIC only obtains We cap the buffer level at b . max about 80% of the offline optimal bound. Also, the utility x(cid:48)δ(n,t,b,m)=max[xδ(n,t,m),b+p−bmax] of BOLA-BASIC decreases slightly when the buffer size is increasedbecauseitmustdownloadmorelower-bitratechunks Let y(n,t,b,m) be the rebuffering time. during startup before it can reach the buffer levels required y(n,t,b,m)=max[x(cid:48)(n,t,b,m)−b,0] to switch to higher-bitrate chunks. Our results suggests that δ there is room to improve BOLA-BASIC that motivates our We generate entries for r(n,·,·) from r(n−1,·,·) using next version. (cid:16) (cid:17) r(n,t,b)= max r(n−1,t(cid:48),b(cid:48))+υ −γy(n,t(cid:48),b(cid:48),m) m D. Adapting BOLA to Finite-Sized Videos m,t(cid:48),b(cid:48) such that t=t(cid:48)+x(cid:48)(n,t(cid:48),b(cid:48),m) and BOLA-BASIC was derived under the assumption that the δ b=b(cid:48)−x(cid:48)(n,t(cid:48),b(cid:48),m)+y(n,t(cid:48),b(cid:48),m). videos are infinite. Thus, some adaptations are needed for δ The dynamic programming algorithm is shown in Fig. 4. BOLA to work effectively with smaller videos. Motivated by our initial experiments, we implemeted two adaptations to C. Evaluating BOLA-BASIC BOLA-BASIC to derive a version we call BOLA-FINITE. Fig.5showsthetime-averageutilityofBOLA-BASICwhen 1) Dynamic V value for startup and wind down: A large the video length is 10, 30 and 120 minutes. We set γp = 5 buffer allows BOLA-BASIC to perform better but it has two andvariedV fordifferentbuffersizes.Wecomparedtheutility drawbacks.First,ittakeslongertoprimealargebufferduring of BOLA-BASIC with the offline optimal bound described in startup. Lower bitrate chunks are preferred until the buffer 7 12:: funcrtmion←S(HVADLLυAmBA+NVDODNγ(pm−,SQmR))/SmR 3 43:: rremtu(cid:48)r←nt(ruVeDifυmrm(cid:48)(cid:48)+>VrDmγpfo−rsQom)/eSmm(cid:48)(cid:48) subjecttom<m(cid:48)≤M y 2.5 5: endfunction utilit 2 Fig.7. BOLA-FINITE’sDownloadAbandonmentHeuristic:misthecurrent e cchuurrnekntbcihtruantek.and SmR is the number of bits remaining to download in the verag 1.5 e-a 1 10 minutes BOLA-FINITE m 30 minutes BOLA-FINITE ti 120 minutes BOLA-FINITE level reaches steady state. Second, at some late stage all 0.5 30 minutes BOLA-U downloads are complete and any remaining buffered video is offline optimal bound 0 played out. Any available bandwidth during this period is not 0 20 40 60 80 100 utilized. Shortening this period would result in less unutilized maximum buffer size (s) available bandwidth. We mitigate these effects by introducing a dynamic VD which corresponds to a dynamic buffer size Fig.8. Time-averageutilityforγp=5usingprofile1forBOLA-FINITE andBOLA-U. QD , shown in lines 2–5 in Fig. 6. BOLA-FINITE does not max trytofillthewholebuffertoosoonanddoesnottrytomaintain a full buffer too long. We still need a minimum buffer size 3p bitrate switching. We discuss three causes of bitrate switches. for the algorithm to work effectively. 1) Bandwidth variation: As the network conditions change, 2) Download abandonment: BOLA-BASIC takes control the player varies the bitrate, tracking the network bandwidth. decisions just before the download of each chunk. Consider a Suchswitchesareacceptable;theplayerhasnocontrolonthe scenariowheretheplayerisdownloadinghigh-bitrate6Mbps bandwidth and should adapt to different network conditions. chunks in good network conditions. The network bandwidth 2)Densebufferthresholds:Eitheralargernumberofbitrate suddenly drops to 1 Mbps as the player has just started a levels and/or a smaller buffer size may push the threshold new chunk download. The chunk will take 6p seconds to levels closer. If the differences between threshold levels are download, depleting the buffer and possibly causing rebuffer- less than the chunk duration p, adding one downloaded chunk ing. BOLA-FINITE mitigates this problem by monitoring to the buffer may push the buffer level over several threshold download progress and possibly abandoning a download. levels at once. This might cause BOLA-FINITE to overshoot Fig. 7 shows how BOLA-FINITE decides whether or not to and choose a bitrate that is too high for the available band- abandon the download. If a chunk at bitrate index m is being width. Consequently, the chunk download would take much downloaded,theremainingsizeSR islessthanS .Thechunk more than p seconds, leading to excessive buffer depletion, m m can be abandoned and downloaded at some bitrate index m(cid:48) causing BOLA-FINITE to switch down its bitrate by more subject to m<m(cid:48) ≤M when (VDυ +VDγp−Q)/SR < thanonelevel.InsuchascenarioBOLA-FINITEcanoscillate m m (VDυ + VDγp − Q)/S . The control idea remains the betweenbitrates,evenwhentheavailablebandwidthisstable. m(cid:48) m(cid:48) same, but the current bitrate m has a smaller corresponding 3) Bitrate quantization: Having a stable network bandwidth size SR because part of the chunk has already been down- and widely-spaced thresholds still does not avoid all bitrate m loaded.Fig.3illustratesascenariowhereabandonmentmight switching. Suppose the bandwidth is 2.0 Mbps and it lies help. At 46s a 3 Mbps chunk download starts. Since there is between two encoded bitrates of 1.5 and 3.0 Mbps. While a bandwidth drop at the time, the chunk takes almost 9s to the player downloads 1.5 Mbps chunks, the buffer keeps download. The buffer is depleted and BOLA-BASIC switches growing. When the buffer crosses the threshold the player to downloading at a bitrate of 0.3 Mbps. BOLA-FINITE with switchesto3.0Mbps,depletingthebuffer.Afterthebuffergets abandonment logic would have detected the rapidly depleting sufficiently depleted, the player switches back to 1.5 Mbps, buffer and stopped the long download, with the system only and the cycle repeats. In this example, a viewer might prefer dropping to the 1.4 and 0.7 Mbps download bitrates in the the video player to stick to the 1.5 Mbps bitrate, sacrificing low-bandwidth period. some utility in order to have fewer oscillations. Or, a viewer Fig. 8 shows the time-average utility of BOLA-FINITE mightwanttomaximizeutilityandplayapartofthevideoin for 10, 30 and 120 minutes of playback time with γp = 5. thehigherbitrateof3.0Mbpsatthecostofmoreoscillations. ComparingwithBOLA-BASICinFig.5,weseethatthetime- WedescribetwovariantsofBOLAbelowtosuiteitherviewer. averageutilityismuchclosertotheofflineoptimalbound.The ThefirstvariantthatwecallBOLA-Omitigatesoscillations benefit of the adjustments is also evident as the buffer grows by introducing bitrate capping (lines 7–20 in Fig. 6) when larger, as there is no significant decrease in utility caused by switching to a higher bitrate. BOLA-O verifies that the higher filling the buffer with low-bitrate chunks in the earlier stages bitrate is sustainable by comparing it to the bandwidth as of the video. measured when downloading the previous chunk (lines 8– 11). Since the motive is to limit oscillations rather than to E. Avoiding Bitrate Oscillations predict future bandwidth, this adaptation does not drop the While our performance objective optimizes playback utility bitrate to a lower level than in the previous download (lines andplaybacksmoothness,usersarealsosensitivetoexcessive 12–13). Continuous downloading at a bitrate lower than the 8 3 Offline OptimalBound BOLA-O BOLA-U y 2.5 te utili 2 g a er 1.5 v a e- 1 m ti 0.5 0 1 2 3 4 5 6 7 8 9 10 11 12 3G network profile index Fig. 9. The time-average utility of BOLA-O and BOLA-U with γp = 5 and a 25-second buffer playing a 30-minute video for the DASH test network profiles1–12andmobiletraces(3G).BOLAutilityiswithin84–95%ofofflineoptimalutility. 1 s) BOLA-O BOLA-U ELASTIC PANDA p b M 0.8 e( g n a 0.6 h c e bitrat 0.4 e ag 0.2 er v a 0 1 2 3 4 5 6 7 8 9 10 11 12 3G network profile index Fig.10. TheaveragebitratechangebetweenadjacentchunkswassmallerforBOLA-OthanforBOLA-U,butsomebitratechangeisneededtoaccurately trackthenetworkbandwidth.Inourexperiments,ELASTICandPANDAtrackedthebandwidthlessaccuratelythanBOLA-O. bandwidth would cause the buffer to keep growing. BOLA-O because of network bandwidth variations. avoids this by allowing the buffer to slip to the appropriate threshold before starting the download (line 15). F. Comparison With State-of-the-Art Algorithms The second variant that we call BOLA-U does not sacrifice We now compare BOLA with two state-of-the art algo- utility. Excessive buffer growth is avoided by allowing the rithms, ELASTIC [9] and PANDA [10]. We use the default bitrate to be one level higher than the sustainable bandwidth design parameters in [9] and [10]. We test both BOLA-O and (line 17). This allows the player to choose 3 Mbps in the BOLA-U.AlthoughBOLAperformsbetterwithlargerbuffers, example. While BOLA-U does not handle the third type of welimitedthebuffersizeto25sfortheteststoensurefairness. oscillations, it handles the more severe second type. ELASTIC targets a buffer level of 15s but the buffer level Looking back at Fig. 8, we see that the added stability of varies higher. PANDA targets a minimum buffer level of 26s. BOLA-UpaysoffwhenusingasmallbuffersizeandBOLA-U Fig. 11 compares the algorithms using each of the 12 achievesalargerutilitythanBOLA-FINITE.Fig.9showsthe network profiles and the mobile traces. BOLA-U consistently time-average utility of BOLA-O and BOLA-U with γp = 5 performs significantly better than PANDA. While BOLA-U and Qmaxp=25s playing a 30-minute video. The utility lost and ELASTIC perform similarly for profiles 1–6, BOLA-U byBOLA-Otoavoidoscillationsisclearlyevident.Inpractice performs significantly better for the other profiles that have the lost utility is limited by the distance between encoded larger bandwidth variations. Recall that BOLA-O always per- bitrates; if the next lower bitrate level is not far from the forms within a small margin of BOLA-U in Fig. 9. network bandwidth, then little utility will be lost. Since ELASTIC and PANDA were not designed for the We measure oscillations by comparing consecutive chunks. utilityscorewerepeatthecomparisonusingtheaveragebitrate The change in bitrate between a chunk and the next is the and rebuffering metrics in Fig. 12. For profiles 1–6, BOLA-U absolute difference between bitrates (in Mbps) of the two has approximately the same bitrate as ELASTIC. ELASTIC chunks. Fig. 10 shows the bitrate change averaged across all has a higher bitrate for profiles 7–12, but that comes at a thechunks.WhileBOLA-Uhasahighaveragebitratechange significant cost in terms of rebuffering. For these profiles, the because of the quantization, BOLA-O only switches bitrate ratio of the rebuffering time to the play time is more than 9 3 BOLA-U ELASTIC PANDA y 2.5 te utili 2 g a er 1.5 v a e- 1 m ti 0.5 0 1 2 3 4 5 6 7 8 9 10 11 12 3G network profile index Fig. 11. The time-average utility of BOLA-U, ELASTIC and PANDA with γp=5 playing a 30-minute video for the DASH test network profiles 1–12 andmobiletraces(3G).ComparedwithELASTICandPANDA,BOLA-Uhasabout1.75timestheutilityoftheotheralgorithmsinroughlyhalfthecases. 5 BOLA-O BOLA-U ELASTIC PANDA s) p b 4 M e( ta 3 bitr e g 2 a er v a a) 1 ( 0 1 2 3 4 5 6 7 8 9 10 11 12 3G network profile index 0.3 atio BOLA-O BOLA-U ELASTIC PANDA yr a pl er/ 0.2 ffu b e e r g 0.1 a er v a b) ( 0 1 2 3 4 5 6 7 8 9 10 11 12 3G network profile index Fig.12. ComparingBOLAwithELASTICandPANDAusingrawmetrics:averagebitrateandrebuffer-to-playratio.BOLAandPANDAdonotrebuffer forprofiles1–12.ELASTIChasalmostnorebufferingforprofiles1–6,butithasarebuffer-to-playratiogreaterthan20%forprofiles7–12. 20% for ELASTIC, while BOLA-U has no rebuffering. For of bitrate oscillations. BOLA-U does not perform well in this the 3G traces, ELASTIC has marginally higher bitrate than metric, since it attempts to maximize utility at the cost of BOLA-U but has a 12.0% rebuffer-to-play ratio compared increased oscillations. Comparing BOLA-O with ELASTIC with BOLA-U’s 3.5%. ELASTIC rebuffers significantly more and PANDA, ELASTIC has a lower average change than because it does not react in time when the bandwidth drops. BOLA-O only in the cases where it has a slow reaction and ComparingBOLA-UwithPANDA,bothdonotrebufferfor excessive rebuffering. PANDA has a lower average change profiles1–12.Forthe3Gtraces,BOLA-UandPANDAhavea because it is more conservative and in some cases does not rebuffer-to-playratioof3.5%and2.6%respectively.However, change to a higher bitrate even if that bitrate is sustainable. PANDA has significantly lower bitrate than BOLA-U. The Thus, from our empirical analysis, we can conclude that reasonisthatPANDAismoreconservativeandinsomecases BOLA achieves higher utility, and performs more consistently does not change to a higher bitrate even if it is sustainable. across different scenarios in comparison with ELASTIC and In Fig. 10 we show our results for our secondary metric PANDA. One reason for the consistency of BOLA is that 10