Yoann Desmouceaux
email: yoann.desmouceaux@polytechnique.edu

Sónia Toubaline

Thomas Clausen
email: thomas.clausen@polytechnique.edu

Sonia Toubaline
email: sonia.toubaline@dauphine.fr

Flow-Aware Workload Migration in Data Centers

Keywords: Data Center Networking, VM Migration, Application-Aware Allocation, MILP, Multi-objective Optimization, Pareto Optimality

published or not. The documents may come   L'archive ouverte pluridisciplinaire

1 Introduction

Context and Approach

Virtual Machine (VM) live migration [START_REF] Clark | Live migration of virtual machines[END_REF] is a way to transfer a VM from a host to another, by iteratively copying its memory. It is further suggested in [START_REF] Bolla | Seamless and transparent migration for tcp sessions[END_REF][START_REF] Nadgowda | Voyager: Complete container state migration[END_REF] that it is possible to perform live migration of individual processes or containers, thus attaining one further level of granularity of task placement flexibility. In virtualized data centers, applications thus need not be tied to a specific machine -and their relocation can become part of a "natural" mode of data center operation. This provides a way to accommodate hardware failures without service downtime, of course, but more generally may be beneficial to the efficiency of the whole data center in terms of resource usage and execution efficiency.

With the desirability of task (VM or container, also occasionally called "workload" in literature [START_REF] Cheng | Heterogeneity-aware workload placement and migration in distributed sustainable datacenters[END_REF]) mobility established, the question of an optimal task migration mechanism naturally arises, which will be investigated in this paper. Task placement has been studied, and current approaches provide mathematical models focusing on optimal usage of resources and on flow minimization [START_REF] Zeng | Cost minimization for big data processing in geodistributed data centers[END_REF], or models that also consider migration but do not take detailed the network topology into account [START_REF] Shrivastava | Application-aware virtual machine migration in data centers[END_REF][START_REF] Huang | Multiobjective virtual machine migration in virtualized data center environments[END_REF].

This paper introduces a multi-objective linear programming model of task migration that satisfies per-node resources constraints and inter-nodes communication requirements while minimizing the cost incurred by migrations. The fundamental assumptions are (i) that tasks have inter-communication demands that change with time, (ii) that tasks that communicate benefit from being topologically close, and therefore (iii) that changes in inter-communication demands may make a current task placement suboptimal, suggesting possible efficiency gains by relocation. Hence, the developed multi-objective linear programming model of task migration is intended to run iteratively, at regular time intervals. It uses task inter-communication demands to decide if and where to reallocate tasks so as to provide the best possible task placement, while minimizing a migration cost. Network constraints are taken into account by modeling the traffic as a multi-commodity flow problem, where a commodity represents an inter-task communication demand.

Related Work

Data center traffic has been extensively studied: it has been shown that the amount of intra-rack traffic is as voluminous as is extra-rack traffic [START_REF] Benson | Network traffic characteristics of data centers in the wild[END_REF], and that patterns emerge when considering the traffic matrix between interdependent tasks [START_REF] Kandula | The nature of data center traffic: measurements & analysis[END_REF][START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF]. Some task pairs communicate more than others, in which case it makes sense to locate those on either the same machine, or on machines close to each other in the network topology. Therefore, data center architectures have been studied which take communication dependencies between workloads into account, from a network systems perspective [START_REF] Lacurts | Choreo: Networkaware task placement for cloud applications[END_REF][START_REF] Al-Fares | Hedera: Dynamic flow scheduling for data center networks[END_REF]. This motivates the need for models that can place workloads according to their pairwise communication demands.

The VM placement problem consists of finding an efficient assignment of VMs to machines within a data center, satisfying a set of constraints (resources, possibly traffic demand) with respect to one or more objective functions such as energy consumption minimization [START_REF] Cheng | Heterogeneity-aware workload placement and migration in distributed sustainable datacenters[END_REF][START_REF] Tiago | Server consolidation with migration control for virtualized data centers[END_REF][START_REF] Ghribi | Energy efficient VM scheduling for cloud data centers: Exact allocation and migration algorithms[END_REF][START_REF] Hao | Joint host-network optimization for energy-efficient data center networking[END_REF][START_REF] Liu | Task and server assignment for reduction of energy consumption in datacenters[END_REF], communication cost minimization [START_REF] Dhaemesh Kakadia | Network-aware virtual machine consolidation for large data centers[END_REF][START_REF] Zeng | Cost minimization for big data processing in geodistributed data centers[END_REF], network traffic minimization or resource utilization maximization. Different optimization approaches have been proposed for the VM placement problem: solution techniques include deterministic algorithms, heuristics, meta-heuristics and approximation algorithms. Surveys of these methods can be found in [START_REF] Wasim | A survey on virtual machine migration and server consolidation frameworks for cloud data centers[END_REF][START_REF] López | Virtual machine placement literature review[END_REF][START_REF] Hasanul Ferdaus | Network-aware virtual machine placement and migration in cloud data centers[END_REF][START_REF] Usmani | A survey of virtual machine placement techniques in cloud data center[END_REF]. Many approaches have been proposed that aim at optimizing a single objective. Multi-objectives formulations have also been introduced, but they are often reduced to a mono-objective problem, failing to provide a set of Pareto-optimal solutions.

Single-objective approaches: In [START_REF] Shrivastava | Application-aware virtual machine migration in data centers[END_REF], a model that considers resources constraints as well as dependencies between applications is proposed, which then re-allocates VMs while minimizing the migration impact. Contrary to the approach presented in this paper, [START_REF] Shrivastava | Application-aware virtual machine migration in data centers[END_REF] does not consider changing communication demands between applications, but only migrate VMs located on overloaded machines. In [START_REF] Huang | Multiobjective virtual machine migration in virtualized data center environments[END_REF], this model is refined by incorporating finer-grained server-side constraints, as well as network capacities of the machines. In [START_REF] Fang | VMPlanner: Optimizing virtual machine placement and traffic flow routing to reduce network power costs in cloud data centers[END_REF], the problem of optimizing both VM placement and traffic flow routing so as to save energy is considered. A model is formulated that minimizes the power consumption of switches and links, while satisfying capacity and traffic demands constraints. In [START_REF] Dhaemesh Kakadia | Network-aware virtual machine consolidation for large data centers[END_REF], a network-aware model is considered that places VMs with the aim of minimizing communication cost. A greedy consolidation algorithm is proposed, consisting of identifying VM clusters based on network traffic (using a cost matrix). In [START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF], a traffic-aware VM placement model is introduced, where the objective is to minimize the aggregate traffic rates perceived by every switch. A two-tier approach given by a cluster-and-cut heuristic is proposed.

Multi-objective reduced to single-objective: Some VM placement problems are formulated as multi-objectives models, which are then reduced to single-objective models. In [START_REF] Chen | Optized virtual machine placement with traffic-aware balancing in data ceter networks[END_REF], the authors consider the placement of VMs on machines by minimizing the size of clusters of VM serving the same jobs, and minimizing the maximum traffic on uplinks of top-of-rack switches. An iterative least-loaded-first based placement algorithm is proposed, which first gives the priority to locality, and then to bandwidth occupancy. In [START_REF] Fang | Power-efficient virtual machine placement and migration in data centers[END_REF], a power-efficient VM placement and migration model is introduced, aiming at minimizing the number of machines used, the network energy consumption and the network end-to-end delay. The model is solved using a weighted sum approach. In [START_REF] Xu | Multi-objective virtual machine placement in virtualized data center environments[END_REF], VM placement is considered under three objectives, to be minimized: total resource "waste", power consumption, and thermal dissipation costs. The solution approach is a combination of a generic grouping algorithm and a fuzz multi-objective evaluation. In [START_REF] Xu | A multi-objective approach to virtual machine management in datacenters[END_REF], a VM management framework considering initial VM placement and VM migration is introduced, with three objectives: elimination of thermal hotspots, minimization of power consumption and application performance satisfaction. The problem is solved using a weighted sum approach.

Pure multi-objective approaches: In [START_REF] Gao | A multiobjective ant colony system algorithm for virtual machine placement in cloud computing[END_REF], a bi-objective mathematical formulation for VM placement is proposed, aiming at minimizing resource wastage and power consumption. A multi-objective ant colony system algorithm is proposed to generate the set of non dominated solutions. In [START_REF] López | Multi-objective virtual machine placement with service level agreement[END_REF] (extending [START_REF] López | Virtual machine placement. A multi-objective approach[END_REF]), a multi-objective formulation of the VM placement problem is introduced, aiming at minimizing energy consumption and network traffic, and maximizing economical revenue while satisfying a service level agreement (SLA). A memetic algorithm given by an evolutionary process is proposed, and a Pareto set approximation is returned.

Problem Restatement

For some distributed computing applications, where tasks frequently communicate with each other, the limiting factor for the completion of a running task is not necessarily its actual location (assuming that the task is allocated with the full physical resources it needs), but can be the throughput at which it exchanges data with other tasks. Furthermore, if those tasks have changing traffic requirements, migrating them within the data center can be an efficient way to re-organize the load across all available machines so as to optimally satisfy these requirements.

With these two assumptions as a baseline -tasks need to be allocated according to their communication requirements, and those requirements can change over time -the multi-objective mathematical problem introduced in this paper consists of determining a task placement which satisfies machine, network and applications constraints, while (i) maximizing the number of new tasks to be assigned, (ii) minimizing the migration cost and (iii) maximizing the total inter-task throughput.

The contribution of this paper is therefore threefold: (i) it formulates a model of workload migration which uses an accurate description of network demands and of the network topology; (ii) it proposes a multi-objective approach which generates the set of Pareto-optimal solutions, from which the operator can choose according to operational tradeoffs; and (iii) it proposes a heuristic method that can generate an approximate Pareto front while greatly reducing solving time as compared to obtaining the exact solution.

Evaluations show that the sets of solutions generated by this approximation method remain close to their optimal counterparts, regardless of the topology and the task-to-machine ratio.

Paper Outline

The remainder of this paper is organized as follows. Section 2 introduces the framework needed to represent the state of the data center. Section 3 presents the mathematical formulation proposed for the flow-aware workload placement and migration problem, given by a multi-objective Mixed Integer Linear Program (MILP) [START_REF] Ehrgott | Multicriteria optimization[END_REF]. Section 4 describes the algorithm used to generate the set of Pareto-optimal solutions to this problem, and provides a computational example. An approximation method is proposed in section 5; its performance in terms of solving time and quality of the generated approximate solutions (as compared to the optimal ones) are then evaluated. Finally, section 6 concludes this paper.

Data Center Representation

This paper presents a multi-objective time-indexed formulation of a task migration and placement problem. Before detailing the problem formulation (section 3), resolution (section 4) and approximation (section 5), this section introduces the framework used to describe the state (including the topology) of a data center. This is achieved by considering (i) a set of machines, (ii) the network topology connecting them, and (iii) a set of tasks to allocate on these machines. As this model considers workload migration, for which it is necessary to be aware of the evolution of the state of the data center, the model makes the assumption that it is running at a given time t (where t is an abstract index without unit), and that the previous state of the data center corresponds to time (t -1). Thus as a convention, a variable superscripted with t represents the current state of the data center (to be optimized), and a variable superscripted with (t -1) is a known input representing the previous state of the data center. A summary of the notations used throughout this paper is provided in Table 1.

Tasks and Machines

Tasks to be run at time t are represented by a set I t . At time t, new tasks can arrive or existing tasks can finish executing. Arriving tasks correspond to those in I t \ I t-1 . Already existing tasks correspond to those in I t ∩ I t-1 , and among those, the ones that were successfully assigned to a machine at time (t -1) have priority over new tasks and must be placed to some machine at time t (they can continue execution on the same machine, or be migrated to Yoann Desmouceaux et al.

Notation

Description

i, i ′ , • • • ∈ I t Tasks to be run at time t m, m ′ , • • • ∈ M Machines s, s ′ , • • • ∈ S Switches A ⊆ (M ∪ S) 2
Network edges

A mm ′ ∈ 2 A Path m → m ′ cuv > 0 Capacity of link (u, v) κm > 0 Machine CPU capacity r i > 0 Task CPU requirement s i > 0
Task size

C t ⊆ I t × I t Communicating tasks at time t d t ii ′ > 0 Throughput demand for i → i ′ at time t x t im ∈ {0, 1} Task i is allocated on machine m at time t f t ii ′ (u, v) ∈ R + Flow for i → i ′ along (u, v) at time t
Table 1 Inputs and variables to the model another one, but not be stopped). Terminated tasks correspond to those in I t-1 \ I t , and thus are not of interest to the model. Machines are represented by a set M . Each machine m ∈ M has a CPU capacity κ m > 0 which represents the amount of work it can accommodate. Conversely, each task i ∈ I t has a CPU requirement r i > 0, representing the amount of resources it needs in order to run. Finally, each task i ∈ I t has a size 1 s i > 0. This size will be used to model the cost of migrating the task from one machine to another.

Network Model

In order to take application dependencies into account, the physical network topology existing between the machines must be known. To that end, a network is modeled as a directed graph G = (V, A), where V = M ∪ S is the set of vertices, with S the set of switches2 and A the set of arcs. An arc (u, v) ∈ A can exist between two switches or between a machine and a switch, but also between a machine and itself to model a loopback interface (so that two tasks on the same machine can communicate). Each of those arcs represents a link in the network, and has a capacity of c uv > 0. For each ordered pair of machines

(m, m ′ ) ∈ M 2 , a list A mm ′ ∈ 2 A represents the path from m to m ′ .
For example, given the topology depicted in Figure 1 with three switches s 0 , s 1 , s 2 and four machines m 1 , m 2 , m 3 , m 4 , the arcs of the graph will be as follows:

A = {(m 1 , m 1 ), (m 1 , s 1 ), (s 1 , m 1 ), (m 2 , m 2 ), (m 2 , s 1 ), (s 1 , m 2 ), (m 3 , m 3 ), (m 3 , s 2 ), (s 2 , m 3 ), (m 4 , m 4 ), (m 4 , s 2 ), (s 2 , m 4 ), (s 1 , s 0 ), (s 0 , s 1 ), (s 2 , s 0 ), (s 0 , s 2 )}.
The path from e.g., m 1 to m 3 will be Finally, at a given time t, an ordered pair of tasks (i, i ′ ) ∈ I t × I t can communicate with a throughput demand d t ii ′ > 0, representing the throughput at which i would like to send data to i ′ . Let G t d = (I t , C t ) be a weighted directed graph representing these communication demands, where each arc

A m1m3 = {(m 1 , s 1 ), (s 1 , s 0 ), (s 0 , s 2 ), (s 2 , m 3 )}.
(i, i ′ ) ∈ C t is weighted by d t
ii ′ . G t d will be referred to as the throughput demand graph.

Mathematical Modeling

Based on the data center framework described in section 2, this section presents a multi-objective Mixed Integer Non Linear Program (MINLP) aiming at optimizing workload allocation and migration while satisfying inter-application network demands. A linearization as a multi-objective MILP is then derived, allowing for an easier resolution.

Variables

Two sets of variables are introduced, representing (i) task placement and (ii) the network flow for a particular allocation.

Task placement

The aim of the model is to provide a placement of each task i ∈ I t on a machine m ∈ M , at a given timestep t. The binary variable x t im reflects this allocation: x t im = 1 if i is placed on m, and x t im = 0 otherwise.

Network flow

In order to determine the best throughput that can be achieved between each pair of communicating tasks, a variant of the multi-commodity flow problem [31, p. 58] is used, where a commodity is defined by the existence of (i, i ′ ) ∈ C t . A commodity thus represents an inter-task communication.

For each link (u, v) ∈ A, f t ii ′ (u, v) is a variable representing the throughput for communication from i to i ′ along the link (u, v).

Constraints

Two sets of constraints are used to model this flow-aware workload migration problem: allocation constraints (equations (1-3)) represent task allocation, whereas flow constraints (equations (4-8)) focus on network flow computation.

The allocation constraints represent the relationship between tasks and machines. First, each task i ∈ I t must be placed on at most one machine:

m∈M x t im ≤ 1, ∀i ∈ I t (1)
Forcefully terminating a task is not desirable: if a task was running at time t -1, and is still part of the set of tasks at time t, it must not be forcefully terminated:

m∈M x t-1 im ≤ m∈M x t im , ∀i ∈ I t-1 ∩ I t (2)
where x t-1 im is a known input given by the state of the system at time t-1. If the task was successfully allocated at time t-1 (i.e. i ∈ I t-1 and m∈M x t-1 im = 1) and is still to be run at time t (i.e. i ∈ I t ), the left-hand-side of the equation will be 1, thus forcing allocation of the task at time t.

Finally, the tasks on a machine cannot use more CPU resources than the capacity of that machine:

i∈I t r i x t im ≤ κ m , ∀m ∈ M (3)
The flow constraints allow computing the throughput for each commodity (i.e. ordered pair of communicating task). For each link (u, v) ∈ A in the network, the total flow along the link must not exceed its capacity:

(i,i ′ )∈C t f t ii ′ (u, v) ≤ c uv , ∀(u, v) ∈ A (4)
For a commodity (i, i ′ ) ∈ C t , the flow going out of a machine m must not exceed the throughput demand for the communication from i to i ′ . Also, the flow must be zero if task i is not hosted by machine m:

v:(m,v)∈A f t ii ′ (m, v) ≤ d t ii ′ x t im , ∀m ∈ M, ∀(i, i ′ ) ∈ C t (5)
Conversely, for a commodity (i, i ′ ) ∈ C t , the flow entering a machine m ′ must not exceed the throughput demand for the communication from i to i ′ , and must be set to zero if task i ′ is not on m ′ :

v:(v,m ′ )∈A f t ii ′ (v, m ′ ) ≤ d t ii ′ x t i ′ m ′ , ∀m ′ ∈ M, ∀(i, i ′ ) ∈ C t (6)
Each switch s ∈ S must forward the flow for each commodity -that is, the ingress flow must be equal to the egress flow:

v:(u,v)∈A f t ii ′ (u, v) = v:(v,u)∈A f t ii ′ (v, u), ∀u ∈ S, ∀(i, i ′ ) ∈ C t (7)
Finally, if a task i is placed on machine m and a task i ′ on machine m ′ , the corresponding flow must go through the path specified by A mm ′ . Otherwise, the flow computed by the model could go through a non-optimal path or take multiple parallel paths, which does not accurately reflects what happens in an IP network. Hence, the flow needs to be set to zero for all edges that do not belong to the path from m to m ′ :

f t ii ′ (u, v) ≤ c uv (1 -x t im x t i ′ m ′ ), ∀(i, i ′ ) ∈ C t , ∀m, m ′ ∈ M, ∀(u, v) ∈ A \ A mm ′ (8)
This constraint has no side effect if task i is not on m or task i ′ is not on m ′ , since in this case it reduces to f t ii ′ (u, v) ≤ c uv , already covered by equation (4).

Objective Functions

The migration model as presented in this paper introduces three different objective functions, modeling (i) the placement of tasks, (ii) the overall throughput achieved in the network and (iii) the cost incurred by task migration, respectively. These functions depend on an allocation, i.e. on an assignment of all variables x t im and f t ii ′ (u, v). Let x t (respectively f t ) be the characteristic vectors of the variables x t im (respectively f t ii ′ (u, v)). The placement objective is simple and expresses that a maximal number of tasks should be allocated. When removing tasks dependencies, this degenerates to a standard assignment problem wherein each task should be placed on a machine satisfying its CPU requirement, while also not exceeding the machine capacity. The placement objective function is simply the number of tasks which are successfully allocated to a machine:

P (x t ) = i∈I t m∈M x t im (9)
The throughput objective expresses the need to satisfy applications throughput demands. Modeling network dependencies between workloads in a data center is usually (e.g., in [START_REF] Shrivastava | Application-aware virtual machine migration in data centers[END_REF]) done through the use of a cost function depending on the network distance between two machines. Having introduced a representation of the physical network and of applications dependencies in section 2.2, it is possible to represent the overall throughput reached in the data center. To compute the throughput of the communication from a task i to a task i ′ , it suffices to identify the machine m on which i is running and take the flow going out of this machine for this commodity:

m∈M x t im v:(m,v)∈A f t ii ′ (m, v
). This expression is quadratic in variables x t im and f t ii ′ (u, v), but, owing to the fact that (5) constrains the flow to be zero for machines to which i is not assigned, can be simplified to m∈M v:(m,v)∈A f t ii ′ (m, v). Therefore, the overall throughput in the data center can be expressed as:

T (f t ) = (i,i ′ )∈C t m∈M v:(m,v)∈A f t ii ′ (m, v) (10)
Since each machine has a loopback link in the graph G (i.e. that (m, m) ∈ A, ∀m ∈ M ), this formulation also covers the case where i and i ′ are hosted on the same machine.

Finally, the migration cost reflects the cost of re-allocating tasks from one machine to another. The fundamental assumption is that tasks in a data center have communication demands that can evolve over time (modeled by d t ii ′ ). This means that migrating a task to a machine topologically closer to those machines hosting other tasks with which it communicates, can be a simple way to achieve overall better performance. The migration cost incurred between two successive times (t -1) and t is modeled as the sum of the sizes of tasks that have migrated. Since at time t, the assignment x t-1 is known, it is possible to know if a task i ∈ I t ∩ I t-1 placed on a machine m ∈ M has moved, by comparing x t im to (1 -x t-1 im ). Also, if a task is to be shut off at time t (i.e. i ∈ I t-1 \ I t ), it must not be part of the computation of the number of migrated tasks. The total migration cost from time t -1 to time t can thus be expressed as:

M (x t ) = i∈I t ∩I t-1 m∈M s i x t-1 im (1 -x t im ) (11)
Using these three objectives, it is possible to express the flow-aware placement and migration model as a multi-objective MILNP:

(P)                    max T (f t ) max P (x t ) min M (x t ) subject to      (1-8) x t ∈ {0, 1} I t ×M f t ∈ (R + ) C t ×A (12)
These objectives tend to compete with each other. Indeed, if a task starts communicating with another task, migrating it to the same machine (or to a machine closer in the topology) can increase the throughput at which they communicate, thus increasing the throughput objective function -but this will incur an increase of the migration cost. Likewise, if a new task arrives at t and needs important CPU resources, placing it right away could utilize CPU capacity that could have been used for co-locating tasks: increasing the placement objective can in some cases decrease the throughput objective.

As an illustration, consider two machines m 1 and m 2 with CPU capacities κ 1 = 1 and κ 2 = 2, with a bottleneck link (of capacity 1) in between. Assume that at (t -1) there were two tasks i 1 , i 2 with CPU requirements r i1 = 1 and r i2 = 1, and that i 1 was placed on m 1 and i 2 on m 2 . At time t, i 1 starts to communicate with i 2 (with throughput demand d t i1i2 = 2), and a third task i 3 arrives with CPU requirement r i3 = 2. Then, if one decides to place this new task, m 2 is the only machine with enough capacity to host it. But placing i 3 on m 2 would prevent a migration of i 1 from m 1 to m 2 , which would have increased the throughput of communication i 1 → i 2 . This situation is summarized in figure 2.

m 1 i 1 m 2 i 2 capa=1Gbps m 1 i 1 m 2 i 2 i 3 1Gbps capa=1Gbps m 1 m 2 i 2 i 1 i 3 2Gbps capa=1Gbps throughput=2,placed=2,migrated=1 throughput=1,placed=3,migrated=0 i 1 i 2 demand =2Gbps t-1 t i 1 i 2 demand =0Gbps
Fig. 2 Competition between objective functions

Linearization

All constraints expressed in section 3.2 are linear with respect to the variables x t im and f t ii ′ (u, v), except for the path enforcement constraint in equation ( 8). Exploiting the fact that x t im ∈ {0, 1}, this constraint can be linearized:

f t ii ′ (u, v) ≤ c uv (2 -x t im -x t i ′ m ′ ), ∀(i, i ′ ) ∈ C t , ∀m, m ′ ∈ M, ∀(u, v) ∈ A \ A mm ′ (13) If x t im × x t i ′ m ′ = 1, the equation will be f t ii ′ (u, v) ≤ c uv or f t ii ′ (u, v) ≤ 2 c
uv , and will therefore be superseded by equation [START_REF] Cheng | Heterogeneity-aware workload placement and migration in distributed sustainable datacenters[END_REF].

The set of constraints can be further compressed by writing only one equation per machine m ∈ M instead of one per tuple m, m ′ ∈ M . This does not alter the model but makes the formulation more compact:

f t ii ′ (u, v) ≤ c uv   2 -x t im - m ′ ∈M :(u,v) / ∈A mm ′ x t i ′ m ′   , ∀(i, i ′ ) ∈ C t , ∀m ∈ M, ∀(u, v) ∈ A (14)
In this way, the flow-aware workload migration problem can be expressed as the following multi-objective Mixed Integer Liner Program (MILP):

(P ′ )                    max T (f t ) max P (x t ) min M (x t ) subject to     
(1-7), ( 14)

x t ∈ {0, 1} I t ×M f t ∈ (R + ) C t ×A (15)
4 Flow-Aware Workload Migration

Resolution Algorithm

This section describes an algorithm (Algorithm 1) solving the previously introduced multi-objective MILP [START_REF] Hao | Joint host-network optimization for energy-efficient data center networking[END_REF]. This algorithm runs at a given time t representing the "present". It takes the current inter-application communication requirements and the "past" (from time t -1) task allocation as inputs, and returning a new allocation as a solution.

A Pareto-optimal approach [30, p. 24] is used: a set of optimal solutions is generated, from which a final solution z t = (x t , f t ) can be extracted based on an operator-defined policy getSolutionFromPolicy(). In the context of this migration model, an allocation z = (x, f ) dominates an allocation z ′ = (x ′ , f ′ ) if all the objectives functions of the former have better values than the ones of the latter (with at least of one having a strictly better value). That is denoted z ≻ z ′ :

z ≻ z ′ ⇔          P (z) ≥ P (z ′ ) T (z) ≥ T (z ′ ) M (z) ≤ M (z ′ ) (P (z), T (z), M (z)) = (P (z ′ ), T (z ′ ), M (z ′ )) (16)
A set S = {z 1 , . . . , z n } of solutions is Pareto-optimal if and only if:

∀z, z ′ ∈ S, z = z ′ ⇒ (z ≻ z ′ ∧ z ′ ≻ z) (17)
To generate the set of Pareto-optimal solutions for the multi-objective problem, the ε-constraint method [30, p. 98] a multi-objective linear programming model to a single-objective model, by relaxing all objective functions but one and considering them as constraints. These constraints are obtained by bounding the relaxed objective function by a number ε that varies in a certain interval. Although its initial formulation only considers two-objectives problems, it can be extended to problems with a greater number of objective functions [START_REF] Laumanns | An adaptive scheme to generate the pareto front based on the epsilon-constraint method[END_REF], as it is the case here.

The two functions that are relaxed are the placement objective and the migration cost, because it is simple to grid the corresponding space. The singleobjective MILP that results is given by:

(P ε )                    max T (f t ) subject to               
(1-7), ( 14)

P (x t ) ≥ ε p M (x t ) ≤ ε m x t ∈ {0, 1} I t ×M f t ∈ (R + ) C t ×A (18)
where ε p , ε m are bounds varying in [ε p , ε p ] and [0, B] respectively.

For the placement objective, a simple upper bound for ε p corresponds to the number of tasks:

ε p = i∈I t 1 = |I t | (19)
Similarly, a lower bound for ε p can be easily derived from tasks that were running at the previous iteration and that are still to be run. As per equation (2), they cannot be forcefully terminated:

u = s 0 , v ∈ {s 1 , s 2 } cuv = cvu = 40 u ∈ {s 1 , s 2 }, v ∈ M cuv = cvu = 40 u ∈ M cuu = 200
ε p = i∈I t-1 ∩I t m∈M x t-1 im (20)
For the migration cost, correctly choosing the upper bound B for ε m has a large impact on the running time of the algorithm. This bound B will be referred to as the migration budget.

Computational Example

In large-scale deployments, the amount of CPU resources is likely sufficient for all tasks to be deployed. However, complex situations can exist, for which it is beneficial to have an understanding of the implications that different allocation choices can have. For instance, when new tasks arrive that have a high CPU requirement, choosing to place them upfront can consume CPU capacity which could have been used to migrate a smaller task and satisfy its throughput demand. This section illustrates the model response in situations where placement and migration are competing with each other, by way of an environment in which the machines are nearly overloaded in the initial state. The algorithm has been implemented in Python using the Gurobi MILP solver [START_REF] Inc | Gurobi Optimization[END_REF], and all the simulations have been run on a virtual machine with 4 GB of RAM and an 2.6 GHz CPU.

Simulation Parameters

A simple two-tier tree topology is used, consisting of one root switch s 0 linked to two ToR switches s 1 , s 2 , each linked to 10 machines (Figure 3). In order to represent the fact that tasks located on the same machine can achieve a higher throughput, each machine has a link to itself, with a higher capacity than other links in the data center, as depicted in Table 2.

The CPU capacity is set to 3 for each machine -which gives a total capacity of 60. An initial state with 40 tasks of size r i = 1 and a throughput demand graph G t-1 d with 80 arcs of intensity d t-1

ii ′ = 10 is considered, with an initial allocation z t-1 optimal with respect to throughput demands 3 .

Given this allocation, this study explores the model behavior when communication demands of existing tasks change, while new bigger tasks arrive in the system. Communication demand changes are modeled by adding 10 random arcs (of intensity d t ii ′ = 10) between the already running tasks. Arrival of new tasks is modeled by creating 10 new tasks of size r i = 2, and by adding 10 random arcs (of intensity d t ii ′ = 5) going out of these tasks.

Results

In order to obtain the set of Pareto-optimal solutions S at time t, one iteration of Algorithm 1 was run. Figure 4 shows a three-dimensional representation of the solutions computed for one of those runs: Pareto-optimal solutions can be visually identified as those for which no other solutions have better coordinates in all dimensions. Results show that non-trivial behavior occurs when the data center is almost fully loaded: while placing a few new tasks improves the overall throughput, allocating all of them has a detrimental effect on the overall throughput because it prevents migration of other tasks. This shows the interest of using a multi-objective model in cases where the objectives are conflicting with each other.

Yoann Desmouceaux et al.

Algorithm 2 Heuristic Multi-Objective Resolution

z t-1 ← input ⊲ initial state C t , d t ii ′ , B ← input ⊲ parameters m ← 0 ⊲ total migration cost ∆ ← input ⊲ incremental budget Ŝ ← ∅ ẑ0 ← z t-1 τ ← 1 ⊲ step index while m < B do ⊲ reduce ∆ at last iteration so that m + ∆ ≤ B ∆ ← min{∆, B -m} ⊲ find an allocation within ∆ of the previous one ẑτ ← solution of                    max T ( f τ ) subject to              (1-7), ( 14
) with t → τ P (x τ ) = |I| M (x τ , xτ-1 ) ≤ ∆ xτ ∈ {0, 1} I×M f τ ∈ (R + ) C t ×A if M (x τ , xτ-1 ) = 0 then break ⊲ stop if no task could be migrated end if Ŝ ← Ŝ ∪ {ẑ τ } ⊲ compute the migration cost w.r.t. initial state m ← M (x τ , x0 ) τ ← τ + 1 end while z t ← getSolutionF romP olicy( Ŝ) return z t 5 Pareto Front Approximation
Section 4 introduced a generic solution approach, which allows to compute the exact Pareto front for the three competing objectives (placing the highest number of tasks, minimizing the cost incurred by migration, achieving the best inter-application throughput) by means of an ε-constraint method. Although this approach generates an exact set of efficient solutions, and thus can be useful for small and highly-constrained deployments, its computational complexity makes it unsuitable to model larger infrastructures.

In order to overcome this issue, this section derives and experimentally analyses a heuristic for approximating the Pareto front. Section 5.1 introduces the approximation method, and section 5.2 provides the results of computational experiments in order to validate the quality of the proposed approach.

Heuristic Formulation

In large deployments, it is assumed that there are enough resources to accommodate all tasks to be run, thus the remainder of this section assumes that all tasks can be placed (i.e. that there exists at least one solution to [START_REF] Wasim | A survey on virtual machine migration and server consolidation frameworks for cloud data centers[END_REF]

such u = s 0 , v ∈ {s 1 , . . . , s k } cuv = cvu = 40 u ∈ {s 1 , . . . , s k }, v ∈ M cuv = cvu = 40 u ∈ M cuu = 1000
Table 3 Link capacities for the k-racks topology that P (x) = |I t |). In order to focus on migration, it is also assumed that no new task arrives (i.e. I t = I t-1 := I).

Given this assumption, a heuristic allowing to approximate the Pareto front in the throughput-migration plane, i.e. for (P (z), T (z), M (z)) ∈ {|I|} × [0, +∞) × [0, B], is introduced. The issue with the ε-constraint approach introduced in section 4 is that, when considering the migration of B tasks, there are O(|I| B |M | B ) possible recombinations, which can be computationally expensive. In order to limit the combinatorics of the recombination, the introduced heuristic splits the migration process in smaller chunks, considering fewer migrations at a time, and proceeding in a greedy way until the total budget is exhausted, as described in Algorithm 2.

For clarity, let M (x t , x t ′ ) represent the migration cost when going from state x t to x t ′ :

M (x t , x t ′ ) = i∈I∩I t ′ m∈M s i x t ′ im (1 -x t im ) (21)
Let ∆ > 0 be a parameter representing an incremental budget. Starting from an initial configuration z t-1 , and given an upper-bound B on the migration cost, intermediary states (ẑ 0 = z t-1 , ẑ1 , . . . , ẑτ , . . . , ẑτ ) are created. At each step τ ≥ 1, a new placement is generated by maximizing the throughput objective, with the constraint that no more than ∆ is incurred as a migration cost as compared to step (τ -1). This way, no more than O(|I| ∆ |M | ∆ ) recombinations are considered at each step, allowing for a smaller expected computational complexity. This process ends when no further tasks can be migrated, or when a total migration cost of B (as compared to step 0) has incurred. The heuristic tracks of the solutions generated while generating the successive solutions, so as to build an approximate Pareto front Ŝ.

Computational Experiments

This section experimentally illustrates the benefits of using the Pareto front approximation heuristic, both in terms of computational complexity and quality of the approximation. The sensitivity of the heuristic to the incremental budget parameter ∆ is also experimentally explored. The experimental platform is the same as in section 4.2.

Simulation Parameters

In a common data center, all machines in a rack are linked to a top-of-rack (ToR) switch, and those ToR switches are linked to each other via an aggrega-tion router. In data centers, several such configurations can be linked together thanks to a third routing layer -in all cases, resulting in a tree-like topology.

For the purposes of these simulations, a k-racks topology is defined as a tree where a core switch s 0 is attached to k ToR switches s 1 , s 2 , . . . , s k . Each ToR switch s h (1 ≤ h ≤ k) is attached to 10 machines m h,1 , m h,2 , . . . , m h,10 . This topology thus comprises 10 × k machines, and Figure 3 depicts a 2-racks topology. Links capacities are set as per Table 3, i.e. links between the core switch and the ToR switches, and between the ToR switches and the machines have a capacity of 40. Loopback interfaces on the machines have a capacity of 1000 -so as to favor placement of tasks which communicate with each other on the same machine.

Five k-racks topologies are considered, for k ∈ {2, 3, 4, 5, 10} (for a corresponding number of machines |M | ∈ {20, 30, 40, 50, 100}). For each of these topologies, four scenarios are considered with different tasks-per-machine ratios, such that |I| ∈ {|M |, 2|M |, 5|M |, 10|M |} -as a way to compare between different load factors for the machines. This makes for a total of 5 × 4 = 20 scenarios.

CPU requirements of tasks are set to r i = 1, and CPU capacities of the machines to κ m = 20. This allows for up to 20 tasks per machine, thus ensuring that all tasks can always be placed. To simplify understanding the migration cost, tasks size (for computing the migration cost) are set to s i = 1, thus the migration cost simply becomes the number of migrated tasks. Tasks are initially uniformly randomly assigned to the machines. The communication matrix is generated by: (i) for each task i ∈ I, uniformly choosing a random number d i of destinations in {1, 2, 3}, (ii) for each of these d i destinations, uniformly choosing a task i ′ ∈ I \ {i} and (iii) setting a throughput demand d ii ′ for the communication i → i ′ uniformly in {1, 2, . . . , 10}.

For each of these 20 scenarios, the exact Pareto front is computed using Algorithm 1, with a migration budget (maximum migration cost) B = 30. The approximate Pareto front as described in Algorithm 2 is computed for five different values of the incremental budget ∆ ∈ {1, 2, 3, 4, 5}.

Comparative Results

In order to illustrate the results, the cases of the 2-racks topology (20 machines) with 40 and 100 tasks are first considered as examples. For these two cases, Figures 5 and6 depict the generated exact and approximate Pareto fronts. Those figures show the different solutions from among which one can be choose, after running either algorithm. As depicted in the figures, migrating more tasks obviously increases the migration cost -while enabling communicating tasks to be co-located, hence increasing the total achievable throughput.

Depending on requirements, a solution can be chosen from the Paretooptimal set that offers a tradeoff between improving the overall throughput and incurring more migrations. In these two examples, it can be observed that the approximate Pareto fronts generated by algorithm 2 for ∆ ≥ 3 closely follow the exact front. It can also be observed that for ∆ = 1, results are of lower quality, and that in the example of Figure 6, the algorithm was unable to find solutions for more than 24 migrations.

In order to quantify the impact of these algorithms on the quality of the obtained solution set, let θ 20 (resp. θ 0 , θ 30 ) represent the throughput corresponding to a migration cost of 20 (resp. 0, 30) in the Pareto front. More formally, this means that θ 20 is the coordinate such that (|I|, θ 20 , 20) ∈ S; for instance, in Figure 6, θ 20 = 876 for the exact Pareto front. Figure 7 (resp. 8) shows the throughput improvement θ 20 /θ 0 (resp. θ 30 /θ 0 ) for the 20 tested sce- narios, for the exact Pareto front as well as the approximate Pareto fronts. This represents the relative improvement in terms of overall throughput if the operator chooses to migrate 20 (resp. 30) tasks after inspecting the set of Pareto-optimal solutions. It appears that, for ∆ ≥ 2, the achievable throughput improvement when using the heuristic method introduced in section 5.1 is close to the exact solution. Overall, choosing ∆ = 5 yields the better results: for 20 migrations, the results are better in all the twenty tested instances, and for 30 migrations they are outperformed by ∆ = 4 in only three instances. For ∆ = 5, the throughput improvement remains within a 3% error as compared to the exact solution after 20 migrations, and within a 5% error after 30 migrations. Using ∆ = 1 yields results of lower quality, because the algorithm is not able to explore reconfigurations with two migrations at the same time (i.e. swapping tasks), and because it can terminate prematurely if the throughput cannot be improved by migrating only one task. For 20 migrations, ∆ = 3 also yields results of lower quality, but this is more of an artificial nature: the number of migrations considered is 18 instead of 20 (since 20 is not a multiple of 3). Finally, Figure 9 depicts the time needed to generate the exact and approximate Pareto fronts. While computing the exact Pareto front is very time-consuming, the approximation heuristics introduced reduces the required computation time. Overall, the lowest computation times are achieved for ∆ ∈ {3, 4, 5}, whereas ∆ ∈ {1, 2} exhibit higher running times. The choice ∆ = 5, which can be observed to exhibit the best results, in terms of throughput improvement, in the majority of cases -with a computation time constantly better than the reference exact approach, performing approximately one order of magnitude faster when B = 30 (from 5.1× faster for 100 machines and 200 tasks, to 1800× faster for 30 machines and 60 tasks).

To conclude, the approximation method presented in section 5.1 can greatly reduce the time needed to compute a set of approximate Pareto optimal solutions, while generating solutions close enough to the exact ones. It is realistic to note that, although an improvement in solving time is observed regardless of the topology size, Figure 9 suggests that using a MILP approach (exact or approximate) might be unfit for too large topologies.

Conclusion

In data centers, applications may exhibit time-varying communications dependencies, and migrating tasks in such environments can be a means to redistribute the load over the whole infrastructure, while optimizing inter-task communications. In this paper, a linear programming framework is introduced, which represents the data center topology, and communications dependencies between workloads. Using this framework, a multi-objective model is developed, which, when solved, can propose a reorganization of workloads so as to (i) place the highest number of new tasks, (ii) maximize the overall achievable throughput, and (iii) minimize the migration cost, incurred by this reorganization.

The approach developed is generic with respect to the network topology and the inter-application communication demands, and is novel in that, when compared to other workload migration frameworks, it generates a set of Paretooptimal solutions. From among this solution set, a workload allocation can be chosen, which yields the best tradeoff in terms of throughput improvement versus the cost incurred by task migration. A solution algorithm using the ε-constraint method is proposed as a baseline. Then, a heuristic is presented, which generates an approximate Pareto front. Computational experiments on different topologies show that the proposed approximation builds solutions close to the optimal Pareto front, while greatly reducing the computation time.

Having shown the desirability of considering inter-application dependencies in migration models, an interesting question that arises is how the proposed model can be extended to take into account more fine-grained parameters. These could include the distance between source and destination hosts when migrating, the energy cost induced by machines which are on or off, and the possibility to load-balance flows across multiple paths.

Fig. 1

 1 Fig. 1 Simple network example

Fig. 3

 3 Fig. 3 Network topology used in the example run

Fig. 4

 4 Fig. 4 Multi-objective model example run: solutions and Pareto-optimal solutions.

Fig. 5 Fig. 6

 56 Fig. 5 Pareto front approximation: Exact Pareto front and approximate Pareto fronts from Algorithm 2 for ∆ ∈ {1, 3, 5}. Tree topology, 20 machines, 40 tasks.

Fig. 8

 8 Fig. 8 Pareto front approximation: throughput improvement for 30 migrations θ 30 /θ 0 . Exact Pareto front vs approximate Pareto fronts from Algorithm 2 for ∆ ∈ {1, 2, 3, 4, 5}. 20 different scenarios.

Fig. 9

 9 Fig. 9 Pareto front approximation: time to generate the approximate Pareto front, for up to B = 30 migrations. Exact Pareto front (Algorithm 1) vs approximate Pareto fronts (Algorithm 2) for ∆ ∈ {1, 2, 3, 4, 5}. 20 different scenarios.

  is used. It consists of reducing Algorithm 1 Multi-Objective Migration Algorithm z t-1 ← input ⊲ initial state C t , d t ii ′ , B, εp, εp ← input ⊲ parameters S ← ∅ for εp ∈ [εp, εp] with step δp do for εm ∈ [B, 0] with step -δm do if ∃z ′ ∈ S, P (z ′ ) ≥ εp ∧ M (z ′ ) ≤ εm then continue ⊲ dominant solution already existing end if z ← solution of (18) ⊲ if z is not dominated, it is a candidate solution if ∃z ′ ∈ S, z ′ ≻ z then

	⊲ remove any existing solution dominated by z
	for z ′ ∈ S do
	if z ≻ z ′ then
	S ← S \ {z}
	end if
	end for
	S ← S ∪ {z} ⊲ add z to candidate solutions
	end if
	end for
	end for
	⊲ select the best solution according to the considered policy
	z t ← getSolutionFromPolicy(S)

Table 2

 2 Link capacities for the example topology

  Pareto front approximation: throughput improvement for 20 migrations θ 20 /θ 0 . Exact Pareto front vs approximate Pareto fronts from Algorithm 2 for ∆ ∈ {1, 2, 3, 4, 5}. 20 different scenarios.

		2.2
		2
	Throughput improvement	1.4 1.6 1.8
		20-20 1 1.2	30-30	100-1000	50-500	30-300	20-200	40-400	20-40	100-500	20-100	50-50	40-40	50-250	100-200	100-100	30-150	40-200 Δ=1 50-100 Δ=2 Δ=3 Δ=4 Δ=5 Exact	30-60	40-80
								Topology (#machines-#tasks)
	1.4 1.6 1.8 2 2.2 2.4 Fig. 7 1 20-20 Throughput improvement 1.2	30-30	100-1000	50-500	30-300	20-200	40-400	20-40	100-500	20-100	50-50	40-40	50-250	100-200	100-100	30-150	40-200 Δ=1 50-100 Δ=2 Δ=3 Δ=4 Δ=5 Exact	30-60	40-80
								Topology (#machines-#tasks)

For instance, the size of RAM plus storage for a virtual machine.

This term is used generically to refer to any forwarding node in the network, regardless of its actually being a router or a switch.

z t-1 is obtained by starting from a random state and solving[START_REF] Hao | Joint host-network optimization for energy-efficient data center networking[END_REF] where only the throughput objective is considered, with the additional constraint that all tasks must be allocated.