Selim Bertrand Mathieu

David Griffin

Toufik Ahmed

Ribera Oriol

Prats

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 1

Keywords: cooperation, ISP, overlay, media applications, P2P, network services. I

In recent years there has been a trend for more user participation in Internet-based services leading to an explosion of user-generated, tailored and reviewed content and social networking-based applications. The next generation of applications will continue this trend and be more interactive and distributed, putting the users at the centre of a massively multi-participant communications environment. Furthermore, future networked media environments will be high-quality, multi-sensory, multi-viewpoint and multi-streamed, relying on HD and 3D video. These applications will place unprecedented demands on networks for high capacity, low-latency, and low-loss communication paths between unpredictable and arbitrarily large meshes of network endpoints. It would require operators to upgrade the capacity of their infrastructure by several orders of magnitude to ensure end-to-end quality of service. Instead, we advocate the development of intelligent cross-layer techniques that, on the one hand, will mobilise network and user resources to provide network capacity where it is needed, and, on the other hand, will ensure that the applications adapt themselves and the content they are conveying to available network resources, considering core network capacity as well as the heterogeneity of access network and end-device capabilities. This paper presents an architecture that enables this level of cooperation between the application providers, the users and the communications networks, so that the QoE of the application should be improved and the network traffic optimised.

adequately dimensioned and carefully positioned by service providers in large data centres at strategic locations across the Internet to ensure an adequate Quality of Experience for their users. These deployments require significant investment to maintain; they cannot expand beyond the selected locations and have limited flexibility to adapt to demand variations over time.

The next generation of applications will continue the trend of user-centricity where users are not just seen as consumers of a product or service but are active participants in providing it. They will be more interactive and distributed, putting the users at the centre of a massively multi-participant communications environment where they can interact in real-time with other users and provider resources, to provide and access a seamless mixture of live, archived and background material. Furthermore, future networked media environments will be high-quality, multi-sensory, multi-viewpoint and multi-streamed, relying on HD and 3D video. These applications will place unprecedented demands on networks for high capacity, low-latency, and low-loss communication paths between unpredictable and arbitrarily large meshes of network endpoints, distributed around the entire globe, putting additional pressure for upload capacity in access networks.

If the entire burden of supporting high volumes of HD/3D multi-media streams is pushed to the ISPs with highly concurrent unicast flows this would require operators to upgrade the capacity of their infrastructure by several orders of magnitude to ensure end-to-end quality of service between arbitrary end points.

Rather than simply throwing bandwidth at the problem, we advocate the development of intelligent cross-layer techniques that, on the one hand, will mobilise network and user resources to provide network capacity where it is needed, and, on the other hand, will ensure that the applications adapt themselves and the content they are conveying to available network resources, considering core network capacity as well as the heterogeneity of access network and end-device capabilities. Meeting these challenges requires a previously unseen amount of cooperation between application providers, users and the communications networks that will transport the application data. This paper presents an architecture that enables this level of cooperation between the actors and elaborates on the related interactions. Section II presents some example applications to illustrate the benefits of collaboration between the applications and the

Improving end-to-end QoE via close cooperation between applications and ISPs

Bertrand Mathieu, Selim Ellouze, Nico Schwan, David Griffin, Eleni Mykoniati, Toufik Ahmed, Oriol Ribera Prats network. Section III presents the big picture of our approach. Section IV elaborates on the cross-layer interactions. The functional architecture which captures the high-level building blocks of our system is detailed in Section V. Section VI of this paper describes research and standardisation initiatives related to our approach. Finally, a summary of the paper and a discussion of future work is presented in Section VII.

II. EXAMPLE APPLICATIONS

We present the following examples to illustrate the type of advanced services that can benefit from increased cooperation with underlying ISPs. Their features include low-latency and high capacity content dissemination; manipulation of distributed and streaming content such as the interpolation of multiple audio-visual streams from different viewpoints; exchange of live, multi-sensory and contextual information between participants; and the discovery and navigation of distributed content, information and users. The common denominator being the collaborative production, processing and consumption of a mixture of live, archived and background high quality media from multiple sources with demands than can outstrip the capabilities of the underlying networks unless the applications adapt themselves and content is tailored to meet network capacity and performance constraints, and/or specific network services such as multicast or in-network caching facilities are provisioned to support their efficient distribution.

One example of such an application is the multi-viewpoint coverage of sporting events as a bicycle race like the Tour de France (figure 1). In this scenario numerous fixed and mobile sources, such as professional media organisations, trackside spectators as well as the cyclists themselves can generate live audio-visual streams. As each stream shows a specific view of a potentially different subject, a potentially large number of streams with overlapping content are generated. Consumers of this content, who may be distributed around the globe using various fixed and mobile end-devices, can tailor their viewing experience by selecting from many streams according to their preference, or navigate between streams in real-time to zoom or pan around or to follow particular cyclists. The popularity of individual streams is difficult to predict and may change rapidly, therefore the creation and adaptation of efficient distribution trees or meshes to transmit the content to interested sets of users at the required quality levels presents problems that can not easily be solved by individual ISPs or the application overlay in isolation. ISPs are unaware of the popularity of dynamically changing content sources, the locations of the consumers of that content or the heterogeneous end-terminal capabilities in remote networks. From the ISPs' perspective the applications are simply generating large quantities of traffic between unpredictable locations. On the other hand application logic can track and match content sources and consumers, but efficient distribution overlays can only be built with knowledge of underlying network capabilities so that caching and adaptation functions, for example, can be placed where they are required and are most effective, or advanced network services such as regional multicast distribution can be invoked where most needed to relieve congestion and improve the Quality of Experience (QoE) for the users.

Figure 1: Bicycle use-case

A second example is a virtual meeting such as a 3D virtual conference, where a large number of participants, represented by virtual avatars, can meet and communicate via voice, avatar gestures as well as share additional multimedia data such as live video, 3D models, text and presentation slides (figure 2). Participants can move around the virtual meeting space, attend presentations, establish special interest discussion groups, socialise in coffee breaks, etc. Tracking the participants and managing their interests and participation in various activities is the responsibility of the application overlay only, however the distribution of content to various groups of users is something that benefits by the cooperation with the underlying networks. Users in the same virtual meeting room with a similar point of view need access to similar data, such as static background material as well as dynamically changing objects that need to synchronised between many consumers. The efficiency of the system can therefore be greatly improved by organising the overlay with regards to the position of content within the virtual space and making use of ISP-provided network services such as localised in-network content caching or multicast for distributing state changes of common objects to reduce latency in live updates, reduce network load and therefore costs.

Figure 2: 3D virtual conference

It can be seen that both of the above examples could generate huge amounts of data to be transmitted to sets of receivers that range from small groups to many hundreds or even millions of consumers, with some specific constraints of quality levels such as maximum latency. Our proposed solution of increased cooperation between ISPs and the overlays will assist in exchanging rich information between the application and the network so that the overlays can be organised efficiently and can adapt to network constraints (by avoiding high cost or highly congested areas, or adapting the quality of the streams to match available network capacity); or by enabling specific network services such as multicast distribution or caching to be invoked in areas of densely populated receivers.

III. OVERALL APPROACH

Because applications will be more participatory and interactive, today's model of centralised or replicated servers in large data centres is likely to be by a highly distributed model where processes run in user equipment and interwork with one another in an overlay layer and can be enhanced via the invocation of network services. In our approach, we advocate a close and strong cooperation between ISPs and overlay applications for an optimised delivery of content to end-users. This cooperation is achieved via the comprehensive, media-aware and open ENVISION interface which bridges the gap between ISPs and application overlays and aims at:

• increasing the degree of cooperation between the network layer and the applications through mutual exchange of information;

• optimising application overlay networks with respect to the capabilities of the underlying networks and the participant end users; • providing the means by which service providers can request the activation of specialised network services or resources to achieve efficient distribution of highly demanding content streams;

• enabling dynamic adaptation of the content to meet the abilities of the underlying networks and user requirements. The overall picture of the network system is illustrated in figure 3 which in particular highlights the ENVISION interface in blue. Further we can see the overlay application network on top of the Internet, consisting of nodes provided by one or more Service Provider (SP), the users themselves and, optionally, nodes of the ISPs. There will be separate overlay instances for each application. The different applications may be more or less dependent on SP nodes. At one extreme, there might be the SP acting simply as the P2P software that is run by the users.

From now on this section focuses on the overlay level while the network-level will be described in section IV via the cross-layer interactions.

Given that the applications are global in coverage, and require end-to-end traffic optimisation involving multiple hops in different networks, it is necessary to collect information from many underlying networks, via the ENVISION interface. Since data from one network may conflict with that provided by another or the quantity and quality of the information may differ from ISP to ISP, the harmonisation of the information gleaned from the ISPs is required in the overlay. The overlay could also aggregate the information collected from different ISPs, with additional data collected by measurements of the overlay itself for the global optimisation of the application. The use of this information will benefit algorithms that are needed for optimising the distribution of the content. These algorithms determine which application resources need to be involved, how to best interconnect the participants and distribute the load and the content to achieve the best QoE given the available resources.

Also content adaption services will profit from the cooperation. Until now digital coding and encoding systems have been designed following the client/server paradigm but now applications will have to deal with the fact that content may come from several sources and terminal devices with different capabilities, residing in networks that offer different service levels. Applications need to adapt and select "quality layers" with a brand new set of constraints and circumstances. Pre-adaptation of content using offline pre-generation strategies on the subset of the most popular content is inefficient and cannot meet the continuously increasing number of users' changing interest and heterogeneous terminals capabilities. For the success of future networked media the adaptation of content to the capabilities of the core and access networks, user devices and user preferences is one of the targeted objectives. The cooperation between the ISPs and the content adaptation services provided within ENVISION enables dynamic, distributed and on-the-fly content adaptation.

Content adaptation, therefore, has two dimensions: personalising and tailoring the content for the subjective viewpoint of the user(s); and encoding content in a flexible way to match the capabilities of the network (application-layer overlay as well as the ISP's layer-3 network). The latter could also allow the upload capacity of participants, especially those that act as content sources, to be boosted by making use of parallel connections across several available access networks.

A set of comprehensive application metadata is required for characterising: (1) end-users, including personal information such as name, location, content access rights, user preferences in terms of content type, quality, etc.; (2) device capabilities such as class, network interfaces, codec facility, power/CPU requirements, display capability, adaptation, caching facilities, etc.; (3) content, such as the type, characteristic, angle of view, encoding, cost, etc.

Adaptation is achieved through mechanisms which dynamically adjust the content via the use of scalable video coding, video layer coding, or adaptive streaming, being performed at source, end-user side or by intermediate nodes as appropriate to match the requirements of the set of users receiving the content while adhering to network capabilities and restrictions such as congested access links.

In order to evaluate the benefit the cooperation for both the overlay and the ISP, we are investigating models capturing the utility-maximising behaviour of overlay applications and the profit-maximising behaviour of ISPs, exploring the resulting Nash equilibriums. This study aims at proving our approach of cooperation, removing tensions between the preferences of the overlay and the ISP, such those that have been analysed from a game-theoretical perspective [START_REF] Altman | A survey on networking games in telecommunications[END_REF].

IV. CROSS-LAYER INTERACTIONS

The cross-layer interactions we propose will help future applications to provide an adequate QoE by being aware of the underlying networks' capabilities and limitations and by being able to invoke the facilities and services provided by the underlying ISP networks in a dynamic and flexible way. These networks also get information from the overlay so that they can optimise the traffic in their networks, mobilise resources and adapt to the overlay applications, eventually transparently.

Towards this aim, the exchange of rich information between the ISP and the applications is required. The ISP could inform the application about the capabilities of its network: details of access networks (type, link capabilities, coverage, etc.), current network services status (availability of multicast groups, availability of caches, etc.) as well as on other possible metrics (load of routers, bandwidth, delay, etc.). The application, in turn, could inform the ISP about its traffic demand: information related to users (e.g. user location and estimated traffic matrix) or information related to content (quantity of sources, their bitrate, adaptive coding, etc.). This information exchanged between the application and the ISP might be more or less dynamic, might be expressed in absolute or relative terms, and goes further than information reflecting the preferences and policies of the involved business entities as it is currently defined in the IETF ALTO [6] working group by also including information on objectively measured properties of the application and the network.

In addition to information exchange our approach enables future networked media applications to make use of advanced network services in a dynamic and flexible way to achieve a cost-efficient delivery of high QoE for their users. Examples of such network services include: (1) multicasting: possibly with hybrid application layer and native IP multicast since the applications will usually be spread over several ISPs, or the use of high fan-out nodes, located in the network;

(2) caching: via the use of specialised nodes, provided either by ISPs or third party entities, to optimise the delivery and save bandwidth in the network; (3) bandwidth on demand: to enable the delivery towards end-users over multiple access networks simultaneously, and provide bandwidth on demand over aggregated access networks; (4) dynamic QoS mapping: invocation and mapping of application QoS requirements network capabilities, end-users devices and access networks;

(5) ads/text insertion: in order to offer added-value services that might be monetised by network operators, (6) content adaptation: the presence of heterogeneous end-users devices and network infrastructures will require multiple versions of the same resource that can be efficiently generated using content adaptation. In our solution, the network services can be dynamically requested by overlay applications and instantiated by ISPs.

Overlay nodes are mobile and can potentially join different networks, meaning that a static configuration of the address and access details of the ENVISION interface of a single access network is insufficient. Instead we advocate the use of a dynamic protocol that allows nodes or their surrogates to discover the right ENVISION interface with respect to their current location.

V. OVERALL FUNCTIONAL ARCHITECTURE

In this section, we describe the overall functional architecture of our system (figure 4). As it is a functional architecture, we do not specify whether the building blocks are centralised or distributed or located on specific network or service provider equipment or end-user devices, nor we give recommendations regarding their implementation, such as co-locating functional blocks in the same server or distributing them over many nodes. Rather, the architecture is defined to identify the functionality required to achieve the necessary interaction between application overlays and underlying ISPs and to identify the interfaces and interactions required between the functional blocks to facilitate cross-layer optimisation.

The underlying network is composed of several Autonomous Systems (AS). A managing functionality in the network level is required in each ISP which is willing to cooperate by providing an ENVISION interface. As the aimed cooperation will allow layers to provide information and invoke services reciprocally, appropriate security mechanisms for authentication, authorisation and accounting facilities are needed. At the overlay level, this desired cooperation requires a functionality that allows information sharing. New interactive media applications offering high QoE for their users require functions such as content adaptation that could be provided by various entities including third party service providers. The interfaces were defined after studying the interactions between these functionalities delimited into blocks in the architecture. In the following paragraphs the roles and the interfaces of the individual blocks are described. From the ten main blocks that have been identified, the lower blocks, named 7 to 10, are the network part of our system (e.g. network-level, managed by ISPs), while the others blocks are at the overlay level.

At both levels two blocks are assigned for AAA (Authentication, Authorisation, and Accounting) purposes. Block 2, "AAA & Profile Management for Overlay", enables authentication of users joining the overlay, ISPs cooperating with the overlay and potentially third party services providers. Block 7, "AAA & Security Management for ISP", enables the authentication of overlays cooperating with the ISP. Both blocks offer standard AAA functions, such as accounting facilities, access authorisation, profile management, with security mechanisms and can be accessed respectively by the blocks 5 "ENVSION Overlay Network Administration" and 9 "ENVISION ISP Network Administration".

At the network level, the block 8, "ISP Network & Services Capabilities" processes, stores and provides information about the network such as the network description, the offered network services, the recommended routing, the ISP policies and preferences, the level of cooperation with the overlay, etc. Via the metadata interface M1, part of that information can be given to the block 4, "Overlay and Network information exchange".

Block 10, "ISP Network Access and Services Provisioner", manages the available network services, e.g., multicast, caches, ads insertion, etc. These services are invoked by block 9 via the command interface C3 to optimise the data distribution to answer an overlay request or independently. Results are reported back to block 9 such as the execution feedback or the status of the services. User data (data flows) passes via this block (data interface D0) for being processed and distributed.

Block 9 is responsible for the overlay management at the ISP domain (intra-ISP). Therefore it receives: (1) information about the data distribution from block 4 via M7;

(2) specific requests for further actions or specific service mobilisation from block 5 via C0; (3) network information from block 8; and (4) feedback about services execution and network status from block 10. This information is compiled and its the optimisation algorithm is executed in order to: (1) determine the appropriate actions to undertake for this distribution context; (2) mobilise network resources and services if needed; (3) provide feedback and recommendations to block 5; and (4) update the network information within block 8 via M6.

At the overlay level, block 4 manages the information provided by the ISPs and the overlay. It allows the overlay accessing the information provided by ISPs via interface C5, and additionally it allows ISPs via interface M7 to access information provided by the overlay and eventually any other information shared between them. It contains data related to the distribution context; being data relative to the overlay application (e.g., video codec, bit rate, number of sources, number of users, necessary services, etc.), relative to information provided by the ISPs, via the interface M1.

Block 6, "ENVISION Services" manages the availability and execution of the services provided at the overlay level, e.g. content adaptation, caching or multi-view aggregation (i.e. when multiple streams are retrieved and combined into one single stream and distributed again). These services could be provided by the end-users or by third-party entities and that can be added to the overlay swarm. These services are acknowledgeable to block 9 via interface M4 and commanded via interface C4. The data to be processed and distributed is received via D1.

At the upper level, block 3, "Terminal Application and Media Management" represents the end-users side and the application related features. It implements functions for: (1) content generation, consumption, search, etc; (2) data flow handling e.g. transmission, reception, synchronisation; (3) providing information about the user (e.g. interest, profile, etc.) and the terminal via interface C2; and (4) providing feedback about QoE to block 5 via interface M2.

Being the major block of the architecture, block 5, "ENVISION Overlay Network Administration" is in charge of managing the cross-domain application overlay. It therefore implements the overlay optimisation algorithms. This block is aware of the complete content distribution context, i.e.: (1) content characteristics and processing possibilities, e.g. adaptations; (2) end-user context, e.g. access network, terminal capabilities; (3) underlying network's capacities and available services, e.g. multicast and (4) available overlay services, e.g. multi-view, transcoding, caching etc. Executing the overlay optimisation algorithms based upon the content distribution context collected from the different blocks, block 9 sets up a distribution strategy by: (1) defining a distribution topology, e.g. selecting appropriate set of peers, requesting a multicast tree from an ISP, etc.; (2) defining the set of actions that will enhance the QoE, e.g. performing content adaptation for a set of end-users, activating a set of cache servers, etc.; (3) defining appropriate actions to answer eventual requests made by underlying networks, e.g. reducing the data rate for a specified region under congestion risks; and (4) sharing the valuable information about the content distribution strategy with underlying networks. Obviously some of these actions are subject to security checks performed by block 2 via interface C1.

Finally block 1, "Administration Policies Management", is a configuration function defining and updating the policies for the overlay-ISPs cooperation and its execution parameters allowing more flexibility for these operations VI. RELATED WORK Overlay applications are currently totally agnostic from the underlying network infrastructure and thus perform end-to-end measurements to gain some knowledge [START_REF] Gurbani | A survey of research on the application-layer traffic optimization problem and the need for layer cooperation[END_REF], but this is not in cooperation with the ISP and can lead to undermine routing policies of ISPs [START_REF] Keralapura | Can ISPs take the heat from overlay networks?[END_REF][3]. To avoid this, several initiatives or research projects have been initiated in the last few years related to promote a cooperation between overlay applications and underlying networks.

The P4P initiative [START_REF] Xie | P4P: Explicit Communications for Cooperative Control Between P2P and NetworkProviders[END_REF] and later the IETF ALTO working group [6] investigate how overlay networks and ISPs can cooperate to optimise traffic being generated by P2P applications and transported over the ISP's infrastructure. In their approach, the ISP is able to indicate preferences which peers should exchange data. Our solution is somehow related to ALTO, however ALTO is of limited functionality for future media services. Therefore our system proposes a much richer interface that will allow true cross-layer cooperation, both in terms of information exchange and via the possibility for overlays to dynamically request ISP's network services.

Some research work such as those investigated in [START_REF] Fortuna | QoE in Pull Based P2P-TV Systems: Overlay Topology Design Tradeoffs[END_REF] and [START_REF] Jimenez | P2P-Next: Technical and Legal Challenges[END_REF] aims at building a P2P framework or a delivery platform for Live TV. In contrast to our approach they do not consider multi-view point applications, highly interactive applications between participants in the network, and also [START_REF] Fortuna | QoE in Pull Based P2P-TV Systems: Overlay Topology Design Tradeoffs[END_REF] does not deal with content adaptation.

Research work studied P2P support in the context of massively multi-participant virtual environments such as [START_REF] Bharambe | Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-Peer Games[END_REF] for games, [START_REF] Frey | Solipsis: A Decentralized Architecture for Virtual Environments[END_REF] for virtual environments and [START_REF] Hu | FloD: A Framework for Peer-to-Peer 3D Streaming[END_REF] for 3D streaming. Those applications are close to the ones we focus on but in these solutions, the volume of the content is rather small compared to HD video from potentially a large number of sources we addressed by our approach. Also dynamic activation of network services via the cooperation between overlay and ISPs for improving the QoE is not taken into consideration.

For the definition of interfaces between the underlying network and the application or control level the well known IMS (IP Multimedia System) [START_REF]IP Multimedia Subsystem (IMS); Stage 2 (Release 7)[END_REF] designs an interface between the control entity and the network entities. However, this interface is still closed and only usable by the ISPs. Also the possible network services that might be dynamically activated are limited. In another initiative, the Parlay/OSA framework has been created some years ago for the telecommunications networks and telecom services (call control, call redirection, etc.), and has more recently been adapted for the Internet (Web services) with the Parlay/X specification [START_REF] Osa/Parlay | [END_REF]. The objectives of this group were similar as ours, however the defined interfaces depend on the network service to be activated, do not permit the exchange of dynamic information between the network and the application (in the two directions) and the supported services were limited to more traditional telecoms applications rather than media applications we aim to support. Furthermore, those two initiatives do not really address issues for massive multi-participant distributed applications as we envision.

Finally, open interfaces are promoted by the OpenFlow initiative [START_REF]OpenFlow Switch Specification, version 1.0[END_REF], but here the interface is rather related to network configurations or functions, and not to activation of network services by overlay applications.

VII. CONCLUSIONS & FUTURE WORK

In this paper, we have presented a new architecture, fostering cooperation between overlay applications and ISPs for an optimised delivery of services to end-users. Overlay algorithms are optimised thanks to information provided by ISPs and the delivery QoE is further improved via the activation of network services, provided by ISPs. The functional architecture and associated interfaces has been defined to support this level of cooperation between applications and ISPs.

While the approach presented in this article has been developed to support interactive, multi-party, high capacity media applications such as those presented in section II the architecture, the interface and the principles of cross-layer cooperation can also benefit existing applications. Content Distribution Networks (CDNs) providing Video on Demand, for example, could have greater awareness of network capabilities and could also make use of other network services provided by the ENVISION interface, such as capacity reservation for background distribution of content to CDN nodes.

The ongoing work is focused on the internal functions of each block, including the development of overlay optimisation algorithms, source selection algorithms according to context information, dynamic activation logic for network services, such as multicast (and multi-ISPs multicast) and caching/adaptation functions. Finally evaluation through both simulation and testbed experiments is planned.

Figure 3 :

 3 Figure 3: Overview of the system and its relationship with users, ISPs and overlays applications

Figure 4 :

 4 Figure 4: ENVISION Functional Architecture

ACKNOWLEDGEMENTS

This work was supported by the ENVISION project (http://www.envision-project.org), a research project partially funded by the European Union's 7th Framework Program (contract no. 248565). The authors wish to thank all project participants for their valuable comments and contributions to the work described in this article.


Robert Eymard
email: robert.eymard@u-pem.fr

Pierre Feron
email: pierre.feron@u-pem.fr

Gradient Schemes for Stokes problem

We provide a framework which encompasses a large family of conforming and nonconforming numerical schemes, for the approximation of the steady state incompressible Stokes equations with homogeneous Dirichlet's boundary conditions. Three examples (Taylor-Hood, extended MAC and Crouzeix-Raviart schemes) are shown to enter into this framework. The convergence of the scheme is proved by compactness arguments, thanks to estimates on the discrete solution that allow to prove the weak convergence to the unique continuous solution of the problem. Then strong convergence results are obtained thanks to the limit problem. An error estimate result is provided, applying on solutions with low regularity.

Under Hypotheses (H ), denoting, for (ξ (i) , χ (i) ) i=1,...,d with ξ (i) , χ (i) ∈ R d , by ξ : χ = d i=1 ξ (i) • χ (i) , (u, p) is called a weak solution to [START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF] if

         u ∈ H 1 0 (Ω) d , p ∈ L 2 0 (Ω) where L 2 0 (Ω) = {q ∈ L 2 (Ω), Ω qdx = 0}, η Ω u • vdx + Ω ∇u : ∇vdx - Ω pdivvdx = Ω f • vdx, ∀v ∈ H 1 0 (Ω) d , div(u) = 0 a.e. in Ω.
(2) Theorem 1.1 (Existence and uniqueness [START_REF] Temam | Navier-Stokes equations[END_REF]) Under Hypotheses (H ), there exists one and only one weak solution (u, p) to Problem [START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF] in the sense of Definition 1.1.

The aim of this paper is to provide a theoretical framework which includes several useful schemes for the Stokes (and the Navier-Stokes) problems. This framework is given in Section 2, as an extension of the notion of gradient schemes provided for scalar elliptic problems [START_REF] Droniou | Gradient schemes for elliptic and parabolic problems[END_REF][START_REF] Droniou | Gradient schemes: a generic framework for the discretisation of linear, nonlinear and nonlocal elliptic and parabolic equations[END_REF][START_REF] Eymard | Gradient schemes for the Stefan problem[END_REF][START_REF] Eymard | Gradient scheme approximations for diffusion problems[END_REF][START_REF] Eymard | Gradient schemes for two-phase flow in heterogeneous porous media and Richards equation[END_REF]. Among the schemes which are included in this framework, we briefly present in Section 3 the Taylor-Hood scheme, an extended version [START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF] of the Marker-And-Cell (MAC) scheme [START_REF] Harlow | Numerical calculation of time-dependent viscous incompressible flow of fluid with a free surface[END_REF][START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF][START_REF] Wesseling | Principles of Computational Fluid Dynamics[END_REF] and the Crouzeix-Raviart scheme [START_REF] Crouzeix | Conforming and nonconforming finite element methods for solving the stationary Stokes equations[END_REF] (these three schemes are useful in many industrial applications). In Section 4, we provide the convergence result for this general framework, followed by an error estimate result, also providing a proof for the convergence of the general scheme, but needing slightly more regularity than the convergence result. 1. XD,0 is a vector space on R with finite dimension.

Gradient scheme

2. YD is a vector space on R with finite dimension.

3. The linear mapping ΠD : XD,0 → L 2 (Ω) d is the reconstruction of the approximate velocity field.

4. The linear mapping χD : YD → L 2 (Ω) is the reconstruction of the approximate pressure, and must be chosen such that χD • L 2 (Ω) is a norm on YD . We then denote YD,0 = {q ∈ YD , Ω χD qdx = 0}.

The linear mapping

∇D : XD,0 → L 2 (Ω)
CD = max v∈X D,0 , v D =1 ΠD v L 2 (Ω) + max v∈X D,0 , v D =1 divD v L 2 (Ω) , βD = min{ max v∈X D,0 , v D =1 Ω
χD q divD v dx, q ∈ YD,0 such that χD q L 2 (Ω) = 1}.

A sequence (Dm) m∈N of gradient discretisation is said to be coercive if there exist CP ∈ R+ such that CD m ≤ CP (discrete Poincaré inequality and control of discrete divergence) and if there exists β ∈ (0, +∞) such that βD m ≥ β (discrete LBB condition), for all m ∈ N. Definition 2.3 (Consistency) Let D be a gradient discretisation in the sense of definition 2.1, and let ID :

H 1 0 (Ω) d → XD,0, SD : H 1 0 (Ω) d → [0, +∞), ID : L 2 0 (Ω) → YD,0 and SD : L 2 0 (Ω) → [0, +∞) be defined by ∀ϕ ∈ H 1 0 (Ω) d , ∀v ∈ XD,0, ED (v, ϕ) = ΠD v -ϕ L 2 (Ω) d + ∇D v -∇ϕ L 2 (Ω) d×d + divD v -divϕ L 2 (Ω) , ∀ϕ ∈ H 1 0 (Ω) d , ID (ϕ) = argmin v∈X D,0 ED (v, ϕ), SD (ϕ) = ED (ID (ϕ), ϕ),
and ∀ψ ∈ L 2 0 (Ω) , ID (ψ) = argmin z∈Y D,0 χD z -ψ L 2 (Ω) , SD (ψ) = χD ID (ψ) -ψ L 2 (Ω) .
A sequence (Dm) m∈N of gradient discretisation is said to be consistent if, for all ϕ ∈ H 1 0 (Ω) d , SD m (ϕ) tends to 0 when m → ∞ and for all ψ ∈ L 2 0 (Ω), SD m (ψ) tends to 0 as m → ∞. Definition 2.4 (Limit-conformity) Let D be a gradient discretisation in the sense of definition 2.1, and let WD :

H div (Ω) d → [0, +∞) and WD : H 1 (Ω) → [0, +∞) be respectively defined by ∀ϕ ∈ H div (Ω) d , WD (ϕ) = max v∈X D,0 , v D =1 Ω (∇D v : ϕ + ΠD v • divϕ) dx , ∀ψ ∈ H 1 (Ω), WD (ψ) = max v∈X D,0 , v D =1 Ω (ΠD v • ∇ψ + ψ divD v)dx .
A sequence (Dm) m∈N of gradient discretisation is said to be limit-conforming if, for all ϕ ∈ H div (Ω) d , WD m (ϕ) tends to 0 when m → ∞ and if, for all ψ ∈ H 1 (Ω), WD m (ψ) tends to 0 as m → ∞.

Under Hypotheses (H ), let D be a gradient discretisation of Ω in the sense of definition 2.1. The gradient scheme for the approximation of Problem ( 1) is given by

         (u, p) ∈ XD,0 × YD,0, ∀v ∈ XD,0, η Ω ΠD u • ΠD vdx + Ω ∇D u : ∇D vdx - Ω χD p divD vdx = Ω f • ΠD vdx, Ω divD uχD q dx = 0, ∀q ∈ YD,0. (3)

Examples of gradient schemes for the Stokes problem

Conforming Taylor-Hood scheme For this example, XD,0 (resp. YD ) is the vector space of the degrees of freedom for the velocity (resp. the pressure) in the Taylor-Hood element, ΠD and χD are obtained through the finite element basis functions, and we define the conforming operators ∇D = ∇ • ΠD and divD = div • ΠD (this implies that WD and WD are identically null).

The extended MAC scheme for non conforming meshes

This example is detailed in [START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF]. We consider 2D or 3D meshes of Ω, which are such that all internal faces have their normal vector parallel to one of the basis vector e (k) of the space R d , for some k = 1, . . . , d (see an example at left part of Figure 1). Note that on the other hand, the external faces need not be aligned with the axes: they are only assumed to be planar. Hence curved boundaries may be meshed with such grids, by using local refinement close to the boundaries, such as in Figure 1. These meshes are used for the approximation of the pressure and of the divergence operator. Then the gradient scheme is defined as follows.

1. XD,0 is the vector space on R of all families of normal velocities to all internal edges of the mesh (see the left part of Figure 1).

2. YD is the vector space on R of all families of values in the cells of the mesh.

3. The linear mapping ΠD : XD,0 → L 2 (Ω) d is the reconstruction of the approximate velocity field, defined as the piecewise constant value of each component of the velocity in the corresponding Voronoï cells (the right part of Figure 1 presents the grid for the horizontal velocity).

4. The linear mapping χD : YD → L 2 (Ω) is the piecewise constant reconstruction of the approximate pressure in the pressure mesh.

5. The linear mapping ∇D : XD,0 → L 2 (Ω) d×d is the discrete gradient operator, obtained as the gradient of the P 1 reconstruction of each component of the velocity in the corresponding triangular grid (the medium part of Figure 1 shows this triangular grid for the horizontal velocity, joining the barycenters of the vertical edges of the pressure grid).

6. The linear mapping divD : XD,0 → L 2 (Ω) is the discrete divergence operator, simply computed as the piecewise constant value in the cells of the pressure grid obtained through the balance of the normal velocities integrated over the faces of the mesh.

The Crouzeix-Raviart scheme

We consider 2D or 3D simplicial meshes of Ω (triangles in 2D, tetrahedra in 3D). Then the Crouzeix-Raviart scheme [START_REF] Crouzeix | Conforming and nonconforming finite element methods for solving the stationary Stokes equations[END_REF] can be defined as a gradient scheme by the following way:

1. XD,0 is the vector space on R of all families of vectors of R d at the center of all internal faces of the mesh.

2. YD is the vector space on R of all families of values in the simplices.

3. The linear mapping ΠD : XD,0 → L 2 (Ω) d is the nonconforming piecewise affine reconstruction of each component of the velocity.

4. The linear mapping χD : YD → L 2 (Ω) is the piecewise constant reconstruction in the simplices.

5. The linear mapping ∇D : XD,0 → L 2 (Ω) d×d is the so-called "broken gradient" of the velocity, defined as the piecewise constant field of the gradient of the affine components of the velocity in all the simplices. 6. The linear mapping divD : XD,0 → L 2 (Ω) is the discrete divergence operator, simply computed as the piecewise constant value in the cells of the pressure grid obtained through the balance of the normal velocities integrated over the faces of the mesh.

Convergence results

u D ≤ C1 f L 2 (Ω) d and χD p L 2 (Ω) ≤ C1 f L 2 (Ω) d . ( 4
)
As an immediate consequence, there exists one and only one (u, p), solution to [START_REF] Droniou | Gradient schemes for elliptic and parabolic problems[END_REF].

Proof. One first set v = u in (3). This immediately provides the left part of (4), thanks to the Cauchy-Schwarz inequality and to Definition 2.2. Then one selects some v ∈ XD,0 such that v D = 1 and βD χD p L 2 (Ω) ≤ Ω χD p divD v dx. Choosing this v in (3) leads to the right part of (4). The existence and uniqueness of (u, p) results from the fact that it is the solution of a square linear system, with kernel reduced to (0, 0). ) m∈N be a sequence of gradient discretisation on Ω in the sense of definition 2.1, which is consistent, limitconforming and coercive in the sense of the above definitions. Let (um, pm) be the unique solution of the scheme (3) for D = Dm. Then, as m → ∞,

• Π D (m) um converges to u in L 2 (Ω) d , • ∇ D (m) um converges to ∇u in L 2 (Ω) d×d , • χ D (m) pm converges to p in L 2 (Ω).
Proof. In the following proof, we use simplified notations for the integrals for shortness reasons, and we replace all indices D (m) by m, hence denoting by D (m) = (Xm, Πm, ∇m, Ym, χm, divm), and the values provided by Definition 2.2 are denoted by Cm and βm ≥ β > 0. We first observe that, thanks to Lemma 4.1 and to the limit-conformity property, up to a subsequence, there exists u ∈ H 1 0 (Ω) d and p ∈ L 2 0 (Ω) such that weak convergence properties hold for the discrete reconstructions of the approximate velocity, its approximate gradient, its approximate divergence, and the approximate pressure. Then, for any test function v ∈ H 1 0 (Ω) d , we set in (3) v = Imv and q = Im(divu) (we have divu ∈ L 2 0 (Ω) since Ω divu = ∂Ω u • n = 0, see Definition 2.4). Then we pass to the limit m → ∞ in the scheme. We get, by weak/strong convergence, that Ω (divu) 2 = 0 and that (2) holds. This proves that (u, p) is the unique weak solution of the incompressible steady Stokes problem (1). The uniqueness of the limit shows that the whole sequence converges.

Passing to the limit in the scheme with v = um shows the convergence of the norm of the discrete velocity gradient ∇mum to its continuous counterpart ∇u. This shows the strong convergence of the gradient. The coercivity property and interpolation of the limit shows that the reconstruction of the velocity Πmum is strongly convergent. Let us now turn to the convergence of the approximate pressure in L 2 (Ω). We select vm ∈ Xm such that vm D (m) = 1 and

β χm( Imp -pm) L 2 (Ω) ≤ Ω χm( Imp -pm)divmvm.
Letting v = vm in the scheme, we get

η Ω Πmum • Πmvm + Ω ∇mum : ∇mvm - Ω χmpm divmvm = Ω f • Πmvm.
Combining the two above relations and using the triangle inequality, we deduce

β p -χmpm L 2 (Ω) ≤ β χm Imp -p L 2 (Ω) + Ω f • Πmvm + Ω χm Imp divmvm -η Ω Πmum • Πmvm - Ω ∇mum : ∇mvm.
Up to the extraction of a subsequence, we may assume that there exists v ∈ H 1 0 (Ω) d such that the following weak convergences hold in L 2 : Πmvm to v, ∇mvm to ∇v and divmvm to divv. Using the (already proved) strong convergence properties for the velocity, we may now pass to the limit m → ∞, since all integrals involve weak/strong convergence properties. We get

β lim sup m→∞ p -χmpm L 2 (Ω) ≤ Ω f • v + Ω p divv -η Ω u • v - Ω ∇u : ∇v.
It now suffices to use the fact that we already proved that (u, p) is a weak solution to the Stokes equation. We then get that the right hand side of the previous inequality vanishes, which shows the convergence in L 2 for this subsequence. Using a standard uniqueness argument, we deduce that the whole sequence converges.

The following error estimate needs more regularity hypotheses than that which have been done for the above convergence theorem. Theorem 4.2 Under Hypotheses (H ), Let (u, p) be the unique solution of the incompressible steady Stokes problem [START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF] in the sense of definition 1.1 such that p ∈ H 1 (Ω) (which implies that ∇u ∈ H div (Ω) d ). Let D be a gradient discretisation on Ω in the sense of definition 2.1 such that βD > 0 (see Definition 2.2). Let (u, p) ∈ VD be the unique solution of the scheme [START_REF] Droniou | Gradient schemes for elliptic and parabolic problems[END_REF]. Then there exists Ce, which increasingly depends on only η, CD and 1 β D , such that there holds

u -ΠD u D + p -χD p L 2 (Ω) ≤ Ce WD (∇u) + WD (p) + SD (u) + SD (p) .
Proof. Under the hypotheses of the theorem, since -∆u = -div(∇u) = f -∇p -ηu a.e., we get that ∇u ∈ H div (Ω) d . Using this expression in WD (∇u) and using (3), we can write, for any v ∈ XD,0, We then get, from (5), and using Definition 2.

Now setting v = ID u -uD in (5) and using Ω divD uD χD q = 0 for all q ∈ YD , we can write Thanks to [START_REF] Eymard | Gradient schemes for two-phase flow in heterogeneous porous media and Richards equation[END_REF] and to the inequality ab ≤ 1 2 a 2 + 1 2 b 2 , the above inequality yields the existence of C1, increasing function of 1/βD , CD and η, such that ID u -uD D ≤ C1εD (u, p). The conclusion follows, thanks to the definitions of ID u and ID p, to Definition 2.2, to the triangle inequality and to the use of [START_REF] Eymard | Gradient schemes for two-phase flow in heterogeneous porous media and Richards equation[END_REF].

1

  Incompressible steady Stokes problem We consider the incompressible steady Stokes problem: u represents the velocity field and p the pressure, under the following hypotheses (called Hypotheses H in the following): Ω an open bounded Lipschitz domain of R d with d = 2 or 3, f ∈ L 2 (Ω) d and η ∈ [0, +∞). Definition 1.1

Definition 2 . 1 (

 21 Gradient Discretisation for the Stokes problem) A gradient discretisation D for the Stokes problem with homogeneous Dirichlet's boundary conditions, is defined by D = (XD,0, ΠD , ∇D , YD , χD , divD ), with:

Figure 1 :

 1 Figure 1: Left: pressure grid. Middle: Zoom on the top right triangular velocity grid, used for the gradient reconstruction of the horizontal velocity (pressure grid recalled by discontinuous lines). Right: Voronoï cells used for the velocity reconstruction.

Lemma 4 . 1 (

 41 Estimates) Under Hypotheses (H ), Let D a gradient discretisation of Ω in the sense of definition 2.1 such that βD > 0 (see Definition 2.2). Let (u, p) be a solution of[START_REF] Droniou | Gradient schemes for elliptic and parabolic problems[END_REF]. Then, there exists C1 ≥ 0, only depending on Ω, et d, η, and any C ≥ CD + 1 β D such that:

Theorem 4 . 1 (

 41 Convergence of the scheme) Under Hypotheses (H ), Let (u, p) the unique weak solution of the incompressible steady Stokes problem[START_REF] Chénier | An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations[END_REF] in the sense of definition 1.1 and let (D(m)

Ω 5 )

 5 η(u -ΠD uD ) • ΠD v + (∇u -∇D uD ) : ∇D v + (χD pD divD v + ∇p • ΠD v) dx ≤ WD (∇u) v D .Then, introducing the expression of WD (p), we getΩ η(u -ΠD uD ) • ΠD v + (∇u -∇D uD ) : ∇D v + (χD pD -p) divD v dx ≤ (WD (∇u) + WD (p)) v D .We now use the values ID u and ID p introduced in Definition 2.3, and we denote by εD (u, p) = WD (∇u) + WD (p) + SD (u) + SD (p). We can then writeΩ η(ΠD ID u -ΠD uD ) • ΠD v + (∇D ID u -∇D uD ) : ∇D v dx + Ω (χD pD -χD ID p) divD v ≤ (1 + η)εD (u, p) vD . (Thanks to Definition 2.2, let us now take v ∈ XD,0 such that v D = 1 and Ω χD (pD -ID p) divD v dx ≥ βD χD (pD -ID p) L 2 (Ω) .

ID u -uD 2

 2 D + Ω χD (pD -ID p) divD ID u dx ≤ (1 + η)εD (u, p) ID u -uD D , which implies ID u -uD 2 D ≤ (1 + η)εD (u, p) ID u -uD D + SD (u) χD (pD -ID p) L 2 (Ω) .

  2, χD (pD -ID p) L 2 (Ω) ≤

	1 + η βD	εD (u, p) +	1 + ηCD βD	ID u -uD D .