Christian Bessiere
email: bessiere@lirmm.fr

Emmanuel Hebrard
email: hebrard@laas.fr

Marc-André Ménard
email: marc-andre.menard.2@ulaval.ca

Claude-Guy Quimper
email: claude-guy.quimper@ift.ulaval.ca

Toby Walsh
email: toby.walsh@nicta.com.au

Buffered Resource Constraint: Algorithms and Complexity

The notion of buffered resource is useful in many problems. A buffer contains a finite set of items required by some activities, and changing the content of the buffer is costly. For instance, in instruction scheduling, the registers are a buffered resource and any switch of registers has a significant impact on the total runtime of the compiled code. We first show that sequencing activities to minimize the number of switches in the buffer is NP-hard. We then introduce an algorithm which, given a set of already sequenced activities, computes a buffer assignment which minimizes the number of switches in linear time, i.e., O(nd) where n is the length of the sequence and d the number of buffered items. Next, we introduce an algorithm to achieve bound consistency on the constraint Switch, that bounds the number of changes in the buffer, in O(n 2 d + n 1.5 d 1.5 ) time. Finally, we report the results of experimental evaluations that demonstrate the efficiency of this propagator.

Introduction

We consider a special type of resource, a buffer, corresponding to a set of items required by some tasks. In order to process a task, all items required by the task must be present in the buffer. However, the buffer has a limited capacity, and adding a new item is costly. Therefore, one may want to minimize the total number of changes, or switches. For instance, in instruction scheduling, the buffer can stand for memory caches, and minimizing the number of switches corresponds to minimizing page faults. Alternatively, the buffer may correspond to the reels of colored threads on an embroidery machine, and minimizing the number of reels changes over a sequence helps reducing the overall processing time. Yet another example arises in the design of validation plans for satellite payload [START_REF] Verfaillie | Constraint programming for optimising satellite validation plans[END_REF]. Here, each test requires some components of the payload to be in a given configuration, and again the total number of configuration changes during the test campaign is a significant factor of its total duration. We show that achieving hybrid consistency on the BufferedResource constraint, i.e., domain consistency on the integer variables and bound consistency on the set variables, is NP-hard. We therefore consider a decomposition involving an AllDifferent constraint to enforce that the sequence is a permutation of the original set of tasks, and the constraint Switch, that counts the number of switches along the sequence.

We introduce an algorithm for finding a support of Switch in linear time, that is, O(nd) where n is the length of the sequence and d the number of items. Moreover, we show how bound consistency can be enforced in O(n 2 d + n 1.5 d 1.5 ) time using a flow representation.

Finally, we compare our filtering algorithm against a decomposition on two crafted optimization problems, albeit derived from industrial applications. In both cases the objective function is defined using one or several Switch constraints. In these experiments, the proposed propagation algorithm for Switch greatly outperforms the standard decomposition.

The paper is organized as follows: In Section 2 we recall some background about consistency on constraints involving both integer and set variables. In Section 3 we define the BufferedResource and Switch constraints and discuss their complexities. Then, in Section 4, we introduce an algorithm for achieving bound consistency on the Switch constraint. Finally, in Section 5, we report experimental results.

Formal Background

A constraint satisfaction problem consists of a set of variables, each with a finite domain of values, and a set of constraints specifying allowed combinations of values for subsets of variables. We write dom(X) for the domain of a variable X. For totally ordered domains, we write min(X) and max(X) for the minimum and maximum values. A solution is an assignment of values to the variables satisfying the constraints. We consider both integer and set variables. A set variable S is represented by its lower bound lb(S) which contains the definite elements and an upper bound ub(S) which also contains the potential elements.

Constraint solvers typically explore partial assignments enforcing a local consistency property using either specialized or general purpose propagation algorithms. Given a constraint C, a bound support on C is a tuple that assigns to each integer variable a value between its minimum and maximum, and to each set variable a set between its lower and upper bounds which satisfies C. According to [START_REF] Bessiere | The range and roots constraints: Specifying counting and occurrence problems[END_REF], a bound support in which each integer variable is assigned a value in its domain is called a hybrid support. If C involves only integer variables, a hybrid support is a support. A constraint C is bound consistent (BC ) iff for each integer variable X i , its minimum and maximum values belong to a bound support, and for each set variable S j , the values in ub(S j ) belong to S j in at least one bound support and the values in lb(S j ) belong to S j in all bound supports. A constraint C is hybrid consistent (HC ) iff for each integer variable X i , every value in dom(X i ) belongs to a hybrid support, and for each set variable S j , the values in ub(S j ) belong to S j in at least one hybrid support, and the values in lb(S j ) are all those from ub(S j ) that belong to S j in all hybrid supports. A constraint C involving only integer variables is generalized arc consistent (GAC ) iff for each variable X i , every value in dom(X i ) belongs to a support.

If all variables in C are integer variables, hybrid consistency reduces to generalized arc-consistency, and if all variables in C are set variables, hybrid consistency reduces to bound consistency.

To illustrate these concepts, consider the constraint C(X 1 , X 2 , S) that holds iff the set variable S is assigned exactly the values used by the integer variables X 1 and X 2 . Let dom(X 1 ) = {1, 3}, dom(X 2 ) = {2, 4}, lb(S) = {2} and ub(S) = {1, 2, 3, 4}. BC does not remove any value since all domains are already bound consistent. On the other hand, HC removes 4 from dom(X 2 ) and from ub(S) as there does not exist any tuple satisfying C in which X 2 does not take value 2. Note that as BC deals with bounds, value 2 was considered as possible for X 1 .

The BufferedResource and Switch Constraints

We consider the problem of performing a set of tasks, each requiring a set of resources to be available on a buffer, whilst bounding the number of switches of resources on the buffer. We are given:

-A maximum buffer size k i and a minimum buffer usage k i at time i; -A set of resources R = {r 1 , . . . , r m }; -A set of tasks T = {T i } 1≤i≤n , where each task T i ∈ T is associated with the set of resources it requires, that is, ∀i ∈ [1, n], T i ⊆ R.

Example 1. For instance, suppose that we want to embroid n garments. Each garment requires a set of colors. However, only k reels and therefore k different colors of thread can be loaded on the embroidery machine. Hence, whenever we embroid a garment requiring a color of thread that is not already mounted on the machine, we need to switch it with one of the currently mounted reels. Each such switch is time consuming. Therefore, the goal is to sequence the garments so that we minimize the number of reel changes. In other words, we want to compute a permutation of the tasks p : [1, n] → [1, n] and an assignment σ : [1, n] → 2 R of the buffer over time such that the items required by each task are buffered

(∀1 ≤ i ≤ n, T i ⊆ σ(p i )), the size of the buffer is not exceeded (k i ≤ | σ(i)| ≤ k i ) and the number of switches 1≤i<n | σ(i + 1) \ σ(i)| is minimized.
We introduce the BufferedResource constraint to model this pattern. We shall see that this constraint is NP-hard (even if the buffer's size is fixed). Hence, throughout the rest of the paper we shall consider a decomposition:

. ∀i, j ∈ [1, n], i = j → X i = X j (X 1 , . . . , X n is a permutation) 2. ∀i ∈ [1, n], k i ≤ |S i | ≤ k i (
BufferedResource(X 1 , . . . , X n , S 1 , . . . , S n , [k 1 , . . . , k n ], [k 1 , . . . , k n ], M ) ⇔ AllDifferent(X 1 , . . . , X n ) ∧ ∀i ∈ [1, n], k i ≤ |S i | ≤ k i ∧ ∀i, T i ⊆ S Xi ∧ Switch([S 1 , . . . , S n ], [k 1 , . . . , k n ], [k 1 , . . . , k n ], M )
And in particular the constraint Switch, defined as follows:

∀i ∈ [1, n], k i ≤ |S i | ≤ k i ∧ 1≤i<n |S i+1 \ S i | ≤ M Example 1 (Continued)
. Assume that we want to embroid 5 garments, each requiring one of 5 colors as shown in Fig. 1a, on a machine with 3 reels of thread. Let the domains shown Fig. 1b represent the possible permutations at some point during search. To this sequence of variables corresponds a sequence of set variables shown in Fig. 1c. Whereas the BufferedResource constraint defines the possible combinations for all X's and S's, the constraint Switch involves only the set variables. We illustrate a support for Switch with M = 2 in Fig. 1d and a feasible solution for BufferedResource corresponding to the permutation 2, 1, 3, 4, 5 with 4 switches in Fig. 1e. Proof. We reduce Hamiltonian path (on undirected graphs) to the problem of finding a satisfying solution to BufferedResource. Let G = (V, E) be an undirected graph with |V | = n and |E| = m. We build an instance of BufferedResource on the integer variables [X 1 , . . . , X n ], the set variables [S 1 , . . . , S n ] and switch variable M .

T1 = {B, G, Y } T2 = {B, G, R} T3 = {W, Y } T4 = {B, R, W } T5 = {R, W, Y } (a) Garments X1 = {1, 2} X2 = {1, 2} X3 = {3, 4, 5} X4 = {3, 5} X5 = {4, 5} (b) Perm. {B, G} ⊆ S1 ⊆ {B, G, R, Y } {B, G} ⊆ S2 ⊆ {B, G, R, Y } {R} ⊆ S3 ⊆ {B, R, W, Y } {W, Y } ⊆ S4 ⊆ {R, W, Y } {R, W } ⊆ S5 ⊆ {B, R, W, Y } (c) Buffer bounds S1 = {B, G, R} S2 = {B, G, R} S3 = {B, W, R} S4 = {Y, W, R} S5 = {Y, R, W } (d) Support S1 = {B, G, R} S2 = {B, G, Y } S3 = {B, W, Y } S4 = {B, W, R} S5 = {Y, W, R} (e) Solution
-For each v i ∈ V , we have a task T i requiring m items, that is, a set T i of cardinality m that contains one value j for every edge e j ∈ E such that v i ∈ e j . In order to make sure that |T i | = m, we use as fillers values appearing in no other task ({i * m + j} 1≤j≤m-d(vi) where d(v i ) is the degree of v i ). -There is one integer variable X i per vertex v i ∈ V with domain {1, . . . , n}.

-There are as many set variables S i as vertices in the graph G, with domains ranging from the empty set to the whole universe of values: {} ⊆ S i ⊆ {1, . . . , (n + 1)m} for each v i ∈ V . The cardinality of each one of these set variables is

k i = k i = m. -The domain of M is set to the single value (n -1)(m -1).
We first show that the existence of an Hamiltonian path entails the existence of a solution of BufferedResource on the construction above. We set the value of X i to the rank of the vertex v i in the Hamiltonian path. Observe that given a permutation, there is a unique valuation of the set variables satisfying the constraint: ∀i ∈ [1, n], S Xi = T i . Consider any two consecutive set variables S j , S j+1 . Their domains correspond to two consecutive vertices in the Hamiltonian path, hence they share exactly one value: the common edge between the two nodes. The number of switches between these two set variables is thus equal to m -1, hence the total number of switches is (n -1)(m -1).

Next we show that the existence of a solution entails the existence of an Hamiltonian path in G. Consider any two consecutive set variables S j , S j+1 , and assume that X i = j and X k = j + 1. There are two cases, either there exists an edge e x = (v i , v k ) in E and then T i ∩ T k = {x} or such edge does not exist, and therefore T i ∩ T k = ∅. Since there are (n -1) consecutive pairs of set variables, and since the only possible value for M is (n -1)(m -1), the first case must hold for every consecutive pair. We can therefore conclude that there exists a path visiting every vertex of the graph exactly once.

⊓ ⊔

Observe that the cardinality of each set variable S i can be as low as 3 since Hamiltonian path is still NP-hard when the maximum degree of a vertex is 3. On the other hand, the proof above requires both the total number of resources and the bound on the number of switches to be large.

Filtering Algorithm for Switch

In this section, we show how bound consistency can be enforced on Switch in O(n 2 d + n 1.5 d 1.5 ) time. First we introduce a greedy algorithm that finds an assignment minimizing the number of switches in O(nd) time where d is the total number of resources. Let L be the number of switches of that assignment. Then we introduce a filtering procedure based on a network flow representation. The cost of the flow represents the number of switches and for each pair S i , v such that v ∈ ub(S i ) there is an edge in the network that can receive a unit of flow if and only if the set S i may contain the value v in a support. Observe that forcing v ∈ S i may never entail more than two extra switches in the optimal assignment with L switches. Therefore, we need to prune the set variables only if the difference between L and the upper bound of M is at most 1.

The algorithm we propose therefore proceeds as follows. First, we compute a flow of minimum cost, which is a support, and provides a lower bound on M . Then, if max(M )min(M ) ≤ 1, we consider the residual graph with respect to this flow, and re-weight the edges so as to eliminate negative costs. Then we find all null cycles and, if max(M )min(M ) = 1, all cycles of weight 1. Table 1 summarizes the complexity of these four steps.

Step Complexity Finding an optimal assignment O(nd) Re-weighting the residual graph O((nd) 1.5 ) Finding null cycles

O(nd) Finding cycles of weight 1 O(n 2 d) Total O(n 2 d + n 1.5 d 1.5 )
Table 1: Summary of the algorithm and its complexity.

Finding a Support

We present an algorithm that greedily constructs a support for the Switch constraint. This support is optimal in the sense that it minimizes the number of switches. The algorithm FindSupport (Algorithm 1) successively assigns the variables S 1 to S n to sets σ 1 to σ n . At each step i, the algorithm computes a priority for each value. The lower the priority is for value v, the more likely the value v will belong to σ i . While processing the variables S i for i = 1..n, we maintain for each value v the index next ∈ (v) = min({j | v ∈ lb(S j ), j ≥ i}∪{n+ 1}) that is the smallest variable index no smaller than i such that v ∈ lb(S j ). We also maintain the index next ∈ (v) = min({j | v ∈ ub(S j ), j ≥ i} ∪ {n + 1}) that is the smallest variable index no smaller than i such that v ∈ ub(S j ).

If next ∈ (v) < next ∈ (v), the value v will be required in the sequence S i . . . S n before it gets forbidden. We assign such a value a priority between 1 and n. If next ∈ (v) > next ∈ (v), the value v will be forbidden in the sequence S i , . . . , S n before it gets required. We assign such a value a priority between n+2 and 2n+1. Finally, if next ∈ (v) = next ∈ (v), we assign to value v a priority of n+1. This later case only occurs if the value v is allowed to appear but not required to appear in every variable of the sequence S i , . . . , S n . The insertion of a value that is not required or that does not belong to the previous set σ i-1 induces a unnecessary switch. Such a value is given a penalty of 2n + 1 on its priority. Once the priority is computed, we add the value

l v = prio(v) × (d + 1) + v to a set L.
From l v , we can retrieve the value using the arithmetic operation l v mod (d + 1). Moreover, the smaller the priority is, the smaller the value l v is. The algorithm keeps a counter k of the number of values that can be added to σ i without causing an unnecessary switch, i.e. a switch that is not due to the requirement v ∈ lb(S i ). This counter is the cardinality that will be given to

σ i . If k ∈ [k i , k i ],
we update k to the closest value between k i and k i . We call the algorithm Selection(L, k)

Algorithm 1: FindSupport([S 1 , . . . , S n ], [k 1 , . . . , k n ], [k 1 , . . . , k n ]) for v = 1..d do next∈(v) ← next ∈ (v) ← 1; σ 0 ← ∅; for i = 1..n do L ← ∅, k ← 0; for v ∈ ub(Si) do if next∈(v) < i then next∈(v) ← i; 1 while next∈(v) ≤ n ∧ v ∈ lb(S next∈(v) ) do next∈(v) ← next∈(v) + 1; if next ∈ (v) < i then next ∈ (v) ← i; 2 while next ∈ (v) ≤ n ∧ v ∈ ub(S next ∈ (v) ) do next ∈ (v) ← next ∈ (v) + 1; prio ←    next∈(v) if next∈(v) < next ∈ (v) n + 1 if next∈(v) = next ∈ (v) 2(n + 1) -next ∈ (v) if next∈(v) > next ∈ (v) ; 3 if v ∈ lb(Si) ∧ v ∈ σ i-1 then prio ← prio +2n + 1 else k ← k + 1 L ← L ∪ {prio ×(d + 1) + v}; k ← min(max(k, k i ), ki); lmax ← Selection(L, k); σ i ← {l mod (d + 1) | l ∈ L ∧ l ≤ lmax}; return [σ1, . . . , σ n];
to retrieve the k th smallest element in L. This algorithm has a running time complexity of O(d) when implemented using a divide-and-conquer strategy and a randomized partition algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. We finally retrieve the k smallest elements l v from L and include their respective value v in the set σ i . Some values might share a same priority, the algorithm breaks ties on the lexicographical order of the values in order not to obtain sets with cardinality greater than k. The vector [σ 1 , . . . , σ n ] constitutes an optimal support to the constraint.

Theorem 2. The algorithm FindSupport returns a support of Switch that minimizes the number of switches.

Proof. Let next i ∈ (v), next i ∈ (v)
, and prio i (v) be the values of next ∈ (v), next ∈ (v) and prio(v) at iteration i.

We consider an optimal solution σ that cannot be built by FindSupport. Let θ i be the instantiation of S i by FindSupport and let i be the first index such that θ i = σ i . One of the three following propositions is true:

1. σ i ⊂ θ i , hence ∃v such that |{w | prio i (w) < prio i (v)}| ≤ |θ i |, v ∈ σ i ; 2. θ i ⊂ σ i , hence ∃v such that |{w | prio i (w) < prio i (v)}| > |θ i |, v ∈ σ i ; 3. σ i ⊂ θ i & θ i ⊂ σ i , hence ∃v, w s.t. prio i (v) < prio i (w), v ∈ σ i and w ∈ σ i ; Case 1: Since v ∈ σ i , we have v ∈ lb(S i ) and |θ i | > k i . Therefore, | σ i-1 ∪ lb(S i )| > k i . It follows that v ∈ σ i-1
, hence adding v to σ i does not add any v-switch (and might prevent one latter).

Case 2: Since v ∈ θ i , we have v ∈ lb(S i ) and since v ∈ σ i we have

|θ i | > k i . Therefore, | σ i-1 ∪ lb(S i )| < k i . It follows that v ∈ σ i-1
, hence removing v from σ i suppresses one v-switch (and might entail one latter).

Case 3: From now on, we assume prio i (v) < prio i (w), v ∈ σ i and w ∈ σ i . We now show that for some j > i, we can swap all instances of w for v in the sets σ i , . . . , σ j-1 whilst not increasing the number of switches. Let σ ′ be the solution obtained by this transformation on σ. For each such operation, we get strictly closer to a solution that can be obtained by FindSupport. We say that there is a v-switch at index i in solution σ iff v ∈ σ i \ σ i-1 . Since the transformation only changes indices i to j -1 and values v and w, we only have to count v-switches and w-switches from index i to j.

Notice that prio i (v)

< prio i (w) & w ∈ σ i-1 implies v ∈ σ i-1
. Indeed, in Line 3 of Algorithm 1, we make sure that values in σ i-1 ∪ lb(S i ) have the best priority. Moreover, since w and v can be interchanged, none of them is in lb(S i ).

We first consider the case where only v is in the previous buffer: w ∈ σ i-1 and v ∈ σ i-1 . Let j be the minimum integer greater than i such that either w ∈ σ j or v ∈ σ j or w ∈ lb(S j ) or v ∈ ub(S j ) or j = n + 1. Now we count v-and w-switches on the solutions σ and σ ′ .

-On σ there is a w-switch at index i, and there may be a v-switch at index j.

-On σ ′ there is no v-switch, however there may be a w-switch at index j.

Therefore, in this case the transformation can only decrease the number of switches, or leave it unchanged. Now we consider the case where both v and w are either in or out the previous buffer: w ∈ σ i-1 ⇔ v ∈ σ i-1 . Let j be the minimum integer greater than i such that either w ∈ σ j or v ∈ σ j or j = n + 1. We show that v ∈ ub(S l ) and w ∈ lb(S l ) for all i ≤ l < j, i.e.,

j ≤ next i ∈ (w) and j ≤ next i ∈ (v) (1)
Now, by hypothesis, prio i (w) > prio i (v). There are two cases:

1. next i ∈ (v) < next ∈ (i)v: In this case, next i ∈ (v) < next i ∈ (w). However, v ∈ σ next i ∈ (v) entails j ≤ next i ∈ (v), therefore proposition 1 is correct in this case. 2. next i ∈ (v) ≥ next ∈ (i)v: In this case, next i ∈ (w) ≥ next i ∈ (w) and next ∈ (i)v > next i
∈ (w). However, w ∈ σ next i ∈ (w) we have j ≤ next i ∈ (w), therefore proposition 1 is correct in this case too. Now we count v-and w-switches on the solutions σ and σ ′ .

-On σ there is a w-switch

at index i iff w ∈ σ i-1 . Moreover, if v ∈ σ j there is a v-switch at index j. -On σ ′ : there is a v-switch at index i iff v ∈ σ i-1 . Moreover, if w ∈ σ j there is a w-switch at index j.
By definition of j, w ∈ σ j implies that v ∈ σ j , hence there is a w-switch at index j in σ ′ only if there is a v-switch at index j in σ. Moreover, by hypothesis, w ∈ σ i-1 ⇔ v ∈ σ i-1 . It follows that the number of switches may not increase after the transformation.

⊓ ⊔

The increments on line 1 and 2 are executed at most n times for each value v. The Selection algorithm is called exactly n times and has a running time complexity of O(d). Consequently, the algorithm FindSupport runs in time O(nd).

Network Flow Model

Let σ 1 , . . . , σ n be an optimal solution with L switches, such as the one computed by FindSupport. For any set S i , any value v ∈ ub(S i ) can be inserted into σ i by adding at most 2 more switches (unless | lb(S i )| = k i ). Indeed we can add a value v to S i or replace any value w ∈ S i \ lb(S i ) with v, entailing at most one switch with S i-1 and one switch with S i+1 . Hence no pruning is required unless max(M ) -L < 2,.

We therefore focus on the case where max(M ) -L < 2 and we describe an algorithm that finds the values that can be used without additional switches and the values that require exactly one additional switch.

We construct a network flow G s where every flow of value d represents a solution to the Switch constraint. The network has the following nodes. For every v ∈ ub(S i ), we have the nodes a v i and b v i . For 0 ≤ i ≤ n, we have a collector node C i . The collector node C 0 is the source node and the collector node C n is the sink node.

Each edge has a capacity of the form [l, u] where l is the required amount and u is the allowed amount of flow that can circulate through the edge. The network G s has the following edges:

1. An edge between the node a v i and b

v i for every v ∈ ub(S i ) (a) with capacity [1, 1] if v ∈ lb(S i ); (b) with capacity [0, 1] otherwise.
2. An edge between b v i and a v i+1 of capacity [0, 1] if these two nodes exist.

An edge between b v

i and C i of capacity [0, 1] for 1 ≤ i ≤ n and v ∈ ub(S i ). 4. An edge between C i-1 and a v i of capacity [0, 1] for 1 ≤ i ≤ n and v ∈ ub(S i ).

An edge between C i-1 and C

i of capacity [d -k i , d -k i ] for 1 ≤ i ≤ n.
All edges have a cost of zero except the edges (C i-1 , a v i ) for 2 ≤ i ≤ n and v ∈ ub(S i ) that have a cost of 1. The cost c(f ) of a flow f is the sum, over the edges, of the cost of the edge times the amount of flow on this edge, i.e. c(f ) = (x,y)∈E f (x, y)c(x, y). Proof. We construct a solution σ 1 , . . . , σ n by setting v ∈ σ i if and only if the edge (a v i , b v i ) accepts a unit of flow. Since the flow value is d and there are between dk i and dk i units of flow circulating through the edge (C i-1 , C i ), there are between k i and k i edges (a v i , b v i ) accepting a unit of flow, thus

k i ≤ | σ i | ≤ k i . ⊓ ⊔ Lemma 2.
The cost of a flow in G s gives the number of switches in the solution.

Proof. The amount of flow going out of the collector C i-1 to the nodes a v i indicates the number of switches between S i-1 and S i . Since these edges have a cost of 1, the cost of the flow equals the number of switches in the solution. Note that a flow can go through the nodes b v i-1 , C i-1 , and then a v i which counts as a switch. Such cases do not occur in a minimum-cost flow as the flow could go through the edge (b v i-1 , a v i ) at a lesser cost. ⊓ ⊔

Bound Consistency

The function FindSupport computes a minimum-cost flow with a flow value of d. Let f (x, y) be the amount of flow circulating on the edge (x, y) that has capacity [l, u]. The residual graph G r has the same nodes as the original network but has the following edges. If f (x, y) < u, there is an edge (x, y) with capacity [lf (x, y), uf (x, y)] and cost c(x, y). If f (x, y) > l there is an edge (y, x) with capacity [f (x, y)u, f (x, y)l] and cost -c(x, y). Note that in the residual graph, all costs are either -1, 0, or 1.

Theorem 3. Let f be a flow of minimum cost in G s , and G r the corresponding residual graph, Switch is BC if and only if:

1. For all v ∈ ub(S i ), f (a v i , b v i ) > 0 or the edge (a v i , b v i ) belongs to a cycle of cost lower than or equal to max(M ) -c(f ) in G r . 2. For all v ∈ lb(S i ), f (a v i , b v i )
> 0 and there is no cycle of cost lower than or equal to max(M )c(f ) in G r that involves the edge (b v i , a v i ). Proof. By Lemma 1, we know that a flow in G s corresponds to an assignment of S 1 , . . . , S n that satisfies the capacities of the sets. Moreover, by Theorem 2, we know that the support corresponding to f minimizes the number of switches. Hence, f witnesses the existence of a support for all v

∈ S i such that f (a v i , b v i ) > 0. Now, if f (a v i , b v i ) = 0
, it is known that there is a flow going through the edge (a v i , b v i ) iff there exists a cycle in G r passing by the edge (a v i , b v i ). Moreover, by Lemma 2, the cost of the minimum cycle passing by the edge (a v i , b v i ) gives the number of required additional switches if v ∈ S i is forced. It follows that in this case, v ∈ S i has a support iff there exists a cycle of cost max(M )c(f ) or less going through (a v i , b v i ) in the graph G r .

The flow f satisfies the bounds and capacities of the sets. Therefore, if f (a v i , b v i ) = 0 then v cannot be in the lower bound of S i . Now, suppose that f (a v i , b v i ) > 0. By a reasoning similar as above, we have that there exists a bound support where v ∈ S i iff there exists a cycle of cost max(M )c(f ) or less going through (b v i , a v i ) in the graph G r . Therefore, v ∈ lb(S i ) is entailed iff there is no such cycle.

⊓ ⊔

Recall that we assume max(M ) ≥ c(f ) + 2 where c(f ) is the number of switches in an optimal solution. Therefore, we are interested to find all cycles of cost 0 and 1. We now describe how can this be done efficiently.

Since computing the minimum cycles is as hard as finding shortest paths, we first perform a preprocessing operation that will eliminate negative weights in the residual graph. This preprocessing is the same as the one used in Johnson's allpair shortest path algorithm and was also used by Régin to filter Cost-GCC [START_REF] Régin | Cost-based arc consistency for global cardinality constraints[END_REF].

We add a dummy node z to the residual graph that is connected to all other nodes with an edge of null cost. We compute the shortest path from the dummy node z to all other nodes. This can be done using Goldberg's algorithm [START_REF] Goldberg | Scaling Algorithms for the Shortest Path Problem[END_REF] which computes the shortest path in a graph in O( |V ||E| log W ) time where |V | is the number of vertices, |E| is the number of edges, and W is the greatest absolute cost of an edge. In our case, we have |V | ∈ O(nd), |E| ∈ O(nd), and W = 1 which leads to a complexity of O((nd) 1.5 ). Let π(x) be the shortest distance between the dummy node z and the node x. Let (x, y) be an edge in the residual graph with cost c(x, y). We re-weight this edge with the cost function

c π (a, b) = c(a, b)+π(a)-π(b).
It is known that with the new cost function, there are no negative edges and that the cost of any cycle remains unchanged.

Finding null cycles in the new re-weighted residual graph becomes an easy problem. Since there are no negative edges, a cycle is null if and only if all its edges have a null cost. We can thus compute the strongly connected components in the graph induced by the edges of null costs. All values v ∈ ub(S i ) such that the edge (a v i , b v i ) belongs to a null cycle has a support without extra switches. To compute the supports with one additional switch, we modify once more the residual graph. We delete all edges with a cost greater than 1. Such edges necessarily lie on a path of weight greater than 1 and are not relevant. Only edges with weight 0 and 1 remain in the graph. We create two copies of the graph. We connect the two copies as follows: if there is an edge (x, y) of cost c π (x, y) = 1, then we delete this edge in both copies and add an edge from x in the first graph to y in the second graph. The intuition is that to travel from a node in the first graph to a node in the second graph, one must pass through an edge of cost 1. Moreover, it is not possible to cross twice such an edge. So all paths in the resulting graph have cost at most 1.

To find a cycle of cost 1 passing by the edge (a v i , b v i ) in the original graph, one needs to find a path from b v i in the first graph to a v i in the second graph. The problem is therefore transformed to a problem of reachability.

Computing whether there is a path from each of the O(nd) nodes b v i to their associated nodes a v i can be done using O(nd) depth first search (DFS) for a total computational time of O(n 2 d 2 ). However, we use a key information to decrease this complexity. We know that to generate one more switch, the flow needs to pass by a collector. We can restrict our search to the cycles passing by a collector. For each of the n collectors C i , we can compute with a DFS the nodes F 0 i that can be reached from this collector with a forward path of cost 0 and the nodes F1 i that can be reached with a path of cost 1. While doing the DFS, we use two bitsets to represent F 0 i and F 1 i and flag the nodes in the appropriate bitsets depending whether the node belongs to the first copy of the graph or the second copy. We perform the same operation on the transposed graph to compute the nodes B 0 i and B 1 i that can be reached with a backward path from collector C i with a cost of at most 0 and at most 1. We then compute the set of nodes P ub that lie on a cycle of cost at most 1 that passes by a collector as follows.

P ub = n i=1 F 0 i ∩ B 1 i ∪ F 1 i ∩ B 0 i (2)
For every v ∈ ub(S i ) such that v ∈ σ i and a v i ∈ P ub , then it is possible to modify the solution σ to obtain a new solution σ ′ with v ∈ σ ′ i . One simply needs to push one unit of flow on the cycle on which lies the node a v i . Since this node has (a v i , b v i ) has unique outgoing edge in the residual graph, the new flow will pass by (a v i , b v i ) and will have at most one more switch. We use the same idea to test whether v ∈ S i has a bound support whenever f (a v i , b v i ) > 0. We compute the set P lb that contains all indices i such that there does not exist a cycle of cost at most 1 that passes by a collector and by the edge (b v i , a v i ) as follows.

P lb = {i | ∃j s.t. (a v i ∈ B 0 j ∧ b v i ∈ F 1 j ) ∨ (a v i ∈ B 1 j ∧ b v i ∈ F 0 j )} (3)
For every v ∈ lb(S i ) such that v ∈ σ i and i ∈ P lb , then it would not be possible to modify the solution σ to obtain a new solution σ ′ with v ∈ σ ′ i . Indeed there is no alternative for the unit of flow going through (a v i , b v i ) without increasing the cost above max(M ). We can therefore deduce that v should be added to lb(S i ).

Each of the n DFS runs in time O(nd). The union and intersection operations required for the computation of P ub and P lb can be done using bitwise conjunction and disjunctions in time O(n 2 d). So the computation of the cycles are done in time O(n 2 d).

Experimental Evaluation

We tested our propagator for Switch on two optimization problems based on industrial applications. However, they have been somewhat abstracted and simplified for the purpose of our experiments. Moreover, we randomly generated two sets of instances. 1 All experiments were run on Intel Core i5 2.30GHz machine with 6GB of RAM on Windows 7. For each problem, we have generated 50 instances of four classes, each defined by a tuple of parameters. We compare two Choco programs that differ in the representation of the objective function. In the first model it is decomposed into a sum of reified LessThan (<) constraints. In the second model, the objective function is represented using a single Switch constraint (for the first problem), or several (for the second problem). All other constraints are the same in both models. Finally, we used two search heuristics (Impact-based Search [START_REF] Refalo | Impact-Based Search Strategies for Constraint Programming[END_REF] and the Domain over Weighted Degree Heuristic [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF], denoted respectively Impact and Wdeg).

Embroidery Scheduling. This first problem is derived from a real life scheduling problem in the textile industry involving job-dependent setup times.

A set of n garments have to be embroidered using m machines. Each garment is characterized by a set col i ⊆ {1, . . . , k} of colors required for embroidering a given pattern. Last, at most c j reels of threads can be mounted on machine j (i.e., at most c j colors of threads can be used without changing the reels).

The load on each machine must be balanced, so we assume that each machine will process n/m garments. A feasible solution for this problem is a mapping of the garments to the machines f : {1, . . . , n} → {1, . . . , m}. Moreover, each garment i must be assigned a position s i on the machine it is assigned to, and for each machine j the set of colors of threads S j g available when processing the the g th garment must be sufficient for embroidering that garment (Eq. 5) while taking into account the maximum number of reels that can be mounted on each machine (Eq. 6). However, whenever the next garment to be embroidered requires a color of thread that is not loaded on the machine, one need to turn the machine off, change some reels and restart the machine. The number of reel changes must therefore be minimized (Eq. 4). minimize :

1≤j≤m 1≤g<n/m |S j g+1 \ S j g | (4)
subject to : ∀i ∈ {1, . . . , n} col i ⊆ S

f (i) s(i) (5)
∀j ∈ {1, . . . , m}, g ∈ {1, . . . , n/m} |S j g | ≤ c j

We have a set of n integer variables with domain {1, . . . , m} standing for the mapping of garments to position in the sequence (we consider here the whole sequence obtained by concatenating the sequences on each machine). Then we have n set variables, one for each garment and standing for the set of colors of threads on the machine when embroidering the i th garment. Then we used a set of Element constraints to channel these two sets of variables. In the first model, the objective function is implemented through a decomposition using a Sum of reified LessThan and Member constraints. In the second model, the objective is stated as a sum of m Switch constraints (one per machine).

Test Sequencing. Next we consider the design of validation tests. A set of n tests have to be performed in order to verify a system involving a set F of k features. A test i is defined by a set on i ⊆ F of features that must be turned ON, and a set of f i ⊆ F \ on i of features that must be turned OFF while doing the test.

A configuration is a complete characterization of the system, represented by the set C j ⊆ F of features that are ON (all other features are considered OFF).

The verification will go through m phases during which the system will be in a given configuration, and a subset of the tests will be performed. A feasible solution is a sequence of m configurations [S 1 , . . . , S m ] and a mapping of the tests to a phase f : {1, . . . , n} → {1, . . . , m} such that each test is compatible with the configuration in which it is done (Eq. 8). Moreover, there are restrictions on the number of features that can be ON simultaneously (Eq. 9). Finally, the total duration of the test campaign depends on the set of features that need to be turned ON during the transitions between two configurations (Eq. 7).

minimize :

1≤j<m |S j+1 \ S j |

subject to :

∀j ∈ {1, . . . , m} l ≤ |S j | ≤ u (8) ∀i ∈ {1, . . . , n} on i ⊆ S f (i) & of f i ∩ S f (i) = ∅ (9)
We use two straightforward models for this problem. In both models, we have a set of n integer variables with domain {1, . . . , m} standing for the mapping between tests to phases and m set variables standing for the configuration during phase j. Then we use a set of Element constraints to channel these two sets of variables. In the first model, the objective function is implemented through a decomposition using a Sum of reified LessThan and Member constraints. In the second model, the objective is stated as a Switch constraint.

Results. We generated 4 classes of 50 instances, for each of the two problems, parameterized respectively by number of garments, colors and machines, and number of tests, features and configurations. For each class, we report the mean value of the objective function over time in both models. Results are shown in Figure 3 and Figure 4, for the Embroidery and Test Sequencing problems, respectively. These curves were obtained by averaging the step functions corresponding to the runs of one algorithm on every instance of the class.

We observe that the model using the propagator for Switch clearly outperforms the decomposition model. In particular, the decomposition does not seem able to significantly improve the objective after the initial drop. It is interesting to notice that whilst Wdeg outperforms Impact on the decomposition model, it is slightly worse in the model using the global constraint (except for the classes 100, 2, 5 in the Embroidery benchmark and 300, 10, 15 for the Test Sequencing benchmark). This is actually not surprising since Wdeg relies heavily on the shape of the constraint network and is severely hindered when using a global constraint. Despite this, the propagator yields better results, irrespective of the heuristic that is used. On the Embroidery problem, the improvement on the objective value obtained by using the propagator ranges from 32 to 48% (counted on the best heuristic in each case). On the Test Sequencing problem, we observe more modest but still sizeable improvements, ranging from 12 to 29%.

Conclusion

We have introduced the constraints BufferedResource and Switch to reason about the number of item switches in a buffered resource. The former constraint is NP-hard, however it can be effectively decomposed using the latter in conjunction with an AllDifferent. We have introduced a linear algorithm to find a support to the Switch constraint, that is, to assign a sequence of set variables standing for the buffer so that the number of switches is minimized. Furthermore, using this algorithm and a flow-based model, we have shown that bound consistency can achieved in O(n 2 d + n 1.15 d 1.5 ) time. Finally, our experimental results show that this propagator is a significant improvement with respect to expressing this relation with primitive constraints.

Fig. 1 :Theorem 1 .

 11 Fig. 1: Illustration of Example 1.

Figure 2 Lemma 1 .

 21 shows the network flow of Example 1. Each flow of value d in G s corresponds to an assignment of the Switch constraint where capacities are satisfied.

Fig. 2 :

 2 Fig. 2: The network flow associated to the Switch constraint of Example 1. Bold edges represent the flow. A pair of nodes (a v i , b v i ) in bold indicates that v ∈ lb(S i ) and that the flow must go through the edge (a v i , b v i ).

Fig. 3 :

 3 Fig. 3: Embroidery: #switches over time

Fig. 4 :

 4 Fig. 4: Test Sequencing: #switches over time

  |S i+1 \ S i | ≤ M (the number of switches is less than or equal to M )

	4.
	the buffer has a bounded capacity)
	3. ∀i, T i ⊆ S Xi (when a task is processed, all required resources are buffered)

1≤i<n

  Definition 2 (Switch). Let S 1 , . . . , S n be set variables, k i a lower bound on the cardinality of S i , k i an upper bound on the cardinality of S i , and M an integer variable. The constraint Switch([S 1 , . . . , S n ], [k 1 , . . . , k n ], [k 1 , . . . , k n ], M ) holds if and only if:

Available at http://homepages.laas.fr/ehebrard/switch/


Radu Tudoran
email: radu.tudoran@inria.fr

Alexandru Costan
email: alexandru.costan@irisa.fr

Gabriel Antoniu
email: gabriel.antoniu@inria.fr

Transfer as a Service: Towards a Cost-Effective Model for Multi-Site Cloud Data Management

The global deployment of cloud datacenters is enabling large web services to deliver fast response to users worldwide. This unprecedented geographical distribution of the computation also brings new challenges related to the efficient data management across sites. High throughput, low latencies, cost-or energy-related trade-offs are just a few concerns for both cloud providers and users when it comes to handling data across datacenters. Existing cloud data management solutions are limited to cloud-provided storage, which offers low performance based on rigid cost schemas. Users are therefore forced to design and deploy custom solutions, achieving performance at the cost of complex system configurations, maintenance overheads, reduced reliability and reusability. In this paper, we are proposing a dedicated cloud data transfer service that supports largescale data dissemination across geographically distributed sites, advocating for a Transfer as a Service (TaaS) paradigm. The system aggregates the available bandwidth by enabling multiroute transfers across cloud sites. We argue that the adoption of such a TaaS approach brings several benefits for both users and the cloud providers who propose it. For users of multi-site or federated clouds, our proposal is able to decrease the variability of transfers and increase the throughput up to three times compared to baseline user options, while benefiting from the well-known high availability of cloud-provided services. For cloud providers, such a service can decrease the energy consumption within a datacenter down to half compared to user-based transfers. Finally, we propose a dynamic cost model schema for the service usage, which enables the cloud providers to regulate and encourage data exchanges via a data transfer market.

I. INTRODUCTION

With their globally distributed datacenters, cloud infrastructures enable the rapid development of large scale applications. Examples of such applications running as cloud services across sites range from office collaborative tools (Microsoft Office 365, Google Drive), search engines (Bing, Google), global stock market financial analysis tools to entertainment services (e.g., sport events broadcasting, massively parallel games, news mining) and scientific applications [START_REF]Azure Succesful Stories[END_REF]. Most of the web-based applications are deployed on multiple sites to leverage proximity to users through content delivery networks. Besides serving the local client requests, these services need to maintain a global coherence for mining queries, maintenance or monitoring operations, that require large data movements. Studies show that the inter-datacenter traffic is expected to triple in the following years [START_REF] Kosar | Storkcloud: Data transfer scheduling and optimization as a service[END_REF], [START_REF] Laoutaris | Interdatacenter bulk transfers with netstitcher[END_REF]. This geographical distribution of computation becomes increasingly important for scientific discovery as well. Processing the large amounts of data (e.g., 40 PB per year) generated by the CERN LHC overpasses single site or single institution capacity, as it was the case for the Higgs boson discovery, where the processing was extended to the Google cloud infrastructure [START_REF]Cloud Computing and High-Energy Particle Physics: How ATLAS Experiment at CERN Uses Google Compute Engine in the Search for New Physics at LHC[END_REF]. Accelerating the process of understanding data by partitioning the computation across sites has proven effective also in solving bio-informatics problems [START_REF] Costan | TomusBlobs: Scalable Data-intensive Processing on Azure Clouds[END_REF]. However, the major bottlenecks of these geographically distributed computations are the data transfers, which incur high costs and significant latencies [START_REF] Cho | Budget-constrained bulk data transfer via internet and shipping networks[END_REF].

Currently, the cloud providers' support for data management is limited to the cloud storage (e.g., Azure Blobs, Amazon S3). These storage services, accessed through basic REST APIs, are highly optimized for availability, enforcing strong consistency and replication [START_REF] Calder | Windows azure storage: a highly available cloud storage service with strong consistency[END_REF]. Clearly, they are not well suited for end-to-end transfers, as this was not their intended goal: users need to upload data into the remote persistent storage, from where it becomes then available for download to the other party. In case of inter-site data movements, the throughput is drastically reduced by the high latency of the cloud storage and the low interconnecting bandwidth. Recent developments led to alternative transfer tools such as Globus Online [START_REF] Foster | Campus bridging made easy via globus services[END_REF] or StorkCloud [START_REF] Kosar | Storkcloud: Data transfer scheduling and optimization as a service[END_REF]. Although such tools are more efficient than the cloud storage, they act as third party middleware, requiring users to setup and configure complex systems, with the overhead of dedicating some of the resources (initially leased for computation) to the data management. Our goal is to understand to what extent and under which incentives the inter-datacenter transfers can be externalized from users and be provided as a service by the cloud vendors.

In our previous work [START_REF] Tudoran | Bridging data in the clouds: An environment-aware system for geographically distributed data transfers[END_REF] we have proposed a user managed transfer tool that was monitoring the cloud environment for insights on the underlying infrastructure, used to choose the best combination of protocol and transfer parameters. In this paper, we investigate how such a tool can be "democratized" and offered transparently by the cloud provider, using a Transfer as a Service (TaaS) paradigm. This shift of perspective comes naturally: instead of letting users optimize their transfers by making (possible false) assumptions about the underlying network topology and performance through intrusive monitoring, we delegate this task to the cloud provider. Indeed, the cloud owner has extensive knowledge about its network resources, which it can exploit to optimize (e.g., by grouping) user transfers, as long as it provides a service to enable them. Our working hypothesis is that such a service will offer slightly lower performances than a highly-optimized dedicated userbased setup (e.g., based on multi-routing through extensive use of network parallelism) but substantial higher performance than todays' state-of-the-art transfer solutions (e.g., using the cloud storage or GridFTP). In turn, this approach has the advantage of freeing users from the burden of configuring and maintaining complex data management systems, while providing the same availability guarantees as for any cloud managed service.

We argue that by adopting TaaS, cloud providers achieve a key milestone towards the new generation datacenters, expected to provide mixed service models for accommodating the business needs to exchange data [START_REF] Bishop | Data center 2.0 a roadmap for data center transformation[END_REF]. In [START_REF] Greenberg | The cost of a cloud: Research problems in data center networks[END_REF], the authors emphasize that the network and the system innovation are the key dimensions to reduce costs. Cloud providers rent the interconnecting bandwidth between datacenters from Tier 1 Internet Service Providers and get discounts based on the committed transfer levels [START_REF] Valancius | How many tiers?: Pricing in the internet transit market[END_REF]. Coupled with the flexible pricing schema that we propose, TaaS can regulate the demand and increase the number of users which move data. Enabling fast transfers through simple interfaces, as advocated by TaaS, cloud providers can therefore grow their outbound traffic and increase the associated revenues.

Our contributions can be summarized as follows:

• We introduce two user managed options for data transfers in the cloud (Section II) • We propose an architecture for a dedicated cloud TaaS, targeting high performance inter site transfers, and we discuss its declinations (Section III) • We perform a thorough comparison between the userand the cloud-managed strategies in different scenarios, considering several factors that can impact the throughput (concurrency, data size, CPU load etc.) (Section IV) • We propose a flexible pricing schema for the service usage, that enables a "data transfer market" (Sections V-A,V-B) • We analyze the energy efficiency of user-versus cloudmanaged inter site transfers (Section V-C) • We provide an overview of the cloud data management solutions and their issues (Section VI)

II. CONTEXT OF DATA MANAGEMENT IN THE CLOUD

We first introduce the terminology used throughout this paper and present the existing user-managed options for data transfers.

A. The cloud ecosystem

Our proposal relies on the following concepts:

The datacenter (the site) is the largest building block of the cloud. Public clouds typically have tens of datacenters distributed in different geographical areas, each datacenter holding both storage and computation nodes. The compute infrastructure is partitioned in multiple fault domains, delimited by rack switches. The physical resources of a node are shared among several VMs, generally belonging to different users, unless the largest VM type is running, which is fully mapped to a physical node. Cloud providers do not own the backbone that interconnects datacenters; instead, they pay for the inter-site traffic to Tier 1 ISPs. Multiple network links interconnect the physical nodes within a site with the ISP infrastructure [START_REF] Greenberg | The cost of a cloud: Research problems in data center networks[END_REF], for higher performance and availability. The deployment is the virtual space that aggregates several VMs, in which a user application is executed. The VMs are placed on different compute nodes in separate fault A deployment runs within a single data-center and the number of cores that can be leased within a deployment is often limited (e.g., in Azure that is 300 cores / deployment). This means that large scale applications, using several thousand cores, need to be distributed across multiple deployments, on multiple sites. The storage can be used as a high-latency intermediate for data transfers through some basic store (PUT) or retrieve (GET) operations. For inter-site transfers, choosing the best temporary storage location is not trivial. Putting data at the destination side, at the sender side or in-between is ambiguous and depends on the access pattern. Adding to the high latencies and low throughput this increased sensitivity to each particular transfer, the cloud storage is clearly an inefficient option for common transfers.

B. User-managed inter-site transfer scenarios

Users can set up their own tools to move data between deployments, through direct communication, without intermediaries, at higher transfer rates. They can adhere to two transfer strategies, depending on their cost and performance requirements:

Endpoint to endpoint solutions leverage the basic transfers from source to destination, regardless the technology used (e.g., GridFTP, scp, etc.). This baseline option is relatively simple to set in place, using the public endpoint provided for each deployment. The major drawback in this scenario is the low bandwidth between sites, which limits drastically the throughput that can be achieved. Multi-route transfers. Building on the observations that a user application typically runs on multiple VMs and that communication between datacenters follows different physical routes, we have proposed in [START_REF] Tudoran | Bridging data in the clouds: An environment-aware system for geographically distributed data transfers[END_REF] a multi-route transfer strategy illustrated in Figure 1. Such a schema exploits the intra-site low-latency bandwidth to copy data to intermediate nodes within the deployment. Next, this data is forwarded towards the destination across multiple routes, aggregating additional bandwidth between sites. This approach is better suited for managing Big Data, but comes at an increased costs: the performance speedup is sub-linear with respect to the leased resources (i.e., N times more intermediate nodes do not provide N times faster throughput). The factors which limit the speedup are the (small) overhead of inner-deployment transfers and the congestions in ISP infrastructures. The main issue with these user-managed solutions is that they are not available out-of-the-box. For instance, prohibiting factors to deploy the multi-route strategy range from the lack of user networking and cloud expertise to budget constraints. Applications might not tolerate even low intrusiveness levels linked to handling data in the intermediate nodes. Finally, scaling up VMs for short time periods to handle the transfer is currently strongly penalized by the VM startup times.

From the cloud provider perspective, having multiple users that deploy multi-route systems can lead to an uncontrolled boost of expensive Layer 1 ports towards the ISP [START_REF] Greenberg | The cost of a cloud: Research problems in data center networks[END_REF]. Bandwidth saturation or congestion at the outer datacenter switches are likely to appear. The bandwidth capacity towards the Tier 1 ISP backbones, with a ratio of 1:40 or 1:100 compared to the bandwidth between nodes and Tier 2 switches, can rapidly be overwhelmed by the number of users VMs staging-out data. Moreover, activating many rack switches for such communications increases the energy consumption as demonstrated in Section V-C. Our goal is to find the right trade-off between the (typically contradicting) cloud providers economic constraints and users needs.

III.ZOOM ON THE TRANSFER AS A SERVICE

We argue that a cloud-managed transfer service could substitute the user-based mechanisms without significant performance degradations. At the core of such a service lies a set of dedicated nodes within each datacenter, used by the cloud provider to distribute the transferred data and to further forward it towards the destination. As opposed to our previous approach, the dedicated nodes are owned and managed by the cloud provider, they no longer consume resources from the users deployments. Building on elasticity, the service can accommodate fluctuating user demands. Multiple parallel paths are then used for all chunks of data, leveraging the fact that the cloud routes packages through different switches, racks and network links. This approach increases the aggregated inter-datacenter throughput and is based on the empirical observation that intra-site transfers are at least 10x faster than the wide-area transfers.

The proposed architecture makes the service locally available to all applications within a datacenter, as depicted in Figure 2. The usage scenario consists in: 1) applications transferring data through the intra-site low-latency links to this service; and 2) the service forwarding the data across multiple routes towards the destination. The transfer process becomes transparent to users, as the configuration, operation and management are all handed to the cloud provider (cloudified), making it resilient to administrative errors.

When the TaaS approach is available at only one endpoint of the transfer, it can be viewed as an asymmetric service. This is often the case within federated clouds, where some providers may not propose TaaS. Users can still benefit from the service when migrating their data to computation instances located in different infrastructures. Such an option is particularly interesting for scientific applications which rely on hybrid clouds (e.g., scaling up the local infrastructure to public clouds). The main advantage with this architecture is the minimal number of hops added between the source deployment and the destination, which translates into smaller overheads and lower latencies. However, situations can arise when the network bandwidth between datacenters might still not be used at its maximum capacity. For instance, applications which exchange data in real-time can have temporary lower rates of transferred packages. Taking also into account that the connection to the user destination is direct, multiplexing data from several users is not possible. In fact, as only one end of the transmission over the expensive inter-site link is controlled by the cloud vendor, communication optimizations are not feasible. To enable them, the cloud provider should manage both ends of the inter-site connection.

We therefore advocate the use of the symmetric solution, in which TaaS is available at both transfer ends. This approach makes better use of the inter-datacenter bandwidth, and is particularly suited for transfers between sites of the same cloud provider. With this architecture, the TaaS is deployed on every datacenter and when an inter-site transfer is performed, the local service forwards the data to the destination service, which further delivers it to the destination node, as depicted in Figure 3. This approach enables many optimizations which only require some simple pairwise encode/decode operations: multiplexing data from different users, compression, deduplication, etc. Such optimizations, which were not possible with the asymmetric solution, can decrease the outbound traffic, to the benefit of both users and cloud providers. Moreover, the topology of the datacenter can now be taken into account by the cloud provider when partitioning the nodes of the service, such that load is balanced across the Tier 2 switches. Enabling this informed resource allocation has been shown to provide significant performance gains [START_REF] Tudoran | Datasteward: Using dedicated compute nodes for scalable data management on public clouds[END_REF]. Despite the potential lower performance compared to the symmetric solution, due to the additional dissemination step at destination, this approach has the potential of bringing several operational benefits to the cloud provider. The service is accessed through a simple API, that currently implements send and receive functions. Users only need to provide a pointer to their data and the destination node to perform a high performance, resilient data movement. The API can be further enhanced to allow experienced users to configure several transfer parameters (e.g., chunk size, number of routes).

IV. EVALUATION

In this section we analyze the performance of our proposal and compare it to user managed schemas through experiments focusing on realistic usage scenarios. The working hypothesis is that user based transfers are slightly more efficient but a cloud service can deliver comparable performance with less administrative overhead, lower costs and more reliability guarantees.

A. Experimental setup

The experiments were performed on the Microsoft Azure cloud, using two datacenters: North Central US, located in Chicago, and North Europe, located in Dublin, with data being transferred from US towards EU. These distant sites were selected in order to ensure a wide geographical setup across continents, with high-latency interconnecting links crossing the Atlantic ocean and communication paths across the infrastructures belonging to multiple ISPs. Considering the time zone differences between sites, the experiments are relevant both for typical user transfers and for cloud maintenance operations (e.g., bulk backups, inter-site replication). The latter are regularly performed by cloud providers and allow the TaaS approach to be further tuned in order to take into account the hourly loads of datacenters, as discussed in [START_REF] Laoutaris | Interdatacenter bulk transfers with netstitcher[END_REF].

The cloud is used at the Platform as a Service (PaaS) level with Azure Web Roles running Small and xLarge VMs. The Small VM type is the elementary resource unit in Azure, offering 1 virtual CPU, mapped to a physical CPU, 1.75 GB memory, 225 GB local ephemeral storage. The xLarge VM type spans over an entire physical node, offering 8 virtual CPUs, 14 GB memory and 2 TB ephemeral local disk. From the network point of view, a physical node in Azure is connected through a 1 Gbps Ethernet card, meaning that an xLarge VM will benefit entirely from it, while a Small VM might get only one eighth of the network when other user VMs are deployed on the same physical node.

The experiments are performed by repeatedly transferring data chunks of 64 MB each from the memory. The intermediate nodes handle the data entirely in memory, both for user and cloud transfer configurations. For all experiments scaling up

B. User-manged multi-route transfers

We first discuss the throughput gains which can be achieved by users with multi-route transfer strategies. The performance shift is represented in Figure 4 based on the overall cumulative throughput of Small VMs when increasing the number of intermediate nodes. We notice that the gain obtained when scaling up to more nodes is asymptotically bounded as first discussed in [START_REF] Tudoran | Bridging data in the clouds: An environment-aware system for geographically distributed data transfers[END_REF]. However, our previous results do no conclusively show whether the performance bound is caused by a bottleneck at the destination side. To answer this question, we devise a new experiment in which the same sender setup is kept and the destination node is replaced by a xLarge VM, which has eight times more resources than the previously used Small instance. The results show a similar throughput, despite the extra resources, which means that the performance bound is not due to a bottleneck at the destination. This observation prevents wasting resources and increasing costs by using larger VMs when trying to increase the performance. This finding raises a new question: is then the performance bounded due to the sender setup, the bandwidth between the datacenters or both? To answer it we continue by changing the sender VM type too and evaluate all resulting combinations: Small to Small, Small to xLarge, xLarge to Small and xLarge to xLarge. The results are presented in Figure 5. The number of intermediate nodes is 3, which is the upper limit of our resource subscription (i.e., 4 xLarge VMs = 32 cores). Nevertheless, at this point there is no need to go beyond that limit as we have already determined the performance trend in the experiment shown in Figure 4. Contrary to the expectations, using xLarge VMs at the sender does not improve the aggregated throughput. This shows that the interconnecting bandwidth within the sender datacenter has low impact on the overall transfer. However, the topology of the virtual network between the sender and intermediate nodes, scattered based on their size across different physical nodes, fault domains or racks, can increase the overhead for intra-site communication. Using Small VMs is therefore sufficient to aggregate the bandwidth between datacenters. We can conclude that the transfer performance is mainly determined by the number of distinct physical paths through which the packages are routed across the ISP infrastructures connecting the datacenters. Next, we focus on the variability with respect to multiroute transfers. Figure 6 shows the coefficient of variation (i.e., standard deviation/average%) for the throughput measurements in Figure 4. Surprisingly, using multiple paths decreases the otherwise high data transfer variability. This result is explained by the fact that with multiple routes the drops in performance on some links are compensated by bursts on others. The overall cumulative throughput, perceived by an application in this case, tends to be more stable. This observation is particularly important for scientific applications which build on predictability and stability of performance.

C. Evaluating the inter-site transfer options

We present in Figure 7 the comparison between the average throughput of the cloud transfer service and the user-based multi-route strategies. The experimental setup consists of 5 nodes per transfer service dedicated for data handling.

The asymmetric solution delivers slightly lower performance (∼16%) than a user-based multi-route schema. The first factor causing this performance degradation is the overhead introduced by the load balancer that distributes the incoming requests (i.e., from the application to the cloud service) between the nodes. The second factor is the placement of the VMs in the datacenter. For user-based transfers, the sender node and the intermediate nodes are closer rack-wise, some of them being even in the same fault domain. This translates into less congestion in the switches in the first phase of the transfer when data is sent to the intermediate nodes.

For the cloud-managed transfers, the user source nodes and the cloud dedicated transfer nodes clearly belong to distinct deployments, meaning that they are farther apart with no proximity guarantees.

The symmetric solution is able to compensate for the previous performance degradation with the extra nodes at the destination site. The overhead of the additional hop with this approach is therefore neutralized when additional resources are provisioned by the cloud provider. The observation opens the possibility for differentiated cloud-managed transfer services in which different QoS guarantees are proposed and charged differently.

D. Dealing with concurrency

The experiment presented in Figure 8 depicts the throughput of an increasing number of applications using the transfer service in a configuration with 5 intermediate nodes. The goal of this experiment is to assess whether a sustainable quality of service can be provided to the user applications in a highly-concurrent context. Not surprisingly, an increase in the Fig. 8. The average throughput and the corresponding standard deviation for an increasing number of applications using the cloud transfer service concurrently number of parallel applications decreases the average transfer performance per application with 25%. This is generated by the congestion in the transfers to the cloud service nodes and by the limit in the aggregated inter-site bandwidth that can be aggregated by these nodes. While this might seem a bottleneck for providing TaaS at large scale, it is worth zooming on the insights of the experiment to learn how such a performance degradation can be alleviated. We have scaled the number of clients up to the point where their number matches the number of nodes used for the transfer service. Hypothetically, we can consider having 1 node from the transfer service per client application. At this point the transfer performance delivered by the service per application is reduced, but asymptotically bounded, with less than 25% compared to the situation where only one application was accessing the service and all the 5 nodes where serving it. This shows that by maintaining a number of VMs proportional to the number of applications accessing the service, TaaS can be a viable solution and that it can in fact provide high performance for many applications in parallel.

We further notice that under increased concurrency, the performance of the symmetric solution drops more than in the case of the asymmetric one. This demonstrates that the congestion in handling data packets in the service nodes is the main cause of the performance degradation, since its effects are doubled in the case of the symmetric solution. At the same time, the aggregated throughput achieved by the applications using the transfer service would require 3 dedicated nodes from each of them (i.e., 15 nodes in total) compared to 5 or 10 nodes with the asymmetric or the symmetric solution, respectively. Deploying such services would make the inter-site transfers more energy efficient and the datacenters greener.

E. Towards a cloud service for inter-site data transfers

Not all applications afford to fully dedicate several nodes just for performing transfers. It is interesting to analyze to what extent, the computation load from the intermediate nodes can impact the performance of user-based transfers. We present in Figure 9 the evolution of the throughput when the computation done in the intermediate nodes has different CPU loads and execution priorities. All 100% CPU loads were induced using the standardized HeavyLoad tool [START_REF]HeavyLoad[END_REF], while the 40%-50% load was generated using system background threads which only access the memory.

Two main observations can be made based on the results shown in Figure 9. First, the throughput is reduced from 20% to 50% when the intermediate nodes are performing other computation in parallel with the transfers. This illustrates that the IO inter-site throughput is highly sensitive to the CPU usage levels. This observation complements the findings related to the IO behavior discussed in [START_REF] Tudoran | Evaluating streaming strategies for event processing across infrastructure clouds[END_REF] for streaming strategies, in [START_REF] Dorier | Damaris: How to Efficiently Leverage Multicore Parallelism to Achieve Scalable, Jitterfree I/O[END_REF] for storing data in the context of HPC or in [START_REF] Gamage | Protocol responsibility offloading to improve tcp throughput in virtualized environments[END_REF] for the TCP throughput with shared CPUs between several VMs. Second, the performance obtained by users under CPU load is similar, or even worse, to the one delivered by transfer service under increased concurrency (see Figure 8). This gives a strong argument for many applications running in the cloud to migrate towards such a TaaS offered by the cloud provider. Doing so, applications are able to perform high performance transfers while discharging their VMs from secondary tasks other than the computation for which they were rented for.

F. Inter-site transfers for Big Data

In the next experiment larger sets of data ranging from 30 GB to 120 GB are transferred between sites, using the cloud-and the user-managed options (grouped in 4 scenarios). The goal of this experiment is to understand the viability of the cloud services in the context of geographically distributed Big Data applications. The results are displayed in Figured 10 and 11. The experiment is relevant both to users and cloud providers since it offers concrete incentives about the costs (e.g., money, time) to perform large data movements in the cloud. To the best of our knowledge, there are no previous performance studies about the data management capabilities of the cloud infrastructures across datacenters.

Figure 10 presents the transfer times for the 4 scenarios. The baseline user endpoint to endpoint transfer gives very poor performance due to the low bandwidth between the datacenters. In fact, the resulting times can be considered as the upper bounds of user-based transfers (i.e., we do not consider here the even slower options like using the cloud storage). On the other hand, the user-based multi-route option is the fastest, and it can be considered as the lower bound for the transfer times. In-between, the cloud transfer service declinations are up to 20% slower than user-based multi-route but two times faster than the user baseline option.

In Figure 11 we depict the corresponding costs of these transfers. The costs can be divided in two components: the compute cost, paid for leasing a certain number of VMs for the transfer period and the outbound cost, which is charged based on the amount of data exiting the datacenter. Despite taking longer time for the transfer, the compute cost of the user-based endpoint to endpoint is the smallest as it only uses 2 VMs (i.e., sender and destination). On the other hand, user-based multi-route transfers are faster but at higher costs resulted from the extra VMs, as explained in Section II-B and detailed in [START_REF] Tudoran | Bridging data in the clouds: An environment-aware system for geographically distributed data transfers[END_REF]. The outbound cost only depends on the data volume and the cost plan. As the inter-site infrastructure is not the property of the cloud provider, part of this costs represent the ISP fees, while the difference is accounted by the cloud provider. The real cost (i.e., the one charged by the ISP) is not publicly known and depends on business agreements between the companies. However, we can assume that this is lower than the price charged to the cloud customers, giving thus a range in which the price can potentially be adjusted. Combining the observations about the current pricing margins for transferring data with the performance of the cloud transfer service, we argue that cloud providers should propose TaaS as an efficient transfer mechanisms with flexible prices. Cloud vendors can use this approach to regulate the outbound traffic of datacenters, reduces their operating costs, and minimising the idle bandwidth.

V. DISCUSSION

This section analyses the potential advantages brought by a cloud service for inter-site data transfers. From the users perspective, TaaS can offer a transparent and easy-touse method to handle large amounts of data. The service can sustain high throughput, close to the one achieved by users when renting and dedicating for the data handling alone at least 4-5 extra VMs. Besides avoiding the burden of configuring and managing extra nodes or complex transfer tools, the performance cost ratio can be significantly increased.

From the cloud providers points of view, such a service would give an incent to increase customer demand and brings competitive economical and energy advantages. TaaS extends the rather limited cloud data management ecosystem with a flexibly priced service, that supports a data transfer market, as explained in Sections V-A and V-B, and makes the datacenter greener, as shown in Section V-C.

A. Defining the cost margins for TaaS

In our quest for a viable pricing schema, we start by defining the cost structure of the transfer options. The price is based on the outbound traffic and the computation. The outbound cost structure is identical for all transfer strategies while the computational cost is particular to each option:

Outbound Cost:

Size * Cost outbound , where Size is the volume of transferred data and the Cost outbound is the price charged by the cloud provider for the traffic exiting the datacenter.

Computational Cost:

User-managed Endpoint to Endpoint time E2E * 2 * Cost V M , where time E2E is the time to transfer data between the sender and the destination VMs. To obtain the cost, this has to be multiplied with the renting price of a VM:

V M Cost . User-managed Multi-Route time U M R * (2 + N extraV M s ) * Cost V M
, where time U M R is the time to transfer data from the sender to the destination using N extraV M s extra VMs. As before, the cost is obtained by multiplying with the VM cost.

TaaS time CT S * 2 * Cost V M +time CT S * service computecost ,
where time CT S is the transfer time and service computecost is the price charged by the cloud provider for using the transfer service. Hence, this cost is defined as the price for leasing the sender and destination VMs plus the price for using the service for the period of the transfer.

The computation cost paid by users ranges from the cheapest Endpoint to Endpoint option to the more performant, but more expensive, User-managed Multi-Route transfers. These costs can be used as lower and upper margins for defining a flexible pricing schema, to be charged for the time the cloud transfer service is used (i.e., service computecost ). Defining the service cost within these limits correlates with the delivered performance, which is between the same limits of the user-based options. To represent the service computecost as a function within these bounds, we introduce the following gain parameters, that describe the performance proportionality between transfer options: time E2E = a * time U M R = b * time CT S and time CT S = c * time U M R . Based on the empirical observations shown in Section IV, we can concretize the parameters with the following values: a = 3, b = 2.5 and c = 1.2. Rewriting the previous computation cost equation and simplifying terms, we obtain in Equation 1 the cost margins for the service computecost .

2 * CostV M * (b-1) ≤ servicecompute cost ≤ CostV M * 2 + N + 2 * c c (1)
Equation 1 shows that a flexible cost schema is indeed possible. Varying the cost within these margins, a data transfer market for inter-site data movements can be created, giving the cloud provider the mechanisms to regulate the outbound traffic and the demand, as discussed next.

B. Proposal for a data transfer market

Offering diversified services to customers in order to increase usage and revenues are among the primary goals of the cloud providers. We argue that these objectives can be fulfilled by creating a data transfer market. This can be implemented based on the proposed cloud transfer service offered at SaaS level with reliability, availability, scalability, on-demand provisioning and pay-as-you-go pricing guarantees. In Equation 1we have defined the margins within which the service cost can be varied. We illustrate in Figure 12 these flexible prices for the two TaaS declinations (symmetric and asymmetric). The values are computed based on the measurements for transferring the large data sets mentioned in Section IV-F. The cost is normalized and expressed as the price charged when using the service (i.e., the compute cost component) to transfer 1 GB of data. A conversion between the per hour and the per GB usage is possible due to the stable performance delivered by this approach.

The minimal and maximal values in Figure 12 correspond to the user-managed solutions (i.e., Endpoint to Endpoint and Multi-Route). Between these margins, the cloud transfer service can model the price with a range of discretization values. The two TaaS declinations have different pricing schemas due to their performance gap, with the symmetric one being slightly less performant and having a lower price. As for the outbound cost, the assumption we made is that any outbound cost schema offered today brings profit to the cloud provider. Hence, we propose to extend the flexible usage pricing to integrate this cost component, as shown in Figure 13. The main advantage is that the combined cost gives a wider range in which the price can be adjusted. Additionally, it allows cloud providers to propose a unique cost schema instead of charging users separately for the service usage and for the outbound traffic.

A key advantage of setting up a data transfer market for this service is that it enables cloud providers to regulate the traffic. A simple strategy to encourage users to send data is to decrease the price towards the lower bounds shown in Figure 13 in order to reduce the idle bandwidth periods. A price drop would attract users which otherwise would send data by dedicating 4-5 additional VMs, with equivalent performance. Building on such costs and complementing the work described in [START_REF] Laoutaris | Interdatacenter bulk transfers with netstitcher[END_REF], applications could buffer in VMs the less urgent data The price range for the cloud transfer service Fig. 12. The range in which the price for the cloud services can be varied.

and send it in bulks only during the discounted periods. On the other hand, when many users send data simultaneously, independently or using TaaS, the overall performance decreases due to switch and network bottlenecks. Moreover, the peak usage of outbound traffic from the cloud towards the ISPs grows, which leads to lower profit margins and penalty fees for overpassing the SLA quotas [START_REF] Valancius | How many tiers?: Pricing in the internet transit market[END_REF], [START_REF] Hande | Network pricing and rate allocation with content provider participation[END_REF], [START_REF] Shakkottai | Economics of network pricing with multiple isps[END_REF]. It is in the interest of the cloud providers to avoid such situations. With the flexible pricing, they have the means to react to such situations by simply increasing the usage price. With the high prices approaching the ones of user multi-route option, the demand can be temporarily decreased. At this point, it becomes more interesting for users to get their own VMs to handle data.

Adjusting the price strategy on the fly, following the demand, produces a win-win situation for users and cloud providers. Clients have multiple services with different price options, allowing them to pay the desired cost that matches their targeted performance. Cloud providers increase their revenues by outsourcing the inter-site transfers from clients and by controlling the traffic. Finally, TaaS can act as a proxy between ISPs and users, protecting the latter from price fluctuations introduced by the former; after all, cloud providers are less sensitive to price changes than users are, as discussed in [START_REF] Valancius | How many tiers?: Pricing in the internet transit market[END_REF].

C. The energy efficiency of data transfers

When breaking the operating costs of a cloud datacenter, the authors of [START_REF] Greenberg | The cost of a cloud: Research problems in data center networks[END_REF] find that "over half the power used by network equipment is consumed by the top of rack switches". Such a rack switch connects around 24 nodes and has an hourly energy consumption of about 60W, while a server node consumes about 200W [START_REF] Ananthanarayanan | Greening the switch[END_REF]. Our goal is to assess and compare the energy consumed in a datacenter when transferring data using the user-managed multi-route setup (E U M R in Equation 2) and the cloud transfer service (E CT S in Equation 3). We consider N App applications, each using N extraV M s extra nodes to perform user-based multi-route transfers. For simplicity, we use the average transfer time (time) of applications, and then the total energy consumed by the application nodes and switches is:

EUMR = ( NApp * (2 + NextraV M s) 24 * 60W/h + NApp * (2 + NextraV M s * 200W/h)) * time (2)
where the first part of the equation corresponds to the energy used by the rack switches in which the applications nodes are deployed and the last part gives the power used by the nodes. Aggregating the cost components, outbound traffic cost and computation cost, into a unified cost schema for inter-site traffic where the total energy is the sum of: 1) the energy used at the application side (i.e., the sender, destination nodes and the rack switches they activate) and 2) the energy consumed at the transfer service side, by the nodes which operate it (i.e., N odes T aaS ) and the switches connecting them.

Comparing the two scenarios, we obtain in Equation 4the generic ratio for the extra energy used when each user is handling his data on its own:

U ser -basedenergy T aaSenergy = NApp * (2 + NextraV M s) (2 * NApp + N odesT aaS ) * c (4)
When we illustrate this for the configurations used in the evaluation section (N extraV M s = 5, N App = N odes T aaS and c = 1.2), we notice that twice more energy is consumed if the transfers are done by users.

D. One more thing: reliability

A cloud managed transfer service has the advantage of being always available, in line with the reliability guarantees of all cloud services. Requests for transfers are carried over network paths that the cloud provider constantly monitors and optimizes for both availability and performance. This allows to quickly satisfy peaks in demand with rapid deployments and increased elasticity. Cloud providers ensure that a TaaS system incorporates service continuity and disaster recovery assurances. This is achieved by leveraging a highly available load-balanced dedicated nodes-farm to minimize downtime and prevent data losses, even in the event of a major unplanned service failure or disaster. Predictable performance can be achieved through strict uptime and SLAs guarantees.

User managed solutions typically involve hard-to-maintain scripts and unreliable manual tasks, that often lead to discontinuity of service and errors (e.g., incompatibility between new versions of some building blocks of the transfer framework). These errors are likely to cause VM failures and, currently, the period while a VM is stopped or is being rebooted is charged to users. With a TaaS approach, both the underlying infrastructure failures and the user errors are isolated from the transfer itself: they are transparent to users and are not charged to them. This allows to automate file transfer processes and provides a predictable operating cost per user over a long period.

VI.RELATED WORK

The landscape of cloud data transfers is rather rich in user managed solutions, spanning from basic tools for endto-end communication (e.g., scp, ftp, GridFTP) to complex systems that support large-scale data movements for workflows and scientific applications (e.g., GlobusOnline, Stork, Frugal). The common denominator of these solutions is their need to be deployed, fully configured and managed by users, with potentially little networking knowledge. Meanwhile, the only viable cloud provided alternative is the use of the cloud storage, which incurs large latencies and is subject to additional costs. To the best of our knowledge, our proposal is the first attempt to delegate the intra-and inter-cloud data transfers from users to the cloud providers, following a Transfer as a Service paradigm.

The handiest option for handling data distributed across several datacenters is to rely on the existing cloud storage services. This approach allows to transfer data between arbitrary endpoints via the cloud storage and it is adopted by several systems in order to manage data movements over wide-area networks [START_REF] Kosar | A framework for reliable and efficient data placement in distributed computing systems[END_REF], [START_REF] Rizk | Catch: a cloud-based adaptive data-transfer service for hpc[END_REF]. There is a rich storage ecosystem around public clouds. Cloud providers typically offer their own object storage solutions (e.g., Amazon S3 [START_REF]Amazon S3[END_REF], Azure Blobs [START_REF] Calder | Windows azure storage: a highly available cloud storage service with strong consistency[END_REF]), which are quite heterogeneous, with neither a clearly defined set of capabilities nor any single architecture. They offer binary large objects (BLOBs) storage with different interfaces (such as key-value stores, queues or flat linear address spaces) and persistence guarantees, usually alongside with traditional remote access protocols or virtual or physical server hosting. They are optimized for high-availability, under the assumption that data is frequently read and only seldom updated. Most of these services focus on data storage primarily and support other functionalities essentially as a "side effect" Typically, they are not concerned by achieving high throughput, nor by potential optimizations, let alone offer the ability to support different data services (e.g., geographically distributed transfers). Our work aims is to specifically address these issues.

Besides storage, there are few cloud-provided services that focus on data handling. Some of them use the geographical distribution of data to reduce latencies of data transfers. Amazon's CloudFront [START_REF]Amazon CloudFront[END_REF], for instance, uses a network of edge locations around the world to cache copy static content close to users. The goal here is different from ours: this approach is meaningful when delivering large popular objects to many end users. It lowers the latency and allows high, sustained transfer rates. However, this comes at the cost and overhead of replication, which is considerable for large datasets, making it inappropriate for simple end-to-end data transfers. Instead, we don't use multiple copies of data, but rather exploit the network parallelism to allow per transfer optimizations.

The alternative to the cloud offerings are the transfer systems that users can choose and deploy on their own, which we will generically call user-managed solutions. A number of such systems emerged in the context of the GridFTP [START_REF] Allcock | GridFTP: Protocol Extensions to FTP for the Grid[END_REF] transfer tool, initially developed for grids. Among these, the work most comparable to ours is Globus Online [START_REF] Allcock | The globus striped gridftp framework and server[END_REF], which provides high performance file transfers through intuitive web 2.0 interfaces, with support for automatic fault recovery. However, Globus Online only performs file transfers between GridFTP instances, remains unaware of the environment and therefore its transfer optimizations are mostly done statically. Several extensions brought to GridFTP allow users to enhance transfer performance by tuning some key parameters: threading in [START_REF] Liu | A data transfer framework for large-scale science experiments[END_REF] or overlays in [START_REF] Khanna | Using overlays for efficient data transfer over shared wide-area networks[END_REF]. Still, these works only focus on optimizing some specific constraints and ignore others (e.g., TCP buffer size, number of outbound requests). This leaves the burden of applying the most appropriate settings effectively to users. In contrast, we propose a shift of paradigm and demonstrate the advantages of having an optimized transfer service provided by the cloud provider, through a simple and transparent interface.

Other approaches aim at improving the throughput by exploiting the network and the end-system parallelism or a hybrid approach between them. Building on the nework parallelism, the transfer performance can be enhanced by routing data via intermediate nodes chosen to increase aggregate bandwidth. Multi-hop path splitting solutions [START_REF] Khanna | Using overlays for efficient data transfer over shared wide-area networks[END_REF] replace a direct TCP connection between the source and destination by a multihop chain through some intermediate nodes. Multi-pathing [START_REF] Raiciu | Data center networking with multipath tcp[END_REF] employs multiple independent routes to simultaneously transfer disjoint chunks of a file to its destination. These solutions come at some costs: under heavy load, per-packet latency may increase due to timeouts while more memory is needed for the receive buffers. On the other hand, endsystem parallelism can be exploited to improve utilization of a single path. This can be achieved by means of parallel streams [START_REF] Hacker | Adaptive data block scheduling for parallel tcp streams[END_REF] or concurrent transfers [START_REF] Liu | A data transfer framework for large-scale science experiments[END_REF]. Although using parallelism may improve throughput in certain cases, one should also consider system configuration since specific local constraints (e.g., low disk I/O speeds or over-tasked CPUs) may introduce bottlenecks. More recently, a hybrid approach was proposed [START_REF] Yildirim | Network-aware end-to-end data throughput optimization[END_REF] to alleviate from these. It provides the best parameter combination (i.e., parallel stream, disk, and CPU numbers) to achieve the highest end-to-end throughput between two end-systems. One issue with all these techniques is that they cannot be ported to the clouds, since they strongly rely on the underlying network topology, unknown at the user-level (but instead exploitable by the cloud provider).

Finally, one simple alternative for data management involves dedicated tools run on the end-systems. Rsync, scp, ftp are used to move data between a client and a remote location. However, they are not optimized for large numbers of transfers and require some networking knowledge for configuring, operating and updating them. BitTorrent based solutions are good at distributing a relatively stable set of large files but do not address scientists' need for many frequently updated files, nor they provide predictable performance.

VII. CONCLUSION

This paper introduces a new paradigm, Transfer as a Service, for handling large scale data movements in federated cloud environments. The idea is to delegate the burden of data transfers from users to the cloud providers, who are able to optimize them through their extensive knowledge on the underlying topologies and infrastructures. We propose a prototype that validates these design principles through the use of a set of dedicated transfer VMs that further aggregate the available bandwidth and enable multi-route transfers across geographically distributed cloud sites. We show that this solution is able to effectively use the high-speed networks connecting the cloud datacenters and bring a transfer speed-up of up to a factor of 3 compared to state-of-the-art user tools. At the same time, it enables a reduction to half of the energy fingerprint for the cloud providers, while it sets the grounds for a data transfer market, allowing them to regulate the data movements.

Thanks to these encouraging results, we plan to further investigate the benefits of TaaS approaches both for users and cloud providers. In particular, we plan to study new cost models that allow users to bid on idle bandwidth and use it when their bid exceeds the current price, which varies in real-time based on supply and demand. We also see a good potential to use our prototype to study the performance of inter-datacenter or inter-cloud transfers. We believe that cloud providers could leverage this tool as a metric to describe the performance of network resources. As a further evolution, they could provide Introspection as a Service to reveal information about the cost of internal cloud operations to relevant applications.

Fig. 1 .

 1 Fig. 1. Multi-route user transfers

Fig. 2 .

 2 Fig. 2. An asymmetric Transfer as a Service approach

Fig. 3 .

 3 Fig. 3. A symmetric Transfer as a Service approach

Fig. 4 .

 4 Fig. 4. Aggregated throughput from multiple routes towards different types of destination VMs

Fig. 5 .

 5 Fig. 5. The throughput of multiple routes with respect to different combinations of VM types the number of resources, the amount of transferred data is increased proportionally, always handling a constant amount of data per intermediate node. The throughput is computed at the receiver side by measuring the time to transfer a fixed amount of data. Each sample is the average of at least 100 independent measurements.

Fig. 6 .

 6 Fig. 6. The coefficient of variation for an increasing number of routes

AFig. 7 .

 7 Fig. 7. The average throughput and the standard deviation with different transfer options with 5 intermediate nodes used to multi-route the packets.

Fig. 9 .

 9 Fig. 9. Comparing the throughput of the cloud service against user-based multi-route transfers, using 4 extra nodes. The measurements depict the performance while the intermediate nodes are handling different CPU loads

Fig. 10 .

 10 Fig. 10. The time to transfer large data sets using the available options. The user default Endpoint to Endpoint (E2E) option gives the upper bound, while the User-Based Multi Route offers the fastest transfer time. The cloud services, each based on 5 nodes deployments give intermediate performances, closer to the lower bounds

Fig. 11 .

 11 Fig. 11. The cost components corresponding to the transfer of 4 large data sets. a) The cost of the compute resources which perform the transfers, given by their lower and upper bounds. b) The cost for the outbound traffic computed based on the available cost plans offered by the cloud provider.

Fig. 13 .

 13 Fig.[START_REF] Tudoran | Datasteward: Using dedicated compute nodes for scalable data management on public clouds[END_REF].Aggregating the cost components, outbound traffic cost and computation cost, into a unified cost schema for inter-site traffic