Sage Journals: Discover world-class research

Abstract

Combinatorial auction is a popular approach for resource allocation in cloud computing. One of the challenges in resource allocation is that QoS (Quality of Service) constraints are satisfied and provider's profit is maximized. In order to increase the profit, the penalty cost for SLA (Service Level Agreement) violations needs to be reduced. We consider execution time constraint as SLA constraint in combinatorial auction system. In the system, we determine winners at each bidding round according to the job's urgency based on execution time deadline, in order to efficiently allocate resources and reduce the penalty cost. To analyze the performance of our mechanism, we compare the provider's profit and success rate of job completion with conventional mechanism using real workload data.

1. Introduction

Over recent years, the growth of the IoT (Internet of Things) is expected to create a pervasive connection of things such as embedded devices, sensors, and actuators. This will inevitably result in the generation of enormous amount of data, which have to be autonomously stored, processed, accessed, and managed. Cloud computing has been recognized as a paradigm for the big data problem [1]. Cloud computing allows the sensing data to be stored and used intelligently for smart applications.

One of challenges which arose when IoT meets cloud is resource allocation by which a cloud provider efficiently allocates its resources to cloud users with SLA constraints. The dominating performance factors in resource allocation include provider's and user's profit, resource utilization, and QoS (Quality of Service) [2]. For resource allocation in cloud, auction-based model is a popular approach in resource allocation and pricing [3]. In particular, combinatorial auction is preferred in cloud computing because it allows a user to buy a package of resources rather than an individual resource. Since the auction is done on group of resources, it provides efficient resource allocation and helps to improve the profit to both a provider and a user.

The other issue of resource allocation in cloud computing is meeting SLA (Service Level Agreement) established with a user. Before a provider provisions a service to a user, a provider and a user need to establish SLA contract. The SLA is an agreement that specifies QoS between a provider and a user [4]. We define two-levels of SLA to represent different objectives: class-based SLA and job-based SLA [5]. In class-based SLA, for each job class, QoS is measured based on performance metrics. In job-based SLA, QoS is measured using the metrics of individual jobs. Any single job with a poor service quality immediately affects the measured QoS and incurs some SLA penalty cost. We believe the job-based SLA is a more robust type of SLAs from the users' perspective than providers' perspective and we focus on this. In general, SLA is defined in terms of various performance metrics, such as service latency, throughput, consistency, and security. In our paper, SLA is defined in terms of deadline along with execution time of each job. The deadline violation is important from QoS guarantees perspective. It causes loss of profit for a provider due to incompletion to execute the certain jobs and SLA penalty cost [6].

Considering SLA guarantee, we propose a resource allocation mechanism in combinatorial auction system for cloud computing. For efficient resource allocation, winner determination problem in the auction should be solved. The conventional winner determination mechanisms are proposed to maximize resource utilization and a provider's profit for each time interval. However, the profit can be maximized by reducing the penalty cost for SLA violation. To reduce SLA violations, the deadline constraints need to be considered when winner is determined in the auction. Thus, we propose a winner determination mechanism with consideration for the deadline constraints to maximize the provider's profit.

The rest of the paper is organized as follows. In Section 2, we discuss the related work. In Section 3, we present our winner determination mechanism. In Sections 4 and 5, we evaluate the performance of our mechanism and conclude the paper with the future research plan.

2. Related Work

We investigate resource allocation strategies for the SLA-based cloud computing framework. Several proposals in the literature are based on utility functions to dynamically allocate resources. In [7], a two-tier resource management approach based on utility functions is presented. It defines the VM (Virtual Machine) utility function as a linear function of the CPU resources. In [8], an autonomic resource manager is presented to control the virtualized environment which decouples the provisioning of resources from the dynamic placement of VMs. It finds an optimal number and size of VMs to allocate CPU resources to applications while maximizing the utility function.

There are several proposals that dynamically manage VMs by optimizing objective functions. Reference [9] determines dynamic placement of VMs based on minimizing an objective cost function using linear programming. The function is to provide an economic model between infrastructure providers and users. The pMapper [10] system includes a power-aware application placement controller to optimize a cost-performance function. It uses the bin-packing algorithm based on a modified version of FFD (First-Fit Decreasing) to place the VMs on the servers, while trying to meet the target utilization.

Researchers have investigated maximizing the profit under SLA constraints. In [11], a multilevel generalized assignment problem is formulated. To solve the problem, the first-fit heuristic is used for maximizing the profit under SLA and the power budget constraint. In [12], a combinatorial optimization problem is defined to maximize the provider's profit from SLA compliant placement. The problem is presented as a multiunit combinatorial auction. To solve the problem, a column generation method is presented to obtain near optimal solutions.

A combinatorial auction allows bidders to bid for a combination of multiple resources. In other words, bids are submitted for the whole bundle as a single unit. After the auction, each bidder receives either the whole bundle or nothing. In the auction, the goal of a cloud provider is to efficiently allocate the available resources to users and to maximally generate its revenue. In [13], CA-provision is proposed as an allocation mechanism to maximize the revenue for a cloud provider as well as maximize the resource utilization. The provider's revenue has three elements: the revenue of the resource, the cost of the VM instances that are allocated to the users, and the cost of keeping the remaining resources idle. The purpose of considering the two costs is to reduce the cloud provider's losses. Reference [14] proposes a model, called ABRA (Auction-Based Resource Co-Allocation) to solve the resource coallocation problem. It imposes penalty costs on unallocated resources after an auction in order to improve the resource utilization. First, a new neighborhood structure is proposed to define an ordering as a permutation of the bids in the auction. Then, the search space is defined as the set of all possible orderings to find the optimum solution. Finally, various neighbor selection methods are used to find the solution.

The conventional resource allocation mechanisms in combinatorial auction system present winner determination algorithms to reduce the penalty cost in each bidding round. However, since they do not consider the probability of SLA violation when deadline gets to end, the performance is limited. We present a new winner determination algorithm with consideration for deadline constraints of jobs (i.e., urgency) to reduce the penalty cost for SLA violation and maximize the profit of the provider.

3. Proposed Mechanism

A cloud provider offers computing services to users through m different types of VM instances, ${V M}_{1}, {V M}_{2}, \dots, {V M}_{m}$ . The computing power of a VM instance of type ${V M}_{i}, i = 1, \dots, m$ , is $w_{i}$ , where $w_{1} = 1$ , $w_{1} < w_{2} < \dots < w_{m}$ , and $w = (w_{1}, w_{2}, \dots, w_{m})$ [13]. We consider that w is determined mainly by the number of cores, like Amazon EC2 [15]. Let $k_{i}$ be the number of ${V M}_{i}$ instances provisioned by the provider. Let M be the maximum number of VM instances provisioned by the provider. The provider provisions a combination of instances given by the vector $(k_{1}, k_{2}, \dots, k_{m})$ as long as $\sum_{i = 1}^{m} w_{i} k_{i} \leq M$ . We consider n users $u_{1}, \dots, u_{n}$ who request computing resources from the provider specified as bundles of VM instances. A user $u_{j}$ requests VM instances for its job ${j o b}_{j}$ by submitting a bid $B_{j} = (r_{1}^{j}, \dots, r_{m}^{j}, v_{j})$ to the provider, where $r_{i}^{j}$ is the number of requested instances of type ${V M}_{i}$ and $v_{j}$ is the price user $u_{j}$ is willing to pay to use the requested bundle of VMs for a unit of time. In addition, let us denote by $p_{j}$ the amount paid by user $u_{j}$ for using its requested bundle of VMs, and $p_{j}$ and $v_{j}$ can be different (usually $p_{j} \leq v_{j}$ ). We assume that the users are single minded which means a user bids for only one bundle.

The provider runs auction mechanism periodically to allocate the VM instances. Thus, users bid for obtaining the VM bundles for a unit of time. If the user's job requires a bundle for more than one unit of time, the user has to bid again in the next round of the auction, separately. A user bids until its application is completed or its deadline is exceeded. Conventional winner determination mechanisms do not consider that each job has different urgency. In other words, the job which has impending deadline needs to have a weight to the job with the time left before the deadline in the competitive bidding. To maximize the provider's profit by reducing the penalty cost for SLA violations, we use the probability of deadline violations by considering the job's urgency, when winners are determined [16].

In our paper, SLA is defined in terms of completion deadline $d_{j}$ for job ${j o b}_{j}$ of user $u_{j}$ . For simplicity's sake, we assume that a user has one job at a time. Our problem is that $K_{j}$ , $K_{j} \leq d_{j}$ biddings should be succeeded to complete ${j o b}_{j}$ before $d_{j}$ gets to end. The current bidding round $θ_{j}$ is the sum of the number of successful biddings $k_{j}$ , $k_{j} < K_{j}$ and the number of bidding failures $f_{j}$ ; in other words $θ_{j} = k_{j} + f_{j}$ and $θ_{j} \leq d_{j}$ . We define the problem as the combination of $d_{j}$ taken $K_{j}$ :

\begin{matrix} {{}_{d_{j}}C}_{K_{j}} \end{matrix}

(1)

subject to

\begin{matrix} d_{j} \geq K_{j} . \end{matrix}

(2)

The success probability of

K_{j}

biddings before

d_{j}

is as follows:

\begin{matrix} \frac{1}{{{}_{d_{j}}C}_{K_{j}}} . \end{matrix}

(3)

We identify that the probability of successful job completion needs to be increased as

f_{j}

θ_{j}

increases. At the current round

θ_{j}

with

k_{j}

successful bidding, to complete the job before

d_{j}

K_{j} - k_{j}

successful biddings need more. The remaining rounds before

d_{j}

are

d_{j} - θ_{j} = d_{j} - f_{j} - k_{j}

. Thus to get the probability of job completion before

d_{j}

, (3) is rewritten as follows:

\begin{matrix} {P r}_{j} = \frac{1}{{{}_{(d_{j} - f_{j} - k_{j})}C}_{(K_{j} - k_{j})}} = \frac{(K_{j} - k_{j})!}{{{}_{(d_{j} - f_{j} - k_{j})}P}_{(K_{j} - k_{j})}} . \end{matrix}

(4)

Using (4), we calculate the expected value of the provider's profit for each user to determine the winners at a bidding round. The profit is divided into two cases. When the job is completed before deadline, the profit is the difference between revenue and running cost

C_{R}

of the VM instances to be allocated to the user. When the job is not completed before deadline and SLA is violated, the provider should pay the penalty cost

C_{j}^{p e n a l t y}

. With the probability of SLA violation in (4), we define

E_{j}^{p r o f i t}

the expected value of the provider's profit for

u_{j}

as follows:

\begin{matrix} E_{j}^{p r o f i t} = \Pr_{j} (v_{j} - C_{R} \sum_{i = 1}^{m} w_{i} r_{i}^{j}) + (1 - {P r}_{j}) (v_{j} - C_{R} \sum_{i = 1}^{m} w_{i} r_{i}^{j} - C_{j}^{p e n a l t y}) . \end{matrix}

(5)

In (6), we normalize

E_{j}^{p r o f i t}

with the maximum value of

E_{j}^{p r o f i t}

to remove the dependence on

v_{j}

. The maximum value of

E_{j}^{p r o f i t}

indicates the expected value when there is no SLA violation:

\begin{matrix} \frac{E_{j}^{p r o f i t}}{v_{j} - C_{R} \sum_{i = 1}^{m} w_{i} r_{i}^{j}} . \end{matrix}

(6)

Using (6), winners are determined at each round.

Figure 1 shows that ${P r}_{j}$ increases as $k_{j}$ or $f_{j}$ increases in our mechanism. We set $d_{j}$ and $K_{j}$ to 15 and 10, respectively. Thus, when $f_{j} > 5$ , ${j o b}_{j}$ is not completed before the deadline. In the figure, ${P r}_{j}$ gets to 1 in order to complete the job before the deadline, when $f_{j} = 5$ . Besides, as you can see, $f_{j}$ has the bigger impact than $k_{j}$ on ${P r}_{j}$ . Because $E_{j}^{p r o f i t}$ increases as ${P r}_{j}$ increases, the probability that $u_{j}$ is to be a winner also increases. Thus, the jobs with impending deadlines are likely to be determined as winners. Through the determination, deadline violation can be reduced and the profit of the provider can be improved.

Figure 1

${P r}_{j}$ with varying the number of biddings.

4. Performance Analysis

To evaluate the performance of our mechanism, we conduct simulation with real workload data and compare the performance of the conventional mechanism (CA-provision [13]). In preliminary experiments, we use UniLu-Gaia-2014 workload logs from the Parallel Workload Archive [17]. In the logs, the average number of submitted jobs per round is set to about 24 and the average number of processors required per job is 9.97. In the experiments, we set $C_{R}$ to 0.5 and $C_{j}^{p e n a l t y}$ to 10 percent of $v_{j}$ . $K_{j}$ is randomly selected from (1, 20) and the average execution time of a job is multiplying bidding time interval $Δ t$ with $K_{j}$ .

Figure 2 shows the probability of bidding success at current round $θ_{j}$ when the remaining bidding rounds before $d_{j}$ vary. In CA-provision, the probability does not show the big change. In our mechanism, the probability increases as the remaining round decreases. By considering the job's urgency, the probability gets to 1 as the deadline gets to end, and the jobs with impending deadlines are likely to be determined as winners.

Figure 2

The probability of bidding success at a current round.

Figure 3 shows the success rate of job completion for each user. The success rate of job completion indicates the number of jobs completed before the deadline to the number of jobs submitted by user $u_{j}$ in the total simulation time. The success rate of ours is about 27.4% higher than that of CA-provision. In Figure 4, the deadline of a job is determined by multiplying a deadline factor $τ_{j}$ with $K_{j}$ ; thus the deadline is $d_{j} = τ_{j} K_{j}$ . Here, $τ_{j}$ is chosen from 1.5, 2.0, 2.5, and 3.0. The figure shows the success rate of job completion with varying the deadline factors. As you can see, the success rate increases as the deadline increases. The success rate of our mechanism is about 2%, 13.3%, 19.8%, and 27.4% higher than that of CA-provision, respectively. Figures 3 and 4 show that our mechanism effectively reduces the deadline violation and increases the success rate of job completion.

Figure 3

The success rate of job completion for users.

Figure 4

The success rate of job completion with varying the deadline factors.

Figure 5 shows the profit of a cloud provider with varying the deadline factors. The profit of our mechanism is about 10.5%, 12%, 10%, and 13% higher than that of CA-provision, respectively. This figure shows that, through the winner determination by considering the job's urgency, deadline violation decreases and the profit of the provider increases.

Figure 5

The provider's profit with varying the deadline factors.

To evaluate the performance in different system scenarios, we use eight workload logs from the Parallel Workload Archive [17]. In Table 1, we show a brief description of the workload files. The table describes the log file name, the average execution time of the jobs ( $T_{w l}$ ), the average number of jobs submitted for a unit of time ( $J_{w l}$ ), the average number of processors required per job ( $P_{w l}$ ), and the total number of processors in the system ( $M_{w l}$ ). From the real workload data, we use several data such as job number, execution time, the number of allocated processors, average CPU time used, and user ID. Some records in a log file are not specified because the original files had missing information. So if a record data is missing, we randomly generate the record data within the average range of the other records using a uniform distribution. In RICC and UniLu-Gaia of the eight workloads, we decrease $M_{w l}$ by about 70% to make competitive environment. Thus, we mark the two workloads with ${R I C C}^{'}$ and ${U n i L u - G a i a}^{'}$ in the figures. Since the workloads are heterogeneous in several dimensions, we need normalization for workload logs. To normalize workload logs, we use normalized load in a workload $w l$ , $η_{w l} = (J_{w l} \times T_{w l} \times P_{w l}) / M_{w l}$ . The normalized load measures the average amount of load per processor. When analyzing the results, we use the normalized load to rank the heterogeneous log files.

Table 1

Real workload data.

Log file	$T_{w l}$ (hours)	$J_{w l}$ (jobs/hr)	$P_{w l}$	$M_{w l}$
SDSC-DS	13	10.26	62.36	8192
LLNL-Thunder	5	33.62	42.36	4008
LLNL-Atlas	8	7.6	401	9216
RICC	5	119.87	16.45	4096
PIK-IPLEX	40	20.46	34.49	2560
LCG	1	261.16	34.52	4096
LLNL-uBGL	7	22.34	576	2048
UniLu-Gaia	3	24.06	9.97	64

Figure 6 shows the success rate of job completion in different workloads. In the experiments, we set $τ_{j}$ to 2.0. Our mechanism has 18.2% more success rate than CA-provision. Figure 7 shows the profit of a cloud provider. Since the workloads are generated for different durations of time for systems with different number of processors, we scale the profit with respect to the total simulation hours and the number of processors. We define the profit per processor-hour as $Π_{w l}^{p r} = Π_{w l} / (M_{w l} \times R_{w l})$ , where $Π_{w l}$ is the sum of profits in all bidding round and $R_{w l}$ is the number of biddings provided in each workload [13]. As you can see, our mechanism has about 26.8% more profit than CA-provision. As a result, our mechanism shows the better performance with respect to the success rate and the profit than CA-provision in various workload scenarios.

Figure 6

The success rate of job completion with varying the workloads.

Figure 7

The provider's profit with varying the workloads.

5. Conclusion

To increase the provider's profit, the penalty cost for SLA violations needs to be considered. To reduce the cost, we consider the job's urgency based on the deadline constraint when winners are determined in the combinatorial auction. Taking the urgency into consideration, we calculate the probability of deadline violation for each job. Then, using the probability, we calculate the expected value of the provider's profit when the corresponding user is selected as a winner at a bidding round. The user with the larger expected value is likely to be determined as a winner. Thus, the penalty cost decreases by the decrease of SLA violation, and the provider's profit increases. The experimental results show that our mechanism has higher profit and success rate of job completion than these of the conventional mechanism. We look forward to compare the other winner determination mechanisms in the combinatorial auction and demonstrate effectiveness of our mechanism.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2015R1D1A1A09057141).

References

Truong

H.-L.

Dustdar

Principles for engineering IoT cloud systems

IEEE Cloud Computing 2015 2 2 68 76

10.1109/mcc.2015.23

Lampe

Siebenhaar

Papageorgiou

Schuller

Steinmetz

Maximizing cloud provider profit from equilibrium price auctions

Proceedings of the IEEE 5th International Conference on Cloud Computing (CLOUD '12)

June 2012

Honolulu, Hawaii, USA

83 90

10.1109/cloud.2012.19

2-s2.0-84866769702

Shirley

S. R.

Karthikeyan

A survey on auction based resource allocation in cloud environment

International Journal of Research in Computer Applications and Robotics 2013 1 9 96 102

Son

Jung

Jun

S. C.

An SLA-based cloud computing that facilitates resource allocation in the distributed data centers of a cloud provider

Journal of Supercomputing 2013 64 2 606 637

10.1007/s11227-012-0861-z

2-s2.0-84886726811

Moon

H. J.

Chi

Hacıgümüş

SLA-aware profit optimization in cloud services via resource scheduling

Proceedings of the 6th International Conference on World Congress on Services (SERVICES '10)

July 2010

Miami, Fla, USA

IEEE

152 153

10.1109/services.2010.97

2-s2.0-78049323025

Alrokayan

Dastjerdi

A. V.

Buyya

SLA-aware provisioning and scheduling of cloud resources for big data analytics

Proceedings of the 3rd IEEE International Conference on Cloud Computing for Emerging Markets (CCEM '14)

October 2014

Bangalore, India

1 8

10.1109/ccem.2014.7015497

2-s2.0-84923247795

Minarolli

Freisleben

Utility-based resource allocation for virtual machines in cloud computing

Proceeding of the 16th IEEE Symposium on Computers and Communications (ISCC '11)

July 2011

Kerkyra, Greece

410 417

10.1109/iscc.2011.5983872

2-s2.0-80052727456

Van

H. N.

Tran

F. D.

Menaud

J.-M.

Autonomic virtual resource management for service hosting platforms

Proceedings of the ICSE Workshop on Software Engineering Challenges of Cloud Computing (CLOUD '09)

May 2009

Vancouver, Canada

1 8

10.1109/cloud.2009.5071526

2-s2.0-70349789955

Park

J.-G.

Kim

J.-M.

Choi

Woo

Y.-C.

Virtual machine migration in self-managing virtualized server environments

Proceeding of the 11th IEEE International Conference on Advanced Communication Technology (ICACT '09)

February 2009

2077 2083

2-s2.0-67649871103

10.

Verma

Ahuja

Neogi

pMapper: power and migration cost aware application placement in virtualized systems

Middleware 2008: ACM/IFIP/USENIX 9th International Middleware Conference Leuven, Belgium, December 1–5, 2008 Proceedings 2008 5346

Berlin, Germany

Springer

243 264 Lecture Notes in Computer Science

10.1007/978-3-540-89856-6_13

11.

Shi

Hong

Towards profitable virtual machine placement in the data center

Proceedings of the 4th IEEE International Conference on Cloud and Utility Computing (UCC '11)

December 2011

Victoria, Australia

IEEE

138 145

10.1109/ucc.2011.28

2-s2.0-84856325634

12.

Breitgand

Epstein

SLA-aware placement of multi-virtual machine elastic services in compute clouds

Proceedings of the IFIP/IEEE International Symposium on Integrated Network Management (IM '11)

May 2011

Dublin, Ireland

161 168

13.

Zaman

Grosu

A combinatorial auction-based mechanism for dynamic VM provisioning and allocation in clouds

IEEE Transactions on Cloud Computing 2013 1 2 129 141

10.1109/tcc.2013.9

14.

Özer

A. H.

Özturan

An auction based mathematical model and heuristics for resource co-allocation problem in grids and clouds

Proceedings of the 5th International Conference on Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control (ICSCCW '09)

September 2009

Famagusta, Cyprus

1 4

10.1109/icsccw.2009.5379493

2-s2.0-77950514612

15.

Amazon EC2 Spot Instances http://aws.amazon.com/ec2/spot-instances/

16.

Choi

Lim

Resource management mechanism for SLA provisioning on cloud computing for IoT

Proceedings of the International Conference on Information and Communication Technology Convergence (ICTC '15)

October 2015

Jeju Island, South Korea

IEEE

500 502

10.1109/ICTC.2015.7354595

17.

Feitelson

D. G.

Parallel Workloads Archive

http://www.cs.huji.ac.il/labs/parallel/workload/logs.html

Optimization Approach for Resource Allocation on Cloud Computing for IoT

Abstract

1. Introduction

2. Related Work

3. Proposed Mechanism

4. Performance Analysis

5. Conclusion

Footnotes

Conflict of Interests

Acknowledgment

References