Eugen Feller
email: eugen.feller@inria.fr

Louis Rilling
email: louis.rilling@kerlabs.com

Christine Morin
email: christine.morin@inria.fr

Energy-Aware Ant Colony Based Workload Placement in Clouds

Keywords: Ant Colony Optimization, Combinatorial Optimization, Green Cloud Computing, Multidimensional Bin Packing, Swarm Intelligence, Virtualization

With increasing numbers of energy hungry data centers energy conservation has now become a major design constraint. One traditional approach to conserve energy in virtualized data centers is to perform workload (i.e., VM) consolidation. Thereby, workload is packed on the least number of physical machines and over-provisioned resources are transitioned into a lower power state. However, most of the workload consolidation approaches applied until now are limited to a single resource (e.g., CPU) and rely on simple greedy algorithms such as First-Fit Decreasing (FFD), which perform resource-dissipative workload placement. Moreover, they are highly centralized and known to be hard to distribute. In this work, we model the workload consolidation problem as an instance of the multidimensional bin-packing (MDBP) problem and design a novel, nature-inspired workload consolidation algorithm based on the Ant Colony Optimization (ACO). We evaluate the ACO-based approach by comparing it with one frequently applied greedy algorithm (i.e., FFD). Our simulation results demonstrate that ACO outperforms the evaluated greedy approach as it achieves superior energy gains through better server utilization and requires less machines. Moreover, it computes solutions which are nearly optimal. Finally, the autonomous nature of the approach allows it to be implemented in a fully distributed environment.

I. INTRODUCTION

Cloud computing has recently evolved as a new computing paradigm which promises virtually unlimited resources. Customers can rent resources based on the pay-as-you-go model and thus are charged only for as much as they have used. Thereby, resources are transparently provisioned by the cloud provider according to the customers requirements. However, customers growing demands for computing power are now facilitating the cloud service providers (e.g., Amazon, Google, Microsoft, Yahoo!, etc.) to deploy increasing amounts of energy hungry data centers [START_REF]Make it green: Cloud computing and its contribution to climate change[END_REF]. Consequently, energy costs for operating and cooling the equipment of such data centers have increased significantly up to a point where they are able to surpass the hardware acquisition costs. Studies have shown that data centers around the world consumed 201.8 terawatt hours (TWh) in 2010. This is enough energy to power 19 million average U.S. households and results in approximately $23.3 billion spent for energy costs [START_REF] Alliance | Carbon footprint values[END_REF].

From the business perspective, reducing the energy consumption can lead to immense cost reductions. Moreover, besides the huge energy costs, heat dissipation increases inevitably with higher power consumption and doubles the probability of hardware failures [START_REF] Feng | Green supercomputing comes of age[END_REF]. Therefore, reducing the energy dissipation has a significant effect on the overall availability, reliability and productivity of a system. Not least, the way energy is generated influences our environment either directly by the carbon footprint or indirectly by the nuclear waste. Therefore, reducing the energy consumption does not only save a significant amount of money and improves the system reliability, but also helps protecting our environment. According to [START_REF] Kaplan | Revolutionizing data center energy efficiency[END_REF], data centers emit as much CO 2 as the whole Argentine, and will quadruple their CO 2 emissions by 2020.

Several approaches exist in order to conserve energy. Besides the possibility to replace the hardware with more energyefficient one, reducing the energy wasted because of hardware over-provisioning is crucial. Today's data centers infrastructure is typically over-provisioned in order to sustain the service availability during periods of peak resource demand. However, resource demand in current data centers is usually of a bursty nature and thus results in a low average utilization of approximately 15-20% [START_REF] Vogels | Beyond server consolidation[END_REF]. Therefore, a big fraction of the resources can be used to take energy conservation decisions such as suspending or turning off unnecessary servers, while still preserving the customers performance requirements. Several open-source cloud projects have been recently started to provide alternative solutions to public Infrastructure as a Service (IaaS) cloud providers (e.g., Amazon EC2). Examples of such cloud management frameworks include Eucalyptus, OpenNebula, and Nimbus.

Given that ubiquitous virtualization solutions are able to live migrate the workload (i.e., VMs) and servers can be turned on and off at any time, clusters can be turned into dynamic pools of resources by these frameworks. However, one of the main limitations of all current cloud management frameworks next to their high degree of centralization [START_REF] Feller | Snooze: A Scalable, Fault-Tolerant and Distributed Consolidation Manager for Large-Scale Clusters[END_REF], is that they do not provide any advanced energy-aware workload consolidation policies.

Consolidation of virtual machines on the least number of physical nodes is an instance of the well known multidimensional bin-packing (MDBP) problem and has been mostly studied by means of simulations in several works (e.g., [START_REF] Chekuri | On multi-dimensional packing problems[END_REF], [START_REF] Stillwell | Resource allocation algorithms for virtualized service hosting platforms[END_REF]). Thereby, because of the NP-hard nature of the problem and the need to compute the solutions in a reasonable amount of time, approximation approaches (i.e., heuristics) have shown to provide good results. However, many of the existing approaches nowadays still: (1) ignore the multidimensional character of the problem (e.g., [START_REF] Buyya | Energy-efficient management of data center resources for cloud computing: A vision, architectural elements, and open challenges[END_REF], [START_REF] Li | Enacloud: An energysaving application live placement approach for cloud computing environments[END_REF]), [START_REF] Alliance | Carbon footprint values[END_REF] adapt simple greedy algorithms (e.g., FFD), which tend to waste a lot of resources [START_REF] Setzer | Decision support for virtual machine reassignments in enterprise data centers[END_REF] and are highly centralized.

In this paper, we first accurately model the workload placement problem as an instance of the multi-dimensional binpacking (MDBP) problem. We then take a nature-inspired approach derived from the behavior of real ants and propose a novel algorithm based on the Ant Colony Optimization (ACO) meta-heuristic to compute the placement dynamically according to the current load. We apply our algorithm on a number of synthetic test instances and compare it with one frequently applied greedy algorithm (i.e., FFD). The results indicate that the ACO-based algorithm outperforms the evaluated greedy approach as it computes workload placements with superior energy gains through better resource utilization and requires less machines. Moreover, by solving the model utilizing the IBM ILOG CPLEX [START_REF]Ilog cplex: High-performance software for mathematical programming and optimization[END_REF] solver, we show that the solutions computed by our approach are nearly optimal (i.e., small deviation of 1.1%). To the best of our knowledge this is the first work to: (1) apply ACO on the MDBP problem in the context of dynamic workload consolidation and (2) utilize ACO in order to conserve energy.

The remainder of this paper is organized as follows. Section II gives a short introduction to the ACO. Section III provides a formal problem definition of the workload placement problem as an instance of the multi-dimensional bin-packing (MDBP) problem and introduces our workload resource demand estimation approach. Section IV details the design of the ACO-based workload consolidation algorithm. Section V presents the experimental results. Section VI discusses the related work. Finally, Section VII closes the paper with conclusions and future work.

II. ANT COLONY OPTIMIZATION

Ant Colony Optimization (ACO) is a meta-heuristic, which was initially introduced as Ant Systems (AS) in 1992 within the PhD thesis of the Italian researcher Marco Dorigo [START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF]. Initially, it was developed to solve the Traveling Salesman Problem (TSP). However, since then it has been successfully adapted to solve many other complex combinatorial optimization problems (e.g., vehicle routing, quadratic assignment, dynamic job scheduling, graph coloring and bin packing).

The main inspiration to develop this system was the natural food-discovery behavior of real ants. Because of the limited abilities of the ants to see and hear their environment they have developed a form of indirect communications (also called Stigmergy) by use of a chemical substance referred as pheromone. This substance is deposited by each ant on the path it traverses and evaporates after a certain period of time. Other ants can smell the concentration of this substance and tend to favor paths probabilistically according to the amount of pheromone deposited on them. Surprisingly, after some time the entire ant colony converges towards the shortest path to the food source. This behavior was studied by biologists in numerous controlled experiments [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF] and can be explained as follows. At the beginning, when starting from the nest the ants choose a random path to follow. However, on the shortest path to the food source the ants will return faster. Thereby, this path will have a stronger pheromone concentration thus being more attractive for subsequent ants to follow it. When time passes, pheromone concentration on the shortest paths will continue to increase, while on the longer ones it will keep falling, making them less and less attractive.

When applied on combinatorial optimization problems such as TSP or the Bin-Packing Problem (BPP), artificial ants act as a multi-agent system and construct a complex solution based on indirect low-level communication. Thereby, several parts of the algorithm need to be defined in order to imitate real ants. Similarly, as real ants do, a decision on which path or item to choose next needs to be taken. Therefore, a probabilistic decision rule has to be defined which will be used by the algorithm to guide the ants choice towards the optimal solution. Furthermore, unlike real ants, a memory is necessary for each ant, which will be used to keep track of the local solution constructed so far. Finally, a pheromone update mechanism is required in order to: (1) simulate pheromone evaporation, (2) deposit pheromone either on the visited paths (i.e., TSP) or on the selected item-bin pairs (i.e., BPP), respectively. Thereby, a decision needs to be taken on which ant will perform the pheromone updates. This can be either done after each ants move, by the iterations best ant, or the best-so-far ant. We will describe our design choices in Section IV.

III. FORMAL PROBLEM DEFINITION AND RESOURCE DEMAND ESTIMATION

This section details the assumptions of this work and provides a formal definition of the workload consolidation problem as a multi-dimensional bin-packing (MDBP) problem. Thereby, a binary integer programming (BIP) representation of the problem is introduced. Afterwards, the workload resource demand estimation approach is presented.

A. Assumptions

We assume a homogeneous environment in which all physical machines have the same capacity. Furthermore, the algorithm requires the knowledge about all the workload and its associated resource requirements in order to compute the placement. These resource requirements can be either seen as static or dynamic. In the static case it is assumed that a batch of VMs is submitted to the system and needs to be placed. Thereby, as no utilization information is available upon initial submission, given VMs resource requirements are considered static and VMs are scheduled according to this information.

On the other hand, when time passes (i.e., sufficiently long) history resource utilization becomes available and can be used to estimate the resource demand. In that case, VM resource requirements can be seen as the dynamic estimates of the maximum resources required by the VMs over the predefined monitoring interval (e.g., week). The proposed algorithm then takes those values as input and dynamically overbooks the resources when the workload resource demand permits it. Thereby, the resource utilization is optimized. Consequently, we assume that workload resource utilization can be measured over predefined periods of time T (e.g., weeks) thus allowing the maximum workload resource demand to be estimated. Thereby, for the sake of simplicity the time t at which the maximum resource demand values are computed is not mentioned in the following formal definitions and is assumed to be the same as on which the workload consolidation algorithm is triggered. Moreover, in order to minimize the amount of migrations and limit the degree of performance degradation the algorithm is assumed to be triggered after predefined, sufficiently long periods of time (e.g., weekly basis). More intelligent triggering decisions based on the analysis of workload characteristics (see [START_REF] Setzer | Decision support for virtual machine reassignments in enterprise data centers[END_REF]) are possible but go beyond the scope of this paper. Finally, despite the relative long measurement periods, overbooking of resources can lead to performance degradation when workload resource demands suddenly start to increase. It is assumed that such changes can be detected and handled by the appropriate algorithm [START_REF] Khanna | Application performance management in virtualized server environments[END_REF].

B. Formal Problem Definition

We define the problem of mapping the workload (i.e., VMs) to physical machines as an instance of the MDBP problem, in which the physical machines represent the bins and the workload the items to be packed. Each bin has a predefined static resource (e.g., CPU cycles, CPU cores, RAM size, network bandwidth and disk size) capacity vector and each item is assigned with one time-varying resource demand vector.

Let B := {B 0 , . . . , B v , . . . , B n-1 } denote the set of bins and I := {0, . . . , m -1} the set of items, with n = |B| and m = |I| representing the amounts of bins and items, respectively. Furthermore, available resources (i.e., CPU cycles, CPU cores, RAM size, network bandwidth and disk size) are defined by the set R with d = |R|.

Each bin B v is assigned with a predefined static homogeneous d-dimensional bin capacity vector

C v := (C v,1 , . . . , C v,k , . . . C v,d
), in which each component defines the bin's capacity of resource k ∈ R. Moreover, all item's i ∈ I are represented by their time-varying d-dimensional resource demand vectors r i := (r i,1 , . . . , r i,k , . . . , r i,d ) ∈ [0, 1] d , with each component of the vector being the items maximum demand for resource k ∈ R over the last measurement period T (e.g., week) relative to the corresponding dimension in the static bin resource capacity vector C v . Thereby, without loss of generality we assume that the values of C v have been normalized to 1 in the following definitions.

Finally, in order to complete our binary integer programming (BIP) model, we define the following two decision variables:

1) Bin allocation variable y v , equals 1 if the bin v is chosen, and 0 otherwise. 2) Item allocation variable x i,v , equals 1 if the item i is assigned to the bin v, and 0 otherwise. The ultimate goal of the consolidation algorithm is then to place all items such that, the number of bins used is minimized. This is reflected in our objective function [START_REF]Ilog cplex: High-performance software for mathematical programming and optimization[END_REF].

Minimizef (y) = n-1 v=0 y v (1)
Subject to the following constraints:

m-1 i=0 r i,k x i,v ≤ C v,k y v , ∀v ∈ {0, . . . , n -1}, ∀k ∈ R (2) n-1 v=0 x i,v = 1, ∀i ∈ {0, . . . , m -1} (3)
Constraint ( 2) ensures that the capacity of each bin is not exceeded and constraint (3) guarantees that each item is assigned to exactly one bin.

C. Workload Resource Demand Estimation

Given that workloads resource demands are of time varying nature, spikes in utilization are most likely to appear. In order to provide stable values to the workload consolidation algorithm and minimize the amount of performance degradation due to consolidation, workload demand estimations are needed. We base our estimations on the long-term workload resource utilization history (e.g., weeks, months). Thereby, workload resource utilization is captured at predefined measure points thus creating a data set composed out of discrete resource measures. These measures are then analyzed and workload resource demand r i,k is estimated by taking the maximum value of the previous measures. These values are then used by the algorithm to perform the consolidation.

IV. ENERGY-AWARE ANT COLONY OPTIMIZATION BASED WORKLOAD CONSOLIDATION

This section presents the design of our ACO meta-heuristic based algorithm, to solve the previously defined workload consolidation problem. Thereby, all parts of the algorithm are described and the pseudocode is presented. In the proposed algorithm each ant receives all items (i.e., VMs), opens a bin (i.e., physical machine) and starts assigning the items to the bin. This is achieved by the use of a probabilistic decision rule, which describes the desirability for an ant to choose a particular item as the next one to pack in its current bin. This rule is based on the information about the current pheromone concentration on the item-bin pair and a heuristic which guides the ants towards choosing the most promising items. Hence, the higher the amount of pheromone and heuristic information is associated with a particular item-bin pair, the higher the probability is that an ant will choose it. This stochastic nature of the algorithm allows the ants to explore a large number of potential solutions and thus compute better placements than the evaluated state-of-the-art greedy algorithm (see Section V).

Finally, after all ants have constructed their solutions, the amount of pheromone associated with each item-bin pair needs to be updated in order to simulate pheromone evaporation and reinforce item-bin pairs which belonged to the better solutions. Consequently, a pheromone update rule is defined.

A. Probabilistic Decision Rule

We define the probability for an ant to choose an item i as the next one to pack in its current bin v as follows.

p i v := [τ i,v ] α × [η i,v ] β u∈Nv [τ u,v ] α × [η u,v ] β , ∀i ∈ N v (4)
whereby, τ i,v denotes the pheromone based desirability of packing item i into bin v and η i,v the items heuristic information. Moreover, two parameters α, β ≥ 0 are used in order to either emphasize more the pheromone or the heuristic information. Finally, N v defines the set of all items which qualify for inclusion into the current bin v. Hence, those are all items which have not been assigned to any bin yet and do not violate the bin capacity constraints in all dimensions.

N v := {i | n-1 j=0 x i,j = 0 ∧ b v + r i ≤ C v } (5)
Thereby, b v is defined as the load vector of the bin v. It is computed as the sum all item resource demand vectors assigned to the bin.

b v := i∈Bv r i (6)

B. Heuristic Information

As our objective is to minimize the number of machines (i.e., maximize the resource utilization), we define the heuristic information to favor items which utilize the bins better. This is achieved by defining η i,v as the inverse of the scalar valued difference between the static capacity of bin v and the load of bin after packing the item i ∈ N v .

η i,v := 1 | C v -( b v + r i )| 1 (7)
In order to compute the ratio defined by equation 7 the resulting d-dimensional resource demand vector needs to be mapped to a scalar value. Therefore, the L1-norm is used in this work. However, alternative methods such as taking the arithmetic mean are possible.

C. Pheromone Trail Update

After all ants have finished building a solution, pheromone trails on all item-bin pairs need to be updated in order to help guiding the algorithm towards the optimal solution. Thereby, a pheromone trail update rule τ i,v exists and is used in order to simulate pheromone evaporation and reinforce item-bin pairs which belonged to the so far best solution. In this work we follow the MAX-MIN Ant System (MMAS) [START_REF] Stutzle | Improvements on ant-system: Introducing maxmin ant system[END_REF] approach in which only the iteration's-best ant (i.e., ant whose solution's objective function value is minimal) is allowed to deposit pheromone. The pheromone update rule is defined in Eq. 8.

τ i,v := (1 -ρ) × τ i,v + △τ best i,v , ∀ (i, B v ) ∈ I × B (8)
whereby, the constant ρ, 0 ≤ ρ ≤ 1 is used to simulate pheromone evaporation. Hence, higher values for ρ lead to increased evaporation rate. Moreover, some item-bin pairs need to be reinforced. Thereby, △τ best i,v is defined as the iteration's-best item-bin pheromone amount. Hence, if some item belongs to a bin of the so far best solution S best , its pheromone amount is reinforced. Consequently, only itembin pairs which are part of S best will be reinforced and thus become more attractive. Others, which are not part of S best will continue loosing pheromone according to the pheromone evaporation rate ρ. Thereby, a solution S := [x i,j ] |I|×|B| is defined as a binary matrix whose elements represent the mapping of items to bins.

The ultimate goal of our ACO-based algorithm is to minimize the amount of bins, thus increasing the average utilization of each bin. Hence, we target to favor solutions which utilize the least number of bins. Therefore, we define the amount of pheromone iteration's best ant deposits on the item-bin pair to be inverse proportional to the value of the objective function f applied on the iteration's best-solution S best . Thereby, only item-bin pairs which are marked as allocated in S best will be reinforced.

△τ best i,v := 1 f (S best ) if x i,v = 1 0 otherwise (9)
Finally, because only the iteration's-best ant is allowed to deposit pheromone, early stagnation of the search is most likely to happen, thus leading to a situation in which all ants always choose the same items. Thereby, the ability of the algorithm to explore alternative solutions is decreased. In order to limit this effect, MMAS [START_REF] Stutzle | Improvements on ant-system: Introducing maxmin ant system[END_REF] introduces lower and upper bounds for the pheromone values τ i,v . Hence, τ i,v is restricted to the range [τ min , τ max ]. Analogously, we define τ max as τ max := 1 f (S best )×(1-ρ) and τ min as τ min := τmax g , respectively with factor g > 1.

D. Formal Algorithm Definition

The pseudocode of the ACO-based algorithm is depicted in Figure 1. The algorithm takes as input the set of items and bins, including their corresponding time-varying resource demand vectors r i and static resource capacity vectors C v , respectively. Moreover, a set of parameters (i.e., α, β, ρ, g, τ max , nCycles, nAnts) is required for initialization. First, the parameters are initialized and the pheromone trails of the items are set to τ max (line 4). The algorithm then iterates until the specified number of cycles nCycles (lines 5 to 35). Thereby, for each iterations an ant a opens a bin v and starts building a solution S a (lines 6 to 20). This is achieved by first initializing the set of items IS, the elements of the binary solution matrix S a and the bin-index variable v. The algorithm then enters a loop and starts assigning the items to the bins (lines 9 to 19). Thereby, the current bin v is being filled until its resources are saturated. This is achieved by initializing the set N v with all items which are not yet assigned to any bin and do not violate the capacity constraints of the current bin (line 10). If this set is not empty, the probabilistic decision rule p i v is used to select one item i out of the set to be packed in the current bin v, stochastically (line 12). The item is then marked as allocated in the solution matrix by setting the appropriate value in the matrix S a to 1, removed from the set of items IS and the host utilization is updated (lines 13 to 15). This process is performed as long as there still items left to be assigned and enough capacity available in the current bin (line 9 and 10). Afterwards, when the bin capacity is saturated (i.e., N v becomes empty) the bin-index variable is incremented and the packing process is continued until all items are placed (lines 9 to 19). After all ants have constructed their solutions S a , a comparison is performed and the cycle's best solution is saved (line 21) as S cycle . Thereby, two criteria: amount of utilized bins and amount of failed item allocations are used in order to judge about the cycle best solution. While the first one seems natural, the second one is a result of two solutions which equal in terms of utilizing all available bins but differ in the utilization efficiently of the bins. For instance, two solutions would use the same number of bins, but the first one would fail allocating resources for 10% of the requests while the second one would satisfy all requests. Finally, if this is the first cycle, the cycle best solution becomes the global best one. Otherwise, a comparison is done with the current global best solution. Thereby, if the cycle best solution yields to an improvement it becomes the new global best one (lines 22 to 24). Afterwards, the values for τ min and τ max are computed (line 25) and the pheromone trails on all item-bin pairs (i, B v ) are updated using the pheromone update rule τ i,v (lines 26 to 34). Thereby, in order to respect the specified lower and upper bounds for τ i,v two conditions exist. First condition guarantees that the upper bound is respected. Hence, if some item-bin pair received a higher pheromone amount than τ max , it is reinitialized to τ max (lines 28 to 30). Similarly, when the pheromone amount of some items falls below the predefined lower bound τ min it is updated accordingly (lines 31 to 33). The algorithm terminates after nCycles and returns the so far global best computed solution S best (line 36).

V. EXPERIMENTAL RESULTS

This section present the performance evaluation of the proposed ACO-based workload consolidation algorithm. Thereby, in order to gain a first insight into the performance of the algorithm on large-scale before implementing it in a real environment, we have decided to conduct simulation-based experiments. Therefore, because of limitations of existing cloud computing simulation frameworks (e.g., CloudSim [START_REF] Calheiros | Cloudsim: A novel framework for modeling and simulation of cloud computing infrastructures and services[END_REF] only allows to move one VM per event, making it difficult to simulate global re-packing), we have developed our own Javabased simulation toolkit and used it to compare the ACO-based while IS = ∅ do 10:

Nv := {i | n-1 j=0 xi,j = 0 ∧ bv + ri ≤ Cv} 11: if Nv = ∅ then 12:
Choose item i ∈ Nv stochastically according to probability p i v :=

[τ i,v ] α ×[η i,v ] β u∈Nv [τu,v ] α ×[ηu,v ] β 13:
xi,v := 1 if q = 0 ∨ IsGlobalBest(S cycle ) then algorithm with the frequently applied FFD heuristic. Thereby, in order to improve the performance a multithreaded version of the ACO-based workload consolidation algorithm was developed. Furthermore, a modified version of the FFD heuristic has been implemented in order to consider the multidimensional character of the problem. Thereby, the VM resource demand vectors were sorted in decreasing order according to the L1norm.

We simulated a cluster composed of homogeneous hosts with each having a static resource capacity of 10000 MIPS, 24 cores, 50 GB of RAM, 1 TB storage and 10 GBit/sec network connection. Thereby, the amount of hosts was set to the amount of VMs in order to support the worst packing scenario, in which only one VM is assigned per host. In total, up to 600 VMs were simulated with each requiring either 1000, 2000, 3000 or 5000 of MIPS, 2 cores, 4 GB of RAM, 200 GB of storage and 1 GBit/sec of network bandwidth.

In order to estimate the energy consumed by a placement, we approximate the power of a host as a linear function P (u) in its current utilization u ∈ [0, 1] (see Eq. 10). P (u) = (P max -P idle ) × u + P idle [START_REF] Csorba | Ant system for service deployment in private and public clouds[END_REF] with P idle and P max being the average power values when the system is idle and fully utilized, respectively. Both values have been fixed to 171 and 218 Watt, for all simulations according to the measurements performed on our own testbed. The testbed we use is equipped with one Dell PowerEdge 1950 server plugged into a Sentry POPS (Per Outlet Power Sensing) switched Cabinet Distribution Unit (CDU). The machine comprises 4 GB of RAM and two Intel Xeon 5148 2.33 GHz CPUs, each having 2 cores. Idle power was derived by measuring the power drawn by the testbed machine when it only hosts the OS and the least amount of required system services (e.g., udev, sshd, etc.). Average peak power consumption was measured by running the stress benchmark application, with parameters set to stress all the system components. Finally, for estimating the energy consumed by a placement a time period t was defined and set to 24 hours. Consequently, the energy values represent the power drawn by the cluster at the utilization given by the placement over the period of 24 Thereby, it was assumed that idle machines are turned off after the workload consolidation. Hence, their idle power is not part of the total placement energy consumption. In particular, energy consumed by a placement was computed according to Eq. 11.

E(B) := t × n-1 v=0 P ( | bv|1 d ) if | b v | 1 = 0 0 otherwise (11)
Note, that because of the non-proportional power usage (i.e., high idle power) of traditional servers, no manner which energy model is used, turning off/suspending machines always yields to energy savings assuming that the algorithm is triggered during appropriate time periods (e.g., low utilization). Moreover, since the packing is based on peak resource demands, we assume that consolidated workloads will not suffer from significant performance degradation. Given such assumptions, consolidating the workload of for example two servers at 0.3 and 0.7 utilization, respectively, onto one server running at peak utilization (i.e., 1) is always advantageous. The parameters of the ACO-based algorithm were derived empirically through numerous simulations and finally set as depicted in Table I. Thereby, the amount of cycles and ants were finally initialized to 2 and 5, respectively, above which no improvement in the solutions could be observed. We run the simulation for up to 600 VMs and measured the amount of provisioned hosts, energy consumption of the placement and the average execution times for both algorithms (i.e., FFD and ACO-based). In addition, in order to judge the quality of the solutions, optimal solutions were computed by integrating the previously introduced BIP model into the highperformance Mixed-integer linear programming (MILP) solver IBM ILOG CPLEX v12.2 [START_REF]Ilog cplex: High-performance software for mathematical programming and optimization[END_REF]. Thereby, the solver was set to emphasis optimality and run in parallel mode with 4 threads.

In order, to derive the actual energy savings, the amount of energy spent for computing the placement was estimated by multiplying the execution time of the algorithm with average power drawn (i.e., 198 Watt) of the system during the simulation. The resulting amount of energy spent for the simulation was included into the final energy consumption of the placement and accounted not more than 400 Wh. Therefore, it did not impact the total energy results of the algorithms which were in the order of kWh. The final numerical simulation results are depicted in Table II. As it can be observed, computation time required to derive the placement and thus the energy spent in computation are higher using the ACO-based approach. This is because of our implementation which is far from being optimal while the used LP-solver (i.e., CPLEX) is highly optimized. In particular, 1.75 sec were required to compute the placement for the highest amount of VMs (i.e., 600) by the FFD and 2.01 hours by the ACO-based algorithm, resulting in 0.09 Wh and 397.98 Wh of energy spent in computation. Nevertheless, the solutions of the ACO-based approach utilize significantly lower amounts of hosts and thus yield to superior average host utilizations and energy gains. Thereby, on average 4.7% of hosts and 4.1% of energy were conserved by applying the ACO approach. Moreover, the solutions computed by the ACO-based approach are nearly optimal (i.e., small deviation of 1.1%). In addition, complexity of both evaluated algorithms is quadratic in the number of virtual machines, while CPLEX despite being highly efficient is exponential in the worst-case. Finally, it is worth mentioning that under a constrained number of hosts such as it is the case in a real system, FFD would need longer time to schedule the workload as it requires higher amounts of hosts. Consequently, the number of VMs which are required to reside in queues (i.e., non-allocatable) is higher when the FFD approach is applied.

VI. RELATED WORK

A lot of research has been done designing algorithms for solving instances of bin-packing problems, during the last three decades. Hence, a variety of exact algorithms and heuristics have been designed. Because of the NP-hard nature of the problem and the need to compute the solutions in reasonable time we focus our work and thus the related work on heuristic algorithms. These works can be divided into two categories: greedy algorithms (e.g., Best-Fit (BF), First-Fit (FF), Next-Fit (FF), Best-Fit Decreasing (BFD), First-Fit Decreasing (FFD), Permutation Pack (PP), Choose Pack (CP)) and evolutionary algorithms (e.g., genetic algorithms, ant systems).

In [START_REF] Coffman | Approximation algorithms for bin packing: a survey[END_REF], the authors survey the existing greedy algorithms for solving one-dimensional bin-packing problems. The approximability of the multi-dimensional bin-packing (MDBP) problem and the related Vector Bin-Packing (VBP) problem is studied in [START_REF] Chekuri | On multi-dimensional packing problems[END_REF]. Moreover, in [START_REF] Stillwell | Resource allocation algorithms for virtualized service hosting platforms[END_REF], the authors model the MDBP related resource allocation problem in virtualized service hosting environments and provide simulation-driven results for many state-of-the-art greedy algorithms (e.g., FF, BF, PP, CP). Thereby, the objective of the evaluated algorithms is to maximize the minimum yield over all services. Given such an objective, they identify the CP algorithm to be the most effective one. On the contrary, our objective is to minimize the amount of active servers.

In [START_REF] Levine | Ant colony optimisation and local search for bin packing and cutting stock problems[END_REF], the first evolutionary algorithm based on the Ant Colony Optimization (ACO) meta-heuristic was designed for solving one-dimensional bin-packing problems. The authors have shown that combined with a local search their algorithm could compete with the best known solution methods. This work has been further refined in [START_REF] Brugger | Antpacking an ant colony optimization approach for the one-dimensional bin packing problem[END_REF]. Thereby, an algorithm called AntPacking is proposed and shown to perform at least as good as the best genetic algorithm.

In [START_REF] Verma | pmapper: power and migration cost aware application placement in virtualized systems[END_REF], the authors model the workload placement as an instance of the one-dimensional bin-packing problem and apply a modified version of the FFD algorithm to perform the placement. In [START_REF] Li | Enacloud: An energysaving application live placement approach for cloud computing environments[END_REF], a framework called EnaCloud is proposed and a modified version of the Better-Fit algorithm is applied. Similar work can be found in [START_REF] Beloglazov | Adaptive threshold-based approach for energy-efficient consolidation of virtual machines in cloud data centers[END_REF], where the authors present simulation-driven results for a workload placement algorithm based on a modified version of the BFD algorithm and report substantial energy saving. More energy-aware workload placement approaches, which resort to the adaptation of simple greedy algorithms can be found in [START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF] and [START_REF] Lim | Padd: Power aware domain distribution[END_REF].

In [START_REF] Csorba | Ant system for service deployment in private and public clouds[END_REF], a virtual machine deployment framework for private and public clouds based on Ant Colony Optimization (ACO) is proposed. Thereby, the authors deal with the problem of how to efficiently deploy virtual machines images in the cloud. Particularly, this work aims at constructing balanced and dependable deployment configurations by the use of replication.

Our approach falls down into the same category of techniques (i.e., ACO-based). However, its objective is contrary as it targets to unbalance the workload in order to conserve energy. To the best of our knowledge this is the first work to: (1) apply ACO on the MDBP problem in the context of dynamic workload placement and (2) utilize ACO in order to conserve energy. Hence, unlike most of the introduced approaches dealing with the dynamic workload placement problem which consider only one resource (i.e., CPU) and resort to relatively simple resource-dissipative greedy algorithms [START_REF] Setzer | Decision support for virtual machine reassignments in enterprise data centers[END_REF], we accurately model the workload placement problem as an instance of the MDBP problem and take a natureinspired evolutionary approach to perform the placement. Our simulation results show that the ACO-based approach outperforms the evaluated greedy algorithm (i.e., FFD) as it achieves superior energy gains through improved resource utilization. Moreover, it computes solutions which are within 1.1% from the optimal and unlike CPLEX its complexity is quadratic in the number of virtual machines. Finally, contrary to simple greedy algorithms and LP solvers, the proposed algorithm can be implemented in a distributed manner, thus making it more suitable for scalability and fault-tolerance.

VII. CONCLUSIONS AND FUTURE WORK

In this paper, we propose a nature-inspired approach for solving the dynamic workload placement problem for present and future energy-aware Infrastructure-as-a-Service (IaaS) cloud computing environments. To the best of our knowledge this is the first work to apply artificial swarm intelligence on the MDBP problem in the context of dynamic workload placement and analyze its energy benefits. In particular, we have first accurately defined the workload placement problem as an instance of the multi-dimensional bin-packing (MDBP) problem by introducing a binary integer programming (BIP) model and proposed to use long-term history resource utilization measures in order to estimate future workload resource demands. We then have introduced a novel dynamic workload placement algorithm based on the Ant Colony Optimization (ACO) meta-heuristic to solve the introduced problem and compared it with one traditional greedy algorithm (i.e., FFD). Both algorithms have been implemented and experimentally validated by means of simulations. The results demonstrate that the artificial swarm intelligence based approach (i.e., ACO) provides superior energy gains than traditional workload placement based on the evaluated greedy algorithm and achieves nearly optimal results (i.e., 1.1% deviation). Particularly, on average 4.7% of hosts and 4.1% of energy were conserved by applying ACO. However, the savings came at the cost of increased computation time. Therefore, we conclude that complementarity between the two approaches should be exploited in order to increase the energy efficiency. For example, a FFD-based policy could be used to perform initial schedule of submitted VM batches, while the ACObased approach could run in background and optimize the placements on regular time intervals (e.g., daily or weekly basis). Moreover, FFD and other heuristics of the same category (e.g., Best-Fit, Next-Fit, etc.) are highly centralized. Hence, they fail to fulfill important properties such as scalability and fault tolerance. Even though our approach is also implemented in a centralized manner and its implementation is far from being optimal, the autonomous nature of ants allows to it be implemented in a fully distributed environment. Hence, avoiding single point of failure (SPOF) and providing good properties such as scalability and fault-tolerance.

Consequently, in the future we plan to design a distributed version of the algorithm and support hardware heterogeneity. In addition, despite the resource isolation properties of virtualization technology, co-location of workload with similar characteristics (e.g., memory intensive) on the same physical machine can lead to performance degradation even if no resource shortage exists as the caches are typically shared between the workload. Hence, we plan to adapt the algorithm in order to take into account workload characteristics. Finally, we plan to investigate approaches for accurate time estimations at which the algorithm should be triggered. Such estimations are necessary in order to prevent possible performance degradation because of migration and thus reduce the risk of Service Level Agreement (SLA) violation. This will enable the application of the algorithm in an real environment. Last but not least, we are currently working on a first prototype implementation of the previously proposed hierarchical and distributed workload (i.e., VM) consolidation manager called Snooze [START_REF] Feller | Snooze: A Scalable, Fault-Tolerant and Distributed Consolidation Manager for Large-Scale Clusters[END_REF]. The algorithm introduced in the present paper is part of this prototype and thus will be experimentally validated in the near future. Experiments will be performed on the Grid5000 testbed [START_REF] Cappello | Grid'5000: A large scale and highly reconfigurable grid experimental testbed[END_REF].

VIII. ACKNOWLEDGMENT

This research is funded by the french Agence Nationale de la Recherche (ANR) project EcoGrappe under the contract number ANR-08-SEGI-000.

Algorithm 1 3 : 4 : 8 :

 1348 Energy-Aware ACO-based Workload Consolidation 1: Input: Set of items I and set of bins B with their associated resource demand vectors ri and Cv respectively, Set of parameters 2: Output: Global best solution S best Initialize parameters, Set pheromone value on all item-bin pairs to τmax 5: for all q ∈ {0 . . . nCycles -1} do 6: for all a ∈ {0 . . . nAnts -1} do 7: IS := I; v := 0 Sa := [xi,j := 0], ∀i ∈ {0, . . . , m -1}, ∀j ∈ {0, . . . , n -1} 9:

  Sa according to the objective function f → Save cycle best solution as S cycle 22:

Fig. 1 .

 1 Fig. 1. Amount of utilized hosts and energy consumption


S Perruchot

F Bouchy

B Chazelas

R F Díaz

G Hébrard

K Arnaud

L Arnold

G Avila

X Delfosse

I Boisse

G Moreaux

F Pepe

Y Richaud

A Santerne

R Sottile

D Tezier

Higher-precision radial velocity measurements with the SOPHIE spectrograph using octagonal-section fibers

Keywords: Instrumentation, spectrograph, fiber-fed spectrograph, scrambling, octagonal fiber, radial velocity, exoplanets, asteroseismology

High-precision spectrographs play a key role in exoplanet searches using the radial velocity technique. But at the accuracy level of 1 m.s -1 , required for super-Earth characterization, stability of fiber-fed spectrograph performance is crucial considering variable observing conditions such as seeing, guiding and centering errors and, telescope vignetting. In fiber-fed spectrographs such as HARPS or SOPHIE, the fiber link scrambling properties are one of the main issues. Both the stability of the fiber near-field uniformity at the spectrograph entrance and of the far-field illumination on the echelle grating (pupil) are critical for high-precision radial velocity measurements due to the spectrograph geometrical field and aperture aberrations. We conducted tests on the SOPHIE spectrograph at the 1.93-m OHP telescope to measure the instrument sensitivity to the fiber link light feeding conditions: star decentering, telescope vignetting by the dome,and defocussing.

To significantly improve on current precision, we designed a fiber link modification considering the spectrograph operational constraints. We have developed a new link which includes a piece of octagonal-section fiber, having good scrambling properties, lying inside the former circular-section fiber, and we tested the concept on a bench to characterize near-field and far-field scrambling properties. This modification has been implemented in spring 2011 on the SOPHIE spectrograph fibers and tested for the first time directly on the sky to demonstrate the gain compared to the previous fiber link. Scientific validation for exoplanet search and characterization has been conducted by observing standard stars.

INTRODUCTION

High-precision radial velocity measurements are so far the main technique for search and characterization of exoplanetary systems. Up to date, almost 90% of the known extrasolar planets have been detected or established and characterized (for transiting planets) using this method. The sensitivity of this technique continuously increases, opening the possibility of exploring the domain of low-mass planets down to a few Earth masses as illustrated by the discoveries made by the state-of-art spectrograph HARPS [START_REF] Mayor | Setting new standards with HARPS[END_REF] with a radial velocity precision below 1 m.s -1 .

Far from being an old-fashioned technique, Doppler measurements will remain at the forefront of exoplanet science for the coming years thanks to their capability to explore the domain of low-mass planets down to Earth masses, to discover and characterize multiple planetary systems, to perform long-term surveys to find true Jupiter-like planets, to establish the planetary nature and to characterize the transiting candidates of photometric surveys. In the aim to reach Earth-type planets and, also measure the expansion of the universe, new spectrographs in the visible are now under study with the goal to reach in the near future a precision of only few cm.s -1 (ESPRESSO@VLT [START_REF] Pepe | ESPRESSO: the Echelle spectrograph for rocky exoplanets and stable spectroscopic observations[END_REF], CODEX@E-ELT [START_REF] Pasquini | Codex[END_REF]).

To reach such a level of accuracy, one must avoid a certain number of limitations. Among these, stellar noise (activity, pulsation, surface granulation), contamination by external sources (moon, close-by objects, background continuum), and changes in the spectrograph feed (e.g. atmospheric dispersion, turbulence, guiding and centering errors) [START_REF] Bouchy | Autoguider locked on a fiber input for precision stellar radial velocities[END_REF]. Unlike the "Iodine cell" calibration technique, which reduces the available spectral range (500-630 nm) and the throughput of the spectrograph, the "simultaneous Thorium" calibration technique allows a larger spectral range (380-680 nm) without flux losses, but it requires two fibers, one for the stellar beam and the other for the calibration lamp used to monitor the instrumental drift, assuming that both fibers follow exactly the same path inside the spectrograph. Additional instrumental factors, such as CCD cosmetics, charge transfer inefficiency, wavelength calibration errors, thermal instability effects, should also be mentioned. For an exhaustive discussion of these limitations, we refer to [START_REF] Pepe | From HARPS to CODEX: exploring the limits of Doppler measurements[END_REF], where the authors highlight the impact of the spectrograph illumination as one of the main limiting factors.

The high-precision fiber-fed SOPHIE spectrograph, operating at the 1.93-m telescope of the Haute-Provence Observatory since November 2006, reached a Doppler precision of about 5 m.s -1 , similar to other high-precision spectrographs involved in exoplanet surveys. SOPHIE plays a very efficient role in the search for northern extrasolar planets [START_REF] Bouchy | The SOPHIE search for northern extrasolar planets . I. A companion around HD 16760 with mass close to the planet/brown-dwarf transition[END_REF], as well as in the Doppler follow-up of photometric surveys for planetary transit searches like SuperWASP [START_REF] Collier Cameron | WASP-1b and WASP-2b: two new transiting exoplanets detected with SuperWASP and SOPHIE[END_REF], HAT [START_REF] Bakos | HAT-P-5b: A Jupiter-like Hot Jupiter Transiting a Bright Star[END_REF], CoRoT [START_REF] Barge | Transiting exoplanets from the CoRoT space mission. I. CoRoT-Exo-1b: a low-density short-period planet around a G0V star[END_REF] and Kepler [START_REF] Santerne | SOPHIE velocimetry of Kepler transit candidates. II. KOI-428b: a hot Jupiter transiting a subgiant F-star[END_REF].

A radial velocity precision of 5 m.s -1 , although well adapted for detection and characterization of giant exoplanets, is far to be appropriate for the low-mass planet domain like Super-Earth and Neptune which requires the 1-2 m.s -1 precision. We have found that SOPHIE is strongly limited by the insufficient scrambling gain of the fibers. The instrument set-up and the intrinsic properties of the fiber-link make the instrument very sensitive to observing conditions such as seeing, guiding and centering errors, and telescope vignetting (see section 2). To significantly improve the Doppler precision, we designed a fiber link modification taking into account spectrograph operational constraints. We have developed a new fiber link which includes a piece of octagonal-section fiber, having good scrambling properties, lying inside the former circular-section fiber, and we tested the concept on a bench to characterize near-field and far-field scrambling properties (see section 3). This modification has been implemented in June 2011 on the fiber links of the SOPHIE spectrograph and tested for the first time directly on the sky by observing standard stars to demonstrate the precision gain (see section 4).

SOPHIE AND ITS LIMITATIONS IN RADIAL VELOCITY 2.1 A brief description of the SOPHIE spectrograph

The SOPHIE architecture and design are fully described in [START_REF] Perruchot | The SOPHIE spectrograph: design and technical key-points for high throughput and high stability[END_REF]. See also Table 1 for a characteristics summary. The optical concept is a double-pass Schmidt echelle spectrograph installed in an isothermal environment associated with a high efficiency coupling fiber feeding system, including simultaneous wavelength calibration. Two observation channels are available: High Efficiency mode (HE) and High Resolution mode (HR), to obtain higher throughput or better radial velocity precision respectively. Each channel has two fibers: one for the target and the other for the sky or simultaneous calibration lamp exposure, the same as used in ELODIE [START_REF] Baranne | ELODIE: a spectrograph for accurate radial velocity measurements[END_REF]. Fibers have a diameter of 100 µm, leading to a resolution of 39 000 in HE mode. Resolution is increased to 75 000 in HR mode thanks to an exit slit (of width 40.5 µm). A doublescrambler (symmetrical doublets arranged to exchange object and pupil spaces) is included in the HR fiber link to homogenize the spectrograph entrance illumination.

Radial velocity precision limitations

Fiber-fed spectrographs such as HARPS or SOPHIE have a radial velocity precision limited by several error sources as described in [START_REF] Pepe | From HARPS to CODEX: exploring the limits of Doppler measurements[END_REF]. Among them, Doppler measurements are affected by atmospheric effects such as spectral dependent absorption or contamination, and chromatic flux variations mostly produced by the atmospheric dispersion combined with the varying seeing, as well as by varying atmospheric extinction. There are also instrumental effects whose amplitudes are linked to the architecture and design of the instrument: guiding, centering and focus stability, spectrograph illumination stability, instrument stability with regard to the environmental conditions, detector characteristics, wavelength calibration.

In the historical context of SOPHIE's development, its design was driven by the aim to significantly enhance (by a factor of 10) the instrument throughput compared to ELODIE, the previous spectrograph at the 1.93 m telescope, in addition to increased stability. This specification enforced a very compact design with few optical elements number and a large working aperture (f/3.6), which explains why SOPHIE geometric aberrations are large compared to those of HARPS.

Images are affected by field aberrations (especially distortion and coma because the fibers are far from the collimator axis) and aperture aberrations (spherical and astigmatism). Thus variations of illumination at fiber link output, in near field or in far field, have critical consequences on spectrum stability on the CCD. For this reason, SOPHIE is more sensitive than HARPS to illumination variations in the input fiber due to seeing variations or guiding and centering errors as already described in [START_REF] Boisse | Consequences of spectrograph illumination for the accuracy of radial-velocimetry[END_REF].

SOPHIE FIBER LINK MODIFICATIONS

Octagonal fibers: a way to improve scrambling efficiency

Despite the very successful results obtained with SOPHIE since the end of 2006, a precision better than 5 m.s -1 is required in the search for Super-Earth and Neptune-like exoplanets. As identified in previous section, improving the fiber scrambling properties before the spectrograph entrance is required to increase the precision obtainable with SOPHIE. As square and polygonal light pipes are a classical way to get more homogeneous illumination [START_REF] Fischer | Optical System Design[END_REF], such fibers have been considered for the next generation of precision radial velocity instruments as first proposed by P. Connes (1999 private communication). After promising simulations, Geneva Observatory , ESO and OHP teamed up to procure and characterize new fibers (octagonal or square sections from various manufacturers and dimensions), confirming the expected scrambling gain [15] [16].

Implementing octagonal fibers on the SOPHIE fiber links permits to test directly on the sky the increase in scrambling gain. Because of its very high sensitivity to variable illumination, SOPHIE is a good test bench for fiber-fed spectrographs to experiment new scrambling systems. To allow further understanding of the role played by the scrambling, the operation consisted in inserting a piece of octagonal-section fiber, lying inside the former circularsection fiber link, so that no other hardware is changed. The instrumental development consisted in two essential parts: validating the circular-octagonal-circular link in laboratory in terms of scrambling property (section 3.2) and implementing safely the new hardware (section 3.3).

Laboratory tests for fiber link losses and scrambling properties

Two properties had to be characterized in preliminary lab tests. First, the circular-octogonal-circular junctions should not affect too much the throughput of the spectrograph. Losses are a combination of effects: geometrical mismatch between circular and octagonal cores (~5%), decentering and misorientation at each junction, and Focal Ratio Degradation (FRD) due to constraints at the fibers terminations or some other effects. Second, the scrambling gain should be proved by comparison with a circular-only fiber link.

The circular-section fibers used in SOPHIE are Polymicro FVP100110125, with a core diameter of 100µm and a cladding diameter of 110µm. The octagonal-section fiber is a preform for an octagonal fiber of 70µm-core diameter from Ceramoptec; the preform octagon inner circle has a diameter of 100µm, the cladding is 187µm while the polyimide buffer is 210µm. We tried several techniques to join the octagonal fiber to the circular fiber. Core-to-core fusion splicing assures very good core alignment, but at a price of stress at the junction that produces FRD. Several tries on circular fibers gave inhomogeneous FRD results. We encountered many difficulties in splicing our octagonal fiber to the circular fibers essentially due to their very different cladding and buffer dimensions. We then decided to terminated this approach and to use FC to FC mating sleeves (available for instance in the Thorlabs® catalog). These mating components contain a centering ring, and the contact between fibers is maintained by a spring system inside the FC connectors. This connection achieves very good performance (excellent centering and very low FRD), possibly enhanced with indexmatching liquid to reduce Fresnel losses in case of non perfect optical core contact. See on Figure 2 (left) the measurements achieved with the experimental set-up described in Figure 1 for a circular-circular junction (pink curve) compared to a single circular fiber (blue curve).

Metallic FC connectors have been especially drilled to receive the octagonal fibers, but unfortunately the first set showed some obvious decentering. Laboratory tests (set-up Figure 1) showed that the induced losses with the connection to circular FC fibers were acceptable in SOPHIE for a temporary implementation in order to validate their scrambling properties. As can be seen in Figure 2 (left), FRD is increased with a circular-octagonal-circular link (green curve) compared to circular-only connections. But we obtained the same FRD even in the fusion spliced case than in the FC to FC mating sleeve case (Figure 2 right side); it should be noticed that in both cases the octagonal fiber was well decentered. This FRD is not yet well-understood.

Scrambling properties were measured in the Geneva Observatory facility; see Figure 3 and [START_REF] Chazelas | New scramblers for precision radial velocity: Square and octagonal fibers[END_REF] for a full description of the experimental set-up and measurement technique. The near field scrambling is measured using an image of the output of the fiber through a microscope objective. The beam at the fiber entrance is scanned across the core of the tested fiber assembly, simulating guiding errors in the telescope. The scrambling gain is defined as the ratio between maximum displacement of the barycenter of the near field illumination at the fiber output and the displacement of the spot at the fiber entrance.

We compared results between a SOPHIE-type circular fiber and an octagonal fiber that was fusion spliced inside a SOPHIE-type circular fiber (two splices). The Figure 4 illustrates the scrambling measurements. Table 2 summarizes the obtained scrambling gains. The use of an octagonal piece lying inside a circular fiber link is validated with a scrambling gain larger than a factor 10. We checked with a fusion spliced circular-section fiber assembly that FRD slightly increases the scrambling gain, even in near field. Furthermore one noticed that in a general way, the faster the beam, the lower the scrambling gain. This last property explains at least partially the lower scrambling gain of the f/3.6 SOPHIE spectrograph compared to HARPS (f/4) and ELODIE (f/5.6). There is also a slight scrambling gain in far field, identified as an FRD consequence.

All these laboratory results encourage us to implement octagonal fibers in the SOPHIE fiber links, expecting near-field scrambling gain without losing too much throughput (near 20%).

Figure 1. Experimental set-up in LAM (Marseille) for technical validation: images in intermediate space at fixed distance, fixed beam speed (f/3.6). Same set-up for every tested fiber assembly (octagonal fiber spliced to two circular fibers for instance). This allows relative FRD estimation, losses estimation and constraints detection by comparison to a reference fiber. The pinhole size can be chosen between an entire illumination of the fiber or half the fiber-diameter.

In situ implementation of octagonal fibers

Several possibilities are offered on the octagonal piece's localization on the HR fiber links: before, before and after or in the place of the optical double scrambler, the system that optically exchanges near field and far field as explained in [START_REF] Perruchot | The SOPHIE spectrograph: design and technical key-points for high throughput and high stability[END_REF]. Different results are expected as the octagonal fiber increases the scrambling gain only in the near field. Replacing the optical double scrambler has the advantage of reducing losses (about 20%) and attenuating guiding error effect and nearfield seeing impact; the HE channel will work in this mode. Having an octagonal piece before the scrambler offers the advantage to attenuate guiding error effects and near-field seeing impact on the spectrograph pupil space, while the spectrograph slit is not affected in near-field. Adding a second octagonal piece after the double scrambler allows reducing far-field effects on the spectrograph slit, at the price of second octagonal-circular junction loss.

We benefit from the very good performance of FC-FC connections with circular fibers to prepare the implementation of all those possibilities and add FC connectors in all interesting places as shown in the lower part of Figure 5. We paid attention to have a minimal fiber length of 45 cm to allow correct azimuthal scrambling from the circular pipes. SOPHIE is a fully operational instrument, with more than 90% of nights a year dedicated on the 1.93m -telescope. Each instrumental modification has to be implemented in a short time to avoid a too large lack of observations in the scientific programs, and with a risk management plan to reduce failure possibilities to a bare minimum. Insertion of octagonal fiber pieces is localized near the spectrograph entrance, where no fiber movement happens, constraining to work in the isothermal small space available. As the chosen junction technique is to interconnect FC connectors, each initial fiber had to be cut, bonded to a FC connector and polished in situ, requiring protection of all the spectrograph optics. No local diagnostic except microscope viewing of the polished surface was available during technical intervention. As the SOPHIE fibers at f/3.6 are very sensitive to constraints in the termination, a great part of the operation success was based on the extensive experience of our technician in handling these fibers.

INITIAL CONFIGURATION

For the first implementation of the modified SOPHIE fiber links in June 2011, we had available 1.5-m octagonal pieces that were slightly decentered in their FC connectors, as explained in section 3.2. Nevertheless, loss estimates (~20%) led us to validate the use of three of them for a temporary setup: two of them in front of the double scrambler on the HR channel, and one on the target HE channel, the calibration link being less crucial in principle. This configuration allows testing two operational modes, one direct on HE channel, and one with space exchange in HR channel. When wellcentered FC-connected octagonal fibers will be available, they will be implemented on each link, reducing losses, and other configurations could be tested on the HR channel.

Technical validation of the implementation was achieved by controlling the flux before and after the operation. This was done using a tungsten calibration lamp, allowing spectral loss control along the blaze with a precision better than 2-3%. Measured losses are -20%, -22% and -21% on HR star, HR calibration and HE star fiber link respectively, as estimated during laboratory tests considering geometrical and decentering losses on one hand, and FRD losses on the other hand.

NEW SOPHIE SPECTROGRAPH PERFORMANCE

We conducted systematic tests on the SOPHIE spectrograph at the 1.93-m OHP telescope to measure the instrument sensitivity to the fiber link light feeding conditions. These tests were performed before and after the new fiber links implementation.

Star decentering

We tested the sensitivity to guiding and centering effects on the fiber entrance with radial velocity sequences on standard stars. We fixed a given offset of the guiding system to impose a shift of the guiding set point to 1.0, 1.5 and 2.0 arcsec from the center of the fiber (3 arcsec diameter) in the four directions North, South, East and West. Figure 6 (Left) shows one sequence obtained with a seeing of about 1.8 arcsec using the HR mode with the initial configuration (showing RV variations reaching up to 30 m.s -1 with a guiding shift of 2 arcsec) and with the new fiber links configuration. Figure 6 (Right) compares the RV change as a function of the position of the center of gravity of the star image at the fiber entrance for both modes (HE and HR). The sensitivity to the guiding decentering is clearly reduced by at least a factor 6 in both modes with the new fiber links. With the typical precision of the guiding system (0.2-0.3 arcsec), we now do not expect RV changes larger than 1 m.s -1 due to guiding errors.

RV dispersion with standard RV stars

RV measurement precision was evaluated by sequences on the standard RV stars in HR mode, made before and after the implementation of the octagonal fibers. As shown on Figure 7, the new fiber links reduce the dispersion by a factor of about 6. Dispersion was 7.2 and 7.8 m.s -1 with the previous configuration for HD109358 (mv=4.3) and HD185144 (mv=4.7) respectively. With the new configuration, we obtained precisions over 20 days of 1.8 m.s -1 and 1.2 m.s -1 .

To go further, a seeing effect had been identified ( [START_REF] Boisse | Consequences of spectrograph illumination for the accuracy of radial-velocimetry[END_REF]), illustrating RV variations due to seeing conditions. Figure 8 shows the RV obtained on standard stars as a function of the seeing. The seeing factor is computed as the flux per unit of exposure time monitored by the spectrograph. We see a clear anti-correlation of the RVs with this seeing factor for the previous fiber configuration with an amplitude of up to 25 m.s -1 . With the new octagonal fiber the seeing effect seems to be negligible or at least smaller than 2 m.s -1 .

Defocussing and dome vignetting effects

We also tested the effect of a change in the far field of the fiber entrance illumination by defocussing the telescope or by vignetting of the telescope with the help of the dome.

RV changes up to +8 m.s -1 and about -5 m.s -1 in HR and HE modes respectively when about 40% of the telescope aperture is vignetted. We find the same amplitude using the new fiber link configuration as the previous one, as predicted since the octagonal fiber is not expected to affect the far field.

Testing the defocussing of the telescope is not equivalent to a seeing increase, but allows comparing the two fiber configurations with a test affecting both near and far field illumination. Increasing the apparent width of the star image from 2 arcsec up to 4-5 arcsec (controlled on the guiding camera) changed the corresponding RV in HE and HR modes up to -20 m.s -1 and +10 m.s -1 respectively. With the new fiber link configuration, the amplitude is slightly reduced to 12 m.s -1 and 3.5 m.s -1 respectively. This may confirm that defocussing affects probably both near and far field of the fiber illumination, but additional tests should be done to better characterize this effect.

Intrinsic calibration stability

We checked the intrinsic performances of the two SOPHIE fibers to measure the same instrumental drift. We computed the drift difference measured on each mode for both fibers using all the Thorium-Argon double calibration made during a full month before and after the implementation of the octagonal fibers. Figure 9 shows the dispersion of the drift difference. With the previous fiber link we found 2.27 m.s -1 rms and 0.57 m.s -1 for the HE and HR mode respectively, while with the new configuration we find 1.10 m.s -1 and 0.22 m.s -1 . For the HR mode, the gain in relative stability is a factor of more than 2.5, and only 2 for HE mode where one fiber link only is equipped with an octagonal fiber.

For comparison, the typical daily drift of the spectrograph is 20-30 m.s -1 . This means that in HR mode the two fibers follow the spectrograph drift with a precision 100 times better. Note also that the photon noise on ThAr spectra is estimated to about 10 cm.s -1 .

Figure 9. Radial velocity drift difference measured on fiber A (star channel) and B (calibration channel) for HE and HR mode before and after (+) the octagonal fibers implementation. The vertical scale is arbitrarily shifted to separate the four curves.

CONCLUSIONS AND PERSPECTIVES

We have successfully implemented octagonal-section fiber pieces in SOPHIE spectrograph fiber links using FC to FC mating sleeves. For the first time, the improvement by comparison with circular only-fiber links has been clearly demonstrated by tests directly on the sky with SOPHIE spectrograph. Scientific validation for exoplanet search and characterization has been started by observing standard radial velocity stars. The Doppler precision on a time scale of 20 days is better than 2 m.s -1 . Long term performance will be tested in the next months. We showed that the guiding, centering and seeing effects on the near field of the entrance fiber are reduced by more than a factor 6 thanks to the octagonal fiber and are now below 2 m.s -1 . The precision of the simultaneous drift measurement at 0.22 m.s -1 in HR mode is now close to the photon noise of the Thorium-Argon spectra. The better precision achieved allows further investigation of other instrumental effects at the level of 1 m.s -1 .

We will implement new octagonal links as soon as more convenient ones will be delivered to improve throughput by reducing decentering effects and maybe FRD losses. The new fiber link arrangement allows also further configurations as adding an octagonal fiber after the optical double scrambler (to stabilize far-field illumination if necessary) or replacing the scrambler itself by a unique octagonal fiber. Results shall be exploited in the SOPHIE context as effects are spectrograph-dependent.

Octagonal-section fibers open a very significant improvement of fiber-fed spectrograph dedicated to high-precision radial velocity measurements with the possibility to reach the 1 m.s -1 level. Future spectrographs now being developed like HARPS-North, SPIROU, and ESPRESSO will have benefit strongly from the use of such octagonal fiber link.

Figure 2 .Figure 3 .

 23 Figure 2. Cross sections of images obtained with the LAM set-up Figure 1. Left: comparison of links with FC to FCmating sleeves; note the FRD and the losses of the decentered octagonal link. Right: comparison between two circular-octagonal-circular fibers assemblies, both with decentered octagonal piece, the green curve with FC to FC mating sleeve connections, and the orange curve with fusion splice connections.

Figure 4 .

 4 Figure 4. Near Field scrambling measurements with Figure 3 set-up. Left: for a FVP circular fiber 100 µm. Right: for the octagonal piece fusion spliced between two pieces of circular fiber 100 µm. The points represent the barycenter displacements of the output near field during a scan of a 35µm -diameter spot at N=2.3 on the core of the tested fiber assembly, in units of 1000 th of fiber diameter. Red and Blue points are for the X and Y axis.

Figure 5 .

 5 Figure 5. SOPHIE fiber links before (upper part) and after (lower part) the modification of June 2011: octagonalsection fiber insertion.

Figure 6 .

 6 Figure 6. (Left) Sequence of radial velocity measurements with star decentering in HR mode with previous circular fiber links (black circle) and with the new links including octagonal fiber (black triangle). (Right) Radial velocity changes as a function of the position of the center of gravity (CG) of the star image at the fiber entrance in HE and HR modes with previous (circles) and new (triangles) fiber links configurations.

Figure 7 .

 7 Figure 7. Radial velocity sequences made the standard RV stars HD185144 (Left) and HD109358 (Right) before and after the octagonal fiber implementation (BJD = 2455720).

Figure 8 .

 8 Figure 8. Radial velocity changes as function of the seeing factor showing a clear correlation when the previous configuration is used (black circle).

Table 1 .

 1 Summary of SOPHIE instrumental characteristics up to June 2011

	Instrumental parameter	Value
	Fiber acceptance on the sky	3 arcsec
	Spectrograph working aperture	f/3.6
	Pupil diameter	200 mm
	Typical resolution power [HE / HR]	39 000 / 75 000
	Wavelength domain	387 nm -694 nm
	Number of spectral orders	39
	Pixel sampling per FWHM [HE / HR]	6.7 / 2.7
	Detector	1 CCD EEV 2kx4k (61 x 31 mm)
		Pixel size 15 µm
	Internal precision of the wavelength calibration	1 m.s -1
	Observed instrumental velocity error	5 m.s -1
	Efficiency at 390 nm [HE / HR]	4.6% / 1.9%
	Efficiency at 550 nm [HE / HR]	10.4% / 4.3%
	Efficiency at 690 nm [HE / HR]	8.3% / 3.5%
	(including atmosphere, telescope, Cassegrain adapter,
	fibers, spectrograph and CCD)
	S/N ratio per pixel at 550 nm	S/N = 100 in 1 hour on mag 11 (HE)
		S/N = 100 in 1 hour on mag 10 (HR)

Table 2 .

 2

		Circular fiber	Circ-circ-circ	Circ-octa-circ
			(fusion splices)	(fusion splices)
	Spot diameter 35µm, f/2.3	180	370	>2200
	Spot diameter 35µm, f/4	240	730	NA

Scrambling gain measured with Geneva bench for three fiber assemblies for 70-µm displacement of a 35µm diameter-spot.

ACKNOWLEDGEMENTS

The authors would like to thank all the staff of Haute-Provence Observatory for their contribution to the success of the SOPHIE upgrade and their support at the 1.93-m telescope. We wish to thank the Institut National des Sciences de l'Univers (INSU), the "Programme National de Planétologie" (PNP) of CNRS/INSU, the French National Research Agency (ANR-08-JCJC-0102-01) and the Swiss National Science Foundation for their continuous support to the SOPHIE project.

François Bouchy is grateful to Pierre Connes for all his useful advices on fiber scrambling.