published or not. The documents may come

The quantum dynamics of the diffusion of dissociatively adsorbed diatomic molecules

Thiago Diamond Reis Firmino


Frédéric Giroire
email: frederic.giroire@inria.fr

Dorian Mazauric
email: dorian.mazauric@inria.fr

Joanna Moulierac
email: joanna.moulierac@inria.fr

Energy Efficient Routing by Switching-Off Network Interfaces

Keywords: power consumption, energy-efficient routing, graphs, integer linear programming, algorithms

Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces. When a connection is not used, both network interfaces can be turned off. Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. We first define formally the problem and we model it as an integer linear program. Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm. We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms. Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies. We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies: we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation. Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.

Introduction

The minimization of ICT energy consumption has become a priority with the recent increase of energy cost and the new sensibility of the public, governments and corporations towards energy consumption. ICT alone is responsible of 2% to 10% (depending on the estimations) of the world consumption (Chiaraviglio, Leonardi, & Mellia, How much can Internet be greened?, 2009).

In this paper, we are interested in the networking part of this energy consumption, and in particular in the routing. It is estimated that switches, hubs, routers account for 6 TWh per year in the US [START_REF] Nordman | Reducing the energy consumption of networked devices[END_REF].

Some recent studies [START_REF] Chabarek | Power awareness in network design and routing[END_REF], (Mahadevan, Sharma, Banerjee, & Ranganathan, A Power Benchmarking Framework for Network Devices., 2009) exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the dominating factor is the number of switched-on network elements: interfaces, platforms, routers,… In order to minimize energy, we should try to use as few network elements as possible.

Nevertheless, in most of networks, PoPs or even routers cannot be turned off. As a matter of fact, first, they are the source or destination of demands; second, they can be part of backup routes to protect the network again failures. For this reason, we consider in this paper a simplified architecture where a connection between two routers is represented by a link joining two network interfaces.

We can spare energy by turning off the two network interfaces which are the extremities of the link. The network is represented by an undirected graph and, in that case, the goal in this simplified architecture is to find a subgraph minimum in number of links to route the demands. The contributions of this paper are the following:

• We prove that there is no polynomial-time constant-factor approximation algorithm for this problem, even for two demands or if all links have the same capacity, unless P=NP.

• We present heuristics to find close to optimal solutions for general networks. These heuristics are validated by comparison with theoretical bounds for specific instances of the problem. Furthermore, we exhibit negative results about greedy and probabilistic heuristic algorithms.

• We give explicit close formulas or bounds for specific topologies, such as trees, complete graphs, and square grids. They provide limit behaviors and give indications of how the problem behaves for general networks.

• We study the energy gain on a set of topologies of existing backbone networks. We exhibit that at least one third of the network interfaces can be spared for usual range of demands.

• Finally, we discuss the impact of energy-efficient routing on route length and fault tolerance.

Related Work

Measure of energy consumptions. Several measurement campaigns of network energy consumption have been carried out in the last few years. See for example (Mahadevan, Sharma, Banerjee, & Ranganathan, Energy Aware Network Operations, 2008) (Mahadevan, Sharma, Banerjee, & Ranganathan, A Power Benchmarking Framework for Network Devices., 2009) [START_REF] Chabarek | Power awareness in network design and routing[END_REF]. Their authors claim that the consumption of network devices is largely independent of their load. In particular, in [START_REF] Chabarek | Power awareness in network design and routing[END_REF], the authors were interested by routers' energy consumption. They observe that for the popular Cisco 12000 series, the consumption at a load of 75% is only 2% more than at an idle state (770W vs. 755W). In (Mahadevan, Sharma, Banerjee, & Ranganathan, A Power Benchmarking Framework for Network Devices., 2009), the authors show through experimentation that the power consumed depends on the number of active ports. Explicitly disabling unused ports on a line card reduces the device power consumption. The values obtained during experimentation show that the consumption of a linecard 4-port Gigabit ethernet (100W) is approximately one fourth the consumption of the global base system (430W).

Energy minimization. In [START_REF] Chabarek | Power awareness in network design and routing[END_REF], the authors model this problem as an integer linear program. The objective function is a weighted sum of the number of platforms and interfaces. They show how much energy can be saved on different networks with this model. However, they do not give intuitions, explanations, nor formulas for their results. In [START_REF] Idzikowski | Saving energy in IP-over-WDM networks by switching off line cards in lowdemand scenarios[END_REF], the authors propose a rerouting at different layers in IP-over-WDM networks for energy savings while [START_REF] Puype | Power Reduction Techniques in Multilayer Traffic Engineering[END_REF] study the impact of the technology for energy efficient routing. In (Nedevschi, Popa, Iannaccone, Ratnasamy, & Wetherall, 2008), (Gupta & Singh, 2003), (Chiaraviglio, Leonardi, & Mellia, How much can Internet be greened?, 2009), researchers proposed techniques such as putting idle subcomponents (line cards, ports, etc.) to sleep, as well as adapting the rate for forwarding packets depending on the traffic in local area networks. In (Coudert, Nepomuceno, & Rivano, 2010), the authors propose a modulation of the radio configurations in fixed broadband wireless networks to reduce the power consumption. We prove in this paper that there is no polynomial-time constant-factor approximation algorithm for this problem, even for specific instances. We give also theoretical results about the inefficiency of greedy and probabilistic algorithms. To the best of our knowledge, we are presenting in this paper the first study of energyefficient routing solutions on specific topologies. We link the proposed theoretical bounds with general networks. Finally, we study the impact of such solutions on route length and fault tolerance.

The remainder of the paper is organized as follows.

• In Section 2, we first present formally the problem and we model it as an integer linear program.

• In Section 3, we recall the complexity of related problems and we prove that the problem cannot be approximated within a constant factor.

• In Section 4, we design heuristic algorithms and we prove also negative results about greedy and probabilistic heuristic algorithms.

• Then, specific topologies, such as trees or complete graphs, are discussed in Section 5,

• and grids in Section 6.

• We show the good performance of our proposed heuristic in terms of power consumption in Section 7, and we show the impact of such energy-efficient solutions on route lengths and network fault tolerance. We also propose the construction of fault-tolerant spanners.

• Finally, we discussed the impact of such algorithms for network operators in Section 8.

Problem Modeling

One way to reduce the network power consumption consists in minimizing the number of turned-on network equipments. We model a network topology as an undirected weighted graph G=( For our purpose, we study a simplified network architecture in which a link (A,B) connects two routers A and B through 2 network interfaces, one for A and one for B.

The degree of a node in the graph corresponds to the number of network interfaces on the corresponding router. If a network interface is turned-off, then the other interface at the extremity of the link is not useful anymore and can also be turned-off. Therefore, the objective of our problem is to minimize the number of active links in the network. Formally:

Definition 2.2 Given an undirected weighted graph G=(V,E) and a set of demands D, the MINIMUM EDGES ROUTING PROBLEM consists in finding a minimum cardinality subset E* E such that there is a valid routing of the demands D in G.

In Section 2.1, we present some simple instances of the MINIMUM EDGES ROUTING PROBLEM and the corresponding solutions. In Section 2.2, we describe a linear program for our problem.

Examples

Consider the graph G=(V,E) depicted in Figure 1 . Because of the second demand, there is no feasible routing. Indeed node s 2 has two adjacent edges of capacities 8 and 9, and so it is impossible to route a demand of 10 units through one of these edges. In our problem, a demand can not be divided into sub-demands. The solution of the ROUTING PROBLEM for this instance is 'no', and so there is no solution for the MINIMUM EDGES ROUTING PROBLEM because the whole graph is not sufficient.

In Figure 2 in G*=(V,E*) is composed of 5 edges, whereas the shortest path in G is composed of 4 edges, for i{1,2}. Indeed these two shortest paths are edgedisjoint whereas, in the optimal routing, the two paths share 3 edges. This simple example shows that the shortest paths routing does not give the optimal solution in general.

In Figure 2

Integer Linear Program

The MINIMUM EDGES ROUTING PROBLEM can be modeled as a multicommodity integral flow problem in which the objective function is the minimization of the number of edges. We note f st uv the flow on edge uv corresponding to the demand D st flowing from u to v. We note

    V V
Flow constraints: , , ) , ( V u V V t s                  0 ) ( ) ( st st u N v st uv u N v st vu D D f f . otherwise t u if s u if   Capacity constraints : , ) , ( E v u e      . e e D d d vu d uv c x f f    
The flow constraints are usual flow conservation. The capacity constraints state that for each edge eE, the total amount of demands through e does not exceed the capacity c e .

Impossibility of Approximation

The MINIMUM EDGES ROUTING PROBLEM in this paper is a special case of different well known network optimization problems: minimum cost routing (Yaged Jr.), minimum concave flow problem [START_REF] Guisewite | Minimum concave-cost network flow problems: Applications, complexity, and algorithms[END_REF], minimum flow problem with step cost functions (Gabrel, Knippel, & Minoux). In operation research, this problem can be seen as a special case of the FIXED CHARGE TRANSPORTATION PROBLEM [START_REF] Spielberg | On the fixed charge transportation problem[END_REF], (Dantzig), where the cost of the flow unit on an edge is zero. Note that this problem is NP-Hard [START_REF] Guisewite | Minimum concave-cost network flow problems: Applications, complexity, and algorithms[END_REF]: the number of possible subgraphs to test is strongly exponential for most graphs. Moreover, even for a given subgraph (when the set of edges to be used is fixed), the feasibility of a multicommodity integral flow problem has to be assessed. This simpler problem corresponds to the ROUTING PROBLEMit is known to be NP-complete even for two commodities [START_REF] Even | On the complexity of time table and multicommodity flow problems[END_REF]. Last, note that it is also the worst case of step-functions as most of the approximations by linearization are very far from a feasible solution.

We now prove that the MINIMUM EDGES ROUTING PROBLEM is not in APX (and so it is an NP-hard problem) even for two special kinds of instances (Theorem and Theorem ). It means that there is no polynomial-time constant-factor approximation algorithms for the MINIMUM EDGES ROUTING PROBLEM, unless P=NP. Theorem 3.1 The MINIMUM EDGES ROUTING PROBLEM is not in APX even for two commodities.

Proof.

Let G=(V,E) be an undirected weighted graph. Consider the case of two commodities D s 1 t 1 >0 and D s 2 t 2 >0. We build a graph G'=(V',E') as follows: we start with a copy of . From u to v, there are 3 disjoint paths composed of 2 edges each and |D| disjoint paths of x > k|E| edges each. Because of the k-approximation, if there is a solution using no long paths, then our polynomial-time algorithm returns necessarily such a solution. Otherwise it returns a solution with edges belonging to these paths.

Note that the problem of finding if there exists a partition of requests into three sets of same weight c is an NP-complete problem. Our polynomial-time approximation algorithm would thus solve it, a contradiction, unless P=NP. □ These two negative results motivate the design of heuristic algorithms for the MINIMUM EDGES ROUTING PROBLEM in Section 4 and the study of theoretical bounds for particular instances in Section 5 that give information for general networks.

Heuristics

As we have seen in the previous section, the MINIMUM EDGES ROUTING PROBLEM is a problem difficult to solve exactly and is even difficult to approximate to an insured factor in general. Hence, the necessity of proposing good heuristic algorithms for classical real network topologies. We propose in this section two heuristics to find energy-efficient routing, namely LESS LOADED EDGE HEURISTIC, RANDOM HEURISTIC. These heuristics are tested in Section 7. We also discuss the efficiency of greedy and random heuristics on the MINIMUM EDGES ROUTING PROBLEM.

Heuristics

Algorithm 1 presents a simple heuristic named LESS LOADED EDGE HEURISTIC for our problem. We start from the whole network, compute a feasible routing as described in Algorithm 2 and try to remove in priority edges that are less loaded. We believe that it is better to remove these edges that are not involved in many shortest paths than overloaded edges. For the routing, the demands are considered one by one in random order. We compute a shortest path for the demand with the metric c e /r e on edges, where r e is the residual capacity on edge e when the previous demands have been routed. Then, the residual capacity is updated for each edge and the next demand is considered. This routing allows a better load balancing of the demands in the network. Note that finding a feasible routing can also be done with an integer linear program for the ROUTING PROBLEM for small topologies. Each time an edge is removed in the network, a feasible routing is computed. If no routing exists, then the removed edge is put back and we try to remove another edge that has not been yet considered. The process of removing less loaded edges is done until no more edges can be removed.

The second heuristic, RANDOM HEURISTIC, is used as a measure of comparison during the simulations. The only difference with the first one is that it selects uniformly at random the links to be removed and not (necessarily) the less loaded edges. The routing is performed in the same way as for LESS LOADED EDGE HEURISTIC. These heuristics are evaluated through simulations in Section 6.3 and 7 and compared to the theoretical bounds given in Section 5 and to the integer linear program described in Section 2.2.

Note on the execution time of Random Heuristic

Consider an undirected weighted graph G=(V,E), a set of demands D, and a unique optimal solution E * for the MINIMUM EDGES ROUTING PROBLEM.

When you have drawn a percentage μ of edges of G and when the routing is still feasible after these edges removals, the probability of having removed an edge of the optimal solution is given by .

* 1                   E E E E E  
For example, if |E|=100 and |E * |=20, then the probability to remove 50 edges without removing one edge of the solution is smaller than 8.8 10 -8

. The number of random trials to find the optimal solution is then prohibitive for large networks.

Order of the execution time. A bound can be easily derived by considering the drawing problem but with replacement. The probability to draw an edge of the solution is larger than

. 1 * 1           E E E  When |E| is large, we have ≈1-e -μ|E * | .
Hence, finding the optimal solution by removing edges uniformly at random may be exponentially long.

When the number of vertices is large, the time of execution of the random heuristic may be very large. Indeed, exp(-.5×50)=1.4 10 -11 . Tens of billions of trials would be necessary to find the optimal solution for a graph with only one optimal solution.

Shortest Paths Routings and Greedy Algorithms

In this section we show that greedy algorithms based on shortest paths or minimum added edges at each step, may return a solution whose cardinality is arbitrarily large compared to the optimal number |E * |. Furthermore, even if we have the best order that minimizes the total number of edges used when routing, the quality of the solution may be very bad compared to the optimal one. : each demand is routed through the 4 edges of infinite capacity. Note that for this optimal routing, there is no demand routed through a shortest path. Taking |D|>4C/(5-2C), we get the inequality.

Furthermore if the number |D| of demands is fixed, we can modify G as follows: we replace the path of 4 edges from u to v by a path of x+1 edges, each of infinite capacity; we replace the |D| disjoint paths of 3 edges each from u to v by |D| disjoint paths of x edges, each of capacity 1. We get |E Consider the instance of the MINIMUM EDGES ROUTING PROBLEM described in proof of Lemma composed of |D| demands. Consider any order of these demands among the |D|!. From Lemma , we deduce that if we route the demands greedily according to this order, through a shortest path, then we get a routing that uses 5|D| whereas |E * |=2|D|+4. In other words, even if we have the best order to route greedily the demands, the number of edges may be arbitrarily large compared to the minimum number. Furthermore, if we route the demands greedily choosing, at each step, a path that minimizes the number of added edges, then we get also 5|D| edges for any order.

In conclusion simple greedy algorithms may return a solution whose cardinality is arbitrarily large compared to the optimal number |E * |. Even if we have the best order, the quality of the solution may be very bad compared to the optimal one. Because of previous negative results, we study in Section 5 the MINIMUM EDGES ROUTING PROBLEM for specific instances. We present here the general framework of the studies of the rest of this paper. We then study two extreme cases for general networks, namely trees and complete graphs. They give us the limit behavior of the real networks for different network loads. We also derive an upper bound on the number of links that can be spared in function of the demands.

Topology Study: extreme cases

Our Framework

In general networks, the demands vary during the life of the networks, e.g. with the increase of the number of users, with the development of new technologies, or, more simply, according to the time of the day. The goal of the study in this section is to see how much energy can be spared depending on the resources available for the routing.

Given an undirected weighted graph G=(V,E) representing a network, each edge e∈ E has the same amount of capacity c e =c. We perform an all-to-all routing with demands of volume,(s,t) VV, D st =κ.

Definition 5.1.1 The capacity/demand ratio λ expresses the relation between the demand and the edge capacity: λ=c/κ.

Although an all-to-all routing is not a realistic scenario, it allows to study the effects of such routing in extreme conditions and also to keep the network connected. With such scenario, we can certify that the topology given by our algorithm will be suitable for more realistic traffic matrices. Then, for each topology, we look at the number of links that can be spared for different capacity/demand ratios λ.

A toy example. As an illustration, Figure 7 shows an optimal solution H given by the integer linear program described in Section 2.2 for the complete graph G composed of 5 nodes when the capacity/demand ratio λ varies from 2 to 8. When λ equals 2, all the edges of G are needed to perform an all-to-all routing with κ=1. The larger the ratio is, the fewer network interfaces are needed until we reach the star graph where no more network interfaces can be removed. The two extreme cases are the complete graph (λ=2) and the tree (λ=8). The gain in terms of network interfaces can reach 60%, indeed, only 4 edges (or 8 network interfaces) are needed instead of 10 (or 20).

We also measure the impact of this energy-efficient routing on delay and failure protection: for each different λ, we give the average route length, lH (D), given by a feasible routing of the all-to-all demands on the solution subgraph H, and the average number of edge-disjoint paths linking two nodes, DP H (D). We see that, for this simple example, the route length increases by 60% and that the number of disjoint paths drops from 4 to 1 between the two extreme cases.

Note that an orthogonal way to conduct the study is to fix the number of network interfaces/edges to be turned-on and to compute the load of the network, that is the minimum capacity needed to be able to satisfy the all-to-all routing.

General Bounds

Path length lower bounds. The global capacity of the system has to be larger than the global demand. The global flow is minimum when all demands are following the shortest paths between their source and destination. We note d(s,t) the length of a shortest path between a source s and a destination t. Hence, we have . ) , (

; 2       t s V st st E e e D t s d c
In particular, when all the edges have the same capacity c and all the couples of nodes have the same demand κ, it becomes . ) , ( E is the number of edges of the cut between S and . S The load of a graph can thus be computed by looking at the minimum cut of the network that supports the maximum flow.

; 2     t s V st t s d E c  or equivalently . ) , ( 1 ; 2 

Minimum bisection cut.

A particular example of cut is the minimum bisection cut denoted .

S S E

The minimum bisection cut is the minimum cut that divides the network into two (almost) equal-sized regions S and :

S        2 n S and . 2        n S
The set of edges corresponding to the minimum bisection cut will support the demands exchanged between the nodes of the two regions. This gives a minimum value for the load of the graph which is for most practical networks a good approximation of the real load as shown in Section 7.

In a graph with n vertices, with minimum bisection cut , '

S S E

the load of the graph in case of all-to-all demand is at least:

. 2 2 ' 2             n n E S S 

Load of the Minimal Subgraph: a Spanning Tree

In the undirected case, the subgraph with the minimum number of edges is a tree, as it is the smallest connected subgraph, see e.g. Figure 7. This minimal configuration can be attained when the capacity is larger than the load given in Lemma 5.3.1.

Lemma 5.3.1 [Tree and Spanning Tree]

a) The load of a tree composed of n nodes is 2(n-v), where v is the size of the larger branch incident to the tree centroid. b) In a graph with n nodes and of maximum degree δ max , the load of a spanning tree is at least )), as the function x(n-x) is increasing for 0 ≤ x ≤ n/2. For the same reasons, the load of the tree is the load of the edge of the centroid (if the centroid is an edge) or incident to the centroid in the larger branch.

. 1 1 2 max max                           n n n
b) We have just shown that the load of a tree is the load of the edge centroid or incident to the centroid in the larger branch. The load is then minimum for a tree with minimum larger branch. In a graph of maximum degree δ max , the larger branch is of size at least (n-1)/δ max . Hence, the load of a spanning tree is at least .

1 1 2 max max                           n n n □
Note that the load of a (spanning) tree mostly depends on the maximum node degree of the underlying graph. On a complete graph where δ max =n-1, the tree with the lowest load is a star and its load is 2κ(n-1), to be compared with the load of a path κn 2 /2., for which δ max =2. Hence, networks with nodes of large degrees tend to attain the minimum configuration for smallest capacities, see Section 7.

Complete Graph -Bound on the Number of Spared Edges

We consider here the complete graph K n composed of n nodes and n(n-1)/2 edges.

This topology is the second extreme case (all possible edges) of our problem. It corresponds to the design problem of finding the best network satisfying the load when all possible edges between nodes can be used. The all-to-all routing is possible on the complete graph as soon as the capacity/demand ratio λ is larger than 2. We also have seen in the previous section that when λ is larger than 2(n-1) the routing is possible on the star with only n-1 edges, corresponding to the fraction 2/n of the total number of edges of the complete graph. But what happens between these two capacities? Lemma 5.4.1 In a complete graph with n vertices, the all-to-all routing uses at least

         1 , 2 ) 1 ( 2 max n c n n  
edges, with c the capacity of the edges.

Proof

When all the edges have the same capacity c and for all-to-all demands,

    V V j i j i d c E , ), , ( *



where d(i,j) is the shortest path distance between i and j. Note that 

  V V j i j i d , ) , ( is
given as a closed formula by twice the Wiener Index [START_REF] Wiener | Structural determination of paraffin boiling points[END_REF]. In a complete graph, all the paths have length one. If we remove the edge ij, we know that two paths (from i to j and from j to i) are now of length at least 2. Hence, for an optimal subgraph with |E

). * 2 ) 1 ( ( 2 * 2 ) , ( * E n n E j i d c E V V ij           
The bound, holding for any topology, gives . 2 8 the results of the integer linear program described in Section 2.2 given by CPLEX 10 for the complete graph with 5 nodes. The figure shows that the lower bound given in Lemma 5.4.1 is close to the optimal solution. The capacity/demand ratio λ varies between 2 and 8 as stated before. For λ=4, a gain of 30% of networks interfaces is attained, leading to 7 active links instead of 10.

) 1 ( 2 *      c n n E □ We validate in Figure

Results on the Square Grid

After providing some bounds on extreme cases, such as trees or complete graphs, we consider in this section MINIMUM EDGES ROUTING PROBLEM on the square grid which is an example of a structured network studied, e.g., in the context of wireless mesh networks [START_REF] Akyildiz | Wireless mesh networks: a survey[END_REF]. We give the load of the best spanning tree and of the full grid when all the edges are present in Section 6.1. We then propose bounds and constructions for intermediate loads in Section 6.2. Last, we compare the proposed constructions with the solutions given by the integer linear program and the heuristics LESS LOADED EDGE HEURISTIC and RANDOM HEURISTIC.

Limit Configurations

We first look at the load of the two limit configurations with minimum and maximum number of edges, namely spanning trees and full grids. Note that in the following, for sake of simplicity, results are presented for κ=1.

Spanning Tree

The load of the best (accepting the largest volume of demands) spanning tree is given by the following lemma. Lemma 6.1.1.1 (Grid Spanning Tree) The tree with the smallest load on a a×a square grid (a≥3), is a tree with a centroid of degree 4 and 4 branches of almost equal sizes. Its load is . 8

3 4 1 4 1 2 4 2 2 2 a a a a                        

Proof

In any a×a square grid, it is possible to partition the vertices into a central node C and 4 connected subsets of sizes (a 2 -1)/4 and (a 2 -1)/4. The proof is done by induction.

The induction hypothesis H a is: The partition P={P 1 , P 2 , P 3 , P 4 }exists for an a×a grid and part i of the partition is adjacent to side i of the square. It is true for the 3×3 grid and the 4×4 grid, see Figure 9. We prove that H a implies H a+2 by connecting the side i of the square to one of the vertices of part P i that is on side i.

Hence, there exists a spanning tree of centroid C, with four branch and whose largest branch is of size (a 2 -1)/4. Its load is then 2(a 2 -1)/4(a 2 -(a 2 -1)/4) and is maximum, as stated in Lemma 5.3.1. □

Full grid

The maximum volume of demands that can be routed on a square grid is given by a cut argument in the following lemma.

Lemma 6.1.2.1 (Load on a aa grid) The edge load on a grid is larger than, for a even, , 2 3 a and, for a odd,

. 1 1 1 1 2 3 2 3          a a a a

Proof

From the second general lower bound argument, with a cut "in the middle" of the grid. We divide the grid into two almost equal subsets.

If a even, we have a 2 /2 nodes in S and in S. We have a edges in the cut. Thus, we have ac2 a 2 /2 a 2 /2, giving c a 3 /2

If a odd, we have a 2 /2 nodes in S and a 2 /2+1 in S. But we have here a+1 edges in the cut. Hence, . 2 We have already got the load of the two extremes cases: the full grid (when we have 2n-2 ,n edges) and a spanning tree (when we have n-1 edges). We know that the load spans between two different orders from n 3/2 to n 2 . How the load evolves between these two values? We give a bound on the load based on the computations of the shortest paths at the end of the section. But first, we present constructions of subgraphs spanning between these two orders.

) 1 )( 1 ( 1 2 1 2 1 2 1 2 . 2 2 ) 1 ( 2 2 2 2 2 2                                       a a a a a a c a It gives . 1 1 1 1 2 ) 1 ( 2 ) 1 )( 1 )( 1 ( 3 2 3 2                a a a

Constructions

We present here a construction of a subgraph with n+p-2 ,p edges for p a square number, that is if ,p=q 2 . The load of the subgraph is of order n 2 / ,p. This construction gives an upper bound of the load of a grid with missing edges. For other values of p (-1≤p≤n), this formula is taken as an approximation of the load of the best subgraph. Note that it spans between the orders of the two limit configurations. We discuss this approximation for two examples, the 4×4 and the 10×10 square grids.

Proof

The proof is done by providing a construction with this load. We divide the grid into p regions, see Figure 10. The regions are connected into a square grid. The node inside a region are linked into a tree. The graph has n+p-2 ,p edges (n-1-(p-1) edges inside the regions and 2p-2 ,p edges of the grid). Note that when p=n, the construction is simply the full square grid. Similarly, when p=1, the construction is just a spanning tree.

Load of the edges of the square grid, L grid . The load of a grid with p nodes is ½.p 3/2 .

Each region corresponds to n/p or n/p nodes. Hence, between two nodes, there are (at most) n/pn/p routes instead of 1. (By choosing the routing of the grid for the n 2 /p 2 demands), we can route with a capacity of node. These demands have to be routed through the region. The spanning tree of a region can be constructed in a way that the (at most) 4 edges of the grid are connected by 4 branches to a node of the region with degree 4. Hence, it is possible to route this demand with a capacity of L grid ..

In addition, demands have to be routed between nodes inside the region. This corresponds to an all-to-all routing in a tree of size n/p. An additional capacity of 3/8.n 2 is needed.

In summary, we get

Lower Bound

Figure 11: Proof of Lemma 6.2.2.1. A grid with 5 edges removed: the edges are removed in a column (raw) starting from position 1. The shortest path between nodes A and B increases by 2 (blue path).

We give here a bound on the load based on the computations of the shortest paths. Lemma 6.2.2.1 Let G be an a×a square grid. The load of a subgraph of G with k edges is at least

. ) ( 4 ) 1 ( 2 3 ) 1 ( 2 1 ) 1 ( 1 2 3                                     a a k E k E i i a a a a k E a a k

Proof

The sum of the shortest path lengths for a full grid is directly obtained from the Wiener index (H. [START_REF] Wiener | Structural determination of paraffin boiling points[END_REF] ; Eric W. Weisstein. (w.d.)) of a grid. We multiply it by two, as, in our case, we have an all-to-all demand, that is we have both path (u,v) and path (v,u). We get (2a 3 .(a 2 -1))/3.

When you remove an edge from the grid, all the shortest paths that were using this edge are increased by 2 units, see Figure 11. For an edge at position i, there are at least 2i(a-i) such paths on the column (or raw) of the edge. It is minimum when i=1 and equal to 2(a-1). To obtain a lower bound on the load, we have to take a sequence of edge removal that minimizes the increase of the sum of the shortest paths. It is minimum to remove edges of a column (raw) with missing edges. The second edge removal increases at least 2(a-2) paths, and more generally the ith removal increases 2(a-i) paths. In total, at least a(a-1) paths are increased when a whole column (raw) has been removed.

In a subgraph with k edges, where |E|-k edges have been removed from the original graph,

         a k E
such columns (raws) can be removed. It gives the term

). 1 ( 2         a a a k E
The remaining edges are removed from the same column (raw) giving the term: We present results for the 4×4 grid (LP, lower bound, construction and heuristics) and for a 10×10 grid (lower bound, construction and heuristics), see Figure 12 and 13.

. ) 2 2 ( 2 ) 1 ( 1                a a k E k E i i a □

Results

Bound using Minimum Cut. On Figure 12, we give result for the 4×4 grid. We have plotted the path length bound (magenta -). We see that, on the contrary to the complete graph, that this bound is not very tight. The explanation is that edges in the square grid are not all equivalent: the edges in the middle of the grid have a larger load than those on the borders with a shortest path routing.

The load can be computed by looking at the minimum cut of the network as explained in Lemma 6.1.2.1. The cut composed by the a horizontal edges in the middle of the grid gives ca 3 /2. For the 4×4 grid, we can check that the load induced by the routing is greater than 4 3 /2=32. This cut phenomena also explains that as soon as the routing is possible (for λ=32), some edges can be spared (around 8%): the middle edges are fully loaded, but not the edges on the borders. The same cut phenomenas are present for some SNDLib topologies studied in the next section. Order given by construction. This order, given by Claim 6.2.1.1, is depicted on Figure 12 and 13. We see that it is very close (only a few percent) to the optimal solution given by the integer linear program and largely better than the bound using minimum cut. For the grid 10×10, we were not able to launch the integer linear program, and we see that LESS LOADED EDGE HEURISTIC behaves well compared to this order. How many network interfaces can be spared? For values of λ larger than 32, a large number of edges can be saved at the beginning: for the 4×4 grid, 25% for an overprovisioning factor of 1.5 (λ=48) and 33% for a factor of 2 (λ=64). The savings become less important for larger capacities: only a 4 percent difference between capacities of 64 and 96, and the tree is attained with an overprovisioning factor of 3 (λ=96). For this value of λ, we use a 2 -1=15 edges, when the full grid has 24 edges, saving 37.5% of edges.

Behavior of the heuristics. Note that the heuristic (green ×) behaves well and is close to the optimal values given by the integer linear program (red +). The heuristic is also significantly better than the Random heuristic, see Figure 12 and13. For example, for the 10×10 grid, for a capacity/demand ratio of 1000, LESS LOADED EDGE HEURISTIC saves 39% and RANDOM HEURISTIC saves 28%.

Results on General Networks

We present in this section the results of our proposed heuristics on general networks. We study ten classical network topologies extracted from SNDLib (http://sndlib.zib.de). In our experiments, we explore how many network interfaces can be spared for different ranges of overprovisioning factor. We consider a range of capacity/demand ratio λ starting from the smallest value λ 1 allowing to route all the demands (overprovisioning factor equals 1) to the value λ tree allowing to route on a minimal subgraph, that is a spanning tree (overprovisioning factor equals λ tree /λ 1 ). We also study the impact of this energy-efficient routing on the route lengths and on the network fault tolerance. To this end, we propose an integer linear program finding spanners of the topology having good stretch and two disjoint paths between all pairs of nodes. We compare the number of edges of these spanners with the one of the minimum subgraphs.

SNDLib Topologies

Table 2: (a) Gain of network interfaces (in %) depending on the overprovisioning factor and (b) Evaluation of the load given by the bounds in previous section with λ 1 the capacity/demand ratio for overprovisioning factor equals 1 and λ tree for the tree. We studied ten classical real network topologies extracted from SNDLib (http://sndlib.zib.de). These networks correspond to US (Atlanta, see Figure 14), European (Nobel EU, Cost266), or single country (Nobel Germany, France) topologies. Their sizes span from 15 to 54 nodes and from 22 to 89 edges, as summarized in Table 2. For these 10 topologies, we computed energy efficient routings for different capacity/demand ratios λ. We could only run the integer linear program for the smallest network, Atlanta, for which the results are presented in Figure 15. We see that LESS LOADED EDGE HEURISTICwell, attaining the optimal value most of the time, when the Random heuristic needs a larger λ to attain the same value. As a matter of fact CPLEX already takes several hours on Atlanta to solve the problem for one capacity/demand ratio. We thus present the results found by the heuristic (which takes only tens of ms) in Tables 2 and3.

Spared network interfaces.

We give the percentage of spared network interfaces in function of the overprovisioning factor (OF) in Table 2 (a). A factor of 1 means that we use the minimum capacity/demand ratio necessary to route all the demands (corresponding to the value λ 1 ), when, e.g., a factor of 2 means that we have twice the value λ 1 . Note that in most today's backbone networks overprovisioning is heavily used as it is an efficient and easy way to provide protection against failure: links are often used between 30 and 50 % of their capacity.

First, note that on some of the ten topologies, as soon as the routing is feasible (OF=1), some network interfaces can already be turned off (12% for Norway and Nobel EU). As a matter of fact, in this case, the important edges of the network (the edges in the minimum cut for example) are fully used, but at the same time edges at the periphery are less used and some can be spared. With an overprovisioning factor OF=2, around one third of the edges can be spared (and even 53% for the Pioro40 network). With larger factors (3 or 4), the gain is not as important, but still some network interfaces can be saved (e.g. 36% for Atlanta). We show in Table 2 (a), in the 2 last columns, the value of OF for which the tree is attained together with the corresponding spared network interfaces in percentage (SNE). The values are directly linked to the density of the network. For example, Norway needs a factor of 4.71 (λ tree =4.71×λ 1 ) to reach the tree with 26 links (instead of 51), sparing 49% edges.

Hence, the larger the density, the more the network interfaces that can be turned off. To conclude, for all the studied networks between one third and one half of the network interfaces can be spared for usual overprovisioning factors. Furthermore, when the best routing cannot be found by the integer linear program (large topologies), the proposed heuristic found close to optimal solutions.

Full Network Topology

We report in Table 2 (b) the minimum capacity/demand ratio λ 1 for which the heuristic can perform an all-to-all routing. As explained in Section , λ 1 depends on the minimum cut of the network. We reported for each network the minimum bisection cut dividing the network into two (almost) equal-sized regions. We computed this minimum bisection cut with an integer linear program. The bound on λ 1 implied by the cut is given in the second column of the table. We see that it gives a very good indication of λ 1 for most of the networks, even if the value is not tight, as the heuristic does not always find the optimal solution. For example, we see that the bound is tight for Atlanta, where the minimum cut is of size 3 and splits the network into two subnetworks of sizes 8 and 7. For Atlanta, and Nobel EU, the capacity/demand ratios evaluated by the minimum cut bound is equal to the values given by the simulations (λ 1 =38 for Atlanta and 131 for Nobel EU).

Spanning Trees

As explained in Section 5, the ratio λ tree , for which we get a spanning tree, depends on the network node degree. On the contrary to regular network, such as the grid, the existence of a spanning tree centered on the node of maximum degree with equalsized branch is not given. Hence, the bounds given in Table 2 (b) are not tight. Nevertheless, we see that the node degree is still a good indication on what can be achieved on these networks. Graphs with low maximum degree attain the best configuration for lower values of capacity/demand ratio λ tree . For example, the network Atlanta has a maximum node degree of 4 (the bound is 88) and λ tree is 101, when for Zib54, λ tree is 1385 for a maximum degree of 10 (the bound is 576).

Table 3: Impact of the energy-efficient routing on (a) the route length (Average multiplicative stretch factor) and on (b) the network fault tolerance (average number of disjoint paths).

Impact on the Network

We believe that network operators will implement energy efficient routing only if the impact on other parameters is limited. We discuss here the impact on the route lengths and on the fault tolerance of our proposed heuristic. Impact on the route lengths. When turning-off some components in a network, we save some energy but, at the same time, we route on longer paths. The multiplicative stretch is defined as the ratio between the average route length in the new routing divided by the average route length with the old routing (using all the edges). Results for the SNDLib topologies are given in Table 3 ( a). A stretch of one corresponds to the cases where no edge could be spared and thus the routing is not affected. We see that, as expected, the general trend is that when the overprovisioning factor increases, the paths become longer.

Nevertheless we see that the impact on the route lengths is limited. E.g., for the topology Zib54, the increase is 11% for the extreme case when routing on a tree (for 34% of turned-off network interfaces). In general, the increase for this extreme case spans from 11% to 50%, and in average 27%. For the network with the larger impact, Giul39, the stretch is increased by 50% for the tree, with a saving of 56% of the network interfaces. We see that a saving of already 45% is attained for OF=2, leading to a route length increase of only 18%. Impact on the fault tolerance. We measure in Table 3 (b) the network fault tolerance as the average number of disjoint paths linking two nodes. We see that the full network topologies have an average number of disjoint paths between 1.82 and 4.90. When routing on the tree, this number is of course 1 as only one route exists, and this value is almost already attained for OF=3. The drop is quick as all the ten networks have a number below 1.41 for OF=2. Discussion on Technology. When there is a failure between two nodes, it may be necessary to turn on some network interfaces to compute a new routing for some demands. Hence, this study shows that the use of such energy efficient solutions is conditioned by the existence of technologies allowing a quick switching on of network interfaces. Network interfaces companies are currently working on designing this kind of interfaces as mentioned in [START_REF] Akyildiz | Wireless mesh networks: a survey[END_REF].

We propose in the following section a solution for the routing with fault-tolerant spanners, such that there are two disjoint paths per demand. Therefore, the impact of links failures on the network will be reduced because a protection path with enough capacity will be available.

Table 4: (α,β)-spanners with 2 disjoint paths between every pair of nodes.

Fault tolerant spanners

During the simulations, we show that as soon as some network interfaces are spared, the average number of disjoint paths fail dramatically. Therefore, the network fault tolerance is no longer assured, as any failure will imply the re-computation of the routing structure. As the network tolerance is of major importance, we show in this subsection how to find a fault tolerant spanner which has at least γ disjoint paths for each demand and which respects additive and multiplicative constraints for the stretch.

We show in the following that this structure is related to the (α,β)-spanners (D. Peleg and A.A. Schaffer. (1989)). An (α,β)-spanner of a graph G=(V,E) is a subgraph H=(V(H)V,E(H)E) of G such that (u,v)V×V, This problem can be modeled as previously seen, with a multicommodity integral flow problem in which the objective function is the minimization of the number of edges. The demands D st are equal to γ between every pair of vertices (s,t)V×V. As the utilization constraint imposes only unitary flow per edge and per demand, γ disjoint paths will be set. Finally, the distance constraint limits the maximum route length that can be accepted per demand. Note that this constraint is given in a global manner for all the γ disjoint paths.

The integer linear program can be modeled as follows.

The Objective function is



 E e e x min subject to:

Flow constraints: , , ) , ( V u V V t s                  0 ) ( ) (   u N v st uv u N v
        N N d f G H E v u N N uv
This spanner provides a gain of 13.64% of the number of network interfaces.

Table 4 shows the results of the integer linear program for Atlanta, New York, Nobel Germany and France. The number of disjoint paths per demand γ=2. As the program takes several hours to be launched on large topologies, we set a limit of 1 hour, and a gap from the optimal solution of 3% for the integer linear program. The results show that for Atlanta, 23% of network interfaces can still be spared. The spanner needs an overprovisionning factor of 1.92 and an average stretch of 1.42 is attained. For Atlanta, the integer linear program was not able to find (1,1), (1,2) and (2,0) fault tolerant spanners. This is mainly due to topology constraints where 2 disjoint paths with such distance constraints cannot be found.

Note that we compute the average stretch by the comparison with fault-tolerant spanners with two disjoint paths per demand, without the distance constraint, and with the objective of minimization of 

Conclusion and Perspectives

In this work, we present through a simplified architecture the problem of minimizing power consumption in networks. We show non-approximation results. The simulations on real topologies show that the gain in energy is significant when some network interfaces can be turned-off.

• At least one third of the network interfaces can be spared for usual range of demands. • For a medium-sized backbone network, this leads to a reduction of power consumption of approximately 33MWh per year (for Cost266 with 37% of spared interfaces). For this estimation, we consider a scenario where the turned-off interfaces of our simplified architecture are 4-port Gb Ethernet linecards. We believe it corresponds to a reasonable capacity for backbone networks. We use the consumption values given in [START_REF] Chabarek | Power awareness in network design and routing[END_REF]: 100W for these linecards.

• The route lengths increase, but not too much: in average 27% for almost all studied topologies.

• Fault tolerance can be achieved with the use of fast switching-on technologies or by adding disjoint path constraints to the problem so that the network remains γ-connected, allowing a tolerance of γ-1 failures.

• The bounds for specific topologies are useful for general networks to evaluate the overprovisioning factors needed for such energy-efficient solutions.

As part of future work, we plan to study a detailed cost function for a more complex router architecture. Moreover, we will carry on lab experiments on small network topologies to measure in practice the performance of the proposed energy-efficient routing.

  composed of 14 nodes and 15 edges. Integers on edges represent the different capacities. We denote by 1

D

  (b), there are also two demands but the amount of demand from s must be routed through the shortest path composed of 4 edges because of the edge of capacity 11. Thus E * is composed of the two previous edgedisjoint shortest paths of length 4the three edges of capacity 16, only two demands can share these 3 edges. Two optimal solutions are depicted in these figures, each one of cost |E * |=9. In these optimal solutions, the 3 edges of capacity 16 support the demand 3 D and one of the two demands 2 D (for Figure3 (a)) or 1 D (for Figure3(b)). The other demand is routed through the shortest path.

Figure 1 :

 1 Figure 1: no solution for the MINIMUM EDGES ROUTING PROBLEM with 10 1 1 

Figure 2 :

 2 Figure 2: two different solutions for the MINIMUM EDGES ROUTING PROBLEM with almost the same set of demands.

D

  are routed through shortest paths.

D

  are routed through shortest paths.

Figure

  Figure 3: Two different optimal solutions

Figure 4 :

 4 Figure 4: Construction of G' from G used in the proof of Theorem 3.1.

Figure 5 :

 5 Figure 5: Graph G=(V,E) used in the proof of Theorem 3.2. Each edge eE has capacity c e =c.

  e r (depending on the demands supported on e). A set of demands D , each demand has a volume of traffic st D .Sort the demands in random order while st D is a demand in D with no routing assigned do Compute a shortest path st SP with the metric the routing (if it exists) assigned to the demands in D .

Figure 6 :

 6 Figure 6: Undirected weighted graph used in Lemma 4.3.2. From u to v, there are |D|+1 elementary paths: 1 is composed of 4 edges of infinite capacity and |D| are composed of 3 edges of capacity 1. There are |D| demands, each of value 1.

Figure 7 :

 7 Figure 7: A Toy example, study of the complete graph with 5 vertices: subgraphs with the minimum number of edges, with λ the capacity/demand ratio, lH (D) average route length and DP H (D) the average number of edgedisjoint paths between two nodes where D contains the all-to-all demands.

  of a Graph) Let G=(V,E) be an undirected weighted graph and D the set of demands. The load of G is the minimum over all routings (feasible flows F) of the maximum load over all edges:

  cut lower bounds. We present here a generalized max flow min cut argument. For each subset SV, we must have . when all the edges have the same capacity c and all the couples of nodes have the same demand κ

Proofa)

  Load of an edge. Removing an edge e in a tree disconnects the graph into 2 connected components of sizes v(e) and n-v(e) (with v(e)≤n-v(e)). The load of this edge is 2(e)(n-v(e)). Tree centroid. Consider the tree centroid C and consider one of the branch starting at C. A tree centroid is a vertex or an edge C which minimizes over all nodes the largest connected component induced by removing C from the graph. The maximal load of an edge of this branch is the load of the edge e * incident to C. Indeed, for any e of the branch v(e)<v(e * ) and v(e*) ≤ (n+1)/2, as any branch of the centroid is of size less than (n+1)/2. Hence 2v(e)(n-v(e))≤2v(e * )(n-v(e *

  of length at least two. This gives

Figure 8 :

 8 Figure 8: Number of spared edges on the complete graph with 5 nodes. Bound of Lemma 5.4.1 and integer linear program described in Section 2.2.

Figure 9 :

 9 Figure 9: Partition of the grid into 4 connected subsets of almost equal sizes. Left: 3×3 grid, Middle: 4×4 grid, Right: Induction step of Lemma 6.1.1.1.

Figure 10 :

 10 Figure 10: Construction of a subgraph with n+p-,p edges: 1-Divide the grid into p almost equal-sized regions (p=4 here). 2-Link the regions into a grid (red edges). 3-Connect nodes inside a region into a tree (blue edges).

  Let p be a square number between 1 and n. The load of a subgraph with n+p edges is less than

  edges inside the regions L region . There are at most 4L grid entering/leaving

Figure 12 :

 12 Figure 12: Percentage of spared network interfaces for a 4×4 grid.

Figure 13 :

 13 Figure 13: Percentage of spared network interfaces for a 10×10 grid.

Figure 14 :

 14 Figure 14: Atlanta network with 15 nodes and 22 edges.

Figure 15 :

 15 Figure 15: Percentage of spared network interfaces for the Atlanta network.

  d H (u,v)≤.d G (u,v)+ in which |E(H)| is minimized. This guarantees that the distances of any couple of vertices in the spanner is streched by a multiplicative and additive factors α and β, ideally close to 1 and 0.

Figure 16 :

 16 Figure 16: A (1,3)-spanner for Atlanta with 2 disjoint paths for each demand represented in full lines.

Figure 16

 16 Figure16shows a (1,3)-spanner with 2 disjoint paths (γ=2) between any pair of vertices. Consider for example the distance d H (N5,N13) between N5 and N13. In G, d G (N5,N13)=2, and in the spanner H, the two disjoint paths, (N5,N0,N6,N13) and (N5,N12,N10,N13) have both distances 3. This respects the distance constraint:. 10 ) 3 ) 13 , 5 ( 1 ( 2 6

  section, fault-tolerant spanners are interesting solutions to achieve power consumption reduction while taking into account network fault tolerance and distance constraints.

Table 1

 1

	summarizes the notations used throughout the paper.

Table 1 :

 1 Summary of Notations

  We consider the same set of demands. G' is depicted in Figure4. Suppose now that there is a constant k≥1, such that there exists a polynomial-time algorithm finding a subset E k E ensuring that |E

	G; we add a path P 1	between s 1	and t 1	composed of x>k|E| edges and a path P 2
	between s 2	and t 2	also composed of x>k|E| edges. Each edge of P 1	and P 2	has an
	infinite capacity.

k |/|E * |≤k, where E * is an optimal solution of the MINIMUM EDGES ROUTING PROBLEM. We name E' k the solution found for G' by this algorithm and we have |E'

  Compute a feasible routing of the demands with Algorithm 2 while Edges can be removed do Remove the edge e' that has not been chosen once, with the smallest

	Algorithm 1 LESS LOADED EDGE HEURISTIC
	Require: An undirected weighted graph	G 	, ( E V	)	where each edge	E e  has an
	initial capacity	c and a residual capacity	r (depending on the demands supported
									e	e
	on e). A set of demands	D , each demand has a volume of traffic	D .
									st
		e		E	,	r		c
						e			e
									c	e	' /	e r	'	.
	Compute a feasible routing with Algorithm 2
	If no feasible routing exists, then put back e' in	G
	end while
	return the subgraph	G .
	Algorithm 2 Feasible routing Heuristic for ROUTING PROBLEM
	Require: An undirected weighted graph	G 	, ( E V	)	where each edge	E e  has an
	initial capacity

e c and a residual capacity

http://www-sop.inria.fr/teams/mascotte/Contrats/DIMAGREEN/wiki/

Acknowledgements

This work has been partly funded by ANR DIMAGREEN 1 (DesIgn and MAnagement of GREEN networks with low power consumption).

Key Terms and Definitions

APX: in complexity theory, the class APX ("approximable") is the set of optimization problems that admit a polynomial-time approximation algorithms with approximation ratio bounded by a constant. In other words, if a problem is not in APX, it means that there does nos exist a polynomial-time within a constant factor of approximation (unless P=NP).

Heuristic: algorithm that finds quickly a solution to a problem. For NP-hard problems, heuristic algorithms are used to find in polynomial time a solution, not necessaily optimal, but a solution that may be not so bad.

ICT: Information and Communication Technology is a term that includes any communication device or application: radio, television, cellular phones, computer and network hardware and software, satellite systems, and so on.

Complete graph: in graph theory, a complete graph is an undirected graph with all possible edges. In other words, if any two nodes of the graph are linked by an edge, then the graph is a complete graph.

Grid: in graph theory, a grid graph is the square product of two paths.

Linear Programming: mathematical method for describing an optimization problem in a mathematical model. Linear Programming is a technique for optimization problems with linear objective functions, subject to linear equalities and linear inequalities.

Multicommodity flow problem: network flow problem with multiple commodities (demands) between different sources and sinks. In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. This amount of flow cannot exceed the capacity of the edge. Given a graph, a set of demands, and the capacities of the edges, the mulicommodity flow problem consists in finding a flow network satisfying the demands and respecting the constraints of capacities.

Network: set of nodes linked by links. A communication network is a set of nodes connected by links which permit telecommunication between the nodes A network can be seen as a graph composed by a set of vertices and a set of edges.


V De Andrade
email: vdeandrade@anl.gov

J Ganne

B Dubacq

G Ryan

F Bourdelle

A Plunder

G Falkenberg

J Thieme

Retrieving past geodynamic events by unlocking rock archives with μ-XRF and μ-spectroscopy

Rocks are commonly polycrystalline systems presenting multi-scale chemical and structural heterogeneities inherited from crystallization processes or successive metamorphic events. This work illustrates how spatially resolved analytical techniques coupled with thermodynamic approaches allow rock compositional variations to be related to large-scale geodynamic processes. Emphasis is placed on the contribution of quantitative chemical imaging to the study of 2.2-2.0 Gy old metamorphic rocks from the West African Craton. A thorough analysis of elemental chemical maps acquired on rock thin sections enabled high pressure relic minerals to be located and re-analyzed later with precise point analyses. The pressure-temperature conditions of crystallization calculated from these analyses are typical of modern subduction zones. These results push back the onset of modern-style plate tectonics to 2.15 Gy, i.e. more than one billion years earlier than was consensually accepted. The second part of the paper describes the imaging capabilities offered by the new ultra-bright diffraction limited synchrotron sources. Experimental data acquired with the Maia detector at beamline P06 at Petra III as well as simulations of µ-XRF spectra that will be generated at the SRX beamline at NSLS-II are presented. These results demonstrate that cm 2 large chemical maps can be acquired with submicron spatial resolution and a precision suitable for thermobarometric estimates, with dwell time smaller than 1 millisecond. The last part of the paper discusses the relevance of utilizing recent X-ray fluorescence nanoprobes for diagenetic to low grade metamorphism applications.

Introduction

Rocks are products and witnesses of geodynamic events shaping the Earth and planetary bodies. A rock is defined by its mineralogy that is inherited from its genesis and from the successive events it encountered during its lifetime. Historically, geologists endeavor to characterize the mineralogy of rocks, from which they infer large-scale processes, for example derived from plate tectonics. With the constant improvement of analytical tools in terms of sensitivity and spatial resolution, the apparent degree of complexity of rocks keeps increasing. The amount of information stored in rock-forming minerals is indeed extremely large, and more information about these minerals leads to a better understanding and more accurate modeling of rock-forming processes. These processes resulted in heterogeneities in the physical and chemical properties of continental crustal rocks over scales varying from the geological unit (10 2 -10 3 meters) to the mineral (10 -3 -10 -4 meters) ; several studies within the past 10 years focused on heterogeneities occurring at the micrometer and nanometer level [START_REF] Yamato | New, high-precision P-T estimates for Oman blueschists: implications for obduction, nappe stacking and exhumation processes[END_REF][START_REF] Vidal | P-T-deformation-Fe3+/Fe2+ mapping at the thin section scale and comparison with XANES mapping: application to a garnet-bearing metapelite from the Sambagawa metamorphic belt (Japan)[END_REF][START_REF] Andrade | Quantification of electron microprobe compositional maps of rock t h i n s e c t i o n s : a n o p t i m i z e d m e t h o d a n d e x a m p l e s[END_REF][START_REF] Bourdelle | Clay minerals as geo-thermometer: A comparative study based on high spatial analyses of illite and chlorite in Gulf Coast sandstones (Texas, U.S.A.)[END_REF][START_REF] Vidal | Exhumation paths of high-pressure metapelites obtained from local equilibria for chlorite-phengite assemblages[END_REF]. Thanks to elemental chemical imaging acquired either with electron probe micro-analyzer (EPMA), transmission electron microscope (TEM) or synchrotron X-ray fluorescence microprobe, scientists were able to characterize micrometric subdomains and the modalities of their interconnections. Combining thermodynamic models with chemical maps, it is possible to calculate the conditions of crystallization of the rock-forming minerals, which are combined to obtain high resolution pressuretemperature (P-T) paths in favorable samples [START_REF] Yamato | New, high-precision P-T estimates for Oman blueschists: implications for obduction, nappe stacking and exhumation processes[END_REF][START_REF] Vidal | P-T-deformation-Fe3+/Fe2+ mapping at the thin section scale and comparison with XANES mapping: application to a garnet-bearing metapelite from the Sambagawa metamorphic belt (Japan)[END_REF][START_REF] Andrade | Quantification of electron microprobe compositional maps of rock t h i n s e c t i o n s : a n o p t i m i z e d m e t h o d a n d e x a m p l e s[END_REF][START_REF] Lanari | XMapTools: A MATLAB©-based program for electron microprobe X-ray image processing and geothermobarometry[END_REF]. Such P-T paths are of primary importance for the understanding of geological processes. If EPMA remains one of the main analytical tool of geologists, it shows important limitations when it comes to chemical imaging, analysis of trace elements and spatial resolution below a few microns. A typical acquisition time for a single analysis of major elements is about 1 minute. Such a dwell time is incompatible with chemical imaging, where hundreds of thousands -if not millions -of analyses are required. Ultra-high brightness synchrotron Xray fluorescence microprobes are currently the most suitable instruments to overcome the physical limitations of non-synchrotron laboratory techniques. The current light source construction projects like NSLS-II, MAX-IV or the upgrades of ESRF and APS [START_REF] Reich | Ultimate upgrade for US synchrotron[END_REF] aiming for ultra-low emittance sources are about to enable very fast imaging of elements in concentration down to the sub-ppm level. The several-orders-of-magnitude gain in flux in comparison with current facilities will be also highly favorable to 3D imaging, boosting time consuming tomography techniques with a micro or nano pencil beam in combined fluorescence and diffraction mode.

The first part of this paper illustrates the contribution of micro X-ray fluorescence (µ-XRF) imaging and microspectroscopy to the study of metamorphic rocks. The second part highlights the possibilities offered by intense new generation synchrotron fluorescence microprobes l i k e the Submicron Resolution X-ray Spectroscopy beamline [START_REF] De Andrade | The sub-micron resolution X-ray spectroscopy beamline at NSLS-II[END_REF][START_REF] De Andrade | Simulation and optimization of the NSLS-II SRX beamline combining ray-tracing and wavefront propagation[END_REF](SRX) at the National Synchrotron Light Source II (NSLS-II). Recent detector developments are also discussed. The third section focusses on the interest of zooming at the nanoscale with XRF nanoprobes while the last one concludes on radiation damage that may occur with high fluence X-ray beams.

Contribution of fluorescence microprobes to the study of the 2.2-2.0 Gy old West African metamorphic province

This part comments on a study [START_REF] Ganne | Modern-style plate subduction preserved in the Palaeoproterozoic West African craton[END_REF] performed on the West African Craton (WAC). As most of the other metamorphic units in Archaean and Palaeoproterozoic cratons, WAC mainly consists o f volcano-sedimentary and volcano-plutonic basins metamorphosed in greenschist facies. WAC rocks are principally composed of phyllosilicate called chlorite (chl) and phengite (phg) stable over large ranges of pressure and temperature. Previously, the lack of detailed thermodynamic data on these mineralogical phases has been a h i n d r a nce t o obtaining precise and accurate P-T estimates of greenschist facies rocks. Owing to recent advances in our knowledge of the thermodynamic properties of these minerals [START_REF] Dubacq | Dehydration of dioctahedral aluminous phyllosilicates: thermodynamic modelling and implications for thermobarometric estimates[END_REF][START_REF] Vidal | Thermodynamic modelling of clay dehydration, stability and compositional evolution with temperature, pressure and H2O activity[END_REF][START_REF] Parra | A thermodynamic model for Fe-Mg dioctahedral K white micas using data from phase-equilibrium experiments and natural pelitic assemblages[END_REF][START_REF] Vidal | A Thermodynamic Model for Fe-Mg Aluminous Chlorite Using Data from Phase Equilibrium Experiments and Natural Pelitic Assemblages in the 100° to 600°c, 1 to 25 kb Range[END_REF], detailed investigations of the thermal evolution of the WAC has been possible.

Hundreds of rock thin sections were prepared from samples collected during field missions in Burkina Faso. Following visible light microscopy, tens of samples were selected to be analyzed with point EPMA analyses, while EPMA images were acquired on a few of the most promising samples. Chl and phg were preferentially analyzed. From the measured compositions, the thermodynamic multi-equilibria technique [START_REF] Berman | Thermobarometry using multi-equilibrium calculations: a new technique, with petrological applications[END_REF] can be applied. This approach checks if different mineralogical phases are in thermodynamic equilibrium and returns the P-T conditions of equilibrium, interpreted as conditions of crystallization. Below ~550 o C, it has been demonstrated that rocks do not fully re- The Si-poor chl and K-depleted phg corresponding to the high P group A are mostly observed in the early-formed microstructures (modified after Ganne et al., 2011) [START_REF] Ganne | Modern-style plate subduction preserved in the Palaeoproterozoic West African craton[END_REF].

equilibrate. Dissolution / crystallization processes take over intra-crystalline diffusion. New crystallizations occurred locally while environmental constraints like P & T evolve. Metamorphic rocks end up as a mosaic of subdomains of different compositions whose spatial organization is a result of deformation structures, rock protolith, fluid chemistry and rock trajectory in the continental crust.

In parallel to EPMA analyses that are insensitive to the speciation of elements, µ-XANES spectra were acquired on the ID21 beamline at the ESRF to quantify the Fe 3+ /(Fe 2+ +Fe 3+ ) ratio in several chl and phg g r a i n s . The amount of Fe 3+ i n c o r p o r a t e d i n p h y l l o s i l i c a t e v a ries significantly a n d h a s important consequences for the P-T calculations. A thermodynamic method allowing the inference of this ratio in chl has been proposed [START_REF] Vidal | P-T-deformation-Fe3+/Fe2+ mapping at the thin section scale and comparison with XANES mapping: application to a garnet-bearing metapelite from the Sambagawa metamorphic belt (Japan)[END_REF] and validated at the ESRF on the ID24 beamline, with a µ-XANES imaging approach [START_REF] Muñoz | Redox and speciation micromapping using dispersive X-ray absorption spectroscopy: Application to iron in chlorite mineral of a metamorphic rock thin section[END_REF]. This method has been extended here to phg and confirmed with µ-XANES spectra acquired on ID21 as control points. In some phg, the amount of Fe 3+ is greater than 80%. Building on these new methods and considering in addition the interlayer water content in phg [START_REF] Dubacq | Dehydration of dioctahedral aluminous phyllosilicates: thermodynamic modelling and implications for thermobarometric estimates[END_REF], the multi-equilibria technique was successfully applied. For most of the samples, more than a hundred P-T conditions of crystallization were returned, defining high resolution P-T paths (fig. 1d). The most remarkable results came from two samples, where the calculated pressure of crystallization reached 10-12 kb for temperatures lower than 450 o C, and where a segment of their P-T path follows a cold thermal gradient around 10-12 o C.km -1 . These conditions are typical of modern subduction zones, suggesting that modern-style plate tectonics already existed during the Palaeoproterozoic era. These results push back the onset of modern-style plate tectonic to 2.15 Gyr, i.e. more than one billion years earlier than what was consensually accepted. P-T path calculation of rocks from the WAC has been relatively straightforward. However, finding the relic minerals present in minute quantities and that crystallized at high P in a subduction zone has proved challenging. Amongst s e v e r a l hundred phg a n a l y s e s , o n l y o n e w a s i n t h e r m o d y n a m i c equilibrium with the tested chl, a result statistically not robust enough to question the date of the onset of modern-style tectonics. If the µ-XRF images obtained cover the high pressure relic minerals (fig. 1a-c), the ± 2 kb large error bars of the P-T calculations resulting from low dwell time analyses (100 ms/pixel in imaging mode) prevent drawing definitive conclusions. However, the precision of chemical maps on major elements is good enough to highlight different generations of phyllosilicates. P-T maps of crystallization have been derived from these chemical maps where the location of HP relics could be inferred out of the background noise (fig. 1e). A new set of high precision (1 minute dwell time) point analyses performed on tiny grains pre-localized on P-T maps eventually revealed the HP history of rocks.

Necessity for high flux fluorescence microprobes

Using modern synchrotron XRF microprobe would have been of great interest in the WAC study framework, because the high flux delivered by beamlines provides analytical precision comparable to 1 minute long point EPMA analyses, but with dwell time in the millisecond range. In the case of latest generation synchrotron sources like NSLS-II, i n v o l v i n g s t a t e o f t h e a r t f l u o r e s c e n c e d e t e c t o r s , mapping of elements with sup-ppm concentrations would be feasible with millisecond dwell-time, providing that detectors are able to handle high count rates. Trace elements are of great interest in Earth Science because they provide geologists with information on large geodynamic cycles. Many trace elements also are of economic interest. Being able to map their spatial distribution in rocks will bring new light on their transport modes. The SRX beamline at NSLS-II will be equipped with two kinds of energy dispersive X-ray spectrometers (EDX). One is the Maia [START_REF] Ryan | The New Maia Detector System: Methods For High Definition Trace Element Imaging Of Natural Material[END_REF][START_REF] Ryan | Large detector array and real-time processing and elemental image projection of X-ray and proton microprobe fluorescence data[END_REF][START_REF] Ryan | Elemental X-ray imaging using the Maia detector array: The benefits and challenges of large solid-angle[END_REF], a collaborative undertaking between CSIRO and Brookhaven National Laboratory. The last version of the Maia benefits from a large solid angle of 1.2 sr with 384 elements that can handle dwell time in the 10's µsecond range. With a maximum count rate of 50k counts/s/element, Maia can manage a maximum rate of 19M counts/s before saturating. The drawback of the detector is currently its average energy resolution of about 300 eV. Figures 3 and4 show images of trace elements concentrations in a metamorphic rock containing quartz, chloritoid and garnet in addition to chl and phg [START_REF] Plunder | How continuous and precise is the record of P-T paths? Insights from combined thermobarometry and thermodynamic modelling into subduction dynamics (Schistes Lustrés, W. Alps)[END_REF]. Maps were acquired with the 384 version B of Maia on the P06 beamline at Petra III, with incoming beam energy set at 20.5 keV. The experimental setup uses Kirkpatrick-Baez (KB) mirrors as focusing optics with characteristics close to those of SRX (fig. 2). During the experiment, the KB focusing optics provided about 10 12 ph/s into a 300×300 nm 2 beam spot [START_REF] Schroer | Hard X-ray nanoprobe at beamline P06 at PETRA III[END_REF]. A 4×8 mm 2 area was scanned with a 0.6 µm large beam a n d a 0 . 5 ms dwell time. The images c o r r e s p o n d t o 1 3 3 3 2 ×6666 pixel 2 h y p e r s p e c t r a l fluorescence data from which elemental composition maps were extracted using the Dynamic Analysis method [START_REF] Ryan | Quantitative trace element imaging using PIXE and the nuclear microprobe[END_REF]. The method is based on a fundamental parameters approach to µXRF quantification using the GeoPIXE software that builds a transformation matrix to project individual events into pixel concentration after following the fitting of a representative spectrum with emission lines as well as the Compton and Thomson scattering [START_REF] Ryan | The New Maia Detector System: Methods For High Definition Trace Element Imaging Of Natural Material[END_REF]. The resolution (in term of pixel number) obtained here is 43 times higher than the Blu-ray standard for instance. For such analytical conditions, detection limits are of the order of a few ppm. But it must be kept in mind that the ability to discern spatial chemical gradients also depends on relative chemical variations. The quantitative analyses forming the images of figures 3 and 4 are being studied in the framework of a large project concerning trace elements in metamorphic rocks and are not discussed here. They are exhibited here to illustrate the results scientists can expect with sub-millisecond dwell time for different trace element contents. Imaging tests were also performed on an EPMA Cameca SX100 at the ISTEP laboratory of the Paris 6 university in France. For analytical condition of 20 kV and 300 nA, a detection limit of 400-500 ppm has been reached with a dwell time of 300 ms using 4 spectrometers (~1.2 ms dwell time / spectrometer).

SRX will also operate with one ME3 and another ME4 multi-element Vortex silicon drift detector (50 mm 2 per element). Detectors will be combined with the new Quantum Xspress3 electronics, which claims a high count-rate capability providing 200, 300 and 400 eV energy resolution for photon flux of 1, 2.3 and 3 million counts per second (Mn Kα emission at ~5.9 keV). This means that the 7 elements should be able to provide 7, 16 or 21 million counts/s for energy resolution of 200, 300 or 400 eV, although a sub-ms pixel spectrum acquisition capability is yet to be demonstrated. However, the issue that remains when large elements experience high count rate is the pile-up effect for non-diluted samples like rocks. Commissioning data shows that with 3 M counts/s/element throughput on concentrated samples, background level generated with pile-up could reach about 20% of the main peaks intensity, jeopardizing trace elements detection. Z minus 1 filters have to be introduced between the sample and the detector to preferentially attenuate the most intense emission lines. For instance, a Mn foil with an absorption edge at 6.5 keV will absorb preferentially Fe K-α emission line. To summarize, Maia provides very high throughput, allowing raster scanning large areas of a square centimeter with submicron resolution and sensitivity of the order of a ppm. It can discern subtle chemico-spatial variations in a rock for a large range of elements and concentrations or locate tiny and rare particles [START_REF] Lintern | Natural gold particles in Eucalyptus leaves and their relevance to exploration for buried gold deposits[END_REF] or preserved relic mineral in matrix. It also opens new paths for fluorescence µtomography or µ-XANES imaging spectroscopy. Megapixel hyperspectral XANES images so far only are achievable using full-field absorption imaging [START_REF] Fayard | The new ID21 XANES full-field end-station at ESRF[END_REF][START_REF] Beck | The redox state of iron in the matrix of CI, CM and metamorphosed CM chondrites by XANES spectroscopy[END_REF][START_REF] De Andrade | Submicrometer Hyperspectral X-ray Imaging of Heterogeneous Rocks and Geomaterials: Applications at the Fe K-Edge[END_REF] can be obtained in fluorescence mode [START_REF] Cook | Determination of the oxidation state of Cu in substituted Cu-In-Fe-bearing sphalerite via μ-XANES spectroscopy[END_REF]. New detectors, such as the Vortex multi element arrays coupled with fast electronics also show great promise given a suitable data acquisition system.

Without considering potential radiation damages on the sample, would these detectors be able to fully sustain the outstanding flux of SRX? SRX will host in its end-station a microprobe and a nanoprobe, focusing on the sample respectively more than 10 13 ph/s into a submicron spot and more than 10 12 ph/s into a 50 nm spot. Both should be the most intense submicron and sub-100 nanometer , for a Maia detector in backscattered geometry and a single element SDD for different working distance (15, 30, 50 and 70 mm), when operating on the SRX nanoprobe, i.e. with an incoming flux of 10 12 ph/s. Dwell time: 50 ms. The Maia saturates at 5.10 4 ph/s, and the SDD warranty an energy resolution of 200, 300 and 400 eV for count rates of 1, 2.3 and 3M ph/s. beams of the world. When analyzing non diluted samples, with intense major element lines, the experiment performed at Petra III on P06 beamline demonstrated that the incoming beam intensity should stay below 10 11 ph/s to prevent detector saturation. To anticipate performances of the SRX detectors, simulations of fluorescence spectra were performed with the XMI-MSIM software [START_REF] Schoonjans | A general Monte Carlo simulation of energy-dispersive X-ray fluorescence spectrometers â€" Part 6. Quantification through iterative simulations[END_REF], a Monte Carlo code dedicated to ED-XRF spectrometers including several features such as the simulation of M-lines and cascade effects. Simulations represent the Maia 384 and a single SDD element (energy resolution fixed at 200 eV) for different working distances and an incoming beam of 10 12 ph/s as for the nanoprobe (fig. 5). The simulated sample is a 20 µm thick chl crystal. The input composition corresponds to an analyses made by laser ablation mass spectroscopy on a chl imaged in fig. 34. It turns out that the Maia will experience 10 6 ph/s/elt while it can only handle 5.10 4 ph/s/elt, and the SDD should move 6 cm back to operate at 1Mcts/s. Current state of the art EDX technologies are clearly a limiting factor for operating SRX at its full potential. This high flux density however offers flexibility. It allows to maintain short dwell time even for highly diluted samples, or still to work on very thin samples (<1 µm). In such cases, the amount of fluorescence emitted by thin samples drops while the spatial resolution degradation due to X-ray depth penetration is minimized.

Utilization of new wavelength dispersive spectrometers (WDS) is a credible alternative to EDX in order to benefit from the very intense beams of ultra-low emittance new synchrotron sources. With recent progresses in fabrication of polycapillary optics, compact WDS with large solid angles are now feasible and easily integrated into fluorescence microprobes [START_REF] Cotte | Coupling a wavelength dispersive spectrometer with a synchrotron-based X-ray microscope: A winning combination for micro-X-ray fluorescence and micro-XANES analyses of complex artistic materials[END_REF][START_REF] Szlachetko | Wavelength-dispersive spectrometer for X-ray microfluorescence analysis at the Xray microscopy beamline ID21 (ESRF)[END_REF]. They provide energy resolution superior to EDX, ranging from ~5 to ~40 eV according to photon energy probed and crystal analyzers used for Bragg reflections. If these polycapillary optics based WDS designs still not sustain the comparison with recent EDX in term of efficiency, it would not saturate and not produce any pile-up with the 10 13 ph/s flux of the SRX microprobe, and would then outclass the EDX presented earlier. However, the down side of WDS is that a full emission spectrum cannot be acquired in one shot. A continuous spectrum is obtained by rocking the analyzer and the detector. It means that one set polycapillary / analyzer / detector at fixed location in imaging mode can analyze only one element at a time.

Zooming from micro to nanometer scale with XRF analyses

Fluorescence nanoprobes are nowadays blooming in synchrotron facilities, especially to support research on nanomaterials, but these instruments are also relevant for metamorphic geology where tiny objects or nanoscale processes are involved. For instance, the study of small mineral inclusions, whose crystallization occurs at high P-T conditions, presents a strong interest since such objects are a window on Earth interior. Inclusions trapped in diamonds can be exhumed from locations as deep as the lower mantle [START_REF] Walter | Deep Mantle Cycling of Oceanic Crust: Evidence from Diamonds and Their Mineral Inclusions[END_REF]. Because of technical limitations, most studies have been performed so far on micro inclusions, but nanoprobes make possible to revisit samples containing nano-inclusions [START_REF] Logvinova | Nanometre-sized mineral and fluid inclusions in cloudy Siberian diamonds: new insights on diamond formation[END_REF].

Nanometric spatial resolution is also particularly relevant for probing diagenetic to low grade metamorphic rocks. Indeed, mineralogical processes generally occur at the sub-micron level for relatively low temperature (T<250 o C), when slow kinetics of reactions do not permit crystallization of large grains. Phg crystallize as clay-size illite, intercalations of clays with oxides are observed in micrometric volumes. In the vein of the study described in paragraph 2, Bourdelle et al. interested in the compositional variations of sandstones, but using high resolution analyses acquired with transmission electron microscope (TEM) coupled with EDX [START_REF] Bourdelle | Clay minerals as geo-thermometer: A comparative study based on high spatial analyses of illite and chlorite in Gulf Coast sandstones (Texas, U.S.A.)[END_REF]. As for phyllosilicate of West Africa greenstones, flakes of illite and chl contained in (low T diagenetic conditions) sandstones from the Gulf Coast in Texas exhibit compositional variations but for spatial range spanning a couple of hundreds of nanometres only. Crystals present rims around relic cores overgrowing during diagenetic processes. From these fine scale analyses, it is then possible to apply newly developed thermobarometers involving clays [START_REF] Bourdelle | Clay minerals as geo-thermometer: A comparative study based on high spatial analyses of illite and chlorite in Gulf Coast sandstones (Texas, U.S.A.)[END_REF][START_REF] Dubacq | Dehydration of dioctahedral aluminous phyllosilicates: thermodynamic modelling and implications for thermobarometric estimates[END_REF][START_REF] Vidal | Thermodynamic modelling of clay dehydration, stability and compositional evolution with temperature, pressure and H2O activity[END_REF]] and low T chl [START_REF] Bourdelle | A new chlorite geothermometer for diagenetic to low-grade metamorphic conditions[END_REF][START_REF] Inoue | Application of chemical geothermometry to low-temperature trioctahedral chlorites[END_REF] to relate measured compositions to P-T conditions.

X-ray nanoprobes are still not able to compete with the sub-nanometric resolution of TEM instruments. However, obtaining reliable quantitative chemical analyses of phyllosilicate with TEM-EDX implies to reduce the power density of the beam by defocusing electrons from1 to 50 nm [START_REF] Bourdelle | Clay minerals as geo-thermometer: A comparative study based on high spatial analyses of illite and chlorite in Gulf Coast sandstones (Texas, U.S.A.)[END_REF]. In this case, the expected 30 nm large X-ray beam of the SRX nanoprobe surpasses the resolution provided by TEM. More important, the acquisition time needed to get a decent signal with TEM-EDX is in the minute range. It completely annihilates imaging possibilities while on the SRX nanoprobe, dwell times be maintained in the millisecond range to acquire high resolution large images of trace elements concentration. Also, the SRX nanoprobe will have the unique opportunity to perform XANES spectroscopy at the nanoscale with achromatic and high efficiency KB optics, offering the possibility to assess oxidation state of elements or to identify mineralogical phases with the XANES spectra "finger print" approach.

To conclude, coupling of nanoscale analyses with suitable thermobarometers offers new perspectives. In the case of metamorphic rocks, this approach reveals the end of their retrograde P-T paths (<250 o C), i.e. the final steps of exhumation. For industrial applications, a more accurate modeling of sedimentary basins with these mineralogical tools can substantially enhance prospection efficiency of petroleum, uranium or other precious ore deposits.

Radiation damage considerations

Radiation damage on organic materials has been intensively studied since such compounds are easily altered by intense X-ray beams. However, effects of X-rays on hard condense matter can be observed as well, especially when submicron beams with high power density are used. Regarding SRX, the microprobe and the nanoprobe will subject samples to very high power density of about 100 and 1000 kW/mm 2 (corresponding to 1.92 mW in the nanobeam) at 12 keV. The use of such high fluence X-ray beams will necessitate extreme caution when analyzing materials to avoid any misinterpretation derived from analytical artifacts. One can cite as an example the case of S 4+ species observed in silicate glasses. S 4+ were first documented in natural melt inclusions in olivine of arcrelated magmas [START_REF] Métrich | Presence of sulfite (SIV) in arc magmas: Implications for volcanic sulfur emissions[END_REF][START_REF] Bonnin-Mosbah | Micro X-ray absorption near edge structure at the sulfur and iron K-edges in natural silicate glasses[END_REF] before being identified as an instrumental artifact caused by irradiation with intense focused X-ray beams [START_REF] Wilke | The origin of S4+ detected in silicate glasses by XANES[END_REF].

The main interaction process between X-ray beams and matter is photo-ionization yielding photoelectrons with energies lower or equal to the incident beam energy, followed by inelastic (Compton) and elastic (Rayleigh) scattering. The predominant relaxation process following the ionization is through Auger electron emission. In silicates, the travel range of electrons generated by X-ray beam below 20 keV is of the order of 1 to 2 µm. Therefore, except from a small fraction reemitted by fluorescence or s c a t t e r e d , m o s t o f t h e a b s o r b e d e n e r g y r e m a i n s i n t h e sample [START_REF] Simionovici | High Fluence Synchrotron Radiation Microprobe Effects on Stardust Interstellar Dust Candidates[END_REF]. Radiation damage results in oxidation state change of elements as well as mass or crystallinity loss. These effects required mechanisms for converting energy acquired by atomic electrons to kinetic energy [START_REF] Egerton | Radiation damage in the TEM and SEM[END_REF]. In detail, these complex mechanisms are not always well understood and vary according to the targeted materials, the thickness of the sample, the environmental conditions, and the power density of the beam. For instance, Alkali halides are among the most radiation sensitive inorganic material whereas oxides or transition metal oxides can sustain a much higher dose before being altered by electrostatic charging [START_REF] Egerton | Radiation damage in the TEM and SEM[END_REF]. In glass silicate, the use of a sub-microbeam focused with a zone plate induces photo-reduction of sulfur with the decrease S 6+ in favor to S 4+ . When submitted to flux two orders of magnitude higher (use of KB as focusing optics), the same sample exhibits this time photooxidation. Fine structure variations in a series of XANES spectra accumulated at the same sample location indicates that the S oxidation state change is coupled with reorganization of the S local structural environment [START_REF] Wilke | The origin of S4+ detected in silicate glasses by XANES[END_REF].

Simionovici et al. [START_REF] Simionovici | High Fluence Synchrotron Radiation Microprobe Effects on Stardust Interstellar Dust Candidates[END_REF] discussed radiation damage observed in silicates of the Stardust return samples mission. 2 µm large Mg-and Al-rich silicate grains trapped in aerogel were analyzed at the ESRF on ID22NI with a 150 nm large pink beam with a flux of 3×10 10 ph/s. The dose deposited with 200 ms dwell time per pixel did not damage the samples, but a comparison of subsequent XRF images of the same area acquired 8 s dwell time showed smearing of the grains along the fast scan direction and mass loss involving Mn and K. The identified damage mechanism is electrostatic charging subsequent to photoelectron and Auger electron emissions, while ionic displacement and heating processes are negligible for the analytical conditions. The power density of the SRX nanoprobe is however about 350 times higher than the one of ID22NI. It means that the dose responsible of the silicates grains radiolysis would be reached at SRX with 25 ms dwell time. In addition, to validate the assumption that heating has still negligible effects on such materials with 1 MW/mm 2 , FEA are currently ongoing to establish how much the temperature would increase at the sample, either in air or in vacuum with cryogenic conditions.

After these considerations, it is clear that SRX needs a strategy to manage radiation damage even for inorganic materials. First of all, particular care must be brought to the most fragile materials, like the ones composed of alkaline elements. Hydrated materials are also very sensitive. Photoelectrons hydrolyze water making free radicals that will as a second effect produce oxidative attack. Clays and phyllosilicates comprising both alkali and water in the interlayer would be particularly subject to radiation damage. Some procedure or special sample preparation can help to circumvent this problem. For instance, in paragraph 3 is discussed the interest of working on FIB sections to minimize the spatial resolution loss due to X-ray depth penetration while decreasing the throughput on the detectors. Using sub-micron thick thin sections would also minimize the amount of absorbed Auger electrons and therefore of radiation damage. Also, when working in air, intense X-ray beams break some O 2 molecules bonds. The free O atoms recombined then with O 2 to form ozone [START_REF] Weilandics | Ozone production due to synchrotron radiation[END_REF]. Placing the sample in N or He atmosphere prevents the production of ozone that is a strong oxidant able to corrode sample surfaces. One general approach that SRX could adopt to deal with radiation damage could be to shorten dwell times to sub-ms levels, taking benefit of the very fast fluorescence detectors of SRX. Several frames of the same area could be acquired with 0.2 ms dwell time. This may allow enough time for charge migration and a lessening of the charge trapped gradients that drive some element loss effects (e.g. alkalis). XANES spectroscopy is a very valuable diagnostic tool for radiation damage assessment. With the help of filters, low flux XANES spectra can be measured before and after image or stationary acquisitions to track p o t e n t i a l o x i d a t i o n s t a t e ( e . g . t r a n s i t i o n m e t a l i n o x i d e s ) o r crystallinity changes identifiable by fine spectral modifications. In the same way, fast images with moderate flux could be performed in a first time. Comparison of peak ratio between images acquired with low and high power density would help identifying potential mass loss.

Because the degree of radiation damage experienced by materials is composition dependent, an early study of standard samples would benefit to future experiments performed at SRX. In a certain extent, those results could also be extended to Free Electron Laser instruments since interactions between hard condense matter and high fluence X-ray beam are still poorly known.

Conclusion

The use of elemental chemical imaging derived from XRF microprobes were an important milestone for the understanding of mineralogical and geodynamic processes, as is illustrated in the study of greenstones from WAC. The steady improvement of these instruments realized by the current construction or upgrade of ultra-bright diffraction limited synchrotron sources like NSLS-II opens new horizons for high speed chemical imaging of trace elements with large fields of view. Examples of acquisitions performed with the Maia 384 on a metamorphic rock underscore the achievable performances with current beamlines and EDX detectors. Simulations also show that further detector development is necessary to fully benefit from the potential of a beamline like SRX. In addition, the recent improvement in optics fabrication enables construction of efficient nanoprobes that are of interest for applications concerning low T metamorphism. However, the use of the high fluence beam of SRX necessitates strategy to control and diagnose radiation damage even on hard condense matter.

Figure 1 . 1 :

 11 Figure 1. Group 1: Chemical evolution of chl and phg during deformation in sample Fa-33. (a) Photomicrograph of sample Fa-33. (b) Distribution of K-rich phg around a crystallization tail. (c) Distribution of Si-rich chl around haematite grains. Color bars correspond to the number of K & Si cations in phg (b) and chl (c). Group 2: P-T calculations based on chl-phg analyses. (d) P-T path vs K-content (left) and Si-content (right) in phg & chl. The P-T path was calculated from conventional spot analysis. (e) P-T maps derived from compositional images. Each chl and phg group is characterized by a specific range of composition, P & T determined in (d).The Si-poor chl and K-depleted phg corresponding to the high P group A are mostly observed in the early-formed microstructures (modified afterGanne et al., 2011)[START_REF] Ganne | Modern-style plate subduction preserved in the Palaeoproterozoic West African craton[END_REF].

Figure 2 .

 2 Figure 2. Experimental setup at the P06 beamline at Petra III. The Maia (384 version B) is in introduced between the KB focusing optics and the sample.

Figure 3 .

 3 Figure 3. Quantitative images of Rb, Zn and Y concentrations acquired together with the Cr image showed in fig.4.

Figure 4 .

 4 Figure 4. Quantitative image of Cr concentration (ppm) in a qtz-chl-phgcld-gt-accessory minerals bearing metamorphic rock. This image has been acquired with the Maia 384 elements detector on the P06 beamline at Petra III. Some of the minerals present in the rock are labelled in fig.3. The disk

Figure 5 .

 5 Figure 5.Fluorescence spectra simulations derived from the XMI-MSIM software[START_REF] Beck | The redox state of iron in the matrix of CI, CM and metamorphosed CM chondrites by XANES spectroscopy[END_REF]

Acknowledgements

This work was financially supported by the NSLS-II project, itself funded by the US department of Energy, Office of Science and Office of Basic Energy Sciences. We are grateful to Ulrike Boesenberg and Gerd Wellenreuther from the P06 beamline team at Petra III, who helped setting up the experiment aiming to test the new Maia 384 detector. We also want to thank Robin Kirkham & Pete Siddons for their support and advices concerning the Maia. At last, thanks to Tom Schoonjans for his support in configuring the XMI-MSIM software and the SRX team endeavoring to build an outstanding instrument.