Computational Intelligence - February 2015 - 36

of cloud services. Therefore, the virtual broker needs to solve a
mapping problem to efficiently assign the VM requests from its
customers to the available RIs, satisfying the minimum performance requirements of the VMs.
Assumptions and definitions:
❏ The set of virtual machine requests from the customers of
the virtual broker VM = " v 1, f, v n , .
❏ Each virtual machine has specific hardware demands,
including processor speed P (v i), memory M (v i), storage
S (v i), and the number of cores nc (v i) .
❏ Virtual machine requests arrive in batches (i.e., hourly,
diary). Arrival times A i follow a stochastic homogeneous
Poisson process with rate parameter m.
❏ The execution time of v i is defined as T (v i), and it must
start before a deadline D (v i) . Both T (v i) and D (v i) are
specified by the user in the request made to the virtual broker, as it is normally considered in cloud systems.
❏ The set of cloud resource instances pre-booked by the virtual broker RI = " r1, f, rm ,, m % n, with specific features
including processor speed P (r j), memory M (r j), and storage
S (r j), according to a predefined list of instance types
t (r j) ! {t 1, f, t k}.
❏ A cost function C is defined for pre-booked cloud resource
instances, and a cost function COD for on-demand instances, with C (r j) % COD (r j). Both cost functions are given in
an hourly basis.
❏ A pricing function p (r j) that defines the price the virtual
broker charges to the customers per hour for the resources
r j . To attract customers, the virtual broker should charge for
a virtual machine r j a lower cost than the on-demand pricing for that virtual machine offered by the cloud provider,
i.e., p (r j) < COD (r j).
The Virtual Machine Mapping Problem (VMMP) can be formalized as finding a mapping function f : VM " RI that maximizes the total profit of the virtual broker, computed according to the optimization problem defined next.
max

m

/; /

j = 1 i: f (v i) = r j

+

/

(p (BF (v i)) - C (r j)) # T (v i)E
(p (BF (v h)) - COD (BF (v h))) # T (v h)

h: ST (v h) > D (v h)

subject to M (v i) # M (r j), P (v i) # P (r j)
S (v i) # S (r j), nc (v i) # nc (r j)
where the BF (v k) function gives the less expensive instance
capable of executing the request v k and ST (v i) states the starting time of request v i .
We model deadlines as hard constraints. In case the virtual broker cannot accommodate the VM request to start execution by the
specified deadline, it must either use a larger RI offering more
resources than those requested, or buy an on-demand instance to
fulfil the request (in any case, at the cost of the one requested by
the user). Both solutions obviously account for a negative impact
on the profit of the broker. We would like to emphasize at this
point that none of the VM deadlines are ever violated, since the

36

IEEE ComputatIonal IntEllIgEnCE magazInE | fEbruary 2015

broker buys on-demand instances to provide those VMs for which
it cannot satisfy the deadline restriction with its own RIs.
The first double summation in the objective function measures the total profit of the virtual broker due to the RIs used
to allocate the customers VM requests. The last summation
accounts for the additional costs implied by buying on-demand
VMs to fulfil those requests for which the planning does not
satisfy the deadline constraints.
In this problem formulation, data transmission for VM
requests is not considered in the objective function: the
model assumes that the virtual broker directly transfers the
data transmission costs to the user, so it does not provide any
economic profit.
III. Literature Review

Despite the large number of papers on cloud brokering in the
literature, only very few of them tackle similar problems as the
one addressed in this paper. Usually, the traditional cloud brokering approach [4] is used, which typically deals with the
problems of finding the cloud providers whose offer better suits
the customer needs-technically and in terms of cost [15]
[16]-, or providing the customer with the best possible way to
deploy his/her application in the cloud [17]. The literature
review indicates that there are a number of works proposing
methods for scheduling applications in private resources using
the cloud bursting technique [18]. These works enhance the
local schedulers with the capability of using VMs from the public cloud when additional resources are required. This is a similar concept to the one addressed in this paper, since in the case
that all RIs are used and a request cannot start before its deadline, then the virtual broker will buy an on-demand instance
from the cloud to execute it. However, in our work we do not
address the resource provisioning problem, since the virtual
broker does not own any physical computing resources; it is an
intermediate entity which always works with VMs (either
reserved or on-demand) from the public cloud.
The nested cloud architecture was studied by Pan et al. [19]
and Spillner et al. [20]. This technology allows using a VM as a
running host system for another VM. Therefore, users are able
to resell surplus slices to others, leveraging the additional cost
that resources over-provisioning imply. The experimental analysis in [20] allowed to conclude that the use of nesting techniques involves a small cost of less than 10% overhead.
Closer to the VMMP, Wu et al. [21] proposed encouraging
customers to provide realistic likelihood that they will purchase
a given resource, at the reward of price reductions. This method
allows the provider to efficiently forecast the required resources,
minimizing underutilization and/or overbooking of the available resources, and it benefits the customer too, who will have
the service at a low price. Rogers and Cliff [9] adapted this
method for a cloud broker subletting reserved VMs to its customers. The broker uses the information given by the customers to decide whether to invest in buying more resources or
not, and what kind of resources should be bought. This technique is shown to provide up to a 44% increase in the profit of



Table of Contents for the Digital Edition of Computational Intelligence - February 2015

Computational Intelligence - February 2015 - Cover1
Computational Intelligence - February 2015 - Cover2
Computational Intelligence - February 2015 - 1
Computational Intelligence - February 2015 - 2
Computational Intelligence - February 2015 - 3
Computational Intelligence - February 2015 - 4
Computational Intelligence - February 2015 - 5
Computational Intelligence - February 2015 - 6
Computational Intelligence - February 2015 - 7
Computational Intelligence - February 2015 - 8
Computational Intelligence - February 2015 - 9
Computational Intelligence - February 2015 - 10
Computational Intelligence - February 2015 - 11
Computational Intelligence - February 2015 - 12
Computational Intelligence - February 2015 - 13
Computational Intelligence - February 2015 - 14
Computational Intelligence - February 2015 - 15
Computational Intelligence - February 2015 - 16
Computational Intelligence - February 2015 - 17
Computational Intelligence - February 2015 - 18
Computational Intelligence - February 2015 - 19
Computational Intelligence - February 2015 - 20
Computational Intelligence - February 2015 - 21
Computational Intelligence - February 2015 - 22
Computational Intelligence - February 2015 - 23
Computational Intelligence - February 2015 - 24
Computational Intelligence - February 2015 - 25
Computational Intelligence - February 2015 - 26
Computational Intelligence - February 2015 - 27
Computational Intelligence - February 2015 - 28
Computational Intelligence - February 2015 - 29
Computational Intelligence - February 2015 - 30
Computational Intelligence - February 2015 - 31
Computational Intelligence - February 2015 - 32
Computational Intelligence - February 2015 - 33
Computational Intelligence - February 2015 - 34
Computational Intelligence - February 2015 - 35
Computational Intelligence - February 2015 - 36
Computational Intelligence - February 2015 - 37
Computational Intelligence - February 2015 - 38
Computational Intelligence - February 2015 - 39
Computational Intelligence - February 2015 - 40
Computational Intelligence - February 2015 - 41
Computational Intelligence - February 2015 - 42
Computational Intelligence - February 2015 - 43
Computational Intelligence - February 2015 - 44
Computational Intelligence - February 2015 - 45
Computational Intelligence - February 2015 - 46
Computational Intelligence - February 2015 - 47
Computational Intelligence - February 2015 - 48
Computational Intelligence - February 2015 - 49
Computational Intelligence - February 2015 - 50
Computational Intelligence - February 2015 - 51
Computational Intelligence - February 2015 - 52
Computational Intelligence - February 2015 - 53
Computational Intelligence - February 2015 - 54
Computational Intelligence - February 2015 - 55
Computational Intelligence - February 2015 - 56
Computational Intelligence - February 2015 - 57
Computational Intelligence - February 2015 - 58
Computational Intelligence - February 2015 - 59
Computational Intelligence - February 2015 - 60
Computational Intelligence - February 2015 - 61
Computational Intelligence - February 2015 - 62
Computational Intelligence - February 2015 - 63
Computational Intelligence - February 2015 - 64
Computational Intelligence - February 2015 - Cover3
Computational Intelligence - February 2015 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com