Innovative Schemes for Resource Allocation in the Cloud for Media Streaming Applications

—Media streaming applications have recently attracted a large number of users in the Internet. With the advent of thesebandwidth-intensive applications, it is economically inefficient to provide streaming distribution with guaranteed QoS relying only oncentral resources at a media content provider. Cloud computing offers an elastic infrastructure that media content providers (e.g., Videoon Demand (VoD) providers) can use to obtain streaming resources that match the demand. Media content providers are charged forthe amount of resources allocated (reserved) in the cloud. Most of the existing cloud providers employ a pricing model for the reservedresources that is based on non-linear time-discount tariffs (e.g., Amazon CloudFront and Amazon EC2). Such a pricing scheme offersdiscount rates depending non-linearly on the period of time during which the resources are reserved in the cloud. In this case, an openproblem is to decide on both the right amount of resources reserved in the cloud, and their reservation time such that the financial coston the media content provider is minimized. We propose a simple—easy to implement—algorithm for resource reservation thatmaximally exploits discounted rates offered in the tariffs, while ensuring that sufficient resources are reserved in the cloud. Based onthe prediction of demand for streaming capacity, our algorithm is carefully designed to reduce the risk of making wrong resourceallocation decisions. The results of our numerical evaluations and simulations show that the proposed algorithm significantly reducesthe monetary cost of resource allocations in the cloud as compared to other conventional schemes.Index Terms—Media streaming, cloud computing, non-linear pricing models, network economicsÇ1 INTRODUCTIONMEDIA streaming applications have recently attractedlarge number of users in the Internet. In 2010, thenumber of video streams served increased 38.8 percent to24.92 billion as compared to 2009 [1]. This huge demand createsa burden on centralized data centers at media contentproviders such as Video-on-Demand (VoD) providers tosustain the required QoS guarantees [2]. The problembecomes more critical with the increasing demand forhigher bit rates required for the growing number of higherdefinitionvideo quality desired by consumers. In thispaper, we explore new approaches that mitigate the cost ofstreaming distribution on media content providers usingcloud computing.A media content provider needs to equip its data-centerwith over-provisioned (excessive) amount of resources inorder to meet the strict QoS requirements of streaming traffic.Since it is possible to anticipate the size of usage peaksfor streaming capacity in a daily, weekly, monthly, andyearly basis, a media content provider can make long terminvestments in infrastructure (e.g., bandwidth and computingcapacities) to target the expected usage peak. However,this causes economic inefficiency problems in view of flashcrowdevents. Since data-centers of a media content providerare equipped with resources that target the peakexpected demand, most servers in a typical data-center of amedia content provider are only used at about 30 percent oftheir capacity [3]. Hence, a huge amount of capacity at theservers will be idle most of the time, which is highly wastefuland inefficient.Cloud computing creates the possibility for media contentproviders to convert the upfront infrastructure investmentto operating expenses charged by cloud providers (e.g., Netflix moved its streaming servers to Amazon WebServices (AWS) [4], [5]). Instead of buying over-provisionedservers and building private data-centres, media contentproviders can use computing and bandwidth resources ofcloud service providers. Hence, a media content providercan be viewed as a re-seller of cloud resources, where itpays the cloud service provider for the streaming resources(bandwidth) served from the cloud directly to clients of themedia content provider. This paradigm reduces theexpenses of media content providers in terms of purchaseand maintenance of over-provisioned resources at theirdata-centres.In the cloud, the amount of allocated resources can bechanged adaptively at a fine granularity, which is commonlyreferred to as auto-scaling. The auto-scaling ability ofthe cloud enhances resource utilization by matching thesupply with the demand. So far, CPU and memory are thecommon resources offered by the cloud providers (e.g.,Amazon EC2 [6]). However, recently, streaming resources(bandwidth) have become a feature offered by many cloudproviders to users with intensive bandwidth demand (e.g.,Amazon CloudFront and Octoshape) [5], [7], [8], [9]._ A. Alasaad and H.M. Behairy are with the National Center for Electronics,Communications, and Photonics, King Abdulaziz City for Science andTechnology, Riyadh, Saudi Arabia.E-mail: {alasaad, hbehairy}@kacst.edu.sa._ K. Shafiee and V.C.M. Leung are with the Department of Electrical andComputer Engineering, University of British Columbia, Vancouver, BC,Canada. E-mail : {kshafiee, vleung}@ece.ubc.ca.Manuscript received 7 Nov. 2013; revised 23 Jan. 2014; accepted 24 Mar.2014. Date of publication 10 Apr. 2014; date of current version 6 Mar. 2015.Recommended for acceptance by H. Wu.For information on obtaining reprints of this article, please send e-mail to:reprints@ieee.org, and reference the Digital Object Identifier below.Digital Object Identifier no. 10.1109/TPDS.2014.2316827IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015 10211045-9219 _ 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.The delay sensitive nature of media streaming trafficposes unique challenges due to the need for guaranteedthroughput (i.e., download rate no smaller than the videoplayback rate) in order to enable users to smoothly watchvideo content on-line. Hence, the media content providerneeds to allocate streaming resources in the cloud such thatthe demand for streaming capacity can be sustained at anyinstant of time.The common type of resource provisioning plan that isoffered by cloud providers is referred to as on-demandplan. This plan allows the media content provider to purchaseresources upon needed. The pricing model that cloudproviders employ for the on-demand plan is the pay-peruse.Another type of streaming resource provisioning plansthat is offered by many cloud providers is based on resourcereservation. With the reservation plan, the media contentprovider allocates (reserves) resources in advance and pricingis charged before the resources are utilized (upon receivingthe request by the cloud provider, i.e., prepaidresources). The reserved streaming resources are basicallythe bandwidth (streaming data-rate) at which the cloud providerguarantees to deliver to clients of the media contentprovider (content viewers) according to the required QoS.In general, the prices (tariffs) of the reservation plan arecheaper than those of the on-demand plan (i.e., time discountrates are only offered to the reserved (prepaid)resources). We consider a pricing model for resource reservationin the cloud that is based on non-linear time-discounttariffs. In such a pricing scheme, the cloud serviceprovider offers higher discount rates to the resourcesreserved in the cloud for longer times. Such a pricingscheme enables a cloud service provider to better utilize itsabundantly available resources because it encourages consumersto reserve resources in the cloud for longer times.This pricing scheme is currently being used by many cloudproviders [10]. See for example the pricing of virtualmachines (VM) in the reservation phase defined by AmazonEC2 in February 2010. In this case, an open problem isto decide on both the optimum amount of resourcesreserved in the cloud (i.e., the prepaid allocated resources),and the optimum period of time during which thoseresources are reserved such that the monetary cost on themedia content provider is minimized. In order for a mediacontent provider to address this problem, prediction offuture demand for streaming capacity is required to helpwith the resource reservation planning. Many methodshave been proposed in prior works to predict the demandfor streaming capacity [11], [12], [13], [14].Our main contribution in this paper is a practical—easyto implement—Prediction-Based Resource Allocation algorithm(PBRA) that minimizes the monetary cost of resourcereservation in the cloud by maximally exploiting discountedrates offered in the tariffs, while ensuring that sufficientresources are reserved in the cloud with some level ofconfidence in probabilistic sense. We first describe the systemmodel. We formulate the problem based on the predictionof future demand for streaming capacity (Section 3).We then describe the design of our proposed algorithm forsolving the problem (Section 4).The results of our numerical evaluations and simulationsshow that the proposed algorithms significantly reduce themonetary cost of resource allocations in the cloud as comparedto other conventional schemes.2 RELATED WORKThe prediction of CPU utilization and user access demandfor web-based applications has been extensively studied inthe literature. A prediction method has been proposed withrespect to upcoming CPU utilization pattern demandsbased on neural networking and linear regression that is ofinterest in e-commerce applications [15]. Y. Lee et al. proposeda prediction method based on radial basis function(RBF) networks to predict the user access demand requestfor web type of services in web-based applications [16].Although the demand prediction for CPU utilization andweb applications has been studied for a relatively longperiod of time, the prediction of demand for media streaminghas gained popularity more recently [11], [12], [13], [14].The access behaviour of users in peer-to-peer (P2P) streamingwith time-series analysis techniques using non-stationarytime-series models was predicted in [11]. The method oftime-series prediction based on wavelet analysis was studiedin [12]. In [13], principal component analysis isemployed by the authors to extract the access pattern ofstreaming users. Although most of the above studies predictthe average streaming capacity demands, few papers havealso studied the volatility of the capacity demand, i.e., thedemand variance at any future point in time, which yieldsmore accurate risk factors [14]. The prediction of streamingbandwidth demand is outside the scope of this paper. Inthis work, we formulate the problem considering a givenprobability distribution function of prediction of futuredemand for streaming bandwidth. In addition to demandprediction for resource reservation, other relevant studieshave addressed the appropriate joint reservation of bandwidthresources on multiple cloud service providers withthe purpose of maximizing bandwidth utilization [12], [14].In [17], an adaptive resource provisioning scheme is presentedthat optimizes the bandwidth utilization whilesatisfying the required levels of QoS. Maximization of bandwidthutilization in turn helps cloud service providersreduce their expenses and maximize their revenues. In [18],an optimization framework for making dynamic resourceallocation decisions under risky and uncertain operatingenvironments was developed to maximize revenue whilereducing operating costs. This framework considered multipleclient QoS classes under uncertainty of workloads.Recently, streaming resources (e.g., bandwidth) havebecome a feature offered by many cloud providers to contentproviders with intensive bandwidth demand. Thestreaming of media content to content viewers located atdifferent geographical regions at guaranteed data-rate is apart of the service offered by the cloud provider. The commonway of implementing this service in the cloud is byhaving multiple data-centres inside the networks of theaccess connection providers (e.g., Internet Service Providers,ISPs) located at appropriate geographical locations(Fig. 1) [5], [19], [20]. Cloud service providers may need tonegotiate contracts with a number of ISPs to co-locate theirservers into the networks of those ISPs. In this regard,another group of papers have focused on studying different1022 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015types of contracts between cloud service providers and ISPswith the purpose of minimizing the expenses of cloud providers[21]. However, an interesting design approach is tolook at the resource reservation problem from the viewpointof content providers. Obviously, content providers are moreinterested in minimizing their costs, i.e., the amount ofmoney that they are charged directly by cloud providers.To the best of our knowledge, very few studies haveinvestigated the problem of optimizing resource reservationwith the objective of minimizing the monetary costs for contentproviders. A good example is presented in [22],wherein a resource reservation optimization problem wasformulated to minimize the costs of content providers, socalledcloud consumers, using a stochastic programmingmodel. In the process of problem formulation, uncertaindemand and uncertain cloud providers’ resource prices areconsidered. In contrast, the optimization problem formulatedin our work takes into account a given probability distributionfunction obtained from aforementioned studiesfor the prediction of media streaming demands. Furthermore,the problem of cost minimization is addressed by utilizingthe discounted rates offered in the non-linear tariffs.To the best of our knowledge, none of the previous papershas investigated the problem of cost minimization for mediacontent providers in terms of monetary expenses by takinginto account both the penalties caused by the over-provisionedor under-provisioned reserved resources, and theadvance purchase of resources at cloud providers for justthe right period of time.3 SYSTEM MODEL AND PROBLEM FORMULATIONThe system model that we advocate in this paper for mediastreaming using cloud computing consists of the followingcomponents (Fig. 1)._ Demand forecasting module, which predicts thedemand of streaming capacity for every video channelduring future period of time._ Cloud broker, which is responsible on behalf of themedia content provider for both allocating theappropriate amount of resources in the cloud, andreserving the time over which the required resourcesare allocated. Given the demand prediction, the brokerimplements our proposed algorithm to makedecision on resource allocations in the cloud.Both the demand forecasting module and thecloud broker are located in the media content providersite._ Cloud provider, which provides the streamingresources and delivers streaming traffic directly tomedia viewers.In this paper, we consider the case, wherein the cloudprovider charges media content providers for the reservedresources according to the period of time during which theresources are reserved in the cloud. In this case, the cloudprovider offers higher discount rates to the resourcesreserved in the cloud for longer times.Non-linear time-discount is a very popular pricingmodel. Non-linear tariffs are those with marginal rates varyingwith quantity purchased and time rented. Time discountrates are available in purchasing most types of goods.Products or services with time usage (e.g., rental cars, rentalreal-estates, loans, long distance telephone cards, photocopiers)are typically offered with variety of plans (pricingschemes) depending on the period of time the product isconsumed (reserved). It has been shown that such pricingschemes enable sellers to increase their revenues [23]. Manycloud providers also use such a pricing scheme [10]. See forexample pricing of virtual machines in reservation phasedefined by Amazon EC2 in February 2010. An example oftariffs using such a pricing scheme is shown in Fig. 2. Wecan see that the tariff is a function of both units of allocatedresources and reservation time.We observe the following dilemma: how can the mediacontent provider reserve sufficient resources in the cloud—based on the prediction of future streaming demand—suchthat no resource wastage is incurred, while QoS for theactual (real) streaming traffic is maintained with some levelof confidence (h) in probabilistic sense? Moreover, how canthe media content provider utilize the non-linear tariffs(time discount rates offered to the reserved (prepaid)resources) to minimize its monetary cost?Consider a video channel offered by a media content provider.Let DðtÞ be the actual demand for streaming capacityof the video channel at an instant of time t, and measured asthe number of users that stream the channel at instant oftime t multiplied by the data rate required for every downloadinguser to meet QoS guarantees. It has been shownthat DðtÞ is a random process that follows a log-normalFig. 2. An example of tariffs as function of allocated resources and reservationtime.Fig. 1. System model.ALASAAD ET AL.: INNOVATIVE SCHEMES FOR RESOURCE ALLOCATION IN THE CLOUD FOR MEDIA STREAMING APPLICATIONS 1023distribution with mean E½DðtÞ_ and variance (s) characterizedin [11] and [14], respectively.We denote the amount of streaming bandwidth that themedia content provider allocates in the cloud at any timeinstant t by AllocðtÞ. Since DðtÞ is a random process, themedia content provider needs to maintain reserved resourcesin the cloud AllocðtÞ such that in any instant of time,ProbabilityðDðtÞ _ AllocðtÞÞ _ h; (1)where h is a pre-determined threshold (level of confidence).Note that a higher h means a higher degree ofconfidence, in a probabilistic sense, that the reservedresources in the cloud AllocðtÞ meet the QoS guaranteesfor the actual streaming traffic at any future time instant t.However, increasing h increases the probability of wastageof reserved bandwidth (i.e., over-subscribed cost).Hence, proper selection of h is necessary. We shall proposean algorithm that determines the best value of h inSection 5. In this section, our objective is to find the rightamount of reserved resources and their corresponding reservationtime such that the monetary cost required forstreaming a video content (channel) is minimized giventhe constraint in Eq. (1).4 ALGORITHM DESIGNWe summarize the assumptions that we use in our analysisas follows:1) We assume that upon receiving the resource allocationrequest by the cloud provider from the mediacontent provider, the resources required are immediatelyallocated in the cloud, i.e., updating the cloudconfiguration and launching instances in cloud datacentresincurs no delay.2) Since the only resource that we consider in this workis bandwidth, it would be important to delve intothe relation between the cloud provider and contentdelivery networks (CDN). However, we assume thatthe provisioning of media content to media viewers(clients of the media content provider) located at differentgeographical regions at guaranteed data-rateis a part of the service offered by the cloud provider.The common way of implementing this service inthe cloud is by having multiple data-centres insidethe networks of the access connection providers(e.g., ISPs) located at appropriate geographical locations(Fig. 1) [5], [19], [20].3) We assume that the media content provider ischarged for the reserved resources in the cloudupon making the request for resource reservation(i.e., prepaid resources); and therefore, the mediacontent provider cannot revoke, cancel, or change arequest for resource reservation previously submittedto the cloud.4) In clouds, tariffs (prices of different amount ofreserved resources in $ per unit of reservation time)are often given in a tabular form. Therefore, thecloud service provider requires a minimum reservationtime for any allocated resources, and onlyallows discrete levels (categories) of the amount ofallocated resources in the cloud. See for example thereservation phase in the Amazon CloudFrontresource provisioning plans [7].We take into account the aforementioned constraints andpropose a practical—easy to implement—algorithm forresource reservation in the cloud, such that the financialcost on the media content provider is minimized.Suppose that the media content provider can predict thedemand for streaming capacity of a video channel (i.e., thestatistical expected value of the demand E½DðtÞ_ is known)over a future period of time L using one of the methods in[11], [12], [13], [14]. The content provider reserves resourcesin the cloud according to the predicted demand. The proposedalgorithm is based on time-slots with varied durations(sizes). In every time-slot, the media content providermakes a decision to reserve amount of resources in thecloud. Both the amount of resources to be reserved and theperiod of time over which the reservation is made (durationof time-slots) vary from one time-slot to another, and aredetermined in our algorithm to yield the minimum overallmonetary cost (Fig. 3).We alternatively call a time-slot a window, and denote thewindow size (duration of the time-slot) by w. Since theactual demand varies during a window size, while allocatedresources in the cloud remain the same for the entire windowsize (according to the third assumption above), thealgorithm needs to reserve resources in every window jthat are sufficient to handle the maximum predicteddemand for streaming capacity during that window withsome probabilistic level of confidence h.We denote the amount of reserved resources in window jby Allocj. Since the decision on the amount of reservedresources is affected by the wrong prediction of futurestreaming demand, our on-line algorithm is carefullydesigned to obtain accurate demand prediction (by enablinga mechanism that continuously updates the demand forecastmodule according to the actual demand received at themedia content provider over time) in order to reduce therisk of making wrong resource reservation decisions (Fig. 1).We denote the monetary cost of the reserved resourcesduring window j by Costðwj;AllocjÞ, and can becomputed asCostðwj; AllocjÞ ¼ tariffðwj; AllocjÞ _ wj; (2)where tariffðwj; AllocjÞ represents the price (in $ per timeunit) charged by the cloud provider for amount of resourcesFig. 3. PBRA algorithm design.1024 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015Allocj reserved for period of time (window size) wj. Notethat the values of tariff and Cost in any window j dependon both the amount of allocated resources (Allocj) and theperiod of time over which resources are reserved (wj). Alsonote that the algorithm runs on-the-fly. More specifically,the demand forecast module predicts streaming capacitydemand in the upcoming period of time L and feeds thisinformation to our algorithm. The algorithm upon receivingthe demand prediction, computes the right size of windowj (i.e., w_j ), and the right amount of reserved resources inwindow j (i.e., Alloc_j ), such that the cost of the reservedresources during window j (i.e., Costðwj; AllocjÞ in (2)) isminimized; or equivalently, the discounted rates offered inthe tariffs are maximally utilized.Hence, the objective of our algorithm is to minimizeCostðwj; AllocjÞ 8j, subject toProbabilityðDðtÞ _ AllocðtÞÞ _ h; 8 t 2 L:In other words, our objective is to minimize the monetarycost of reserved resources such that the amount of reservedresources at any instant of time is guaranteed to meet theactual demand with probabilistic confidence equals to h. Aswe have discussed earlier, DðtÞ is a random process that followsa log-normal distribution with mean E½DðtÞ_ and variance(s) characterized in [11] and [14], respectively. Thus,using the constraint above, and for any window size wj, wecan compute the minimum amount of required reservedresources during window j (Allocj) by solving the followingformula for AllocjZAllocj01x _ sffiffiffiffiffiffi2p p e       1 2ðlnðxÞ       mmaxs Þ2dx ¼ h; (3)where mmax is the maximum value of the predictedstreaming demand during the window j (i.e., mmax ¼ argmaxðE½DðtÞ_Þ 8 t 2 wj). Note that the Equation (3) followsfrom the log-normal probabilistic distribution of thedemand for streaming capacity.As we have discussed earlier, the cloud service provideroften requires a minimum reservation time for any allocatedresources (wmin), and only allows discrete levels (categories)of reservation times for any amount of allocated resourcesin the cloud. We therefore, assume that any reservationtime required at the cloud has to be in multiplicative orderof wmin (i.e., wj ¼ k _ wmin, where k is a positive integer).Thus, the algorithm employs a trial window (wh) to assist inmaking optimum decision on the size of every window j. Inparticular, for every window j, the algorithm starts an iterationprocess with a trial window of size wh ¼ wmin, andcomputes the cost rate (Xh ¼ tariffðwh; AllochÞ, where h isiteration index), and Alloch is computed by solving Eq. (3)for Alloc.Recall that due to the time discount rates offered in thetariffs, increasing the time during which the allocatedresources are reserved may lead to less monetary cost(higher discounted rate) on the media content provider(Fig. 2). However, increasing the window size (time-slot)significantly may also result in high over-provisioning(over-subscribed) cost as the media content provider has toallocate resources in the cloud that meet the highestdemand during the window period. Thus, in order torecognize whether the cost is decreasing or increasing withincreasing the window size, the trial window size (wh) isincreased one wmin unit in every iteration (i.e.,wh ¼ wh þ wmin) and the cost rate of this new trial windowsize is computed (Xhþ1). The algorithm keeps increasing thetrial window size until wh ¼ L in order to scan the entireperiod of time over which the demand was predicted (L)(Fig. 3), and finds the value of wh that yields the minimumcost; that is the optimum size of window j (w_j ). Since L isthe period of time over which the future demand is predicted,then wmin _ w_j _ L.During every window, the media content providerreceives the real (actual) streaming demand for the videochannel, which may be different from the predicteddemand. According to the actual demand, the demandforecast module updates its prediction and feeds thealgorithm with a newly predicted demand for anotherfuture period of time L (Fig. 1). The algorithm uponreceiving the updated demand prediction, computes theoptimum size of the next window, and reserves optimumresources in the next window, and so on. Thepseudo code for the proposed algorithm is shown inAlgorithm 1. In order to further clarify operations of theproposed algorithm (which we call it Prediction-BasedResource Allocation algorithm), an example is given inthe following.ALASAAD ET AL.: INNOVATIVE SCHEMES FOR RESOURCE ALLOCATION IN THE CLOUD FOR MEDIA STREAMING APPLICATIONS 10254.1 Example: Finding the Right Amount of ReservedResources in Window j and Their ReservationtimeConsider the normalized predicted streaming demandgiven in Fig. 4 for a future period of time L ¼ 12. Letwmin ¼ 1; and let h ¼ 0:75. Assume that the amount ofreserved resources in the cloud can only take integer numbersof unit of resources (i.e., cloud provider applies certainlevels (categories) on the amount of allowed reservedresources, AllocðtÞ 2 f1; 2; 3; . . .g.For the given predicted demand, our algorithm findsthe optimum size of every window j and optimumamount of reserved resources in window j as follows.The algorithm starts iterations to determine the size ofthe first window (i.e., wj¼1). In the first iteration (h ¼ 1),wh¼1 ¼ 1, we can see that the maximum predicteddemand when wh¼1 ¼ 1 is 0:63 (Fig. 4). Thus, we havemmaxh ¼ 0:63. Using Eq. (3), we have Alloch¼1 ¼ 0:81.Since the cloud allows only discrete levels for reservedresources in the cloud, then Alloch¼1 must be rounded tothe nearest upper value allowed in the cloud. Thus,Alloch¼1 ¼ 1. Using tariff functions shown in Fig. 2, wehave the cost rate Xh ¼ tariffðwh¼1 ¼ 1; Alloch¼1 ¼ 1Þ ¼ 11.The iterations continue until wh ¼ L.We summarize the results of all iterations h performedfor window j ¼ 1 using our proposed algorithm in Table 1.From the table, we can see that the minimum value of costrate Xh is when h_ ¼ 10. Hence, the optimum window sizeis w_j ¼1 ¼ wh¼10 ¼ 10, and the optimum amount of reservedresources during window j ¼ 1 is Alloc_j¼1 ¼ Alloch¼10 ¼ 2.Similarly, we can find the optimum window size and optimumamount of resources in the next window (j ¼ 2) givenan updated prediction of the demand in another period offuture time L.5 HYBRID APPROACH FOR RESOURCEPROVISIONINGIn this section, we consider the case, wherein the cloud provideroffers two different types of streaming resource provisioningplans: the reservation plan and the on-demandplan. With the reservation plan, the media content providerreserves resources in advance and pricing is charged beforethe resources are utilized (upon receiving the request at thecloud provider, i.e., prepaid resources). With the ondemandplan, the media content provider allocates streamingresources upon needed. Pricing in the on-demand planis charged by pay-per-use basis. In general, the prices (tariffs)of the reservation plan are cheaper than those of the ondemandplan (i.e., time discount rates are only offered tothe reserved (prepaid) resources). Amazon CloudFront [7],Amazon EC2 [6], GoGrid [24], MS Azure, Op-Source, andTerre-mark are examples of cloud providers which offerInfrastructure-as-a-Service (IaaS) with both plans [10].When the media content provider only uses theresource reservation plan, the under-provisioning problemcan occur if the reserved (prepaid) resources are unable tofully meet the actual demand due to high fluctuatingdemand or prediction mismatch. Also, over-provisioningproblem can occur if the reserved (prepaid) resources aremore than the actual demand, in which parts of thereserved resources are wasted. However, when the cloudprovider offers both the reservation plan and the ondemandplan, the media content provider can allocateresources in the cloud more efficiently. In particular, themedia content provider can use reservation plan to benefitfrom the time-discounted rate, while use the on-demandplan to dynamically allocate streaming resources to its clientsat the moment when the reserved resources allocatedusing the reservation plan are unable to meet the actualdemand and extra resources are needed to fit the fluctuatedand unpredictable demands (e.g., flash crowd). Wecall this approach hybrid resource provisioning. This hybridapproach eliminates both the over-provisioning (over-subscribed)cost and the under-provisioning problem thatmay occur when using the reservation plan only.In this hybrid resource provisioning approach, tradeoffbetween the amount of resources allocated using the ondemandplan and the amount of resources allocated usingthe reservation plan needs to be adjusted in which thehybrid approach can optimally perform. In this section, wepropose an algorithm for this hybrid resource provisioningapproach that maximally benefits from the time discountedrate offered in the resource reservation plan, while eliminatingany over-provisioning cost of reserved resources suchthat the overall monetary cost of resource allocations in thecloud (including both the reserved resources and the ondemandresources) is minimized.Fig. 4. An example of predicted demand over a period of future timeL ¼ 12.TABLE 1Example: Summary of Results for Iterations Executed for Window j ¼ 11026 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015As we have described in the previous section (Section4), the cost of allocated resources using the reservationplan depends on the parameter h. We referred to has the level of confidence. We have shown that usinghigher value of h results in higher amount of reservedresources in the cloud, and vice-versa. However, increasingthe value of h for the reserved resources may lead tothe over-provisioning problem, while decreasing the valueof h may lead to the under-provisioning problem. Sincepricing of resource allocation in the on-demand plan ishigher than the reservation plan, one may erroneouslybelieve that increasing the value of h would alwaysreduce the overall monetary cost since the portion ofreserved (discounted) resources in the cloud is increased.However, reserving too many resources (i.e., using highvalue of h for the reserved (prepaid) resources) may befar from optimal because it may significantly increasethe over-provisioning (over-subscribed) cost. Hence, thishybrid approach requires that the content provider selectthe right value of h for the reserved resources. Our proposedalgorithm in this section computes the optimumvalue of h (h_) that yields the minimum overall monetarycost of resource allocations in the cloud (both reservedand on-demand resources) when the media content provideruses this hybrid resource provisioning approach.Let us again assume that the media content provider canpredict the demand for a future period of time L. Let Chybridbe the price that the media content provider expects topay to the cloud provider for all streaming resource allocatedin the cloud using the hybrid approach (i.e., Chybrid isthe statistical mean of the cost). We can see that Chybrid is thesummation of two terms: the price charged for the reservedresources in every window j using the reservation plan(denoted by CRSVj ), and the expected cost of resources allocatedin the cloud during every window j using the ondemandplan (denoted by CODj ). Hence,Chybrid ¼Xj ðCRSVj þ CODj Þ: (4)Let AllocRSVj be the amount of reserved resources in windowj, while AllocODj be the amount of on-demand resources allocatedin window j. Let tariffðwRSVj ; AllocRSVj Þ be the tariffcharged for the reserved resources in window j, whiletariffðAllocODj Þ be the tariff charged for the on-demandresources in windowj. Note that the cost rate of the resourcesreservation plan, tariffðwRSVj ; AllocRSVj Þ, depends on bothwRSVj and AllocRSVj; while tariffðAllocODj Þ depends only onthe amount of allocated resources AllocODj . This is becauseno time discount rate is offered to the on-demand resources.Let x be a random variable representing the demand forstreaming capacity in any instant of time during window j,and fðxÞ be the probability density function of variable x.Note that when the amount of reserved resources in windowj (AllocRSVj ) is known, CODj can be computed by consideringthe event when AllocRSVj < x < 1. This isbecause when x < AllocRSVj , the amount of reservedresources in the cloud is sufficient to handle the actualstreaming demand and no need to allocate extra resourcesusing the on-demand plan. Thus, we can compute the costof reserved resources in window j (in $) asCRSVj ¼ wj _ tariffðwRSVj ; AllocRSVj Þ; (5)and consequently the expected (statistical mean) cost of theon-demand resources in window j can be computed asCODj ¼ wj _Z1AllocRSVjfðxÞ_tariffðx     AllocRSVj Þ dx:(6)We shall consider a log-normal statistical probability distributionfðxÞ as discussed earlier [11], [14]. Thus, fðxÞ inEq. (6) can be written asfðxÞ ¼1x _ sffiffiffiffiffiffi2p p e       12_ðlnðxÞ      mmaxs Þ2:As we have described in Section 4, the right amount ofreserved resources in window j (AllocRSVj ) can be determinedgiven the parameter h. Thus, Chybrid in Eq. (4) is afunction of the parameter h only. Our objective is to minimizeChybrid in Eq. (4), or equivalently determining the valueof h that minimizes the overall cost of allocated resourcesusing the hybrid approach. It is straight forward to showthat Chybrid is convex with respect to h. Thus, in order tominimize Chybrid, we need to find the optimum value of h(h_) using Equations (5) and (6).We can see that h_ can be easily solved numerically forevery window j if tariff functions are given (i.e.,tariffðt; AllocRSV ðtÞÞ and tariffðAllocODðtÞÞ for any durationof resource allocation). However, as we have discussedearlier, tariffs are often given in a tabular form. Moreover,the cloud service provider often requires a minimum reservationtime for any allocated resources, and only allowsdiscrete levels (categories) of allocated resources in thecloud. We take into account those constraints and proposean efficient heuristic algorithm for this hybridresource provisioning approach. The pseudo code of theproposed algorithms is shown in Algorithm 2.The algorithm works as follows. Suppose that h takesdiscrete values, and the total possible values of h is S. Forevery window j, the iteration process described in Algorithm1 is performed for every value of h in order to computeboth the right amount of reserved resources(AllocRSVj ) and the right time over which these resourcesare reserved (wRSVj ). When the amount of reserved resourcesin window j is determined, the amount of extra resourcesthat must be allocated using the on-demand plan inorder to fulfil the predicted streaming demand can be easilycomputed as AllocODj ¼ mmax      AllocRSVj, where mmaxis the maximum value of the predicted streaming demandduring window j. Thus, the total corresponding cost rateof allocated resources in window j is computed asXh ¼ tariffðRSVj; AllocRSVjÞ þ tariffðAllocODj Þ, where h isthe iteration index. The iteration process continues, andout of all values of Xh computed for different values of h,the algorithm finds h_ corresponding to the minimumvalue. The algorithm is repeated for every window.We can see that the complexity of the proposed algorithm(measured in terms of number of iterations requiredfor every window) is Oð Lwmin _ SÞ. Thus, increasing the size ofALASAAD ET AL.: INNOVATIVE SCHEMES FOR RESOURCE ALLOCATION IN THE CLOUD FOR MEDIA STREAMING APPLICATIONS 1027S increases the complexity of the algorithm, but alsoincreases the accuracy of the algorithm. However, the complexityof our algorithm linearly scales with size of the input(S), which means that our algorithm executes efficiently.6 PERFORMANCE EVALUATIONWe first analytically derive a demand prediction functionthat we shall use in our performance evaluations (Section6.1). We then investigate the performance of our simple“on-line” Prediction-Based Resource Allocation algorithmproposed for reserving resources in the cloud, in terms ofboth monetary cost of reserved resources in the cloud andcomplexity (CPU time) (Section 6.2). We then compare theperformance of PBRA proposed for reserving resources inthe cloud against two other schemes: Fixed window sizeresource reservation scheme, and pay-as-you-go resourceallocation scheme (Section 6.2.2). Finally, we evaluate theperformance of our hybrid resource allocation algorithmproposed for the case when the cloud provider offers twostreaming resource provisioning plans: the reservation andon-demand, and show that our algorithm significantlyreduces the overall cost of resource allocation (Section 6.3).6.1 Demand ModelAs we have discussed so far, prediction of the future demandfor streaming capacity is required in order for the media contentprovider (e.g., VoD) to optimally reserve resources inthe cloud. In this section, we use a special case of the demandin which the function of expected (mean) future streamingdemand for a video channel (i.e., E½DðtÞ_) can be easily formulatedanalytically. Specifically, we assume that all mediastreaming demand for a video channel available at a localVoD provider is generated from users located in a single privatenetwork (e.g., users in a college or office campuses).What distinguishes the evolution of interest in a mediacontent among users of a private network from the Internetis that users in a private network are often socially connected(e.g., friends/colleagues in a social network). Thoseusers form a community and share similar interests. Thus,the demand of a media content grows quickly in the privatenetwork as interested users contact others (by either broadcastingthe knowledge about existence of the media contentto their friends in the social network, e.g., facebook, or usingEmail-group broadcast) and make them interested. However,the interest (demand) tapers off when a certain cumulativelevel of interest among users of the private network isreached. For example, a student, in a class of 100 students,can spread the knowledge about a video content to his classmates.If the popularity of this content among students inthe class is 0.2, the evolution of the demand increasesquickly over time as interested users contact others, buttapers off when all potential number of interested studentsin the class (20 students) get interested in the content andviewed the content. When all 20 students finish viewing thevideo content, the life-time of that content in this communitynetwork expires.We analytically characterize this viral evolution of interestin a media content among users of a private network.Let us assume that the number of friends to whom a user isconnected in a social network (node’s degree) at any instantof time on average is N. Let us further assume that a userwho receives the notification about the existence of the contentgets interested with probability p and re-broadcasts thenotification, in turn, to his friends on the social network,where p is the expected popularity of the content amongusers of the private network. We further assume that userswho receive multiple notifications for the same content donot rebroadcast the message.If the social network graph is fully connected (i.e., a notificationabout existence of the content reaches all users inthe private network), we can then use the fluid-flow modelto write the evolution of interest in a media content asdIðtÞdt ¼ IðtÞ½pðN  gðtÞ _ NÞ_;where IðtÞ be the total number of interested users in the contentat time t (cumulative interest). ðgðtÞ _ NÞ accounts forthe fraction of N users who received multiple notificationsby time instant t, gðtÞ :¼ IðtÞ NT, where NT is the potential numberof users in the network who will ultimately becomeinterested in the content (NT ¼ 100 in Fig. 5), i.e., NT be themaximum expected level of the content cumulative interestin the private network.The above formula is a second order Bernoulli differentialequation and can be solved asIðtÞ ¼NT _ Ið0ÞIð0Þ þ ðNT  Ið0ÞÞe p_N_t ; (7)1028 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015where Ið0Þ be the number of interested users at time t ¼ 0.We note that IðtÞ has an S-shape (Fig. 5). It shows that thenumber of interested users increases quickly when the contentbecomes available and then gradually decreases andtapers off once the level of interest reaches NT . This is similarto the demand function that was obtained using wordof-mouth spread of information by interested users (Bassmodel). Similar interest evolution was also observed whenmeasuring user interest in a video file on YouTube server[25], and when measuring user interest in popular videohosted on a university infrastructure (CoralCDN) [26].Given the evolution of interest in a media content IðtÞ inEq. (7), we can now use fluid-flow model to write the rate atwhich downloading users are completely served (finishdownloading the media content) asdSðtÞdt ¼ mQ _ ½IðtÞ          SðtÞ_;where mQ is the required QoS streaming rate for everydownloading user (measured in bits/second), and SðtÞ isthe number of completely served users at time instant t. Theabove differential equation can be easily solved for SðtÞ.Hence, the expected value of demand for stream capacity ofthe content at any time t (measured in bits/second) isE½DðtÞ_ ¼dSðtÞdt ¼ mQ _ ½IðtÞ  SðtÞ_: (8)6.2 Evaluation of the Algorithm (PBRA) Proposedfor Reserving Resources in the CloudThe algorithm that we evaluate in this section is the veryfirst algorithm that was proposed in Section 4 for resourcereservation in the cloud. We used time-discount rates similarto those used in the pricing model employed by AmazonEC2 [6] in order to derive tariff functions that we used inour evaluations. Those tariffs are non-linear functions ofboth the amount of reserved resources and reservationtime. An example of a tariff function that we used in ourevaluations for units of reserved resources equal to 3 isdepicted in Fig. 6. Note that time discounts are given to thereserved resources. For example, we can see that if themedia content provider wants to reserve (prepaid purchase)3 units of streaming resources for 6 time units, then the tariffis 13 $ per unit of reserved time; whereas the tariff is 14:25 ifthe same amount of resources is reserved for only 1 timeunit. We consider a log-normal probability distribution ofthe demand for streaming capacity with mean (i.e., predicteddemand E½DðtÞ_) computed by Eq. (8) for IðtÞ givenin Fig. 5, mQ ¼ 1, and variance of 3.6.2.1 Performance versus ComplexityAs we have discussed in Section 4, our proposed algorithm(PBRA) employs a trial window wtry with size taking valuesin multiplicative order of wmin, where wmin can be definedas the granularity of the resource allocation in the cloud(i.e., it is the minimum reservation time that the cloud providerrequires for any amount of resource reserved in thecloud), and it is measured in units of time. To investigatethe impact of the value of wmin on the performance of ouralgorithm, we compared the financial cost of media streamingwhen using our algorithm for varied sizes of wmin ath ¼ 0:75. To plot the comparison figure, we computed theratio of the overall cost of resource reservation for everyvalue of wmin to the overall cost when using wmin ¼ 1 (i.e.,normalized cost) (Fig. 7).Fig. 5. The evolution of interest in the video channel.Fig. 6. A tariff function for units of reserved resources equal to 3.Fig. 7. Performance versus complexity of the PBRA algorithm forresource reservation in the cloud.ALASAAD ET AL.: INNOVATIVE SCHEMES FOR RESOURCE ALLOCATION IN THE CLOUD FOR MEDIA STREAMING APPLICATIONS 1029The results show that the algorithm provides the leastcost of resource allocation in the cloud when wmin ¼ 1.Hence, we can see that the finer granularity that we havein resource allocation in the cloud (i.e., the smaller value ofwmin), the better performance we get in our algorithm. Thebetter performance, however, comes at higher algorithmcomplexity, where complexity is measured in terms of totalnumber of iterations (h). We can see that h is higher forsmaller wmin (Fig. 7). However, even for the highest numberof iterations (when wmin ¼ 1), total CPU time was only1:02 second using Intel(R) Core(TM)2 Quad CPU @2.82 GHz. If we compare this execution time with theperiod of time over which the algorithm is operating0 _ tðsecÞ _ 1;000 (Fig. 5), we can see that our algorithmexecutes very efficiently.6.2.2 Comparison with Other Resource ProvisioningAlgorithmsRecall that our proposed algorithm for resource reservationin the cloud (PBRA) is based on windows with variablesizes (i.e., variable time slots as shown in Fig. 3). The sizeof every window and the amount of reserved resources inevery window is determined to minimize the financial coston the media content provider. We evaluate the performanceof our PBRA algorithm against two other resourceprovisioning schemes: fixed window size scheme (denotedby fixed-reserve-time), and the pay-as-you-go resourceallocation scheme which is widely used in the clouds(denoted by pay-as-you-go). The fixed window sizescheme is based on resource reservation wherein all timeslots(windows) are of the same size (i.e., wj is the same8j). The pay-as-you-go scheme is based on on-demandresource allocation wherein resources are allocated uponneeded. The price of reserved resources is less than the ondemandresources since time-discounted rates are onlygiven to the reserved resources.We computed the overall financial cost when using eachof the above schemes for resource allocation in the cloud.To plot the comparison figure, we computed the ratio ofthe overall cost for every value of wmin to the cost whenusing our PBRA algorithm with wmin ¼ 1 (Normalizedcost) (Fig. 8). In the case of Fixed-reserve-time, we set wjalways fixed as wj ¼ wmin 8j, and wj ¼ 10. We can see thatPBRA outperforms the Fixed-reserve-time scheme for allvalues of wmin. This is because PBRA selects window sizesaccording to the predicated demand such that the rightamount of resource is reserved in the cloud that maximallybenefits from the time-discount rates in the tariffs, andensures that reserved resources meet the actual demandwithout incurring wastage. PBRA also outperforms thepay-as-you-go scheme because it maximally benefits fromthe time-discounted rates given to the reserved resources,while no discount is given to resources allocated using theon-demand scheme.6.2.3 Impact of Different Probability Distributions of theDemandIn the next set of evaluations, we considered three log-normalprobability distribution functions for the demand withsame mean but varied variances. The mean of all log-normaldistributions E½DðtÞ_ is given in Eq. (8), where IðtÞ is givenin Fig. 5, mQ ¼ 1, while variances of the log-normal distributionswere set to 3, 6, and 8.The stochastic effect of demand on the cost of reservedresources using PBRA is shown in Table 2 when h ¼ 0:75.We observe that the overall resource reservation costincreases as the variance of the log-normal distributionincreases. This is because larger variance means higher likelihoodthat the reserved resources in the cloud do not meetthe actual demand. Consequently, higher reserved resourcesare required in the cloud to meet the actual demandgiven a certain probabilistic confidence h, which results inhigher cost for resource reservation in the cloud.6.3 Evaluation of the Hybrid Approach for ResourceAllocation in the CloudIn this section, we evaluate the performance of our hybridresource allocation algorithm proposed in Section 5. Ourhybrid approach enables the media content provider to efficientlyallocate resources in the cloud using both the reservationresource provisioning plan and the on-demandresource provisioning plan offered by the cloud provider.As we have discussed in Section 5, the right value ofparameter h has to be determined for this hybrid approachto optimally perform. To investigate the impact of differentvalues of h on the performance of the hybrid approach, weconsidered continuous non-linear tariffs that are functionsof both the allocated resources and reservation time. Weused time-discount rates similar to those used in the pricingmodel employed by Amazon EC2 [6] in order to derive tarifffunctions that we used in our evaluations. Time discountrates are only offered to reserved resources, while no timediscount rates are offered to resources allocated using theon-demand plan. An example of a tariff function that weFig. 8. Performance comparisons.TABLE 2Media Streaming Cost Given Different Probability Distributions of the Demand (in $)1030 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 4, APRIL 2015used in our evaluations for units of allocated resourcesequal 3 is depicted in Fig. 6. Referring to Fig. 6, if the averageunits of resources allocated in the cloud for 6 time unitsusing the on-demand plan is 3, then the cost is 15 _ 6 ¼ $90;whereas if the media content provider reserves (prepaidpurchase) the same amount of resources for 6 time unitsusing the reservation plan, then the price charged is only13 _ 6 ¼ $78.In the next set of simulations, we consider a demandwith mean E½DðtÞ_ given in Eq. (8), where IðtÞ is given inFig. 5, mQ ¼ 1, and variance of 3. Recall that our hybridapproach selects the right value of h in every window. Inevery window j, different values of h are tested to selectsthe one that yields the least overall cost. Table 3 show thecost of resources allocated using both the resource reservationplan and resource on-demand plan when j ¼ 7 (correspondingto t ¼ 650), which results from using our hybridalgorithm. We observe that when h increases, the cost of theresources allocated using the reservation plan increases,while the cost of resources allocated using the on-demandplan decreases. This is because higher amount of reservedresources is required in the cloud for higher h and, consequently,less amount of on-demand resources is needed. Wealso observe that when h increases from 0:75 to 0:8 the overallcost (i.e., the cost of both reservation and on-demandresources) decreases; whereas when h increases beyond 0:8the overall cost increases. This is because the over-subscribed(over-provisioning) cost of the reserved resourcesbecomes very high when h > 0:8. We can see that the optimumvalue of h (i.e., the value of h that yields the least overallcost) when j ¼ 7 is about 0:8.To get a sense of how the optimal selection of thevalue of h can significantly reduce the overall monetarycost on the media content provider when using thishybrid streaming resource provisioning approach, let uscompare the total cost when using our hybrid resourceallocation algorithm at j ¼ 7 against two cases: the casewhen the media content provider uses the on-demandplan only (pay-as-you-go), and the case when the mediacontent provider uses the reservation plan only (fixedreserve-time). We observed that the cost of our hybridapproach when h_ ¼ 0:8 is $45;833; while the cost of allocatedresource in the case of pay-as-you-go is fixed atabout $52;000 (does not depend on the value of h), andthe cost of allocated resources in the case of fixed-reservetimewhen h ¼ 0:8 is about $48;000 (Fig. 9). Hence, ouralgorithm reduces the cost by an amount of about $6;200compared to pay-as-you-go (i.e., about 12 percent cost saving),and reduces the cost by an amount of $2;200 comparedto fixed-reserve-time (i.e., 4:5 percent cost saving).We note here that the cost was computed for onlyone video channel. However, a media content providergenerally offers hundreds of video channels to its clients.Therefore, the overall cost-saving using our proposedalgorithm can be significantly high for large number ofvideo channels offered by the media content provider.7 CONCLUSION AND FUTURE WORKThis paper studies the problem of resource allocations in thecloud for media streaming applications. We have considerednon-linear time-discount tariffs that a cloud providercharges for resources reserved in the cloud. We have proposedalgorithms that optimally determine both the amountof reserved resources in the cloud and their reservationtime—based on prediction of future demand for streamingcapacity—such that the financial cost on the media contentprovider is minimized. The proposed algorithms exploit thetime discounted rates in the tariffs, while ensuring that sufficientresources are reserved in the cloud without incurringwastage. We have evaluated the performance of our algorithmsnumerically and using simulations. The results showthat our algorithms adjust the tradeoff between resourcesreserved on the cloud and resources allocated on-demand.In future work, we shall perform experimental measurementsto characterize the streaming demand in the Internetand develop our own demand forecasting module. We shallalso investigate the case of multiple cloud providers andconsider the market competition when allocating resourcesin the clouds.ACKNOWLEDGMENTSThis work was supported by the National Center of Electronics,Communication, and Photonics at King AbdulazizCity for Science and Technology (Saudi Arabia). This paperwas based in part on a paper appeared in the proceeding ofthe IEEE Globecom 2012.TABLE 3Media Streaming Cost Using Two Resource Allocation Plans Provided by the Cloud (Hybrid Resource Provisioning Approach) (in $)Fig. 9. Hybrid approach performance comparisons.ALASAAD ET AL.: INNOVATIVE SCHEMES FOR RESOURCE ALLOCATION IN THE CLOUD FOR MEDIA STREAMING APPLICATIONS