# A Time-Efficient Solution to the General Resource Placement Problem in Cloud

Authors: Wei Wei; Yuhong Zhang; Yang Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Cloud based large-scale online services are faced with
regionally distributed stochastic demands for various resources.
With multiple regional cloud data centers, a crucial problem that
needs to be settled is how to properly place resources to satisfy
massive stochastic demands from many different regions. For the
general stochastic demands oriented cross region resource placement
problem, the time complexity of existing optimal algorithm
is linear to total amount of resources and thus may be inefficient
when dealing with a large number of resources. To end this, we
propose an efficient algorithm, named discrete function based
unbound resource placement (D-URP). Experiments show that
in scenarios with general settings, D-URP can averagely achieve
at least 97% revenue of optimal solution, with reducing time
by three orders of magnitude. Moreover, due to the generality
of problem setting, it can be extended to get efficient solution
for a broad range of similar problems under various scenarios
with different constraints. Therefore, D-URP can be used as
an effective supplement to existing algorithm under time-tense
scheduling scenarios with large number of resources.


---

## Body

## 1. Introduction

Large-scale online services (such as YouTube [1] and Facebook [2]) often face highly dynamic user demands from distributed physical locations. A proper online service can leverage cloud computing to lower cost and serve more users. Based on typical cloud platform like [3, 4], the target of resource scheduling in large-scale online services can be viewed as placing given resources at geographically dispersed data centers and serving as many demands as possible. For a specific request, one prefers to be served in local data center rather than in remote one. This is most obviously because the locality of data centers needs to be considered to guarantee QoS (quality of service). Moreover, under scenarios like online scheduling, a relative high response time is often a must, and it is essential to recompute placement quickly and efficiently to handle high dynamic demands with time. Therefore, how to minimize operation cost and to find optimal placement efficiently in such scheduling scenarios is an impending need to meet in cloud platform.For instance, the cloud based content distribution network can be viewed as an example that falls under above paradigm, where a number of geographically dispersed cloud data centers are selected to be close to end users. Under this scenario, user’s requests are preferred to be served by a local data center, and service provider would like to predistribute content replicas at each data center so as to meet as much content demand as possible in the most efficient way. Another example is cloud based media streaming, in which service provider faces the problem of where to place virtual machine instances, so as to satisfy time-varying bandwidth demands from users spreading across various geographical regions.In above paradigm, online services are faced with stochastic demands which are represented by demand distribution for each resource type in each region. Since we do not suppose stochastic demands to follow a specific distribution, a variety of scenarios can be covered:(1) demands with various patterns and distributions, for example, realistic demand patterns, extracted from a large number of traces in production servers [5], which contains several different kinds of variability, autocorrelation, and periodicity. (2) Demands that vary across data centers, as in [6], and demands in different data centers may be correlated with each other. (3) Demands vary across resources; for example, the demands change significantly across channels in media streaming services like YouTube [7].Summarized from above scenarios, the general resource placement problem can be formulated as follows: given a global resource budget, how to satisfy as many requests as possible by placing resources optimally over regions. Since each request can be satisfied either by the data center in same region with high QoS (i.e., high revenue) or by the data center from a different region with low QoS (i.e., low revenue), algorithm’s aim is to maximize expected revenue of resources.By considering stochasticity of demands, algorithm can be more efficient than prior mean demand based ones. Consider the scenario of placingk resources in a system with two regions and one resource type. Demands from the first region have a deterministic demand of k requests, and the demands from the second region have bursty demands of nk(n>1) requests with probability 1/n and 0 request with probability 1-1/n. The aim of algorithm is to maximize the expected number of satisfied requests (i.e., the revenue). Assuming that one resource can satisfy one request, then the algorithm using stochastic demand will place all k resources in the first region with a revenue of k. In comparison, the algorithm using demands mean will place k/2 resources in each region, yielding a revenue of (n+1)k/2n, which approximates k/2 if n≫1; that is, considering stochasticity in demands may significantly improve utilization of resources.However, stochastic demands will significantly increase computation complexity. It is challenging to efficiently solve a resource allocation problem that combines combinatorial aspects and arbitrary stochastic demand distribution in time-tense scheduling scenarios. To the best of our knowledge, only one SSP (successive shortest path) based optimal algorithm was proposed for a similar stochastic demand based problem [8], whose time complexity, however, is linear to total amount of resources and then may be inefficient when dealing with a large number of resources.To reduce the computational complexity, one can efficiently optimize servicing revenue by utilizing the inner structure of the problem. We develop an efficient placement algorithm accordingly, suitable for time-tense scheduling in large-scale systems. Our paper mainly makes three contributions.(1) We prove that the problem can be transformed to two subproblems, and the solutions to these subproblems can be represented as functions of demands and resources. (2) We derive mathematical description of all necessary functions, to facilitate computation of optimal solution. (3) We develop an efficient discrete function based resource placement algorithm (called D-URP), which gets solution quickly by leveraging discrete functions to approximate continuous ones. Under the scenarios with general settings, we compare the effect and efficiency of D-URP with commonly used mean demand based algorithm and the optimal SSP based algorithm. Our analysis and preliminary experiments indicate that D-URP outperforms mean demand based algorithm under all scenarios and can averagely achieve at least 97% revenue of optimal SSP based algorithm, with time complexity reduced to nearly one thousandth of it. Therefore, it can be used as an effective supplement to existing algorithm in time-tense scheduling scenarios. And due to the generality of problem settings, it can be extended to get efficient solution for a broad range of similar problems under various scenarios with different constraints.


## 2.  Related Work

One part of related works was cloud based resource scheduling for multiple services [9–11]. Reference [9] handled the problem of scheduling multiple resources under budget constraint in one data center. The viewing behaviors of users in a multichannel VoD (video on demand) application were analyzed to get a queueing network and then a dynamic resource provisioning algorithm is provided to reduce cloud utilization cost. Reference [10] investigated the response time and resource cost minimization problem under three typical scenarios: single-service, multiservice, and priority-service scenarios. Queueing model based algorithms were developed to optimally allocate cloud resources for each service in all scenarios. Reference [11] proposed QoS-aware resource elasticity (QRE) framework. Based on the assessment of the application behavior, QRE framework can help dynamic adjust cloud resources.There was also a substantial research effort being made about similar problems of resource consolidation [12, 13]. Reference [12] investigated resource provisioning problem in shared Internet hosting platforms, which was similar to the scenarios in distributed cloud centers. The proposed algorithm overbooked cluster resources in a controlled fashion; thus, it could provide application isolation and performance guarantees at run time. Reference [13] treated virtual machine as “moldable” during consolidation and developed a genetic algorithm to minimize the overhead of transition between system states.Other similar works were cloud based content delivery [14–18]. MetaCDN in [14] intelligently matches and places users’ content onto many storage clouds and exploits the difference in storage cloud to maximize utility functions like quality of service. Reference [15] studied the cost optimization problem in content multihoming scenario, where a content publisher uses multiple CDN to aggregate the diversity of individual CDN providers on features, performance, and commitment. The proposed algorithm can reduce publishing cost by 40%. Reference [16] proposed a hierarchical framework to solve the deployment problem in cloud-oriented content delivery network. In the framework, inter- and intracloud communication resources were simultaneously considered and the problem was transformed to replica placement and graph partitioning problem. Reference [17] handled the problem of efficiently moving the data from different geographical locations into a cloud for further processing. The two proposed online algorithms can efficiently find the optimal routing paths and the right data centers for processing. Reference [18] studied the cost minimization problem of content migration in cloud of clouds. An online heuristic algorithm is proposed to optimize the cost of migration and adapt to the changes of user access pattern.Some related works in P2P (peer-to-peer) systems also investigated similar problems [19, 20]. Reference [19] addressed the problem of content placement in “distributed server networks” scenario of P2P systems, where the content placement strategy can help resolve similar problems in cloud related scenarios. Reference [20] investigated the relationship between the number of videos and peers, the storage capacity of each peer, and the resultant offloading of video server bandwidth. The conclusion can also help design cloud based VoD systems.Most of existing works were carried out only based on mean demands of resource placement. However, a more realistic scenario is that resource demands from massive users are dynamic and stochastic. The main challenge posed by this paradigm is how to deal with an arbitrary multidimensional (high-dimensionality) stochastic demand. A method of resource placement for similar problem is proposed in [8]. The main differences between their problem setting and ours are that their problem setting is for data centers with dedicated servers (with resource constraints in each region), while our setting is for cloud data center (with only a global resource budget). The typical scenario of their problem is placing resources over traditional data centers with limited resources. To solve the problem, they transformed the resource placement problem into min-cost flow one, and the optimal solution can be obtained by a customized version of SSP (successive shortest path) algorithm. But under scenario with large number of resources, the SSP based algorithm is not efficient enough since its time complexity is linear to total amount of resources. Different from the SSP based idea, we propose an efficient algorithm by leveraging the special structure of our problem. The algorithm can achieve at least 97% revenue of optimal solution, and its time complexity is independent of the total amount of resources.


## 3. Problem Formulation

We consider a system consisting ofJ regions indexed by j(1≤j≤J). In each region, one can place multiple resources of different types indexed by i(1≤i≤I). We denote by Lij the amount of type-i resources placed in region j, the set of resources placed in these regions is called aplacement and denoted by P={Lij}, with Li=∑j=1J‍Lij as the total amount of type-i resources. There is no limit on the amount of resources in each region, which is consistent with the model of cloud computing. For a type-i request from region j, if the request is assigned to a type-i resource, it is labelled as “satisfied.” If a type-i request from region j is satisfied, it is assigned to either (1) type-i resources located in region j, that is, the request is satisfied locally, or (2) A type-i resource located in a different region, that is, the request is satisfied remotely.LetSloc⁡ and Srem denote the number of requests satisfied locally and remotely; then the revenue under placement P is
(1)RP=wloc⁡Sloc⁡+wremSrem.DenoteSsat⁡ as the total number of satisfied requests; there is Ssat⁡=Sloc⁡+Srem, and then revenue can be rewritten as
(2)RP=wloc⁡Sloc⁡+wsat⁡Ssat⁡,
where wloc⁡, wsat⁡, and wrem are revenue weights. For stochastic demand, let Dij be a random variable denoting the demand for type-i resource in region j and let Di be a random variable denoting the demand for type-i resource in all regions. Their CDFs (cumulative distribution functions) are denoted by cdfi,j and cdfi, respectively. Given demand realization dij and di, the revenue can be represented as
(3)RP=wsat⁡∑i=1Imin⁡(Li,di)+wloc⁡∑i=1I∑j=1Jmin⁡(Lij,dij).
For any arbitrary placement P and stochastic demand Dij, the expected revenue is
(4)E(RP)=wsat⁡∑i=1I‍E(min⁡(Li,Di))+wloc⁡∑i=1I‍∑j=1J‍E(min⁡(Lij,Dij)).
Then given a global resource constraint U, the aim of algorithm is to find the optimal placement P that maximizes the expected revenue. Consider
(5)max⁡(E(RP))s.t.∑i=1I‍∑j=1J‍Lij=U.


## 4. Algorithm

Generally, the problem formulated by (5) can be solved by traversing all possible placements P∈{P}U (Algorithm 1), where O={Li} istype-placement, which only presents the total amount of resources of each type. And a type-placement O can be concretized to a set of placements {P}O. We denote by {P}U and {O}U the set of placements and type-placements under global constraint U, respectively.Algorithm 1:The traversing search algorithm.
input:    total amount of resources U, the demand
distributions.
output: the optimal placement P^
(1)R^=-∞; P^=null;
(2)for  O∈{O}U  do
(3)for  P∈{P}O  do
(4)if  (E(RP))>R^  then  R^=(E(RP)),P^=P;
(5)end
(6)endHowever, the traversing algorithm is of high complexity; for example, in a typical cloud based scenario, there is a very large data space to search. And in each iteration, the computation of(E(RP)) is time-expensive, and,for instance, needs to use the I×J distributions with each one represented by N data units (in some specific applications, it is possible that I×J>104). To find efficient algorithm, we need to decompose the problem firstly, which is as illustrated below.Firstly, the problem to be solved by lines (3)–(5) in Algorithm1 can be described as Subproblem 1.Subproblem
1. Given a type-placement O′={Li′}, find the max expected revenue of all possible placements P∈{P}O′, which can be formulated as follows:
(6)max⁡(E(RP))s.t.∑j=1JLi′j=Li′∀i′∈[1,I].And the problem to be solved by lines (2)–(6) in Algorithm1 can be described as Subproblem 2.Subproblem
2. Given a global resource constraint U, find the type-placement O′ whose solution to Subproblem 1 is the maximal one among all O∈{O}U.It can be easily observed that the solution of Subproblem 1 can contribute to solution of Subproblem 2, and Algorithm1 is just a solution to Subproblem 2 using traversing search algorithm. To find efficient solution, we need to investigate the properties of these subproblems.


### 4.1. Efficient Solution to Subproblem 1

To investigate the properties of solution to Subproblem 1, we introduce some notations. Denote bytype-irevenue of placement P (RiP) the revenue of type-i resource in the placement; then theexpected type-irevenue for P (i.e., E(RiP)) is
(7)E(RiP)=wsatE(min⁡(Li,Di))+wloc∑j=1J‍E(min⁡(Lij,Dij)).For placementP, its expected revenue E(RP) can be rewritten as the summation of all its expected type-i revenues. Consider
(8)E(RP)=∑i=1I‍E(RiP).Given type-placementO′, Li is constant for each i. E(RiP) is only functions of Lij with ∑J=1J‍Lij=Li. Then for all i∈[1,I], the maximal value of E(RiP) can be achieved independently of each other, which is as follows:
(9)max⁡(E(RP))=∑i=1I‍max⁡(E(RiP))∀P∈{P}O′.Therefore, we can get Subproblem 1.2.Subproblem 1.2. Given a type-placement O′={Li′} and i′, find the max expected type-i′ revenue of all possible placements P∈{P}O′, which can be as follows:
(10)max⁡(E(RiP))s.t.∑j=1JLij=Li,
where Li is the amount of type-i resources in type-placement O′. It is obvious that Subproblem 1 can be decomposed into I Subproblem 1.2, which can also be solved by traversing search algorithm with high computation complexity. Fortunately, we are able to find properties of solutions after investigating the problem in continuous domain. These properties will be later utilized to devise efficient algorithms for the problem in discrete domain. To get the closed form of (10) in continuous domain, we first introduce Lemma 1.Lemma 1.
For any continuous nonnegative random variableX with CDF cdfX(·) and constant C, it satisfies E(min⁡(C,X))=∫0C‍(1-cdfX(v))dv.
The proof of lemmas, corollaries, and theorems in the paper can be found in Appendix. Then the closed form ofE(RiP) in continuous domain is
(11)E(RiP)=wsat⁡∫0Li‍(1-cdfi(n))dn+wloc⁡∑j=1J‍∫0Lij‍(1-cdfi,j(n))dn.To investigate the properties of solutions to Subproblem 1.2, the following theorem is introduced first.Theorem 2.
ForN functions f1(x1),f2(x2),…,fN(xN), with xn∈[0,∞) and fn(xn)≥0(1≤n≤N), the derivative functions f1′(x1),f2′(x2),…,fN′(xN) are continuous and monotonic decreasing functions, with 0≤fn′(xn)≤Y(Y>0). Then for constraint ∑i=1Nxn=U, the maximal value of ∑i=1Nfi(xi) is achieved when f1′(x1)=f2′(x2)=⋯=fN′(xN).
Note that in Theorem2 the optimal X may not be unique, since fn′(xn) need not be strictly monotonically decreasing and there may be fn′(xn′)=fn′(xn′′) with xn′≠xn′′; thus, we only need to find one of the optimal solutions to achieve the maximal value of f(X). Since Li(1≤i≤I) in (5) is constant for a given O, then according to Theorem 2, the solution to Subproblem 1.2 can be calculated as follows.Corollary 3 (the efficient solution to Subproblem 1.2).
Given type-placementO and given i(1≤i≤I), if a placement P′∈{P}O satisfies Lij=cdfi,j-1(1-Gi-1(Li)(∀j∈[1,J]), then max⁡(E(RiP′)) is achieved. Here Gi(v)=∑j=1J‍cdfi,j-1(1-v)(0≤v≤1).
According to Corollary3, by leveraging some functions, we can quickly calculate the solution to Subproblem 1.2; as a result, we can get the solution to Subproblem 1.
Additionally, for a giveni, according to Corollary 3 and the definition of E(RiP) as in (11), max⁡(E(RiP)) is a function of Li under given demand distribution, which is denoted by hi(Li). Then the maximal expected revenue of solution to Subproblem 1 can be quickly calculated as follows:
(12)max⁡(E(RP))=∑i=1I‍hi(Li)∀P∈{P}O.


### 4.2. Efficient Solution to Subproblem 2

For a given global resource constraintU, Subproblem 2 can be rewritten as follows:
(13)max⁡(∑i=1Ihi(Li))s.t.∑i=1ILi=U.According to Theorem2, the solution to Subproblem 1 can be as characterized below.Corollary 4.
GivenU>0, for a type-placement O′∈{O}U, if it satisfies Li=hi′-1(H-1(U)) for any i, then max⁡(∑i=1I‍hi(Li)) is achieved. Here H(s)=∑i=1I‍hi′-1(s) and hi′(Li)=wsat⁡(1-cdfi(Li))+wloc⁡Gi-1(Li).
In Corollary4, Gi-1(·), H-1(·), and hi′-1(·) are inverse function of Gi(·), H(·), and hi′(·), respectively. By solving Subproblem 2, we can get the maximal expected revenue in original problem of (5) and the type-placement O′; then the corresponding optimal placement P can be located by solving Subproblem 1 for type-placement O′.
The above continuous functions can be approximated by discrete ones and the optimal placement for global resource constraintU can be obtained as in Algorithm 2. The discrete functions are firstly calculated iteratively (lines (1)–(14)) and then the optimal solution is produced by calling their inverse functions (lines (15)–(18)). We denote the algorithm as discrete function based resource placement algorithm (D-URP).
In our implementation of D-URP, each of these discrete functions is recorded in hash map data structure, and its time complexity of querying isO(1). And for discrete function f, an absent f(x) is approximated proportionally by
(14)f(x)=f(x1)+(x-x1)f(x2)-f(x1)x2-x1,
where x1 and x2 are the nearest present values to x with x1<x<x2. By binary search algorithm, the time complexity of finding x1 and x2 within K keys is O(log⁡(K)). As in [8], the demand distributions from input can be precalculated in O(1) and are available in an external data base. As a result, the worse time complexity of codes in Algorithm 2 is O(I*J) (lines (1)–(3)), O(IJK+IKlog⁡K) (lines (4)–(14)), and O(IJlog⁡K) (lines (15)–(18)); one can easily calculate that the time complexity of D-URP is no more than O(IJK+IKlog⁡K) and less than O(IJK) when log⁡K≤J, where K is the cycle count in Algorithm 2. Additionally, iterations in the algorithm can be easily parallelized to get further acceleration. If some iterations are executed in parallel (lines (1)–(3), (6)–(10), and (15)–(18), resp.), the time complexity is less than O(JK+IKlog⁡K).Algorithm 2:The steps of D-URP.
input:     total amount of resources U;
demand distributioncdfi(·), cdfi,j(·), cdfi-1(·)
andcdfi,j-1(·); Xi,j=min⁡(cdfi,j(x)=1|∀x).
output: amount of resources of each type placed in each
regionLij.
(1)for  i=1  to  I  do
(2)Gi-1(x)=h′i(x)=0, for x≥∑j=1J‍Xi,j.
(3)end
(4)for  k=0  to  K  do
(5)v=wloc⁡*k/K.
(6)for  i=1  to  I  do
(7)L′i=∑j=1J‍cdfi,j-1(1-v).
(8)Gi(v)=L′i.
(9)h′i(L′i)=wsat⁡(1-cdfi(L′i))+wloc⁡v.
(10)end
(11)s=(wsat⁡+wloc⁡)*k/K.
(12)H(s)=∑i=1I‍hi′-1(s).
(13)if  H(s)≥U  then break;
(14)end
(15)for  i=1  to  I  do
(16)Li=hi′-1(H-1(U)).
(17)for  j=1  to  J  do Lij=cdfi,j-1(1-Gi-1(Li));
(18)end


## 4.1. Efficient Solution to Subproblem 1

To investigate the properties of solution to Subproblem 1, we introduce some notations. Denote bytype-irevenue of placement P (RiP) the revenue of type-i resource in the placement; then theexpected type-irevenue for P (i.e., E(RiP)) is
(7)E(RiP)=wsatE(min⁡(Li,Di))+wloc∑j=1J‍E(min⁡(Lij,Dij)).For placementP, its expected revenue E(RP) can be rewritten as the summation of all its expected type-i revenues. Consider
(8)E(RP)=∑i=1I‍E(RiP).Given type-placementO′, Li is constant for each i. E(RiP) is only functions of Lij with ∑J=1J‍Lij=Li. Then for all i∈[1,I], the maximal value of E(RiP) can be achieved independently of each other, which is as follows:
(9)max⁡(E(RP))=∑i=1I‍max⁡(E(RiP))∀P∈{P}O′.Therefore, we can get Subproblem 1.2.Subproblem 1.2. Given a type-placement O′={Li′} and i′, find the max expected type-i′ revenue of all possible placements P∈{P}O′, which can be as follows:
(10)max⁡(E(RiP))s.t.∑j=1JLij=Li,
where Li is the amount of type-i resources in type-placement O′. It is obvious that Subproblem 1 can be decomposed into I Subproblem 1.2, which can also be solved by traversing search algorithm with high computation complexity. Fortunately, we are able to find properties of solutions after investigating the problem in continuous domain. These properties will be later utilized to devise efficient algorithms for the problem in discrete domain. To get the closed form of (10) in continuous domain, we first introduce Lemma 1.Lemma 1.
For any continuous nonnegative random variableX with CDF cdfX(·) and constant C, it satisfies E(min⁡(C,X))=∫0C‍(1-cdfX(v))dv.
The proof of lemmas, corollaries, and theorems in the paper can be found in Appendix. Then the closed form ofE(RiP) in continuous domain is
(11)E(RiP)=wsat⁡∫0Li‍(1-cdfi(n))dn+wloc⁡∑j=1J‍∫0Lij‍(1-cdfi,j(n))dn.To investigate the properties of solutions to Subproblem 1.2, the following theorem is introduced first.Theorem 2.
ForN functions f1(x1),f2(x2),…,fN(xN), with xn∈[0,∞) and fn(xn)≥0(1≤n≤N), the derivative functions f1′(x1),f2′(x2),…,fN′(xN) are continuous and monotonic decreasing functions, with 0≤fn′(xn)≤Y(Y>0). Then for constraint ∑i=1Nxn=U, the maximal value of ∑i=1Nfi(xi) is achieved when f1′(x1)=f2′(x2)=⋯=fN′(xN).
Note that in Theorem2 the optimal X may not be unique, since fn′(xn) need not be strictly monotonically decreasing and there may be fn′(xn′)=fn′(xn′′) with xn′≠xn′′; thus, we only need to find one of the optimal solutions to achieve the maximal value of f(X). Since Li(1≤i≤I) in (5) is constant for a given O, then according to Theorem 2, the solution to Subproblem 1.2 can be calculated as follows.Corollary 3 (the efficient solution to Subproblem 1.2).
Given type-placementO and given i(1≤i≤I), if a placement P′∈{P}O satisfies Lij=cdfi,j-1(1-Gi-1(Li)(∀j∈[1,J]), then max⁡(E(RiP′)) is achieved. Here Gi(v)=∑j=1J‍cdfi,j-1(1-v)(0≤v≤1).
According to Corollary3, by leveraging some functions, we can quickly calculate the solution to Subproblem 1.2; as a result, we can get the solution to Subproblem 1.
Additionally, for a giveni, according to Corollary 3 and the definition of E(RiP) as in (11), max⁡(E(RiP)) is a function of Li under given demand distribution, which is denoted by hi(Li). Then the maximal expected revenue of solution to Subproblem 1 can be quickly calculated as follows:
(12)max⁡(E(RP))=∑i=1I‍hi(Li)∀P∈{P}O.


## 4.2. Efficient Solution to Subproblem 2

For a given global resource constraintU, Subproblem 2 can be rewritten as follows:
(13)max⁡(∑i=1Ihi(Li))s.t.∑i=1ILi=U.According to Theorem2, the solution to Subproblem 1 can be as characterized below.Corollary 4.
GivenU>0, for a type-placement O′∈{O}U, if it satisfies Li=hi′-1(H-1(U)) for any i, then max⁡(∑i=1I‍hi(Li)) is achieved. Here H(s)=∑i=1I‍hi′-1(s) and hi′(Li)=wsat⁡(1-cdfi(Li))+wloc⁡Gi-1(Li).
In Corollary4, Gi-1(·), H-1(·), and hi′-1(·) are inverse function of Gi(·), H(·), and hi′(·), respectively. By solving Subproblem 2, we can get the maximal expected revenue in original problem of (5) and the type-placement O′; then the corresponding optimal placement P can be located by solving Subproblem 1 for type-placement O′.
The above continuous functions can be approximated by discrete ones and the optimal placement for global resource constraintU can be obtained as in Algorithm 2. The discrete functions are firstly calculated iteratively (lines (1)–(14)) and then the optimal solution is produced by calling their inverse functions (lines (15)–(18)). We denote the algorithm as discrete function based resource placement algorithm (D-URP).
In our implementation of D-URP, each of these discrete functions is recorded in hash map data structure, and its time complexity of querying isO(1). And for discrete function f, an absent f(x) is approximated proportionally by
(14)f(x)=f(x1)+(x-x1)f(x2)-f(x1)x2-x1,
where x1 and x2 are the nearest present values to x with x1<x<x2. By binary search algorithm, the time complexity of finding x1 and x2 within K keys is O(log⁡(K)). As in [8], the demand distributions from input can be precalculated in O(1) and are available in an external data base. As a result, the worse time complexity of codes in Algorithm 2 is O(I*J) (lines (1)–(3)), O(IJK+IKlog⁡K) (lines (4)–(14)), and O(IJlog⁡K) (lines (15)–(18)); one can easily calculate that the time complexity of D-URP is no more than O(IJK+IKlog⁡K) and less than O(IJK) when log⁡K≤J, where K is the cycle count in Algorithm 2. Additionally, iterations in the algorithm can be easily parallelized to get further acceleration. If some iterations are executed in parallel (lines (1)–(3), (6)–(10), and (15)–(18), resp.), the time complexity is less than O(JK+IKlog⁡K).Algorithm 2:The steps of D-URP.
input:     total amount of resources U;
demand distributioncdfi(·), cdfi,j(·), cdfi-1(·)
andcdfi,j-1(·); Xi,j=min⁡(cdfi,j(x)=1|∀x).
output: amount of resources of each type placed in each
regionLij.
(1)for  i=1  to  I  do
(2)Gi-1(x)=h′i(x)=0, for x≥∑j=1J‍Xi,j.
(3)end
(4)for  k=0  to  K  do
(5)v=wloc⁡*k/K.
(6)for  i=1  to  I  do
(7)L′i=∑j=1J‍cdfi,j-1(1-v).
(8)Gi(v)=L′i.
(9)h′i(L′i)=wsat⁡(1-cdfi(L′i))+wloc⁡v.
(10)end
(11)s=(wsat⁡+wloc⁡)*k/K.
(12)H(s)=∑i=1I‍hi′-1(s).
(13)if  H(s)≥U  then break;
(14)end
(15)for  i=1  to  I  do
(16)Li=hi′-1(H-1(U)).
(17)for  j=1  to  J  do Lij=cdfi,j-1(1-Gi-1(Li));
(18)end


## 5. Experiments

In this section, we evaluate D-URP algorithm to study the following subjects:(1) comparing the effectiveness of D-URP with SSP based algorithm in [8], which is denoted by S-URP (SSP based unbounded resource placement) and (2) checking the relationship of time complexity and effectiveness of D-URP.Similar to the experiment settings of prior works [8], we consider demands that follow Zipf distribution; that is, the probability of a single request to demand a type-i resource is
(15)pi=i-e∑n=1In-e,
where e>0 is a real number. Without loss of generality, we choose Dij to be Poisson distribution with a rate of piλ/J, where λ is the expected number of total requests and the expectation of demands from each region is equal.First we compare the effect of proportional mean method, S-URP, and D-URP under different scenarios, where in method of proportional mean, the number of type-i resources in region j is proportional to the mean demand:
(16)Li′j′=E(Di′j′)∑i=1I∑j=1JE(Dij)U.From Figures1, 2, and 3, the expected revenues of three methods are compared under surplus scenario (U=1500>λ), balanced scenario (U=1000=λ), and deficit scenario (U=500<λ), respectively. The expected revenue is drawn against Zipf parameters. The number of regions J=4 and the revenue parameters wloc⁡=wsat⁡=1. The parameter settings are I=500 and λ=1000 and the cycle count of D-URP is K=100. Similar to previous works [8], the Zipf parameter is set to be wide enough and ranges from 0.7 to 1.4.Figure 1
Expected revenue of mean, S-URP, and D-URP with different Zipf values under deficit scenarios (U=500).Figure 2
Expected revenue of mean, S-URP, and D-URP with different Zipf values under balanced scenarios (U=1000).Figure 3
Expected revenue of mean, S-URP, and D-URP with different Zipf values under surplus scenarios (U=1500).It is observed from Figures1, 2, and 3 that D-URP can outperform proportional mean based methods with different Zipf values; for example, the expected revenue of D-URP (line marked with “×”) is always larger than that of proportional mean based method (line marked with “*” ). And the effect of D-URP is close to that of S-URP; for example, the difference in expected revenue between D-URP and S-URP (distance between line marked with “×” and line marked with “+”) is always within 100 in all three figures.As shown in Figures4, 5, and 6, the expected revenues of these three methods are compared under surplus (U=1500>λ), balanced (U=1000=λ), and deficit scenario (U=500<λ), respectively. The expected revenue is drawn against number of resource types (I). The number of regions J=4 and the revenue parameters wloc⁡=wsat⁡=1. The parameter settings are Zipf = 1.0 and λ=1000 and the cycle count of D-URP is K=100. The number of type I resources ranges from 100 to 1000 to cover the result in different orders of magnitude of I.Figure 4
Expected revenue of mean, S-URP, and D-URP with different number of resource types under deficit scenarios (U=500).Figure 5
Expected revenue of mean, S-URP, and D-URP with different number of resource types under balanced scenarios (U=1000).Figure 6
Expected revenue of mean, S-URP, and D-URP with different number of resource types under surplus scenarios (U=1500).It is shown from Figures4, 5, and 6 that D-URP always outperforms proportional mean based methods with different number of resource types, since the expected revenue of D-URP (marked with “×”) is always larger than that of proportional mean based method (marked with “*”). Because the difference in expected revenue between D-URP and S-URP (between line marked with “×” and “+”) changes little (always within 100) in all three figures, the effect of D-URP is close to that of S-URP with increasing number of resource types.In brief, from Figures1, 2, 3, 4, 5, and 6, we can see that D-URP can outperform proportional mean based methods, and the effect of D-URP is close to S-URP in all scenarios. However, it is observed that, along with the increasing of available resources (U increases from 500 to 1500), the effect of mean based method (line marked with “*”) approaches that of optimal solution S-URP (line marked with “+”). The underlying reason is that the number of unsatisfied demands decreases with more resources, which leads to the decreasing of room for optimization. Since resources cannot be surplus enough in most of real scenarios, D-URP and S-URP can still be used to gain more revenue in common scenarios.Since the result of S-URP is optimal, we then investigated the effect of D-URP using the revenue ratio of D-URP to S-URP. In Figures7 and 8, the revenue ratio is drawn against Zipf parameters with λ=1000. The number of regions J=4 and the revenue parameters wloc⁡=wsat⁡=1. In Figure 7, Zipf ranges from 0.7 to 1.4. We compared D-URP and S-URP using the revenue ratio of D-URP to S-URP, with K=100 and I=100, under surplus scenario (U=1500>λ), balanced scenario (U=1000=λ), and deficit scenario (U=500<λ). In Figure 8, we compare D-URP and S-URP with K=100 and I ranging from 100 to 1000, under surplus, balanced, and deficit scenarios. We can see that the effect of D-URP does not change significantly along with the increasing of Zipf and number of resource types (I).Figure 7
Revenue ratio of D-URP to S-URP with different Zipf values under deficit, balanced, and surplus scenarios.Figure 8
Revenue ratio of D-URP to S-URP with different number of resource types under deficit, balanced, and surplus scenarios.In Figure9, we investigate the time complexity of D-URP using different expected numbers of total requests (λ=1000,5000,10000), Zipf values (0.7 to 1.4), I (100 to 1000), and available resources U (0.5λ to 1.5λ with interval of 0.1λ). For each pair of λ and U, S-URP and D-URP are applied to get revenue ratio, with D-URP’s cycle count K ranging from 10 to 200. The average revenue ratio (of all U) for each K under different λ is plotted in Figure 9. We can see that averagely D-URP can achieve more than 97% revenue of optimal solution and can achieve more than 99% when λ=10000.Figure 9
Average revenue ratio of D-URP to S-URP with different D-URP cycle counts under scenarios with different expected number of requests.In brief, the following is shown in above experiments.(1)
D-URP is lightly affected by the popularity distribution of resources (Zipf) and number of resource types (I).(2)
D-URP is affected by the scarcity of resources. It is observed that it is better in surplus scenario or with more total available resources. By inspecting the data, we find that since the optimal solution is rounded to integers, the revenue under smallerU is more affected by rounding.(3)
In D-URP, near optimal result can be calculated with much lower time complexity. The average effect of D-URP can still achieve at least 97% of optimal solution in all considered scenarios. Note the time complexity of S-URP and D-URP isO(IJU) [8] and O(IJK+IKlog⁡K) (as stated in Section 3), respectively. When λ=10000 and K=10, the time complexity is reduced by nearly three orders of magnitude and the effect of D-URP can still achieve 99% of optimal result.


## 6. Conclusion

In this paper, we propose a fast algorithm D-URP for resource placement in cloud platform considering stochastic demands with multidimensional distribution. Our analysis and the preliminary experiments indicate that D-URP can achieve at most 99% revenue of optimal solution, and compared with existing algorithms, its time complexity is reduced by nearly three orders of magnitude in our scenarios with general settings. Therefore, D-URP can be an effective supplement to existing algorithms under time-tense scheduling scenarios.Our future interesting works may include more precise approximation of continuous functions using discrete ones and efficient algorithms to variant of resource placement problem with more constraints.



---

*Source: 760458-2014-09-29.xml*