Guillaume Aupy

Anne Benoit

Matthieu Journault

Yves Robert

Power-aware replica placement in tree networks with multiple servers per client

Keywords: replica placement, tree network, multiple servers, power-aware algorithm, complexity, discrete speeds placement de répliques, arbres, serveurs multiples, puissance, complexité, vitesses discrètes

In this paper, we revisit the well-studied problem of replica placement in tree networks. Rather than minimizing the number of servers needed to serve all client requests, we aim at minimizing the total power consumed by these servers. In addition, we use the most general (and powerful) server assignment policy, where the requests of a client can be served by multiple servers located in the (unique) path from this client to the root of the tree. We consider multi-modal servers that can operate at a set of discrete speeds, using the dynamic voltage and frequency scaling (DVFS) technique. The optimization problem is to determine an optimal location of the servers in the tree, as well as the speed at which each server is operated. A major result is the NP-completeness of this problem, to be contrasted with the minimization of the number of servers, which has polynomial complexity. Another important contribution is the formulation of a Mixed Integer Linear Program (MILP) for the problem, together with the design of several polynomialtime heuristics. We assess the efficiency of these heuristics by simulation. For mid-size instances (up to 30 nodes in the tree), we evaluate their absolute performance by comparison with the optimal solution (obtained via the MILP). The most efficient heuristics provide satisfactory results, within 20% of the optimal solution.

Introduction

In this paper, we revisit the well-studied problem of replica placement in tree networks. Replica placement in tree networks is an important problem [START_REF] Cidon | Optimal allocation of electronic content[END_REF][START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF][START_REF] Benoit | Replica placement and access policies in tree networks[END_REF], with a broad spectrum of applications, such as electronic, ISP, or VOD service delivery (see [START_REF] Kalpakis | Optimal placement of replicas in trees with read, write, and storage costs[END_REF][START_REF] Cidon | Optimal allocation of electronic content[END_REF][START_REF] Liu | Optimal placement of replicas in data grid environments with locality assurance[END_REF] and additional references in [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF]). The problem is the following: one is given a tree-shaped network where clients are periodically issuing requests to be satisfied by servers. The clients are known (both their position in the tree and their number of requests per time unit), while the number and location of the replicas (also called servers) are to be determined. Clients are leaves of the tree, and requests can be served by one or several internal nodes. Note that the distribution tree (clients and nodes) is fixed in the approach.

Initially, there is no replica; when a node is equipped with a replica, it can process a number of requests, up to its capacity limit. Nodes equipped with a replica, also called servers, can only serve clients located in their subtree (so that the root, if equipped with a replica, can serve any client); this restriction is usually adopted to enforce the hierarchical nature of the target application platforms, where a node has knowledge only of its parent and children in the tree. More precisely, there are three classical policies to serve the requests of a client [START_REF] Benoit | Replica placement and access policies in tree networks[END_REF]: (i) Closest: All requests of a client must be served by the first server located in the path from this client to the root; (ii) Single: All requests of a client must be served by a single server, located anywhere in the path from this client to the root; and (iii) Multiple: The requests of a client can be served by several servers, all located in the path from this client to the root. For instance in the Multiple policy, half the requests of a client can be served by one server, and the other half by another server located higher in this path. In this paper, we study the Multiple policy, because it is the most flexible, hence it will lead to the most efficient solution in terms of both the number of servers and total consumed power.

The classical optimization objective in the literature is the number of servers needed to serve all requests. However, minimizing the total power consumed by the servers has recently become a very important objective, both for economic and environmental reasons [START_REF] Mills | The internet begins with coal[END_REF]. To help reduce power dissipation, multi-modal servers are used: each server has a discrete number of predefined speeds, which correspond to different voltages that the server can be subjected to. State-ofthe-art processors can only be operated with a restricted number of voltage levels, hence with a few speeds [START_REF] Larabel | Intel EIST SpeedStep[END_REF][START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a PC cluster[END_REF]. The power consumption is the sum of a static part (the cost for a server to be on and operated) and a dynamic part. This dynamic part is a strictly convex function of the server speed, so that the execution of a given amount of work costs more power if a server runs at a higher speed [START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a PC cluster[END_REF]. More precisely, a server operated at speed s dissipates s 3 watts [START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks[END_REF][START_REF] Anantha | Jouletrack: A web based tool for software energy profiling[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF]. Faster speeds allow servers to handle more requests per time unit, but at the price of a much higher (supra-linear) power consumption.

A major contribution of this paper is to show that minimizing power consumption is an NP-complete problem, even if the servers are already placed in the network (and without static power). This is to be contrasted with the polynomial complexity of minimizing the number or servers [START_REF] Benoit | Replica placement and access policies in tree networks[END_REF]. Another major contribution is the design of a set of heuristics to minimize power consumption. These heuristics work in two steps: (i) server placement and (ii) request assign-

RR n°8474

ment. The placement step relies on an interesting theoretical result: given a fixed set of servers that should all be used, and assuming continuous speeds, it is possible to optimally assign the requests to these servers in polynomial time. We can therefore easily derive a greedy algorithm to place the servers in the continuous case, because for a given placement, we can directly compute the corresponding optimal power consumption. Of course, assuming continuous speeds is not realistic, but it is a handy simplification of the problem: with continuous speeds, once requests are assigned to servers, each server can operate just at the right speed, namely the sum of its requests, so that selecting the server speeds is immediate. With discrete speeds, the problem is more challenging and may well lead to re-assign the requests, for a given placement of servers.

To see this, we start from the solution with continuous speeds (including the greedy placement and the optimal request assignment). Let r be the number of requests processed by a given server N in the solution with continuous speeds. With discrete speeds, we have to use the smallest speed s that is larger than r, thereby losing a lot of power if the difference sr is large. If it is the case, we can try and re-assign some requests to another server N ′ located upper in the path from N to the tree root. There would then remain only s ′ requests to be served by N , where s ′ is the largest speed that is smaller than r: this saves power locally by avoiding the large sr gap, but we have to re-assign rs ′ requests to another server, and this has a cost that should be balanced with the local gain. Such trade-off decisions are exactly those taken in the request assignment step of the heuristics.

To the best of our knowledge, this paper is the first to propose heuristics for power minimization with multiple servers, hence we cannot use any heuristics from the literature as reference. However, we have derived a Mixed Integer Linear Program (MILP) to compute the optimal solution to the power minimization problem. Using this linear program has (potentially) an exponential cost, but it enables us to assess the absolute performance of the heuristics, at least for small-size problems.

The rest of the paper is organized as follows. Section 2 surveys related work. Section 3 is devoted to a precise statement of the framework. Section 4 assesses the complexity of the power minimization problem, through an intricate NPcompleteness proof. This section also provides the MILP to compute the optimal solution. Section 5 introduces several heuristics to solve the problem. The placement step is an incremental greedy procedure, whose evaluation is based on the optimal solution for request assignment with fixed servers, when assuming continuous speeds. Section 6 reports simulation results and comparisons of the heuristics, together with their absolute performance evaluation: the distance to the optimal solution is computed through the linear program for instances with up to 30 servers.

Related work

Many papers considering the replica placement problem deal with general graphs, while we focus in this work on tree networks. In the problem with a general graph network, it is already difficult to decide which spanning tree to use, in order to optimize some global objective function. A survey of work targeting performance issues can be found in [START_REF] Loukopoulos | An overview of data replication on the Internet[END_REF]. Recently, some work start to tackle energy-related problems. For instance, in [START_REF] Shi | Thermal and Power-Aware Task Scheduling and Data Placement for Storage Centric Datacenters[END_REF], the authors discuss thermal and power-aware task scheduling and data placement heuristics, in the context of a Hadoop system. All problems are NP-hard, and there is no tree structure but rather a set of racks, and a set of data nodes per rack.

For tree networks, a large effort has been spent to optimize the performance of replica placements, assuming that the spanning tree was given, or that the network had a tree structure initially. Most work has focused on the Closest policy, where a client is requested to be served by the closest server on the path towards the root of the tree, see for instance [START_REF] Cidon | Optimal allocation of electronic content[END_REF][START_REF] Liu | Optimal placement of replicas in data grid environments with locality assurance[END_REF]. Kalpakis et al. [START_REF] Kalpakis | Optimal placement of replicas in trees with read, write, and storage costs[END_REF] studied a variant with bi-directional links, and therefore the tree structure may not be respected anymore, and a client may be served by a node that is not its ancestor in the tree. While the problem with a tree structure has polynomial complexity, the bi-directional problem becomes NP-complete.

Following this line of work, we had investigated in our previous work [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF] the complexity of the power-aware replica placement problem with the Closest policy, and proved that the problem becomes NP-complete when the objective is to minimize the total power consumption. We considered servers with several distinct possible speeds, and a server operating at a given speed consumes a power composed of a static part and a dynamic part proportional to the cube of the speed. We keep the same model in this paper, because it is a classical model extensively used when considering dynamic voltage and frequency scaling (DVFS) technique [START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks[END_REF][START_REF] Anantha | Jouletrack: A web based tool for software energy profiling[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF].

The Multiple policy is more flexible than Closest because it loosens placement rules: the requests of a client can be processed by several servers located anywhere in the path from the client to the root. Similarly to the Closest policy, the problem of minimizing the cost of the replica placement can be solved in polynomial time [START_REF] Benoit | Replica placement and access policies in tree networks[END_REF]. However, we are not aware on any other work aiming at optimizing the power consumption on tree networks for this Multiple policy.

Framework

This section is devoted to a precise statement of the framework. We start with a description of the replica placement problem. Then we detail the power consumption model. Finally, we state the objective function, and the corresponding optimization problems.

Replica placement

We consider a distribution tree whose nodes are partitioned into a set of clients C, and a set of N nodes, N . The clients are leaf nodes of the tree, while N is the set of internal nodes. Each client i ∈ C (leaf of the tree) is sending r i requests per time unit to a database object. Internal nodes equipped with a replica (also called servers) can process requests from clients in their subtree. If a server j ∈ N is operated at speed s j , then it can process up to s j requests per time unit. Both the r i 's and the s j 's are assumed to take rational values. Note that it would be easy to allow client-nodes that play both the rule of a client and of a node (possibly a server), by dividing such a node into an internal node and a leaf in the tree.

For each client i ∈ C and each node j ∈ N , r i,j is the number of requests from client i processed by server j. We must have j∈N r i,j = r i for all i ∈ C, i.e., all requests are processed. Furthermore, a server cannot process more requests than its assigned speed, i.e., w j = i∈C r i,j ≤ s j for all j ∈ N , where w j is the load of server j. The set of replicas is defined as R = {j ∈ N | ∃i ∈ C , r i,j > 0} .

Power consumption model

We (realistically) consider discrete speeds. Servers may operate only at a set {s 1 , . . . , s K } of different (rational) speeds, depending upon the number of requests that they have to process per time unit. We assume that 0 ≤ s 1 ≤ • • • ≤ s K , and therefore no server can handle more than s K requests. A server with a load w will therefore operate at speed s k , where s k-1 < w ≤ s k (letting s 0 = -1 for the limit case). The power consumption of a server j ∈ R operated at speed s(j) obeys the classical model, P(j) = P static + s(j) 3 , and the total power consumption P(R) of the solution is the sum of the power consumption of all server nodes:

P(R) = j∈R P(j) = j∈R (P static + s(j) 3 ) = |R| × P static + j∈R s(j) 3 , (1)
where |R| is the total number of servers in the solution.

Optimization problems

The main optimization problem is the Discrete problem: given a distribution tree (with a number of requests per client), decide where to place the servers, and how to distribute client requests among them (which can also be seen as assigning the speed of each server), in order to minimize the total power consumption.

We also consider the sub-problem where the servers are already placed in the tree, Discrete-Placed. The goal is then only to decide how to distribute requests among servers, hence at which speed to operate each server, in order to minimize the total power consumption.

Complexity results

In this section, we establish the NP-completeness of Discrete and Discrete-Placed (Section 4.1). Then in Section 4.2, we provide a Mixed Integer Linear Program (MILP) to solve Discrete.

NP-completeness

Theorem 1. The Discrete and Discrete-Placed problems are NP-complete, even with P static = 0.

Proof. Consider the decision problem associated to Discrete: given a tree network with a set of requests, a set of server speeds, and a bound K on power consumption, can we find a placement of servers and an assignment of the requests to these servers so that the bound K on power consumption is met? The problem is clearly in NP: given the servers and the request assignments, we can compute the load of each server, select the smallest possible speed and compute the total power consumption in polynomial time.

To establish the completeness, we use a reduction from 2-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. We consider an instance I 1 of 2-Partition: given n strictly positive integers a 1 , . . . , a n , does there exist a subset I of {1, . . . , n} such that i∈I a i = i / ∈I a i ? Let S = 1 2 n i=1 a i . We further assume, without loss of generality, that S is an integer, and that a i < S for 1 ≤ i ≤ n.

We build the following instance I 2 of the Discrete problem:

• P static = 0

• We first define two constants (see below for an intuitive explanation):

X = 2n 7n 2 S 4 , (2)
M = 7n 2 X 2 . (3)
• There are K = 2n + 1 possible speeds for servers:

for 1 ≤ i ≤ n,    s i = iX si = iX 1 + 1 3 M ai (iX) 3 -1 9 M ai (iX) 3 2 + 5 81 M ai (iX) 3 3 (4)
and s n+1 = (n + 1)X.

• The tree is a fork with n + 1 internal nodes; node 0 is the root of the tree and node i is a child of node 0, for 1 ≤ i ≤ n. Each internal node i has a unique leaf child with r i requests, where r 0 = (n+1)X -S and r i = s i +a i for 1 ≤ i ≤ n.

• The bound on power consumption is B = (n+1

) 3 X 3 + n i=1 (iX) 3 + M a i - M S + 0.5.
Note that for all i, si is a rational number polynomial in the size of the instance. The size of I 2 is polynomial in the size of I 1 . Let us further define a new set of speeds:

for

1 ≤ i ≤ n, s ′ i = (iX) 3 + M a i 1/3 . (5)
The speeds s ′ i are not part of the instance but they will be used for the proof. Intuitively, si is a close approximation of s ′ i for 1 ≤ i ≤ n. The intuition behind the proof is that there is a server on each node, hence the proof works for both problems (Discrete and Discrete-Placed). Furthermore, the root node will run at speed s n+1 , and it will process exactly (n + 1)X requests. Therefore, S requests can come from its children. Because of the speed configurations, server i has exactly two choices, either speed s i or speed si . The constants X and M ensure that no other speed can be used, because speeds are spaced apart enough. Either server i processes all its requests, and it must run at speed si , or a i requests are forwarded to the root server and server i can then run at speed s i . There can be at most S requests going up (server capacity limit at the root node), and because of the bound on the power consumption, there should be at least S requests going up, hence the 2-partition. Indeed, the power saved when moving from speed s ′ i (and hence almost si ) to speed s i is linear in a i : s

′ 3 i -s 3 i = M a i .
First we prove some preliminary properties on the si 's to ensure that the s ′ i 's are a good approximation and that speeds are spaced apart enough so that each server is restricted to its set of two speeds.

Lemma 1. The following properties hold true:

1. for 1 ≤ i ≤ n, s ′ i ≤ si ; 2. for 1 ≤ i ≤ n, s i + a i = iX + a i ≤ si ; 3. for 1 ≤ i ≤ n, si ≤ (i + 1)X = s i+1 ; 4. n i=1 s ′ 3 i ≤ n i=1 s3 i ≤ n i=1 s ′ 3 i + 0.5 ; 5. for 1 ≤ i ≤ n, si ≤ iX + (M a i ) 1/3 .
Proof. Consider the following functions on [0, 1]:

f 1 : x → (1 + x) 1/3 and f 2 : x → 1+x/3-x 2 /9+5x 3 /81. We have s ′ i = iXf 1 M ai (iX) 3 and si = iXf 2 M ai
(iX) 3 , and note that M ai (iX) 3 ≤ M S X 3 < 1, because M = 7n 2 X 2 and X > 7n 2 S. We prove the five properties:

1. (s i -s ′ i ≥ 0)
We can verify, using several differentiations (or a computer algebra software), that

f 2 (x) -f 1 (x) > 0 for x ∈ [0, 1]. 2. (iX +a i ≤ si ) Thanks to Property 1, si > s ′
i , and showing that s ′ i ≥ s i +a i gives the result:

s ′ i ≥ s i + a i ⇔ (s 3 i + M a i ) 1/3 ≥ s i + a i ⇔ s 3 i + M a i ≥ s 3 i + 3s 2 i a i + 3s i a 2 i + a 3 i ⇔ M ≥ 3(iX) 2 + 3iXa i + a 2 i Because X > a i and n ≥ i ≥ 1, we have M = 7n 2 X 2 ≥ 3(iX) 2 + 3iXa i + a 2 i , hence the result. 3. (s i ≤ (i + 1)X) We have already seen that M ai X 3 < 1, and therefore si ≤ iX 1 + 1 3i + 5 81i = i + 32 81 X ≤ (i + 1)X. 4. ( n i=1 s ′ 3 i ≤ n i=1 s3 i ≤ n i=1 s ′ 3 i + 0.5)
We can verify, using several differentiations (or a computer algebra software), that ∀x ∈ [0, 1],

f 2 (x) 3 -f 1 (x) 3 ≤ x 4 .

RR n°8474

Hence, s3 is

′ 3 i = (iX) 3 f 2 M ai (iX) 3 3 -f 1 M ai (iX) 3 3 ≤ (7n 2 ai) 4 i 9 X
. Hence:

n i=1 s3 i ≤ n i=1 s ′ 3 i + 7n 2 a i 4 i 9 X ≤ n i=1 s ′ 3 i + n 7n 2 a i 4 X ≤ n i=1 s ′ 3 i + n 7n 2 S 4 X ≤ n i=1 s ′ 3 i + 0.5 because X ≥ 2n 7n 2 S 4 5. (s i ≤ iX + M ai 3 ) We have si -iX -(M a i ) 1/3 = M ai 3(iX) 2 -(M a i ) 1/3 - iX 9 M ai (iX) 3 2 + 5iX 81 M ai (iX) 3 3 . Then, first let us show that -iX 9 M ai (iX) 3 2 + 5iX 81 M ai (iX) 3 3 < 0: iX 9 M a i (iX) 3 2 > 5iX 81
M a i (iX) 3 3 9 5 (iX) 3 > M a i 9 5 > 7n 2 a i i 3 X
This last equation is always true since X > 7n 2 a i . Then let us show that

M ai 3(iX) 2 -(M a i ) 1/3 < 0: (M a i ) 1/3 > M a i 3(iX) 2 3i 2 X 2 > (7n 2 X 2 a i ) 2/3 X 1/3 > 7 2/3 n 4/3 a i 3i 2 X > 49n 4 a 3 i 27i 6
which is true since

X = 2n 7n 2 S 4 .
This concludes the proof of Lemma 1.

With these properties, we are now ready to show the NP-hardness of the problem. Note that

s 1 ≤ s1 ≤ s 2 ≤ s2 ≤ • • • ≤ s n ≤ sn ≤ s n+1 .
Suppose first that instance I 1 has a solution I. We assign the servers as follows: the root node is assigned a server at speed s n+1 ; for all i ∈ I, we assign to node i a server at speed s i , and for all i / ∈ I, we assign to node i a server at speed si . Because si ≥ s i + a i (Lemma 1), the server on node i can process all its requests, for i / ∈ I. On the contrary, for i ∈ I, the server can only process s i requests, and therefore a i requests are going up in the tree. Hence, a total of i∈I a i = S requests need to be processed by the root node, in addition to the (n + 1)X -S requests that arrive directly to this node (and the speed is s n+1 so the root server can process all its requests).

Finally we need to compute the power consumption, that is:

E = (n + 1) 3 X 3 + i / ∈I s3 i + i∈I s 3 i = (n + 1) 3 X 3 + i / ∈I s3 i + i∈I (s ′ 3 i -M a i ) ≤ (n + 1) 3 X 3 + i / ∈I s3 i + i∈I s3 i -M i∈I a i = (n + 1) 3 X 3 + n i=1 s3 i -M S ≤ (n + 1) 3 X 3 + n i=1 s ′ 3 i + 0.5 -M S = B
The power bound is respected, and therefore we have a solution to I 2 .

Suppose now that I 2 has a solution. We define the set I of nodes as follows:

i ∈ I ⇐⇒ there is a server on node i operating at speed s < si

We show that I is a solution to I 1 . First let us show that for i ∈ I, the speed of the server on node i is exactly s i . We prove this by contradiction: if this server has a lower speed s, then the number of requests from node i that goes up to the root node is at least

iX + a i -s ≥ iX + a i -((i -1)X + (M a i-1 ) 1/3 ) ≥ X + a i -(M a i-1 ) 1/3 ,
because s ≤ si-1 , and si-1 ≤ (i -1)X + (M a i-1 ) 1/3 (Lemma 1). This would lead to execute at the root more requests than the maximum (n + 1)X. Indeed,

(n + 1)X -S + X + a i -(M a i-1 ) 1/3 > (n + 1)X ⇔ X > (M a i-1 ) 1/3 + S -a i ⇔ X > (a i-1 7n 2 X 2 ) 1/3 + S -a i
We know that S < X 2/3 , and that X 1/3 > (1 + (7n 2 ) 1/3 ) (we use a i < S), hence the contradiction. Therefore we conclude that for all i ∈ I, the server on node i works at speed s i . Then for all i / ∈ I, there is a server on node i (otherwise the root node could not process the iX + a i upcoming requests with the largest speed (n + 1)X), and its speed is at least si by definition of I. We have seen that si ≥ iX + a i , so every request can be processed directly on node i.

Consequently, the power consumption is at least E ≥ (n+1

) 3 X 3 + i / ∈I s3 i + i∈I s 3 i ≥ (n + 1) 3 X 3 + n i=1 s ′ i -M i∈I a i Then we have, M i∈I a i ≥ RR n°8474
M S -0.5 because E ≤ B (we have a solution of the problem). Because M and S are integers, it implies that i∈I a i ≥ S. Because of the constraint on the maximum speed at the root node, the quantity of requests coming from other nodes and processed at the root cannot be greater than S, and we have i∈I a i ≤ S. Indeed, for all i ∈ I, no more than iX requests can be executed on node i, and therefore there are at least a i requests from node i executed at the root.

Finally, we conclude that i∈I a i = S, and therefore that I 1 has a solution. This concludes the proof for Discrete. The same instance can be used to prove the NP-completeness of Discrete-Placed (which belongs to NP since Discrete does), because each internal node is equipped with a server in the solution.

Mixed integer linear program

Theorem 2. The following MILP characterizes the Discrete problem, where the unknown variables are the x j,k 's (Boolean variables) and the y i,j 's (rational variables), for j ∈ N , 1 ≤ k ≤ K and i ∈ C:

Minimize j∈N 1≤k≤K x j,k (P static + s 3 k ) subject to (i) j∈N y i,j = r i , i ∈ C (ii) 1≤k≤K x j,k ≤ 1, j ∈ N (iii) i∈C y i,j ≤ 1≤k≤K x j,k s k , j ∈ N (6)
Proof. The constants are the r i 's for i ∈ C, and the s k 's for 1 ≤ k ≤ K, and we consider the following variables:

• x j,k is a boolean variable equal to 1 if j is a server operated at speed s k , for j ∈ N and 1 ≤ k ≤ K; x j,k = 0 otherwise. • y i,j is a rational variable equal to r i,j , the number of requests of client i ∈ C processed by server j ∈ N ; if j is not an ancestor of i in the tree, we directly set y i,j = 0.

Then the constraints are:

• For all i ∈ C, all requests of client i must be processed: ∀i ∈ C, j∈N y i,j = r i ; • Each server is assigned at most one speed: ∀j ∈ N , 1≤k≤K x j,k ≤ 1; note that a node j is equipped with a server if and only if 1≤k≤K x j,k = 1; • The processing capacity of any server cannot be exceeded: ∀j ∈ N , i∈C y i,j ≤ 1≤k≤K x j,k s k . Finally, we minimize the total power consumption. Overall, there are |C| + 2|N | constraints and |N | • (|K| + |C|) variables in this MILP.

RR n°8474 5 Heuristics

In this section, we propose some polynomial-time heuristics for the Discrete problem. We start by outlining the general principles that have guided their design before exposing the details for each heuristic.

General principles

As already mentioned in Section 1, the heuristics work in two steps: (i) server placement and (ii) request assignment. The placement step of the heuristics relies on the following result, whose proof can be found in Appendix A: Proposition 1. Given a fixed set of servers deployed on a tree of size s = |C| + |N | and assuming continuous speeds, the optimal assignment Alg-Cont-Placed of requests to servers that uses all these servers and minimizes power consumption can be determined in time O(s 2 ).

The placement step works incrementally: to compute a solution with k servers, the heuristic starts from a solution with k -1 servers, and then greedily tests the addition of one additional server. It uses Proposition 1 to compute the optimal assignment of requests with this additional server, computes the corresponding power, and returns the best solution over all possible choices for the additional server.

The placement step assumes continuous speeds, hence the loads assigned by Alg-Cont-Placed to each server do not take the set of actual speeds into account. The second step of the heuristics consists in determining a discrete speed for each server, which usually leads to re-assigning some requests, as explained in Section 1. While the first step of the heuristics is common to all heuristics, we outline below three different methods to perform this request assignment step.

List of heuristics

We provide here three different heuristics to determine the actual speed of each server. In the first heuristic, Greedy, we assign the smallest speed equal to or greater than the load given by Alg-Cont-Placed to each server. While simple, Greedy provides a 1 + maxi(si+1-si) smin 3 -approximation for the problem with the placement given by Alg-Cont-Placed, where s min is the smallest speed available. Finally, we point out that if there is no speed greater than the value determined by Alg-Cont-Placed for some server, then there does not exist a solution for this (given) placement (see Appendix B for further details).

The next two heuristics, Speed and Excess, improve the Greedy heuristic by trying to modify the load of each server, via request re-assignment. The goal is to decrease the speed of some servers. More precisely, in the procedure, which is called Equilibrate and detailed in Algorithm 1, if a server is not loaded up to its full capacity (meaning its load is equal to its capacity), then the heuristics take some load out of its children until this server reaches its capacity (see the loop line 15). The capacity of a server is defined as the maximum between its actual speed and the maximum speed of its children (see line [START_REF] Larabel | Intel EIST SpeedStep[END_REF], hence transferring even more load to this server if one of its children has a higher speed (and thus we should be able to reduce the speed of at least one child). This may happen if we have decreased the speed of the current node in a previous step of the algorithm, but not the speed of its children.

The main difference between the two heuristics Speed and Excess lies in the selection of the children whose load is taken out:

• In the Speed heuristic, we favor the children whose servers have the largest speeds. To break ties if two children of a given server have the same speed, we favor the one with the smallest load. The idea is that the gain in power will be more important if we can decrease the execution speed of a server with a large speed (favor large speeds); and if there is a tie, there is more chance to decrease the speed of a server if its load is small. • On the contrary, in the Excess heuristic, we favor children with small excess. The excess of a server is defined as the difference between its load and the largest speed below it. The idea is that we will be able to decrease the speed of more servers if we favor small excess. Finally, when two children have the same excess, we favor the one with the largest load.

Recall that K is the number of speeds and s = |C| + |N |. The complexity of the Greedy heuristic is O(s 2 ), the most costly part being the call to Alg-Cont-Placed. For the Equilibrate procedure, and hence for the Speed and Excess heuristics, the complexity becomes O(Ks 2 log s). First, it takes s log s operations to sort the children of each of the s nodes in a pre-treatment phase. Then, the procedure sub-Equilibrate is called s times, and it has a cost O(Ks log s): in the worst case, we visit each child, for each possible speed, to fill the parent at full capacity, and we have to include the cost of updating the list of sorted children, that can be done in O(log s).

Simulations

In this section, we report extensive simulations to assess the performance of the heuristics presented in Section 5. All the source code, together with scripts to obtain additional results, are publicly available [START_REF] Aupy | Source code for the simulations[END_REF]. The heuristics have been coded using the programming language OCaml, while the MILP computing the optimal solution is generated using the C language and solved using IBM Cplex [START_REF] Cplex | ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF].

In order to evaluate the heuristics, we have generated more than 100 random trees for each simulation. To simplify the generation, each internal node in the tree has a unique client leaf, which is assigned a random rational number of requests between 0 and 100. For processor speeds, unless stated otherwise, we use five speeds spaced as those of the Intel Xscale, following [START_REF] Chen | Expected energy consumption minimization in DVS systems with discrete frequencies[END_REF][START_REF] Niu | Energy Efficient Scheduling for Real-Time Embedded Systems with QoS Guarantee[END_REF]: we suppose that the largest speed can process 150 requests, and the ratio of the different speeds to the largest speed is then: (0.15, 0.4, 0.6, 0.8, 1). In [START_REF] Chen | Expected energy consumption minimization in DVS systems with discrete frequencies[END_REF][START_REF] Niu | Energy Efficient Scheduling for Real-Time Embedded Systems with QoS Guarantee[END_REF], the static power is equal to the power consumed in the lowest speed, which here corresponds to (0.15 * 150) 3 ≈ 11, 000.

We have conducted four different sets of simulations to assess the impact of the number of nodes, of static power, of the number of available speeds and of the total load of requests.

Impact of the number of nodes. In the first set of simulations, we study the impact of the number of nodes on power consumption: in Figure 1, we plot the ratio of the power returned by the heuristics over the power of the optimal solution, with a static power of 1,000, 5,000, 10,000, 20,000 and 100,000 respectively. Note that Figure 1f is different from the others and provides results at larger scale: there we plot the ratio of the power returned by Speed and Excess over the power consumption of Greedy, with a static power of 50,000, but for a larger number of nodes (up to 200 nodes). While one could expect that the performance of the heuristics would decrease for larger trees, it seems that Speed and Excess reach a tangent after ≈ 15 nodes, and that on average the maximum waste is between 20 and 25%. Furthermore, when the static power is higher (100,000), this maximum waste is even below 20%. This observed tangent is very likely correlated to the set of speeds and to the static power. This tangent makes sense in practice if we assume that the first step (the placement step) of the heuristics is not too far from the optimal solution because the Greedy heuristic is an approximation algorithm. Speed and Excess are just improvements of the Greedy heuristic. It would be interesting to see how much they improve the approximation factor, though probably complicated. Note that in Figure 1f, we see that Speed and Excess are still constantly better than Greedy even with a larger number of nodes, with a power consumption of around 80% of the power consumption for Greedy.

Impact of the static power. In the second set of simulations, we have studied the impact of the static power on total power consumption. In Figure 2, we plot the ratio of the power returned by the heuristics over the power of the optimal solution, with a static power varying between 0 and 200,000 for trees of 20 nodes. Note that the higher the static power, the better the results. Indeed, at some point, what matters most is the number of servers placed, and not the allocation of requests, hence Greedy gets closer to the optimal solution as well.

Impact of the number of speeds. In this third set of simulations, we have studied the impact of the number of speeds on power consumption. For this set of simulations, we do not use Intel speeds anymore, but instead speeds that are equally distributed between 0 and 150. In Figure 3, we plot the ratio of the power returned by the heuristics over the power of the optimal solution, with a static power of 50,000, for trees of 20 nodes, with the number of speeds varying from one (150) and ten [START_REF] Mills | The internet begins with coal[END_REF]30,45,60,75,90,105,120,135,150).

When there is only one speed, obviously the results are as good as they can be and only depend on the allocation heuristic. Then starting from three speeds, we observe that the more speeds, the better the results. This was expected since the more speeds we have, the closer we can get to the optimal solution computed by Alg-Cont-Placed, and the better the results. The fact that the results are better with two speeds than three can be explained by the fact that with only two speeds, it is still easier to find the optimal speed (hence a lower ratio than with three speeds), but a mistake is very expensive, hence a result that is not as good as with four speeds. A final remark: when speeds are equally distributed, the (proven) approximation ratio of the Greedy heuristic is 8. However in Figure 3 we see that the ratio never goes above 1.8.

Impact of the total load of the tree. Finally, in the last set of simulations, we have studied the impact of the total load of the tree on the power consumption. In Figure 4, we plot the ratio of the power returned by the heuristics over the power of the optimal solution, for trees of 20 nodes, and for a static power of 1,000, 5,000, 10,000, 20,000 and 100,000 respectively. Overall, the total number of requests does not impact the performance of the heuristics: the average ratio stays constant with the total load of the tree, for all values of static power.

Summary of simulation results. To conclude on the different studies, the first observation is somewhat expected: there is a huge gap between the Greedy heuristic, and the Speed and Excess heuristics: there is a degradation w.r.t. the optimal of 50 to 70% when using the Greedy heuristic with 10 to 30 nodes, while it is only approximately 20% (or less with larger static power) when using the Speed or Excess heuristic. The difference between the Speed and Excess heuristics is negligible, although it should be noted that on average, the Speed heuristic performs slightly (≈ 1%) better than the Excess heuristic. Furthermore, it seems that what matters most for the competitiveness of the heuristics is the set of speeds and the static power P static . In particular, the number of speeds is very important: the closer the speeds are to each other, the better the results. Above a certain number of nodes (≈ 15), the ratio of the results of the heuristics over the optimal solution seems to reach a threshold (independently of the load and the static power), but the value of this threshold depends on the set of speeds and on the static power. Higher static power lowers the value of the threshold: at some point, what matters most is the number of servers, even if they are all at maximum speed. Similarly, the smaller the gap between two consecutive speeds, then the closer we can get to the optimal solution computed by Alg-Cont-Placed, and the better the results. (c) P static = 10, 000 (d) P static = 20, 000

P static = 5, 000 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2

Conclusion

In this paper, we have revisited the well-known replica problem in tree networks under power constraints, in the most flexible scenario where requests of a client can be split between multiple servers. While the problem of minimizing the number of servers has polynomial complexity, we have proved that the problem of minimizing the power consumption is NP-complete, even if the servers are already placed in the tree. We assume that the server speeds can be modified using dynamic voltage and frequency scaling, depending upon the number of requests to be processed, and that a set of discrete speeds is available. Therefore, the core of the difficulty lies in assigning requests to servers in order to optimize the speeds given to each server. Building upon the optimal solution with already placed servers and continuous speeds, we have designed efficient polynomial-time heuristics to solve the general optimization problem (deciding where to place servers and how to assign requests).

In order to assess the performance of the heuristics, we have also provided a mixed integer linear program (MILP) that returns the optimal solution of the problem for small instances (up to 30 nodes in the tree). The heuristics are always quite close to the optimal solution, and the sophisticated versions that readjust the request assignment to better fit server speeds prove to be valuable improvements of the basic greedy solution.

For future work, it would be very interesting to prove a competitive ratio for the heuristics that we have designed. However, this is quite a challenging work for arbitrary trees, and one may try to design approximation algorithms only for special tree structures, e.g. binary trees.

A Proof of Proposition 1

First let us define formally the problem with continuous speeds and already placed servers that we are solving in Proposition 1: Definition 1 (Continuous-Placed). Given a distribution tree (with a number of requests per client), with servers turned on and already placed on the tree, decide how to distribute client requests among them (which can also be seen as assigning the speed, equal to the number of requests, of each server), in order to minimize the total power consumption.

Note that in the following, because placed servers are all assumed turned on, we do not need to account for P static . Definition 2. Let T be a distribution tree. Let N and N ′ be two nodes of T :

• N ′ is a server-child of N if there is a path from N ′ to N (i.e., N is an ancestor of N ′ in the tree), and there is a server on N ′ . Furthermore, we call it a direct server-child if it is a server-child and there are no other servers on the path from N ′ to N . Symmetrically, N is a server-parent of N ′ .

• Given a solution where N ′ is a child of N , and such that there is a server on N ′ that computes r ′ requests, and a server on N that computes r requests, then a transfer of t ∈ [0, r ′ ] requests from N ′ to N is a solution where N ′ computes r ′t requests and N computes r + t requests.

Given a solution to Continuous-Placed we consider the two following hypothesis:

Hypothesis 1. The number of requests processed by a server is never smaller than the number of requests processed by each of its server-children.

Hypothesis 2. If a server does not process all requests that are available in its subtree (i.e., some of these requests are processed higher in the tree), then the number of requests that it processes is equal to the number of requests processed by its direct server-parent. Lemma 2. There exists an optimal solution to Continuous-Placed that satisfies hypothesis 1.

Proof. Consider an optimal solution to Continuous-Placed that does not satisfy hypothesis 1. Then there exists a server N 1 processing w 1 requests, while one of its server-children N 2 is processing w 2 > w 1 requests. By transferring w 2w 1 requests from N 2 to N 1 (which is possible because N 1 is a parent of N 2 ), we can construct a solution such that N 1 executes w 2 requests and N 2 executes w 1 requests. This solution has the same power consumption as the previous one.

Similarly we can do this in the new solution, on all nodes that violate hypothesis 1, until the solution does not violate anymore hypothesis 1.

Lemma 3. If a solution to Continuous-Placed is optimal, then it satisfies hypothesis 2.

Proof. Let us consider a solution that does not satisfy hypothesis 2. Then there exists a server N 2 processing w 2 requests, and its direct parent-server N 1 is processing w 1 = w 2 requests. Moreover, N 2 leaves l requests to be processed higher in the tree (either by N 1 or by an ancestor of N 1 ).

1. if w 1 < w 2 , then transferring w2-w1 2 additional requests from N 2 to N 1 is still a valid solution since N 1 is a parent of N 2 , and the power consumption of this solution is better (2 w1+w2 2 3 < w 3 1 + w 3 2 ).

2. if w 2 < w 1 , then it would be better to process l ′ = min l, w1-w2 2 more requests at node 2 . This is possible because these requests are processed higher in the tree and we can always exchange them with some requests of N 1 if N 1 is not processing them. In the new solution, N 2 processes w 2 + l ′ requests, while N 1 processes w 1l ′ requests. Because l ′ > 0, and by convexity, this new solution has a better power consumption.

Hence the solution is not optimal, and all optimal solutions satisfy hypothesis 2.

Theorem 3. If a solution to Continuous-Placed satisfies hypothesis 1 and 2, then it is optimal.

To prove this theorem, let us show that 1. there is a unique solution that satisfies both hypotheses; 2. this solution is optimal. Proposition 2. Given two optimal solutions to Continuous-Placed that satisfy hypothesis 1 and 2, consider a server N that computes w 1 (resp. w 2 ) requests in the first (resp. second) solution, and that leaves t 1 (resp. t 2 ) requests to be processed higher in the tree. Proof. In order to prove this proposition, note that we know that w i + t i is equal to the sum of the requests coming directly into N , and of all requests transferred from N 's server-children. Then, because w 1 + t 1 > w 2 + t 2 in both cases, there exists a direct server-child of N such that t ′ 1 > t ′ 2 . Then necessarily t ′ 1 > 0, and with hypothesis 2, w ′ 1 = w 1 . Finally, with hypothesis 1, w ′ 2 ≤ w 2 , hence the results: if

w 2 < w 1 , then w ′ 2 ≤ w 2 < w 1 = w ′ 1 , and if w 2 ≤ w 1 , then w ′ 2 ≤ w 2 ≤ w 1 = w ′ 1 .
Proof of Theorem 3. Uniqueness of the optimal solution: To show that there is a unique optimal solution, we proceed by induction. If there is a unique server, then there is a unique solution where this server processes all requests.

Let us now consider a tree with n servers. Let us consider two optimal solutions that satisfy hypothesis 1 and 2. Finally, let us consider w 1 (resp. w 2 ) the number of requests computed by the server at the root of the tree in the first (resp. second) solution. The transfer at the root of the tree is necessary null, i.e., t 1 = t 2 = 0 at the root. Note that if there is no server at the root of the tree, then we can divide the tree into subtrees with a server at their roots, and by induction the two solutions are identical. If there is only one subtree with a server at its root, then we conduct the same reasoning on this subtree, and the transfer is necessary null because there are no servers upper in the tree. N denotes the server at the root of the tree.

Then, there are five different possibilities: 2 , because initially t 1 = t 2 (no transfer from the root node). Hence, we have a contradiction since there are only n servers.

• If w 1 > w 2 ,
• The case with w 2 > w 1 is symmetrical.

• If w 1 = w 2 , and if there exists a direct server-child s of N such that t

2 , then with hypothesis 2, w

= w 1 , and with hypothesis 1, w (s) 2 ≤ w 2 . Finally, with Proposition 2, we can construct an infinite sequence of servers s starting from s such that w

(s) 1 ≥ w (s) 2 and t (s) 1 > t (s) 2 .
Hence we have a contradiction since there are only n servers.

• The case with w 1 = w 2 , and there exists a direct server-child s of N such that t (s)

1 < t (s)
2 , is symmetrical.

• Finally, if w 1 = w 2 , and for all direct server-child s of N , t

= t (s) (s) 1
2 , then we look at the sub-problem for all sub-trees of N , and by induction hypothesis, the two solutions are equal.

Finally, we have shown that two solutions to Continuous-Placed that satisfy both hypothesis are identical.

Existence of a solution: With Lemma 2, we know that there exists an optimal solution to Continuous-Placed that satisfies hypothesis 1. With Lemma 3, we know that this solution satisfies hypothesis 2. Therefore, it is exactly the solution that satisfies both hypothesis.

Finally, we have shown that if a solution satisfies both hypothesis, it is optimal.

We now introduce the algorithm Alg-Cont-Placed that computes a distribution of the requests over a set of placed servers. First, note that if there are requests coming in a node such that there are no servers placed on that node or on any of the ancestors of that node, then there is no solution to the problem Continuous-Placed: these requests cannot be satisfied. Definition 3 (server-subtrees). For a given node N of a tree T , a server-subtree of N is a subtree of T below N such that 1. there is a server at the root N ′ of the subtree; 2. there are no servers on any nodes of the path of T from N to N ′ .

RR n°8474

Hence we can consider trees such that there is a server on the root node (otherwise, either there is no solution to Continuous-Placed, or we can divide a tree into the disjoint server-subtrees of the root of the original tree). Proof. It is easy to verify that both hypothesis are verified by the result of the algorithm. Given a node N ,

• They are verified at the beginning of the execution of the algorithm for all server subtrees of N .

• At all time during the execution of the "while" loop, they are verified for all the servers below N .

• The "while" loop ensures that both hypothesis are verified for N at the end of the execution.

Note that the proofs also work if the only set of speeds allowed is [s min , s max ]. We detail in Algorithm 3 what Alg-Cont-Placed would become.

B Theoretical results on heuristics

In this section, we detail some theoretical results, on which the heuristics are based. Recall that the set of discrete speeds is {s 1 , . . . , s K }.

Theorem 5. Given a distribution tree (with a number of requests per client), with servers turned on and already placed on the tree, if the maximum speed given by the solution of Alg-Cont-Placed is greater than the maximum discrete speed, then there is no solution.

Proof. Assume a distribution tree with servers turned on and already placed on the tree. Let us call S the solution given by Alg-Cont-Placed, such that one server works at a speed s greater than the maximum discrete speed (s K ). Since the result given by Alg-Cont-Placed follows hypothesis 1 (Theorem 4), then in particular the server placed at the root of the tree works at speed s.

Let us assume that there exists a solution S ′ to Discrete-Placed. Then the root of the tree is processed at a speed lower than or equal to s K . Let us consider the ss K requests that are processed on the root in S, but are not processed on the root in S ′ . Then, in S ′ they are processed on a server below the root:

• Either this server works at speed s in S, but then we can consider the subtree rooted in this server and reach a contradiction;

• Either this server works at a speed lower than s in S, and because S follows hypothesis 2 (Theorem 4), it does not transfer any requests higher the tree. Hence necessarily, it cannot process some of the ss K requests that are not processed on the root in S ′ .

Finally, necessarily, the ss K requests that are not processed on the root are processed on a node that works at speed s > s K in S, and we have a contradiction.

In conclusion, if the maximum speed given by the solution of Alg-Cont-Placed is greater than the maximum discrete speed, there is no solution to Discrete-Placed. Theorem 6. Given a distribution tree (with a number of requests per client), with servers turned on and already placed on the tree, Greedy is a (1 + max 1<i<K (si+1-si) s1

) 3 -approximation to the Discrete-Placed problem.

Proof. First, note that the optimal solution to Continuous-Placed, where the set of speeds is bounded in the interval [s 1 , s K ], is a lower-bound on the optimal solution to Discrete-Placed. Indeed, any solution to Discrete-Placed is a solution to Continuous-Placed.

Then, for each server N , let us call s Finally, we can bound the total energy consumption E {g} of the Greedy solution:

E {g} = N s {g}3 N ≤ N s {c}3 N 1 + max 1<i<K (s i+1 -s i ) s 1 3 ≤ E {opt} 1 + max 1<i<K (s i+1 -s i ) s 1 3
, where E {opt} is the optimal energy consumption. Indeed, N s {c}3 N corresponds to the lower bound of the optimal energy consumption in the continuous case. This concludes the proof.

RR n°8474

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES

3 6 7 9 Let

 369 Apply the Greedy heuristic on T ; 4 return sub-Equilibrate (T, root) 5 procedure sub-Equilibrate(T , N ) /* here N is a node of T */ 8 begin L the list of children of N sorted as favored by the heuristic; 10 Let (i N , w N ) be the indices of the speed and load of N ; 11Let i N ′ be the index of the maximum speed of the children of N ;12 if s i N ′ > s i N then 13 i N ← i N ′ ; 14 remaining ← s i Nw N ;15 while remaining = 0 do 16 Let N ′ be the first element of L; 17 Let (i N ′ , w N ′ ) be the indices of the speed and load of ′ ; 18 temp ← min remaining, w N ′s i N ′ ; 19 w N ′ ← w N ′temp; 20 remaining ← remainingtemp; 21 w N ← w N + temp; 22 Update the index of the speed of N ′ ; 23 Update the order of L to account for the new load and speed of N ′ ; 24 for N ′ ∈ children of N do 25 T ← sub-Equilibrate (T, N ′ ); 26 return T

Figure 1 -

 1 Figure 1 -Study of the impact of the number of nodes, for random requests between 0 and 100, average on 100 tests.

Figure 2 -

 2 Figure 2 -Study of the impact of the static power, for trees of 20 nodes, for random requests between 0 and 100, average on 100 tests.

Figure 3 -

 3 Figure3-Study of the impact of the number of speeds, for trees of 20 nodes, static power of 50,000, for random requests between 0 and 100, average on 100 tests.

Figure 4 -

 4 Figure 4 -Study of the impact of the total load, for trees of 20 nodes, for random requests between 0 and 100, average on 100 tests.

Algorithm 2 : 4 5 13 Let S 2 16 if S ′ > S 2 then 17 N 1 18 R/ 19 else 20 N 1 Theorem 4 .

 241321617118192014 Procedure Alg-Cont-Placed 1 procedure Alg-Cont-Placed(T ) 2 begin 3 return sub-Alg-Cont-Placed (T, root) procedure sub-Alg-Cont-Placed(T , N ) /* here N is a node of T */ 6 begin 7 for s ∈ Child(N ) do 8 T s = sub-Alg-Cont-Placed (T, s); 9 Let R be the number of requests that are sent by clients on internal nodes that are not in server-subtrees of N ; 10 Let S N = R be the speed of the server on node N ; 11 while there exists a server-child of N with a speed greater than S N do 12Let S max be the maximum speed of a server-child of N ; be the second maximum speed of a server-child of N (S 2 = S max ), S 2 = 0 if there is no second maximum speed; 14 Let N 1 , . . . , N k be the k server-children of N that work at speed S max ; 15 Let S ′ = kSmax+R k+1 ; , . . . , N k now work at speed S ′ , and transfer S max -S ′ additional requests to N ; ← S ′ /* We will exit the while loop at the next step *, . . . , N k now work at speed S 2 , and transfer S max -S 2 additional requests to N ; 21 R ← R + k(S max -S 2 ) /* Note that R < S 2 */ 22 return T The solution returned by Algorithm 2 satisfies hypothesis 1 and 2, therefore it is optimal.

Algorithm 3 : 3 Let 5 if S > s max then 6 return 8 return T 9 10 18 Let S 2 / 24 else 25 N 1

 335689182251 Procedure Alg-Cont-Placed where allowed speeds range from s min to s max . 1 procedure Alg-Cont-Placed-Bounded(T ) 2 begin T =sub-Alg-Cont-Placed-Bounded (T, root); 4 Let S be the speed of the root of T ; There are no solutions 7 else procedure sub-Alg-Cont-Placed-Bounded(T , N ) /* here N is a node of T */ 11 begin 12 for s ∈ Child(N ) do 13 T s = sub-Alg-Cont-Placed-Bounded (T, s); 14 Let R be the number of requests that are sent by clients on internal nodes that are not in server-subtrees of N ; 15 Let S N = R be the speed of the server on node N ; 16 while there exists a server-child of N with a speed greater than S N do 17Let S max be the maximum speed of a server-child of N ; be the second maximum speed of a server-child of N (S 2 = S max ), S 2 = s min if there is no second maximum speed; 19 Let N 1 , . . . , N k be the k server-children of N that work at speed S max ; 20 Let S ′ = kSmax+R k+1 ; 21 if S ′ > S 2 then 22 N 1 , . . . , N k now work at speed S ′ , and transfer S max -S ′ additional requests to N ; 23 R ← S ′ /* We will exit the while loop at the next step *, . . . , N k now work at speed S 2 , and transfer S max -S 2 additional requests to N ; 26 R ← R + k(S max -S 2 ) /* Note that R < S 2 */ 27 return T RR n°8474

{c}N

  the speed given by the Alg-Cont-Placed-Bounded with bounded speeds (Algorithm 3), and s {g} N the speed given by the Greedy algorithm. There exists i such that s {g} N = s i+1 (with 0 ≤ i < K and s 0 = 0), and by definition of s {g} N , s {g} N ≥ s {c} N > s i = s {g} N -(s i+1s i ) .

  1<i<K (s i+1s i ) s 1.

  Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

•

  If w 1 > w 2 and t 1 ≥ t 2 , then there exists a direct server-child N ′ of N that

	computes w ′ 1 (resp. w ′ 2 ) requests in the first (resp. second) solution, and that transfers t ′ 1 (resp. t ′ 2 ) requests to N , such that w ′ 1 > w ′ 2 and t ′ 1 > t ′ 2 .
	• If w 1 ≥ w 2 and t 1 > t 2 , then there exists a direct server-child N ′ of N that computes w ′ 1 (resp. w ′ 2 ) requests in the first (resp. second) solution, and that transfers t ′ 1 (resp. t ′ 2 ) requests to N , such that w ′ 1 ≥ w ′ 2 and t ′ 1 > t ′ 2 .

  with Proposition 2, we can construct an infinite sequence of servers s starting from N such that w

	(s) 1 > w	(s) 2	and t	(s) 1 ≥ t	(s)

RR n°8474

Acknowledgements

This work was supported in part by the French Research Agency (ANR) through the Rescue project. Anne Benoit and Yves Robert are with Institut Universitaire de France.