Cloud data replication strategy using multiple-criteria decision analysis methods

Abstract

Data stored on a cloud is becoming more and more important. Thus, data replication across multiple cloud nodes is considered an effective solution to achieve good performance in terms of response time, load balancing and most importantly, high data availability and reliability. To maximize the benefit of data replication, strategic placement of replicas in the system is critical. In this paper, the vision of replicas management is turned to multi-criteria optimization methods, again known as Multiple-Criteria Decision Analysis (MCDA) for decision support system. For this, we propose a data replication strategy in a cloud environment based on two different methods. The first is based on the Analytic Hierarchy Process (AHP), and the second is based on the ELECTRE-I multi-criteria decision support method. The main aim is to propose and demonstrate the use of an AHP and ELECTRE-I models for cloud data replication. The results of simulations of our strategy were satisfactory and improved performances, with the two methods, by comparing it with other strategy proposed in the literature.

Keywords

Cloud replicas placement AHP method ELECTRE-I method

1. Introduction

Today, the field of information and communication technologies has become one of the pillars of modern society. The development of the cloud computing concept has been a major step towards the democratization of this field. Data management becomes one of the crucial elements of the infrastructure [13]. It plays a central and major role in the cloud and, as such, it needs to be given greater attention so that it is always available.

Data replication is a very well known and researched data management technique that has been used for decades in many systems [7]. Benefits of data replication include increased performance by strategic placement of replicas, improved availability by having multiple copies of data files and better fault-tolerance against possible failures of servers.

Multiple-Criteria Decision Analysis (MCDA) is a major area of study for operational research. There are methods and calculations to choose the best solution or the optimal solution among a whole set of solutions.

The formulation of an MCDA problem requires four steps:

•
List the potential actions;
•
List the criteria to be considered;
•
Establish the performances chart;
•
Aggregate performances.

The first three steps are common to all methods. So the step of aggregate performances that makes the difference between methods. According to the mode of aggregation, there are three main families of methods: complete aggregation methods, partial aggregation methods, and local aggregation methods [3, 2].

Complete aggregation methods are based on a mathematical function that produces a unique value from the evaluations of the different criteria thus allowing compensation between the criteria. The result of the function used makes it possible to choose a solution globally. Among these methods, we mention the Weight Sum Method (WSM) and the Weight Product Method (WPM), which are the simplest forms of the function used. We can also mention other methods such as MAUT (Multi Attribute Utility Theory) [15], the UTA method (Utility Additive) [6], as well as the AHP method (Analytic Hierarchy Process) [18].

Partial aggregation methods (also called outranking relation methods) are based on the comparison of pair wise actions. This comparison is carried out for each criterion and makes it possible to determine the relation which links each pair of actions. The relation can be a relationship of preference, indifference or incomparability. Using these relationships, we can determine either the best action, or some of the dominant actions. Among these methods, we quote the family of ELECTRE methods (ELimination and Choice Expressing REality) developed by Roy [3], and PROMETHEE method [8].

A replica placement strategy has inputs and outputs. as input each strategy proposes a set of criteria to calculate and evaluate for each site of the system; then to choose the candidate site to place a replica, strategies used a very simple technique called the weighted sum to calculate the replicas placement cost (output) necessary for each site, then choose the site having the least cost. The principle of the weighted sum is to calculate the sum of, the products of each criterion with its coefficient, to have a unique value that makes it possible to compare the results of each site.

In order to handle the placement of replicas in a cloud environment, we propose a data replication strategy using two different MCDA methods. The goal of our strategy is to choose the best candidate site to place a replica. With the first method, we calculate a cost function based on a multi-criteria optimization method called AHP (Analytic Hierarchy Process). This method allows us to calculate in a formal way the coefficient of each criterion after having introduced the weight of each criteria proposed by the user. The second method used is called ELECTRE-I, which aims to select a subset of solutions from an initial set of actions. This method consists of three phases, named respectively, introduction of weight of criteria and calculation of the concordance indices, calculation of the discordance indices, and extraction of over-ranking relationships.

Our contribution is to put in place a more adapted approach that models the system as a multi-criteria optimization problem, in which we applied two multi-criteria optimization methods called AHP and ELECTRE-I. Our work is focused on the evaluation of MCDA techniques for cloud data replication.

Our data replication strategy considers replacing replicas in case there is not enough space to store the replica.

The remainder of the paper is organized as follows. Section 2 presents the most related works on existing data replication strategies in cloud. Section 3 presents our model and the detailed steps of the proposed data placement approach. Section 4 demonstrates the simulation results and the evaluation we have adopted. Finally, Section 5 addresses our conclusions and future work.
2. Literature review

The main goal of replicas placement strategies is to select the best sites to place replicas to improve performances. Replica placement belongs to the NP-complete class of problems [17, 24].

In the literature, several works have dealt with the problem of managing replicas in clouds, and more precisely the replicas placement. MCDA techniques have not been widely applied to replication strategies in the clouds, and only recently.

2.1 Data replication strategies without multiple-criteria decision techniques

Wei et al. [12] presented a Cost-effective Dynamic Replication Management scheme (CDRM). They propose a model that studies the relationship between replica number and availability. The purpose of this model is to limit the number of replicas while meeting availability requirements. According to CDRM, the data replica placement is based on several parameters such as CPU power, memory capacity, network bandwidth and the saturation of data nodes storage system. They implemented CDRM in Hadoop distributed file system (HDFS). CDRM was compared to the default replication management of HDFS and evaluation results obviously show that CDRM improved performance and load balancing. However, the replicas replacement was not taken into consideration.

Yuan et al. [5] proposed a matrix based k-means clustering strategy for data placement in scientific cloud workflows systems. In their strategy, they attempt to keep the datasets in one data center, with the goal that when jobs were scheduled to this data center, most, if not all, of the data they need are stored locally. Their idea was to study and determine dependency matrix for all the application data, which shows the dependencies between all the datasets including the datasets that may have fixed locations. Then they introduced the BEA algorithm [22] to cluster the matrix and partition it that datasets in every partition are highly dependent upon each other. The simulation results indicate that with this strategy, the data movement between the data centers is significantly reduced compared to a random data placement.

Li et al. [21] presented a new cost-effective dynamic data replication strategy named Cost effective Incremental Replication (CIR). Their strategy has the objective to reduce the storage cost and meet the data reliability requirement at the same time. CIR is a data reliability strategy for Cloud-based applications in which the focus is for cost-effectively managing the data reliability issue in a data-center. The approach proposed in CIR is to calculating the replica creation time point, which indicates the storage duration that the reliability requirement can be met. In order to guarantee the reliability requirement, CIR dynamically increases the number of replicas by predicting when an additional replica is needed. The data storage model used in CIR exploits the relationship between the number of replicas and the storage duration. The simulation results demonstrate that CIR strategy can significantly reduce the number of replicas in a data-center, and consequently, the storage cost of the whole storage system can be considerably reduced. Nonetheless, CIR did not consider the issue of the trade-offs between cost and performance.

Hussein and Mousa [9] proposed a data replication strategy which adaptively selects the data files for replication in order to improve the availability and efficient access of files in data centers. This strategy determines the popular files that are identified by analyzing the access history of the file. The popularity of a file is determined by the rate of access to that file by the clients. Once the access number of a popular file exceeds a predefined threshold, the replication system is triggered. Hence, the adaptive strategy finds the appropriate replication location based on a heuristic search for the best replication factor of each file. Simulation results show that the adaptive strategy improves the availability of the cloud system under study, but it doesn’t take into account the load balancing of the system.

Rajalakshmi et al. [1] presented a dynamic replica selection and placement (DRSP) architecture for managing replicas in cloud environment. The proposed strategy concentrates on designing an algorithm for suitable optimal replica selection and placement to increase availability of data in the cloud. In a first phase, the strategy consists of locating and creating replicas using catalog and index. The index is used for storing replica file into local or remote candidate site. In the second phase, the policy determines whether there is enough space, or not, in the candidate site to store the requested file. Experimental evaluation shows that DRSP stores data efficiently in selected sites and improves the performance of access and bandwidth utilization. Further, this strategy has not dealt with the storage usage issue and consistency of data file.

2.2 Data replication strategies with multiple-criteria decision techniques

In another work [10], the author presented a Replicas Placement strategy based on Analytic Hierarchy Process in cloud data storage (RPAHP). Replicas placement was modeled as a classical Multi-Attribute Decision Making (MADM) problem. The analytic hierarchy process (AHP) is a structured technique for organizing and analyzing complex decisions. RPAHP considered six attributes (criteria), namely, CPU, Memory, Bandwidth, CPU Utilization, Memory Utilization, and Bandwidth Utilization, which characterized the Data Center and affected the DC performance. We noticed that the optimization criteria that have been chosen for the replicas placement concerned only data center components. The author neglected criteria judged much more important for a better choice of candidate sites for replicas placement such as: the response time, load variance, replicas frequently. AHP method was also used in other work of [23]. An algorithm based on fuzzy comprehensive evaluation, based on AHP method, was implemented. A QoS (quality of service) model of cloud storage service was proposed. Then, a QoS preference-aware algorithm was introduced to deal with individual QoS sensitivity (IQS) constraints.

Mansouri [11] proposed an approach called “Adaptive Data Replication Strategy (ADRS) in cloud computing for performance improvement”. She proposed replicas placement strategy based on five parameters: mean service time, failure probability, load variance, latency and storage usage. At the base of these parameters, she calculated the cost function for each site. The smaller the Cost-Function value, the better the individual’s fitness. When a new replica was generated, the ADRS chose one of light-load sites to store the new replica. The simulation results showed that ADRS gave better performances compared to other works such as CIR [20], DRSP [1] and CDRM [11], according to the five parameters cited above.

2.3 Discussion

The main goal of replication strategies differs from one strategy to another. In a typical cloud environment, where frequent access requests are placed on large-scale data, response time and high availability are crucial for users. As in many systems, a number of data replication strategies have been proposed (Hussein and Mousa [9]; Wu and Guan [23]) to improve the service quality through SLA-awareness in cloud systems.

Some of the proposed replication strategies focus on minimizing the consumption of a certain cloud resource (Rajaklashmi et al. [1]), e.g., Bandwidth, while others limit the number of replicas to reduce the storage cost (Li et al. [21]) and improve the load balancing of the system (Wei et al. [12]). In data replication strategies, only a few studies are particularly interested in improving the response time (Mansouri [11]) to improve performances.

According to this bibliographic study, we noticed that each strategy improved performances but in a well specified context. Meanwhile, each of these strategies has some limitations, we quote as an example, the load balancing criterion that was not taken into consideration by [9, 10], or the strategy [1] which has not dealt with the storage usage issue and consistency of data file, and so on.

Among the works cited in this section, we look to the strategy proposed by N. Mansouri called (ADRS) [11] which used a maximum of criteria (5 criteria). Meanwhile, her strategy has been compared with some works cited above (CIR, CDRM, DRSP), and improved performances compared to the Average Response Time, Load Variance, Effective Network Usage, Replication Frequency and Storage Used. She calculated a cost function, for each site, based on service time, load variance, storage usage, failure probability and latency. The cost function that she used was calculated by applying the weighted sum method where the user proposed weights for each criterion. Nevertheless, this method, the weighted sum, had several limitations:

•
The choice of weights is critical. The user sometimes finds it difficult to determine the values of $w_{1},{w}_{2},w_{3},w_{4}\text{ and }w_{5}$ , or even the proportion between these weights.
•
The underlying aggregation logic is totally compensatory. A very low weight on one criterion can be offset by one or more high weights on other criteria.
•
Some efficient (non-dominated) data nodes may never appear as an optimal solution for a weighted sum regardless of the set of weights selected.
•
High sensitivity to small variations in weightings. Very slight variations in weight values can lead to radically different solutions
•
No intuitive correspondence between the values of the weights and the optimal solution obtained by a weighted sum.

In order to overcome these limitations we propose an approach using two MCDA methods, respectively, AHP (CF-AHP) and ELECTRE-I (DRS-ELECTRE-I).

The details of the proposed approach will be described in the following section.
3. The proposed approach

In this section we present our approach based on two methods called Cost Function based AHP method (CF-AHP) and Data Replication Strategy based on ELECTRE-I method (DRS-ELECTRE-I). This section is organized as follows. First, we describe the model of the system used. Then we briefly mention the criteria used in our model. Next, we present the first approach proposed CF-AHP and finally, we present our second approach DRS-ELECTRE-I.

3.1 System model

Before discussing our replication strategy, we must first define the system model of replication management used. The cloud storage cluster we propose in this paper is composed of m independent heterogeneous data nodes $D_{1},\ldots,D_{j},\ldots,D_{m}$ storing a total of $n$ different files $f_{1},\ldots,f_{i},\ldots,f_{n}$ . Figure 1 presents the system model of our replication management.

Most file systems [20] suppose that each access to file $f_{i}$ is a sequential read of the total file. In our system, each file must be placed entirely onto one data node, and thus, we do not consider file partitioning.

Figure 1.

System model of replication management.

3.2 Criteria used

We kept the criteria used in [10], which are as follows:

Mean service time (MST):

$\displaystyle\textit{ST}\left(i,j\right)=d(i,j)\times\frac{{\textit{size}}_{i}% }{{tp}_{j}}$ (1)

where: $\textit{ST}(i,j)$ is the expected service time of file $f_{i}$ on the data node $N_{j}$ (1 $\leqslant$ j $\leqslant$ m), $d(i,j)$ is the decision variable that equals to 1 if the file $f_{i}$ exists on data node $N_{j}$ , otherwise it sets to 0; ${\textit{size}}_{i}$ is the size of file $f_{i}$ and ${tp}_{j}$ is the transfer rate of the data node $N_{j}$ .

$\displaystyle\textit{AR}(i)=\sum\nolimits_{j=1}^{m}{\textit{Acc}(i,j)}$ (2)

where: $\textit{AR}(i)$ is the mean access rate; Acc(i, j) is the access rate of read requests coming from data node $N_{j}$ asking for the file $f_{i}$ . If the file $f_{i}$ is not on the data node $N_{j}$ , we set $\textit{Acc}(i,j)=0$ .

The mean service time of file $f_{i}$ can be defined as

$\displaystyle\overline{\textit{ST}}(i)=\sum\nolimits_{j=1}^{m}{\left(\textit{% ST}(i,j)\times\frac{\textit{Acc}(i,j)}{\textit{AR}(i)}\right)}$ (3)

The mean service time of the system is given by the following:

$\displaystyle\textit{MST}=\frac{1}{n}\sum\nolimits_{i=1}^{n}\overline{\textit{% ST}}(i)$ (4)

Load variance (LV): Data node load variance is the standard deviation of data node load of all data nodes in the cloud storage cluster which can be used to show the degree of load balancing of the system. The lower value of load variance, the better load balancing is achieved. It is calculated as follows:

$\displaystyle\textit{Load}(i,j)=\textit{Acc}(i,j)\times\textit{ST}(i,j)$ (5)

Storage usage (SU): It is the storage space used in each node.

Failure probability (FP): If one node fails, a replica of the failed service will be possibly created on a different node in order to process the requests. Thus, it is better to place popular files in data nodes with low failure probability to minimize their latency.

Latency (L): The mean latency $Latency(i)$ of file $f_{i}$ is given as follows:

$\displaystyle\textit{Latency}(i)=\frac{1}{r_{i}}\times\sum\nolimits_{j=1}^{m}{% d(i,j)\times\frac{{\textit{size}}_{i}}{B_{j}}\times\textit{Acc}(i,j)}$ (6)

Each file $f_{i}$ has $r_{i}$ replicas; $B_{j}$ is the minimum bandwidth of data node $N_{j}$ ; Then, the mean latency L of the system can be computed by:

$\displaystyle L=\frac{1}{n}\sum\nolimits_{i=1}^{n}{\textit{Latency}(i)}$ (7)

3.3 The procedure of cost function based on analytic hierarchy process

In this approach we propose a multi-criteria optimized data replication strategy for cloud storage. We take into account several factors such as mean service time, load variance, storage usage, failure probability and latency to select candidate data nodes for replica placement.

Our system is modeled as a multi-criteria optimization model. The weighted sum method that was used in [10] has presented several limits, for this we have chosen to use the AHP method which gives more flexibility to the users.

This generic method of decision-making aid can be used with each time we have to make a decision on the basis of several criteria [19]. The cost function is used to determine the best sites candidates to place replicas.

The cost function is calculated as follows:

$\displaystyle\text{CostFunction}=c_{1}\times\textit{MST}+c_{2}\times\textit{LV% }+c_{3}\times\textit{SU}+c_{4}\times\textit{FP}+c_{5}\times L$ (8)

where MST, LV, SU, FP and $L$ are the criteria calculated in Section 3.2. $c_{1},\ldots,c_{5}$ are coefficients determined by applying the AHP method, while passing by the following steps.

3.3.1 Determination of evaluation matrix

For the whole of the criteria, we calculate a matrix of analysis per pair to evaluate the importance of each one of them.

Saaty and Vargas in [18] proposed an evaluation on 5 levels according to Table 1.

Table 1
Relative scores

Description	Numerical value
The two elements have an equal importance	1
The element on line is a little more important than that in column	3
The element on line is more important than that in column	5
The element on line is much more important than that in column	7
The element on line is absolutely more important than that in column	9
The element on line is a little less important than that in column	1/3
The element on line is less important than that in column	1/5
The element on line is much less important than that in column	1/7
The element on line is absolutely less important than that in column	1/9
In certain case, if we have difficulties in evaluate, one will be able to	2, 4, 6, 8
refine by adding intermediate values

On the base of this table, we build a square matrix whose elements of the lines and columns are the 5 criteria of the cost function (MST, LV, SU, FP and $L$ ). The values of the matrix are introduced by the user by comparing the criteria two by two and giving numerical values suggested by the table above.

3.3.2 Calculate the coefficient of each criterion

In the preceding step, we built a square matrix which rises from an evaluation 2 to 2 of the criteria. In order to calculate the coefficients of the criteria based on the values of our matrix, we have to calculate the sum by column, then, we divide each value of the column by the sum of those, and finally, the coefficient (which corresponds to the value of the matrix) is given by calculating the average of each line.

The AHP method will enable us to calculate the coefficients $c_{1},\ldots,c_{5}$ in a formal way. However, it will be easy to calculate the cost function and from where we will be able to identify the sites candidates for the replicas placement. Our system chooses the site that has the lowest value of cost function to place replica.

3.4 Data replication strategy using ELECTRE-I

In this approach we propose a multi-criteria optimized data replication strategy based on ELECTRE-I method.

For an ELECTRE application, there are two main parts. First, the construction of one or several outranking relations, which aims at comparing in a comprehensive way each pair of actions. And second, a phase of exploitation and development of the recommendations obtained in the first phase. In ELECTRE methods, criteria have two distinct sets of parameters: the importance coefficients and the veto thresholds.

Choosing sites for replica placement is a crucial problem. In the proposed approach, we will choose the candidate site to place a replica based on the ELECTRE-1 method.

3.4.1 Criterion weight and concordance matrix

The importance of each criterion is reflected by a weight proposed by the user. To normalize the calculations, the sum of weights must be equal to 10.

The problem to solve is to choose the best candidate site to place a replica. Let $S$ be the set of $m$ sites (actions). We have five criteria to optimize, for each criterion is associated an evaluation function $g_{j}$ (as mentioned in Section 3.2) (where $j=$ 1 to 5, number of criteria), for each criterion is associated a weight $w_{j}$ . The concordance index for two actions $a$ and $b$ is denoted by $C(a,b)$ , ranging from 1 to 0, and measures the relevance of the assertion “a over-rank b” as follows:

$\displaystyle C(a,b)=\frac{\sum\nolimits_{\forall j:g_{j}(a)\geqslant g_{j}(b)% }w_{j}}{W}\textit{ avec }W=\sum\nolimits_{j=1}^{5}w_{j}$ (9)

3.4.2 Discordance matrix

The discordance index $D(a,b)$ is define by

$\displaystyle D(a,b)=0\text{ if }\forall j:g_{j}(a)\geqslant g_{j}(b)$ (10) $\displaystyle D(a,b)=\frac{1}{\delta}{\max}_{j}[g_{j}(b)-g_{j}(a)]\text{ Else}$

where $\delta$ is the maximum difference between the same criterions for two given actions (sites).

3.4.3 Over-ranking relationship

The over-ranking relationship for Electre-I is constructed by comparing concordance and discordance indices at thresholds of concordance $\bar{C}$ and discordance $\bar{D}$ . Thus, “a over-rank b”, if:

$\displaystyle aOb\Leftrightarrow C(a,b)\geqslant\bar{C}\text{ and }D(a,b)% \leqslant\bar{D}$ (11)

The concordance and discordance thresholds are defined as the max value of the concordance matrix and the min value of the discordance matrix respectively.

The over-ranking relationship allows us to determine the site which dominates the most of the other sites, and in which we can place a replica.

3.5 Replicas replacement

Our strategy takes into consideration the replica replacement phase in case there is not enough storage space in the candidate sites. The problem that existed for these kinds of strategies before is that at the beginning of the system launch, if a subset of files is frequently requested and these files are unavailable on the replica servers, the system will launch one or multiple replications of these files, and in case there is not enough space, the concerned strategy will be forced to delete one of the files to free up space; while this deleted file could be one of the files that was not requested at first but after a moment the file will be solicited, knowing that it has been deleted. In our replication strategies, the novelty of the replica replacement phase was to mark the initial files as master files, and the replicas generated as a slave files, so even if we do not have enough space, we will not be able to delete a master file. So we can keep the integrity of the files.

In replicas replacement case, one or more files will be deleted based on several parameters such as:

•
Non frequently used files;
•
Replicas size;
•
File availability in other sites;
•
Replicas access history.

Replicas access history allows us to have two important parameters, access number (AN) and the last time the replica was requested (LT). From there, we can define an indication of the probability of requesting the replica again. Another important parameter for replica replacement is the file size (S), it is better to replace files with large size to reduce the number of replica replacement.

We can calculate the potentiality (PT) of each replica with the following formula:

$\displaystyle\textit{PT}=\frac{w_{1}\times\textit{AN}+w_{2}\times\textit{FA}}{% w_{3}\times(\textit{CT}-\textit{LT})+w_{4}S}$ (12)

where FA is the file availability, CT is the current time and the value of $w_{1},w_{2},w_{3},\text{ and }w_{4}$ can be assigned by the users. The replica which has the lowest value of PT will be replaced by the new replica.

Replicas placement and replacement for the two proposed methods can be summarized as illustrated in Algorithms 1 and 2.

Algorithm 1: CF-AHP

1. For each requested file $f_{i}$ (unavailable in local site)

2. {

3. //Replica placement

4. //Calculate CostFunction

5. Determination of evaluation matrix;

6. Calculate the coefficient of each criterion;

7. Calculate the CostFunction based on Eq. (8); for each site;

8. Determine the best site with the minimum CostFunction value;

9. //Replica Replacement

10. If enough space exist for $f_{i}$ replica in the best site

11. Store replica of $f_{i}$ ;

12. Else

13. {

14. Create list L of files in the best site;

15. Sort list L based on Eq. (12) in ascending order;

16. While (not enough space for replica of $f_{i}$ && L is not empty)

17. Delete first file from list L;

18. Store replica of $f_{i}$ ;

19. }

20. }

Algorithm 2: DRS-ELECTRE-I

1. For each requested file $f_{i}$ (unavailable in local site)

2. {

3. //Replica placement

4. Determination of criteria weights given by user

5. Determination of evaluation matrix: calculate criteria for each site;

6. Calculate the concordance matrix;

7. Calculate the discordance matrix;

8. Determination of the Over-ranking relationship;

9. Determine the best site with the maximum of over-ranking relationships;

10. //Replica Replacement

11. If enough space exist for $f_{i}$ replica in the best site

12. Store replica of $f_{i}$ ;

13. Else

14. {

15. Create list L of files in the best site;

16. Sort list L based on Eq. (12) in ascending order;

17. While (not enough space for replica of $f_{i}$ && L is not empty)

18. Delete first file from list L;

19. Store replica of $f_{i}$ ;

20. }

21. }

4. Experimentation

Algorithm 1: CF-AHP
1.	For each requested file $f_{i}$ (unavailable in local site)
2.	{
3.	//Replica placement
4.	//Calculate CostFunction
5.	Determination of evaluation matrix;
6.	Calculate the coefficient of each criterion;
7.	Calculate the CostFunction based on Eq. (8); for each site;
8.	Determine the best site with the minimum CostFunction value;
9.	//Replica Replacement
10.	If enough space exist for $f_{i}$ replica in the best site
11.	Store replica of $f_{i}$ ;
12.	Else
13.	{
14.	Create list L of files in the best site;
15.	Sort list L based on Eq. (12) in ascending order;
16.	While (not enough space for replica of $f_{i}$ && L is not empty)
17.	Delete first file from list L;
18.	Store replica of $f_{i}$ ;
19.	}
20.	}

Algorithm 2: DRS-ELECTRE-I
1.	For each requested file $f_{i}$ (unavailable in local site)
2.	{
3.	//Replica placement
4.	Determination of criteria weights given by user
5.	Determination of evaluation matrix: calculate criteria for each site;
6.	Calculate the concordance matrix;
7.	Calculate the discordance matrix;
8.	Determination of the Over-ranking relationship;
9.	Determine the best site with the maximum of over-ranking relationships;
10.	//Replica Replacement
11.	If enough space exist for $f_{i}$ replica in the best site
12.	Store replica of $f_{i}$ ;
13.	Else
14.	{
15.	Create list L of files in the best site;
16.	Sort list L based on Eq. (12) in ascending order;
17.	While (not enough space for replica of $f_{i}$ && L is not empty)
18.	Delete first file from list L;
19.	Store replica of $f_{i}$ ;
20.	}
21.	}

In our study we use the simulator CloudSim which is the best tool simulation known and used in domain of cloud simulation [16].

To start the simulation, the user uses the method startSimulation in its code. This method calls other methods such as run, runClockTick, runStart and runStop. All these methods dispose of entered cloudlets by a FCFS scheduling policy [14].

In our experimentation, file accesses show Poisson arrival rates and fixed service times. We only consider that all the data are read only, and thus no data consistency strategy is needed.

Figure 2.

Cloud data server architecture.

Figure 3.

Mean response time based on varying number of tasks.

In the work of [11], the author compared her strategy called ADRS with other ARS, DRSP, CIR, CDRM and Build-time. According to experimentation results ADRS gave better results.

In our experiment we opted to compare our strategies CF-AHP and DRS-ELECTRE-I with ADRS which was already validated in the paper [11]. For that we used the same configurations that were installed in [11]. We configure 64 datacenters geographically distributed in cloud with the corresponding topology shown in Fig. 2. The service providers are represented by 1000 virtual machines. Each virtual machine (VM) is configured as 512 MB RAM, 1000 MIPS, 1000 M bandwidth, and single processer. A hundred different data files are placed in the cloud storage environment, with each size in the range of [0.1, 10] GB. 1000 tasks are submitted to the service providers using Poisson distribution and ensure their processing requirements larger than 10 MI, as well as adopt Random function to assign tasks file size and output file size. Each task requires one or two data files randomly. The host allocates query requests to each VM by the VMSchedulerTimeShared policy.

Initially, the number of replicas of each data file is 1 and replicas are placed randomly.

4.1 Performance evaluation metrics

In order to compare our CF-AHP, DRS-ELECTRE-I and ADRS replication strategy, we use several metrics which are: Average response time (ART), Effective network usage (ENU), Load variance (LV), Replication frequency (RF) and Storage usage (SU).

The calculation of each criterion is as follows:

ART: for each data file, we can calculate the response time, which is the interval between the submission time of the task and return time of the result. The average response time of the system is the mean value of the response time for all data request tasks of the users, which can be obtained by the following equation:

If our system is composed of m users ( $j=1,\ldots,m$ ), each user has $m_{j}$ tasks to run ( $k=1,\ldots,m_{j}$ );

$\displaystyle\textit{ART}=\frac{\sum\nolimits_{j=1}^{m}\sum\nolimits_{k=1}^{mj% }{({\textit{UT}}_{jk}(rt)-{\textit{UT}}_{jk}(st))}}{\sum\nolimits_{j=1}^{m}m_{% j}}$ (13)

Where ${\textit{UT}}_{jk}(rt)$ and ${\textit{UT}}_{jk}(st)$ are the return time and the submission time of the result of task k of the user j.

ENU: we have used the formula of [4] where ENU is given as follows:

$\displaystyle\textit{ENU}=\frac{N_{rfa}+N_{fa}}{N_{lfa}}$ (14)

where $N_{rfa}$ is the number of access times that computing element reads a file from a remote site, $N_{fa}$ is the total number of file replication operation, and $N_{lfa}$ is the number of times that computing element reads a file locally. The effective network usage ranges from 0 to 1. A lower value of ENU means that the network bandwidth is used more efficiently.

LV: Data node load variance is the standard deviation of data node load of all data nodes in the cloud storage cluster. Load variance is used to represent the degree of load balancing of the system. The lower value of load variance, the better load balancing is achieved.

RF: it is the number of replications generated per data access. The lower value indicates that strategies are better at putting data in the proper nodes.

SU: it is determined as the ratio of filled space available in total space. The lower value indicates that strategies are better at placement and replacement of replicas in the system.

$\displaystyle\text{SU}=\frac{\text{Filled\_Space\_Available}}{\text{Space}}$ (15)

4.2 Simulation results and analysis

After configuring the cloud environment of our simulator, we proceed to configure the different weights of the criteria for each implemented strategy (i.e., ADRS, CF-AHP and DRS-ELECTRE-I). Once the simulation is complete, we present in the following the results of the different strategies with respect to each evaluation criterion presented in the previous Section 4.1).

4.2.1 Average response time (ART)

Figure 3 shows the average run time of spots based on the number of spots. According to Fig. 3, the difference between ADRS and our two strategies, DRS-ELECTRE-I and CF-AHP, is clear especially by exceeding 700 tasks. CF-AHP and DRS-ELECTRE-I significantly reduced the average execution time of tasks by selecting the best replica location for task execution, taking into account the cost of replicas.

In the ADRS strategy, the author has calculated the cost function based on the weighted sum method, while the cost function of our CF-AHP strategy is based on the AHP method, and again the DRS-ELECTRE-I strategy is based on the multi-criteria method ELECTRE-I, which made the difference on the choice of the candidate sites for the placement of the replicas. Therefore, the placement of the replicas influenced the average execution time of the tasks and even the other criteria.

It is clear that the DRS-ELECTRE-I replication strategy improves response time and keeps response time at a stable level in a short time. The main reason is that in DRS-ELECTRE-I, the total number of local accesses has been increased by placing the replica in the best site and avoiding unnecessary replication. As a result, the total number of replications and remote access has been reduced and, as a result, the response rate has been decreased.

Figure 4.

Effective network usage.

Figure 5.

Load variance based on varying number of files.

4.2.2 Effective network usage (ENU)

Data replication takes time and consumes network bandwidth. However, a non-replication-based strategy is inefficient compared to the simplest replication strategy. Any replication has an interest in reducing network traffic. ENU is calculated based on the ratio of the files transferred to the requested files, so a low value indicates that the strategy used is better to put the files in the right place. The effective use of the network for the three strategies is illustrated in Fig. 4. ENU of the DRS-ELECTRE-I strategy is about 52% lower compared to the ADRS strategy, and 28% than the CF-AHP strategy. The main reason is that the sites will have their files needed at the time of need, hence the total number of replicas will decrease and the total number of local accesses will increase. The DRS-ELECTRE-I strategy is optimized to minimize bandwidth consumption and reduce network traffic.

4.2.3 Load variance (LV)

Regarding another criterion, LV (Load Variance), we took into consideration the load balancing of data centers. The simulation showed that the load variance of the three strategies converges, up to 400 files, but subsequently, the DRS-ELECTRE-I consistently outperforms the other two strategies. Figure 5 shows the simulation results of load variance based on the number of files.

Figure 6.

Replication frequency.

Figure 7.

Storage usage.

4.2.4 Replication frequency (RF)

In the following experiment, we study the replicas frequency, i.e., the number of replicas generated. When the system initiates replication, not only the network bandwidth resource is consumed, but the replica server load also increases due to disk I/O and processor usage. Therefore, the frequency of the replication operation must be limited to avoid significant overhead of the network and the replica server. The replication frequency results are shown in Fig. 6. The replication frequency of ADRS is approximately 0.09, i.e., at most nine replicas are created for 100 data access, but for our two strategies, they have 0.07 and 0.06 for CF-AHP and DRS-ELECTRE-I respectively. The proposed policy can adapt to the changing environment and maintain rational replica placement, which not only satisfies availability, but also reduces unnecessary replication. The difference in the replication rate will be clear by increasing the number of data accesses. The results presented in Fig. 6 are given at the rate of 100 data accesses.

4.2.5 Storage usage (SU)

The storage utilization percentages for the three strategies are shown in Fig. 7. The DRS-ELECTRE-I algorithm creates replicas dynamically in advance. Instead of storing files in many sites, they can be stored in a particular site so that storage usage can be reduced. This indicates that with DRS-ELECTRE-I, we can expect fewer replicas, which leads to better performance than the other two strategies.

As shown in Fig. 7, the DRS-ELECTRE-I strategy reduces storage usage to 29% compared to ADRS, this is obvious, as long as this strategy generates fewer replicas and therefore it takes up less storage space.

In conclusion of the results, we note that the strategy DRS-ELECTRE-I improves the performances of the five studied criteria, and this thanks to the choice of the optimization multi-criteria method which selects the best candidate site to place the replica. Meanwhile, the different simulation results also show the performances presented by the CF-AHP strategy comparing with ADRS.

5. Conclusion

The purpose of data replication works in cloud environment differs from one strategy to another, those focuses on optimizing system performance, such as load balancing and storage space reduction, and others that aim to satisfy users by meeting criteria such as response time and data availability. Mansouri’s work [11] met several criteria satisfying the system and the users, for that we concentrated on this work. In our approach we were able to improve mansouri’s performance by adopting two MCDA methods named AHP and ELECTRE-I. The application of the two multiple-criteria decision analysis methods has as objective to select the best candidate site to place a replica by optimizing a set of criteria. These criteria are: mean service time, failure probability, load variance, latency and storage usage. We used the CloudSim simulator to compare Cf-AHP and DRS-ELECTRE-I with ADRS which gave better performances before. The simulation results showed that DRS-ELECTRE-I outperforms CF-AHP and ADRS compared to metrics: Mean response time, load variance and replicas frequency. Especially, its performance becomes better and better with the incensement of the number of tasks.

However, these strategies present some limitations. They don’t integrate the economic concept and energy economic with the criteria used, because these are very crucial points in cloud environment. For that, we have as perspective to integrate them in future works.

Footnotes

Authors’ Bios

Mohamed Redha Djebbara is a teacher/researcher at the Science and technology Department, Faculty of Science and technology at the University of Mostaganem, Algeria. He was graduated in 2001 from Computer Science Department, Faculty of Sciences, University of Oran1, Algeria. He received his Post graduation Degree in computer science in 2010. He is Phd student at the University of Science and Technology Mohamed Boudiaf USTO-MB Oran. His research interests include Distibuted System, Grids, Cloud computing and multicriteria decision support.

Hafida Belbachir is a full professor at the Computer Science Department, Faculty of Computer Science and Mathematics at the University of Science and Technology Mohamed Boudiaf USTO-MB Oran, Algeria. She obtained, after several scientific stays in LCP-INPG of Grenoble France, her Phd Degree at the University of Oran1 in 1990. She is a team leader within the laboratory signals data systems (LSSD) which is approved in 2003. Her research covers advanced aspects of Databases, Distributed Systems, Web Technology and Data mining. Her works have been published in several international journals and conferences.

References

Rajalakshmi

Vijayakumar

and Srinivasagan

K.G.

, An improved dynamic data replica selection and placement in cloud, in: Proceedings of the 2014 International Conference on Recent Trends in Information Technology, Chennai, INDIA (2014), 426–431.

Scharlig

, Décider sur plusieurs critères, panorama de l’aide à la décision multicritère, Collection Diriger l’entreprise, No. 1, Edition Presses Polytechniques et universitaires Romandes, Lausanne, Suisse, 1985.

Roy

, Vers une méthodologie générale d’aide à la décision, Metra 14(3) (1975), 459–497.

Cameron

D.G.

Carvajal-schiaffino

Millar

A.P.

Nicholson

Stockinger

and Zini

, UK grid simulation with OptorSim, in: Proceedings of UK e-Science All Hands Meeting, Nottingham, UK (2003), 188–191.

Yuan

Yang

Liu

and Chen

J.J.

, A data placement strategy in scientific cloud workflows, Future Generation Computer Systems 26(8) (2010), 1200–1214.

Jacquet-Lagrèze

and Siskos

, Assessing a set of additive utility functions for multicriteria decision making, the UTA method, European Journal of Operations Research 10(2) (1982), 151–164.

Bouharaoua

and Belalem

, A quorum-based intelligent replicas managements in data grids to improve performances, Multiagent and Grid Systems Journal 13(2) (2017), 143–161.

Brans

J.P.

Mareschal

and Vincke

, PROMETHEE: A new family of outranking methods in multicriteria analysis, Proceedings of the 10th IFORS International Conference on Operational Research, Washington, USA (1982), 408–421.

Hussein

and Mousa

M.H.

, A light-weight data replication for cloud data centers environment, International Journal of Engineering and Innovative Technology 1(6) (2012), 169–175.

10.

Radi

, Replica placement strategy based on analytic hierarchy process in heterogeneous cloud data storage, ACIT International Arab Conference on Information Technology, Beni-mellal, Morocco (2016), 1–9.

11.

Mansouri

, Adaptive data replication strategy in cloud computing for performance improvement, Frontiers Computer Science 10(5) (2016), 925–935.

12.

Wei

Veeravalli

Gong

Zeng

and Feng

, CDRM: A cost-effective dynamic replication management scheme for cloud storage cluster, in: Proceedings of the IEEE International Conference on Cluster Computing, Heraklion, Crete, Greece (2010), 188–196.

13.

Buyya

Yeo

C.S.

Venugopal

Broberg

and Brandic

, Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility, Future Generation Computer Systems, Elsevier 25(6) (2009), 599–616.

14.

Buyya

Ranjan

and Calheiros

R.N.

, Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities, in Proceedings of the 7th High Performance Computing and Simulation Conference (HPCS), Leipzig, Germany, IEEE Press: New York, USA (2009), 1–11.

15.

Keeney

and Raiffa

, Decision with multiple objectives: Preferences and value tradeoffs, Edition Wiley, New York, 1976.

16.

Calheiros

R.N.

Ranjan

Beloglazov

Rose

C.A.F.D.

and Buyya

, Cloudsim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms, Software: Practice and Experience (SPE) 41(1) (2011), 23–50.

17.

Neves

T.A.

Drummond

Ochi

L.S.

et al., Solving replica placement and request distribution in content distribution networks, Electronic Notes in Discrete Mathematics, Hammamet, Tunisia 36 (2010), 89–96.

18.

Saaty

T.L.

and Vargas

L.G.

, Prediction, Projection, and Forecasting: Applications of the Analytical Hierarchy Process in Economics, Finance, Politics, Games, and Sports, Kluwer Academic Publishers, Boston, 1991.

19.

Saaty

T.L.

, The Analytic Hierarchy Process, (book) McGraw-Hill, New York (1980), revised editions, Paperback (1996, 2000), Pittsburgh: RWS Publications.

20.

Xie

, SEA: A striping-based energy-aware strategy for data placement in RAID-structured storage systems, IEEE Transactions on Computers 57(6) (2008), 748–761.

21.

W.H.

Yang

and Yuan

, A novel cost-effective dynamic data replication strategy for reliability in Cloud data centres, in: Proceedings of the 9th IEEE International Conference on Dependable, Autonomic and Secure Computing, Sydney, Australia (2011), 496–502.

22.

McCormick

W.T.

Sehweitzer

P.J.

and White

T.W.

, Problem decomposition and data reorganization by a clustering technique, Operations Research 20(5) (1972), 993–1009.

23.

and Guan

, Data set replica placement strategy based on fuzzy evaluation in the cloud, Journal of Intelligent & Fuzzy Systems 31(6) (2016), 2859–2868.

24.

Shijia

Zhou

Haomin

and Ming

, Video replica placement strategy for storage cloud-based CDN, Journal of Theoretical and Applied Information Technology 59(3) (2014), 610–620.