Jérémy Omer
email: jeremy.omer@insa-rennes.fr

Michael Poss
email: michael.poss@lirmm.fr

Time-dependent shortest paths with discounted waits

Keywords: Time-dependent networks; Shortest paths, N P-completeness, Approximation, Dynamic programming, Waiting

We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving time. Although optimal solutions may contain cycles and pseudopolynomially many arcs, we provide a representation of the solutions that is polynomial in the absolute value of the inverse of the slopes as well as in the dimensions of the graph. We further prove that the problem is N P-Hard when the slopes are integer. We introduce a restriction of the problem where waits must be integer and propose pseudo-polynomial algorithms for the latter. We also provide a pseudo-FPTAS, polynomial in the ratio between the bound on the total waiting time and the minimum travel time. Finally, we discuss harder variants of the problem and show their inapproximability.

Introduction

We are interested in the situation of a salesman who must travel from an origin o to a destination d in a potentially congested transport network. The variations in traffic conditions imply that the travel time between any two points in the network can vary over the day. Instead of losing time in the traffic, the salesman can avoid peak hours by delaying his departure or stopping at specific places to perform other activities that will be useful to him or his work. If he does not have a strong constraint on his arrival time and if he can value the time he spends waiting for better traffic conditions, only travel time is wasted. Therefore, the salesman's objective is to minimize total travel time.

Alternative applications of our model are varied. One example arises in truck transportation problems where some freight must be sent from a source to a destination at minimum cost. The transportation cost is essentially driven by the fuel consumption along the trip. The latter is minimized by letting the drivers pause to avoid the most congested legs. Another example is related to organized tourist trips that last several days. Some destinations along these trips cannot be missed. On the other hand, there are many more choices of interesting and secondary spots that can be visited along the way. These spots represent the nodes where waiting is allowed, bounded by the time that can be spent in each of them. Overall, the tourism agency wishes to maximize the interest of the whole trip, reducing the time spent in congested traffic by organizing well-chosen stops.

Literature review

Route planning in congested transport networks is classically formalized as the search for a shortest path in a time-dependent network. Due to this natural application, the time-dependent shortest path problem (TDSP) has been the subject of active research since its introduction by Cooke and Halsey in 1966 [4]. In particular, the study of the algorithmic complexity of TDSP has raised subtle issues from the beginning. For instance, Dreyfus [START_REF] Dreyfus | An appraisal of some shortest-path algorithms[END_REF] presented the first polynomial algorithm for the search of a shortest path in a graph where arc costs are positive and integer-valued functions of time. However, as discussed by Kaufman and Smith [START_REF] Kaufman | Fastest paths in time-dependent networks for intelligent vehiclehighway systems application[END_REF], this result implicitly assumes that the cost functions (i.e., the travel time functions) are consistent. This property, also referred to as FIFO (first-in first-out), expresses that one cannot reach the head of an arc earlier by departing later from its tail. Actually, it so happens that if we alleviate the consistency assumption, it is possible to build a time-dependent network where the shortest path is infinite, as shown by Orda and Rom [START_REF] Orda | Minimum weight paths in time-dependent networks[END_REF]. Finiteness of the optimal paths can be guaranteed by imposing a positive constant lower bound to arc travel time functions, but Orda and Rom [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF] observe that the problem remains N P-Hard. This statement is proved by Sherali et al. [START_REF] Sherali | The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms[END_REF] by reduction from the partition problem.

In close connection to the topic of consistency is that of waiting at the tail of an arc before traversing it. The possibility of waiting has first been investigated by Halpern [START_REF] Halpern | Shortest route with time dependent length of edges and limited delay possibilities in nodes[END_REF] in inconsistent networks. In his work, inconsistency arises from the existence of time intervals where departing from a node is forbidden, and waits stand for parking periods. Orda and Rom [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF] continued Halpern's work by considering two different waiting models: unrestricted waiting, and source waiting. In the unrestricted version, waiting is allowed everywhere without restriction, but the arrival time is minimized, which means that waiting time is counted. Interestingly, the problem can then be solved in polynomial time if sufficiently simple travel time functions are considered (e.g., piecewise linear functions with constant numbers of breakpoints). As argued by Foschini et al. [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF], the problem is then equivalent to the consistent case, since one can always wait at the tail of an arc as long as it reduces the arrival time at the head of the arc.

In the source waiting model, waiting is forbidden everywhere except for the source node. This particular case raises the question of determining arrival time at destination as a function of departure time from source. Several theoretical works have been devoted to the study of this function [START_REF] Borradaile | Time-dependent shortest paths in bounded treewidth graphs[END_REF][START_REF] Dean | Shortest paths in FIFO time-dependent networks: Theory and algorithms[END_REF][START_REF] Dehne | Shortest paths in time-dependent FIFO networks[END_REF][START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] for piecewise-linear arc travel time functions. In these articles, the authors deal only with consistent networks. Foschini et al. [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] then established that the arrival time function is a piecewise linear function that can have a superpolynomial number of pieces, even if the total number of pieces in arc travel time functions is bounded. More specifically, if the total number of pieces in the arc functions is K and n is the number of nodes in the graph, then the complexity of the arrival time function is at most Kn log(Θ(n)) . Foschini et al. show that at most K breakpoints of this function correspond to those of the arc functions, while the others are intersection of piecewiselinear functions. From this result, they establish that despite the superpolynomial complexity of the arrival time function, it is polynomial to determine the departure time that minimizes total travel time.

Cai et al. [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF] considered models where each arc has a time-dependent cost, in addition to the time-dependent traversal time. What is more, they allowed waiting at every node, incurring waiting costs described by time-dependent functions. They provided dynamic programming algorithms, later improved in [START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: Complexity, algorithms and implementations[END_REF] and [START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF].

An even larger literature about TDSP has focused on practical solution methods (e.g., [START_REF] Delling | Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems[END_REF][START_REF] Ding | Finding time-dependent shortest paths over large graphs[END_REF][START_REF] Kanoulas | Finding fastest paths on a road network with speed patterns[END_REF]). The effort on practical implementation issues is motivated by the need to get optimal paths in largescale time-dependent networks in only a fraction of a second. This is necessary both for the usual needs of web applications for route planning and to solve more complex problems such as vehicle routing problem in a time-dependent network. A recent review of these works is available in [START_REF] Gendreau | Time-dependent routing problems: A review[END_REF].

Our contributions

To answer the salesman problem presented above, we consider a TDSP in a consistent network where waiting is allowed and arc travel time functions are continuous and piecewise linear. In contrast to the unrestricted case introduced by Orda and Rom [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF], the total wait is bounded and each waiting period at a node is also bounded. More importantly, we do not seek to minimize the arrival time at destination but the total travel time. Stated otherwise, the waiting time is discounted from the arrival time at destination. This can be seen as a generalization of the problem studied by Foschini et al. [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF], where they also seek a minimum travel time path, but waiting is restricted to the origin. Our model is also related to one of the models studied in [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF][START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: Complexity, algorithms and implementations[END_REF][START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF], were waiting at each node is bounded, with the following differences. First, in addition to local waiting constraints, we also consider a global constraint. Second, [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF][START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: Complexity, algorithms and implementations[END_REF][START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF] focus only on integer values for the waiting times, while we consider both integer and continuous values for these. Last, the model of [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF][START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: Complexity, algorithms and implementations[END_REF][START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF] considers paths having lengths not greater than a given time horizon T (and provide algorithms polynomial in T ), while no such restriction appears in our model.

The main focus of this article is on the complexity of the TDSP with discounted waits. Our findings reveal that this small shift from classical assumptions yields complex issues with that respect.

Our first result is in the observation that the problem may not be in N P, since optimal paths may contain a number of arcs that is not polynomially bounded. Nevertheless, we show that the optimal paths have compact representations if the right derivatives are not too small. Using a reduction from the partition problem, we then show that the problem is N P-Hard if the graph is acyclic and the slopes in the pieces of arc travel time functions are restricted to the values -1, 0 and 1.

A more detailed study leads us to consider both integer and real-valued waiting times. We show that the two problems are equivalent if the slopes in arc cost functions are all integer. But a counter-example highlights that this is not true in general, even if the intervals defining the pieces of the arc travel time functions are integer. Nevertheless, we can bound the ratio between the optimal values of the two problems if the arc functions are lower bounded by a common value C min . This result is meaningful, because we develop a label setting algorithm that finds an optimal path in pseudo-polynomial time if waiting times are restricted to integer values. If n and m are the numbers of nodes and arcs in the graph, the algorithm runs in O(mW 2 + nW log(nW )) time. We also observe that an arbitrarily high precision can be obtained with this integer approximation by increasing the granularity of the time discretization.

As an alternative to this approach, we develop a pseudo-FPTAS having a complexity polynomial in the ratio of W to C min . The scheme is valid for both integer and real-valued waiting times.

, τ s

e ], where c s e ∈ Z, ρ s e ∈ Q and τ 0 e = 0. Let r max = max e∈E r e be the maximum number of pieces in the arc travel time functions. We also denote by the minimum and the maximum values of all travel times functions by C min = min e,t C e (t) and C max = max e,t C e (t), respectively. To simplify the exposure of some results of this paper, we assume throughout that C e (t) is never smaller than 1.

Assumption 1. C min ≥ 1.

Let P v be the set of all paths from o to v ∈ V . We study herein the cost of (p, w), where p = (v 1 (= o), v 2 , . . . , v |p| (= d)) belongs to P d , and w = (w 1 , . . . , w |p| ) is the vector of waiting times which belongs to

W(p, W ) =    w ∈ R |p| + : |p| k=1 w k ≤ W, w k ≤ W v k , k = 1, . . . , |p|    . When the path p = (v 1 , v 2 , . . . , v |p| ) is fixed, we introduce the notation C k := C v k v k+1 .
Since we wish to minimize total travel time, the cost of (p, w) can be expressed as

T (p, w) = |p|-1 k=1 C k (t k ), (1)
where t k is the departure time from node v k ; it is computed recursively as

t k = t k-1 + C k-1 (t k-1 ) + w k . (2)
Notice that T (p, w) for p ∈ P d is different from t |p| , which also accounts for the total waiting time up to node d. More precisely, the two quantities are related through the equation

T (p, w) = t |p| - |p| k=1 w k . (3)
The aim of the article is to study the complexity of the following two optimization problems. In most applications, we can assume that arc travel times are consistent: if we enter an arc e at time t ≤ t , then we leave the arc at time t + C e (t) ≤ t + C e (t ). Hence, unless stated otherwise, we assume throughout the paper that consistency holds. For the particular travel time functions we consider, this assumption can also be stated as follows. We suppose the following holds throughout the paper, apart from Proposition 8 from Section 8.

opt = min

Assumption 2 (Consistency assumption). Let ρ min = min e,s ρ s e . We have ρ min ≥ -1.

We shall sometime refer to the right-derivative of a one-variable function f (x) as ∂ + f (x).

Compact representation

Optimal solutions to WTDSP and WTDSP I may contain cyclic paths where one waits several times at the same node v provided that each waiting time does not exceed the upper bound W v .

In fact, we can construct examples in which the optimal path traverses a node W times. One such example is depicted in Figure 1. The optimal solution goes W times through the loop on node 1 to wait 1 at every stop at the node. This wait is made profitable by the decreasing travel time on arc (1, d). This implies that the problem may actually not be in N P since it may not be possible to compute the objective function in polynomial time. Of course, if the graph is acyclic, the previous situation never happens. Before proving the theorem, we introduce two technical results that bound the number of times any piece s of an arc e such that ρ s e = 0 can be hit along a path.

Observation 1. If G is acyclic, WTDSP is in N P. o C o1 = 1 C 11 = 1 1 W 1 = 1 d t C 1d 1 2W + 1 2W + 2
Lemma 1. Let (p, w) be a solution of WTDSP and assume that there exist

1 ≤ k 1 < k 2 < • • • < k q < |p| such that (v k i , v k i +1
), i = 1, . . . , q, are different repetitions of the same arc e and τ s-1 e ≤ t k i < τ s e , ∀i ∈ {1, . . . , q}. The following holds:

t kq+1 ≥ t k 1 + (c s e + ρ s e t k 1 ) q-1 i=0 (1 + ρ s e ) i .
Proof. We prove the result by induction on l. First assume that q = 1. We have

t k 1 +1 = t k 1 + C e (t k 1 ) + w k 1 +1 ≥ t k 1 + c s e + ρ s e t k 1 .
Hence the result holds. Now, assume that the result holds for some index q -1 ≥ 1 and assume that there is a q th repetition of e such that τ s-1 e ≤ t kq < τ s e . By definition of the travel time on arc e, we have

t kq+1 = t kq + c s e + ρ s e × t kq + w kq+1 .
To use the induction hypothesis, we rewrite this equality as

t kq+1 -t k 1 = t kq -t k 1 + c s e + ρ s e × t k 1 + ρ s e (t kq -t k 1 ) + w kq+1 = (1 + ρ s e )(t kq -t k 1 ) + c s e + ρ s e t k 1 + w kq+1
By non-negativity of travel and waiting times, we then notice that t kq ≥ t k q-1 +1 and w kq+1 ≥ 0, so the above yields

t kq+1 -t k 1 ≥ (1 + ρ s e )(t k q-1 +1 -t k 1 ) + c s e + ρ s e t k 1
We can then use the induction hypothesis to obtain

t kq+1 -t k 1 ≥ (c s e + ρ s e t k 1 ) × (1 + ρ s e ) q-2 i=0 (1 + ρ s e ) i + 1 = (c s e + ρ s e t k 1 ) q-1 i=0 (1 + ρ s e ) i .
For a given solution (p, w) where v k is the k th node on p, we say that e = (v k , v k 1 ) is nonconstant if τ s-1 e ≤ t k < τ s e and ρ s e = 0, and we call s a non-constant piece of e. We similarly say that e is constant if ρ s e = 0. Let us introduce the notation C s e = C e (τ s e ).

Lemma 2. Let (p, w) be a solution of WTDSP, and e a non-constant arc of p. If ρ s e = -1, piece s of e cannot appear more than once in p. Otherwise, the non-constant piece cannot appear in p more than log(C s e )-log(c s e ) log(1+ρ s e )

times.

Proof. Let (p, w) be a solution of WTDSP, and e ∈ p. We first assume that ρ s e = -1 and that there exists 1 ≤ k < |p| such that (v k , v k+1 ) = e and τ s-1 e ≤ t k < τ s e . Recall the assumption that C e (t) ≥ 1 for all t, which in turn implies that c s e > τ s e . By definition of the travel time function of e, we get

t k+1 = t k + C e (t k ) + w k = t k + c s e -t k + w k > τ s e , so the result holds. Let 1 ≤ k 1 < • • • < k q+1 < |p| be such that (v k i , v k i +1
), i = 1, . . . , q + 1, are q + 1 occurrences of piece s of e and suppose ρ s e > -1. In particular, this means that t k q+1 ≤ τ s e . Since t kq+1 ≤ t k q+1 , Lemma 1 implies that this inequality can be satisfied only if

t k 1 + (c s e + ρ s e t k 1 ) q-1 i=0 (1 + ρ s e ) i ≤ τ s e ⇔ t k 1 + (c s e + ρ s e t k 1 ) 1 -(1 + ρ s e ) q -ρ s e ≤ τ s e ⇔ t k
Similarly, if ρ s e > 0, we get that t k q+1 ≤ τ s e only if

(1 + ρ s e ) q ≤ C s e c s e + ρ s e t k 1 ≤ C s e c s e . (5)
Taking the logarithm of both sides of (4) and ( 5) yields the result.

We are now able to prove the main result of this section. ≤ λ log(C s e ) ≤ λ log(C max ). For a reasonable encoding of travel times, Lemma 2 thus ensures the solutions of WTDSP include a polynomial (in λ) number of non-constant arcs.

Consider some solution (p, w): p can then be described as the concatenation of a polynomial number of paths (p 1 , . . . , p q ), where only the last arc of p i can be non-constant for all i = 1, . . . , q.

Let σ e ∈ {1, . . . , r e + 1} index the -th constant piece of C e for each = 1, . . . , L e . Notice that L e ≥ 1 since the last piece of each travel time function is constant; denote L max = max e∈E L e . Let i ∈ {1, . . . , q}, and denote by (v i 1 , . . . , v iq ) the sequence of nodes in p i . If an arc e appears in position k ≤ |p i | -2 of p i , it is constant. Since the arrival time at the nodes of a path increases along the path, it is possible to identify L e + 1 positions

k 1 e ≤ k 2 e ≤ • • • ≤ k Le+1 e ≤ |p i |, such that
1. e first appears in p i at position k 1 e , and it last appears at position k Le+1 e -1;

2. each occurrence k of e in piece σ e is such that k

σ e e ≤ k < k σ e +1 e .
As a consequence, if we sort e∈p i ∈{1,...,Le+1} {k e } by ascending order, we can describe p i as the concatenation of at most mL max subpaths p 1 i , . . . , p r i and one non-constant arc such that, for all j ∈ {1, . . . , r}, every arc e ∈ p j i has the same travel time every time it appears in p j i . The above means that each subpath can be described with one array of size O(r max m) containing the number of times each arc appears in the subpath, and the waiting times on the subpath can be stored in another array of size O(n) containing the total waiting time at each node of the subpath. The travel and waiting times over a subpath are then computed in O(m) operations, so that the travel and waiting times along p i , i = 1, . . . , q, are computed in at most O(r max m 2 ) operations. By Lemma 2 and (6), q ≤ λr max m log(C max ), so the travel time of p can be computed in at most O(λr 2 max m 3 log(C max )) operations. Reciprocally, let (p, w) be a path described as the concatenation of a polynomial number of subpaths with waiting times separated by isolated arcs. Assume also that the subpaths are represented by two tables, one with the number of times each arc is followed and one with the total waiting time over each node of the subpath. The flow conservation constraints and the bounds on waiting time can be checked in O(m) operations on each subpath. It is also possible to check that the travel time of every arc of a subpath remains constant over the subpath by computing travel time at the start and at the end of the subpath. This is done in O(r max m) operations. As a consequence, the validity of (p, w) can be verified in a polynomial number of operations.

Hardness

We prove below that WTDSP and WTDSP I are hard, following a polynomial reduction from the classical number partitioning problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] (PARTITION). It is well known that PARTITION is N P-Complete, but it can be solved by an algorithm whose execution time is a polynomial in the sum of the weights of the items involved.

Proposition 1. The decision versions of WTDSP and WTDSP I are N P-Complete if G is acyclic and ρ s e ∈ {-1, 0, 1} for all e and s.

Proof. We consider below the case of WTDSP, the proof being similar for WTDSP I . From Theorem 1, WTDSP is in N P. We reduce PARTITION to the decision version of WTDSP in an acyclic graph to show that the latter problem is N P-Complete.

Consider an instance of PARTITION characterized by n integers a 1 , . . . , a n such that n i=1 a i = 2A. We build the corresponding instance of WTDSP by considering a graph G = (V, E) such that

V ={o, d} ∪ {1, . . . , n} ∪ {1 W , . . . , n W } E ={(o, 1), (o, 1 W ), (1 W , 1), (n, d)} ∪ n-1 i=1 {(i, i + 1), (i, (i + 1) W ), ((i + 1) W , (i + 1))},
where o and d are the origin and destination nodes, and {1 W , . . . , n W } are waiting nodes. The travel time of the arcs (i W , i) are constant and equal to A + a i for i = 1, . . . , n, and the arc (n, d) has a travel time function given by C nd (t) = A + |t -2(n + 1)A|. The upper arcs have a travel time equal to 2A and the travel times of (o, 1 W ) and of the arcs (i -1, i W ) are constant and equal to A for i = 2, . . . , n. The maximum total waiting time is W = A; the node maximum waiting times are W i W = a i , ∀i ∈ {1, . . . , n}, and zero for every other node. Figure 2 illustrates the instance of WTDSP described above.

For any solution (p, w) of the above instance of WTDSP, we denote I = {i : (i W , i) ∈ p}. We get a solution of PARTITION from a solution of WTDSP by summing the integers a i , i ∈ I. o n 1

W 1 W = a 1 2A A d C nd (t) 1 W A + a 1 A + a n W n W = a n n W 2A A 2A A Figure 2:
Reduction from an instance of PARTITION to WTDSP Departure time from n is then given by 2nA + i∈I (a i + w i ), so the expression of C nd yields

T (p, w) = 2nA + i∈I a i + A + i∈I (a i + w i ) -2A .
One readily verifies that T (p, w) = (2n + 2)A if i∈I a i = A and i∈I w i = A, and T (p, w) > (2n + 2)A if i∈I a i > A. If i∈I a i < A, the maximum waiting times at the nodes involve that i∈I w i ≤ i∈I a i , so

T (p, w) ≥ (2n + 1)A + i∈I a i + 2A -2 i∈I a i > (2n + 2)A.
As a conclusion, there exists a subset I ⊂ {1, . . . , n} such that i∈I a i = A if and only if the instance of WTDSP has a solution with total travel time equal to (2n + 2)A, which shows that the decision version of WTDSP is N P-Complete.

Fractionality matters

In this section, we study the relation between the optimal solutions of problem WTDSP and its restriction to integer waiting times, WTDSP I . While one can expect that the solutions to both problems are different in general, the following example shows that the ratio between their optimal values can be as large as 3/2.

Example 1. Consider the simple example drawn on Figure 3. One readily verifies that the optimal solution waits M -1 at node o and M -1 M at node 1, yielding a total travel time of 2 + 1 M . Moreover, the cheapest integer solution waits M -1 at node o and 0 node 1, and it has a total travel time equal to 3. Hence, for any > 0, the ratio between the two solutions is equal to 3/(2 + 1 M ), which is not smaller than 3/2 -if M is large enough.

The instance used in Example 1 is particularly pessimistic because its lowest travel times values are equal to 1. We show next that the ratio between the two objectives decreases with the increase of the minimum value of the travel time functions.

Proposition 2. Let C min = inf e∈E,t≥0 C e (t) ≥ 1. Then, opt I ≤ (1 + 1 C min ) opt.
To prove the result, we first show that the decreasing rates of T (p, w) along each variable w i are bounded below by -1. Let e k denote the vector with value 1 in coordinate k and 0 otherwise. Proof. Let p ∈ P v and let t and t be the vectors of departure times for w and w + δe k , respectively. By definition, t k = t k + δ and, since ρ min ≥ -

Lemma 3. Let v ∈ V . For any p ∈ P v and δ ≥ 0, T (p, w + δe k ) ≥ T (p, w) -δ. o max(2 -t M , 1) max(M + 2 -t, M t -M 2 -M + 1) d 1 W 1 = 1 W o = M -1
I ≤ T (p * , w * ) ≤ T (p * , w * ) + |p * | -1 ≤ opt + 1 C min opt = (1 + 1 C min ) opt .
Proposition 2 shows that the error made by restricting ourselves to integer values can be quite small for practical instances. Integer solutions may also happen to be optimal in the continuous variant. There are some cases in which we can predict that this will happen, as the instance used in the proof of Proposition 1. A particularity of this instance is that all slopes of functions C e are integer. Next, we prove that when this happens, WTDSP always has an integer optimal solution. Proposition 3. If ρ s e ∈ Z for all e and s, there exists an optimal solution to WTDSP with integer waiting times.

Proof. Let p = (v 1 (= o), v 2 , . . . , v |p| (= d)) be an optimal path and w ∈ W(p, w) the optimal waiting times. Notice first that Assumption 2 implies that ρ s e = -1, ρ s e = 0 or ρ s e ≥ 1 for each e ∈ E and s = 1, . . . , r e . Let us recall that

T (p, w) = |p|-1 k=1 C k (t k (w)), (7)
where t k (w) is the departure time from node v k using waiting times w. Suppose first that w is the unique fractional value of w along p and let ρ = ∂ + C e (t (w)) for e = (v , v +1 ). Three cases occur, depending on the value of ρ. ρ = -1. Define w = w . These waiting times are also feasible, because every maximum waiting time is integer.

Now, t k (w) = t k (w ) for each k < , so that C k (t k (w )) = C k (t k (w)) for k < . What is more, C (t (w )) = C (t (w)) -( w -w ).
This means that C (t (w )) ≤ C (t (w)) and t +1 (w ) = t +1 (w). From the latter, we get C k (t k (w )) = C k (t k (w)) for k > , which, combined to the former, yields T (p, w ) ≤ T (p, w).

ρ ≥ 1. We define w = w . We have

C k (t k (w )) = C k (t k (w)) (8)
for all k ∈ {1, . . . , -1}, and

C (t (w )) = C (t (w)) -ρ(w -w ). (9)
Applying Lemma 3 to the path (v +1 , . . . , v |p| ), we also have

|p|-1 k= +1 C k (t k (w )) ≤ |p|-1 k= +1 C k (t k (w)) + w -w . (10)
Combining ( 8), ( 9) and ( 10), we obtain T (p, w ) ≤ T (p, w). ρ = 0. Let ∈ { + 1, . . . , |p|} index the first node along p such that t lies in a non-constant piece of C e , where e = (v , v +1 ). If ρ s e = -1, define w = w so that t k (w ) = t k (w) for each k ≤ . Otherwise, define w = w so that t k (w ) = t k (w) for each k ≤ . Then, notice that because the breakpoints are integer and

∂ + C k (t k (w)) = 0 for all k ∈ { , . . . , -1}, we have C k (t k (w)) = C k ( t k (w) ) = C k ( t k (w) ), ∀k ∈ { , . . . , -1}. ( 11
)
The result follows by combining [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] with the analysis of the above cases applied to v instead of v to study

|p|-1 k= C k (t k (w )
). Suppose now that there are two or more components of w that are fractional, denoted { 1 , . . . , s }, and let ρ = ∂ + C e (t 1 (w)). In what follows, we build a solution that has a smaller number of fractional components and whose travel time is not greater than that of the original solution. Repeating the procedure yields an optimal integer solution. Only the departure times of nodes in {v 1 , . . . , v 2 -1 } are affected and these do not cross any of the (integer) breakpoints of their respective cost functions.

For the other two sub-cases, we define k = min{k : 1 < k < 2 , ρ k = 0}. If ρ k > 0, we define w as in the first sub-case. Otherwise, ρ k < 0, and we define w by transferring the fractional part from component 2 to component

1 until w 1 = w 1 or w 2 = w 2 .

Pseudo-polynomial-time algorithms

We now show how WTDSP I can be solved in pseudo-polynomial time, yielding also a pseudo-FPTAS for WTDSP. For any v ∈ V , let T I v (ω) be the minimum travel time among all paths from o to v whose waiting times are integer and total waiting times (not including the wait at node v) are equal to ω:

T I v (ω) = min p∈Pv min w∈W I (p,ω) T (p, w). ( 12
)
In particular, T I o (0) = 0 and T I o (ω) = +∞ for ω > 0. The main idea of the algorithm described in this section relies on defining T I v (ω) recursively along candidate paths. Considering a particular path p = (v 1 , . . . , v |p| ) ∈ P d and ω ∈ Z + , we have

T I v k (ω) = min ν∈[(ω-Wv k-1 ) + ,ω]∩Z T I v k-1 (ν) + C k-1 (T I v k-1 (ν) + ω)} , (13)
where ν ∈ [(ω -W v k-1 ) + , ω]∩Z guarantees that the wait at node v k-1 is at most W v k-1 . Combining the above recursion with a dynamic search for the optimal path, we obtain a dynamic programming (DP) recursion:

T I v (ω) =        min (u,v)∈E min ν∈{(ω-Wu) + ,...,ω} T I u (ν) + C uv (T I u (ν) + ω) v = o 0 v = o, ω = 0 +∞ v = o, ω = 0 (14)
To introduce a pseudo-polynomial-time algorithm, we first describe a simpler version of the problem that assumes that G is acyclic. Observe that the reduction of PARTITION we made in the proof of Proposition 1 involves an acyclic graph, so this assumption maintains N P-Completeness.

Proposition 4. If G is acyclic, opt I can be computed in O(mW 2 ) operations.
Proof. Since G is a directed acyclic graph, we can order its nodes such that (i, j) ∈ E ⇒ i ≤ j. Hence, recursion ( 14) can be solved in O(W 2 m) operations by computing the value function T I v (ω) according to the order of the nodes.

The DP recursion ( 14) cannot be used to solve the problem in general graphs. Specifically, the presence of cycles in G together with the fact that ω belongs to the inner minimization domain yields cycles in the graph that represents the states of the DP. Stated otherwise, one cannot define an order to fill the states of the value-function T I v (ω). We can overcome this issue by considering a label-setting algorithm, which allows for cycles in the solution.

Proposition 5. In general graphs, opt I can be computed in O(mW 2 + nW log(nW )) operations.

Proof. To prove the result, we solve WTDSP I with Algorithm 1 using a Fibonacci heap [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF]. The validity of the algorithm can be proved similarly to Dijkstra's algorithm, proving by induction on the cardinality of S that θ v (ω) = T v (ω) for each (v, ω) ∈ S.

We finish this section by mentioning that the above algorithms can be extended to provide a pseudo-FPTAS for opt. Let us introduce the notation Z/q = { z q : z ∈ Z}. We can refine ( 14) for the granularity Z/q as follows.

T q v (ω) =        min (u,v)∈E min w∈[(ω-Wu) + ,ω]∩Z/q {T q u (w) + C uv (T q u (w) + ω)} v = o 0 v = o, ω = 0 +∞ v = o, ω = 0 (15)
We can similarly adapt Algorithm 1 to the granularity Z/q. Next, we denote the optimal solution of the problem solved by [START_REF] Halpern | Shortest route with time dependent length of edges and limited delay possibilities in nodes[END_REF] as opt q = min ω∈[0,W ]∩Z/q T q d (ω). One readily verifies that computing opt q through (15) can be done in O(mq 2 W 2 ) operations in acyclic graphs. Similarly, adapting Algorithm 1 to the granularity Z/q leads to a time complexity of O mq 2 W 2 + nqW log(nqW ) operations. What is more, the next result shows that the approximation of opt provided by opt q is tighter than that provided by opt I .

θ o (0) = 0 θ v (ω) = +∞, v ∈ V, ω = 0, . . . , W, (v, ω) = (o, 0) S = ∅ // set of marked labels repeat (u, ω) = arg min (v,w)∈V ×{0,...,W }\S
{θ v (w)} // mark the label with minimum travel time

S ← S ∪ {(u, ω)} for (u, v) ∈ E do for ν = 0, . . . , min(W u , W -ω) do θ v (ω + ν) = min(θ v (ω + ν), θ u (ω) + C uv (θ u (ω) + ω + ν)) // update minimum travel times until u = d output: θ v (ω), v ∈ V, ω ∈ {0, . . . , W } Algorithm 1: Label-setting algorithm for WTDSP Proposition 6. Let C min = inf e∈E,t≥0
C e (t) ≥ 1. Then, opt q ≤ 1 + 1 q×C min opt.

Proof. Let (p * , w * ) be the optimal solution to WTDSP and (p * , q × w * /q) a feasible solution to its Z/q counterpart. We obtain

opt q ≤ T (p * , q × w * /q) ≤ T (p * , w * ) + |p * | q ≤ opt + 1 q × C min opt = 1 + 1 q × C min opt .
Considering the worst-case of Proposition 6 (C min = 1), we obtain a pseudo-fully polynomialtime approximation scheme for WTDSP.

A pseudo-FPTAS for bounded waiting times

Next we study approximation algorithms for WTDSP. Our first observation is that the problem may be hard to approximate in general because optimal solutions could contain pseudo-polynomially many arcs. The example below shows that solutions with polynomially many arcs cannot yield constant-factor approximations for the problem.

Example 2. Let γ(n) be a given polynomial function. Consider a set of instances built on the graph from Figure 1, with W ≥ γ(n). Then, for any integers K and L large enough, we define a specific instance as follows:

W o = 0, W 1 = K, W = L × K, C o1 (t) = C 11 (t) = 1, and C 1d (t) = max(L×(K +1)+2-t, 1
). The optimal solution to this instance contains L loops around node 1 and its total travel time is equal to L + 2. The best path, p, from o to d with length at most γ(n) is that having γ(n) loops around node 1. What is more, the total travel time of p is L + 2 + K(L -γ(n)). Hence, for any K, we can choose L large enough so that the approximation ratio provided by p is greater than 1 + K.

The difficulty of getting good approximate solutions in Example 2 is due to the large ratio between W and the minimum travel time C min , which we denote by α in what follows. Notice that assuming that α is constant still leads to hard optimization problems as the instances used in Proposition 1 have α = 1. The following example shows that optimal solutions can be approximated by the factor 1 + by paths having polynomially many arcs in n, m, α, and 1/ .

L = W α ; W ← W L ; W v ← Wv L for all v ∈ V ; C e (t) ← L -1 × C e (Lt)
W o = 0, W 1 = 1, W = K, C o1 (t) = C 11 (t) = K and C 1d (t) = max(K(K + 3) -t, K). Hence, α = 1.
The optimal solution contains K loops around node 1 and its total travel time is equal to K(K + 2). Yet, for any > 0, this modified example can be approximated by the factor 1 + by the path from o to d that contains min(K, 1/ ) loops around 1.

We now provide a pseudo-FPTAS, described in Algorithm 2. The latter follows the classical technique introduced by Ibarra and Kim [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF], where the parameters of the instance are rounded and the rounded problem is solved exactly (using Algorithm 1 in our case). In particular, Algorithm 2 involves rounded travel time functions C e (t) = L Similarly to (1), we then define

T (p, w) = |p|-1 k=1 C k ( t k ),
where w ∈ W(p, W ) and t k is the departure time from node v k computed recursively as

t k = t k-1 + C k-1 ( t k-1 ) + w k . (16)
The corresponding optimal travel time is denoted as opt. We see that T (p, w) can be easily related to T (p, L w).

Lemma 4. For any path p ∈ P d and w ∈ W(p, W ), we have T (p, w) = L -1 × T (p, L w).

Proof. Let t be the solution to recursion (2) for w = L × w ∈ W(p, W ), and t be the solution to recursion [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF] for w. We see by recurrence that t k = L -1 t k . Specifically, t 1 = w 1 = L -1 w 1 = L -1 t 1 , and

t k = t k-1 + C k-1 ( t k-1 ) + w k = L -1 t k-1 + L -1 C k-1 (L × L -1 × t k-1 ) + L -1 w k = L -1 t k .
Hence,

T (p, w) = |p|-1 k=1 L -1 × C k (L × L -1 × t k ) = L -1 T (p, w).
To compute the approximation ratio of Algorithm 2, we introduce the following notations. We define W = (W, W v : v ∈ V ) as the (n + 1)-tuple of all bounds on waiting times, and define similarly W = ( W , W v : v ∈ V ). Further, we let opt(W) be the optimal solution of WTDSP for the specific waiting times W; we define similarly opt I (W). The following result details how far opt I ( W ) is from opt(W). We skip the proof, because it is a straightforward adaptation of that of Proposition 2.

L = C min W α ≥ 1 .
Therefore, We conclude the section by discussing how to extend the pseudo-FPTAS to WTDSP I . If L ≤ 1, then W < α/ and the exact pseudo-polynomial-time algorithms run in polynomial time. Otherwise, we consider L = L in Algorithm 2, in which case the algorithm returns solution ( p, L w). The solution is feasible for WTDSP I and satisfies T ( p, L w) ≤ (1 + ) opt ≤ (1 + ) opt I .

T ( p, L w) = L × T ( p, w) (Lemma 4) = L × opt I ( W) (Definition of opt I ) ≤ L(1 + ) opt W L ( Lemma 5

Harder variants of WTDSP

Out of completeness, we consider the case the time-dependent network is not consistent (i.e., where Assumption 2 is not satisfied). This can be meaningful in applications where different modes of transport can be taken depending on departure time. It has been considered for instance by Orda and Rom [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF] in the context of telecommunications, where a message can be sent through different channels whose availabilities depend on time. Orda and Rom [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF] state that the problem is N P-Hard when no waiting time is allowed (W = 0). As in the rest of the literature, the authors aimed at minimizing arrival time, but without wait, this is equivalent to minimizing arrival time. A proof of N P-Hardness is given by Sherali et al. in [START_REF] Sherali | The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms[END_REF], where the reduction is made from PARTITION. The reduction is similar to that depicted in Figure 2, but they use a piecewise constant travel time function on the last arc. Below, we extend their result to the class of functions considered in this article, and we study the approximability of the problem.

Proposition 8. If we relax Assumption 2 in the definition of WTDSP, then, for any polynomialtime computable function γ(n), WTDSP cannot be approximated within a factor of γ(n) if P = N P, even when W = 0.

Proof. We reduce PARTITION to WTDSP to show the inapproximability result. For this, consider an instance of PARTITION characterized by n integers a 1 , . . . , a n such that n i=1 a i = 2A, and consider the corresponding instance depicted on Figure 4, where the travel time C e of each arc different from (n, d) is a constant function indicated on the figure. In addition, we define C nd (t) = (n + A + 1)γ(n)|t -n -A| + 1. If the answer to the partition problem is yes, we obtain a path of length n + A + 1; if it is no, there exists no path shorter than (n + A + 1)γ(n).

Another variant of WTDSP could be considered with more practical significance than relaxing Assumption 2. For all v ∈ V , the upper bound W v means that every time a path goes through v, it is allowed to wait at most W v . This means that in a cyclic path going k times through v, it is allowed to wait k × W v at v. This will not be relevant in some contexts, which is why we wish to consider the variant where it is allowed to wait only W v in total at each node v. This comes down to replacing the constraint

w k ≤ W k from the definition of W(p, ω) with k∈{1,...,|p|}:v k =v w k ≤ W v , ∀v ∈ V. (17)
The optimization problem we obtain by adding the above constraint to WTDSP is denoted as TWTDSP.

Proposition 9. The optimization problem TWTDSP is N P-Hard, and, for any polynomial-time computable function γ(n), it cannot be approximated within a factor of γ(n) if P = N P.

Proof. We prove the result by reduction from the classical HAMILTONIAN CYCLE problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

We consider an instance of HAMILTONIAN CYCLE described by a directed graph G = (V, E) and let γ(n) be any polynomial-time computable function. We also define β(n) = (2n + 3)γ(n).

As illustrated by Figure 5, we create an instance of TWTDSP by duplicating each node i of G into one in and one out node, i in and i out , so that one arc (i out , j in ) with constant travel time is

1 out 1 in o C 1 (t) i out i in to j in for all (i, j) ∈ E from k in for all (k, i) ∈ E to j in for all (1, j) ∈ E from k out for all (k, 1) ∈ E 2 C d (t) 1 1 1 1 1 1 1 1
W i out = 0 d W i in = β(n) -2 W 1 in = β(n) -2 W 1 out = 0 C i (t)
Figure 5: Reduction from HAMILTONIAN CYCLE to an instance of TWTDSP. created for each arc (i, j) of E. We also create one arc (i in , i out ) for each i ∈ V and define its travel time function as:

C i (t) =    (β(n) -1)(t -kβ(n)) + 1 if kβ(n) ≤ t ≤ kβ(n) + 1, k = 0, . . . , n -1 -t + (k + 1)β(n) + 1 if kβ(n) + 1 ≤ t ≤ (k + 1)β(n), k = 0, . . . , n -1 (β(n) -1)(t -nβ(n)) + 1 if t ≥ nβ(n)
The origin node o is connected to 1 in with constant travel time 2 and 1 in is connected to d with travel time function

C d (t) = max{-t + nβ(n) + 3, γ(n)(t -nβ(n) -2) + 1}.
Finally, the maximum wait is equal to β(n) -2 at nodes i in and 0 on the other nodes.

First, observe that if the departure time from a node i in is such that kβ(n)+1 ≤ t i in ≤ (k+1)β(n) for some k ∈ {0, . . . , n -1}, the expression of C i implies that t i in + C i (t i in ) = (k + 1)β(n) + 1. Since the arcs originating from the out nodes all have constant costs equal to 1, this involves that for k ≤ n -1, the departure time from the k th out node on a path is at least kβ(n) + 1. In particular, if v in n+1 is the (n + 1) th in node on a path, t v in n+1 ≥ nβ(n) + 2. As a consequence, if the path traverses (v in n+1 , v out n+1 ), the last piece of the arc travel time function involves that

C v n+1 ≥ β(n). (18)
Second, let (p, w) be a feasible solution, and denote as t(d -1) the departure time from 1 in before traversing (1 in

w i + nβ(n) + 3 if t(d -1) ≤ nβ(n) + 2 γ(n)(2t(d -1) -nβ(n) -2) + 1 if t(d -1) > nβ(n) + 2
From the maximum wait values and constraint [START_REF] Kanoulas | Finding fastest paths on a road network with speed patterns[END_REF], we also know that |p|-1

i=1 w i ≤ k(β(n) -2),
where k is the number of distinct in nodes in the path. In particular, this means that T (p, w) ≥ (2k + 3) + (n -k)β(n).

(

) 19
Now, if the answer to HAMILTONIAN CYCLE is yes, there is a path (v 1 , . . . , v n , v n+1 ) in G where v 1 = v n+1 = 1 and v 1 , . . . , v n are distinct nodes of G. Thus, we can build a solution (p, w) of TWTDSP where p = (o, v in 1 , v out 1 , . . . , v in n , v out n , 1 in , d) and |p|-1 i=1 w i = n(β(n) -2) (by waiting β(n) -2 at nodes v in i for i = 1, . . . , n). With this solution, we get T (p, w) = (2n + 3). Finally, assume that the answer is no. We first observe that there is a straightforward bijection between the cycles starting from node 1 in G and the set of paths that appear in the solutions of TWTDSP. This means that for any solution (p, w) of TWTDSP, either p goes through less than n distinct in nodes or it goes through at least n + 1 out nodes. In the former case, inequality [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF] shows that T (p, w) ≥ (2k + 3) + β(n) > γ(n)(2n + 3). In the latter case, inequality [START_REF] Kaufman | Fastest paths in time-dependent networks for intelligent vehiclehighway systems application[END_REF] applies on the (n + 1) th arc connecting an in node to an out node in p, which also proves that T (p, w) > γ(n)(2n + 3).

Observe that although constraint (17) guarantees a maximum total waiting time at each node, it does not exclude the possibility of a cyclic optimal solution. To see this, consider the simple example drawn on Figure 6. The costs of the arcs other than (2, d) are all constant and equal to 1, C 2d (t) = max{7 -t, 1}, and the bounds are W v = 0, ∀v = 3, and W 3 = 1. It is straightforward to verify that the optimal value is 6 by considering the solution defined as p = (o, 1, 2, 3, 1, 2, d) and w 3 = 1. The only acyclic path from o to d is (o, 1, 2, d) whose total travel time is equal to 7. It is also interesting to notice that adding constraint [START_REF] Kanoulas | Finding fastest paths on a road network with speed patterns[END_REF] does not change the optimal value of this instance. [4] K.L. Cooke and E. Halsey, The shortest route through a network with time-dependent internodal transit times, J. Math. Anal. Appl. 14 (1966), 493 -498.

T

  (p, w), (WTDSP I ) where W I (p, ω) = W(p, ω) ∩ Z [p| contains only integer waiting times.

Figure 1 :Theorem 1 .

 11 Figure 1: Instance where the optimal path traverses W arcs.

Figure 3 :

 3 Figure 3: Instance of WTDSP with a fractional solution.

ρ = - 1 . 1 = w 1 or w 2 = w 2 .

 112 Define w by transferring the fractional part from component 2 to component 1 until w We see similarly as above that T (p, w ) ≤ T (p, w). ρ ≥ 1. Define w 1 = w 1 and w k = w k for k = 1 . Using the same argument as above, we obtain T (p, w ) ≤ T (p, w). ρ = 0. Let us define ρ k = ∂ + C e (t k (w)) for each 1 < k < 2 . We consider three sub-cases. First, if ρ k = 0 for each 1 < k < 2 , then we define w by transferring the fractional part from component 1 to component 2 until w 2 = w 2 or w 1 = w 1 .

3 .

 3 for all e ∈ E; Run Algorithm 1 using W , { W v } v∈V and { C e } e∈E instead of W, {W v } v∈V and {C e } e∈E ; Let ( p, w) be the optimal solution and opt I the optimal value; return ( p, L w) Algorithm 2: Pseudo-FPTAS for WTDSPExample Consider another variant of the example from Figure1described by the integer K with

  -1 ×C e (Lt), ∀e ∈ E, and waiting bounds W = W L and W v = Wv L , ∀v ∈ V . For a given path p = (v 1 (= o), v 2 , . . . , v |p| (= d)) ∈ P d , we get the following set of feasible waiting times. W , w k ≤ W v k , k = 1, . . . , |p|    .

Lemma 5 .Proposition 7 .

 57 For any W ∈ R n+1 , we have optI ( W ) ≤ (1 + 1 C min ) opt(W ). Let α = W C min . Algorithm 2 is a pseudo-FPTAS for opt running in O mα 2 2 + nα log nα operations.Proof. Let (p * , w * ) be the optimal solution of WTDSP and ( p, L w) be the solution returned by Algorithm 2. Notice that the definitions of C e and α, imply that inf e∈E,t≥0C e = inf e∈E,t≥0 C e (t)

  ) ≤ L(1 + ) T (p * , w * /L) (Definition of opt) = (1 + )T (p * , w * ) (Lemma 4) = (1 + ) opt (Definition of opt)What is more, observing that W = α/ , we get that Algorithm 2 runs in

Figure 4 :

 4 Figure 4: Reduction from partition to show inapproximability.

  , d). The expression of C d gives T (p, w) = t(d -1) + C d (t(d -1)) -

Figure 6 :

 6 Figure 6: Instance of WTDSP with a cyclic solution.

  1, we see by induction that t ≤ t for all ∈ {k, . . . , |p|}. In particular, t |p| ≤ t |p| , and the result follows from (3).

	Proof of Proposition 2. Let (p

* , w * ) be the optimal solution to WTDSP and (p * , w * ) a feasible solution to WTDSP I . From the definition of C min we have |p * | -1 ≤ opt C min . Hence, we obtain opt


Camille Thévenin-Lemoine
email: camille.theveninlemoine@gmail.com

MD Louise Destombes

MD Julie Vial

MD Matthieu Wargny

MD Paul Bonnevialle

MD Yan Lefevre

MD, PhD Anne Gomez Brouchet

Jérôme Sales De Gauzy

MD Camille The ´venin-Lemoine

MD, PhD Jérome Sales De Gauzy

Planning for Bone Excision in Ewing Sarcoma: Post-Chemotherapy MRI More Accurate Than Pre-Chemotherapy MRI Assessment

Background: In determining the level of bone resection in Ewing sarcoma, the most suitable time at which to perform magnetic resonance imaging (MRI) remains controversial. Current guidelines recommend that surgical planning be based on MRI performed prior to neoadjuvant chemotherapy. The goal of this study was to determine whether pre-chemotherapy or post-chemotherapy MRI provides greater accuracy of tumor limits for planning bone excision in the management of Ewing sarcoma.

Methods: This was a single-center, retrospective study. MRI was performed using 3 sequences: T1-weighted, T1-weighted with contrast enhancement by gadolinium injection, and a fluid-sensitive sequence (STIR [short tau inversion recovery] or proton-density-weighted with fat saturation). The tumor extent as assessed on pre-chemotherapy and postchemotherapy MRI was compared with histological measurement of the resected specimen.

Results: Twenty patients with Ewing sarcoma of a long bone were included. In 6 cases, the tumor was located on the femur, in 5, the tibia; in 5, the fibula; and in 4, the humerus. The median patient age at diagnosis was 9.7 years. We found greater accuracy of measurements from MRI scans acquired after chemotherapy than from those acquired before chemotherapy. For both pre-chemotherapy and post-chemotherapy MRI, the greatest accuracy was achieved with the nonenhanced T1 sequence. There was no benefit to gadolinium enhancement. The median difference between T1 MRI and histological measurements was 19.0 mm (interquartile range [IQR], 4.3 to 32.8 mm) before chemotherapy and 5.0 mm (IQR, 2.0 to 13.0 mm) after chemotherapy. Adding a minimum margin of 20 mm to the limit of the tumor on postchemotherapy T1 MRI always led to safe histological margin.

Conclusions: Post-chemotherapy MRI provided a more accurate assessment of the limits of Ewing sarcoma. Surgical planning can therefore be based on post-chemotherapy MRI. Surgical cuts can be, at minimum, 20 mm from the limits as seen on MRI.

E

wing sarcoma is the second-most common type of malignant bone tumor in children [START_REF] Unni | Dahlin's bone tumors: general aspects and data on 11,087 cases[END_REF] . Conventional treatment includes neoadjuvant chemotherapy, local treatment, and adjuvant chemotherapy. Local treatment may consist of surgical resection and/or radiation therapy 2 . When possible, resection within healthy margins seems preferable to radiation therapy alone [START_REF] Givens | Non-metastatic Ewing's sarcoma: twenty years of experience suggests that surgery is a prime factor for successful multimodality therapy[END_REF][START_REF] Oberlin | French Society of Paediatric Oncology. Prognostic factors in localized Ewing's tumours and peripheral neuroectodermal tumours: the third study of the French Society of Paediatric Oncology (EW88 study)[END_REF] . Enneking 5 defined resection areas as "radical," "wide," "marginal," and "intralesional." Because of the importance of neoadjuvant chemotherapy in reducing the size of the tumor, the required size of the margins has come under reconsideration. The issue remains controversial in the literature. In a review of 244 patients, Ozaki et al. found no significant difference between adequate (radical and wide) and inadequate (marginal and intralesional) margins with respect to the local relapse rate and overall survival after surgery [START_REF] Ozaki | Significance of surgical margin on the prognosis of patients with Ewing's sarcoma. A report from the Cooperative Ewing's Sarcoma Study[END_REF] . In a review of 64 patients, Lin et al. assessed local control according to whether the margins were 0 to 2 mm, 3 to 9 mm, or ‡10 mm 7 . They found a trend toward better local control with wider as opposed to narrower margins, although this did not reach significance.

Magnetic resonance imaging (MRI), by improving the assessment of tumor limits [START_REF] Bloem | Radiologic staging of primary bone sarcoma: MR imaging, scintigraphy, angiography, and CT correlated with pathologic examination[END_REF] , is the gold standard for planning surgical margins. During the treatment of Ewing sarcoma, 3 MRI studies are generally performed: the first, at diagnosis, before the start of neoadjuvant chemotherapy; the

Planning for Bone Excision in Ewing Sarcoma

Post-Chemotherapy MRI More Accurate Than Pre-Chemotherapy MRI Assessment

Camille The ´venin-Lemoine, MD, Louise Destombes, MD, Julie Vial, MD, Matthieu Wargny, MD, Paul Bonnevialle, MD, PhD, Yan Lefevre, MD, Anne Gomez Brouchet, MD, PhD, and Jérome Sales de Gauzy, MD, PhD Investigation performed at Hôpital des Enfants, Toulouse, France second, during the course of chemotherapy; and the third, at the end of neoadjuvant chemotherapy, before local treatment. The intraosseous signal anomalies found on MRI may be related to tumor development but also to perilesional inflammation. Neoadjuvant chemotherapy can alter the signals of both the inflammation and tumor regions, but to an extent that is not known. It also remains unknown whether bone resection should be carried out at the level defined on the initial pre-chemotherapy MRI or as defined on the post-chemotherapy MRI, with the latter typically supporting a lesser and better defined resection. The current recommendation is to decide the limits of surgical resection using pre-chemotherapy MRI [START_REF] Gerrand | UK guidelines for the management of bone sarcomas[END_REF][START_REF] Jones | Effects of neoadjuvant chemotherapy on image-directed planning of surgical resection for distal femoral osteosarcoma[END_REF] to avoid the risk of contaminated resection margins.

The primary objective of this study was to determine which MRI study was more reliable for determining tumor extent: MRI performed pre-neoadjuvant chemotherapy or performed post-neoadjuvant chemotherapy. The secondary objective was to determine the most suitable MRI sequence. We compared the assessment of tumor limits on prechemotherapy and post-chemotherapy MRI with the limits as evaluated on histological analysis of the resected specimen.

Materials and Methods

T his was a single-center, retrospective study including pa- tients treated for Ewing sarcoma of a long bone between March 2005 and June 2015. Excluded were patients with a bone resection margin that was contaminated (classified as R1 or R2), because histological tumor limits could not be determined, or those with a pathological fracture, because the modification of bone orientation could result in noncomparable radiographic measurements.

An analysis of pre-chemotherapy and post-chemotherapy MRI scans was performed in a standardized manner by a senior radiologist. Three sequences were studied: T1-weighted, T1weighted with contrast enhancement by gadolinium injection, and a fluid-sensitive sequence (STIR [short tau inversion recovery] or proton-density-weighted with fat saturation [PD fat-sat]) (Fig. 1). For each sequence, we determined the tumor extent as delineated by abnormal compared with normal signal on the coronal sections. We considered that it was not possible to determine the difference between edema and tumor by MRI signal changes, so we therefore included all signal abnormalities. Once the tumor extent was determined, we measured the distance between the proximal and distal limits of the abnormal signal within the bone and the corresponding bone end (Figs. 2-A and2-B). The extension into the soft tissues was not part of the evaluation. These MRI measurements were performed for the study and were independent from the measurements used for surgical planning.

Histological analysis was performed by an experienced bone-tumor pathologist. We defined the limits of the tumor as the area beyond which the tissue was normal, i.e., without necrotic tumor and without a scar area that could contain tumor stigma as foamy macrophages or fibrous regions. On the resected specimen, we measured the distance between the tumor limits (proximal and distal) and the corresponding bone ends. When the end included the epiphysis, this histological measurement was sufficient. When the end was a bone cut, we added to the histological measurement the distance between the bone cut and the end of the residual bone as measured on postoperative computed radiography. The sum of these 2 distances corresponded to the distance of the tumor relative to the bone end (Fig. 2-C).

To evaluate MRI accuracy in determining the tumor limit, we chose to study the difference between each MRI measurement and the reference histological measurement. Thus, this difference was not dependent on bone length. Values were scored negative when the MRI limit was in a healthy zone relative to the histological limit and were scored positive when the MRI limit was within the tumor area.

Statistical Analysis

For descriptive analyses, we report frequencies and percentages for categorical variables and the median and interquartile range (IQR) for quantitative variables. We used the 1-sample Wilcoxon paired test to compare the results between pre-chemotherapy and postchemotherapy. The concordance between values of the different measures was assessed using Bland and Altman plots and Spearman correlation coefficients. Analyses were performed using R software (version 3.0.1; R Foundation for Statistical Computing).

Results

T wenty-two patients with Ewing sarcoma of a long bone were initially included. However, 2 patients were excluded, 1 because of a pathological fracture and 1 because of an intralesional resection (R2). In the latter case, prechemotherapy and post-chemotherapy MRI showed signal abnormalities where the surgical cut was made. It was therefore not a failure of MRI to identify the tumor limits. We analyzed the data of 20 patients, 15 children and 5 adults, with a median age at diagnosis of 9.7 years (range, 3 to 38 years). In 6 cases, the tumor was located on the femur; in 5, the fibula; in 5, the tibia; and in 4, the humerus. In some cases, measurements were not feasible for all of the sequences studied because of the quality of the images. Thus, of the 40 possible measurements for each sequence at each MRI assessment period, we report measurements from 38 T1, 36 STIR, and 36 T1 1 gadolinium-enhanced sequences from prechemotherapy MRI and 39 T1, 35 STIR, and 39 T1 1 gadolinium-enhanced sequences from post-chemotherapy MRI. The median duration between pre-chemotherapy MRI and surgery was 161 days (range, 93 to 315 days). The median duration between post-chemotherapy MRI and surgery was 13 days (range, 1 to 60 days).

Table I lists the difference between the MRI measurement (distance between the signal abnormalities and the corresponding bone end) and the histological measurement (distance between the proximal or distal extent of the tumor and the corresponding bone end) by MRI sequence for each patient.

We compared the distribution of the absolute values of these differences for all sequences studied and found greater accuracy of the measurements made using post-chemotherapy MRI compared with pre-chemotherapy MRI (Table II). The greatest accuracy was found for the nonenhanced T1 Fig. 2 Ewing sarcoma of the left tibia in an 8-year-old boy. Fig. 2-A Pre-chemotherapy T1-weighted MRI. The distance between the proximal end of the bone and the proximal limit of the tumor (x) and the distance between the distal end of the bone and the distant limit of the tumor (x') are indicated. *Difference between the MRI measurement (distance between the signal abnormalities and the corresponding bone end) and the histological measurement (distance between the proximal or distal extent of the tumor and the corresponding bone end) for each MRI sequence. STIR = short tau inversion recovery, and gado. = gadolinium.

sequences. There seemed to be no benefit from the addition of a contrast medium.

We then conducted a categorical analysis of the differences between MRI and histological measurements, with the differences categorized as follows: £210 mm, >210 to 0 mm, and >0 mm (Table III). For each MRI sequence, we also report the minimum and maximum difference between the MRI and histological measurements.

Using a threshold of 210 mm, the categorical analysis demonstrated a trend similar to that of an analysis of the average of the absolute values: values of £210 mm were more common for the pre-chemotherapy measurements. MRI limits within the tumor area were slightly more common for the postchemotherapy measurements but with much lower maximum values than for the pre-chemotherapy measurements (15 mm post-chemotherapy compared with values ranging from 51 to 60 mm pre-chemotherapy). On pre-chemotherapy MRI, the overvaluation of the tumor limits was sometimes important, up to 76 mm for the T1 sequence, with 4 values of >50 mm. In 2 cases, there was an underestimation corresponding to tumor progression during the course of chemotherapy (Fig. 3). On post-chemotherapy MRI, the underestimation of the tumor limits was always £15 mm.

Finally, we report the results as Bland and Altman plots, which demonstrate greater accuracy of post-chemotherapy assessment (Fig. 4). The Spearman correlation coefficients for the MRI-based measurements in relation to the histological measurements were high: before chemotherapy, 0.96 for T1, 0.94 for STIR, and 0.94 for T1 1 gadolinium enhancement; and after chemotherapy, 0.98, 0.98 and 0.99, respectively (p < 0.0001 for all). There were epiphyseal signal abnormalities in 12 cases on pre-chemotherapy MRI, and in 8 of those cases, abnormal signal persisted on post-chemotherapy MRI. However, pathological evaluation revealed epiphyseal extension of the tumor in only 2 of the 8 cases; in the remaining 6 cases, no epiphyseal abnormality was observed. Among the 4 cases in which the anomaly of epiphyseal signal was normalized on post-chemotherapy MRI, 1 resection with epiphyseal preservation was carried out, with R0 margins on pathological evaluation. This would not have been possible with surgical cuts planned according to pre-chemotherapy MRI (Fig. 5). In the 3 other cases, the epiphyseal bone pathology was strictly normal.

No local recurrence was diagnosed in any of the patients included in this study at the time of the latest follow-up (mean follow-up of 68 months; range, 24 to 111 months).

Discussion

W e found excellent correlation between MRI and histo- logical analysis in the assessment of tumor limits. Similar results were presented by Panuel et al. [START_REF] Panuel | Physeal and epiphyseal extent of primary malignant bone tumors in childhood. Correlation of preoperative MRI and the pathologic examination[END_REF] . Their study included 22 children (5 with Ewing sarcoma and 17 with osteosarcoma). Pathological analyses were compared with MRI performed up to 3 weeks before surgery. A transphyseal extension was evident on MRI in 13 cases (12 of the 17 patients with osteosarcoma and 1 of the 5 with Ewing sarcoma), which corresponded in all cases to an extension found histologically. There were no false-positive or false-negative cases. They recommended using primarily T1 sequences. Bloem et al. [START_REF] Bloem | Radiologic staging of primary bone sarcoma: MR imaging, scintigraphy, angiography, and CT correlated with pathologic examination[END_REF] compared the length of the tumor as measured on MRI with that of the histological specimen for 56 patients (including 27 with osteosarcoma, 14 with chondrosarcoma, and 10 with Ewing sarcoma). MRI measurements were acquired using T1 and T2 sequences; the timing of MRI in relation to neoadjuvant chemotherapy was not specified. The correlation coefficient was 0.99. The most precise type of sequence was not investigated.

The current study validates the use of postchemotherapy MRI to determine the tumor limits during the planning of bone cuts in the management of Ewing sarcoma. We found that the best sequence to determine the tumor limits was T1-weighted. Our results did not show any benefit of gadolinium enhancement. STIR sequences overestimated tumor limits because of their susceptibility to in-flammatory abnormalities. These results are similar to those of Panuel et al. [START_REF] Panuel | Physeal and epiphyseal extent of primary malignant bone tumors in childhood. Correlation of preoperative MRI and the pathologic examination[END_REF] . In our series, growth-plate signal abnormalities on pre-chemotherapy MRI disappeared after chemotherapy in 4 cases. This allowed surgery preserving the epiphysis in 1 case (Fig. 5).

Planning the resection using post-chemotherapy MRI allows for the possibility of tumor progression during the course of chemotherapy. In the case of progression, planning based on pre-chemotherapy MRI may lead to an incomplete resection. In our series, pre-chemotherapy MRI undervalued the tumor limit for 2 patients, with a difference of 20 mm for one and 60 mm for the other (Fig. 3). Similarly, there is sometimes a period of several weeks between the initial MRI and the beginning of chemotherapy, particularly when a problem of biopsy analysis arises. The tumor may progress in the meantime. Again, the initial MRI may undervalue the length of the bone segment to be resected.

Our study had limitations. This was a retrospective study, with a small number of cases (n = 20). However, this did not prevent the demonstration of significant differences between pre-chemotherapy and post-chemotherapy MRI measurements (Table II). In this study, we dealt only with bone limits. Therefore, our results do not suggest on which MRI to base planning regarding the extension to soft tissues. In addition, we chose not to analyze the tumor limit on MRI in the sagittal plane because we thought that measurements were less reproducible than in the coronal plane and that it would not dramatically improve accuracy. Finally, the time when the MRI was performed was variable, which may have affected the accuracy of the measurements.

We chose to study only Ewing sarcoma and not osteosarcoma, as inflammatory peri-tumor phenomena vary between the 2 types. They are often more important in Ewing sarcoma, which makes the choice of resection limits more difficult. These non-mass-like areas with abnormal MR signal intensity are often qualified as inflammation or edema. However, we know that there may be tumor cells in those areas. Masrouha et al. [START_REF] Masrouha | Correlation of non-mass-like abnormal MR signal intensity with pathological findings surrounding pediatric osteosarcoma and Ewing's sarcoma[END_REF] reported on 30 cases (27 osteosarcoma and 3 Ewing sarcoma) in which they found that 17.4% of these areas were positive for tumor (viable or necrotic). That is why we included all signal abnormalities in the MRI analysis.

Improving the accuracy of the assessment of tumor limits can permit reduction of safety margins. The objective is to expand the possibilities for epiphyseal conservation, for better durability of function of the reconstructed limb. Because of the possibility of the presence of tumor cells away from the main tumor, it seems necessary to maintain a margin beyond the limit suggested by post-chemotherapy MRI. We recommend a minimum margin of 20 mm, which, in our series, always allowed a resection in a healthy area. This recommendation is valid when there is no anatomical barrier separating the resection limit from the tumor. However, it can probably be further reduced when there is an anatomical barrier such as the physis. Previous studies showed the capacity of the physis to act as a barrier, limiting tumor extension [START_REF] Cañadell | Removal of metaphyseal bone tumours with preservation of the epiphysis. Physeal distraction before excision[END_REF][START_REF] Sales De Gauzy | Ewing sarcoma of the acetabulum in children: a "growth plate-based" surgical strategy[END_REF] , although it can sometimes be crossed [START_REF] Panuel | Physeal and epiphyseal extent of primary malignant bone tumors in childhood. Correlation of preoperative MRI and the pathologic examination[END_REF] . It is important to underline that the objective of the present study was to correlate MRI with histological evaluation, not to determine the amount of margin necessary. Despite there being no local recurrence among our patients, additional studies are needed to highlight prognostic factors.

In summary, the results of our study contradict the conventional recommendation: the determination of Ewing sarcoma bone tumor limits as assessed on postchemotherapy MRI seems more accurate than limits assessed on pre-chemotherapy MRI. We therefore recommend planning for bone excision in Ewing sarcoma using postchemotherapy MRI.

Fig. 1

 1 Fig. 1 Ewing sarcoma of the left femur in an 11-year-old boy, as demonstrated on pre-chemotherapy T1-weighted MRI (Fig. 1-A), post-chemotherapy T1-weighted MRI (Fig. 1-A'), pre-chemotherapy STIR MRI (Fig. 1-B), post-chemotherapy STIR MRI (Fig. 1-B'), pre-chemotherapy T1-weighted MRI with gadolinium enhancement (Fig. 1-C), and post-chemotherapy T1-weighted MRI with gadolinium enhancement (Fig. 1-C').

Fig. 2 -

 2 B Postchemotherapy T1-weighted MRI. The distance between the proximal end of the bone and the proximal limit of the tumor (y) and the distance between the distal end of the bone and the distant limit of the tumor (y') are indicated. Fig.2-C Histological measurements are shown. In this case, the proximal (z) and distal (z') measurements represent the distance between the respective tumor limit and the bone cut on the surgical specimen added to length of the residual bone as measured on computed radiograph.

Fig. 3

 3 Fig. 3 Ewing sarcoma of the left femur in a 23-year-old woman. Fig. 3-A Prechemotherapy T1-weighted MRI. Fig. 3-B Post-chemotherapy T1-weighted MRI, showing obvious tumor progression during the course of chemotherapy.

Fig. 4

 4 Fig. 4Bland and Altman plots of MRI-based measurements compared with measurements made by an anatomopathologist (AP). The continuous red line indicates the average difference (diff) between the considered MRI measurements and histological measurements. The dashed red lines indicate 2 standard deviations above and below the average difference.

Fig. 5

 5 Fig. 5Ewing sarcoma of the right femur in a 3-year-old girl. Fig. 5-A Pre-chemotherapy T1-weighted MRI, showing epiphyseal signal abnormalities. Fig. 5-B Postchemotherapy T1-weighted MRI, showing complete normalization of epiphyseal signal. Fig. 5-C Radiograph made 3 years after surgery. The epiphysis was preserved with healthy margins.

TABLE I Difference

 I Between MRI Measurement and Histological Measurement, by MRI Sequence*

						Difference (mm)
					Pre-Chemotherapy		Post-Chemotherapy
	Patient	Age (yr)		T1	STIR	T1 1 Gado.	T1	STIR	T1 1 Gado.
	1	10	Proximal	223	222	222	213	215	215
			Distal	28	228	234	24	24	24
	2	6	Proximal	220	224	224	28	212	26
			Distal	221	234	235	28	27	211
	3	10	Proximal	25	211		3	1	0
			Distal	229	236		215	213	29
	4	5	Proximal	242	246	241	236	234	232
			Distal	24	21	22	2	1	1
	5	11	Proximal	213	269	262	21	22	24
			Distal	213	213	246	26	25	28
	6	9	Proximal	22	211	23	24	23	22
			Distal	4	27	3	1	2	1
	7	9	Proximal	21	0	2	4	22	4
			Distal	241	230	226	214	212	7
	8	3	Proximal	233	229	235	21	214	210
			Distal	267	277	275	218	225	216
	9	6	Proximal	25	28	25	22		22
			Distal	20	215	2	1		210
	10	8	Proximal	276	276	278	0	1	0
			Distal	263	263	261	15	15	15
	11	13	Proximal	212		29	28		28
			Distal	234		224	217		218
	12	38	Proximal	232	238	240	221	218	221
			Distal	226	219	228	225	222	222
	13	14	Proximal	1	245	248	0	212	25
			Distal
	14	4	Proximal	232	242	242	28	213	220
			Distal	218	217	219	0	24	21
	15	9	Proximal	25	27	28	22	0	0
			Distal	234	289	281	249	257	257
	16	8	Proximal	224	234	234	28	27	25
			Distal	274	271	249	6	27	29
	17	24	Proximal	2	222	220	25	28	27
			Distal	218	218	210	213	211	215
	18	27	Proximal	2	220	26	21	24	219
			Distal	22	22	22	22	22	22
	19	23	Proximal	0	23	27	0	1	1
			Distal	60	53	51	25	28	214
	20	32	Proximal	22	22	22	22	22	22
			Distal				234	228	242

TABLE II Quantitative

 II Analysis of Differences between MRI and Histological MeasurementsAbsolute Value of Difference* (mm) The values are given as the median with the interquartile range in parentheses.

		Pre-Chemotherapy	Post-Chemotherapy	P Value
	MRI sequence
	T1 (n = 38)	19.0 (4.3-32.8)	5.0 (2.0-13.0)	<0.0001
	STIR (n = 34)	26.0 (11.5-44.3)	7.0 (2.0-13.0)	<0.0001
	T1 1 gadolinium (n = 36)	25.0 (6.8-43.0)	7.5 (2.0-15.0)	<0.0001

*

TABLE III Categorical

 III Analysis of Differences Between MRI and Histological Measurements

		£210 mm	>210 to 0 mm	>0 mm		Min./Max. Difference (mm)
		No.	%	No.	%	No.	%
	Pre-chemotherapy
	T1 (n = 38)	22	58%	10	26%	6	16%	276/60
	STIR (n = 36)	27	75%	8	22%	1	3%	289/53
	T1 1 gadolinium (n = 36)	23	64%	9	25%	4	11%	281/51
	Post-chemotherapy
	T1 (n = 39)	11	28%	21	54%	7	18%	249/15
	STIR (n = 35)	14	40%	15	43%	6	17%	257/15
	T1 1 gadolinium (n = 39)	15	38%	18	46%	6	15%	257/15


Hakima Khelifi
email: hakima@bit.edu.cn

Senlin Luo
email: luosenlin@bit.edu.cn

Boubakr Nour

Hassine Moungla
email: hassine.moungla@parisdescartes.fr

LQCC: A Link Quality-based Congestion Control Scheme in Named Data Networks

Information-Centric Networking (ICN) is a new communication paradigm that replaces the host addresses by the name of content; Named Data Networking (NDN) is a promising ICN architecture that has attracted research attention in recent years. NDN is a receiver-driven architecture implements pullbased communication in the form of one-interest-one-data. This model poses different challenges, especially from the transport layer perspective. In contact to IP-based networks where the congestion is handled in an end-to-end manner, NDN cannot apply the same concept, while most of the existing solutions are based on hop-by-hop connection. In this paper, we present a new congestion control mechanism for NDN based on link quality estimation. We focus our efforts to provide fast data transmission, decrease packet dropping rate, and maximize the link utilization. The simulation results show that our solution outperforms the NDN schemes in terms of throughput and drop packets.

I. INTRODUCTION

Recently, the research community is exploring new architectures for the future Internet. Information-Centric Networking (ICN) [START_REF] Xylomenos | A survey of information-centric networking research[END_REF], which is a content-oriented paradigm, has been proposed as a new model to replace the current host-centric paradigm. Several projects have been implemented under the umbrella of ICN, all of them focus on the use of the content name instead of the host address. Named Data Networking (NDN) [START_REF] Zhang | Named data networking[END_REF] is recent and active ICN project that rapidly gained a considerable research interest.

NDN uses hierarchical names to identify, request, and deliver the content in the network [START_REF] Nour | M2HAV: A Standardized ICN Naming Scheme for Wireless Devices in Internet of Things[END_REF]. It also uses three data structures namely Cache Store (CS), Pending Interest Table (PIT), and Forwarding Interest Table (FIB), to provide innetwork caching feature [START_REF] Khelifi | An Optimized Proactive Caching Scheme based on Mobility Prediction for Vehicular Networks[END_REF], ensure a simple receiver-driven data exchange, and provide a name-based routing, respectively. In NDN-based networks, a consumer initializes the communications by sending an interest packet, to request content by specifying its name. NDN nodes forward the interest packets hop-by-hop until reaching the original content producer, or any replicate node that has the content. The forwarding process is based on name-based routing rules and consulting both PIT and FIB tables; the former is used to keep tracing the path in order to use it in the data delivery phase, while the latter is used to select the next hop and forward the interest upstream. When content is available, the said node replies with a data packet that carries the content and the same requested name, and delivers back to the consumer(s) using the reverse path created by the interest. Moreover, NDN architecture uses different mechanisms and trust models to ensure data-integrity and authentication [START_REF] Khelifi | Security and Privacy Issues in Vehicular Named Data Networks: An Overview[END_REF]. However, and as illustrated in Figure 1, the NDN stack does not have a dedicated Transport layer. Hence, all transport mechanisms such as a reliable data delivery, link utilization, and congestion control must be treated by the Strategies and the Application layer.

NDN has been applied in different domains including Internet of Things [START_REF] Nour | A Distributed ICN-based IoT Network Architecture: An Ambient Assisted Living Application Case Study[END_REF], Vehicular Ad hoc Networks [START_REF] Khelifi | Named Data Networking in Vehicular Ad hoc Networks: State-of-the-Art and Challenges[END_REF], and Wireless Sensor Network [START_REF] Amadeo | Content-centric wireless networking: A survey[END_REF]. On the other hand, Link Quality Estimation (LQE) [START_REF] Audéoud | Quick and Efficient Link Quality Estimation in Wireless Sensors Networks[END_REF] is used to estimate and select the stable and reliable link over a set of candidate links that can be used to forward interest. LQE integrates different information and metrics to select the stable link. Indeed, choosing the stable link may increase end-to-end data delivery, avoid the congestion, and improve the overall network performance.

In LQE, there are two types of estimators: (a) hardwarebased estimators that are based on using signal strength of a received packet that is obtained directly from radio transceiver, and (b) software-based estimators that are collected via the persistent tracking of messages losses. The main advantage of this type of estimators is that they do not depend on specific hardware and correlate directly with the application layer [START_REF] Moungla | Distributed interference management in medical wireless sensor networks[END_REF], [START_REF] Ali | Distributed scheme for interference mitigation of WBANs using predictable channel hopping[END_REF]. The link quality estimation process consists of three steps:

1) Link Monitoring: three kinds of link monitoring can be used: active link monitoring, passive link monitoring, and hybrid link monitoring. 2) Link Measurements: are performed by retrieving useful information from received packets and acknowledgments, or from the sent packets such as sequence numbers, timestamp, Received Signal Strength Indication (RSSI), Link Quality Indicator (LQI), and packet retransmission count. 3) Metric Evaluation: metrics are evaluated based on the link measurements to produce an estimation of the link quality.

In this paper, we focus on the NDN transport layer issues, more specifically the congestion control and reliable communication. Hence, we apply the Link Quality Estimator to provide The remainder of the paper is organized as follows. Section II reviews the existing NDN congestion control solutions. Section III describes the used network model and the defined LQE metrics. Section IV details the proposed scheme and its working process. In Section V, we evaluate the proposed scheme and discuss the obtained results. Finally, Section VI concludes the paper.

II. RELATED WORK

NDN uses Interest/Data exchange model to retrieve content from multiple sources through multiple paths. Hence, network congestion can appear during the data transmission (on both content discovery or delivery phases). The traditional congestion control mechanisms that have been designed for end-toend communication model, cannot be adapted in NDN [START_REF] Chen | Transport Control Strategies in Named Data Networking: A Survey[END_REF]. Various research efforts have been shown in the literature addressing this issue, categorized as follows:

TCP-like Congestion Control Schemes: Carofiglio et al. [START_REF] Carofiglio | Optimal Multipath Congestion Control and Request Forwarding in Information-Centric Networks[END_REF] propose a delay-based congestion control mechanism. Authors define an interest window that is decreased based on the past RTT measurements. In addition, route-labeling and remote adaptive active queue management have been proposed to overcome the problem of mixing RTT from different packet sources. However, Nguyen et al. [START_REF] Nguyen | Efficient multipath forwarding and congestion control without route-labeling in CCN[END_REF] argue that route-labels have scalability and practicality issues. The number of potential routes increases exponentially when the number of nodes increases. Thus, authors propose a congestion control scheme by estimating the available bandwidth, without using route-labeling or any cooperation mechanism.

Implicit-Feedback Congestion Control Solutions: Schneider et al. [START_REF] Schneider | A Practical Congestion Control Scheme for Named Data Networking[END_REF] propose a practical congestion control scheme. This scheme measures packet queuing time to detect congestion, then marks certain packets to signal them to the consumer. Hence, the downstream routers can forward packets to alternative paths, while consumers can reduce their interest sending rates. In a similar manner, Nour et al. [START_REF] Nour | NNCP: A Named Data Network Control Protocol for IoT Applications[END_REF] propose a control protocol for NDN, they also introduce a Bottleneck Notification message to reduce the interest sending rate and avoid the congestion.

Hop-by-Hop Congestion Control Mechanisms: Other researches show their efforts in Hop-by-Hop Interest Sharing mechanism. This mechanism uses the interest sending rate in the opposite direction to control the number of data returning on its links. Carofiglio et al. [START_REF] Carofiglio | Joint hop-by-hop and receiver-driven interest control protocol for content-centric networks[END_REF] propose a joint Hop-by-Hop and Receiver-driven Interest Control Protocol. This protocol aims to control user requests using per-flow in each output interfaces at every router. This will improve the network scalability and overall performance. Similarly, Wang et al. [START_REF] Wang | An improved hop-by-hop interest shaper for congestion control in named data networking[END_REF] propose a hop-by-hop interest shaping algorithm for NDN. This solution is based on controlling the interest packet rate by taking into account the interdependence between interests and contents in opposite directions. Hence, it tends to maximize the use of available bandwidth, and minimize the loss of content packets.

Shaping-based Congestion Control Solutions: Lei et al. [START_REF] Lei | A RCP-Based Congestion Control Protocol in Named Data Networking[END_REF] propose a shaping-based algorithm that combines Rate Control Protocol (RCP), rate-based, hop-by-hop, and explicit congestion control algorithm. The objective of the proposed algorithm is to achieve a high link utilization, and increase overall network throughput. Zhou et al. [START_REF] Zhou | A proactive transport mechanism with explicit congestion notification for NDN[END_REF] propose an Explicit Congestion Notification based on proactive interest sending rate control mechanism. All receivers send their RTT measurements to the routers to calculate the available bandwidth, and adopt a smart forwarding using Software Defined Network-style controller to select the best forwarding path. Wang et al. [START_REF] Wang | C3PO: Computation Congestion Control (PrOactive)[END_REF] design a passive and proactive mechanism that aims to distribute the computation among different routers, and hence avoid the congestion in the network. The scheme takes advantage of the available resources in a neighborhood to balance the service load, and reduce service latency and request drop rate. Miyoshi et al. [START_REF] Miyoshit | Multi-Source Congestion Control for Content Centric Networks[END_REF] propose a Multi-Source Congestion Control scheme that is based on the combination of consumer window control and router-assisted branch probability control.

Although the aforementioned solutions, most of them take only one (static) metric into consideration, or try to bring IP-based congestion mechanisms to NDN network. In fact, none of them consider the link quality with multiple dynamic metrics. To authors' best knowledge, there are no existing efforts on NDN and LQE. This paper proposes a congestion control scheme based on LQE to reduce the packet dropping rate and maximize the link utilization.

III. SYSTEM DESCRIPTION

The network congestion control is one of the most important aspects of networking [START_REF] Ren | Congestion control in named data networking -A survey[END_REF]. In this section, we describe in detail our proposed congestion control mechanism. In fact, we apply Link Quality Estimator on top of NDN network, and define four methods that can deal with different cases. Combined all methods, we achieve a high link utilization, fast data transmission, as well as a low packet dropping rate.

A. Network Model

Consider a connected multi-hop network modeled by a directed graph G = (N, L) comprising a set nodes N and links L. A connection link l ∈ L between two nodes (i, j) ∈ N is denoted by l i, j , we denote B and U, the bandwidth and link utilization of link l i, j , respectively. Also we denote LQ as the link quality value of link l i, j . In addition, define a new data structure namely Link Quality Table (LQT ) where nodes store all LQ values. Table I provides a summary about the notations used in this paper.

B. LQE Metrics

For a give node n ∈ N , I(t) denotes the interest sending rate at time t over the link l, where D(t) denotes the data delivery rate at time t. Let C o be the size of data occupied on the local cache, and C f the free cache size. V = {0, 1} is a boolean variable indicating if the node will move to another network or not.

According to the status of NDN network, we define three dynamic LQE metrics:

1. Data Reception Rate (DRR): The Data Reception Rate (DRR) metric is calculated at the consumer level, and measures the average of successfully received data. DRR is defined as follows: In order to control the congestion in NDN network, we define two thresholds: Avoid Congestion Value (ACV), and Congestion Value (CV). When LQ reaches the ACV value, the node sends a notification packet to all connected consumers in order to reduce their interest sending rate. This mechanism is used to avoid the congestion before it happens. Otherwise, if the LQ reaches CV value, here we distinguish two cases based on the number of available paths (faces): (i) one-path scenario: we enable data caching and hop-by-hop fragmentation, (ii) multi-path scenario: an alternative path from LQT table is selected based on the highest value. A pseudo-code of LQCC scheme is presented in Algorithm 1, and detailed as follows:

DRR = Number of
Step 1 -Persistent Link Monitoring: By using the aforementioned link quality metrics, we monitor each link l i, x ∈ L, and store their estimated LQ in LQT . LQT table contains the name of the interface and link quality value. We sort the table based on the link quality values to achieve a fast selection of an alternative path in case of congestion. To calculate LQ value, we define our function as the sum of bandwidth, link utilization, mobility, and cache capacity, as well as the metrics (DRR, DSR, and, IRR). The result is an estimation of the link quality. If LQ reaches mathcal ACV the Step 2 is applied. Otherwise, if LQ reaches the CV, then the Step 3 or Step 4 is applied according to the context. The node updates this value for each incoming interest or data packet. The calculation of LQ is based on the node type, and is presented in the following cases:

(1) Consumer node: from the consumer side, the link quality LQ is calculated by using the proposed metric DRR, and U, C, V and D(t), and is defined in the following equation:

LQ = αDRR + βD(t) + γU + δC + θV
(2) Intermediate node: from the intermediate node side, the LQ is calculated by using the defined metric DSR, and U, C, V, and D(t), and is defined in the following equation:

LQ = αDSR + βD(t) + γU + δC + θV
(2) Data producer node: from the data producer node, the link quality LQ is calculated by using the defined metric IRR, and U, C, V, and I(t), and is defined in the following equation:

LQ = αIRR + βI(t) + γU + δC + θV
Where α, β, γ, δ, and θ are weigh parameters that may be used to balance the preferable metrics, with the constraint that

(α + β + γ + δ + θ) = 1
Step 2 -Congestion Avoidance: During the data retrieval, when the link quality LQ ≥ ACV, the node n sends a notification packet to all directly connected nodes in the said interface informing them to reduce their interest sending rate. This notification packet format is inherited from the regular interest packet, and contains the coefficient of the delay α. If the congestion is still happing, the node re-sends another notification packets, with another bigger coefficient α < α. It is important to highlight that notification packets are not rout-able, they are used only by the neighbor nodes.

Step 3 -Congestion Detection: In case of the congestion is still happening after Step 2, and the link quality LQ ≥ mathcalCV. We propose two different mechanisms based on the type of communication:

1) Single-Path Communication: if a node n has only one path/interface (Figure 2(a)), we apply a hop-by-hop fragmentation mechanism (Step 4). We take the benefits of content naming and caching to enable this feature. It is worth noting that the content integrity and security are preserved by using the content-based security concept adopted in NDN design. 2) Multi-path Communication: if a node n has more than one path/interface p (Figure 2(b)), we select the best alternative link (interface) by consulting the LQT table. value (Maximum Transmission Unit) if needed, while the next hop assembles the packet immediately. Also, each segment is signed separately by the node who fragment the content. In case of losing a fragment, the node sends a simple interest packet that carries the content name as well as the segment number for the requested segment. This interest is satisfied by the node who applied the fragmentation.

Naming Convention: during the fragmentation phase, we use the same NDN hierarchical naming scheme. However, we extend it by adding the number of the segment at the end of naming (naming := naming/SegNumber). In case of transmitting the last segment, we add the flat F I N to indicate that all segments have been sent (naming := naming/SegNumber/F I N) and the next node can assemble them.

V. PERFORMANCE EVALUATION

We have implemented the LQCC scheme on top of ndnSIM [START_REF] Afanasyev | ndnSIM: NDN simulator for NS-3[END_REF], which is an NS3-based simulator for NDN. We have used the bottleneck topology that illustrated in Figure 2, and benchmarked the LQCC against NDN forwarding strategies (i.e., Best-route, NCC, Multicast, and Broadcast). Figure 3 illustrates the path selection for LQCC and bestroute scheme. Here, we emphasize on best-route only as the other schemes (i.e., NCC, Multicast, and Broadcast) produce the same results in the bottleneck topology.

A. Simulation Metrics

We have made a comparison in terms of throughput, the number of drop packets, and end-to-end delay:

• Throughput: has been measured as the size of wellreceived data in compared to the requested interests. • Number of Drop Packets: is measured as the total number of dropped packets in the network including data and interest packets. • End-to-End Delay: is used to evaluate the network performance and calculated as the of sending interest and receiving its corresponding data packet.

B. Simulation Results

In the following, we discuss the obtained numerical results: Figure 4 shows the throughput measurement results. In contrast to NDN that uses only one static metric (e.g., a small 1.5 number of hops regardless of the link status), we observe that LQCC scheme achieves a better throughput as it selects the stable link based on different dynamic metrics to avoid the congestion.

Figure 5 shows the drop packets measurements in a bottleneck link. Results are plotted for two scenarios: singlepath (Figure 5(a)), and multi-path (Figure 5(b)). As the path selection in NDN is limited to the number of hops, more packets are dropped in both scenarios. However, LQCC integrates different dynamic metrics to select the best path (according to the current network status) in case of multi-path and hop-byhop fragmentation in the case of single-path, hence it did not drop any packet during the communication.

The end-to-end delay measurements are represented in Figure 6. We observe that the delay in NDN is smaller than LQCC scheme. We argue this by the fact that NDN uses the short path (in terms of hops) regardless of the path reliability or stability during the data forwarding, while LQCC uses the optimal and stable path that can forward the data with higher throughput, fewer drop packets, and a reasonable delay.

VI. CONCLUSION

In this paper, we propose a Link Quality-based Congestion Control (LQCC) scheme for Named Data Networks in order to avoid congestion in the network and achieve an efficient data delivery. We define different dynamic metrics related to NDN communication. These metrics, along with other metrics such as link utilization, cache store, and the mobility impact, are used to select the optimal and stable path that can be used to forward the interest and deliver that data without facing any congestion issues. Simulation results show that LQCC achieves an optimal throughput and fewer drop packets. Moreover, the proposed scheme can be integrated with different wired and wireless environment including Internet of Things, and vehicular applications. As future work, realworld implementation of LQCC is planned with a large-scale network.

Step 4 -Fig. 2 :

 42 Fig. 2: Bottleneck Network Topology. (a) single-path, (b) multi-path.

Fig. 3 :

 3 Fig. 3: Forwarding Path

Fig. 4 :

 4 Fig. 4: Throughput Measurement.

Fig. 5 :

 5 Fig. 5: Drop Packets Measurements: (a) single-path, (b) multipath.

Fig. 6 :

 6 Fig. 6: Network Delay Measurement.

Every Node Individual Apps Individual Links Host Centric Model Content Centric Model

	Application (HTTP, FTP, RTP)	Application (Browser, Chat, File stream)
	Transport (TCP, UDP)	Security
	IP	NDN
	(IPv4, IPv6)	(Content Name)
		Strategy
	Data Link	(Forwarding, Caching,
	(LLC, PPP, CSMA/CD)	and replacement
		strategies)
	Physical	Physical
	(Wifi, Ethernet, 802.11)	(Wifi, Ethernet, 802.11)
	Fig. 1: Host Centric Model VS Content Centric Model
	a reliable data delivery along the best path, and maximize
	the link utilization. We define new dynamic metrics that have
	a direct impact on the best alternative link selection, rather
	than using only one or two static metrics such as bandwidth
	or Round-Trip Time (RTT). Thus, we propose Link Quality-
	based Congestion Control (LQCC) scheme that can be coupled
	with the smart NDN forwarding plane to persistently monitor
	the connected links, detect the congestion in the earlier phase,
	avoid the congestion based on the link metrics, and provide
	hop-by-hop fragmentation. The simulation results show that
	LQCC scheme outperforms the existing NDN forwarding
	schemes in terms of throughput, and less packet drops.

TABLE I :

 I Notations used throughout this paper.

	Notation	Definition
	l i, j	Link between nodes i and j
	B	Bandwidth
	U	Link utilization
	L Q	Link quality
	C i	Cache capacity for node i
	C o	Occupied cache size
	C f	Free cache size
	I(t)	Interest sending rate
	D(t)	Data delivery rate
	V	Mobility variable
	D R R	Data Reception Rate
	I S R	Data Success Rate
	I R R	Interest Reception Rate
	A C V	Avoid Congestion Value
	C V	Congestion Value

TABLE II :

 II Simulation Parameters

	Parameter	Settings
	Scenario	Bottleneck
	No. of Nodes	[1, 12]
	No. of Routers	[1, 4]
	Packet size	1024 Kbyte
	Capacity	[10, 100] Mbps
	Sim. Time	30 sec
	CS Buffer Size	1000 pkts
	Interest Rate	500 Interest/sec

ACKNOWLEDGEMENTS

The work of S. Luo was supported by the National 242 Project under Grant No. 2017A149. Dr. Luo is corresponding author.