Definition 1.

Cloud computing environment (CCE). Cloud computing environment can be described as a pair: (DC, B), where,

1. (i)

   DC is a set of distributed data centers, written as DC=∪i=1,2,…,|DC|{dci} , and dc_i denotes the i^th data center. The detailed description of data center will be given in Definition 2.

2. (ii)

   B is a matrix, representing bandwidth between data centers, and the element b_ij means the bandwidth between two data centers dc_i and dc_j, indicating the network transmission capacity.

The bandwidth may fluctuate from time to time according to peak or off-peak data access time in practice. In this paper, we simplify the problem and regard the bandwidth as a static value, ignoring the volatility during different access time. On the other hand, the value of bandwidth means the time of transferring data from one data center to another. So, we will use the bandwidth as a basis for calculating the transfer time in the following section. Fig 1 depicts a typical architecture of a cloud computing environment with 7 data centers.

Fig. 1.

Architecture of cloud computing environment.

Data centers provide the basic ingredients such as storage, CPUs, and network bandwidth as a commodity by specialized service providers at low unit cost. In this paper, we define the data center as follows.

Definition 2.

Data center (DC). Each data center dc_i∈DC can be described as a 7-tuple (dc_i, sp_i, cp_i, tp_i, D, ts_i, vs_i), where,

1. (i)

   dc_i is the identifier of a data center, and is unique in CCE;

2. (ii)

   sp_i means the storage price policy of data center dc_i;

3. (iii)

   cp_i means the computation price policy of data center dc_i;

4. (iv)

   tp_i means the transfer price policy of data center dc_i. Usually, sp_i, cp_i and tp_i are all determined by the cloud service providers;

5. (v)

   D=D_org⋃D_gen is a set of original data set and generated data sets on the data center dc_i;

6. (vi)

   ts_i is the total space of data center dc_i, whose unit is TB; and,

7. (vii)

   vs_i is the size of vacant space on data center; means the extra storage capacity of dc_i.

A data set involves its size, stored places and its provenance. In this paper, we define a data set as follows.

Definition 3.

Data set (D). A data set d_m∈D can be described as a 5-tuple (d_m, s_m, sp, f_i, provSet_m), where,

1. (i)

   d_m is the identifier of data set, which is unique in the cloud;

2. (ii)

   s_m is the size of data set d_m;

3. (iii)

   sp∈DC, is the data set d_m’s storage place;

4. (iv)

   f_i is a flag, which denotes the status whether data set d_m is stored or deleted in the system; and,

5. (v)

   provSet_m is the set of stored provenances that are needed when regenerating data set d_m. The detailed description of provSet_m will be given in Definition 5.

Definition 4.

Data sets dependency graph (DDG). Data sets dependency graph is a directed acyclic graph, and can be described as a 3-tuple (V_D, E, φ), where,

1. (i)

   V_D={d₁, d₂, …}, is a set of nodes; and each node denotes a data set;

2. (ii)

   E={e₁, e₂, …}, is a set of edges between pair of nodes;

3. (iii)

   φ is a mapping from each edge e_k to pair of nodes (d_i, d_j) if these two data sets, d_i and d_j, have generation relationship, in other words, d_i is a predecessor data set of d_j.

Fig 2 shows a simple DDG, where each node in the graph denotes a data set.

Fig. 2.

A simple data dependency graph.

In Fig 2, data set d₁ pointing to data set d₂ means that d₁ is used to generated d₂; and d₂ pointing to d₃ and d₅ means that d₂ is used to generate d₃ and d₅ based on different operations. Also, data set d₄ and d₆ pointing to dataset d₇ means that d₄ and d₆ are used together to generate d₇. Meanwhile, we denotes a data set d_m in DDG as d_m∈DDG, and to better describe the relationships of data sets in DDG, we define two symbols → and ↮:

1. (i)

   → denotes that two data sets have a generation relationship. In other words, d_n → d_m means that d_n is a predecessor data set of d_m in DDG. For example, in the DDG depicted in Fig 2, we have d₁ → d₂, d₁ → d₄, d₅ → d₇, etc. Furthermore, generation relationship is transitive, i.e. d_i→d_j→d_k ⇔ d_i→d_j ⋀ d_j→d_k; d_i→d_j ⋀ d_j→d_k ⇒ d_i→d_k.

2. (ii)

   ↮ denotes that two data sets do not have a generation relationship. In other words, d_n ↮ d_m means that d_m and d_n are in different branches in DDG. For example, in the DDG depicted in Fig 2, we have d₃ ↮ d₅, d₃ ↮ d₆, etc. Furthermore, ↮ is commutative, i.e. d_m ↮ d_n ⇔ d_n ↮ d_m.

Obviously, DDG records the provenances of how datasets are derived in the system as time goes on. To generate a dataset in the cloud, we need to find its stored predecessors and start the computation from them.

Definition 5.

Data set provenance (provSet). Formally, we can describe a data set d_m’s provenance provSet_m as follows:

In this way, provSet_m is the set of nearest stored predecessors of d_m in DDG. Fig 3 describes the provSet_m of a data set d_m in different situations. Therefore, the regeneration of a data set includes not only the computation of the data set itself, but also the regeneration of its deleted predecessors, if any. In other words, data set provenance is the set of references of stored predecessor data sets that are adjacent to d_m in the DDG.

Definition 6.

Total data set management cost of data set d_m . The total data set management cost of data set d_m during a time period τ, is the sum of its storage cost, transfer cost, and generation cost if needed, written as:

1. (i)

   TCost_dm is the total management cost of data set d_m in period τ;

2. (ii)

   tc_strg_dm, the sum of storage cost, is the total cost used to store the data sets on data centers;

3. (iii)

   tc_trsf_dm, the sum of transfer cost, is the total cost for transfer data d_m to another data center;

4. (iv)

   p ∈ {0,1}, p=0 means the status of data set d_m is “stored”, while p=1 means the status is “deleted”;

5. (v)

   tc_gen_dm, the sum of computation cost, is the total cost for regeneration data set d_m from its provSet_m.

Next, we will present these costs computational approaches separately in detail.

Definition 7.

Storage cost function (scf). Storage cost function (scf) on data center dc_m can be described as a 4-tuple (itv_k, size_lk, size_hk, p_k), where,

1. (i)

   itv_k is interval identifier, and k is a integer value from integer 1 to n;

2. (ii)

   size_lk is the lower storage bound of interval k;

3. (iii)

   size_hk is the upper storage bound of interval k;

4. (iv)

   p_k is storage price per unit time in interval k .

5. (v)

The total storage cost is the storage cost function scf multiplied by data set sizes and their respective storage time during the intervals. Consequently, the data storage cost on data center dc_m can be defined as follows.

Definition 8.

Total storage cost (tc_strg). The storage cost of data set d_m during a certain time period τ can be defined as follows:

1. (i)

   l is the minimum integer that guarantees the following condition:

   ∑k=1l(itvk.sizehk−itvk.sizelk)≥dm.sm;

2. (ii)

   itv_k, size_hk and size_lk have the same meaning as in Definition 7;

3. (iii)

   scf(k) is the CSP’s storage cost function as defined in Definition 7;

4. (iv)

   τ is the storage time.

In this model, the price varies with respect to data size and storage time on data center. For example, using Amazon S3 for storage pricing (referred to Table 2) and considering that d_m has been stored for 6 months with 2TB (2048 GB) data size, then the storage cost is:

Compared to the other storage cost models, interval storage cost ratio is the change in the total cost that arises when the quantity produced changes by one unit. So, it can effectively reflect the real storage cost of a data set.

Definition 9.

Data transfer cost function (tcf). Data transfer cost function (tcf) can be defined as a 5-tuple (itv_k, type, size_lk, size_hk, p_k), where,

1. (i)

   itv_k is interval identifier, and k is a integer value from integer 1 to n;

2. (ii)

   type∈{input, output}, means the type of transferred data sets;

3. (iii)

   size_lk, size_hk, means the lower and upper transfer size bound of interval k separately;

4. (iv)

   p_k is the data transfer cost ration in interval k.

In this way, the total transfer cost tc_ trsf_dm is the product of the CSP’s atomic transfer cost function by the total size of transferred data.

Definition 10.

Data transfer cost (tc_trsf_dm). Data set transfer cost of data set d_m can be defined as:

1. (i)

   itv_k, size_hk and size_lk have the same meaning as in Definition 9;

2. (ii)

   tcf(k) is the CSP’s transfer cost function as defined in Definition 9, where k is the interval index;

3. (iii)

   l is the minimum integer that guarantee the following condition:

   ∑k=1l(itvk.sizehk−itvk.sizelk)≥dm.sm.

Moreover, recall the Amazon EC3’s transfer cost is variable. It is free for the first GB. Then, it becomes $0.12 up to 10TB, and so on (Section 2.2). For example, using Amazon EC3’s data sets transfer cost model and considering that d_m with 10TB data size is transferred from current data centers to another, and then the cost is: tc_trsf_dm=0×1+0.12×(10-1)=$1.08.

Definition 11.

Computation cost function (ccf). Computation cost function (ccf) can be defined as a 3-tuple (k, type, p_k), where,

1. (i)

   k means index identifier;

2. (ii)

   type is data center configurations types;

3. (iii)

   p_k is the computation cost in configuration type.

Based on the computation cost function, we can define the data set generation cost from its direct predecessor.

Definition 12.

Data set computation cost from its direct predecessor (dp_gen). Generation cost for a data set d_m is proportional to its CPU instance time t and CPU computation cost function ccf(dc_i), and can be described as:

1. (i)

   dp_gen_dm denotes the generation cost of data set d_m from its direct predecessors;

2. (ii)

   ccf(dc_i) is computation cost function, where dc_i is i^thdata center;

3. (iii)

   t is the amount of time spent for generating data set d_m, can be obtained from the system logs.

In this paper, we only consider the linear generation relation for the sake of simplification. And further, not all the data sets are stored in the cloud, in other words, some data sets’ status are “deleted” according to their usage frequency and other cost constraints. In this case, when we want to regenerate a data set in DDG, we have to start the computation from the data set in its provSet. Hence, for data set d_m, its generation cost can be defined as follows.

Definition 13.

Generation cost for data set d_m (tc_gen). A data set d_i’s generation cost from its provSet can be described as:

1. (i)

   tc_gen_dm is the total generation cost each time;

2. (ii)

   dp_gen_dm is the generation cost from its direct predecessor;

3. (iii)

   d_k is a data set from d_m’s provSet_m whose states are “deleted”.

From above, we can easily know that tc_gen_dm is a total cost of (1) the generation cost of data set d_m from its direct predecessor data set, and, (2) the generation costs of d_m’s deleted predecessors that need to be regenerated as well.

Theorem 1.

For a data set d_m, its replicas placements problem with the minimum cost is NP-Hard.

Proof.

We can map the data centers to a graph G(V, E): the data set dc_i are mapped as node v_i, and all nodes constitute a set V={dc₁,dc₂, dc₃,…, dc_n};

E={e₁, e₂, e₃, …, e_p}, e_k represents the connection from dc_i to dc_j, and the weigh is transfer cost multiplied by transfer times;

S represents the data centers set with data set replicas, S⊆V;

∀s∈S, Ds={dc_s1, dc_s2, … } means the data centers access from data center Ds.

Then, the minimum cost replicas placements strategy can be modeled as follows:

1. (i)

   Ds≠∅, and ∪dci∈DsmDsm is a covering of set with all data centers;

2. (ii)

   λ_i is the request times on data center dc_i;

3. (iii)

   tc_trsf_dm is the transfer cost each time;

It is obvious that the objective function of the data management cost with replicas is identical to the location problems. However, the major models, such as Fixed Charge Location Model, the Covering Model in None-Competitive Location Theory and the Medianoid and Centroid Model [28,29] from Competitive Location theory, are all NP-Hard, i.e. computationally difficult, combinatorial optimization problems. In this way, for a data set d_m, its replicas placements problem with the minimum cost is NP-Hard.

Theorem 2.

For a data set d_m, the minimum cost real- and pseudo-replicas placements strategy is NP-Hard.

Proof.

As a specific circumstance, we define each data set’s generation cost as 0, then the minimum cost for real and pseudo replicas strategy is the same as the minimum cost for replicas placements strategy, as is shown in Theorem 1. Accordingly, we know that the minimum cost for replicas and pseudo-replicas placements strategy is NP-Hard.

Therefore, exact algorithms are computationally feasible only for medium sized problems or for special cases, not include the general cases [30]. As a result, much research has been devoted to devising heuristic solution procedures which run in reasonable computer time and yield solutions of acceptable quality.

6.2.1 Representation scheme and fitness function

The first step in designing a genetic algorithm for a data sets problem is to devise a suitable representation scheme. The representation scheme developed is an n_f-bit string as the chromosome structure, where n_f is the number of potential data sets replicas placements. A value of 1 for the ith bit implies that a replica is located in the ith data center. The representation of an individual’s chromosome (solution) is illustrated in Fig 6.

Fig. 6.

Example of replicas placements chromosome representation.

The data centers network illustrated in Fig 6. has eight data centers. The case (a) represents the situation when three replicas are located in data centers dc₀, dc₂ and dc₆, and case (b) illustrates the situation when replicas are located in data centers dc₀ and dc₃. In addition, data center dc₇ can generate data set from its provenance. The respective binary representations for cases (a) and (b) are also shown in the same figure.

The fitness function in a GA is a measure of goodness of a solution to the objective function. In our modified GA, the fitness of an individual is directly related to its objective function value, which is defined as minimum management cost.

The fitness function value of each possible solution to the replicas placements problem is calculated by finding the set of data centers belonging to the solution being evaluated and adding the demands that are covered by these data centers. Care must be taken in order to avoid demands being counted several times since each data center belongs to only one d_s (d_s∈DC).

6.2.2 Parents selection-procedure and crossover

We will now address the parents’ selection, i.e., solutions chosen for crossover. And we chose the Binary Tournament Selection Method, for the reasons that: (i) it can be implemented very efficiently; (ii) it has been shown that this method gives solutions whose quality compare favorable to the ones proposed by other methods.

In this paper, we chose the crossover operator fitness-based fusion proposed in [31]. This operator is more capable of generating new solutions when two parent solutions are similar in structure than the one-point crossover operator, since it focuses on the difference in the two structures. However, the possibility of getting an offspring identical to one of its parents still remains. As a result of this problem, the following modification was made to the over all crossover operator. The crossover algorithm can be described as in Algorithm 2.

6.2.3 Mutation

Mutation is a process that reverses the structure of a chromosome and hence produces albinos, i.e., individuals with different chromosome properties from the majority in a population. In this work, the mutation operator works by selecting randomly one of the data centers and transferring this to destination data center. The new stored place is also picked randomly from the set of empty possible places to located data storage.

Once new child solutions have been constructed through the GA operators, the child solutions will replace “less fit” members of the population. The average fitness of the population will improve if the child solutions have better fitness than those of the solutions being replaced.

In our GA, we used the incremental replacement method. Using this method, the best solutions are always in the population and the newly created solutions are immediately available for selection and reproduction. Note that when replacing a solution, care must be taken to prevent excessive copies of a solution from entering the population. Allowing too many duplicate solutions to exist in the population may be undesirable because a population could come to consist of identical solutions, thus severely limiting the GAs ability to generate new solutions.

7.2.1 Simulation 1: Data management cost factors values comparison

Fig 9 describes the total storage cost, transfer cost and total cost with different number of replicas, from where we can see that the storage cost is less than transfer cost at the beginning, for the reason that much data be transferred in the system. However, with the replicas number increased, the storage cost gradually grows larger for the reason that more replicas need to be stored on data centers. Also, the total cost has a minimum value with three replicas, which means the optimal solution in this circumstance.

Fig. 9.

Storage cost, transfer cost and total cost with different number of replicas.

Next, we will present the pseudo-replicas strategy under different data sets usage frequencies, as shown in Table 10. In this circumstance, the data set storage cost is only for the original data set, while the computation cost will gradually increase with the number of requests increased.

Fig 10 illustrates the data management cost comparison with different number of data set requests, from where we can see that (1) the storage cost is a fixed value for the reason that the cost is only for the original data set; (2) the computation cost and transfer cost will grow with the requested number increased for the reason that the computation cost is proportional to the number of generation.

Fig. 10.

Data management cost with different number of data set requests.

7.2.2 Simulation 2: Feasibility and effectiveness of replicas and pseudo-replicas strategy

In order to evaluate the performance of combination replicas strategy, we have run a large number of simulations with different parameters settings. We present some representative results in this sub-section. Table 11 summarizes the simulations results of real-replicas strategy and pseudo-replica strategy. In this table, we list the best replicas solution and pseudo-replica solution, such as replicas numbers, their storage places, the average CPU solution time, etc al.

From Table 11, the following remarks can be made regarding the results illustrated. (i) The real-replicas and pseudo-replicas solution can reach the better or the same result for all the data sets, compared to the solution without pseudo-replica. Though the mean CPU time is bigger than the traditional replicas solution, the number of replicas and the management cost are both optimal. (ii) The combination of real-replicas and pseudo-replicas strategy can decrease the storage space on data centers, for the reason that the less number of real replicas leads to little storage. In this way, the algorithm reached the same objective function value in all of the instances. These results indicate that the real-replicas and pseudo-replicas placements strategy availability and validity.

To further illustrate the cost reduction between combination strategy and other works, we have designed specifically and exclusively for cost comparison. In the performance evaluation, in addition to the proposed algorithms (GA), we also include the no replication (NREP) scheme as the baseline, random (RAND) scheme and minimum-cost replicas placements algorithm (MCRP)[38] for comparison. As the name states, in NREP there is just the original objects in the root as a replica of data set.

In order to compare the data sets management cost in different strategies, we define the normalized cost (NC_k) as the ratio of difference among NREP cost and the cost of the feasible solution founded by the algorithm to the cost of the NREP scheme. It is given by the following formula.

Fig. 11.

Comparisons of the total data management cost with different replicas placements strategies.

Fig 11 clearly shows a cost cut of proposed replicas strategy over the other algorithms. And it is obvious that the total cost of replicas becomes constant for a certain more number of replicas. As a result, our proposed algorithm optimizes the cost of replication.

Fig 12 shows the convergence of the GA algorithm with different replicas placements strategies. From the result illustrated in Fig 12, we can see that the algorithm arrives at a stable convergence after 200 loops, which takes about 500 seconds. However, this observation should be viewed with caution in light of the facts that (i) the number of data centers is only eight, which is less than the real environment in practice; (ii) the dependency is simple, which is only linear dependency relation, and may be complex in real application.

Fig. 12.

The convergence of the GA algorithm with different replicas placements strategies.

7.2.3 Simulation 3: the robustness of the combination strategy

In order to testify the robustness of GA algorithm, we design a series of problems with different number of data centers and data sets dependency relations, even to solve real-world problems. The real-world problem is a network that also established in Cloud Computing Research Laboratory. This network has 40 data centers and nearly 200 client computers.

Table 12 depicts each problem, such as data centers numbers, the data sets number, the percentage of optimal solution reached, the optimal management cost, and the corresponding result of tradition replicas strategy.

The GA-based heuristics are run on each data set multiple times since GAs are stochastic and therefore yield different searches and potentially different results, for each random number seed used. Ten different seeds were selected to create 10 genetic runs for each problem. These ten runs tested the dependence of the method on the seed selected, both in terms of solution quality and search effort. When the solution quality showed little sensitivity to the choice of the initial seed, we considered the GAs to be “robust”.