Jean-Bernard Baillon

J-B Baillon

R Cominetti

Markovian traffic equilibrium

come

Introduction

Traffic assignment models describe the way in which the transportation demands flow through a given network. Users are supposed to behave rationally and to travel along the shortest available paths [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]Wardrop's principle]. However, because of congestion the path costs are themselves influenced by the flows and therefore the models give rise to equilibrium or fixed point problems.

Assignment models can be classified as deterministic or stochastic depending whether all users perceive the same costs or there is some variability among the population. In the first case the shortest paths connecting a given origin-destination pair (OD) are the same for all users and the flow distribution rule is deterministic, while in a stochastic setting the shortest paths depend on the particular user under consideration leading to a flow distribution principle based on random utility theory. Despite the similarity of both situations, the mathematical formulations found in the literature are rather different and both approaches remain somewhat disconnected. In this paper we describe a unifying framework for deterministic and stochastic traffic assignment, in the form of an unconstrained convex minimization problem that encompasses both types of assignment simultaneously. In this approach, the deterministic assignment becomes a particular instance of the stochastic assignment.

Stochastic route choice models can be traced back to Dial [START_REF] Dial | A probabilistic multipath traffic assignment model which obviates path enumeration[END_REF] where the demand on each OD pair is distributed among routes according to a logit discrete choice model. To reduce the computational burden of path enumeration, the choices are restricted to a smaller set of efficient routes, namely those for which each arc leads farther away from the origin and gets closer to the destination. This approach, further investigated in [START_REF] Trahan | Probabilistic assignment: an algorithm[END_REF]Trahan] and [START_REF] Sheffi | An algorithm for the equilibrium assignment with random link times[END_REF]Sheffi and Powell], was conceived for the flow-independent case and assumes route costs to be independent Gumbel random variables. Since independence is an unlikely assumption when dealing with overlapping routes, Daganzo and Sheffi [START_REF] Daganzo | On stochastic models of traffic assignment[END_REF] proposed an alternative model based on a probit stochastic assignment which was solved by Montecarlo simulation. On a different direction, Dial's logit-based model was extended to the case of flow-dependent arc costs in [START_REF] Fisk | Some developments in equilibrium traffic assignment[END_REF]Fisk], where an equivalent optimization problem was found. The latter was formulated in the high dimensional space of route flows and the method of successive averages was proposed as a practical numerical scheme. Alternative methods based on a dual formulation and which do not require path enumeration were investigated in [START_REF] Larsson | A dual scheme for traffic assignment problems[END_REF]Larrson,Liu and Patrickson]. Finally, we mention an attempt to extend the stochastic assignment to the case of transit networks in [START_REF] Nguyen | Implicit enumeration of hyperpaths in a logit model for transit newtorks[END_REF]Nguyen et al]. For a more complete account on deterministic and stochastic traffic assignment we refer to the surveys of Florian and Hearn [START_REF] Hearn | Network equilibrium models and algorithms[END_REF][START_REF] Hearn | Network equilibrium and pricing[END_REF].

A common feature of all the mentioned works is that each user on a given OD pair directly selects an optimal route by comparing it with all the available routes. From a modelling perspective this has several drawbacks. Firstly, partial information and limited discrimination capacity of the users suggest that the choices should be restricted to a few "reasonable" routes, but then defining a priori which routes should be considered is not obvious specially since travel times are flow-dependent. On the other hand, as already mentioned the logit-based models assume the independence of route costs which is unreasonable when dealing with overlapping routes, and also both logit and probit models distribute flows among all the available routes no matter how large their travel times are. Finally, models requiring path enumeration are computationally impractical for large networks.

In this paper we consider an alternative approach which is still based on discrete choice models but imbedded in a dynamic programming framework: route choice is no longer seen as an issue to be solved once and for all at the origin of each trip, but instead we consider it as the outcome of a sequential process of selection of arcs at every intermediate node. Passenger movements are then governed by an embedded Markov chain and therefore we call this type of assignment a Markovian Traffic Equilibrium or MTE. The idea is similar to the logit Markovian assignment of [START_REF] Akamatsu | Cyclic flows, Markov processes and stochastic traffic assignment[END_REF]Akamatsu] except that we consider general discrete choice models and at the same time we provide a compact dual characterization which seems more easily amenable to large scale computations. This approach does not require independence of the random route costs, and the number of alternative arcs to be considered at each node remains within the discrimination capabilities of the users with no need for arbitrarily reducing the set of possible routes. Moreover, by appropriately choosing the discrete choice models one can force the equilibrium assignments to use only nearly optimal routes and not every route as in the logit or probit route-based setting. Finally, the model avoids path enumeration and leads to computational procedures which are effective even for large networks.

An additional advantage of the MTE model is its flexibility to deal with different discrete choice models at every node, and even to mix deterministic and stochastic assignment rules within the same model. In particular, by considering multi-modal networks the approach applies directly to model the simultaneous selection of mode and route. Also, the case of elastic demands may be treated as usual by adding no-trip arcs connecting directly each OD pair with travel cost equal to the inverse of the demand function.

The paper is structured as follows. Section §2 sets the notation and reviews the basics of deterministic traffic equilibrium, describing its equivalent formulation in terms of a primal and a dual optimization problems. Section §3 then introduces the MTE model and establishes an analog characterization which has exactly the same form as the deterministic dual characterization, providing a unified framework for both types of equilibrium. This dual program is unconstrained, strictly convex and coercive, implying the existence and uniqueness of an MTE. In the stochastic case the dual turns out to be smooth, and since it is also low dimensional (one variable per arc) it opens the way to solve large networks. Some extensions of the basic MTE model are briefly described in section §4, while section §5 reports some preliminary numerical results comparing the performance of the well known method of successive averages (which is interpreted as a variable metric gradient scheme) and Newton's method. These experiments show that the model is solvable even for large networks. We conclude the paper in §6 by giving sufficient conditions for the convergence of the method of successive averages. Appendix A at the end of the paper provides an analytical characterization of discrete choice models which plays an essential role in our analysis, while Appendix B computes the Hessians required to implement Newton's method.

Deterministic traffic equilibrium

Let G = (N, A) be a directed graph representing a traffic network, and D ⊆ N a set of destinations. Given the demands g d i ≥ 0 from each node i = d to each destination d ∈ D, a traffic assignment model seeks to predict how these demands flow throughout the network. More precisely, if we let R d i denote the set of simple paths connecting i to d (assumed nonempty) and writing R for the union of the R d i 's, the problem is to determine an "efficient" path-flow assignment h = (h r ) r∈R with non-negative entries h r ≥ 0 and satisfying the flow conservation constraints

g d i = r∈R d i h r ∀ d ∈ D, i = d. ( 1
)
The efficiency of a path r ∈ R is measured by its generalized cost

c r = a∈r t a ( 2
)
where t a = s a (w a ) represents the travel time or generalized cost of arc a as a strictly increasing continuous function of the total flow on that arc, namely s a : [0, ∞) → [0, ∞) and

w a = r a h r . (3)
A deterministic model assumes that all users perceive the exact costs c r , and then an efficient assignment is characterized by the fact that only shortest paths are used [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]Wardrop].

(∀ r ∈ R d i ) h r > 0 ⇒ c r = τ d i
where c r is given by (2) and τ d i = min r∈R d i c r , with t a = s a (w a ).

These equilibria are characterized [START_REF] Beckman | Studies in Economics of Transportation[END_REF]Beckman et al.] as the optimal solutions of the convex program

(P H ) m i n (w,h)∈H a∈A wa 0 s a (z) dz.
Since H is compact there exist optimal solutions, while strict convexity implies that the optimal w * is unique, although there may exist several path-flow assignments h which correspond to this w * . We loosely refer to w * as being "the" equilibrium flow.

Arc-flow formulation

As the number of paths is usually very large, the formulation (P H ) is computationally inefficient. An alternative formulation is obtained by considering variables v d a ≥ 0 representing the flow on arc a heading to destination d, and the set V of pairs (w, v) ≥ 0 satisfying the flow conservation constraints

g d i + a∈A - i v d a = a∈A + i v d a ∀ d ∈ D, i = d (4)
as well as the total flow relations

w a = d∈D v d a ∀ a ∈ A. ( 5
)
Clearly, to every feasible assignment (w, h) ∈ H it corresponds a unique pair (w, v) ∈ V by setting v d a = {h r : a ∈ r, r ∈ R d i , i = d}. However, not all elements in V are of this form since the latter allows flow along cycles which may be forbidden in H. In any case, the convex program

(P V ) m i n (w,v)∈V a∈A wa 0 s a (z) dz
is a relaxation of (P H ) with the same optimal w * . Moreover, any v with (w * , v) ∈ V is optimal and the sets {a ∈ A : v d a > 0} are cycle-free so that v may be decomposed into path-flows h r satisfying (1) and (3) (see e.g. [START_REF] Ahuja | Network flows[END_REF]Theorem 2.1]). Any such decomposition gives an equilibrium and, conversely, every equilibrium is of this form.

Dual formulation

The main point when computing a traffic equilibrium is then to find the optimal arc-flow vector w * . A dual problem which provides an alternative for this was described in [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF]Fukushima]. We slightly re-formulate the latter in a form which is more convenient for comparison with the MTE model to be presented in the next section. For the sake of completeness we provide a short proof of the equivalence. The dual variables are the arc travel times t a for a ∈ A and the time-to-destination variables τ d i for d ∈ D and i = d. For notational convenience we set τ d d = 0 (considered as a constant rather than a constrained variable) and we let T denote the set of all vectors (t, τ ) satisfying

τ d ia ≤ t a + τ d ja ∀ a ∈ A, d ∈ D ( 6
)
where i a and j a are the initial and terminal nodes of arc a. We also extend the functions s a (•) to R -by setting s a (w a ) = s a (0)+w a for w a < 0.

Theorem 1 The convex program

(D) m i n (t,τ )∈T a∈A ta 0 s -1 a (y) dy - d∈D i =d g d i τ d i
has optimal solutions, and any such solution

(t, τ ) satisfies w * a = s -1 a (t a ).
Proof. Let (t, τ ) be an optimal solution. Since the constraints of (D) are linear, there exist multipliers

v d a ≥ 0 satisfying the Kuhn-Tucker conditions (a) v d a [τ d ia -t a -τ d ja ] = 0 ∀ a ∈ A (b) s -1 a (t a ) = d∈D v d a ∀ a ∈ A (c) g d i + a∈A - i v d a = a∈A + i v d a ∀ d ∈ D, i = d.
Setting w a = d∈D v d a , the pair (w, v) turns out to be feasible for (P V ), while conditions (a), (b) and ( 6) imply that t a and τ d i are Lagrange multipliers for the constraints ( 5) and ( 4) respectively. Hence (w, v) is a stationary point for (P V ) and since the latter is a convex program it follows that (w, v) is optimal. Therefore w = w * and the equality w * a = s -1 a (t a ) results from (b). The existence of optimal solutions for (D) follows by proceeding in the other direction: take (w * , v) optimal for (P V ) and let t a and τ d i be corresponding multipliers. Then (t, τ ) is a stationary point for (D), hence an optimal solution.

Notice that given any t, a corresponding optimal τ = τ (t) may be found by solving shortest paths for each OD pair (i, d), so that problem (D) is equivalent to the unconstrained, non-smooth, and strictly convex program

( D) m i n t∈R |A| Φ(t) a∈A ta 0 s -1 a (y) dy - d∈D i =d g d i τ d i (t)
with unique optimal solution t * a = s a (w * a ).

Markovian traffic equilibrium

A critical assumption in the deterministic model is the fact that all users perceive the same costs c r . Now, the difficulty to discriminate paths with similar costs, as well as small variations in the perception of travel time among different users, suggest the necessity to relax this assumption. Stochastic models approach this question by assuming that users are randomly drawn from a large population having a variable perception of routes: the costs cr become random variables and the demand g d i splits among the paths r ∈ R d i according to

h r = g d i P(c r ≤ cp , ∀ p ∈ R d i ). ( 7
)
For instance, in the popular logit model the cr 's are taken as independent Gumbel variables with expectation c r and shape parameter β, leading to h r = g d i e -βcr / p∈R d i e -βcp . Except for very small networks, this approach is impractical as it requires path enumeration. More importantly, the independence assumption is unrealistic when dealing with overlapping paths. For instance, in the small example below with 3 routes from i to d, all of them with the same expected cost c r = 1, the logit rule assigns one third of the demand to each route. However, since both routes using the lower arc are almost identical the assignment ( 12 , 1 4 , 1 4 ) seems more natural. The latter is the solution obtained if we focus on arc choices rather than path choices: at node i there are only two arc options (upper and lower), both offering the same travel time so that one may reasonably expect that each one gets roughly one half of the demand. The half taking the lower arc faces a second choice at the intermediate node j where it splits again giving 1 4 of the demand on each of the two lower routes. In this paper we pursue the latter idea by looking at route selection as a recursive decision process based on arc choices. The variability within the population is introduced by modelling the cost of each arc as a continuous random variable ta = t a + a with E( a ) = 0. Consequently, the route costs cr = a∈r ta , and therefore the optimal costs τ d i = min r∈R d i cr as well as the cost zd a = ta + τ d ja of an arc a in regard to destination d, become random variables which we write in the form τ

d i = τ d i + θ d i and zd a = z d a + d a with τ d i = E(τ d i ) and z d a = E(z d a )
. Each user travelling towards d and reaching node i observes the variables zd a and then selects the arc a ∈ A + i with the lowest cost (the probability of a tie is supposed to be zero). This process is repeated at each subsequent node giving rise to a recursive discrete choice model. Hence, for each destination d ∈ D we have an underlying finite-state Markov chain on the graph G with transition probabilities

P d ij = P(z d a ≤ zd b , ∀ b ∈ A + i ) if i = i a , j = j a 0 otherwise.
for i = d; and P d dd = 1, P d dj = 0 for j = d (i.e. destination d is an absorbing state of the chain). The distribution rule [START_REF] Fisk | Some developments in equilibrium traffic assignment[END_REF] is therefore replaced by a recursive scheme where the expected flow x d i entering a node i = d and directed towards d splits among the arcs a ∈ A + i according to

v d a = x d i P(z d a ≤ zd b , ∀ b ∈ A + i ). ( 8
)
Denoting P d = (P d ij ) i,j =d the restriction of the transition matrix to N \ {d} and letting

g d = (g d i ) i =d , the expected flow x d = (x d i ) i =d for destination d is given by x d = ∞ k=0 [( P d ) ] k g d .
This can also be expressed as

x d = g d + ( P d ) x d , that is to say x d i = g d i + i∈A - i v d a . (9)
Before stating a formal definition, we make a short detour to show that all the relevant information for building a stochastic model is encapsulated in the functions

ϕ d i (z d ) E( min a∈A + i [z d a + d a ]
), which we take as the primary modelling objects. We denote by E the class of functions that can be expressed in this form, and which are completely characterized in Appendix A at the end of the paper. For the moment it suffices to mention that these functions are componentwise non-decreasing, concave and smooth, and the transition probabilities may be expressed as

P(z d a ≤ zd b , ∀ b ∈ A + i ) = ∂ϕ d i ∂z d a (z d )
so that the flow distribution equations ( 8) and ( 9) can be restated as

⎧ ⎨ ⎩ v d a = x d i ∂ϕ d i ∂z d a (z d ) ∀ a ∈ A + i x d i = g d i + a∈A - i v d a . ( 10
)
On the other hand, since zd a = ta + τ d ja we may write Bellman's equations of dynamic programming in the form τ d i = min a∈A + i zd a , and by taking expectation we get

z d a = t a + τ d ja τ d i = ϕ d i (z d )
which can be expressed solely in terms of the variables z d a 's as

z d a = t a + ϕ d ja (z d ) (11)
or in terms of the variables τ d i as

τ d i = ϕ d i (t a + τ d ja : a ∈ A). ( 12
)
We stress that [START_REF] Larsson | A dual scheme for traffic assignment problems[END_REF]

s a (w a ) = ∞, t 0 a = s a (0) ≥ 0 and ϕ d i (t 0 ) > 0 for all i = d
and as before we extend s a (•) to R -by setting s a (w a ) = s a (0)+w a for w a < 0.

Definition 2 A pair (w, v) ≥ 0 is a Markovian Traffic Equilibrium (MTE) iff w a = d∈D v d a
where the v d a 's satisfy the flow distribution equations [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF] with z d solving [START_REF] Larsson | A dual scheme for traffic assignment problems[END_REF] for t a = s a (w a ).

Although this notion looks rather different from the deterministic one in Definition 1, we will show that they are in fact closely related. Before we proceed, let us check that the equations ( 10)-( 12) uniquely define v, x, z and τ as implicit functions of t. In order to fix the notations used in the sequel we set

τ d = (τ d i ) i =d , x d = (x d i ) i =d , v d = (v d a ) a∈A , g d = (g d i )
i =d , and we consider the matrices P d (z d ) = (P d ij ) i,j =d and Qd (z d ) = (Q d ia ) i =d,a∈A with entries

P d ij = ∂ϕ d i ∂z d a (z d ) if i = i a and j = j a 0 otherwise Q d ia = ∂ϕ d i ∂z d a (z d ) if i = i a 0 otherwise.
We begin by stating a technical Lemma.

Lemma 1 Assume (H 0 ) and let t = (t a ) a∈A with t a ≥ t 0 a . If (z d , τ d ) solves (11)-(12) then (a) for each i = d there is j ∈ N with P d ij > 0 and τ d j < τ d i , (b) the matrix [I -P d (z d )] is invertible, (c) equation (10) has a unique solution v d = Qd (z d ) x d with x d = [I -P d (z d ) ] -1 g d .
Proof. (a) Let us set ẑd a = t a + τ d i for all a ∈ A. Since ϕ d i is concave and smooth we have

ϕ d i (ẑ d ) ≤ ϕ d i (z d ) + a∈A ∂ϕ d i ∂z d a (z d )(ẑ d a -z d a ) = τ d i + a∈A + i P d ija (τ d i -τ d ja ). Now, Proposition A.2(b) in the appendix gives ϕ d i (ẑ d ) = τ d i + ϕ d i (t), while assumption (H 0 ) implies ϕ d i (t) ≥ ϕ d i (t 0 ) > 0, so that 0 < a∈A + i P d ija (τ d i -τ d ja )
from which (a) follows at once. (b) Using (a) inductively, for all i = d we may find a sequence of nodes i 0 , i 1 , . . . , i m with i 0 = i, i m = d and P d i k i k+1 > 0. Hence the Markov chain started from i has a positive probability of reaching the absorbing state d, so that P d (z d ) k is strictly sub-markovian for k large enough and then [I -

P d (z d )] is invertible. (c)
The first equation of [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF] gives v d = Qd (z d ) x d , which substituted into the second equation yields the linear system

x d = g d + P d (z d ) x d so that x d = [I -P d (z d ) ] -1 g d .
Proposition 1 Assume (H 0 ) and let t = (t a ) a∈A with t a ≥ t 0 a . Then, for each destination d ∈ D, the equations (10)-( 12) have unique solutions [START_REF] Nguyen | Implicit enumeration of hyperpaths in a logit model for transit newtorks[END_REF]. Uniqueness. Let τ 1 , τ 2 be 2 solutions, and denote α = max i∈N [τ 1 iτ 2 i ] and N * the set of nodes i ∈ N where this maximum is attained. Since τ 1 ja ≤ τ 2 ja +α, for all i ∈ N * we have

v d = v d (t), x d = x d (t), z d = z d (t
τ 1 i = ϕ d i (t a + τ 1 ja ) ≤ ϕ d i (t a + τ 2 ja + α) = ϕ d i (t a + τ 2 ja ) + α = τ 2 i + α = τ 1 i .
A contradiction argument based on strict monotonicity then shows that whenever

∂ϕ d i ∂z d a (t a + τ 1 ja ) > 0 one must also have τ 1 ja = τ 2 ja + α, that is j a ∈ N * .
Hence, using Lemma 1(a) we deduce that for all i ∈ N * \ {d} we may find j ∈ N * with τ 1 j < τ 1 i . Proceeding inductively we eventually reach j = d proving that d ∈ N * and therefore α = τ 1 dτ 2 d = 0. It follows that τ 1 ≤ τ 2 and exchanging the roles we obtain τ 1 = τ 2 proving uniqueness.

Concavity.

Let τ 1 = τ (t 1 ) and τ 2 = τ (t 2 ), and set t α = αt 1 +(1-α)t 2 and τ α = ατ 1 +(1-α)τ 2 with α ∈ (0, 1). Since the functions ϕ d i are concave, we obtain

ϕ d i (t α a +τ α ja ) ≥ αϕ d i (t 1 a +τ 1 ja )+(1-α)ϕ d i (t 2 a +τ 2 ja ) = ατ 1 i + (1 -α)τ 2 i = τ α i . Hence, the recursion τ k+1 i = ϕ d i (t α a + τ k ja )
started from τ 0 = τ α generates a non-decreasing sequence. Moreover, proceeding as in the existence part of the proof we may show inductively that τ k i ≤ τ α i with τ α i the shortest distance from i to d with arc travel times t α a . Hence τ k converges and by continuity the limit is a solution of ( 12) so that τ k → τ (t α ). Moreover, since τ k is non-decreasing this limit is greater than τ 0 , that is to say

τ d i (t α ) ≥ τ 0 i = ατ d i (t 1 ) + (1 -α)τ d i (t 2 ) which proves that τ d i (•) is concave.
Smoothness. This is a direct consequence of the Implicit Function Theorem. Indeed, noting that τ d d = 0 we may reduce (12) to a system in the variables (τ d i ) i =d . The Jacobian of this reduced system is [I -P d ] which is invertible according to Lemma 1(b), so the conclusion follows.

To simplify the notation, in the sequel we denote P d (t) = P d (z d (t)) and Qd (t) = Qd (z d (t)), so that Proof. An implicit differentiation of (12) yields ∂τ d ∂ta = Qd •a (t) + P d (t) ∂τ d ∂ta , from which we easily get the expression for ∂τ d ∂t . Then, using the formula of ψ d (t) we deduce

x d (t) = [I -P d (t) ] -1 g d and v d (t) = Qd (t) x d (t).
∇ψ d (t) = ∂τ d ∂t g d = Qd (t) [I -P d (t) ] -1 g d = Qd (t) x d (t) = v d (t).
We are ready to establish our main result for the stochastic traffic equilibrium. We will prove that, with the new meaning of the functions τ d i (•), the characterization ( D) of a deterministic assignment remains valid for the stochastic assignment. This provides a unified framework for both approaches.

Theorem 2 Under (H 0 ) there exists a unique MTE which is given by

(C) w a = s -1 a (t * a ) v d a = v d a (t *
) where t * denotes the unique optimal solution of the smooth strictly convex program

(S) m i n t∈R |A| Φ(t) a∈A ta 0 s -1 a (z) dz - d∈D i =d g d i τ d i (t).
Proof. From Definition 2 and Proposition 1 it follows that a pair (w, v) ≥ 0 is a stochastic equilibrium if and only if w a = d∈D v d a with v d = v d (t) and t a = s a (w a ). This is equivalent to say that (w, v) may be written as w a = s -1 a (t a ) and v d = v d (t) with t satisfying s -1 a (t a ) = d∈D v d a (t). Now, using Corollary 1 we observe that the latter corresponds to ∇Φ(t) = 0, and therefore (w, v) is a stochastic equilibrium iff it is of the form (C) with t * an optimal solution of (S). To conclude we observe that since the τ d i (•)'s are concave and the s -1 a (•)'s are strictly increasing with s -1 a (t a ) → ±∞ when t a → ±∞, then Φ(•) is strictly convex and coercive so that (S) has a unique optimal solution t * .

We stress the fact that (S) is a smooth and strictly convex unconstrained problem, and the dimension of the space R |A| is very low compared to the models based on route flows. These nice features must be weighted against the difficulty in computing the implicit functions τ d i (•). Notice however that the existence proof in Proposition 1 provides a constructive algorithm for this, which will be exploited in section §5 to obtain numerical schemes for computing the MTE. Alternatively, introducing variables τ d i and z d a one may rewrite (S) as a constrained program ( S)

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ min (t,τ,z) a∈A ta 0 s -1 a (z) dz -d∈D i =d g d i τ d i s.t. τ d i = ϕ d i (z d ) z d a = t a + τ d ja
The latter may be dualized to obtain a primal characterization of MTE which is the analog of the primal characterization (P V ) for the deterministic equilibrium, namely

Theorem 3

The MTE is the unique optimal solution of the problem

(P ) m i n (w,v)∈V a∈A wa 0 s a (z) dz + d∈D χ d (v d )
where

χ d (v d ) = sup z d a∈A (ϕ d ia (z d ) -z d a )v d
a is positively homogeneous and convex.

Proof. Let us check that the stationarity conditions for (P ) correspond to the conditions for MTE. We begin by noting that the constraints (w, v) ≥ 0 are implicit in the flow conservation constraints and the fact that χ d (v d ) = ∞ whenever v d a < 0 for some a ∈ A. Hence, we may consider ( 4) and ( 5) as the only constraints in (P ) so that taking multipliers τ d i and t a and forming the lagrangian

L = a∈A wa 0 s a (z) dz + d∈D χ d (v d ) + d∈D i =d τ d i A + i v d a -g d i -A - i v d a + a∈A t a d∈D v d a -w a
stationarity amounts to the conditions s a (w a ) = t a and

ν d ∈ ∂χ d (v d ) where ν d a = τ d ia -t a -τ d ja (with τ d d = 0)
. By subdifferential calculus the latter means that there exists z d an optimal solution of

χ d (v d ) such that ϕ d ia (z d ) -z d a = ν d a .
From Proposition A.2(b) we observe that (z d a : a ∈ A + i ) may be modified by a constant without affecting its optimality, and therefore we may assume with no loss of generality that

ϕ d i (z d ) = τ d i . The equality ϕ d ia (z d ) -z d a = τ d ia -t a -τ d ja then becomes z d a = t a + τ d ja so
that the subdifferential condition is equivalent to ( 11)- [START_REF] Nguyen | Implicit enumeration of hyperpaths in a logit model for transit newtorks[END_REF]. Finally, we observe that the optimality of z d is equivalent to

v d a = ∂ϕ d ia ∂z d a a∈A + i v d a
which corresponds to [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF]. Therefore the stationarity conditions for (P ) correspond to [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF] and [START_REF] Larsson | A dual scheme for traffic assignment problems[END_REF] with t a = s a (w a ), which are precisely the conditions that define the MTE.

We observe that

χ d (v d ) = i =d χ d i (v d ) with χ d i (v d ) = sup z d a∈A + i (ϕ d i (z d ) -z d a )v d a .
In particular, in the deterministic case where we have

ϕ d i (z d ) = min a∈A + i z d a it follows that χ d i (v d
) ≡ 0 and therefore (P ) reduces exactly to (P V ). Also, in the case of a logit Markov model where

ϕ d i (z d ) = -1 β d i ln( a∈A + i e -β d i z d a )
a straightforward computation yields

χ d i (v d ) = 1 β d i a∈A + i v d a ln(v d a ) -( a∈A + i v d a ) ln( a∈A + i v d a )
so that (P ) coincides with Akamatsu's logit Markovian model [START_REF] Akamatsu | Cyclic flows, Markov processes and stochastic traffic assignment[END_REF] where the case β d i ≡ θ is considered.

Extensions

Arc capacities and saturation

So far, the volume-delay functions s a (•) were assumed to be defined over [0, ∞). Since very often the arcs have a maximal saturation capacity, it is useful to extend the model by considering strictly increasing continuous functions s a : [0, wa ) → [0, ∞). The saturation capacity wa is supposed strictly positive and may be infinite for those arcs which are not subject to saturation. To ensure feasibility we must assume that these capacities are large enough for the given demands, namely Theorem 4 Assume (H 0 ) with s a : [0, wa ) → [0, ∞) such that lim wa→ wa s a (w a ) = ∞, and suppose that there is a vector ( ŵ, v) satisfying ( 4) and (5) with ŵa < wa for all a ∈ A. Then the conclusions of Theorem 2 remain valid.

Proof. It suffices to establish the coercivity of the objective function Φ(t), for which we prove that the recession function Φ ∞ (t) lim λ→∞ Φ(λt) λ satisfies Φ ∞ (t) > 0 for all t = 0. The recession function of a∈A ta 0 s -1 a (z) dz is equal to a∈A wa t a if t ≥ 0 and +∞ otherwise. In order to compute the recession functions of the τ d i (•)'s we exploit equation ( 12) to obtain

(τ d i ) ∞ (t) = (ϕ d i ) ∞ (t a + (τ d ja ) ∞ (t)). (13)
Now, the definition of the class E and Lebesgue's theorem imply that (ϕ d i ) ∞ (z d ) = min{z d a : a ∈ A + i }, and therefore (13)

g d i τ d i (t) ≤ a∈A t a ŵa < a∈A t a wa
which implies Φ ∞ (t) > 0 as was to be proved.

Mixed deterministic/stochastic assignment

The functions ϕ d i ∈ E in the stochastic model are used to describe the flow distribution rule [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF], and may differ from node to node: at some nodes one could consider logit distribution, while other nodes may be governed by probit or other discrete choice models. On the other hand, the deterministic model assumes that the flow entering each node is distributed among optimal arcs, which may also be written in the form [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF] by taking ϕ d i (z d ) = max{z d a : a ∈ A + i } and replacing the gradient by the subdifferential. This further explains the analogy between the characterizations ( D) and (S), and leads naturally to consider the possibility of a hybrid model where some nodes have a stochastic distribution rule while other nodes are deterministic. The analysis carries over to this more general setting with (S) characterizing the traffic equilibrium, though Φ(•) will no longer be smooth.

Simultaneous mode/route selection and elastic demands.

Noting that the graph G = (N, A) need not be limited to a single mode, the previous framework turns out to be flexible enough to handle more complex decision processes such as the simultaneous choice of mode and route. To this end it suffices to apply the model over a multi-modal graph built by connecting every origin and destination to one or several corresponding nodes on the subgraphs representing the basic transportation modes (car, bus, metro, walk, etc.). Combined modes such as car-metro-walk may be easily included by connecting the nodes on the corresponding subgraphs through additional transfer arcs. At every origin node one may adopt a particular distribution rule based on a logit or probit model, while at other nodes (e.g. the metro sub-network) one may use a deterministic rule. A further extension concerns the modelling of elastic demands. The option of not making a trip for a given OD pair may be simulated as usual by adding a no-trip arc which connects directly the origin to the destination, with cost equal to the inverse of the demand function (see [START_REF] Hearn | Network equilibrium models and algorithms[END_REF]).

Numerical experiments

In this short section we describe some numerical tests for solving the minimization problem (S). According to Corollary 1 the derivatives of the objective function Φ(t) in problem (S) are given by

∂Φ ∂ta = s -1 a (t a ) -wa (t)
with wa (t) = d∈D v d a (t). The computation of these derivatives requires solving first the system (12) in order to find the functions τ d i (t) and then solving [START_REF] Fukushima | On the dual approach to the traffic assignment problem[END_REF] to find v d a (t). As seen from the existence proof of Proposition 1 this may be done for each destination d ∈ D by a fixed point iteration A gradient method would use the above to estimate wk ∼ w(t k ) and then use the update

F P (t) ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ -Iterate τ d,n+1 i = ϕ d i (t a + τ d,n ja ) to find an estimate τ d i ∼ τ d i (t) -Compute
(G t ) t k+1 a = t k a -α k [s -1 a (t k a ) -wk a ]
with α k a suitably chosen stepsize. Since performing a linesearch is too expensive, a normalized gradient stepsize was implemented by taking [START_REF] Shor | Minimization methods for non-differentiable functions[END_REF]Theorem 2.3] guarantees that t k → t * , in our numerical tests the convergence was extremely slow (as usual for a gradient method).

α k = λ k / h k with h k a = [s -1 a (t k a ) -wk a ] and λ k > 0 such that λ k → 0 and k λ k = ∞. Although
An alternative method is obtained by using the change of variables t a = s a (w a ) to transform (S) into a strictly convex program in the total flow variables w a , that is to say, minimizing the function Ψ(w) = Φ(s(w)). The derivatives of the latter are given by ∂Ψ ∂wa = [w aw(s(w))]s a (w a ) so that the gradient iteration now becomes

(G w ) w k+1 a = w k a -α k [w k a -wk a ]s a (w k a ).
This was also implemented with a normalized stepsize but the convergence was again too slow. A more efficient variant is the method of successive averages which slightly modifies the latter as

(MSA) w k+1 a = w k a -α k [w k a -wk a ]
and which may be interpreted as a variable metric gradient method.

A Matlab implementation of MSA with constant stepsize α k ≡ α was tested on the traffic network of Siouxfalls, a small network of 24 nodes and 76 arcs with travel times s a (w a ) = t 0 a [1 + b a ( wa ca ) pa ]. A recursive logit discrete choice model was considered by taking 2 plots the precision log( wkw k ) along the iterations showing a linear rate of convergence. The method attains high absolute accuracy1 but the number of iterations is large. However, the cost per iteration is low and the overall CPU time on a 1.6Mhz processor was 3. In order to speed up convergence, the MSA iteration was combined with a Newton method which was activated after MSA reached a 10% relative precision, i.e. wkw k ≤ 0.1 w k . Figure 3 illustrates the performance of this variant. The faster convergence compensates the additional work involved in computing Newton's direction, with a significant reduction in CPU time to 0.7 [s]. Additional tests were carried out on the larger network of Chicago which comprises 2950 arcs and 933 nodes (387 of which are destinations). The performance of both methods was very similar to the case of Siouxfalls reaching a precision wkw k ≤ 10 -9 after 234 iterations and 29 [min] of CPU for the case of MSA, and 14 iterations and 11 [min] of CPU for Newton. In the latter case the Newton direction was computed by a conjugate gradient method that does not require explicitly the Hessian (whose computation becomes expensive for large networks, see Appendix B) but only to evaluate products of this Hessian by vectors which can be done much more efficiently. The advantage of Newton's method over MSA is less clear for medium precision computation. For instance, MSA takes 6.3 [min] to reach a 0.1% relative accuracy, while Newton requires 4.3 [min] for this precision.

ϕ d i (z d ) = -ln[ a∈A + i exp(-β d i z d a )]/β d i . Figure

Convergence of MSA

We conclude the paper by establishing a sufficient condition for the convergence of MSA. This result can be seen as a discrete analog of the convergence analysis for continuous Riemannian gradient flows presented in [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF]Alvarez,Bolte and Brahic].

Theorem 5 Assume (H 0 ) with s a : [0, ∞) → [0, ∞) of class C 2 . If λ k > 0 is such that k λ k = ∞ and k λ 2 k < ∞, then the sequence (w k ) k∈N generated by the MSA iteration w k+1 = (1-λ k )w k +λ k wk converges to the MTE w * .
Proof. We begin by noting that wk satisfies flow conservation so that the sequences wk and w k remain bounded. Proceeding as in §5 we rewrite MSA as the variable metric subgradient scheme

w k+1 -w k λ k ∈ -D(w k ) -1 ∂Ψ(w k )
where

D(w) = diag[s a (w a ) : a ∈ A].
The convexity inequality then gives

Ψ(w k ) + D(w k ) w k+1 -w k λ k , w k -w * ≤ Ψ(w * )
which we may rewrite as

[Ψ(w k ) -Ψ(w * )]λ k + ∇h(w k ), w k+1 -w k ≤ 0 (14)
with h(w) = a∈A wa w * a s a (z)(zw * a ) dz. We notice that h(w * ) = 0 and h(w) > 0 for w = w * . Now, by the mean value theorem there exists

ξ k ∈ [w k , w k+1 ] such that h(w k+1 ) = h(w k ) + ∇h(w k ), w k+1 -w k + 1 2 ∇ 2 h(ξ k )(w k+1 -w k
), w k+1w k and since the w k 's are bounded we may find α ≥ 0 such that

h(w k+1 ) ≤ h(w k ) + ∇h(w k ), w k+1 -w k + α w k+1 -w k 2 .
But then, since w k+1w k = λ k wkw k ≤ βλ k for some constant β ≥ 0, using [START_REF] Sheffi | An algorithm for the equilibrium assignment with random link times[END_REF] we deduce

[Ψ(w k+1 ) -Ψ(w * )]λ k + [h(w k+1 ) -h(w k )] ≤ αβ 2 λ 2 k . In particular we get 0 ≤ h(w k+1 ) ≤ h(w k ) + αβ 2 λ 2
k which implies that h(w k ) converges. On the other hand, summing these inequalities we obtain

∞ k=0 [Ψ(w k+1 ) -Ψ(w * )]λ k ≤ h(w 0 ) + αβ 2 ∞ k=0 λ 2 k < ∞ and then the condition λ k = ∞ implies lim inf Ψ(w k ) ≤ Ψ(w * )
. Since w * is the unique minimum of Ψ(•) it follows that we may find a subsequence w k j → w * , and then lim k h(w k ) = lim j h(w k j ) = 0 from which we conclude that w k → w * as claimed.

Appendix A

Let E denote the class of functions ϕ : R n → R which can be expressed in the form

ϕ(x) = E( min i=1...n [x i + i ]) (15)
for random variables i 's such that E( i ) = 0 and

P( i -j = α) = 0 ∀ α ∈ R, i = j. ( 16
)
Example. The logit model assumes that the i 's are independent Gumbel variables with parameter β, which gives ϕ(x) = -1 β ln(e -βx1 + • • • + e -βxn ). In the probit model with normally distributed i 's there is no simple analytical expression for ϕ(x).

Proposition A.1 Every ϕ ∈ E is concave and C 1 with ϕ(x) ≤ m(x) min{x 1 , . . . , x n } and ∂ϕ ∂x i (x) = P(x i + i ≤ x j + j , ∀ j = i). ( 17
)
Proof. The inequality ϕ(x) ≤ m(x) follows at once by taking expectation in the inequality min i=1..

.n [x i + i ] ≤ x j + j . Let F ( ) be the joint distribution of = ( 1 , . . . , n ) so that ϕ(x) = R n m(x + ) dF ( ).
Since m is concave the same holds for ϕ. To compute ∂ϕ ∂xi we consider the differential quotient

ϕ(x + te i ) -ϕ(x) t = R n q t ( ) dF ( ) where q t ( )=[m(x+ +te i )-m(x+ )]/t. Denoting A = { ∈ R n : x i + i < x j + j , ∀j = i} B = { ∈ R n : x i + i ≤ x j + j , ∀j = i}
it follows that lim t↓0 + q t ( ) = 1 A ( ) and lim t↑0 -q t ( ) = 1 B ( ). Since the convergence is monotone we may use Lebesgue's theorem to deduce

D + i ϕ(x) = R n 1 A ( ) dF ( ) = P(A), D - i ϕ(x) = R n 1 B ( ) dF ( ) = P(B). (18)
Assumption [START_REF] Trahan | Probabilistic assignment: an algorithm[END_REF] gives P(A) = P(B) and therefore the partial derivative ∂ϕ ∂xi exists and satisfies [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. The C 1 character then follows since ϕ is concave.

The following result of San Martín [13], provides a useful characterization of the class E. and then we may conclude by taking 1 = 0 and i = -η i for i = 2, . . . , n. Notice that E( i ) = 0 follows from (c) by using Lebesgue's theorem, while ( 16) is obtained from (18) using the fact that ϕ is differentiable.

Remark. We observe that condition (d) may be weakened to ∂ϕ ∂x1 (0, x 2 , . . . , x n ) being a distribution on R n-1 .

Appendix B

This short appendix provides analytic expressions for the Hessians of the functions Φ(t) and Ψ(w) = Φ(s(w)), which are required to implement Newton's method. We denote where δ ca = 1 if c = a and δ ca = 0 otherwise. This corresponds precisely to (19) as was to be proved.

B
Using the chain rule and the equality ∇[ d∈D ψ d (t)] = d∈D v d (t) = w(t) one may easily deduce

Figure 1 :

 1 Figure 1: path v/s arc choices on a small network

Corollary 1

 1 We have ∂τ d ∂t = [I -P d (t)] -1 Qd (t). Moreover, the function ψ d (t) = i =d g d i τ d i (t) is concave and smooth with ∇ψ d (t) = v d (t).

  d ) with z d a = t a + τ d ja and build the matrices P d and Qd -Compute x d = [I -( P d ) ] -1 g d and v d = ( Qd ) x d -Aggregate w = d∈D v d

Figure 2 :

 2 Figure 2: MSA iterations -Siouxfalls

Figure 3 :

 3 Figure 3: MSA-Newton iterations -Siouxfalls

Proposition A. 2 ϕ[ 1 -min{x 1 ,

 211 ∈ E iff the following properties hold: (a) ϕ is C 1 and componentwise non-decreasing. (b) ϕ(x 1 + c, . . . , x n+ c) = ϕ(x 1 , . . . , x n ) + c. (c) ϕ(x) → x i when x j → ∞ for all j = i.(d) for x i fixed, the function ∂ϕ ∂xi (x 1 , . . . , x n ) is a distribution on the remaining variables, i.e. it is componentwise non-decreasing with respect to x j for j = i and∂ϕ ∂x i (c, . . . , c, x i , c, . . . , c) → 1 if c → +∞ 0 if c → -∞.Proof. For ϕ ∈ E the properties (a) through (d) follow easily from[START_REF] Shor | Minimization methods for non-differentiable functions[END_REF] and Proposition A.1. To establish the converse let us consider a random vector η = (η 2 , . . . , η n ) with distributionF η (x 2 , . . . , x n ) = ∂ϕ ∂x1 (0, x 2 , . . . , x n ).We begin by noting that property (b) impliesϕ(x) = x 1 -x1 a ∂ϕ ∂x1 (y, x 2 , . . . , x n )] dy + ϕ(0, x 2 -a, . . . , x n -a)so that letting a → -∞ and using (c) we getϕ(x) = x 1 -x1 -∞ [1-∂ϕ ∂x1 (y, x 2 , . . . , x n )] dy. Now, property (b) also implies ∂ϕ ∂x 1 (y, x 2 , . . . , x n ) = ∂ϕ ∂x 1 (0, x 2 -y, . . . , x n -y) = F η (x 2 -y, . . . , x n -y) = P(y ≤ Y )with Y = min{x 2 -η 2 , . . . , x n -η n }, and thereforeϕ(x) = x 1 -x1 -∞ F Y (y) dy.Integration by parts allows to further work out this expression asϕ(x) = x 1 -x1 -∞ [x 1y] dF Y (y) = x 1 [1 -P(Y ≤ x 1 )] + y} dF Y (y) = E(min{x 1 , Y }) = E(min{x 1 , x 2 -η 2 , . . . , x n -η n })

∂ 2

 2 τ d ∂t b ∂t a = [I -P d ] -1 ∂ Qd the fact that x d = [I -( P d ) ] -1 g d and the chain rule we get ∂ 2 ψ d ∂t b ∂t a = (g d ) [I -P d ] -1 ∂ Qd

Definition 1

  Let H denote the set of all (w, h) satisfying (1) and (3) with h ≥ 0. A pair (w, h) ∈ H is a deterministic traffic equilibrium iff for each destination d ∈ D and every i = d one has

  ) and τ d = τ d (t).Moreover, the functions t → τ dExistence. Consider the sequence generated inductively by τ k+1

i (t) and t → z d a (t) are concave and smooth. Proof. According to Lemma 1(c) and since z d a = t a + τ d ja , it suffices to analyze τ d (t). Let us then examine (12) for a fixed d. i = ϕ d i (t a +τ k ja ) started from τ 0 i = 0. Since the ϕ d i 's are componentwise non-decreasing, using (H 0 ) we get τ 1 ≥ τ 0 and then it follows inductively that τ k+1 ≥ τ k . Denoting τi the shortest distance from i to d, Proposition A.1 in the appendix yields ϕ d i (t a + τja ) ≤ min a∈A + i [t a + τja ] = τi and since we obviously have τ 0 ≤ τ , it follows inductively that τ k ≤ τ for all k. Therefore the non-decreasing sequences τ k i have a limit τ d i satisfying τ d i = ϕ d i (t a +τ d ja ), i.e. a solution of

  d (t) = [I + J d ∂τ d ∂t ]where J d = (J aj ) a∈A,j =d with J d aj = 1 if j = j a and J d aj = 0 otherwise. Recall from Corollary 1 that∂τ d ∂t = [I -P d (t)] -1 Qd (t) If the functions ϕ d i (•) are of class C 2 then we have ∇ 2 Φ(t) = diag[1/s a (s -1 a (t a ))] -Proof. Setting ψ d (t) = i =d g d i τ d i (t)as in Corollary 1, the formula for ∇ 2 Φ(t) follows easily if we show that∇ 2 ψ d (t) = (B d ) [ i =d x d i ∇ 2 ϕ d i (z d )]B d . (19)To prove the latter we exploit the equality [I -P d ] ∂τ d ∂ta = Qd •a which gives

	Proposition B.1

d∈D B d (t) [ i =d x d i (t)∇ 2 ϕ d i (z d (t))]B d (t).

The relative accuracy wk -w k / w k is even higher reaching 10 -14 .

Acknowledgements. We sincerely thank Jaime San Martín for long discussions on the probabilistic foundation of discrete choice models as well as for the characterization of the class E in Proposition A.2. We are also indebted to Marleen van Rijsbergen who helped us in implementing Newton's method for the MTE.

* Partially supported by ECOS-Conicyt program under grant No. C00E05 I.


Renaud Pawlak

Laurence Duchien

Lionel Seinturier

CompAr: Ensuring Safe Around Advice Composition

Advanced techniques in separation of concerns such as Aspect-Oriented Programming, help to develop more maintainable and more efficient applications by providing means for modularizing crosscutting concerns. However, conflicts may appear when several concerns need to be composed for the same application, especially when dealing with around advice. We call this problem the Aspect Composition Issue (ACI). Based on our experience in programming aspects, this paper presents a language called CompAr, which allows the programmer to abstractly define an execution domain, the advice codes, and their execution constraints. The CompAr compiler then evaluates the definitions in order to check if the execution constraints are fulfilled. Using a concrete AOP case study, we show how to use the CompAr language in order to detect and avoid ACIs.

Introduction

When dealing with complex software, programmers and designers naturally try to apply the divide and conquer principle by splitting the application into small pieces, which are easier to understand than the whole system. This technique is referred to as Separation of Concerns (SoC) and has been originally described in [START_REF] Parnas | On the criteria to be used in decomposing systems into modules[END_REF]4]. The goal of SoC is to analyze one of the parts without having to take the other parts into account. However, in the difficult process of making the application parts independent, many issues can arise.

Within the last few years, Aspect-Oriented Programming (AOP) [START_REF] Kiczales | Aspect-oriented programming[END_REF] has stressed the point that some concerns are significantly difficult to modularize. AOP identifies these concerns as crosscutting concerns, i.e. the implementation of these concerns spans over some modules of the other concerns. AOP and related approached propose some solutions to these issues which would pull out the crosscutting concerns from the application code, allowing for easier modularization.

Thanks to AOP, some techniques that are used in middleware and other fields have been highlighted and are becoming more popular. One of the most important and widely used techniques can be referred to as the around advising of the code; this is an important mechanism used to compose concerns together. It has been employed under several contexts and can be implemented by wrappers, filters, interceptors, proxies, around code injections, and so on. However, all these implementation techniques face the same issues when composing several concerns. We call this kind of issue the Aspect Composition Issue (ACI) [START_REF] Pawlak | An automatic aspect weaver with a reflective programming language[END_REF]. Unfortunately, little support is provided to solve this problem and, most of the time, it has to be handled manually, without any tools or guidelines.

In this paper, we present a language called CompAr that is able to automatically detect conflicting around advice codes out of an abstract specification of the aspect-oriented program.

In section 2, we define the around advice and give some examples of its use. Then, in section 3, we present our case study, which deals with real-life aspects that we use for reasoning on specific ACIs. In section 4, we define CompAr, our language to specify composition-relevant information. We show how CompAr checks a specification to detect composition issues. Section 5 goes further in studying ACI by focussing on composing all the aspects of our case study by using CompAr. Finally, before concluding, we list some related works in section 6.

The Around Advice

Breaking down software into independent modules, objects or components that can be designed or programmed separately, implies a composition phase. In this section, we focus on a useful composition mechanism called around advice; we introduce its mechanisms and common utilizations.

Introducing Around Advice

When composing several modules together, structural or behavioral composition mechanisms are needed; our focus is on the behavioral compositions. When composing behaviors, the behavior of the target module is modified by another behavior coming from source modules. In order to achieve this, around advice is a convenient mechanism; we describe the device here in an informal manner.

One can apply an around device code to a given target executable element such as a method, a constructor, or a field access; as a result, the target element will be modified transparently for the base program; the target element is said to be advised. Once this element is executed in the program, the flow of execution is the following:

1. the advice code is executed (and can access some contextual information from the base program), 2. when a special instruction called proceed is reached, the advice code executes the advised executable element (called this), 3. when the advised method ends, the rest of the advice code is executed and can finally return. Note that an advice code has a before part (before the call to proceed ) and an after part (after the call to proceed ). It is not required to call proceed (it then completely replaces the implementation of the advised method).

As shown in figure 1, a method can be advised several times; this method then holds an advice chain. Each advice before part is executed in the order defined by the chain (the top advice code is executed first). When the execution of an advice code reaches proceed, the control is passed to the next advice of the chain.

The advised element is executed at the end of the chain and returns so that all the advice after parts are executed in the reverse order of the before parts execution order. An advice code can break the regular advice chain control flow by not calling proceed or by throwing an exception.

Note that an advice code is said to precede the advice codes that come after it in the chain and to follow the advice codes that come before it in the chain.

Around Advice Utilizations

Even though around advice-related techniques are used in many contexts and languages, the main utilization of around advice is in Aspect-Oriented Programming (AOP) [START_REF] Kiczales | Aspect-oriented programming[END_REF]. AOP focuses on solving crosscutting of concerns when programming or designing complex applications. In short, AOP solves crosscutting and tangling code issues by allowing the programmer to define pointcuts. A pointcut is a set of points (joinpoints) in the base program that are affected by aspect-level advice, including around advice.

Aside from the popular AspectJ [START_REF] Kiczales | Getting started with AspectJ[END_REF] language, numerous projects have included AOP features such as JAC [START_REF] Pawlak | Jac: A flexible solution for aspect-oriented programming in java[END_REF], CFOM [START_REF] Bergmans | Software Architectures and Component Technology, chapter Aspect Composition Using Composition Filters[END_REF], CaesarJ [START_REF] Mezini | Conquering aspects with Caesar[END_REF], and PROSE [START_REF] Popovici | Just-in-time aspects: Efficient dynamic weaving for java[END_REF]. Besides, several other approaches use techniques that can be closely related to around advising, for instance: Composition Filters [START_REF] Bergmans | Software Architectures and Component Technology, chapter Aspect Composition Using Composition Filters[END_REF] and Multi-Dimensional Separation of Concerns [START_REF] Ossher | Using multidimensional separation of concerns to (re)shape evolving software[END_REF].

When a new language is not available, around advice is usually implemented by using Interception [START_REF] Lämmel | A semantical approach to method-call interception[END_REF] [START_REF] Pawlak | Jac: A flexible solution for aspect-oriented programming in java[END_REF], which is a very popular mechanism to imple-ment separation of concerns in middleware environments. In these frameworks, interceptors are regular objects which may intercept the method invocations, the object constructions, and/or the field accesses. Chains of interceptors are functionally equivalent to around advice chains.

The following code shows the implementation of an interceptor using the AOP-Alliance [1] Java interfaces (the common Public Domain interfaces that have been defined and implemented by some of the the aforementioned projects).

An AOP Case Study for Composition

This section presents a set of useful generic server-side aspects which are typically used in distributed middleware layers.

For the sake of this paper, we have focused solely on the around devices of the aspects, and have simplified them to keep only the relevant details. Note that we use the AOP Alliance API in order to remain as independent as possible from any specific language or commercial framework. The aspects depicted here are used to illustrate typical composition issues, and they will be formalized in the next sections.

Logging Aspect

The most well-known and straightforward application of AOP consists of seamlessly introducing logging when needed. By using around advice, the logging aspect can write into files what happens on a server; this can be useful for maintenance (security, performance, debugging). As shown below, the implementation of the logging aspect's around advice is quite simple.

Authentication Aspect

Within a client/server interaction, a server-side authentication aspect checks that the user associated to the current session has the right to access the involved resources. If the current session has no associated user, the authentication aspect may ask the client to authenticate by, for example, asking for a login and a password. If the client does not have the right to perform the current action, the authentication aspect performs an alternative action, such as throwing an exception to notify the client that the rights were not granted.

The implementation of the authentication aspect's logic is mainly done within the following around advice:

Persistence Aspect

On the server, objects can be persistent. Typically, this is achieved by advising all the setters and getters of the objects and by writing or reading the data in a storage (XML files, JDBC data source). In many systems, the object's fields may still be directly accessed on optimization purpose so that the object acts as a cache for the storage. Additionally, any transient object that is referenced by a persistent object (through a reference or a collection) should itself become persistent.

The implementation of the persistence aspect's logic is mainly done within the following around advice:

Association Aspect

In object or component models, entities may be related to each other through references or collections. At a higher level, these references or collections can be part of an association; they are then called roles.

For instance, an association exists between an employee and a company: an employee belongs to a company and a company employs several employees; each class (Employee and Company) defines a role field of this association. When a role that is part of an association is set, as through a role setter, it generally means that the other role should be updated in order to preserve the association integrity.

With AOP, it is possible to handle the association integrity concern within an aspect. This concern, which is usually a crosscutting one, can then be cleanly modularized and the maintenance of the application is more straightforward. The main logic of the association integrity concern is programmed in the following around advice:

Composing Logging, Authentication, and Persistence

As a first introduction to ACIs, this section informally shows how to compose the Logging, Authentication, and Persistence aspects. This simple composition problem illustrates the importance of correctly ordering the around advice.

When composing these three aspects, a simple reasoning can help the programmer to find the aspect interactions and thus find out how to solve them. Let us first look at the code of these aspects (see sections 3.1, 3.2, and 3.3). A quick glance shows that the only aspect that does not call proceed all the time is the authentication aspect. This property is important because when an aspect is programmed independently from any context, the programmer assumes that the invocation is actually proceeded to the advised element.

Therefore, if the logging around advice is placed after the authentication advice, then the logging will only be performed if the invocation is authenticated. However, it is not always the behavior that a programmer would expect for the system. Indeed, to detect attack attempts on the server, we may want to log all the requests, even if the associated action is not successfully executed. On the contrary, a quick study of the persistence aspect shows that we want to apply the persistence only if the action is successfully executed.

Finally, we are in the presence of three significantly different kinds of around advice.

-The logging has an execution constraint which states that its before part must always be executed. By using first order action logic, this constraint can be expressed as: beforeLogging, where beforeLogging is true if the beforelogging part has been executed at the end of the advice chain execution. We refer to this kind of advice as obligatory advice.

-The persistence has an execution constraint which can be expressed as:

[persistent]?this<=>writeStorage:true, to be read as "if our execution context is persistent (boolean), then the execution of this advised implies the execution of the writeStorage action and vice versa, else the execution constraint is always fulfilled (true)". Note that we refer to this kind of advice as exclusive advice. -The authentication does not have an execution constraint, but it does not always call proceed. We refer to this kind of advice as conditional advice.

Taking into account all that has been said, in order to fulfill the obligatory and exclusive constraints, the best order for the chain should be: (Logging > Authentication > Persistence). This is, on the other hand, a very intuitive result that would need to be validated. Besides, when the number of aspects grows, it can become tedious to manually fulfill all the execution constraints. In the next section, we present CompAr, a language which helps the programmer to find and validate the right composition order in a rigorous way.

Supporting Aspects Composition: the CompAr Language

In the previous section, we presented a set of useful aspects for server-side middleware layers: Logging, Authentication, Persistence, and Association.

Thanks to AOP and around advising, we have been able to separately define these different concerns so that the understanding of the sever-side system is easier. However, as seen in section 3.5 some ACIs are likely to appear when composing the aspects. This is due to the fact that each aspect is programmed independently, and holds some implicit constraints.

In order to deal with the ACIs, we have defined a language called CompAr (for Composing Around advice). CompAr allows the programmer to specify the advice codes and their implicit constraints. In addition, CompAr checks that a given composition order is valid for a set of execution contexts.

In the rest of this section, we present CompAr (4.1), we define its semantics (4.2), and we apply it to our composition example (4.3).

The CompAr Language

In order to introduce CompAr, we first show how to specify the composition problem which was informally presented in 3.5. In order to do this, we write the following abstract program: choices: persistent, authenticated; advice logging:loggingEnter {loggingEnter+loggingExit} advice authentication { [authenticated]?-+-:throw NotAuthenticated } advice persistenceSetter:[persistent]?this<=>writeStorage:true {

[persistent]?-+(caller(persistent=true),writeStorage):-+-} advised a { logging, authentication, persistenceSetter; } Where the choices command defines the different boolean variables of the execution domain, advice defines a new abstract advice code, and advised defines a composition order to be tested by the compiler. When run, the compiler executes the defined advised in the domain (all the possible combinations of choices values) and checks that the advice definitions are valid. Note that choices can be initialized to true or false in order to restrain the execution domain, but they are usually left undefined, as in this case, to test all the possible executions.

An advice definition contains two parts: an optional post-execution constraint, defined after the advice name and separated from it by a colon; and a body, within curly brackets, which represents the abstract definition of the advice code.

As a result, with CompAr, the logging advice programmed in section 3.1 can be abstractly defined by: advice logging:loggingEnter{loggingEnter+loggingExit}. It means that the body is composed of a loggingEnter before-proceed action and a loggingExit after-proceed action. Besides, when the advice is included in an advised, the post-condition execution constraint ensures that the loggingEnter action has been executed.

The persistence advice is more complicated but follows the same principle: advice persistenceSetter:[persistent]?this<=>writeStorage:true { [persistent]?-+(caller(persistent=true),writeStorage):-+-}

As an execution constraint, we recognize the constraint defined in section 3.5. The body must be understood as follows: "If the execution context is persistent we define a body that does nothing as a before part and that executes two actions as an after part: (1) it sets the calling context to persistent (as an effect, the newly referred object is made persistent), (2) it executes the writeStorage action. If the execution context is not persistent, we just proceed the execution."

Note that we use -to indicate that the advised body code performs some action that is not relevant for composition.

The CompAr Semantics

We now give a brief overview of the CompAr semantics by using a denotational semantics. CompAr can be split into two sub-languages: the body language and the constraint language.

The Body Language Semantics: The body language is inductively defined by three denotation functions: B :Environment→Environment (body denotation function), E :Environment→ Environment (expression denotation function), and T :Environment→Boolean (boolean expression denotation function). For the sake of simplification, we use primitive functions that we informally describe.

The B denotation function is defined through the E denotation function:

1. E1 +E2 (e) = E2 ( proceed( E1 (e)))
2

. E (e) = E (e)

where proceed:Environment→Environment is the function that corresponds to the denotation function of the next advice body in the chain. For a given advised execution, an environment contains a linked code list, which corresponds to the advice order that has been defined for the advised. Moreover, when the end of the chain is reached and the advised element is executed, a this action is set to 'executed' in the environment.

The E denotation function (for expressions) is defined as follows and using B and T :

., Tn (e)/in]

where advised:Identifier ×Environment×Environment→Environment is the function that initializes a new child environment (new:→Environment) with the linked code that corresponds to the advised identified by i. It then proceeds the first linked code of the chain in the new environment. Note that 'advised' sets the i action state to 'invoked' in the parent environment. This i action state will be set to 'executed' in the parent environment by the 'proceed' function whenever the advised element is executed in the child environment.

Note that two types of environment changes can be performed: an action state change, where an action can be set to 'executed' or 'invoked', and a choice boolean value assignment. This assignment can be done in a new context, during an 'advised' invocation, or in a calling context, during a caller instruction.

We do not formally define the throwing of exceptions since it is easy to understand intuitively. When a exception is thrown, the program terminates its execution and the environment is returned as is.

Finally, we do not define the denotation function T because it is a classical boolean expression denotation function.

The Constraint Language Semantics: When a CompAr program is executed, it is important to note that some choices may be left undefined. As a consequence, the compiler creates all the possible environments in order to cover the domain and check out all the possible executions. For instance, When an invocation towards an advised is done, a new set of environmental contexts is created and the invocation is performed for all these contexts. Hence, the compiler creates an execution tree rather than a simple execution.

When the execution tree is created, the compiler inspects all the final environmental contexts (one per tree node) and checks, for each one, that the advice post-execution constraints are fulfilled. For a given environment, we define the C denotation function, which is used for constraint verification.

As we can see, the compiler checked the post-execution constraints for the domain, which is formed out of the combination of the persistent and authenticated choices possible values. Here, since the values are undefined, there are four possible executions and they all fulfill the constraints for the advised: ordered as logging, authentication, persistenceSetter.

Next, if we try an invalid order such as persistenceSetter, authentication, logging, the compiler reports an error for each execution that does not fulfill all the constraints: Here, we see that the loggingEnter constraint defined by the logging advice is not fulfilled when authenticated=true.

Using CompAr to Solve Complex ACIs

In this section, we finalize our case study which had started in sections 3.5 and 4.3 by adding the association aspect of section 3.4. As we will see next, adding this final aspect induces a difficult ACI that we manage to detect and solve with CompAr.

Composing the Association

For the association, the advice code, applied on a role setter, is active only if the advised method is a role (part of an association), and if we are not already in an update process. Further, in the case that the role&&!update condition is fulfilled, the association is exclusive -the opposite role of an association has to be updated only if the current role itself is updated. As a consequence, a possibly valid order for the roleSetter advice can be defined in the total advised: advised total { logging, authentication, persistenceSetter, roleSetter; }.

More precisely, by using CompAr, the association around advice can be abstractly specified as: advice roleSetter : [role && !update]?this <=> total:true { ([role && !update]?total(update=true):-) + -} where total is the name of the advised that defines the full order of our four aspects. The association specification should be read as follows: "the before part does nothing except proceeding; the after part invokes recursively the advised total if we are in a role and not in an updating process (role && !update condition)".

Note that this definition makes the total advised definition recursive. The infinite recursion is avoided by the update=true assignment which restricts the domain of the total invocation and prevents having to re-apply the roleSetter advice.

However, the total ordering leads to a conflict that we explain in the next section.

The Persistence and Association Conflict

Let us imagine that we want to apply our aspects to two objects o1 and o2, where o1 and o2 can be linked through an association. This association has two roles r1 and r2. A method setR2 can be called on o1 in order to set the association's role and a method setR1 can be called on o2 in order to set the association's opposite role. Let us also assume our initial conditions imply that o2 is persistent, that o1 is not persistent, and that o1.r2 and o2.r1 are null. Figure 2 shows the execution flow when setR2(o2) is invoked on o1 and when the advice chain is the one suggested by the total advised of the previous section. Note that x refers to a memory variable, whereas x refers to the corresponding variable in the persistent storage.

As seen in the figure, the composition of the aspects as they are produces a side-effect that breaks the implicit persistence constraint; the final storage state (o1.r2=null) differs from the final memory state (o1.r2=o2). This composition error is mainly a result of the condition [persistent] being global to the before and after parts of the persistent advice code. As a consequence, the persistence after code, which is supposed to write the value of the r2 role in the storage, is never executed.

Solving the Conflict by Using CompAr

In the previous section, we have seen that the persistence and the association conflict. Detecting this conflict requires a great deal of analysis and understanding from the aspect designer. However, by using CompAr, this conflict can be automatically detected. In fact, if we run CompAr on the total advised as defined in section 5.1, it gives the following output: Therefore, by simply analyzing the compiler's output, the designer can deduce that the persistence execution constraint is not fulfilled because the action writeStorage is not executed at level 0 of the recursive evaluation (the final context contains a list of the executed actions). A simple solution to solve this conflict is to decouple the [persistent] condition. In fact, by specifying the persistence body as, ([persistent]?-:-)+([persistent]?(caller(persistent= true),writeStorage):-), the compiler does not report any more errors. It is then easy for the designer to report this design change in the persistence implementation of section 3.3.

Related works

Some interesting studies on aspect interaction are conducted in [5]. This work, which is based on a more precise definition of the AOP's pointcuts semantics, allows their authors to automatically detect the points where a potential conflict may occur (the points where several advice codes are applied). However, it does not give solutions for ordering the advice codes. We believe that this work and our work are complementary.

Works related to this article can also be found in [START_REF] Katara | Architectural views of aspects[END_REF] and [START_REF] Van Gurp | Architectural design support for composition and superimposition[END_REF]. Their authors present interesting formal design languages to specify superimpositions at an architectural level and to compose them.

Conclusion

In this paper, we study the Aspect Composition Issues (ACIs) when using the around advice construct, which is a significant construct for separating concerns, especially for AOP and related approaches. Our work defines a language called CompAr that allows the specification of composition-relevant information that includes boolean choices (forming the execution domain), action executions or invocations, and post-execution constraints. Our compiler then evaluates the specification within the defined domain and checks that all the execution paths fulfill the constraints.

Our study of the four real-life aspects (logging, authentication, persistence, and association) shows that our approach helps to detect and solve ACIs (see the persistence/association ACI of section 5). Besides, the fact that we define a new language makes the approach independent from existing concrete environments or languages. CompAr can then be used as a complementary tool or a DSL for helping the designers.

Finally, even though CompAr is a research prototype, our study is a proof of concept that validation of AO programs is possible. For instance, it would be possible, for a tool or language editor, to generate the abstract CompAr specification out of a real program. One could argue that we could face a state explosion problem when executing the specification. However, since the abstract specification focuses only on composition-relevant information, and that the number of around advice codes it somehow restrained in real systems, we think that this method is applicable in most cases.

We are currently working on several improvements of the language. For instance, we would like to introduce missing constructs such as exception catches, that have not been implemented yet. We also would like to enhance the post execution constraint sub-language to allow TLA-like expressions. This would allow the designer to specify advice where the performed actions must be executed in a certain order. For instance, a security aspect should always execute the crypt action before the decrypt action.

Fig. 1 .

 1 Fig. 1. An around advice chain.

  1. -(e) = e // skip function 2. (E ) (e) = E (e) 3. (E1 ,E2 ) (e) = E2 ( E1 (e)) 4. i (e) = e[ executed/i] 5. [T ]?B1 :B2 (e) = B1 (e) if T (e)=true, B2 (e) otherwise 6. i (i1 =T1 ,...,in=Tn) (e) =advised(i,new[ T1 (e)/i1,..., Tn (e)/in],e[ invoked/i]) 7. caller(i1 =T1 ,...,in=Tn) (e) = parent(e)[ T1 (e)/i1,..

[

  START] checking 'a' advised execution constraints... [OK] [0] {persistent=true, authenticated=true} [ERROR] [0] constraint unfulfilled in 'logging' (loggingEnter) -final context: choices: {persistent=true, authenticated=false} actions: {} -execution trace: test([persistent]?(-+caller([persistent=true]),writeStorage) :(-+-)=>true) enter(a.persistenceSetter=>before) test([authenticated]?(-+-):(throw NotAuthenticated)=>false) * throw(throw NotAuthenticated) [OK] [0] {persistent=false, authenticated=true} [ERROR] [0] constraint unfulfilled in 'logging' (loggingEnter) [...][END] 2 composition error(s) found while checking 'a'

Fig. 2 .

 2 Fig. 2. Example of conflict between persistence and association.