Mohammad Noormohammadpour

Cauligi S Raghavendra

Sriram Rao
email: sriramra@microsoft.com

DCRoute: Speeding up Inter-Datacenter Traffic Allocation while Guaranteeing Deadlines

Keywords: Datacenter, Routing, Traffic Allocation, Traffic Scheduling, Deadlines, Wide Area Networks

Datacenters provide the infrastructure for cloud computing services used by millions of users everyday. Many such services are distributed over multiple datacenters at geographically distant locations possibly in different continents. These datacenters are then connected through high speed WAN links over private or public networks. To perform data backups or data synchronization operations, many transfers take place over these networks that have to be completed before a deadline in order to provide necessary service guarantees to end users. Upon arrival of a transfer request, we would like the system to be able to decide whether such a request can be guaranteed successful delivery. If yes, it should provide us with transmission schedule in the shortest time possible. In addition, we would like to avoid packet reordering at the destination as it affects TCP performance. Previous work in this area either cannot guarantee that admitted transfers actually finish before the specified deadlines or use techniques that can result in packet reordering. In this paper, we propose DCRoute, a fast and efficient routing and traffic allocation technique that guarantees transfer completion before deadlines for admitted requests. It assigns each transfer a single path to avoid packet reordering. Through simulations, we show that DCRoute is at least 200 times faster than other traffic allocation techniques based on linear programming (LP) while admitting almost the same amount of traffic to the system.

I. INTRODUCTION

Cloud Computing allows customers to build online applications that can cost effectively scale as necessary [START_REF] Armbrust | A view of cloud computing[END_REF]. It provides a massive pool of resources for online applications that can be flexibly obtained when needed and then returned back to the pool at a later time. Such resources can be provided to different applications on top of the infrastructure built and maintained by a cloud company. Examples of hosted online applications include video streaming, data storage and sharing, and big data processing. Most companies that provide cloud computing services own multiple datacenters placed in different cities and countries in order to improve availability, reduce end-to-end delays for end users, and provide customized regional services. At the time of writing this paper, Amazon has more than two dozen availability zones each consisting of one or more discrete datacenters [START_REF]Amazon web services (aws) -cloud computing services[END_REF], Microsoft has 22 regions with plans to build 8 more [START_REF]Microsoft azure: Cloud computing platform & services[END_REF], and Google relies on more than a dozen datacenters [START_REF]Compute engine -iaas -google cloud platform[END_REF].

Many applications hosted on these datacenters need to transfer data to their peers in other datacenters for the purpose of data replication and synchronization [START_REF] Kiran | Datacenter synchronization[END_REF], [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]. The aim is to improve fault-tolerance and user quality of service by making multiple copies of data and getting data closer to end users. Most of these transfers have to be completed before a deadline in order to meet customer service level agreements (SLAs) and they can take hours to complete [START_REF] Kandula | Calendaring for wide area networks[END_REF]. For example, search engines may have to exchange data among datacenters in order to synchronize their search databases and storage applications may need to back up user data over certain periods.

As mentioned in [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], inter-datacenter traffic can be categorized into three groups: interactive traffic that has to be transmitted as soon as possible since it is in the critical path of user experience, elastic traffic that requires timely delivery which can be modeled in the form of a deadline, and background traffic which is bandwidth hungry and has less priority than the other two categories of traffic. In this paper, we focus on elastic traffic with user specified deadlines.

Previous work in the context of inter-datacenter traffic scheduling either fails to consider the negative effects of packet reordering caused by multiplexing packets over different paths (AMOEBA [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]) or cannot guarantee that admitted requests will actually complete transmission before the deadlines specified by customers (B4 [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], SWAN [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], TEMPUS [START_REF] Kandula | Calendaring for wide area networks[END_REF]). In addition, AMOEBA and TEMPUS which are the state-of-the-art techniques in this area, model the allocation problem as large linear programs (LP), with possibly hundreds of thousands of variables, solving which incurs large memory and CPU overhead and can take a long time.

Avoiding packet reordering allows data to be instantly delivered to applications upon arrival of packets. In addition, inter-datacenter networks have characteristics similar to WAN networks (including asymmetric link delays and large delays for links that connect distant locations) for which multiplexing packets over different paths has been shown to considerably degrade TCP performance [START_REF] Laor | The effect of packet reordering in a backbone link on application throughput[END_REF]. Putting out of order packets and segments back in order can be expensive in terms of memory and CPU usage, especially when transmitting at high rates.

As explained in [START_REF] Raiciu | How hard can it be? designing and implementing a deployable multipath tcp[END_REF], TCP needs to buffer as much as the bandwidth-delay product (BDP ) of the network in lossless and 2 × BDP in lossy networks to put out of order packets back in order. For high speed inter-datacenter networks with tens of gigabits of speed and tens of milliseconds of latency considerable amount of buffering may be needed. In [START_REF] Geng | Juggler: a practical reordering resilient network stack for datacenters[END_REF], authors show how Vanilla kernel uses 50% more CPU in presence of severe packet reordering and present Juggler, a reordering resilient network stack designed for low latency datacenter networks which can reduce the extra CPU utilization to 10%: still a considerable amount. For higher latency networks, due to large variation of RTT over multiple paths, reordering may further increase CPU utilization.

In [START_REF] Noormohammadpour | Rcd: Rapid close to deadline scheduling for datacenter networks[END_REF], we proposed RCD, a technique that speeds up the traffic allocation problem by scheduling transfers close to their deadlines. Through simulations, we showed that RCD speeds up the allocation process by allowing new transfers to be scheduled only considering the residual bandwidth which would result in creation of much smaller LP models. However, we did not discuss the reordering problem and only evaluated our technique for a single link scenario.

In this paper, we propose DCRoute, a fast and efficient routing algorithm which eliminates the need for LP modeling and:

• Guarantees that admitted transfers complete prior to specified deadlines.

• Schedules all packets of each transfer over the same path to avoid packet reordering.

• Works much faster than other techniques while admitting almost equal traffic to the system.

The input to DCRoute is the network topology as well as a list of transfers including their volumes and deadlines which are submitted to DCRoute in the order of arrival. DCRoute assigns a single path to every transfer and generates a transmission schedule which specifies the rate at which every transfer should be sent over their assigned path during current timeslot. In this paper, we verify the performance of DCRoute through long running simulations. In practice, label switching (such as VLAN tagging) can be used to enforce paths and ratelimiting at the end hosts can be used to enforce transmission rates as in SWAN [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF].

II. PROBLEM DESCRIPTION

Figure 1 shows our problem setup which is comprised of multiple datacenters in different locations managed by a central controller. The datacenters are connected using high speed WAN links. Applications hosted on these datacenters will make transfers that may take hours to complete and have to be finished before specified deadlines. Due to large transfer time, the time it takes for the source datacenter to request a path from the central controller and the time it takes to setup such a path is considered negligible. However, the time it takes for the scheduling algorithm to prepare a traffic schedule depends on the scheduling algorithm which we aim at minimizing. In addition, in order to avoid packet reordering, we would prefer to send all packets of a transfer on a single path.

As in [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF], [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], we assume the timeline is divided into properly sized timeslots over which the transmission rate is constant. Using a slotted timeline allows for schedules with variable transmission rates over time. In our model, an inter-datacenter request R is represented with four parameters src(R), dst(R), vol(R) and dl(R) which stand for source, destination, volume of data to be transferred and the deadline prior to which the transfer has to be completed.

Similar to previous work [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF], we assume arriving requests are put into a queue and processed in the order of arrival and that there is no preemption: once a request is allocated, it cannot be unallocated from the system. At each moment, we have two parameters t now and t end which represent current timeslot and the latest deadline among all active requests, respectively. A request arriving sometime in timeslot t can be allocated starting timeslot t + 1 since the schedule and transmission rate for current timeslot is already decided upon and broadcast into all datacenters. Also, at any moment t, t now is the timeslot that includes t (current timeslot), and t now + 1 is the next available timeslot for allocation (next timeslot).

Upon arrival of a request, a central controller decides whether it is possible to allocate it considering some criteria that includes the total available bandwidth over future timeslots. If there is not enough room to allocate a request, the request is rejected and can be submitted to the system again later with a new deadline.

A request is considered active if it is accepted into the system and its deadline has not passed yet. Some active requests may take many timeslots to complete transmission. The total unsatisfied demand of an active request is called the residual demand of that request.

Allocation Problem: Given active requests R 1 through R n with residual demands

D 1 to D n (0 ≤ D i , 1 ≤ i ≤ n), is it possible to allocate a new request R n+1 ? If yes, what is a possible schedule?
An important characteristic of network traffic is that the size of smallest traffic unit (which is a packet) is significantly smaller than link capacities (which are in the range of gigabits nowadays). This allows us to solve the allocation problem by forming a linear program (LP) considering capacity constraints of the network edges as well as demand constraints of requests. The answer will give us a possible allocation if the constructed LP is feasible. Although this solution maybe straightforward, considering the number of active requests, number of links in network graph, and how far we are planning ahead into the future (t end ), the resulting LP could be large and may take a long time to solve. One of the ways to speed up this process is to limit the number of possible paths between every pair of nodes [START_REF] Kandula | Calendaring for wide area networks[END_REF], for example, using k-shortest paths [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]. While solving the LP, another speedup method is to limit the number of considered active requests based on some criterion [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF] such as having a common link with the new request. It is also possible to use customized iterative methods to solve the resulting LP models faster based on the solutions of previous LP models in a way similar to the water filling process [START_REF] Kandula | Calendaring for wide area networks[END_REF].

Our proposition is to avoid building an LP model in the first place by trying to allocate new requests only knowing the residual bandwidth on the edges for different timeslots.

III. DCROUTE DCRoute relies on the following three techniques:

• Requests are initially allocated as late as possible (ALAP) [START_REF] Li | An iterative scheduling technique for resourceconstrained project scheduling[END_REF] • Utilization is maximized by pulling traffic from closest future timeslots into the upcoming timeslot

• A variant of BFS search is used for path selection Figure 2 provides an example of the ALAP allocation technique. As can be seen, when the first transfer is received the timeline is empty and therefore it is allocated adjacent to its deadline. The second transfer is allocated as close as possible to its deadline. The benefit of this type of scheduling is that requests do not use resources until it is absolutely necessary. This means resources will be available to other requests that currently demand them. Now when the third transfer is submitted, the resources are free and it just grabs as much bandwidth as needed. If we had allocated the first two requests closer to current time we may have had to either reject the third transfer or move the first two transfers ahead freeing resources for the third transfer.

Assume requests R 1 through R n are current active requests and we would like to allocate R n+1 . For every request

R i , 1 ≤ i ≤ n, we either have dl(R i ) ≤ dl(R n+1 ) or dl(R i ) > dl(R n+1 ).
In the former case, since there is no preemption, there is no way to increase the chance of new request being accepted by shifting the traffic allocation of request i away as it has to be completed before dl(R n+1 ). For the latter case, since we allocated all requests ALAP, the traffic is already shifted out of R n+1 's window as much as possible. As a result, it is possible to decide on admission of new request by just looking at the residual bandwidth on the links. For a single link, since all requests use a single shared resource (link capacity) this technique allows us to optimally decide whether a new request can be allocated. For a network, each request is routed on multiple links and there are many ways to schedule requests ALAP. If some link is used by multiple requests that are routed on different edges, how traffic is allocated on the common link can affect multiple other links which will affect the requests that use those links later on. Despite this uncertainty, we will show that using this feature, we can greatly speed up the allocation process.

Using ALAP alone can result in poor utilization as we always push traffic towards future timeslots and leave the current timeslot underutilized. In order to maximize utilization, upon beginning of a new timeslot, the scheduler looks at future timeslots and pulls as much traffic as possible from the closest timeslots in the future to the upcoming timeslot. Pulling from closest timeslot allows the ALAP characteristic of allocation to hold true afterwards: all residual demands will still be allocated as close to their deadlines as possible.

While pulling traffic from future timeslots, a request can span over multiple links and if there is some traffic fully occupying the next timeslot on one of those links, it is impossible to pull traffic back for that request from the future timeslots to the next timeslot. In such cases, we may need to pull traffic from requests that may not be the closest to current timeslot. This can result in an allocation in which some requests are not scheduled ALAP because they can be pushed further into the future. To address this problem, after pulling traffic from future timeslots, we sweep requests allocated on future timeslots and push them forward as much as possible. Figure 3 shows an example of this process. There are three different requests all of which having the same deadline. It is not possible to pull back the green request as the link E1 is already occupied. Therefore, we have to pull the orange request (PullBack phase). Afterwards, the allocation is not ALAP anymore, so we push the green request towards its deadline (PushForward phase). The final allocation is ALAP and the utilization of upcoming timeslot is maximum.

A. DCRoute Algorithms

We assume a graph G(V, E) connecting datacenters with M bidirectional links. For simplicity, we also assume all links/edges have equal capacity of 1.0. Every edge e has a boolean use property which identifies whether that edge can be used in the course of routing. Also each node v has 4 parameters v, r, rv and rs. If p is the path on BFS tree from src(R) ending at v, these parameters represent whether v has been visited before, the number of hops to v from source, the load of bottleneck link, and the sum of loads on all edges from source to v, respectively. Moreover, we have variables S t,m that represent the total sum of traffic over link m from time t now + 1 to t. Every time a new request is submitted to the system, t end is updated so that it covers all active requests. Finally, we define the active window as the set of all timeslots over all edges from time t now +1 to t end . Our algorithms only operate on the active window.

Allocate(R): Algorithm 1 is executed upon arrival of a new request R and performs multiple BFS searches. In every search, we calculate multiple costs, remove edges with highest costs, and compare the result with previous steps. While examining different paths, our heuristic finds the path with most preferred characteristics: the total sum of traffic before dl(R) over the chosen path will be minimal compared to other paths when R gets allocated on that path.

In each round, the path assignment algorithm starts by choosing the path with the least number of hops and calculates the total cost of sending the request on that path. Also, the bottleneck link on that path is identified. If the total cost is less than the best path found in previous steps, this path replaces the best path. Next, all edges with an equal or higher cost than the bottleneck edge are removed from the network. This process continues until there is no path from source to destination. Now, if it is possible to allocate the request on the selected path, we apply the allocation, otherwise, the request is rejected since admitting it might result in many more future requests to be rejected.

PullBack(): Algorithm 2 looks at the timeslots starting t now + 2 to t end and pulls back traffic to t now + 1 (next timeslot to be scheduled). When pulling back traffic, all edges on a request's path have to be checked for unused capacity and updated together as we pull traffic back.

PushForward(): After pulling some traffic back, it may be possible for some other traffic to be pushed ahead even further. Algorithm 3 scans all future timeslots starting t now + 2 and makes sure that all demands are allocated ALAP. If not, it moves as much traffic as possible to the future timeslots until all residual demands are ALAP.

23:

if (α > β) or ((α == β) and (r b .rv > rn.rv)) then 24:

j ← i + 1, r b ← rn, f lag ← T rue

25:

while i ≥ j do 26: for t = tnow + 1 to t = t end do

i ← i -1, SE[i].use ← T

3:

for e ∈ E do

4:

reqs ← all requests allocated on e at t

5:

for R ∈ reqs do

6:

vol ← how much of R allocated on e at t

7:

path ← path assigned to R upon allocation

8:

for e ∈ path do

9:

vol ← min(vol, 1 -S tnow +1,e ) 10:

if vol > 0 then

11:

for e ∈ path do

12:

move vol of R from edge e at t

13:

to edge e at tnow + 1

14:

for t = tnow + 1 to t = t do 15:

S t ,e ← S t ,e + vol Algorithm 3

1: procedure PUSHFORWARD() 2:

for t = tnow + 2 to t = t end do

3:

for e ∈ E do

4:

reqs ← all requests allocated on e at t

5:

for R ∈ reqs do

6:

vol ← how much of R allocated on e at t

7:

path ← path assigned to R upon allocation 8:

for t2 = R.dl to t2 = t + 1 step -1 do

9:

f ree ← min(vol, free space on e at t2)

10:

for e ∈ path do

11:

f ree ← min(f ree, free space on e at t2)

12:

if f ree > 0 then

13:

for e ∈ path do 14:

remove f ree of R from edge e at t

15:

add f ree of R to edge e at t2

16:

for t = t to t = t2 do 17:

S t ,e ← S t ,e -f ree Walk(): Algorithm 4 is executed when the allocation for next timeslot is final. This algorithm tells each datacenter of the decided allocation and adjusts request demands accordingly by deducting what is scheduled to be sent from the total demand.

B. DCRoute and Multi-Path Routing

As mentioned earlier, to avoid packet reordering, DCRoute maps every transfer to exactly one path and if there is no single path that can allocate a transfer, it will be rejected. Although this sounds too restrictive, we show in the next section that Algorithm 4

1: procedure WALK() 2:

Broadcast the schedule for tnow + 1 to all datacenters

3:

for e ∈ E do 4:

D ← St now +1

5:

for t = tnow + 1 to t = t end do

6:

St,e ← St,e -D

7:

tnow ← tnow + 1 8:

t end ← max(t end , tnow + 1)
limiting every transfer to a single path results in 2% less utilization in the worst case.

To use the aggregate bandwidth on multiple paths, one can use Multi-Path TCP (MPTCP) [START_REF] Ford | Tcp extensions for multipath operation with multiple addresses[END_REF] which allows sending traffic from multiple interfaces of a single host. MPTCP is based on multiple sub-flows that behave similar to single TCP flows. While using MPTCP, the overall CPU and memory footprint can increase significantly compared to TCP which is the cost paid for increased bandwidth. However, by carefully choosing which parts of the data goes over what path, it is possible to improve the CPU footprint [START_REF] Raiciu | How hard can it be? designing and implementing a deployable multipath tcp[END_REF].

To increase network utilization, it is possible to use MPTCP and apply DCRoute to all sub-flows created. To do that, one can divide the total demand of a request over multiple subflows and assign the same deadline as the deadline of the original request to all of them. If all sub-flows can be allocated with DCRoute, then the request is accepted.

Deciding on the number of sub-flows and the portion of traffic that goes over each one of them is not a trivial problem. It may be possible to extend DCRoute by ranking the paths found in Allocate procedure and choosing a subset of the best paths. Further discussion of this subject is out of the scope of this paper.

IV. SIMULATION RESULTS

In this section, we perform simulations to evaluate the performance of DCRoute. We generate synthetic traffic requests with Poisson arrival and input the traffic to both DCRoute and a few other techniques that can be used for traffic allocation. Two metrics are being measured and compared: allocation time and portion of rejected traffic both of which are desired to be small.

Simulation Parameters: We used the same traffic distributions as described in [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]. Requests arrive with Poisson distribution of rate λ. Also, total demand of each request R is distributed exponentially with mean 1 8 proportional to the maximum transmission volume possible prior to dl(R). In addition, the length of requests is exponentially distributed for which we assumed a mean of 10 timeslots. We performed the simulations over 500 timeslots.

All simulations were performed on a machine with an Intel Core i7-6700T CPU and 24 GBs of memory and the algorithms are coded in Java. To solve linear programs faster, we used Gurobi Optimizer [START_REF]Gurobi Optimization[END_REF] with a free academic license. Gurobi Optimizer can speedup the LP solving process using several techniques including parallel processing. All simulations presented here are performed 3 times and the average is reported. We compare DCRoute with the following allocation schemes for all of which we used the same objective function as [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]:

Global LP: This technique is the most general and flexible way of allocation which routes traffic over all possible edges. All active requests are considered for all timeslots on all edges creating a potentially large linear program. The solution here gives us a lower bound on traffic rejection rate.

K-Shortest Paths: Same as Global LP, however, only the K-Shortest Paths between each pair of nodes are considered in routing. The traffic is allocated using a linear program over such paths. We simulated four cases of K ∈ {1, 3, 5, 7}. It is obvious that as K increases, the overall rejection rate will decrease as we have higher flexibility for choosing paths and multiplexing traffic.

Pseudo-Integer Programming (PIP): In terms of traffic rejection rate, comparing DCRoute with the previous two techniques is not fair as they allow multiplexing packets on multiple paths. The aim of this technique is to find a lower bound on traffic rejection rate when packets of each request are sent over a single path. To do so, the general way is to create an integer program involving a list of possible paths (maybe all paths) for the new request and fixed paths for requests already allocated. The resulting model would be a non-linear integer program which cannot be solved using standard optimization libraries available. We instead created a number of linear programs each assigning one of the possible K-Shortest Paths for the newly arriving request. We then compare the objective values manually and choose the best possible path. In our implementation, we chose K = 20. This K seems to be more than necessary as we saw negligible improvement in traffic rejection rate even when increasing K from 5 to 7. Using PIP, the path over which a request is transferred is decided upon admission and does not change afterwards. We implemented two versions of this scheme:

• Pure Minimum Cost (PMC): We choose the path that results in smallest objective value.

• Shortest Path, Minimum Cost (SPMC): Amongst all shortest paths that result in a feasible solution and have the least number of hops, we choose the one with smallest objective value.

A. Google's GScale Network

GScale network [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF] comprised of 12 nodes and 19 links (at 2013, they have 15 datacenters as of 2016 [START_REF]Compute engine -iaas -google cloud platform[END_REF]) is a private network that connects Google data centers. We used the same topology to evaluate DCRoute as well as other allocation schemes. Figure 4 shows the rejection rate of different techniques for different arrival rates from low load (λ = 1) to high load (λ = 15). We have included the schemes that potentially multiplex traffic over multiple paths just to provide a lower bound. Comparing with PMC and SPMC schemes over all arrival rates, DCRoute performs < 2% worse than the one with minimum rejection rate. Also, compared to all schemes, DCRoute rejects at most 4% more traffic.

Figure 4 shows the relative time to process a request using different schemes. This time is calculated dividing the total time to allocate/adjust all requests over all timeslots by the total number of requests. DCRoute is about 3 orders of magnitude faster than either PMC or SPMC. It should be noted that the rate at which time complexity grows drops as we move towards higher arrival rates since there is less capacity available for new requests and many arriving requests get rejected by failing simple capacity constraint checks.

B. Variable Network Size

We simulated different methods against four networks from 5 to 20 nodes:

(N, M ) ∈ {(5, 7), [START_REF] Laor | The effect of packet reordering in a backbone link on application throughput[END_REF]17), [START_REF] Ford | Tcp extensions for multipath operation with multiple addresses[END_REF]27), (20, 37)} In our topology, each node was connected to 3 or 4 other nodes at most 2 hops away. The arrival rate was kept constant at λ = 6.0 for all cases.

Figure 5 shows the rejection rate of different schemes for different network sizes. As network size increases, since λ is kept constant, the total cpacity of network increases compared to the total demand of requests. As a result, for a scheme that multiplexes request traffic over different paths, we expect to see decrease in rejection rate. For the K-Shortest Paths case with K ∈ {1, 3} we see increase in rejection rate which we think is because these schemes cannot multiplex packets that much. Increasing the network size for these cases can cause more requests to have common links as the network is sparsely connected and create more bottlenecks resulting in a higher rejection rate.

PMC has a high rejection rate for small networks since choosing the minimum cost path might result in selecting longer (more hops) paths that create larger number of bottlenecks due to collision with other requests. Increasing network size, there are more paths to choose from and that results in less bottlenecks and therefore less rejection rate. In contrast, SPMC enforces the selection of paths with smaller number of hops resulting in lower rejection rates for small networks (due to request paths colliding less) and more rejections as network grows due to less diversity of chosen paths.

Compared to these two approaches, DCRoute balances the choice between smaller and longer paths. The assigned path has the least sum of load on the entire path and the least bottleneck load among all such paths. Paths with heavily loaded links and unnecessarily larger number of hops are avoided. As a result, rejection rate compared to min(PMC, SPMC) is relatively small (< 3%) for all network sizes. Also, as Figure 5 shows, similar to previous simulation, DCRoute is almost three orders of magnitude faster than PIP schemes and more than 200 times faster than all considered schemes.

C. Effect of Timeslot Length

As mentioned earlier, the timeline is divided into timeslots. In this paper, we do not discuss the exact duration of timeslots, however we would like to see how smaller timeslots affect the amount of rejected traffic as well as the speed of different methods. The transmission rate of transfers only changes when moving from one timeslot to the next. Having timeslots that last longer than most requests would essentially result in a fixed transmission rate for such transfers. This causes less critical transfers (with a later deadline) to have to share the bandwidth with more critical transfers (with a closer deadline), reducing the flexibility of the system and increasing the number of rejected transfers. Having very short timeslots on the other hand can result in unnecessary scheduling overhead and practical complications. For example, rate-limiters at the end hosts may not be able to converge to specified rate if they have to change rate too often. Therefore, a proper timeslot length could be a few times smaller than most requests but large enough to avoid unnecessary processing overhead.

As shown in Figure 6, we divide every timeslot into 2 to 5 smaller timeslots. We again use GScale topology and consider (λ = 6). We only considered the K-Shortest Paths techniques with K ∈ {3, 7} since during previous tests they provided the best utilization at the least processing cost. It appears that if the timeslots are short enough, making them shorter does not improve the load accepted into the system: DCRoute rejects 2% more traffic compared to K-Shortest Paths schemes for all timeslot resolutions. Although DCRoute is always more than 2 orders of magnitude faster than K-Shortest Paths schemes, it does have a slightly higher growth rate in processing time as the timeslot resolution increases.

D. Discussion

We do not directly compare our scheme with any of the previous schemes, such as AMOEBA or TEMPUS, since we pursue the following two objectives together which is not the case for previous work:

• Avoiding any packet reordering

• Guaranteeing deadlines for admitted transfers However, since AMOEBA is the most similar to DCRoute, we would like to provide an approximate comparison. We argue that AMOEBA is essentially an extension to the K-Shortest Paths LP technique (K = 10) introduced here. By intelligently avoiding LP modeling for some special cases, AMOEBA provides a speedup of 30 times compared to 10-Shortest Paths LP for (λ = 8) [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]. For the same arrival rate and request volume/deadline distribution, DCRoute performs more than 1000 times faster than 10-Shortest Paths LP technique. Also in a previous work called RCD [START_REF] Noormohammadpour | Rcd: Rapid close to deadline scheduling for datacenter networks[END_REF], we showed how the close to deadline scheduling technique can speed up the traffic allocation by up to 15 times compared to AMOEBA while resulting in same utilization over a single link. DCRoute is based on RCD coupled with a path selection heuristic that eliminates the need for LP modeling.

Network Size (# Nodes) 6. Total % of rejected traffic and relative request processing time as timeslot resolution increases

V. CONCLUSIONS AND FUTURE WORK

In this paper, we proposed DCRoute, a routing algorithm for Inter-Datacenter networks which guarantees that transfers complete before their deadlines and to avoid reordering, schedules all packets of a request on the same path. Inspired by the fact that allocating ALAP allows for new requests to be scheduled considering only residual bandwidth, DCRoute performs much faster than schemes based on LP modeling. It is more than 2 orders of magnitude faster than all simulated schemes and 3 orders of magnitude faster than schemes that do not multiplex transfer packets on multiple paths.

We showed that DCRoute admits at most 4% less traffic compared to schemes that multiplex packets on multiple paths (which provide an estimate of lower bound on rejected traffic) and 2% less traffic compared to schemes that schedule all packets of each transfer on the same path.

Finally, we studied the effect of timeslot resolution and found out that making timeslots smaller than necessary does not increase the admitted load and only incurs extra processing costs. In this paper, we evaluated DCRoute with synthetic traffic. Evaluation of DCRoute using real inter-datacenter traffic is suggested as a future work. In addition, studying the effects of link failures and developing methods to properly handle them can be a subject for future work.

  Fig. 1. Problem Setup

Fig. 2 .

 2 Fig. 2. An example of "As Late As Possible" allocation

Algorithm 1 1 : 4 : 6 :

 146 procedure ALLOCATE(R) 2: for t = t end + 1 to R.dl do 3: for e ∈ E do St,e ← St-1,e 5: t end ← max(R.dl, t end ) for e ∈ E do 7: e.use ← T rue 8: for v ∈ V do 9: {v.v, v.r, v.rv, v.rs} ← {F alse, 0, 0, 0} 10: SE ← array of edges sorted by S R.dl,e descending 11: i ← 0, j ← 1, f lag ← T rue, r b ← BFS test(R) 12: while r b .r is not -1 do 13: if (r b .rv > 0) and f lag then 14: f lag ← F alse 15: while S R.dl,SE[i] > r b .rv do 16: SE[i].use ← F alse 17: i ← i + 1 18: SE[i].use ← F alse, i ← i + 1 19: rn ← BFS test(R) 20: if rn.r == -1 then break 21: α ← r b .r × R.vol + r b .rs 22: β ← rn.r × R.vol + rn.rs

Fig. 3 . 2 1:

 32 Fig. 3. An example of improving utilization while keeping the final allocation ALAP

Fig. 5 .

 5 Fig. 5. Total % of rejected traffic and relative request processing time for different network sizes

  Fig. 4. Total % of rejected traffic and relative request processing time for GScale network with 12 nodes and 19 links

		45								10 5
		40
				DCRoute
	% of Rejected Traffic	15 20 25 30 35		K-Shortest Paths (K=5) K-Shortest Paths (K=7) SPMC PMC K-Shortest Paths (K=3) Global LP K-Shortest Paths (K=1)				Relative Time to Process a Request	10 2 10 3 10 4
		10								10 1
		5
		0	2	4	6	8	1 0	1 2	1 4	10 0	2	4	6	8	1 0	1 2	1 4
					Arrival Rate ( )								Arrival Rate ( )

ACKNOWLEDGEMENT

We would like to thank the anonymous reviewers of HiPC whose suggestions and comments helped us improve the quality of this paper.


R Mailler

J Gasperi
email: gasperi@u-pec.fr

G Chebbo

V Rocher

Priority and emerging pollutants in sewage sludge and fate during sludge treatment

Keywords: Anaerobic digestion, thermal drying, centrifugation, emerging pollutants, priority pollutants, sludge

Highlights

 117 pollutants were studied in different treated sludges from Parisian WWTPs  The pollutant pattern is quite similar in the different sludges  During centrifugation, no removal of pollutant is observed  Thermal drying allows a 10 -80% removal of alkylphenols, PAHs and MBT  Pollutants are not, similarly or more removed than dry matter during digestion

Introduction

Wastewater treatment plants (WWTP) produce an important quantity of sludge resulting from total suspended solids (TSS) removal and growth of microorganisms within biological treatments.

Actually, about 1 million tons dry matter (DM) of sludge are produced every year by French WWTPs, while Germany and UK produce respectively 2.2 and 1.8 million tons [START_REF] Kelessidis | Comparative study of the methods used for treatment and final disposal of sewage sludge in European countries[END_REF], for a total of 11 million tons DM of sludge in all Europe (EU-27). The management of these sludges is achieved through three principal pathways: agricultural uses (land farming), incineration and disposal/landfilling [START_REF] Fytili | Utilization of sewage sludge in EU application of old and new methods----A review[END_REF]. In 2008, land farming was the main pathway both in France (> 60%) and in the European Union (> 50%) [START_REF] Kelessidis | Comparative study of the methods used for treatment and final disposal of sewage sludge in European countries[END_REF].

Contamination of WWTP sludges by micropollutants has been reported for several years [START_REF] Clarke | Review of 'emerging' organic contaminants in biosolids and assessment of international research priorities for the agricultural use of biosolids[END_REF][START_REF] Harrison | Organic chemicals in sewage sludges[END_REF][START_REF] Scancar | Total metal concentrations and partitioning of Cd, Cr, Cu, Fe, Ni and Zn in sewage sludge[END_REF]. This results from pollutant sorption during primary and biological treatments because of their hydrophobicity or propensity to be adsorbed on particles (Byrns, 2001). As sludges are mainly land farmed, this contamination is worrying especially considering accumulation of some micropollutants in sludge and their transfer to the environment, like polybromodiphenyl ethers (PBDE) [START_REF] Eljarrat | Effect of sewage sludges contaminated with polybrominated diphenylethers on agricultural soils[END_REF], metals (Chipasa, 2003), organotins [START_REF] Craig | Changes of heavy metal speciation during high-solid anaerobic digestion of sewage sludge[END_REF] or polychlorobiphenyls (PCB) [START_REF] Stevens | PAHs, PCBs, PCNs, Organochlorine Pesticides, Synthetic Musks, and Polychlorinated n-Alkanes in U.K. Sewage Sludge: Survey Results and Implications[END_REF]. To limit contamination of the environment by micropollutants, European and national regulations have been established to progressively forbid sludge disposal and regulate land farming. Such regulations concern principally heavy metals, PAHs and PCBs (Table 1). In particular, the Urban Wastewater Treatment Directive [START_REF] Ec | Directive of the European Parliament and of the Council n°86/278/EEC establishing a framework for the community action in the field of sewage sludge policy[END_REF], amended by (91/271/EEC) [START_REF] Ec | Directive of the European Parliament and of the Council n°91/271/EC establishing a framework for the community action in the field of sewage sludge policy[END_REF], states maximum thresholds and maximum annual flux to land farm for metals. Despite that, data and knowledge are still missing concerning i) the quality of treated sludges and ii) the efficiency of the sludge treatment processes (STP) for micropollutant removal as well as the mechanisms involved. This paper aims at improving and completing knowledge about Parisian sludges contamination by micropollutants and their fate during four different STPs, i.e. anaerobic digestion, centrifugation, thermal drying and sludge cake production.

As no typical sludge treatment layout can be identified, and different configurations exist depending on the capacity of the treatment plant or the quality of treated sludge expected (regulations), the characterization of each process individually seems to be a relevant strategy.

To achieve that, a large number of micropollutants (n=117) were monitored in these STPs. Contents were measured in raw, digested, centrifuged, thermally dried sludges and sludge cake (cooked then press filtered). Micropollutant removals were calculated, to better understand the behaviors of these compounds and to determine the potential of these processes for controlling the micropollutant contamination of sludge.

Material and methods

2.1. Sludge treatment processes (STP) description and sampling procedure Three STPs from three WWTPs in Paris were studied (Figure 1). It should be noted that these WWTPs, run by the Parisian public sanitation service (SIAAP), treat wastewater from the same catchment (downstream Paris conurbation) and the comparison of processes and treated sludges (digested sludge -DS, centrifuged sludge -CS, sludge cake -SC and thermally dried sludge -TS, Figure 1) is then relevant to underline the differences in micropollutants fate.

The Seine Centre plant treats 240 000 m 3 of wastewater per day. Sludge produced is first centrifuged to achieve a volume reduction, resulting in a production of almost 21 000 tons DM of centrifuged sludge per year (SIAAP source). Then, sludge is incinerated producing ash and smoke, which is specifically treated to minimize odors. The Seine Aval plant receives 1 700 000 m 3 of wastewater per day (biggest in Europe) and produces more than 55 000 tons DM of treated sludge per year (SIAAP source). The first STP consists in a mesophilic (37°C) anaerobic digestion to transform an important part of organic matter into biogas and eliminating pathogens and parasites.

Digested sludge is then dewatered by thickening, thermal conditioning (heat exchange and cooking at 195°C and 20 bars) and press filtration. These successive treatments allow reducing sludge volume by more than a factor 10 (i.e. DM, Table 2) and producing a dewatered cake called sludge cake which is reused as agricultural fertilizer. The Seine Grésillons plant treats 100 000 m 3 of wastewater per day. Sludge treatment is performed by centrifugation and thermal drying. The thermal drying process can operate at a wide range of temperature, but the facility used in this plant operates at a high temperature (260°C) compared to conventional dryers (generally 105°C [START_REF] Voulvoulis | Fate of organotins in sewage sludge during anaerobic digestion[END_REF]). This allows reducing the water content drastically (i.e. DM content,

Table 2) to obtain, after compacting, almost 8 000 tons DM of solid pellets per year (SIAAP source) which are stocked in big bags or silos before to be reused in agriculture. More information about WWTPs and treatment processes are presented in supporting material -Table 1 and on SIAAP website (www.siaap.fr -in French).

Seine Centre

Seine Aval

Seine Grésillons n = number of campaigns performed. While six independent campaigns (between October and December 2011) were performed for thermal drying and sludge cake, consecutive day sampling was considered for centrifugation and digestion to throw off the possible lack of homogeneity. Thus, one sample per day was collected within three consecutive days for digestion (October 2011). Similarly, six samples were collected within two periods of three consecutive days (one in October and one in December) for centrifugation. Each sludge sample was manually collected (2 L for TS and SC -3 L for RS, CS and DS) respecting all guidelines to avoid sample contamination. SC samples are a mix of sludge produced within a week (7 days) while other samples were punctual due to technical issues. For digestion, a period of 16 days has been applied between inlet and outlet samples to take the solid retention time into account. Overall, removals of dry matter and volatile matter during anaerobic digestion are about 42% and 56% respectively. This removal is in good agreement with conventional anaerobic digestion removal [START_REF] Moletta | Méthanisation de la biomasse (Biomass methanisation)[END_REF]. VM content in sludge cake is low (42 % DM) compared to the other sludges highlighting a removal during the sludge cake production process (thermal conditioning + press filtration, Figure 1). This is most likely due to the solubilization of a fraction of the organic matter [START_REF] Neyens | A review of thermal sludge pre-treatment processes to improve dewaterability[END_REF][START_REF] Valo | Thermal, chemical and thermochemical pre-treatment of waste activated sludge for anaerobic digestion[END_REF] during thermal conditioning (195°C and 20 bars). This fraction is then removed with water during press filtration. In contrary, VM is rather constant in both thermal drying and centrifugation, highlighting that VM is whether not or similarly removed (no change in percentage) as DM during these treatments.

General sludge quality parameters

Pollutants and analytical procedures

A total of 117 pollutants were monitored and depending on the compound, two accredited laboratories (COFRAC -French official accreditation committee) were involved: Eurofins and SIAAP laboratory. Table 3 gives the different groups of pollutants monitored, their analytical procedures and quantification limits. The complete list of studied compounds is given in supporting material -Table 2. d Analytical methods: GC = gas chromatography; GC-PFPD = GC with pulsed flame photometric detector; GC-MSMS = GC with tandem mass spectrometry; GC-ECD = GC with electron capture detector; GC-FID = GC with flame ionization detector; ICP-AES = inductively coupled plasma with atomic emission spectrometry. e Quantification limit in mg/kg DM. f Chloroalkanes C10-C13, tributylphosphate and hexachlorocyclopentadiene.

Methodology of result exploitation and efficiency evaluation

Only contents above the quantification limits were considered. Then, removals have been calculated only when the compound is quantified both in inlet and outlet of the treatment. Removals could be also evaluated when the compound is quantified only in inlet or outlet, but this case was not encountered here.

For the second part of this paper dealing with pollutant fate during sludge treatment, thermal drying and centrifugation are differently examined from anaerobic digestion. In fact, dry matter is not removed and only water quantity is reduced (volume reduction) during dewatering treatments such as thermal drying and centrifugation. Given this, removals of micropollutant content (in mg/kg DM) have been considered for these treatments since it is not linked to the volumetric flow, which varies between inlet and outlet resulting from water removal.

In contrary, since the matrix is reduced as regards digestion, removal calculations were not based on content removals but on the removal of micropollutant loads. Therefore, the micropollutant loads (Lµp) have been calculated according to Equation 1.

𝑳 µ𝒑 [ 𝒎𝒈 µ𝒑 𝒅𝒂𝒚 ⁄ ] = 𝑪 µ𝒑 × 𝑫𝑴 × 𝑸 𝒗 ;
With Cµp: micropolluant content (mg/kg DM), DM: dry matter content (kg/L) and Qv: sludge feed rate (L/day).

Equation 1

A conservation of volumetric flow during anaerobic digestion has been considered. The removal of load (Rload) is then given by Equation 2, calculated from the removal of the micropollutant content (RC) and the removal of the dry matter content (RDM).

𝑅 𝑙𝑜𝑎𝑑 = (𝐿 𝑖𝑛 -𝐿 𝑜𝑢𝑡 ) 𝐿 𝑖𝑛 ⁄ = 1 - 𝐶 𝑜𝑢𝑡 𝐶 𝑖𝑛 ⁄ × 𝐷𝑀 𝑜𝑢𝑡 𝐷𝑀 𝑖𝑛 ⁄ = 1 -(1 -𝑅 𝐶 ) × (1 -𝑅 𝐷𝑀 ); Equation 2
3. Results and discussion

Micropollutant contamination of treated sludges

Figure 2 displays the quality of treated sludges regarding micropollutants. Each type of sludge (number of samples in brackets) and quantification limits for each compound detected are illustrated. A table with contents of all compounds found in treated sludges is given in supporting material -Table 3. In order to enable comparison of results, Table 4 provides a literature synthesis concerning micropollutant sludge contents. BDE 47, 99, 100, 153, 154 and 209. 4 BDE 28, 47, 99, 100, 153, 154, 183 and 209. 5 Fluoranthene, benzo(a)pyrene, benzo(b)fluoranthene, benzo(k)fluoranthene, benzo(ghi)perylene and indeno(1,2,3-cd)pyrene. 6 See 5 + acenaphtene, phenanthrene, fluorene, pyrene and benzo(j)fluoranthene. 7 PCB 28, 52, 101, 118, 138, 153 and 180. Out of the 117 molecules monitored (Table 3), 35 are detected in treated sludges but pesticides, VOCs, hepta-, hexa-, penta-, tetra-and octa-PBDEs and benzene based products (BBP) were never detected. Concerning pesticides, it is consistent as they are mainly hydrophilic (log Kow < 3-4) and their presence in water are both variable and weak [START_REF] Gasperi | Occurrence and removal of priority pollutants by lamella clarification and biofiltration[END_REF]. Moreover, a lot of them are now forbidden (i.e. endosulfan or atrazine). Similarly, VOCs and BBPs are volatile and mainly removed by volatilization during wastewater treatment (Byrns, 2001;[START_REF] Joss | Are we about to upgrade wastewater treatment for removing organic micropollutants[END_REF]. Finally, BDE 209 is the main PBDE congener used and found in water by far and other congeners are generally quantified in sludge in lower contents than the detection limit in this study (50 µg/kg DM), as showed by [START_REF] Knoth | Polybrominated diphenyl ether in sewage sludge in Germany[END_REF]. Contrariwise, metals (Zn, Pb, Cu and Cr), organotins, DEHP and alkylphenols are always detected in all samples. In addition, tributylphosphate, a hydrophobic compound principally used as extractant and plasticizer but also employed as antifoaming or herbicide agent in detergents or paints, was detected in several samples. PCBs and PAHs are classically found in sludges (Table 4), but they are only detected in sludge cake in this study due to analytical performances (detection and quantification limits).

The pollutant content variability is broadly weak (less than one order of magnitude) for one type of sludge except for alkylphenols. For this family, a variability of two orders of magnitude is observed within a type of sludge, as observed for DS and TS comparatively to others sludges. This high variability of NP was also observed for wastewater by (Bergé et al., 2012b). Contents from sludge to sludge vary in a range of about one order of magnitude due to treatments but overall all sludges have a similar micropollutant pattern. This is consistent as they are produced by WWTPs treating water from the same catchment. Sludge cake and digested sludge are the most contaminated, particularly for PAHs, PCBs and metals, with contents found in the upper part of the range. This results from a dry matter removal of more than 40% allowed by digestion and further treatments (sludge cooking) in Seine Aval (Figure 1). In contrary, contents in centrifuged and thermally dried sludges are found in the lower part of the range for most of the compounds.

Contents found are in accordance with the literature (Table 4), particularly for organotins (0.005 -0.2 mg/kg DM), alkylphenols (NP 0.22 -50 and NP1EO 0.067 -31 mg/kg DM), BDE 209 (0.11 -0.38 mg/kg DM), individual PAHs (0.11 -0.99 mg/kg DM), PCBs (0.010 -0.053 mg/kg DM) and metals (10-3 000 mg/kg DM). In particular, high contents of metals, NP and NP1EO are observed while other compounds are all found below 1 mg/kg dm. Tributylphosphate is poorly documented in sludge and is found between 0.02 and 0.36 mg/kg DM. Surprisingly, DEHP is found in the very lower part of the range displayed in the literature (0.1 -1 mg/kg DM), especially in digested sludge.

Nevertheless, (Blanchard et al., 2012) observed similar DEHP levels in sludge coming from the same plants.

Comparing to regulations (Table 1), treated sludges respect European standards (EC, 1986) for metals overall, except Cd for which two sludge cake samples slightly exceeded the actual threshold value (10 mg/kg DM). Similarly, French standards (Table 1) are respected as contents of Σ7 PCBs (< 0.8 mg/kg DM) and both individual and sum of PAHs (< 2 and < 5 mg/kg DM) are always below the threshold values for agricultural reuse [START_REF] Ec | Directive of the European Parliament and of the Council n°91/271/EC establishing a framework for the community action in the field of sewage sludge policy[END_REF]. In addition and as shown by Figure 3 illustrating the historical evolution of heavy metals and PAH yearly average contents in sludge cake, no exceedances of threshold values were observed in the past, except the first years after the application of the Urban Wastewater Treatment Directive [START_REF] Ec | Directive of the European Parliament and of the Council n°86/278/EEC establishing a framework for the community action in the field of sewage sludge policy[END_REF] for Zn, Pb and Cd. Zn content respects regulation since 1988, Pb since 1987 and Cd since 1993, while Cu, Ni and Cr ones have always been below threshold values on a yearly average basis. Similarly, PAH contents were always in accordance with French standards since they are measured (2001). All data presented in Figure 3 were provided by SIAAP from their routine quality controls which are accredited and subject to European norms. They are published for the first time (PAHs) or represent an update of former works (metals - [START_REF] Meybeck | Historical perspective of heavy metals contamination (Cd, Cr, Cu, Hg, Pb, Zn) in the Seine River basin (France) following a DPSIR approach (1950-2005)[END_REF]).

Moreover, contents obtained in this study (mean values in the box on the right -Figure 3) are totally consistent as they are in the continuity of the time-trends from Seine Aval sludge, both for PAHs and metals.

An important decrease of metal contents in sludge cake is observed since the 80s. In particular, contents have decreased from 1980 to 2012 with a factor 3 for Zn (-70%), a factor 7 for Cr (-89%) and a factor 3 to 5 for Ni (-88%), Cu (-65%), Pb (-80%) and Cd (-95%). This tendency results from a decrease of emissions like atmospheric fallout, roof runoff, street runoff, domestic sewage and industrial sewage [START_REF] Thevenot | Critical budget of metal sources and pathways in the Seine River basin (1994-2003) for Cd, Cr, Cu, Hg, Ni, Pb and Zn. Science of The Total Environment, Human activity and material fluxes in a regional river basin: the Seine River watershed -Seine Special Issue[END_REF], which was driven by different regulatory standards adopted over past decades and by global de-industrialization of Parisian catchment [START_REF] Meybeck | Historical perspective of heavy metals contamination (Cd, Cr, Cu, Hg, Pb, Zn) in the Seine River basin (France) following a DPSIR approach (1950-2005)[END_REF], inducing changes in metal uses and decrease of both industrial and domestic metal discharges. However, this decrease is not linear and three phases can be observed: until 1994 contamination of sludge decreased significantly (i.e. -76% for Zn), then between 1994 and 1996 a short period of increase is observed before another phase of decrease which is slight and tends to stabilize in the 2000s. Finally, all metals seem to undergo the same evolutions. PAH data are available since 2001 and it is not possible to establish a clear trend as contents vary with a factor 2 from year to year. In fact, the evolutions of the three PAH contents in sludge seem linked as they have all the same historical pattern. Even if contents seem overall stable over the years, periodic evolutions seem to occur when looking at weekly data (not represented), with contamination peaks observed regularly.

Actually, time-trends of sludge contamination significantly follow time-trends of quantity used in the society, generally decreasing due to regulatory actions, as shown by [START_REF] Olofsson | Time-trends of metals and organic contaminants in sewage sludge[END_REF].

Even if no time-trend is available for PBDEs in Parisian sludge, [START_REF] Ricklund | Mass balance of decabromodiphenyl ethane and decabromodiphenyl ether in a WWTP[END_REF] Results obtained for both dewatering processes show a high variability of content removals, except for metals and PAHs. The higher variability of removal for organic pollutants, particularly for alkylphenols, compared to metals, probably results from both the significantly lower contents of these compounds (higher analytical uncertainty) and the variability of the mechanisms involved in their removal. For metals, the low variability can be explained by both the lower analytical uncertainty and their fate during sludge treatment, since no removal mechanism is occurring for them.

Values calculated for hexachlorocyclopentadiene and tributylphosphate have to be considered with caution as these molecules were always detected very close from their detection limits or not detected.

Most of pollutants are broadly not removed during dewatering treatments, whatever the process used. This is particularly significant for metals as they are known to be highly persistent (not biodegradable and volatile) during sludge treatment (Chipasa, 2003;[START_REF] Craig | Changes of heavy metal speciation during high-solid anaerobic digestion of sewage sludge[END_REF]. Contents of metals, TBT, DBT, tributylphosphate and DEHP are not affected by both treatments.

Only alkylphenols, MBT, PAHs and BDE 209 seem to have a different behavior in both treatments.

Contrary to centrifugation, thermal drying seems to allow a quite stable removal of about 10 -40% for PAHs and MBT, and a very variable removal of 20 -90% for alkylphenols. As temperature inside the dryer reaches 260°C, transfers to atmosphere by desorption and volatilization could be significantly enhanced as depicted by [START_REF] Tuncal | Abatement of Organic Pollutant Concentrations in Residual Treatment Sludges: A Review of Selected Treatment Technologies Including Drying[END_REF] in spite of a short solid retention time (3 min). Similarly, abiotic degradation of these compounds, such as hydrolysis, may occur at this temperature [START_REF] Kepp | Enhanced stabilisation of sewage sludge through thermal hydrolysis: three years of experience with full scale plant[END_REF][START_REF] Veeken | Effect of temperature on hydrolysis rates of selected biowaste components[END_REF]. More specific measurements should be performed to highlight these pathways. In contrary, a removal of about 50% of BDE 209 is observed in centrifugation despite a high variability, while content is rather stable during thermal drying. As this molecule is strongly hydrophobic (log Kow = 12.8, [START_REF] Langford | The partitioning of alkylphenolic surfactants and polybrominated diphenyl ether flame retardants in activated sludge batch tests[END_REF]), so strongly linked to the particulate phase, further specific measurements are needed to explain this astonishing result.

Anaerobic digestion

Anaerobic digestion is widely used all over the world to stabilize sludge and reduce the quantity of dry matter. Results obtained during campaigns performed are represented in Figure 5 separated by behavior by dotted lines.

1

Figure 5 -Fate of micropollutants during mesophilic anaerobic digestion 2

As regards the three campaigns performed and similarly to dewatering processes, a higher variability of removal is observed for organic pollutants (20-50%) than for metals like Pb or Cr (max 30%), probably due to lower contents and a variability of degradation. However, three different behaviors can be observed depending on the compound: i) conservation of load, ii) removal in the same extent to dry matter removal and iii) removal higher than dry matter removal.

Conservative species are those which are not removed resulting in an increase of their contents (mg/kg DM) in digested sludge, as matrix is partially removed (DM -42%, Table 2). In contrary, compounds with removal of load higher than dry matter have their content decreasing in sludge.

Finally, a load removal comparable to dry matter removal is linked with stability in sludge content.

Thus, even if every positive load removal corresponds to a real elimination of the compound, it doesn't reflect automatically a decrease of content in sludge.

Loads of metals are conservative during digestion which is consistent as they are not biodegradable and volatile. Thus, this confirms the validity of the data treatment strategy applied in this study. This conservation results in an increase of metal contents in sludge within treatments. In the context of land farming, limitation of emissions (contamination of water) seems to be the easiest strategy to reduce metals contamination of sludge. As it was previously shown [START_REF] Meybeck | Historical perspective of heavy metals contamination (Cd, Cr, Cu, Hg, Pb, Zn) in the Seine River basin (France) following a DPSIR approach (1950-2005)[END_REF], this strategy clearly leads to a decrease of contents in treated sludge.

Organotins are degraded similarly to dry matter except DBT which is not removed and even slightly produced (-15%). This is confirmed by Figure 2 where it is clear that DBT content in digested sludge is significantly higher than in other sludges. Biodegradation of TBT in DBT through dealkylation mechanism has been observed at laboratory scale and in surface water and sediment under both aerobic and anaerobic conditions [START_REF] Craig | Changes of heavy metal speciation during high-solid anaerobic digestion of sewage sludge[END_REF][START_REF] Maguire | Degradation of the tri-n-butyltin species in water and sediment from Toronto Harbor[END_REF][START_REF] Stasinakis | Aerobic biodegradation of organotin compounds in activated sludge batch reactors[END_REF]. This reaction in anaerobic digestion of sludge could counteract DBT biodegradation and explain this result.

Alkylphenols are more removed than dry matter, except NP. Anaerobic biodegradation of carboxylate and ethoxylate species to NP has been observed in the literature (Ejlertsson et al., 1998;[START_REF] Lu | Anaerobic degradation behavior of nonylphenol polyethoxylates in sludge[END_REF] as well as NP biotransformation [START_REF] Patureau | Impact of sewage sludge treatment processes on the removal of the endocrine disrupters nonylphenol ethoxylates[END_REF][START_REF] Salanitro | Anaerobic biodegradability testing of surfactants[END_REF].

Thus, the lesser load removal observed for NP compared to other alkylphenols could actually highlight that NP anaerobic biodegradation is slower than its formation from other alkylphenols with longer chains, as proposed by (Chang et al., 2005;[START_REF] Stasinakis | Review on the fate of emerging contaminants during sludge anaerobic digestion[END_REF]. However, biodegradation kinetic measurements should be performed to validate this assumption. DEHP (50 -70%) and BDE 209 (40 -90%) are also removed in a higher proportion than matrix. For DEHP, such high removal has already been observed at pilot scale by [START_REF] Parker | Estimation of anaerobic biodegradation rates for toxic organic compounds in municipal sludge digestion[END_REF]. Biodegradation of phthalate esters such as DEHP has been reported under methanogenic conditions [START_REF] El-Hadj | Biodegradation of PAH and DEHP micro-pollutants in mesophilic and thermophilic anaerobic sewage sludge digestion[END_REF][START_REF] Gavala | Biodegradation of phthalate esters during the mesophilic anaerobic digestion of sludge[END_REF][START_REF] Marttinen | Occurrence and removal of organic pollutants in sewages and landfill leachates[END_REF] and results from hydrolysis of the two ester side chains to phthalic acid and alkyl alcohols which can then be degraded to methane and carbon dioxide [START_REF] Shelton | Anaerobic biodegradation of phthalic acid esters in sludge[END_REF][START_REF] Stasinakis | Review on the fate of emerging contaminants during sludge anaerobic digestion[END_REF]. Concerning BDE 209, anaerobic debromination of this congener to less brominated congeners could explain this removal as this mechanism has been highlighted by several papers [START_REF] Gerecke | Anaerobic Degradation of Decabromodiphenyl Ether[END_REF][START_REF] He | Microbial Reductive Debromination of Polybrominated Diphenyl Ethers (PBDEs)[END_REF][START_REF] Robrock | Pathways for the Anaerobic Microbial Debromination of Polybrominated Diphenyl Ethers[END_REF].

Overall, alkylphenols, DEHP and BDE 209 are significantly removed (> 50%) while organotins and NP are moderately removed (40%) and metals and DBT are not removed. These results show that anaerobic digestion allows a significant removal of some micropollutants despite not being designed for that.

Conclusions

This study has investigated the fate of a large panel of micropollutants (n=117) during sludge treatment and the quality of treated sludges obtained. While some data are available for anaerobic digestion, centrifugation and thermal drying are still not documented. In addition, the content of a lot of micropollutants in French and Parisian sludges in particular is not well documented.

Overall, treated sludges have a similar micropollutant pattern despite different treatments. Some compounds are always detected (metals, organotins, alkylphenols, DEHP) while others are never detected (pesticides, BBPs and VOCs). Contents found in the different sludges are rather similar and in accordance with previous works. In treated sludges, micropollutant contents are always in compliance with regulations except two sludge cake samples for which Cd exceeds the threshold value. Historical evolution of micropollutants in sludge cake allows showing that contamination is directly linked to compounds uses and establishment of regulations on uses seems to be an efficient strategy to decrease the sludge content of micropollutants, as it is the case for metals.

Regarding dewatering processes, centrifugation and thermal drying seem to have no significant impact on micropollutant content of sludge overall. A slight removal of alkylphenols, MBT and PAHs by abiotic transfers (volatilization, hydrolysis) seems however to be possible by thermal drying thanks to the high temperature inside the reactor. In contrary, digestion enables the removal of a lot of organics. DEHP, BDE 209, organotins and alkylphenols are similarly or better removed than dry matter which is the designing parameter of the process, while metals are persistent. This result confirms that among the existing and largely used sludge treatments, digestion is the only one with composting to really allow a reduction of the biodegradable micropollutants load. Specific studies on mechanisms involved in thermal drying and on the fate of micropollutants during composting should be held to complete this work. In addition, a similar work will be soon performed on pharmaceuticals, to enrich the data base obtained and improve the understanding of the micropollutant fate during sludge treatments. An optimization of digestion operational parameters (temperature, hydraulic retention time, pre-treatment) in order to improve matrix elimination could lead to a significant improvement of treated sludge quality in terms of organic micropollutants, as they influence the biodegradation of a lot of compounds such as DEHP or alkylphenols [START_REF] El-Hadj | Effect of ultrasound pretreatment in mesophilic and thermophilic anaerobic digestion with emphasis on naphthalene and pyrene removal[END_REF][START_REF] Stasinakis | Review on the fate of emerging contaminants during sludge anaerobic digestion[END_REF]. However, some specific processes such as bioleaching treatments [START_REF] Pathak | Bioleaching of heavy metals from sewage sludge: A review[END_REF]

LIST OF REFERENCES

Abad, E., Martínez, K., Planas, C., Palacios, O., Caixach, J., Rivera, J., 2005. Priority organic pollutant assessment of sludges for agricultural purposes. Chemosphere 61, 1358-1369. Aparicio, I., Santos, J.L., Alonso, E., 2009. Limitation of the concentration of organic pollutants in sewage sludge for agricultural purposes: A case study in South Spain. Waste Management 29, 1747-1753. Bergé, A., Cladière, M., Gasperi, J., Coursimault, A., Tassin, B., Moilleron, R., 2012a. Meta-analysis of environmental contamination by alkylphenols. Env Sci Poll Res Int 19, 3798-3819. Bergé, A., Gasperi, J., Rocher, V., 2012b. Phthalate and alkylphenol removal within wastewater treatment plants using physicochemical lamellar clarification and biofiltration, 11th International Conference on Water Pollution: Modelling, Monitoring and Management. Water Pollution XI, UK. Blanchard, M., Alliot, F., Bourges, C., Dargnat, C., Desportes, A., Dinh, T., Eurin, J., Labadie, P., LeBot, B., Mompelat, S., Moreau-Guigon, E., Tamtam, F., Teil, M.-J., Chevreuil, M., 2012. Contamination of urban sludge from different treatment processes. Example of phtalates, PBDE, PAH and antibiotics., Piren-Seine 2012, Paris (in French). Blanchard, M., Teil, M.J., Ollivon, D., Legenti, L., Chevreuil, M., 2004. Polycyclic aromatic hydrocarbons and polychlorobiphenyls in wastewaters and sewage sludges from the Paris area (France). Environmental Research 95, 184-197. Byrns, G., 2001. The fate of xenobiotic organic compounds in wastewater treatment plants. Water Research 35, 2523-2533. Chang, B.V., Chiang, F., Yuan, S.Y., 2005. Anaerobic degradation of nonylphenol in sludge. Chemosphere 59, 1415-1420. Chen, M., Li, X.-m., Yang, Q., Zeng, G.-m., Zhang, Y., Liao, D.-x., Liu, J.-j., Hu, J.-m., Guo, L., 2008. Total concentrations and speciation of heavy metals in municipal sludge from Changsha, Zhuzhou and Xiangtan in middle-south region of China. Journal of Hazardous Materials 160, 324-329. Chipasa, K.B., 2003. Accumulation and fate of selected heavy metals in a biological wastewater treatment system. Waste Management 23,[135][136][137][138][139][140][141][142][143]

Figure 1 -

 1 Layouts of the three studied plants Different sampling points have been defined to study both the quality of treated sludges and the fate of micropollutants during treatments: raw sludge (RS), CS, DS, TS and SC -Figure 1. Thus, inlet and outlet of digestion, centrifugation and thermal drying were sampled, as well as SC.

  Figure 2 -Micropollutant contents of treated sludges studied

1

  Figure 4 displays the content removals of studied compounds within dewatering processes (thermal

  could be implemented in parallel of regulations reinforcement to decrease the metal contents of sewage sludge, as they are currently persistent in almost all the treatments including digestion. ACKNOWLEDGEMENT This study was carried out within the framework of OPUR (Observatory of Urban Pollutants) research program. The authors would like to thank SIAAP teams for their technical support and their active participation in sampling campaigns and data analysis.

Table 1 -French (order of 8 th of January 1998) and European (EC, 1986) thresholds for PCBs, PAHs and metals in sludges to landfarm Threshold value in sludge (mg/kg DM) Maximal flux from sludges in last 10 years (g/m 2 )

 1

	General case	Pasture case	General case	Pasture case
	Σ7 PCBs*	0.8	0.8	1.2	1.2
	Fluoranthene	5	4	7.5	6
	Benzo(b)fluoranthene	2.5	2.5	4	4
	Benzo(a)pyrene	2	1.5	3	2
	Cadmium	10 (20 -40)		0.015
	Chrome	1 000		1.5
	Copper	1 000 (1 000 -1 750)	1.5
	Mercury	10 (16 -25)		0.015
	Nickel	200 (300 -400)	0.3
	Lead	800 (750 -1200)	1.5
	Zinc	3 000 (2 500 -4 000)	4.5
	Chrome + Zinc + Copper + Nickel	4 000		6
	* PCBs 28, 52, 101, 118, 138, 153 and 180.
	Figures presented are from French regulation (order of 8 th of January 1998), while European thresholds from Wastewater Treatment
	Directive (EC, 1986) are given in brackets.

Table 2

 2

	displays the general quality parameters for each sample, i.e. dry matter (DM, in % -1% =
	10 g/L) and volatile matter (VM, in % DM). Both criteria are commonly used in sludge
	management. Minimum, maximum and mean (in italics below) values are given.

Table 2 -Dry matter and volatile matter contents (min -max -mean) of sludges studied Digestion RS DS Thermal drying CS TS Centrifugation RS CS

 2

	Sludge cake
	TS

Table 3 -Groups of pollutants and analytical methods

 3 Groups of molecules: DEHP = di(2-ethylhexyl) phthalate ; PBDE = polybromodiphenyl ethers; VOC = volatile organic compounds; PAH = polycyclic aromatic hydrocarbons; PCB = polychlorobiphenyls. b Number of molecules. c Number of measuring campaigns.

	Groups a	Total b	n c	Standards	Methods d	LOQ e
	Organotins	4	3 -6	Eurofins Internal Method	GC-PFPD	0.005
	Organochlorine pesticides	22	3 -6	XP X 33-012	GC-MSMS	0.005 to 0.800
	Organophoshorus pesticides	2	3 -6	XP X 33-012	GC-MSMS	0.02
	Nitrogenous herbicides	2	3 -6	XP X 33-012	GC-MSMS	0.02
	Urea pesticides	4	3 -6	XP X 33-012	GC-MSMS	0.02 to 0.05
	Various herbicides	3	3 -6	XP X 33-012	GC-MSMS	0.02 to 0.05
	Benzene based products	12 2	3 -6	NF ISO 15009 XP X 33-012	GC-FID GC-MSMS	0.02
	Nitrobenzenes	3	3 -6	XP X 33-012	GC-MSMS	0.05
	VOCs	17	3 -6	NF ISO 15009	GC-ECD	0.02
	Phenolic compounds	8	3 -6	XP X 33-012	GC-MSMS	0.04 to 0.05
	DEHP	1	3 -6	XP X 33-012	GC-MSMS	0.05
	Alkylphenols	6	3 -6	XP X 33-012	GC-MSMS	0.01
	PBDEs	9	3 -6	XP X 33-012/Isotopic Dilution	GC-MSMS	0.05
	Other organic compounds f	3	3 -6	XP X 33-012	GC-MSMS	0.01 to 0.02
	Eurofins screening	98
	PAHs	6	3 -6	NF ISO 17993	GC-MSMS	0.04 to 0.2

Table 4 -Literature review of studied micropollutants in sludge 1

 4

	Molecules	Location	Type of sludge	n 1	Mean 2	Min 2	Max 2	Reference
	Organotins
	TPHT	World	Various	5	0.63	<0.02	9	(Clarke and Smith,
								2011)
	TBT	Sweden	Digested	1	0.004	*	*	(Olofsson et al., 2012)
		Switzerland	Digested	1	1.1 ± 0.4	*	*	(Fent, 1996)
		World	Various	7	0.86	0.02	6	(Clarke and Smith,
								2011)
	DBT	Sweden	Digested	1	0.075	*	*	(Olofsson et al., 2012)
		Switzerland	Digested	1	1.5 ± 0.5	*	*	(Fent, 1996)
		World	Various	6	1.28	0.41	7.5	(Clarke and Smith,
								2011)
	MBT	Sweden	Digested	1	0.074	*	*	(Olofsson et al., 2012)
		Switzerland	Digested	1	0.5 ± 0.2	*	*	(Fent, 1996)
		World	Various	6	0.93	0.1	6	(Clarke and Smith,
								2011)
	Phtalates
	DEHP	Finland	Digested	1	126	91	179	(Marttinen et al., 2003)
		Spain	Digested	1	159	13	345	(Aparicio et al., 2009)
		Spain	Thermally dried	1	148.8	1.5	3 514	(Abad et al., 2005)
		World	Various	13	58	<0.02	3 514	(Clarke and Smith,
								2011)
	Alkylphenols
	NP	Greece	Digested	1	0.17	<0.04	0.45	(Stasinakis et al., 2008)
		Spain	Digested	1	102.1	<0.19	358.2	(González et al., 2010)
		France	Thermally dried	1	61.7	16.5	124.9	(Ghanem et al., 2007)
		World	Various	24	128	0.02	2530	(Bergé et al., 2012a)
	NP1EO	Greece	Digested	1	12.3	1.01	41.3	(Stasinakis et al., 2008)
		Spain	Digested	1	53.2	<0.75	287.8	(González et al., 2010)
		World	Various	18	40.2	0.15	850	(Bergé et al., 2012a)
	Various
	Tributylphosphate	Denmark	Various	1	*	<0.020	2.400	(Tørsløv et al., 1997)
		Sweden	Digested	1	0.011	*	*	(Olofsson et al., 2012)
	PBDEs
	BDE 209	Sweden	Various	1	0.120	0.006	1.000	(Law et al., 2006)
		Germany	Digested	1	0.443	0.133	1.339	(Knoth et al., 2007)
		World	Various	14	1.039	0.003	18.632	(Clarke and Smith,
								2011)
	Σ6 PBDEs 3	Sweden	Various	1	0.250	0.024	1.260	(Law et al., 2006)
		Germany	Digested	1	0.577	0.186	1.627	(Knoth et al., 2007)
	Σ8 PBDEs 4	World	Various	7	1.360	0.005	4.690	(Clarke and Smith,
								2011)
	PAHs
	Σ6 PAHs 5	UK France	Digested Dewatered	1 1	14.8 1.68	4.75 0.52	28.1 3.36	(Stevens et al., 2002) (Blanchard et al., 2004)
	Σ11 PAHs 6	Spain	Thermally dried	1	1.89	0.13	7.35	(Abad et al., 2005)
	PCBs
	Σ7 PCBs 7	UK	Digested	1	0.080	0.033	0.221	(Stevens et al., 2002)
		Spain	Thermally dried	1	0.041	<0.006	0.131	(Abad et al., 2005)
		France	Dewatered	1	0.617	0.12	1.93	(Blanchard et al., 2004)
	Metals
	Zn	China	Dewatered	1	557.4	361.0	1 105.9	(Chen et al., 2008)
		Greece	Digested	1	4 500 ± 450	*	*	(Karvelas et al., 2003)
		France	Treated	1	875 ± 1005	*	*	(Martin et al., 2008)
	Cu	China	Dewatered	1	557.4	361.0	1 105.9	(Chen et al., 2008)
		Poland	Digested	1	240.4 ± 1.2	*	*	(Sprynskyy et al.,
								2007)
		Greece	Digested	1	1 200 ± 220	*	*	(Karvelas et al., 2003)
		France	Treated	1	335 ± 338	*	*	(Martin et al., 2008)
	Pb	China	Dewatered	1	225.4	67.0	659.0	(Chen et al., 2008)
		Poland	Digested	1	38.12 ± 1.2	*	*	(Sprynskyy et al.,
								2007)
		Greece	Digested	1	330 ± 84	*	*	(Karvelas et al., 2003)