Eugen Feller
email: eugenfeller@inria.fr

Christine Morin
email: christinemorin@inria.fr

Armel Esnault
email: armel.esnault@irisa.fr

A Case for Fully Decentralized Dynamic VM Consolidation in Clouds

Keywords: Cloud Computing, Dynamic Virtual Machine Consolidation, Ant Colony Optimization, Unstructured P2P Network, Virtualization

One way to conserve energy in cloud data centers is to transition idle servers into a power saving state during periods of low utilization. Dynamic virtual machine (VM) consolidation (VMC) algorithms are proposed to create idle times by periodically repacking VMs on the least number of physical machines (PMs). Existing works mostly apply VMC on top of centralized, hierarchical, or ring-based system topologies which result in poor scalability and/or packing eciency with increasing number of PMs and VMs.

In this paper we propose a novel fully decentralized dynamic VMC schema based on an unstructured peer-to-peer (P2P) network of PMs. The proposed schema is validated using three well known VMC algorithms: First-Fit Decreasing (FFD), Sercon, V-MAN, and a novel migration-cost aware ACO-based algorithm. Extensive experiments performed on the Grid'5000 testbed show that once integrated in our fully decentralized VMC schema, traditional VMC algorithms achieve a global packing eciency very close to a centralized system. Moreover, the system remains scalable with increasing number of PMs and VMs. Finally, the migration-cost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and requires less migrations than FFD and V-MAN.

Une approche complètement décentralisée pour la consolidation dynamique de VM dans les clouds Résumé : Une manière d'économiser l'énergie dans les centres de données est de mettre les serveurs inutilisés dans un mode de faible consommation d'énergie pendant les périodes de faible utilisation. Des algorithmes de consolidation dynamique de machines virtuelles ont été proposés pour créer des périodes d'inactivité en tassant les machines virtuelles sur le plus petit nombre possible de serveurs. Les travaux existants ont essentiellement appliqué les algorithmes de consolidation sur des topologies centralisée, hiérarchique ou fondée sur un anneau. Les approches proposées conduisent à un mauvais passage à l'échelle et/ou une faible ecacité en terme de quantité de serveurs libérés avec un nombre croissant de serveurs et de machines virtuelles.

Dans cet article, nous proposons un nouveau schéma de consolidation dynamique de machines virtuelles complètement décentralisé fondé sur un réseau pair-à-pair non structuré de serveurs. Le schéma proposé a été validé à l'aide de trois algorithmes de consolidation de machines virtuelles bien connus : First-Fit Decreasing (FFD), Sercon, V-MAN et d'un nouvel algorithme prenant en compte le coût des migrations et fondé sur une approche d'optimisation par colonies de fourmis. Plusieurs expériences menées sur la plate-forme Grid'5000 montrent qu'une fois intégrés à notre schéma complètement décentralisé, les algorithmes de consolidation de machines virtuelles traditionnels atteignent une ecacité globale en terme de nombre de serveurs libérés comparable à celle obtenue avec les systèmes communément utilisés fondés sur une topologie centralisée. En outre, le système passe à l'échelle avec un nombre croissant de serveurs et de machines virtuelles. Enn, l'algorithme prenant en compte le coût des migrations et fondé sur l'approche d'optimisation par colonies de fourmis se comporte mieux que les algorithmes FFD et Sercon en terme de nombre de serveurs libérés et nécessite moins de migrations que les algorithmes FFD et V-MAN.

Mots-clés : Cloud, consolidation dynamique de machines virtuelles, optimisation par colonies de fourmis, réseau pair-à-pair non structuré, virtualisation 1 Introduction

Cloud data center providers are now provisioning an increasing number of data centers to handle customers growing resource demands. Such data centers do not only require tremendous energy amounts to power their IT and cooling infrastructures but also impose scalability challenges on their system management frameworks. For example, according to [1] cloud computing services consumed approximately 662 billion kWh of energy in 2007. This is not surprising when considering today's public cloud providers data center scales. For instance, Rackspace which is one of the leading Infrastructure-as-a-Service (IaaS)

providers is estimated to host approximately 78 000 servers in 2012 [2].

While the system architecture details of Rackspace and other cloud providers (e.g. Amazon EC2) are not publicly available, several research attempts have been made in the last years on the design of energy-ecient VM management frameworks in order to ease the creation of private clouds. Energy eciency is typically obtained by transitioning idle physical machines (PMs) into a powersaving state during periods of low utilization. To facilitate the creation of idle times dynamic VM consolidation (VMC) can be used, whose objective is to pack the VMs on the least number of PMs while minimizing the number of migrations.

In contrast to static VMC which assumes empty PMs prior starting the VM to PM assignment, dynamic VMC starts from pre-loaded PMs. Starting from preloaded PMs adds a new dimension to the problem as it not only requires the number of PMs to be minimized but also the number of migrations required in order to arrive to the new VM-PM assignment. In other words, dynamic VMC is a multi-objective problem while static VMC is a single-objective problem.

Throughout the rest of the document we assume dynamic VMC when we refer to VMC.

VMC even in its single-objective variant is an NP-hard combinatorial optimization problem and thus is expensive (in time and space) to compute with increasing numbers of PMs and VMs. Consequently, choosing the appropriate system topology is crucial in order to obtain good scalability and packing eciency. Packing eciency is dened as the ratio between the number of released PMs to the total number of PMs. Existing VMC approaches either rely on centralized (e.g. [START_REF]Distributed Resource Scheduler (DRS)[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF][START_REF] Verma | pMapper: power and migration cost aware application placement in virtualized systems[END_REF]), hierarchical (e.g. [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF][START_REF] Graubner | Energy-Ecient Management of Virtual Machines in Eucalyptus[END_REF]), or ring-based [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF] system topologies. While the centralized topology yields to the best packing eciency, it suers from poor scalability due to the large amount of considered PMs and VMs. On the other hand, the hierarchical approach achieves better scalability through partitioning of PMs in groups and applying VMC only in the scope of the groups. However, this is achieved at the cost of decreased packing eciency as the VMC solutions remain local to the groups. Finally, in the ring-based approach PMs are organized in a ring and scheduling is performed event-based upon underload/overload detection by forwarding the VMC requests in the ring.

The scalability of this system is limited by the cost of ring-maintenance and its worst-case complexity which requires a full ring traversal to place the VMs.

This paper makes the following two contributions:

To address the scalability and packing eciency issues we propose a novel fully decentralized dynamic VMC schema based on an unstructured peer-topeer (P2P) network of PMs. In contrast to existing works our schema does not enforce any particular system topology shape. Indeed, the topology is RR n°8032

periodically modied to form random neighbourhoods of PMs. Considering the computational complexity of VMC we limit its application to the scope of the neighbourhoods. Moreover, the randomness of the system facilitates the convergence of the schema towards a global packing eciency very close to a centralized system.

We adapt our previously proposed ACO-based static VMC algorithm [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF] to minimize the number of VM migrations in the framework of dynamic VMC. Minimizing the number of migrations required to move from the current state (VM-PM assignment) to the newly computed one is crucial as each migration has a direct impact on the VM performance as well as the amount of data to be transferred over the network.

Both contributions are integrated within a distributed emulator along with three state-of-the-art greedy VMC algorithms, namely FFD, Sercon [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF] and V-MAN [START_REF] Marzolla | Server consolidation in Clouds through gossiping[END_REF]. Extensive evaluation performed on the Grid'5000 experimental testbed shows that once integrated all the evaluated algorithms achieve a global packing eciency very similar to a centralized system. Moreover, the migrationcost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and its solutions require less migrations than the ones from FFD and V-MAN (see Table 1). In [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] a centralized system called Entropy is introduced. Entropy employs constraint programming to solve the VMC problem using a centralized architecture. Both design choices result in limited scalability and make it suer from single point of failure (SPOF). A similar approach can be found in [START_REF] Verma | pMapper: power and migration cost aware application placement in virtualized systems[END_REF] which applies a greedy VMC algorithm on top of a centralized system architecture.

In our previous work [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF] we have introduced Snooze, a scalable and autonomic VM management framework based on a hierarchical architecture. Snooze currently relies on a greedy VMC algorithm called Sercon proposed by Murtazaev et al [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF]. VMC is only applied within groups of PMs thus allowing it to scale with increasing number of PMs and VMs. However, due to a lack of RR n°8032

inter-group coordination currently the VMC solutions remain local thus limiting the packing eciency of the system.

In [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF] a system based on a structured P2P network of PMs is presented. Each PM attempts to apply VMC event-based upon underload/overload detection by rst considering all the predecessor PMs and otherwise forwards the VMC request to the successor PM in the ring which repeats the procedure by considering itself and all its predecessor PMs. Besides the fact that the achievable packing eciency remains unclear when used with periodic VMC, its scalability is limited by the cost of the ring maintenance and its worst-case complexity which requires a full ring traversal to consolidate the VMs.

In contrast to all these works our schema does not rely on a static system topology but rather employs a fully decentralized dynamic topology construction schema. Particularly, the system topology is periodically and randomly modied through the exchange of neighbourhood information among the PMs to form random PM neighbourhoods. VMC is applied periodically only within the scope of the neighbourhoods. This property does not only allow the system to scale with increasing number of PMs and VMs but also facilitates the VMC algorithm convergence towards almost the same global packing eciency as of a centralized system. Finally, the schema is not limited to any particular VMC algorithm and supports heterogeneous PMs and VMs.

The closest work in terms of system architecture can be found in [START_REF] Marzolla | Server consolidation in Clouds through gossiping[END_REF] where the authors introduce V-MAN, a fully decentralized VMC schema. Similarly to our work V-MAN leverages randomized system topology construction and applies VMC only within the scope of the neighbourhoods. However, it is limited to a simple VMC algorithm which considers at most two PMs at a time. Moreover, it makes its decisions solely based on the number of VMs thus ignoring the actual VM resource demands. As our results show both design decisions yield to a large number of migrations. Finally, V-MAN as introduced is restricted to homogeneous servers (physical/virtual) and has been validated by simulation only.

3 Fully Decentralized Dynamic VM Consolidation This section presents our rst contribution: a fully decentralized dynamic VMC schema. First, the system assumptions and notations are introduced. Afterwards, the design principles are discussed and the system topology construction mechanism is detailed. Finally, the consolidation protocol is presented.

System Assumptions

We assume a data center whose PMs are interconnected with a high-speed LAN connection such as Gigabit Ethernet or Inniband. PMs hardware can be either homogeneous or heterogeneous. VMs can be live migrated between the PMs.

This work considers the dynamic VMC problem. Particularly, VMs are assumed to be running on the PMs and VMC is triggered periodically according to the system administrator specied interval to further optimize the VM placement.

RR n°8032

VM resource demands are assumed to be static. In other words, VMC decisions are based on the requested VM capacity as specied during VM deployment. Taking into account the actual resource usage could further improve the data center utilization. However, it is out of the scope of this work.

Notations

We now dene the notions used in this work. Let P denote the set of PMs and V p the set of VMs hosted by a PM p.

PMs are represented by d-dimensional total capacity vectors. Particularly, total capacity is dened as follows: TC p := {T C p,k } 1≤k≤d . In this work three dimensions are considered (d = 3). Each dimension k represents the PMs capacity of resource R k ∈ R with R being dened as R := {CP U, M emory, N etwork}.

VMs are represented by requested capacity vectors RC v := {RC v,k } 1≤k≤d with each component specifying the requested VM capacity of resource R k .

The total used PM capacity l p is computed as the sum of all VM requested capacity vectors: l p := ∀v∈Vp RC v .

Design Principles

Due to the NP-hardness of the VMC problem it is not sucient for a system to rely on a centralized server which executes the VMC algorithm. Indeed, to remain scalable and avoid SPOF with increasing numbers of servers (physical and virtual) a more distributed approach is desirable. Moreover, the system should compute VMC solutions which have a high packing eciency thus able to release a large number of PMs.

In order to achieve both scalability and high packing eciency we have designed a fully decentralized VMC system based on an unstructured P2P network of PMs. For scalability our system is built on top of the Cyclon protocol [START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF].

Cyclon is an epidemic membership protocol which allows to periodically construct time-varying randomized P2P overlays in which each PM has only a partial system view, the so-called neighbourhood. This property allows the system to scale with increasing number of PMs as it does not rely on a central server. PMs can join and leave the network at any time without the need to notify a central server.

The proposed system exploits the randomized neighbourhoods in order to achieve a high packing eciency by periodically applying the VMC algorithms only within the scope of the neighbourhoods. Thereby, as the partial views are modied periodically and randomly the entire system tends to converge towards a high packing eciency by solely making local VMC decisions within neighbourhoods thus eliminating the need of a central server.

System Topology Construction

The system topology construction mechanism is based on the Cyclon membership protocol. Cyclon has been designed for fast information dissemination while dealing with a high number of nodes that can join and leave the system. It is based on a periodic and random exchange of neighbourhood information among the peers, the so called shuing operation. Each peer maintains a local list of RR n°8032 neighbours, called cache entries. A cache entry contains the address (IP/port) and the age value of a neighbour. The role of the age eld is to bound the time a neighbour is chosen for shuing thus facilitating the early elimination of dead peers. The shuing operation is repeated periodically according to a parameter λt > 0. The resulting system topology can be viewed as a directed graph where vertices represent nodes and edges the relations. For example, X -→ Y means Y is a neighbour of X. Note, that the relations are asymmetric (i.e. Y is a neighbour of X does not imply that X is a neighbour of Y). More details on the system topology construction can be found in [START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF].

Consolidation Protocol

Each PM periodically triggers a consolidation process within its neighbourhood in order to optimize the VM placement. The process is composed of the following six steps:

1. First, PM p which initiates the consolidation checks whether it is not already under consolidation. If not it attempts to acquire a lock for each member (including itself ) of its neighbourhood. Otherwise, the consolidation is aborted. Locks are associated with all PMs in order to avoid concurrent access to PM resources in case of multiple ongoing consolidations. Acquiring a lock is a non-blocking operation. If it does not succeed, the member will not participate in the consolidation process.

RR n°8032

2. For each successful lock acquisition, PM p requests from the corresponding node its total capacity, currently packed VMs and their requested capacity vectors.

3. The VMC algorithm is started once all the resource information is received from the locked members. It outputs a migration plan (MP) which corresponds to the ordered set of the new VM-PM assignments. Any VMC algorithm can be used in this operation.

4. An actuation module on the PM enforces the MP by sending migration operations to the PMs hypervisors.

5. After the actuation all locks are released.

6. Each PM which does not accommodate VMs anymore power-cycles itself in order to conserve energy.

Ant Colony Optimization

Ant Colony Optimization (ACO) [START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF] is a probabilistic meta-heuristic for nding near optimal solutions to complex combinatorial optimization problems (e.g.

Design Principles

In our previous work [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF] we have applied ACO to solve the static VMC problem. ACO is especially attractive for VMC due to its polynomial worst-case complexity and ease of parallelization (i.e. ants work independently).

The key idea of the algorithm is to let multiple articial ants construct VMC solutions concurrently in parallel within multiple cycles. As the VMC model does not incorporate the notion of a path, ants deposit pheromone on each VM-PM pair within a pheromone matrix.

To choose a particular VM as the next one to pack in a PM a probabilistic decision rule is used. This rule is based on the current pheromone concentration information on the VM-PM pair and a heuristic information which guides the ants towards choosing VMs leading to better overall PM utilization. Hence, the higher the amount of pheromone and heuristic information associated with an VM-PM pair is, the higher the probability that it will be chosen.

RR n°8032

At the end of each cycle, all solutions are compared and the one requiring the least number of PMs is saved as the new global best solution. Afterwards, the pheromone matrix is updated to simulate pheromone evaporation and reinforce VM-PM pairs which belong to the so-far best solution.

In the following sections we describe the modications (marked bold) done to the original algorithm for considering the dynamic VMC problem. They involve the objective function, heuristic information, the pheromone evaporation rule and nally the algorithm pseudo-code.

Formal Problem Denition

The objective function (OF) we attempt to maximize is dened by Eq. 1. It takes as input the set of PMs and the migration plan (MP). MP denotes the ordered set of new VM to PM assignments.

max f (P, MP) := (nReleasedP M s) e × Var((|l p | 1 ) p∈P ) g × ( 1 |M P | ) m (1)
The OF is designed to favour the number of released PMs, the variance [START_REF] Goodman | The Variance of the Product of K Random Variables[END_REF] of the scalar valued PM used capacity vectors l p and smaller MPs. In other words, the higher the number of released PMs and the variance between the PMs used capacity vectors, the better it is. Indeed, one of our objectives is to release as many PMs as possible. Releasing PMs also helps to increase the variance which is an important indicator for increased resource utilization. In this work the L1 norm [START_REF] Weisstein | L1-norm[END_REF] is used to compute the scalar values. The second objective is to minimize the number of migrations. Consequently, we favour MPs with the least number of migrations. This is reected by dening the OF to be inverse proportional to the MP size. MPs with high number of migrations (i.e. VM-PM pairs) will lower its value, while smaller MPs will increase it.

Three parameters, e, g, m > 0, are used to either give more weight to the number of released PMs, MP size, or the PM load variance.

Probabilistic Decision Rule and Heuristic Information

The probability p v,p for an ant to choose a VM v to be migrated to PM p is dened in Eq. 2.

p v,p := [τ v,p ] α × [η v,p ] β v∈Vp [τ v,p ] α × [η v,p ] β , ∀v ∈ V, ∀p ∈ P (2)
where τ v,p represents the amount of pheromone associated with a particular VM-PM pair. η v,p denotes the heuristic information. Its denition is shown in Eq. 3.

η v,p, := κv,p |M P | if l p + RC v ≤ TC p 0 otherwise (3)
The key idea is to emphasize VM to PM migrations which yield in: high PM used capacity and are part of a small MP. Consequently, η v,p is dened as the ratio between κ v,p and the MP size in case the VM ts into the PM, and 0 otherwise. We use the constraint l p + RC v ≤ TC p to prevent new VMs from exceeding the total PM capacity.

To reward VMs which ll the PMs better κ v,p is dened as the inverse of the scalar valued dierence between the static PM capacity and the utilization of the PM after placing VM v (see Eq. 4). Consequently, VMs which yield to better PM used capacity result in higher κ v,p value.

κ v,p := 1 |TC p -(l p + RC v )| 1 (4)
Finally, two parameters, α, β ≥ 0 are used to either emphasize the pheromone or heuristic information.

Pheromone Trail Update

After all ants have computed a MP, the pheromone trail update rule is used to reward VM-PM pairs which belong to the smallest MP (M P gBest ) as well as to simulate pheromone evaporation on the remaining VM-PM pairs. The pheromone trail update rule τ v,p is dened in Eq. 5.

τ v,p := (1 -ρ) × τ v,p + ∆ best τv,p , ∀(v, p) ∈ V × P (5)
where ρ, 0 ≤ ρ ≤ 1 is used to control the evaporation rate. Consequently, higher values for ρ yield to faster pheromone evaporation. In order to reward VM-PM pairs which belong to the best MP, ∆ best τv,p is dened as the cycle-best VM- PM pheromone amount. Particularly, VM-PM pairs which belong to the best MP receive an increasing pheromone amount and thus become more attractive during subsequent cycles. Other pairs, which are not part of the best MP continue loosing pheromone and thus become less attractive.

The goal of the algorithm is to release as many PMs as possible using the least number of migrations. Consequently, it attempts to maximize the OF f . Therefore, ∆ best τv,p is dened to give f (P, M P gBest ) pheromone amount to VM-PM pairs (v, p) which belong to M P gBest , and 0 otherwise.

∆ best

τv,p :=

f (P, MP gBest ) if (v, p) ∈ M P gBest 0 otherwise (6)
Finally, to bound the pheromone amount on the VM-PM pairs, τ v,p is restricted to the range [τ min , τ max ].

Algorithm Denition

The pseudo-code is shown in Algorithm 1. It takes as input the set of PMs P including their associated VMs and a set of parameters (e.g. τ max , α, β, nCycles, nAnts) (line 1). The algorithm then sets the pheromone value on all the VM-PM pairs to τ max and iterates over a number of nCycles (lines 5 to 35 for all a ∈ {0 . . . nAnts -1} do 8:

Experimental Results

This section presents the evaluation results. First, the prototype implementation principles are introduced. Afterwards, the system setup is detailed and the results are discussed.

Prototype Implementation

To validate our work we have implemented a distributed Python-based VMCenabled Cyclon P2P system emulator. Each PM is emulated by a daemon which listens for TCP connections. One node serves as the introducer to bootstrap the system. To prevent concurrent access to PMs the prototype implementation integrates a distributed locking mechanism. PMs shutdown themselves when they do not host any VMs. VMs are represented by their requested capacity vectors. Each PM writes events (e.g. migration, consolidation, shutdown) in a local SQLite database during the experiment execution. Once the experiment is nished all databases are collected and merged into a single one for post-analysis.

Emulator modules such as the introducer mechanism, consolidation algorithms, scheduler for shuing and consolidation are dened in a conguration le for the ease of replacement.

The current implementation integrates four VMC algorithms: the FFD, Sercon, V-MAN state-of-the-art algorithms and the introduced migration-cost aware ACO-based algorithm. FFD is a static VMC algorithm which is often applied in the context of dynamic VMC. Consequently, it serves as the baseline for comparison in our work. In contrast, Sercon, V-MAN and our algorithm are dynamic VMC algorithms which were specically designed to reduce the number of migrations.

System Setup

We have deployed the emulator on 42 servers of the Grid'5000 testbed in France.

All servers are equipped with two CPUs each having 12 cores (in total 1008 cores). This allowed us to emulate one PM per core. In other words, throughout all the experiments each server hosts 24 emulator instances (one per core) which represent the emulated PMs.

The emulator considers three types of resources: CPU, memory, and network. It supports six kinds of VM instances: nano, micro, small, medium, large and xlarge, which are represented by their corresponding requested capacity vectors: (0.2, 0.5, 0.1), (1, 1, 1), (2, 1, 1), (4, 2, 2), [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] and [START_REF] Weisstein | L1-norm[END_REF][START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] respectively.

PMs have a total capacity of (48, 26, 20). They host 6 VMs, one of each type at the beginning of the experiment. Consequently, in total 6048 VMs are emulated. The experiment runs for six minutes. Consolidation is triggered by the PMs concurrently and independently every 30 seconds. The neighbourhood size is set to 16 PMs and the shuing operation is triggered every 10 seconds by the PMs. Table 2 provides a summary of the introduced system parameters and their corresponding values.

We run the emulator once for each of the evaluated algorithms: FFD, Sercon, V-MAN and the proposed ACO-based algorithm. The ACO algorithm parameters are shown in Table 3. They were derived empirically through numerous RR n°8032 VM requested capacity vectors (0.2, 0.5, 0.1), (1, 1, 1), (2, 1, 1), (4, 2, 2), [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF], [START_REF] Weisstein | L1-norm[END_REF][START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS, Concurrency and Computation: Practice and Experience[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] experiments. The evaluation is focused on: (1) analysis of the number of active PMs (packing eciency) and migrations;

(2) scalability of the system; and (3) comparison of the packing eciency with the centralized topology for all the VMC algorithms.

Number of Active PMs and Migrations

We rst analyze the number of active PMs. The results of this evaluation are shown in Figure 3.

As it can be observed the consolidation phase starts at the 30th second. FFD performs the worst as it only manages to release 246 nodes. V-MAN achieves the best result with 323 released PMs which is closely followed by the ACObased algorithm with 322 released PMs. Note, that Sercon performs worse than V-MAN and the ACO algorithm.

Figure 4 depicts the number of migrations with the progress of the experiment.

As it can be observed the number of migrations quickly converges towards zero with Sercon, V-MAN and the ACO algorithm thus demonstrating the good reactivity of our schema. Note, that the ACO algorithm requires more migrations than Sercon. Indeed, it trades the number of migrations for the amount of released PMs (see Figure 3). Finally, V-MAN performs the worst among the three dynamic VMC algorithms.

FFD yields in a tremendous amount of migrations (in total 96494). We explain this with the fact the algorithm is not designed to take into account the current VM-PM assignment. ment. This results a permanent movement of most of the VMs in each VMC iteration.

Scalability

To evaluate the scalability of our system we have varied the number of PMs from 120 to 1008 and analyzed the obtained packing eciency. The results are summarized in Table 4. As it can be observed, except the outlier with

V-MAN at 504 PMs, the packing eciency does not change signicantly with increasing numbers of PMs and VMs, thus demonstrating the good scalability of our schema. Another important metric to evaluate is the maximum number of migrations per VM during the whole duration of the experiment. In other words, due to the fully decentralized nature of the system and the random neighbourhood construction, VMs could traverse multiple PMs during subsequent consolidation rounds. As our results show, the maximum number of migrations per VM highly depends on the current VM-PM assignment and the VMC algorithm, less on the number of PMs and VMs. Particularly, in the current setup, Sercon requires at most one migration per VM. On the other hand, V-MAN results in at most 5 and ACO needs at most 9 migrations. Finally, FFD as it does not consider the current VM-PM assignment yields to the largest number of migrations. algorithms (FFD, Sercon, ACO) on a single PM. Note that, V-MAN is a decentralized algorithm thus its evaluation is not part of the centralized topology evaluation. More interestingly, our fully decentralized VMC schema achieves almost equivalent packing eciency for the evaluated algorithms when compared to the centralized topology. When considering the number of migrations, FFD achieves the worst result with 96494 migrations. We explain this with the fact that the algorithm by nature does not take into account the current VM-PM assignments. Consequently, its solutions result in a permanent reassignment of VMs within neighbourhoods during subsequent consolidation rounds.

Comparison with a Centralized System Topology

Our ACO-based algorithm outperforms FFD as well as Sercon in the number of released PMs and performs equal with V-MAN. However, the gains in the number of released PMs come at the cost of an increased number of migrations.

For example, when compared to Sercon twice as many migrations are required.

On the other hand, when considering V-MAN more than 150 migrations are saved by the ACO algorithm. This demonstrates that the ACO algorithm can serve as a competitive alternative to the other evaluated algorithms in the fully decentralized VMC schema.

Conclusions and Future Work

This paper has made two novel contributions. The rst contribution has introduced a fully decentralized dynamic VMC schema based on an unstructured P2P network of PMs. In contrast to existing works which mostly rely on static system topologies our system employs a dynamic topology which is built by periodically and randomly exchanging neighbourhood information among the PMs. VMC is periodically applied only within the scope of the neighbourhoods thus allowing the system to scale with increasing number of PMs and VMs as no global system knowledge is required. Moreover, the randomized neighbourhood RR n°8032 construction property facilitates the VMC convergence towards a global packing eciency very similar to a centralized system.

The second contribution has introduced a migration-cost aware ACO-based dynamic VMC algorithm. In contrast to our previously proposed ACO-based algorithm which solely focuses on minimizing the number of PMs, the novel algorithm also attempts to minimize the number of migrations required to move from the current to the newly computed VM placement.

We have implemented a distributed Python-based VMC-enabled Cyclon P2P

system emulator and used it to evaluate three state-of-the-art VMC algorithms, namely FFD, Sercon and V-MAN along with our migration-cost aware ACObased algorithm. The evaluation was conducted on a 42 node cluster of the Grid'5000 testbed which allowed to emulate up to 1008 PMs and 6048 VMs.

The results show that the proposed fully decentralized VMC schema achieves a global packing eciency very close to a centralized topology for all the evaluated algorithms. Moreover, the system remains scalable with increasing numbers of PMs and VMs. Finally, the proposed migration-cost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and requires less migrations than FFD and V-MAN when used in our fully decentralized VMC schema (see Table 1).

In the future we plan to integrate both works in our recently open-sourced holistic energy-ecient VM management framework called Snooze [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF]. This will allow taking into account the dynamic VM resource demands as well as to handle underload situations thus allowing to further improve the data center utilization. Another interesting area of work is to investigate the impact of the network topology choice on the system performance. In this context we will study how to improve the neighbourhood construction schema to build neighbourhoods taking into account the physical distance between the PMs.

Finally, additional VM constraints such as co-location and anti-colocation will be considered. Last but not least fault tolerance properties of the VMC schema will be evaluated.

Figure 1 Figure 1 :

 11 Figure 1 depicts an example system topology with six PMs (P M 1 , . . . , P M 6 ) and eleven VMs (V M 1 , . . . , V M 11 ) that are distributed among the PMs. The neighbourhood size is two. For the sake of simplicity a single resource number of cores is considered in this example: physical (PCORES) and virtual (VCORES). PMs are homogeneous and have ve PCORES. VMs can request one, two or three VCORES. The total capacity of PMs in the system is 30 PCORES. 19 PCORES are currently utilized, which corresponds to an utilization of approximately 63%.PM1

Figure 2

 2 Figure2illustrates the consolidation process using the topology introduced in Figure1. Starting from the initial state as shown in Figure1, P M 4 initiates the rst consolidation with its neighbours P M 3 and P M 5 . The result of this consolidation is shown in (1). V M 11 has been migrated from P M 4 to P M 5 and V M 6 & V M 7 have been migrated from P M 4 to P M 3 . P M 5 and P M 3 resources are now better utilized than in the previous conguration. Afterwards, P M 2 triggers a consolidation with its neighbours P M 1 and P M 6 . The result of this consolidation is shown in (2). V M 4 has been migrated from P M 2 to P M 1 . P M 1 is now fully utilized and P M 2 has become idle. Finally, in (3) P M 6 start another consolidation with P M 1 and P M 4 . V M 5 has been moved from P M 4 to P M 6 . The node P M 4 has now become idle and P M 6 better utilized. The nal system state with two released PMs (P M 2 and P M 4 ) is shown in[START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF]. It results in a new, almost global optimal data center utilization of approximately 95%.

  VMC). ACO design is inspired from the natural food discovery behaviour of real ants. Particularly, while traversing their environment ants deposit a chemical substance called pheromone. Other ants can smell the concentration of this substance on a certain path and tend to favour paths with a higher concentration. To favour the exploration of alternative paths pheromone evaporates after RR n°8032

Figure 2 :

 2 Figure 2: Example VM consolidation

Figure 3 :Figure 4 :

 34 Figure 3: Number of active PMs

Table 1

 1

		: Evaluation Summary
		Criteria #Migrations Packing eciency V-MAN ACO Sercon FFD Best algorithm 2nd 3rd 4th Sercon ACO V-MAN FFD
		This paper is organized as follows. Section 2 presents existing dynamic VMC
	works. Section 3 details the rst contribution, a fully decentralized dynamic
	VMC schema. Section 4 describes the second contribution, a migration-cost
	aware ACO-based dynamic VMC algorithm. Section 5 discusses the evaluation
	results. Finally, Section 6 closes this paper with conclusions and future work.
	2	Background
	Several dynamic VMC systems and algorithms have been proposed during the last years. In this work we distinguish between four types of systems: centralized, hierarchical, structured P2P, and unstructured P2P which integrate dierent
	types of algorithms (e.g. mathematical programming, greedy).

  Finally, if the newly computed score is greater than the local best score the local best score is updated and the VM-PM pair (v, p) is added to the local MP (lines 16 to 19). Note, that a VM is allowed to appear multiple times in the MP as long as it yields to a better score. After all ants have nished computing the MPs, they are compared according to the OF f . The cycle best MP is selected and saved as M P cBest (line 22). If the cycle best MP is also the global best one, it becomes the new global best one (lines 23 to 25). Finally, the pheromone values on all VM-PM pairs are updated by applying the pheromone trail update rule (see Eq. 5) and enforcing the τ min , τ max bounds (lines 26 to 34).

	source and destination PM capacity is then updated by removing the selected
	VM from the source and adding it to the destination PM (line 14). Afterwards,
	a score is computed by applying the OF (see Eq. 1) on the set of PMs P and
	the MP (line 15). The algorithm terminates after nCycles and returns the global best migration
	plan M P gBest (line 36).
	). In
	each cycle multiple (nAnts) ants compute MPs concurrently in parallel (lines 7
	to 21). The MPs accommodate at most |V M | migrations (line 10). Particu-
	RR n°8032

larly, rst the ants compute a probability p v,p for migrating a VM v to PM p for all VMs and PMs (line 11). Based on the computed probability they choose a VM-PM pair (v, p) stochastically and add it to the MP (lines 12 to 13). The Algorithm 1 Migration-cost Aware ACO-based Dynamic VMC 1: Input: Set of PMs P with their associated VMs, Set of parameters 2: Output: Global best migration plan M PgBest 3: 4: M PgBest := ∅ 5: Set pheromone value on all VM-PM pairs to τmax 6: for all q ∈ {0 . . . nCycles -1} do 7:

Table 2 :

 2 System parameters

	Parameter	Value
	Number of PMs	1008
	Number of VMs	6048
	Experiment duration	360s
	Consolidation interval	30s
	Shuing interval	10s
	Neighbourhood size	16 PMs
	Considered resources	CPU, memory and net-
		work
	Static PM capacity vector	(48, 26, 20)

Table 3 :

 3 ACO parameters

	α, β	ρ	τ min , τ max e, g, m nCycles nAnts
	0.1, 0.9	0.1	0.2, 1	5, 3, 1	2	2

  Particularly, due to its static nature it assumes that the PMs do not host any VMs prior computing the new VM-PM assign-

				Sercon	ACO	V-MAN	FFD
		1000
		800
	Number of active PMs	400 600
		200
		0	00:31	01:31	02:31 Time (min:sec) 03:31	04:31	05:31
	RR n°8032

Table 4

 4

	: Scalability Algorithm PMs VMs Released PMs Migrations per VM	Packing Eciency (%)
		120	720	29	26	24.1
	FFD	240 504	1440 3024	58 124	26 27	24.1 24.6
		1008	6048	246	26	24.4
		120	720	36	5	30.0
	ACO	240 504	1440 3024	77 161	7 8	32.0 31.9
		1008	6048	322	9	31.9
		120	720	39	3	32.5
	V-MAN	240 504	1440 3024	79 122	5 4	32.9 24.2
		1008	6048	323	4	32.0
		120	720	37	1	30.8
	Sercon	240 504	1440 3024	74 155	1 1	30.8 30.7
		1008	6048	311	1	30.8

Table 5

 5 depicts the results from the comparison of the number of migrations and packing eciency of our approach with the centralized topology for 1008 PMs and 6048 VMs. To simulate a centralized topology we have run the VMC

	RR n°8032

Table Centralized

 Centralized

	vs. Unstructured P2P Topology Topology Algorithm Migrations Released PMs Packing Eciency (%)
		FFD	6040	249	24.7
	Centralized	Sercon	1920	320	31.7
		ACO	-	-	-
		FFD	96494	246	24.4
	P2P	V-MAN	4189	323	32.0
		ACO	4015	322	31.9
		Sercon	1872	311	30.8

As it can be observed the ACO-based VMC algorithm is unable to compute a solution in a reasonable amount of time when used in the centralized topology for this kind of scale. Sercon on the other hand outperforms FFD in both the number of migrations (1920 vs. 6040) and released PMs (320 vs. 249). This is not further surprising as in contrast to FFD, Sercon is designed to minimize the number of migrations.

  System Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.4 System Topology Construction . . . . . . . . . . . . . . . . . . . 6 3.5 Consolidation Protocol . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Migration-cost Aware ACO-based Dynamic VM Consolidation 8 4.1 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . 8 4.2 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3 Formal Problem Denition . . . . . . . . . . . . . . . . . . . . . . 10 4.4 Probabilistic Decision Rule and Heuristic Information . . . . . . 10 4.5 Pheromone Trail Update . . . . . . . . . . . . . . . . . . . . . . . 11 4.6 Algorithm Denition . . . . . . . . . . . . . . . . . . . . . . . . . 11 5 Experimental Results 13 5.1 Prototype Implementation . . . . . . . . . . . . . . . . . . . . . . 13 5.2 System Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3 Number of Active PMs and Migrations . . . . . . . . . . . . . . . 14 5.4 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	2 Background 3 Fully Decentralized Dynamic VM Consolidation 3.1 5.5 Comparison with a Centralized System Topology . . . . . . . . . 6 Conclusions and Future Work 7 1 Introduction 7 Acknowledgements	3 4 5 16 16 17 18

RR n°8032

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

We would like to express our gratitude to Louis Rilling and Nikos Parlavantzas for their detailed feedbacks. This research is funded by the French Agence Nationale de la Recherche (ANR) project EcoGrappe under the contract number ANR-08-SEGI-008-02. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

for all (v, p) ∈ V × P do 27:


Antoine Coutrot

Nathalie Guyader

Gelu Ionescu

Alice Caplier

Influence of soundtrack on eye movements during video exploration

Keywords: multimodal, audio-visual, sound, eye movements, attention, videos

HAL is

Introduction

Over the past hundred years attention -the focus on one aspect of an environment while ignoring othershas become one of the most intensely studied topics within cognitive neurosciences.

Different studies tried to determine which part of signals captured by different senses (e.g. vision, hearing, touch) generates attention. In this field of research, most studies have been dedicated to visual attention. Since 1980, numerous visual attention models have been proposed [START_REF] Tsotsos | Modeling visual attention via selective tuning[END_REF][START_REF] Itti | A model of saliencybased visual attention for rapid scene analysis[END_REF][START_REF] Le Meur | Predicting visual fixations on video based on low-level visual features[END_REF]. These models break a visual signal down into several feature maps dedicated to specific visual features (orientation, spatial frequencies, intensity, etc.). In each map, the spatial locations that locally differ from their surroundings are emphasized. Then, maps are merged into a master saliency map, which points out regions that are the most likely to attract the visual attention of observers. Studies in cognitive neurosciences have established a close link between visual attention and eye movements. The premotor theory of spatial attention posits that visual attention and oculomotor system share the same neural substrate [START_REF] Rizzolatti | Reorienting attention across the horizontal and vertical meridians: Evidence in favor of a premotor theory of attention[END_REF]. This theory has been strengthened by recent neurophysiological experiments which have shown that intracranial subthreshold stimulation of several oculomotor brain areas results in enhanced visual sensitivity at the corresponding retinotopic location [START_REF] Belopolsky | When Are Attention and Saccade Preparation Dissociated[END_REF]. Although some other studies suggest a greater separation of the two processes [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF], the existence of a high correlation between eye movements and visual attention meets general consensus. This link between visual attention and eye movements allows authors to evaluate their visual attention models by comparing the predicted salient regions with the locations actually looked at by observers during an oculometric experiment [START_REF] Parkhurst | Modeling the role of salience in the allocation of overt visual attention[END_REF][START_REF] Itti | Quantifying the contribution of low-level saliency to human eye movements in dynamic scenes[END_REF][START_REF] Le Meur | Predicting visual fixations on video based on low-level visual features[END_REF]. These models were initially built for static images, but since motion plays a very important role in visual attention [START_REF] Yantis | Abrupt Visual Onsets and Selective Attention: Evidence From Visual Search[END_REF], they rapidly evolved to be used with videos [START_REF] Carmi | Visual causes versus correlates of attentional selection in dynamic scenes[END_REF][START_REF] Marat | Modelling Spatio-Temporal Saliency to Predict Gaze Direction for Short Videos[END_REF]. All the cited models are bottom-up (i.e. based on stimulus properties), and hence are particularly suitable for dynamic stimuli: the constant appearance of new salient regions promotes bottom-up influences at the expense of top-down strategies (i.e. induced by the subject), making models more stable over time. Indeed, the high consistency of eye movements when watching dynamic scenes both within and across observers is a characteristic that is often outlined in the literature [START_REF] Goldstein | Where people look when watching movies: Do all viewers look at the same place?[END_REF]Hasson et Coutrot, Guyader, Ionescu & Caplier (2012). Soundtrack & eye movements al., 2008;[START_REF] Dorr | Variability of eye movements when viewing dynamic natural scenes[END_REF]. Aside from motion, other features such as faces or top-down influences have been integrated into visual attention models [START_REF] Torralba | Contextual guidance of eye movements and attention in real-world scenes: The role of global features in object search[END_REF]Marat, Guyader, & Pellerin, 2009). However, these features always belong to visual modality. When using eye tracking and dynamic stimuli, authors do not mention the soundtracks or explicitly remove them, making participants look at "silent movies" which is far from natural situations. Up to now, the influence of sound on eye movements has been left aside. , 1976). Another well-known audio-visual interaction is the help given by "lip reading" to understanding speech, even more when speech is produced in poor acoustical conditions or in a foreign language [START_REF] Jeffers | Speechreading (lipreading)[END_REF][START_REF] Gailey | Psychological parameters of lip-reading skill in hearing by eye: The psychology of lip-reading[END_REF][START_REF] Summerfield | The central fixation bias in scene viewing: Selecting an optimal viewing position independently of motor biases and image feature distributions[END_REF]. Studies have shown that when presenting audio-visual monologues, perceivers gazed more at the mouth as auditory masking noise levels increased [START_REF] Vatikiotis-Bateson | Eye movement of perceivers during audiovisualspeech perception[END_REF].

Besides these perceptual phenomena, some studies have tried to develop models of cross-modal integration. To this end, influences of competing visual and auditory stimuli on different behavioural measurement and on the shifts of gazes have been examined. Authors showed that speed and accuracy of eye movements in detection tasks were improved when using a congruent audio-visual stimulus compared to a mere visual or auditory stimulus [START_REF] Corneil | The influence of auditory and visual distractors on human orienting gaze shifts[END_REF][START_REF] Mcdonald | Involuntary orienting to sound improves visual perception[END_REF][START_REF] Corneil | Auditory-visual interactions subserving goaldirected saccades in a complex scene[END_REF][START_REF] Arndt | Two stages in crossmodal saccadic integration: evidence from a visual-auditory focused attention task[END_REF]. In their study, Quigley, Onat, Harding, Cooke and Konig (2008) presented static natural images and spatially localized (left, right, up, down) simple sounds. They compared eye movements of observers when viewing visual only, auditory only or audio-visual stimuli. Results indicated that eye movements were spatially biased towards the regions of the scene corresponding to the sound sources. However, spatial localization is not necessary to observe the influence of sound on visual attention.

One study [START_REF] Burg | Pip and pop: Nonspatial auditory signals improve spatial visual search[END_REF] stated that a nonspatial auditory signal improved spatial visual search. The correct mean reaction time was up to 4 seconds shorter (depending on the number of distractors) when a nonspatial beep was synchronized with the visual target change. After controlling alternative explanations of the so-called pip and pop phenomenon (an auditory "pip" makes the visual target pop out), the authors proposed that the temporal information of the auditory signal directly interacted with the synchronous visual event. As a result, the visual target became more salient within its environment.

Nonspatial auditory information has also been used with visual saliency to generate video summaries [START_REF] Rapantzikos | An audio-visual saliency model for movie summarization[END_REF][START_REF] Evangelopoulos | Video event detection and summarization using audio, visual and text saliency[END_REF]. In these studies, authors computed and coupled visual and auditory saliencies to detect the most salient frames, chosen to make up the video summary.

Apart from one preliminary study discussed below [START_REF] Song | Sound effect on visual gaze when looking at videos[END_REF], the influence of non-spatialized sound on eye movements made by observers watching videos has never been explored.

To investigate that issue, we checked if eye movements of observers changed when looking at videos with their original soundtracks and without any sound. We compared the regions fixated in the scenes as well as eye movement parameters such as saccade amplitude and fixation duration.

Methods

Participants

Participants were made up of 40 undergraduate and PhD students from the University of Grenoble (France): 26 men and 14 women, ages ranging from 20 to 29 years (M = 25.3, SD = 2.7). Participants were not aware of the purpose of the experiment and gave their consent to participate. This study was approved by the local ethics committee. All were French native speakers, had a normal or corrected to normal vision and reported normal hearing.

Apparatus

Participants were seated 57 cm away from a 21 inch CRT monitor with a spatial resolution of 1024 x 768 pixels and a refresh rate of 75 Hz. The head was stabilized with a chin rest, forehead rest and headband. The audio signal was presented via headphones (HD280 Pro, 64Ω, Sennheiser). Participants wore headphones during the whole experiment, even when the stimuli were presented without soundtrack. Eye movements were recorded using an eyetracker (Eyelink 1000, SR Research) with a sampling rate of 1000 Hz and a nominal spatial resolution of 0.01 degree of visual angle. Thus, an eye position was recorded every millisecond in binocular "pupil -corneal reflect" tracking mode. Each experiment was preceded by a calibration procedure, during which participants focused their gaze on 9 separate targets in a 3 x 3 grid that occupied the entire display. A drift correction was carried out between each video, and a new calibration was done at the middle of the experiment and if the drift error was above 0.5 ˚.

Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements

Stimuli

We chose 50 video sequences with their original soundtracks. When the soundtrack contained speech, it was always in French. Several studies showed that eye movements are impacted by movie editing style [START_REF] Dorr | Variability of eye movements when viewing dynamic natural scenes[END_REF]. Here, we chose only extracts from professional movies (action movies, drama, documentary films, dialogues). Each video sequence has a resolution of 720 x 576 pixels (30 ˚x 24 ˚of visual angle) and a frame rate of 25 frames per second. They last from 0.9 s to 35 s (M = 8.7 s; SD = 7.2 s). As a whole, video sequences last 23.1 min. As explained in the introduction, we chose to focus on the influence of nonspatial sound on eye movements, hence, we used monophonic stimuli. For the cases (41 out of 50 videos) where the original audio signal was stereo, we added the two channels and sent the result to both headphones. Most of the video sequences we used were made of several shots, separated from each other by shot cuts. A shot cut is an abrupt transition from one shot to another that greatly impacts visual exploration (Garsoffky, Huff, & Schwan, 2007;[START_REF] Smith | A Window on Reality: Perceiving Edited Moving Images[END_REF]. Thus, we did not study whole videos but we analyzed each shot. Shots were automatically detected using the pixel by pixel correlation value between two adjacent video frames. We ensured that the shot cuts detected were visually correct. Sequences contained different number of shots, with a total number of 163 shots. In the analyzes, we separated the first shot of each video (50 shots) from the others (113 shots) because the central fixation cross preceding each video biased gazes at the beginning of the first shot.

Procedure

The experiment was designed using a software named SoftEye [START_REF] Ionescu | SoftEye software[END_REF]. It is a flexible software that allows the stimulus presentation to be synchronized with the eyetracker. It releases, in a single file, all the required data for further analysis: eye positions, events (saccades, fixations and blinks) detected by the Eyelink system, stimulus beginning and ending. Figure 1 illustrates the time course of experimental trials. Before each video sequence, a fixation cross was displayed in the center of the screen for 1 second. After that time, and only if the participant looked at the center of the screen (gaze contingent display), the video sequence was played on a mean grey level background. Between two consecutive video sequences a grey screen was displayed for 1 second. Participants had to look freely at 50 videos. In order to avoid any order effect, videos were randomly displayed. Twenty participants saw the first half of videos in the visual condition (i.e. without any sound) and the other half in the audio-visual condition (i.e. with their original soundtracks), with a small break in between. Stimulus conditions (Visual and Audio-Visual) were counterbalanced between participants. Finally, To control the gaze of observer, a fixation cross is presented at the center of the screen. Then, a video sequence is presented in the center, followed by a grey screen. This sequence is repeated for the 50 videos, one block of 25 videos without sound (Visual condition) and the other block with their original soundtracks (Audio-Visual condition).

each video sequence was seen in the visual condition by 20 participants and in the audio-visual condition by 20 other participants.

Analysis

Data

We discarded data from four subjects due to recording problems.

Eye positions per frame

We only analyzed the guiding eye of each subject. The eye tracker system gives one eye position each millisecond, but since the frame rate is 25 frames per second, 40 eye positions per frame and per participant were recorded. In the following, an eye position is the median position that corresponds to the coordinates of the 40 raw eye positions recorded per frame and per subject. Frames containing a saccade or a blink were discarded from eye position analysis. For each frame and each stimulus condition, we discarded outliers, i.e. eye positions above ±2 standard deviations from the mean.

Saccades, fixations and blinks

Besides the eye positions, the eye tracker software organizes the recorded movements into events: saccades, fixations and blinks. Saccades are automatically detected by the Eyelink software using three thresholds: velocity (30 degrees/s), acceleration (8000 degrees/s 2 ) and saccadic motion (0.15 ˚). Fixations are detected as long as the pupil is visible and as long as there is no saccade in 5(4):2, 1-10 Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements progress. Blinks are detected as saccades with a partial or total occlusion of the pupil. We did not use them in this analysis. For each stimulus condition, we discarded outliers, i.e. saccades (resp. fixations) whose amplitude (resp. duration) was above ±2 standard deviations from the mean. We separated the recorded eye movements into two sets of data. First, the data recorded in the audio-visual (AV) condition, i.e. when videos were seen with their original soundtrack. Then, the data recorded in the visual (V) condition, i.e. when videos were seen without sound.

Metrics

Dispersion To estimate the variability of eye positions between observers, we used a measure called dispersion. For a frame and for n participants (thus n eye positions p = (x i , y i ) i∈[1.

.n] ), the dispersion D is defined as follows:

D(p) = 1 n(n -1) n ∑ i=1 n ∑ j=1 j =i (x i -x j ) 2 + (y i -y j ) 2
In other words, the dispersion is the mean of the Euclidian distances between the eye positions of different observers for a given frame. If all participants look at the same location, the dispersion value is small. On the contrary, if eye positions are scattered, the dispersion value increases. Note that this metric has some limitations: there might be more than one region of interest, and thus, eye position cluster around these regions. Hence, the dispersion would increase even though eye positions are located in the same few region of interest. In this analysis, we computed a dispersion value for each frame of the 163 shots. First, we took the mean dispersion over all frames (global analysis). Then, we looked at the frame by frame evolution of dispersion (temporal analysis). For both analyses, we compared the dispersion within conditions (intra V and AV dispersions) and the dispersion between stimulus conditions (inter dispersion). If soundtrack impacts on eye position dispersion, we should find a significant difference between the mean intra AV and V dispersions.

Distance to center

The distance to center is defined as the distance between the barycenter of a set of eye positions and the center of the screen. This distance reflects the central bias, and we analyzed its evolution along shots. The central bias expresses the fact that when exploring visual scenes, the gaze of observers is often biased toward the center of the screen. In this analysis, we computed a distance to center value for each frame of the 163 shots in each stimulus condition.

KL-divergence

The Kullback-Leibler divergence is used to estimate the difference between two probability distributions. This metric can be compared as a weighted correlation measure between two probability density functions. It was already used to compare distributions of eye positions [START_REF] Tatler | Visual correlates of fixation selection: effects of scale and time[END_REF][START_REF] Le Meur | Predicting visual fixations on video based on low-level visual features[END_REF][START_REF] Quigley | Audio-visual integration during overt visual attention[END_REF]. The KL-divergence (KLD) between two distributions Q a and Q b is defined as follows, with p the size of the distributions:

KLD(Q a , Q b ) = 1 2 p ∑ i=1 Q a i log Q a i Q b i + p ∑ i=1 Q b i log Q b i Q a i
The lower the KL-divergence is, the closer the two distributions are.

In this analysis, we computed, for each frame of the 163 shots, two density maps (one for each condition): Q V and Q AV . For a given frame, a 2D Gaussian patch (one degree wide) was added to each eye position. These maps are the same size as video frames (p = 720 x 576 pixels) and are normalized to a 2D probability density function. Then, we computed the KL-divergence between Q V and Q AV (inter KL-divergence): the lower the KL-divergence is, the closer the two maps are, and the more the participants in V and AV conditions tend to look at the same positions. First, we took the mean KL-divergence over all frames (global analysis). Then, we looked at the frame by frame evolution of KL-divergence (temporal analysis). For each analysis, we compared the inter KLdivergence with the KL-divergence between two maps drawn from two random sets of eye positions. We also compared the inter KL-divergence with the intra V and AV KL-divergences, defined as the KLdivergence between two maps drawn from the eye positions recorded under the same stimulus condition. These maps were created by randomly splitting each dataset of 20 participants in two subgroups of 10 participants. We repeated this random split 10 times and took the mean KL-divergence. If soundtrack impacts on eye position locations, we should find a significant difference between the mean inter and intra KL-divergences. Dispersion and KL-divergence are two complementary metrics. Dispersion provides information about the variability between eye positions, but does not tell anything about the relative position of the two data sets of eye positions for the two stimulus conditions. For the KL-divergence, it is the opposite.

Results

The aim of this research is to quantify the influence of soundtrack on eye movements when freely exploring videos. To this end, we compared the eye movements recorded on video sequences seen in visual (V) and audio-visual (AV) conditions, using different metrics. First, we analyzed the eye positions of participants (dispersion and Kullback-Leibler divergence). Then, we focused on two eye movement parameters: saccade amplitude and fixation duration. 5(4):2, 1-10 Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF] Inter V-AV Intra AV Intra V 1.5

1.6 1.7

1.8

1.9

KL-divergence

Figure 3. Mean Kullback-Leibler divergence between the eye position distributions in the V and AV conditions (blue), between two sets of eye positions extracted from the AV (green) and the V (red) conditions. Error bars correspond to standard errors.

Eye position variability (dispersion)

Global analysis We compared the mean dispersion for all the 163 shots according to three conditions (see Figure 2): Intra AV (green bar), Intra V (red bar) and Inter (blue bar). We performed t-test on the mean dispersions for 163 observations (video shots). The dispersion is lower for the AV condition than for the V (t(324)=2.17, p < 0.03) and the Inter V-AV condition (t(324)=1.97, p < 0.05). This result means that on average, there was less variability between the eye positions of observers when they explored videos with their original soundtracks.

We also performed a mixed-factor ANOVA, with the stimulus condition (V and AV) the within-subjects factor and stimulus condition order (AV-V and V-AV) the between-subjects factor. It revealed that the stimulus condition order had no effect.

Temporal analysis Since we worked on dynamic stimuli, it is interesting to analyze the temporal evolution of the dispersion along shots to see how the influence of sound evolves along video shots exploration. On the left side of Figure 4, the temporal evolution of the dispersion and of the distance to center are plotted, averaged over all the shots except the first ones, i.e. the shots that were not impacted by the central cross before video onset.

During the first 3 frames after a shot cut, the dispersion (resp. the distance to center) is stable. During this period, the gaze of observers stays at the same locations as before the cut. Then, from frame 4 to 10, the dispersion and the distance to center dip deeply. From frames 11 to 25, curves both increase regularly. This leads to the last stage where the dispersion (resp. the distance to center) fluctuates around a mean stationary value.

The temporal evolution of the dispersion and of the distance to center averaged over all the first shots are slightly different (see the right side of Figure 4). Before each video, participants were asked to look at a fixation cross in the center of the screen. Hence, during the 3 first frames, both the dispersion and the distance to center are low in both AV and V conditions (as previously, gazes stay at the same locations as before the cut, i.e. at the center of the screen). Then, curves increase linearly and reach a plateau, which was identical to previously in the left-hand plots, except that the mean value is here slightly higher.

The following statistics are performed on all 163 shots. Until the 25 th frame (∼1 s), no clear distinction can be made between V and AV conditions: the red and green curves overlay each other. However, after that (i.e. when the curves have stabilized) the mean value of dispersion in V condition is significantly above the one in AV condition (t-test: from frame 1 to 25 : t(324)=1.85, n.s.; from frame 25 to end : t(324)=2.06, p < 0.05).

For the distance to center, the opposite occurs: during the stabilized phase, the AV condition curve is mostly above the V condition curve. Nevertheless, this relation is not statistically significant. Note that the separation before vs. after frame 25 is not a clean-cut classification, but is estimated from the shapes of the dispersion and distance to center curves. To sum up, around one second after shot onset, participants in AV condition are less dispersed than participants in V condition. Moreover, participants in AV condition tend to look away from the screen center more than participants in V condition. These results will be further discussed.

Eye position locations (KL-divergence)

Global analysis We compared the mean KLdivergence for all the 163 shots according to 3 conditions (see Figure 3): Intra AV (green bar), 5(4):2, 1-10 Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements 0 10 20 30 40 50 60 In blue, the KL-divergence between the V and AV conditions. In red, the KL-divergence within the V condition. In green, the KL-divergence within the AV condition. For the inter KL-divergence, the error bars are standard errors. For the intra KL-divergences, the error bars are calculated on the KL-divergence values averaged over the ten random sets of eye positions within each stimulus condition. 5(4):2, 1-10

Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements Intra V (red bar) and Inter (blue bar). The random KL-divergence (M = 6.13) is high above the others and is not plotted. We performed t-test on the mean KL-divergences for 163 observations (video shots). The KL-divergence is higher for the Inter condition than for the Intra AV (t-test: t(324)=2.27, p < 0.05) and V conditions (t(324)=1.69, p < 0.05). This result means that on average, sound impacts the fixated locations. The congruency between fixation locations is higher inside respective both conditions than between the two different stimulus conditions.

Temporal analysis Figure 5 presents the frame by frame Inter KL-divergence (in blue), Intra V KLdivergence (in red), and Intra AV KL-divergence (in green). The KL-divergence temporal evolution follows the same pattern as the dispersion: during the first 25 frames, no distinction can be made between intra and Inter KL-divergences. However then, the Inter KLdivergence is significantly above the Intra AV and V KL-divergences (respective t-test: from frame 1 to 25, t(324)=1.55, n.s. and t(324)=1.21, n.s.; from frame 25 to end, t(324)=2.1, p < 0.05 and t(324)=1.94, p < 0.05).

Fixations and saccades

We analyzed the distributions of fixation duration and saccade amplitude made by participants in V and AV conditions. In both stimulus conditions, both parameters follow a positively skewed, long-tailed distribution, which is classical when studying such parameters during scene exploration [START_REF] Bahill | Most naturally occurring human saccades have magnitudes of 15 degrees or less[END_REF][START_REF] Pelz | Oculomotor behavior and perceptual strategies in complex tasks[END_REF][START_REF] Tatler | The long and the short of it: Spatial statistics at fixation vary with saccade amplitude and task[END_REF][START_REF] Tatler | Systematic tendencies in scene viewing[END_REF][START_REF] Ho-Phuoc | When viewing natural scenes, do abnormal colours impact on spatial or temporal parameters of eye movements[END_REF]. We performed paired t-test on median saccades amplitude and median fixation duration for 36 observations (participants). We observed shorter saccade amplitudes in V condition (Mdn = 3.01 ˚) than in AV condition (Mdn = 3.17 ˚; t(35)=2.35, p < 0.05). Shorter fixation durations in V condition (Mdn = 290 ms) than in AV condition (Mdn = 298 ms) were observed, but this difference is only a tendency (t(35)=1.6, p = 0.1).

Discussion

We compared eye positions and movements of participants looking freely at videos with their original soundtracks (AV condition) and without sound (V condition). We found that the soundtrack of a video influences the eye movements of observers. Since we found that the influence of sound is not constant over time, it is crucial to understand the temporal evolution of eye positions on dynamic stimuli, regardless of the stimulus condition. Hence, before discussing the impact of sound on eye movements, we first focus on the dynamic of eye movements during video exploration.

Eye movements during video viewing

In our experiment, we chose to use dynamic stimuli -and more precisely professional movies -for the following reasons. Eye movements made while watching videos are known to be highly consistent. It is true both between different observers watching the same video and between repeated viewing of the same video by one observer [START_REF] Goldstein | Where people look when watching movies: Do all viewers look at the same place?[END_REF]. Nonetheless, this consistency depends on the movie content, editing and directing style [START_REF] Hasson | Neurocinematics: The Neuroscience of Film[END_REF][START_REF] Dorr | Variability of eye movements when viewing dynamic natural scenes[END_REF]. Indeed, authors found much more correlation between the recorded eye movements and brain activity during professional movies than during amateur ones. It reflects that in a general way, eye movements are strongly constrained by the dynamics of the stimuli [START_REF] Boccignone | Modelling gaze shift as a constrained random walk[END_REF]. In particular, video shot cuts have a great impact on gaze shift [START_REF] Boccignone | Foveated Shot Detection for Video Segmentation[END_REF][START_REF] Mital | Clustering of Gaze During Dynamic Scene Viewing is Predicted by Motion[END_REF]. A shot cut is an abrupt transition from one scene to another, and eye movements depend more on this transition than on contextual information [START_REF] Wang | Temporal eye movement strategies during naturalistic viewing[END_REF]. Thus, in this study, we analyzed eye movements over shots rather than over the all videos. We found that after each cut, the eye position variability (dispersion), the mean distance between eye positions and the center of the screen (distance to center) and the difference between eye position locations (KL-divergence) followed the same pattern. Independently of stimulus condition, we identified four phases during video exploration, summarized in Figure 6. Our time unit is a video shot. Phase 1: from frame 1 to 3 (∼120 ms) after shot onset, gazes remain at the last position they were in on the previous shot. Dispersion, distance to center and KLdivergence are stable. Phase 1 stands for the latency needed by participants to start moving their eyes to a new visual scene. This delay is classically reported for reflexive saccades toward peripheral target (latency around 120-200 ms [START_REF] Carpenter | Movements of the eyes[END_REF]). Phase 2: from frame 4 to 10 (∼240 ms), gazes go to the center of the screen (which is the optimal position for a rough overview of the scene), dispersion, distance to center and KL-divergence drop sharply. This behaviour is known as the center bias, see (Tatler, 2007;[START_REF] Tseng | Quantifying center bias of observers in free viewing of dynamic natural scenes[END_REF][START_REF] Dorr | Variability of eye movements when viewing dynamic natural scenes[END_REF]. Phase 3: from frame 11 to 25 (∼500 ms), dispersion, distance to center and KL-divergence increase regularly. This phase is classical in scene exploration literature: bottom-up influences are high and participants begin to explore the scene in a consistent way [START_REF] Tatler | Visual correlates of fixation selection: effects of scale and time[END_REF]. This behaviour is indicated by a rising distance to center (after getting closer to the center of the screen, gazes begin to move away) and by a still low dispersion and KL-divergence. Nevertheless, top-down (i.e. subject specific) strategies rise, inducing a gradual increase 5(4):2, 1-10 Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements of dispersion between participants. Phase 4: from frame 25 to the end, dispersion, distance to center and KL-divergence oscillate around a stationary value. In dynamic stimuli, the constant appearance of new salient regions promotes bottom-up influences at the expense of top-down strategies. This induces a stable consistency between participants over time [START_REF] Carmi | Visual causes versus correlates of attentional selection in dynamic scenes[END_REF][START_REF] Marat | Modelling Spatio-Temporal Saliency to Predict Gaze Direction for Short Videos[END_REF].

Influence of sound across time

Psychophysical studies showed that synchronized multimodal stimuli lead to faster and more accurate responses during target detection tasks, e.g. [START_REF] Spence | Audiovisual links in exogenous covert spatial orienting[END_REF][START_REF] Corneil | Auditory-visual interactions subserving goaldirected saccades in a complex scene[END_REF][START_REF] Arndt | Two stages in crossmodal saccadic integration: evidence from a visual-auditory focused attention task[END_REF]. Other studies trying to address this issue are often based on the spatial bias induced on eye movements by sound sources. Often, authors modulate the visual saliency map with the sound source position map [START_REF] Quigley | Audio-visual integration during overt visual attention[END_REF][START_REF] Ruesch | Multimodal Saliency-Based Bottom-Up Attention, A Framework for the Humanoid Robot iCub[END_REF]. Our approach is different: we studied the effect of nonspatial (monophonic) sound on the eye movements of observers viewing videos. Indeed, we hypothesized that sound might be extracted to form a new feature which interacts with visual saliency, bringing about a change in the gaze of the observers. In a preliminary study, we elicited the effect of video editing (shots and cuts) by averaging dispersion between eye positions on all the frames of videos made up of several shots, and found no significant evidence for an effect of sound on eye movements [START_REF] Coutrot | Audio Tracks Do Not Influence Eye Movements When Watching Videos[END_REF]. The new study presented in this paper points out the importance of considering the video editing impact on the temporal course of eye movements, as mentioned in the previous paragraph. Through the first three phases, sound does not have a significant effect on eye positions: we found that the dispersion in V and AV conditions overlap, as well as the inter and intra KL-divergences. This shows that during the beginning of scene exploration, the influence of sound is outweighed by visual information. During the last phase, the dispersion is lower and the distance to center higher in AV condition than in V condition. Furthermore, inter KL-divergence is higher than intra KL-divergences, which shows that fixation locations are different between the two conditions. This behaviour might be explained if we consider that sound strengthens visual saliency: without sound, participants' gaze might be less attracted to salient regions. This hypothesis is confirmed by the difference in saccade amplitude distributions: participants in AV condition make larger saccades than participants in V condition. This is coherent with the idea that participants in AV condition move their gaze further away from the center of the screen. Moreover, participants in AV condition tend to make longer fixations than participants in V condition. According to our hypothesis, salient regions might attract participants' gaze for a longer time period in AV condition. These results are consistent with a recent study that investigated the oculomotor scanning behavior during the pip and pop experiment [START_REF] Zou | Non-spatial sounds regulate eye movements and enhance visual search[END_REF]. The authors found that spatially uninformative sound events increase fixation durations upon their occurrence and reduce the mean number of saccades. More specifically, spatially uninformative sounds facilitated the orientation of ocular scanning away from already scanned display regions not containing a target. It is interesting to observe that these results are the same whether the stimuli are complex and natural (the videos we used) or very simple (bars and auditory pip). Note that in a preliminary study, sound induced a tendency to increase dispersion [START_REF] Song | Sound effect on visual gaze when looking at videos[END_REF], but this effect was not statistically tested. 5(4):2, 1-10 Coutrot, Guyader, [START_REF] Coutrot | Does oculomotor readiness mediate cognitive control of visual attention[END_REF].

Soundtrack & eye movements

These results indicate that models predicting eye movements on videos could significantly be improved by considering non spatial sound information. In their study, [START_REF] Wang | Temporal eye movement strategies during naturalistic viewing[END_REF] proposed a simple model for eye movements during video exploration: at the beginning of each shot, the observers seek, find and track an interesting object, each cut resetting the process. The model provided a good fit to experimental eye position variance.

Here, we show that to be complete this model should consider two more stages: gaze persistence at the last location of the previous shot three frames after a cut and gaze centering before the exploration of salient regions (phases 1 and 2). Moreover, the parameters of the model should be different depending on the presence or absence of sound. For instance, the probability of finding a point of interest following a saccade should be higher with than without sound.

Conclusion

In this study, we showed that during video exploration, gaze is impacted by the related soundtrack, even without spatial auditory information. We showed that in audio-visual condition, the eye positions of participants are less dispersed and tend to go more away from the screen center, with larger saccades. Moreover, we showed that observers do not look at the same locations when videos are seen with or without sound. Our results highlighted that the effect of sound is not constant across time: we did not find any significant effect of sound after abrupt visual changes (shot cuts). All these results indicate that adding sound as a new feature to classical visual saliency models might improve their efficiency. The next step would be to determine the most efficient way to insert this new attribute into visual saliency models. In particular, one would test the influence of a specific sound on specific visual features. For instance, one can assume that sound does not impact faces the same way as landscapes.

Figure 1 .

 1 Figure 1. Time course of two trials in the visual condition.To control the gaze of observer, a fixation cross is presented at the center of the screen. Then, a video sequence is presented in the center, followed by a grey screen. This sequence is repeated for the 50 videos, one block of 25 videos without sound (Visual condition) and the other block with their original soundtracks (Audio-Visual condition).

Figure 4 .Figure 5 .

 45 Figure 4. Temporal evolution of the dispersion (up) and distance to center (down). These values are averaged over all shots except the first ones (113 shots, left plots) and over the first shots (50 shots, right plots). Values are given in degree of visual angle with error bars corresponding to the standard errors.

Figure 6 .

 6 Figure 6. Schematic representation of the four temporal phases of eye movements across a shot. The ellipses represent the location and the dispersion of the two sets of eye positions (V and AV). They were computed using Principal Component Analysis, their axes correspond to the two principal components: the larger axe gives similar values to the dispersion. They are centered at the barycenter of the two sets of eye positions.

Acknowledgments

We thank two anonymous reviewers for their very helpful comments and insights on earlier versions of this manuscript.