Luke Bertot
email: lbertot@unistra.fr

Stéphane Genaud
email: genaud@unistra.fr

Julien Gossa
email: gossa@unistra.fr

An Overview of Cloud Simulation Enhancement using the Monte-Carlo Method

Keywords: cloud computing, computer simulation, monte carlo methods

In the cloud computing model, cloud providers invoice clients for resource consumption. Hence, tools helping the client to budget the cost of running their application are of pre-eminent importance. However, the opaque and multi-tenant nature of clouds, make job runtimes both variable and hard to predict. In this paper, we propose an improved simulation framework that takes into account this variability using the Monte-Carlo method.

We consider the execution of batch jobs on an actual platform, scheduled using typical heuristics based on the user estimates of tasks' runtimes. We model the observed variability through simple distributions to use as inputs to the Monte-Carlo simulation. We show that, our method can capture over 90% of the empirical observations of total execution times.

I. INTRODUCTION.

A. Simulation

Because they allow one to experiment without having to build or even use a real platform, simulations are a cornerstone of the study of distributed systems and clouds. Most cloud simulators are based on discrete event simulation (DES). Given a set of inputs a DES produces deterministic output results by computing the timeline of the events generated by the inputs. In this paper we simulate task directed acyclic graphs (DAGs), based on task runtime as input in order get the total execution time, makespan, and the execution cost.

However, when the simulated system is subject to variability, it is difficult to establish the validity of simulation results formally. Indeed, given some defined inputs, a DES outputs a single deterministic result, while a real system will output slightly different results for each repeated execution.

B. Stochastic Simulation and Monte-Carlo Method

For more comprehensive predictions in such variable environments, the simulation must be stochastic. In stochastic simulations inputs become distributions of possible runtimes, provided as random variables (RVs). The result of one such simulation is itself a distribution of the possible results.

Numerical methods have been proposed for solving stochastic DAGs [START_REF] Li | Estimating the execution time distribution for a task graph in a heterogeneous computing system[END_REF], [START_REF] Ludwig | A computational study on bounding the makespan distribution in stochastic project networks[END_REF]. However, they are computationally intensive and their core constraint, the independence of RVs, can not always be guaranteed.

On the other hand, a Monte-Carlo simulation (MCS), depicted in Figure 1 multiple realizations in a deterministic fashion. Each realization is a possible scenario obtained by drawing a runtime from each task's respective RV. Realizations are then simulated using traditional methods like DES. Eventually, given enough realizations, the distribution of the simulation results will tend towards the distribution of the equivalent stochastic simulation.

II. WORK CONTEXT

The study conducted in this paper is built upon a genuine comparison between experiments run in actual environments and experimental results obtained by simulation.

A. Real Execution Setup

Using the Schlouder [START_REF] Michon | Schlouder: A broker for iaas clouds[END_REF] cloud batch-scheduler, we carried out multiple executions of a scientific application, OMSSA [START_REF] Geer | Open mass spectrometry search algorithm[END_REF] on a private cloud. The application was scheduled 200 times favoring alternatively low runtimes (ASAP, as soon as possible) or low cost (AFAP, as full as possible). These executions were performed on an Openstack 96-core cloud.

B. Simulated Execution Setup

Using the SimGrid [START_REF] Casanova | Versatile, scalable, and accurate simulation of distributed applications and platforms[END_REF] simulation framework we built a simulator capable of simulating our cloud platform, scheduling, and executions. This simulator has been fine-tuned against the real execution traces, and is precise to the second for executions performed by Schlouder. This DES outputs the makespan, in seconds, and the cost, in BTU (billing time unit, e.g. VM×hour) for the simulated execution.

III. ENRICHED SIMULATION FRAMEWORK A. Simulation process

As depicted in Figure 1 the MCS consists in repeatedly drawing runtimes for each task, to form realizations. Each realization is then simulated independently and the resulting makespans, the total runtime of the application, are aggregated in a distribution.

B. Input Modeling

The MCS requires a runtime distribution for every task. Although more precise input distributions will always yield more precise results we aim to show that even simple models will provide sufficiently accurate simulation results. In our model, the tasks runtimes follow a uniform distribution centered on the average expected runtime for a given task t ( rt ). The relative spread of each distribution represents the expected platform variability and is called the perturbation level (P ). As such the distribution of possible runtimes for a task t, R t is expressed as :

R t = U( rt • (1 -P ), rt • (1 + P )) (1)
We computed the expected variability of our platform as being the average across all tasks of the worst-case deviation from the expected value for each task. The perturbation level given by this method is P ≈ 10% for both strategies.

IV. EVALUATION

Using this model, we ran a 500-iteration MCS for each strategy. The resulting distributions are shown in Figure 2. The makespan density graph shows the simulation result distribution as filled curves and the real observed executions as non-filled curves. On the BTU count graph, the left bar represents the empirical data, and the right bar the prediction from the simulation.

The distribution of simulated makespans covers fairly well the ranges of observed makespans, notwithstanding a slight right skew and shift of the empirical makespan distribution. Likewise the range of BTU numbers required for an execution is correct but the simulated distribution differs slightly. The divergence between the simulated and observed distribution is due to our simplified model described in section III-B. We quantify this divergence by fitting the simulated distribution to a Normal distribution, and producing confidence interval (CI). The 95%CI captures 90% of real executions in ASAP and 92% in AFAP. Using the 99%CI yields capture rates of 98% and 100% respectively.

V. CONCLUSION

In this paper, we propose a Monte-Carlo simulation extension to a discrete event simulator based on SimGrid. This extension provides stochastic predictions which are more informative than single values produced by traditional discrete event simulators. In this work we show that the variability we seek to account for can be modeled by a single parameter, called the perturbation level and applied to all task runtimes. We apply our method in a real setting, for which we have collected execution traces. In light of these empirical observations, our study shows that the proposed method could capture over 90% of the observed makespans given an appropriate perturbation level.

Fig. 1 .

 1 Fig.1. Overview of a Monte-Carlo simulation : 500 realizations are generated by drawing runtimes (rt) for each of the n tasks provided distributions (Rt); every realization is then simulated; the resulting makespan samples make up the final result M.

  Makespan and BTU count distribution for OMSSA Monte Carlo Simulation compared to reality at 10% perturbation level. Reading example: Simulating AFAP with OMSSA leads to makespans roughly ranging from 12800 s to 13400 s and BTU counts ranging from 33 to 36.

		Type/Strategy real/afap real/asap sim/afap sim/asap
			OMSSA
		0.004
		0.003
	density	0.002
		0.001
		0.000
		13000	13500	14000	14500
			makespan (s)
			OMSSA
		100
		75
	% runs	50
		25
		0
		34	36	38	40
			BTU
	Fig. 2.


Luke Bertot
email: lbertot@unistra.fr

Stéphane Genaud
email: genaud@unistra.fr

Julien Gossa
email: gossa@unistra.fr

Improving Cloud Simulation using the Monte-Carlo Method

In the cloud computing model, cloud providers invoice clients for resource consumption. Hence, tools helping the client to budget the cost of running his application are of pre-eminent importance. However, the opaque and multi-tenant nature of clouds make task runtimes variable and hard to predict, and hamper the creation of reliable simulation tools. In this paper, we propose an improved simulation framework that takes into account this variability using the Monte-Carlo method. We consider the execution of batch jobs on an actual platform, scheduled using typical heuristics based on the user estimates of task runtimes. We model the observed variability through simple random variables to use as inputs to the Monte-Carlo simulation. Based on this stochastic process, predictions are expressed as interval-based makespan and cost. We show that, our method can capture over 90% of the empirical observations of makespan while keeping the capture interval size below 5% of the average makespan.

Introduction

Over the last decade, the advancement of virtualization techniques has led to the emergence of new economic and exploitation approaches of computer resources in Infrastructure as a Service (IaaS), one form of cloud computing. In this model, all computing resources are made available on demand by third-party operators and paid based on usage. The ability to provision resources on demand is mainly used in two ways. First, it can serve for scaling purposes where new machines are brought online to face higher workloads and allows for a lower baseline cost. Second, it is useful for parallelizing tasks to achieve a shorter makespan (i.e. the time between the submission of the first task and the completion of the last task) at equal cost, this approach being often used for scientific and industrial workloads when runtime is heavily dependent on computing power. This approach is made possible by the pricing model of cloud infrastructures, as popularized by Amazon Web Services, in which payment for computing power provided as Virtual Machines (VMs), happens in increments of arbitrary lengths of time, billing time unit (BTU), usually of one hour. This model offers the client an almost complete freedom to start or stop new servers as long as it can be afforded. However, for distributed applications, it quickly becomes difficult to manually provision the resources in an efficient way. The use of a scheduler becomes unavoidable for such workloads. In this paper, we are interested in predicting the execution time and cost of such workloads, in which the scheduling plays an important role.

Independently of scheduling decisions, the accurate prediction of complex workload execution is hampered by the inherent variability of clouds, explained by multiple factors. Firstly IaaS operates in an opaque fashion: the exact nature of the underlying platforms is unknown, and their hardware are subject to evolution. Secondly cloud systems are multi-tenant by nature. This adds uncertainty due to contention on network and memory accesses. This variability, reported by a number of practitionners who evaluate parallel application performance on clouds (e.g. [START_REF] Mehrotra | Performance evaluation of amazon elastic compute cloud for NASA high-performance computing applications[END_REF], who report an average 5%-6% variability on AWS cluster compute instances), has also been measured by one of the most comprehensive and recent surveys by Leitner et al. [START_REF] Leitner | Patterns in the chaos -A study of performance variation and predictability in public iaas clouds[END_REF]. We will see in this paper that our observations fit with the figures presented in this survey. This variability increases the difficulty of modeling task execution times. In this regard, the prediction is highly dependent on the underlying simulator of the system and on the phenomena it can capture. In our work, we rely on the SimGrid [START_REF] Casanova | Versatile, scalable, and accurate simulation of distributed applications and platforms[END_REF] simulation toolkit, enabling us to build discrete event simulators of distributed systems such as Grids, Clouds, or HPC systems. SimGrid has been chosen for its well-studied accuracy against reality (e.g. [START_REF] Stanisic | Faithful performance prediction of a dynamic task-based runtime system for heterogeneous multicore architectures[END_REF][START_REF] Velho | On the validity of flow-level tcp network models for grid and cloud simulations[END_REF]). In particular, given a precise description of the hardware platform, its network model takes into account network contention in presence of multiple communication flows.

However, we may not be able to provide a fully accurate platform description, or be unable to estimate the network cross-traffic, yielding a distortion between simulation and reality. To deal with this problem, the standard approach is to consider task runtimes to be stochastic. Every task can be modeled by a random variable (RV) that models the whole spectrum of possible runtimes. These RVs are the basis required for a stochastic simulation. Such simulations output RVs of the observed phenomenon (makespan or BTU) which in turn can be used to create intervals of possible results with their assorted confidence. In this paper, we propose a stochastic method to enrich the classical prediction based on the discrete-event simulator SimGrid, and we study the conditions needed for this approach to be relevant. This study is carried out in a real setting, described in section 3, where the applications , and the scheduler are presented. The stochastic framework we propose is then presented in section 4 and is evaluated in section 5. We discuss the limits of this approach in section 6.

Related Work

Simulation. Most cloud simulators are based on discrete event simulation (DES). In discrete event simulations the simulation is a serie of events changing the state of the simulated system. For instance, events can be the start (or end) of computations or communications. The simulator will jump from one event to the next, updating the times of upcoming events to reflect the state change in the simulation. Such DES-based simulators require at least a platform specification and an application description. The available cloud DESs can be divided in two categories. In the first category are the simulators dedicated to study the clouds from the provider point-of-view, whose purpose is to help evaluating the design decisions of the datacenter. Examples of such simulators are MDCSim [START_REF] Lim | Mdcsim: A multi-tier data center simulation, platform[END_REF], which offers specific and precise models for low-level components including network (e.g InfiniBand or Gigabit ethernet), operating system kernel and disks. It also offers a model for energy consumption. However, the cloud client activity that can be modeled is restricted to web-servers, application-servers, or data-base applications. GreenCloud [START_REF] Kliazovich | Greencloud: a packet-level simulator of energy-aware cloud computing data centers[END_REF] follows the same purpose with a strong focus on energy consumption of cloud's network apparatus using a packet-level simulation for network communications (NS2). In the second category (which we focus on) are the simulators targeting the whole cloud ecosystem including client activity. In this category, CloudSim [START_REF] Calheiros | Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] is the most broadly used simulator in academic research. It offers simplified models regarding network communications, CPU, or disks. However, it is easily extensible and serves as the underlying simulation engine in a number of projects. Simgrid [START_REF] Casanova | Versatile, scalable, and accurate simulation of distributed applications and platforms[END_REF] is the other long-standing project, which when used in conjunction with the SchIaaS cloud interface provides similar functionnalities as CloudSim. Among the other related projects is iCanCloud [START_REF] Nuñez | icancloud: A flexible and scalable cloud infrastructure simulator[END_REF] proposed to address scalability issues encountered with CloudSim (written in Java) for the simulation of large use-cases. Most recently, PICS [START_REF] Kim | PICS: A public iaas cloud simulator[END_REF] has been proposed to evaluate specifically the simulation of public clouds. The configuration of the simulator uses only parameters that can be measured by the cloud client, namely inbound and outbound network bandwidths, average CPU power, VM boot times, and scale-in/scale-out policies. The data center is therefore seen as a black box, for which no detailed description of the hardware setting is required. The validation study of PICS under a variety of use-cases has nonetheless shown accurate predictions.

However, when the simulated system is subject to variability, it is difficult to establish the validity of simulation results formally. Indeed, given some defined inputs, a DES outputs a single deterministic result, while a real system will output slightly different results at each repeated execution. Hence, in practice the simulation is informally regarded as valid if its results are "close" to one or some of the real observations. Stochastic Simulation and Monte-Carlo Method. For more comprehensive predictions in such variable environments, the simulation must be stochastic. In stochastic simulations inputs become random variables (RVs) representing the distribution of possible values for the parameters. The result of one such simulation is itself an RV representing the distribution of the results.

Extensive work has been done on numerical methods for solving stochastic simulations of directed acyclic graph (DAG) [START_REF] Li | Estimating the execution time distribution for a task graph in a heterogeneous computing system[END_REF][START_REF] Ludwig | A computational study on bounding the makespan distribution in stochastic project networks[END_REF]. In a DAG model the vertices represent the tasks comprising the application, and the edges represent the dependencies between those tasks. The numerical approach presented in [START_REF] Li | Estimating the execution time distribution for a task graph in a heterogeneous computing system[END_REF][START_REF] Ludwig | A computational study on bounding the makespan distribution in stochastic project networks[END_REF] shows that, when tasks' runtimes are independent, the makespan distribution of two successive tasks is the convolution product of the tasks' probability density functions, while the makespan of two parallel tasks joining is the product of the tasks' cumulative distribution functions. This makes the numerical approach computationally intensive and its core constraint, the tasks RVs independence, can not be guaranteed in all cases. Moreover this DAG-based approach implies fixed scheduling, since the scheduling creates implicit dependencies between tasks scheduled one after another. In a cloud context where resources can be provisioned on the fly, dynamic scheduling is much more common.

Instead of numerically computing the resulting RV, a Monte-Carlo simulation (MCS) samples the possible results by testing multiple realizations in a deterministic fashion. A realization is obtained by drawing a runtime that follows their task's respective RV for every task in the application. This allows one to simulate each realization using traditional methods like DES. Eventually, given enough realizations, the distribution of the simulation results will tend towards the distribution of the equivalent stochastic simulation. Statistical fitting techniques can then be used to characterize this makespan RV. MCS's permits non-independent RV and dynamic scheduling. This approach was first suggested in [START_REF] Van Slyke | Monte carlo methods and the pert problem[END_REF] for stochastic PERT graphs. Later, in the context of grids, where the number of resources is fixed during one execution, Tang et al. [START_REF] Tang | A stochastic scheduling algorithm for precedence constrained tasks on grid[END_REF] proposed, a modification of the well-known scheduling heuristic HEFT to compute a schedule yielding the shortest makespan given randomly variable task durations. Canon and Jeannot [START_REF] Canon | Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments[END_REF] have used MCS to evaluate the robustness of DAG schedules when task durations vary, and similarly, Zheng et al. [START_REF] Zheng | Stochastic DAG scheduling using a monte carlo approach[END_REF] evaluated the impact of this variability on the makespan. More recently, ElasticSim [START_REF] Cai | Elasticsim: A toolkit for simulating workflows with cloud resource runtime auto-scaling and stochastic task execution times[END_REF] has been proposed as a simulator extending Cloudsim to integrate resource auto-scaling and stochastic task durations. Similarly to our work, ElasticSim computes a schedule whose objective is to minimize rental cost while meeting deadline constraints. For several generated workflows, the study compares the simulation results regarding rental cost and makespan, when varying the variability of task duration and deadline with arbitrary values. By contrast, our work focuses on how the MCS method, under some given variability assumptions, captures actual observations.

Work Context

The study conducted in this paper is built upon a real comparison between experiments run in actual environments and experimental results obtained by simulation. To strengthen the validity of the comparison, the experimental conditions for the real setup and the simulation should share as many commonalities as possible, as advocated in [START_REF] Pucher | Using trustworthy simulation to engineer cloud schedulers[END_REF]. Our experimental setup described hereafter consists of two test applications which, on one hand, are run on a real platform with our scheduler Schlouder, and on the other hand are simulated with our simulator SimSchlouder based on SimGrid.

Test Applications We carried out multiple executions of two broadly used scientific applications to evaluate Schlouder performance. The execution traces for those runs were collected in an archive. This backlog of real executions is the benchmark against which our simulation performance will be evaluated. Those applications are:

-Montage [START_REF] Jacob | Montage: a grid portal and software toolkit for science-grade astronomical image mosaicking[END_REF], the Montage Astronomical Image Mosaic Engine, is designed to splice astronomical images. This application is a data intensive fork-join type workflow with a communication-to-computation ratio greater than 90%.

-OMSSA [START_REF] Geer | Open mass spectrometry search algorithm[END_REF], the Open Mass-Spectrometry Search Algorithm, is used to analyze mass-spectrometer results. The application is a computation intensive set of independent parallel tasks with a communication-to-computation ratio lower than 20%.

Real Execution Setup Schlouder [START_REF] Michon | Schlouder: A broker for iaas clouds[END_REF] is a client-side cloud broker for IaaS capable of executing the user's batch jobs, sets of independent tasks and workflows alike. The broker's main role is to schedule the tasks onto a set of cloud resources, which the broker can scale up or down. Technically, the broker connects to the cloud management system (for instance, OpenStack) to instruct how the infrastructure should be provisioned. It then assigns the tasks to the resources using the Slurm job management system. As in most batch scheduler systems, the task description includes its runtime estimation by the user called user estimate. In case of a workflow, the task dependencies are also provided. Schlouder uses just-in-time scheduling where tasks are assigned to VMs as soon as all their dependencies are satisfied. A task's real runtime, called effective runtime, usually differs from estimated runtimes, but this does not change previous scheduling decisions. The schedulig problem in IaaS clouds is a bi-ojective optimization problem, taking into account the rental cost of resources and the execution makespan. Schlouder's requests users to choose a strategy that favors one objective or the other. The scheduling and provisioning decisions are then controlled accordingly by specific heuristics. In this paper, we used the two following heuristics:

- effective runtime of each task, that are used by the simulator to compute the tasks' end dates. Together, they allow the simulation to be accurately representative of reality.

Proposal: an Enriched Simulation Framework

To address the limited trustworthiness of DES in variable environments such as clouds, we propose a framework implementing the Monte-Carlo method using SimSchlouder as simulation engine. This solution combines the extensive results provided by stochastic simulations with correctness of scheduling and provisioning provided by SimSchlouder.

Simulation Process.

The whole extended simulation process is referred to as MCS. For an application composed of n tasks (as depicted Fig. 1), MCS consists in applying successive MCS-iterations. Assuming we can provide a runtime distribution T j for every task j, a MCS-iteration k consists in :

drawing a runtime value, t j , for each task from the associated RV, T j ; proceed to a simulation using all runtimes t j to obtain a makespan m k .

With enough makespans m k , we can compute a statistical distribution of the makespan as a final RV noted M . We extend our simulation to two output variables: we will not only observe the makespan computed at every iteration but also the cost for each execution in number of BTU.

Real Observations

Using Schlouder (cf. Section 3), we performed numerous executions of the application of OMSSA and Montage. These executions were performed on a 96 cores Openstack cloud system set up on 4 identical dual 2.67GHz Intel Xeon X5650 servers. We used the KVM hypervisor and Openstack version 2012.1 and 2014.4. The traces obtained from these experiments contain several useful metrics including, but not limited to, the VM start dates, boot time, shutdown times, and assigned tasks, as well as the task start date and effective runtimes. They were initially used all along the development of Schlouder and then to properly tune SimSchlouder in order to make the simulation as accurate as possible. As a result, for the execution used in this paper, simulations done with SimSchlouder are precise to the second on the makespan and systematically exact on the BTU count. Regarding variability, we find our platform variability to stand between 3% and 6% using the metrics described in the study [START_REF] Leitner | Patterns in the chaos -A study of performance variation and predictability in public iaas clouds[END_REF] based on relative standard deviation of tasks runtimes. This variability is within the range reported in the study for platforms like Amazon's EC2 or Google Cloud Engine, with the exception of shared CPU instances. In this paper these execution traces are used to generate our MCS input RVs using the method we will describe in Section 4.3 and we compare the makespan and BTU distributions of the MCS to the distribution observed in the corresponding traces. For this purpose, traces from comparable runs are grouped by application and heuristic. Fig. 2 presents the distribution of resulting makespans and BTU counts. For OMSSA, ASAP yields a makespan variation in the range [12811s;13488s] (variability ≈5%) with a constant BTU count of 40, and AFAP yields [13564s;14172s] (4%) with a BTU count ranging [33;36]. For Montage, the makespans are in the range [1478s;1554s] (≈ 4%) with 10 BTUs for ASAP and [2833s;2837s] (0.1%) with 1 BTU for AFAP.

Input Modeling

Using a MCS we can account for this variability and provide the user with a range of possible makespans. The MCS requires a runtime RV for every task in the application. These RVs form the input model. Although precise models will yield more exact results, creating such models would not be possible in more common use-cases where a backlog of real observations is not available. In this section we propose a simple model to represent the variability of the whole system using a single factor parameter to create a small range around every estimated runtime. We test this model against our backlog of real runs. The key finding detailed hereafter is that this simple model can be precise enough for the MCS to predict over 90% of real runs.

This model for the runtimes RV uses a single expected runtime per task and a global perturbation level for all tasks. This model uses uniform distributions (U). These RVs are centered on the expected runtime of the task they represent. The relative spread of these distributions is defined by the perturbation level P , which is the same for every task. If we assume P can summarize the variability of the whole system, a central question is how should P and the expected runtimes be chosen to assess the validity of the MCS. To this end, we assume a good guess for an expected runtime is the average of all effective runtimes, rj for a given task j. As such the runtime distribution's RV T j for task j is:

T j = U[ rj × (1 -P ), rj × (1 + P )] (1)
Since the global perturbation level P establishes the limit for the worst deviations from the estimated runtimes, the relative standard deviation metric used in [START_REF] Leitner | Patterns in the chaos -A study of performance variation and predictability in public iaas clouds[END_REF] is not well suited. Instead we choose to build P using the average of the worst observed deviation for every task in the application. With r n j the nth runtime observation for task j, P is set to :

P = mean j max n |r n j -rj | rj (2)
For OMSSA, the perturbation level given by this model is P ≈ 10% for both heuristics. For Montage our calculated perturbation level is P ≈ 20% for ASAP and P ≈ 5% for AFAP. Using a similar metric, [START_REF] Kim | PICS: A public iaas cloud simulator[END_REF] also observed most deviations to be within 10% of the average runtime when working on Amazon EC2 instances with dedicated CPUs.

Simulation execution. The execution of an MCS is implemented through a series of scripts created to automate large numbers of simulations. The simulation driver first passes an application template, including dependencies and task expected runtimes, to a generator script. The generator creates the necessary number of simulation input files, with task runtimes randomised following the input model. The driver script can then execute an instance of SimSchlouder for every input file, sequentially or concurrently. Once all the instances of Sim-Schlouder have been executed, the result are aggregated in the MCS output file. This process is supple enough to accommodate other simulator and models as long as the user can provide a command to generate input files and another to parse simulation outputs.

Evaluation

We ran a 500-iteration MCS for every heuristic × application group using the task model described in the previous section. The resulting distributions are shown in Fig. 3. The makespan density graphs show the simulation result distribution as filled curves. The real observed executions, as in Fig. 2 non-filled curves. On the BTU count graphs, the left bar represents the empirical data, and the right bar the results from the simulation. These graphs show the simulation results cover the same ranges as the real observation, but do not present the same distribution within those ranges. We quantify our simulation results correctness using statistical confidence intervals. Since the makespan is in essence the sum of the tasks' runtimes in the execution critical path and tasks are all distributed using the uniform distribution which has a finite variance, we consider the Central Limit Theorem applicable. Fitting to a normal distribution gives us an average makespan µ, and a standard deviation σ. These can be used to build confidence intervals (CIs). For the normal distribution the 95% CI, defined as [µ -2σ, µ + 2σ] and the 99% CI, [µ -3σ, µ + 3σ]. The capture rate expresses the number of observed real makespans that fall within a given CI relative to the total number of real observations. Table 1 presents the capture rate obtained by each interval computed after normal fitting. Additionally we provide for each interval its size relative to the average makespan. Regarding OMSSA, the MCS captures at least 90% of real observed makespans. The divergence between the capture rate and the CI expected capture rate is due to the fact that the empirical makespan distribution does not follow a perfect normal distribution. Using a 99% CI improves the capture rate up to 98%, hence very close to the theoretical expectation. Regarding Montage the MCS achieves a capture rate of 100% for any CI.

Our MCS and a simple task model can capture 90% of reality all the while producing makespan intervals of limited size, a 3% relative size representing 7 minutes on a 3h 45m long makespan. We consider this result a satisfactory tradeoff between the simplicity of the input model and the accuracy with regards to the theoretical CI.

Perspectives

Outside of the realm of reproduction or predictions, we believe that MCS can have other more research oriented applications. In this section we will illustrate one such application. Then we will discuss limitations we have encountered in our work with MCS.

High perturbation simulations. We have so far set the perturbation level to a value that was relevant to the real system observed (see Section 4.3). A subsequent question is how does the prediction change when increasing this perturbation level. In this section we will focus on simulation of makespans using the ASAP heuristic. Fig. 4 presents the 95% CIs obtained through the normal distribution fitting of simulations with both P = 10% and P = 40%. Notice that a 40% perturbation level may be experienced in current cloud provider offers when renting shared instances ( [START_REF] Leitner | Patterns in the chaos -A study of performance variation and predictability in public iaas clouds[END_REF]). On the makespan interval graphs (first and third subfigures from left to right) the boxes represent the span of the CI interval. The mean simulated makespan (µ) is represented by the vertical bar inside the interval. The middle row shows the interval of real observed makespans. Simulation of OMSSA using P = 40% exhibits a clear drift upward of the ranges of simulated makespans and BTU. This drift is significant compared to the growth of the capture interval to the point that the capture rate of the simulation with P = 40% is of only 83% when the P = 10% simulation had a 90% capture rate. Montage simulations exhibit the upwards drift but not to the extent that it affects the simulation's capture rate. These results have two interesting implications. Firstly, the perturbation level can not be used as a trade-off variable to augment capture rate at the expense of CI compactness. The lower capture rate at P = 40% is a strong indication that our real platform exhibits a variability closer to 10% than to 40%. Misestimation of the perturbation level will have the same implication for the MCS as a wrong effective runtime given to DES. Users for whom higher capture rates are more important than interval compactness should use statistical methods to build higher rate CIs, like the 99% normal distribution CI used in section 5. Secondly, this result shows that MCSs can be used to exhibit heuristic behaviours. This upwards shift of the CI shows that ASAP, an heuristic geared towards reducing the makespan regardless of cost, is not as effective when scheduling bag-of-tasks with task runtimes that might vary widely. However, the same observation on Montage shows that when scheduling workflows ASAP remains capable of low makespans. This can be explained by the scheduler's behaviour and the workflow's nature. In workflows the makespan depends only on execution of tasks in the critical path, and remains unaffected by variability of tasks outside the path. This is compounded by the just-in-time scheduling used in Schlouder, later scheduling decisions take into account the tasks' deviation from their expected runtimes. This kind of analysis can be used to gain insight in the strengths and weaknesses of any heuristic, regardless of complexity.

Limitations of the enriched simulation. In this paper all the MCS presented used 500 iterations. Such an MCS requires in average 15 minutes of CPU time, and iterations can be parallelized. We determined that this was enough in the context of our simulation as additional simulations did not change the results and only marginally increased the confidence of the fitting process. The number of simulations necessary in an MCS depends on the number of input variables and the distribution of these variables. A MCS works by sampling the possible scenarios to get a distribution of possible outcomes, hence when more scenarios are possible then more samples are required. The relative quick convergence (as compared to other scientific fields where MCS is used) is explained by the relatively low number of input variables found in batch job scheduling. In our case, there are respectively 223 and 184 tasks for OMSSA and Montage. As the perturbation level influences the input variable distribution, we are currently studying its relationship with the number of required MCS-iterations.

Conclusion

Predicting the execution behaviour of complex workloads in the cloud is an important challenge. While a number of works have proposed model-driven simulators, much remains to be done for their adoption in production-grade cloud settings. As advocated by Puchert et al. [START_REF] Pucher | Using trustworthy simulation to engineer cloud schedulers[END_REF], the trust we can put in the prediction demands certainty and precision that only comes from validating simulation against empirical observation. This paper contributes to this effort in two ways. First, we propose a Monte-Carlo simulation extension to a discrete event simulator based on SimGrid. This extension provides stochastic predictions which are more informative than single values of billing cost and makespan produced by traditional discrete event simulators. The Monte-Carlo simulation must be parameterized to draw random values from relevant value spaces. In this work we show that the variability we seek to account for can be modeled by a single parameter, called perturbation level and applied to all task runtimes. Second, we apply our model in a real setting, on two different applications, for which we have collected execution traces. At the light of these empirical observations, our study shows that the proposed model could capture over 90% of the observed makespans for all combinations of application and scheduling heuristics given an appropriate perturbation level. We now aim to test our simulator on more use-cases and platforms. In particular as a number of studies on public clouds have reported variability levels similar to our platform ([2, 10]), we intend to reproduce these results on public clouds.

Fig. 1 .

 1 Fig. 1. Overview of a 500-iteration Monte-Carlo simulation.

Fig. 2 .

 2 Fig. 2. Empirical observations for makespan distributions and #BTU.

Fig. 3 .

 3 Fig. 3. Makespan and #BTU distributions for MCS compared to reality for P = 10%.

Fig. 4 .

 4 Fig.[START_REF] Stanisic | Faithful performance prediction of a dynamic task-based runtime system for heterogeneous multicore architectures[END_REF]. Makespan intervals and #BTU distributions for OMSSA and Montage at different perturbation levels. In the makespan interval graph the boxes represent the 95% CI resulting from the normal fit of the MCS's results, and the bar the results of a single unperturbed simulation.

  ASAP (as soon as possible) schedules each task onto an idle VM if one is available, or provisions a new VM otherwise. This heuristic minimizes the makespan.-AFAP (as full as possible) schedules each task onto one VM if it does not increase the rental cost (i.e. the number of BTU), or provisions a new VM otherwise. This heuristic minimizes cost by minimizing the BTU count.Simulated Execution Setup.As a follow-up to our work on Schlouder we developed SimSchlouder, a simulator mimicking the behaviour of Schlouder. It has the same interfaces and implements the same scheduling heuristics as Schlouder.It uses SimGrid as its core simulation engine. In practice, SimSchlouder is included as a plugin into Schlouder to allow the user to request an estimate of the makespan and cost before choosing an heuristic for a real run. SimSchlouder shares with Schlouder a common subset of inputs, including the same tasks description and heuristic. Whereas Schlouder operates on a real cloud controller, SimSchlouder provisions simulated VMs through SimGrid's cloud interface called SchIaaS. Additionally SimSchlouder requires a platform specification, which describe the physical nature of the cloud as well as the management rules, and the

	Task RVs	Realizations {t 1 , . . . , t n } 1	Sim	Samples m 1	Makespan RV
	{T 1 , . . . , T n }	. . .	. . .	. . .	M
		{t 1 , . . . , t n } 500	Sim	m 500
	realization		distribution
	draw			aggregation

Table 1 .

 1 Makespan and BTU capture rate depending on CI for P=10%.

	Application Heuristic Makespan (Size of CI) BTU
			CI 95%	CI 99%
	OMSSA	ASAP AFAP	90% (3%) 98% (5%) 100% 92% (4%) 100% (6%) 100%
	Montage	ASAP AFAP	100% (2%) 100% (4%) 100% 100% (1%) 100% (2%) 100%


Eveline Kaboré
email: eveline.kabore@enst-bretagne.fr

Antoine Beugnard
email: antoine.beugnard@enst-bretagne.fr

Implementing data distribution variant with a metamodel, some models and a transformation

In this paper, we show how models transformations can be used to implement data distribution features in the software design process of a component. This approach is based on a single metamodel that defines data distribution abstractions and on the design of alternatives that are used to implement each data distribution variants. A model transformation is associated to the metamodel and the component metamodel we consider as the target. We show that this approach facilitates the derivation of different implementation strategies from the model of a component. We illustrate our approach through the example of a distributed communication component software that implements a centralized and two peer-to-peer variants and demonstrates the reusability of the transformation.

Introduction and motivation

Models are widely used in sciences and have become an unavoidable tool for software designers and programmers. Models were used in many development methods such as SADT, JSD, etc. They allow the description of different aspects of a system: structural, functional, behavioral, temporal, etc. Models also permit the description of the system to be developed at different stages with various levels of details.

The Unied Modelling Language (UML) is the last avatar of a standard modelling notation. The way models are produced and elaborated is mainly beyond the scope of modelling; it is mainly good-practices, know-how and methods more or less formalized. One of the last great advances in software engineering was the introduction of patterns (especially design patterns) as a semi-formalization of good (or bad) practices.

The formalization and the clarication of the process of elaborating models are the next challenges. Considering the processes of elaborating and rening models as an activity that can be described with a dedicated language is in our point of view, a revolution.

We show in this article how models, metamodels (that can be defined as model types) and models transformations can be used to automatize the design and implementation process of a distributed software component.

We are working on a specific component model dedicated to communication [START_REF] Cariou | The specification of UML collaboration as interaction component[END_REF][START_REF] Matougui | Two ways of implementing software connections among distributed components[END_REF] and the way to derive an implementation thanks to a process based on models transformations [START_REF] Cariou | An archictecture and a process for implementing distributed collaborations[END_REF][START_REF] Kabore | Conception de composants répartis par transformations de modèle[END_REF]. Many models and metamodels have been developed and a design process (figure 1) has been implemented as a set of models transformations. The first transformations that were defined introduced the general architecture of the implementation. In this paper we want to describe the way we have automated the design choice related to data placement and distribution.

We argue that if models can describe the product to develop and metamodels the abstractions and constrains that are used and reused to define models, models transformations can be used to describe the process to follow. Hence, we have analysed the different design choices that are open when implementing communication components. Among them, we isolated data placement strategies. We have then look for the abstractions required to describe data placement and elaborated a dedicated metamodel. The validation of this metamodel was made thanks to the definition of some models of data placement such as "centralized placement" "peer-to-peer Pastry placement strategy" or "peer-to-peer Chord placement strategy".

Abstract medium model

Step 1

Manager introduction

Medium deployment abstract model

Step 2 Design alternative models (distributed protocols, data structure,...)

Designer

Chooses

Step 3

Merging models In order to apply these design choices we had to define a model transformation that was compatible with or target: communication components. The transformation was hence defined using both metamodels: the communication component one and the data placement one. This choice guarantees the transformation to be reusable since applicable to all models that conforms: any communication component model or any data placement model. Finally, this approach ensures also extensibility since new data placement models -if conformingcould be added.

Centralized

The paper is organized as follows. The next section summarizes the definition and the deployment target of communication components in order to ensure a better understanding of metamodels and transformation. Section 3 presents our approach defining the implementation parts of data distribution issues as a sequence of transformations in a communication component design process. Section 4 presents some related works. We conclude the paper in section 5 with some perspectives of this work.

Communication component: medium

Definition. A medium is a special component which implements any level communication protocol or system. A medium can implement, for example, a consensus protocol, a multimedia stream broadcast or a voting system. A medium includes classical component properties such as explicit interface specification, reusability or replaceability, but a medium is not a unit of deployment. A communication component is a logical architectural entity built to be distributed. An application is the result of inter-connecting a set of components and mediums. This is particularly interesting as it would allow the separation of two concerns: local concerns described by components and communication concerns described by mediums.

Example. As an illustration, we reuse the example published in [START_REF] Cariou | An archictecture and a process for implementing distributed collaborations[END_REF] of an airline company with travel agencies located worldwide. A medium can implement the reservation system and offer services to initialize information on seats, to reserve seats and to cancel reservations. A reservation application can then be built by inter-connecting the reservation medium and components representing the company and the agencies as illustrated in figure 2 Deployment target In the previous section, we saw that, at the abstract level, the medium is represented by a single software component. The goal of the design process is to make the distribution of this abstraction possible. The single software component which represents the medium at the abstract level is split into small implementation components called role managers. Each role manager is locally associated with a local component and the medium becomes a logical unit composed of all the role managers. From a local point of view, each role manager implements the services used by its associated component. From Thus, at the deployment level the single software communication component which represents the medium at the abstract level disappears completely and the medium becomes an aggregation of distributed role managers. The data manipulated by the medium at the abstract level are distributed between role managers.

The next section presents our approach to implement data distribution features as a sequence of transformations. We note that the definition of technical details related to elements which are used to ensure data distribution and access services is out of the scope of this paper.

3 Our approach

Analysis

Identifying the source and the target of the transformation Identifying the source. Managers introduction is out of the scope (step 1 in figure 1) of this paper. Thus, in the context of this paper, the source of the transformation is a medium deployment abstract model in which: (1) a manager is associated to each role; (2) each manager implements all the service offered by the medium to its associated role; (3) each role is separate from the other elements constituting the medium. (4) the medium is defined by the aggregation of managers as illustrated in figure 3 for the reservation medium.

Identifying the target. The target of the transformation is a medium implementation model in which: (1) a manager is associated to each role; (2) each manager implements all the service offered by the medium to its associated role; (3) the entity representing the medium in the source specification is deleted; (4) the medium is defined by the aggregation of managers; (5) each data managed by the medium in the source specification is distributed between managers. The description of the target does not provide design alternatives that will be used to implement data distribution features. It just specifies the set of constraints that each final implementation model of the medium should satisfy. Both source and target descriptions are detailed in [START_REF] Cariou | contribution un processus de rification d'abstraction de communication[END_REF]. Identifying and separating design alternatives. We decompose the problem of implementing data distribution issues in three design alternatives for the moment. Others design alternatives related to data distribution such as synchronization or context adaptation aspects can be added in future works.

First design alternative: data distribution topology choice. It consists in specifying the set of managers that can participate to the distribution of each data and those that can only access to it.

Second design alternative: distributed protocol choice. It specifies the distributed protocol (Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF], ...) that will be used to implement the distribution strategy of each data.

Third design alternative: distributed protocol implementation algorithm. The last step is the choice of the algorithm that will be used to implement each distributed protocol services. As an illustration, in the case of the Chord protocol, the designer can choose the algorithm proposed by the MIT [8] or the algorithm proposed the MACEDON [START_REF] Rodriguez | Macedon: Methodology for automatically creating, evaluating, and designing overlay networks[END_REF] framework to implement the protocol.

Automation

In this section, we sketch out metamodels and transformations that we use to describe and automate the introduction of design alternatives identified in the previous section in the medium deployment abstract model.

Metamodelling We define a different metamodel for the source, the target and distributed protocols in order to ensure a better understanding of metamodels. Each metamodel is specified with to elements: a UML class diagram describing the generic structure of the concept and a set of OCL specifications describing the properties of the concept which cannot be expressed in the class diagram. In sake of brevity, we only show the generic structure of each metamodel in this paper. The full definition of all the metamodels is available in [START_REF] Kaboré | Metamodel definitions[END_REF].

Medium deployment specification metamodel. Figure 5 shows the generic structure of a medium during the deployment. A manager (</RoleName>Manager ) is associated to each role (</RoleName>). Each manager implements the interface of service offered by the medium (I<RoleName>MediumServices) to its associated role and the medium (<MediumName>Medium) is defined by the aggregation of managers. Medium implementation specification metamodel. Figure 5 shows the generic structure of a medium during the implementation. The medium class disappears completely and the medium data are distributed between managers. The gray color delimits our metamodel of a distributed data. Each distributed data is represented by two elements. The first element (DataManager ) ensures the data distribution services and the second (DataObject) element ensures the data access services. Distributed protocol metamodel. We define a distributed protocol by a set of objects called ProtocolObject (figure 6). A ProtocolObject is an object that can execute the behaviour of a distributed protocol. Each ProtocolObject is implemented by a specific algorithm (ProtocolObjectAlgorithm). The main goal of the distributed protocol metamodel consists in defining a common interface for all distributed protocols that will be used in the context of mediums. Such interfaces are proposed in [START_REF] Dabek | Towards a common api for structured peer-to-peer overlays[END_REF][START_REF] Rodriguez | Macedon: Methodology for automatically creating, evaluating, and designing overlay networks[END_REF][START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF]. The interface IProtocolObjectServices exported by the distributed protocol definition metamodel is similar to the interface defined in [START_REF] Dabek | Towards a common api for structured peer-to-peer overlays[END_REF]. This interface defines services for three main distributed application abstractions: the DHT (Distributed Hash Tables), DOLR (Decentralized Object Location and Routing) and the CAST (group anycast/multicast). The interface IProtocolObjectServices offers the following services: route (to route a message), forward (to forward a message), deliver (to deliver a message), join (to join the distributed application) and leave ( to leave the distributed protocol). A definition of a distributed protocol model which conforms to the distributed protocol metamodel consists in: (1) the description of each ProtocolObject and at least one of its implementation algorithms and (2) the implementation of each service offered by the IProtocolObjectServices. We illustrate the definition of a Chord protocol model in [START_REF] Kabor | On the benefits of using model transformations to describe components design process[END_REF].

Model transformation

Principle. The entry point of the transformation is a well defined medium deployment abstract model ( figure 3) in this paper. In the full design process of the medium, we perform a first transformation in order to transform this model into an abstract implementation model in which all the UML associations between the medium class and the medium data classes are replaced by the appropriate abstract types specified by the designer [START_REF] Kaboré | Automatisation dun processus de conception par transformations de modles[END_REF]. In the case of the reservation medium for example, the available reservation identifiers (available property in figure 3) can be represented by a list. Since we haven't discuss abstract types choice in this paper, this transformation will not be described in this section. After the introduction of abstract types, we perform five successive transformations in order to introduce data distribution topologies, distributed protocols and distributed protocol algorithms in the abstract implementation model of the medium. These transformations leads to a generic implementation model implementing the actual data distribution variant. The designer completes this generic implementation model by defining each offered service actual implementation algorithm to produce the final implementation model of the medium.

The following example describes a data distribution variant that will be used to illustrate transformations in remain of this section.

An example of data distribution variant. We will use the reservation medium to illustrate transformations in this section. We suppose that the available reservation identifiers (available property) are represented by a list. The goal is to distributed this list between managers associated to agencies (ReserverManager ) using the Chord protocol. The manager associated to the airline company (SourceManager ) can only access to the list. The Chord protocol will be implemented by the MIT algorithm. These information are defined in a medium decision model in the full implementation process in order to allow the automate the execution of transformations [START_REF] Kaboré | Automatisation dun processus de conception par transformations de modles[END_REF].

T 1 . Introducing each data distribution topology in the abstract implementation model of the medium. The input model of this step is the medium abstract implementation model obtained after abstract types introduction. We aim at introducing each data distribution topology in this model. We define a transformation based on the medium deployment and implementation metamodels and the distributed data metamodel for this purpose. This transformation leads to an abstract implementation model of the medium in which : (1) a DataManager is associated to each manager participating to each data distribution and (2) a DataObject is associated to each manager accessing to each distributed data.

Here is an informal summarize of its main operations.

Preconditions: 1.Verify if each distribution node is defined in the medium model. Actions:

for each data managed by the medium class: 1.Create and associate a generic DataManager object to each manager participating to data distribution. 2.Create and associate a generic DataAccess object to each manager using the data Postcondition:

Verify if a DataManage and/or a DataObject is associated to each manager according to the implementation variant.

As an illustration, in the example of the reservation medium, the transformation associates a ListDataManager to ReserverManager and a ListObject to both SourceManager and ReserverManager (figure 7). T 2 . Introducing distributed protocol in the abstract implementation model of the medium In this step we define another transformation based on the same metamodels as T 1 to introduce the distributed protocol that will be used to ensure each data distribution strategy in the abstract implementation model generate by T 1 . Its operations can be summarize as follows.

Preconditions: Verify if the model of each distributed protocol conforms to the distributed protocol metamodel Actions: 1. Create and associate a generic ProtocolObject to each DataManager according to the distribution variant. Postcondition: Verify if a generic ProtocolObject is associated to each DataManager according to the distribution variant.

T 3 . Introducing distributed protocol algorithms in the abstract implementation model of the medium This transformation perform the following operations in order to introduce the implementation algorithm of each distributed protocol object in the model generated by T 2 as illustrated in figure 7.

Preconditions: Verify if each distributed ProtocolObject implementation algorithm is well defined according to distributed protocol metamodel. Actions: Create and associate a generic ProtocolObjectAlgorithm to X each protocol object according to the distribution variant. Postcondition:

Verify if a generic ProtocolObjectAlgorithm is associated to each ProtocolObject according to the distribution variant.

T 4 . Generating abstract methods implementation algorithms in the abstract implementation model of the medium In this step, we define a transformation to generate a default algorithm in order to implement each abstract method contained in the abstract implementation model produced by T 3 . Here is an example of piece of code generated by this transformation in order to implement the add primitive of the list for the reservation medium example. T 5 . Configurating the medium The previous step leads to an abstract implementation model of the medium in which all the generic elements needed to provide each data distribution and access services are well defined. In this step, we define a last transformation based on the same metamodels as the previous transformation in order to instantiate and associate the appropriate value to each generic element. Four generic operations named managerConnection, man-agerDisconnection, initialization and termination are defined in [START_REF] Cariou | contribution un processus de rification d'abstraction de communication[END_REF] in order to associate a specific behaviour to a manager during its connection, disconnection, initialization and termination. The last transformation redefine these operations in order to reach its goal. Here are an informal summery of the main operations performed by the last transformation an example of generated code for the reservation medium. Transformation definitions platform. Transformations are implemented, testing and executed in Kermeta [START_REF] Muller | Weaving executability into object-oriented meta-languages[END_REF] platform. Each metamodel is implemented by two Kermeta files. The first file implements all the structural aspects of the metamodel. The second file implements all the properties of the metamodel. It is then possible to check if a specific model is conform to the metamodel in which it is defined. Each transformation is implemented by three Kermeta files. The first file implements the preconditions, the second file implements the operations and last file implements the postconditions of the transformation. A full definition of metamodels and transformations in Kermeta is available in [START_REF] Kaboré | Metamodel definitions[END_REF] 4 Related works Most methodologies are informally described. They suggest a process which, in the most formalized cases, rely on contracts [START_REF] Souza | Objects, Components and Framework with UML: The Catalysis Approach[END_REF] or mathematical refinements like the B-method [START_REF] Abrial | The B-Book, Assigning Programs to Meanings[END_REF]. B defines a language and a refinement methodology. It is an algebraic specification language that is supported by tools that help refining specification safely. Each step of the process generates proof requirement the developer has to demonstrate, either manually or automatically. Some critical systems were developed in B (in 1998 the control system of line 14 of the Parisian subway was fully developed and proved in B). Our approach is more empirical and uses the so-called "semi formal" approach. It may be easier to learn and may tackle different kind of design problems such as distribution. We do not try to prove design steps, but just to automatize them and give enough confidence in the transformations thanks to pre and post-conditions.

In a recent paper, H. Sneed [START_REF] Sneed | The drawbacks of model-driven software evolution[END_REF] criticizes the model driven approach. He argues that model-driven tools (1) magnify the mistakes made in the problem definition, (2) create an additional semantic level to be maintained, (3) distort the image of what the program is really like, (4) complicate the maintenance process by creating redundant descriptions which have to be maintained in parallel, [START_REF] Cariou | contribution un processus de rification d'abstraction de communication[END_REF] are designed for top-down development that creates well-known maintenance problems. These drawbacks are mainly associated with tools. All these criticisms have already been raised when assembly was replaced by high level programming languages. We agree tools are not mature. Our experiment shows that transformations may help make explicit the process and simplify the maintenance, if models are defined well enough.

Other experiments [START_REF] Muller | On some properties of parametrized model application[END_REF] tend to prove that model composition (hence a bottomup approach) is possible. This compositional approach looks like Aspect Oriented Modelling [START_REF] Mens | Aspect-oriented programming[END_REF]. This approach recommends to separate concerns and offers an operation of weaving that composes/weaves each concern with the functional specification. Our approach differs since the "weaving" operation we use is a transformation that is adapted to the kind of concern composed. Instead of using a universal weaving operation we propose a more flexible approach (but less re-usable) were a balance may be found between the metamodel definition of the concern and its composition operation implemented as a transformation.

Model transformations are widely used on UML models. Most of them cover a small part of the development life cycle. Some transformations are dedicated to code generation. They usually produce the skeleton (structural part) of the source code that has to be completed manually. Another current use is applying design patterns [START_REF] Sunyé | Design pattern application in UML[END_REF]. Once again, the structural part is rather well implemented1 , but the collaboration one is still research in progress.

Conclusion

This paper shows how models transformations can be used to describe the implementation process of data distribution issues in a distributed software component. To do this we have defined metamodels that capture the required concepts of data distribution. We also have realized a sequence of models transformations that weave a variant of data distribution design choice into the model of a distributed component.

The transformations describe the process of introducing actual design alternatives models in the specification of the component. The approach makes explicit the data distribution implementation process. We argue it is very interesting in the sense that it facilitates the traceability (the sequence of transformations), the reuse (applicability of transformations on many different models) and the evolution of the full process (adding more variant models).

As an illustration, we have applied our approach to implement data distribution in the context of mediums. We have described a set of transformations and metamodels that can be used to introduce distributed protocols.

But the concern of data distribution is only one step in a larger design process. We have described an approach based on the definition of a sequence of design concerns. As an example we have selected the choice of an abstract type for collection of data, the choice of distribution strategies (described in this paper) and the choice of data representation format.

Transformations are implemented, tested and executed with the Kermeta platform. The implementation of the full design process relies on 6 metamodels and 5 main transformations. Each metamodel is implemented by two Kermeta files. The first file implements all the structural aspects of the metamodel. The second file implements all the properties of the metamodel. It is then possible to check if a specific model is conformed to the metamodel in which it is defined. Each transformation is implemented by three Kermeta files. The first file implements the preconditions, the second the operations and the last file the transformation postconditions. We also provide a library containing some abstract type (list, set, bag, . . . ), distributed protocol (chord, pastry, . . . ) and data representation format models (hashtable, array, matrix, . . . ).

Transformations can be used to implement any abstract type, distributed protocol and data representation format models which conforms to our metamodels in any well defined medium initial specification model. As an illustration, we have used transformations to automatically derive various centralized and distributed implementation variants of the reservation medium presented in this paper and two other mediums: a voting medium and a message broadcast medium.

The actual generated implementation models of mediums are not fully executable in the sense that they to not provide a full executable code of distributed protocols. They just call protocol APIs to ensure that all distributed feature are well implemented. Thus, in short time, our main perspective is to build a middleware in order to allow the execution of the generate models in conjunction with existing executable distributed protocol frameworks such as MACEDON. We also aim at defining other design concerns metamodels and models to enrich our library. After that, we aim at extending transformations to define auto-adaptable mediums that embed many variants and that could change there internal deployed structures according to environment evolutions.

Fig. 1 .

 1 Fig. 1. A view of a medium full design process

Fig. 2 .

 2 Fig. 2. An example of communication component: reservation medium

Fig. 3 .

 3 Fig. 3. Structure of the reservation medium after manager introduction

Fig. 4 .

 4 Fig. 4. Generic structure of a medium at the deployment level

Fig. 5 .

 5 Fig. 5. Generic structure of a medium at the implementation level

Fig. 6 .

 6 Fig. 6. A view of the distributed protocol specification metamodel

Fig. 7 .

 7 Fig. 7. A view of the reservation medium after T1, T2 and T3

Patterns purists would say that patterns are not dedicated to be automatically applied. In the absolute, we agree, but why not consider applying patterns in well defined contexts?