A M Picard

M Ladvig

V Resseguier
email: valentin.resseguier@scalian.com

D Heitz

E Mémin

B Chapron

FP11-2020-resseguier REAL-TIME FLOW ESTIMATION FROM REDUCED ORDER MODELS AND SPARSE MEASUREMENTS

To successfully monitor and actively control hydrodynamic and aerodynamic systems (e.g. aircraft wings), it can be critical to estimate and predict the unsteady flow around them in real-time. Thus, we introduce a new algorithm to couple on-board measurements with fluid dynamics simulations and prior data in real-time without the need to rely on large computational infrastructure. This is achieved through a combination of a Proper Orthogonal Decomposition Galerkin method, stochastic closuremodel under location uncertainty -and a particle filtering scheme. Impressive numerical results have been obtained for a 3-dimensional wake flows at moderate Reynolds for up to 14 vortex shedding cycles after the learning window, using a single measurement point.

INTRODUCTION

Accurate aeroelastic and aerodynamics active control (e.g. active flutter suppression, flight stability augmentation, gust and loads alleviation) can require state observers. However, estimating -or even predicting -in real-time an unsteady turbulent flow state from sparse measurements can be challenging. Through statistical estimation techniques, sensor observations can be assimilated to flow dynamical models' predictions, but for this to be a viable strategy, some difficulties must be surmounted first. Firstly, the system must be able to resolve sufficient spatio-temporal scales for the system to be stable, and this in real-time. Though tempting, tackling this problem with purely data-driven fluid dynamics models (typ-ically learned through machine learning techniques) may not be accurate and/or robust enough. On the other hand, pure physics-based model simulations (e.g. LES, RANS) are often too slow for real-time applications and a speedup would most likely push it to miss important spatiotemporal scales. Hence, Reduced Order Models (ROM) represent a nice compromise (see e.g. [START_REF] Jeffrey P Thomas | Three-dimensional transonic aeroelasticity using proper orthogonal decomposition-based reducedorder models[END_REF] for some aeroelastic applications). In particular, the Proper Orthogonal Decomposition (POD) -Galerkin method is a model that relies on physical equations while constraining the solution to live inside a small subspace learned from data. Nevertheless, the unsteady CFD ROM state of art limits itself mostly to deterministic ROMs (often linear and/or with purely data-driven calibration) with limited prediction capabilities, especially due to the chaotic and intermittent nature of turbulence, and closure problems. The simulation-measurement coupling, known in the literature as data assimilation, can be in itself a challenging task too, but thanks to the weather forecast community, there have been many advances in the field, with promising research and many operational perspectives thriving lately. Notwithstanding, algorithms fully addressing non-linear dynamics -like fluid mechanics -are limited by the available computational power and the dynamical model's accuracy quantification. The former could easily be overcome by the use of the use of our proposed ROM, whereas the second would require a method that can combine two distinct information sources, each with its own accuracy: predictions and measurements. As this not currently possible with the ROM alone, we will rely on socalled dynamics under location uncertainty -a random fluid mechanics framework designed specifically for this purpose [START_REF] Mémin | Fluid flow dynamics under location uncertainty[END_REF][START_REF] Resseguier | Geophysical flows under location uncertainty, part II quasi-geostrophy and efficient ensemble spreading[END_REF]. This paper will be organized as follows: section 2 will recall the main aspects of POD-Galerkin ROM, section 3 will present our main contribution: a randomized version of POD-Galerkin ROM, and explain the data assimilation procedure, and finally, section 5 will showcase its potential through some of our numerical results.

POD-ROM

The goal of Reduced Order Models (ROM) is to reduce the computational cost of simulations by drastically constricting the solution's degrees of freedom. This gain is typically enabled by a combination of simulation data and modeling based on physical equations. In CFD, solutions i.e. the velocity field have as many degrees of freedom as there are grid points in the spatial domain (typically in the order of 10 6 ). Thus, to achieve such a dimensionality reduction using ROMs, velocity fields are traditionally decomposed as follows:

v(x,t) = w(x,t) Resolved by the ROM + v (x) Unresolved by the ROM , (1)
with

w(x,t) = v(x) Time averaged + n ∑ 1=1 b i (t)φ i (x) Unsteady component , (2)
with n ∈ [1, 10 2 ]. Proper orthogonal decomposition (POD) learns the time averaged v(x) and the spatial modes φ (x) through principal component analysis (PCA) applied to a set of high-resolution simulation solutions (learning period). Then, one can project the physical equations (e.g. Navier-Stokes equations) onto these spatial modes, thus providing a system of n coupled ordinary differential equations that describe the evolution of the temporal modes b i (t). Through the time integration of this low-dimensional system and from equation (2), we can predict an a priori estimation of the velocity field at any given time. Consequently, this ROM construction scheme can be seen as a midpoint between fully datadriven methods and pure physics-based model, as it takes advantage of both, the available simulation data and physical modeling in order to infer reliable predictions more efficiently.

MODEL UNCERTAINTY QUANTIFI-CATION AND DATA ASSIMILATION

Models under location uncertainty are a type of random CFD model [START_REF] Mémin | Fluid flow dynamics under location uncertainty[END_REF][START_REF] Resseguier | Geophysical flows under location uncertainty, part II quasi-geostrophy and efficient ensemble spreading[END_REF] that provides both an efficient closure (i.e. an efficient way to model the effect of the neglected dynamics degrees of freedom v ) and an efficient quantification of the error induced by this closure. Though for it to be tractable, two assumptions must be made: i) the time decorrelation of the unresolved velocity component v (see eq. ( 1)) and the stochastic transport -up to some forces F -of the resolved velocity component w. With Ito stochastic calculus notations, this reads:

Dw k Dt = ∂ t w k + w -1 2 (∇•a) T + v • ∇w k -1 2 ∇•(a∇w k ) , = F k , (3)
with

a pq = v p v q τ v , (4)
being the unresolved velocity (Eulerian) absolute diffusivity, and τ v the unresolved velocity correlation time.

In order to express that uncertainty (inherent to any closure in CFD), multiple simulations are run in parallel using the stochastic model so as to efficiently realize the most probable future states of the fluid system. Since that stochastic closure is based on physics, its robustness is proved and calibrations can be performed from available physical quantities, hence almost no tuning nor fitting is required.

[6] makes use of this formalism in a POD-Galerkin context for data analysis, but without considering the noise term v • ∇w k . Here, we do consider this noise term. As per chapter 8 of [START_REF] Resseguier | Mixing and fluid dynamics under location uncertainty[END_REF], we have implemented the POD-Galerkin of the Navier-Stokes model under location uncertainty (3), along with the corresponding technical statistical estimations based on stochastic calculus presented there. Interested readers can refer to [START_REF] Resseguier | Mixing and fluid dynamics under location uncertainty[END_REF] for more details. The ensuing low-dimensional system incorporates noise terms, thus enabling model uncertainty quantification and strengthening its forecasting capabilities to allow for more stable forecasts beyond the learning period.

MEASUREMENTS AND DATA AS-SIMILATION

The final block in our stochastic POD-ROM model's pipeline is a particle filter [START_REF] Doucet | A tutorial on particle filtering and smoothing: Fifteen years later[END_REF] to integrate the realtime measurements coming from all the different sensors. In particular, this scheme was tested with a two dimensional, two components particle image velocimetry (2D2C PIV) experimental arrangement with a linear observation model as per 6.

y = Hv + ε y , (5)
= ∑ i (Hφ i )b i + Hv + ε y , (6)
where, in order to mimic the PIV measurement process, the linear operator H incorporates a 3-dimensional spatial smoothing operation, the occlusion of the horizontal plane and its corresponding component in the velocity field. Additionally, to make the data assimilation task more challenging, the information relating to a subset of points in the grid was obscured though this operator. Indeed, estimating a vector b of n ∼ 10 components from a noisy linearly-dependent observation vector y of M PIV ∼ 10 4 ( n) components could otherwise be solved using a simple least-squares procedure. The parameters inside H and ε y are estimated using experimental data, comparing the hot wire and PIV measurements' spectrum (using a Taylor assumption). Note that the unresolved velocity v 's strong influence on the final observation model's uncertainty is taken into account through a noise term in [START_REF] Resseguier | Stochastic modelling and diffusion modes for proper orthogonal decomposition models and small-scale flow analysis[END_REF].

For the first tests presented here, we consider only synthetically generated measurements produced using the aforementioned observation model [START_REF] Resseguier | Geophysical flows under location uncertainty, part II quasi-geostrophy and efficient ensemble spreading[END_REF], as this allow us to know the exact values of the velocity field everywhere on the 3-dimensional space.

NUMERICAL RESULTS

Our data assimilation procedure has been applied to a 3-dimensional cylinder wake flows at Reynolds number 300. In wake flows, vortices are shed from the cylinder in a pseudo-periodic way. As shown by figure 1, even at this moderate Reynolds, the flow is already three-dimensional and very complex. Before our data assimilation tests, we performed direct numerical simulations (DNS) using Incompact3d, a high-order flow solver based on the discretization of the incompressible Navier-Stokes equations [START_REF] Laizet | High-order compact schemes for incompressible flows: a simple and efficient method with the quasi-spectral accuracy[END_REF]. The simulation's spatial grids correspond to state space dimensions of about 10 7 . 80 vortex shedding cycles are used for the ROM constructions (learning period). The remaining vortex shedding cycles are used to test and to build synthetic measurements.

Figures 2, 3, 4 and 5 show the Q-criterion 1 isosurfaces of the data assimilation results, with n = 2 , 4, 6 and 8 modes respectively . Here, a single spatial resolution point of the synthetic PIV data is assimilated ten times for each of the vortex shedding cycles. The observation point is outside but close to the recirculation zone. Specifi-1 Q-criterion is a classical visual tool of CFD to visualize vortices. cally, its coordinates are x = 1.31D (streamwise direction), z = 0 (spanwise direction) and y = -1.48D (orthogonal direction), where the cylinder is centered on (0, 0, -) and has a diameter D. Despite the little amount of information contained in the measurements, the ROM shows a very good predictive power even outside the learning period. The proposed observers are almost identical to the references, positively demonstrating the huge potential of our approach. Those references (top plots in figures 2, 3, 4 and 5) are the theoretical performance limits: they correspond to the case of exactly known temporal modes b i (t) in the equation [START_REF] Laizet | High-order compact schemes for incompressible flows: a simple and efficient method with the quasi-spectral accuracy[END_REF]. The differences between those theoretical optimums and the DNS reference (see figure 1) is the unresolved velocity v , this difference is restricted to small scales and 3 dimensional effects at 300. In order to better appreciate the potential of our method, figures 2, 3, 4 and 5 display predictions from a benchmark POD-ROMs -POD-Galerkin with optimally fitted eddy viscosity and additive noise. The same data assimilation algorithm is used there. Nevertheless, the benchmark method strongly differs from the reference whereas our method sticks to it.

Q-criterion iso-surfaces provide a good qualitative analysis. For a quantitative one, figures 6, 7, 8 and 9 plot the global velocity prediction normalized error from the end of the learning period until 14 vortex shedding cycles later. Again, our method performs extremely well whereas the benchmark perform extremely bad.

To generate the simulation dataset, the offline highresolution highly-optimized CFD code needs to run for several hours on a supercomputer, whereas the off-line ROM construction just takes a few hours on a laptop for the current non-parallelized MATLAB code. Meanwhile, the online ROM should allow for measurements to be assimilated on the fly (i.e. at one vortex shedding cycle every 5 seconds) on a non-parallelized Python implementation, also on a laptop computer. Consequently, a considerable speed-up should be expected for their conversion to C++ and code parallelization.

CONCLUSION

In this paper, we have presented a novel accurate yet efficient method to estimate and predict a flow velocity field globally in space from sparse measurements. Our algorithm is based on a stochastic, low-dimensional system built using the knowledge of physics equations and simulated DNS data, and enabling the coupling with realtime measurements. Comparisons with a benchmark approach have shown a remarkable improvement. With our method, a single measurement point was enough to accurately predict the unsteady velocity field in the whole 3-dimensional space.

Naturally, as a continuation to this work we will perform some tests with actual particle velocimetry (PIV) measurements. Some enhancements to address more turbulent flows are also underway. Finally, we envisage the introduction of parametric ROMs and ROM construction from noisy and/or incomplete data.

Figure 1 :

 1 Figure 1: Q-criterion -13 vortex shedding cycles after the learning period -from the 3D DNS at Reynolds 300.

Figure 2 :

 2 Figure 2: Q-criterion -13 vortex shedding cycles after the learning period -from the reference 2-dimensional representation (projection of the 3D DNS at Reynolds 300 onto the POD modes) (top), our reduced data assimilation (middle) and a reduced data assimilation benchmark (bottom).

Figure 3 :

 3 Figure 3: Q-criterion -13 vortex shedding cycles after the learning period -from the reference 4-dimensional representation (projection of the 3D DNS at Reynolds 300 onto the POD modes) (top), our reduced data assimilation (middle) and a reduced data assimilation benchmark (bottom).

Figure 4 :

 4 Figure 4: Q-criterion -13 vortex shedding cycles after the learning period -from the reference 6-dimensional representation (projection of the 3D DNS at Reynolds 300 onto the POD modes) (top), our reduced data assimilation (middle) and a reduced data assimilation benchmark (bottom).

Figure 5 :Figure 6 :

 56 Figure 5: Q-criterion -13 vortex shedding cycles after the learning period -from the reference 8-dimensional representation (projection of the 3D DNS at Reynolds 300 onto the POD modes) (top), our reduced data assimilation (middle) and a reduced data assimilation benchmark (bottom).

Figure 7 :Figure 8 :Figure 9 :

 789 Figure 7: Global velocity prediction normalized error (after the learning period) with n = 4 modes for our reduced data assimilation (dark blue) and a reduced data assimilation benchmark (light blue). The shade colors (grey and light blue) correspond to the respective estimated a posteriori standard deviations. The dashed black line at the bottom is the POD truncation error. The solid black line at the top is the error obtained by setting all temporal modes b i to 0, i.e. keeping only the time averaged velocity v.


Morgan Séguéla -Riad

Mokadem -Jean-Marc Pierson

Morgan Séguéla

Riad Mokadem

Jean-Marc Pierson

Energy and Expenditure Aware Data Replication Strategy Version 5

Keywords: Cloud, Data replication, Provider expenditure, Energy consumption, SLA violation

Energy saving is a major challenge for Information Technology (IT) companies that aim to reduce their carbon footprint while providing large scale cloud services. These companies often rely on data replication technique in order to satisfy tenant's objectives, e.g., performance, especially with the increasing volume of data distributed throughout the world. In this paper, we propose a static and multi objective data replication strategy (E2ARS) that aims to reduce both energy consumption and expenditure of the provider. E2ARS leverages on cloud heterogeneity and energy efficient technologies. We first compare different policies of our strategy, from only taking energy consumption into account to only taking expenditure into account. Unsurprisingly, the more you want to reduce the energy consumption, the less you replicate. Then, we compare E2ARS with strategies from the literature. E2ARS reduces both energy consumption and expenditure where those strategies satisfy only one of the two objectives.

Stratégie de Réplication de données qui prend en compte la consommation énergétique et la dépense Version 5

Résumé : La consommation énergétique est un défi majeur pour les sociétés d'informatique qui cherchent à réduire leurs émissions de gaz à effet de serre tout en fournissant des services cloud à large échelle. Ces sociétés s'appuient souvent sur la réplication de données pour satisfaire les objectifs des locataires, comme la performance, surtout avec une augmentation du volume de données distribuées autour du monde. Dans ce rapport, nous proposons une stratégie statique de réplication de données qui est multiobjectif (E2ARS) qui cherche à diminuer à la fois la consommation énergétique et la dépense pour le fournisseur. E2ARS s'appuie sur l'hétérogénéité dans le cloud et des technologies d'efficacité énergétique. Dans un premier temps, nous comparerons les différentes politiques de notre stratégie, d'uniquement prendre en compte la consommation énergétique à uniquement prendre en compte la dépense. Les résultats montrent qu'au plus l'utilisateur veut réduire la consommation énergétique, moins la stratégie va répliquer. Puis, nous comparons E2ARS avec des stratégies venant de la littérature. E2ARS réduit la consommation énergétique et la dépense alors que d'autres stratégies réduisent uniquement l'un ou l'autre des objectifs.

Mots-clés : Cloud, Réplication de données, Dépense du fournisseur, Consommation énergétique, Violation de SLA IRIT, Université Toulouse 3 Paul Sabatier (UT3) 118 Route de Narbonne -F-31062 TOULOUSE Cedex 9 FRANCE

Introduction

Since the spread of information technologies, data produced by humanity as a whole increased sharply. These data are accessed by people and companies, for entertainment and debates, to fuel economic and scientific productions. Data have to be accessed at anytime and from everywhere as some data are accessed a lot in a short period of time. This became more relevant during the pandemic lockdown as everyone had to stay home even for working, implying a high raise of data access for IT companies, and for entertainment providers [START_REF] Reed | Netflix Q1 Report 2020[END_REF].

One way to answer this increasing number of accesses is to replicate data. Data replication is a well studied technique for several years and contexts. It has been commonly used in traditional systems like parallel databases systems [START_REF] Valduriez | Parallel database systems: Open problems and new issues[END_REF] and more recently Cloud systems [START_REF] Buyya | Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility[END_REF] on which we are focusing in this paper. Data replication aims to satisfy different objectives, from performance and availability objectives [START_REF] Janpet | Reliable and Available Data Replication Planning for Cloud Storage[END_REF] to reducing energy consumption [START_REF] Boru | Energy-efficient data replication in cloud computing datacenters[END_REF] and, costs [START_REF] Tos | Ensuring performance and provider profit through data replication in cloud systems[END_REF] such as bandwidth network consumption. In fact, most giant IT companies like Google, Amazon and Microsoft provide cloud services for economic profit while investing in more powerful and greener components.

Elastic resource management is critical to minimize operating cost while ensuring tenant objectives [START_REF] Herbst | Elasticity in Cloud Computing: What It Is, and What It Is Not[END_REF]. In fact, the provider automatically adapts its resources as closely as possible to the tenant needs. Then, tenants only pay for what they consume. This corresponds to a specific economic model called the Pay-as-you-go model. The price to rent resources is specified in an agreement [START_REF] Serrano | SLA guarantees for cloud services[END_REF] signed by the provider and the tenant. This agreement, called the Service Level Agreement (SLA), essentially contains Service Level Objectives (SLO) that the provider has to achieve otherwise there will be penalties, mostly applied by refunding a part of the rent to the tenant. These penalties can be seen as costs for the provider amongst different kind of expenditure. [START_REF] Barroso | The Datacenter as a Computer: Designing Warehouse-Scale Machines, Third Edition[END_REF] studied ways to model costs as most of them are split into capital expense (CAPEX) and operational expense (OPEX). CAPEX includes data center and server depreciation over a certain time-frame. OPEX includes all others costs like resource costs, salaries, maintenance and so on.

Reducing the carbon footprint is becoming a more and more important objective for companies. In this context, companies communicate on this objective and Greenpeace made a report to state their evolution in terms of energy consumption and production [START_REF] Cook | Clicking Clean: Who is Winning the Race to Build a Green Internet?[END_REF]. In order to achieve this objective, several studies have been done to reduce energy consumption [START_REF] Mastelic | Cloud Computing: Survey on Energy Efficiency[END_REF] [12] [START_REF] Hamzaoui | A Survey on the Current Challenges of Energy-Efficient Cloud Resources Management[END_REF]. These studies focus on technologies like sleep state which permits putting in sleep mode some servers to reduce their energy consumption [START_REF] Wang | PowerSleep: A Smart Power-Saving Scheme With Sleep for Servers Under Response Time Constraint[END_REF], and techniques like consolidation that avoid over-provisioning and put useless resources in sleep mode for instance.

In this paper, we propose a static data replication strategy E2ARS that aims to reduce both expenditure and energy consumption of the provider while considering performance for tenants. For this aim, we introduce models to estimate energy consumption and expenditure, e.g., storage and replication. In this context, the heterogeneity of prices and components in different data centers are taken into account. Based on these models, we propose an optimization algorithm in order to reduce both energy consumption and expenditure, through a 2 steps decision process. The reduction of energy consumption is leveraged by technologies like sleep state and consolidation. Note that we consider read-only data that will not be updated.

We compared the proposed static strategy to other static and dynamic data replication strategies. Compared to static strategies, the proposed strategy E2ARS is able to significantly reduce both energy consumption and expenditure when others reduce only one side. On the other hand, despite E2ARS is a static strategy, its energy consumption and the number of violations are only slightly higher compared to dynamic strategies, depending on the workload.

The rest of this paper is organized as follows: we begin in Section II by a state of the art of data replication strategies that takes into account energy consumption and/or expenditure of the provider. Then, in Section III, we describe our data replication strategy. After that, in Section IV, we validate the proposed strategy through the analysis of experimental results. Finally, we conclude and draw some lines for future works.

State of the art

We focus on strategies that take into account the provider expenditures or its energy consumption or both. Dealing with strategies that consider economic issues, one of the first data replication strategies that take into account this issue in cloud systems is [START_REF] Li | A Novel Cost-Effective Dynamic Data Replication Strategy for Reliability in Cloud Data Centres[END_REF]. The replication is based on the failing probability of a node and a reliability requirement. This permits to reduce the storage cost by delaying the replication while holding the reliability requirement. The strategy [START_REF] Gill | A dynamic, cost-aware, optimized data replication strategy for heterogeneous cloud data centers[END_REF] uses a multi-tier cloud to reduce the operating cost while keeping a high level of performance based on heterogeneity. It supposes that there is a top-tier data center that is very effective but very expensive and low-tier data centers that are cheaper but less reliable. In the strategy proposed by [START_REF] Tos | Ensuring performance and provider profit through data replication in cloud systems[END_REF], replication is triggered by a SLO violation and is applied only if it makes profit for the provider. The profit estimation is done during the replication choice based on the provider's revenue minus the operating cost from the start of the tenant's rent. [START_REF] Liu | Popularity-aware Multi-failure Resilient and Cost-effective Replication for High Data Durability in Cloud Storage[END_REF] proposed a resilient and cost-effective data replication strategy. Their idea is to classify data based on their popularity. The servers are classified into 2 groups, primary servers and backup ones. Each data item has 2 replicas in the primary group and a third replica in the backup. Based on their popularity, replicas are compressed in the backup group or not. [START_REF] Xie | A Data Dependency and Access Threshold Based Replication Strategy for Multi-cloud Workflow Applications[END_REF] considers a workflow application model that contains information about which task needs which data. This permits to regroup data based on their dependencies, and know which data are requested too many times. If there is an overlap between the ones that are highly dependent, and the ones that are accessed a lot, they become eligible and are replicated if it reduces the cost compared to doing nothing. [START_REF] Mansouri | Dynamic replication and migration of data objects with hot-spot and cold-spot statuses across storage data centers[END_REF] proposed a strategy that considers time frames and for each time frame estimates the benefit made from a new replica or data migration compared to letting data stored in their precedent location. They also take into account a minimum number of replicas based on a latency constraint such as all data center can request data with a maximum latency under a given threshold.

The other scope of this paper is the reduction of energy consumption. The authors in [START_REF] Long | MORM: A Multi-objective Optimized Replication Management strategy for cloud storage cluster[END_REF] proposed a static Multi-Objective Replica Management. The proposed strategy tries to answer availability, service time, load balancing, energy consumption and latency issues through an evolutionary algorithm where each objective is weighted. A dynamic strategy is proposed by [START_REF] Boru | Energy-efficient data replication in cloud computing datacenters[END_REF], that aims to reduce both energy and bandwidth consumption. This strategy considers a 3-tier fat tree data center architecture with a database at each level and one across the internet. A replication is triggered when the number of data accesses is higher than a threshold and occurs only if the energy and the bandwidth consumed by the database at a lower level are lower than the ones consumed by the database at the current level. Another data replication proposed in [START_REF] Lin | EAFR: An Energy-Efficient Adaptive File Replication System in Data-Intensive Clusters[END_REF] takes into account availability and performance issues through the energy consumption prism. For this aim, it classifies both data and servers, the first based on their popularity and the second based on their power consumption. Then, hot data are replicated in hot servers (that consumes more) and cold data are replicated in cold servers. [START_REF] Xu | CADRE: Carbon-Aware Data Replication for Geo-Diverse Services[END_REF] tries to reduce providers carbon footprint by reducing energy consumption and choosing the replication placement based on the energy mix of each data center. However, most of these strategies neglect the economic costs of the resources consumed by the provider.

Authors in [START_REF] Séguéla | Comparing energy-aware vs. cost-aware data replication strategy[END_REF] state that there are very few strategies that consider both expenditure and energy consumption. Among those strategies, [START_REF] Alghamdi | Profit-based file replication in data intensive cloud data centers[END_REF] aims to reduce energy consumption in order to maximize the provider profit. The profit is estimated by the energy cost from an absence of replication minus the energy cost under this strategy. This strategy does not model all the other costs that can occur while transferring files for instance. To reduce both, [START_REF] Ebadi | An energy-aware method for data replication in the cloud environments using a Tabu search and particle swarm optimization algorithm[END_REF] considers a linear combination of energy consumption and expenditure and then use a Particle Swarm Optimization mixed with a Tabu Search Algorithm between each iteration. However, this strategy cannot let the administrator choose its policy with a clear view, and does not allow a high range of choices. The proposed strategy in this paper aims, through a static replica placement, to reduce both energy consumption and costs to store, read and replicate data.

3 Data placement strategy

Notation

Let F be a set of files stored on a set of nodes N . Each file

f i ∈ F, 1 ≤ i ≤ z has a size s(f i ).
Each node n j ∈ N, 1 ≤ j ≤ m has a storage capacity cp j . ϕ is a matrix of size (z, m) and denotes the placement of the files on the nodes: ϕ(f i , n j ) is equal to 1 if f i is on n j , and 0 otherwise. E a denotes the energy consumed to perform the action a, a ∈ A. P r b represents the price of a node action b, b ∈ B.

The sets of actions depend on the state of the node. The static state represents the node when it is up but inactive (static). The dynamic state contains actions such as reading a file from a node (read ), writing a file to a node (write), transferring data between nodes through the network (net) and storing a file on a node (storage). A contains read, write, net actions of the dynamic state and also contains the static state. B contains only the storage and net actions. t is the time the user will rent the provider's nodes, and nbRds is the number of reads the user will do. To summarize those parameters, it is possible to refer to Table 1.

In the following part, models used in our data placement strategy are described. At first, cost and energy consumption of the storage for a fixed number of seconds is detailed. Then, the writing process for each replica and the average energy consumption for a fixed number of reads are given.

Models and Objective functions

In this part, models are proposed to estimate the provider's expenditure and energy consumption used in the optimization algorithm. These models are divided into 3 kinds of events: replicating, storing, reading. The expenditure model used in the following estimations are based on the work of [START_REF] Tos | Ensuring performance and provider profit through data replication in cloud systems[END_REF]. To estimate the energy consumption, we modeled each component that is used in the data management of a server. At first, disks energy consumption is modeled based on [START_REF] Hylick | A methodology for generating disk drive energy models using performance data[END_REF] that is also used in [START_REF] Song | Minimizing Power Consumption in Video Servers by the Combined Use of Solid-State Disks and Multi-Speed Disks[END_REF] to model Solid-State Drive. Then the memory is modeled, and more precisely the Random Access Memory, based on [START_REF] Rhu | A locality-aware memory hierarchy for energyefficient GPU architectures[END_REF] which is regularly updated by technical reports of a founder like [START_REF] Micron | TN-40-07: Calculating Memory Power for DDR4 SDRAM[END_REF]. Finally, the network energy consumption is considered through the Network Interface Card for the nodes, based on [START_REF] Basmadjian | Cloud computing and its interest in saving energy: the use case of a private cloud[END_REF], and switches, from [START_REF] Vishwanath | Modeling energy consumption in high-capacity routers and switches[END_REF]. In these models, processors are only considered through their idle energy consumption. However, it is worth to say that these models are only used to build the following strategy and are not meant to precisely describe reality. Note that they can be modified or updated as it will not impact the core of the proposed strategy.

Replication

First, the impact of replicating data from their original node to the chosen node is modeled. Let N o be the set of nodes included in N which contains nodes that store the original file before the placement strategy occurs. n io represents the original node where file f i is stored. If the chosen node is the original node of the file, the energy consumption and the cost needed to replicate are equal to 0. Most of the time, the replication occurs on other nodes which implies costs for the network.

To model the energy consumption, transferring and writing energy consumption have to be considered. The writing part includes the following steps: writing the received file on the RAM, and reading the file from the RAM to write it on the Disk. Note that we do not consider RDMA in this work.

Energy:

EC replic (F, N, N o , ϕ) = z i=1 m j=1 ϕ(f i , n j ) * [E net (n io , n j , f i ) + E write (n j , f i )] (1)
Replicating a file implies costs for provider which is mostly represented by the communication cost through the network. This cost is based on the size of the file s(f i ) and the price per megabyte is represented by P r net (n io , n j ) and depends on the placement: if the files are in the same data center it will be cheaper than being in 2 different regions. The expenditure model to replicate files is considered as follow:

Cost: Cost replic (F, N, N o , ϕ) = z i=1 m j=1 ϕ(f i , n j ) * s(f i ) * P r net (n io , n j ) (2)

Storage

After writing all replicas, the impact of storing files for t seconds on nodes is modeled. We suppose here that nodes cannot be turned off if they store data, in order to retrieve requested data as quick as possible. Also, adding data to a node that already stores data does not increase its power consumption. This implies that storing a file on an empty node will consume more than placing it on a node that already store files. An empty node can be turned off and its power consumption will be equal to 0.

In the following model all files in F can be stored on all nodes in N based on ϕ which represents nodes that store files. E static (n j , t) is the static energy consumption to keep n j up for t seconds. To estimate this energy consumption we consider the summation of the static power consumption of each component multiplied by t seconds. The model is described as follows:

Energy: EC storage (F, N, t, ϕ) = m j=1 E static (n j , t) * [1 - z i=1 (1 -ϕ(f i , n j ))] (3)
On the other hand, storing files imply a cost for the provider. This cost depends on the size of the file s(f i ) and on the price P r storage (n j ) to store data on the chosen node and for t seconds. The model is considered as follows:

Cost:

Cost storage (F, N, t, ϕ) = z i=1 m j=1 ϕ(f i , n j ) * s(f i ) * P r storage (n j ) * t (4)
Where P r storage (n j ) is the storage price per second and per megabyte of n j .

IRIT/RR -2021-07-FR

Read

Finally, the energy consumption and costs linked to the number of reads is modeled.

Let N i be a set of nodes that contains f i and N i the set of nodes that do not contain this file. These sets are different for each file and are built based on ϕ(f i , n j ). In fact, N i is the set of nodes where ϕ(f i , n j ) = 1 for a specific file f i , and N i contains the rest. Each node in N i is written as n j with 1 ≤ j ≤ m i and m i being equal to the number of replicas of f i . In N i , nodes are written n j ′ with 1 ≤ j ′ ≤ m i . One last notation specific to this part is shortest(n j , n j ′ ) which is equal to 1 if the requestor node n j ′ is the closest to the storage node n j in terms of transfer time and 0 otherwise.

The energy consumption model for this event includes the energy consumption to read a file f i from the closest node n j to the node n j ′ that requested this file (E read (n j , f i )), and the energy consumed by the network to transfer this file between those nodes (E net (n j , n j ′ , f i )). The energy consumption to read the file considers the following steps: reading from the disk to write on the RAM, and then reading from the RAM to get transferred through the network.

Energy:

EC read (F, N, ϕ) = 1 z z i=1 [ m i j=1 1 m i m i j ′ =1 shortest(n j , n j ′ ) * [E net (n j , n j ′ , f i ) + E read (n j , f i )]] (5)
s.t. N i ∪ N i = N
Like the writing part, the cost is mainly based on the cost to transfer data to the node n j ′ that requested the file f i from the closest node n j that stores this file. This cost is based on the size of f i and the price to transfer this file P r net (n j , n j ′ ) per megabyte.

Cost:

Cost read (F, N, ϕ) = 1 z z i=1 [ m i j=1 1 m i m i j ′ =1 shortest(n j , n j ′ ) * s(f i ) * P r net (n j , n ′ j )] (6)
s.t. N i ∪ N i = N

Multi-Objective Function

In this last part, global models and the objective function used in the optimization algorithm are introduced. As it was detailed before, t represents the renting time of the user and nbRds is the number of reads the user will do. These parameters are hypothesis made to balance the number of replicas. In fact, the lower the number of reads and the higher the renting time, the lower the number of replicas to reduce long term energy consumption and cost.

Based on previously defined functions (3), ( 1), ( 5), the global energy consumption model is described as follows:

Energy: ECG(F, N, N 0 , t, nbRds, ϕ) = EC replic (F, N, N o , ϕ) + EC storage (F, N, t, ϕ)+ nbRds * EC read (F, N, ϕ) (7)
The following global expenditure model is based on (4), ( 2), ( 6):

Cost: IRIT ExpG(F, N, N 0 , t, nbRds, ϕ) = Cost replic (F, N, N o , ϕ) + Cost storage (F, N, t, ϕ)+ nbRds * Cost read (F, N, ϕ) (8)
Let cp j be the storage capacity of node n j , the size of all files stored on this node cannot be higher than cp j . This constraint is applied to nodes only, as it will be discussed later it does not occur if the node is considered as a representative of one data center. Based on [START_REF] Li | A Novel Cost-Effective Dynamic Data Replication Strategy for Reliability in Cloud Data Centres[END_REF], we choose to create a minimum of 2 replicas per file to assure a data availability within a year of more than 99.99%.

The following objective function is built upon 7 and 8. It searches the minimum value of both global models depending on ϕ.

               min ϕ ECG(F, N, N 0 , t, nbRds, ϕ), ExpG(F, N, N 0 , t, nbRds, ϕ) z i=1 * ϕ(f i , n j ) * s(f i ) ≤ cp j , ∀j z j=1 ϕ(f i , n j ) ≥ 3 , ∀i (9)

Energy and Expenditure Aware Strategy

We propose an Energy and Expenditure Aware Replication Strategy (E2ARS ). This static data replication strategy can be considered as an initial data placement for a dynamic data replication strategy. The optimization algorithm used in this static data replication strategy is described below.

Overview on the static data replication algorithm

We consider a transnational cloud provider, like Amazon Web Services for instance, which provides services through different regions with several data centers in each region. All data centers have different prices and parameters. Nonetheless, we suppose that all nodes can store data, and for the sake of simplicity these nodes are homogeneous inside a data center. A multiobjective optimization algorithm is used to reduce both energy consumption and expenditure. However, including all nodes in the search space would make the processing very long. As the objective function considers the reading expenditure and energy consumption for each node between all other nodes, considering a subset of nodes permits to highly reduce the time to compute this part of the objective function. In order to make the algorithm works in a decent amount of time, a two steps decision process is proposed. The first optimization algorithm chooses on which data center replicas are stored. To do so, a node is chosen to represent the data center (referred to as getRepresentatives(N) in Algorithm 1). The second optimization algorithm chooses where the data will be stored inside the chosen data center. The whole process is given in algorithm 1.

Data replication between data centers (lines 1-5)

The first step is the most important because it has to choose between highly different data centers. It has to replicate and place data where the trade-off between expenditure and energy consumption is the most balanced from the database administrators (and all the hierarchy above them) perspective. To consider both objectives, we could use one objective as a constraint and minimize the other or use a weighted objective to mix them into one. However, we choose Final Individual[tempNodesInDCList] = tempDCIndividual // replace in the subset of nodes from the current DC in Final Individual the result of FirstFitNoBottleneck 11: end for to find the Pareto front to let the administrator choose if this is more important to reduce energy consumption, reduce expenditure, or make a more balanced choice. Thus, their choice could be supported by having an idea on their future costs and energy consumption. The Improved Strength Pareto Evolutionary Algorithm, also known as SPEA2 [START_REF] Zitzler | SPEA2: Improving the strength Pareto evolutionary algorithm[END_REF] (referred to as getSPEA2Result in algorithm 1), is efficient to find this Pareto front. SPEA2 returns a group of individuals from the Pareto front that are as far as possible from each other, the administrator can then choose the policy they want to apply (referred to as chooseIndividual in algorithm 1). This algorithm works with a population of individuals that can be dominated or not by other individuals, an archive that stores mostly non-dominated individuals. SPEA2 has 6 steps: Expenditure and energy consumption models are used as objective functions in the fitness calculation. For this first optimization algorithm, we suppose that each data center can store all the data. However, we are under the constraint of creating at least 2 replicas. [START_REF] Li | A Novel Cost-Effective Dynamic Data Replication Strategy for Reliability in Cloud Data Centres[END_REF] is a data replication strategy that tries to delay as much as possible replication in order to save costs, but it considers an availability issue. It highlights the fact that having independently stored IRIT replicas increases the probability of not loosing data by node failure. Here, independently means reducing dependence of nodes where our data are stored. For instance, if 2 replicas are stored in the same data center and if there is an electrical shortage in this data center. Then, both replicas will not be available anymore. In a performance context, this will reduce a bottleneck induced by an overload of reading and replication requests.

Data placement inside chosen data centers (lines 6-10)

The second step chooses on which node a replica is stored inside each data center. Before processing this optimization algorithm, it has to gather nodes from the data center (referred to as getNodesFromDC in algorithm 1) and files that will be stored in the data center (getFileOnDC in algorithm 1). At first, we tried genetic and greedy algorithms. But, we found out that placing data on a very few nodes could highly reduce the energy consumption and there are not many things that could be done to reduce the expenditure. This kind of algorithm might not be optimal but the solution provided is enough considering the processing time. However, getting the minimum number of nodes storing data, would introduce a bottleneck in a performance context as a high amount of requests will be done on these nodes. Also, the more there is data on a node, the longer the response time would be if the workload is very high. To consider this issue, we choose to wake and store those replicas on a small proportion of nodes in the data center so that those nodes are not fully loaded. This small proportion of nodes includes nodes that store the original files if those files are planned to be replicated in this data center. Otherwise, these files will be deleted. Based on our experiments, we chose to use 6.25% of the data center nodes as it is a good trade off between performance and energy consumption. If this number of nodes cannot hold all the data, we increase this proportion by 6.25% steps.

The second optimization algorithm (Algorithm 2) takes as input, the set of files F, the set of files that will be stored in the chosen data center FilesInDC and the set of nodes in the current data center Nodes DC. This algorithm at first sort chosen files by their size and return their id from the set F. The function used in line 3 is described in the algorithm 3. It permits to find the right number of nodes based on the 6.25% policy discussed before. Algorithm 3 starts by getting the size of all data that has to be stored (line 2) and verify if there is enough space for each increment by 6.25% of the number of woken up nodes. If this is the case, it returns this number of nodes. Then we place each file with a round-robin method between each node (lines 10-18). If the node cannot store the file due to its lack of capacity, it seeks for the next node (lines 21-29). If the file is not stored after trying all nodes chosen from the algorithm 3, it stores the file on another node, outside the ones considered by the algorithm 3. In fact, it bases its estimation of the number of nodes needed on the size of all the data that has to be stored and the capacity of these chosen nodes.

Experiments

Experimental Environment

Strategies Parameters

First, we highlight the differences between three kinds of policies based on our optimization algorithm. Those policies represent a range on our objective spectrum based on the Pareto front, from only considering energy consumption (E2ARSEC ) to only considering expenditure (E2ARSEX ). We also tried a policy that is more balanced toward energy consumption and expenditure which will be considered on the following experiments (E2ARS ). To choose this balanced policy, we ordered all the proposed individuals by energy consumption, and we chose prop += 0.0625 12: until allFileFit the middle one. In following experiments, t is set at 30 days, and nbRds at 100. Then we compare our strategy with other data replication strategies proposed in the literature and control strategies. As control replication strategy, we used a strategy that places 3 replicas randomly called 3Rand. From the literature, we compare our strategy with a static replication strategy called MORM [START_REF] Long | MORM: A Multi-objective Optimized Replication Management strategy for cloud storage cluster[END_REF] that occurs before the experiment starts, with a multi-objective algorithm that considers availability, latency, load balancing, service time and energy consumption. We also compare our strategy with 2 dynamic replication strategies: (i) PEPR [START_REF] Tos | Ensuring performance and provider profit through data replication in cloud systems[END_REF] and (ii) the one proposed by Boru et al. [START_REF] Boru | Energy-efficient data replication in cloud computing datacenters[END_REF]. PEPR is a strategy that takes into account the provider profit (with an income of 0.0205$ per cloudlet) and performance. It is triggered by each violation, replicates if it is still profitable. Boru et al. considers a hierarchical topology with 3 level of databases (central, data center, rack). In this strategy, the replication is triggered by the number of reads reaching a threshold, and the replication occurs on lower level databases (data center, rack) if they consume less energy and bandwidth than the higher level databases (central, data center).

IRIT/RR -2021-07-FR

Simulation Parameters

In order to compare those strategies, we implemented them on CloudSim [START_REF] Calheiros | CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF]. This simulator has been extended by [START_REF] Tos | Ensuring performance and provider profit through data replication in cloud systems[END_REF] in order to take into account data replication while considering heterogeneous network bandwidth, and monetary cost of resources. Then, it has been extended to estimate the energy consumption [START_REF] Séguéla | Comparing energy-aware vs. cost-aware data replication strategy[END_REF]. Finally, we added the capacity for all nodes to be turned into sleep mode based on [START_REF] Wang | PowerSleep: A Smart Power-Saving Scheme With Sleep for Servers Under Response Time Constraint[END_REF] in order to reduce the energy consumption. However, we have supposed that storing data block the node from sleeping to keep access to the data it stores. This implies some differences compared to results in [START_REF] Séguéla | Comparing energy-aware vs. cost-aware data replication strategy[END_REF] in terms of energy consumption.

Networks parameters come from different sources. Bandwidth is based on [START_REF] Boru | Energy-efficient data replication in cloud computing datacenters[END_REF] and latency values are from Wikipedia1 . Pricing characteristics are coming from Google Cloud Pricing, assuming a 20% margin. The response time threshold is coming from [START_REF] Nah | A study on tolerable waiting time: how long are Web users willing to wait?[END_REF] where a 15 seconds wait without feedback implies a loss of 25% of users. This threshold corresponds to our SLO, and if the response time is higher than 15 seconds, we consider that this cloudlet violates the SLO implying a refund to the tenant. Experiment parameters are summarized in the Table 2. We consider 2 kinds of experiments. Large scale ones with 1024 files with 128 nodes per data center, and smaller scale ones with 30 files and 32 nodes per data center. Smaller scale experiments are kept as MORM needed too much memory and could not be processed for larger scale ones. Then, when the number of nodes and files is higher, we also increased the number of cloudlets from 75,000 to 150,000.

In our experiments, we have to take care of the given architecture for each data replication strategy. In fact, 3Rand, E2ARS, MORM and PEPR are considered using an architecture following a peer to peer topology. In this case, all nodes can process tasks and store data. Boru et al.'s architecture is based on a three tier fat tree topology where each level has a database. In order to take its architecture into account inside a peer to peer one, we add a data center per region which corresponds to the data center database, and a region which represents the central database. However, these added structures are not taken into account to the global energy consumption, because those nodes can not process tasks, and only store data. This permits us to compare those strategies for a given amount of storage and processing resources. For the workload, [START_REF] Moyer | Determining the influence of Reddit posts on Wikipedia pageviews[END_REF] shows that when there is a post on a social media with a link to Wikipedia, there is an increasing interest about the topic, increasing the number of views on the linked Wikipedia page. Then the interest fades away, decreasing the number of access to the topic page on Wikipedia. [START_REF] Lerman | Information Contagion: an Empirical Study of the Spread of News on Digg and Twitter Social Networks[END_REF] also highlights the fact that this interest can fade at different speed. Based on this information, we simulate 2 different workload. The first one is represented by experiment 1 and experiment 3 for the smaller and larger scale ones respectively. The second workload is represented by experiment 2 and experiment 4. These workload model a short interest for a content. To do so, we choose the gamma probabilistic distribution to model the arrival rate of requests with parameters α = 4 and β = 600. The difference between the first workload and the second is that the increase comes at 4h and 1h30, respectively. All differences between experiments are summarized in Table 3. Also, experiments are processed 25 times as there is some randomness that may impact the results. Results are shown through means and standard deviations.

To compare these policies and strategies, we used 4 metrics: (i) the number of created replicas, (ii) the proportion of violations which represents the number of time the response time is higher than the SLO divided by the number of request. (iii) The energy consumed (in MJ) by the Cloud at the end of the experiment and (iv) the total cost for the provider (in $).

A GitHub repository is available here2 to let everyone run their own experiments with their parameter on our environment.

Comparison between different policies

First, we compare different policies from our static data replication strategy. As a reminder, we compare E2ARSEX and E2ARSEC which are policies that only take respectively expenditure and energy consumption exclusively. There is a 3 rd policy that is a balance between those 2 objectives called E2ARS. The following figures and analysis are first based on experiment 3 (large scale experiment with an increase after 4h). At first, it can be highlighted the fact that the more energy consumption is considered, the less the strategy creates replicas. In fact, E2ARSEC is the the lowest number of replicas with an average of 2915.1 (σ = 13.12) replicas, followed by E2ARS and E2ARSEX with an average of 2,923.2 (σ = 9.61) and 2,937.5 (σ = 9.26) replicas respectively. These differences have an impact on the number of violations. Figure 1a represents the cloudlet arrival rate of experiment 3 and the SLO violations ratio. This figure shows that violations are sorted according to the number of replicas which mean that E2ARSEC, with an average of 3,027.3 (σ = 1, 184.3), has more violations than E2ARS, with an average of 2,752.4 (σ = 1, 634.6). Then E2ARS has more violations than E2ARSEX with an average of 2,171.6 (σ = 786.7). Yet, only the difference between E2ARSEC and E2ARSEX are statistically different (based on Student tests to compare means).

Figure 1b shows the standardized values of energy consumption and expenditure for experiment 3. On this plot, E2ARSEC is the policy that consume less with an average of 595.4 MJ (σ = 16.64) compared to E2ARSEX which consumes 606.1 MJ (σ = 17.3) and E2ARS that consumes 601.7 MJ (σ = 14.1). E2ARSEX is the cheapest one with an average cost of 8,713.8$ (σ = 234.6) compared to E2ARS which costs 8,848.6$ (σ = 215) and E2ARSEC 8,867.3$ (σ = 210.1). The ordering of those policies still seems to make sense as they represent 3 different policies of our spectrum. E2ARS will then correspond to the selected strategy as it is in the middle of the spectrum. Just like the replication, E2ARSEC and E2ARSEX are significantly different for both energy consumption and expenditure.

However, it has to be highlighted that the number of files and nodes have an impact on these results. In fact, this has an impact on their range of possibility, implying that some results shows that E2ARS can be closer to E2ARSEX or E2ARSEC in terms of performance, energy consumption and expenditure.

Comparison between different strategies

To compare all the strategies, we analyze experiment 1 (small scale, increase after 4h), but other results will also be analyzed as they highlight some differences compared to this experiment. Figure 2a shows the number of replications during the experiment 1 when comparing our strategy with the static ones (MORM, 3Rand), and the dynamic ones (Boru et al., PEPR). Within the static strategies, 3Rand creates 2 replicas per files, MORM creates a lot of replicas (more than a thousand) and E2ARS created a bit less than 3 replicas per file. A first comparison we can focus on is the time needed to let MORM choose how many and where to place its replicas compared to E2ARS. In fact MORM takes an average of 1,164 seconds to compute its strategy while E2ARS takes around 9.6 seconds. In the dynamic group, PEPR starts without replicas, and it adapts dynamically based on violations and profit. Implying that the stop of the increasing number of replicas can be either due to the lack of violations or the lack of profit. Boru et al. starts without replicas either, as all data are stored in the central database, and then if the number of requests is higher than a threshold it triggers the replication, and it replicates if the energy consumption and the bandwidth of the level below is lower. This is why there is a sharp increase of data replication, then it gets slower, as long as most of the highly requested data in the central database are already replicated. However, on Figure 2b, we can see that even with the 2 nd largest number of replicas, it as the highest number of violations (reaching up to 83% at the end. This is mostly due to the topology that makes a bottleneck where data are stored. It is followed by 3Rand and E2ARS which violated the SLO with an average of 700 times (σ = 370) corresponding to 0.9% of cloudlets and 510 times (σ = 164) which correponds to 0.7% of all cloudlets respectively. PEPR's number of violations follows the number of replicas created in this workload. In fact, as the number of violations began to remain constant, the number of replicas is also kept constant. Which means that the reason of stopping the creation of replicas in this workload is based on the number of violations. Finally, MORM is the strategy that has no violations at all as it created a huge amount of replicas. Table 4 and Table 5 represent the number of replicas created and the number of SLO violations respectively at the end of each workload. Figure 3 corresponds to the standardized values of energy consumption and expenditure of experiment 1. We chose 3Rand as a control strategy, its average energy consumption is 228.47 MJ (σ = 7.17) and it costs 4,732$ (σ = 304.89). It is the baseline to which we compare others strategies. On this figure, MORM is the cheapest with a reduction of 87% of the cost. It is explained by the fact that it replicates a lot implying an absence of data transfer between regions which is very expensive, but this would be very expensive for a long term storage. But, this is the second most energy consuming strategy with an increase of 84% compared to 3Rand Based on all results (Table 4, Table 5, Table 6 and Table 7), experiments show differences in terms of results and behaviors. For instance, Boru et al. keeps a low number of replicas in larger scale experiments compared to smaller ones. This is mostly explained by the chosen threshold that has to be lowered as the number of file increases. However, we kept the same replication conditions between all experiments as it was for other strategies. It mostly has an impact on transfer time, implying an increase in terms of violations (up to 98% of all cloudlets), expenditure and energy consumption. PEPR handles the larger scale experiments and keeps reducing both expenditure and energy consumption in almost all experiments. Yet, in experiment 3 (large scale, increase after 4h), PEPR has a very low number of replicas linked with a high number of violations (73% of all cloudlets). This means that replications stopped due to the lack of profit as the expenditure went higher. Finally, E2ARS keep its performance in larger scale with a low number of violations (up to 1.8% in large scale) with a low processing time (around 9 seconds in small scale and 161 seconds for larger scale ones). Also, larger scale experiments highlight a higher reduction of both energy consumption and expenditure compared to 3Rand with a reduction of 36% and 18% respectively.

Conclusion

In this paper, we proposed a static data replication strategy called E2ARS that achieves its objective to reduce both energy consumption and expenditure compared to other strategies. The proposed strategy takes into account the trade-off between reducing energy consumption and reducing expenditure that is considered and decided by the administrator instead of finding an optimal solution for one issue or another. E2ARS uses a 2 steps decision process in order to reduce the search space. The first step uses an Evolutionary Algorithm named SPEA2 followed by a second step which is a heuristic that places data on a few amounts of nodes in order to leverage technologies like PowerSleep. We compared our strategy alongside a control strategy that places 3 replicas placed randomly (3Rand). We also compared our strategy to other existing strategies proposed in the literature, both static (MORM) and dynamic (Boru et al., PEPR). Results show that E2ARS reduces the number of violations compared to 3Rand with only a few more replicas. Also, E2ARS fulfilled its objective to reduce both energy consumption and expenditure compared to the others strategies, that mostly reduced efficiently one objective. Compared to MORM, E2ARS significantly reduces both energy consumption and expenditure. On the other hand, despite E2ARS is a static strategy, its energy consumption and the number of violations are only slightly higher compared to the compared dynamic strategies. Furthermore, E2ARS leverages the cloud heterogeneity and technologies like PowerSleep while keeping a high level of performance without creating a large amount of replicas.

For future work, we will use the proposed static data replication strategy as an initial placement for a forthcoming dynamic data replication strategy. Also, it would be interesting to use some techniques like data compression in order to reduce storage cost and energy consumption. Another idea is to include the reduction of carbon footprint by knowing the energy mix of each data center. Finally, we are currently repeating these experiments on a real architecture.

  IRIT/RR -2021-07-FR Algorithm 1 Static Data Replication Algorithm Input: N: List of nodes Input: F: List of Files Input: t: renting time Input: NbRds: number of reads Input: listOfDC: List of DC Output: Final Individual: matrix of files and nodes that represents replica placement 1: Final Individual = zeros(F,N) // matrix (number of files, number of nodes) of zeros 2: DCrep = getRepresentativesDC(N) // retrieve one node for each data center 3: OriginFiles = getOriginalNodeFile(F, N) // nodes where files are stored at first 4: DC individuals = getSPEA2Result(F, DCrep, OriginFiles, t, NbRds) 5: DC individual = chooseIndividual(DC individuals) 6: for all DC in listOfDC do 7: tempNodesInDCList = getNodesFromDC(N, DC) 8: tempFileInDCList = getFileOnDC(DC individual, F) 9: tempDCIndividual = FirstFitNoBottleneck(F, tempFileInDCList, tempNodesInDCList) 10:

1 .

 1 Generate an initial population 2. Calculate the fitness for each individual 3. Select individuals based on domination and truncation 4. End the algorithm if the maximum number of generations is reached 5. Selection with replacement within the archive to fill the mating pool 6. Recombination and mutation operators to the mating pool, go to step 2

Algorithm 2 FirstFitNoBottleneck

 2 Input: F: List of all files Input: FilesInDC: List of files that will be stored in the current DC Input: Nodes DC: List of nodes in DC Output: DCIndividual : matrix of File stored on Node 1: DCIndividual = zeros(z, Node DC) // matrix (z, nbNodesInDc) of zeros 2: orderedFileListId = sort(FilesInDC) // sort files based on their size and return their id 3: totalNbNode = getTotalNbNode(Node DC, FilesInDC) 4: capacity = getAllCapacity(Node DC) // get a list of capacity for all nodes in DC 5: for all idFile in ordderFilesListId do 6: idNode = idFile % totalNbNode // First chosen node 7: tempNode = Node DC[idNode]

25 :

 25 if capacity(tempNode) > size(F[idFile]) then Input: Nodes DC: Set of nodes in DC Input: FilesInDC: Set of files that will be stored in DC Output: Number of Nodes 1: prop = 0.0625 2: totalFileSize = getTotalSize(FilesInDC) // return the size of all stored data in the chosen DC 3:

  (a) Cloudlets distribution and Violations over execution between policies (b) Standardized Value of energy consumption and expenditure between policies

Figure 1 :

 1 Figure 1: Results from experiment 3

Experience

Table 1 :

 1 Notation table

	Notation Description
	F	Set of files, F = {f 1 , ..., f i , ..., f z }
	N	Set of nodes, N = {n 1 , ..., n j , ..., n m }
	ϕ	Matrix of files F stored on node N
	s(f i )	Size of file i (MB)
	cp j	Storage capacity of node j
	P w a	Energy consumption of node action (in Joules)
		a ∈ {read, write, net, static}
	P r b	Price of a node action (in $/MB or $/MB per second)
		b ∈ {net, storage}
	t	Renting time parameter (in seconds)
	nbRds	Number of reads parameter

Table 2 :

 2 Simulation parameters (Smaller scale / Larger scale)

Table 3 :

 3 Differences between experiments

	4.2 Results

Table 4 :

 4 Number of replicas created per each experiment -Mean (Standard -Deviation)

	IRIT

Table 5 :

 5 Number of SLO violations per experiment -Mean (Standard -Deviation) Standardized Value of energy consumption and expenditure of experiment 1 between strategiesas it needs to keep all nodes awaken while other strategies can put them in sleep mode. Boru et al. is the one that costs and consumes the most with expenditure increase of 33% and an energy consumption that is equal to more than 3 times 3Rand. This is mostly explained by the bottleneck created by the topology increasing the execution time, implying an increase in of energy consumption. Also, due to its topology, Boru et al. has to retrieve data from the central database, as it is considered as another region, it sharply increases the cost to transfer data. Compared to 3Rand, PEPR slightly reduces its energy consumption by 4% while keeping the same cost. E2ARS reduces both energy consumption and by 3% and 10% respectively. As other experiments have been done on other workload, results are summarized on table 6 and 7 for energy consumption and expenditure respectively.

IRIT/RR -2021-07-FR Figure 3:

Table 6 :

 6 Energy consumption by experiment and policies in MJ -Mean (Standard-Deviation)

		1	2	3	4
	Boru et al. 747 (77) 722 (56) 8.9k (131) 8.8k (129)
	3Rand	227 (6)	194 (1)	942 (37)	785 (5.54)
	MORM	419 (14) 457 (9)	-	-
	PEPR	216 (6)	192 (1) 896 (119) 498 (2.81)
	E2ARS	220 (6)	187 (1)	602 (14)	503 (4.55)
	E2ARSEC	220 (7)	187 (1)	595 (17)	501 (3.8)
	E2ARSEX 228 (10) 188 (1)	606 (17)	505 (3.2)
	Experience	1	2	3	4
	Boru et al. 6.3k (377) 6.4k (288) 40k (488) 40k (484)
	3Rand	4.8k (305) 4.7k (195) 11k (230) 11k (262)
	MORM	594 (102) 1.8k (1.1k)	-	-
	PEPR	4.7k (350) 3.7k (230) 22k (2.1k) 6.8k (106)
	E2ARS	4.3k (268) 4.1k (331) 8.8k (215) 8.8k (244)
	E2ARSEC 4.3k (269) 4.2k (389) 8.8k (210) 8.9k (209)
	E2ARSEX 3.8k (299) 3.7k 8.7k (235) 8.7k (186)

Table 7 :

 7 Expenditure by experiment and policies in $ -Mean (Standard -Deviation)

Tel: (33) 5 61 55 67 65 -mail: contact@irit.fr

IRIT/RR -2021-07-FR

https://wikitech.wikimedia.org/wiki/Network design (08/28/2020)

https://github.com/MorganSeguela/Cloud 2021 XPS

http://www.irit.fr


Radwan El

Hadj Khalaf

Bruno Agard
email: bruno.agard@polymtl.ca

Bernard Penz
email: bernard.penz@g-scop.inpg.fr

GREEDY HEURISTICS FOR DETERMINING A PRODUCT FAMILY BILL OF MATERIALS

Keywords: family design, bill of materials, integer programming, greedy heuristic, assembly costs

When designing a new product family, designers and manufacturers have to define simultaneously the product structure and its supply chain. This leads to a complex optimization problem to solve in order to satisfy diversified customers' requirements with various options and variants. The paper focuses on the first step of this design problem. It consists in selecting a set of modules that will be manufactured in distant facilities and shipped in a nearby location plant for a final assembly operation under time limits. The objective is to determine the set of modules able to define the bill of materials of each finished product in order to minimize assembly costs. We propose in this paper two heuristic strategies to solve the problem. We provide experiments on small instances which we compare with optimal solutions and we provide also experiments on big instances to compare performance of each heuristic.

INTRODUCTION

Nowadays, the growing demand for customized products involves an increasing number of product variants and options. It follows a complex product diversity to manage. This variety must be controlled in term of product, process and supply chain costs, as well as customer lead-time. Consequently, when designing a new product family, a consistent approach is necessary to quickly define a set of variants and the relevant supply chain, in order to guarantee the customers' satisfaction and to minimize the total investment and operating cost of the global supply chain [START_REF] Lamothe | An optimization model for selecting a product family and designing its supply chain[END_REF].

A product family is composed by similar products that differ by some characteristics such as options. For example, the basic car model may contain few options in order to minimize the sale price. Then, some options can be added to this basic model like air-conditioning, automatic gear box or diesel engines and so on.

There are two extreme production strategies that a company can use. The first one consists to make to stock the different products. This leads to select a minimum set of standardized products [START_REF] Briant | The optimal diversity management problem[END_REF], that could include supplementary options to meet diversified customer requirements. However, storage costs may be too high because of the large product portfolio. The second strategy consists to produce only when an order is received. In this case, the lead time may be higher leading to the non satisfaction of the customer. An intermediate strategy consists to manufacture pre-assembly components, called modules, for stock and to assemble them when an order is planed. The advantage of such strategy is to reduce the lead time and to avoid great storage costs.

In this paper, we explore this production policy where modules are manufactured in distant location facilities for cost minimization. Those modules are shipped and assembled in a nearby location facility in order to ensure a short lead-time for the customers.

We present two heuristic strategies to define the bill of materials of each finished products: (1) the first one consists on exploring the finished product set and determining the most suitable bill of materials for each one and (2) the second strategy consists on exploring the module set, selecting the most interesting one and inserting it in the bill of materials of compatible finished products.

This work is of a great utility for us afterwards, because we need to dtermine quickly the product bills of materials in order to affect the resulting modules on the distant location facilities.

Literature proposes various approaches for the design of product families. Some product design methodologies focus on the product architecture [START_REF] Dahmus | Modular product architecture[END_REF], [START_REF] Jiao | A methodology of developing product family architecture for mass customization[END_REF], this is advantageously supported with modular design [START_REF] Hung | Modularity in design of products and systems[END_REF], component / product / process standardization [START_REF] Kota | A metric for evaluating design commonality in product families[END_REF], [START_REF] Lee | Modelling the costs and benefits of delayed product differentiation[END_REF], [START_REF] Thonemann | Optimal commonality in component design[END_REF]. Different methodologies concentrate on process standardization [START_REF] Lee | Modelling the costs and benefits of delayed product differentiation[END_REF], process resequencing [START_REF] Lee | Effective inventory and service management through product and process redesign[END_REF] or generic assembly routing [START_REF] Gupta | Table 4 Gap rate between MSH results and linear relaxation results[END_REF], [START_REF] He | Design of assembly systems for modular products[END_REF]. From another point of view, authors concentrate on supply chain design methodologies, by integrating customers and suppliers in uncertain environment [START_REF] Davis | Global outsourcing: have U.S. managers thrown the baby out with the bath water?[END_REF], centred on stocks management [START_REF] Lee | Managing supply chain inventory: Pitfalls and opportunities[END_REF] and for distant facility location [START_REF] Van Roy | Cross decomposition algorithm for capacity facility location[END_REF].

In all these works, design of product, process and supply chain are integrated two by two. However, there is some recent works dealing with a global design modeling. [START_REF] Agard | Selection of a module stock composition using genetic algorithm[END_REF] propose a genetic algorithm to minimize the mean of finished product assembly times for a given demand. [START_REF] Agard | A simulated annealing method based on a clustering approach to determine bills of materials for a large product family[END_REF] propose a model for minimizing module production costs and a solving approach based simulated annealing. [START_REF] Lamothe | An optimization model for selecting a product family and designing its supply chain[END_REF] use a generic bill of material representation in order to identify simultaneously the best bill of material for each product and the optimal structure of the associated supply chain

In section 2 we give a more detailed description of the problem and we propose an Integer Linear Program model. Section 3 is devoted then to the description of the two heuristic strategies. Some computational experiments are given and analyzed in section 4. Finally concluding remarks and perspectives are proposed in section 5.

PROBLEM PRESENTATION

Consider the following industrial context: a producer receives customers' orders for finished products containing options and variants. Each individual product is then manufactured from a set of modules that come from various suppliers [START_REF] El Hadj Khalaf | Product and supply chain design using a two-phases optimization approach[END_REF].

Consider now that the producer has only a short delay (T) to respond to customer demands. This delay is less than the necessary time to assemble products from elementary components. In addition to this, the producer has to provide the product exactly like the customer demand (without extra options). This constraint comes from technical considerations or simply to avoid supplementary costs.

To satisfy customers, the producer brings preassembled components, called modules, from many suppliers which are located in distant facilities around the world. The suppliers' facilities are characterized by a very weak production costs. Then, the modules are assembled in the producer facility which we assume to be very close to the customers and thus characterized by its great reactivity and a reduced lead-time. Our problem consists then on defining the bill of materials of each finished product in order to minimize the total assembly costs.

Specifying the problem assumptions: a product or a module is considered as the set of functions that it must fill, then:  a function F k is a requirement that must be ensured by the finished product.

 a module M j is an assembly of functions that could be added with other modules to make a finished product.

 a finished product P i is an assembly of modules that corresponds exactly to at least one customer demand.

Let introduce the following notations:

 F = {F 1 ,...,F q }: set of q functions that can appeared in both finished products and modules.

 P = {P 1 ,...,P n }: set of n possible finished products that may be demanded by at least one customer. We note D i the estimated demand of the product P i during the life cycle of the product family.

 M = {M 1 ,...,M m }: set of m possible modules.

 CF j : the management fixed cost of module M j in the nearby facility.

 CV j : the assembly variable cost of module M j in the nearby facility.

 w j : the necessary time to assemble the module M j in a finished product (which is fixed to 1 for all modules).

 T: the available time to assemble a finished product from modules.

 WhP i , WhM j : the weights of respectively product P i and module M j (which represent the number of existing functions in a product or a module).

Under these assumptions, we can represent a product (or a module) by a binary vector of size q. Each element shows whether the corresponding function is required in the product (value = 1) or not (value = 0).

The set M contains m modules. It may be a selection of modules defined by the engineering or all the possible modules issued from the whole combinatory.

The problem is now to determine the subset M' M, of minimum cost, such that all products in P can be built in a constrained time window T with elements from M'. Concerning the products, the goal is to determine which bill of material is the most suitable (Figure 1).

We have done a model of the problem using an Integer Linear Program formulation. Our objective consists in minimizing costs linked to the producer activity. These costs are: fixed costs due to modules management in the nearby location facility and modules assembly costs in the nearby location facility.

        m j n i ij i j m j j j X D CV Y CF Z 1 1 1 ) ( min s.t.   n i Pi AXi ,..., 1    (1)   ,..., 1 1 n i T X w m j ij j      (2)     m j n i Y X j ij ,..., 1 ,..., 1      (3)       m j n i X Y ij j ,..., 1 ,..., 1 1 , 0 ,      (4)
Where X ij = 1 if module M j is used in the bill of materials of product P i , 0 otherwise. Y j = 1 if module M j is selected (belongs to M'), 0 otherwise. A is the binary matrix whose the column j is the vector M j . X j is the column vector composed by the variables X ij .

The objective function minimizes the costs occurring in the nearby location facility, where

  n i ij i X D 1 ) ( is the total need of module M j .
Constraint (1) shows that a finished product P i must be assembled exactly like the customer demand. Constraint (2) indicates that products must be assembled within the time window T in order to respect the delivery time. Constraint (3) traduces the relation between X ij and Y j variables. If a module is used in the bill of materials of some products then it belongs to M'.

The problem described here contains the set partitioning problem. We then conclude that it is NPhard in the strong sense.

HEURISTIC DESCRIPTION

The product building heuristic (PBH)

The main idea of this heuristic is to affect an attractive coefficient to each module and to determine the bill of materials of products one by one (by using Cplex) in such a way as to maximize the sum of attractive coefficients of the product's components. So at each iteration, we resolve the problem described above but only for one finished product. The coefficient expression is given as follow: As much as a module is compatible with finished products F2 becomes bigger. So that, this coefficient favours modules which are compatible with many finished products.

) ( 3 ) ( 2 ) ( 1 j j j j WhM F CV F CF F Coef  
We have used two different functions F3:

        T q WhM WhM F j j if 100 ) ( 31
, 0 otherwise. This function favours small modules which is necessary when cost configuration is such that total fixed costs are greater than total variable costs. In such case it is better to select small modules because they are compatible with much more products, so using them leads to a solution with small number of modules which reduces fixed costs which represent the great part of objective function (el hadj khalaf, R., et al. 2008).

WhP WhM WhM F j j   if 100 ) ( 32 , 0 otherwise. With    n i i n WhP WhP 1 .
This function favours relatively big modules which is necessary when cost configuration is such that total variable costs are greater than total fixed costs. In such case using big modules allows to have small and so to reduce total variable costs which represent the great part of the objective function.

Since we don't know in advance the report between fixed and variable costs, we test this heuristic with both functions F3. Moreover, to improve this heuristic we sort finished products by increasing (and decreasing) order of their weights.

The module selecting heuristic (MSH)

This heuristic is quite simple; the idea is to select the module having the smallest value of

   j i i j j D CV CF
and insert it in the bill of materials of compatible finished products.

To improve this heuristic also, we determine first at each iteration k the ideal weight of the module to be selected by the formula:

        i ik ik k k W WhP n Wh 1
with: WhP ik is the weight of the remaining functions of product P i at iteration k which are not covered yet and W ik = T -W0 ik where W0 ik is the number of modules inserted in the bill of materials of the product P i up to the iteration k, n k is the number of remaining products at iteration k ( those which haven't the complete bill of materials yet). This operation aims to avoid selecting unitary modules (whose weight is 1) at the beginning which is proved to be bad for the solution quality.

So we can summarize this heuristic as follow at iteration k:

1. Calculate the ideal weight Wh k of the module to be selected. With WhP i1 = WhP i and n 1 = n and W i1 = T and P i1 = P i 2. Select the module M j whose weight is equal to Wh k and having the smallest value of

   j i i j j D CV CF
. (i represents the products P ik compatible with M j ).

3. Insert the module selected in the bill of materials of compatible finished products.

4. For these compatible products update the product code: P ik = P i(k-1) -M j 5. Update also W ik = W i(k-1) -1 which represents the maximum number of modules that can be inserted in product P ik .

6. For products having W ik = 1, complete their bill of materials by the alone compatible module.

7. Repeat these steps until constructing all bills of materials.

COMPUTATIONAL EXPERIMENTS

Data sets and experimental conditions

We have randomly generated ten small instances for five different sizes;

  The demand D i of a product P i is a decreasing function on the product function number. So that, as soon as the finished product contains more options, then its demand becomes lesser than if it had a few ones. The assembly operating times w j were fixed to 1, so that the constraint (2) turns out on a limitation of the number of modules in a bill of materials.

In order to simplify the problem data, we introduced some rules on the different costs:

     j j j q f CF 1          j j j q f CV 2    
Where q j is the number of existing functions in module M j , f is the square root function

j j q q f  ) (
, we estimate that this function represents at best the relation between costs and q j than the identity and the square functions [START_REF] El Hadj Khalaf | Product and supply chain design using a two-phases optimization approach[END_REF]. α, β are coefficients used to scan different cost configurations. λ1, λ2 are jamming factors.

For each instance size, three cost files are generated by the method described above. The aim is to scan different cases of report between fixed and variable costs.

Table 2 gives the values affected to α and β for each cost. For cost 1 fixed costs are prependerant than variable ones while for cost 2 the two costs are almost equivalen, for cost 3 variable costs are the most preponderant. We have

% 12 2 , 1 % 8    
. For the tests, T was varied from Minf to Maxf. Heuristics are then tested on all instances and all costs. Finally, the mean value of the ten instance objective value is recorded for comparison analyses.

Result analyses

At first, our objective is to compare heuristic results with optimal solutions. This is why we have tested them on an instance of size eight. Table 3 shows the gap rate between the both heuristic results and the optimal solutions for the three cost tests. The first lecture of these results shows that the MS heuristic is better than the PB one. In addition to this, we note that both heuristics run well for medium and high values of T and specially for cost 2 and cost 3 thus when assembly fixed costs are not greater than assembly variable costs. This leads to think that these heuristics optimize well variable costs. Our second objective is to test the two heuristics on relatively big instances in order to compare there performance for a higher problem sizes. That was the object of tests on sizes 10, 11, 12 and 13.

Figures 2, 3 and 4 show the gap rate (as a percentage) between the results of the product building heuristic and the module selecting heuristic (MSH objective value is considered as the reference value). These figures confirm the results obtained for q=8, MSH is much better than PBH and this is true for practically all sizes, delays, and costs. We can note also that the gap rate increases as the problem size increases too. So the gap for q=13 is generally greater than the one for q=12 and so on.

We note also that generally the gap rates are more important for cost 1 than cost 2 and for cost 2 than cost 3. This indicates that MSH optimizes fixed costs more effectively than PBH.

Finally Figure 5 shows the computational time of PBH for q=13. At the end, we present table 4 which show the gap rate (as a percentage) between the MSH results and the problem linear relaxation results for each problem size, cost file and delivery delay. As we can see, the gap is quite reasonable for medium and big delays, it could reaches till 0% in some cases (when T = Maxf). However, it is very great for small values of T because in this case the problem itself becomes much more difficult and even for small instances Cplex spends much more time to reaches the optimal.

We note again, that the gap rate is more important (for small delays) for the cost 1 contrarily to the other costs. We can hope that MSH provides relatively good solutions for cost configurations on which assembly fixed costs are not preponderant than assembly variable costs.

CONCLUSION

This paper was dedicated to a difficult industrial problem arising when companies try to offer a large variety of products to consumers. In this problem, a choice of components (modules) has to be efficient. These modules are produced for stock, and used in the last stage, in the assembly line. Several authors considered this problem, using different assumptions -a function can appear twice in a final product, a final product can be substituted by another one containing more functions -but few papers consider the problem in which each final product must correspond exactly to the demand.

We have focus on the assembly operation and we tried to determine an efficient module set allowing to assemble products and to avoid function redundancy while respecting the delivery delay. The objective function consists in optimizing the costs occurring in the producer activity.

Our aim was to analyze to strategies of heuristic design. The first one consists in determining the bill of materials of finished products one by one by fixing attractive coefficients for each module. The second strategy takes the ideal module verifying the selecting criterion and inserts it in the bill of materials of compatible finished products.

Besides the computational time speed, our tests reveal that the MSH strategy is by far the one which gives the best results. This can be explained by the difficulty to find good module coefficients and especially the problem structure in which solutions must take into account the interactions between finished products which make very difficult the determining of one product bill of materials independently from the other ones.

Finally, the MSH results encourage us to use it as an initial solution for a metaheuristic resolution in the future. It would be also interesting to extrapolate this heuristic in order to take into account the logistic chain phase.

Figure

  Figure 1 alternative bills of material

  P i must be compatible with module M j (M j haven't extra functions than P i ). So that the term   j i i D represents the needs of module M j if we use it in the remaining compatible products at iteration k.

Figure 2 Figure 3 Figure 4 Figure 5

 2345 Figure 2 Gap rate between PBH & MSH for cost 1

Table 1

 1 Instance parameters

Table 2

 2 Cost Configurations

Table 3

 3 Gap rate between heuristic results and optimal solutions for q = 8