Keywords

1 Introduction

With the rapid development of information and data in the Internet age, computational domain including science, engineering, and business need to process large-scale, massive data. In this case, the concept of cloud computing is proposed. Cloud computing is a further development of distributed computing, parallel processing, and grid computing [13]. It is a system based on Internet computing that can provide hardware services, infrastructure services, platform services, software services, and storage services to a variety of Internet applications [6, 7].

Virtualization is a key technology of cloud computing, which can turn a host into multiple virtual hosts which have different computer systems resources that can support applications. Virtualization has lot of advantages. By reducing the number of physical hosts by turning the physical host into a virtual host, energy consumption is reduced and energy efficiency is achieved. In addition, virtualization is a cost-effective technology [3]. However, load balancing is a challenge. There are overloaded hosts and underutilized hosts. When too many VMs are running on one host, the host will become overloaded and cause exceptions. VM migration can solve this problem. In this case, we must select one or more VMs to migrate once the host become overloaded and find the best destination host for these selected VMs which to be migrated. Double auction is widely used in the field of artificial intelligence to solve the problem of resource competition [5, 14]. In this paper, we proposed a VM migration algorithm based on double auction, which considers communication cost.

The rest of this paper is organized below. Section 2 reviews some related works. In Sect. 3, we detail system model. We introduce VMs-GSA and VMM-DAM in Sect. 4. Section 5 is simulation results and conclusion.

2 Related Work

In recent years, VM migration in the data center has been widely studied and has become a hot topic. The process of VM migration mainly involves energy consumption and communication costs. In order to improve energy efficiency of the data center, Tao et al. [10] proposed a new algorithm named BGM-BLA for VM migration, which considered three factors including energy consumption, communication cost, and migration cost. The algorithm in [10] targets these three factors has two parts. The first part generates bucket codes. The second part is to learn and mutate to reduce communication cost and migration cost based on the original bucket codes and output the Pareto set of solutions. Beloglazov et al. [2] proposed energy-aware allocation heuristics which provides the resources of servers or hosts to client applications while guaranteeing quality of service (QoS). In [8], the authors proposed three VM migration schemes which take the traffic factor and VM clustering into account, which are the improvement of papers [12]. VM clustering includes two steps. First step forms the VM graph on same host, in which vertexes are VMs and edges are communications between VMs. Then, form clusters. In addition, many studies have considered communication factors in the migration of VMs, such as [4] and [11].

Zhang et al. [15] apply the genetic algorithm (GA) and artificial bee colony (ABC) to the problem of VM migration problem and aim to find an approximate optimal solution through repeated iterations. The GA first generated a population of PopSize chromosomes which is a vector represented the mapping of VMs and servers. Then, cross and mutate the chromosomes and compare with the previous chromosome to select smaller chromosomes with smaller fitness value. In [1], migration algorithm is investigated, which is a new system based on matching game theory. The paper applied firefly algorithm to energy-aware VM migration, which migrates the maximally loaded VM to the least loaded active node.

3 System Model

We consider that there are K hosts in data center and the relation between these hosts can be denoted as an undirected graph DC = (H, D), where H = {h 1, h 2,…, h k} represents the set of hosts and ∀(h i, h j) ∈ D represents the edge between hosts h i and h j. The weight W(h i, h j) is the communication distance.

Each host h j ∈ H can be represented by a 3-tuple (τ(h j), sl(h j), V (h j)), where τ(h j) is the threshold of h j, i.e., if h j’s load exceeds this value τ(h j), h j is overloaded. sl(h j) indicates the safety limit of h j, i.e., if h j’s load is lower than this value sl(h j), h j is underutilized. \(V({h_j}) = \{ v_1^j,v_2^j,\ldots ,v_n^j\}\) is the set of VMs residing on h j. The communication relation of VMs residing on h j is represented by an undirected graph G = (V, E), where V = V (h j) and \(E = \{ (v_i^j,v_l^j)|\mbox{where }v_i^j\mbox{ and }v_l^j\mbox{ exist communications}\}\) is the set of edges. The weight \({W'}(v_i^j,v_l^j)\) represents VM traffic. \(\forall v_l^j \in V({h_j})\) that communicate with \(v_i^j\) are called \(v_i^j\)s neighbor, i.e., \(N(v_i^j) = \{ v_l^j|(v_i^j,v_l^j) \in E,\forall v_l^j \in V({h_j})\}\).

\(v_i^j \in V({h_j})\) have two attributes denoted by a 2-tuple \((O(v_i^j),C(v_i^j))\), where \(O(v_i^j)\) denotes the size of occupied resources of \(v_i^j\). \(C(v_i^j) = \sum \nolimits _{v_l^j \in N(v_i^j)} {{W'}(v_i^j,v_l^j)} \) is the traffic of \(v_i^j\). The residing set of overloaded hosts is represented by \({H^ + } = \{ {h_j}|\sum \nolimits _{i \in V({h_j})} {O(i)} > \tau ({h_j}),{h_j} \in H\} \) and \({H^ - } = \{ {h_j}|\sum \nolimits _{i \in V({h_j})} {O(i)} \le sl({h_j}),{h_j} \in H\} \) denotes the set of underutilized hosts. We use \(h_j^ + \in {H^ + }\) to denote overloaded host h j and \(h_j^ - \in {H^ - }\) to denote underutilized host h j.

Our work is mainly focused on the communication costs of VMs migration in data center. Let mapping function σ : V M → H − denotes the mapping between VMs and underutilized hosts. Let vm i denote the selected VM from overloaded host. The communication cost that vm i matches \(h_j^- \in H^-\) is defined as below

$$\displaystyle \begin{aligned} Cost_{i} = \sum_{{v_{l \in N(v{m_i})}}} {W'(v{m_i},{v_l})} W(h_{\sigma(i)}^-,h_{\sigma(l)}^-) \end{aligned} $$
(1)

4 VM Migration Algorithm

In this section, VM migration algorithm based on heuristic consists of two parts: (1) selecting VMs from overloaded hosts to migrate and we proposed VMs-GSA to determine these VMs, (2) obtaining the mapping between VMs and underutilized hosts and we employed VMM-DAM to obtain it.

4.1 VMs-GSA Design

The idea of VMs-GSA is to select the VMs resided on \(h_j^ + \in {H^ + }\) with smaller traffic and smaller occupied resource to migrate, thereby reducing communication costs. Therefore, the algorithm will be executed as follows. First of all, the VMs residing on \(h_j^+\) are sorted by \(O(v_i^j)C(v_i^j)\) in the ascending order. Then, starting from \(v_i^j\) with the highest \(O(v_i^j)C(v_i^j)\) value, select the VMs in sequence and put them in the list W until the host is not overloaded.

Algorithm 1 VMs-GSA (one host hj+)

4.2 VMM-DAM Design

Auction Model

We consider that the allocation process of finding the destination hosts for VMs which to be migrated is modeled as an auction process. Auction market consists of three entities. The buyers refer to the VMs which to be migrated. The sellers are the underutilized hosts. The third-party auctioneer mainly solves the mapping problem and final payment. Buyer vm i ∈ V M submits a bid represented by B i to auctioneer and B i can be denoted by a 2-tuple:(O(vm i), v i), where O(vm i) is the size of vm i’s resource demand and v i indicates vm i’s valuation. B = {B 1, B 2, …, B N} denotes the bids of all buyers. Seller \(h_j^- \in H^-\) submits a bid S j to the auctioneer. S j is denoted as a 2-tuple: (o j, p j(m j)), where p j(m j) denotes the unit price of the resource o j provided by \(h_j^-\), which is piecewise constant function. m j is the quantity sold of \(h_j^-\). The bids of all sellers are denoted as S = {S 1, S 2, …, S M}.

Allocation Algorithm Design

Let \({d_i} = {v_i}/\sqrt {O(v{m_i})}\) be vm i’s bid density. Firstly, we sort the VMs according to d i in the descending order. Let L be the sorted VMs list. Then, select VM from the sorted list L in turn to match seller. Suppose the selected VM currently is vm i. The host \(h_{j^*}^-\) which satisfies two conditions of vm i with maximum revenue increment RI ij = v i − O(vm i)p j(m j) is matched with vm i. One condition is that the host can meet demand of vm i and another is that the ask price of the host is more than vm i’s valuation. Next, the algorithm finds other VMs that reside on the vm i’s original host from L and put them in list \(L_i^{\prime } \subset L\). Then, select VM from \(L_i^{\prime }\) in turn to match seller. Suppose the selected VM currently is vm u. If \(h_{j^*}^-\) satisfies the conditions of vm u, vm u is matched with \(h_{j^*}^-\). Otherwise, the algorithm finds other hosts which satisfy conditions of vm u. The host with maximum φ uk = αRI uk − βCost u becomes the destination host of vm u, where α and β are the weight coefficients. The algorithm loops until all the VMs in L are matched.

Algorithm 2 VMs allocation algorithm

Scheme of Payment

We employ “Vickery” price to the payment of buyers [9]. The “Vickery” price of vm i is defined as the value of the size of vm i’s demand multiplied by the highest bid density of vm l among losers who would become the winner if vm i would not participate in the auction. The winner vm i’ payment c i to its matched seller is \({c_i} = {\max \{{d_l}\sqrt {O(v{m_i})} ,O(v{m_i}){p_j}({m_j}) \} }\). The payment \(\dot b_j\) to the winner \(h_j^-\) is the sum of payments of all the VMs that matched \(h_j^-\).

5 Results and Conclusion

In this section, we simulated VMs migration in the data center and summarized the paper. Simulation experiment has shown that compared with the random algorithm, the total amount of communication generated by VMs-GSA reduces about 35% and the VMs-GSA is approximately similar to the enumeration algorithm. However, the computational complexity of the enumeration algorithm is very huge. The load of overloaded hosts drops significantly to the threshold after the migration by VMM-DAM and VM migration is almost 100% successful and the communication generated by VMM-DAM is small.

We investigated traffic-aware VM migration problem in data center. The VM migration algorithm consists of two parts. We designed VMs-GSA in the first part to select VMs with the low communication costs, which greatly reduces the communication generated by VM migration. VMM-DAM is applied to the second part of VM migration to match hosts with the low communication costs. Simulation experiment has shown that the VMs-GSA and VMM-DAM are traffic-aware and effective.