Laila Bouhouch

| Mostapha Zbakh

Claude Tadonki

Dynamic Data Replication and Placement Strategy in Geographically Distributed data centers

Keywords: Big Data, Cloud Computing, Data Placement, Dynamic Data Replication, Cloudsim

With the evolution of geographically distributed data centers in the Cloud Computing landscape along with the amount of data being processed in these data centers, which is growing at an exponential rate, processing massive data applications become an important topic. Since a given task may require many datasets for its execution and the datasets are spread over several different data centers, finding an efficient way to manage the datasets storage across nodes of a Cloud system is a difficult problem.

In fact, the execution time of a task might be influenced by the cost of data transfers, which mainly depends on two criterias. The first one is the initial placement of the input datasets during the build-time phase, while the second is the replication of the datasets during the runtime phase. The replication is explicitly consider when datasets are being migrated over the data centers in order to make them locally available wherever needed. Data placement and data replication are important challenges in Cloud Computing. Nevertheless, many studies focus on data placement or data replication exclusively. In this paper, a combination of a data placement strategy followed by a dynamic data replication management strategy is proposed, with the purpose of reducing the associated cost of all data transfers between the (distant) data centers. Our proposed data placement approach considers the main characteristics of a data center such as storage capacity and read/write speeds to efficiently store the datasets, while our dynamic data replication management approach considers three parameters: the number of replicas in the system, the dependency between datasets and tasks and the storage capacity of data centers. The decision of when and whether to keep or to delete replicas is determined by the fulfillment of those three parameters. Our approach estimates the total execution time of the tasks as well as the monetary cost, considering the data transfers activity. Our experiments are conducted using Cloudsim simulator. The obtained results show that our proposed strategies produce an efficient data management by reducing the overheads of the data transfers, compared to both a data placement without replication (by 76%) and the selected data replication approach from Kouidri et al. (by 52%), and by improving the financial cost.

INTRODUCTION

With the expansion of Internet technologies and virtualization, Cloud Computing has established a new and exciting computing paradigm for common applications in various areas such astronomy [START_REF] Berriman | The Application of Cloud Computing to Astronomy: A Study of Cost and Performance[END_REF] , physics [START_REF] Coutinho | Physics and microeconomics-based metrics for evaluating Cloud Computing elasticity[END_REF] and bioinformatics [START_REF] Navale | Cloud Computing applications for biomedical science: A perspective[END_REF] , to name a few. It provides several services [START_REF] Sadiku | Cloud Computing: Opportunities and Challenges[END_REF] like high performance computing resources, distributed computing, mass storage devices and lower cost of infrastructure (pay-as-you go model), and can scale as desired by considering a geo-distributed data center configuration.

Nowadays, various applications produce terabytes or even petabytes of data [START_REF] Furht | Introduction to Big Data[END_REF] that need to be efficiently analyzed, stored and processed. In addition, some data need to be exchanged and shared between different actors of the data market. Hence, scientists and industrials have adopted Cloud Computing environment as a good solution to deploy large-scale data applications and thereby simplify storage, partitioning, distribution and assignment of massive data over distant heterogeneous nodes of a given cluster [START_REF] Zhu | Cost-Aware Big Data Processing Across Geo-Distributed data centers[END_REF] . Moreover, the principle of geographically distributed data centers brought a great value for these Cloud-based platforms by improving the access times, availability and scalability of the stored data, where the heterogeneity refers to main characteristics of a data center such as hardware type, storage capacity and processing speed.

There are many challenging problems for deploying big data applications in a Cloud environment [START_REF] Chaowei | Big Data and Cloud Computing: innovation opportunities and challenges[END_REF] . Sometimes it is hard to get enough space available to store a large amount of data, and it might quiet expensive to move datasets between data centers when the tasks of of a given workflow need them (i.e. when the source data center is different from the target one where the requesting task is being executed).

In addition, the resources are provided in a cost-effective manner [START_REF] Foster | Cloud computing and grid com-puting 360-degree compared[END_REF] . This trend toward economy-based systems raises new challenges for interactions between Cloud providers and users. As the user might need to adjust its current configuration, Cloud resources are provided in an elastical way and the monetary cost is determined on the pay-as-you-go basis [START_REF] Armbrust | A view of Cloud computing[END_REF] . Like any economic enterprise, Cloud service providers seek maximal profit. For this purpose, an efficient data management is essential as it contributes to obtain better performances.

However, in large-scale applications executed across different and distant data centers, a given task might require several input datasets, but there is guarantee that both the task and the required datasets are in the same data center. If the required datasets are not locally available on the same node than that of the consumer task, then they have to be transferred via the network. Thus, migrating these (large-sized) datasets obviously impacts the global execution time of the job. An inefficient data management can lead a severe penalty on the execution time as well as on the monetary cost. In the literature, many techniques are available to boost the performance of Cloud environment [START_REF] Subia | Performance Analysis of Big Data and Cloud Computing Techniques: A Survey[END_REF][START_REF] Nayak | Nature Inspired Optimizations in Cloud Computing: Applications and Challenges[END_REF][START_REF] Arunarani | Task scheduling techniques in Cloud Computing: A literature survey[END_REF] such as initial data placement [START_REF] Mazumdar | A survey on data storage and placement methodologies for Cloud-Big Data ecosystem[END_REF] and data replication [START_REF] Bahareh | A Systematic Literature Review of the Data Replication Techniques in the Cloud Environments[END_REF] strategies. In fact, data placement strategies aim to reduce the total volume of data transfers. The idea is to store the datasets in the appropriate data centers before starting the workflow execution. Afterwards, data replication strategies, which might be dynamic, also aim to to decrease the overall cost of data transfers through the use of replicas at runtime (after using a requested dataset, it might be kept as a copy to serve further requests in a most efficient way through the election of the best source). These techniques are regularly improved by the researchers at various levels. However, most of studies focus on the placement and the replication separately [START_REF] Kouidri | Dynamic Data Replication Based on Tasks scheduling for Cloud Computing Environment[END_REF] .

In our work, we improve and combine the two techniques of initial placement of the datasets over data centers and efficient management of data replication during the workflow. The main goal is to reduce the time and cost cost of data migrations. Our two-phase strategy starts with a static placement, considered before starting the execution (build-time phase) and is based on our previous work [START_REF] Bouhouch | A Big Data Placement Strategy in Geographically Distributed data centers[END_REF] . It carefully places the datasets over the distributed data centers considering the heterogeneity of their characteristics (read/write speeds, network bandwidth). We start by computing the matrix of the transfer costs, that gives the global transfer time of every dataset from all possible locations to all possible destinations (the destination is where the dataset is requested by a given task for its execution). Then, using that costs matrix, a greedy algorithm is applied to optimally decide about the final location of the datasets. In other words, instead of reducing the number of data movements among data centers, which does not ensure reducing the time consumption, we directly focus on reducing the data transfers time cost through an appropriate formulation. Henceforth, all the required datasets for a given task will be efficiently transferred to the corresponding data center.

The second phase of our strategy is replication, which is performed itertaively at runtime and aims to manage (keep or delete) multiple copies of the datasets. We are aware about the fact that a replication is automatically handled during the build-time phase by the Cloud system itself, but we do not consider this explicitly in our initial placement because we need to exploit the efficiency of our proposed dynamic replication strategy. Our proposed replication strategy takes advantage of the data movement that occur during tasks execution. In other words, when a gievn dataset are transferred from one location to another, a data replication might be considered. In order be able to create a new replica when there aren't enough space, we decide which copy to keep or delete following a specific procedure. Three parameters are considered our choice: (1) the minimum number of replicas that should exist in the entire system to ensure availability, (2) the dependency between datasets and future tasks, and (3) the storage capacity of the data centers to avoid saturation . Our main objective is to further minimize the total task execution time and financial cost through an efficient management of the datasets as previously explained.

We evaluated the performance of our strategies through simulations using Cloudsim tool. We illustrate that our strategy not only reduce the time consumption of data migrations but also decrease the monetary cost.

The rest of the paper is organized as follows: Section 2 presents a summary of the related works on data placement and data replication strategies. In section 3, we present and describe our model. Section 4 explains in details our static data placement algorithm followed by our dynamic data replication algorithm. Section 5 present a case study and discusses the experimental results obtained using an extension of Cloudsim toolkit. Finally, we draw our conclusions and future work in section 6.

RELATED WORK

We present the related literature and give a summary of some existing works on data placement (static) and on data replication (dynamic). Finding an optimal data placement is considered as a critical issue in geographically distributed data center systems, mainly because of the important cost of each transfer. A reasonable data placement strategy definitely reduces the time overhead of data migration. Several disseminated studies propose different techniques related to that concern.

Authors of [START_REF] Yuan | A data placement strategy in scientific Cloud workflows[END_REF] propose a K-means algorithm to solve the data placement problem. They distribute the data over the data centers based on a dependency matrix that they first compute, and they chose to store strongly interdependent datasets into the same data center. In [START_REF] Qiang | A Data-Placement Strategy Based on Genetic Algorithm in Cloud Computing[END_REF] , the authors consider a data placement algorithm based on the genetic algorithm paradigm, where a better solution is produced at each new generation. They get a better approximated-optimal solution for placing and scheduling datasets compared to a Monte Carlo algorithm and the exhaustive search algorithm. The work in [START_REF] Er-Dun | A Data Placement Strategy Based on Genetic Algorithm for Scientific Workflows[END_REF] contains two contributions: (1) a genetic algorithm based on a heuristic approach, (2) a load balancing procedure over the data centers taking into account the constraints related to the workload and the storage capacity. The combination of the two strategies reduces significantly the amount of data transfers. Another contribution is described in [START_REF] Zhao | A Data Placement Strategy for Data-Intensive Scientific Workflows in Cloud[END_REF] , where the datasets are clustered based on the correlation between them. The size of the datasets is considered as the main factor for the correlation that is used for the clustering procedure. In [START_REF] Ebrahimi | BDAP: A Big Data Placement Strategy for Cloud-Based Scientific Workflows[END_REF] , the proposed data placement strategy aims to decrease the total amount of data migrations between virtual machines based on a genetic algorithm. The most interdependent datasets are placed on the same virtual machine. The data transfer rate between virtual machines is also considered.

However, as far as we know, most of the afromentioned works mainly focus on reducing the number of data migrations rather than the time consumption of data transfers, which is the current interest. In fact, while processing a data intensive application in a geographically distributed data centers, multiple datasets are migrated from one data center to another distant location. Considering the heterogeneity of the data centers in terms of storage capacities, processing and read/write speeds and the bandwidth of the connections, the total cost of data transfers will definitely affect the overall efficiency. So, only reducing number of data movements over distributed data centers is not equivalent to decreasing the data migrations time cost. For this reason, in this work, we propose a data placement strategy in order to minimize time to transfer datasets when running large-scale applications in a Cloud Computing environment and consequently improve the global performance.

Beside data placement technique in managing big data applications, there is also the data replication technique which is adopted to create multiple copies of datasets and geographically disperse them. The main goal of replicating data is to improve data availability by saving bandwidth consumption which is a considerable obstacle that impacts data access, reduce the data transfers amounts/costs and minimize execution time when tasks are processed in the Cloud. Given this, data replication management is considered one of the hot spot researches in large-scale distributed systems. The data replication strategies can be categorized into two types: static replication [START_REF] Long | MORM: A Multi-objective Optimized Replication Management strategy for Cloud storage cluster[END_REF][START_REF] Shvachko | The Hadoop distributed file system[END_REF][START_REF] Zeng | Optimal metadata replications and request balancing strategy on Cloud data centers[END_REF][START_REF] Rahman | Replica placement design with static optimality and dynamic maintainability[END_REF] and dynamic replication [START_REF] Tos | A Performance and Profit Oriented Data Replication Strategy for Cloud System[END_REF][START_REF] Lihui | BRPS: A Big Data Placement Strategy for Data Intensive Applications[END_REF][START_REF] Najme | Adaptive data replication strategy in Cloud Computing for performance improvement[END_REF][START_REF] Xie | Towards Cost Reduction in Cloud-Based Workflow Management through Data Replication[END_REF][START_REF] Kouidri | Dynamic Data Replication Based on Tasks scheduling for Cloud Computing Environment[END_REF][START_REF] Amadeo | Optimising Data Access with an Adaptive Geo-Replication Strategy[END_REF] . Static data replication strategies create and manage replicas manually and are incapable to be adjusted with the various changes especially in a large-scale Cloud systems. While the dynamic data replication strategies are able to automatically generate and delete replicas as things keep going. Hence, studies defined new dynamic techniques to deal with this major issue.

Authors in work [START_REF] Tos | A Performance and Profit Oriented Data Replication Strategy for Cloud System[END_REF] suggest a data replication strategy to ensure a good response time of tenant's query while satisfying the Cloud provider in term of economic profitability. The replication process is triggered only if it doesn't effect the expenditures of the provider and if the estimated response time of the query is greater than the response time threshold. In [START_REF] Lihui | BRPS: A Big Data Placement Strategy for Data Intensive Applications[END_REF] , authors propose a two-step big data replicas placement strategy where the first step aims to group tasks using the same replicas. While the second step aims to group datasets that are used together by the same tasks. The main goal of this work is to reduce the data movement among data centers when executing tasks and progress task parallel execution. Authors of [START_REF] Najme | Adaptive data replication strategy in Cloud Computing for performance improvement[END_REF] suggested a replica placement algorithm to minimize the response time of the workflow while reducing the number of replicas. The replica placement strategy established some parameters such as the size of replica, the number of replicas accesses and when the replica was requested lately, in order to rationally decide about which datasets to replicate and which one no to due of the storage limitations. Results of this work show the efficiency of the proposed algorithm regarding the response time, the network usage, the replication frequency and also the storage usage. The data replication strategy proposed in [START_REF] Xie | Towards Cost Reduction in Cloud-Based Workflow Management through Data Replication[END_REF] aims to minimize the cost of data communication and data storage. Their approach is based on three parameters: datasets dependencies, access latency for each dataset and data centers capacities. The replication process is done in the pre-built phase, after the initial data placement is accomplished. In [START_REF] Kouidri | Dynamic Data Replication Based on Tasks scheduling for Cloud Computing Environment[END_REF] , authors combined job scheduling and dynamic replication strategies into one framework to better minimize the total response time and data movement among virtual machines. The most frequently used datasets are replicated and stored in the machine that contains enough storage space and doesn't already store the replicate dataset. This work shows better results when strategies are applied together. The study in [START_REF] Amadeo | Optimising Data Access with an Adaptive Geo-Replication Strategy[END_REF] proposed an adaptive geo-replication strategy inspired by Ant Colony algorithm. Their algorithm dynamically determines the number of replicas, the location of replicas and when replicas are deleted from a site based on predefined thresholds. Read and write operations on data centers were taken into consideration to implement the strategy and results provided an optimal solution in terms of availability/accessibility, scalability and latency.

To the best of our knowledge, the afromentioned contributions on data replication approaches do not take into account the replicated data resulting from data movement during task execution, which we address in our paper. In fact, we proposed a replica management strategy to take advantage of these replicated datasets and that occur as a result of dataset transfers, then reuse them for the execution of other tasks. In this manner, we will have more datasets available on the data centers and less data movement. Considering the number of existing replicas, the dependency between datasets and tasks that are not yet executed, and the storage capacity, during the execution of a task, some datasets will be kept and others will be removed from a specific data center to ensure the execution of the task. In our study, we also address the economic aspects of the replication process in Cloud systems as well as the concept of geographically distributed data centers which are not much studied in many works. Moreover, the objective of our study is to combine both strategies, the quantities and costs of data migration will be progressively reduced due to the availability of datasets across data centers; therefore, the overall task execution time and the total monetary cost of replication will be further improved.

SYSTEM MODEL

In order to reduce the time cost of data transfers among data centers in a Cloud Computing environment, we seek a good datasets management through an optimal placement at the build-time phase and a skillful replication at runtime. We first list the basic elements of our model.

Symbols and notations

Table 1 depicts the essential symbols and notations.

Description of the model

We now define the model as follows:

1. Data centers graph: We consider a system of geographically distributed and interconnected data centers. We model the system with a graph = ( , , , ). = { , 1 ≤ ≤ } is the set of data centers. Each data center is characterised by its storage capacity , its read speed and its write speed . Next, we consider matrix = ( ) 1≤ , ≤ to model the is the write speed of data center = ( ) is the bandwidth of the connection between data centers and Ψ = ( ) is the elementary data transfer time between data centers and = ( )

designates the ℎ task = ( )
is the index of the data center where task is assigned to (i.e. ) = ( )

designates the ℎ dataset = ( )
is the volume of dataset = ( ) = 1 if is required by , and 0 otherwise ( is the datasets to tasks assigments matrix) = ( ) is total cost of all necessary transfers of from data center = ( ) = 1 if there is a copy of stored in data center , and 0 otherwise ( is the replication matrix) = ( ) is the total monetary cost of the data storage associated to task (per unit of volume) = ( ) is the total monetary cost of all data transfers associated to task (per unit of volume)

Objective function

Total workflow data transfers cost

Outputs Φ = ( )
is the index of the data center where dataset is (indicated to be) placed (i.e. ) = ( ( ) ) ( ) is the index of the chosen source data center for required by (i.e. ( )

)
interconnection between the data centers, where , 1 ≤ , ≤ is the bandwidth of the connection between data centers and . We define matrix Ψ = ( ) as follows:

= ⎧ ⎪ ⎨ ⎪ ⎩ 0 if i = j ∞ if and aren't linked 1 otherwise (1)
Considering matrix Ψ is because we are interested in the transfer time, which is proportional to the volume of the dataset and 1 (it is the product of both). Thus, the cost of transfering a dataset of volume from to is given by:

( , , ) = × . ( 2
)
2. Definition of the tasks: We assume a fixed number of tasks to be sumitted, each of which provided with its workload (not considered here) and the required datasets for its execution. As indicated in Table 1 , we denote the group of task as = { 1 , 2 , … , }, where is the number of tasks. An allocation of the tasks to the data center is provided (as input) through vector = { 1 , 2 , … , }, i.e. is executed on data center . The tasks can be executed in parallel, but each one is processed in only one data center (no task migration and no preemption).

Datasets to tasks assignment:

The set of datasets is = { 1 , 2 , … , }, and dataset has volume . A task might require one or several datasets and a single dataset may be consumed by several different tasks. This led us to a × matrix to model the assignment of the datasets and the tasks:

= 1 if is required by 0 otherwise (3)

Constraints:

The only constraint that is considered in this paper is related to the data center storage capacity. The total volume of the datasets stored in a given data center should be lower than its capacity.

Data placement solution:

This the (initial) datasets to data centers assignment that is provided as the result of a given strategy. We use vector Φ ∈ | | where is the index of the data center that should house , ∈ 1, … , . Thus is stored in data center (4)

Our data placement algorithm is executed first to provide a datasets to data centers assignment (i.e. before the execution of the tasks) and the objective is to minimize the cost of data migrations (i.e. moving datasets from one data center to another) while considering the storage capacity constraint.

Data replication:

We consider that a given dataset might be replicated in order to create several source alternatives. We consider a × matrix to indicate the data centers that hold a copy (replica) of a dataset:

= 1 if has a replica in 0 otherwise (5)
Our data replication strategy aims to complete the data placement solution by taking profit of the datasets movements during the runtime. The idea is to create copies on-the-fly of the datasets so as to be able to chose the best source for any given dataset required, by a task, at a given data center. Next section explains more clearly both strategies and illustrates the benefit of combining the two approaches.

Problem formulation

Considering a workflow W and a Cloud system C, the workflow communication cost WCC is the total data transfer cost for executing all the tasks of the workflow W in the Cloud C. WCC can be estimated using formulas 6 and 7.

(

, ) = | | ∑ =1 | | ∑ =1 × ( ) ( ( ) , ) (6)
where

( ) ( ( ) , ) = ⎧ ⎪ ⎨ ⎪ ⎩ ( 1 ( ) + 1 + 1 ( ) ) × if ( ) ≠ 0 otherwise (7)
The transfer cost of task , 1 ≤ ≤ | |, is computed by considering all involved datasets (i.e. datasets , 1 ≤ ≤ | |, such that ≠ 0). Equation 7 sums up this cost for all the tasks. Regarding Equation 7, two cases should be considered:

• If dataset is not locally avalaible, thus it should be migrated from its source data center ( ) to the target data center (where task is assigned to). The transfer cost is calculated considering the read/transfer/write sequence as follows: (1) is read from ( ) for a duration given by ( ) ; (2) is migrated (through the network) at a cost given by ( ) ; (3) finally is written in (to be locally avalaible for ) at a cost given by . The main constraint related to storage is that the aggregated volume of the datasets stored within a given data center should not exceeds its capacity. In contrast, when data replication occurs, the storage capacity constraint is handled by selecting the right dataset(s) to be delete as we will explain in Section 4.2 through our proposed strategy.

• Otherwise, since is stored in the same data center which runs task , no transfer is needed.

The mathematical programming formulation of our problem could be written as follows:

min | | ∑ =1 | | ∑ =1 × ( ) ( ( ) , ) subject to | | ∑ =1 ( ) ≤ , = 1, ⋯ , | | (8)
where is the Kronecker symbol (i.e.

= 1 if = and 0 otherwise). This is what we intend to solve by a heuristic approach.

Financial cost model

Unlike traditional models or federated systems such as a data grid, the Cloud systems is essentially based on the pay-as-you-go model [START_REF] Tos | A Performance and Profit Oriented Data Replication Strategy for Cloud System[END_REF] . To really benefit from this flexibility, a cost-efficient management by the provider is necessary, as well as by the user.

Provider's revenue

A provider's income is essentially the amount received from the Cloud users [START_REF] Badshah | Performance-based service-level agreement in cloud computing to optimise penalties and revenue[END_REF] . The user typically pays a fee that is associated with the delivered services. The exact amount to be paid is determined based on defined service parameters during a billing period. Both the provider and the user agree on the suitable services for a given working session. In our data replication strategy, we assume that the service level agreement is satisfied. The user is not charged for the number of maintained replicas. It is the responsibility of the provider to store the replicas in the Cloud. The user only pays for the used services and does not care about how many replicas the provider create.

Provider's expenses

The Cloud service provider has a certain number of expenses [START_REF] Tos | Achieving query performance in the cloud via a cost-effective data replication strategy[END_REF] . For every task execution, three types of cost are resulting when required datasets are migrated from remote data centers:

• = ( ): is the cost of the network usage related to task for the involved datasets migrations and replications.

• = ( ): is the cost of the storage space for the replicas created when executing .

• = (

): is the penalty paid by the provider to the user when there is a violation of the response time delay. The data replication strategy aims to contribute in reducing this penalty by providing several potential sources for a specific data request so as to allow for a better choice.

Our goal is to propose a replication strategy that carefully balances the monetary cost and performance improvment. With respect to the types of cost previously described, we estimate an economic cost, denoted by FinancialCost, using equation 9:

= + + (9)

PROPOSED APPROACH

In this section, we explain the main stages of our suggested approach that integrates two techniques in order to reduce the communication cost while migrating datasets among data centers. The first technique is a data placement strategy that is executed in the build-time phase and the second technique is a data replication strategy that is executed during the runtime phase.

Data placement strategy

Our proposed data placement algorithm is executed in the build-time before starting the execution of the tasks. It seeks an optimal initial placement for the datasets. The procedure has mainly two steps presented in Algorithms 1 & 2 and explained in next sections 4.1.1 & 4.1.2. In the first step, the total transfer time of the datasets between the data centers is computed based on the volume of the datasets, the read/write speeds of the disks and the network bandwidth. In the second step, a greedy algorithm is applied based on the previously calculated transfer time to assign each dataset to the optimal data center. Our algorithm is a heuristic, thus it should provide a good solution (not necessarily optimal) in an affordable time overhead. Even if we are aware of the internal replication made by the Cloud system, we do not consider it explicitly in our placement algorithm.

As we know, a given dataset may be either stored in the same data center where its consumer(s) task(s) is/are executed, in that case no migration is needed, or stored in a distant data center and thus an explicit transfer is needed.

If dataset is stored in data center and is required by a task assigned to data center ( ≠ ). The time to transfer from its source to the target , 1 ≤ , ≤ and 1 ≤ ≤ , is given by equation 10:

( ) = × ( 1 + 1 + 1 ) (10)
Since dataset could be used by many tasks, its total migration time from , taking into account all the tasks during the whole execution, is given by:

= | | ∑ =1 × ( ) = | | ∑ =1 ( 1 + 1 + 1 ) × (11)
where (reminder): (11), the aggregated transfer time matrix = ( ), where 1 ≤ ≤ and 1 ≤ ≤ , is thereby calculated.

= 1 if ∈ is used by 0 otherwise Using equation

Compute transfer time matrix Algorithm 1 Calculate data transfer time matrix

Input: ( , ) ← ( , ) + ( 1 + 1 + 1 ) × end for // Sort elements of each row ( , ∶) in ascending order 20:

1: = ( 1 , 2 , … , ) : Set of data
[ ( , ∶)] ← ( ( , ∶)) // ( ) = , the ℎ element of ( , ∶) 21: end for Algorithm 1 calculates the data transfer time matrix as mentioned in the previous section. The algorithm complexity is depicted as follows: ( × × ), where I = card(M), the number of data centers, J = card(T), the number of tasks and K = card(D), the number of datasets.

For every data , we run through each data center to estimate the needed time of moving from the data center to every other location where one of its consumer tasks is assigned to (line 9 to 19). in line 15 is measured using:

• Data size

• Read speed of data center , which is initially designed as the potential location of

• Write speed of data center where should be migrated to for the execution of task

• Bandwidth between the two data centers and (task is executed on data center )

Once the matrix is calculated, each of its rows (line 20) is sorted in ascending order and the corresponding permutation is provided by the array . More precisely, ( ) is the index of the data center corresponding to the ℎ migration time cost of in the ascending order. The goal is to get a better data center for each dataset, starting with the one that yields the smallest transfer time, otherwise the second one, and so one. We would also like to point out that the data transfer matrix is computed only once during our simulation and then used each time it is needed. As an example, we consider:

• 3 data centers { 1 , 2 , 3 } with ( 1 , 2 , 3 ) = (80, 40, 120), ( 1 , 2 , 3 ) = (1, 2, 3), ( 1 , 2 , 3 ) = (1.5, 2, 1
) and ( 12 , 13 , 23 ) = (5, 4, 6).

• 3 tasks { 1 , 2 , 3 } with = (1, 3 , 2).
• 4 datasets { 1 , 2 , 3 , 4 } with ( 1 , 2 , 3 , 4 ) = (45, 20, 25, 50).

Matrix F is given by:

= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 0 1 1 1 0 1 1 0 1 0 1 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (12)
The matrix F shows that 1 is used by 2 and 3 (first line), 2 by 1 and 3 (second line), and so on. The corresponding graph of the relationship between the datasets and the tasks is depicted in Figure 1 :

d 4
⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (13)
(1, 1) indicates global expected time to migrate 1 from 1 to 2 and 3 , where the consumer tasks 2 and 3 are respectively assigned. Eventually, we sort matrix row by row as shown in line 20 of Algorithm 1 and get new matrix below:

= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 3 2 1 2 1 3 2 1 3 3 2 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (14)
(1, 1) = 3, means that the smallest transfer time of 1 in comparison to other data centers is obtained with data center 3 and the corresponding cost is (1, 3) = 45 units of time. In contrast, the last column of the same row (thus the same dataset) yields the highest migration time of 177.75 (i.e. (1, 1) and (1, 3) = 1) obtained with data center 1 .

Algorithm for an efficient placement

To obtain an efficient datasets placement, we implement Algorithm 2, which is the refinement of the results from Algorithm 1. For this purpose, a greedy algorithm is applied and iteratively assigns datasets to the appropriate data centers so as to reduce the total transfer time. After calculating the complexity of the Algorithm 2, we have the following result: ( 2 ), where K = card(D), the number of datasets.

We consider a variable c as an index indicating the current column within related to transfer matrix , a variable s to present the number of placed datasets and a binary variable placed that indicates if a dataset is placed or not.

As long as s is less than the overall number of datasets and c doesn't exceed the total number of data centers in the system (Algorithm 2-line 9), the following steps are done:

• We initialize max and k to -1 (line 10-11). is the index of the most costly choice, this will be use for a relocation in case of storage space saturation.

• We individually examine the datasets and for each one:

1. We check if the dataset is already stored (line 13). If so we check the next one. Otherwise, we select the column c (current) of ( ) that returns index (line 14) and is supposed to be a good initial placement for now. Next, we check (line 15) if the transfer time is greater than the current maximum ( ) and if the remaining capacity storage ( ) allows to store the corresponding volume . If the two conditions are satisfied, then we update with the current transfer time and with the index of the current dataset. Otherwise, we keep the previous values of and .

2. The main goal of the bloc from line 12 to line 20 is to go over all unplaced datasets and choose the one with the biggest transfer time that can be stored in the selected data center. Thereby, the transition to the following position ( + 1) is avoided. The latter certainly cost more, considering that we are dealing with an ascending order. The idea is, for a specific data center (column ), we search for the eligible dataset with the highest migration time if placed in data center number without violating the capacity storage constraint. Since the rows of matrix are sorted in an ascending order, gives the lowest transfer time. This is a max/min procedure and it places earlier the dataset with the highest potential transfer cost.

• At the end of the iteration on the current column, either we selected one dataset (i.e. ≠ 1) or we couldn't mainly because of the capacity storage constraint that was always blocking:

1. In the first case (line 21 to 26), will be stored in data center number (considering the sorting, we consider [ , ] instead of ). Then we set = (line 24), where = [ , ] specifies that is already stored (line 23). Next, we refresh the storage capacity of the selected data center (line 25). Finally, we increment s to move to the next dataset.

Algorithm 2 Algorithm for an efficient datasets placement

Input: /* Refinement of the datasets placement following a greedy approach */ 1: : index of the current column in the transfer cost matrix 2: : number of already placed datasets ← -1 [ ] ← 1

24:

[ ] ← // will be stored in data center Problem with data placement ! 35: end if 2. In the second case, no compatible data was found, so we increase c in order to consider the next column.

• After having iterate over all the datasets and all the data centers in the system, we check if ( = ), which means that our data placement problem was successfully resolved and that every dataset was assigned to a data center (line 31,32). Otherwise, an issue was encountered (because of the capacity storage constraint) and some datasets couldn't be placed (line 34).

We apply the steps explained above to our previous illustrative example. First, we create an intermediate ′ matrix that corresponds to the transfer time values of matrix (equation 14) to help us iterating over the unplaced datasets and pick the one with the greatest transfer time.

′ matrix is given by equation 15:

′ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎝
⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (15)
′ (1, 1) = 45 is the best transfer time for 1 and should be stored in 3 ( (1, 1) = 3); 1 ( (1, 3)) is the last location that can store 1 with the biggest transfer time ′ (1, 3) = 177.75. Then, we start by the first column in matrix looking for the dataset that has the biggest time for migration. Based on the first column of ′ matrix, we can see that 1 ( 1 = 45) has the largest transfer time ( ′ (1, 1) = 45) and can be stored in 3 ( (1, 1) = 3 and 3 = 120) without violating the storage capacity constraint. Now, 1 is marked as a placed dataset and 3 the capacity of 3 is updated to 120 -45 = 75. We repeat the same process to place the next dataset, and this time the dataset with the biggest transfer time 34.17 is 3 . We check if 2 ( (2, 1) = 2 and 2 = 40) can store 3 ( 3 = 25). Thus, 3 is saved in 2 and 2 is refreshed to 40 -25 = 15. The next dataset to place is 2 with a transfer time of ′ (2, 1) = 27.33 and that corresponds to 2 ( (1, 1) = 2). But since 2 ( 2 = 15) has not enough space to store 2 ( 2 = 20), then we skip to the next dataset which is 4 . 2 will be placed later when we move to the second column of matrix. 4 that has a volume of 50 should be placed in 3 ( (3, 1) = 3) since 3 = 75. By that, the new 3 is 35 and 4 is also marked as placed dataset. After going through the first column of matrix and since we still have 2 that is not already placed, then we need to iterate within the second column of matrix. Therefore, we check if 1 ( (2, 2) = 1) can store 2 with a transfer time of 34. 1 equals 80 and 2 equals 20, thus 2 is successfully placed in data center 2 and 1 is updated to 60.

The final data placement solution is depicted in Figure 2.

Data replication placement

The proposed dynamic data replication algorithm is executed at the runtime phase and intends to manage existing and replicated datasets while tasks are being processed. Our proposed technique is implemented following two steps as described in section 4.2.1 & 4.2.2 (Algorithm 3 & 4 successively). The first step tries to find the best data center source that owns a copy of the required dataset for the execution of a given task. The second step aims to manage the replication of the datasets during their transfers. It decides about the datasets to delete in case storage space saturation. The suppression process is based on the number of replicas and the dependency between datasets and tasks. It worth noting that many works deal with replication in the buildtime phase by finding a better number of replicas and a better placement before starting the execution of the tasks. Our idea in this work is to create and reuse the replicas during the transfers of the datasets.

Source data center selection

The goal of this step is to find the best data center source to get the data needed in a given data center. The main idea is to choose the data center with the smallest transfer time as done by Algorithm 3.

For each task , we go through all the datasets to check which ones are required for the execution of that task (line 18) as follows considering a specific dataset :

1. If is available locally (i.e. the same data center where is executed -line 19). Though, is either initially placed and in that case we talk about (initial placement result of Algorithm 2) or already stored as a replica in via a migration process and in that case we talk about , = 1. If one of the conditions is true, then is indeed available locally and can be directly consumed by . In that case, we increment the execution time of (line 20).

2. Otherwise (line 21 to line 44), is in different(s) source(s). For its local availability for , should be migrated from a chosen source (if multiple ones) to while considering data center's capacity. Basically, we have two steps:

(a) Find the best distant source from where to read for . To achieve that, we go through all the data centers (line 22) and see which ones are storing (original or a replica) (line 23).

For each found in a specific , we compute its migration time ( ) ( , ) from (source node) to (destination node), then save it in matrix ( ) (line 24). At the end, every will have a row in matrix ( ) filled with estimated time to transfer it from every distant data center to . If is not found in a distant source then ( ) ( , ) is equal to ∞ (line 26). As last, we sort the row that corresponds to in ( ) matrix in ascending order and we get matrix ( ) where ( ) ( , ) = is the ℎ element of ( ) (line 30). Then we select the first element in ( ) ( , 0) which gives the best data center source that providing with the smallest transfer time ( ) ( , ) (line 31). The goal of this phase is to select the best data center from where we can read our dataset, transfer it and write it where the consumer task is executed. All the migrated datasets while executing tasks are considered as a replicas and may be deleted if needed in case of space issue. Now, the best source is successfully chosen.

(b) Verify

's capacity where should be migrated to. Lines from 32 to 40 in Algorithm 3 and the function in Algorithm 4 depict the way we deal with data centers capacities and how we manage the replicated datasets.

Select datasets to delete

As mentioned before while executing tasks, several datasets are moving from one location to another so as to be locally available on the node where the consumer task is assigned to. As we create replicas on the fly, this might lead to have many replicas. Due to storage limitation, keeping all the replicas may prevent storing new incoming useful data or creating new replicas. Thus, we need to delete some copies whenever necessary. We propose a dynamic data replication management strategy, which is an extension of our previous work 2 about data placement. Our strategy (explained in section 4.2.2) aims to decide about which datasets to remove or keep.

When don't have enough space available for (line 32 in Algorithm 3), we execute "SelectDatasetToDelete" function (Algorithm 4), to chose which datasets to delete so as to free enough space. In fact, the function takes two parameters: the index of the concerned data center and the arrival time of the task for which we want to gather the required datasets. The steps of this function are:

1. We iteratively examine the tasks (Algorithm 4, line 2 to line 6) looking for the ones having their arrival time ( ) greater than (line 3), which means they are not yet executed at that time, and add them to vector . Then, we compute the dependency between these tasks and the datasets as explained below. : Index of optimal placement of datasets : Matrix to specify if is a replica in so = 1 Output: = ( ( ) ): Index of chosen data center as source to migrate when executing // Migrate data //Sort row ' ' of migration time matrix corresponding to , in ascending order 30:

[ ( ) ( , ∶)] ← ( ( ) ( , ∶)) // ( ) ( , ) = , the ℎ element of ( ) ( , ∶) 31:
( ) ← ( ) ( , 0) // Select placement with the smallest transfer cost as a source 32: while (( -) < 0) do // 's capacity is not enough to store 33:

← SELECTDATASETTODELETE( , ) // Decide which dataset to remove from to free up space and store the migrated , is the arrival time of ) and select which one to delete. The deletion process is based on: (a) Dependency between tasks and datasets (Algorithm 4, line 13 to line 17): this factor aims to specify how many unexecuted tasks require each replicated dataset. So, for each in , we verify which task requires the replica (when is equal to 1 -line 14). Then, we increment the value of , which corresponds to how many tasks are using .

(b) Number of existing replicas of the dataset (Algorithm 4, line 18 to line 22): this factor aims to specify the number of existing replicas for each dataset. So, for each data center (line 18) we verify if it stores as a replica copy (line 19). Whenever a replica is found, the value of is increased by one. ( corresponds to existing number of replicas of ) Since a dataset might be replicated many times, only those having more that replicas (here equals 2) are eligible for deletion. Another step is added (Algorithm 4, line 24 to line 26) to present what we have previously explained by adding each resulting dataset to the list.

3. Once we establish our factors, now we can apply our strategy in Algorithm 4 (line 30 to line 39) to store the migrated dataset locally. The approach we proposed in our work considers a lexicographic sorting to take the decision. The goal of this sorting algorithm is to pick that has the lowest (the least used from the tasks not executed yet). In case we have many datasets with the same , we consider the one having the greatest (the most duplicated dataset across the other data centers).

4. As result to the lexicographic sorting, a new list is created, then we choose the first element on it, which is denoted by in Algorithm 4, line 40.

shows the index of the best dataset to remove. Finally, the result is returned to the main Algorithm 3 in line 33.

An exception is thrown if no is found (Algorithm 3, line 35), in that case the system has faced an issue and therefore stops. Otherwise (line 37 & 38), is deleted from and its capacity is henceforth incremented. In some cases, removing does not free enough space for dataset that we want to migrate. To fix this problem we keep processing the function until we get the a sufficient amount of available space to transfer dataset (loop in Algorithm 3, line 32). Once out of the loop, data center can finally receive . The migration process is started and the task can eventually consume ; the execution time of the task is updated (line 41); we indicate that is stored in (line 41) and update the capacity of (line 43).

N.B. : The whole process as described above is repeated for each required dataset for task , and the execution time is updated accordingly (line 20 or 31) to give the workflow communication cost suitable for . Moreover, the estimated complexity of Algorithms 3 & 4 is depicted in Table 2, where I = card(M), the number of data centers, J = card(T), the number of tasks and I = card(D), the number of datasets.

TABLE 2 Algorithms Complexity

Algorithm

Asymptotic complexity Algorithm 3

( 4 × × + 3 × 2 × + 3 × 2 × + 2 × 2 × + × × ) Algorithm 4 ( 2 + × + × )
To evaluate our algorithm, we sum the of every task to get the global communication cost (Algorithm 3, line 47) that will be used in the experiments described in section 5.

Algorithm 4 Data replication placement -Datasets to delete from the destination node

EXPERIMENTS AND DISCUSSION

Simulation set-up

In order to inspect the behavior of our algorithms and evaluate their impacts, we compare the following strategies:

1. Build-time strategy [START_REF] Bouhouch | A Big Data Placement Strategy in Geographically Distributed data centers[END_REF] : the datasets are (efficiently) stored before runtime and immediately deleted once consumed (this was the focus of our previous work).

2. Kouidri's strategy [START_REF] Kouidri | Dynamic Data Replication Based on Tasks scheduling for Cloud Computing Environment[END_REF] : he suggests to keep the most used replicas, storing them where there is enough space.

3. Combination of data placement and replication strategies: describes our two-steps approach.

For our experiments, we consider 1000 tasks, assuming that each task is assigned to one data center (no task migration). The number of data centers is 5, 10, 15 and 25, with a uniform distribution within the range [1PB, 25PB] for the storage capacities. In addition, for each task, we randomly assign atb most five different datasets. We limit the number of datasets to 5, 10, 25, 50, 75, 100 and 200. The sizes of the datasets are uniformly distributed within the range [1TB, 100TB]. Overall description is shown in Table 3.

We generate different scenarios of workloads and for each, we consider 100 executions and take the mean value as the final result. We use an extended version 1 of Cloudsim 34 framework, which is a well-known simulator for single and multi-Cloud scenarios. However, it lacks handling and evaluating data migration issues, as well as providing the execution time of the tasks. For this reason, our extension (1) proposes a module to simulate data migration; (2) implements and tests its own data migration strategy; (3) describes data movements across geo-distributed data centers; and (4) estimates the overall time to transfer datasets. We would like to mention that the proposed approaches (including the greedy algorithm) can run on a real Cloud by construction, but this will require extra efforts and the results might be different from that of the simulations. Running on a real cloud, especially with applications managing a huge volume of data, might be costly and source of several technical issues that are not relevant for our consideration in this work. However, we consider this transition in our perspectives.

Simulation results

In our experiments, we evaluate our proposed two-steps strategy and compare the performances with the build-time phase (without replication) and Kouidri's approach. We mainly consider the workflow communication cost (WCC) as described in section 3.3.

Using our extended simulation tool 1 , we simulate each workflow 100 times and consider the average value of the WCC.

In the first experiment, we set the number of geographically distributed data centers to 5, 10, 15, 20 and 25, and for each case we vary the number of datasets from 5 to 200 while estimating WCC as shown in Figure 3. We can notice that in all cases, WCC continuously increases with the growth of the number of datasets. Despite this, our results show that our combined strategy outperforms the build-time approach (data placement without replication) and the kouidri's work (i.e. lower global transfer time). For example, in the case of 20 data centers, owe get a reduction of 75.31% and 48.02% respectively. Moreover, for the same case, our strategy yields a variance of 3.67 hours for the timings with 5 to 200 datasets, while the no-replication and Kouidri give 13.92 hours and 6.8 hours respectively. Thereby, we can say that our proposed algorithm is always better regarding the reduction of communication cost and running time fluctuation. In the second experiment, as shown in Figure 4, we set the number of datasets to 5, 10, 25, 50, 75, 100 and 200 and vary the number of geographically distributed data centers within the range [5, 25]. We observe that by increasing the number of data centers, the WCC for the no-replication appraoch increases. In contrast, WCC seems to decrease with our approach as well as with Kouidri.

In the case with 50 datasets, our approach gives 1.05 hours on average, next to 3.23 and 1.7 hours on average for the noreplication and Koudiri's algorithm respectively. Thus, our proposed approach reduces effectively the cost of data movement by 67.51% and 37.82%, respectively. The results show an increasing improvment with more and more data centers. Figure 5 shows the total monetary cost of each strategy over the simulated billing period. All strategies are evaluated from the case of 15 data centers and varying datasets within the range [5, 200]. About the storage cost, the value looks huge with the no-replication approach. With the other two strategies, a high number replicated datasets is produced. However, our proposed startegy reduces the storage cost by 45% compared to the Kouidri's strategy. In terms of network cost, the build-time strategy generates a very high cost. Our proposed approach does have a little more network cost compared to Kouidri's approach, but this can be considered as a compromise to save on the storage cost. In addition, with no-replication appraoch, the high number of SLA violations results in a high penalty. Whereas apprshow a low number of SLA violations. Based on total costs, data placement and replication strategy reduce the total financial costs by 81.33% and 36.5% compared to the build-time and Kouidri's strategy respectively. This cost reduction shows the efficiency of our work in improving the performance of the Cloud system.

CONCLUSION AND FUTURE WORK

This paper proposes a combination of data placement and data replication to address the problem of data movements across geographically distributed data centers in the Cloud Computing environment. Our aim is to reduce the total transfer cost of moving the datasets between data centers when executing a given workflow. Our data placement approach is a static algorithm that begins with creating a matrix of data migration costs followed by a greedy algorithm to get the final placement of the datasets over the data centers. Our data replication approach is a dynamic procedure that is considered during the runtime phase. While tasks are running, our algorithm searches for the best sources from where to get required datasets. A conjunction of both strategies lead to noticeable improvment compare to a naive management and a selected contribution from the litterature. Indeed, using the extension of Cloudsim framework, we compared our work with other studies in the literature and see that we perform better regarding the minimization of time consumption for moving datasets as well as in reducing the monetary cost by re-using the replicas. As a future work, we intend to simulate our exprimental study considering Peagsus generator for more consistency in the measurements and to implement our solution in a real platform for realistic results. Another possible future direction to reduce the overall execution time is to propose (1) a migration strategy that considers a routing procedure for data migration and (2) a dynamic tasks allocation in conjunction with our data management strategies.

  centers

2 := ( 1 , 2 , 7 :

 2127 … , ) : Set of tasks 3: = ( 1 , 2 , … , ) : Set of datasets 4: = ( 1 , 2 , … , ) : Capacities of the data centers 5: = ( 1 , 2 , … , ) : Volumes of the datasets 6: = ( ) : Matrix of relationship between datasets and tasks Output: = ( ) : Matrix of datasets transfer time from a fixed source to all target data centers 8: = ( ) : Matrix sorted row by row (the aim to facilitate the selection of the best values at the row level) // Computation of matrix 9: for ∈ do

9 :

 9 while ( < && ≤ ) do10:

FIGURE 2 A

 2 FIGURE 2 A sample data placement solution

Algorithm 3 1 : : Number of data centers 2 := ( 1 , 2 ,= ( 1 , 2 ,= ( 1 , 2 ,

 312121212 Data replication placement -Multiple sources Input: … , ): Set of data centers 3: … , ): Capacities of the data centers 4: : Number of tasks 5: = ( 1 , 2 , … , ): Set of tasks 6: = ( 1 , … , ): Arrival time of tasks for the execution … , ): Set of datasets 9: = ( 1 , 2 , … , ): Volumes of the datasets 10: : Relationship between datasets and tasks ( = 1 if needs ) 11: = ( 1 , … , ): Array of tasks assignment 12: Workflow communication cost, where is the execution time of 13:

FIGURE 3 FIGURE 4

 34 FIGURE 3 Communication cost with different number of datasets and a fixed number of data centers

FIGURE 5

 5 FIGURE 5 Total monetary cost

TABLE 1

 1 Parameters and variables of our model

	Inputs
	= ( )	designates the ℎ data center
	= ( )	is the storage capacity of data center
	= ( )	is the read speed of data center
	= ( )

TABLE 3

 3 Default setting for our experiment

	Components	Values
	# of datasets	[5, 10, 25, 50, 75, 100]
	Dataset size	[1TB -100TB]
	# of data centers	[5, 10, 15, 20, 25]
	data center capacity [1PB -25PB]
	Storage cost	$0.1 per GB
	Transfer cost	$0.05 per GB
	Penalty cost	$0.01 per violation