Mikael Capelle

Slim Abdellatif

Marie-José Huguet

Pascal Berthou

Online Virtual Links Resource Allocation in Software-Defined Networks

Network virtualization is seen as a key networking paradigm for building diverse network services and architectures over a shared network infrastructure. Assigning network resources to virtual links and, more generally to virtual network topologies, efficiently and on-demand is one of the most challenging components of any network virtualization solution. This paper addresses the problem of on-line resource allocation of multiple virtual links on a Software Defined Network (SDN) infrastructure. The application context that is targeted is primarily the online provisioning of virtual overlay networks even if it can be broadened to address more general virtual networks. Considering an SDN physical infrastructure allows a complete freedom in choosing the optimal physical paths and the associated resources that support the virtual links with no interference from any other network function (such as routing). However, for the time being, forwarding in an SDN network is resource consuming with a noticeable impact on the size of the flow tables. Hence, forwarding (i.e. switching) resources should be carefully considered by the network resource allocation algorithm. This paper proposes an Integer-Linear formulation of the above cited problem by considering: (1) point-to-point as well as point-to-multipoint virtual links, each with an associated bandwidth requirement and a maximum transfer delay requirement, (2) two types of network resources, namely network links' bandwidth and nodes' switching resources, and (3) optionally, path splitting which allows a virtual link to be established on multiple physical paths. We report preliminary experimental results on a real network topology in an overloaded scenario (bandwidth requests largely exceed network capacity); they show that our algorithm outperforms shortest path heuristics with a gain on the admission rate (of virtual links requests) that ranges from 5 to 15% (compared to the most efficient heuristic) and with a computation time less than a few seconds.

I. INTRODUCTION

Network Virtualization enables the creation and coexistence of multiple isolated and independent virtual networks over a shared network infrastructure [START_REF] Chowdhury | Network virtualization: state of the art and research challenges[END_REF]. A virtual network is a logical (opposed to physical) network with some of its elements (nodes and links) being virtual. A virtual node is an abstraction of a network device that is often hosted on a single physical node. It executes network functions such as routing, forwarding, etc. by consuming part of the resources of the hosting node. The resources allocated to a virtual network device are as diverse as CPU, volatile memory, network interfaces, storage, switching, etc. Similarly, a virtual link is an abstraction of a network link that is established on one or multiple physical links or physical paths. It consumes transmission resources (i.e. physical links' bandwidth) as well as switching resources at the traversed physical nodes.

Network virtualisation is claimed to be an essential component of future Internet architecture where elastic, potentially programmable, virtual networks are provisioned on-demand [START_REF]Framework of network virtualization for future networks[END_REF]. The virtual network can be a fully virtualised network (with virtual nodes and links) or a simpler construct with virtual links connecting end nodes (which can be virtual) known as overlay networks. In data centres, these latter are considered as the mean to provide network services to applications and are gaining broad acceptance from academia and industry [START_REF] Jain | Network Virtualization and Software Defined Networking for Cloud Computing -A Survey[END_REF], [START_REF] Racherla | Implementing IBM Software Defined Network for Virtual Environments[END_REF], [START_REF] Koponen | Network virtualization in multi-tenant datacenters[END_REF].

Virtual link resource allocation is a key component of an overlay network solution (and also of a fully virtualised virtual network solution). It determines the physical paths and the appropriate resources that are used to support a virtual link with predefined characteristics. On legacy networks, it is strongly coupled and dependent on the routing used by the physical network infrastructure which imposes the route(s) used to support the virtual link. With the advent of Software-Defined Networking (SDN) [START_REF]Software-Defined Networking: The New Norm for Networks[END_REF], a virtual link resource allocation method can be devised with no interference from any other network function. Indeed, on a physical SDN network infrastructure, flows and their forwarding behaviour can be defined at will allowing the virtual link resource allocation method to freely choose the physical paths to be used. This paper proposes a Integer Linear Programming (ILP) formulation of the problem of resource allocation of multiple virtual links (that compose a virtual/overlay network) in SDN network infrastructures. The proposed method addresses pointto-point virtual links as well as point-to-multipoint virtual links (typically useful when providing network services to applications), each with an associated bandwidth requirement and a maximum transfer delay requirement. Two types of network resources are taken into account: classically, the links' bandwidth but also the switching resources of nodes. This is particularly important since, for the time being, switching in an SDN enabled node is a resource consuming task (because of the match operation (which allows the use of wildcards) and the instructions to execute) and this limits the size of the switching table to a few thousands of entries [START_REF] Astuto | Thierry Turletti A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks Communications Surveys & Tutorials[END_REF], [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF]. A last characteristic of our method is the optional support of path splitting which allows a virtual link to be established on multiple paths. This capability contributes to the objective of the method which is: fairly spreading network load on network links and nodes in order to improve the admissibility of subsequent virtual network requests. Even if virtual network resource allocation has recently attracted lots of attention [START_REF] Abdeltouab Belbekkouche | Ahmed Karmouch Resource Discovery and Allocation in Network Virtualization[END_REF], to the best of our knowledge, the resource allocation problem as described above has not been investigated so far. Indeed, it is in the conjunction of all the above-cited constraints that resides the originality of the addressed problem (point-to-multipoint virtual links, accounting for switching resources, delay requirements and path splitting being the least considered in the literature). Experimentations on a real network topology brought from the G ÉANT network [START_REF]GEANT: the pan-European research and education network[END_REF] in an overloaded scenario (virtual links requests largely exceed network capacity) show that our method outperforms shortest path heuristics with a gain on the admission rate that ranges from 5% up to 15% compared to the most efficient heuristic (and much more compared to the other heuristics). They also show that the computation time is satisfactory (less than a second for point-to-point links and a few seconds on average for point-to-multipoint virtual links) and that the contribution of path splitting is limited (2 to 3%) for the considered scenario. This paper is organised as follows. Section II reviews previous work from the literature that are related to virtual network resource allocation. Then, section III describes the mathematical formulation of the problem that we are addressing. Section IV presents the performance analysis of the proposed method and its comparaison to the considered shortest path heuristics. Finally, section V concludes the paper and describes the perspectives to this work.

II. RELATED WORK

Virtual network resource allocation (or embedding) has attracted a lot of attention from the research community during the last few years [START_REF] Abdeltouab Belbekkouche | Ahmed Karmouch Resource Discovery and Allocation in Network Virtualization[END_REF]. Several optimization approaches were proposed, some follow an integrated strategy considering simultaneously the resource embedding of virtual nodes and links and, most, follow a split approach that considers separately and successively the two resource embedding problems. Whatever the approach, virtual link resource allocation is the core component of any virtual network resource embedding method. Without being exhaustive, virtual link resource allocation methods can be classified with respect to the following criteria. Some are related to the characteristics of the virtual links being considered, namely: the type which is usually point-to-point but can also be point-to-multipoint, the Quality of Service (QoS) requirements with possibly a bandwidth, a delay and/or a loss rate requirement. The others are related to some features of the methods such as: (1) the allocation process which can be online or offline (the requests are fully known in advance);

(2) the general class to which a method belongs which can be heuristic or exact; (3) the followed approach which leads either to a stand-alone method exclusively concerned with virtual link resource embedding or a more general method that integrates and combines virtual node and virtual link resource allocation, (4) the network resources that are concerned by the allocation which can be the bandwidth of physical links and, possibly, the switching resources of nodes 1 (that are needed to forward the packets that belong to a virtual link); and (5) the potential support of techniques that contribute to improve the efficiency of the methods, such as path splitting and/or migration which allows the reallocation of resources to already admitted virtual 1 other node resources (typically, CPU and RAM) may be allocated to virtual nodes by the virtual node resource embedding algorithm Among this list of papers, we point at the works of [START_REF] Melo | Optimal Virtual Network Embedding: Node-Link Formulation[END_REF], [START_REF] Guerzoni | A novel approach to virtual networks embedding for SDN management and orchestration[END_REF], [START_REF] Houidi | Virtual network provisioning across multiple substrate networks[END_REF] which address an allocation problem similar to the one addressed in this paper while using the same class of methods (based on an ILP or Mixed ILP formulation). In [START_REF] Melo | Optimal Virtual Network Embedding: Node-Link Formulation[END_REF], the authors proposed an integer linear model for solving the on-line virtual network embedding problem (virtual nodes and links). Several constraints were considered such as bandwidth, delay, node load (CPU, RAM) and their method aimed at minimizing the resource consumption. The proposed method was compared with several heuristics approaches on theoretical physical network topologies. In [START_REF] Guerzoni | A novel approach to virtual networks embedding for SDN management and orchestration[END_REF], an integer-linear model was proposed to consider the embedding of virtual network requests. The constraints taken into account, and evaluated in their paper, are the capacity of nodes, in terms of CPU, and the bandwidth on links. Moreover, a virtualization request which is composed of a set of subgraphs is considered to be satisfied if at least one subgraph can be embedded in the physical network. The aim is to maximize the revenue (which is dependent from the allocated CPU) while minimizing resource consumption, i.e. bandwith utilization. Their method can be either applied online or offline as it can consider simultaneously a set of virtual requests leading to better solutions. In [START_REF] Houidi | Virtual network provisioning across multiple substrate networks[END_REF], the authors consider the embedding of virtual networks on several physical network infrastructures. This problem is solved in two steps. The first one focuses on the selection of the physical network and the second step is dedicated to the embedding of a virtual network (with virtual nodes and links) on the selected physical network. A mixed integer linear model is proposed that aims at minimizing the load on the physical network. This model is evaluated for on-line virtual requests and also for optimizing the embedding of a set of virtual requests. The considered constraints are the capacity of each node and the bandwidth of each link. To the best of our knowledge, this is the first paper presenting an integrated approach for the virtualization of both nodes and links. A worth noting point is that the flow variables used in their model are assumed to be real numbers leading to a relaxation of the optimization problem.

III. PROBLEM FORMULATION

This section describes the ILP mathematical formulation that we propose to solve the online virtual links resource allocation problem. Requests arrive and are treated in sequence with no information on future requests (i.e. online). Each request gathers multiple concurrent virtual link sub-requests, each concerning a point-to-point or point-to-multipoint virtual link with bandwidth and delay requirements. The objective is to distribute fairly network traffic and use efficiently network resources (transmission and switching). Below, the physical network and virtual links request models are described; Then, the variables and problem constraints are listed; Lastly, the considered objective function is defined.

A. Physical Network Model

The physical network is modelled by a bidirectional graph G = (V, E) where V (|V |) is the set of physical nodes (SDN switches) and E (|E| , E ⊆ V × V ) the set of physical links which operate in full-duplex mode. To each node i ∈ V is associated a switching capacity U i which is the maximum number of entries (i.e. size limit) of its flow table. The current size of node i flow table is denoted by U ′ i . Each link (i, j), i, j ∈ V is weighted by its bandwidth B ij and its propagation delay D ij . Links are assumed to exhibit the same characteristics in both directions, i.e. B ij = B ji and D ij = D ji . The bandwidth that is currently assigned at link (i, j) by already admitted virtual links is denoted by B ′ ij .

B. Virtual Links Requests Model

A virtual links request consists of a set of K virtual links. Each virtual link k is characterised by:

• a source node s k ∈ V , and a set of destination nodes

T k ⊆ V -{s k } (when |T k | = 1, the virtual link is point-to-point, otherwise it is point-to-multipoint); • a bandwidth requirement of b k ∈ N * and a maximum transfer delay of d k ∈ N * ;
• a maximum packet size of p k .

C. Resource-related assignment variables

The output of our assignment problem is the set of routes (with the bandwidth allocations at each supporting physical link and the number of flow table entries at each traversed node) that support each of the virtual links that compose a request. It is worth noting that since virtual links may be point-to-multipoint, it is likely that resource allocations will be mutualised close to the source and as we get closer to destinations, they will tend to be more and more dedicated to specific destinations. As a consequence, basic assignment variables are related to a specific destination of a virtual link.

In our model, we distinguish the following variables :

• f t k (i, j
) is an integer variable that represents the bandwidth allocated at link (i, j) to the packets of virtual link k that are flowing from the origin node s k to a destination node t. More generally, f k (i, j) refers to the amount of bandwidth used on link (i, j) by the virtual link k, whatever the destination. It is set to the maximum of f t k (i, j) for all k ∈ K. • l k (i) is an integer variable that indicates the switching resources consumed by virtual link k at node i. It is expressed as the number of entries that are installed in node i flow table to support virtual link k with the assumption that all entries consume the same amount of resources regardless of the complexity of the match operation and the related instructions to perform. The number of flow table entries is assumed to be in proportion to the number of node i ports that are receiving traffic from virtual link k (as given by equation 1).

∀k ∈ K, ∀i ∈ V : l k (i) = j∈V (j,i)∈E g k (j, i) (1)
where g k (i, j) is an intermediate boolean variable that indicates if some bandwidth from link (i, j) is assigned to virtual link k or not. It is derived from another set of more focused intermediate variables g t k (i, j) that reflects whether the flow of packets of virtual link k destined to t is supported by the physical link (i, j) (i.e.

g t k (i, j) = 0 if f t k (i, j) = 0 and g t k (i, j) = 1 otherwise). • d t k (i)
which is an upper bound on the time needed for a packet of virtual link k destined to t to reach node i from its originating node s k .

• f max which refers to maximum link utilization (when considering all network links) after request acceptance (i.e. by taking into account the bandwidth allocations consumed by the virtual links that compose the request).

• u max which similarly refers to maximum flow table utilization (when considering all network nodes) after request acceptance.

D. Problem Constraints

The constraints on bandwidth allocations are described hereafter in equations 2 to 8. Equation 2 reflects the linearisation of the M ax operator applied to variables f t k (i, j) to get f k (i, j). Equations 3 and 4 have a similar purpose and focus respectively on f max and u max which are minimized by the objective function (as explained below).

∀k ∈ K, ∀(i, j) ∈ E, ∀t ∈ T k : f t k (i, j) ≤ f k (i, j) (2)
∀(i, j) ∈ E : 1 B ij *   B ′ ij + k∈K f k (i, j)   ≤ fmax (3) ∀i ∈ V : 1 U i *   U ′ i + k∈K l k (i)   ≤ umax (4)
Equation 5 ensures that the bandwidth assigned to each virtual link k at link (i, j) does not exceed the remaining bandwidth. Equation 6 is the usual flow conservation constraints.

∀(i, j) ∈ E : k∈K f k (i, j) ≤ B ij -B ′ ij (5) ∀k ∈ K, ∀t ∈ T k , ∀i ∈ V : j∈Γ(i) (f t k (i, j) -f t k (j, i)) =    b k if i = s k -b k if i = t 0 else (6)
Equation 7 is a channeling constraint between integer and boolean variables: f k (i, j) and g k (i, j). It also constrains the virtual link k's bandwidth assignment at a physical link to the requested bandwidth b k . Equation 8 constrains the bandwidth that is assigned to the flow of packets destined to a specific virtual link's end-point (or destination) within a range of values, in addition to establishing a channeling constraints between boolean and integer variables. The inequalty on the right side ensures that the bandwidth requirement of the virtual link is never exceeded. The inequalty on the left side directs path-spliting and avoids the multiplication of splits with low bandwidth allocations. Indeed, if active, pathsplitting is feasible only if the bandwidth allocated to the splits respects a minimum threshold b min (then, P S ratio ≤ 0.5 when the path-splitting is allowed, and P S ratio = 1.0 when it is forbidden).

∀k ∈ K, ∀(i, j) ∈ E : g k (i, j) ≤ f k (i, j) and f k (i, j) ≤ b k * g k (i, j) (7) ∀k ∈ K, ∀(i, j) ∈ E : b min k * g t k (i, j) ≤ f t k (i, j) and f t k (i, j) ≤ b k * g t k (i, j) (8)
The constraint related to switching resource allocations is given by inequalty 9. It simply ensures that with the addition of flow table entries needed by the virtual links composing the request, the size of network nodes' flow tables remains below their maximum size.

∀i ∈ V : k∈K l k (i) ≤ U i -U ′ i (9)
Virtual links have end-to-end delay requirements. For pointto-multipoint links, they hold and must be met for all of their end-points (destinations). These requirements are taken into account by inequalities 10 and 11 which establish a set of constraints on variables d t k (i) (defined in section III-C as an upper bound on the time needed for a packet of virtual link k destined to t to reach node i from its originating node s k ). The expressions in 10 assure the initialisations at the sources (of virtual links) and that the computed upper bounds at the destinations meet the delay requirements. Inequaltiy 11 show how the upper bounds, computed at two subsequent nodes along the route to a destination, are related to account for packet transmission times and physical link propagation delays. More clearly, let us consider the flow of packets belonging to virtual link k destined to t and let us assume that this flow of packets really goes through link (i, j). Then, the expression in 11 simply states that the increment to the upper bound on the packet transfer delay from s k to i in order to get the upper bound at j must at least take into account : the transmission time of a packet of maximum size p k at the lowest possible bandwidth (i.e. b min k ) and the propagation delay along link (i, j). The last term of the left-side of inequality 11 is a hint used to neutralise its effect in case link (i, j) is not traversed by the flow of packets (Ψ being large).

∀k ∈ K, ∀t ∈ T k : d t k (s k ) = 0 and d t k (t) ≤ d k (10) ∀k ∈ K, ∀t ∈ T k , ∀(i, j) ∈ E : d t k (i) + p k b min k + D ij -Ψ * (1 -g t k (i, j)) ≤ d t k (j) (11)

E. Objective function

The objective function aims at minimizing link and node (switching) resource consumption but also at distributing the consumed resources among nodes an links in order to reduce the creation of bottlenecks. Both contribute to improve the admissibility of forthcoming requests.

As shown in expression 12, it consists of four components, each weighted with a parameter that controls the impact of the component on the resolution process. The first two concern bandwidth allocations and the last two are their analogue for flow table entries (or switching) allocations. We focus hereafter on the former expressions.

minimize α 1 * 1 |E| * (i,j)∈E 1 B ij * B ′ ij + k∈K f k (i, j) + α 2 * f max + β 1 * 1 |V | * i∈V 1 U i * U ′ i + k∈K l k (i) + β 2 * u max (12)
In the first term, the aspect that is minimized is the average of utilization of network links after allocating bandwidth to the considered request. In the second term, the aspect that is minimized is the maximum of network links utilization. This means that the allocations devoted to the request are distributed over different links in such a way that links load disparity is reduced. This is mainly (but not only) enabled by path-splitting which often has as a side effect the increase of node and link resource consumption.

IV. EXPERIMENTAL RESULTS

The main objectives of the experimental analysis are:

• evaluate the performance of our proposed method from the point of view of network resource utilisation, virtual links requests admissibility and convergence (or computation) time.

• gain comprehension in the behaviour of our method and more precisely, assess the effect of some of its parameters: α i , β i , i : 1, 2 and path splitting (P S ratio )

• compare its performance with respect to different variants of shortest path heuristics. Indeed, an objective comparison with the work cited in section II is not obvious because of the disparity of each solution's features (refer to table I).

A. Simulation model 1) Network model:

We consider in this work a real network topology taken from the European Research Network GEANT2 (January 2014) with 41 network nodes and 60 links that connect the main European cities. We adopt the link capacities that are given by GEANT. For some links the exact capacity is not given, instead, an interval is provided. For those whose capacity falls within the range of 1 to 10Gbps, the capacity is set to 5Gbps. For those whose capacity ranges from 10 to 100Gbps, the capacity is set to the uppermost value. Link propagation delays are derived from the geographic coordinates of nodes assuming a straight line between the involved nodes and light speed propagation. Finally, we assume that a flow table size of 2000 entries is dedicated at each node to the considered virtual links resource allocations.

2) Load model: The load model defines the types of virtual links requests and their characteristics as well as their arrival and lifte-time processes. Two types of virtual link requests are considered :

• Unicast Requests which are made of one single pointto-point virtual link request. The bandwidth (respectively delay) requirement is randomly chosen between 7 and 12Gbps (resp. 50 to 80ms). Unicast Requests target network service providers or virtual network operators to answer the need to connect some of their networking devices;

• Multicast Requests which are made of a set of multiple point-to-multipoint virtual links. The number of virtual links is randomly chosen between 4 and 6. Each pointto-multipoint virtual link has from 4 to 6 endpoints.

The bandwidth requirements are fixed on a virtual link basis and is chosen randomly from 200M bps to 3Gbps. Similarly to unicast requests, the delay requirements range from 50 to 80ms. This kind of requests target application service providers such as over-the-top players or content distribution networks to connect some of their elements (cache servers, etc.).

For both types of requests, source and destination selection is performed on a random basis, the probability that a node is chosen is proportional to its overall bandwidth capacity (i.e. when considering all its incoming/outgoing links).

As for previous papers [START_REF] Chowdhury | Virtual Network Embedding with Coordinated Node and Link Mapping[END_REF], [START_REF] Melo | Optimal Virtual Network Embedding: Node-Link Formulation[END_REF], the request arrivals follow a Poisson process with an arrival rate λ that is varied on {0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 1.0}, i.e. the average number of requests varies from 4 to 10 requests each 100 units of time (U T ). The request life-time conforms to an exponential distribution with an average of 1000 UT.

It is important to note that with this load model, our experimental analysis is considering an overloaded scenario where the cumulative bandwidth requests exceed network capacity. For instance, on average, the G ÉANT edge nodes which are connected to the backbone via physical links with a bandwidth less than 10Gbps are fully saturated with no available bandwidth by two hundreds point-to-multipoint virtual link requests.

3) simulation settings: The Integer Linear model was implemented in C++ with CPLEX-12.6 solver3 . The experiments were carried out on an Intel Core i7-4770, 3.4GHz, 8GB of RAM and running Linux Ubuntu-12.04. The resolution time is set to a maximum of 15 seconds. A gap of less than 5% to the optimal solution is considered satisfactory. The simulation horizon is fixed to 10000U T (this time period is sufficient to have our method in the stationary regime). Parameters α 1 and α 2 of the objective function are set to 1 (α 1 = α 2 = α = 1). Parameters β 1 and β 2 are merged and are varied to tune the importance of minimizing and distributing swichting resources consumption (and conversely bandwidth) in the search of the optimal solution (β 1 = β 2 = β ∈ {1, 50, 100, 150}). P S ratio is also varied within {10%, 33%, 45%} and 100% (path-splitting is inhibited).

4) Performance metrics:

The following performance metrics are computed during simulation for performance analysis purposes:

• Acceptance rate: the percentage of successful virtual links requests out of all the requests that arrived during the simulation time;

• Convergence time: the time needed by our method to compute the optimal allocations associated to a virtual links request. The average convergence time and the maximum convergence time are computed over the number of successful requests;

• Instantaneous link utilisation: the percentage of assigned bandwidth at a given link, computed at a time instant t, i.e.

B ′ ij Bij for link (i, j). The instantaneous average link utilisation is averaged over the set of network links as follows

1 |E| * (i,j)∈E B ′ ij B ij (13)

B. Preliminary results and analysis 1) Virtual Links assignment method general performance:

The goal is to give an insight into the general performance of our proposed method by describing the evolution of the requests acceptance rate and network resource utilisation when varying the requests arrival rate and the request type (unicast, multicast). Without any loss of generality, β and P S ratio are respectively set to 150 and 45%, the presented results are representative of what we observed with different settings.

Figures 1 and2 describe the instantaneous acceptance rate as a function of time with different requests arrival rates (λ). As explained above, we are considering an overloaded scenario with cumulative bandwidth requests that exceed network capacity. The effect is a request acceptance rate that falls sharply away from full acceptance when the arrival rate λ is increased. This is particularly noticeable for multicast requests. The reason is that for a given arrival rate, the bandwidth requirement of a multicast request is much more important than its corresponding requirement for a unicast request. Indeed, a multicast request is made of 4 to 6 point-to-multipoint virtual links, each with 4 to 6 end-points while unicast requests are made of one single point-to-point virtual link. Even if the bandwidth requirement of a point-to-point virtual link is more important than its corresponding in a point-to-multipoint virtual link, the overall bandwidth requirement of a multicast request measured at destination nodes is on average four times as important. Another worth noting point is that a multicast request is declined when the network resources needed by at least one of its virtual links can not be afforded. In other words, if one virtual link out of a set of six virtual links that compose a multicast request can not be established, then the whole request is refused. This is the reason why the acceptance rate for multicast request falls down to 40% for some values of λ. It clearly shows that most links have less than half of their bandwidth assigned and that around 20% of links have more than 80% of their bandwidth already assigned. A more detailed analysis on the data sets shows that a few backbone links have more than 95% of their bandwidth assigned. They are the major cause of request refusals. These results brings some evidence on the efficiency of the allocations in terms of consumption and distribution although it may seem that our method failed in avoiding the overload of some backbone links.

In fact, this must be tempered with the request loads scenario (requirements >> network capacity) that we are considering as well as with the network topology of GEANT which binds most allocations to backbone links. request and contrast it to its application scenario which is the on-demand provisioning of virtual links or overlay networks. We believe that a provisioning time that falls within a few tens of seconds is a reasonable target. So is the target of the convergence time of the resource allocation method that precedes the real deployment of the virtual links.

Figure 6 shows the average convergence time of our method for unicast requests as a function of requests arrival rates with and without the use of path splitting. When path splitting is used, the P S ratio leading to the largest search space and hence to the largest convergence time is chosen (i.e. P S ratio = 10%). Figure 6 also shows the maximum observed convergence time for a successful request. These results are obtained with a value of β = 100, but again, they are representative of what was observed with other settings. For the considered network and load model, the convergence times associated to unicast requests fully meet the requirements described above. Indeed, the average convergence time is below 100ms while the maximum remains below 1s (more precisely, 200ms without path splitting and 700ms with path splitting).

Figure 7 describes the results for multicast requests. The observed convergence times are satisfactory since they remain on average below 1s when path splitting is inhibited and below 4s when path splitting is active. However, for some very few requests, the convergence time exceeds the maximum resolution time of 15s (refer to section IV-A3). At the time of this writing, the network conditions and the request profiles that lead to such convergence times are not identified yet. Remakably, path splitting has a significant impact on the convergence time of our method.

3) Path splitting and β parameter impact: The goal is to evaluate the impact of parameters P S ratio and β on the behaviour of our method. To that end, parameters P S ratio and β are respectively varied over {10%, 33%, 45%, 100%} and {1, 50, 100, 150} and the request acceptance rates are measured both, for unicast and multicast requests. No clear impact of parameter β is observed from the experiments for unicast but also for multicast requests (as shown in For space reasons, the results related to the other values of β and to multicast requests are omitted, but the findings are the same. In fact, the load model that is considered for the experiments does not stress the switching resources and the impact of β which weights the importance of the switching resource in the selection of the optimal allocation remains marginal. It is clear that additional experiments with different load models are needed to have a clear understanding on the impact of parameter β.

Path splitting does bring some gain in the admission rate even if, for the considered overloaded scenario, the gains remain within a few percents : 2 to 3% for unicast requests (Refer again to figures 8 and 9) and 1 to 2% for multicast. In a less loaded scenario, its impact on the performance would be stronger. The choice of the most efficient P S ratio is not clear even if a P S ratio = 10% often exhibit good admission rates. The activation of path splitting is questioned for the considered scenario since the limited gain it brings is balanced with the increase in convergence time of the method as well as in flow tables sizes. Moreover, it introduces desequencing of packet transmissions. Additional experiments are needed to specify the situations where path splitting deserves being activated.

4) Comparison with shortest path heuristics:

The goal is to compare the performance of our method with three Shortest Path (SP) heuristics from a requests admissibility perspective. SP heuristics use a cost function to assign a cost to each physical link. For each couple of end-points that belong to a virtual link, the physical path with the minimum cost (the cost of a path being the sum of the costs of the traversed links) is chosen. If the bandwidth available on the chosen path is below the bandwidth requirement of the virtual link, the corresponding request is not admitted. The three SP heuristics differ in their cost function. The first heuristic SP 1 uses a unitary cost for each link meaning that path selection is based on the lowest hop counts. In the second heuristic SP 2 , the cost of a link is inversely proportional to its bandwidth meaning that the selection favours paths with the highest bandwidth. Finally in heuristic SP 3 , the link's cost is inversely proportional to its current capacity. Paths with the highest available bandwidth are firstly chosen. It is worth noting that the three heuristics do not care about switching resources. Hence, some of the allocations derived from these heuristics may not be feasible if the induced size of each flow table is taken into account.

Figures 10 and11, present the acceptance rates respectively for unicast and multicast requests. As expected our method have the best admission rate. When compared to SP 3, the gain ranges from 3 to 15% (for multicast request when λ = 0, 04). The gains are more important with SP 2 and significantly more important with SP 1. We believe that under less loaded scenarios, our method will exhibit much better performance. Indeed, by increasing the load beyond a certain limit, more and more request are declined whatever the allocation method. The performance of these methods in terms of admission will tend to get closer, to each other. This is exactly what we observe in figures 10 and 11 when λ increases. In this paper, we developed an Integer-Linear programming method for the resource allocation of multiple virtual links. Compared to existing work from the literature, its contribution lies in the conjunction of the following features: (1) the support of point-to-multipoint virtual links in addition to point-to-point virtual links, (2) the support of virtual links' delay requirements in addition to bandwidth requirements, (3) the consideration of switching resources in the allocation of resources in addition to the bandwidth of links, and (4) the support of path splitting.

Our method was evaluated on a real network topology under high loads (which is not in favour of our method). The analysis showed that our method achieve efficient resource utilisation with a relative fair distribution of the load among nodes and links. The convergence time of our method was also assessed and it proved to be satisfactory. Our method was also compared with three shortest path heuristics and it Additional experiments are however needed to cover other load models and other network topologies. This is necessary to get a more exhaustive view on the performance of our method and a more precise understanding on the impact of path splitting and parameter β of the objective function. Other perspectives to this work concern the extension of our ILP model. A first direction is to devise a more precise modelling of the switching resources consumed by each virtual link that takes more precisely into account the resources consumed by the SDN matching operations and the associated instructions.

A second direction is the inclusion of resource migration in our model in order to have a more efficient and potentially adaptive method. A last perspective concerns the implementation of our method on a real SDN/Openflow network infrastructure.

k.

  In practice, b min k is a ratio of b k , b min k = P S ratio * b k with P S ratio ∈ [0, 1]

10 Fig. 1 : 10 Fig. 2 :

 101102 Fig. 1: Acceptance rate -Unicast Requests

10 Fig. 3 : 10 Fig. 4 : 10 Fig. 5 :

 103104105 Fig. 3: Average link utilization -Unicast Requests

Fig. 6 :20Fig. 7 :

 67 Fig. 6: Convergence time -Unicast requests

Fig. 9 :

 9 Fig. 9: Unicast requests acceptance rate for β = 150

Fig. 10 :

 10 Fig. 10: Comparison with SP heuristics -Unicast requests

Fig. 11 :

 11 Fig. 11: Comparison with SP heuristics -Multicast requests

TABLE I :

 I Classification of virtual link resource allocation methods

		VL	VL	allocation method	network	supported
		type	QoS	process		resources	techniques
	[15]	P2P	BW	offline	integrated	link
	[14]	P2P	BW delay	online	integrated	link
	[16]	P2P	BW	online	stand-alone	link	path-split migration
	[11] [12]	P2P	BW	online	stand-alone	link
	[17]	P2P P2M	BW	offline	stand-alone	link
	[18]	P2P	BW	online	stand-alone	link
	[19]	P2P P2M	BW	offline	stand-alone	link
	[21]	P2P	BW	online offline	integrated	link	path-split
	[13]	P2P	BW delay	online	integrated	link
	[22]	P2P	BW	offline online	integrated	link
	our met.	P2P P2M	BW delay	online	stand-alone	link node	path-split
	links. Table I summarises the existing work according to these
	criteria (where P2P, P2M, BW and ILP respectively stand
	for point-to-point, point-to-multipoint, bandwidth and integer-
	linear Programming). It also classifies the method that we are
	proposing in this paper.

http://www.geant.net/

http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

ACKNOWLEDGMENT

This work was partially funded by the French National Research Agency (ANR) and the French Defense Agency (DGA) under the project ANR DGA ADN (ANR-13-ASTR-0024).


R Buckdahn

M Quincampoix
email: marc.quincampoix@univ-brest.fr.

J Renault

On Representation Formulas for Long Run Averaging Optimal Control Problem *

We investigate an optimal control problem with an averaging cost. The asymptotic behavior of the values is a classical problem in ergodic control. To study the long run averaging we consider both Cesàro and Abel means. A main result of the paper says that there is at most one possible accumulation point -in the uniform convergence topology -of the values, when the time horizon of the Cesàro means converges to infinity or the discount factor of the Abel means converges to zero. This unique accumulation point is explicitly described by representation formulas involving probability measures on the state and control spaces. As a byproduct we obtain the existence of a limit value whenever the Cesàro or Abel values are equicontinuous. Our approach allows to generalise several results in ergodic control, and in particular it allows to cope with cases where the limit value is not constant with respect to the initial condition.

Introduction

Let us consider the following control system

x ′ (t) = f (x(t), α(t)), α(t) ∈ A, t ∈ R, [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF] with its unique solution x(t, x 0 , α) such that x(0) = x 0 . Here f : R d ×A → R d is supposed to be bounded and Lipschitz, and A is some compact metric space. We will denote by A the set of all measurable controls α : R → A.

Given a bounded cost function l : R d × A → R, we consider two ways of averaging the cost along the trajectory x(t, x 0 , α), t ≥ 0, (Cesàro Mean) 1 T T 0 l(x(s, x 0 , , α), α(s))ds,

(Abel Mean) λ

+∞ 0 e -λs l(x(s, x 0 , , α), α(s))ds, where λ > 0 and T > 0. This leads to the definition of the following value functions:

v T (x 0 ) := 1 T inf α∈A T 0
l(x(s, x 0 , t 0 , α), α(s))ds, (2) u λ (x 0 ) := λ inf α∈A +∞ 0 e -λs l(x(s, x 0 , t 0 , α), α(s))ds.

(3)

The existence of the limit of v T , as T → +∞, and of u λ , as λ → 0 + , is a crucial problem studied in a huge literature: We refer the reader to [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF][START_REF] Arisawa | Ergodic problem for the Hamilton Jacobi Belmann equations II[END_REF][START_REF] Arisawa | On Ergodic Stochastic Control[END_REF][START_REF] Bardi | Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellmann Equations[END_REF][START_REF] Lions | Homogenization of Hamilton-Jacobi equations[END_REF][START_REF] Oliu-Barton | A Uniform Tauberian Theorem in Optimal Control[END_REF][START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] and the references therein.

The works in ergodic control deal with sufficient conditions proving the existence of a limit -in the uniform convergence topology -which is constant, i.e., which does not depend on the initial condition x 0 . These studies use different methods. For instance, the PDE method which uses the possibility of characterising the values as the unique viscosity solution of an associated Hamilton-Jacobi-Bellman equation. A typical assumption for this approach is that of coercivity of the Hamiltonian.

In the present paper we manage to consider the much harder case, where the limit is not necessarily constant (cf also [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF][START_REF] Oliu-Barton | A Uniform Tauberian Theorem in Optimal Control[END_REF]). Our main aim is to provide a representation formula of the cluster points in the uniform convergence topology of v T , as T → +∞, and of u λ , as λ → 0 + . As we will prove, there is only one possible cluster point, and the problems of the convergence of v T and of u λ will be reduced to the relative compactness of the families (v T (•)) T >0 and (u λ (•)) λ>0 . We also stress that in [START_REF] Oliu-Barton | A Uniform Tauberian Theorem in Optimal Control[END_REF] the authors have proved that, if v T converges uniformly to some function then u λ converges uniformly to the same function and conversely.

In the present work we establish two representations formulas. The first one corresponds to the case, where the cost function l does not depend on the control variable, and it is based on invariant measures for differential inclusion [START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF][START_REF] Artstein | Singularly perturbed ordinary differential equations with nonautonomous fast dynamics[END_REF]. It relates to similar questions for discrete time systems [START_REF] Renault | Uniform value in dynamic programming[END_REF][START_REF] Renault | General limit Value in Dynamic Programming[END_REF][START_REF] Venel | A Distance for probability spaces, and long term values in Markov Decision Processes and Repeated Games[END_REF]. The second representation formula is well adapted to the more general case (x, a) → l(x, a) of a cost function l depending also on the control variable, but it is based on probability measures which description with respect to the dynamical system is more involved (cf [START_REF] Gaitsgory | On a representation of the limit occupational measures set of a control system with applications to singularly perturbed control systems[END_REF][START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF][START_REF] Gaitsgory | On sets of occupational measures generated by a deterministic control system on an infinite time horizon[END_REF]).

Both representation formulas have a common structure: For any initial condition x 0 the only possible cluster point u ⋆ (•) is the supremum of all continuous bounded functions w(•) satisfying the following two conditions i) t ∈ [0, +∞) → w(x(t, x 0 , α)) is nondecreasing, for all (x 0 , α) ∈ X × A, ii) X w(x)dµ(x, a) ≤ X×A l(x, a)dµ(x, a), for all µ ∈ W , where W is a suitable set of probability measure on X × A and X ⊂ R d is a compact set which is supposed to be invariant with respect to the controlled equation [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF].

The difference between both representation formulas concerns relation ii): When the cost function l does not depend on the control variable, ii) reduces to ii) X w(x)dµ(x) ≤ X l(x)dµ(x), for all µ ∈ M, where M is the set of invariant measures of the differential inclusion. In the general case l(x, a), the set W of probability measures is defined through infinitely many linear equalities.

Both formulas crucially require the existence of a compact set X ⊂ R d invariant for [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF] and that the cost l is continuous and bounded (throughout the paper we will suppose for sake of simplicity that the cost l belongs to [0, 1]). Because the ideas of the proofs of the representations formulas for Abel and the Cesàro means are very similar, we have chosen to prove the first representation formula for the Cesàro means and the second one for the Abel means.

An important consequence of the uniqueness of the (possible) accumulation point of the values is the possibility to deduce the convergence of the values from an equicontinuity condition on the families (v T (•)) T >0 and (u λ (•)) λ>0 . We discuss several nonexpansivity conditions (see [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF]) which allows to obtain the equicontinuity and, thus, the convergence of the values (cf [START_REF] Buckdahn | Existence of Asymptotic Values for Nonexpansive Stochastic Control Systems[END_REF] for an extension to stochastic control).

Let us now describe how the paper is organised. In Section 1 we recall preliminaries and notations. Section 2 is devoted to the first representation formula with invariant measures in the case of a cost independent of the control. Section 3 concerns the general case of a cost possibly depending on the control. In Section 4 we compare briefly both obtained representation formulas. In Section 5 we discuss potential applications of the formulas and several examples. An Appendix concerning occupational measures is provided at the end of the paper.

Preliminaries, Assumptions and Notations

For any metric space U we will denote by ∆(U) the set of Borel probability measures on U and by C(U) the set of continuous functions ϕ : U → R. The notation B(U) stands for the Borel σ-algebra on U.

We will suppose throughout the article that X ⊂ R d is compact and invariant by [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF]. [START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF] Recall that this invariance means that, for all x 0 ∈ X and all measurable control α ∈ A, the trajectory t → x(t, x 0 , α) always remains in X.

We now describe the assumptions made on the coefficients f and l. Choosing as control set A a compact metric space, we suppose:

         The function l : R d × A -→ [0, 1] is continuous; The function f : R d × A -→ R d is continuous; ∃L ≥ 0, ∀(y, y ′ ) ∈ R 2d , ∀a ∈ A, f (y, a) -f (y ′ , a) ≤ L y -y ′ ; The set f (x, A) is convex, for all x ∈ X (5)
Let M ∈ R denote a real such that sup (x,a)∈X×A |f (x, a)| < M. Under assumption [START_REF] Artstein | Singularly perturbed ordinary differential equations with nonautonomous fast dynamics[END_REF] it is well known that, for all control α ∈ A and all x 0 in X, there is a unique solution x(., x 0 , α) := x(•) of (1), defined over (-∞, +∞) and satisfying x(0) = x 0 . We also recall that, for each positive T and λ, the value functions v T and u λ defined by ( 2) and (3), respectively, are continuous on X.

Given T > 0, x 0 ∈ R d and α ∈ A, we associate with the solution x(., x 0 , α) the following occupational measure µ x 0 ,α T ∈ ∆(X) defined by

µ x 0 ,α T (Q) := 1 T meas{s ∈ [0, T ], x(s, α, x 0 ) ∈ Q }, Q ∈ B(X),
where meas denotes the Lebesgue measure on R. The measure µ x 0 ,α T can be equivalently defined by the relation

X ϕdµ x 0 ,α T = 1 T T 0 ϕ(x(s, x 0 , α))ds, ϕ ∈ C(X).
We observe that µ x 0 ,α T ∈ ∆(X), where the space of probability measures ∆(X) over the compact set X is compact with respect to the topology generated by the weak convergence of measures. In the Appendix (Section 6) a description of cluster points of occupational measures is discussed.

First Representation Formula

In this section we first investigate the simpler case of a running cost l(x, a) = l(x) which does not depend on the control variable a. In this case the cost depends only on the trajectory x(•, x 0 , α), and this makes it more convenient to use a formulation of the problem in terms of differential inclusions.

We know that under assumptions (5), any solution x(•) = x(•, x 0 , α) of ( 1) is a solution of the differential inclusion

x ′ (t) ∈ F (x(t)), x(0) = x 0 , (6)
with F (x) := {f (x, a), a ∈ A}.

Conversely, for any absolutely continuous function x(•) which solves [START_REF] Artstein | The value function of singularly perturbed control systems[END_REF], there exists a control α ∈ A such that x(•) = x(•, x 0 , α). We refer the reader to [START_REF] Aubin | Differential inclusions[END_REF][START_REF] Aubin | Viability Theory[END_REF]. For x 0 in X, we denote by F (x 0 ) the set of absolutely continuous solution of (6) with initial condition x 0 , i.e., the collection of all absolutely continuous functions x : R -→ X such that x(0) = x 0 and x ′ (t) ∈ F (x(t)), a.e. Then we have:

v T (x 0 ) = 1 T inf x(•)∈F (x 0 ) T t 0 l(x(s))ds, u λ (x 0 ) = λ inf x(•)∈F (x 0 )
+∞ 0 e -λs l(x(s))ds.

One advantage of the differential inclusion is its nice topological structure. Define by F the set of all solutions of (6) in X, i.e. F = ∪ x 0 ∈X F (x 0 ). We endow F with the uniform topology

x ∞ := sup t∈R |x(t)e -M |t| |
(where M > sup (x,a)∈X×A |f (x, a)|). Thanks to assumption (5) the set F endowed with this uniform norm is a compact metric space (cf Theorem 3.5.2 in [START_REF] Aubin | Viability Theory[END_REF]). We also introduce the reachable map in time t associated with (1) (or (6):

R t X → X x 0 → {x(t, x 0 , α), α ∈ A } = {x(t), x(•) ∈ F (x 0 ) }.

Preliminaries on Invariant Measures

Let us recall some useful notions that will be used frequently in what follows (cf [START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF]).

We consider the following flow Φ on F defined for every t ∈ R by

Φ t F → F x(•) → x(• + t),
and we recall that a Borelian probability measure p ∈ ∆(F ) is invariant for Φ, if and only if p(Φ t (Γ)) = p(Γ), for all Γ ∈ B(F ), t ∈ R.

Definition 2.1 Given p ∈ ∆(F ), we associate it with the projected probability measure µ ∈ ∆(X) defined by:

µ(B) := p(< B >), B ∈ B(X), where < B >:= {x(•) ∈ F , x(0) ∈ B}.
The measure µ is equivalently defined by the relation

X ϕ(x)dµ(x) = F ϕ(x(0))dp(x • ), ϕ ∈ C(X).
If p is an invariant probability measure for Φ, then we say that the projected measure µ is a projected invariant measure on X. We denote by M the set of projected invariant measures on X.

Let us point out that M is a closed convex set of probability measures on X.

A representation Formula for Cesàro Means

Definition 2.2 We define H as the set of continuous functions w : X → [0, 1] satisfying the following two conditions: i) t ∈ [0, +∞) → w(x(t, x 0 , α)) is nondecreasing, for all (x 0 , α) ∈ X × A;

ii) X w(x)dµ(x) ≤ X l(x)dµ(x), for all µ ∈ M. We also introduce the function

v ⋆ (x 0 ) = sup{w(x 0 ), w ∈ H }, x 0 ∈ X.
Let us illustrate the previous definitions with the following example.

Example 2.3 Let X be the unit circle in R 2 , and let the uncontrolled dynamics be given by:

x ′ (t) = 0 -1 1 0 x(t). (7)
Here, the uniform (Haar) measure on X is the unique projected invariant measure, and H is the set of functions w : X → [0, 1] which are constant (by condition (i)) and not greater than 1 2π 2π 0 l(e iθ )dθ (condition (ii)). Thus, for all x 0 in X, we have v * (x 0 ) = 1 2π 2π 0 l(e iθ )dθ.

Remark 2.4

We say that the control problem is leavable, if for all x in X we have 0 ∈ F (x). This condition means that at any point x ∈ X it is possible to stop by choosing a suitable control and stay at this point forever.

We remark that for leavable problems any probability µ in ∆(X) is a projected invariant measure, and so condition (ii) of the definition of H is equivalent to w ≤ l. Then, for x 0 in X, we obtain: v ⋆ (x 0 ) = sup{w(x 0 ), w : X → [0, 1] continuous, w ≤ l and such that t ∈ [0, +∞) → w(x(t, x, α)) is nondecreasing for every α ∈ A and any x ∈ X}. Remark 2.5 We say that the problem is controllable, if for any states x and y in X, starting from x allows to approach to y arbitrarily closely, i.e., y belongs to the closure of the reachable set ∪ t≥0 R t (x 0 ). In this case all functions in H are constant (by condition (i)), and it follows that v * itself is constant and satisfies

v * (x 0 ) = inf µ∈M X l(x)dµ(x), x 0 ∈ X.
Example 2.6 Let X be the unit circle in R 2 , and let the dynamics be given by

x ′ (t) = 0 -1 1 0 a x(t), a ∈ [0, 1]. ( 8
)
Then one can generate any anticlockwise motion on X with speed varying between 0 and 1. This problem is both leavable and controllable, and so we can apply the previous remarks and obtain:

v * (x 0 ) = inf x∈X l(x), x 0 ∈ X.
Example 2.7 We consider the two-dimensional dynamics

x ′ 1 (t) = a(t)(1 -x 1 (t)) x ′ 2 (t) = a 2 (t)(1 -x 1 (t)) a(t) ∈ [0, 1], x(0) = x 0 , (9)
endowed with the cost function l

(x) = 1 -x 1 (1 -x 2 ), x = (x 1 , x 2 ) ∈ R 2 . It is easy to check that X = {(x 1 , x 2 ) ∈ [0, 1] 2 , x 1 ≥ x 2 } is an invariant set, and for x 0 ∈ X we always have x ′ 1 (t) ≥ x ′ 2 (t) ≥ 0.
Obviously, the problem is leavable, but not controllable. However, starting from any (x 1 , x 2 ) in X, by choosing arbitrarily small constant controls it is possible to approach arbitrarily closely to (1, x 2 ). Thus, all functions w in H satisfy: w(x 1 , x 2 ) ≤ x 2 . Moreover, as the function w : (x 1 , x 2 ) → x 2 belongs to H, we obtain:

v * (x 1 , x 2 ) = x 2 , x = (x 1 , x 2 ) ∈ X.
We observe that here the function v * (x 0 ) does depend on x 0 and the problem cannot be reduced to an ergodic one by changing the state space X (see cf [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] p.4).

Theorem 2.8 Suppose that the assumptions (4) and ( 5) are satisfied and that, moreover, the cost function l does not depend on the control variable a. Then any accumulation point -in the uniform convergence topology on X -of (v

T (•)) T >0 , as T → ∞, is equal to v ⋆ (•) .
Proof : Let v be an accumulation point of (v T (•)) T >0 . Then, up to a subsequence, v T converges uniformly to v as T → +∞. In order to avoid too many notations, we suppose that v T → v.

Step 1 : v ⋆ (x 0 ) ≥ v(x 0 ) For proving this, it is enough to show that v ∈ H. Let us fix arbitrarily r < t, x 0 ∈ X and α ∈ A, and let us prove v(x(r, x 0 , α)) ≤ v(x(t, x 0 , α)). Without loss of generality we can suppose r = 0. Then,

v T (x(t, x 0 , α)) = 1 T inf α T 0 l(x(s, x(t, x 0 , α), α))ds = 1 T inf α T 0 l(x(s + t, x 0 , α ⊙ α(• -t)))ds
where α runs all controls in A and

α ⊙ α(• -t)(s) = α(s), if s ≤ t, α(s -t), if s > t.
Thus,

v T (x(t, x 0 , α)) = 1 T inf α T +t t l(x(σ, x 0 , α ⊙ α(• -t)))dσ ≥ 1 T inf α T 0 l(x(σ, x 0 , α ⊙ α(• -t)))dσ - t T ≥ v T (x 0 ) - t T .
Passing to the limit as T → ∞ we get v(x(t, x 0 , α)) ≥ v(x 0 ). This proves that v satisfies the property i) of the definition of H. Now we proceed by checking that v satisfies the property ii) of the definition of H. For this end we fix µ ∈ M and show that X vdµ ≤ X ldµ.

Let T > 0. Since, for all α ∈ A,

v T (x 0 ) ≤ 1 T T 0 l(x(s, x 0 , α))ds,
we have, for any

x(•) ∈ F , v T (x(0)) ≤ 1 T T 0 l(x(s))ds = 1 T T 0 l([Φ s (x(•)](0))ds.
Now we integrate the above inequality with respect to an invariant probability measure p ∈ ∆(F ) which projection is µ. By using the Fubini Theorem and the invariance property of p, we obtain

X v T dµ = F v T (x(0))dp(x(•)) ≤ 1 T F T 0 l([Φ s (x(•)](0))dsdp(x(•)) ≤ 1 T T 0 F l([Φ s (x(•)](0))dp(x(•))ds = 1 T T 0 F l(x(0))dp(x(•))ds = F l(x(0))dp(x(•)) = X ldµ.
Consequently, taking the limit as T tends to ∞, we get X vdµ ≤ X ldµ. This proves that v ∈ F .

Step 2: v ⋆ (x 0 ) ≤ v(x 0 ) By definition of v ⋆ it is enough to show that w(x 0 ) ≤ v(x 0 ), for all w ∈ H. Let us fix arbitrarily w ∈ H.

For any arbitrarily given T > 0 and ε > 0, there exists a ε-optimal control α ε ∈ A such that 1

T T 0 l(x(s, x 0 , α ε ))ds ≤ v T (x 0 ) + ε (10)
We consider the occupational measure on µ x 0 ,αε T ∈ ∆(X). This measure µ x 0 ,αε T can be regarded as the projection (in the sense of Definition 2.1) of the occupational measure p T on F defined by

F Gdp T = 1 T T 0 G(Φ s (x(•, x 0 , α ε )))ds, G ∈ C(F ).
On the other hand, relation [START_REF] Bardi | Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellmann Equations[END_REF] can be written as

X ldµ x 0 ,αε T ≤ v T (x 0 ) + ε. (11)
As a consequence of Prohorov's Theorem, the compactness of the spaces F and X implies that of ∆(F ) and ∆(X). Consequently, there is (p, µ) ∈ ∆(F ) × ∆(X) such that (p T , µ x 0 ,αε T ) → (p, µ) weakly along a subsequence, as T → +∞. Once again, for simplicity, let us denote this weakly converging subsequence by (p T , µ x 0 ,αε T ). Referring to Theorem 6.2 in [START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF] or Lemma 6.1 of the Appendix, we know that p is an invariant probability measure and, consequently, also µ is invariant, i.e., µ ∈ M. Consequently, as w ∈ H, we have X wdµ ≤ X ldµ. On the other hand, since w satisfies the monotonicity condition i) in Definition 2.2, we have

X wdµ x 0 ,αε T = 1 T T 0 w(x(s, x 0 , α ε ))ds ≥ w(x 0 ). ( 12
)
The relations [START_REF] Buckdahn | Existence of Asymptotic Values for Nonexpansive Stochastic Control Systems[END_REF] and [START_REF] Cannarsa | Vanishing discount limit for nonexpansive optimal control and differential games[END_REF], combined with X wdµ ≤ X ldµ, allow to pass to the limit as T → +∞ and yield

v(x 0 ) + ε ≥ X ldµ ≥ X wdµ ≥ w(x 0 ).
To finish the proof of the claimed result, it suffices to observe that ε > 0 has been chosen arbitrarily. QED Remarks 2.9

1. The proof of Theorem 2.8 shows that the above result remains valid, when we replace M by the set of accumulation points (in the sense of the topology of weak convergence) of occupational measures µ x 0 ,α Tn (T n ↑ +∞):

M(x 0 ) := { lim n µ x 0 ,α Tn , T n → +∞, α ∈ A }.
2. Observe that M(x 0 ) ⊂ M thanks to Lemma 6.1.

3. Since v T (x 0 ) = inf α X l(x)dµ x 0 ,α T (x), we deduce from Theorem 2.8 the following "pointwise" representation formula

v ⋆ (x 0 ) = inf µ∈M(x 0 ) X ldµ. (13)

A representation formula for Abel Means

At the end of this section we provide a representation formula for cluster points of u λ , when λ → 0 + . Theorem 2.10 We suppose that the assumptions (4) and ( 5) are satisfied and that, moreover, the cost function l does not depend on the control variable a. Then any accumulation point -in the uniform convergence topology -of

(u λ (•)) λ>0 as λ → 0 + , is equal to v ⋆ (•).
We omit the proof of this result, since it is based on similar arguments than those used in Theorem 2.8, with the only real difference that now Lemma 6.2 in the appendix instead of Lemma 6.1 has to be used.

Second representation formula

This section is devoted to the investigation of the general case of a cost function l(x, a) which may depend on the control variable a.

3.1 On the accumulation points of u λ as λ → 0.

We begin our studies with establishing a representation formula for the accumulation points of u λ as λ → 0 + . Recall that u λ has been defined in (3).

Discounted Occupational Measures on X × A

Given any λ > 0, x 0 and a control α ∈ A, we define the discounted occupational measure ν x 0 ,α λ ∈ ∆(X × A) as follows:

X×A ϕdν x 0 ,α λ (x, a) := λ +∞ 0 e -λs ϕ(x(s, x 0 , α), α(s))ds, ϕ ∈ C(X × A),
and introduce the following set of discounted occupational measures over X × A:

Γ λ (x 0 ) := {ν x 0 ,α λ ∈ ∆(X × A), α ∈ A}.
We observe that, for all

ν x 0 ,α λ ∈ Γ λ (x 0 ) and ϕ ∈ C 1 (X), X×A (∇ϕ(x) • f (x, a) + λ(ϕ(x 0 ) -ϕ(x))) dν x 0 ,α λ (x, a) = 0. (14) Indeed X×A ∇ϕ(x) • f (x, a)dν x 0 ,α λ (x, a) = λ +∞ 0 e -λs ∇ϕ(x(s, x 0 , α))f (x(s, x 0 , α), α(s))ds = λ +∞ 0 d ds [e -λs ϕ(x(s, x 0 , α))] + λe -λs ϕ(x(s, x 0 , α)) ds = -λϕ(x 0 ) + λ 2 +∞ 0 e -λs ϕ(x(s, x 0 , α))ds = -λ X×A (ϕ(x 0 ) -ϕ(x))dν x 0 ,α λ (x, a).
This means that Γ λ (x 0 ) ⊂ W λ (x 0 ), where

W λ (x 0 ) := {ν ∈ ∆(X × A) : X×A (∇ϕ(x) • f (x, a) + λ(ϕ(x 0 ) -ϕ(x))) dν(x, a) = 0, for all ϕ ∈ C 1 (X)}.
Since the set W λ (x 0 ) is defined by linear equalities, it is convex. Moreover, by Prohorov's Theorem it is compact. Consequently, co(Γ λ (x 0 )) ⊂ W λ (x 0 ), where co denotes the closed convex hull. Now if ν n ∈ W λn (x 0 ) and ν n ⇀ ν for some sequence λ n → 0 + , then, obviously, ν belongs to the set

W := {ν ∈ ∆(X × A) : X×A ∇ϕ(x) • f (x, a)dν(x, a) = 0, for all ϕ ∈ C 1 (X)}. (15)
Thus, lim sup

λ→0 + co(Γ λ (x 0 )) ⊂ W,
where lim sup λ→0 + co(Γ λ (x 0 )) denotes the set of accumulation points 1 of all sequences ν n ∈ co(Γ λn (x 0 )). The above inclusion has a kind of converse as stated in the following Lemma 3.1 (see [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF], Proposition 6.1) We have

lim λ→0 + d H (co(Γ λ (X)), W ) = 0, ( 16
)
where d H is the Haussdorff distance associated with any distance d which is consistent with the weak convergence of measures in ∆(X × A).

Here Γ λ (X) = x 0 ∈X Γ λ (x 0 ). Recall that the Haussdorff distance d H between two sets M 1 and M 2 is given by

d H (M 1 , M 2 ) = max{ sup µ∈M 1 d(µ, M 2 ), sup µ∈M 2 d(µ, M 1 )}.
1 In fact, lim sup λ→0 + co(Γ λ (x 0 )) is the upper Kuratowski limit of co(Γ λ (x 0 )) (cf for instance [START_REF] Aubin | Set-Valued Analysis[END_REF]).

Remark 3.2 -The distance d on ∆(X × A) could be any distance compatible with the weak convergence of measures, for instance a Wasserstein distance [START_REF] Villani | Topics in Optimal transportation[END_REF] or a distance defined through a dense countable family of elements of C(X × U), cf, e.g., [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF].

-The fact that relation ( 16) is independent of the distance d relies on the fact that it can be equivalently written as

lim λ→0 + coΓ λ (X) = W,
where lim denotes the Kuratowski limit of sets, see [START_REF] Aubin | Set-Valued Analysis[END_REF].

Representation formula for Abel Means

Definition 3.3 For all x 0 in X we set u ⋆ (x 0 ) := sup{w(x 0 ), w ∈ K} where K denotes the set of all functions w : X → [0, 1] which are continuous and satisfy the following conditions:

i) t ∈ [0, +∞) → w(x(t, x 0 , α)) is nondecreasing, for all (x 0 , α) ∈ X × A; ii) X×A w(x)dµ(x, a) ≤ X×A l(x, a)dµ(x, a), for all µ ∈ W .
Recall that the set W has been defined in [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF].

Theorem 3.4

We suppose that the assumptions ( 4) and ( 5) hold true. Then any accumulation point -in the uniform convergence topology -of (u λ (•)) λ>0 as λ → 0 + , is equal to u ⋆ (•).

Proof : Let us consider any accumulation point u of (u λ (•)) λ>0 . Then, along a subsequence, u λ converges uniformly to u as λ → 0 + . In order to simplify the notation, let us suppose that u λ → u.

Step 1: u ⋆ (x 0 ) ≥ u(x 0 ) For proving this assertion, it suffices to show that u ∈ K.

Let us fix any r < t, x 0 ∈ X and α ∈ A, and let us show that u(x(r, x 0 , α)) ≤ u(x(t, x 0 , α)). Without loss of generality we can suppose r = 0. Recalling the definition of u λ , we observe that

u λ (x(t, x 0 , α)) = λ inf α∈A +∞ 0 e -λs l(x(s, x(t, x 0 , α), α), α(s))ds = λ inf α∈A +∞ 0 e -λs l(x(s + t, x 0 , α ⊙ α(• -t)), α ⊙ α(• -t)(s + t))ds, where α ⊙ α(• -t)(s) := α(s), if s ≤ t, α(s -t), if s > t.
Thus, with the help of a change of variables σ = t + s we obtain

u λ (x(t, x 0 , α)) = λe λt inf α∈A +∞ t e -λσ l(x(σ, x 0 , α ⊙ α(• -t)), α ⊙ α(• -t)(σ))dσ ≥ λe λt inf α∈A [ +∞ 0 e -λσ l(x(σ, x 0 , α ⊙ α(• -t)), α ⊙ α(• -t)(σ))dσ - t 0 e -λσ l(x(σ, x 0 , α ⊙ α(• -t)), α ⊙ α(• -t)(σ))dσ] ≥ λe λt inf α∈A +∞ 0 e -λσ l(x(σ, x 0 , α ⊙ α(• -t)), α ⊙ α(• -t)(σ))dσ -(e λt -1)
≥ e λt u λ (x 0 ) -(e λt -1). Finally, passing to the limit as λ → 0 + we get u(x(t, x 0 , α)) ≥ u(x 0 ). This proves that u satisfies property i) of the definition of K.

Now we proceed with checking that u satisfies property ii) of the definition of K. Let us consider any λ ′ < λ and the discounted occupational measure ν x 0 ,α λ ′ ∈ ∆(X × A) associated with (x 0 , α) ∈ X × A and λ ′ > 0. Then, taking into account that u λ (y) ≤ λ ∞ 0 e -λr l(x(r, y, α(• + s)), α(r + s))dr, y ∈ X, a forward computation combined with Fubini's theorem and a change of variables yield

X×A u λ dν x 0 ,α λ ′ = λ ′ ∞ 0 e -λ ′ s u λ (x(s, x 0 , α))ds ≤ λ ′ ∞ 0 e -λ ′ s λ ∞ 0 e -λr l(x(r, x(s, x 0 , α), α(• + s)), α(r + s))drds = λ ′ ∞ 0 e -λ ′ s λ ∞ 0 e -λr l(x(s + r, x 0 , α), α(r + s))drds = λ +∞ 0 e -λr λ ′ e λ ′ r
+∞ r e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσdr = λ +∞ 0 e -λr {λ ′ e λ ′ r +∞ 0 e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσ -λ ′ e λ ′ r r 0 e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσ}dr

= λ +∞ 0 e -λr {λ ′ (1 + e λ ′ r ) +∞ 0 e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσ -λ ′ +∞ 0 e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσ -λ ′ e λ ′ r r 0 e -λ ′ σ l(x(σ, x 0 , α), α(σ))dσ}dr ≤ λ +∞ 0 e -λr X×A ldν x 0 ,α λ ′ dr + λ +∞ 0 e -(λ-λ ′ )r dr. Consequently, X×A u λ dν ≤ X×A ldν + λ ′ λ -λ ′ , for all ν ∈ Γ λ ′ (X).
Then, by taking the limit as λ ′ → 0 + and considering Lemma 3.1, we get X×A u λ dν ≤ X×A ldν, for all ν ∈ W.

Letting now λ tend to 0 + , we obtain X×A udν ≤ X×A ldν, for all ν ∈ W, and this is just condition ii) in the definition of K.

Step 2: u ⋆ (x 0 ) ≤ u(x 0 ) Let us fix any w ∈ K and prove that w(x 0 ) ≤ u(x 0 ). For an arbitrarily given but fixed ε > 0 we consider an ε-optimal control α λ,ε ∈ A for u λ (x 0 ),

X×A ldν x 0 ,α λ,ε λ = λ ∞ 0 e -λs l(x(s, x 0 , α λ,ε ), α λ,ε (s))ds ≤ ε + u λ (x 0 ). ( 17
)
By Prokohov's Theorem, as λ → 0 + , ν x 0 ,α λ,ε λ converges weakly along a subsequence to some measure ν ∈ ∆(X × A). Once again we suppose for simplicity of notation that ν x 0 ,α λ,ε λ ⇀ ν. By taking the limit λ → 0 + , we deduce from [START_REF] Lions | Homogenization of Hamilton-Jacobi equations[END_REF] that

X×A ldν ≤ u(x 0 ) + ε. (18) Moreover, since ν x 0 ,α λ,ε λ ∈ Γ λ (x 0 ) ⊂ coΓ λ (X), Lemma 3.1 implies that ν ∈ W . Conse- quently, from condition ii) of Definition 3.3 we have X×A wdν ≤ X×A ldν. ( 19
)
On the other hand, since w satisfies condition i) of Definition 3.3, we also have

w(x 0 ) = λ ∞ 0 e -λs w(x 0 )ds ≤ λ ∞ 0 e -λs w(x(s, x 0 , α λ,ε ), α λ,ε (s))ds = X×A wdν x 0 ,α λ,ε λ .
Hence, letting λ tend to 0 + , this gives

w(x 0 ) ≤ X×A wdν. (20)
Finally, combining [START_REF] Oliu-Barton | A Uniform Tauberian Theorem in Optimal Control[END_REF], [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] and [START_REF] Renault | Uniform value in dynamic programming[END_REF], we obtain w(x 0 ) ≤ ε + u(x 0 ), which is just the wished conclusion, recalling that ε > 0 has been chosen arbitrarily. QED Remark 3.5 Condition i) of Definition 3.3 of K can be translated equivalently in the following Hamilton-Jacobi equation satisfied by u ⋆ (•) in viscosity sense:

inf a∈A ∇u ⋆ (x), f (x, a) = 0, x ∈ X. (21)
Indeed, the stability result for viscosity solutions (see [START_REF] Bardi | Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellmann Equations[END_REF]) enables us to pass to the limit λ → 0 + in the Hamilton-Jacobi equation satisfied by u λ (•), and this gives precisely (21).

On Limits of v T as T → +∞.

This subsection is devoted to the study of a representation formula for the accumulation points of the value functions v T as T → ∞ in the case of a control l depending on the control variable (Recall the definition (2) of v T ).

Occupational Measures on X × A

Given any T > 0 and (x 0 , α) ∈ X × A, we define the occupational measure µ x 0 ,α T ∈ ∆(X × A) by the following relation:

X×A ϕdµ x 0 ,α T (x, a) := 1 T T 0 ϕ(x(s, x 0 , α), α(s))ds, for all ϕ ∈ C(X × A),
and we introduce the set of occupational measures

Γ T (x 0 ) := {µ x 0 ,α T ∈ ∆(X × A), α ∈ A}.
In particular, we observe that

X×A < ∇ϕ(x), f (x, a) > dµ x 0 ,α T (x, a) = 1 T (ϕ(x(T, x 0 , α)) -ϕ(x 0 )), ϕ ∈ C 1 (X). ( 22
)
This property allows to deduce easily that, if a sequence µ n ∈ Γ Tn (x 0 ) converges weakly to some µ, as T n → +∞, then µ ∈ W .

As in Lemma 3.1 the set W can be somehow understood as the limit of the set of occupational measures. More precisely, we have the following with Γ T (X) = x 0 ∈X Γ T (x 0 ):

Lemma 3.6 (See [14], Theorem 2.1) lim T →+∞ d H (co(Γ T (X)), W ) = 0, ( 23
)
where d H is the Haussdorff distance associated with any distance d which is consistent with the weak convergence of measures in ∆(X × A).

Remark 3.7

The relation ( 23) can be equivalently written as

lim T →∞ coΓ T (X) = W,
where lim denotes the Kuratowski limit.

Representation formula for Cesàro Means

Theorem 3.8 Let us suppose that the assumptions (4) and ( 5) are satisfied. Then any accumulation point in the sense of the uniform convergence topology of (v T (•)) T >0 , as T → +∞, coincides with u ⋆ (•).

We omit the proof here, because it is based on the same ideas as that for Theorem 3.4. The main difference here consists in the use of the occupational measures described in Section 3.2.1 instead of the discounted occupational measures defined in Section 3.1.1.

Comparison between both representation formulas

In the Sections 1 and 2 we have obtained two representations of different nature: While the first one is based on invariant measures and concerns mainly the case where l is independent of the control, the second one is based on measures which are limits of occupational measures on the product space X ×A. In this section we discuss the relations between the both approaches.

Invariant measure approach

A natural question is the possibility to use an approach based on invariant measures (as that in Section 2) also in the case of a running cost l(x, a) which depends on the control variable. In fact, this is possible to a certain extent, if one equips the space of controls with a weak L 2 -topology. Let us be more precise and discuss this question.

We define by G the set of all pairs (x(•), α(•)) solving equation ( 1) on (-∞, +∞), and we equip G with the product topology defined by a following norm for the x(•) component weak -topology associated with the following

L 2 norm α(•) L 2 := ( +∞ -∞ |α(t)| 2 e -M |t| dt) 1 2 ,
for the α(•) component.

From [START_REF] Aubin | Set-Valued Analysis[END_REF] we now that the space G is (sequentially) compact (cf Theorem 3.5.2 in [START_REF] Aubin | Viability Theory[END_REF]). Hence, since the topology of G is metrizable, G can be considered as a complete metric space and Prohorov's Theorem can be used.

Let us define the following continuous flow ϕ = (ϕ t ) t∈R on G by putting, for t ∈ R,

ϕ t G → G (x(•), α(•)) → (x(• + t), α(• + t)).
The main difficulty in the use of the approach of Section 2 consists in the fact that, for defining the measures, we need to consider G ldp for p ∈ ∆(G), and we have to pass to the limit in such integrals. But this requires that through the function l one can define continuous functions on the space G endowed with the weak topology introduced above.

One possible way is to observe that the mapping

G s G → R (x(•), α(•)) → s 0 ϕ(x(r), α(r))dr
is continuous on G, when ϕ(x, a) is continuous in x and affine with respect to a.

Then we can associate with any p ∈ ∆(G) a family (ν s ) s>0 of probability measures ν s ∈ ∆(X × A) defined by the relation

X×A ϕ(x, a)dν s (x, a) := 1 s G s 0 ϕ(x(r), α(r))drdp(x, α),
satisfied by all functions ϕ : X × A → R continuous in x and affine in a.

Thus we are able to state and prove results similar to those of Section 2. We define M as the set of all µ ∈ ∆(X × A) which are accumulation points -in the sense of the weak convergence of measures -for (ν s ) s>0 associated with all possible invariant probability measures p ∈ ∆(G) through the above relation.

Definition 4.1 For x 0 in X we set v ⋆ (x 0 ) := sup{w(x 0 ), w ∈ H }
where H is the set of all functions w : X → [0, 1] which are continuous and satisfy the following both condition:

-i) The function t ∈ [0, +∞) → w(x(t, x 0 , α)) is nondecreasing, for every

(x 0 , α) ∈ X × A; -ii) X×A w(x)dµ(x, a) ≤ X×A l(x, a)dµ(x, a), µ ∈ M.
Proposition 4.2 Suppose that the assumptions ( 4) and ( 5) hold true and that, moreover, a → l(x, a) is affine, for all x ∈ X. Then any accumulation point -in the sense of the uniform convergence topology -of (v

T (•) T >0 , as T → ∞, is equal to v ⋆ .
We also have the corresponding result for the accumulation points of the sequence (u λ (•)) λ>0 .

Proposition 4.3 If the assumptions ( 4) and ( 5) are satisfied and a → l(x, a) is affine, for all x ∈ X, then any accumulation point -in the sense of the uniform convergence topology -of (u λ (•)) λ>0 , as λ → 0 + , coincides with v ⋆ .

We do not prove both above propositions because, firstly, the representation formulas (3.4) and (3.8) are more general (they do no not require that l is affine), secondly, the definition of M is less direct that those in Section 2, and last not least, the proofs are rather technical (due to the topology on G) and this for a result weaker than (3.4) and (3.8).

The case of a cost independent of the control variable

Let us now discuss the case of a cost function l which is independent of the control variable.

In this case, we have two different representation formulas in Sections 2 and 3. We will explain how the results of Section 2 can be deduced from those of Section 3 thanks to Proposition 4.4 which is stated in this subsection and concerns the relation between the set W (defined in [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] ) and the set M given by Definition 2.1. One can deduce from ( 23) and Lemma 6.1 that

Π X (W ) ⊂ M,
where Π X (m) ∈ ∆(X) denotes the projection on X of a measure m ∈ ∆(X ×A). However, it is not clear a priori if the above inclusion is even an equality. Such an equality would imply that the both types of representation formula are in fact the same. Let us consider µ ∈ M and an associated invariant measure p ∈ ∆(F ). Let us also fix an arbitrary ϕ ∈ C 1 (X). Then, for all t > 0,

0 = F ϕ(Φ t (x • )(0))dp(x • ) - F ϕ(x(0)•)dp(x • ) = F ϕ(x(t))dp(x • ) - F ϕ(x(0))dp(x • ).
Then, dividing by t and letting t → 0 + , we obtain by the dominated convergence theorem that

0 ≤ F sup a∈A ∇ϕ(x(0)), f (x(0), a) dp(x • ) = X sup a∈A ∇ϕ(x), f (x, a) dµ(x).
By replacing in the above relation ϕ by -ϕ, we obtain2

X inf a∈A ∇ϕ(x), f (x, a) dµ(x) ≤ 0 ≤ X sup a∈A ∇ϕ(x), f (x, a) dµ(x), µ ∈ M.
Thus, for the particular case where f (x, a) does not depend on a, we have

X ∇ϕ(x), f (x) dµ(x) = 0, µ ∈ M,
and, consequently, Π X (W ) = M. In fact, this relation is valid in a more general context, as it is stated in the following Proposition 4.4 Let the set W be defined by [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] and the set M be given by Definition 2.1. Then Π X (W ) = M. (24) Before proving the above Proposition we state two auxiliary results which proofs are postponed to the end of the section. Lemma 4.5 For every x(•) ∈ F there exists a measurable control α x(•) ∈ A such that, for almost all t ∈ R, we have x ′ (t) = f (x(t), α x(•) (t)) and such that, moreover, the mapping

F → A x(•) → α x(•)
is measurable, where A is endowed with the L 2 (e -m A |t| dt) topology3 and F is equipped with the uniform topology described in Section 2. Lemma 4.6 For all t, t ′ in R and all ϕ ∈ C 1 (X) we have

F t ′ t ∇ϕ(x(s)), f (x(s), α x(•) (s)) dsdp(x • ) = 0,
for any invariant measure p ∈ ∆(F ).

Proof of Proposition 4.4: Since we already know that Π X (W ) ⊂ M, we only need to prove the converse inclusion. Let us consider an arbitrary µ ∈ M and let p ∈ ∆(F ) be an associated invariant measure. We want to show that µ ∈ Π X (W ).

For this end, for any h > 0, let γ h ∈ ∆(X × A) be the probability measure defined by the relation

X×A ψdγ h = F 1 h h 0 ψ(x(s), α x(•) (s))dsdp(x • ), ψ ∈ C(X × A).
We observe that the above integral is well defined thanks to Lemma 4.5. Moreover, by Prokhorov's Theorem we know that there exists an accumulation point γ ∈ ∆(X × A) of γ h as h → 0 + . By abuse of notation we suppose that γ h ⇀ γ weakly.

We claim that Π X (γ) = µ. Indeed, for any fixed ϕ ∈ C(X) we have thanks to the dominated convergence theorem

X ϕdΠ X (γ) = X×A ϕ(x)dγ(x, a) = lim h→0 + X×A ϕ(x)dγ h (x, a) = lim h→0 + F 1 h h 0 ϕ(x(s))dsdp(x • ) = F ϕ(x(0))dp(x(•)) = X ϕ(x)dµ(x). Now, again for ϕ ∈ C 1 (X), we observe that X ∇ϕ(x), f (x, a) dγ(x, a) = lim h→0 + X×A ∇ϕ(x), f (x, a) dγ h (x, a) = lim h→0 + F 1 h h 0 ∇ϕ(x(s)), f (x(s), α x(•) (s)) dsdp(x • ) = 0
due to Lemma 4.6. But, X ∇ϕ(x), f (x, a) dγ(x, a) = 0, for all ϕ ∈ C 1 (X), means that γ ∈ W .

Hence µ = Π X (γ) ∈ Π X (W ), and the proof is complete.

QED

Let us now come to the proof of the auxiliary lemmas.

Proof of Lemma 4.5 : It is easy to show that the function

D F → L 2 (R → X; e -m A |t| dt) x(•) → x ′ (•)
has a closed graph with respect to the F ×L 2 (R → X; e -M |t| dt) product topology. Hence, it is in particular measurable. Let us now show that the set-valued map

E Graph(E) → L 2 (R → A; e -m A |t| dt) (x(•), x ′ (•)) → {α(•) ∈ L 2 (e -m A |t| dt), x ′ (t) = f (x(t), α(t)), for a.e. t ∈ R} is measurable with respect to the (F × L 2 (R → X; e -M |t| dt)) -L 2 (R → A, e -m A |t| dt)
topology. We know that E has nonempty images. Once again the measurability of E is a consequence of the fact that E has a closed graph, and this we will prove now.

For this end we consider a sequence (x n (•), x ′ n (•), α n (•)) ∈ Graph(E) and we suppose that (x n (•), x ′ n (•), α n (•)) converges to some (x(•), y(•), α(•)) in the F × L 2 (R → X; e -M |t| dt) × L 2 (R → A; e -m A |t| dt) product topology. We want to prove that α(•) ∈ E(x(•), y(•)). As Graph(D) is closed, we know already that y(•) = x ′ (•). On the other hand, since α n (•) converges to α(•) in L 2 (R → A; e -m A |t| dt), it converges also in measure dt. Let us denote by ω f (•) the modulus of continuity of f (x, a) with respect to the variable a on the compact X × A. Then, for all t ∈ R,

|x(t) -x(0) - t 0 f (x(s), α(s))ds| ≤ |x n (t) -x n (0) - t 0 f (x n (s), α n (s))ds| + |x n (t) -x(t)| + |x(0) -x n (0)| + t 0 |f (x n (s), α n (s)) -f (x(s), α n (s))ds| + t 0 |f (x(s), α n (s)) -f (x(s), α(s))|ds ≤ 2 x n (•) -x(•) F e M |t| + K x n (•) -x(•) F t 0 e M |s| ds + t 0 ω f (|α n (s)) -α(s)|)ds,
where we have used for the latter estimate the Lipschitz continuity of f in x and its uniform continuity in a. We notice that, thanks to the dominated convergence theorem, the latter integral converges to zero, as n → +∞, and we also observe that all the other terms vanish in the limit. Consequently,

x(t) = x(0) + t 0 f (x(s), α(s))ds, for all t, but this means that α(•) ∈ E(x(•), x ′ (•)). Therefore, the graph of E is closed.
This implies that the set valued map

Z F → L 2 (R → A; e -m A |t| dt) x(•) → {α(•) ∈ L 2 (e -m A |t| dt), x ′ (t) = f (x(t), α(t)) for a.e. t ∈ R}
is measurable, since it is just a composition between the two measurable maps E and D. Finally, the measurable selection theorem (cf, e.g., Theorem 8.1.3 in [START_REF] Aubin | Set-Valued Analysis[END_REF]) enables us to choose a measurable selection x(•) → α x(•) (•) of Z. The proof is complete.

QED

Proof of Lemma 4.6: Let p ∈ ∆(F ) be an arbitrary invariant measure. Let us fix any t, t ′ ∈ R with t < t ′ and let ϕ ∈ C 1 (X). Since p is an invariant measure, we know that

F ϕ(x(s + h)) -ϕ(x(s)) h dp(x(•)) = 0, (25)
for all h > 0 and all s ∈ [t, t ′ ]. On the other hand, as for all x(•) ∈ F , ds-a.e. in [t, t ′ ], lim

h→0 + ϕ(x(s + h)) -ϕ(x(s)) h = ∇ϕ(x(s)), f (x(s), α x(•) (s)) ,
we get from the dominated convergence theorem that, for all x(•) ∈ F ,

lim h→0 + t ′ t ϕ(x(s + h)) -ϕ(x(s)) h ds = t ′ t ∇ϕ(x(s)), f (x(s), α x(•) (s)) ds. Thus, F t ′ t ∇ϕ(x(s)), f (x(s), α x(•) (s)) dsdp(x(•)) = F lim h→0 + t ′ t ϕ(x(s + h)) -ϕ(x(s)) h dsdp(x(•)).
Consequently, applying Fatou's Lemma and Fubini's Theorem, we obtain in view of (25)

F t ′ t ∇ϕ(x(s)), f (x(s), α x(•) (s)) dsdp(x(•)) ≤ lim inf h→0 + F t ′ t ϕ(x(s + h)) -ϕ(x(s)) h dsdp(x(•)) = lim inf h→0 + t ′ t F ϕ(x(s + h)) -ϕ(x(s)) h dp(x(•))ds = 0.
Hence, for all ϕ ∈ C 1 (X),

F t ′ t ∇ϕ(x(s)), f (x(s), α x(•) (s)) dsdp(x(•)) ≤ 0.
By changing ϕ into -ϕ, we complete the proof.

QED 5 Applications and Examples

One of the main advantages of the representation formulas provided in the previous sections lies in the fact that the convergence of averaging values is deduced from equicontinuity.

Corollary 5.1 We suppose that the assumptions (4) and ( 5) are satisfied. Then, if the family (v T (•)) T >0 is equicontinuous, it converges uniformly to u ⋆ (•), as T → ∞. The same holds true for the family (u λ (•)) λ>0 : Its equicontinuity implies its uniform convergence to u ⋆ (•), as λ → 0 + . Indeed, from the Arzelà-Ascoli Theorem we deduce that (v T (•)) T >0 and (u λ (•)) λ>0 are relatively compact, and by the Theorems 2.8 and 2.10 we obtain the uniform convergence of these both families of functions to u ⋆ (•). Let us illustrate this observation in several cases.

Nonexpansivity

Corollary 5.2 (Nonexpansivity [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF]) Let us suppose that the assumptions (4), (5) as well as the following nonexpansivity condition hold true: There is some c ∈ R+ such that, for all x 1 , x 2 ∈ X,

sup a 1 ∈A inf a 2 ∈A max{ x 1 -x 2 , f (x 1 , a 1 ) -f (x 2 , a 2 ) , |l(x 1 , a 1 ) -l(x 2 , a 2 )| -c|x 1 -x 2 |} ≤ 0.
Then both v T (•) and u λ (.) converge uniformly to u ⋆ , as T → ∞ and λ → 0 + , respectively.

Under the above nonexpansivity condition [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] proves the existence of a limit. A crucial argument in the proof enables to deduce the equicontinuity of the families (v T (•)) T >0 and (u λ (•)) λ>0 from the above nonexpansivity condition (26). Finally, from Corollary 5.1 we obtain the uniform convergence to v ⋆ (•). Let us also observe that for a Lipschitz cost l(x) independent of the control variable a the nonexpansivity condition reduces to sup

a 1 ∈A inf a 2 ∈A x 1 -x 2 , f (x 1 , a 1 ) -f (x 2 , a 2 ) ≤ 0, x 1 , x 2 ∈ X. (26)
Indeed the nonexpansivity condition of Corollary 5.2 is obtained from (26) by choosing as constant c a Lipschitz constant of l.

Let us also point out that [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] studies several extensions of the nonexpansivity condition (26). However, for all these extensions we obtain the equicontinuity of the families (v T (•)) T >0 and (u λ (•)) λ>0 and, hence, with the help of the Theorems 2.8 and 2.10, their uniform convergence to u ⋆ (•). We also mention the paper [START_REF] Cannarsa | Vanishing discount limit for nonexpansive optimal control and differential games[END_REF], where equicontinuity and monotone convergence are proved by PDE arguments.

The interest of the nonexpansivity property lies in the fact that under this condition the limit u ⋆ (•) may depend on the initial condition x 0 . We refer the reader to several examples discussed in Section 2.2 of [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF]. Unlike the nonexpansivity property, the following stronger condition -called dissipativity condition -implies that the limit u ⋆ (•) is a constant independent of x 0 (see [START_REF] Artstein | The value function of singularly perturbed control systems[END_REF]):

sup a 1 ∈A inf a 2 ∈A < x 1 -x 2 , f (x 1 , a 1 ) -f (x 2 , a 2 ) >≤ -C x 1 -x 2 2 ,
for all x 1 , x 2 ∈ X and some constant C > 0. This convergence to a constant phenomenon will be met also in the case discussed in the following subsection.

Coercivity of the Hamiltonian and controllability

Let us focus our consideration upon the Abel means u λ , when the cost function l is Lipschitz (Remark that in this case also u λ is Lipschitz). Our aim is to discuss and to comment a well known PDE approach with the help of the results obtained in the present paper (See [START_REF] Arisawa | Ergodic problem for the Hamilton-Jacobi-Bellman equation. I. Existence of the ergodic attractor[END_REF][START_REF] Arisawa | Ergodic problem for the Hamilton Jacobi Belmann equations II[END_REF][START_REF] Arisawa | On Ergodic Stochastic Control[END_REF], [START_REF] Bardi | Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellmann Equations[END_REF], [START_REF] Lions | Homogenization of Hamilton-Jacobi equations[END_REF] and the references therein).

A typical assumption in this pde approach is the coercivity of the Hamiltonian : Let us explain roughly4 this method in view of our result Theorem 2.10. Since, thanks to our assumptions u λ is bounded by some constant C independent of λ, the coercivity assumption (27) together with (28) enables us to obtain that 1 λ ∇u λ is bounded by some constant M independent of λ. This implies not only that u λ is equi-Lipschitz (and thus, by Corollary 5.1, lim λ→0+ u λ = u ⋆ ), but also that the Lipschitz constant of u λ is bounded by Mλ and, hence, its convergence to zero. It follows that the function u ⋆ must be constant.

It is worth pointing out that in this case equation ( 21) -which is deduced from condition i) of the definition of K -does not bring any information on the constant u ⋆ . But condition ii) of the definition of K does imply that the constant u ⋆ is given by

u ⋆ = inf µ∈W X×A ldµ,
which can be compared to results obtained through the weak KAM theory [START_REF] Fathi | Weak KAM theorem in Lagrangian dynamics[END_REF].

Finally, let us mention that the coercivity (27) of the Hamiltonian is usually deduced from controllability conditions on the control system (1) (cf [START_REF] Bardi | Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellmann Equations[END_REF]). Such a typical controllability assumption is that of the existence of an ω > 0 such that, for all x ∈ R d , B(0, ω) := {y ∈ R d , |y| < ω} ⊂ F (x) = {f (x, a), a ∈ A}. (29) Similar ideas than those described above for Abel means can be used to show that under the coercivity condition (27) the values v T converge uniformly to a constant, as T → +∞.

Examples

We have seen in examples that the limit u ⋆ may not be constant. Let us revisit the examples 2.3 and 2.7 from Section 2.

Example 2.3 Here the coercivity condition (27) is not fulfilled. Indeed, it cannot be satisfied, when the dynamics and the cost function do not depend on the control. But, on the other hand, if the cost function l : x ∈ R 2 → l(x) ∈ [0, 1] is Lipschitz and independent of a, Corollary 5.2 shows that, choosing as c the Lipschitz constant of l, we have the convergence of u λ and v T , as λ → 0+ and T → +∞, respectively.

Example 2.7 By explicit computations it can be shown that v T converges to v ⋆ (x) = x 2 (cf [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF] p.4). However, also a variant of Corollary 5.2 can be used here. Indeed, it is easy to prove that here, for the given example,

  x(.) ∞ := sup t∈R |x(t)e -M |t| | (Recall that M > sup (x,a)∈X×A |f (x, a)|) and by the L 2

  is based on the fact that u λ is the unique viscosity solution of the Hamilton-Jacobi equationV (x) + H(x, H(x, p) := max a∈A { -f (x, a), pl(x, a)}, x, p ∈ R d .

  sup

  1 , x 2 ) + f (x 2 , a 2 ), ∂ ∂x 2 ∆(x 1 , x 2 ) ≤ 0 (30) with ∆(x, y) := |x 1y 1 | + |x 2y 2 |.

This is also related to the relation 0 ∈ X F (x)dµ(x) proved in Proposition 4.2 of[START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF] for an invariant measure µ ∈ M.

Here m A denotes an upper bound of the distance function d(a, 0) on A, where 0 is a reference point of the compact set A and a runs A.

This explanation would be correct, if u λ were of class C 1 . However, since it is only continuous, a rigorous proof would require detailed a priori estimations of the super and subdifferentials of u λ ; cf, e.g.,[START_REF] Lions | Homogenization of Hamilton-Jacobi equations[END_REF].

The occupational measure µ q T can be equivalently defined by µ q T (Q) := 1 T meas{τ ∈ [0, T ], Φ τ (q) ∈ Q}, Q ∈ B(P ).

This work has been partially supported by the French National Research Agency ANR-10-BLAN 0112.

But this implies that the families (v T (•)) T >0 and (u λ (•)) λ>0 are equicontinuous (cf Proposition 3.6 in [START_REF] Quincampoix | On existence of a limit value in some non expansive optimal control problems[END_REF]), and, thus, they both converge to u ⋆ (•) uniformly on X.

This example illustrates that the equicontinuity can be obtained through various nonexpansivity conditions. The nonexpansivity condition (26) corresponds to the case, where ∆ is the Euclidean norm.

Appendix

Let us consider a flow Φ defined on a complete metric space P . Recall that a flow Φ is a function R × P ∋ (t, p) → Φ t (p) ∈ P satisfying the three following conditions: a) Φ is continuous, b) Φ(0, p) = p, for all p ∈ P , c) Φ(t + s, p) = Φ(t, Φ(s, p)), for all p ∈ P and all reals t, s.

We recall the following well-known Lemma which proof is given for the reader convenience (See, e.g., Lemma 5.4 in [START_REF] Artstein | Invariant measures of differential inclusions applied to singular perturbations[END_REF] or Proposition 4.3 in [START_REF] Artstein | Singularly perturbed ordinary differential equations with nonautonomous fast dynamics[END_REF]). Lemma 6.1 Suppose that the complete metric space P is compact. We fix q ∈ P and we define for all T > 0 the occupational measure µ q T as follows 5

If for some sequence T n → ∞ we have the weak convergence of µ q Tn to some measure µ, then µ is an invariant measure for the flow Φ.

Proof : In order to prove that µ is an invariant measure, we fix any ϕ ∈ C(P ) and t > 0, and we show that We remark that, thanks to the flow condition c) and a change of variable,

Thus,

Finally, passing in the above relation to the limit as n → +∞, we obtain with

QED

For discounted occupational measures, we have the following result which proof is very similar to that of the preceding Lemma. Lemma 6.2 Let P be a compact complete metric space. For all q ∈ P and λ > 0 we define the occupational measure ν q λ by the following relation:

e -λs ϕ(Φ s (q))ds, for all ϕ ∈ C(P ).

Then, if for some sequence λ n → 0 + we have the weak convergence of ν q λn to some measure ν, then this measure ν is invariant for the flow Φ.