# Optimization Approach for Resource Allocation on Cloud Computing for IoT

Authors: Yeongho Choi; Yujin Lim
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## 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.


---

## Body

## 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 Section2, 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 throughm different types of VM instances, VM1,VM2,…,VMm. The computing power of a VM instance of type VMi,i=1,…,m, is wi, where w1=1, w1<w2<⋯<wm, and w=(w1,w2,…,wm) [13]. We consider that w is determined mainly by the number of cores, like Amazon EC2 [15]. Let ki be the number of VMi 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 k1,k2,…,km as long as ∑i=1mwiki≤M. We consider n users u1,…,un who request computing resources from the provider specified as bundles of VM instances. A user uj requests VM instances for its job jobj by submitting a bid Bj=r1j,…,rmj,vj to the provider, where rij is the number of requested instances of type VMi and vj is the price user uj is willing to pay to use the requested bundle of VMs for a unit of time. In addition, let us denote by pj the amount paid by user uj for using its requested bundle of VMs, and pj and vj can be different (usually pj≤vj). 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 deadlinedj for job jobj of user uj. For simplicity’s sake, we assume that a user has one job at a time. Our problem is that Kj, Kj≤dj biddings should be succeeded to complete jobj before dj gets to end. The current bidding round θj is the sum of the number of successful biddings kj, kj<Kj and the number of bidding failures fj; in other words θj=kj+fj and θj≤dj. We define the problem as the combination of dj taken Kj:(1)CdjKjsubject to(2)dj≥Kj.The success probability of Kj biddings before dj is as follows:(3)1CdjKj.We identify that the probability of successful job completion needs to be increased as fj or θj increases. At the current round θj with kj successful bidding, to complete the job before dj, Kj-kj successful biddings need more. The remaining rounds before dj are dj-θj=dj-fj-kj. Thus to get the probability of job completion before dj, (3) is rewritten as follows:(4)Prj=1Cdj-fj-kjKj-kj=Kj-kj!Pdj-fj-kjKj-kj.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 CR 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 Cjpenalty. With the probability of SLA violation in (4), we define Ejprofit the expected value of the provider’s profit for uj as follows:(5)Ejprofit=Prj⁡vj-CR∑i=1mwirij+1-Prjvj-CR∑i=1mwirij-Cjpenalty.In (6), we normalize Ejprofit with the maximum value of Ejprofit to remove the dependence on vj. The maximum value of Ejprofit indicates the expected value when there is no SLA violation:(6)Ejprofitvj-CR∑i=1mwirij.Using (6), winners are determined at each round.Figure1 shows that Prj increases as kj or fj increases in our mechanism. We set dj and Kj to 15 and 10, respectively. Thus, when fj>5, jobj is not completed before the deadline. In the figure, Prj gets to 1 in order to complete the job before the deadline, when fj=5. Besides, as you can see, fj has the bigger impact than kj on Prj. Because Ejprofit increases as Prj increases, the probability that uj 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 useUniLu-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 CR to 0.5 and Cjpenalty to 10 percent of vj. Kj is randomly selected from (1, 20) and the average execution time of a job is multiplying bidding time interval Δt with Kj.Figure2 shows the probability of bidding success at current round θj when the remaining bidding rounds before dj 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.Figure3 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 uj 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 Kj; thus the deadline is dj=τjKj. 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.Figure5 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 (Twl), the average number of jobs submitted for a unit of time (Jwl), the average number of processors required per job (Pwl), and the total number of processors in the system (Mwl). 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. InRICC andUniLu-Gaia of the eight workloads, we decrease Mwl by about 70% to make competitive environment. Thus, we mark the two workloads with RICC′ and UniLu-Gaia′ 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 wl, ηwl=(Jwl×Twl×Pwl)/Mwl. 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
64Figure6 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 Πwlpr=Πwl/(Mwl×Rwl), where Πwl is the sum of profits in all bidding round and Rwl 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.



---

*Source: 3479247-2016-03-02.xml*