Elsevier

Journal of Systems and Software

Combinatorial double auction-based resource allocation mechanism in cloud computing market

Abstract

The cloud computing environment may be considered as market for computing and storage resources. Providers rent their available resources in the form of Virtual Machines (VM) and charge the users accordingly. One of the challenges in this market is providing a mechanism for the allocation of resources and their pricing, such that the proper benefit of both users and providers are guaranteed. In this paper, a combinatorial double auction-based market is studied in which a broker performs the allocation of the providers' VMs according to the users' requests. The proposed allocation problem is formulated as an integer linear programming model aiming at maximizing the total profit of users and providers. It is proved that the proposed model satisfies the desirable properties including: truthfulness, fairness, economic efficiency and allocation efficiency. Furthermore, due to the high complexity of the proposed model, a heuristic resource allocation algorithm with a quasi linear time complexity is presented. The results of evaluations confirm the good agreement of the heuristic algorithm with the optimization model in terms of allocation performance. Moreover, simulation results using CloudSim indicate that, compared to the previous works in literature, the proposed algorithm increases the profit of providers and users and reduces the resource wastage.

Introduction

Cloud computing is a model that enables a convenient and on-demand network access to a shared pool of configurable computing resources (Hashem et al., 2015). It can be defined as a parallel and distributed system consisting of a collection of interconnected and virtualized computer systems. These systems are presented as one or more unified computing resources. Cloud computing services are usually provided in three categories: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). In cloud computing, providers cooperate together to provide cloud services and resources for customers. A customer acquires and releases cloud resources by requesting and returning virtual machines (VMs) in the cloud (Li and Li., 2013).

Cloud users are willing to achieve the highest possible level of quality of service (QoS) at a reasonable price. On the other hand, cloud providers aim at increasing their profit as much as possible. In addition, the amount of resources and workloads of providers are changed over the time. In such a case, satisfying QoS requirements of the users and simultaneously ensuring the profit of the providers is the main issue that should be considered. The key answer for this problem is designing an appropriate pricing mechanism. Pricing is the process of determining what a service provider will receive from an end user for providing a specific service. In literature, pricing is practiced by one of the following methods (see Basu et al., 2015 and Huang et al., 2015):

1) Fixed pricing model: users pay a fixed price for the service during subscription period, 2) Dynamic (differential) Pricing Model: users pay a variable price based on service features, user characteristics, and the amount of purchased product or user priorities, that is, the prices are changing during the time. 3) Market-dependent Pricing Model: users pay a fixed price for each period of time and after the end of this period, the paying price is re-set for the next period according to the real-time market conditions such as supply, demand and revenue of users and providers. In this pricing mechanism, the price is determined by one of the market-based mechanisms such as bargaining and auction. The determined price influences user behavior, provider honesty and organization's success (Al-Roomi et al., 2013). Therefore, an appropriate pricing mechanism is of great importance and leads to attract more users and generate more revenue for providers. Raja et al. (2016) claimed that the success of cloud computing in the IT market and IT organizations can be achieved by developing appropriate pricing techniques.

The fixed-price scheme has several drawbacks: First, it is not economically efficient. Second, it does not reflect the equilibrium prices that arise from market demand and supply and thus decreases the revenue for providers (Zaman and Grosu, 2013). On the other hand, in dynamic pricing schemes, prices are continuously changing, that lead to increase in computation and complexity of these schemes. Moreover, frequent price changes are not desirable from the user point of view. As a result, it seems that the market-dependent pricing models are superior to the both cases. Our pricing model in this paper falls in this category. We propose a combinatorial double auction based pricing mechanism for pricing and allocating of VMs in cloud environments. Combinatorial double auction is a market-dependent pricing mechanism which allows many-to-many price negotiations between providers and users (Samimi et al., 2016). Participants of combinatorial auctions bid for bundles of items instead of individual items, this makes the bidders state their valuations in a more reasonable way, especially when the requested items are complementary to each other. Otherwise, if the customer bids for each item separately, there is a risk that he/she may not be able to obtain all the necessary items to fulfill his/her demands (Zaman and Grosu, 2013). It should be noted that in many such scenarios the partially acquired resources are useless.

In this paper we consider a market consist of providers, users and a broker for trading VMs in cloud environments. The problem of allocating VM instances in this market is modeled as a combinatorial double auction-based problem and is formulated as an integer linear programming (ILP) model. The objective of the formulation is to efficiently allocate some sets of VM instances (with different attributes and different quantities) offered by different providers to several users requesting a set of VM instances to fulfill their tasks. This allocation should maximize the financial profit of users and providers and should reduce the wasted resources of VMs. The value of each VM is set based on its computational capabilities such as processing power of CPUs, memory capacity, storage capacity and BW capacity. Since the proposed model is NP-HARD, we propose a heuristic algorithm to solve it with a quasi linear time complexity. The proposed algorithm tries to allocate the VMs of providers to users in a way that the total profit of both sides are close to the optimal model as much as possible.

The remainder of this paper is organized as follows. Section 2 overviews the related works. Section 3 describes the studied cloud computing market. Section 4 explains the proposed integer linear programming model for combinatorial double auction-based VM allocation. Some special cases of the proposed model are also investigated in this section. Section 5 explains the proposed heuristic algorithm in details. Section 6 evaluates the performance of the proposed model and algorithm by means of CloudSim simulator and finally, Section 7 concludes the paper.

Section snippets

Related works

Cloud resource allocation problem has been extensively studied in the literature. In this regard, different optimization methods are taken advantage such as statistical optimization, bio-inspired optimization, integer programming, linear programming, and greedy optimization. Among these optimization methods, integer, linear and greedy methods are computationally effective compared with bio-inspired and statistical methods (Yousafzai et al., 2017).

Recently, many auction-based models and

The cloud market model

In this paper, as shown in Fig. 1, a cloud computing market is considered consisting of three entities; users, providers and a broker. Users request a bundle of several different VMs to fulfill their tasks. Each VM includes four resources: CPU, memory, storage and BW. The user determines a bid value and the time duration he intends to keep the requested VMs according to his budget and real-time market conditions. Then he sends a bundle composed of requested VMs, offered bid and the required

Combinatorial double auction-based virtual machine allocation model

The proposed model considers m providers (p1,…,pm) and n users (u1,…,un). Each provider i (i = 1,…, m) provides A types of VMs. Sil denotes an instance of the VM of type l (l = 1..A) which is offered by provider i. The resources feature (i.e., CPU, memory, Storage, BW) of VMl offered by different providers, may be different. bidP i is the price that provider i is willing to receive for his offered bundle including different VMs. bidP il is the price that provider i is willing to receive for VMl

Proposed algorithm for solving the allocation model

The proposed model in Section 4 is an integer linear programming problem (ILP) that contains N binary variables and a searching space as big as 2 N solutions to be explored leading to an exponential time complexity, thus the problem is NP-Hard. In this section, we propose a greedy mechanism to solve the model in a reasonable time. In the followings we explain the proposed greedy algorithm in details.

First of all, the priority of users should be determined to increase the efficiency of the

Performance evaluation

In this section the performance of the proposed model and algorithm is evaluated. The proposed ILP model is solved using Lingo and the proposed algorithm is simulated in CloudSim. The scenario under study is similar to the market shown in Fig. 1 including 20 users and 7 providers. Each user requests different quantities of at most 4 types of VMs. From the other side, each provider offers different quantities of at most 4 types of VMs. The proposed bundles of users and providers are shown in

Conclusions and future works

We have proposed a combinatorial double auction-based mechanism for VM allocation in cloud computing environments. The allocation mechanism has been formulated as an integer linear programming model and it has been proved that the proposed model provides truthfulness, fairness, economic and allocation efficiency. Furthermore, since the proposed model is NP-Hard, a greedy algorithm with low time complexity has also been proposed. The Simulation results using CloudSim has shown a good agreement

Saleh Yousefi is an Associate Professor at Computer Engineering department, Urmia University, Urmia, Iran. He received his BS and MS in Computer Engineering (in the hardware engineering field) and PhD in Computer Engineering (in the networking field) from Iran University of Science and Technology, Tehran, Iran, in 1999, 2002 and 2008, respectively. His research interests include the performance evaluation of computer networks, cloud computing, mechanism design, and (vehicular) ad hoc networks.

Cited by (42)

Saleh Yousefi is an Associate Professor at Computer Engineering department, Urmia University, Urmia, Iran. He received his BS and MS in Computer Engineering (in the hardware engineering field) and PhD in Computer Engineering (in the networking field) from Iran University of Science and Technology, Tehran, Iran, in 1999, 2002 and 2008, respectively. His research interests include the performance evaluation of computer networks, cloud computing, mechanism design, and (vehicular) ad hoc networks.

Seyedeh Aso Tafsiri received his B.S. degree in Software Engineering in 2012 from Kurdistan University, Sanandaj, Iran and M.Sc degree in Information Technology-Networking from Urmia University in 2015. Her research interests include Cloud Computing, Mechanism Design and wireless networking.

View full text

© 2017 Elsevier Inc. All rights reserved.