Advanced Schemes for Resource Allocation in the Cloud for Transport Streaming Applications

Advanced Schemes for Resource Allocation in the Cloud for Transport Streaming Applications

Abstract In present days ,Transport/Media streaming is famous application and emerging trend technology in Internet.These are having different range of Bandwidths. With the advent of these bandwidth-intensive applications, it is economically inefficient to provide streaming distribution with guaranteed QoS relying only on central resources at a media content provider. Cloud computing offers an elastic infrastructure that media content providers (ex: Video on Demand providers) can use to obtain streaming resources that match the demand. Media content providers are charged for the amount of resources allocated in the cloud. Most of the existing cloud providers employ a pricing model for the reserved resources that is based on non-linear time-discount tariffs (ex: Amazon Cloud Front and Amazon EC2). Such a pricing scheme offers discount rates depending non-linearly on the period of time during which the resources are reserved in the cloud. In this case, an open problem is to decide on both the right amount of resources reserved in the cloud, and their reservation time such that the financial cost on the media content provider is minimized. We propose a simple – easy to implement – algorithm for resource reservation that maximally exploits discounted rates offered in the tariffs, while ensuring that sufficient resources are reserved in the cloud. Based on the prediction of demand for streaming capacity, our algorithm is carefully designed to reduce the risk of making wrong resource allocation decisions. The results in this numerical evaluations and simulations show that the proposed algorithm significantly reduce the implementation cost of resource allocations in the cloud as compared to other traditional approaches.

Index Terms Cloud Computing, Media streaming, time- discount tariffs;

1. INTRODUCTION

   Media streaming applications have recently attracted large number of users in the Internet. In 2010, the number of video streams are increased 38.8% to 24.92 billion as compared to 2009 [1]. This huge demand creates a burden on centralized data centers at media content providers such as Video-on-Demand (VoD) providers to sustain the required QoS guarantees [2]. The problem becomes more critical with the increasing demand for higher bit rates required for the growing number of higher-definition video quality desired by consumers. In this paper, we explore new approaches that mitigate the cost of streaming distribution on media content providers using cloud computing.

   A media content provider needs to equip its data-center with over-provisioned (excessive) amount of resources in order to meet the strict QoS requirements of streaming traffic. Since it is possible to anticipate the size of usage peaks for streaming capacity in a daily, weekly, monthly, and yearly basis, a media content provider can make long term investments in infrastructure (e.g., bandwidth and computing capacities) to target the expected usage peak. However, this causes economic inefficiency problems in view of flash-crowd events. Since data-centers of a media content provider are equipped with resources that target the peak expected demand, most servers in a typical data- center of a media content provider are only used at about 30% of their capacity [3]. Hence, a huge amount of capacity at the servers will be idle most of the time, which is highly wasteful and inefficient.

   Cloud computing creates the possibility for media content providers to convert the upfront infrastructure investment to operating expenses charged by cloud providers (e.g., Netflix moved its streaming servers to Amazon Web Services (AWS) [4], [5]). Instead of buying over-provisioned servers and building private data-centers, media content providers can use computing and bandwidth resources of cloud service providers. Hence, a media content provider can be viewed as a re-seller of cloud resources, where it pays the cloud service provider for the streaming resources (bandwidth) served from the cloud directly to clients of the media content provider. This paradigm reduces the expenses of media content providers in terms of purchase and maintenance of over-provisioned re-sources at their data-centers.

   In the cloud, the amount of allocated resources can be changed adaptively at a fine granularity, which is commonly referred to as auto-scaling. The auto-scaling ability of the cloud enhances resource utilization by matching the supply with the demand. So far, CPU and memory are the common resources offered by the cloud providers (e.g., Amazon EC2 [6]). How-ever, recently, streaming resources (bandwidth) have become a feature offered by many cloud providers to users with intensive bandwidth demand (e.g., Amazon Cloud Front and Octoshape) [5], [7], [8], [9].

   The delay sensitive nature of media streaming traffic poses unique challenges due to the need for guaranteed throughput (i.e., download rate no smaller than the video playback rate) in order to enable users to smoothly watch video content on-line. Hence, the media content provider needs to allocate streaming resources in the cloud such that the demand for streaming capacity can be sustained at any instant of time.

   The common type of resource provisioning plan that is offered by cloud providers is referred to as on-demand plan. This plan allows the media content provider to purchase resources upon needed. The pricing model that cloud providers employ for the on-demand plan is the pay- per-use. Another type of streaming resource provisioning plans that is offered by many cloud providers is based on resource reservation. With the reservation plan, the media content provider allocates (reserves) resources in advance and pricing is charged before the resources are utilized (upon receiving the request by the cloud provider, i.e., prepaid resources). The reserved streaming resources are basically the bandwidth (streaming data-rate) at which the cloud provider guarantees to deliver to clients of the media content provider (content view-ers) according to the required QoS.

   In general, the prices (tariffs) of the reservation plan are cheaper than those of the on-demand plan (i.e., time discount rates are only offered to the reserved (prepaid) resources). We consider a pricing model for resource reservation in the cloud that is based on non-linear time- discount tariffs. In such a pric-ing scheme, the cloud service provider offers higher discount rates to the resources reserved in the cloud for longer times. Such a pricing scheme enables a cloud service provider to better utilize its abundantly available resources because it encourages consumers to reserve resources in the cloud for longer times. This pricing scheme is currently being used by many cloud providers [10]. See for example the pricing of Virtual Machines (VM) in the reservation phase defined by Amazon EC2 in February 2010. In this case, an open problem is to decide on both the optimum amount of resources reserved in the cloud (i.e., the prepaid allocated resources), and the optimum period of time during which those resources ae reserved such that the monetary cost on the media content provider is minimized. In order for a media content provider to address this problem, prediction of future demand for streaming capacity is required to help with the resource reservation planning. Many methods have been proposed in prior works to predict the demand for streaming capacity [11].

   Our main contribution in this paper is a practical – easy to implement Prediction-Based Resource Allocation algorithm (PBRA) that minimizes the monetary cost of resource reservation in the cloud by maximally exploiting discounted rates offered in the tariffs, while ensuring that sufficient resources are reserved in the cloud with some level of confidence in probabilistic sense. We first describe the system model. We formulate the problem based on the prediction of future demand for streaming capacity (Section 3). We then describe the design of our proposed algorithm for solving the problem (Section 4).

2. RELATED WORK

   The prediction of CPU utilization and user access demand for web-based applications has been extensively studied in the literature. A prediction method has been proposed with respect to upcoming CPU utilization pattern demands based on neural networking and linear regression that is of interest in e-commerce applications [15]. Y. Lee et al. proposed a prediction method based on Radial Basis Function (RBF) net-works to predict the user access demand request for web type of services in web-based applications [16].

   Although the demand prediction for CPU utilization and web applications has been studied for a relatively long period of time, the prediction of demand for media streaming has gained popularity more recently [11]-[14]. The access behavior of users in Peer-to-Peer (P2P) streaming with time-series analysis techniques using non- stationary time-series models was predicted in [11]. The method of time-series pre-diction based on wavelet analysis was studied in [12]. In [13], principal component analysis is employed by the authors to extract the access pattern of streaming users. Although most of the above studies predict the average streaming capacity demands, few papers have also studied the volatility of the capacity demand, i.e., the demand variance at any future point in time, which yields more accurate risk factors [14]. The prediction of streaming bandwidth demand is outside the scope of this paper. In this work, we formulate the problem considering a given probability distribution function of prediction of future demand for streaming bandwidth. In addition to demand pre-diction for resource reservation, other relevant studies have addressed the appropriate joint reservation of bandwidth resources on multiple cloud service providers with the purpose of maximizing bandwidth utilization [12], [14]. In [17], an adaptive resource provisioning scheme is presented that optimizes the bandwidth utilization while satisfying the required levels of QoS. Maximization of bandwidth utilization in turn helps cloud service providers reduce their expenses and maximize their revenues. In [18], an optimization framework for making dynamic resource allocation decisions under risky and uncertain operating environments was developed to maximize revenue while reducing operating costs. This frame-work considered multiple client QoS classes under uncertainty of workloads Recently,

   streaming resources (e.g., bandwidth) have become a feature offered by many cloud providers to content providers with intensive band-width demand. The streaming of media content to content viewers located at different geographical regions at guaranteed data-rate is a part of the service offered by the cloud provider. The common way of implementing this service in the cloud is by having multiple data-centers inside the networks of the access connection providers (e.g., Internet Service Providers, ISPs) located at appropriate geographical locations (Fig. 1) [5], [19]. Cloud service providers may need to negotiate contracts with a number of ISPs to co- locate their servers into the networks of those ISPs. In this regard, another group of papers have focused on studying different types of contracts between cloud service providers

   account a given probability distribution function obtained from aforementioned studies for the prediction of media streaming demands. Furthermore, the problem of cost minimization is ad-dressed by utilizing the discounted rates offered in the non-linear tariffs. To the best of our knowledge, none of the previous papers has investigated the problem of cost minimization for media content providers in terms of monetary expenses by taking into account both the penalties caused by the over-provisioned or under-provisioned reserved resources, and the advance purchase of resources at cloud providers for just the right period of time.

   Cloud providers infrastructure

   Cloud

   and ISPs with the purpose of minimizing the expenses of cloud providers . How-ever, an interesting design approach is to look at the resource reservation problem from the viewpoint of content providers. Obviously, content

   provider

   Media

   r

   ISP A

   Server

   ISP B

   Server

   ISP C

   providers are more interested in minimizing their costs, i.e., the amount of money that they are charged directly by cloud providers.

   To the best of our knowledge, very few studies have investigated the problem of optimizing resource reservation with the objective of minimizing the monetary costs for content providers. A good example is presented in [17], wherein a resource reservation optimization problem was formulated to minimize the costs of content providers, so- called cloud consumers, using a stochastic programming

   Cloud

   broker Content Provider

   Demand

   PBRAforecast module

   Fig. 1. System model

   media stream

   Demand for media

   media veiwer

   streaming

   model. In the process of problem formulation, uncertain demand and uncertain

3. SYSTEM MODEL AND PROBLEM FORMU-

LATION

The system model that we advocate in this paper for media streaming using cloud computing consists of the following components (Fig. 1).

Demand forecasting module, which predicts the demand of streaming capacity for every video channel during future period of time.

Cloud broker, which is responsible on behalf of the media content provider for both allocating the appropriate amount of resources in the cloud, and reserving the time over which the required resources are allocated. Given the demand pre-diction, the broker implements our proposed algorithm to make decision on resource allocations in the cloud.

Both the demand forecasting module and the cloud broker are located in the media content provider site.

Cloud provider, which provides the streaming resources and delivers streaming traffic directly to media viewers.

cloud providers resource prices are considered. In contrast, the optimization problem formulated in our work takes into

In this paper, we consider the case, wherein the cloud

provider charges media content providers for the reserved resources according to the period of time during which the resources are reserved in the cloud. In this case, the cloud provider offers higher discount rates to the resources reserved in the cloud for longer times.

Non-linear time-discount is a very popular pricing model. Non-linear tariffs are those with marginal rates varying with quantity purchased and time rented.

Time discount rates are available in purchasing most types of goods. Products or services with time usage (e.g., rental cars, rental real-estates, loans, long distance telephone cards, photocopiers) are typically offered with variety of plans (pricing schemes) depending on the period of time the product is consumed (re-served). It has been shown that such pricing schemes enable sellers to increase their revenues . Many cloud providers also use such a pricing scheme [10]. See for example pricing ofVirtual Machines (VM) in reservation phase defined by Amazon EC2 in February 2010. An example of tariffs using such a pricing scheme is shown in Fig. 2. We can see that the tariff is a function of both units of allocated resources and reservation time.

We observe the following dilemma: how can the media content provider reserve sufficient resources in the cloud – based on the prediction of future streaming demand – such that no resource wastage is incurred, while QoS for the actual (real) streaming traffic is maintained with some level of confidence (n) in probabilistic sense? Moreover, how can the 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 con-tent provider. Let D(t) be the actual demand for streaming capacity of the video channel at an instant of time t, and measured as the number of users that stream the channel at instant of time t multiplied by the data rate required for every downloading user to meet QoS guarantees. It has been shown that D(t) is a random process that follows a log-normal distribution with mean E[D(t)] &variance() characterized in [11] and [14], respectively.

We denote the amount of streaming bandwidth that the media content provider allocates in the cloud at any time instant t by Alloc(t). Since D(t) is a random process, the media content provider needs to maintain reserved resources in the cloud Alloc(t) such that in any instant of time,

Probability(D(t) <= Alloc(t))>= ; (1)

where is a pre-determined threshold (level of confidence). Note that a higher means a higher degree of confidence, in a probabilistic sense, that the reserved resources in the cloud Alloc(t) meet the QoS guarantees for the actual streaming traffic at any future time instant t. However, increasing increases the probability of wastage of reserved bandwidth (i.e., over-subscribed cost). Hence, proper selection of is necessary. We shall propose an algorithm that deter-mines the best value of in Section 5. In this section, our objective is to find the right amount of reserved resources and their corresponding reservation time such that the monetary cost required for streaming a video content (channel) is minimized given the constraint in

Eq. (1).

16

units of allocated resources = 3 units of allocated resources = 2

tariff ($ per unit time)

tariff ($ per unit time)

14 units of allocated resources = 1

12

10

8

6

2 4 6 8 10 12 14 16 18 20

units of time reserved

Fig. 2. An example of tariffs as function of allocated resources and reservation time.

4 ALGORITHM DESIGN

We summarize the assumptions that we use in our analysis as follows.

1. We assume that upon receiving the resource allocation request by the cloud provider from the media content provider, the resources required are immediately allocated in the cloud, i.e., up-dating the cloud configuration and launching instances in cloud data centers incurs no delay.

2. Since the only resource that we consider in this work is bandwidth, it would be important to delve into the relation between the cloud provider and Content Delivery Networks (CDN). However, we assume that the provisioning of media content to media viewers (clients of the media content provider) located at different geographical regions at guaranteed data-rate is a part of the service offered by the cloud provider. The common way of implementing this service in the cloud is by having multiple data centers inside the networks of the access connection providers (e.g., ISPs) located at appropriate geographical locations (Fig. 1) [5].

3. We assume that the media content provider is charged for the reserved resources in the cloud upon making the request for resource reservation (i.e., prepaid resources); and therefore, the media content provider cannot revoke, cancel, or change a request for resource reservation previously submitted to the cloud.

4. In clouds, tariffs (prices of different amount of reserved resources in $ per unit of reservation time) are often given in a tabular form. Therefore, the cloud service provider requires a minimum reservation time for any allocated resources, and only allows discrete levels (categories) of the amount of allocated resources in the cloud. See for example the reservation phase in the Amazon Cloud Front resource provisioning plans [7].

We take into account the aforementioned constraints and propose a practical – easy to implement – algorithm for resource reservation in the cloud, such that the financial cost on the media content provider is minimized.

Suppose that the media content provider can predict the demand for streaming capacity of a video channel (i.e., the statistical expected value of the demand E[D(t)] is known) over a future period of time L using one of the methods in [11]-[14]. The content provider reserves resources in the cloud according to the predicted demand. The proposed algorithm is based on time-slots with varied durations (sizes). In every time-slot, the media content provider makes a decision to reserve amount of resources in the cloud. Both the amount of resources to be reserved and the period of time over which the reservation is made (duration of time-slots) vary from one time-slot to another, and are determined in our algorithm to yield the minimum overall monetary cost (Fig. 3).

We alternatively call a time-slot a window, and de-note the window size (duration of the time-slot) by w. Since the

actual demand varies during a window size, while allocated resources in the cloud remain the same for the entire window size (according to the third assumption above), the algorithm needs to reserve resources in every window j that are sufficient to handle the maximum predicted demand for streaming capacity during that window with some probabilistic level of confidence .

Alloc(wj)

is carefully designed to obtain accurate demand pre-diction (by enabling a mechanism that continuously updates the demand forecast module according to the actual demand received at the media content provider over time) in order to reduce the risk of making wrong resource reservation decisions (Fig. 1).

We denote the monetary cost of the reserved re-sources during window j by Cost(wj; Allocj), and can be computed as

Alloc3 w3 . w

M-1

Cost(wj; Allocj) = tariff(wj; Allocj)*wj; (2)

where tariff(wj; Allocj) represents the price (in $ per time unit) charged by the cloud provider for amount of resources

Alloc2 w2

w1

Allocj reserved for period of time (window size) wj. Note

Alloc1

wM

t0 L t

wj: the jth window size M: number of windows

Allocj: amount of allocated resources in window j

Fig. 3. PBRA algorithm design

that the values of tariff and Cost in any window j depend on both the amount of allocated resources (Allocj) and the period of time over which resources are reserved (wj). Also note that the algorithm runs on-the-fly. More specifically, the demand forecast module predicts streaming capacity demand in the upcoming period of time L and feeds this information to our algorithm. The algorithm upon receiving the demand prediction, computes the right size of window j

We denote the amount of reserved resources in window j by Allocj. Since the decision on the amount of reserved resources is affected by the wrong prediction of future streaming demand, our on-line algorithm where wmax is the maximum value of the predicted streaming demand during the window j .

As we have discussed earlier, the cloud service provider often requires a minimum reservation time for any allocated resources (wmin), and only allows discrete levels (categories) of reservation times for any amount of allocated resources in the cloud.

(i.e., wj ), and the right amount of reserved resources in window j (i.e., Allocj ), such that th cost of the reserved resources during window j (i.e., Cost(wj; Allocj) in (2)) is minimized; or equivalently, the discounted rates offered in the tariffs are maximally utilized.

Hence, the objective of our algorithm is to minimize Cost(wj; Allocj) 8j, subject to

Probability(D(t)<=Alloc(t))>= ; t L:

In other words, our objective is to minimize the monetary cost of reserved resources such that the amount of reserved resources at any instant of time is guar-anteed to meet the actual demand with probabilistic confidence equals to n . As we have discussed earlier, D(t) is a random process that follows a log-normal distribution with mean E[D(t)] and variance () characterized in [11] and [14], respectively. Thus, using the constraint above, and for any window size wj, we can compute the minimum amount of required reserved resources during window j (Allocj) by solving

the existed formula for Allocj.

We therefore, assume that any reservation time required at the cloud has to be in multiplicative order of wmin (i.e., wj = k*wmin, where k is a positive integer). Thus, the algorithm employs a trial window (wh) to assist in making optimum decision on the size of every window j. In particular, for every window j, the algorithm starts an iteration process with a trial window of size wh = wmin, and computes the cost rate (Xh = tariff(wh; Alloch), where h is iteration index), and Alloch is computed by solving Eq. (3) for Alloc.

Recall that due to the time discount rates offered in the tariffs, increasing the time during which the allocated resources 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 to allocate resources in the cloud that meet the highest demand during the window period. Thus, in order to recognize whether the cost is decreasing or increasing with increasing the window size, the trial window size (wh) is increased one wmin unit in every iteration (i.e., wh = wh

j

j

+wmin) and the cost rate of this new trial window size is com-puted (Xh+1). The algorithm keeps increasing the trial window size until wh = L in order to scan the entire period of time over which the demand was predicted (L) (Fig. 3), and finds the value of wh that yields the minimum cost; that is the optimum size of window j (wj*). Since L is the period of time over which the future demand is predicted, then wminw * L.

During every window, the media content provider receives the real (actual) streaming demand for the video channel, which may be different from the predicted demand. According to the actual demand, the demand forecast module updates its prediction and feeds the

Algorithm 1 Pseudo code for determining final window sizes and final resource allocations in every window.

Given the predicted demand (E[D(t)]) over a future period of time L,

Define:

wh as a trial window size that the algorithm uses to make decision on the optimum size of window j,

wmin as the minimum reservation time that is re-quired by the cloud provider for any amount of resources reserved in the cloud,

j refers to the j-th window,

To compute w and Alloc for every window j, do

wh 0, {initial value} h 1, {start iterations} while wh L, do

wh = wh + wmin, fincrement the trial windowg Compute µmaxh ,

Compute Alloch by solving Eq. (3) for Alloc, Xh = tariff(wh; Alloch),

hh + 1,

end while

XF = argmin(Xh h), {out of all Xh values, find the one with least value}

Find h* corresponding to XF , {pick the value of h

that yields the least XF} w * w *

algorithm with a newly predicted demand for another j h

future period of time L (Fig. 1). The algorithm upon receiving the updated demand prediction, computes the optimum size of the next window, and reserves optimum resources in the next window, and so on. The pseudo code for the proposed algorithm is shown in Algorithm 1. In order to further clarify operations of the proposed algorithm (which we call it Prediction-Based Resource Allocation algorithm PBRA), an example is given in the following.

Example: Finding the right amount of reserved resources in window j and their reservation time

Consider the normalized predicted streaming demand given in Fig. 4 for a future period of time L = 12. Let wmin = 1; and let = 0:75. Assume that the amount of reserved resources in the cloud can only take integer numbers of unit of resources (i.e., cloud provider applies certain levels (categories) on the amount of allowed reserved resources, Alloc(t) {1; 2; 3;…}.

Allocj Alloch j j + 1,

For the given predicted demand, our algorithm finds the optimum size of every window j and op-timum amount of reserved resources in window j as follows. The algorithm starts iterations to determine the size of the first window (i.e., wj=1). In the first iteration (h = 1), wh=1 = 1, we can see that the maximum predicted demand when wh=1 = 1 is 0:63 (Fig. 4). Thus, we have µmaxh = 0:63. Using Eq. (3), we have Alloch=1 = 0:81. Since the cloud allows only discrete levels for reserved resources in the cloud, then Alloch=1 must be rounded to the nearest upper value allowed in the cloud. Thus, Alloch=1 = 1. Using tariff functions shown in Fig. 2, we have the cost rate Xh = tariff(wh=1 = 1; Alloch=1 =

1) = 11. The iterations continue until wh = L.

We summarize the results of alh iterations h per-formed for window j = 1 using our proposed algo-rithm in TABLE 1. From the table, we can see that the minimum value of cost rate Xh is when h* = 10. Hence, the optimum window size is w*j=1 = wh=10 = 10, and the optimum amount of reserved

*

*

resources during window j = 1 is Allocj =1 = Alloch=10 = 2. Similarly, we can find the optimum window size and optimum amount of resources in the next window (j = 2)

given an updated prediction of the demand in another period of future time L.

TABLE 1

Example: Summary of results for iterations executed for window j = 1

3

Predictd demand (E[D(t)]) measured in units of resources

Predictd demand (E[D(t)]) measured in units of resources

2.5

2

1.5

1

0.5

00 2 4 6 8 10 12

units of time

Fig. 4. An example of predicted demand over a period of future time L = 12.

5 HYBRID APPROACH FOR RESOURCE PRO-

VISIONING

In this section, we consider the case, wherein the cloud provider offers two different types of streaming resource provisioning plans: the reservatio plan and the on-demand plan. With the reservation plan, the media content provider reserves resources in advance and pricing is charged before the resources are utilized (upon receiving the request at the cloud provider, i.e., prepaid resources). With the on- demand plan, the media content provider allocates streaming resources upon needed. Pricing in the on- demand plan is charged by pay-per-use basis. In general, the prices (tariffs) of the reservation plan are cheaper than those of the on-demand plan (i.e., time discount rates are only offered to the reserved (prepaid) re-sources). Amazon Cloud Front [7], Amazon EC2 [6], MS Azure, Op-Source, and Terre-mark are examples of cloud providers which offer Infrastructure-as-a-Service (IaaS) with both plans [10].

When the media content provider only uses the resource reservation plan, the under-provisioning problem can occur if the reserved (prepaid) resources are unable to fully meet the actual demand due to high fluctuating demand or prediction mismatch. Also, over-provisioning problem can occur if the reserved (prepaid) resources are more than the actual demand, in which parts of the reserved resources are wasted. However, when the cloud provider offers both the

reservation plan and the on-demand plan, the media content provider can allocate resources in the cloud more efficiently. In particular, the media content provider can use reservation plan to benefit from the time-discounted rate,

while use the on-demand plan to dynamically allocate streaming resources to its clients at the moment when the reserved resources al-located using the reservation plan are unable to meet the actual demand and extra resources are needed to fit the fluctuated and unpredictable demands (e.g., flash crowd). We call this approach hybrid resource provisioning. This hybrid approach eliminates both the over-provisioning (over-subscribed) cost and the under- provisioning problem that may occur when using the reservation plan only.

In this hybrid resource provisioning approach, trade-off between the amount of resources allocated using the on- demand plan and the amount of re-sources allocated using the reservation plan needs to be adjusted in which the hybrid approach can optimally perform. In this section, we propose an algorithm for this hybrid resource provisioning approach that maximally benefits from the time dis- counted rate offered in the resource reservation plan, while eliminating any over-provisioning cost of re-served resources such that the overall monetary cost of resource allocations in the cloud (including both the reserved resources and the on-demand resources) is minimized.

As we have described in the previous section (Section 4), the cost of allocated resources using the reservation plan depends on the parameter . We referred to as the level of confidence. We have shown that using higher value of results in higher amount of reserved resources in the cloud, and vice-versa. However, increasing the value of for the reserved resources may lead to the over-provisioning problem, while decreasing the value of may lead to the under-provisioning problem. Since pricing of resource allocation in the on-demand plan is higher than the reservation plan, one may erroneously believe that in- creasing the value of would always reduce the over-all monetary cost since the portion of reserved (discounted) resources in the cloud is increased. However, reserving too many resources (i.e., using high value of for the reserved (prepaid) resources) may be far from optimal because it may significantly increase the over-provisioning (over- subscribed) cost. Hence, this hybrid approach requires that the content provider select the right value of for the reserved resources. Our proposed algorithm in this section computes the optimum value of (*) that yields the minimum overall monetary cost of resource allocations in the cloud (both reserved and on-demand resources) when the media content provider uses this hybrid resource provisioning approach.

Algorithm 2 Pseudo code for determining optimum resource allocations in the cloud using two resource provisioning plans.

Define:

S as the set of all values of that the algorithm needs to test in order to determine the best amount of allocated resources that minimizes Chybrid,

For every window j, do

for every value in the set S, do

h 1, {start iterations}

*

*

Run Alg1 to find the best size of window j (wj ) and the best amount of resource allocation (Alloc*RSVj ) for this particular value of using the reservation plan, Compute AllocODj =µmax-AllocRSVj , where

µmax is the maximum value of the predicted streaming demand during window j,

Compute Xh = tariff(RSVj; AllocRSVj ) + tariff(AllocODj ),

h h + 1

end for

YF = argmin(Xh h), {out of all values of Xh, find the one with the least value}

Find h* corresponding to YF , {pick the value of h that yields the least YF }

significantly reduces the overall cost of resource allocation (Section 6.3).

1. Demand model

   As we have discussed so far, prediction of the future demand for streaming capacity is required in order for the media content provider (e.g., VoD) to optimally reserve resources in the cloud. In this section, we use a special case of the demand in which the function of expected (mean) future streaming demand for a video channel i.e., (E[D(t)]) can be easily formulated analytically.

   Specifically, we assume that all media streaming demand for a video channel available at a local VoD provider is generated from users located in a single private network (e.g., users in a college or office campuses).

   100

   80

   60

   40

   20

   00 200 400 600 800 1000

   Time

   Fig. 5. The evolution of interest in the video channel

   tariff ($ per unit time)

   tariff ($ per unit time)

   15

   14.5

   14

   6 PERFORMANCE EVALUATION

   We first analytically derive a demand prediction function that we shall use in our performance evaluations (Section 6.1). We then investigate the performance of our simple

   13.5

   13

   12.50

   2 4 6 8

   re rvation

   on-line Prediction-Based Resource Allocation algorithm (PBRA) proposed for reserving resources in the cloud, in terms of both monetary cost of reserved resources in the cloud and complexity (CPU time) (Section 6.2). We then compare the performance of PBRA proposed for reserving resources in the cloud against two other schemes: Fixed window size resource reservation scheme, and pay-as-you- go resource allocation scheme (Section 6.2.2). Finally, we evaluate the performance of our hybrid resource allocation algorithm proposed for the case when the cloud provider offers two streaming resource provisioning plans: the reservation and on-demand, and show that our algorithm

   se time

   Fig. 6. A tariff function for units of reserved resources equal to 3

   What distinguishes the evolution of interest in a media content among users of a private network from the Internet is that users in a private network are often socially connected (e.g., friends/colleagues in a social network). Those users form a community and share similar interests. Thus, the demand of a media content grows quickly in the private network as interested users contact others (by either

   broadcasting the knowledge about existence of the media content to their friends in the social network, e.g., face book, or using Email-group broadcast) and make them interested. However, the interest (demand) tapers off when a certain cumulative level of interest among users of the private network is reached. 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 in

   the evolution of the demand increases quickly over time as interested users contact others, but tapers off when all potential number of interested students in the class(20 students) get interested in the content and viewed the content. When all 20 students finish viewing the video content, the life-time of that content in this community network expires.

   We analytically characterize this viral evolution of interest in a media content among users of a private network. Let us assume that the number of friends to whom a user is connected in a social network (nodes degree) at any instant of time on average is N. Let us further assume that a user who receives the notification about the existence of the content gets interested with probability p and re- broadcasts the notification, in turn, to his friends on the social network, where p is the expected popularity of the content among users of the private network. We further assume that users who receive multiple notifications for the same content do not rebroadcast the message.

   If the social network graph is fully connected (i.e., a notification about existence of the content reaches all users in the private network), we can then use the fluid-flow model to write the evolution of interest in a media content as

   dI(t)/dt = I(t)[p(N- (t) *N)];

   where I(t) be the total number of interested users in the content at time t (cumulative interest). ( (t) N) accounts for the fraction of N users who received multiple notifications by time instant t, (t):=I(t)/NT,

   where NT is the potential number of users in the network who will ultimately become interested in the content (NT = 100 in Fig. 5), i.e., NT be the maximum expected level of the content cumulative interest in the private network.

   The above formula is a second order Bernoulli differential equation and can be solved as

   NT * I(0)

   server , and when measuring user interest in popular video hosted on a university infrastructure.

   Given the evolution of interest in a media content I(t) in Eq. (7), we can now use fluid-flow model to write the rate at which downloading users are completely served (finish downloading the media content)

   as

   dS(t)

   dt = µQ. [I(t)- S(t)];

   where Q is the required QoS streaming rate for every downloading user (measured in bits/second), and S(t) is the number of completely served users at time instant t. The above differential equation can be easily solved for S(t). Hence, the expected value of demand for stream capacity of the content at any time t (measured in bits/second) is

   dS(t)

   E[D(t)] = dt = µQ [I(t) -S(t)]; (8)

2. Evaluation of the algorithm (PBRA) proposed for reserving resources in the cloud

   The algorithm that we evaluate in this subsection is the very first algorithm that was proposed in Section 4 for resource reservation in the cloud. We used time-discount rates similar to those used in the pricing model employed by Amazon EC2 [6] in order to derive tariff functions that we used in our evaluations. Those tariffs are non-linear functions of both the amount of reserved resources and reservation time. An example of a tariff function that we used in our evaluations for units of reserved resources equal to 3 is depicted in Fig. 6. Note that time discounts are given to the reserved resources. For example, we can see that if the media content provider wants to reserve (prepaid purchase) 3 units of streaming resources for 6 time units, then the tariff is 13 $ per unit of reserved time; whereas the tariff is 14:25 if the same amount of resources is reserved for only 1 time unit. We consider a log-normal probability distribution of the demand for streaming capacity with mean (i.e., predicted demand E[D(t)]) computed by Eq. 8 for I(t) given in Fig. (5), Q = 1, and variance of 3.

   of iterations)

   of iterations)

   1.4 2000

   cost

   cost

   1.3 1500

   Complexity (number

   Complexity (number

   I(t) =

   I(0) + (NT-I(0))e-p* N* t

   (7)

   1.2 1000

   where 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 the number of interested users increases quickly when the content becomes available and then gradually decreases and tapers off once the level of interest reaches NT . This is similar to the demand function that was obtained using word-of-mouth spread of information by interested users (Bass model). Similar interest evolution was also observed when measuring user interest in a video file on YouTube

   1.1 500

   10

   10

   Normalized

   Normalized

   1 2 4 6 8 0

   W

   min

   Fig. 7. Performance vs. complexity of the PBRA algorithm for resource reservation in the cloud

   1. Performance vs. complexity

      As we have discussed in Section 4, our proposed algorithm 2

      (PBRA) employs a trial window wtry with size taking

      values in multiplicative order of w

      min

      , where wmin

      can be

      1.8

      defined as the granularity of the resource allocation in the cloud (i.e., it is the minimum reservation time that the cloud provider requires for any amount of resource reserved in the cloud), and it is measured in units of time. To investigate the impact of the value of wmin on the performance of our algorithm, we compared the financial cost of media streaming when using our algorithm for varied sizes of wmin at = 0:75. To plot the comparison figure, we computed the ratio of the overall cost of resource reservation for every value of wmin to the overall cost when using wmin = 1 (i.e., normalized cost) (Fig. 7).

      The results show that the algorithm provides the least

      1.6

      Normalized cost

      Normalized cost

      1.4

      1.2

      11

      Fixedreservetime Payasyougo PBRA

      2 3 4 5 W 6 7 8 9 10

      min

      Fig. 8. Performance comparisons

      cost of resource allocation in the cloud when wmin = 1. Hence, we can see that the finer granularity that we have in resource allocation in the cloud (i.e., the smaller value of wmin), the better performance we get in our algorithm. The better performance, how-ever, comes at higher algorithm complexity, where complexity is measured in terms of total number of iterations (h). We can see that h is higher for smaller wmin (Fig. 7). However, even for the highest number of iterations (when wmin = 1), total CPU time was only 1:02 second using Intel(R) Core(TM)2 Quad CPU @ 2.82GHz. If we compare this execution time with the period of time over which the algorithm is operating 0 t(sec) 1000 (Fig. 5), we can see that our algorithm executes very efficiently.

   2. Comparison with other resource provisioning algorithms

      Recall that our proposed algorithm for resource reser- vation in the cloud (PBRA) is based on windows with variable sizes (i.e., variable time slots as shown in Fig. 3). The size of every window and the amount of reserved resources in every window is determined to minimize the financial cost on the media content provider. We evaluate the performance of our PBRA algorithm against two other resource provisioning schemes: fixed window size scheme (denoted by Fixed-reserve-time), and the pay-as-you-go resource allocation scheme which is widely used in the clouds (denoted by Pay-as-you-go). The fixed window size scheme is based on resource reservation wherein all time- slots (windows) are of the same size (i.e., wj is the same j). The pay-as-you-go scheme is based on on-demand resource allocation wherein resources are allocated upon needed. The price of reserved resources is less than the on- demand resources since time-discounted rates are only given to the reserved resources.

      We computed the overall financial cost when using each of the above schemes for resource allocation in the cloud. To plot the comparison figure, we com-puted the ratio of the overall cost for every value of wmin to the cost when using our PBRA algorithm with wmin = 1 (Normalized cost) (Fig. 8).

      In the case of Fixed-reserve-time, we set wj always fixed as wj = wmin j, and wj = 10. We can see that PBRA outperforms the Fixed-reserve-time scheme for all values of wmin. This is because PBRA selects widow sizes according to the predicated demand such that the right amount of resource is reserved in the cloud that maximally benefits from the time-discount rates in the tariffs, and ensures that reserved resources meet the actual demand without incurring wastage. PBRA also outperforms the Pay-as-you-go scheme because it maximally benefits from the time-discounted rates given to the reserved resources, while no discount is given to resources allocated using the on-demand scheme.

   3. Impact of different probability distributions of the demand

      In the next set of evaluations, we considered three log- normal probability distribution functions for the demand with same mean but varied variances. The mean of all log- normal distributions E[D(t)] is given in Eq. 8, where I(t) is given in Fig. (5), µQ = 1, while variances of the log-normal distributions were set to 3, 6, and 8.

      The stochastic effect of demand on the cost of reserved resources using PBRA is shown in TABLE 2 when = 0:75. We observe that the overall resource reservation cost increases as the variance of the log-normal distribution increases. This is because larger variance means higher likelihood that the reserved resources in the cloud do not meet the actual demand. Consequently, higher reserved resources are required in the cloud to meet the actual demand given a certain probabilistic confidence , which results in higher cost for resource reservation in the cloud.

      6.3 Evaluation of the hybrid approach for re-source allocation in the cloud

      In this section, we evaluate the performance of our hybrid resource allocation algorithm proposed in Sec-tion 5. Our hybrid approach enables the media con-tent provider to efficiently allocate resources in the

      TABLE 2

      Media streaming cost given different probability distributions of the demand (in $)

      Distribution	log-normal ( = 3)	log-normal ( = 6)	log-normal ( = 8)
      Cost	34; 457	41; 543	48; 393

      TABLE 3

      Media streaming cost using two resource allocation plans provided by the cloud (hybrid resource provisioning approach) (in $)

      	Cost of reservation plan	Cost of on-demand plan	Total cost
      0:75	34; 457	12; 213	46; 670
      0:8	36; 979	8; 854	45; 833
      0:9	44; 033	2; 821	46; 854
      0:95	46; 324	2; 741	49; 065

      cloud using both the reservation resource provision-ing plan and the on-demand resource provisioning plan offered by the cloud provider.

      As we have discussed in Section 5, the right value of parameter has to be determined for this hybrid approach to optimally perform. To investigate the impact of different values of on the performance of the hybrid approach, we considered continuous non-linear tariffs that are functions of both the allocated re-sources and reservation time. We used time-discount rates similar to those used in the pricing model employed by Amazon EC2 [6] in order to derive tariff functions that we used in our evaluations. Time discount rates are only offered to reserved resources, while no time discount rates are offered to resources allocated using the on-demand plan. An example of a tariff function that we used in our evaluations for units of allocated resources equal 3 is depicted in Fig. 6. Referring to Fig. 6, if the average units of resources allocated in the cloud for 6 time units using the on-demand plan is 3, then the cost is 15 6 = $90; whereas if the media content provider reserves (pre-paid purchase) the same amount of resources for 6 time units using the reservation plan, then the price charged is only 13 6 = $78.

      In the next set of simulations, we consider a demand with mean E[D(t)] given in Eq. 8, where I(t) is given in Fig. (5), µQ = 1, and variance of 3. Recall that our hybrid approach selects the right value of in every window. In every window j, different values of are tested to selects the one that yields the least overall cost. TABLE 3 show the cost of resources allocated using both the resource reservation plan and resource on-demand plan when j = 7 (corresponding to t = 650), which results from using our hybrid algorithm. We observe that when increases, the cost of the resources allocated using the reservation plan increases, while the cost of resources allocated using the on-demand plan decreases. This is because higher amount of reserved resources is required in the cloud for higher and, consequently, less amount of on-demand resources is needed. We also observe that

      when increases from 0:75 to 0:8 the overall cost (i.e., the cost of both reservation and on-demand re-sources) decreases; whereas when increases beyond 0:8 the overall cost increases. This is because the over-subscribed (over-provisioning) cost of the reserved resources becomes very high when > 0:8. We can see that the optimum value of (i.e., the value of that yields the least overall cost) when j = 7 is about

      0:8.

      Fig. 9. performance comparisons

      In the top diagram, a single price (P) is available to all customers. The amount of revenue is represented by area P, A, Q, O. The consumer surplus is the area above line segment P, A but below the demand curve (D).

      With price discrimination, (the bottom diagram), the demand curve is divided into two segments (D1 and D2). A higher price (P1) is charged to the low elasticity segment, and a lower price (P2) is charged to the high elasticity segment. The total revenue from the first segment is equal to the area P1,B, Q1,O. The total revenue from the second segment is equal to the area E, C,Q2,Q1. The sum of these areas will always be greater than the area without discrimination assuming the demand curve resembles a

      rectangular hyperbola with unitary elasticity. The more prices that are introduced, the greater the sum of the revenue areas, and the more of the consumer surplus is captured by the producer.

      To get a sense of how the optimal selection of the value of can significantly reduce the overall monetary cost on the media content provider when using this hybrid streaming resource provisioning approach, let us compare the total cost when using our hybrid resource allocation algorithm at j = 7 against two cases: the case when the media content provider uses the on-demand plan only (Pay- as-you-go), and the case when the media content provider uses the reservation plan only (Fixed-reserve-time). We observed that the cost of our hybrid approach when * = 0:8 is $45; 833; while the cost of allocated resource in the case of Pay-as-you-go is fixed at about $52; 000 (does not depend on the value of ), and the cost of allocated resources in the case of Fixed-reserve-time when = 0:8 is about $48; 000 (Fig. 9). Hence, our algorithm reduces the cost by an amount of about $6,200 compared to Pay-as- you-go (i.e., about 12% cost saving), and reduces the cost by an amount of $2; 200 compared to Fixed-reserve-time (i.e., 4:5% cost saving). We note here that the cost was computed for only one video channel. However, a media content provider generally offers hundreds of video channels to its clients. Therefore, the overall cost-saving using our proposed algorithm can be significantly high for large number of video channels offered by the media content provider.

1. CONCLUSION AND FUTURE WORK

This paper illustrates the problem of resource allocations in the cloud for transport/media streaming applications. We have considered non-linear time-discount tariffs that a cloud provider charges for resources reserved in the cloud. We have proposed algorithms that optimally determine both the amount of rserved resources in the cloud and their reservation time – based on prediction of future demand for streaming capacity – such that the economical cost on the transport content provider is minimized. The proposed algorithms exploit the time discounted rates in the tariffs, while ensuring that sufficient resources are reserved in the cloud without incurring wastage. The results show that our algorithms adjust the trade-off between resources reserved on the cloud and resources allocated on-demand. In future work, we shall perform experimental measurements to characterize the streaming demand in the Internet and develop our own demand forecasting module. We shall also investigate the case of multiple cloud providers and consider the market competition when allocating resources in the clouds.

REFERENCES

1. Cisco Systems Inc., Cisco visual networking index: Forecast and methodology, 2010-2015, white paper, 2010.

2. Y. Liu, Y. Guo, and C. Liang, A survey on peer-to-peer video streaming systems, in Peer-to-Peer Networking and Applications, vol. 18, no. 1, pp. 1828, 2008.

3. Cisco Systems Inc., Data center virtualization and orchestra-tion: Business and financial justification, white paper, 2007.

4. Four Reasons We Choose Amazons Cloud as Our Computing Platform, The Netflix Tech Blog, Dec., 2010.

5. http://www.octoshape.com/

6. Amazon EC2 Reserved Instances, http://aws.amazon.com/ec2/reserved-instances, 2012.

7. Amazon CloudFront, http://aws.amazon.com/cloudfront/, 2012.

8. G. Chuanxiong, G. Lu, H. Wang, S. Yang, C. Kong, P. Sun, W. Wu, and Y. Zhang, SecondNet: a data center network vir-tualization architecture with bandwidth guarantees, in Proc. of the ACM 6th International Conference on emerging Networking EXperiments and Technologies (Co-NEXT), 2010.

9. H. Ballani, P. Costa, T. Karagiannis, and A. Rowstron, To-wards predictable datacenter networks, in Proc. of the ACM SIGCOMM conference, pp. 242253, 2011.

10. E. White, M. OGara, P. Romanski, P. Whitney, Cloud Pricing Models, in Cloud Expo: Article, white paper, 2012. http://java.sys- con.com/node/2409759?page=0,1.

11. D. Niu, Z. Liu, B. Li, and S. Zhao, Demand forecast and performance prediction in peer-assisted on-demand streaming systems, in Proc. of IEEE Infocom conference, pp 421425, 2011.

12. S. Peichang, W. Huaimin, Y. Gang, L. Fengshun, and W. Tianzuo, Prediction-based Federated Management of Multi-scale Resources in Cloud, in AISS: Advances in Infor-mation Sciences and Service Sciences, vol. 4, no. 6, pp. 324334, 2012.

13. G. Gursun, M. Crovella, and I. Matta, Describing and Fore-casting Video Access Patterns, in Proc. IEEE Infocom Mini-Conference, pp. 1620, 2011.

14. D. Niu, H. Xu, B. Li, and S. Zhao, Quality-Assured Cloud Bandwidth Auto-Scaling for Video-on-Demand Applications, in Proc. of IEEE Infocom Conference, pp. 421425, 2012.

15. S. Islam, J. Keung, K. Lee, and A. Liu, Empirical Prediction Models for Adaptive Resource Provisioning in the Cloud, in

    Future Generation Computer Systems, vol. 28, no. 1, pp. 155162, 2012.

16. Y. C. Lee and Y. Albert, Zomaya: Rescheduling for reliable job completion with the support of clouds, in Future Generation Computer Systems, vol. 26, no. 8, pp. 11921199, 2010.

17. A. Filali, A. S. Hafid, and M. Gendreau, Adaptive Resources Provisioning for Grid Applications and Services, in Proc. of ICC Conference, pp. 186 191, 2008.

18. D. Kusic and N. Kandasamy, Risk-Aware Limited Looka-head Control for Dynamic Resource Provisioning in Enterprise Computing Systems, in Cluster Computing, vol. 10, no. 4, pp. 395 408, 2007.

Authors Profile: A.Leelavathi received M.Tech in Computer science and Engineering from JNTUK in 2010, finished M.Sc. (Computer science) from Andhra University in 2003, and B.Sc (Computers) from Andhra University in 2001 . At Present,

working as an assistant professor in CSE Dept of Sri vasavi Engineering College ,Pedatadepalli from 2006. Before that, worked as a Teaching assistant, Lecturer, Assistant professor, with Department of Computer Science in various colleges. Participated in workshops and conducted many campus Placements Technical training programs for students. Name was printed on back side cover page of text book titled Programming in C 2nd Edition by author Reema Thareja from Oxford publications (ISBN 0-19-945614-3) for submission of feedback and topic wise comments and objectives for 1st Edition textbook. Interested areas are object Oriented Programming(C++,Java) and Designing .

Authors Profile: A.Rajesh received M.Tech in Computer science and Engineering from JNTUK in 2010, finished M.Sc. (Computer science) from Andhra University in 2003, and B.Sc. (Computers) from Andhra University in 2001 . At Present,

working as an assistant professor in CSE Dept of Sri vasavi Engg College, Pedatadepalli from 2006. Before that, worked as a Teaching assistant, Lecturer, Assistant professor, with Department of Computer Science in various colleges. Participated in workshops. Interested areas are Network Security,Computer Organization and Embedded Systems .

Authors Profile: R.Sarada received M.Tech in Computer science and Engineering from JNTUK in 2012, finished MCA. (Computer science) from ANU in 2005, and B.Sc. (Computers) from AU in 2002 . At Present, working

as an assistant professor in CSE Dept of Sri vasavi Engg College, Pedatadepalli from 2006. Before that, worked as a Teaching assistant, Lecturer in Department of Computer Science in various colleges.Interested Areas are Database Management and Data Mining