Amina Chikhaoui
email: achikhaoui@usthb.dz

Laurent Lemarchand
email: laurent.lemarchand@univ-brest.fr

Jalil Boukhobza
email: boukhobza@univ-brest.fr

Kamel Boukhalfa
email: k.boukhalfa@usthb.dz

Multi-objective Optimization of Data Placement in a Storage-as-a-Service Federated Cloud

Keywords: CCS Concepts:, Federated cloud → Hybrid storage system;, Data placement → Cost optimization Data placement, optimization, cloud, cloud federation, NSGAII ACM Reference

Cloud federation enables service providers to collaborate to provide better services to customers. For cloud storage services, I/O performance and network latency are important to ensure end-to-end QoS. Therefore, effectively placing customer objects for a cloud that is a member of a federation is a real challenge. In order to optimize data placement, storage, migration and latency costs need to be considered. These costs are contradictory in some cases. In this paper, we modeled object placement as a multi-objective optimization problem. The proposed model takes into account parameters related to the local infrastructure, the federated environment, customer workloads and their SLAs. For resolving this problem, we propose CDP-NSGAII 𝐼 𝑅 , a Constraint Data Placement matheuristic based on NSGAII with injection and repair functions. The objective of the injection function is to enhance the solutions' quality. It consists to calculate some solutions using an exact method then inject them into the initial population of NSGAII. The repair function was designed to ensure that the solutions obey the problem constraints in term of storage and so prevents from exploring large sets of infeasible solutions.

It allows to reduce the execution time of NSGAII. Our experimental results show that, the injection function improves the HV of NSGAII and the exact method by up to 94% and 60% respectively while the repair function reduces the execution time by an average of 68%.

INTRODUCTION

Cloud computing [START_REF] Taherkordi | Future cloud systems design: challenges and research directions[END_REF] is the most popular distributed computing paradigm [START_REF] Hota | Survey of different load balancing approach-based algorithms in cloud computing: a comprehensive review[END_REF]. It provides IT resources to users under the form of ready-to-use services. Storage-as-a-Service (STaaS) is one of the most important services [START_REF] Hou | Understanding I/O performance behaviors of cloud storage from a client's perspective[END_REF][START_REF] Mansouri | Data storage management in cloud environments: Taxonomy, survey, and future directions[END_REF] offered by Cloud Service Providers (CSPs) to customers to manage the storage of their data. For STaaS, the storage I/O performance is a primary QoS indicator. In fact, I/Os take about 90% of a transaction execution time [START_REF] Sharaf | Optimizing i/o-intensive transactions in highly interactive applications[END_REF].

Cloud federation [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF][START_REF] Moreno-Vozmediano | BEACON: a cloud network federation framework[END_REF] may constitute a key solution for such an issue. It consists in making several CSPs cooperate by sharing resources. Thus, CSPs can insource and outsource their customers' data and services to offer them a better QoS and at the same time to increase their own revenue (or reduce costs, for instance, by deploying less hardware resources).

Cloud federation may give the opportunity to small and medium size CSPs to become very competitive [START_REF] Celesti | Toward cloud federation: concepts and challenges[END_REF].

Providing a storage service with the required I/O performance and network latency at a minimum cost is the main objective of CSPs. To handle the I/O bottleneck, cloud infrastructures host different storage classes. These are mechanical Hard Disk Drive (HDD) and Solid State Disks (Flash-based SSD and 3D XPoint memories, such as Intel Optane memory) [START_REF] Boukhobza | Flash Memory Integration: Performance and Energy Issues[END_REF][START_REF] Li | On the trade-offs among performance, energy, and endurance in a versatile hybrid drive[END_REF]. On the other hand, to manage network latency, CSPs try to dynamically bring data close to their users. This helps to reduce the latency experienced by the users and lower the overall traffic among data-centers [START_REF] Yu | Location-aware associated data placement for geo-distributed data-intensive applications[END_REF].

In the context of a Cloud federation, a CSP member tries to leverage both local and the other CSPs storage services to place customers data in order to reduce costs and at the same time meet the required QoS. This is a complex problem because of the heterogeneity of storage and network resources on one hand, and because of the variable federation environment and customers workloads and their respective SLAs on the other hand.

The global data placement cost is roughly composed of the storage, the migration and the network latency costs. These are interdependent and in some cases contradictory costs. For instance, placing data locally may not be expensive in terms of storage and migration costs but may generate a high latency for customers located in far regions. So, trade-offs are inevitable for this type of data placement problem.

The problem of data placement has been widely investigated in the Cloud environment. The proposed techniques have considered many issues related to the hybrid storage system of a centralized cloud as in [START_REF] Boukhelef | Optimizing the cost of DBaaS object placement in hybrid storage systems[END_REF][START_REF] Kakoulli | OctopusFS: A distributed file system with tiered storage management[END_REF][START_REF] Lee | Effective flash-based SSD caching for high performance home cloud server[END_REF][START_REF] Pirahandeh | EGE: A New Energy-Aware GPU Based Erasure Coding Scheduler for Cloud Storage Systems[END_REF][START_REF] Roukh | Eco-physic: Eco-physical design initiative for very large databases[END_REF][START_REF] Wu | GA Based Placement Optimization for Hybrid Distributed Storage[END_REF][START_REF] Shu Yin | DuoFS: A Hybrid Storage System Balancing Energy-Efficiency, Reliability, and Performance[END_REF] and distributed clouds like [START_REF] Guo | Multi-objective optimization for data placement strategy in cloud computing[END_REF][START_REF] Li | Dynamic multi-objective optimized replica placement and migration strategies for SaaS applications in edge cloud[END_REF][START_REF] Liu | PSO based multiobjective reliable optimization model for cloud storage[END_REF][START_REF] Mansouri | Cost optimization for dynamic replication and migration of data in cloud data centers[END_REF][START_REF] Viotti | Hybris: Robust hybrid cloud storage[END_REF][START_REF] Wen | Cost effective, reliable and secure workflow deployment over federated clouds[END_REF][START_REF] Xiao | Cost-aware big data processing across geo-distributed datacenters[END_REF][START_REF] Zhang | Moving big data to the cloud: An online cost-minimizing approach[END_REF]. State-of-the-art studies have considered different objectives under different constraints. Mono and multi-optimization techniques have been proposed to reach the desired objective(s).

Existing work on data placement in centralized cloud cannot be applied in distributed environment because the network factor was not considered. On the other hand, we noticed that the storage cost in existing work is mainly based on volume in terms of GB and I/O performance was not always considered. Furthermore, the storage-related SLA metrics were seldom considered especially when it comes to a distributed cloud.

In this paper, we address the data placement in Cloud federation by modeling it as a multi-objective constrained optimization problem. The storage, migration and latency costs constitute the different objective functions which are subject to different constraints. The heterogeneity of the local and the federated storage classes and services, the customers workloads and the requested QoS have been taken into account.

The data placement problem in this work follows a MAPE-K (Monitor, Analyse, Plan, Execute, and Knowledge) autonomic feedback loop model [START_REF] Jeffrey | The vision of autonomic computing[END_REF]. We focus especially on the Analyse and Plan steps of this model by formulating and resolving the placement problem.

In multi-objective optimization (MOO), it is rarely the case that it exists a single solution that simultaneously optimizes all the objective functions [START_REF] Coello | Multi-objective Optimization[END_REF]. In fact, there is a set of solutions, called non-dominated solutions or Pareto set. These solutions define the trade-offs between the different objectives. The notion of non-dominance is related to the fact that no solution is better than the others for all objective functions. (see Section 4.1).

Our goal is to efficiently obtain a set of non-dominated solutions that simultaneously minimize the storage, the network latency and the migration costs. The selection of a final placement solution from the Pareto set is out of the scope of this paper. It is a subjective task and might be based on other factors and parameters not considered in the optimization process [START_REF] Mukhopadhyay | A survey of multiobjective evolutionary algorithms for data mining: Part I[END_REF].

Due to its popularity and efficiency, we used NSGAII [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] meta-heuristic to solve this multi-objective problem. However, being an evolutionary meta-heuristic, NSGAII suffers from solutions unfeasability caused by the presence of constraints, especially when the problem size increases. Furthermore, NSGAII lacks good initial population [START_REF] Saber | Genepi: A multi-objective machine reassignment algorithm for data centres[END_REF] due to the random initialization. To deal with such problems, we propose an upgrade of NSGAII into a matheuristic [START_REF] Voss | MATHEURISTICS: Hybridizing Metaheuristics and Mathematical Programming[END_REF] by combining it with an exact method. We called this matheuristic CDP-NSGAII 𝐼𝑅 for Constraint Data Placement matheuristic based on Injection and repair functions.

CDP-NSGAII 𝐼𝑅 works as follows. First, it generates a small number of non-dominated solutions by using an exact method. This exact method transforms the MOO problem into a single objective optimisation problem (SOO) by aggregating and weighting the objective functions into one linear function. We used CPLEX [START_REF]CPLEX Optimizer[END_REF] to solve the SOO problem.

Then, the obtained solutions are injected into the initial population of NSGAII in order to populate the initial generation with some good intividuals. Furthermore, we repair all the individuals in each iteration so as to transform unfeasible solutions into feasible ones. The injection function helps NSGAII to improve its solutions quality as NSGAII suffers from a bad initial population which is randomly generated while the repair function helps NSGAII to perform swiftly because with reparation we do not need to check the constraints for the individuals no more as they are already repaired.

In short, the main contributions of this paper are twofold.

' Formulating the data placement problem as a multi-objective integer linear program. The proposed model takes into account the local and the external storage systems characteristics, the customers SLAs and their workloads. ' Upgrading NSGAII to a matheurstic (CDP-NSGAII 𝐼𝑅 ) by merging it with an exact method. Different tools and methods have been used to design and implement the placement problem. CDP-NSGAII 𝐼𝑅 consists in the following steps: -A pre-processing step: Calculation of a set of solutions using CPLEX solver.

-An evolutionary step: First, the set of solutions previously obtained is injected to the initial population of NSGAII.

Then, the evolutionary process of NSGAII is executed with a reparing function for the individuals in each iteration.

The evaluation results show that CDP-NSGAII 𝐼𝑅 reaches quickly the optimal Pareto front for small problem instances with only the repair function. For example, it took 0.3 second for a problem composed of 15 objects and 4 locations while an exact method took about 48 minutes. For large instances, the injection function improves the Pareto front quality of both NSGAII meta-heuristic and the exact method while the repair function enhances the execution time of NSGAII. In fact, the injection function improves the HV of NSGAII and the exact method by up to 94% and 60% respectively and the repair function reduces the execution time of NSGAII by 68%.

The rest of this paper is organized as follows. first, some preliminaries on cloud federation and MOO are given in Section 2. Then, we define the system model and formulate the problem of data placement in Section 3. Section 4 describes the contribution. Experimental results are described in Section 5. Related work are summarized in Section 6 and at last, conclusions and perspectives are given in Section 7.

BACKGROUND

This section gives some preliminary background about the concepts used in this paper. First the cloud federation paradigm is discussed, then, some background knowledge related to the multi-objective optimization field is given.

Manuscript submitted to ACM

Cloud federation

Cloud federation refers to a set of geographically distributed CSPs that interact with each other by sharing their resources in a cooperative manner via centralized and decentralized marketplaces [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF][START_REF] Rebai | Improving profit through cloud federation[END_REF][START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF][START_REF] Nadjaran Toosi | Financial option market model for federated cloud environments[END_REF]. This collaboration helps the CSPs to increase their profit while providing a continuous provisioning of high-quality services by exploiting temporal and spatial availability of resources and diversity of operational costs [START_REF] Li | Profit-maximizing virtual machine trading in a federation of selfish clouds[END_REF]. Cloud federation appeared to overcome some limitations [START_REF] Marcio Rm Assis | Cloud Federations: Requirements, Properties. Developing Interoperable and Federated Cloud Architecture[END_REF][START_REF] Gu | DR-Cloud: Multi-cloud based disaster recovery service[END_REF][START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF] such as resource contention, service interruption and Quality of Service (QoS) degradation.

These limitations appeared with the massive deployment of Cloud infrastructures and the technology maturity of cloud computing [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF] and the emergence of many related new paradigms such as mobile cloud computing, IoT, and big data applications. To work properly and to maintain the integrity of the organization, the federated CSPs are governed by a Federation Level Agreement (FLA) that specifies interconnection rules and describes each participant's responsibilities and permissible behaviors, along with the financial, administrative, or other penalties for violating its terms [START_REF] Kogias | Cloud federation and the evolution of cloud computing[END_REF].

In this section, we first discuss the motivations behind the adoption of federated clouds. Then, a classification of the different federation forms is presented to help positioning our work.

Motivations for the cloud federation.

Cooperation between CSPs creates benefits. We cite, among others, the following reasons that motivate the utilization of a cloud federation [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF][START_REF] Rebai | Improving profit through cloud federation[END_REF]: Elasticity and availability: Elasticity is one of the main cloud computing properties. It allows to dynamically adapt resource provisioning by increasing or decreasing their amount according to customers workloads [START_REF] Zhang | Cloud computing: state-of-the-art and research challenges[END_REF]. Cloud federation enables providers to efficiently adjust their hosting capacity through cooperation with others instead of provisioning (new) extra capacities which increases energy waste and costs. Furthermore, the geographic distribution of federated cloud infrastructures makes it possible to migrate services from areas that may be affected by outages. It allows also for data to be geographically replicated which maintains the availability of customer services. Cost and performance efficiency: Cloud federation allows CSPs to expand their geographic coverage without the need to build new data-centers [START_REF] Kumar | Toward maximization of profit and quality of cloud federation: solution to cloud federation formation problem[END_REF]. This helps to save costs and at the same time improves the offered QoS. Also, the latency can be minimized by satisfying requests from a closer provider and the response time can be reduced by executing the request on a more powerful host from other providers. Furthermore, with cloud federation the load can be balanced between the involved clouds according to some metrics such as energy consumption. Economic Barriers: cloud infrastructures were not designed to inter-operate, therefore there is a lack of standardization and compatibility between the underlying technologies. This generates the "vendor lock-in" phenomenon where customers stay confined to certain CSPs. This vendor lock-in may lead to economic and functional losses for customers because migrating their services to other clouds is expensive and requires a large deal of technical effort. In a cloud federation, the FLA can be used to specify interfaces and data representation protocols supported on the environment, and then interested parties can migrate among federation providers if needed [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF].

Taxonomy of cloud federation.

Two main classifications of cloud federation exist as is seen in Figure 1:

According to the interaction level: There are vertical, horizontal and hybrid federations [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF][START_REF] Nadjaran Toosi | Interconnected cloud computing environments: Challenges, taxonomy, and survey[END_REF]. In a vertical federation, the interconnection, occurs between clouds at different levels of services, while in a horizontal federation the interconnection occurs between clouds at the same service level. Finally, hybrid federations perform horizontal and vertical expansion in accordance with the interest of both customers and providers [START_REF] Marcio Rm Assis | Cloud Federations: Requirements, Properties. Developing Interoperable and Federated Cloud Architecture[END_REF]. According to membership: There are three forms of federations [START_REF] Marcio Rm Assis | Cloud Federations: Requirements, Properties. Developing Interoperable and Federated Cloud Architecture[END_REF][START_REF] Marcio Rm Assis | Cloud Federations: Requirements, Properties. Developing Interoperable and Federated Cloud Architecture[END_REF][START_REF] Darzanos | Cloud Federations: Economics, Games and Benefits[END_REF][START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF]:

(i) ad-hoc federation: A CSP or a broker may use resources of other public CSPs such as Amazon AWS and Google apps. (ii) Structured federation: this federation is represented by small and medium private CSPs (companies which handle their own resources as a Cloud infrastructure) that collaborate with each other to maintain all properties of the cloud paradigm.

Manuscript submitted to ACM

Cloud federation taxonomy

Membership

The CSPs are governed by a Federation Level Agreements (FLA) [START_REF]CPLEX Optimizer[END_REF][START_REF] Boukhelef | Optimizing the cost of DBaaS object placement in hybrid storage systems[END_REF][START_REF] Darzanos | Cloud Federations: Economics, Games and Benefits[END_REF] which describes the relation between the different CSPs through functional and nonfunctional properties. This can be interesting and useful in many critical environments. In fact, FLA determines the behavior of heterogeneous and autonomous clouds [START_REF]CPLEX Optimizer[END_REF]. Therfore, it alleviates the complications between the federated clouds because resource sharing is well-behaved, obeying to this contract [START_REF] Marcio | A survey on cloud federation architectures: identifying functional and non-functional properties[END_REF].

(iii) Internal federation: here the cloud federation is composed of different geographically distributed data-centres belonging to the same institution. In this class there are no complex agreements to maintain between the clouds because they are managed by the same entity.

In this work, we suppose that we have a structured and horizontal federation where an FLA governes the federation CSPs and each one of them devotes a part of his resources to his partners (it can also be adapted to internal federations).

We are specifically interested in the object placement problem of a CSP member of a horizontal structured federation. We assume that each CSP of the federation devotes a part of his resources to the federation. The concerned CSP can use his own resources or that of the other federation members for the placement of his customers data objects. The main objective of this work is to provide the decision-maker with the different placement trade-offs that satisfy the customers requirements and minimize the placement costs.

Multi-objective optimization

Multiobjective optimization is a very important research topic as the nature of most problems is multi-objective in nature.

Unlike single-objective optimization (SOO), the purpose of MOO is to find a set of good solutions [START_REF] Nedjah | Evolutionary multi-objective optimisation: a survey[END_REF] representing trade-offs between objectives since a single solution optimizing all of the objectives simultaneously rarely exists [START_REF] Lemarchand | Multiobjective Optimization for Multimode Transportation Problems[END_REF]. A good solution is often defined by the dominance concept (see Section 2.2.2). A decision maker has to choose the final solution among the good ones [START_REF] Mukhopadhyay | A survey of multiobjective evolutionary algorithms for data mining: Part I[END_REF], by eventually considering factors not included in the optimization process because they can be hardly modeled and are sometimes subjective.

Multi-Objective Optimization Problem.

In MOO, an optimization problem over 𝑛 decision variables can be defined by the optimization (minimization or maximization, minimization in the sequel) of a given objective function vector (of 𝑘 objectives) and satisfaction of a set of 𝑚 constraints. The constraints define the space of feasible solutions [START_REF] Nedjah | Evolutionary multi-objective optimisation: a survey[END_REF]. wherein 𝑥 is the decision (solution) vector, 𝑋 the decision space, 𝑓 the objective vector and 𝑌 the objective space.

2.2.2 Pareto-optimality. The Pareto optimality [START_REF] Coello | Evolutionary algorithms for solving multi-objective problems[END_REF] concept is a way of defining good solutions when more than one objective is considered. A Pareto optimal solution is one that is not dominated by another solution from the feasible space, i.e. there exists no solution that is better for all considered goals.

More formally, the Pareto dominance relation is defined as follows: Definition 1: [START_REF] Coello | Evolutionary algorithms for solving multi-objective problems[END_REF] A vector 𝑣 " p𝑣 1 , 𝑣 2 , ..., 𝑣 𝑘 q dominates another vector 𝑤 " p𝑤 1 , 𝑤 2 , ..., 𝑤 𝑘 q if and only if @𝑖 P t1, 2, ..., 𝑘u, 𝑣 𝑖 ď 𝑤 𝑖 and D𝑗 P t1, 2, ..., 𝑘u, 𝑣 𝑗 ă 𝑤 𝑗 . This is denoted by 𝑣 ă 𝑤. Definition 2: the Pareto optimal set is defined by: 𝑃 " t𝑥 P 𝑋, ∄𝑥 1 P 𝑋, 𝐹 p𝑥 1 q ă 𝐹 p𝑥qu Definition 3: the Pareto front is defined by: 𝑃𝐹 " t𝐹 p𝑥q, 𝑥 P 𝑃u Definition 4: the Pareto set approximation is a set of approximate solutions where no element of this set is dominated by any other. Objective values in red color correspond to non-dominated solutions while those in gray color are dominated ones. They are generally based on the Darwinian natural selection theory. MOEAs help the decision makers to find a Pareto set within a reasonable time in case where the exact methods are not applicable. This is generally the case for large-scale problems due to the prohibitive execution time that their solving requires.

Multiobjective evolutionary algorithms (MOEAs)

Standard MOEAs perform sometimes poorly for difficult problems with complex feasible spaces or a high number of constraints [START_REF] Salcedo-Sanz | A survey of repair methods used as constraint handling techniques in evolutionary algorithms[END_REF]. Repair heuristics, solution penalization methods and special representations and operators are the classical techniques for constraint handling in evolutionary algorithms. Designing special representations and operators can be helpful but is also time consuming and does not take benefit of previous work. Penalization methods are the oldest approach used to handle constraints in optimization algorithms including MOEAs [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF]. They consist to transform a constrained-optimization problem into an unconstrained one by adding/subtracting a certain value to/from the objective function based on the amount of constraint violation present in a certain solution [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF]. However, they do not guarantee to find feasible solutions. Repair operators consist to reduce the search space to feasible solutions by making some local search in order to transform unfeasible solutions to feasible ones. The repair operators avoid repetitive and costly evaluation of unfeasible solutions maintained by penalization methods and they handle directly the problem constraints [START_REF] Salcedo-Sanz | A survey of repair methods used as constraint handling techniques in evolutionary algorithms[END_REF]. Also, a repair operator allows to use all the well-known and efficient standard operators. Three goals must be considered when solving a MOO problem. These are [START_REF] Riquelme | Performance metrics in multi-objective optimization[END_REF][START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF] (i) precision: this means that the found non-dominated solutions should be as close as possible to the Pareto-optimal front, (iii) exhaustivity: the solutions must be numerous and (iii) diversity: as the found solutions should be well spaced over the Pareto front.

Manuscript submitted to ACM

Performance indicators.

In single-objective minimization, the quality of a given solution is trivial to quantify, however, evaluating the quality of an approximation of a Pareto set is a non-trivial task [START_REF] Audet | Performance indicators in multiobjective optimization[END_REF].

To quantify and compare the quality of solution sets produced by different MOEAs, numerous performance indicators have been proposed in the literature. These performance indicators consist in assigning scores to Pareto front approximations [START_REF] Audet | Performance indicators in multiobjective optimization[END_REF][START_REF] Bouaziz | Multi-objective design exploration approach for ravenscar real-time systems[END_REF]. We quote, among others, Generational Distance, Inverted Generational Distance, Hypervolume, Maximum Pareto Front Error and Spacing. These indicators allow to compare Pareto fronts, in term of precision, exhaustivity and diversity or any combination. In our evaluations, we used the Hypervolume indicator. Hypervolume (HV), also called hyperarea, is one of the most popular measures for the performance assessment of multi-objective algorithms [START_REF] While | A faster algorithm for calculating hypervolume[END_REF]. It encompasses the exhaustivity, the precision and the diversity metrics [START_REF] Audet | Performance indicators in multiobjective optimization[END_REF][START_REF] Bouaziz | Multi-objective design exploration approach for ravenscar real-time systems[END_REF]. It computes the portion of the objective space dominated by all the solutions bounded by a reference point 𝑟 . The HV of an approximate Pareto front 𝑃𝐹 𝑎𝑝𝑝𝑟𝑜𝑥 is obtained by 𝜆 𝑘 p Ť 𝑧P𝑃 𝐹 𝑎𝑝𝑝𝑟𝑜𝑥 r𝑧; 𝑟 sq where 𝜆 𝑘 is the k-dimensional Lebesgue measure [START_REF] Audet | Performance indicators in multiobjective optimization[END_REF]. The greater the HV value, the better the approximation is. An illustration is given in Figure 3 for the bi-objective case (𝑘 " 2).

SYSTEM MODEL AND PROBLEM FORMULATION

The placement of customers data objects for a CSP member of a federation is a hard problem [START_REF] Mahi | A new approach based on particle swarm optimization algorithm for solving data allocation problem[END_REF][START_REF] Wen | Cost effective, reliable and secure workflow deployment over federated clouds[END_REF]. In order to build a smart placement solution, we first need to formulate it under the form of an optimization problem. The objective function of this problem seeks the minimization of the placement cost. This work is based on the cost model proposed in [START_REF] Chikhaoui | A Cost Model for Hybrid Storage Systems in a Cloud Federations[END_REF] and built for data object placement in a federated cloud. Furthermore, object placement must be realized while respecting a set of constraints related to the system model. Notation used in this paper is summerized in Table 1.

In this section, we start by briefly discussing the challenges and objectives of this study. Then, we describe the target system. After that, the used cost model is shortly introduced. Finally, we end up by formulating the placement problem.

Challenges and objectives

The main objective in this work is to assist the cloud administrator of a CSP in order to find a good placement configuration of the customers data objects. The local storage infrastructure and other storage services from other CSPs are used to manage the customers data objects. The I/O storage performance and the network latency are the targeted QoS metrics for the customers. The sought placement configuration should respect the customers QoS requirements and at the same time minimize the CSP costs.

Minimizing the placement cost is contradictory with satisfying the customers requirements. On the other hand, the satisfaction of both I/O storage performance and network latency may be contradictory in certain circumstances. For example, placing a customer object in one location may respect the requested I/O storage performance but may generate a high network latency. In addition, the placement configuration must adapt to the dynamic and heterogeneous environment.

In fact the used local and external resources have different characteristics in term of capacity, performance and prices. Also, the CSPs of the federation may update their storage resource prices according to the availability of their resources.

Furthermore, the customers have different workloads which may change over time. Customers may be mobile or have users geographically spread, which impacts the network latency to access their objects. Dealing with such a dynamic and heterogeneous system makes data placement strategies very challenging and a thorough formulation of the placement The placement cost of internal customers data objects 𝐶𝑜𝑠𝑡 𝑙𝑐𝑙,𝑇

The local placement cost 𝐶𝑜𝑠𝑡 𝑙𝑠𝑡𝑔,𝑇

The local storage cost 𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇

The local migration cost 𝐶𝑜𝑠𝑡 𝑜𝑢𝑡𝑠𝑟𝑐,𝑇

The outsourcing cost 𝐶𝑜𝑠𝑡 𝑒𝑠𝑡𝑟,𝑇

The external storage cost 𝐶𝑜𝑠𝑡 𝑔𝑚𝑔𝑟,𝑇

The geo-migration cost 𝐶𝑜𝑠𝑡 𝑏𝑚𝑔𝑟,𝑇

The back-migration cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡,𝑇

The penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑖𝑜 ,𝑇

The storage performance penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇

The network latency penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡𝑚𝑔𝑟 ,𝑇

The migration penalty cost problem must take into account most of the system related factors in order to make adequate decisions for placing data objects.

Manuscript submitted to ACM In this work, we focus on the data objects placement from the stand point of a single CSP. Indeed, in a Cloud federation, each CSP is free to apply his own optimization techniques. We suppose that the CSPs use interfaces and tools like OCCI standard interface [START_REF] Edmonds | Toward an open cloud standard[END_REF] or apache LibCloud [START_REF]One Interface To Rule Them All[END_REF] in order to unify the interface and facilitate migrating services among clouds.

System overview

𝑍 0 𝐶𝑆𝑃 0 𝑢 0 𝑠𝑐 0 (𝑝 " 0) 𝑠𝑐 1 (𝑝 " 1) Data Manager 𝑜 1,0 𝑜 2,1 𝑜 2,0 𝑜 1,1 𝑍 1 𝐶𝑆𝑃 1 𝑢 1 𝑢 0 (𝑝 " 2) 𝑜 3,0 𝑜 0,1 𝑜 3,1
Let 𝐶𝑆𝑃 ℎ be the considered provider that wants to optimize the placement of data objects of his customers (𝐶𝑆𝑃 0 in the example of Figure 4).

The data placement optimization process is performed by the Data Manager component. It incorporates the different steps of a MAPE-K model which is described below.

First, The Monitor step consists to perform a periodic monitoring of the federated environment by collecting and aggregating the monitored parameters such as the available storage resources of the CSPs and their prices, the customers locations and the latency of their requests, the objects current placement, etc. Monitoring tools, such as Amazon CloudWatch [START_REF]Amazon CloudWatch[END_REF] or OpenStack Watcher [START_REF]OpenStack Watcher project[END_REF], may be used in this step. Also, each CSP may share part of his own monitoring data to the federation.

Then, the monitoring data are passed to the Data Placement Optimizer module. This module is composed of the Analyze and Plan steps of the MAPE-K process. The Analyze step consists of two phases. In the first one, the monitored metrics are introduced in a cost model in order to calculate the costs related to the data placement. The second phase uses the monitored metrics in addition to the results of the first phase in order to build and formalize an optimization problem. The Plan step incorporates some methods that aim to find the data placement configurations that achieve a trade-off between some given criteria. Finally, based on the results obtained by the Data Placement Optimizer and some non-technical aspects such as the CSP reputation, in the Execute step, a placement scheme is selected and the customers objects placement are autonomously re-configured.

In this work, we focused on the Data Placement Optimizer module.

Manuscript submitted to ACM

ą 𝑏 𝑖 ą 𝑏 𝑖`1 ą 0) 𝑙𝑡𝑐 𝑜 𝑓 𝑓 𝑒𝑟𝑒𝑑 Price (%) r0..𝐵 1 s 𝑏 0 r𝐵 𝑖 ..𝐵 𝑖`1 s 𝑏 𝑖 ą 𝐵 𝑛 0 (a) 𝑙𝑡𝑐 𝑜 𝑓 𝑓 𝑒𝑟𝑒𝑑 Penalty (%) r0..𝐵 1 s 0 r𝐵 𝑖 ..𝐵 𝑖`1 s 𝑏 0 ´𝑏𝑖 ą 𝐵 𝑛 𝑏 0 (b)

System model

To illustrate our problem, we describe, in this section, the targeted system and the hypotheses of our work.

We consider a cloud federation composed of 𝐷 CSPs, spread over 𝑀 different geographical zones with (𝐷 ě 𝑀). There may be one or more CSPs in each zone with different characteristics.

For instance, in Figure 4, we have 3 CSPs spread over 2 zones 𝑍 0 and 𝑍 1 .

We suppose that 𝐶𝑆𝑃 ℎ accommodates 𝐽 different storage classes. Each storage class 𝑠𝑐 𝑗 (e.g. 𝐽 " 2 in Figure 4, HDD for 𝑠𝑐 0 and SSD for 𝑠𝑐 1 ) is characterized by its capacity 𝑐𝑠𝑐 𝑗 , its iops according to the type of I/O operation issued 𝑖𝑜 𝑗 p𝑜𝑝q.

We considered the following I/O operations as they proved to perform differently according to state-of-the-art work: sequential read p𝑠𝑟 q, sequential write p𝑠𝑤q, random read p𝑟𝑟 q and random write p𝑟𝑤q. Each storage class has also other characteristics such as the price and the guarantee period.

We assume that 𝐶𝑆𝑃 ℎ can use storage services offered by the other CSPs of the federation. A storage service 𝑠𝑠 𝑑 of a distant partner 𝐶𝑆𝑃 𝑑 (for instance 𝐶𝑆𝑃 1 and 𝐶𝑆𝑃 2 in Figure 4) is defined by the storage capacity 𝑐𝑠𝑠 𝑑 and the storage performance 𝑖𝑜 𝑑 . The storage services can be billed differently by partner CSPs.

The provider 𝐶𝑆𝑃 ℎ handles a set 𝑈 of 𝐾 internal customers. Customers may be located in different geographical zones.

They may be mobile or have end-users geographically spread. For example, in Figure 4, there are two customers 𝑢 0 and 𝑢 1 .

Customer 𝑢 0 end users are spread on the two zones 𝑍 0 and 𝑍 1 while end users of customer 𝑢 1 are located in zone 𝑍 1 . Each customer 𝑢 𝑘 has a data application composed of a set of objects 𝑂 𝑘 . It generates a workload made up of several types of requests such as get, put and update. The workload generates a set of different I/O operations (that can be captured with tracing tools as in [START_REF] Ouarnoughi | A multi-level I/O tracer for timing and performance storage systems in IaaS cloud[END_REF]). Each object 𝑖 of a customer 𝑘, denoted 𝑜 𝑖,𝑘 , has a size 𝑠 𝑜 𝑖,𝑘 and is accessed through different I/O requests per operation type 𝑖𝑜 𝑜 𝑖,𝑘 p𝑜𝑝q.

The customer also requests a QoS (SLA) in terms of number of IOPS. The IOPS SLA is expressed by a hard SLA 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 which must be respected and a soft SLA 𝑖𝑜𝑆𝑜 𝑓 𝑡 𝑘 . This is a proportional penalty model related to the degree and the delay of the SLA storage performance violation [START_REF] Boukhelef | A cost model for dbaas storage[END_REF]. Note that 𝑖𝑜𝑆𝑜 𝑓 𝑡 𝑘 represents the agreed upon I/O throughput of customer 𝑢 𝑘 while 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 is the limit of I/O throughput degradation tolerated by 𝑢 𝑘 . 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 represents the IOPS effectively delivered to the customer 𝑢 𝑘 . If 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 is lower than the soft SLA, 𝐶𝑆𝑃 ℎ undergoes a storage IOPS related penalty.

We suppose, as in [START_REF] Douglas B Terry | Consistencybased service level agreements for cloud storage[END_REF], that the network performance of the queries is billed according to the experienced latency as in indicates the (highest) price of the lowest latency interval. If the network latency exceeds a certain limit, its price becomes zero (the higher the latency, the lower the price). So, If the offered latency is within the interval [𝛽 𝑖 ,𝛽 𝑖`1 ], 𝐶𝑆𝑃 ℎ loses an amount corresponding to 𝑏 0 ´𝑏𝑖 as shown in Table 2b. We denote by 𝑝𝑒𝑛𝑎𝑙𝑡𝑦p𝑙 𝑍 𝑚 ,𝑍 𝑚 1 q the latency penalty between the zones 𝑍 𝑚 and 𝑍 𝑚 1 , 𝑙 𝑍 𝑚 ,𝑍 𝑚 1 being the latency between the two zones. For simplicity, 𝑙 𝑍 𝑚 ,𝑍 𝑚 " 0 as the network latency in a given zone is small.

Manuscript submitted to ACM

We suppose that the cloud administrator periodically makes decisions about objects placement. 𝑇 is the time period during which monitoring is executed to extract objects I/O patterns for making such a placement decision. One example of a framework that considers such periodic changes is the OpenStack Watcher project [START_REF]OpenStack Watcher project[END_REF].

As already discussed, Cloud customers are mobile or have many users geographically spread. So, the locations from which requests originate may change over time.

We want to model the overall workload applied by a customer 𝑢 𝑘 (its users) issued from the different zones in order to calculate the network latency penalty. For that, we use the matrix 𝑜𝑐𝑐 𝑘 which elements 𝑜𝑐𝑐 𝑚,𝑟 𝑘 represent the number of requests of type 𝑟 issued by the customer 𝑢 𝑘 from the zone 𝑍 𝑚 . As well, let the matrix 𝑎𝑐𝑐 𝑘 represent the access of the requests to the objects. Each element 𝑎𝑐𝑐 Matrix 𝑎𝑐𝑐 0 represents the access fraction of these requests per object.

𝑎𝑐𝑐 0 " 𝑜 0,0 𝑜 1,0 𝑜 2,0 𝑜 3,0 𝑜 4,0 ˜ģ𝑒𝑡 0.6 0.1 0.2 0 0.1 𝑢𝑝𝑑𝑎𝑡𝑒 0.5 0 0.2 0.1 0.2
So, the resulting matrix 𝑡𝑜𝑡 0 represents the total requests issued from the location of each zone and accessing to the different objects and is given as follows: The element 𝑡𝑜𝑡 1,𝑜 0,0 0

𝑡𝑜𝑡 0 " 𝑜 0,0 𝑜 1,0 𝑜 2,0 𝑜 3,0 𝑜 4,
" 1250 represents the total number of requests issued from the zone 𝑍 1 by the end-users of the customer 𝑢 0 that access to the object 𝑜 0,0 .

Manuscript submitted to ACM

Cost model

A cost model was proposed in [START_REF] Chikhaoui | A Cost Model for Hybrid Storage Systems in a Cloud Federations[END_REF] for object data placement in a federated cloud. The overall placement cost for data objects of internal customers in a time period 𝑇 consists of a local placement cost 𝐶𝑜𝑠𝑡 𝑙𝑐𝑙,𝑇 , an outsourcing cost 𝐶𝑜𝑠𝑡 𝑜𝑢𝑡𝑠𝑟𝑐,𝑇 , a back-migration cost 𝐶𝑜𝑠𝑡 𝑏𝑐𝑘-𝑚𝑔𝑟,𝑇 and a penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡,𝑇 as shown in Eq. ( 2). Note that is in this paper, every time a cost is discussed, it is related to a monetary cost.

𝐶𝑜𝑠𝑡 𝑝𝑙𝑐,𝑇 " 𝐶𝑜𝑠𝑡 𝑙𝑐𝑙,𝑇 `𝐶𝑜𝑠𝑡 𝑜𝑢𝑡𝑠𝑟𝑐,𝑇 C𝑜𝑠𝑡 𝑏𝑚𝑔𝑟,𝑇 `𝐶𝑜𝑠𝑡 𝑝𝑛𝑡,𝑇 (2)
𝐶𝑜𝑠𝑡 𝑙𝑐𝑙,𝑇 " 𝐶𝑜𝑠𝑡 𝑙𝑠𝑡𝑔,𝑇 `𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇 (3)
𝐶𝑜𝑠𝑡 𝑜𝑢𝑡𝑠𝑟𝑐,𝑇 " 𝐶𝑜𝑠𝑡 𝑔𝑚𝑔𝑟,𝑇 `𝐶𝑜𝑠𝑡 𝑒𝑠𝑡𝑟,𝑇 (4)
𝐶𝑜𝑠𝑡 𝑝𝑛𝑡,𝑇 " 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑖𝑜 ,𝑇 `𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 (5)
We briefly describe the different components here-under. 5). As previously discussed, the CSP undergoes an I/O penalty when 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 are less than the 𝑖𝑜𝑆𝑜 𝑓 𝑡 𝑘 for any customer 𝑢 𝑘 . Concerning the network latency penalty, it is related to the number of issued requests 𝑡𝑜𝑡 𝑘 (see Eq. ( 1)) by each customer 𝑢 𝑘 and the latency level between their origin zones and that of the requested objects.

Local placement cost:

Problem formulation

Our objective is to find a good placement configuration for customers' objects of a CSP using opportunistically both its internal storage classes and the storage services of partner CSPs. The sought placement configuration should respect the customers QoS requirements and at the same time minimize CSP costs.

When we analyze the placement cost (see Section 3.4), we find that it is composed of three main components which are: (1) the storage cost related to the occupation and I/O workload costs, (2) the migration cost which is defined by the different migrations in the system, and (3) the network latency cost that is the penalty generated by the deterioration of the QoS caused by the network latency. These costs are in some cases contradictory. For instance, placing data locally may be cheap in term of storage and migration costs but may generate a bad network latency for customers located in other Manuscript submitted to ACM regions. Another example is that there exists a location that may minimize both storage and latency costs but migration to this location generates a prohibitive cost. So, making a trade-off while placing data objects is inevitable.

In order to give more flexibility to the cloud administrator to update the placement configuration of customers objects, we formulate the placement problem under the form of a multi-objective optimization problem taking into account the three functions namely (1) storage cost, (2) migration cost, and (3) latency cost, and constraints related to the limited local and external resources and customers SLAs.

In this section, we will, first, specify how a solution representing a placement configuration is encoded. Then, we will define its cost functions and show how to evaluate them. Finally the constraints to meet will be described.

Individual representation.

In our work, a solution for the placement of customers objects is represented by means of a classical integer encoding schema. With such an encoding, each individual, named also a chromosome, is defined as an integer array which represents a placement configuration of all the objects of all the customers in 𝑃 locations. So, a chromosome is a set of genes. A gene number 𝑖 in a chromosome corresponds to the object number 𝑖. The value of a gene 𝑖 corresponds to the location of object 𝑖. As explained already, from a CSP perspective, the overall number of locations 𝑃 equals to the number of the local storage classes plus the number of partner CSPs (𝑃 " 𝐷 `𝐽 ´1).

So a placement configuration is represented by the vector 𝑥 " p𝑥 𝑜 0,0 , 𝑥 𝑜 1,0 , ¨¨¨, 𝑥 𝑜 𝑖,𝑘 ¨¨¨q where 𝑥 𝑜 𝑖,𝑘 is a potential location for the object 𝑜 𝑖,𝑘 .

For simplification, in our representation, a location 𝑝 P r0, 𝐽 r corresponds to local storage classes while 𝑝 P r𝐽, 𝐷 `𝐽 ´1r corresponds to a location in a partner cloud.

In the example depicted in Figure 4. 𝐶𝑆𝑃 0 is the concerned one by the optimization placement. It accommodates 2 storage classes, then 𝑝 " 0 and 𝑝 " 1 correspond to the local placement. 𝑝 " 2 corresponds to a placement in 𝐶𝑆𝑃 1 while 𝑝 " 3 represents a placement in 𝐶𝑆𝑃 2 .

The particular assignment sketched in Figure 4 corresponds to the chromosome 𝑥 " p𝑥 0,0 , ..., 𝑥 4,0 , 𝑥 0,1 , ..., 𝑥 4,1 q represented by the vector 𝑥 " p3, 0, 1, 2, 3, 2, 1, 0, 2, 3q . The chromosome length indicates the numbers of all customers' objects. In this example we have 2 customers each one has 5 objects which means, the length of the chromosome is 10. The gene 𝑥 𝑜 0,0 holds a value equals to 3 meaning that the object 𝑜 0,0 is assigned to the location 𝑝 " 3, it corresponds to 𝐶𝑆𝑃 2 .

Objective functions.

The addressed problem consists in determining a placement of customers data objects on local and/or external storage systems so as to provide a better data access performance while minimizing the placement cost. The data access patterns are changing in time and the customers are mobile or their users can be geographically spread. The customers QoS requirements are expressed in term of I/O storage performance and network latency. Placing a customer object in one location may satisfy one QoS requirement but not the other. Besides, given the characteristics of the system, to reach the main objective (minimizing the placement cost and satisfying the customers SLAs), the customers data objects placement configuration may change over time. This means that some data objects need to be migrated.

Migrating data objects cost is variable according to the source and destination properties, which makes the migration cost another dimension to be optimized. Hence, storage, latency and migration costs are considered as the dimensions of the fitness function in the placement problem as shown in Eq. ( 6).

Manuscript submitted to ACM

Where 𝑥, 𝑠𝑡𝑜𝑟𝑒p𝑥q, 𝑚𝑖𝑔𝑟𝑎𝑡𝑒p𝑥q and 𝑙𝑎𝑡𝑒𝑛𝑐𝑦p𝑥q respectively represent the decision variable, the storage, migration and latency costs. Figure 5 shows an overview of the considered objective function costs. They encompass the overall placement cost defined in Section 3.4 and will be described in the following sections. 3) and Eq. ( 4)). It also includes the I/O storage performance part penalty cost part 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑖𝑜 ,𝑇 from the penalty cost (see Eq. ( 5)). We recall that this penalty represents the additional monetary cost caused by the I/O SLA violation (the network penalty is considered in the latency cost).

𝑠𝑡𝑜𝑟𝑒p𝑥q is defined as in Eq. ( 7):

𝑠𝑡𝑜𝑟𝑒p𝑥q " 𝐶𝑜𝑠𝑡 𝑙𝑠𝑡𝑔,𝑇 `𝐶𝑜𝑠𝑡 𝑒𝑠𝑡𝑟,𝑇 `𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑖𝑜 ,𝑇 (7)
Migration cost: The migration cost 𝑚𝑖𝑔𝑟𝑎𝑡𝑒p𝑥q encompasses the local migration cost 𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇 from Eq. ( 3) when the objects are moved between local storage classes, the external migration cost 𝐶𝑜𝑠𝑡 𝑔𝑚𝑔𝑟,𝑇 from Eq. ( 4) when the objects are sent to another CSP and the back migration cost 𝐶𝑜𝑠𝑡 𝑏𝑚𝑔𝑟,𝑇 from Eq. ( 2) when the objects are returned back to the local infrastructure. We have also considered a penalty cost related migration operation 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑚𝑔𝑟 ,𝑇 . It is induced by the degradation of the QoS caused by the migration. We have calculated it in term of the total number of customers 𝐾, the maximum migration time 𝑚𝑟𝑔 𝑡𝑖𝑚𝑒,𝑇 and some unitary costs 𝛼 as shown in Eq [START_REF] Brunelle Alan | blktrace User Guide[END_REF].We considered 𝛼 as a storage performance and latency unitary cost assuming that during the migration time the QoS are not met. By doing so, this migration penalty cost represents an upper bound as the QoS degradation is not necessarily experienced by all customers.

In our evaluation, we set 𝛼 as the sum of the cost corresponding to the average IOPS needed by customers and the latency cost corresponding to the average requests sent by customers per second.

𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑚𝑔𝑟 ,𝑇 " 𝛼 ˚𝐾 ˚𝑚𝑟𝑔 𝑡𝑖𝑚𝑒,𝑇 (8)
𝑚𝑖𝑔𝑟𝑎𝑡𝑒p𝑥q " 𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇 `𝐶𝑜𝑠𝑡 𝑔𝑚𝑔𝑟,𝑇

`𝐶𝑜𝑠𝑡 𝑏𝑚𝑔𝑟,𝑇 `𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑚𝑔𝑟 ,𝑇 (9)
Latency cost: The network latency has been considered as a cost in many research studies as in [START_REF] Saeida | A self-configurable geo-replicated cloud storage system[END_REF][START_REF] Mansouri | To move or not to move: Cost optimization in a dual cloud-based storage architecture[END_REF][START_REF] Douglas B Terry | Consistencybased service level agreements for cloud storage[END_REF]. In our work, this cost (𝑙𝑎𝑡𝑒𝑛𝑐𝑦p𝑥q) reflects the network penalty cost. As we supposed in Section 3.3, the network latency is billed for customers, and the deterioration of the delivered latency causes losses for the CSP according to the level of its Manuscript submitted to ACM degradation. Concretely, it is the part of the penalty cost related to the network latency (𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 taken from Eq. ( 5)).

This cost is the sum of all customers latency penalties as shown in Eq. 10

𝑙𝑎𝑡𝑒𝑛𝑐𝑦p𝑥q " 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 "

ÿ 𝑢 𝑘 P𝑈 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 p𝑢 𝑘 q (10)
𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 p𝑢 𝑘 q represents the network latency penalty of customer 𝑢 𝑘 . We calculated it by multiplying the number of requests issued by the customer 𝑢 𝑘 or its end-users from the different zones by the network latency penalty. This penalty is related to the latency between the location of 𝑢 𝑘 or its end-users and that of the requested objects. It is defined according to Table 2b. So, 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 p𝑢 𝑘 q is calculated as in Eq. ( 11):

𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 p𝑢 𝑘 q " ÿ 𝑍 𝑚 ÿ 𝑜 𝑖,𝑘 P𝑂 𝑘 𝑡𝑜𝑡 𝑚,𝑜 𝑖,𝑘 𝑘 ˚𝑝𝑒𝑛𝑎𝑙𝑡𝑦p𝑙p𝑚, 𝑥 𝑜 𝑖,𝑘 qq (11)
3.5.3 Constraints. In this work, we have constraints related to the capacity and the performance throughput limitation of the local and the external storage systems. In addition, there are also constraints related to the customers SLAs.

For each local storage 𝑠𝑐 𝑗 , the sum of the assigned objects sizes (𝑆 𝑜 𝑖,𝑘 ) should not exceed the capacity of that storage class 𝑐𝑠𝑐 𝑗 . This is expressed in Eq. ( 12). Also, the allocated storage service capacity 𝑐𝑠𝑠 𝑑 of each 𝐶𝑆𝑃 𝑑 of the federation is limited. Therefore, the sum of objects sizes affected to each partner storage service 𝑠𝑠 𝑑 should not exceed its capacity as shown in Eq. ( 13)

ÿ 𝑢 𝑘 ÿ 𝑜 𝑖,𝑘 P𝑠𝑐 𝑗 𝑆 𝑜 𝑖,𝑘 ď 𝑐𝑠𝑐 𝑗 @𝑗 ă 𝐽 (12)
ÿ

𝑢 𝑘 ÿ 𝑜 𝑖,𝑘 P𝑠𝑠 𝑑 𝑆 𝑜 𝑖,𝑘 ď 𝑐𝑠𝑠 𝑑 @𝑑 ě 𝐽 (13)
The throughputs of the local and the external storage systems are limited. For the local storage classes, Eq. ( 14)

expresses
ÿ 𝑜𝑝P𝑂𝑃 ř 𝑢 𝑘 ř 𝑜 𝑖,𝑘 P𝑠𝑠 𝑑 𝑖𝑜 𝑜 𝑜 𝑖,𝑘 p𝑜𝑝q 𝑖𝑜 𝑑 ď 1, @𝑑 ě 𝐽 (15)
Regarding the customers I/O SLA, when 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 for a given customer 𝑢 𝑘 is between 𝑖𝑜𝑆𝑜 𝑓 𝑡 𝑘 and 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 , the CSP undergoes a storage I/O penalty. However, 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 must be satisfied. This implies that the 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 storage performance of each customer must exceed his 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 as shown in Eq. ( 16).

𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 ą" 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 @𝑢 𝑘 P 𝑈

Finally we assume that the objects are not replicated. This condition is guaranteed by the used encoding. To solve the above problem, we need to use a multi-objective optimization algorithm tailored to our problem. As shown in Figure 6, this algorithm will use different inputs related to the local storage classes and and foreign services specifications and locations, the workload, SLAs and location of the customers, and finally, the objects specifications and their current placement. For the calculation of objective functions, we used the previously proposed cost model. We have chosen NSGAII to solve the placement problem. However, as evolutionary meta-heuristics do not perform well in difficult problems with complex combinatorial spaces or a high number of constraints [START_REF] Salcedo-Sanz | A survey of repair methods used as constraint handling techniques in evolutionary algorithms[END_REF], we have tailored NSGAII to our placement optimization. This is the subject of the next section.

CDP-NSGAII 𝐼𝑅 : CONSTRAINT DATA PLACEMENT NSGAII WITH INJECTION AND REPAIR OPERATORS

Due to the dynamic nature of cloud federation environment and customers workloads, data objects placement strategies need to be performed online.

The placement problem is known to be NP-hard [START_REF] Kapali | Placement of Records in a File and File Allocation in a Computer[END_REF][START_REF] Mahi | A new approach based on particle swarm optimization algorithm for solving data allocation problem[END_REF]. As a matter of fact, enumerating all possible placement options and eventually choosing the best configuration leads to a combinatorial explosion.

Meta-heuristics constitute a good alternative to alleviate the execution time complexity. Given the popularity and effectiveness of Non-dominated Sorting Genetic Algorithm (NSGAII), we will use it to solve our placement problem.

However, being an evolutionary algorithm, NSGAII suffers from issues related to solutions unfeasability when the size of the problem increases. In fact, solutions unfeasability has a negative impact of the resulting Pareto front quality and the execution time. Thus, our implementation of NSGAII needs some modifications to address those issues.

For that, we upgraded our first implementation of NSGAII to a matheuristic [START_REF] Voss | MATHEURISTICS: Hybridizing Metaheuristics and Mathematical Programming[END_REF] by merging it with an exact method. This latter calculates some solutions which are injected to the initial population of NSGAII. Furthermore, we propose a repair function to improve the NSGAII execution time. It modifies the invalid placement configuration by moving some objects to other locations in order to meet the placement constraints. We call the proposed heuristic CDP-NSGAII 𝐼𝑅 for Constrained Data Placement NSGAII with a Injection and Repair functions.

In this section we will, first, describe the issue of NSGAII evolutionary operators which pushes us to upgrade NSGAII in order to enhance its results for our problem. Then, we will describe the proposed matheuristic.

NSGAII based approach

Among the strategies used to overcome the execution time complexity are heuristics and meta-heuristics. As we are facing a multi-objective problem, multi-objective evolutionary algorithms (MOEAs) are effective techniques for finding multiple efficient solutions in a reasonable time [START_REF] Kumar | Fuzzy rule-based reliability analysis using NSGA-II[END_REF], see Section .

Evolutionary algorithms are iterative stochastic algorithms based on the Darwinian natural selection theory. Their idea is to let a set of solutions (population) evolve according to a given problem over generations, in order to find the best results. The evolution is performed via a set of operators. Generally, selection operators replace individuals for the next generation. Mutation and crossover operators discover new solutions by, respectively, transforming existing ones or mixing parts of different solutions.

Non-dominated Sorting Genetic Algorithm (NSGAII) is a well-known MOEA used in many optimization problems such as [START_REF] Kumar | Fuzzy rule-based reliability analysis using NSGA-II[END_REF][START_REF] Sathya | Multi-objective task scheduling to minimize energy consumption and makespan of cloud computing using NSGA-II[END_REF][START_REF] Xu | Multiobjective computation offloading for workflow management in cloudlet-based mobile cloud using NSGA-II[END_REF]. As for other meta-heuristics, NSGAII has to be customized for the targeted problem. An encoding and operators must be chosen on the shelf or specifically designed. In our case, we have adapted a standard codification to represent placement configurations (see Section 3.5.1 for chromosome strings representation). Also, standard mutation and crossover operators for strings of numbers are used. For example, for 𝑁 " 5 objects and 𝑃 " 2 locations, the r00011s and r11000s solutions can be valid (no resource overflow), but they can be mixed, e.g., into r11011s by a crossover operator, leading to an unfeasible solution, because constraint on location 1 may not be respected or this location may not satisfy the SLAs of all the customers whose objects are placed in this location.

More generally, the search space size induced by the encoding is 𝑃 𝑁 , while the feasible space can be much smaller, due to resource and customers constraints. This could make the search inefficient, especially for large problems, when the unfeasible region explored uselessly is huge. This results in a poor Pareto front.

There exists three possible ways to deal with the solutions unfeasbility caused by problem constraints (See Section 4.1).

The first one consists in modifying the exploration operators, the second one penalizes unfeasible solutions and the third one relies on building a repair function in order to fix an unfeasible solution into a feasible one after applying standard search operators. We used the repair solution for two main reasons: (i) it is simple to implement and allows to use all the well-known and efficient standard operators; (ii) it does not slow down the application of those operators by checking the placement constraints. Furthermore, NSGAII initial population is enriched with some solutions calculated by an exact method making NSGAII a matheuristic which is the subject of the following section.

CDP-NSGAII 𝐼𝑅 matheuristic

The matheuristic optimization process is achieved in two steps : the Preprocessing step and the Evolutionary step as shown in Figure 7. In the former, a set of placement solutions are calculated using CPLEX solver. This process is described later in Section 4. In the following, we will explain how some initial solutions are calculated. Then the repair function is detailed.

Exact method based on MILP tool.

The exact method in this work consists in transforming the MOO problem into a single-objective problem and to solve it using a MILP tool. Algorithm 1 formulates the exact method process. First, the min and max of each objective function are calculated (line 2 and line 3 of Algorithm 1). Then, the values are normalized (line 5 to line 7 of Algorithm 1). These functions are weighted and combined into a single objective function. CPLEX [START_REF]CPLEX Optimizer[END_REF],

is used to solve the obtained single-objective problem (line 9 and line 10 of Algorithm 1). This solving process is repeated several times with different weights in order to generate a set of exact solutions.

Algorithm 1 Calculation of some exact solutions using a MILP solver

Repair

Function. When a solution does not meet all placement constraints defined in Eq. ( 12), Eq. ( 13), Eq. ( 14), Eq. ( 15) and Eq. ( 16), objects are moved leading to a feasible solution. Algorithm 2 shows how our repair function works.

The repair function works according to two steps. The first one consists in finding the objects that violate the placement constraints while the second one tries to revise the placement of these objects by moving them to suitable locations responding to both resources limitations and customers SLAs. These steps are explained as follows:

Step 1: To detect all the objects that break the constraints in a chromosome (a placement configuration), we span the chromosome sequentially gene by gene, checking objects locations one by one. If placing a given object to the corresponding gene value does not imply some constraints violation, the value of the gene is kept unchanged. In the other case, it is added to an unfeasible list called 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 .

At the end, 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 contains all the objects that, with the current placement values, do not meet the capacity or the performance of the storage resources constraints or whose locations do not satisfy customers SLAs.

This step corresponds to Algorithm 2, line 2 to line 9.

Let us take the Cloud federation depicted in Figure 4. For the sake of simplicity, we consider only the constraint related to the capacities of local storage classes and external storage services. Suppose that the two local storage classes capacities (𝑐𝑠𝑐 0 and 𝑐𝑠𝑐 1 ) are respectively 10 and 5 units. 𝐶𝑆𝑃 1 storage service capacity 𝑐𝑠 1 equals to 8 and 𝐶𝑆𝑃 2 capacity 𝑐𝑠 2 is 5 units. We assume also that the size of each object equals to 2 units. A placement configuration 𝑥 " p1, 3, 1, 0, 1, 1, 0, 3, 3, 2q

depicted in Figure 8 is not feasible as the capacity of the resources corresponding to locations 𝑝 " 1 (8 units used from 5 available) and 𝑝 " 3 (6 units used from 5 available) is exceeded.

Manuscript submitted to ACM 𝑜 0,0

1 𝑜 1,0 3 𝑜 2,0 1 𝑜 3,0 0 𝑜 4,0 1 𝑜 0,1 1 𝑜 1,1 0 𝑜 2,1 3 𝑜 3,1 3 𝑜 4,1 2
Step 1: Selection of objects that break the constraints

Result:

𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 " t𝑜 4,0 , 𝑜 0,1 , 𝑜 3,1 u

𝑜 0,0 1 𝑜 1,0 3 𝑜 2,0 1 𝑜 3,0 0 𝑜 4,0 ? 𝑜 0,1 ? 𝑜 1,1 0 𝑜 2,1 3
𝑜 3,1 ? 𝑜 4,1 2
Step 2: Re-affect the objects to suitable places Result: The first step of the repair function looks for the objects that violate the capacity constraint. We check the chromosome object by object. The locations of the first four objects 𝑜 0,0 , 𝑜 1,0 , 𝑜 2,0 , 𝑜 3,0 are kept unchanged because they respect the capacity constraints. At this stage, the remaining storage capacities 𝑐𝑠𝑐 0 , 𝑐𝑠𝑐 1 , 𝑐𝑠 1 , 𝑐𝑠 2 are respectively (8,1,8,3).

𝑜 4,0 𝑝 " 0 𝑜 0,1 𝑝 " 0 𝑜 3,1 𝑝 " 2 𝑜 0,0 1 𝑜 1,0 3 𝑜 2,0 1 𝑜 3,0 0 𝑜 4,0 0 𝑜 0,1 0 𝑜 1,1 0 𝑜 2,1 3 𝑜 3,1 2 𝑜 4,1
Placing the object 𝑜 4,0 in 𝑝 " 1 corresponding to the local storage class 𝑠𝑐 1 exceeds its remaining capacity. So, we place 𝑜 0,4 in 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 . By doing the same process on the remaining objects, the outcome of this 1 𝑠𝑡 step is the list 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 " t𝑜 4,0 , 𝑜 0,1 , 𝑜 3,1 u as illustrated in Figure 8. The remaining storage capacities p𝑐𝑠𝑐 0 , 𝑐𝑠𝑐 1 , 𝑐𝑠 1 , 𝑐𝑠 2 q are respectively (6,1,6,1).

Step 2: we browse 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 in a random order for assigning (repairing) the objects to new locations. We prefer the random browsing in order not to favor one object over another. For each object, we build a list 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠 containing all the existing locations except the one the object is currently assigned to. Then, we randomly choose a new location from 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠 and check the assignment against resource and customers constraints. If it satisfies all the constraints, we accept the assignment and set the gene value accordingly. If it is not the case, we choose randomly another location from 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠, and so forth. We preferred to choose a new location randomly to repair a given solution in order to reduce the computational effort. In effect, checking all the potential location for each object and then choosing a location among those that best optimize the objective functions increases significantly the execution time.

Then, if, for a given object, we do not find any location that satisfies all the constraints, the repair process is interrupted and the initial configuration of the chromosome will be kept still, as a potential candidate for future mutation. Algorithm 2 from line 10 to line 27 corresponds to this second step.

In the previous example, during this 2 𝑛𝑑 step, we browse randomly 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 . Suppose that the first randomly returned object is 𝑜 0,1 . The potential locations for this object are 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠 " t0, 2, 3u, that is all other locations regardless of the capacity . We search randomly for a location from this list to fix 𝑜 0,1 . Let the returned location be 𝑝 " 3. This location corresponds to 𝑠𝑠 2 . It could not accommodate 𝑜 0,1 because it does not have enough capacity. So, 𝑝 " 3 will be deleted from 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠 which will contain now only t0, 2u. We repeat the process, randomly selecting a location from 𝑙𝑖𝑠𝑡𝑃𝑙𝑎𝑐𝑒𝑠. Suppose that 𝑝 " 0 is picked up next, it can accommodate 𝑜 1,1 from a capacity perspective. So, this object is repaired and will be placed in the location 𝑝 " 0. At this stage, 𝑥 " p1, 3, 1, 0, ?, 0, 0, 3, ?, 2q

We delete 𝑜 0,1 from 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 . We repeat the same process for the remaining objects in 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 . As shown in Figure 8, the 𝑥 " p1, 3, 1, 0, 0, 0, 0, 3, 2, 2q represents a possible complete repaired version.

The success rate of the repair function is the fraction of successfully repaired individuals with regard to the total number of unfeasible individuals during the evaluation. It depends on the size of the local and external storage infrastructure, the customers objects, workloads and SLAs. This success rate is related to the pressure that I/O workloads may put on the storage system. The higher the pressure, the lower the success rate as it would be hard for the repair function to meet storage constraints.

The complexity of the repair function equals to Op𝑁 ˚𝑃q where 𝑁 is the overall number of objects and 𝑃 is the number of locations. In the worst case, the assignment of each object does not respect at least one of the constraints. Thus, the 1 𝑠𝑡 step outcome 𝑙𝑖𝑠𝑡𝑇𝑜𝑅𝑒𝑝𝑎𝑖𝑟 contains all the objects which means that its size is 𝑁 . In the second step, the worst case happens when the object is affected to the last location found in the list or in case we do not find a location to fix it after 𝑃 ´1 attempts.

Algorithm 2 Repair function return the new chromosome

This repair function was integrated in the NSGAII algorithm right before the evaluation of the population individuals.

EVALUATION

In this section, we first describe the experiments setting in terms of CSPs and customers characteristics used to evaluate the effectiveness of the proposed approach. Then, we validate the efficacy of the CDP-NSGAII 𝐼𝑅 matheuristic in terms of execution time and quality of Pareto front. Furthermore, we generalize the proposed approach (injection and replication)

Manuscript submitted to ACM on another meta-heuristic. Finally, we show the flexibility of our approach which makes it possible to propose a set of trade-offs between the execution time and the quality of the obtained solution.

One may note that our study does not focus on the objective function behavior according to input parameters. The relevance of the cost models was already discussed in [START_REF] Chikhaoui | A Cost Model for Hybrid Storage Systems in a Cloud Federations[END_REF] which is not the objective of this paper. We focus rather on the ability of CDP-NSGAII 𝐼𝑅 to find a set of solutions close to the Pareto set for such objective functions. By providing an exhaustive and diverse set of precise solutions, we make sure that the CSP has a large set of good solutions from which to choose the most relevant one in his case. Choosing the most relevant solution consists in making a trade-off between the objective functions already discussed, which are the storage, latency an migration costs.

Experimental setting

We used NSGAII meta-heuristic implementation provided by MOEA framework [START_REF]MOEA Framework[END_REF]. We extended it to a matheuristic (CDP-NSGAII 𝐼𝑅 ) by integrating an injection and a repair functions. In order to compare the quality of the sets of solutions provided by different algorithms, we use the Hypervolume indicator (HV) to quantify the quality of a set of solutions. This way, we can compare the algorithms, considering that an algorithm providing a higher HV is better.

The experiments were designed based on the following scenario. A cloud federation contains a set of CSPs, each one composed of only one data-center (for simplicity). Each CSP is located in a different geographical zone. The network latency between each pair of zones is randomly assigned in an interval ]100ms, 700ms]. The considered CSP handles a set of customers, each of which having one data object (yet again for simplicity). The CSP tries to optimize the placement of its internal customers data objects in order to find a set of relevant solutions. It accommodates a hybrid storage system composed of a set of 20 HDDs and 20 SSDs having respectively the characteristics of 1TB Hitachi Deskstar 7K1000.D model HDS721010DLE630 7200 RPM HDD and 1TB Samsung 850 PRO SSD. We suppose that 30% of the customers are mobile (located in a zone that is different from their CSP's data center).

In our work, we consider that customers' SLA is related to storage performance metrics. If performance are not met, a penalty represented by a percentage of the total charge that is deducted from the customer bill (see Section 3.3). In our evaluation this penalty was set to 10% of the total charge paid by the customer.

As in [START_REF] Saeida | A self-configurable geo-replicated cloud storage system[END_REF][START_REF] Douglas B Terry | Consistencybased service level agreements for cloud storage[END_REF], we suppose that the customers requests network latency is billed to the customers. The price of the latency is given in Table 3 and its related penalty in Table 4. We used the following configuration for data centers (DC) specifications, customers' workloads, and testing parameters.

DCs specifications: The different CSPs of the federation offer heterogeneous storage services in terms of price and performance. Also, only the outgoing network cost is considered by the CSPs when migrating data objects. We suppose, as in Amazon storage service EBS io1, that the storage price is related to the capacity, performance and duration. In fact, the price of EBS io1 is set to 0.125$/GB-Month for occupation and 0.065$/IOPS-month [START_REF]Amazon EBS features[END_REF]. Also in Amazon, the network price is 0.09$GB [START_REF]Amazon Data Transfer[END_REF]. In order to attribute the CSPs of the federation different characteristics in term of storage performance and services costs, we selected values from ranges specified in Table 5 following a uniform distribution as in [START_REF] Altmann | Cost model based service placement in federated hybrid clouds[END_REF][START_REF] Rebai | Improving profit through cloud federation[END_REF][START_REF] Zhang | Moving big data to the cloud: An online cost-minimizing approach[END_REF]. In our evaluation, the Amazon EBS costs and network were set as median values of the used interval. For the Manuscript submitted to ACM This interval bounds reflect the minimum and maximum IOPS that can be supplied by Amazon's EBS disks. By doing so, the different CSPs will have different characteristics in terms of storage services costs and performance.

As in a federation, the service prices may change over time [START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF] to foster the federation, we suppose that the storage occupancy prices changes according to the occupancy rate as in [START_REF] Rebai | Improving profit through cloud federation[END_REF][START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF]. In our work, we suppose that the occupancy rate is correlated to the period of time during the day as the generated load has a daily cycle with peak hours [START_REF] Nadjaran Toosi | Resource provisioning policies to increase iaas provider's profit in a federated cloud environment[END_REF]. We suppose that it follows a normal distribution (N p12, 6q ) with a mean equals to 12am and a deviation of 6 hours. Hence, each CSP sets storage prices weighted according to this distribution as in [START_REF] Rebai | Improving profit through cloud federation[END_REF].

Workloads: we experimented with the YCSB benchmark [START_REF] Cooper | Benchmarking cloud serving systems with YCSB[END_REF]. We used different configurations in terms of ratio of read, update, scan and insert requests. We varied the number of request types per customer. We also varied the number of submitted requests per hour.

Two workloads were evaluated in this study. Workload 1 with (100% read) and workload 2 which is 50% read and 50% update.

Workloads generate different I/O operations patterns which we captured using Blktrace tool [START_REF] Brunelle Alan | blktrace User Guide[END_REF]. As for the occupancy rate, the number of requests per client was weighted according to the aforementioned normal distribution. As in [START_REF] Saeida | A self-configurable geo-replicated cloud storage system[END_REF], the workload was set according the number of online customers that changes according to a normal distribution.

Coefficients of the exact method: Coefficients in Table 6 were chosen to calculate solutions with the exact method. As CPLEX cannot get optimal solutions in a reasonable time for some instances, we bounded its execution time to 60 seconds.

Testing parameters: We executed the experiments by varying the number of objects 𝑁 and the number of the locations 𝑃 that is the number of local storage classes plus the number of CSPs in the federation. These two parameters define the search space size in our work. They allow to test the scalability of the designed heuristic. For the customers workloads, we experimented using different configurations.

We evaluated CDP-NSGAII 𝐼𝑅 for small and large problem instances in term of both HV and execution time. In our evaluation, an instance is considered as small if it can be evaluated within an hour using the exact method. We compared our contribution results with the standard version of NSGAII and a multi-objective version of Particle Swarm Optimization used in [START_REF] Liu | PSO based multiobjective reliable optimization model for cloud storage[END_REF] (designated as PSO in the sequel). Finally, we evaluated the success rate of the repair function. Note that the standard NSGAII and PSO meta-heuristics are implemented with penalization technique.

Evaluation results

In this section, we will first evaluate the effectiveness of the repair function for small problem instances. Then, we will evaluate the efficiency of the proposed matheuristic (injection+repair functions) in terms of HV and execution time for large problem instances. After that, we show the results of the generalization of the proposed approach on other meta-heuristics. Finally, we evaluate the flexibility of the proposed approach by giving different trade-offs between the execution time and the HV in function of the number of solutions calculated by the exact method.

Manuscript submitted to ACM

Effectiveness of the repair function for small problem instances.

The objective of this evaluation is to investigate the effectiveness of the repair function for problems of small sizes in term of HV and execution time.

In this evaluation, we compared our approach integrating only the repair function (called CDP-NSGAII 𝑅 ) with standard NSGAII, PSO and an exhaustive enumeration method providing the exact Pareto front, in terms of both HV and execution time.

For that, we have calculated the HV and the execution time for 3 small instances of the problem that can be handled by the exact method within one hour. For these instances, we have considered only 3 CSPs in the federation, 2 local storage classes which constitutes 4 different locations to store objects. The experiment was repeated with 10, 13 and 15 objects.

The results are presented in Table 7. The exact method computes the exact Pareto front, and thus the exact hypervolume. All the other evaluated algorithms obtain more or less the same HV in a small time (less than 1 second). Therefore, contrary to the evaluated evolutionary algorithms, the exact method is unusable for large instances neither offline nor online, because of the combinatorial nature of the placement problem.

For evolutionary algorithms, NSGAII gives the exact HV but doubles the time required by CDP-NSGAII 𝑅 and PSO for a non-significant HV enhancement. PSO has the smallest execution time with a HV error that does not exceed 0.7%.

Effectiveness of injection and repair operators.

The purpose of this evaluation is to see the impact of injection and repair operators in terms of HV and execution time. For that, we compare the different versions of our approach, PSO and the set of solutions obtained by CPLEX. The different versions of our approach are: The solutions set of CPLEX is composed of 10 solutions obtained using coefficients in Table 6.

Figure 9 shows, for each algorithm, the hypervolume derivated from its resulting front according to the number of Moreover, we notice also that in the cases where NSGAII and PSO could find solutions, NSGAII meta-heuristic improves that PSO by up to 79% in term of HV.

For CDP-NSGAII 𝑅 , it has roughly the same HV as CDP-NSGAII; nevertheless, from Figure 10, we notice that CDP-NSGAII 𝑅 highly improves the execution time of NSGAII. This enhancement is between 40% and 86%. In fact, NSGAII takes more time because it must classify the individuals according to the degree of constraints violation (to penalize invalid individuals). As CDP-NSGAII 𝑅 repairs all invalid solutions, it does not perform this additional processing.

PSO takes more time than CDP-NSGAII 𝑅 as it needs twice more evaluations to obtain a comparable HV.

Moreover, from this figure, we see that the execution time of CDP-NSGAII 𝑅 increases linearly with the growth of the number of objects while the number of CSPs impacts slightly the execution time. This is due to the fact that we considered a large number of objects compared to the number of CSPs which is consistent with the theoretical complexity.

From these remarks, we notice that the injection operator has a big impact on the resulting HV while the repair operator has a great impact on the execution time. We can also observe that NSGAII meta-heuristic outperforms the PSO meta-heuristic for the implemented problem.

5.2.3

Generalization of the proposed approach on PSO meta-heuristic . The matheuristic approach proposed in this work can be generalized to other meta-heuristics. In this evaluation, we apply the repair and injection functions to NSGAII and Manuscript submitted to ACM In addition to the results of the proposed approach with NSGAII meta-heuristic, Figure 11 shows its generalization on PSO meta-heuristic. The legend symbol (-) means the standard version of the algorithm, while (R, I, IR) symbols mean that the algorithms are upgraded respectively by repair, injection and both injection and repair operators. The horizontal blue line represents the cumulative HV of CPLEX. Note that for this experiment, the solution set of CPLEX is also composed of ten solutions calculated using the coefficient combinations in Table 6.

From this figure we notice that the set of solutions calculated by CPLEX outperforms the HV of the standard versions of NSGAII and PSO respectively by 46% and 57%. CPLEX outperforms also the two meta-heuristics augmented by the repair function. It outperforms NSGAII 𝑅 by 44% and PSO 𝑅 by 51%. We observe also that both NSGAII and PSO upgraded with injection and repair functions outperform CPLEX and all the other algorithms variants. In fact, NSGAII 𝐼 𝑅 improves the HV of the CPLEX by 35% while PSO 𝐼 𝑅 enhances CPLEX by 16%.

Flexibility of the proposed approach.

In this evaluation, we show how the proposed approach allows to compromise between the quality and the execution time of the algorithm. For that, we calculate the HV and the execution time of From this figure, we noticed that the (cumulative) HV of CDP-NSGAII 𝐼𝑅 is always higher than that of CPLEX for a given execution time. The matheuristic enhances CPLEX by up to 2.2 times (for 21 injected solutions in the figure). We notice that the difference of HV is more significant for small CPLEX sets and when we increase the number of solutions calculated by CPLEX the difference of HV decreases.

More importantly, one may observe in this Figure that by drawing a horizontal line for a given CDP-NSGAII 𝐼𝑅 , let us say 21 injected solutions, CPLEX needs more than 100 solutions. In addition, with such number of solutions CPLEX execution time is around 10x more significant than CDP-NSGAII 𝐼𝑅 .

So reducing the number of solutions provided by CPLEX is a way to improve the scalability of the matheuristic approach because when the problem size increases, CPLEX takes much more time to find the required exact solutions while the execution time of the heuristic part of CDP-NSGAII 𝐼𝑅 stays unchanged. Of course, this is done at the expense of the HV and a compromise is to be achieved.

RELATED WORK

Great efforts have been made on the data object placement problem in cloud environments based on hybrid storage system.

Mono and multi objective optimization techniques and methods have been used and proposed to handle this problem Manuscript submitted to ACM

CONCLUTION

For a Cloud provider participating in a Federation, choosing a good storage location between local devices and external services provided by other CSPs is a crucial concern especially for time-varying workloads. In this paper, we modeled the problem of customers data objects placement in a cloud federation as a multi-objective optimization problem. The data placement model takes into account the different characteristics of the local storage system and the external storage services, the variable workload of customers and their SLAs.

To resolve the proposed multi-objective problem we designed CDP-NSGAII 𝐼 𝑅 matheuristic. CDP-NSGAII 𝐼 𝑅 extends NSGAII by a preprocessing step consisting in calculation of a set of exact solutions that is injected in the initial population of NSGAII. Furthermore a repair function is designed in order to fix a given placement if it is unfeasible in NSGAII populations.

The performed evaluation proved the effectiveness of the proposed matheuristic. CDP-NSGAII 𝐼 𝑅 improves the NSGAII and CPLEX hypervolume up to 94% and 60% respectively while the repair function enhances the execution time of NSGAII by 68% on average.

For future work, we plan to integrate other objectives to the placement problem such as the availability and the consistency in case of object replication. For that, we plan to propose a replication technique for the data placement in a federated cloud taking into account the cost model considered in this study.

Fig. 1 .

 1 Fig. 1. Cloud federations taxonomy Fig. 2. Pareto front Fig. 3. Hypervolume indicator

Figure 2

 2 Figure 2 illustrates a Pareto front of a MOO problem where two objective functions 𝑓 1 p𝑥q and 𝑓 2 p𝑥q are being minimized.

  Solving a MOO problem needs to go through two steps (i) finding the Pareto set, (ii) selecting a solution among the Pareto set through decision making process. In this work, we are interested in the first step. MOEAs are well-known non-deterministic population-based algorithms proposed and used to solve MOO problems.

𝐶𝑆𝑃 2 (𝑝 " 3 )Fig. 4 .

 234 Fig. 4. System architecture

  The local placement cost 𝐶𝑜𝑠𝑡 𝑙𝑐𝑙,𝑇 is the storage cost of internal customers objects in the local infrastructure. It consists of a local storage cost 𝐶𝑜𝑠𝑡 𝑙𝑠𝑡𝑔,𝑇 and a migration cost 𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇 as shown in Eq. (3). 𝐶𝑜𝑠𝑡 𝑙𝑠𝑡𝑔,𝑇 is composed of the occupation cost in terms of purchase cost and guarantee, and the I/O workload execution cost in terms of energy and wear-out. 𝐶𝑜𝑠𝑡 𝑙𝑚𝑔𝑟,𝑇 is related to the cost of local migration between storage classes within the CSP infrastructure (energy and wear-out).Outsourcing cost: This cost (𝐶𝑜𝑠𝑡 𝑜𝑢𝑡𝑠𝑟𝑐,𝑇 ) is related to the placement of internal customers objects in partner CSPs.It is composed of geo-migration cost 𝐶𝑜𝑠𝑡 𝑔𝑚𝑔𝑟,𝑇 of customers objects, and the storage cost fixed by the partner CSP 𝐶𝑜𝑠𝑡 𝑒𝑠𝑡𝑟,𝑇 (see Eq. (4)).Back-migration cost: It (𝐶𝑜𝑠𝑡 𝑏𝑚𝑔𝑟,𝑇 ) represents the cost of bringing back the previously outsourced objects to the home infrastructure. Penalty cost: 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡,𝑇 is composed of the I/O storage performance penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑖𝑜 ,𝑇 related to the violation of I/O SLA term and the network latency penalty cost 𝐶𝑜𝑠𝑡 𝑝𝑛𝑡 𝑙𝑡𝑐 ,𝑇 related to the degradation of the delivered network latency as noted in Eq. (

Fig. 5 .

 5 Fig. 5. Objective functions based cost model

Fig. 6 .

 6 Fig. 6. Federated cloud based hybrid storage system

Fig. 7 .

 7 Fig. 7. Matheuristic optimization approach

2 . 1 .

 21 The output of this step can be used as it is in the Execute phase of the MAPE-K loop. However, in our solution, the set of solutions obtained from the first step is sent to the Evolutionary step to enhance the quality of the final placement. It is injected into the initial population of NGSAII and a repair function (see Section 4.2.2) intervenes before the evaluation of each population individual. Each iteration, the termination conditions are verified, if they are not Manuscript submitted to ACM satisfied, the population are sorted according to crowded comparison operator and new population is generated based on genetic algorithm operators namely selection, crossover and mutation.

2 Fig. 8 .

 28 Fig. 8. Repair function: example

'

  CDP-NSGAII (standard version of NSGAII tailored to our problem), ' CDP-NSGAII 𝑅 (NSGAII with repair operator), ' CDP-NSGAII 𝐼 (NSGAII with injection operator), ' CDP-NSGAII 𝐼𝑅 (NSGAII with injection and repair operators) Note that we considered that the local CSP has two different storage classes. Each experiment was carried out 10 times.

Fig. 9 .

 9 Fig. 9. Hypervolume comparison

Fig. 10 .

 10 Fig. 10. Time execution evolution

  CPLEX and CDP-NSGAII 𝐼𝑅 by varying the number of solutions calculated by CPLEX and used in the injection step of the matheuristic. We varied the coefficient parameters in the range [0..1] with a step equals to 0.05 for each objective function which gives 231 different coefficient combination. We constitute 11 different solutions sets. The first one contains 21 solutions, the second one contains 42 solutions and so on until the 11th set which contains all (231) solutions. Each time, we inject a set of solutions, we calculate the HV and execution time of CDP-NSGAII 𝐼𝑅 and CPLEX.Manuscript submitted to ACM

Fig. 11 .

 11 Fig. 11. Matheuristic generalization Fig. 12. Matheuristic flexibilty

Table 1 . Notation Table Symbol Meaning

 1NotationSymbol 𝑀, 𝑍 𝑚The number of geographic zones, the zone 𝑚 𝐷 the number of clouds in the federation 𝐶𝑆𝑃 𝑑 , 𝑠𝑠 𝑑 ,𝑐𝑠𝑠 𝑑 , 𝑖𝑜 𝑑 cloud provider 𝑑, its storage service, the capacity (𝐺𝐵) of the storage service and its IOPS performance 𝐽 The number of local storage classes 𝑠𝑐 𝑗 , 𝑐𝑠𝑐 𝑗 , 𝑖𝑜 𝑗 p𝑜𝑝q The storage class 𝑗, its capacity and its IOPS per operation type 𝑜𝑝 𝑜𝑝 (𝑜𝑝 P t𝑟𝑟, 𝑟 𝑤, 𝑠𝑟, 𝑠𝑤u) where 𝑟𝑟 : random read, 𝑟 𝑤:random write, 𝑠𝑟 :sequential read, 𝑠𝑤:sequential write 𝑅, 𝑟 The number of request types, the request type 𝑟 (e.g. get, put) 𝐾 The number of customers 𝑈 , 𝑢 𝑘 , 𝑂 𝑘 The set of customers, customer 𝑘 and the set of his objects 𝑖𝑜𝐻𝑎𝑟𝑑 𝑘 ,𝑖𝑜𝑆𝑜 𝑓 𝑡 𝑘 the hard iops SLA and the soft iops SLA of customer 𝑢 𝑘 𝑖𝑜𝑂 𝑓 𝑓 𝑒𝑟𝑒𝑑 𝑘 The IOPS delivered to the customer 𝑢 𝑘 𝑜 𝑖,𝑘 ,𝑠 𝑜 𝑖,𝑘 , 𝑖𝑜 𝑜 𝑖,𝑘 p𝑜𝑝q the object 𝑖 of customer 𝑢 𝑘 , its size and its issued I/O requests per operation type 𝑃 the number of possible storage locations, 𝑃 " 𝐷 `𝐽 ´1 𝑜𝑐𝑐 𝑚,𝑟 𝑘 the number of requests of type 𝑟 issued by the customer 𝑢 𝑘 from the zon 𝑍 𝑚 𝑎𝑐𝑐 𝑟,𝑜 𝑖,𝑘 𝑘The fraction requests of type 𝑟 issued by the customer 𝑢 𝑘 and accesses the object 𝑜 𝑖,𝑘 𝑡𝑜𝑡 𝑚,𝑜 𝑖,𝑘 𝑘 the total number of requests of customer 𝑢 𝑘 issued from the zone of 𝑍 𝑚 and that access to 𝑜 𝑖,𝑘 𝑙 𝑍𝑚,𝑍𝑚1 the network latency between the zone 𝑍 and the zone 𝑍 1 .

𝑇 Period of time 𝑥 Decision variable representing a placement configuration Objective functions 𝑠𝑡𝑜𝑟𝑒 The storage cost for a given 𝑥 placement configuration 𝑚𝑖𝑔𝑟𝑎𝑡𝑒 The migration cost for a given 𝑥 placement configuration 𝑙𝑎𝑡𝑒𝑛𝑐𝑦 The latency cost for a given 𝑥 placement configuration Costs 𝐶𝑜𝑠𝑡 𝑝𝑙𝑐,𝑇

Table 2 .

 2 Network latency price and penalty per request. (𝑏 0

Table 2a .

 2a It defines intervals of network latency QoS values and the corresponding prices. [𝛽 𝑖 ,𝛽 𝑖`1 ] represents the interval of the network latency and 𝑏 𝑖 is the price to pay by the customer for the network latency corresponding to this interval. 𝑏 0

  𝑟,𝑜 𝑖,𝑘 𝑘 of this matrix indicates the fraction of requests of type 𝑟 issued by the customer 𝑢 𝑘 and that access the object 𝑜 𝑖,𝑘 . 𝑎𝑐𝑐 𝑟,𝑜 𝑖,𝑘 𝑘 P r0..1s such as for each request type 𝑟 , ř 𝑜 𝑖,𝑘 P𝑜 𝑘 𝑎𝑐𝑐 We denote the overall workload by the matrix 𝑡𝑜𝑡 𝑘 . It is the product of the matrix 𝑜𝑐𝑐 𝑘 and the matrix 𝑎𝑐𝑐 𝑘 , see Eq. (1)

			𝑟,𝑜 𝑖,𝑘 𝑘	" 1, see
	example below.
	𝑡𝑜𝑡 𝑘 " 𝑜𝑐𝑐 𝑘 ˚𝑎𝑐𝑐 𝑘	(1)
	So, each element 𝑡𝑜𝑡
		𝑔𝑒𝑡 𝑢𝑝𝑑𝑎𝑡𝑒
		˜Z
	𝑜𝑐𝑐 0 "	0 5500	1000
		𝑍 1 2000	100

𝑚,𝑜 𝑖,𝑘 𝑘

represents the overall number of all requests types issued by the customer 𝑢 𝑘 from the zone 𝑍 𝑚 and that access the object 𝑜 𝑖,𝑘 .

Example : Let us take the same federation configuration depicted in Figure

4

. Let customer 𝑢 0 issue 2 types of requests (get, and update). Its end-users are spread over the 2 zones. Matrix 𝑜𝑐𝑐 0 represents the number of requests issued by the users of customer 𝑢 0 from different zones.

  The standard search operators can produce any combination of values, since they do not consider specific problem constraints.

		Preprocessing step	Evolutionary step: NSGAII-IR
		𝑓1p𝑥q Ð 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒p𝑆𝑡𝑜𝑟𝑒p𝑥qq 𝑓2p𝑥qp𝑥q Ð 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒p𝑀𝑖𝑔𝑟𝑎𝑡𝑒p𝑥qq	injection(CPLEX_Pareto_Set initial_population)
		𝑓3p𝑥q Ð 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒p𝐿𝑎𝑡𝑒𝑛𝑐𝑦p𝑥qq
		𝑟𝑒𝑎𝑑p𝑛q
		Sol_SetÐ H	repair population individuals
		𝑟𝑒𝑎𝑑p𝛼, 𝛽, 𝛾q		Generate new population
		𝑥 ÐCPLEX_SOLVE(𝛼 ˚𝑓1p𝑥qβ	Evaluate fitness function
	Start	˚𝑓2p𝑥q `𝛾 ˚𝑓3p𝑥q)
		Sol_SetÐ Sol_Set Y𝑥
		𝑛 Ð 𝑛 ´1		Mutation Crossover Selection
				Stop criteria satisfied ?	no
		𝑛 " 0 ?	no	Sorting based on crowded
		yes		yes	comparison operator
		CPLEX_Pareto_Set Ð Sol_Set	Pareto Set
				Manuscript submitted to ACM

  𝛾 ) // 𝛼 `𝛽`𝛾 "1 10:𝑥 Ð 𝐶𝑃𝐿𝐸𝑋 _𝑆𝑂𝐿𝑉 𝐸p𝛼 ˚𝑆𝑡𝑜𝑟𝑒 𝑁 p𝑥q `𝛽 ˚𝑀𝑖𝑔𝑟𝑎𝑡𝑒 𝑁 p𝑥q `𝛾 ˚𝐿𝑎𝑡𝑒𝑛𝑐𝑦 𝑁 p𝑥q Under

	1: function Calculate_Exact_Solutions(n)
	2:	calculate 𝑚𝑖𝑛𝑆𝑡𝑟 , 𝑚𝑖𝑛𝑀𝑔𝑟 , 𝑚𝑖𝑛𝐿𝑡𝑐
	3:	calculate 𝑚𝑎𝑥𝑆𝑡𝑟 , 𝑚𝑎𝑥𝑀𝑔𝑟 , 𝑚𝑎𝑥𝐿𝑡𝑐
	4:	population ÐH
	5:	𝑆𝑡𝑜𝑟𝑒 𝑁 p𝑥q Ð	𝑆𝑡𝑜𝑟𝑒p𝑥 q´minp𝑆𝑡𝑜𝑟 𝑒p𝑥 qq maxp𝑆𝑡𝑜𝑟𝑒p𝑥 qq´minp𝑆𝑡𝑜𝑟 𝑒p𝑥 qq
	6:	𝑀𝑖𝑔𝑟𝑎𝑡𝑒 𝑁 p𝑥q Ð	𝑀𝑖𝑔𝑟𝑎𝑡𝑒p𝑥 q´minp𝑀𝑖𝑔𝑟 𝑎𝑡𝑒p𝑥 qq maxp𝑀𝑖𝑔𝑟𝑎𝑡𝑒p𝑥 qq´minp𝑀𝑖𝑔𝑟 𝑎𝑡𝑒p𝑥 qq
	7:	𝐿𝑎𝑡𝑒𝑛𝑐𝑦 𝑁 p𝑥q Ð	𝐿𝑎𝑡𝑒𝑛𝑐𝑦p𝑥 q´minp𝐿𝑎𝑡𝑒𝑛𝑐 𝑦p𝑥 qq maxp𝐿𝑎𝑡𝑒𝑛𝑐𝑦p𝑥 qq´minp𝐿𝑎𝑡𝑒𝑛𝑐 𝑦p𝑥 qq
	8:	for 𝑖Ð1 to 𝑛 do
	9:	read(𝛼,𝛽, all constraints)
	11:	population Ð population Y x
	12:	end for
	13:	return (population)

Table 3 .

 3 Latency price/req.

	Latency (ms)	Price by request ($)
	ă 100	0.00001
	ă 300	0.000008
	ą 300	0

Table 4 .

 4 Penalty/req.

	Latency (ms)	Penalty ($)
	ă 200	0
	ă 300	0.000002
	ą 300	0.00001

Table 5 .

 5 Storage prices and performance

		Minimum value	Maximum value
	Occupancy cost	0.025 $	0.225 $
	IOPS cost	0.055 $	0.075 $
	Network cost	0.08 $	0.1 $

Table 6 .

 6 Exact method coeffecient values

	𝛼 1 0 0 0.5 0.5	0	0.6 0.2 0.2 0.4
	𝛽 0 1 0 0.5	0	0.5 0.2 0.6 0.2 0.3
	𝛾 0 0 1	0	0.5 0.5 0.2 0.2 0.6 0.3
	storage performance, the maximum IOPS value which can be provided by each CSP was set randomly in [250, 64 000].

Table 7 .

 7 HV and execution time for small instancesAs one can see in Table7, the execution time of the exact method suffers an exponential growth. It takes about 48 minutes for only 15 objects and 4 locations. So, by extrapolation, it would take about 8 years for evaluating a problem with only 5 locations and 20 objects giving 5 20 possible solutions.

	Objects		10		13		15
	Algorithms	HV	Time (s)	HV	Time (s)	HV	Time (s)
	Exact Method	0.269	2.4	0.311	154	0.131	2886
	CDP-NSGAII 𝑅 0.269	0.3	0.310	0.3	0.129	0.3
	NSGAII	0.269	0.8	0.311	0.6	0.131	0.6
	PSO	0.269	0.2	0.310	0.3	0.130	0.2

  objects, number of CSPs and the workload type. From this figure, we notice that CDP-NSGAII 𝐼𝑅 and CDP-NSGAII 𝐼 give always the best results in term of HV. CDP-NSGAII 𝐼𝑅 improves the HV of CPLEX by 15% to 60% and NSGAII

Manuscript submitted to ACM

Manuscript submitted to ACM

generally classified to be NP-Hard. This section discusses state-of-the-art studies related to our contribution. We can classify them following six criteria related to our work which are: the storage cost, the storage performance, the SLA, the network latency, the federation environment and finally the MOO as shown in In centralized clouds, state-of-the-art studies mixed various types of storage devices and structures in order to find a trade-off between cost and performance within one storage infrastructure. These studies have considered the optimization of one or more factors related to the storage system as the storage and workload cost [START_REF] Boukhelef | Optimizing the cost of DBaaS object placement in hybrid storage systems[END_REF][START_REF] Kim | HybridStore: A cost-efficient, high-performance storage system combining SSDs and HDDs[END_REF][START_REF] Pirahandeh | EGE: A New Energy-Aware GPU Based Erasure Coding Scheduler for Cloud Storage Systems[END_REF][START_REF] Shu Yin | DuoFS: A Hybrid Storage System Balancing Energy-Efficiency, Reliability, and Performance[END_REF][START_REF] Zhang | Towards cost-effective storage provisioning for DBMSs[END_REF] consumption and the I/O response time. Some of them have also considered the storage SLA [START_REF] Boukhelef | Optimizing the cost of DBaaS object placement in hybrid storage systems[END_REF][START_REF] Zhang | Towards cost-effective storage provisioning for DBMSs[END_REF]. Other studies have addressed the multi-objective optimization in centralized clouds based hybrid storage system as [START_REF] Kakoulli | OctopusFS: A distributed file system with tiered storage management[END_REF][START_REF] Roukh | Eco-physic: Eco-physical design initiative for very large databases[END_REF][START_REF] Wu | GA Based Placement Optimization for Hybrid Distributed Storage[END_REF].

Regarding distributed clouds, several studies have been proposed [START_REF] Guo | Multi-objective optimization for data placement strategy in cloud computing[END_REF][START_REF] Li | Dynamic multi-objective optimized replica placement and migration strategies for SaaS applications in edge cloud[END_REF][START_REF] Liu | PSO based multiobjective reliable optimization model for cloud storage[END_REF][START_REF] Mansouri | Cost optimization for dynamic replication and migration of data in cloud data centers[END_REF][START_REF] López | Multi-objective virtual machine placement with service level agreement: A memetic algorithm approach[END_REF][START_REF] Wang | Optimizing data placement for cost effective and high available multi-cloud storage[END_REF][START_REF] Wen | Cost effective, reliable and secure workflow deployment over federated clouds[END_REF][START_REF] Zhang | Moving big data to the cloud: An online cost-minimizing approach[END_REF][START_REF] Zhang | An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in Clouds[END_REF]. They considered different applications such as bigdata analysis, workflow optimization and geo-replication, etc. The placement problem in these studies have considered the diversity of storage and network services prices offered by the federated clouds. Some of them have used multi-objective optimization [START_REF] Guo | Multi-objective optimization for data placement strategy in cloud computing[END_REF][START_REF] Li | Dynamic multi-objective optimized replica placement and migration strategies for SaaS applications in edge cloud[END_REF][START_REF] Liu | PSO based multiobjective reliable optimization model for cloud storage[END_REF][START_REF] López | Multi-objective virtual machine placement with service level agreement: A memetic algorithm approach[END_REF][START_REF] Zhang | An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in Clouds[END_REF].The placement problem in these works have been modeled under different objective functions and constraints according to the faced issues. However, generally the storage cost was only related to the capacity (Price/GB) and only [START_REF] Mansouri | Cost optimization for dynamic replication and migration of data in cloud data centers[END_REF] have considered the workload at a high level. Also, the storage services characteristics have been rarely considered and to the best of our knowledge the storage services SLA have not been taken into account in distributed clouds.

In one hand, the placement techniques in centralized clouds are generally based on the storage system characteristics and architecture, the workloads I/O patterns and the storage SLA requirements. However, these strategies cannot be used directly in distributed clouds due to the absence of the network factor and the difference in managing federated Clouds.

Concerning the placement techniques in distributed clouds, the storage cost was only related to the capacity (Price/GB) and only [START_REF] Mansouri | Cost optimization for dynamic replication and migration of data in cloud data centers[END_REF] have considered the workload at a high level. Also, the storage services characteristics have been rarely considered and to the best of our knowledge the storage services SLA have not been taken into account in distributed clouds.

As one can see in Table 8, several costs related to storage systems were not considered in Distributed Cloud studies while Federation properties, network and SLA were generally not considered in Centralized work. We try to fill this gap through the study presented in this paper. Even if the storage issues are not the sole problems of a CSP, strategies such as the one presented in this paper may be used as is or be inserted in an encompassing optimization systems that may take more parameters into account These parameters could be technical (e.g. CPU occupation), or not (e.g. legal, trust issues)

Manuscript submitted to ACM